mcs/class/Mono.CodeContracts/Mono.CodeContracts.Static.Analysis.HeapAnalysis/HeapAnalysis.cs

   1 //
   2 // HeapAnalysis.cs
   3 //
   4 // Authors:
   5 //      Alexander Chebaturkin (chebaturkin@gmail.com)
   6 //
   7 // Copyright (C) 2011 Alexander Chebaturkin
   8 //
   9 // Permission is hereby granted, free of charge, to any person obtaining
  10 // a copy of this software and associated documentation files (the
  11 // "Software"), to deal in the Software without restriction, including
  12 // without limitation the rights to use, copy, modify, merge, publish,
  13 // distribute, sublicense, and/or sell copies of the Software, and to
  14 // permit persons to whom the Software is furnished to do so, subject to
  15 // the following conditions:
  16 //
  17 // The above copyright notice and this permission notice shall be
  18 // included in all copies or substantial portions of the Software.
  19 //
  20 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  21 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  22 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  23 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  24 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  25 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  26 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  27
  28 using System;
  29 using System.Collections.Generic;
  30 using System.IO;
  31 using Mono.CodeContracts.Static.AST;
  32 using Mono.CodeContracts.Static.AST.Visitors;
  33 using Mono.CodeContracts.Static.Analysis.HeapAnalysis.SymbolicGraph;
  34 using Mono.CodeContracts.Static.ControlFlow;
  35 using Mono.CodeContracts.Static.DataFlowAnalysis;
  36 using Mono.CodeContracts.Static.DataStructures;
  37 using Mono.CodeContracts.Static.Providers;
  38
  39 namespace Mono.CodeContracts.Static.Analysis.HeapAnalysis {
  40         class HeapAnalysis : IAnalysis<APC, Domain, IILVisitor<APC, int, int, Domain, Domain>, Dummy> {
  41                 private readonly Dictionary<Pair<APC, APC>, IImmutableMap<SymbolicValue, Sequence<SymbolicValue>>> forwardRenamings =
  42                         new Dictionary<Pair<APC, APC>, IImmutableMap<SymbolicValue, Sequence<SymbolicValue>>> ();
  43
  44                 public readonly Dictionary<APC, IMergeInfo> MergeInfoCache = new Dictionary<APC, IMergeInfo> ();
  45                 public readonly DoubleDictionary<APC, APC, Dummy> RenamePoints = new DoubleDictionary<APC, APC, Dummy> ();
  46                 private readonly ICodeLayer<int, int, IStackContextProvider, Dummy> stackLayer;
  47                 private IFixPointInfo<APC, Domain> fixPointInfo;
  48
  49                 public HeapAnalysis (ICodeLayer<int, int, IStackContextProvider, Dummy> stackLayer)
  50                 {
  51                         this.stackLayer = stackLayer;
  52                 }
  53
  54                 public IStackContextProvider StackContextProvider
  55                 {
  56                         get { return this.stackLayer.ILDecoder.ContextProvider; }
  57                 }
  58
  59                 public IMetaDataProvider MetaDataProvider
  60                 {
  61                         get { return this.stackLayer.MetaDataProvider; }
  62                 }
  63
  64                 public IContractProvider ContractProvider
  65                 {
  66                         get { return this.stackLayer.ContractProvider; }
  67                 }
  68
  69                 public Method CurrentMethod
  70                 {
  71                         get { return this.StackContextProvider.MethodContext.CurrentMethod; }
  72                 }
  73
  74                 IILVisitor<APC, int, int, Domain, Domain> IAnalysis<APC, Domain, IILVisitor<APC, int, int, Domain, Domain>, Dummy>.
  75                         GetVisitor ()
  76                 {
  77                         return GetVisitor ();
  78                 }
  79
  80                 public Domain Join (Pair<APC, APC> edge, Domain newstate, Domain prevstate, out bool weaker, bool widen)
  81                 {
  82                         if (DebugOptions.Debug)
  83                         {
  84                                 Console.WriteLine ("-----OPT Join at {0}", edge);
  85                                 Console.WriteLine ("-----Existing state:");
  86                                 prevstate.Dump (Console.Out);
  87                                 Console.WriteLine ("-----New state:");
  88                                 newstate.Dump (Console.Out);
  89                         }
  90
  91                         IMergeInfo mi;
  92                         Domain domain = prevstate.Join (newstate, widen, out weaker, out mi);
  93                         if (weaker) {
  94                                 IMergeInfo mi2;
  95                                 if (this.MergeInfoCache.TryGetValue (edge.Value, out mi2) && mi2 == null)
  96                                         this.MergeInfoCache [edge.Value] = mi;
  97                         } else
  98                                 this.MergeInfoCache [edge.Value] = mi;
  99
 100                         if (DebugOptions.Debug)
 101                         {
 102                                 Console.WriteLine ("-----Result state: changed = {0} (widen = {1})", weaker ? 1 : 0, widen ? 1 : 0);
 103                                 domain.Dump (Console.Out);
 104                                 Console.WriteLine ("----------------------------------------------");
 105                         }
 106
 107                         return domain;
 108                 }
 109
 110                 public Domain ImmutableVersion (Domain arg)
 111                 {
 112                         return arg.ImmutableVersion ();
 113                 }
 114
 115                 public Domain MutableVersion (Domain arg)
 116                 {
 117                         if (arg.IsBottom)
 118                                 return arg;
 119                         return arg.Clone ();
 120                 }
 121
 122                 public Domain EdgeConversion (APC @from, APC to, bool isJoinPoint, Dummy data, Domain state)
 123                 {
 124                         if (isJoinPoint) {
 125                                 this.RenamePoints [from, to] = Dummy.Value;
 126                                 if (!this.MergeInfoCache.ContainsKey (to))
 127                                         this.MergeInfoCache.Add (to, null);
 128                         }
 129
 130                         if (DebugOptions.Debug)
 131                         {
 132                                 Console.WriteLine ("----Edge conversion on {0}->{1}------", from, to);
 133                                 state.Dump (Console.Out);
 134                                 Console.WriteLine ("-------------------------------------");
 135                         }
 136
 137                         return state;
 138                 }
 139
 140                 public bool IsBottom (APC pc, Domain state)
 141                 {
 142                         return state.IsBottom;
 143                 }
 144
 145                 public Predicate<APC> SaveFixPointInfo (IFixPointInfo<APC, Domain> fixPointInfo)
 146                 {
 147                         this.fixPointInfo = fixPointInfo;
 148                         return pc => true;
 149                 }
 150
 151                 public void Dump (Pair<Domain, TextWriter> pair)
 152                 {
 153                         pair.Key.Dump (pair.Value);
 154                 }
 155
 156                 private IILVisitor<APC, int, int, Domain, Domain> GetVisitor ()
 157                 {
 158                         return new AnalysisDecoder (this);
 159                 }
 160
 161                 public Domain InitialValue ()
 162                 {
 163                         return new Domain (this);
 164                 }
 165
 166                 public IILDecoder<APC, SymbolicValue, SymbolicValue, IValueContextProvider<SymbolicValue>, IImmutableMap<SymbolicValue, Sequence<SymbolicValue>>>
 167                         GetDecoder<Context>(IILDecoder<APC, int, int, Context, Dummy> underlying)
 168                         where Context : IStackContextProvider
 169                 {
 170                         return new ValueDecoder<Context> (this, underlying);
 171                 }
 172
 173                 public bool IsUnreachable (APC pc)
 174                 {
 175                         Domain domain;
 176                         if (!this.fixPointInfo.PreStateLookup (pc, out domain) || domain.IsBottom)
 177                                 return true;
 178
 179                         return false;
 180                 }
 181
 182                 public IImmutableMap<SymbolicValue, Sequence<SymbolicValue>> EdgeRenaming (Pair<APC, APC> edge, bool isJoinPoint)
 183                 {
 184                         IImmutableMap<SymbolicValue, Sequence<SymbolicValue>> forwardRenaming;
 185
 186                         if (this.forwardRenamings.TryGetValue (edge, out forwardRenaming))
 187                                 return forwardRenaming;
 188
 189                         IImmutableMap<SymbolicValue, Sequence<SymbolicValue>> renaming = null;
 190                         Domain afterBegin;
 191                         PostStateLookup (edge.Key, out afterBegin);
 192                         if (afterBegin == null || afterBegin.IsBottom)
 193                                 return null;
 194                         Domain beforeEnd;
 195                         PreStateLookup (edge.Value, out beforeEnd);
 196                         if (beforeEnd != null) {
 197                                 IImmutableMap<SymValue, Sequence<SymValue>> forward;
 198                                 if (!TryComputeFromJoinCache (afterBegin, beforeEnd, edge.Value, out forward)) {
 199                                         IImmutableMap<SymValue, SymValue> backward;
 200                                         if (!afterBegin.LessEqual (beforeEnd, out forward, out backward))
 201                                                 throw new InvalidOperationException ("Should never happen");
 202                                         if (isJoinPoint && forward == null)
 203                                                 forward = afterBegin.GetForwardIdentityMap ();
 204                                 }
 205                                 if (forward != null) {
 206                                         renaming = ImmutableIntKeyMap<SymbolicValue, Sequence<SymbolicValue>>.Empty (SymbolicValue.GetUniqueKey);
 207                                         foreach (SymValue sv in forward.Keys) {
 208                                                 Sequence<SymbolicValue> targets = null;
 209                                                 foreach (SymValue target in forward [sv].AsEnumerable ())
 210                                                         targets = targets.Cons (new SymbolicValue (target));
 211                                                 if (targets != null)
 212                                                         renaming = renaming.Add (new SymbolicValue (sv), targets);
 213                                         }
 214                                 }
 215                         }
 216                         this.forwardRenamings.Add (edge, renaming);
 217                         return renaming;
 218                 }
 219
 220                 private bool TryComputeFromJoinCache (Domain inDomain, Domain outDomain, APC joinPoint, out IImmutableMap<SymValue, Sequence<SymValue>> forward)
 221                 {
 222                         forward = null;
 223                         IMergeInfo mi;
 224                         if (this.MergeInfoCache.TryGetValue (joinPoint, out mi) && mi != null && outDomain.IsResultEGraph (mi)) {
 225                                 if (inDomain.IsGraph1 (mi)) {
 226                                         forward = mi.ForwardG1Map;
 227                                         return true;
 228                                 }
 229                                 if (inDomain.IsGraph2 (mi)) {
 230                                         forward = mi.ForwardG2Map;
 231                                         return true;
 232                                 }
 233                         }
 234                         return false;
 235                 }
 236
 237                 public Domain GetPreState (APC pc)
 238                 {
 239                         Domain domain;
 240                         PreStateLookup (pc, out domain);
 241                         return domain;
 242                 }
 243
 244                 public bool PreStateLookup (APC pc, out Domain ifFound)
 245                 {
 246                         return this.fixPointInfo.PreStateLookup (pc, out ifFound);
 247                 }
 248
 249                 public bool PostStateLookup (APC pc, out Domain ifFound)
 250                 {
 251                         return this.fixPointInfo.PostStateLookup (pc, out ifFound);
 252                 }
 253         }
 254 }