File: System\Linq\Expressions\Compiler\CompilerScope.cs
Web Access
Project: src\src\libraries\System.Linq.Expressions\src\System.Linq.Expressions.csproj (System.Linq.Expressions)
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
 
using System.Collections;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using System.Dynamic.Utils;
using System.Reflection.Emit;
using System.Runtime.CompilerServices;
using static System.Linq.Expressions.CachedReflectionInfo;
 
namespace System.Linq.Expressions.Compiler
{
    internal enum VariableStorageKind
    {
        Local,
        Hoisted
    }
 
    /// <summary>
    /// CompilerScope is the data structure which the Compiler keeps information
    /// related to compiling scopes. It stores the following information:
    ///   1. Parent relationship (for resolving variables)
    ///   2. Information about hoisted variables
    ///   3. Information for resolving closures
    ///
    /// Instances are produced by VariableBinder, which does a tree walk
    /// looking for scope nodes: LambdaExpression, BlockExpression, and CatchBlock.
    /// </summary>
    [RequiresDynamicCode(Expression.StrongBoxRequiresDynamicCode)]
    internal sealed partial class CompilerScope
    {
        /// <summary>
        /// parent scope, if any
        /// </summary>
        private CompilerScope? _parent;
 
        /// <summary>
        /// The expression node for this scope
        /// Can be LambdaExpression, BlockExpression, or CatchBlock
        /// </summary>
        internal readonly object Node;
 
        /// <summary>
        /// True if this node corresponds to an IL method.
        /// Can only be true if the Node is a LambdaExpression.
        /// But inlined lambdas will have it set to false.
        /// </summary>
        internal readonly bool IsMethod;
 
        /// <summary>
        /// Does this scope (or any inner scope) close over variables from any
        /// parent scope?
        /// Populated by VariableBinder
        /// </summary>
        internal bool NeedsClosure;
 
        /// <summary>
        /// Variables defined in this scope, and whether they're hoisted or not
        /// Populated by VariableBinder
        /// </summary>
        internal readonly Dictionary<ParameterExpression, VariableStorageKind> Definitions = new Dictionary<ParameterExpression, VariableStorageKind>();
 
        /// <summary>
        /// Each variable referenced within this scope, and how often it was referenced
        /// Populated by VariableBinder
        /// </summary>
        internal Dictionary<ParameterExpression, int>? ReferenceCount;
 
        /// <summary>
        /// Scopes whose variables were merged into this one
        ///
        /// Created lazily as we create hundreds of compiler scopes w/o merging scopes when compiling rules.
        /// </summary>
        internal HashSet<BlockExpression>? MergedScopes;
 
        /// <summary>
        /// The scope's hoisted locals, if any.
        /// Provides storage for variables that are referenced from nested lambdas
        /// </summary>
        private HoistedLocals? _hoistedLocals;
 
        /// <summary>
        /// The closed over hoisted locals
        /// </summary>
        private HoistedLocals? _closureHoistedLocals;
 
        /// <summary>
        /// Mutable dictionary that maps non-hoisted variables to either local
        /// slots or argument slots
        /// </summary>
        private readonly Dictionary<ParameterExpression, Storage> _locals = new Dictionary<ParameterExpression, Storage>();
 
        internal CompilerScope(object node, bool isMethod)
        {
            Node = node;
            IsMethod = isMethod;
            IReadOnlyList<ParameterExpression> variables = GetVariables(node);
 
            Definitions = new Dictionary<ParameterExpression, VariableStorageKind>(variables.Count);
            foreach (ParameterExpression v in variables)
            {
                Definitions.Add(v, VariableStorageKind.Local);
            }
        }
 
        /// <summary>
        /// This scope's hoisted locals, or the closed over locals, if any
        /// Equivalent to: _hoistedLocals ?? _closureHoistedLocals
        /// </summary>
        internal HoistedLocals? NearestHoistedLocals
        {
            get { return _hoistedLocals ?? _closureHoistedLocals; }
        }
 
