Merge pull request #347 from JamesB7/master
[mono.git] / mcs / class / dlr / Runtime / Microsoft.Scripting.Core / Compiler / LabelInfo.cs
1 /* ****************************************************************************
2  *
3  * Copyright (c) Microsoft Corporation. 
4  *
5  * This source code is subject to terms and conditions of the Apache License, Version 2.0. A 
6  * copy of the license can be found in the License.html file at the root of this distribution. If 
7  * you cannot locate the  Apache License, Version 2.0, please send an email to 
8  * dlr@microsoft.com. By using this source code in any fashion, you are agreeing to be bound 
9  * by the terms of the Apache License, Version 2.0.
10  *
11  * You must not remove this notice, or any other, from this software.
12  *
13  *
14  * ***************************************************************************/
15
16 using System;
17 using System.Collections.Generic;
18 using System.Diagnostics;
19 using System.Dynamic.Utils;
20 using System.Reflection.Emit;
21
22 #if !FEATURE_CORE_DLR
23 namespace Microsoft.Scripting.Ast.Compiler {
24 #else
25 namespace System.Linq.Expressions.Compiler {
26 #endif
27 #if !FEATURE_CORE_DLR || SILVERLIGHT
28     using ILGenerator = OffsetTrackingILGenerator;
29 #endif
30
31     /// <summary>
32     /// Contains compiler state corresponding to a LabelTarget
33     /// See also LabelScopeInfo.
34     /// </summary>
35     internal sealed class LabelInfo {
36         // The tree node representing this label
37         private readonly LabelTarget _node;
38
39         // The IL label, will be mutated if Node is redefined
40         private Label _label;
41         private bool _labelDefined;
42
43         internal Label Label {
44             get {
45                 EnsureLabelAndValue();
46                 return _label;
47             }
48         }
49
50         // The local that carries the label's value, if any
51         private LocalBuilder _value;
52
53         // The blocks where this label is defined. If it has more than one item,
54         // the blocks can't be jumped to except from a child block
55         private readonly Set<LabelScopeInfo> _definitions = new Set<LabelScopeInfo>();
56
57         // Blocks that jump to this block
58         private readonly List<LabelScopeInfo> _references = new List<LabelScopeInfo>();
59
60         // True if this label is the last thing in this block
61         // (meaning we can emit a direct return)
62         private readonly bool _canReturn;
63
64         // True if at least one jump is across blocks
65         // If we have any jump across blocks to this label, then the
66         // LabelTarget can only be defined in one place
67         private bool _acrossBlockJump;
68
69         // Until we have more information, default to a leave instruction,
70         // which always works. Note: leave spills the stack, so we need to
71         // ensure that StackSpiller has guarenteed us an empty stack at this
72         // point. Otherwise Leave and Branch are not equivalent
73         private OpCode _opCode = OpCodes.Leave;
74
75         private readonly ILGenerator _ilg;
76
77         internal LabelInfo(ILGenerator il, LabelTarget node, bool canReturn) {
78             _ilg = il;
79             _node = node;
80             _canReturn = canReturn;
81         }
82
83         internal bool CanReturn {
84             get { return _canReturn; }
85         }
86
87         /// <summary>
88         /// Indicates if it is legal to emit a "branch" instruction based on
89         /// currently available information. Call the Reference method before 
90         /// using this property.
91         /// </summary>
92         internal bool CanBranch {
93             get { return _opCode != OpCodes.Leave; }
94         }
95
96         internal void Reference(LabelScopeInfo block) {
97             _references.Add(block);
98             if (_definitions.Count > 0) {
99                 ValidateJump(block);
100             }
101         }
102
103         // Returns true if the label was successfully defined
104         // or false if the label is now ambiguous
105         internal void Define(LabelScopeInfo block) {
106             // Prevent the label from being shadowed, which enforces cleaner
107             // trees. Also we depend on this for simplicity (keeping only one
108             // active IL Label per LabelInfo)
109             for (LabelScopeInfo j = block; j != null; j = j.Parent) {
110                 if (j.ContainsTarget(_node)) {
111                     throw Error.LabelTargetAlreadyDefined(_node.Name);
112                 }
113             }
114
115             _definitions.Add(block);
116             block.AddLabelInfo(_node, this);
117
118             // Once defined, validate all jumps
119             if (_definitions.Count == 1) {
120                 foreach (var r in _references) {
121                     ValidateJump(r);
122                 }
123             } else {
124                 // Was just redefined, if we had any across block jumps, they're
125                 // now invalid
126                 if (_acrossBlockJump) {
127                     throw Error.AmbiguousJump(_node.Name);
128                 }
129                 // For local jumps, we need a new IL label
130                 // This is okay because:
131                 //   1. no across block jumps have been made or will be made
132                 //   2. we don't allow the label to be shadowed
133                 _labelDefined = false;
134             }
135         }
136
137         private void ValidateJump(LabelScopeInfo reference) {
138             // Assume we can do a ret/branch
139             _opCode = _canReturn ? OpCodes.Ret : OpCodes.Br;
140
141             // look for a simple jump out
142             for (LabelScopeInfo j = reference; j != null; j = j.Parent) {
143                 if (_definitions.Contains(j)) {
144                     // found it, jump is valid!
145                     return;
146                 }
147                 if (j.Kind == LabelScopeKind.Finally ||
148                     j.Kind == LabelScopeKind.Filter) {
149                     break;
150                 }
151                 if (j.Kind == LabelScopeKind.Try ||
152                     j.Kind == LabelScopeKind.Catch) {
153                     _opCode = OpCodes.Leave;
154                 }
155             }
156
157             _acrossBlockJump = true;
158             if (_node != null && _node.Type != typeof(void)) {
159                 throw Error.NonLocalJumpWithValue(_node.Name);
160             }
161
162             if (_definitions.Count > 1) {
163                 throw Error.AmbiguousJump(_node.Name);
164             }
165
166             // We didn't find an outward jump. Look for a jump across blocks
167             LabelScopeInfo def = _definitions.First();
168             LabelScopeInfo common = Helpers.CommonNode(def, reference, b => b.Parent);
169
170             // Assume we can do a ret/branch
171             _opCode = _canReturn ? OpCodes.Ret : OpCodes.Br;
172
173             // Validate that we aren't jumping across a finally
174             for (LabelScopeInfo j = reference; j != common; j = j.Parent) {
175                 if (j.Kind == LabelScopeKind.Finally) {
176                     throw Error.ControlCannotLeaveFinally();
177                 }
178                 if (j.Kind == LabelScopeKind.Filter) {
179                     throw Error.ControlCannotLeaveFilterTest();
180                 }
181                 if (j.Kind == LabelScopeKind.Try ||
182                     j.Kind == LabelScopeKind.Catch) {
183                     _opCode = OpCodes.Leave;
184                 }
185             }
186
187             // Valdiate that we aren't jumping into a catch or an expression
188             for (LabelScopeInfo j = def; j != common; j = j.Parent) {
189                 if (!j.CanJumpInto) {
190                     if (j.Kind == LabelScopeKind.Expression) {
191                         throw Error.ControlCannotEnterExpression();
192                     } else {
193                         throw Error.ControlCannotEnterTry();
194                     }
195                 }
196             }
197         }
198
199         internal void ValidateFinish() {
200             // Make sure that if this label was jumped to, it is also defined
201             if (_references.Count > 0 && _definitions.Count == 0) {
202                 throw Error.LabelTargetUndefined(_node.Name);
203             }
204         }
205
206         internal void EmitJump() {
207             // Return directly if we can
208             if (_opCode == OpCodes.Ret) {
209                 _ilg.Emit(OpCodes.Ret);
210             } else {
211                 StoreValue();
212                 _ilg.Emit(_opCode, Label);
213             }
214         }
215
216         private void StoreValue() {
217             EnsureLabelAndValue();
218             if (_value != null) {
219                 _ilg.Emit(OpCodes.Stloc, _value);
220             }
221         }
222
223         internal void Mark() {
224             if (_canReturn) {
225                 // Don't mark return labels unless they were actually jumped to
226                 // (returns are last so we know for sure if anyone jumped to it)
227                 if (!_labelDefined) {
228                     // We don't even need to emit the "ret" because
229                     // LambdaCompiler does that for us.
230                     return;
231                 }
232
233                 // Otherwise, emit something like:
234                 // ret
235                 // <marked label>:
236                 // ldloc <value>
237                 _ilg.Emit(OpCodes.Ret);
238             } else {
239
240                 // For the normal case, we emit:
241                 // stloc <value>
242                 // <marked label>:
243                 // ldloc <value>
244                 StoreValue();
245             }
246             MarkWithEmptyStack();
247         }
248
249         // Like Mark, but assumes the stack is empty
250         internal void MarkWithEmptyStack() {
251             _ilg.MarkLabel(Label);
252             if (_value != null) {
253                 // We always read the value from a local, because we don't know
254                 // if there will be a "leave" instruction targeting it ("branch"
255                 // preserves its stack, but "leave" empties the stack)
256                 _ilg.Emit(OpCodes.Ldloc, _value);
257             }
258         }
259
260         private void EnsureLabelAndValue() {
261             if (!_labelDefined) {
262                 _labelDefined = true;
263                 _label = _ilg.DefineLabel();
264                 if (_node != null && _node.Type != typeof(void)) {
265                     _value = _ilg.DeclareLocal(_node.Type);
266                 }
267             }
268         }
269     }
270
271     internal enum LabelScopeKind {
272         // any "statement like" node that can be jumped into
273         Statement,
274
275         // these correspond to the node of the same name
276         Block,
277         Switch,
278         Lambda,
279         Try,
280
281         // these correspond to the part of the try block we're in
282         Catch,
283         Finally,
284         Filter,
285
286         // the catch-all value for any other expression type
287         // (means we can't jump into it)
288         Expression,
289     }
290
291     //
292     // Tracks scoping information for LabelTargets. Logically corresponds to a
293     // "label scope". Even though we have arbitrary goto support, we still need
294     // to track what kinds of nodes that gotos are jumping through, both to
295     // emit property IL ("leave" out of a try block), and for validation, and
296     // to allow labels to be duplicated in the tree, as long as the jumps are
297     // considered "up only" jumps.
298     //
299     // We create one of these for every Expression that can be jumped into, as
300     // well as creating them for the first expression we can't jump into. The
301     // "Kind" property indicates what kind of scope this is.
302     //
303     internal sealed class LabelScopeInfo {
304         private Dictionary<LabelTarget, LabelInfo> Labels; // lazily allocated, we typically use this only once every 6th-7th block
305         internal readonly LabelScopeKind Kind;
306         internal readonly LabelScopeInfo Parent;
307
308         internal LabelScopeInfo(LabelScopeInfo parent, LabelScopeKind kind) {
309             Parent = parent;
310             Kind = kind;
311         }
312
313         /// <summary>
314         /// Returns true if we can jump into this node
315         /// </summary>
316         internal bool CanJumpInto {
317             get {
318                 switch (Kind) {
319                     case LabelScopeKind.Block:
320                     case LabelScopeKind.Statement:
321                     case LabelScopeKind.Switch:
322                     case LabelScopeKind.Lambda:
323                         return true;
324                 }
325                 return false;
326             }
327         }
328
329
330         internal bool ContainsTarget(LabelTarget target) {
331             if (Labels == null) {
332                 return false;
333             }
334
335             return Labels.ContainsKey(target);
336         }
337
338         internal bool TryGetLabelInfo(LabelTarget target, out LabelInfo info) {
339             if (Labels == null) {
340                 info = null;
341                 return false;
342             }
343
344             return Labels.TryGetValue(target, out info);
345         }
346
347         internal void AddLabelInfo(LabelTarget target, LabelInfo info) {
348             Debug.Assert(CanJumpInto);
349
350             if (Labels == null) {
351                 Labels = new Dictionary<LabelTarget, LabelInfo>();
352             }
353
354             Labels.Add(target, info);
355         }
356     }
357 }