mcs/class/Mono.CodeContracts/Mono.CodeContracts.Static.ControlFlow.Subroutines/SubroutineBase.cs

   1 //
   2 // SubroutineBase.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
  29 using System;
  30 using System.Collections.Generic;
  31 using System.IO;
  32 using System.Linq;
  33 using Mono.CodeContracts.Static.AST;
  34 using Mono.CodeContracts.Static.Analysis;
  35 using Mono.CodeContracts.Static.ControlFlow.Blocks;
  36 using Mono.CodeContracts.Static.ControlFlow.Subroutines.Builders;
  37 using Mono.CodeContracts.Static.DataStructures;
  38 using Mono.CodeContracts.Static.Providers;
  39
  40 namespace Mono.CodeContracts.Static.ControlFlow.Subroutines {
  41         abstract class SubroutineBase<Label> : Subroutine, IGraph<CFGBlock, Dummy>, IStackInfo, IEdgeSubroutineAdaptor {
  42                 private const int UnusedBlockIndex = Int32.MaxValue - 1;
  43                 protected readonly Label StartLabel;
  44                 public readonly SubroutineFacade SubroutineFacade;
  45
  46                 private readonly Dictionary<Pair<CFGBlock, CFGBlock>, LispList<Pair<EdgeTag, Subroutine>>> edge_subroutines
  47                         = new Dictionary<Pair<CFGBlock, CFGBlock>, LispList<Pair<EdgeTag, Subroutine>>> ();
  48
  49                 private readonly BlockWithLabels<Label> entry;
  50                 private readonly BlockWithLabels<Label> entry_after_requires;
  51                 private readonly BlockWithLabels<Label> exception_exit;
  52                 private readonly BlockWithLabels<Label> exit;
  53
  54                 private readonly List<Edge<CFGBlock, EdgeTag>> successors = new List<Edge<CFGBlock, EdgeTag>> ();
  55                 protected int BlockIdGenerator;
  56                 protected Dictionary<Label, BlockWithLabels<Label>> LabelsThatStartBlocks = new Dictionary<Label, BlockWithLabels<Label>> ();
  57
  58                 private CFGBlock[] blocks;
  59                 private DepthFirst.Visitor<CFGBlock, Dummy> edge_info;
  60                 private EdgeMap<EdgeTag> predecessor_edges;
  61                 private EdgeMap<EdgeTag> successor_edges;
  62
  63                 protected SubroutineBase (SubroutineFacade subroutineFacade)
  64                 {
  65                         this.SubroutineFacade = subroutineFacade;
  66                         this.entry = new EntryBlock<Label> (this, ref this.BlockIdGenerator);
  67                         this.exit = new EntryExitBlock<Label> (this, ref this.BlockIdGenerator);
  68                         this.exception_exit = new CatchFilterEntryBlock<Label> (this, ref this.BlockIdGenerator);
  69                 }
  70
  71                 protected SubroutineBase (SubroutineFacade SubroutineFacade,
  72                                           Label startLabel, SubroutineBuilder<Label> builder)
  73                         : this (SubroutineFacade)
  74                 {
  75                         this.StartLabel = startLabel;
  76                         Builder = builder;
  77                         CodeProvider = builder.CodeProvider;
  78                         this.entry_after_requires = GetTargetBlock (startLabel);
  79
  80                         AddSuccessor (this.entry, EdgeTag.Entry, this.entry_after_requires);
  81                 }
  82
  83                 public override bool HasContextDependentStackDepth
  84                 {
  85                         get { return true; }
  86                 }
  87
  88                 public override bool HasReturnValue
  89                 {
  90                         get { return false; }
  91                 }
  92
  93                 public override int StackDelta
  94                 {
  95                         get { return 0; }
  96                 }
  97
  98                 protected SubroutineBuilder<Label> Builder { get; set; }
  99
 100                 public override DepthFirst.Visitor<CFGBlock, Dummy> EdgeInfo
 101                 {
 102                         get { return this.edge_info; }
 103                 }
 104
 105                 public ICodeProvider<Label> CodeProvider { get; private set; }
 106
 107                 public override int BlockCount
 108                 {
 109                         get { return this.blocks.Length; }
 110                 }
 111
 112                 public override IEnumerable<CFGBlock> Blocks
 113                 {
 114                         get { return this.blocks; }
 115                 }
 116
 117                 public override string Name
 118                 {
 119                         get { return "SR" + Id; }
 120                 }
 121
 122                 public override EdgeMap<EdgeTag> SuccessorEdges
 123                 {
 124                         get { return this.successor_edges; }
 125                 }
 126
 127                 public override EdgeMap<EdgeTag> PredecessorEdges
 128                 {
 129                         get
 130                         {
 131                                 if (this.predecessor_edges == null)
 132                                         this.predecessor_edges = this.successor_edges.Reverse ();
 133                                 return this.predecessor_edges;
 134                         }
 135                 }
 136
 137                 #region Main Blocks
 138                 public override CFGBlock Entry
 139                 {
 140                         get { return this.entry; }
 141                 }
 142
 143                 public override CFGBlock EntryAfterRequires
 144                 {
 145                         get
 146                         {
 147                                 if (this.entry_after_requires != null)
 148                                         return this.entry_after_requires;
 149                                 return Entry;
 150                         }
 151                 }
 152
 153                 public override CFGBlock Exit
 154                 {
 155                         get { return this.exit; }
 156                 }
 157
 158                 public override CFGBlock ExceptionExit
 159                 {
 160                         get { return this.exception_exit; }
 161                 }
 162                 #endregion
 163
 164                 #region IEdgeSubroutineAdaptor Members
 165                 public LispList<Pair<EdgeTag, Subroutine>> GetOrdinaryEdgeSubroutinesInternal (CFGBlock from, CFGBlock to, LispList<Edge<CFGBlock, EdgeTag>> context)
 166                 {
 167                         LispList<Pair<EdgeTag, Subroutine>> list;
 168                         this.edge_subroutines.TryGetValue (new Pair<CFGBlock, CFGBlock> (from, to), out list);
 169                         if (list != null && context != null)
 170                                 list = list.Where (FilterRecursiveContracts (to, context));
 171                         return list;
 172                 }
 173                 #endregion
 174
 175                 #region IGraph<CFGBlock,Dummy> Members
 176                 public IEnumerable<CFGBlock> Nodes
 177                 {
 178                         get { return this.blocks; }
 179                 }
 180
 181                 public virtual IEnumerable<Pair<Dummy, CFGBlock>> Successors (CFGBlock node)
 182                 {
 183                         foreach (var pair in this.successor_edges [node])
 184                                 yield return new Pair<Dummy, CFGBlock> (Dummy.Value, pair.Value);
 185
 186                         if (node != this.exception_exit)
 187                                 yield return new Pair<Dummy, CFGBlock> (Dummy.Value, this.exception_exit);
 188                 }
 189                 #endregion
 190
 191                 #region IStackInfo Members
 192                 bool IStackInfo.IsCallOnThis (APC apc)
 193                 {
 194                         return false;
 195                 }
 196                 #endregion
 197
 198                 public override IEnumerable<CFGBlock> SuccessorBlocks (CFGBlock block)
 199                 {
 200                         return SuccessorEdges [block].Select (it => it.Value);
 201                 }
 202
 203                 public override bool HasSingleSuccessor (APC point, out APC ifFound)
 204                 {
 205                         if (point.Index < point.Block.Count) {
 206                                 ifFound = new APC (point.Block, point.Index + 1, point.SubroutineContext);
 207                                 return true;
 208                         }
 209
 210                         if (IsSubroutineEnd (point.Block)) {
 211                                 if (point.SubroutineContext == null) {
 212                                         ifFound = APC.Dummy;
 213                                         return false;
 214                                 }
 215
 216                                 ifFound = ComputeSubroutineContinuation (point);
 217                                 return true;
 218                         }
 219
 220                         BlockWithLabels<Label> onlyOne = null;
 221                         foreach (BlockWithLabels<Label> successor in point.Block.Subroutine.SuccessorBlocks (point.Block)) {
 222                                 if (onlyOne == null)
 223                                         onlyOne = successor;
 224                                 else {
 225                                         ifFound = APC.Dummy;
 226                                         return false;
 227                                 }
 228                         }
 229
 230                         if (onlyOne != null) {
 231                                 ifFound = ComputeTargetFinallyContext (point, onlyOne);
 232                                 return true;
 233                         }
 234
 235                         ifFound = APC.Dummy;
 236                         return false;
 237                 }
 238
 239                 public override bool HasSinglePredecessor (APC point, out APC ifFound)
 240                 {
 241                         if (point.Index > 0) {
 242                                 ifFound = new APC (point.Block, point.Index - 1, point.SubroutineContext);
 243                                 return true;
 244                         }
 245
 246                         if (IsSubroutineStart (point.Block)) {
 247                                 if (point.SubroutineContext == null) {
 248                                         ifFound = APC.Dummy;
 249                                         return false;
 250                                 }
 251
 252                                 bool hasSinglePredecessor;
 253                                 ifFound = ComputeSubroutinePreContinuation (point, out hasSinglePredecessor);
 254                                 return hasSinglePredecessor;
 255                         }
 256
 257
 258                         CFGBlock onlyOne = null;
 259                         foreach (CFGBlock predecessor in point.Block.Subroutine.PredecessorBlocks (point.Block)) {
 260                                 if (onlyOne != null) {
 261                                         ifFound = APC.Dummy;
 262                                         return false;
 263                                 }
 264                                 onlyOne = predecessor;
 265                         }
 266                         if (onlyOne == null) {
 267                                 ifFound = APC.Dummy;
 268                                 return false;
 269                         }
 270
 271                         LispList<Pair<EdgeTag, Subroutine>> list = EdgeSubroutinesOuterToInner (onlyOne, point.Block, point.SubroutineContext);
 272                         if (list.IsEmpty ()) {
 273                                 ifFound = APC.ForEnd (onlyOne, point.SubroutineContext);
 274                                 return true;
 275                         }
 276
 277                         var edge = new Edge<CFGBlock, EdgeTag> (onlyOne, point.Block, list.Head.Key);
 278                         Subroutine sub = list.Head.Value;
 279                         ifFound = APC.ForEnd (sub.Exit, point.SubroutineContext.Cons (edge));
 280                         return true;
 281                 }
 282
 283                 private APC ComputeSubroutinePreContinuation (APC point, out bool hasSinglePredecessor)
 284                 {
 285                         Edge<CFGBlock, EdgeTag> head = point.SubroutineContext.Head;
 286                         bool isExceptionHandlerEdge;
 287                         LispList<Edge<CFGBlock, EdgeTag>> tail = point.SubroutineContext.Tail;
 288                         LispList<Pair<EdgeTag, Subroutine>> flist = EdgeSubroutinesOuterToInner (head.From, head.To, out isExceptionHandlerEdge, tail);
 289                         while (flist.Head.Value != this)
 290                                 flist = flist.Tail;
 291                         if (flist.Tail.IsEmpty ()) {
 292                                 if (isExceptionHandlerEdge && head.From.Count > 1) {
 293                                         hasSinglePredecessor = false;
 294                                         return APC.Dummy;
 295                                 }
 296
 297                                 hasSinglePredecessor = true;
 298                                 return APC.ForEnd (head.From, tail);
 299                         }
 300                         Pair<EdgeTag, Subroutine> first = flist.Tail.Head;
 301                         Subroutine sub = first.Value;
 302                         hasSinglePredecessor = true;
 303
 304                         return APC.ForEnd (sub.Exit, point.SubroutineContext.Cons (new Edge<CFGBlock, EdgeTag> (head.From, head.To, first.Key)));
 305                 }
 306
 307                 private APC ComputeSubroutineContinuation (APC point)
 308                 {
 309                         Edge<CFGBlock, EdgeTag> head = point.SubroutineContext.Head;
 310                         LispList<Edge<CFGBlock, EdgeTag>> tail = point.SubroutineContext.Tail;
 311                         LispList<Pair<EdgeTag, Subroutine>> outerToInner = EdgeSubroutinesOuterToInner (head.From, head.To, tail);
 312                         if (outerToInner.Head.Value == this)
 313                                 return new APC (head.To, 0, tail);
 314
 315                         while (outerToInner.Tail.Head.Value != this)
 316                                 outerToInner = outerToInner.Tail;
 317
 318                         return new APC (outerToInner.Head.Value.Entry, 0, tail.Cons (new Edge<CFGBlock, EdgeTag> (head.From, head.To, outerToInner.Head.Key)));
 319                 }
 320
 321                 public override IEnumerable<CFGBlock> PredecessorBlocks (CFGBlock block)
 322                 {
 323                         return PredecessorEdges [block].Select (it => it.Value);
 324                 }
 325
 326                 public override bool IsJoinPoint (CFGBlock block)
 327                 {
 328                         if (IsCatchFilterHeader (block) || IsSubroutineStart (block) || IsSubroutineEnd (block))
 329                                 return true;
 330
 331                         return PredecessorEdges [block].Count > 1;
 332                 }
 333
 334                 public override bool IsSubroutineEnd (CFGBlock block)
 335                 {
 336                         return block == this.exit || block == this.exception_exit;
 337                 }
 338
 339                 public override bool IsSubroutineStart (CFGBlock block)
 340                 {
 341                         return block == this.entry;
 342                 }
 343
 344                 public override bool IsSplitPoint (CFGBlock block)
 345                 {
 346                         if (IsSubroutineStart (block) || IsSubroutineEnd (block))
 347                                 return true;
 348
 349                         return SuccessorEdges [block].Count > 1;
 350                 }
 351
 352                 public override bool IsCatchFilterHeader (CFGBlock block)
 353                 {
 354                         return block is CatchFilterEntryBlock<Label>;
 355                 }
 356
 357                 public void AddSuccessor (CFGBlock from, EdgeTag tag, CFGBlock to)
 358                 {
 359                         AddNormalControlFlowEdge (this.successors, from, tag, to);
 360                 }
 361
 362                 private void AddNormalControlFlowEdge (List<Edge<CFGBlock, EdgeTag>> succs, CFGBlock from, EdgeTag tag, CFGBlock to)
 363                 {
 364                         succs.Add (new Edge<CFGBlock, EdgeTag> (from, to, tag));
 365                 }
 366
 367                 public virtual void AddReturnBlock (BlockWithLabels<Label> block)
 368                 {
 369                 }
 370
 371                 public BlockWithLabels<Label> GetTargetBlock (Label label)
 372                 {
 373                         return GetBlock (label);
 374                 }
 375
 376                 public BlockWithLabels<Label> GetBlock (Label label)
 377                 {
 378                         IMetaDataProvider metadataDecoder = this.SubroutineFacade.MetaDataProvider;
 379
 380                         BlockWithLabels<Label> block;
 381                         if (!this.LabelsThatStartBlocks.TryGetValue (label, out block)) {
 382                                 Pair<Method, bool> methodVirtualPair;
 383                                 Method constructor;
 384
 385                                 if (Builder == null)
 386                                         throw new InvalidOperationException ("Builder must be not null");
 387
 388                                 if (Builder.IsMethodCallSite (label, out methodVirtualPair)) {
 389                                         int parametersCount = metadataDecoder.Parameters (methodVirtualPair.Key).Count;
 390                                         block = new MethodCallBlock<Label> (methodVirtualPair.Key, this, ref this.BlockIdGenerator, parametersCount, methodVirtualPair.Value);
 391                                 } else if (Builder.IsNewObjSite (label, out constructor)) {
 392                                         int parametersCount = metadataDecoder.Parameters (constructor).Count;
 393                                         block = new NewObjCallBlock<Label> (constructor, parametersCount, this, ref this.BlockIdGenerator);
 394                                 } else
 395                                         block = NewBlock ();
 396
 397                                 if (Builder.IsTargetLabel (label))
 398                                         this.LabelsThatStartBlocks.Add (label, block);
 399                         }
 400                         return block;
 401                 }
 402
 403                 public virtual BlockWithLabels<Label> NewBlock ()
 404                 {
 405                         return new BlockWithLabels<Label> (this, ref this.BlockIdGenerator);
 406                 }
 407
 408                 public AssumeBlock<Label> NewAssumeBlock (Label pc, EdgeTag tag)
 409                 {
 410                         return new AssumeBlock<Label> (this, pc, tag, ref this.BlockIdGenerator);
 411                 }
 412
 413                 public override sealed void AddEdgeSubroutine (CFGBlock from, CFGBlock to, Subroutine subroutine, EdgeTag tag)
 414                 {
 415                         if (subroutine == null)
 416                                 return;
 417
 418                         var key = new Pair<CFGBlock, CFGBlock> (from, to);
 419                         LispList<Pair<EdgeTag, Subroutine>> list;
 420                         var item = new Pair<EdgeTag, Subroutine> (tag, subroutine);
 421
 422                         this.edge_subroutines.TryGetValue (key, out list);
 423                         this.edge_subroutines [key] = list.Cons (item);
 424                 }
 425
 426                 public override IEnumerable<APC> Successors (APC pc)
 427                 {
 428                         APC singleNext;
 429                         if (HasSingleSuccessor (pc, out singleNext))
 430                                 yield return singleNext;
 431                         else {
 432                                 foreach (CFGBlock block in pc.Block.Subroutine.SuccessorBlocks (pc.Block))
 433                                         yield return pc.Block.Subroutine.ComputeTargetFinallyContext (pc, block);
 434                         }
 435                 }
 436
 437                 public override IEnumerable<APC> Predecessors (APC pc)
 438                 {
 439                         if (pc.Index > 0)
 440                                 yield return new APC (pc.Block, pc.Index - 1, pc.SubroutineContext);
 441
 442                         else if (IsSubroutineStart (pc.Block)) {
 443                                 if (!pc.SubroutineContext.IsEmpty ()) {
 444                                         foreach (APC apc in ComputeSubroutinePreContinuation (pc))
 445                                                 yield return apc;
 446                                 }
 447                         } else {
 448                                 foreach (CFGBlock block in pc.Block.Subroutine.PredecessorBlocks (pc.Block)) {
 449                                         LispList<Pair<EdgeTag, Subroutine>> diffs = EdgeSubroutinesOuterToInner (block, pc.Block, pc.SubroutineContext);
 450                                         if (diffs.IsEmpty ())
 451                                                 yield return APC.ForEnd (block, pc.SubroutineContext);
 452                                         else {
 453                                                 Subroutine sub = diffs.Head.Value;
 454                                                 var edge = new Edge<CFGBlock, EdgeTag> (block, pc.Block, diffs.Head.Key);
 455                                                 yield return APC.ForEnd (sub.Exit, pc.SubroutineContext.Cons (edge));
 456                                         }
 457                                 }
 458                         }
 459                 }
 460
 461                 private IEnumerable<APC> ComputeSubroutinePreContinuation (APC point)
 462                 {
 463                         Edge<CFGBlock, EdgeTag> edge = point.SubroutineContext.Head;
 464                         LispList<Edge<CFGBlock, EdgeTag>> tail = point.SubroutineContext.Tail;
 465
 466                         bool isHandlerEdge;
 467                         LispList<Pair<EdgeTag, Subroutine>> diffs = EdgeSubroutinesOuterToInner (edge.From, edge.To, out isHandlerEdge, tail);
 468                         while (diffs.Head.Value != this)
 469                                 diffs = diffs.Tail;
 470
 471                         if (diffs.Tail == null) {
 472                                 if (isHandlerEdge) {
 473                                         for (int i = 0; i < edge.From.Count; i++)
 474                                                 yield return new APC (edge.From, i, tail);
 475                                 } else
 476                                         yield return APC.ForEnd (edge.From, tail);
 477                         } else {
 478                                 Pair<EdgeTag, Subroutine> first = diffs.Tail.Head;
 479                                 Subroutine nextSubroutine = first.Value;
 480                                 yield return APC.ForEnd (nextSubroutine.Exit, point.SubroutineContext.Cons (new Edge<CFGBlock, EdgeTag> (edge.From, edge.To, first.Key)));
 481                         }
 482                 }
 483
 484                 public override APC ComputeTargetFinallyContext (APC pc, CFGBlock succ)
 485                 {
 486                         LispList<Pair<EdgeTag, Subroutine>> list = EdgeSubroutinesOuterToInner (pc.Block, succ, pc.SubroutineContext);
 487                         if (list.IsEmpty ())
 488                                 return new APC (succ, 0, pc.SubroutineContext);
 489
 490                         Pair<EdgeTag, Subroutine> last = list.Last ();
 491                         return new APC (last.Value.Entry, 0, pc.SubroutineContext.Cons (new Edge<CFGBlock, EdgeTag> (pc.Block, succ, last.Key)));
 492                 }
 493
 494                 private LispList<Pair<EdgeTag, Subroutine>> EdgeSubroutinesOuterToInner (CFGBlock from, CFGBlock succ, LispList<Edge<CFGBlock, EdgeTag>> subroutineContext)
 495                 {
 496                         bool isExceptionHandlerEdge;
 497                         return EdgeSubroutinesOuterToInner (from, succ, out isExceptionHandlerEdge, subroutineContext);
 498                 }
 499
 500                 public override LispList<Pair<EdgeTag, Subroutine>> EdgeSubroutinesOuterToInner (CFGBlock from, CFGBlock succ, out bool isExceptionHandlerEdge, LispList<Edge<CFGBlock, EdgeTag>> context)
 501                 {
 502                         if (from.Subroutine != this)
 503                                 return from.Subroutine.EdgeSubroutinesOuterToInner (from, succ, out isExceptionHandlerEdge, context);
 504
 505                         isExceptionHandlerEdge = IsCatchFilterHeader (succ);
 506                         return GetOrdinaryEdgeSubroutines (from, succ, context);
 507                 }
 508
 509                 public override LispList<Pair<EdgeTag, Subroutine>> GetOrdinaryEdgeSubroutines (CFGBlock from, CFGBlock to, LispList<Edge<CFGBlock, EdgeTag>> context)
 510                 {
 511                         IMetaDataProvider metadataDecoder = this.SubroutineFacade.MetaDataProvider;
 512                         var apc = new APC (to, 0, context);
 513
 514                         DecoratorHelper.Push (this);
 515                         try {
 516                                 LispList<Pair<EdgeTag, Subroutine>> list = DecoratorHelper.Dispatch<IEdgeSubroutineAdaptor> (this).GetOrdinaryEdgeSubroutinesInternal (from, to, context);
 517                                 if (apc.InsideContract) {
 518                                         if (context != null && !list.IsEmpty ()) {
 519                                                 Method calledMethod;
 520                                                 bool isNewObj;
 521                                                 bool isVirtual;
 522                                                 if (@from.IsMethodCallBlock (out calledMethod, out isNewObj, out isVirtual) && isVirtual && ((IStackInfo) this).IsCallOnThis (new APC (@from, 0, null))) {
 523                                                         TypeNode type = metadataDecoder.DeclaringType (calledMethod);
 524                                                         do {
 525                                                                 if (context.Head.Tag.Is (EdgeTag.InheritedMask) || context.Head.Tag.Is (EdgeTag.ExtraMask) || context.Head.Tag.Is (EdgeTag.OldMask))
 526                                                                         context = context.Tail;
 527                                                                 else {
 528                                                                         Method calledMethod2;
 529                                                                         bool isNewObj2;
 530                                                                         bool isVirtual2;
 531                                                                         if (context.Head.Tag.Is (EdgeTag.AfterMask) && context.Head.From.IsMethodCallBlock (out calledMethod2, out isNewObj2, out isVirtual2)) {
 532                                                                                 TypeNode sub = metadataDecoder.DeclaringType (calledMethod2);
 533                                                                                 if (metadataDecoder.DerivesFrom (sub, type))
 534                                                                                         type = sub;
 535                                                                                 if (!DecoratorHelper.Dispatch<IStackInfo> (this).IsCallOnThis (new APC (context.Head.From, 0, null)))
 536                                                                                         break;
 537                                                                         } else if (context.Head.Tag.Is (EdgeTag.BeforeMask) && context.Head.To.IsMethodCallBlock (out calledMethod2, out isNewObj2, out isVirtual2)) {
 538                                                                                 TypeNode sub = metadataDecoder.DeclaringType (calledMethod2);
 539                                                                                 if (metadataDecoder.DerivesFrom (sub, type))
 540                                                                                         type = sub;
 541                                                                                 if (!DecoratorHelper.Dispatch<IStackInfo> (this).IsCallOnThis (new APC (context.Head.To, 0, null)))
 542                                                                                         break;
 543                                                                         } else if (context.Head.Tag == EdgeTag.Exit) {
 544                                                                                 var methodInfo = context.Head.From.Subroutine as IMethodInfo;
 545                                                                                 if (methodInfo != null) {
 546                                                                                         TypeNode sub = metadataDecoder.DeclaringType (methodInfo.Method);
 547                                                                                         if (metadataDecoder.DerivesFrom (sub, type))
 548                                                                                                 type = sub;
 549                                                                                 }
 550                                                                                 break;
 551                                                                         } else {
 552                                                                                 if (context.Head.Tag != EdgeTag.Entry)
 553                                                                                         return list;
 554                                                                                 var methodInfo = context.Head.From.Subroutine as IMethodInfo;
 555                                                                                 if (methodInfo != null) {
 556                                                                                         TypeNode sub = metadataDecoder.DeclaringType (methodInfo.Method);
 557                                                                                         if (metadataDecoder.DerivesFrom (sub, type))
 558                                                                                                 type = sub;
 559                                                                                 }
 560                                                                                 break;
 561                                                                         }
 562                                                                         context = context.Tail;
 563                                                                 }
 564                                                         } while (!context.IsEmpty ());
 565                                                         Method implementingMethod;
 566                                                         if (!metadataDecoder.Equal (type, metadataDecoder.DeclaringType (calledMethod)) &&
 567                                                             metadataDecoder.TryGetImplementingMethod (type, calledMethod, out implementingMethod))
 568                                                                 list = SpecializedEnsures (list, this.SubroutineFacade.GetEnsures (calledMethod), this.SubroutineFacade.GetEnsures (implementingMethod));
 569                                                 }
 570                                         }
 571                                 } else {
 572                                         Method calledMethod;
 573                                         bool isNewObj;
 574                                         bool isVirtual;
 575                                         if (@from.IsMethodCallBlock (out calledMethod, out isNewObj, out isVirtual)) {
 576                                                 if (DecoratorHelper.Dispatch<IStackInfo> (this).IsCallOnThis (new APC (@from, 0, null))) {
 577                                                         var methodInfo = @from.Subroutine as IMethodInfo;
 578                                                         if (methodInfo != null) {
 579                                                                 TypeNode bestType = metadataDecoder.DeclaringType (methodInfo.Method);
 580                                                                 Method implementingMethod;
 581                                                                 if (isVirtual && metadataDecoder.TryGetImplementingMethod (bestType, calledMethod, out implementingMethod))
 582                                                                         list = SpecializedEnsures (list, this.SubroutineFacade.GetEnsures (calledMethod), this.SubroutineFacade.GetEnsures (implementingMethod));
 583                                                                 list = InsertInvariant (@from, list, calledMethod, ref bestType, context);
 584                                                         }
 585                                                 }
 586                                         }
 587                                 }
 588                                 return list;
 589                         } finally {
 590                                 DecoratorHelper.Pop ();
 591                         }
 592                 }
 593
 594                 private LispList<Pair<EdgeTag, Subroutine>> InsertInvariant (CFGBlock from, LispList<Pair<EdgeTag, Subroutine>> list,
 595                                                                              Method calledMethod, ref TypeNode type,
 596                                                                              LispList<Edge<CFGBlock, EdgeTag>> context)
 597                 {
 598                         IMetaDataProvider metadataDecoder = this.SubroutineFacade.MetaDataProvider;
 599
 600                         Property property;
 601                         if (metadataDecoder.IsPropertySetter (calledMethod, out property)
 602                             && (metadataDecoder.IsAutoPropertyMember (calledMethod) || WithinConstructor (from, context)))
 603                                 return list;
 604
 605                         if (metadataDecoder.IsConstructor (calledMethod))
 606                                 type = metadataDecoder.DeclaringType (calledMethod);
 607
 608                         Subroutine invariant = this.SubroutineFacade.GetInvariant (type);
 609                         if (invariant != null) {
 610                                 var methodCallBlock = from as MethodCallBlock<Label>;
 611                                 if (methodCallBlock != null) {
 612                                         EdgeTag first = methodCallBlock.IsNewObj ? EdgeTag.AfterNewObj : EdgeTag.AfterCall;
 613                                         return list.Cons (new Pair<EdgeTag, Subroutine> (first, invariant));
 614                                 }
 615                         }
 616
 617                         return list;
 618                 }
 619
 620                 private bool WithinConstructor (CFGBlock current, LispList<Edge<CFGBlock, EdgeTag>> context)
 621                 {
 622                         return new APC (current, 0, context).InsideConstructor;
 623                 }
 624
 625                 private LispList<Pair<EdgeTag, Subroutine>> SpecializedEnsures (LispList<Pair<EdgeTag, Subroutine>> subroutines,
 626                                                                                 Subroutine toReplace, Subroutine specializedEnsures)
 627                 {
 628                         return subroutines.Select (pair => new Pair<EdgeTag, Subroutine> (pair.Key, pair.Value == toReplace ? specializedEnsures : pair.Value));
 629                 }
 630
 631                 private static Predicate<Pair<EdgeTag, Subroutine>> FilterRecursiveContracts (CFGBlock from, LispList<Edge<CFGBlock, EdgeTag>> context)
 632                 {
 633                         return (candidate) => {
 634                                 Subroutine sub = candidate.Value;
 635                                 if (!sub.IsContract)
 636                                         return true;
 637                                 if (sub == @from.Subroutine)
 638                                         return false;
 639                                 if (context.Any (ctx => sub == ctx.From.Subroutine))
 640                                         return false;
 641                                 return true;
 642                                };
 643                 }
 644
 645                 public abstract override void Initialize ();
 646
 647                 public virtual void Commit ()
 648                 {
 649                         PostProcessBlocks ();
 650                 }
 651
 652                 protected void PostProcessBlocks ()
 653                 {
 654                         var blockStack = new Stack<CFGBlock> ();
 655                         this.successor_edges = new EdgeMap<EdgeTag> (this.successors);
 656                         this.edge_info = new DepthFirst.Visitor<CFGBlock, Dummy> (this, null, (block) => blockStack.Push (block), null);
 657                         this.edge_info.VisitSubGraphNonRecursive (this.exception_exit);
 658                         this.edge_info.VisitSubGraphNonRecursive (this.exit);
 659                         this.edge_info.VisitSubGraphNonRecursive (this.entry);
 660
 661                         foreach (var successorEdge in this.successor_edges) {
 662                                 int idGen = UnusedBlockIndex;
 663                                 successorEdge.From.Renumber (ref idGen);
 664                         }
 665                         int idGen1 = 0;
 666                         foreach (CFGBlock cfgBlock in blockStack)
 667                                 cfgBlock.Renumber (ref idGen1);
 668
 669                         SuccessorEdges.Filter ((e) => e.From.Index != UnusedBlockIndex);
 670                         this.predecessor_edges = this.successor_edges.Reverse ();
 671                         int finishTime = 0;
 672                         var visitor = new DepthFirst.Visitor<CFGBlock, EdgeTag> (this.predecessor_edges, null, block => block.ReversePostOrderIndex = finishTime++, null);
 673                         visitor.VisitSubGraphNonRecursive (this.exit);
 674                         foreach (CFGBlock node in blockStack)
 675                                 visitor.VisitSubGraphNonRecursive (node);
 676
 677                         SuccessorEdges.Resort ();
 678                         this.blocks = blockStack.ToArray ();
 679                         this.LabelsThatStartBlocks = null;
 680                         Builder = null;
 681                 }
 682
 683                 public override IEnumerable<Subroutine> UsedSubroutines (HashSet<int> alreadySeen)
 684                 {
 685                         foreach (var list in this.edge_subroutines.Values) {
 686                                 foreach (var pair in list.AsEnumerable ()) {
 687                                         Subroutine sub = pair.Value;
 688                                         if (!alreadySeen.Contains (sub.Id)) {
 689                                                 alreadySeen.Add (sub.Id);
 690                                                 yield return sub;
 691                                         }
 692                                 }
 693                         }
 694                 }
 695
 696                 public override IEnumerable<CFGBlock> ExceptionHandlers<Data, TType> (CFGBlock block, Subroutine innerSubroutine,
 697                                                                                       Data data, IHandlerFilter<Data> handlerPredicate)
 698                 {
 699                         yield return this.exception_exit;
 700                 }
 701
 702
 703                 public override void Print (TextWriter tw, ILPrinter<APC> printer, Func<CFGBlock,
 704                                                                                         IEnumerable<LispList<Edge<CFGBlock, EdgeTag>>>> contextLookup,
 705                                             LispList<Edge<CFGBlock, EdgeTag>> context,
 706                                             HashSet<Pair<Subroutine, LispList<Edge<CFGBlock, EdgeTag>>>> printed)
 707                 {
 708                         var element = new Pair<Subroutine, LispList<Edge<CFGBlock, EdgeTag>>> (this, context);
 709                         if (printed.Contains (element))
 710                                 return;
 711                         printed.Add (element);
 712                         var subs = new HashSet<Subroutine> ();
 713                         var methodInfo = this as IMethodInfo;
 714                         string method = (methodInfo != null) ? String.Format ("({0})", this.SubroutineFacade.MetaDataProvider.FullName (methodInfo.Method)) : null;
 715
 716                         tw.WriteLine ("Subroutine SR{0} {1} {2}", Id, Kind, method);
 717                         tw.WriteLine ("-------------");
 718                         foreach (BlockWithLabels<Label> block in this.blocks) {
 719                                 tw.Write ("Block {0} ({1})", block.Index, block.ReversePostOrderIndex);
 720                                 if (this.edge_info.DepthFirstInfo (block).TargetOfBackEdge)
 721                                         tw.WriteLine (" (target of backedge)");
 722                                 else if (IsJoinPoint (block))
 723                                         tw.WriteLine (" (join point)");
 724                                 else
 725                                         tw.WriteLine ();
 726
 727                                 tw.Write ("  Predecessors: ");
 728                                 foreach (var edge in block.Subroutine.PredecessorEdges [block])
 729                                         tw.Write ("({0}, {1}) ", edge.Key, edge.Value.Index);
 730                                 tw.WriteLine ();
 731                                 PrintHandlers (tw, block);
 732
 733                                 tw.WriteLine ("  Code:");
 734                                 foreach (APC apc in block.APCs ())
 735                                         printer (apc, "    ", tw);
 736
 737                                 tw.Write ("  Successors: ");
 738                                 foreach (var edge in block.Subroutine.SuccessorEdges [block]) {
 739                                         tw.Write ("({0}, {1}", edge.Key, edge.Value.Index);
 740                                         if (this.edge_info.IsBackEdge (block, Dummy.Value, edge.Value))
 741                                                 tw.Write (" BE");
 742
 743                                         for (LispList<Pair<EdgeTag, Subroutine>> list = GetOrdinaryEdgeSubroutines (block, edge.Value, context); list != null; list = list.Tail) {
 744                                                 subs.Add (list.Head.Value);
 745                                                 tw.Write (" SR{0}({1})", list.Head.Value.Id, list.Head.Key);
 746                                         }
 747                                         tw.Write (") ");
 748                                 }
 749                                 tw.WriteLine ();
 750                         }
 751                         PrintReferencedSubroutines (tw, subs, printer, contextLookup, context, printed);
 752                 }
 753
 754                 protected virtual void PrintReferencedSubroutines (TextWriter tw, HashSet<Subroutine> subs, ILPrinter<APC> printer,
 755                                                                    Func<CFGBlock, IEnumerable<LispList<Edge<CFGBlock, EdgeTag>>>> contextLookup,
 756                                                                    LispList<Edge<CFGBlock, EdgeTag>> context,
 757                                                                    HashSet<Pair<Subroutine, LispList<Edge<CFGBlock, EdgeTag>>>> printed)
 758                 {
 759                         foreach (Subroutine subroutine in subs) {
 760                                 if (contextLookup == null)
 761                                         subroutine.Print (tw, printer, contextLookup, context, printed);
 762                                 else {
 763                                         foreach (var ctx in contextLookup (subroutine.Entry))
 764                                                 subroutine.Print (tw, printer, contextLookup, ctx, printed);
 765                                 }
 766                         }
 767                 }
 768
 769                 protected virtual void PrintHandlers (TextWriter tw, BlockWithLabels<Label> block)
 770                 {
 771                         tw.Write ("  Handlers: ");
 772                         if (block != ExceptionExit)
 773                                 tw.Write ("{0} ", ExceptionExit.Index);
 774                         tw.WriteLine ();
 775                 }
 776
 777                 public int GetILOffset (Label label)
 778                 {
 779                         return CodeProvider.GetILOffset (label);
 780                 }
 781         }
 782 }