File: FlowAnalysis\NullableWalker.Variables.cs
Web Access
Project: src\src\Compilers\CSharp\Portable\Microsoft.CodeAnalysis.CSharp.csproj (Microsoft.CodeAnalysis.CSharp)
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
 
using System;
using System.Collections.Generic;
using System.Collections.Immutable;
using System.Diagnostics;
using Microsoft.CodeAnalysis.CSharp.Symbols;
using Microsoft.CodeAnalysis.PooledObjects;
 
namespace Microsoft.CodeAnalysis.CSharp
{
    internal partial class NullableWalker
    {
        /// <summary>
        /// An immutable copy of <see cref="Variables"/>.
        /// </summary>
        [DebuggerDisplay("{GetDebuggerDisplay(), nq}")]
        internal sealed class VariablesSnapshot
        {
            /// <summary>
            /// Unique identifier in the chain of nested VariablesSnapshot instances. The value starts at 0
            /// for the outermost method and increases at each nested function.
            /// </summary>
            internal readonly int Id;
 
            /// <summary>
            /// VariablesSnapshot instance for containing method, or null if this is the outermost method.
            /// </summary>
            internal readonly VariablesSnapshot? Container;
 
            /// <summary>
            /// Symbol that contains this set of variables. This is typically a method but may be a field
            /// when analyzing a field initializer. The symbol may be null at the outermost scope when
            /// analyzing an attribute argument value or a parameter default value.
            /// </summary>
            internal readonly Symbol? Symbol;
 
            /// <summary>
            /// Mapping from variable to slot.
            /// </summary>
            internal readonly ImmutableArray<KeyValuePair<VariableIdentifier, int>> VariableSlot;
 
            /// <summary>
            /// Mapping from local or parameter to inferred type.
            /// </summary>
            internal readonly ImmutableDictionary<Symbol, TypeWithAnnotations> VariableTypes;
 
            internal VariablesSnapshot(int id, VariablesSnapshot? container, Symbol? symbol, ImmutableArray<KeyValuePair<VariableIdentifier, int>> variableSlot, ImmutableDictionary<Symbol, TypeWithAnnotations> variableTypes)
            {
                Id = id;
                Container = container;
                Symbol = symbol;
                VariableSlot = variableSlot;
                VariableTypes = variableTypes;
            }
 
            internal bool TryGetType(Symbol symbol, out TypeWithAnnotations type)
            {
                return VariableTypes.TryGetValue(symbol, out type);
            }
 
            private string GetDebuggerDisplay()
            {
                var symbol = (object?)Symbol ?? "<null>";
                return $"Id={Id}, Symbol={symbol}, Count={VariableSlot.Length}";
            }
        }
 
        /// <summary>
        /// A collection of variables associated with a method scope. For a particular method, the variables
        /// may contain parameters and locals and any fields from other variables in the collection. If the method
        /// is a nested function (a lambda or a local function), there is a reference to the variables collection at
        /// the containing method scope. The outermost scope may also contain variables for static fields.
        /// Each variable (parameter, local, or field of other variable) must be associated with the variables collection
        /// for that method where the parameter or local are declared, even if the variable is used in a nested scope.
        /// </summary>
        [DebuggerDisplay("{GetDebuggerDisplay(), nq}")]
        internal sealed class Variables
        {
            // Members of variables are tracked up to a fixed depth, to avoid cycles. The
            // MaxSlotDepth value is arbitrary but large enough to allow most scenarios.
            private const int MaxSlotDepth = 5;
 
            // An int slot is a combination of a 15-bit id (in the high-order 16 bits) and a 16-bit index.
            // Id value starts at 0 for the outermost method and increases at each nested function.
            // There is no relationship between ids of sibling nested functions - the ids of sibling
            // functions may be the same or different.
            private const int IdOffset = 16;
            private const int IdMask = (1 << 15) - 1;
            private const int IndexMask = (1 << 16) - 1;
 
#if DEBUG
            /// <summary>
            /// Used to offset child ids to help catch cases where Variables
            /// and LocalState instances are mismatched.
            /// </summary>
            private readonly Random _nextIdOffset;
#endif
 
            /// <summary>
            /// Unique identifier in the chain of nested Variables instances. The value starts at 0
            /// for the outermost method and increases at each nested function.
            /// </summary>
            internal readonly int Id;
 
            /// <summary>
            /// Variables instance for containing method, or null if this is the outermost method.
            /// </summary>
            internal readonly Variables? Container;
 
            /// <summary>
            /// Symbol that contains this set of variables. This is typically a method but may be a field
            /// when analyzing a field initializer. The symbol may be null at the outermost scope when
            /// analyzing an attribute argument value or a parameter default value.
            /// </summary>
            internal readonly Symbol? Symbol;
 
