// 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.Threading;
using Microsoft.CodeAnalysis.Collections;
using Microsoft.CodeAnalysis.Formatting.Rules;
using Microsoft.CodeAnalysis.Internal.Log;
using Microsoft.CodeAnalysis.LanguageService;
using Microsoft.CodeAnalysis.PooledObjects;
using Microsoft.CodeAnalysis.Shared.Extensions;
using Microsoft.CodeAnalysis.Shared.Utilities;
using Microsoft.CodeAnalysis.Text;
using Roslyn.Utilities;
 
namespace Microsoft.CodeAnalysis.Formatting;
 
// TODO : two alternative design possible for formatting engine
//
//        1. use AAL (TPL Dataflow) in .NET 4.5 to run things concurrently in sequential order
//           * this has a problem of the new TPL lib being not released yet and possibility of not using all cores.
//
//        2. create dependency graph between operations, and format them in topological order and 
//           run chunks that don't have dependency in parallel (kirill's idea)
//           * this requires defining dependencies on each operations. can't use dependency between tokens since
//             that would create too big graph. key for this approach is how to reduce size of graph.
internal abstract partial class AbstractFormatEngine
{
    // Intentionally do not trim the capacities of these collections down.  We will repeatedly try to format large
    // files as we edit them and this will produce a lot of garbage as we free the internal array backing the list
    // over and over again.
    private static readonly ObjectPool<SegmentedList<TokenPairWithOperations>> s_tokenPairListPool = new(() => [], trimOnFree: false);
 
    private readonly ChainedFormattingRules _formattingRules;
 
    private readonly SyntaxNode _commonRoot;
    private readonly SyntaxToken _startToken;
    private readonly SyntaxToken _endToken;
 
    protected readonly TextSpan SpanToFormat;
 
    internal readonly SyntaxFormattingOptions Options;
    internal readonly TreeData TreeData;
 
    /// <summary>
    /// It is very common to be formatting lots of documents at teh same time, with the same set of formatting rules and
    /// options. To help with that, cache the last set of ChainedFormattingRules that was produced, as it is not a cheap
    /// type to create.
    /// </summary>
    /// <remarks>
    /// Stored as a <see cref="Tuple{T1, T2, T3}"/> instead of a <see cref="ValueTuple{T1, T2, T3}"/> so we don't have
    /// to worry about torn write concerns.
    /// </remarks>
    private static Tuple<ImmutableArray<AbstractFormattingRule>, SyntaxFormattingOptions, ChainedFormattingRules>? s_lastRulesAndOptions;
 
    public AbstractFormatEngine(
        TreeData treeData,
        SyntaxFormattingOptions options,
        ImmutableArray<AbstractFormattingRule> formattingRules,
        SyntaxToken startToken,
        SyntaxToken endToken)
        : this(
              treeData,
              options,
              GetChainedFormattingRules(formattingRules, options),
              startToken,
              endToken)
    {
    }
 
    private static ChainedFormattingRules GetChainedFormattingRules(ImmutableArray<AbstractFormattingRule> formattingRules, SyntaxFormattingOptions options)
    {
        var lastRulesAndOptions = s_lastRulesAndOptions;
        if (formattingRules != lastRulesAndOptions?.Item1 || options != s_lastRulesAndOptions?.Item2)
        {
            lastRulesAndOptions = Tuple.Create(formattingRules, options, new ChainedFormattingRules(formattingRules, options));
            s_lastRulesAndOptions = lastRulesAndOptions;
        }
 
        return lastRulesAndOptions.Item3;
    }
 
    internal AbstractFormatEngine(
        TreeData treeData,
        SyntaxFormattingOptions options,
        ChainedFormattingRules formattingRules,
        SyntaxToken startToken,
        SyntaxToken endToken)
    {
        Contract.ThrowIfTrue(treeData.Root.IsInvalidTokenRange(startToken, endToken));
 
        this.Options = options;
        this.TreeData = treeData;
        _formattingRules = formattingRules;
 
        _startToken = startToken;
        _endToken = endToken;
 
        // get span and common root
        this.SpanToFormat = GetSpanToFormat();
        _commonRoot = startToken.GetCommonRoot(endToken) ?? throw ExceptionUtilities.Unreachable();
    }
 
