File: SourceGeneration\Nodes\NodeStateTable.cs
Web Access
Project: src\src\Compilers\Core\Portable\Microsoft.CodeAnalysis.csproj (Microsoft.CodeAnalysis)
// 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 System.Diagnostics.CodeAnalysis;
using System.Linq;
using Microsoft.CodeAnalysis.PooledObjects;
using Roslyn.Utilities;
 
namespace Microsoft.CodeAnalysis
{
    // A node table is the fundamental structure we use to track changes through the incremental 
    // generator api. It can be thought of as a series of slots that take their input from an
    // upstream table and produce 0-or-more outputs. When viewed from a downstream table the outputs
    // are presented as a single unified list, with each output forming the new input to the downstream
    // table.
    // 
    // Each slot has an associated state which is used to inform the operation that should be performed
    // to create or update the outputs. States generally flow through from upstream to downstream tables.
    // For instance an Added state implies that the upstream table produced a value that was not seen 
    // in the previous iteration, and the table should run whatever transform it tracks on the input 
    // to produce the outputs. These new outputs will also have a state of Added. A cached input specifies
    // that the input has not changed, and thus the outputs will be the same as the previous run. Added,
    // and Modified inputs will always run a transform to produce new outputs. Cached and Removed
    // entries will always use the previous entries and perform no work.
    // 
    // It is important to track Removed entries while updating the downstream tables, as an upstream 
    // remove can result in multiple downstream entries being removed. However, once all tables are up 
    // to date, the removed entries are no longer needed, and the remaining entries can be considered to
    // be cached. This process is called 'compaction' and results in the actual tables which are stored
    // between runs, as opposed to the 'live' tables that exist during an update.
    //
    // Modified entries are similar to added inputs, but with a subtle difference. When an input is Added
    // all outputs are unconditionally added too. However when an input is modified, the outputs may still
    // be the same (for instance something changed elsewhere in a file that had no bearing on the produced
    // output). In this case, the state table checks the results against the previously produced values,
    // and any that are found to be the same instead get a cached state, meaning no new downstream work 
    // will be produced for them. Thus a modified input is the only slot that can have differing output 
    // states.
 
    internal enum EntryState { Added, Removed, Modified, Cached };
 
    internal interface IStateTable
    {
        IStateTable AsCached();
 
        bool HasTrackedSteps { get; }
        ImmutableArray<IncrementalGeneratorRunStep> Steps { get; }
    }
 
    internal readonly record struct NodeStateEntry<T>(T Item, EntryState State, int OutputIndex, IncrementalGeneratorRunStep? Step);
 
    /// <summary>
    /// A data structure that tracks the inputs and output of an execution node
    /// </summary>
    /// <typeparam name="T">The type of the items tracked by this table</typeparam>
    internal sealed class NodeStateTable<T> : IStateTable
    {
        internal static NodeStateTable<T> Empty { get; } = new NodeStateTable<T>(ImmutableArray<TableEntry>.Empty, ImmutableArray<IncrementalGeneratorRunStep>.Empty, hasTrackedSteps: true, isCached: false);
 
        private readonly ImmutableArray<TableEntry> _states;
 
        private NodeStateTable(ImmutableArray<TableEntry> states, ImmutableArray<IncrementalGeneratorRunStep> steps, bool hasTrackedSteps, bool isCached)
        {
            Debug.Assert(!hasTrackedSteps || steps.Length == states.Length);
 
            _states = states;
            Steps = steps;
            IsCached = isCached;
            HasTrackedSteps = hasTrackedSteps;
        }
 
        public int Count => _states.Length;
 
        /// <summary>
        /// Indicates that this table is unchanged from the previous version.
        /// </summary>
        public bool IsCached { get; }
 
        public bool IsEmpty => _states.IsEmpty;
 
        public bool HasTrackedSteps { get; }
 
        public ImmutableArray<IncrementalGeneratorRunStep> Steps { get; }
 
        public int GetTotalEntryItemCount()
            => _states.Sum(static e => e.Count);
 
        public struct Enumerator
        {
            private readonly NodeStateTable<T> _stateTable;
            private int _nextStatesIndex;
            private int _nextInputEntryIndex;
            private IncrementalGeneratorRunStep? _step;
            private TableEntry _inputEntry;
            private NodeStateEntry<T> _current;
 