            /// <summary>
            /// A mapping from local variables to the index of their slot in a flow analysis local state.
            /// </summary>
            private readonly PooledDictionary<VariableIdentifier, int> _variableSlot = PooledDictionary<VariableIdentifier, int>.GetInstance();
 
            /// <summary>
            /// The inferred type at the point of declaration of var locals and parameters.
            /// </summary>
            private readonly PooledDictionary<Symbol, TypeWithAnnotations> _variableTypes = SpecializedSymbolCollections.GetPooledSymbolDictionaryInstance<Symbol, TypeWithAnnotations>();
 
            /// <summary>
            /// A mapping from the local variable slot to the symbol for the local variable itself.
            ///
            /// The first slot, slot 0, is reserved for indicating reachability, so the first tracked variable will
            /// be given slot 1. When referring to VariableIdentifier.ContainingSlot, slot 0 indicates
            /// that the variable in VariableIdentifier.Symbol is a root, i.e. not nested within another
            /// tracked variable. Slots less than 0 are illegal.
            /// </summary>
            private readonly ArrayBuilder<VariableIdentifier> _variableBySlot = ArrayBuilder<VariableIdentifier>.GetInstance(1, default);
 
            internal static Variables Create(Symbol? symbol)
            {
                return new Variables(id: 0, container: null, symbol);
            }
 
            internal static Variables Create(VariablesSnapshot snapshot)
            {
                var container = snapshot.Container is null ? null : Create(snapshot.Container);
                var variables = new Variables(snapshot.Id, container, snapshot.Symbol);
                variables.Populate(snapshot);
                return variables;
            }
 
            private int GetNextId()
            {
                return Id +
#if DEBUG
                    _nextIdOffset.Next(maxValue: 7) +
#endif
                    1;
            }
 
            private void Populate(VariablesSnapshot snapshot)
            {
                Debug.Assert(_variableSlot.Count == 0);
                Debug.Assert(_variableTypes.Count == 0);
                Debug.Assert(_variableBySlot.Count == 1);
 
                _variableBySlot.AddMany(default, snapshot.VariableSlot.Length);
                foreach (var pair in snapshot.VariableSlot)
                {
                    var identifier = pair.Key;
                    var index = pair.Value;
                    _variableSlot.Add(identifier, index);
                    _variableBySlot[index] = identifier;
                }
 
                foreach (var pair in snapshot.VariableTypes)
                {
                    _variableTypes.Add(pair.Key, pair.Value);
                }
            }
 
            private Variables(int id, Variables? container, Symbol? symbol)
            {
                Debug.Assert(id >= 0);
                Debug.Assert(id <= IdMask);
                Debug.Assert(container is null || container.Id < id);
#if DEBUG
                _nextIdOffset = container?._nextIdOffset ?? new Random();
#endif
                Id = id;
                Container = container;
                Symbol = symbol;
            }
 
            internal void Free()
            {
                Container?.Free();
                _variableBySlot.Free();
                _variableTypes.Free();
                _variableSlot.Free();
            }
 
            internal VariablesSnapshot CreateSnapshot()
            {
                return new VariablesSnapshot(
                    Id,
                    Container?.CreateSnapshot(),
                    Symbol,
                    ImmutableArray.CreateRange(_variableSlot),
                    ImmutableDictionary.CreateRange(_variableTypes));
            }
 
            internal Variables CreateNestedMethodScope(MethodSymbol method)
            {
                Debug.Assert(GetVariablesForMethodScope(method) is null);
                Debug.Assert(!(method.ContainingSymbol is MethodSymbol containingMethod) ||
                    ((object?)GetVariablesForMethodScope(containingMethod) == this) ||
                    Container is null);
 
                return new Variables(id: GetNextId(), this, method);
            }
 
            internal int RootSlot(int slot)
            {
                while (true)
                {
                    int containingSlot = this[slot].ContainingSlot;
                    if (containingSlot == 0)
                    {
                        return slot;
                    }
                    else
                    {
                        slot = containingSlot;
                    }
                }
            }
 
            internal bool TryGetValue(VariableIdentifier identifier, out int slot)
            {
                var variables = GetVariablesForVariable(identifier);
                return variables.TryGetValueInternal(identifier, out slot);
            }
 
            private bool TryGetValueInternal(VariableIdentifier identifier, out int slot)
            {
                if (_variableSlot.TryGetValue(identifier, out int index))
                {
                    slot = ConstructSlot(Id, index);
                    return true;
                }
                slot = -1;
                return false;
            }
 
            internal int Add(VariableIdentifier identifier)
            {
                var variables = GetVariablesForVariable(identifier);
                int slot = variables.AddInternal(identifier);
                // ContainingSlot must be from the same Variables collection.
                Debug.Assert(slot <= 0 ||
                    identifier.ContainingSlot <= 0 ||
                    DeconstructSlot(slot).Id == DeconstructSlot(identifier.ContainingSlot).Id);
                return slot;
            }
 