    internal abstract IHeaderFacts HeaderFacts { get; }
 
    protected abstract AbstractTriviaDataFactory CreateTriviaFactory();
    protected abstract AbstractFormattingResult CreateFormattingResult(TokenStream tokenStream);
 
    public AbstractFormattingResult Format(CancellationToken cancellationToken)
    {
        using (Logger.LogBlock(FunctionId.Formatting_Format, FormatSummary, cancellationToken))
        {
            // setup environment
            using var nodeOperations = CreateNodeOperations(cancellationToken);
 
            var tokenStream = new TokenStream(this.TreeData, Options, this.SpanToFormat, CreateTriviaFactory());
            using var tokenOperations = s_tokenPairListPool.GetPooledObject();
            AddTokenOperations(tokenStream, tokenOperations.Object, cancellationToken);
 
            // initialize context
            var context = CreateFormattingContext(tokenStream, cancellationToken);
 
            // start anchor task that will be used later
            cancellationToken.ThrowIfCancellationRequested();
            var anchorContext = nodeOperations.AnchorIndentationOperations.Do(context.AddAnchorIndentationOperation);
 
            BuildContext(context, nodeOperations, cancellationToken);
 
            ApplyBeginningOfTreeTriviaOperation(context, cancellationToken);
 
            ApplyTokenOperations(context, nodeOperations, tokenOperations.Object, cancellationToken);
 
            ApplyTriviaOperations(context, cancellationToken);
 
            ApplyEndOfTreeTriviaOperation(context, cancellationToken);
 
            return CreateFormattingResult(tokenStream);
        }
    }
 
    protected virtual FormattingContext CreateFormattingContext(TokenStream tokenStream, CancellationToken cancellationToken)
    {
        // initialize context
        var context = new FormattingContext(this, tokenStream);
        context.Initialize(_formattingRules, _startToken, _endToken, cancellationToken);
 
        return context;
    }
 
    protected virtual NodeOperations CreateNodeOperations(CancellationToken cancellationToken)
    {
        cancellationToken.ThrowIfCancellationRequested();
 
        var nodeOperations = new NodeOperations();
 
        var indentBlockOperationScratch = new List<IndentBlockOperation>();
        var alignmentOperationScratch = new List<AlignTokensOperation>();
        var anchorIndentationOperationsScratch = new List<AnchorIndentationOperation>();
        using var _ = ArrayBuilder<SuppressOperation>.GetInstance(out var suppressOperationScratch);
 
        // Cache delegates out here to avoid allocation overhead.
 
        var addIndentBlockOperations = _formattingRules.AddIndentBlockOperations;
        var addSuppressOperation = _formattingRules.AddSuppressOperations;
        var addAlignTokensOperations = _formattingRules.AddAlignTokensOperations;
        var addAnchorIndentationOperations = _formattingRules.AddAnchorIndentationOperations;
 
        // iterating tree is very expensive. only do it once.
        foreach (var node in _commonRoot.DescendantNodesAndSelf(this.SpanToFormat))
        {
            cancellationToken.ThrowIfCancellationRequested();
 
            AddOperations(nodeOperations.IndentBlockOperation, indentBlockOperationScratch, node, addIndentBlockOperations);
            AddOperations(nodeOperations.SuppressOperation, suppressOperationScratch, node, addSuppressOperation);
            AddOperations(nodeOperations.AlignmentOperation, alignmentOperationScratch, node, addAlignTokensOperations);
            AddOperations(nodeOperations.AnchorIndentationOperations, anchorIndentationOperationsScratch, node, addAnchorIndentationOperations);
        }
 
        // make sure we order align operation from left to right
        nodeOperations.AlignmentOperation.Sort(static (o1, o2) => o1.BaseToken.Span.CompareTo(o2.BaseToken.Span));
 
        return nodeOperations;
    }
 