            public Enumerator(NodeStateTable<T> stateTable)
            {
                _stateTable = stateTable;
                _nextStatesIndex = 0;
 
                UpdateAfterNextStatesIndexModification();
            }
 
            public NodeStateEntry<T> Current => _current;
 
            public bool MoveNext()
            {
                while (_nextStatesIndex < _stateTable._states.Length)
                {
                    if (_nextInputEntryIndex < _inputEntry.Count)
                    {
                        _current = new NodeStateEntry<T>(_inputEntry.GetItem(_nextInputEntryIndex), _inputEntry.GetState(_nextInputEntryIndex), _nextInputEntryIndex, _step);
                        _nextInputEntryIndex += 1;
 
                        return true;
                    }
 
                    _nextStatesIndex += 1;
 
                    UpdateAfterNextStatesIndexModification();
                }
 
                return false;
            }
 
            private void UpdateAfterNextStatesIndexModification()
            {
                _nextInputEntryIndex = 0;
 
                if (_nextStatesIndex < _stateTable._states.Length)
                {
                    _step = _stateTable.HasTrackedSteps ? _stateTable.Steps[_nextStatesIndex] : null;
                    _inputEntry = _stateTable._states[_nextStatesIndex];
                }
            }
        }
 
        public Enumerator GetEnumerator()
        {
            return new Enumerator(this);
        }
 
        public NodeStateTable<T> AsCached()
        {
            if (IsCached)
                return this;
 
            // If the input to an entry was removed, we also need to remove the entry.
            // However, if the input was present, but the entry didn't produce any values (or removed them all),
            // we need to keep the empty entry as a placeholder, so that on the next generation pass
            // we can retrieve it as the cached value of the input.
            var nonRemovedCount = _states.Count(static e => !e.IsRemovedDueToInputRemoval);
 
            var compacted = ArrayBuilder<TableEntry>.GetInstance(nonRemovedCount);
            foreach (var entry in _states)
            {
                if (!entry.IsRemovedDueToInputRemoval)
                    compacted.Add(entry.AsCached());
            }
 
            // When we're preparing a table for caching between runs, we drop the step information as we cannot guarantee the graph structure while also updating
            // the input states
 
            // Ensure we are completely full so that ToImmutable translates to a MoveToImmutable
            Debug.Assert(compacted.Count == nonRemovedCount);
            return new NodeStateTable<T>(compacted.ToImmutableAndFree(), ImmutableArray<IncrementalGeneratorRunStep>.Empty, hasTrackedSteps: false, isCached: true);
        }
 
        IStateTable IStateTable.AsCached() => AsCached();
 
        public (T item, IncrementalGeneratorRunStep? step) Single()
        {
            Debug.Assert((_states.Length == 1 || _states.Length == 2 && _states[0].IsRemovedDueToInputRemoval) && _states[^1].Count == 1);
            return (_states[^1].GetItem(0), HasTrackedSteps ? Steps[^1] : null);
        }
 
        public Builder ToBuilder(string? stepName, bool stepTrackingEnabled, IEqualityComparer<T>? equalityComparer = null, int? tableCapacity = null)
            => new(this, stepName, stepTrackingEnabled, equalityComparer, tableCapacity);
 
        public NodeStateTable<T> CreateCachedTableWithUpdatedSteps<TInput>(NodeStateTable<TInput> inputTable, string? stepName, IEqualityComparer<T> equalityComparer)
        {
            Debug.Assert(inputTable.HasTrackedSteps && inputTable.IsCached);
            NodeStateTable<T>.Builder builder = ToBuilder(stepName, stepTrackingEnabled: true, equalityComparer);
            foreach (var entry in inputTable)
            {
                var inputs = ImmutableArray.Create((entry.Step!, entry.OutputIndex));
                bool usedCachedEntry = builder.TryUseCachedEntries(TimeSpan.Zero, inputs);
                Debug.Assert(usedCachedEntry);
            }
 
            return builder.ToImmutableAndFree();
        }
 
        public string GetPackedStates()
        {
            var pooled = PooledStringBuilder.GetInstance();
            foreach (var state in _states)
            {
                for (int i = 0; i < state.Count; i++)
                {
                    var packedChar = state.GetState(i) switch
                    {
                        EntryState.Added => 'A',
                        EntryState.Removed => 'R',
                        EntryState.Modified => 'M',
                        EntryState.Cached => 'C',
                        _ => throw ExceptionUtilities.Unreachable(),
                    };
 
                    pooled.Builder.Append(packedChar);
                }
                pooled.Builder.Append(',');
            }
            return pooled.ToStringAndFree();
        }
 
