context: // 
  // SubroutineBase.cs
  // 
  // Authors:
  // 	Alexander Chebaturkin (chebaturkin@gmail.com)
  // 
  // Copyright (C) 2011 Alexander Chebaturkin
  // 
  // Permission is hereby granted, free of charge, to any person obtaining
  // a copy of this software and associated documentation files (the
  // "Software"), to deal in the Software without restriction, including
  // without limitation the rights to use, copy, modify, merge, publish,
  // distribute, sublicense, and/or sell copies of the Software, and to
  // permit persons to whom the Software is furnished to do so, subject to
  // the following conditions:
  // 
  // The above copyright notice and this permission notice shall be
  // included in all copies or substantial portions of the Software.
  //  
  // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 
  // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  // 
  
  using System;
  using System.Collections.Generic;
  using System.IO;
  using System.Linq;
  using Mono.CodeContracts.Static.AST;
  using Mono.CodeContracts.Static.Analysis;
  using Mono.CodeContracts.Static.ControlFlow.Blocks;
  using Mono.CodeContracts.Static.ControlFlow.Subroutines.Builders;
  using Mono.CodeContracts.Static.DataStructures;
  using Mono.CodeContracts.Static.Providers;
  
  namespace Mono.CodeContracts.Static.ControlFlow.Subroutines {
  	abstract class SubroutineBase<Label> : Subroutine, IGraph<CFGBlock, Dummy>, IStackInfo, IEdgeSubroutineAdaptor {
  		private const int UnusedBlockIndex = Int32.MaxValue - 1;
  		protected readonly Label StartLabel;
  		public readonly SubroutineFacade SubroutineFacade;
  
  		private readonly Dictionary<Pair<CFGBlock, CFGBlock>, Sequence<Pair<EdgeTag, Subroutine>>> edge_subroutines
  			= new Dictionary<Pair<CFGBlock, CFGBlock>, Sequence<Pair<EdgeTag, Subroutine>>> ();
  
  		private readonly BlockWithLabels<Label> entry;
  		private readonly BlockWithLabels<Label> entry_after_requires;
  		private readonly BlockWithLabels<Label> exception_exit;
  		private readonly BlockWithLabels<Label> exit;
  
  		private readonly List<Edge<CFGBlock, EdgeTag>> successors = new List<Edge<CFGBlock, EdgeTag>> ();
  		protected int BlockIdGenerator;
  		protected Dictionary<Label, BlockWithLabels<Label>> LabelsThatStartBlocks = new Dictionary<Label, BlockWithLabels<Label>> ();
  
  		private CFGBlock[] blocks;
  		private DepthFirst.Visitor<CFGBlock, Dummy> edge_info;
  		private EdgeMap<EdgeTag> predecessor_edges;
  		private EdgeMap<EdgeTag> successor_edges;
  
  		protected SubroutineBase (SubroutineFacade subroutineFacade)
  		{
  			this.SubroutineFacade = subroutineFacade;
  			this.entry = new EntryBlock<Label> (this, ref this.BlockIdGenerator);
  			this.exit = new EntryExitBlock<Label> (this, ref this.BlockIdGenerator);
  			this.exception_exit = new CatchFilterEntryBlock<Label> (this, ref this.BlockIdGenerator);
  		}
  
  		protected SubroutineBase (SubroutineFacade facade,
  		                          Label startLabel, SubroutineBuilder<Label> builder)
  			: this (facade)
  		{
  			this.StartLabel = startLabel;
  			Builder = builder;
  			CodeProvider = builder.CodeProvider;
  			this.entry_after_requires = GetTargetBlock (startLabel);
  
  			AddSuccessor (this.entry, EdgeTag.Entry, this.entry_after_requires);
  		}
  
  		public override bool HasContextDependentStackDepth
  		{
  			get { return true; }
  		}
  
  		public override bool HasReturnValue
  		{
  			get { return false; }
  		}
  
  		public override int StackDelta
  		{
  			get { return 0; }
  		}
  
  		protected SubroutineBuilder<Label> Builder { get; set; }
  
  		public override DepthFirst.Visitor<CFGBlock, Dummy> EdgeInfo
  		{
  			get { return this.edge_info; }
  		}
  
  		public ICodeProvider<Label> CodeProvider { get; private set; }
  
  		public override int BlockCount
  		{
  			get { return this.blocks.Length; }
  		}
  
  		public override IEnumerable<CFGBlock> Blocks
  		{
  			get { return this.blocks; }
  		}
  
  		public override string Name
  		{
  			get { return "SR" + Id; }
  		}
  
  		public override EdgeMap<EdgeTag> SuccessorEdges
  		{
  			get { return this.successor_edges; }
  		}
  
  		public override EdgeMap<EdgeTag> PredecessorEdges
  		{
  			get
  			{
  				if (this.predecessor_edges == null)
  					this.predecessor_edges = this.successor_edges.Reverse ();
  				return this.predecessor_edges;
  			}
  		}
  
  		#region Main Blocks
  		public override CFGBlock Entry
  		{
  			get { return this.entry; }
  		}
  
  		public override CFGBlock EntryAfterRequires
  		{
  			get
  			{
  				if (this.entry_after_requires != null)
  					return this.entry_after_requires;
  				return Entry;
  			}
  		}
  
  		public override CFGBlock Exit
  		{
  			get { return this.exit; }
  		}
  
  		public override CFGBlock ExceptionExit
  		{
  			get { return this.exception_exit; }
  		}
  		#endregion
  
  		#region IEdgeSubroutineAdaptor Members
  		public Sequence<Pair<EdgeTag, Subroutine>> GetOrdinaryEdgeSubroutinesInternal (CFGBlock from, CFGBlock to, Sequence<Edge<CFGBlock, EdgeTag>> context)
  		{
  			Sequence<Pair<EdgeTag, Subroutine>> list;
  			this.edge_subroutines.TryGetValue (new Pair<CFGBlock, CFGBlock> (from, to), out list);
  			if (list != null && context != null)
  				list = list.Where (FilterRecursiveContracts (to, context));
  			return list;
  		}
  		#endregion
  
  		#region IGraph<CFGBlock,Dummy> Members
  		public IEnumerable<CFGBlock> Nodes
  		{
  			get { return this.blocks; }
  		}
  
  		public virtual IEnumerable<Pair<Dummy, CFGBlock>> Successors (CFGBlock node)
  		{
  			foreach (var pair in this.successor_edges [node])
  				yield return new Pair<Dummy, CFGBlock> (Dummy.Value, pair.Value);
  
  			if (node != this.exception_exit)
  				yield return new Pair<Dummy, CFGBlock> (Dummy.Value, this.exception_exit);
  		}
  		#endregion
  
  		#region IStackInfo Members
  		bool IStackInfo.IsCallOnThis (APC apc)
  		{
  			return false;
  		}
  		#endregion
  
  		public override IEnumerable<CFGBlock> SuccessorBlocks (CFGBlock block)
  		{
  			return SuccessorEdges [block].Select (it => it.Value);
  		}
  
  		public override bool HasSingleSuccessor (APC point, out APC ifFound)
  		{
  			if (point.Index < point.Block.Count) {
  				ifFound = new APC (point.Block, point.Index + 1, point.SubroutineContext);
  				return true;
  			}
  
  			if (IsSubroutineEnd (point.Block)) {
  				if (point.SubroutineContext == null) {
  					ifFound = APC.Dummy;
  					return false;
  				}
  
  				ifFound = ComputeSubroutineContinuation (point);
  				return true;
  			}
  
  			BlockWithLabels<Label> onlyOne = null;
  			foreach (BlockWithLabels<Label> successor in point.Block.Subroutine.SuccessorBlocks (point.Block)) {
  				if (onlyOne == null)
  					onlyOne = successor;
  				else {
  					ifFound = APC.Dummy;
  					return false;
  				}
  			}
  
  			if (onlyOne != null) {
  				ifFound = ComputeTargetFinallyContext (point, onlyOne);
  				return true;
  			}
  
  			ifFound = APC.Dummy;
  			return false;
  		}
  
  		public override bool HasSinglePredecessor (APC point, out APC ifFound)
  		{
  			if (point.Index > 0) {
  				ifFound = new APC (point.Block, point.Index - 1, point.SubroutineContext);
  				return true;
  			}
  
  			if (IsSubroutineStart (point.Block)) {
  				if (point.SubroutineContext == null) {
  					ifFound = APC.Dummy;
  					return false;
  				}
  
  				bool hasSinglePredecessor;
  				ifFound = ComputeSubroutinePreContinuation (point, out hasSinglePredecessor);
  				return hasSinglePredecessor;
  			}
  
  
  			CFGBlock onlyOne = null;
  			foreach (CFGBlock predecessor in point.Block.Subroutine.PredecessorBlocks (point.Block)) {
  				if (onlyOne != null) {
  					ifFound = APC.Dummy;
  					return false;
  				}
  				onlyOne = predecessor;
  			}
  			if (onlyOne == null) {
  				ifFound = APC.Dummy;
  				return false;
  			}
  
  			Sequence<Pair<EdgeTag, Subroutine>> list = EdgeSubroutinesOuterToInner (onlyOne, point.Block, point.SubroutineContext);
  			if (list.IsEmpty ()) {
  				ifFound = APC.ForEnd (onlyOne, point.SubroutineContext);
  				return true;
  			}
  
  			var edge = new Edge<CFGBlock, EdgeTag> (onlyOne, point.Block, list.Head.Key);
  			Subroutine sub = list.Head.Value;
  			ifFound = APC.ForEnd (sub.Exit, point.SubroutineContext.Cons (edge));
  			return true;
  		}
  
  		private APC ComputeSubroutinePreContinuation (APC point, out bool hasSinglePredecessor)
  		{
  			Edge<CFGBlock, EdgeTag> head = point.SubroutineContext.Head;
  			bool isExceptionHandlerEdge;
  			Sequence<Edge<CFGBlock, EdgeTag>> tail = point.SubroutineContext.Tail;
  			Sequence<Pair<EdgeTag, Subroutine>> flist = EdgeSubroutinesOuterToInner (head.From, head.To, out isExceptionHandlerEdge, tail);
  			while (flist.Head.Value != this)
  				flist = flist.Tail;
  			if (flist.Tail.IsEmpty ()) {
  				if (isExceptionHandlerEdge && head.From.Count > 1) {
  					hasSinglePredecessor = false;
  					return APC.Dummy;
  				}
  
  				hasSinglePredecessor = true;
  				return APC.ForEnd (head.From, tail);
  			}
  			Pair<EdgeTag, Subroutine> first = flist.Tail.Head;
  			Subroutine sub = first.Value;
  			hasSinglePredecessor = true;
  
  			return APC.ForEnd (sub.Exit, point.SubroutineContext.Cons (new Edge<CFGBlock, EdgeTag> (head.From, head.To, first.Key)));
  		}
  
  		private APC ComputeSubroutineContinuation (APC point)
  		{
  			Edge<CFGBlock, EdgeTag> head = point.SubroutineContext.Head;
  			Sequence<Edge<CFGBlock, EdgeTag>> tail = point.SubroutineContext.Tail;
  			Sequence<Pair<EdgeTag, Subroutine>> outerToInner = EdgeSubroutinesOuterToInner (head.From, head.To, tail);
  			if (outerToInner.Head.Value == this)
  				return new APC (head.To, 0, tail);
  
  			while (outerToInner.Tail.Head.Value != this)
  				outerToInner = outerToInner.Tail;
  
  			return new APC (outerToInner.Head.Value.Entry, 0, tail.Cons (new Edge<CFGBlock, EdgeTag> (head.From, head.To, outerToInner.Head.Key)));
  		}
  
  		public override IEnumerable<CFGBlock> PredecessorBlocks (CFGBlock block)
  		{
  			return PredecessorEdges [block].Select (it => it.Value);
  		}
  
  		public override bool IsJoinPoint (CFGBlock block)
  		{
  			if (IsCatchFilterHeader (block) || IsSubroutineStart (block) || IsSubroutineEnd (block))
  				return true;
  
  			return PredecessorEdges [block].Count > 1;
  		}
  
  		public override bool IsSubroutineEnd (CFGBlock block)
  		{
  			return block == this.exit || block == this.exception_exit;
  		}
  
  		public override bool IsSubroutineStart (CFGBlock block)
  		{
  			return block == this.entry;
  		}
  
  		public override bool IsSplitPoint (CFGBlock block)
  		{
  			if (IsSubroutineStart (block) || IsSubroutineEnd (block))
  				return true;
  
  			return SuccessorEdges [block].Count > 1;
  		}
  
  		public override bool IsCatchFilterHeader (CFGBlock block)
  		{
  			return block is CatchFilterEntryBlock<Label>;
  		}
  
  		public void AddSuccessor (CFGBlock from, EdgeTag tag, CFGBlock to)
  		{
  			AddNormalControlFlowEdge (this.successors, from, tag, to);
  		}
  
  		private void AddNormalControlFlowEdge (List<Edge<CFGBlock, EdgeTag>> succs, CFGBlock from, EdgeTag tag, CFGBlock to)
  		{
  			succs.Add (new Edge<CFGBlock, EdgeTag> (from, to, tag));
  		}
  
  		public virtual void AddReturnBlock (BlockWithLabels<Label> block)
  		{
  		}
  
  		public BlockWithLabels<Label> GetTargetBlock (Label label)
  		{
  			return GetBlock (label);
  		}
  
  		public BlockWithLabels<Label> GetBlock (Label label)
  		{
  			IMetaDataProvider metadataDecoder = this.SubroutineFacade.MetaDataProvider;
  
  			BlockWithLabels<Label> block;
  			if (!this.LabelsThatStartBlocks.TryGetValue (label, out block)) {
  				Pair<Method, bool> methodVirtualPair;
  				Method constructor;
  
  				if (Builder == null)
  					throw new InvalidOperationException ("Builder must be not null");
  
  				if (Builder.IsMethodCallSite (label, out methodVirtualPair)) {
  					int parametersCount = metadataDecoder.Parameters (methodVirtualPair.Key).Count;
  					block = new MethodCallBlock<Label> (methodVirtualPair.Key, this, ref this.BlockIdGenerator, parametersCount, methodVirtualPair.Value);
  				} else if (Builder.IsNewObjSite (label, out constructor)) {
  					int parametersCount = metadataDecoder.Parameters (constructor).Count;
  					block = new NewObjCallBlock<Label> (constructor, parametersCount, this, ref this.BlockIdGenerator);
  				} else
  					block = NewBlock ();
  
  
gt: 				if (Builder.IsTargetLabel (label))