    private static void AddOperations<T>(SegmentedList<T> operations, List<T> scratch, SyntaxNode node, Action<List<T>, SyntaxNode> addOperations)
    {
        Debug.Assert(scratch.Count == 0);
 
        addOperations(scratch, node);
        foreach (var operation in scratch)
        {
            if (operation is not null)
                operations.Add(operation);
        }
 
        scratch.Clear();
    }
 
    private static void AddOperations<T>(SegmentedList<T> operations, ArrayBuilder<T> scratch, SyntaxNode node, Action<ArrayBuilder<T>, SyntaxNode> addOperations)
    {
        Debug.Assert(scratch.Count == 0);
 
        addOperations(scratch, node);
        foreach (var operation in scratch)
        {
            if (operation is not null)
                operations.Add(operation);
        }
 
        scratch.Clear();
    }
 
    private void AddTokenOperations(
        TokenStream tokenStream,
        SegmentedList<TokenPairWithOperations> list,
        CancellationToken cancellationToken)
    {
        cancellationToken.ThrowIfCancellationRequested();
 
        using (Logger.LogBlock(FunctionId.Formatting_CollectTokenOperation, cancellationToken))
        {
            // Grow the SegmentedList in a single allocation if the resultant list is going to be
            // significantly larger than it's existing Capacity.
            if (tokenStream.TokenCount > 2 * list.Capacity)
                list.EnsureCapacity(tokenStream.TokenCount);
 
            foreach (var (index, currentToken, nextToken) in tokenStream.TokenIterator)
            {
                cancellationToken.ThrowIfCancellationRequested();
 
                var spaceOperation = _formattingRules.GetAdjustSpacesOperation(currentToken, nextToken);
                var lineOperation = _formattingRules.GetAdjustNewLinesOperation(currentToken, nextToken);
 
                list.Add(new TokenPairWithOperations(tokenStream, index, spaceOperation, lineOperation));
            }
        }
    }
 
    private void ApplyTokenOperations(
        FormattingContext context,
        NodeOperations nodeOperations,
        SegmentedList<TokenPairWithOperations> tokenOperations,
        CancellationToken cancellationToken)
    {
        var applier = new OperationApplier(context, _formattingRules);
        ApplySpaceAndWrappingOperations(context, tokenOperations, applier, cancellationToken);
 
        ApplyAnchorOperations(context, tokenOperations, applier, cancellationToken);
 
        ApplySpecialOperations(context, nodeOperations, applier, cancellationToken);
    }
 
    private void ApplyBeginningOfTreeTriviaOperation(
        FormattingContext context, CancellationToken cancellationToken)
    {
        if (!context.TokenStream.FormatBeginningOfTree)
        {
            return;
        }
 
        // remove all leading indentation
        var triviaInfo = context.TokenStream.GetTriviaDataAtBeginningOfTree().WithIndentation(0, context, _formattingRules, cancellationToken);
 
        triviaInfo.Format(context, _formattingRules, BeginningOfTreeTriviaInfoApplier, cancellationToken);
 
        return;
 
        // local functions
        static void BeginningOfTreeTriviaInfoApplier(int i, TokenStream ts, TriviaData info)
            => ts.ApplyBeginningOfTreeChange(info);
    }
 
    private void ApplyEndOfTreeTriviaOperation(
        FormattingContext context, CancellationToken cancellationToken)
    {
        if (!context.TokenStream.FormatEndOfTree)
        {
            return;
        }
 
        if (context.IsFormattingDisabled(new TextSpan(context.TokenStream.LastTokenInStream.Token.SpanStart, 0)))
        {
            // Formatting is suppressed in the document, and not restored before the end
            return;
        }
 
        // remove all trailing indentation
        var triviaInfo = context.TokenStream.GetTriviaDataAtEndOfTree().WithIndentation(0, context, _formattingRules, cancellationToken);
 
        triviaInfo.Format(context, _formattingRules, EndOfTreeTriviaInfoApplier, cancellationToken);
 
        return;
 
        // local functions
        static void EndOfTreeTriviaInfoApplier(int i, TokenStream ts, TriviaData info)
            => ts.ApplyEndOfTreeChange(info);
    }
 