        /// <remarks>
        /// The builder is <b>not</b> threadsafe.
        /// </remarks>
        public sealed class Builder
        {
            private readonly ArrayBuilder<TableEntry> _states;
            private readonly NodeStateTable<T> _previous;
 
            private readonly string? _name;
            private readonly IEqualityComparer<T> _equalityComparer;
            private readonly ArrayBuilder<IncrementalGeneratorRunStep>? _steps;
 
            private int _insertedCount = 0;
 
            [MemberNotNullWhen(true, nameof(_steps))]
            public bool TrackIncrementalSteps => _steps is not null;
 
#if DEBUG
            private readonly int? _requestedTableCapacity;
#endif
 
            internal Builder(
                NodeStateTable<T> previous,
                string? name,
                bool stepTrackingEnabled,
                IEqualityComparer<T>? equalityComparer,
                int? tableCapacity)
            {
#if DEBUG
                _requestedTableCapacity = tableCapacity;
#endif
                // If the caller specified a desired capacity, then use that.  Otherwise, use the previous table's total
                // entry count as a reasonable approximation for what we will need.
                _states = ArrayBuilder<TableEntry>.GetInstance(tableCapacity ?? previous.GetTotalEntryItemCount());
                _previous = previous;
                _name = name;
                _equalityComparer = equalityComparer ?? EqualityComparer<T>.Default;
                if (stepTrackingEnabled)
                {
                    _steps = ArrayBuilder<IncrementalGeneratorRunStep>.GetInstance();
                }
            }
 
            public int Count => _states.Count;
 
            public bool TryRemoveEntries(TimeSpan elapsedTime, ImmutableArray<(IncrementalGeneratorRunStep InputStep, int OutputIndex)> stepInputs)
            {
                if (!TryGetPreviousEntry(out var previousEntry))
                {
                    // The previous table had less node executions than this one, so we don't have any entries from a previous corresponding node execution to remove.
                    return false;
                }
 
                // Mark the corresponding entries to this node execution in the previous table as removed.
                // Since they are removed due to their input having been removed, we won't have to keep placeholders for them.
                var previousEntries = previousEntry.AsRemovedDueToInputRemoval();
                _states.Add(previousEntries);
                RecordStepInfoForLastEntry(elapsedTime, stepInputs, EntryState.Removed);
                return true;
            }
 
            public bool TryRemoveEntries(TimeSpan elapsedTime, ImmutableArray<(IncrementalGeneratorRunStep InputStep, int OutputIndex)> stepInputs, out OneOrMany<T> entries)
            {
                if (!TryRemoveEntries(elapsedTime, stepInputs))
                {
                    entries = default;
                    return false;
                }
 
                entries = _states[^1].Items;
                return true;
            }
 
            public bool TryUseCachedEntries(TimeSpan elapsedTime, ImmutableArray<(IncrementalGeneratorRunStep InputStep, int OutputIndex)> stepInputs)
            {
                if (!TryGetPreviousEntry(out var previousEntries))
                {
                    // The previous table had less node executions than this one, so we don't have any entries from a previous corresponding node execution to copy as cached.
                    return false;
                }
 
                Debug.Assert(previousEntries.IsCached);
 
                _states.Add(previousEntries);
                RecordStepInfoForLastEntry(elapsedTime, stepInputs, EntryState.Cached);
                return true;
            }
 
            internal bool TryUseCachedEntries(TimeSpan elapsedTime, ImmutableArray<(IncrementalGeneratorRunStep InputStep, int OutputIndex)> stepInputs, out TableEntry entry)
            {
                if (!TryUseCachedEntries(elapsedTime, stepInputs))
                {
                    entry = default;
                    return false;
                }
 
                entry = _states[^1];
                return true;
            }
 
