// Copyright (c) Microsoft Corporation. All rights reserved.
// Licensed under the MIT license. See LICENSE file in the project root for full license information.

using Microsoft.Testing.Platform.Helpers;
using Microsoft.Testing.Platform.Resources;

namespace Microsoft.Testing.Platform.Requests;

public sealed partial class TreeNodeFilter
{
    /// <remarks>
    /// The current grammar for the filter looks as follows:
    /// <code>
    /// TREE_NODE_FILTER = EXPR ( '/' EXPR )*
    /// EXPR =
    ///   '(' EXPR ')'
    ///   | EXPR OP EXPR
    ///   | NODE_VALUE
    /// FILTER_EXPR =
    ///   '(' FILTER_EXPR ')'
    ///   | TOKEN '=' TOKEN
    ///   | TOKEN '!=' TOKEN
    ///   | FILTER_EXPR OP FILTER_EXPR
    ///   | TOKEN
    /// OP = '&amp;' | '|'
    /// NODE_VALUE = TOKEN | TOKEN '[' FILTER_EXPR ']'
    /// TOKEN = string
    ///
    /// OR expressions are supported for a single path segment, for example:
    /// <c>/A/B/C/(Test1|Test2)</c>.
    ///
    /// OR expressions over full paths are not supported, for example:
    /// <c>(/A/B/C/Test1)|(/A/B/C/Test2)</c>.
    /// </code>
    /// </remarks>
    /// <exception cref="InvalidOperationException">
    /// Exception thrown, if the filter is malformed, for example <c>A(|B)</c> or <c>A)</c>.
    /// </exception>
    private static List<FilterExpression> ParseFilter(string filter)
    {
        // This parsing is an implementation of Dijkstra's shunting yard algorithm.
        //
        // Parsing works by creating two stacks, the expression stack and the operator stack.
        // For instance when parsing an expression A | B, first A is put on the expression stack,
        // | is placed on the operator stack and B is placed on the expression stack.
        // Finally the filter expressions are generated by applying the operators on the stack to
        // the top most expressions, until the operator stack is empty.
        //
        // Note: We do some additional state tracking to parse just the valid expressions.
        //       For instance we should not allow multiple parameter values like A[P1=1][P2=2]
        //       or allow nested parameters A[P1=B[P2=C]]
        Stack<FilterExpression> expressionStack = new();
        Stack<OperatorKind> operatorStack = new();

        // Note: Whether or not we're at a place where operator is allowed within an expression.
        //       For instance right after an open parenthesis, after an operator or at the beginning
        //       of an expression operators are not allowed.
        bool isOperatorAllowed = false;
        bool isPropAllowed = false;
        bool lastWasOpenParen = false;
        OperatorKind topStackOperator;

        foreach (string token in TokenizeFilter(filter))
        {
            switch (token)
            {
                case "&":
                case "|":
                    if (!isOperatorAllowed)
                    {
                        throw new InvalidOperationException(string.Format(CultureInfo.InvariantCulture, PlatformResources.TreeNodeFilterOperatorNotAllowedErrorMessage, filter));
                    }

                    OperatorKind currentOp = token switch
                    {
                        "&" => OperatorKind.And,
                        "|" => OperatorKind.Or,
                        _ => throw ApplicationStateGuard.Unreachable(),
                    };

                    ProcessHigherPrecedenceOperators(expressionStack, operatorStack, currentOp, filter);

                    isOperatorAllowed = false;
                    isPropAllowed = false;
                    break;

                case "/":
                    ProcessHigherPrecedenceOperators(expressionStack, operatorStack, OperatorKind.Separator, filter);

                    isOperatorAllowed = false;
                    isPropAllowed = false;
                    break;

                case "(":
                    // We should consider pushing a well known expression
                    // such as a NopExpression onto the filter operation stack.
                    // This way it's possible to see in the filter stack the boundaries between the different
                    // operations.
                    // For instance we should be able to distinguish A(&B) vs (A&B), but
                    // if we don't separate subexpression stacks, we won't see
                    operatorStack.Push(OperatorKind.LeftBrace);

                    isOperatorAllowed = false;
                    isPropAllowed = false;
                    break;

                case ")":
                    // Note: If operator is not allowed, we must be at the start of an expression
                    //       for example "(". In that case, it's not valid to complete the statement.
                    if (!isOperatorAllowed)
                    {
                        throw new InvalidOperationException();
                    }

                    // Note: Keep merging the operator stack, until the matching brace.
                    while (true)
                    {
                        if (operatorStack.Count == 0)
                        {
                            // Reaching this implies that the input string is unbalanced.
                            // For instance ")".
                            throw new InvalidOperationException(string.Format(CultureInfo.InvariantCulture, PlatformResources.TreeNodeFilterUnbalancedFilterErrorMessage, filter, '(', ')'));
                        }

                        topStackOperator = operatorStack.Pop();
                        if (topStackOperator == OperatorKind.LeftBrace)
                        {
                            break;
                        }

                        ProcessStackOperator(topStackOperator, expressionStack, operatorStack, filter);
                    }

                    isOperatorAllowed = true;
                    isPropAllowed = false;

                    break;

                case "]":
                    // Note: If operator is not allowed, we must be at the start of an expression
                    //       for example "[". In that case, it's not valid to complete the statement.
                    if (!isOperatorAllowed)
                    {
                        throw new InvalidOperationException();
                    }

                    // Note: Keep merging the operator stack, until the matching parameter.
                    while (true)
                    {
                        if (operatorStack.Count == 0)
                        {
                            // Reaching this implies that the input string is unbalanced.
                            // For instance "]".
                            throw new InvalidOperationException(string.Format(CultureInfo.InvariantCulture, PlatformResources.TreeNodeFilterUnbalancedFilterErrorMessage, filter, '[', ']'));
                        }

                        topStackOperator = operatorStack.Pop();
                        if (topStackOperator == OperatorKind.LeftParameter)
                        {
                            break;
                        }

                        ProcessStackOperator(topStackOperator, expressionStack, operatorStack, filter);
                    }

                    // We should end up with an expression and a property.
                    FilterExpression propExpr = expressionStack.Pop();
                    FilterExpression nodeExpr = expressionStack.Pop();

                    if (nodeExpr is not ValueExpression nodeValueExpr)
                    {
                        throw new InvalidOperationException();
                    }

                    expressionStack.Push(new ValueAndPropertyExpression(nodeValueExpr, propExpr));

                    isPropAllowed = false;
                    isOperatorAllowed = true;

                    break;

                case "[":
                    if (!isPropAllowed)
                    {
                        throw new InvalidOperationException();
                    }

                    operatorStack.Push(OperatorKind.LeftParameter);

                    isOperatorAllowed = false;
                    isPropAllowed = false;
                    break;

                case "=":
                    operatorStack.Push(OperatorKind.FilterEquals);

                    isOperatorAllowed = false;
                    isPropAllowed = false;
                    break;

                case "!=":
                    operatorStack.Push(OperatorKind.FilterNotEquals);

                    isOperatorAllowed = false;
                    isPropAllowed = false;
                    break;

                case "!" when lastWasOpenParen:
                    operatorStack.Push(OperatorKind.UnaryNot);
                    break;

                default:
                    expressionStack.Push(new ValueExpression(token));

                    isOperatorAllowed = true;
                    isPropAllowed = true;
                    break;
            }

            lastWasOpenParen = token == "(";
        }

        // Note: What we should end with (as long as the expression is a valid filter)
        // is a bunch of processed separator operators followed by a potentially unprocessed expression.
        while (operatorStack.Count > 0 && operatorStack.Peek() != OperatorKind.Separator)
        {
            topStackOperator = operatorStack.Pop();
            ProcessStackOperator(topStackOperator, expressionStack, operatorStack, filter);
        }

        var parsedFilter = expressionStack.Reverse().ToList();

        for (int i = 0; i < parsedFilter.Count; i++)
        {
            ValidateExpression(parsedFilter[i], isMatchAllAllowed: i == parsedFilter.Count - 1);
        }

        return parsedFilter;

        // Note: By default as the stack is popped, the operators are
        // processed in order, so A B C, Op1 Op2
        // will be processed as A Op1 (B Op2 C)
        // In cases where the Op1 has a higher priority the natural parsing would
        // result in (A Op1 B) Op2 C. As such, we need to process higher priority
        // operators before pushing lower priority operators on the stack.
        static void ProcessHigherPrecedenceOperators(
            Stack<FilterExpression> expressionStack,
            Stack<OperatorKind> operatorStack,
            OperatorKind currentOp,
            string currentFilter)
        {
            while (operatorStack.Count != 0 && operatorStack.Peek() > currentOp)
            {
                OperatorKind topStackOperator = operatorStack.Pop();
                ProcessStackOperator(topStackOperator, expressionStack, operatorStack, currentFilter);
                break;
            }

            operatorStack.Push(currentOp);
        }
    }
}