    [PerformanceSensitive("https://github.com/dotnet/roslyn/issues/30819", AllowCaptures = false)]
    private void ApplyTriviaOperations(FormattingContext context, CancellationToken cancellationToken)
    {
        for (var i = 0; i < context.TokenStream.TokenCount - 1; i++)
        {
            cancellationToken.ThrowIfCancellationRequested();
            TriviaFormatter(i, context, _formattingRules, cancellationToken);
        }
 
        return;
 
        // local functions
 
        static void RegularApplier(int tokenPairIndex, TokenStream ts, TriviaData info)
            => ts.ApplyChange(tokenPairIndex, info);
 
        static void TriviaFormatter(int tokenPairIndex, FormattingContext ctx, ChainedFormattingRules formattingRules, CancellationToken ct)
        {
            if (ctx.IsFormattingDisabled(tokenPairIndex))
            {
                return;
            }
 
            var triviaInfo = ctx.TokenStream.GetTriviaData(tokenPairIndex);
            triviaInfo.Format(
                ctx,
                formattingRules,
                RegularApplier,
                ct,
                tokenPairIndex);
        }
    }
 
    private TextSpan GetSpanToFormat()
    {
        var startPosition = this.TreeData.IsFirstToken(_startToken) ? this.TreeData.StartPosition : _startToken.SpanStart;
        var endPosition = this.TreeData.IsLastToken(_endToken) ? this.TreeData.EndPosition : _endToken.Span.End;
 
        return TextSpan.FromBounds(startPosition, endPosition);
    }
 
    private static void ApplySpecialOperations(
        FormattingContext context, NodeOperations nodeOperationsCollector, OperationApplier applier, CancellationToken cancellationToken)
    {
        // apply alignment operation
        using (Logger.LogBlock(FunctionId.Formatting_ApplyAlignOperation, cancellationToken))
        {
            cancellationToken.ThrowIfCancellationRequested();
 
            // TODO : figure out a way to run alignment operations in parallel. probably find
            // unions and run each chunk in separate tasks
            var previousChangesMap = new Dictionary<SyntaxToken, int>();
            var alignmentOperations = nodeOperationsCollector.AlignmentOperation;
 
            alignmentOperations.Do(operation =>
            {
                cancellationToken.ThrowIfCancellationRequested();
                applier.ApplyAlignment(operation, previousChangesMap, cancellationToken);
            });
 
            // go through all relative indent block operation, and see whether it is affected by previous operations
            context.GetAllRelativeIndentBlockOperations().Do(o =>
            {
                cancellationToken.ThrowIfCancellationRequested();
                applier.ApplyBaseTokenIndentationChangesFromTo(FindCorrectBaseTokenOfRelativeIndentBlockOperation(o, context.TokenStream), o.StartToken, o.EndToken, previousChangesMap, cancellationToken);
            });
        }
    }
 
    private static void ApplyAnchorOperations(
        FormattingContext context,
        SegmentedList<TokenPairWithOperations> tokenOperations,
        OperationApplier applier,
        CancellationToken cancellationToken)
    {
        using (Logger.LogBlock(FunctionId.Formatting_ApplyAnchorOperation, cancellationToken))
        {
            // TODO: find out a way to apply anchor operation concurrently if possible
            var previousChangesMap = new Dictionary<SyntaxToken, int>();
            foreach (var p in tokenOperations)
            {
                cancellationToken.ThrowIfCancellationRequested();
                if (!AnchorOperationCandidate(p))
                    continue;
 
                var pairIndex = p.PairIndex;
                applier.ApplyAnchorIndentation(pairIndex, previousChangesMap, cancellationToken);
            }
 
            // go through all relative indent block operation, and see whether it is affected by the anchor operation
            context.GetAllRelativeIndentBlockOperations().Do(o =>
            {
                cancellationToken.ThrowIfCancellationRequested();
                applier.ApplyBaseTokenIndentationChangesFromTo(FindCorrectBaseTokenOfRelativeIndentBlockOperation(o, context.TokenStream), o.StartToken, o.EndToken, previousChangesMap, cancellationToken);
            });
        }
    }
 