            public bool TryModifyEntry(T value, IEqualityComparer<T> comparer, TimeSpan elapsedTime, ImmutableArray<(IncrementalGeneratorRunStep InputStep, int OutputIndex)> stepInputs, EntryState overallInputState)
            {
                if (!TryGetPreviousEntry(out var previousEntry))
                {
                    // The previous table had less node executions than this one, so we don't have any entries from a previous corresponding node execution to try to modify.
                    return false;
                }
 
                if (previousEntry.Count == 0)
                {
                    // it's possible that the previous execution removed this item, but we left in an empty entry as a placeholder. In which case, we can't modify it
                    return false;
                }
 
                Debug.Assert(previousEntry.Count == 1);
                var (chosen, state, _) = GetModifiedItemAndState(previousEntry.GetItem(0), value, comparer);
                _states.Add(new TableEntry(OneOrMany.Create(chosen), state));
                RecordStepInfoForLastEntry(elapsedTime, stepInputs, overallInputState);
                return true;
            }
 
            public bool TryModifyEntries(ImmutableArray<T> outputs, IEqualityComparer<T> comparer, TimeSpan elapsedTime, ImmutableArray<(IncrementalGeneratorRunStep InputStep, int OutputIndex)> stepInputs, EntryState overallInputState)
            {
                // Semantics:
                // For each item in the row, we compare with the new matching new value.
                // - Cached when the same
                // - Modified when different
                // - Removed when old item position > outputs.length
                // - Added when new item position < previousTable.length
 
                if (!TryGetPreviousEntry(out var previousEntry))
                {
                    return false;
                }
 
                // when both entries have no items, we can short circuit
                if (previousEntry.Count == 0 && outputs.Length == 0)
                {
                    _states.Add(previousEntry);
                    if (TrackIncrementalSteps)
                    {
                        RecordStepInfoForLastEntry(elapsedTime, stepInputs, EntryState.Cached);
                    }
 
                    return true;
                }
 
                // We may be able to move the previous entry over wholesale.  So avoid creating an builder and doing any
                // expensive work there until necessary (e.g. we detected either a different item or a different state).
                // We can only do this if the counts of before/after are the same. If not, then obviously something
                // changed and we can't reuse the before item.
 
                var totalBuilderItems = Math.Max(previousEntry.Count, outputs.Length);
                var builder = previousEntry.Count == outputs.Length ? null : new TableEntry.Builder(capacity: totalBuilderItems);
 
                var sharedCount = Math.Min(previousEntry.Count, outputs.Length);
 
                // cached or modified items
                for (int i = 0; i < sharedCount; i++)
                {
                    var previousItem = previousEntry.GetItem(i);
                    var previousState = previousEntry.GetState(i);
                    var replacementItem = outputs[i];
 
                    var (chosenItem, state, chosePrevious) = GetModifiedItemAndState(previousItem, replacementItem, comparer);
 
                    if (builder != null)
                    {
                        // if we have a builder, then we're keeping track of all entries no matter what.
                        builder.Add(chosenItem, state);
                        continue;
                    }
 
                    if (!chosePrevious || state != previousState)
                    {
                        // We don't have a builder, but we also can't use the previous entry.  Make a builder, copy
                        // everything prior to this point to it, and then add the latest entry.
                        builder = new TableEntry.Builder(capacity: totalBuilderItems);
                        for (int j = 0; j < i; j++)
                            builder.Add(previousEntry.GetItem(j), previousEntry.GetState(j));
 
                        builder.Add(chosenItem, state);
                        continue;
                    }
 
                    // otherwise, we don't have a builder and we are still able to use the previous entry.  Keep going
                    // without constructing anything.
                }
 
                // removed
                for (int i = sharedCount; i < previousEntry.Count; i++)
                {
                    // We know we must have a builder because we only get into this path when the counts are different
                    // (and thus we created a builder at the start).
                    builder!.Add(previousEntry.GetItem(i), EntryState.Removed);
                }
 
                // added
                for (int i = sharedCount; i < outputs.Length; i++)
                {
                    // We know we must have a builder because we only get into this path when the counts are different
                    // (and thus we created a builder at the start).
                    builder!.Add(outputs[i], EntryState.Added);
                }
 
                // If we still don't have a builder, then we can reuse the previous table entry entirely.  Otherwise,
                // construct the new one from the values collected.
                _states.Add(builder == null ? previousEntry : builder.ToImmutableAndFree());
 
                RecordStepInfoForLastEntry(elapsedTime, stepInputs, overallInputState);
                return true;
            }
 
