mcs/class/dlr/Runtime/Microsoft.Dynamic/Interpreter/LightLambdaClosureVisitor.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.Runtime.CompilerServices;
  25 using Microsoft.Scripting.Utils;
  26 using AstUtils = Microsoft.Scripting.Ast.Utils;
  27
  28 namespace Microsoft.Scripting.Interpreter {
  29
  30     /// <summary>
  31     /// Visits a LambdaExpression, replacing the constants with direct accesses
  32     /// to their StrongBox fields. This is very similar to what
  33     /// ExpressionQuoter does for LambdaCompiler.
  34     ///
  35     /// Also inserts debug information tracking similar to what the interpreter
  36     /// would do.
  37     /// </summary>
  38     internal sealed class LightLambdaClosureVisitor : ExpressionVisitor {
  39         /// <summary>
  40         /// Local variable mapping.
  41         /// </summary>
  42         private readonly Dictionary<ParameterExpression, LocalVariable> _closureVars;
  43
  44         /// <summary>
  45         /// The variable that holds onto the StrongBox{object}[] closure from
  46         /// the interpreter
  47         /// </summary>
  48         private readonly ParameterExpression _closureArray;
  49
  50         /// <summary>
  51         /// A stack of variables that are defined in nested scopes. We search
  52         /// this first when resolving a variable in case a nested scope shadows
  53         /// one of our variable instances.
  54         /// </summary>
  55         private readonly Stack<HashSet<ParameterExpression>> _shadowedVars = new Stack<HashSet<ParameterExpression>>();
  56
  57         private LightLambdaClosureVisitor(Dictionary<ParameterExpression, LocalVariable> closureVariables, ParameterExpression closureArray) {
  58             Assert.NotNull(closureVariables, closureArray);
  59             _closureArray = closureArray;
  60             _closureVars = closureVariables;
  61         }
  62
  63         /// <summary>
  64         /// Walks the lambda and produces a higher order function, which can be
  65         /// used to bind the lambda to a closure array from the interpreter.
  66         /// </summary>
  67         /// <param name="lambda">The lambda to bind.</param>
  68         /// <param name="closureVariables">Variables which are being accessed defined in the outer scope.</param>
  69         /// <returns>A delegate that can be called to produce a delegate bound to the passed in closure array.</returns>
  70         internal static Func<StrongBox<object>[], Delegate> BindLambda(LambdaExpression lambda, Dictionary<ParameterExpression, LocalVariable> closureVariables) {
  71             // 1. Create rewriter
  72             var closure = Expression.Parameter(typeof(StrongBox<object>[]), "closure");
  73             var visitor = new LightLambdaClosureVisitor(closureVariables, closure);
  74
  75             // 2. Visit the lambda
  76             lambda = (LambdaExpression)visitor.Visit(lambda);
  77
  78             // 3. Create a higher-order function which fills in the parameters
  79             var result = Expression.Lambda<Func<StrongBox<object>[], Delegate>>(lambda, closure);
  80
  81             // 4. Compile it
  82             return result.Compile();
  83         }
  84
  85         #region closures
  86
  87         protected override Expression VisitLambda<T>(Expression<T> node) {
  88             _shadowedVars.Push(new HashSet<ParameterExpression>(node.Parameters));
  89             Expression b = Visit(node.Body);
  90             _shadowedVars.Pop();
  91             if (b == node.Body) {
  92                 return node;
  93             }
  94             return Expression.Lambda<T>(b, node.Name, node.TailCall, node.Parameters);
  95         }
  96
  97         protected override Expression VisitBlock(BlockExpression node) {
  98             if (node.Variables.Count > 0) {
  99                 _shadowedVars.Push(new HashSet<ParameterExpression>(node.Variables));
 100             }
 101             var b = Visit(node.Expressions);
 102             if (node.Variables.Count > 0) {
 103                 _shadowedVars.Pop();
 104             }
 105             if (b == node.Expressions) {
 106                 return node;
 107             }
 108             return Expression.Block(node.Variables, b);
 109         }
 110
 111         protected override CatchBlock VisitCatchBlock(CatchBlock node) {
 112             if (node.Variable != null) {
 113                 _shadowedVars.Push(new HashSet<ParameterExpression>(new[] { node.Variable }));
 114             }
 115             Expression b = Visit(node.Body);
 116             Expression f = Visit(node.Filter);
 117             if (node.Variable != null) {
 118                 _shadowedVars.Pop();
 119             }
 120             if (b == node.Body && f == node.Filter) {
 121                 return node;
 122             }
 123             return Expression.MakeCatchBlock(node.Test, node.Variable, b, f);
 124         }
 125
 126         protected override Expression VisitRuntimeVariables(RuntimeVariablesExpression node) {
 127             int count = node.Variables.Count;
 128             var boxes = new List<Expression>();
 129             var vars = new List<ParameterExpression>();
 130             var indexes = new int[count];
 131             for (int i = 0; i < count; i++) {
 132                 Expression box = GetClosureItem(node.Variables[i], false);
 133                 if (box == null) {
 134                     indexes[i] = vars.Count;
 135                     vars.Add(node.Variables[i]);
 136                 } else {
 137                     indexes[i] = -1 - boxes.Count;
 138                     boxes.Add(box);
 139                 }
 140             }
 141
 142             // No variables were rewritten. Just return the original node.
 143             if (boxes.Count == 0) {
 144                 return node;
 145             }
 146
 147             var boxesArray = Expression.NewArrayInit(typeof(IStrongBox), boxes);
 148
 149             // All of them were rewritten. Just return the array, wrapped in a
 150             // read-only collection.
 151             if (vars.Count == 0) {
 152                 return Expression.Invoke(
 153                     Expression.Constant((Func<IStrongBox[], IRuntimeVariables>)RuntimeVariables.Create),
 154                     boxesArray
 155                 );
 156             }
 157
 158             // Otherwise, we need to return an object that merges them
 159             Func<IRuntimeVariables, IRuntimeVariables, int[], IRuntimeVariables> helper = MergedRuntimeVariables.Create;
 160             return Expression.Invoke(AstUtils.Constant(helper), Expression.RuntimeVariables(vars), boxesArray, AstUtils.Constant(indexes));
 161         }
 162
 163         protected override Expression VisitParameter(ParameterExpression node) {
 164             Expression closureItem = GetClosureItem(node, true);
 165             if (closureItem == null) {
 166                 return node;
 167             }
 168             // Convert can go away if we switch to strongly typed StrongBox
 169             return Ast.Utils.Convert(closureItem, node.Type);
 170         }
 171
 172         protected override Expression VisitBinary(BinaryExpression node) {
 173             if (node.NodeType == ExpressionType.Assign &&
 174                 node.Left.NodeType == ExpressionType.Parameter) {
 175
 176                 var variable = (ParameterExpression)node.Left;
 177                 Expression closureItem = GetClosureItem(variable, true);
 178                 if (closureItem != null) {
 179                     // We need to convert to object to store the value in the box.
 180                     return Expression.Block(
 181                         new[] { variable },
 182                         Expression.Assign(variable, Visit(node.Right)),
 183                         Expression.Assign(closureItem, Ast.Utils.Convert(variable, typeof(object))),
 184                         variable
 185                     );
 186                 }
 187             }
 188             return base.VisitBinary(node);
 189         }
 190
 191         private Expression GetClosureItem(ParameterExpression variable, bool unbox) {
 192             // Skip variables that are shadowed by a nested scope/lambda
 193             foreach (HashSet<ParameterExpression> hidden in _shadowedVars) {
 194                 if (hidden.Contains(variable)) {
 195                     return null;
 196                 }
 197             }
 198
 199             LocalVariable loc;
 200             if (!_closureVars.TryGetValue(variable, out loc)) {
 201                 throw new InvalidOperationException("unbound variable: " + variable.Name);
 202             }
 203
 204             var result = loc.LoadFromArray(null, _closureArray);
 205             return (unbox) ? LightCompiler.Unbox(result) : result;
 206         }
 207
 208         protected override Expression VisitExtension(Expression node) {
 209             // Reduce extensions now so we can find embedded variables
 210             return Visit(node.ReduceExtensions());
 211         }
 212
 213
 214         #region MergedRuntimeVariables
 215
 216         /// <summary>
 217         /// Provides a list of variables, supporing read/write of the values
 218         /// </summary>
 219         private sealed class MergedRuntimeVariables : IRuntimeVariables {
 220             private readonly IRuntimeVariables _first;
 221             private readonly IRuntimeVariables _second;
 222
 223             // For reach item, the index into the first or second list
 224             // Positive values mean the first array, negative means the second
 225             private readonly int[] _indexes;
 226
 227             private MergedRuntimeVariables(IRuntimeVariables first, IRuntimeVariables second, int[] indexes) {
 228                 _first = first;
 229                 _second = second;
 230                 _indexes = indexes;
 231             }
 232
 233             internal static IRuntimeVariables Create(IRuntimeVariables first, IRuntimeVariables second, int[] indexes) {
 234                 return new MergedRuntimeVariables(first, second, indexes);
 235             }
 236
 237             int IRuntimeVariables.Count {
 238                 get { return _indexes.Length; }
 239             }
 240
 241             object IRuntimeVariables.this[int index] {
 242                 get {
 243                     index = _indexes[index];
 244                     return (index >= 0) ? _first[index] : _second[-1 - index];
 245                 }
 246                 set {
 247                     index = _indexes[index];
 248                     if (index >= 0) {
 249                         _first[index] = value;
 250                     } else {
 251                         _second[-1 - index] = value;
 252                     }
 253                 }
 254             }
 255         }
 256         #endregion
 257
 258         #endregion
 259     }
 260 }