    private static bool AnchorOperationCandidate(TokenPairWithOperations pair)
    {
        if (pair.LineOperation == null)
        {
            return pair.TokenStream.GetTriviaData(pair.PairIndex).SecondTokenIsFirstTokenOnLine;
        }
 
        if (pair.LineOperation.Option == AdjustNewLinesOption.ForceLinesIfOnSingleLine)
        {
            return !pair.TokenStream.TwoTokensOriginallyOnSameLine(pair.Token1, pair.Token2) &&
                    pair.TokenStream.GetTriviaData(pair.PairIndex).SecondTokenIsFirstTokenOnLine;
        }
 
        return false;
    }
 
    private static SyntaxToken FindCorrectBaseTokenOfRelativeIndentBlockOperation(IndentBlockOperation operation, TokenStream tokenStream)
    {
        if (operation.Option.IsOn(IndentBlockOption.RelativeToFirstTokenOnBaseTokenLine))
        {
            return tokenStream.FirstTokenOfBaseTokenLine(operation.BaseToken);
        }
 
        return operation.BaseToken;
    }
 
    private static void ApplySpaceAndWrappingOperations(
        FormattingContext context,
        SegmentedList<TokenPairWithOperations> tokenOperations,
        OperationApplier applier,
        CancellationToken cancellationToken)
    {
        using (Logger.LogBlock(FunctionId.Formatting_ApplySpaceAndLine, cancellationToken))
        {
            // go through each token pairs and apply operations
            foreach (var operationPair in tokenOperations)
                ApplySpaceAndWrappingOperationsBody(context, operationPair, applier, cancellationToken);
        }
    }
 
    private static void ApplySpaceAndWrappingOperationsBody(
        FormattingContext context,
        TokenPairWithOperations operation,
        OperationApplier applier,
        CancellationToken cancellationToken)
    {
        var token1 = operation.Token1;
        var token2 = operation.Token2;
 
        // check whether one of tokens is missing (which means syntax error exist around two tokens)
        // in error case, we leave code as user wrote
        if (token1.IsMissing || token2.IsMissing)
        {
            return;
        }
 
        var triviaInfo = context.TokenStream.GetTriviaData(operation.PairIndex);
        var spanBetweenTokens = TextSpan.FromBounds(token1.Span.End, token2.SpanStart);
 
        if (operation.LineOperation != null)
        {
            if (!context.IsWrappingSuppressed(spanBetweenTokens, triviaInfo.TreatAsElastic))
            {
                // TODO : need to revisit later for the case where line and space operations
                // are conflicting each other by forcing new lines and removing new lines.
                //
                // if wrapping operation applied, no need to run any other operation
                if (applier.Apply(operation.LineOperation, operation.PairIndex, cancellationToken))
                {
                    return;
                }
            }
        }
 
        if (operation.SpaceOperation != null)
        {
            if (!context.IsSpacingSuppressed(spanBetweenTokens, triviaInfo.TreatAsElastic))
            {
                applier.Apply(operation.SpaceOperation, operation.PairIndex);
            }
        }
    }
 
    private static void BuildContext(
        FormattingContext context,
        NodeOperations nodeOperations,
        CancellationToken cancellationToken)
    {
        // add scope operation (run each kind sequentially)
        using (Logger.LogBlock(FunctionId.Formatting_BuildContext, cancellationToken))
        {
            cancellationToken.ThrowIfCancellationRequested();
            context.AddIndentBlockOperations(nodeOperations.IndentBlockOperation, cancellationToken);
            context.AddSuppressOperations(nodeOperations.SuppressOperation, cancellationToken);
        }
    }
 
    /// <summary>
    /// return summary for current formatting work
    /// </summary>
    private string FormatSummary()
    {
        return string.Format("({0}) ({1} - {2})",
            this.SpanToFormat,
            _startToken.ToString().Replace("\r\n", "\\r\\n"),
            _endToken.ToString().Replace("\r\n", "\\r\\n"));
    }
}