← Back to branch summary

~ubuntu-branches/ubuntu/trusty/monodevelop/trusty-proposed

« back to all changes in this revision

Viewing changes to contrib/ICSharpCode.Decompiler/ILAst/StateRange.cs

  • Committer: Package Import Robot
  • Author(s): Jo Shields
  • Date: 2013-05-12 09:46:03 UTC
  • mto: This revision was merged to the branch mainline in revision 29.
  • Revision ID: package-import@ubuntu.com-20130512094603-mad323bzcxvmcam0
Tags: upstream-4.0.5+dfsg
ImportĀ upstreamĀ versionĀ 4.0.5+dfsg

Show diffs side-by-side

added added

removed removed

Lines of Context:
contrib/ICSharpCode.Decompiler/ILAst/StateRange.cs
 
1
ļ»æ// Copyright (c) 2012 AlphaSierraPapa for the SharpDevelop Team
 
2
// 
 
3
// Permission is hereby granted, free of charge, to any person obtaining a copy of this
 
4
// software and associated documentation files (the "Software"), to deal in the Software
 
5
// without restriction, including without limitation the rights to use, copy, modify, merge,
 
6
// publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons
 
7
// to whom the Software is furnished to do so, subject to the following conditions:
 
8
// 
 
9
// The above copyright notice and this permission notice shall be included in all copies or
 
10
// substantial portions of the Software.
 
11
// 
 
12
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
 
13
// INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
 
14
// PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
 
15
// FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
 
16
// OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 
17
// DEALINGS IN THE SOFTWARE.
 
18
 
 
19
using System;
 
20
using System.Collections.Generic;
 
21
using System.Diagnostics;
 
22
using System.Linq;
 
23
using Mono.Cecil;
 
24
 
 
25
namespace ICSharpCode.Decompiler.ILAst
 
