<commit_before>﻿// 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);

        private readonly ImmutableArray<TableEntry> _states;


        private NodeStateTable(ImmutableArray<TableEntry> states, ImmutableArray<IncrementalGeneratorRunStep> steps, bool hasTrackedSteps)
        {
            Debug.Assert(!hasTrackedSteps || steps.Length == states.Length);

            _states = states;
            Steps = steps;
            IsCached = !states.IsEmpty && states.All(s => s.IsCached);
            HasTrackedSteps = hasTrackedSteps;
        }

        public int Count => _states.Length;

        /// <summary>
        /// Indicates if every entry in this table has a state of <see cref="EntryState.Cached"/>
        /// </summary>
        public bool IsCached { get; }

        public bool IsEmpty => _states.IsEmpty;

        public bool HasTrackedSteps { get; }

        public ImmutableArray<IncrementalGeneratorRunStep> Steps { get; }

        public IEnumerator<NodeStateEntry<T>> GetEnumerator()
        {
            for (int i = 0; i < _states.Length; i++)
            {
                TableEntry inputEntry = _states[i];
                IncrementalGeneratorRunStep? step = HasTrackedSteps ? Steps[i] : null;
                for (int j = 0; j < inputEntry.Count; j++)
                {
                    yield return new NodeStateEntry<T>(inputEntry.GetItem(j), inputEntry.GetState(j), j, step);
                }
            }
        }

        public NodeStateTable<T> AsCached()
        {
            if (IsCached)
                return this;

            var compacted = ArrayBuilder<TableEntry>.GetInstance();
            foreach (var entry in _states)
            {
                if (!entry.IsRemoved)
                {
                    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
            return new NodeStateTable<T>(compacted.ToImmutableAndFree(), ImmutableArray<IncrementalGeneratorRunStep>.Empty, hasTrackedSteps: false);
        }

        IStateTable IStateTable.AsCached() => AsCached();

        public (T item, IncrementalGeneratorRunStep? step) Single()
        {
            Debug.Assert((_states.Length == 1 || _states.Length == 2 && _states[0].IsRemoved) && _states[^1].Count == 1);
            return (_states[^1].GetItem(0), HasTrackedSteps ? Steps[^1] : null);
        }

        public Builder ToBuilder(string? stepName, bool stepTrackingEnabled, IEqualityComparer<T>? equalityComparer = null)
            => new(this, stepName, stepTrackingEnabled, equalityComparer);

        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 sealed class Builder
        {
            private readonly ArrayBuilder<TableEntry> _states;<commit_msg>Set capacity of builder to avoid expensive garbage.<commit_after>﻿// 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);

        private readonly ImmutableArray<TableEntry> _states;


        private NodeStateTable(ImmutableArray<TableEntry> states, ImmutableArray<IncrementalGeneratorRunStep> steps, bool hasTrackedSteps)
        {
            Debug.Assert(!hasTrackedSteps || steps.Length == states.Length);

            _states = states;
            Steps = steps;
            IsCached = !states.IsEmpty && states.All(s => s.IsCached);
            HasTrackedSteps = hasTrackedSteps;
        }

        public int Count => _states.Length;

        /// <summary>
        /// Indicates if every entry in this table has a state of <see cref="EntryState.Cached"/>
        /// </summary>
        public bool IsCached { get; }

        public bool IsEmpty => _states.IsEmpty;

        public bool HasTrackedSteps { get; }

        public ImmutableArray<IncrementalGeneratorRunStep> Steps { get; }

        public IEnumerator<NodeStateEntry<T>> GetEnumerator()
        {
            for (int i = 0; i < _states.Length; i++)
            {
                TableEntry inputEntry = _states[i];
                IncrementalGeneratorRunStep? step = HasTrackedSteps ? Steps[i] : null;
                for (int j = 0; j < inputEntry.Count; j++)
                {
                    yield return new NodeStateEntry<T>(inputEntry.GetItem(j), inputEntry.GetState(j), j, step);
                }
            }
        }

        public NodeStateTable<T> AsCached()
        {
            if (IsCached)
                return this;

            var nonRemovedCount = _states.Count(static e => !e.IsRemoved);

            var compacted = ArrayBuilder<TableEntry>.GetInstance(nonRemovedCount);
            foreach (var entry in _states)
            {
                if (!entry.IsRemoved)
                    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);
        }

        IStateTable IStateTable.AsCached() => AsCached();

        public (T item, IncrementalGeneratorRunStep? step) Single()
        {
            Debug.Assert((_states.Length == 1 || _states.Length == 2 && _states[0].IsRemoved) && _states[^1].Count == 1);
            return (_states[^1].GetItem(0), HasTrackedSteps ? Steps[^1] : null);
        }

        public Builder ToBuilder(string? stepName, bool stepTrackingEnabled, IEqualityComparer<T>? equalityComparer = null)
            => new(this, stepName, stepTrackingEnabled, equalityComparer);

        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 sealed class Builder
        {
            private readonly ArrayBuilder<TableEntry> _states;
{'fraction_non_alphanumeric': 0.07472124014141963, 'fraction_numerical': 0.0014957846070165896, 'mean_word_length': 2.6726591760299625, 'pattern_counts': {'":': 0, '<': 71, '<?xml version=': 0, '>': 78, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4230888', 'n_tokens_mistral': 3745, 'n_tokens_neox': 3565, 'n_words': 1449}