        /// <summary>
        /// Called when entering a lambda/block. Performs all variable allocation
        /// needed, including creating hoisted locals and IL locals for accessing
        /// parent locals
        /// </summary>
        internal CompilerScope Enter(LambdaCompiler lc, CompilerScope? parent)
        {
            SetParent(lc, parent);
 
            AllocateLocals(lc);
 
            if (IsMethod && _closureHoistedLocals != null)
            {
                EmitClosureAccess(lc, _closureHoistedLocals);
            }
 
            EmitNewHoistedLocals(lc);
 
            if (IsMethod)
            {
                EmitCachedVariables();
            }
 
            return this;
        }
 
        /// <summary>
        /// Frees unnamed locals, clears state associated with this compiler
        /// </summary>
        internal CompilerScope? Exit()
        {
            // free scope's variables
            if (!IsMethod)
            {
                foreach (Storage storage in _locals.Values)
                {
                    storage.FreeLocal();
                }
            }
 
            // Clear state that is associated with this parent
            // (because the scope can be reused in another context)
            CompilerScope? parent = _parent;
            _parent = null;
            _hoistedLocals = null;
            _closureHoistedLocals = null;
            _locals.Clear();
 
            return parent;
        }
 
        #region RuntimeVariablesExpression support
 
        internal void EmitVariableAccess(LambdaCompiler lc, ReadOnlyCollection<ParameterExpression> vars)
        {
            if (NearestHoistedLocals != null && vars.Count > 0)
            {
                // Find what array each variable is on & its index
                var indexes = new ArrayBuilder<long>(vars.Count);
 
                foreach (ParameterExpression variable in vars)
                {
                    // For each variable, find what array it's defined on
                    ulong parents = 0;
                    HoistedLocals? locals = NearestHoistedLocals;
                    while (!locals.Indexes.ContainsKey(variable))
                    {
                        parents++;
                        locals = locals.Parent;
                        Debug.Assert(locals != null);
                    }
 
                    // combine the number of parents we walked, with the
                    // real index of variable to get the index to emit.
                    ulong index = (parents << 32) | (uint)locals.Indexes[variable];
 
                    indexes.UncheckedAdd((long)index);
                }
 
                EmitGet(NearestHoistedLocals.SelfVariable);
                lc.EmitConstantArray(indexes.ToArray());
                lc.IL.Emit(OpCodes.Call, RuntimeOps_CreateRuntimeVariables_ObjectArray_Int64Array);
            }
            else
            {
                // No visible variables
                lc.IL.Emit(OpCodes.Call, RuntimeOps_CreateRuntimeVariables);
            }
        }
 
        #endregion
 
        #region Variable access
 
        /// <summary>
        /// Adds a new virtual variable corresponding to an IL local
        /// </summary>
        internal void AddLocal(LambdaCompiler gen, ParameterExpression variable)
        {
            _locals.Add(variable, new LocalStorage(gen, variable));
        }
 
        internal void EmitGet(ParameterExpression variable)
        {
            ResolveVariable(variable).EmitLoad();
        }
 
        internal void EmitSet(ParameterExpression variable)
        {
            ResolveVariable(variable).EmitStore();
        }
 
        internal void EmitAddressOf(ParameterExpression variable)
        {
            ResolveVariable(variable).EmitAddress();
        }
 
        private Storage ResolveVariable(ParameterExpression variable)
        {
            return ResolveVariable(variable, NearestHoistedLocals);
        }
 
        /// <summary>
        /// Resolve a local variable in this scope or a closed over scope
        /// Throws if the variable is not defined
        /// </summary>
        private Storage ResolveVariable(ParameterExpression variable, HoistedLocals? hoistedLocals)
        {
            // Search IL locals and arguments, but only in this lambda
            for (CompilerScope? s = this; s != null; s = s._parent)
            {
                if (s._locals.TryGetValue(variable, out Storage? storage))
                {
                    return storage;
                }
 
                // if this is a lambda, we're done
                if (s.IsMethod)
                {
                    break;
                }
            }
 
            // search hoisted locals
            for (HoistedLocals? h = hoistedLocals; h != null; h = h.Parent)
            {
                int index;
                if (h.Indexes.TryGetValue(variable, out index))
                {
                    return new ElementBoxStorage(
                        ResolveVariable(h.SelfVariable, hoistedLocals),
                        index,
                        variable
                    );
                }
            }
 
            //
            // If this is an unbound variable in the lambda, the error will be
            // thrown from VariableBinder. So an error here is generally caused
            // by an internal error, e.g. a scope was created but it bypassed
            // VariableBinder.
            //
            throw Error.UndefinedVariable(variable.Name, variable.Type, CurrentLambdaName);
        }
 