            public bool TryModifyEntries(ImmutableArray<T> outputs, IEqualityComparer<T> comparer, TimeSpan elapsedTime, ImmutableArray<(IncrementalGeneratorRunStep InputStep, int OutputIndex)> stepInputs, EntryState overallInputState, out TableEntry entry)
            {
                if (!TryModifyEntries(outputs, comparer, elapsedTime, stepInputs, overallInputState))
                {
                    entry = default;
                    return false;
                }
 
                entry = _states[^1];
                return true;
            }
 
            public void AddEntry(T value, EntryState state, TimeSpan elapsedTime, ImmutableArray<(IncrementalGeneratorRunStep InputStep, int OutputIndex)> stepInputs, EntryState overallInputState)
            {
                _states.Add(new TableEntry(OneOrMany.Create(value), state));
                _insertedCount += state == EntryState.Added ? 1 : 0;
                RecordStepInfoForLastEntry(elapsedTime, stepInputs, overallInputState);
            }
 
            public TableEntry AddEntries(ImmutableArray<T> values, EntryState state, TimeSpan elapsedTime, ImmutableArray<(IncrementalGeneratorRunStep InputStep, int OutputIndex)> stepInputs, EntryState overallInputState)
            {
                var tableEntry = new TableEntry(OneOrMany.Create(values), state);
                _states.Add(tableEntry);
                _insertedCount += state == EntryState.Added ? 1 : 0;
                RecordStepInfoForLastEntry(elapsedTime, stepInputs, overallInputState);
                return tableEntry;
            }
 
            private bool TryGetPreviousEntry(out TableEntry previousEntry)
            {
                // When indexing into the previous table we need to subtract the number of entries that have been explicitly added
                // to the current table, as they didn't exist in the previous one.
                var previousTableEntryIndex = _states.Count - _insertedCount;
 
                var canUsePrevious = _previous._states.Length > previousTableEntryIndex;
                previousEntry = canUsePrevious ? _previous._states[previousTableEntryIndex] : default;
                return canUsePrevious;
            }
 
            private void RecordStepInfoForLastEntry(TimeSpan elapsedTime, ImmutableArray<(IncrementalGeneratorRunStep InputStep, int OutputIndex)> stepInputs, EntryState overallInputState)
            {
                Debug.Assert(stepInputs.IsDefault == !TrackIncrementalSteps);
                if (TrackIncrementalSteps)
                {
                    // We should have already recorded step information for all steps before the most recently recorded step.
                    Debug.Assert(_steps.Count + 1 == _states.Count);
 
                    TableEntry outputInfo = _states[^1];
 
                    var stepOutputBuilder = ArrayBuilder<(object, IncrementalStepRunReason)>.GetInstance(outputInfo.Count);
 
                    for (int i = 0; i < outputInfo.Count; i++)
                    {
                        stepOutputBuilder.Add((outputInfo.GetItem(i)!, AsStepState(overallInputState, outputInfo.GetState(i))));
                    }
 
                    _steps.Add(
                        new IncrementalGeneratorRunStep(
                            _name,
                            stepInputs,
                            stepOutputBuilder.ToImmutableAndFree(),
                            elapsedTime));
                }
            }
 
            public IReadOnlyList<IncrementalGeneratorRunStep> Steps => (IReadOnlyList<IncrementalGeneratorRunStep>?)_steps ?? ImmutableArray<IncrementalGeneratorRunStep>.Empty;
 
            private static IncrementalStepRunReason AsStepState(EntryState inputState, EntryState outputState)
            {
                return (inputState, outputState) switch
                {
                    (EntryState.Added, EntryState.Added) => IncrementalStepRunReason.New,
                    (EntryState.Modified, EntryState.Modified) => IncrementalStepRunReason.Modified,
                    (EntryState.Modified, EntryState.Cached) => IncrementalStepRunReason.Unchanged,
                    (EntryState.Cached, EntryState.Cached) => IncrementalStepRunReason.Cached,
                    (EntryState.Removed, EntryState.Removed) => IncrementalStepRunReason.Removed,
                    (EntryState.Modified, EntryState.Removed) => IncrementalStepRunReason.Removed,
                    (EntryState.Modified, EntryState.Added) => IncrementalStepRunReason.New,
                    _ => throw ExceptionUtilities.UnexpectedValue((inputState, outputState))
                };
            }
 
