mcs/class/dlr/Runtime/Microsoft.Scripting.Core/Compiler/VariableBinder.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.Collections.Generic;
  17 using System.Collections.ObjectModel;
  18 using System.Diagnostics;
  19 using System.Dynamic.Utils;
  20
  21 #if SILVERLIGHT
  22 using System.Core;
  23 #endif
  24
  25 #if !FEATURE_CORE_DLR
  26 namespace Microsoft.Scripting.Ast.Compiler {
  27 #else
  28 namespace System.Linq.Expressions.Compiler {
  29 #endif
  30     /// <summary>
  31     /// Determines if variables are closed over in nested lambdas and need to
  32     /// be hoisted.
  33     /// </summary>
  34     internal sealed class VariableBinder : ExpressionVisitor {
  35         private readonly AnalyzedTree _tree = new AnalyzedTree();
  36         private readonly Stack<CompilerScope> _scopes = new Stack<CompilerScope>();
  37         private readonly Stack<BoundConstants> _constants = new Stack<BoundConstants>();
  38         private bool _inQuote;
  39
  40         internal static AnalyzedTree Bind(LambdaExpression lambda) {
  41             var binder = new VariableBinder();
  42             binder.Visit(lambda);
  43             return binder._tree;
  44         }
  45
  46         private VariableBinder() {
  47         }
  48
  49         protected internal override Expression VisitConstant(ConstantExpression node) {
  50             // If we're in Quote, we can ignore constants completely
  51             if (_inQuote) {
  52                 return node;
  53             }
  54
  55             // Constants that can be emitted into IL don't need to be stored on
  56             // the delegate
  57             if (ILGen.CanEmitConstant(node.Value, node.Type)) {
  58                 return node;
  59             }
  60
  61             _constants.Peek().AddReference(node.Value, node.Type);
  62             return node;
  63         }
  64
  65         protected internal override Expression VisitUnary(UnaryExpression node) {
  66             if (node.NodeType == ExpressionType.Quote) {
  67                 bool savedInQuote = _inQuote;
  68                 _inQuote = true;
  69                 Visit(node.Operand);
  70                 _inQuote = savedInQuote;
  71             } else {
  72                 Visit(node.Operand);
  73             }
  74             return node;
  75         }
  76
  77         protected internal override Expression VisitLambda<T>(Expression<T> node) {
  78             _scopes.Push(_tree.Scopes[node] = new CompilerScope(node, true));
  79             _constants.Push(_tree.Constants[node] = new BoundConstants());
  80             Visit(MergeScopes(node));
  81             _constants.Pop();
  82             _scopes.Pop();
  83             return node;
  84         }
  85
  86         protected internal override Expression VisitInvocation(InvocationExpression node) {
  87             LambdaExpression lambda = node.LambdaOperand;
  88
  89             // optimization: inline code for literal lambda's directly
  90             if (lambda != null) {
  91                 // visit the lambda, but treat it more like a scope
  92                 _scopes.Push(_tree.Scopes[lambda] = new CompilerScope(lambda, false));
  93                 Visit(MergeScopes(lambda));
  94                 _scopes.Pop();
  95                 // visit the invoke's arguments
  96                 Visit(node.Arguments);
  97                 return node;
  98             }
  99
 100             return base.VisitInvocation(node);
 101         }
 102
 103         protected internal override Expression VisitBlock(BlockExpression node) {
 104             if (node.Variables.Count == 0) {
 105                 Visit(node.Expressions);
 106                 return node;
 107             }
 108             _scopes.Push(_tree.Scopes[node] = new CompilerScope(node, false));
 109             Visit(MergeScopes(node));
 110             _scopes.Pop();
 111             return node;
 112         }
 113
 114         protected override CatchBlock VisitCatchBlock(CatchBlock node) {
 115             if (node.Variable == null) {
 116                 Visit(node.Body);
 117                 return node;
 118             }
 119             _scopes.Push(_tree.Scopes[node] = new CompilerScope(node, false));
 120             Visit(node.Body);
 121             _scopes.Pop();
 122             return node;
 123         }
 124
 125         // If the immediate child is another scope, merge it into this one
 126         // This is an optimization to save environment allocations and
 127         // array accesses.
 128         private ReadOnlyCollection<Expression> MergeScopes(Expression node) {
 129             ReadOnlyCollection<Expression> body;
 130             var lambda = node as LambdaExpression;
 131             if (lambda != null) {
 132                 body = new ReadOnlyCollection<Expression>(new[] { lambda.Body });
 133             }  else {
 134                 body = ((BlockExpression)node).Expressions;
 135             }
 136
 137             var currentScope = _scopes.Peek();
 138
 139             // A block body is mergeable if the body only contains one single block node containing variables,
 140             // and the child block has the same type as the parent block.
 141             while (body.Count == 1 && body[0].NodeType == ExpressionType.Block) {
 142                 var block = (BlockExpression)body[0];
 143
 144                 if (block.Variables.Count > 0) {
 145                     // Make sure none of the variables are shadowed. If any
 146                     // are, we can't merge it.
 147                     foreach (var v in block.Variables) {
 148                         if (currentScope.Definitions.ContainsKey(v)) {
 149                             return body;
 150                         }
 151                     }
 152
 153                     // Otherwise, merge it
 154                     if (currentScope.MergedScopes == null) {
 155                         currentScope.MergedScopes = new Set<object>(ReferenceEqualityComparer<object>.Instance);
 156                     }
 157                     currentScope.MergedScopes.Add(block);
 158                     foreach (var v in block.Variables) {
 159                         currentScope.Definitions.Add(v, VariableStorageKind.Local);
 160                     }
 161                 }
 162                 node = block;
 163                 body = block.Expressions;
 164             }
 165             return body;
 166         }
 167
 168
 169         protected internal override Expression VisitParameter(ParameterExpression node) {
 170             Reference(node, VariableStorageKind.Local);
 171
 172             //
 173             // Track reference count so we can emit it in a more optimal way if
 174             // it is used a lot.
 175             //
 176             CompilerScope referenceScope = null;
 177             foreach (CompilerScope scope in _scopes) {
 178                 //
 179                 // There are two times we care about references:
 180                 //   1. When we enter a lambda, we want to cache frequently
 181                 //      used variables
 182                 //   2. When we enter a scope with closed-over variables, we
 183                 //      want to cache it immediately when we allocate the
 184                 //      closure slot for it
 185                 //
 186                 if (scope.IsMethod || scope.Definitions.ContainsKey(node)) {
 187                     referenceScope = scope;
 188                     break;
 189                 }
 190             }
 191
 192             Debug.Assert(referenceScope != null);
 193             if (referenceScope.ReferenceCount == null) {
 194                 referenceScope.ReferenceCount = new Dictionary<ParameterExpression, int>();
 195             }
 196
 197             Helpers.IncrementCount(node, referenceScope.ReferenceCount);
 198             return node;
 199         }
 200
 201         protected internal override Expression VisitRuntimeVariables(RuntimeVariablesExpression node) {
 202             foreach (var v in node.Variables) {
 203                 // Force hoisting of these variables
 204                 Reference(v, VariableStorageKind.Hoisted);
 205             }
 206             return node;
 207         }
 208
 209         private void Reference(ParameterExpression node, VariableStorageKind storage) {
 210             CompilerScope definition = null;
 211             foreach (CompilerScope scope in _scopes) {
 212                 if (scope.Definitions.ContainsKey(node)) {
 213                     definition = scope;
 214                     break;
 215                 }
 216                 scope.NeedsClosure = true;
 217                 if (scope.IsMethod) {
 218                     storage = VariableStorageKind.Hoisted;
 219                 }
 220             }
 221             if (definition == null) {
 222                 throw Error.UndefinedVariable(node.Name, node.Type, CurrentLambdaName);
 223             }
 224             if (storage == VariableStorageKind.Hoisted) {
 225                 if (node.IsByRef) {
 226                     throw Error.CannotCloseOverByRef(node.Name, CurrentLambdaName);
 227                 }
 228                 definition.Definitions[node] = VariableStorageKind.Hoisted;
 229             }
 230         }
 231
 232         private string CurrentLambdaName {
 233             get {
 234                 foreach (var scope in _scopes) {
 235                     var lambda = scope.Node as LambdaExpression;
 236                     if (lambda != null) {
 237                         return lambda.Name;
 238                     }
 239                 }
 240                 throw ContractUtils.Unreachable;
 241             }
 242         }
 243     }
 244 }