        #endregion
 
        private void SetParent(LambdaCompiler lc, CompilerScope? parent)
        {
            Debug.Assert(_parent == null && parent != this);
            _parent = parent;
 
            if (NeedsClosure && _parent != null)
            {
                _closureHoistedLocals = _parent.NearestHoistedLocals;
            }
 
            ReadOnlyCollection<ParameterExpression> hoistedVars = GetVariables().Where(p => Definitions[p] == VariableStorageKind.Hoisted).ToReadOnly();
 
            if (hoistedVars.Count > 0)
            {
                _hoistedLocals = new HoistedLocals(_closureHoistedLocals, hoistedVars);
                AddLocal(lc, _hoistedLocals.SelfVariable);
            }
        }
 
        // Emits creation of the hoisted local storage
        private void EmitNewHoistedLocals(LambdaCompiler lc)
        {
            if (_hoistedLocals == null)
            {
                return;
            }
 
            // create the array
            lc.IL.EmitPrimitive(_hoistedLocals.Variables.Count);
            lc.IL.Emit(OpCodes.Newarr, typeof(object));
 
            // initialize all elements
            int i = 0;
            foreach (ParameterExpression v in _hoistedLocals.Variables)
            {
                // array[i] = new StrongBox<T>(...);
                lc.IL.Emit(OpCodes.Dup);
                lc.IL.EmitPrimitive(i++);
                Type boxType = typeof(StrongBox<>).MakeGenericType(v.Type);
 
                int index;
                if (IsMethod && (index = lc.Parameters.IndexOf(v)) >= 0)
                {
                    // array[i] = new StrongBox<T>(argument);
                    lc.EmitLambdaArgument(index);
                    lc.IL.Emit(OpCodes.Newobj, boxType.GetConstructor(new Type[] { v.Type })!);
                }
                else if (v == _hoistedLocals.ParentVariable)
                {
                    // array[i] = new StrongBox<T>(closure.Locals);
                    ResolveVariable(v, _closureHoistedLocals).EmitLoad();
                    lc.IL.Emit(OpCodes.Newobj, boxType.GetConstructor(new Type[] { v.Type })!);
                }
                else
                {
                    // array[i] = new StrongBox<T>();
                    lc.IL.Emit(OpCodes.Newobj, boxType.GetConstructor(Type.EmptyTypes)!);
                }
                // if we want to cache this into a local, do it now
                if (ShouldCache(v))
                {
                    lc.IL.Emit(OpCodes.Dup);
                    CacheBoxToLocal(lc, v);
                }
                lc.IL.Emit(OpCodes.Stelem_Ref);
            }
 
            // store it
            EmitSet(_hoistedLocals.SelfVariable);
        }
 
        // If hoisted variables are referenced "enough", we cache the
        // StrongBox<T> in an IL local, which saves an array index and a cast
        // when we go to look it up later
        private void EmitCachedVariables()
        {
            if (ReferenceCount == null)
            {
                return;
            }
 
            foreach (KeyValuePair<ParameterExpression, int> refCount in ReferenceCount)
            {
                if (ShouldCache(refCount.Key, refCount.Value))
                {
                    if (ResolveVariable(refCount.Key) is ElementBoxStorage storage)
                    {
                        storage.EmitLoadBox();
                        CacheBoxToLocal(storage.Compiler, refCount.Key);
                    }
                }
            }
        }
 
        private bool ShouldCache(ParameterExpression v, int refCount)
        {
            // This caching is too aggressive in the face of conditionals and
            // switch. Also, it is too conservative for variables used inside
            // of loops.
            return refCount > 2 && !_locals.ContainsKey(v);
        }
 
        private bool ShouldCache(ParameterExpression v)
        {
            if (ReferenceCount == null)
            {
                return false;
            }
 
            int refCount;
            return ReferenceCount.TryGetValue(v, out refCount) && ShouldCache(v, refCount);
        }
 