            public NodeStateTable<T> ToImmutableAndFree()
            {
                Debug.Assert(!TrackIncrementalSteps || _states.Count == _steps.Count);
 
                if (_states.Count == 0)
                {
                    _states.Free();
                    return NodeStateTable<T>.Empty;
                }
 
#if DEBUG
                // If the caller requested a specific capacity, then we should have added either that amount, or some
                // amount less than that.  It's possible to have added less as a Where clause will mean some amount of
                // states are filtered out.
                Debug.Assert(_requestedTableCapacity == null || _states.Count <= _requestedTableCapacity);
#endif
 
                // if we added the exact same entries as before, then we can directly embed previous' entry array,
                // avoiding a costly allocation of the same data.
                ImmutableArray<TableEntry> finalStates;
                if (_states.Count == _previous.Count && _states.SequenceEqual(_previous._states, (e1, e2) => e1.Matches(e2, _equalityComparer)))
                {
                    finalStates = _previous._states;
                    _states.Free();
                }
                else
                {
                    // Important to use ToImmutableAndFree so that we will MoveToImmutable when the requested capacity
                    // equals the count.
                    finalStates = _states.ToImmutableAndFree();
                }
 
                return new NodeStateTable<T>(
                    finalStates,
                    TrackIncrementalSteps ? _steps.ToImmutableAndFree() : default,
                    hasTrackedSteps: TrackIncrementalSteps,
                    isCached: finalStates.All(static s => s.IsCached) && _previous.GetTotalEntryItemCount() == finalStates.Sum(static s => s.Count));
            }
 
            private static (T chosen, EntryState state, bool chosePrevious) GetModifiedItemAndState(T previous, T replacement, IEqualityComparer<T> comparer)
            {
                // when comparing an item to check if its modified we explicitly cache the *previous* item in the case where its 
                // considered to be equal. This ensures that subsequent comparisons are stable across future generation passes.
                return comparer.Equals(previous, replacement)
                    ? (previous, EntryState.Cached, chosePrevious: true)
                    : (replacement, EntryState.Modified, chosePrevious: false);
            }
        }
 