            private int AddInternal(VariableIdentifier identifier)
            {
                if (getSlotDepth(identifier.ContainingSlot) >= MaxSlotDepth)
                {
                    return -1;
                }
                int index = NextAvailableIndex;
                if (index > IndexMask)
                {
                    return -1;
                }
                _variableSlot.Add(identifier, index);
                _variableBySlot.Add(identifier);
                return ConstructSlot(Id, index);
 
                int getSlotDepth(int slot)
                {
                    int depth = 0;
                    while (slot > 0)
                    {
                        depth++;
                        var (id, index) = DeconstructSlot(slot);
                        Debug.Assert(id == Id);
                        slot = _variableBySlot[index].ContainingSlot;
                    }
                    return depth;
                }
            }
 
            internal bool TryGetType(Symbol symbol, out TypeWithAnnotations type)
            {
                var variables = GetVariablesContainingSymbol(symbol);
                return variables._variableTypes.TryGetValue(symbol, out type);
            }
 
            internal void SetType(Symbol symbol, TypeWithAnnotations type)
            {
                var variables = GetVariablesContainingSymbol(symbol);
                Debug.Assert((object)variables == this);
                variables._variableTypes[symbol] = type;
            }
 
            internal VariableIdentifier this[int slot]
            {
                get
                {
                    (int id, int index) = DeconstructSlot(slot);
                    var variables = GetVariablesForId(id);
                    return variables!._variableBySlot[index];
                }
            }
 
            internal int NextAvailableIndex => _variableBySlot.Count;
 
            internal int GetTotalVariableCount()
            {
                int fromContainer = Container?.GetTotalVariableCount() ?? 0;
                return fromContainer + _variableSlot.Count;
            }
 
            internal void GetMembers(ArrayBuilder<(VariableIdentifier, int)> builder, int containingSlot)
            {
                (int id, int index) = DeconstructSlot(containingSlot);
                var variables = GetVariablesForId(id)!;
                var variableBySlot = variables._variableBySlot;
                for (index++; index < variableBySlot.Count; index++)
                {
                    var variable = variableBySlot[index];
                    if (variable.ContainingSlot == containingSlot)
                    {
                        builder.Add((variable, ConstructSlot(id, index)));
                    }
                }
            }
 
            private Variables GetVariablesForVariable(VariableIdentifier identifier)
            {
                int containingSlot = identifier.ContainingSlot;
                if (containingSlot > 0)
                {
                    return GetVariablesForId(DeconstructSlot(containingSlot).Id)!;
                }
                return GetVariablesContainingSymbol(identifier.Symbol);
            }
 
            private Variables GetVariablesContainingSymbol(Symbol symbol)
            {
                switch (symbol)
                {
                    case LocalSymbol:
                    case ParameterSymbol:
                        if (symbol.ContainingSymbol is MethodSymbol method &&
                            GetVariablesForMethodScope(method) is { } variables)
                        {
                            return variables;
                        }
                        break;
                }
                // Fallback to the outermost scope for the remaining cases. Those cases include: static fields;
                // variables declared in field initializers; locals and parameters when the root symbol is null;
                // and error cases such as an instance field referenced in a static method (no containing slot).
                return GetRootScope();
            }
 
            internal Variables GetRootScope()
            {
                var variables = this;
                while (variables.Container is { } container)
                {
                    variables = container;
                }
                return variables;
            }
 
            private Variables? GetVariablesForId(int id)
            {
                var variables = this;
                do
                {
                    if (variables.Id == id)
                    {
                        return variables;
                    }
                    variables = variables.Container;
                }
                while (variables is { });
                return null;
            }
 
            internal Variables? GetVariablesForMethodScope(MethodSymbol method)
            {
                var variables = this;
                while (true)
                {
                    if ((object)method == variables.Symbol)
                    {
                        return variables;
                    }
                    variables = variables.Container;
                    if (variables is null)
                    {
                        return null;
                    }
                }
            }
 
            internal static int ConstructSlot(int id, int index)
            {
                Debug.Assert(id >= 0);
                Debug.Assert(id <= IdMask);
                Debug.Assert(index >= 0);
                Debug.Assert(index <= IndexMask);
 
                return index < 0 ? index : (id << IdOffset) | index;
            }
 
            internal static (int Id, int Index) DeconstructSlot(int slot)
            {
                Debug.Assert(slot > -1);
                return slot < 0 ? (0, slot) : (slot >> IdOffset & IdMask, slot & IndexMask);
            }
 
            private string GetDebuggerDisplay()
            {
                var symbol = (object?)Symbol ?? "<null>";
                return $"Id={Id}, Symbol={symbol}, Count={_variableSlot.Count}";
            }
        }
    }
}