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