mcs/class/dlr/Runtime/Microsoft.Dynamic/Interpreter/Instructions/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 #if FEATURE_CORE_DLR
  17 using System.Linq.Expressions;
  18 #else
  19 using Microsoft.Scripting.Ast;
  20 #endif
  21
  22 using System;
  23 using System.Collections.Generic;
  24 using System.Diagnostics;
  25 using System.Linq;
  26 #if FEATURE_REFEMIT
  27 using System.Reflection.Emit;
  28 #endif
  29 using System.Text;
  30 using Microsoft.Scripting.Utils;
  31
  32 namespace Microsoft.Scripting.Interpreter {
  33
  34     /// <summary>
  35     /// Contains compiler state corresponding to a LabelTarget
  36     /// See also LabelScopeInfo.
  37     /// </summary>
  38     internal sealed class LabelInfo {
  39         // The tree node representing this label
  40         private readonly LabelTarget _node;
  41
  42         // The BranchLabel label, will be mutated if Node is redefined
  43         private BranchLabel _label;
  44
  45         // The blocks where this label is defined. If it has more than one item,
  46         // the blocks can't be jumped to except from a child block
  47         // If there's only 1 block (the common case) it's stored here, if there's multiple blocks it's stored
  48         // as a HashSet<LabelScopeInfo>
  49         private object _definitions;
  50
  51         // Blocks that jump to this block
  52         private readonly List<LabelScopeInfo> _references = new List<LabelScopeInfo>();
  53
  54         // True if at least one jump is across blocks
  55         // If we have any jump across blocks to this label, then the
  56         // LabelTarget can only be defined in one place
  57         private bool _acrossBlockJump;
  58
  59         internal LabelInfo(LabelTarget node) {
  60             _node = node;
  61         }
  62
  63         internal BranchLabel GetLabel(LightCompiler compiler) {
  64             EnsureLabel(compiler);
  65             return _label;
  66         }
  67
  68         internal void Reference(LabelScopeInfo block) {
  69             _references.Add(block);
  70             if (HasDefinitions) {
  71                 ValidateJump(block);
  72             }
  73         }
  74
  75         internal void Define(LabelScopeInfo block) {
  76             // Prevent the label from being shadowed, which enforces cleaner
  77             // trees. Also we depend on this for simplicity (keeping only one
  78             // active IL Label per LabelInfo)
  79             for (LabelScopeInfo j = block; j != null; j = j.Parent) {
  80                 if (j.ContainsTarget(_node)) {
  81                     throw new InvalidOperationException(String.Format("Label target already defined: {0}", _node.Name));
  82                 }
  83             }
  84
  85             AddDefinition(block);
  86             block.AddLabelInfo(_node, this);
  87
  88             // Once defined, validate all jumps
  89             if (HasDefinitions && !HasMultipleDefinitions) {
  90                 foreach (var r in _references) {
  91                     ValidateJump(r);
  92                 }
  93             } else {
  94                 // Was just redefined, if we had any across block jumps, they're
  95                 // now invalid
  96                 if (_acrossBlockJump) {
  97                     throw new InvalidOperationException("Ambiguous jump");
  98                 }
  99                 // For local jumps, we need a new IL label
 100                 // This is okay because:
 101                 //   1. no across block jumps have been made or will be made
 102                 //   2. we don't allow the label to be shadowed
 103                 _label = null;
 104             }
 105         }
 106
 107         private void ValidateJump(LabelScopeInfo reference) {
 108             // look for a simple jump out
 109             for (LabelScopeInfo j = reference; j != null; j = j.Parent) {
 110                 if (DefinedIn(j)) {
 111                     // found it, jump is valid!
 112                     return;
 113                 }
 114                 if (j.Kind == LabelScopeKind.Filter) {
 115                     break;
 116                 }
 117             }
 118
 119             _acrossBlockJump = true;
 120
 121             if (HasMultipleDefinitions) {
 122                 throw new InvalidOperationException(String.Format("Ambiguous jump {0}", _node.Name));
 123             }
 124
 125             // We didn't find an outward jump. Look for a jump across blocks
 126             LabelScopeInfo def = FirstDefinition();
 127             LabelScopeInfo common = CommonNode(def, reference, b => b.Parent);
 128
 129             // Validate that we aren't jumping across a finally
 130             for (LabelScopeInfo j = reference; j != common; j = j.Parent) {
 131                 if (j.Kind == LabelScopeKind.Filter) {
 132                     throw new InvalidOperationException("Control cannot leave filter test");
 133                 }
 134             }
 135
 136             // Valdiate that we aren't jumping into a catch or an expression
 137             for (LabelScopeInfo j = def; j != common; j = j.Parent) {
 138                 if (!j.CanJumpInto) {
 139                     if (j.Kind == LabelScopeKind.Expression) {
 140                         throw new InvalidOperationException("Control cannot enter an expression");
 141                     } else {
 142                         throw new InvalidOperationException("Control cannot enter try");
 143                     }
 144                 }
 145             }
 146         }
 147
 148         internal void ValidateFinish() {
 149             // Make sure that if this label was jumped to, it is also defined
 150             if (_references.Count > 0 && !HasDefinitions) {
 151                 throw new InvalidOperationException("label target undefined");
 152             }
 153         }
 154
 155         private void EnsureLabel(LightCompiler compiler) {
 156             if (_label == null) {
 157                 _label = compiler.Instructions.MakeLabel();
 158             }
 159         }
 160
 161         private bool DefinedIn(LabelScopeInfo scope) {
 162             if (_definitions == scope) {
 163                 return true;
 164             }
 165
 166             HashSet<LabelScopeInfo> definitions = _definitions as HashSet<LabelScopeInfo>;
 167             if (definitions != null) {
 168                 return definitions.Contains(scope);
 169             }
 170             return false;
 171         }
 172
 173         private bool HasDefinitions {
 174             get {
 175                 return _definitions != null;
 176             }
 177         }
 178
 179         private LabelScopeInfo FirstDefinition() {
 180             LabelScopeInfo scope = _definitions as LabelScopeInfo;
 181             if (scope != null) {
 182                 return scope;
 183             }
 184             return ((HashSet<LabelScopeInfo>)_definitions).First();
 185         }
 186
 187         private void AddDefinition(LabelScopeInfo scope) {
 188             if (_definitions == null) {
 189                 _definitions = scope;
 190             } else {
 191                 HashSet<LabelScopeInfo> set = _definitions as HashSet<LabelScopeInfo>;
 192                 if(set == null) {
 193                     _definitions = set = new HashSet<LabelScopeInfo>() { (LabelScopeInfo)_definitions };
 194                 }
 195                 set.Add(scope);
 196             }
 197         }
 198
 199         private bool HasMultipleDefinitions {
 200             get {
 201                 return _definitions is HashSet<LabelScopeInfo>;
 202             }
 203         }
 204
 205         internal static T CommonNode<T>(T first, T second, Func<T, T> parent) where T : class {
 206             var cmp = EqualityComparer<T>.Default;
 207             if (cmp.Equals(first, second)) {
 208                 return first;
 209             }
 210             var set = new HashSet<T>(cmp);
 211             for (T t = first; t != null; t = parent(t)) {
 212                 set.Add(t);
 213             }
 214             for (T t = second; t != null; t = parent(t)) {
 215                 if (set.Contains(t)) {
 216                     return t;
 217                 }
 218             }
 219             return null;
 220         }
 221     }
 222
 223     public enum LabelScopeKind {
 224         // any "statement like" node that can be jumped into
 225         Statement,
 226
 227         // these correspond to the node of the same name
 228         Block,
 229         Switch,
 230         Lambda,
 231         Try,
 232
 233         // these correspond to the part of the try block we're in
 234         Catch,
 235         Finally,
 236         Filter,
 237
 238         // the catch-all value for any other expression type
 239         // (means we can't jump into it)
 240         Expression,
 241     }
 242
 243     //
 244     // Tracks scoping information for LabelTargets. Logically corresponds to a
 245     // "label scope". Even though we have arbitrary goto support, we still need
 246     // to track what kinds of nodes that gotos are jumping through, both to
 247     // emit property IL ("leave" out of a try block), and for validation, and
 248     // to allow labels to be duplicated in the tree, as long as the jumps are
 249     // considered "up only" jumps.
 250     //
 251     // We create one of these for every Expression that can be jumped into, as
 252     // well as creating them for the first expression we can't jump into. The
 253     // "Kind" property indicates what kind of scope this is.
 254     //
 255     internal sealed class LabelScopeInfo {
 256         private HybridReferenceDictionary<LabelTarget, LabelInfo> Labels; // lazily allocated, we typically use this only once every 6th-7th block
 257         internal readonly LabelScopeKind Kind;
 258         internal readonly LabelScopeInfo Parent;
 259
 260         internal LabelScopeInfo(LabelScopeInfo parent, LabelScopeKind kind) {
 261             Parent = parent;
 262             Kind = kind;
 263         }
 264
 265         /// <summary>
 266         /// Returns true if we can jump into this node
 267         /// </summary>
 268         internal bool CanJumpInto {
 269             get {
 270                 switch (Kind) {
 271                     case LabelScopeKind.Block:
 272                     case LabelScopeKind.Statement:
 273                     case LabelScopeKind.Switch:
 274                     case LabelScopeKind.Lambda:
 275                         return true;
 276                 }
 277                 return false;
 278             }
 279         }
 280
 281
 282         internal bool ContainsTarget(LabelTarget target) {
 283             if (Labels == null) {
 284                 return false;
 285             }
 286
 287             return Labels.ContainsKey(target);
 288         }
 289
 290         internal bool TryGetLabelInfo(LabelTarget target, out LabelInfo info) {
 291             if (Labels == null) {
 292                 info = null;
 293                 return false;
 294             }
 295
 296             return Labels.TryGetValue(target, out info);
 297         }
 298
 299         internal void AddLabelInfo(LabelTarget target, LabelInfo info) {
 300             Debug.Assert(CanJumpInto);
 301
 302             if (Labels == null) {
 303                 Labels = new HybridReferenceDictionary<LabelTarget, LabelInfo>();
 304             }
 305
 306             Labels[target] = info;
 307         }
 308     }
 309 }