        [RequiresDynamicCode(Expression.StrongBoxRequiresDynamicCode)]
        private void CacheBoxToLocal(LambdaCompiler lc, ParameterExpression v)
        {
            Debug.Assert(ShouldCache(v) && !_locals.ContainsKey(v));
            var local = new LocalBoxStorage(lc, v);
            local.EmitStoreBox();
            _locals.Add(v, local);
        }
 
        // Creates IL locals for accessing closures
        private void EmitClosureAccess(LambdaCompiler lc, HoistedLocals? locals)
        {
            if (locals == null)
            {
                return;
            }
 
            EmitClosureToVariable(lc, locals);
 
            while ((locals = locals.Parent) != null)
            {
                ParameterExpression v = locals.SelfVariable;
                var local = new LocalStorage(lc, v);
                local.EmitStore(ResolveVariable(v));
                _locals.Add(v, local);
            }
        }
 
        private void EmitClosureToVariable(LambdaCompiler lc, HoistedLocals locals)
        {
            lc.EmitClosureArgument();
            lc.IL.Emit(OpCodes.Ldfld, Closure_Locals);
            AddLocal(lc, locals.SelfVariable);
            EmitSet(locals.SelfVariable);
        }
 
        // Allocates slots for IL locals or IL arguments
        private void AllocateLocals(LambdaCompiler lc)
        {
            foreach (ParameterExpression v in GetVariables())
            {
                if (Definitions[v] == VariableStorageKind.Local)
                {
                    //
                    // If v is in lc.Parameters, it is a parameter.
                    // Otherwise, it is a local variable.
                    //
                    // Also, for inlined lambdas we'll create a local, which
                    // is possibly a byref local if the parameter is byref.
                    //
                    Storage s;
                    if (IsMethod && lc.Parameters.Contains(v))
                    {
                        s = new ArgumentStorage(lc, v);
                    }
                    else
                    {
                        s = new LocalStorage(lc, v);
                    }
                    _locals.Add(v, s);
                }
            }
        }
 
        private IEnumerable<ParameterExpression> GetVariables() =>
            MergedScopes == null ? GetVariables(Node) : GetVariablesIncludingMerged();
 
        private IEnumerable<ParameterExpression> GetVariablesIncludingMerged()
        {
            foreach (ParameterExpression param in GetVariables(Node))
            {
                yield return param;
            }
 
            foreach (BlockExpression scope in MergedScopes!)
            {
                foreach (ParameterExpression param in scope.Variables)
                {
                    yield return param;
                }
            }
        }
 
        private static IReadOnlyList<ParameterExpression> GetVariables(object scope)
        {
            if (scope is LambdaExpression lambda)
            {
                return new ParameterList(lambda);
            }
            if (scope is BlockExpression block)
            {
                return block.Variables;
            }
            return new[] { ((CatchBlock)scope).Variable! };
        }
 
        private string? CurrentLambdaName
        {
            get
            {
                CompilerScope? s = this;
                while (s != null)
                {
                    if (s.Node is LambdaExpression lambda)
                    {
                        return lambda.Name;
                    }
                    s = s._parent;
                }
                throw ContractUtils.Unreachable;
            }
        }
    }
 
    internal static class ParameterProviderExtensions
    {
        public static int IndexOf(this IParameterProvider provider, ParameterExpression? parameter)
        {
            for (int i = 0, n = provider.ParameterCount; i < n; i++)
            {
                if (provider.GetParameter(i) == parameter)
                {
                    return i;
                }
            }
 
            return -1;
        }
 
        public static bool Contains(this IParameterProvider provider, ParameterExpression? parameter)
        {
            return provider.IndexOf(parameter) >= 0;
        }
    }
 
    internal sealed class ParameterList : IReadOnlyList<ParameterExpression>
    {
        private readonly IParameterProvider _provider;
 
        public ParameterList(IParameterProvider provider)
        {
            _provider = provider;
        }
 
        public ParameterExpression this[int index]
        {
            get
            {
                return _provider.GetParameter(index);
            }
        }
 
        public int Count => _provider.ParameterCount;
 
        public IEnumerator<ParameterExpression> GetEnumerator()
        {
            for (int i = 0, n = _provider.ParameterCount; i < n; i++)
            {
                yield return _provider.GetParameter(i);
            }
        }
 
        IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
    }
}