context: // Copyright (c) 2011 AlphaSierraPapa for the SharpDevelop Team
  // 
  // 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.Concurrent;
  using System.Collections.Generic;
  using System.Linq;
  using System.Text;
  
  using Mono.Cecil;
  using Mono.Cecil.Cil;
  using Cecil = Mono.Cecil;
  
  namespace ICSharpCode.Decompiler.ILAst
  {
  	public class ILAstBuilder
  	{
  		static ByteCode[] EmptyByteCodeArray = new ByteCode[] {};
  		
  		/// <summary> Immutable </summary>
  		class StackSlot
  		{
  			public readonly ByteCode[] PushedBy;  // One of those
  			public readonly ILVariable LoadFrom;  // Where can we get the value from in AST
  			
  			public StackSlot(ByteCode[] pushedBy, ILVariable loadFrom)
  			{
  				this.PushedBy = pushedBy;
  				this.LoadFrom = loadFrom;
  			}
  			
  			public StackSlot(ByteCode pushedBy)
  			{
  				this.PushedBy = new[] { pushedBy };
  				this.LoadFrom = null;
  			}
  			
  			public static List<StackSlot> CloneStack(List<StackSlot> stack, int? popCount)
  			{
  				if (popCount.HasValue) {
  					return stack.GetRange(0, stack.Count - popCount.Value);
  				} else {
  					return new List<StackSlot>(0);
  				}
  			}
  		}
  		
  		/// <summary> Immutable </summary>
  		class VariableSlot
  		{			
  			public readonly ByteCode[] StoredBy;    // One of those
  			public readonly bool       StoredByAll; // Overestimate which is useful for exceptional control flow.
  			
  			public VariableSlot(ByteCode[] storedBy, bool storedByAll)
  			{
  				this.StoredBy = storedBy;
  				this.StoredByAll = storedByAll;
  			}
  			
  			public VariableSlot(ByteCode storedBy)
  			{
  				this.StoredBy = new[] { storedBy };
  				this.StoredByAll = false;
  			}
  			
  			public static VariableSlot[] CloneVariableState(VariableSlot[] state)
  			{
  				VariableSlot[] clone = new VariableSlot[state.Length];
  				for (int i = 0; i < clone.Length; i++) {
  					clone[i] = state[i];
  				}
  				return clone;
  			}
  			
  			public static VariableSlot[] MakeEmptyState(int varCount)
  			{
  				VariableSlot[] emptyVariableState = new VariableSlot[varCount];
  				for (int i = 0; i < emptyVariableState.Length; i++) {
  					emptyVariableState[i] = new VariableSlot(EmptyByteCodeArray, false);
  				}
  				return emptyVariableState;
  			}
  			
  			public static VariableSlot[] MakeFullState(int varCount)
  			{
  				VariableSlot[] unknownVariableState = new VariableSlot[varCount];
  				for (int i = 0; i < unknownVariableState.Length; i++) {
  					unknownVariableState[i] = new VariableSlot(EmptyByteCodeArray, true);
  				}
  				return unknownVariableState;
  			}
  		}
  		
  		class ByteCode
  		{
  			public ILLabel  Label;      // Non-null only if needed
  			public int      Offset;
  			public int      EndOffset;
  			public ILCode   Code;
  			public object   Operand;
  			public int?     PopCount;   // Null means pop all
  			public int      PushCount;
  			public string   Name { get { return "IL_" + this.Offset.ToString("X2"); } }
  			public ByteCode Next;
  			public Instruction[]    Prefixes;        // Non-null only if needed
  			public List<StackSlot>  StackBefore;     // Unique per bytecode; not shared
  			public List<ILVariable> StoreTo;         // Store result of instruction to those AST variables
  			public VariableSlot[]   VariablesBefore; // Unique per bytecode; not shared
  			
  			public VariableDefinition OperandAsVariable { get { return (VariableDefinition)this.Operand; } }
  			
  			public override string ToString()
  			{
  				StringBuilder sb = new StringBuilder();
  				
  				// Label
  				sb.Append(this.Name);
  				sb.Append(':');
  				if (this.Label != null)
  					sb.Append('*');
  				
  				// Name
  				sb.Append(' ');
  				if (this.Prefixes != null) {
  					foreach (var prefix in this.Prefixes) {
  						sb.Append(prefix.OpCode.Name);
  						sb.Append(' ');
  					}
  				}
  				sb.Append(this.Code.GetName());
  				
  				if (this.Operand != null) {
  					sb.Append(' ');
  					if (this.Operand is Instruction) {
  						sb.Append("IL_" + ((Instruction)this.Operand).Offset.ToString("X2"));
  					} else if (this.Operand is Instruction[]) {
  						foreach(Instruction inst in (Instruction[])this.Operand) {
  							sb.Append("IL_" + inst.Offset.ToString("X2"));
  							sb.Append(" ");
  						}
  					} else if (this.Operand is ILLabel) {
  						sb.Append(((ILLabel)this.Operand).Name);
  					} else if (this.Operand is ILLabel[]) {
  						foreach(ILLabel label in (ILLabel[])this.Operand) {
  							sb.Append(label.Name);
  							sb.Append(" ");
  						}
  					} else {
  						sb.Append(this.Operand.ToString());
  					}
  				}
  				
  				if (this.StackBefore != null) {
  					sb.Append(" StackBefore={");
  					bool first = true;
  					foreach (StackSlot slot in this.StackBefore) {
  						if (!first) sb.Append(",");
  						bool first2 = true;
  						foreach(ByteCode pushedBy in slot.PushedBy) {
  							if (!first2) sb.Append("|");
  							sb.AppendFormat("IL_{0:X2}", pushedBy.Offset);
  							first2 = false;
  						}
  						first = false;
  					}
  					sb.Append("}");
  				}
  				
  				if (this.StoreTo != null && this.StoreTo.Count > 0) {
  					sb.Append(" StoreTo={");
  					bool first = true;
  					foreach (ILVariable stackVar in this.StoreTo) {
  						if (!first) sb.Append(",");
  						sb.Append(stackVar.Name);
  						first = false;
  					}
  					sb.Append("}");
  				}
  				
  				if (this.VariablesBefore != null) {
  					sb.Append(" VarsBefore={");
  					bool first = true;
  					foreach (VariableSlot varSlot in this.VariablesBefore) {
  						if (!first) sb.Append(",");
  						if (varSlot.StoredByAll) {
  							sb.Append("*");
  						} else if (varSlot.StoredBy.Length == 0) {
  							sb.Append("_");
  						} else {
  							bool first2 = true;
  							foreach (ByteCode storedBy in varSlot.StoredBy) {
  								if (!first2) sb.Append("|");
  								sb.AppendFormat("IL_{0:X2}", storedBy.Offset);
  								first2 = false;
  							}
  						}
  						first = false;
  					}
  					sb.Append("}");
  				}
  				
  				return sb.ToString();
  			}
  		}
  		
  		MethodDefinition methodDef;
  		bool optimize;
  		
  		// Virtual instructions to load exception on stack
  		Dictionary<ExceptionHandler, ByteCode> ldexceptions = new Dictionary<ExceptionHandler, ILAstBuilder.ByteCode>();
  		
  		public List<ILNode> Build(MethodDefinition methodDef, bool optimize)
  		{
  			this.methodDef = methodDef;
  			this.optimize = optimize;
  			
  			if (methodDef.Body.Instructions.Count == 0) return new List<ILNode>();
  			
  			List<ByteCode> body = StackAnalysis(methodDef);
  			
  			List<ILNode> ast = ConvertToAst(body, new HashSet<ExceptionHandler>(methodDef.Body.ExceptionHandlers));
  			
  			return ast;
  		}
  		
  		List<ByteCode> StackAnalysis(MethodDefinition methodDef)
  		{
  			Dictionary<Instruction, ByteCode> instrToByteCode = new Dictionary<Instruction, ByteCode>();
  			
  			// Create temporary structure for the stack analysis
  			List<ByteCode> body = new List<ByteCode>(methodDef.Body.Instructions.Count);
  			List<Instruction> prefixes = null;
  			foreach(Instruction inst in methodDef.Body.Instructions) {
  				if (inst.OpCode.OpCodeType == OpCodeType.Prefix) {
  					if (prefixes == null)
  						prefixes = new List<Instruction>(1);
  					prefixes.Add(inst);
  					continue;
  				}
  				ILCode code  = (ILCode)inst.OpCode.Code;
  				object operand = inst.Operand;
  				ILCodeUtil.ExpandMacro(ref code, ref operand, methodDef.Body);
  				ByteCode byteCode = new ByteCode() {
  					Offset      = inst.Offset,
  					EndOffset   = inst.Next != null ? inst.Next.Offset : methodDef.Body.CodeSize,
  					Code        = code,
  					Operand     = operand,
  					PopCount    = inst.GetPopDelta(),
  					PushCount   = inst.GetPushDelta()
  				};
  				if (prefixes != null) {
  					instrToByteCode[prefixes[0]] = byteCode;
  					byteCode.Offset = prefixes[0].Offset;
  					byteCode.Prefixes = prefixes.ToArray();
  					prefixes = null;
  				} else {
  					instrToByteCode[inst] = byteCode;
  				}
  				body.Add(byteCode);
  			}
  			for (int i = 0; i < body.Count - 1; i++) {
  				body[i].Next = body[i + 1];
  			}
  			
  			Stack<ByteCode> agenda = new Stack<ByteCode>();
  			
  			int varCount = methodDef.Body.Variables.Count;
  			
  			// Add known states
  			if(methodDef.Body.HasExceptionHandlers) {
  				foreach(ExceptionHandler ex in methodDef.Body.ExceptionHandlers) {
  					ByteCode handlerStart = instrToByteCode[ex.HandlerStart];
  					handlerStart.StackBefore = new List<StackSlot>();
  					handlerStart.VariablesBefore = VariableSlot.MakeFullState(varCount);
  					if (ex.HandlerType == ExceptionHandlerType.Catch || ex.HandlerType == ExceptionHandlerType.Filter) {
  						// Catch and Filter handlers start with the exeption on the stack
  						ByteCode ldexception = new ByteCode() {
  							Code = ILCode.Ldexception,
  							Operand = ex.CatchType,
  							PopCount = 0,
  							PushCount = 1
  						};
  						ldexceptions[ex] = ldexception;
  						handlerStart.StackBefore.Add(new StackSlot(ldexception));
  					}
  					agenda.Push(handlerStart);
  					
  					if (ex.HandlerType == ExceptionHandlerType.Filter)
  					{
  						ByteCode filterStart = instrToByteCode[ex.FilterStart];
  						filterStart.StackBefore = new List<StackSlot>();
  						filterStart.VariablesBefore = VariableSlot.MakeFullState(varCount);
  						ByteCode ldexception = new ByteCode() {
  							Code = ILCode.Ldexception,
  							Operand = ex.CatchType,
  							PopCount = 0,
  							PushCount = 1
  						};
  						// TODO: ldexceptions[ex] = ldexception;
  						filterStart.StackBefore.Add(new StackSlot(ldexception));
  						agenda.Push(filterStart);
  					}
  				}
  			}
  			
  			body[0].StackBefore = new List<StackSlot>();
  			body[0].VariablesBefore = VariableSlot.MakeEmptyState(varCount);
  			agenda.Push(body[0]);
  			
  			// Process agenda
  			while(agenda.Count > 0) {
  				ByteCode byteCode = agenda.Pop();
  				
  				// Calculate new stack
  				List<StackSlot> newStack = StackSlot.CloneStack(byteCode.StackBefore, byteCode.PopCount);
  				for (int i = 0; i < byteCode.PushCount; i++) {
  					newStack.Add(new StackSlot(byteCode));
  				}
  				
  				// Calculate new variable state
  				VariableSlot[] newVariableState = VariableSlot.CloneVariableState(byteCode.VariablesBefore);
  				if (byteCode.Code == ILCode.Stloc) {
  					int varIndex = ((VariableReference)byteCode.Operand).Index;
  					newVariableState[varIndex] = new VariableSlot(byteCode);
  				}
  				
  				// After the leave, finally block might have touched the variables
  				if (byteCode.Code == ILCode.Leave) {
  					newVariableState = VariableSlot.MakeFullState(varCount);
  				}
  				
  				// Find all successors
  				List<ByteCode> branchTargets = new List<ByteCode>();
  				if (!byteCode.Code.IsUnconditionalControlFlow()) {
  					branchTargets.Add(byteCode.Next);
  				}
  				if (byteCode.Operand is Instruction[]) {
  					foreach(Instruction inst in (Instruction[])byteCode.Operand) {
  						ByteCode target = instrToByteCode[inst];
  						branchTargets.Add(target);
  						// The target of a branch must have label
  						if (target.Label == null) {
  							target.Label = new ILLabel() { Name = target.Name };
  						}
  					}
  				} else if (byteCode.Operand is Instruction) {
  					ByteCode target = instrToByteCode[(Instruction)byteCode.Operand];
  					branchTargets.Add(target);
  					// The target of a branch must have label
  					if (target.Label == null) {
  						target.Label = new ILLabel() { Name = target.Name };
  					}
  				}
  				
  				// Apply the state to successors
  				foreach (ByteCode branchTarget in branchTargets) {
  					if (branchTarget.StackBefore == null && branchTarget.VariablesBefore == null) {
  						if (branchTargets.Count == 1) {
  							branchTarget.StackBefore = newStack;
  							branchTarget.VariablesBefore = newVariableState;
  						} else {
  							// Do not share data for several bytecodes
  							branchTarget.StackBefore = StackSlot.CloneStack(newStack, 0);
  							branchTarget.VariablesBefore = VariableSlot.CloneVariableState(newVariableState);
  						}
  						agenda.Push(branchTarget);
  					} else {
  						if (branchTarget.StackBefore.Count != newStack.Count) {
  							throw new Exception("Inconsistent stack size at " + byteCode.Name);
  						}
  						
  						// Be careful not to change our new data - it might be reused for several branch targets.
  						// In general, be careful that two bytecodes never share data structures.
  						
  						bool modified = false;
  						
  						// Merge stacks - modify the target
  						for (int i = 0; i < newStack.Count; i++) {
  							ByteCode[] oldPushedBy = branchTarget.StackBefore[i].PushedBy;
  							ByteCode[] newPushedBy = oldPushedBy.Union(newStack[i].PushedBy);
  							if (newPushedBy.Length > oldPushedBy.Length) {
  								branchTarget.StackBefore[i] = new StackSlot(newPushedBy, null);
  								modified = true;
  							}
  						}
  						
  						// Merge variables - modify the target
  						for (int i = 0; i < newVariableState.Length; i++) {
  							VariableSlot oldSlot = branchTarget.VariablesBefore[i];
  							VariableSlot newSlot = newVariableState[i];
  							// All can not be unioned further
  							if (!oldSlot.StoredByAll) {
  								if (newSlot.StoredByAll) {
  									branchTarget.VariablesBefore[i] = newSlot;
  									modified = true;
  								} else {
  									ByteCode[] oldStoredBy = oldSlot.StoredBy;
  									ByteCode[] newStoredBy = oldStoredBy.Union(newSlot.StoredBy);
  									if (newStoredBy.Length > oldStoredBy.Length) {
  										branchTarget.VariablesBefore[i] = new VariableSlot(newStoredBy, false);
  										modified = true;
  									}
  								}
  							}
  						}
  						
  						if (modified) {
  							agenda.Push(branchTarget);
  						}
  					}
  				}
  			}
  			
  			// Occasionally the compiler generates unreachable code - it can be usually just ignored
  			var reachableBody   = body.Where(b => b.StackBefore != null);
  			var unreachableBody = body.Where(b => b.StackBefore == null);
  			
  			// Genertate temporary variables to replace stack
  			// Unrachable code does not need temporary variables - the values are never pushed on the stack for consuption
  			foreach(ByteCode byteCode in reachableBody) {
  				int argIdx = 0;
  				int popCount = byteCode.PopCount ?? byteCode.StackBefore.Count;
  				for (int i = byteCode.StackBefore.Count - popCount; i < byteCode.StackBefore.Count; i++) {
  					ILVariable tmpVar = new ILVariable() { Name = string.Format("arg_{0:X2}_{1}", byteCode.Offset, argIdx), IsGenerated = true };
  					byteCode.StackBefore[i] = new StackSlot(byteCode.StackBefore[i].PushedBy, tmpVar);
  					foreach(ByteCode pushedBy in byteCode.StackBefore[i].PushedBy) {
  						if (pushedBy.StoreTo == null) {
  
gt: 							pushedBy.StoreTo = new List<ILVariable>(1);