diff options
Diffstat (limited to 'ICSharpCode.Decompiler/ILAst/StateRange.cs')
| -rw-r--r-- | ICSharpCode.Decompiler/ILAst/StateRange.cs | 312 |
1 files changed, 0 insertions, 312 deletions
diff --git a/ICSharpCode.Decompiler/ILAst/StateRange.cs b/ICSharpCode.Decompiler/ILAst/StateRange.cs deleted file mode 100644 index ef27c498..00000000 --- a/ICSharpCode.Decompiler/ILAst/StateRange.cs +++ /dev/null @@ -1,312 +0,0 @@ -// Copyright (c) 2012 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.Generic; -using System.Diagnostics; -using System.Linq; -using Mono.Cecil; - -namespace ICSharpCode.Decompiler.ILAst -{ - internal struct Interval - { - public readonly int Start, End; - - public Interval(int start, int end) - { - Debug.Assert(start <= end || (start == 0 && end == -1)); - Start = start; - End = end; - } - - public override string ToString() - { - return string.Format("({0} to {1})", Start, End); - } - } - - internal class StateRange - { - readonly List<Interval> data = new List<Interval>(); - - public StateRange() - { - } - - public StateRange(int start, int end) - { - data.Add(new Interval(start, end)); - } - - public bool IsEmpty { - get { return data.Count == 0; } - } - - public bool Contains(int val) - { - foreach (Interval v in data) { - if (v.Start <= val && val <= v.End) - return true; - } - return false; - } - - public void UnionWith(StateRange other) - { - data.AddRange(other.data); - } - - /// <summary> - /// Unions this state range with (other intersect (minVal to maxVal)) - /// </summary> - public void UnionWith(StateRange other, int minVal, int maxVal) - { - foreach (Interval v in other.data) { - int start = Math.Max(v.Start, minVal); - int end = Math.Min(v.End, maxVal); - if (start <= end) - data.Add(new Interval(start, end)); - } - } - - /// <summary> - /// Merges overlapping interval ranges. - /// </summary> - public void Simplify() - { - if (data.Count < 2) - return; - data.Sort((a, b) => a.Start.CompareTo(b.Start)); - Interval prev = data[0]; - int prevIndex = 0; - for (int i = 1; i < data.Count; i++) { - Interval next = data[i]; - Debug.Assert(prev.Start <= next.Start); - if (next.Start <= prev.End + 1) { // intervals overlapping or touching - prev = new Interval(prev.Start, Math.Max(prev.End, next.End)); - data[prevIndex] = prev; - data[i] = new Interval(0, -1); // mark as deleted - } else { - prev = next; - prevIndex = i; - } - } - data.RemoveAll(i => i.Start > i.End); // remove all entries that were marked as deleted - } - - public override string ToString() - { - return string.Join(",", data); - } - - public Interval ToEnclosingInterval() - { - if (data.Count == 0) - throw new SymbolicAnalysisFailedException(); - return new Interval(data[0].Start, data[data.Count - 1].End); - } - } - - internal enum StateRangeAnalysisMode - { - IteratorMoveNext, - IteratorDispose, - AsyncMoveNext - } - - internal class StateRangeAnalysis - { - readonly StateRangeAnalysisMode mode; - readonly FieldDefinition stateField; - internal DefaultDictionary<ILNode, StateRange> ranges; - SymbolicEvaluationContext evalContext; - - internal Dictionary<MethodDefinition, StateRange> finallyMethodToStateRange; // used only for IteratorDispose - - /// <summary> - /// Initializes the state range logic: - /// Clears 'ranges' and sets 'ranges[entryPoint]' to the full range (int.MinValue to int.MaxValue) - /// </summary> - public StateRangeAnalysis(ILNode entryPoint, StateRangeAnalysisMode mode, FieldDefinition stateField, ILVariable cachedStateVar = null) - { - this.mode = mode; - this.stateField = stateField; - if (mode == StateRangeAnalysisMode.IteratorDispose) { - finallyMethodToStateRange = new Dictionary<MethodDefinition, StateRange>(); - } - - ranges = new DefaultDictionary<ILNode, StateRange>(n => new StateRange()); - ranges[entryPoint] = new StateRange(int.MinValue, int.MaxValue); - evalContext = new SymbolicEvaluationContext(stateField); - if (cachedStateVar != null) - evalContext.AddStateVariable(cachedStateVar); - } - - public int AssignStateRanges(List<ILNode> body, int bodyLength) - { - if (bodyLength == 0) - return 0; - for (int i = 0; i < bodyLength; i++) { - StateRange nodeRange = ranges[body[i]]; - nodeRange.Simplify(); - - ILLabel label = body[i] as ILLabel; - if (label != null) { - ranges[body[i + 1]].UnionWith(nodeRange); - continue; - } - - ILTryCatchBlock tryFinally = body[i] as ILTryCatchBlock; - if (tryFinally != null) { - if (mode == StateRangeAnalysisMode.IteratorDispose) { - if (tryFinally.CatchBlocks.Count != 0 || tryFinally.FaultBlock != null || tryFinally.FinallyBlock == null) - throw new SymbolicAnalysisFailedException(); - ranges[tryFinally.TryBlock].UnionWith(nodeRange); - if (tryFinally.TryBlock.Body.Count != 0) { - ranges[tryFinally.TryBlock.Body[0]].UnionWith(nodeRange); - AssignStateRanges(tryFinally.TryBlock.Body, tryFinally.TryBlock.Body.Count); - } - continue; - } else if (mode == StateRangeAnalysisMode.AsyncMoveNext) { - return i; - } else { - throw new SymbolicAnalysisFailedException(); - } - } - - ILExpression expr = body[i] as ILExpression; - if (expr == null) - throw new SymbolicAnalysisFailedException(); - switch (expr.Code) { - case ILCode.Switch: - { - SymbolicValue val = evalContext.Eval(expr.Arguments[0]); - if (val.Type != SymbolicValueType.State) - goto default; - ILLabel[] targetLabels = (ILLabel[])expr.Operand; - for (int j = 0; j < targetLabels.Length; j++) { - int state = j - val.Constant; - ranges[targetLabels[j]].UnionWith(nodeRange, state, state); - } - StateRange nextRange = ranges[body[i + 1]]; - nextRange.UnionWith(nodeRange, int.MinValue, -1 - val.Constant); - nextRange.UnionWith(nodeRange, targetLabels.Length - val.Constant, int.MaxValue); - break; - } - case ILCode.Br: - case ILCode.Leave: - ranges[(ILLabel)expr.Operand].UnionWith(nodeRange); - break; - case ILCode.Brtrue: - { - SymbolicValue val = evalContext.Eval(expr.Arguments[0]).AsBool(); - if (val.Type == SymbolicValueType.StateEquals) { - ranges[(ILLabel)expr.Operand].UnionWith(nodeRange, val.Constant, val.Constant); - StateRange nextRange = ranges[body[i + 1]]; - nextRange.UnionWith(nodeRange, int.MinValue, val.Constant - 1); - nextRange.UnionWith(nodeRange, val.Constant + 1, int.MaxValue); - break; - } else if (val.Type == SymbolicValueType.StateInEquals) { - ranges[body[i + 1]].UnionWith(nodeRange, val.Constant, val.Constant); - StateRange targetRange = ranges[(ILLabel)expr.Operand]; - targetRange.UnionWith(nodeRange, int.MinValue, val.Constant - 1); - targetRange.UnionWith(nodeRange, val.Constant + 1, int.MaxValue); - break; - } else { - goto default; - } - } - case ILCode.Nop: - ranges[body[i + 1]].UnionWith(nodeRange); - break; - case ILCode.Ret: - break; - case ILCode.Stloc: - { - SymbolicValue val = evalContext.Eval(expr.Arguments[0]); - if (val.Type == SymbolicValueType.State && val.Constant == 0) { - evalContext.AddStateVariable((ILVariable)expr.Operand); - goto case ILCode.Nop; - } else { - goto default; - } - } - case ILCode.Call: - // in some cases (e.g. foreach over array) the C# compiler produces a finally method outside of try-finally blocks - if (mode == StateRangeAnalysisMode.IteratorDispose) { - MethodDefinition mdef = (expr.Operand as MethodReference).ResolveWithinSameModule(); - if (mdef == null || finallyMethodToStateRange.ContainsKey(mdef)) - throw new SymbolicAnalysisFailedException(); - finallyMethodToStateRange.Add(mdef, nodeRange); - break; - } else { - goto default; - } - default: - if (mode == StateRangeAnalysisMode.IteratorDispose) { - throw new SymbolicAnalysisFailedException(); - } else { - return i; - } - } - } - return bodyLength; - } - - public void EnsureLabelAtPos(List<ILNode> body, ref int pos, ref int bodyLength) - { - if (pos > 0 && body[pos - 1] is ILLabel) { - pos--; - } else { - // ensure that the first element at body[pos] is a label: - ILLabel newLabel = new ILLabel(); - newLabel.Name = "YieldReturnEntryPoint"; - ranges[newLabel] = ranges[body[pos]]; // give the label the range of the instruction at body[pos] - body.Insert(pos, newLabel); - bodyLength++; - } - } - - public LabelRangeMapping CreateLabelRangeMapping(List<ILNode> body, int pos, int bodyLength) - { - LabelRangeMapping result = new LabelRangeMapping(); - CreateLabelRangeMapping(body, pos, bodyLength, result, false); - return result; - } - - void CreateLabelRangeMapping(List<ILNode> body, int pos, int bodyLength, LabelRangeMapping result, bool onlyInitialLabels) - { - for (int i = pos; i < bodyLength; i++) { - ILLabel label = body[i] as ILLabel; - if (label != null) { - result.Add(new KeyValuePair<ILLabel, StateRange>(label, ranges[label])); - } else { - ILTryCatchBlock tryCatchBlock = body[i] as ILTryCatchBlock; - if (tryCatchBlock != null) { - CreateLabelRangeMapping(tryCatchBlock.TryBlock.Body, 0, tryCatchBlock.TryBlock.Body.Count, result, true); - } else if (onlyInitialLabels) { - break; - } - } - } - } - } - - internal class LabelRangeMapping : List<KeyValuePair<ILLabel, StateRange>> {} -} |