26
{
 
27
        struct Interval
 
28
        {
 
29
                public readonly int Start, End;
 
30
                
 
31
                public Interval(int start, int end)
 
32
                {
 
33
                        Debug.Assert(start <= end || (start == 0 && end == -1));
 
34
                        this.Start = start;
 
35
                        this.End = end;
 
36
                }
 
37
                
 
38
                public override string ToString()
 
39
                {
 
40
                        return string.Format("({0} to {1})", Start, End);
 
41
                }
 
42
        }
 
43
        
 
44
        class StateRange
 
45
        {
 
46
                readonly List<Interval> data = new List<Interval>();
 
47
                
 
48
                public StateRange()
 
49
                {
 
50
                }
 
51
                
 
52
                public StateRange(int start, int end)
 
53
                {
 
54
                        this.data.Add(new Interval(start, end));
 
55
                }
 
56
                
 
57
                public bool IsEmpty {
 
58
                        get { return data.Count == 0; }
 
59
                }
 
60
                
 
61
                public bool Contains(int val)
 
62
                {
 
63
                        foreach (Interval v in data) {
 
64
                                if (v.Start <= val && val <= v.End)
 
65
                                        return true;
 
66
                        }
 
67
                        return false;
 
68
                }
 
69
                
 
70
                public void UnionWith(StateRange other)
 
71
                {
 
72
                        data.AddRange(other.data);
 
73
                }
 
74
                
 
75
                /// <summary>
 
76
                /// Unions this state range with (other intersect (minVal to maxVal))
 
77
                /// </summary>
 
78
                public void UnionWith(StateRange other, int minVal, int maxVal)
 
79
                {
 
80
                        foreach (Interval v in other.data) {
 
81
                                int start = Math.Max(v.Start, minVal);
 
82
                                int end = Math.Min(v.End, maxVal);
 
83
                                if (start <= end)
 
84
                                        data.Add(new Interval(start, end));
 
85
                        }
 
86
                }
 
87
                
 
88
                /// <summary>
 
89
                /// Merges overlapping interval ranges.
 
90
                /// </summary>
 
91
                public void Simplify()
 
92
                {
 
93
                        if (data.Count < 2)
 
94
                                return;
 
95
                        data.Sort((a, b) => a.Start.CompareTo(b.Start));
 
96
                        Interval prev = data[0];
 
97
                        int prevIndex = 0;
 
98
                        for (int i = 1; i < data.Count; i++) {
 
99
                                Interval next = data[i];
 
100
                                Debug.Assert(prev.Start <= next.Start);
 
101
                                if (next.Start <= prev.End + 1) { // intervals overlapping or touching
 
102
                                        prev = new Interval(prev.Start, Math.Max(prev.End, next.End));
 
103
                                        data[prevIndex] = prev;
 
104
                                        data[i] = new Interval(0, -1); // mark as deleted
 
105
                                } else {
 
106
                                        prev = next;
 
107
                                        prevIndex = i;
 
108
                                }
 
109
                        }
 
110
                        data.RemoveAll(i => i.Start > i.End); // remove all entries that were marked as deleted
 
111
                }
 
112
                
 
113
                public override string ToString()
 
114
                {
 
115
                        return string.Join(",", data);
 
116
                }
 
117
                
 
118
                public Interval ToEnclosingInterval()
 
119
                {
 
120
                        if (data.Count == 0)
 
121
                                throw new SymbolicAnalysisFailedException();
 
122
                        return new Interval(data[0].Start, data[data.Count - 1].End);
 
123
                }
 
124
        }
 
125
        
 
126
        enum StateRangeAnalysisMode
 
127
        {
 
128
                IteratorMoveNext,
 
129
                IteratorDispose,
 
130
                AsyncMoveNext
 
131
        }
 
132
        
 
133
        class StateRangeAnalysis
 
134
        {
 
135
                readonly StateRangeAnalysisMode mode;
 
136
                readonly FieldDefinition stateField;
 
137
                internal DefaultDictionary<ILNode, StateRange> ranges;
 
138
                SymbolicEvaluationContext evalContext;
 
139
                
 
140
                internal Dictionary<MethodDefinition, Interval> finallyMethodToStateInterval; // used only for IteratorDispose
 
141
                
 
142
                /// <summary>
 
143
                /// Initializes the state range logic:
 
144
                /// Clears 'ranges' and sets 'ranges[entryPoint]' to the full range (int.MinValue to int.MaxValue)
 
145
                /// </summary>
 
146
                public StateRangeAnalysis(ILNode entryPoint, StateRangeAnalysisMode mode, FieldDefinition stateField)
 
147
                {
 
148
                        this.mode = mode;
 
149
                        this.stateField = stateField;
 
150
                        if (mode == StateRangeAnalysisMode.IteratorDispose) {
 
151
                                finallyMethodToStateInterval = new Dictionary<MethodDefinition, Interval>();
 
152
                        }
 
153
                        
 
154
                        ranges = new DefaultDictionary<ILNode, StateRange>(n => new StateRange());
 
155
                        ranges[entryPoint] = new StateRange(int.MinValue, int.MaxValue);
 
156
                        evalContext = new SymbolicEvaluationContext(stateField);
 
157
                }
 
158
                
 
159
                public int AssignStateRanges(List<ILNode> body, int bodyLength)
 
160
                {
 
161
                        if (bodyLength == 0)
 
162
                                return 0;
 
163
                        for (int i = 0; i < bodyLength; i++) {
 
164
                                StateRange nodeRange = ranges[body[i]];
 
165
                                nodeRange.Simplify();
 
166
                                
 
167
                                ILLabel label = body[i] as ILLabel;
 
168
                                if (label != null) {
 
169
                                        ranges[body[i + 1]].UnionWith(nodeRange);
 
170
                                        continue;
 
171
                                }
 
172
                                
 
173
                                ILTryCatchBlock tryFinally = body[i] as ILTryCatchBlock;
 
174
                                if (tryFinally != null) {
 
175
                                        if (mode == StateRangeAnalysisMode.IteratorDispose) {
 
176
                                                if (tryFinally.CatchBlocks.Count != 0 || tryFinally.FaultBlock != null || tryFinally.FinallyBlock == null)
 
177
                                                        throw new SymbolicAnalysisFailedException();
 
178
                                                ranges[tryFinally.TryBlock].UnionWith(nodeRange);
 
179
                                                if (tryFinally.TryBlock.Body.Count != 0) {
 
180
                                                        ranges[tryFinally.TryBlock.Body[0]].UnionWith(nodeRange);
 
181
                                                        AssignStateRanges(tryFinally.TryBlock.Body, tryFinally.TryBlock.Body.Count);
 
182
                                                }
 
183
                                                continue;
 
184
                                        } else if (mode == StateRangeAnalysisMode.AsyncMoveNext) {
 
185
                                                return i;
 
186
                                        } else {
 
187
                                                throw new SymbolicAnalysisFailedException();
 
188
                                        }
 
189
                                }
 
190
                                
 
191
                                ILExpression expr = body[i] as ILExpression;
 
192
                                if (expr == null)
 
193
                                        throw new SymbolicAnalysisFailedException();
 
194
                                switch (expr.Code) {
 
195
                                        case ILCode.Switch:
 
196
                                                {
 
197
                                                        SymbolicValue val = evalContext.Eval(expr.Arguments[0]);
 
198
                                                        if (val.Type != SymbolicValueType.State)
 
199
                                                                goto default;
 
200
                                                        ILLabel[] targetLabels = (ILLabel[])expr.Operand;
 
201
                                                        for (int j = 0; j < targetLabels.Length; j++) {
 
202
                                                                int state = j - val.Constant;
 
203
                                                                ranges[targetLabels[j]].UnionWith(nodeRange, state, state);
 
204
                                                        }
 
205
                                                        StateRange nextRange = ranges[body[i + 1]];
 
206
                                                        nextRange.UnionWith(nodeRange, int.MinValue, -1 - val.Constant);
 
207
                                                        nextRange.UnionWith(nodeRange, targetLabels.Length - val.Constant, int.MaxValue);
 
208
                                                        break;
 
209
                                                }
 
210
                                        case ILCode.Br:
 
211
                                        case ILCode.Leave:
 
212
                                                ranges[(ILLabel)expr.Operand].UnionWith(nodeRange);
 
213
                                                break;
 
214
                                        case ILCode.Brtrue:
 
215
                                                {
 
216
                                                        SymbolicValue val = evalContext.Eval(expr.Arguments[0]);
 
217
                                                        if (val.Type == SymbolicValueType.StateEquals) {
 
218
                                                                ranges[(ILLabel)expr.Operand].UnionWith(nodeRange, val.Constant, val.Constant);
 
219
                                                                StateRange nextRange = ranges[body[i + 1]];
 
220
                                                                nextRange.UnionWith(nodeRange, int.MinValue, val.Constant - 1);
 
221
                                                                nextRange.UnionWith(nodeRange, val.Constant + 1, int.MaxValue);
 
222
                                                                break;
 
223
                                                        } else if (val.Type == SymbolicValueType.StateInEquals) {
 
224
                                                                ranges[body[i + 1]].UnionWith(nodeRange, val.Constant, val.Constant);
 
225
                                                                StateRange targetRange = ranges[(ILLabel)expr.Operand];
 
226
                                                                targetRange.UnionWith(nodeRange, int.MinValue, val.Constant - 1);
 
227
                                                                targetRange.UnionWith(nodeRange, val.Constant + 1, int.MaxValue);
 
228
                                                                break;
 
229
                                                        } else {
 
230
                                                                goto default;
 
231
                                                        }
 
232
                                                }
 
233
                                        case ILCode.Nop:
 
234
                                                ranges[body[i + 1]].UnionWith(nodeRange);
 
235
                                                break;
 
236
                                        case ILCode.Ret:
 
237
                                                break;
 
238
                                        case ILCode.Stloc:
 
239
                                                {
 
240
                                                        SymbolicValue val = evalContext.Eval(expr.Arguments[0]);
 
241
                                                        if (val.Type == SymbolicValueType.State && val.Constant == 0) {
 
242
                                                                evalContext.AddStateVariable((ILVariable)expr.Operand);
 
243
                                                                goto case ILCode.Nop;
 
244
                                                        } else {
 
245
                                                                goto default;
 
246
                                                        }
 
247
                                                }
 
248
                                        case ILCode.Call:
 
249
                                                // in some cases (e.g. foreach over array) the C# compiler produces a finally method outside of try-finally blocks
 
250
                                                if (mode == StateRangeAnalysisMode.IteratorDispose) {
 
251
                                                        MethodDefinition mdef = (expr.Operand as MethodReference).ResolveWithinSameModule();
 
252
                                                        if (mdef == null || finallyMethodToStateInterval.ContainsKey(mdef))
 
253
                                                                throw new SymbolicAnalysisFailedException();
 
254
                                                        finallyMethodToStateInterval.Add(mdef, nodeRange.ToEnclosingInterval());
 
255
                                                        break;
 
256
                                                } else {
 
257
                                                        goto default;
 
258
                                                }
 
259
                                        default:
 
260
                                                if (mode == StateRangeAnalysisMode.IteratorDispose) {
 
261
                                                        throw new SymbolicAnalysisFailedException();
 
262
                                                } else {
 
263
                                                        return i;
 
264
                                                }
 
265
                                }
 
266
                        }
 
267
                        return bodyLength;
 
268
                }
 
269
                
 
270
                public void EnsureLabelAtPos(List<ILNode> body, ref int pos, ref int bodyLength)
 
271
                {
 
272
                        if (pos > 0 && body[pos - 1] is ILLabel) {
 
273
                                pos--;
 
274
                        } else {
 
275
                                // ensure that the first element at body[pos] is a label:
 
276
                                ILLabel newLabel = new ILLabel();
 
277
                                newLabel.Name = "YieldReturnEntryPoint";
 
278
                                ranges[newLabel] = ranges[body[pos]]; // give the label the range of the instruction at body[pos]
 
279
                                body.Insert(pos, newLabel);
 
280
                                bodyLength++;
 
281
                        }
 
282
                }
 
283
                
 
284
                public LabelRangeMapping CreateLabelRangeMapping(List<ILNode> body, int pos, int bodyLength)
 
285
                {
 
286
                        LabelRangeMapping result = new LabelRangeMapping();
 
287
                        CreateLabelRangeMapping(body, pos, bodyLength, result, false);
 
288
                        return result;
 
289
                }
 
290
                
 
291
                void CreateLabelRangeMapping(List<ILNode> body, int pos, int bodyLength, LabelRangeMapping result, bool onlyInitialLabels)
 
292
                {
 
293
                        for (int i = pos; i < bodyLength; i++) {
 
294
                                ILLabel label = body[i] as ILLabel;
 
295
                                if (label != null) {
 
296
                                        result.Add(new KeyValuePair<ILLabel, StateRange>(label, ranges[label]));
 
297
                                } else {
 
298
                                        ILTryCatchBlock tryCatchBlock = body[i] as ILTryCatchBlock;
 
299
                                        if (tryCatchBlock != null) {
 
300
                                                CreateLabelRangeMapping(tryCatchBlock.TryBlock.Body, 0, tryCatchBlock.TryBlock.Body.Count, result, true);
 
301
                                        } else if (onlyInitialLabels) {
 
302
                                                break;
 
303
                                        }
 
304
                                }
 
305
                        }
 
306
                }
 
307
        }
 
308
        
 
309
        class LabelRangeMapping : List<KeyValuePair<ILLabel, StateRange>> {}
 
310
}