        internal readonly struct TableEntry
        {
            private static readonly ImmutableArray<EntryState> s_allAddedEntries = ImmutableArray.Create(EntryState.Added);
            private static readonly ImmutableArray<EntryState> s_allCachedEntries = ImmutableArray.Create(EntryState.Cached);
            private static readonly ImmutableArray<EntryState> s_allModifiedEntries = ImmutableArray.Create(EntryState.Modified);
 
            /// <summary>
            /// All items removed as part of a transformation from non-empty input.
            /// </summary>
            private static readonly ImmutableArray<EntryState> s_allRemovedEntries = ImmutableArray.Create(EntryState.Removed);
 
            /// <summary>
            /// All items removed because the input has been removed.
            /// </summary>
            private static readonly ImmutableArray<EntryState> s_allRemovedDueToInputRemoval = ImmutableArray.Create(EntryState.Removed);
 
            private readonly OneOrMany<T> _items;
            private readonly bool _anyRemoved;
 
            /// <summary>
            /// Represents the corresponding state of each item in <see cref="_items"/>, or contains a single state when
            /// <see cref="_items"/> is populated or when every state of <see cref="_items"/> has the same value.
            /// </summary>
            private readonly ImmutableArray<EntryState> _states;
 
            public TableEntry(OneOrMany<T> items, EntryState state)
                : this(items, GetSingleArray(state), anyRemoved: state == EntryState.Removed) { }
 
            private TableEntry(OneOrMany<T> items, ImmutableArray<EntryState> states, bool anyRemoved)
            {
                Debug.Assert(!states.IsDefault);
                Debug.Assert(states.Length == 1 || states.Distinct().Length > 1);
 
                _items = items;
                _states = states;
                _anyRemoved = anyRemoved;
            }
 
            public bool Matches(TableEntry entry, IEqualityComparer<T> equalityComparer)
            {
                if (!_states.SequenceEqual(entry._states))
                    return false;
 
                if (this.Count != entry.Count)
                    return false;
 
                for (int i = 0, n = this.Count; i < n; i++)
                {
                    if (!equalityComparer.Equals(this.GetItem(i), entry.GetItem(i)))
                        return false;
                }
 
                return true;
            }
 
            public bool IsCached => this._states == s_allCachedEntries || this._states.All(s => s == EntryState.Cached);
 
            public bool IsRemovedDueToInputRemoval => this._states == s_allRemovedDueToInputRemoval;
 
            public int Count => _items.Count;
 
            public T GetItem(int index) => _items[index];
 
            public EntryState GetState(int index) => _states.Length == 1 ? _states[0] : _states[index];
 
            public OneOrMany<T> Items => _items;
 
            public TableEntry AsCached()
            {
                if (!_anyRemoved)
                {
                    return new TableEntry(_items, s_allCachedEntries, anyRemoved: false);
                }
 
                var itemBuilder = ArrayBuilder<T>.GetInstance();
                for (int i = 0; i < this.Count; i++)
                {
                    if (this.GetState(i) != EntryState.Removed)
                    {
                        itemBuilder.Add(this.GetItem(i));
                    }
                }
 
                Debug.Assert(itemBuilder.Count < this.Count);
                return new TableEntry(OneOrMany.Create(itemBuilder.ToImmutableArray()), s_allCachedEntries, anyRemoved: false);
            }
 
            public TableEntry AsRemovedDueToInputRemoval() => new(_items, s_allRemovedDueToInputRemoval, anyRemoved: true);
 
            private static ImmutableArray<EntryState> GetSingleArray(EntryState state) => state switch
            {
                EntryState.Added => s_allAddedEntries,
                EntryState.Cached => s_allCachedEntries,
                EntryState.Modified => s_allModifiedEntries,
                EntryState.Removed => s_allRemovedEntries,
                _ => throw ExceptionUtilities.Unreachable()
            };
 
            public Enumerator GetEnumerator()
                => new(this);
 
            public struct Enumerator
            {
                private readonly TableEntry _entry;
                private int _index = -1;
 
                public Enumerator(TableEntry tableEntry)
                {
                    _entry = tableEntry;
                }
 
                public bool MoveNext()
                {
                    _index++;
                    return _index < _entry.Count;
                }
 
                public T Current => _entry.GetItem(_index);
            }
 
#if DEBUG
            public override string ToString()
            {
                if (this.Count == 1)
                {
                    return $"{GetItem(0)}: {GetState(0)}";
                }
                else
                {
                    var sb = PooledStringBuilder.GetInstance();
                    sb.Builder.Append('{');
                    for (int i = 0; i < Count; i++)
                    {
                        if (i > 0)
                        {
                            sb.Builder.Append(',');
                        }
 
                        sb.Builder.Append(" (");
                        sb.Builder.Append(GetItem(i));
                        sb.Builder.Append(':');
                        sb.Builder.Append(GetState(i));
                        sb.Builder.Append(')');
                    }
 
                    sb.Builder.Append(" }");
                    return sb.ToStringAndFree();
                }
            }
#endif
 
            public sealed class Builder
            {
                private readonly ArrayBuilder<T> _items;
 
                private ArrayBuilder<EntryState>? _states;
                private EntryState? _currentState;
                private bool _anyRemoved;
 
                private readonly int _requestedCapacity;
 
                public Builder(int capacity)
                {
                    _items = ArrayBuilder<T>.GetInstance(capacity);
                    _requestedCapacity = capacity;
                }
 
                public void Add(T item, EntryState state)
                {
                    _items.Add(item);
                    _anyRemoved |= state == EntryState.Removed;
                    if (!_currentState.HasValue)
                    {
                        _currentState = state;
                    }
                    else if (_states is not null)
                    {
                        _states.Add(state);
                    }
                    else if (_currentState != state)
                    {
                        // Create a builder with the right capacity (so we don't waste scratch space). Copy all the same
                        // prior values all the way up to the last item we're about to add.
                        _states = ArrayBuilder<EntryState>.GetInstance(_requestedCapacity);
                        for (int i = 0, n = _items.Count - 1; i < n; i++)
                            _states.Add(_currentState.Value);
 
                        // then finally add the new value at the end.
                        _states.Add(state);
                    }
                }
 
                public TableEntry ToImmutableAndFree()
                {
                    Debug.Assert(_currentState.HasValue, "Created a builder with no values?");
                    Debug.Assert(_items.Count >= 1, "Created a builder with no values?");
 
                    Debug.Assert(_items.Count == _requestedCapacity);
                    Debug.Assert(_states == null || _states.Count == _requestedCapacity);
 
                    return new TableEntry(_items.ToOneOrManyAndFree(), _states?.ToImmutableAndFree() ?? GetSingleArray(_currentState.Value), anyRemoved: _anyRemoved);
                }
            }
        }
    }
}