///////////////////////////////////////////////////////////////////////////////////////////////
// checkstyle: Checks Java source code and other text files for adherence to a set of rules.
// Copyright (C) 2001-2025 the original author or authors.
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
///////////////////////////////////////////////////////////////////////////////////////////////

package com.puppycrawl.tools.checkstyle.checks.metrics;

import java.math.BigInteger;
import java.util.ArrayDeque;
import java.util.Deque;

import com.puppycrawl.tools.checkstyle.FileStatefulCheck;
import com.puppycrawl.tools.checkstyle.api.AbstractCheck;
import com.puppycrawl.tools.checkstyle.api.DetailAST;
import com.puppycrawl.tools.checkstyle.api.TokenTypes;
import com.puppycrawl.tools.checkstyle.utils.TokenUtil;

/**
 * <div>
 * Checks the NPATH complexity against a specified limit.
 * </div>
 *
 * <p>
 * The NPATH metric computes the number of possible execution paths through a
 * function(method). It takes into account the nesting of conditional statements
 * and multipart boolean expressions (A &amp;&amp; B, C || D, E ? F :G and
 * their combinations).
 * </p>
 *
 * <p>
 * The NPATH metric was designed base on Cyclomatic complexity to avoid problem
 * of Cyclomatic complexity metric like nesting level within a function(method).
 * </p>
 *
 * <p>
 * Metric was described at <a href="http://dl.acm.org/citation.cfm?id=42379">
 * "NPATH: a measure of execution pathcomplexity and its applications"</a>.
 * If you need detailed description of algorithm, please read that article,
 * it is well written and have number of examples and details.
 * </p>
 *
 * <p>
 * Here is some quotes:
 * </p>
 * <blockquote>
 * An NPATH threshold value of 200 has been established for a function.
 * The value 200 is based on studies done at AT&amp;T Bell Laboratories [1988 year].
 * </blockquote>
 * <blockquote>
 * Some of the most effective methods of reducing the NPATH value include:
 * <ul>
 * <li>
 * distributing functionality;
 * </li>
 * <li>
 * implementing multiple if statements as a switch statement;
 * </li>
 * <li>
 * creating a separate function for logical expressions with a high count of
 * variables and (&amp;&amp;) and or (||) operators.
 * </li>
 * </ul>
 * </blockquote>
 * <blockquote>
 * Although strategies to reduce the NPATH complexity of functions are important,
 * care must be taken not to distort the logical clarity of the software by
 * applying a strategy to reduce the complexity of functions. That is, there is
 * a point of diminishing return beyond which a further attempt at reduction of
 * complexity distorts the logical clarity of the system structure.
 * </blockquote>
 * <div class="wrapper">
 * <table>
 * <caption>Examples</caption>
 * <thead><tr><th>Structure</th><th>Complexity expression</th></tr></thead>
 * <tr><td>if ([expr]) { [if-range] }</td><td>NP(if-range) + 1 + NP(expr)</td></tr>
 * <tr><td>if ([expr]) { [if-range] } else { [else-range] }</td>
 * <td>NP(if-range)+ NP(else-range) + NP(expr)</td></tr>
 * <tr><td>while ([expr]) { [while-range] }</td><td>NP(while-range) + NP(expr) + 1</td></tr>
 * <tr><td>do { [do-range] } while ([expr])</td><td>NP(do-range) + NP(expr) + 1</td></tr>
 * <tr><td>for([expr1]; [expr2]; [expr3]) { [for-range] }</td>
 * <td>NP(for-range) + NP(expr1)+ NP(expr2) + NP(expr3) + 1</td></tr>
 * <tr><td>switch ([expr]) { case : [case-range] default: [default-range] }</td>
 * <td>S(i=1:i=n)NP(case-range[i]) + NP(default-range) + NP(expr)</td></tr>
 * <tr><td>when[expr]</td><td>NP(expr) + 1</td></tr>
 * <tr><td>[expr1] ? [expr2] : [expr3]</td><td>NP(expr1) + NP(expr2) + NP(expr3) + 2</td></tr>
 * <tr><td>goto label</td><td>1</td></tr><tr><td>break</td><td>1</td></tr>
 * <tr><td>Expressions</td>
 * <td>Number of &amp;&amp; and || operators in expression. No operators - 0</td></tr>
 * <tr><td>continue</td><td>1</td></tr><tr><td>return</td><td>1</td></tr>
 * <tr><td>Statement (even sequential statements)</td><td>1</td></tr>
 * <tr><td>Empty block {}</td><td>1</td></tr><tr><td>Function call</td><td>1</td>
 * </tr><tr><td>Function(Method) declaration or Block</td><td>P(i=1:i=N)NP(Statement[i])</td></tr>
 * </table>
 * </div>
 *
 * <p>
 * <b>Rationale:</b> Nejmeh says that his group had an informal NPATH limit of
 * 200 on individual routines; functions(methods) that exceeded this value were
 * candidates for further decomposition - or at least a closer look.
 * <b>Please do not be fanatic with limit 200</b> - choose number that suites
 * your project style. Limit 200 is empirical number base on some sources of at
 * AT&amp;T Bell Laboratories of 1988 year.
 * </p>
 * <ul>
 * <li>
 * Property {@code max} - Specify the maximum threshold allowed.
 * Type is {@code int}.
 * Default value is {@code 200}.
 * </li>
 * </ul>
 *
 * <p>
 * Parent is {@code com.puppycrawl.tools.checkstyle.TreeWalker}
 * </p>
 *
 * <p>
 * Violation Message Keys:
 * </p>
 * <ul>
 * <li>
 * {@code npathComplexity}
 * </li>
 * </ul>
 *
 * @since 3.4
 */
// -@cs[AbbreviationAsWordInName] Can't change check name
@FileStatefulCheck
public final class NPathComplexityCheck extends AbstractCheck {

    /**
     * A key is pointing to the warning message text in "messages.properties"
     * file.
     */
    public static final String MSG_KEY = "npathComplexity";

    /** Tokens that are considered as case labels. */
    private static final int[] CASE_LABEL_TOKENS = {
        TokenTypes.EXPR,
        TokenTypes.PATTERN_DEF,
        TokenTypes.PATTERN_VARIABLE_DEF,
        TokenTypes.RECORD_PATTERN_DEF,
    };

    /** Default allowed complexity. */
    private static final int DEFAULT_MAX = 200;

    /** The initial current value. */
    private static final BigInteger INITIAL_VALUE = BigInteger.ZERO;

    /**
     * Stack of NP values for ranges.
     */
    private final Deque<BigInteger> rangeValues = new ArrayDeque<>();

    /** Stack of NP values for expressions. */
    private final Deque<Integer> expressionValues = new ArrayDeque<>();

    /** Stack of belongs to range values for question operator. */
    private final Deque<Boolean> afterValues = new ArrayDeque<>();

    /**
     * Range of the last processed expression. Used for checking that ternary operation
     * which is a part of expression won't be processed for second time.
     */
    private final TokenEnd processingTokenEnd = new TokenEnd();

    /** NP value for current range. */
    private BigInteger currentRangeValue;

    /** Specify the maximum threshold allowed. */
    private int max = DEFAULT_MAX;

    /** True, when branch is visited, but not leaved. */
    private boolean branchVisited;

    /**
     * Setter to specify the maximum threshold allowed.
     *
     * @param max the maximum threshold
     * @since 3.4
     */
    public void setMax(int max) {
        this.max = max;
    }

    @Override
    public int[] getDefaultTokens() {
        return getRequiredTokens();
    }

    @Override
    public int[] getAcceptableTokens() {
        return getRequiredTokens();
    }

    @Override
    public int[] getRequiredTokens() {
        return new int[] {
            TokenTypes.CTOR_DEF,
            TokenTypes.METHOD_DEF,
            TokenTypes.STATIC_INIT,
            TokenTypes.INSTANCE_INIT,
            TokenTypes.LITERAL_WHILE,
            TokenTypes.LITERAL_DO,
            TokenTypes.LITERAL_FOR,
            TokenTypes.LITERAL_IF,
            TokenTypes.LITERAL_ELSE,
            TokenTypes.LITERAL_SWITCH,
            TokenTypes.CASE_GROUP,
            TokenTypes.LITERAL_TRY,
            TokenTypes.LITERAL_CATCH,
            TokenTypes.QUESTION,
            TokenTypes.LITERAL_RETURN,
            TokenTypes.LITERAL_DEFAULT,
            TokenTypes.COMPACT_CTOR_DEF,
            TokenTypes.SWITCH_RULE,
            TokenTypes.LITERAL_WHEN,
        };
    }

    @Override
    public void beginTree(DetailAST rootAST) {
        rangeValues.clear();
        expressionValues.clear();
        afterValues.clear();
        processingTokenEnd.reset();
        currentRangeValue = INITIAL_VALUE;
        branchVisited = false;
    }

    @Override
    public void visitToken(DetailAST ast) {
        switch (ast.getType()) {
            case TokenTypes.LITERAL_IF, TokenTypes.LITERAL_SWITCH,
                 TokenTypes.LITERAL_WHILE, TokenTypes.LITERAL_DO,
                 TokenTypes.LITERAL_FOR -> visitConditional(ast, 1);

            case TokenTypes.QUESTION -> visitUnitaryOperator(ast, 2);

            case TokenTypes.LITERAL_RETURN -> visitUnitaryOperator(ast, 0);

            case TokenTypes.LITERAL_WHEN -> visitWhenExpression(ast, 1);

            case TokenTypes.CASE_GROUP -> {
                final int caseNumber = countCaseTokens(ast);
                branchVisited = true;
                pushValue(caseNumber);
            }

            case TokenTypes.SWITCH_RULE -> {
                final int caseConstantNumber = countCaseConstants(ast);
                branchVisited = true;
                pushValue(caseConstantNumber);
            }

            case TokenTypes.LITERAL_ELSE -> {
                branchVisited = true;
                if (currentRangeValue.equals(BigInteger.ZERO)) {
                    currentRangeValue = BigInteger.ONE;
                }
                pushValue(0);
            }

            case TokenTypes.LITERAL_TRY,
                 TokenTypes.LITERAL_CATCH,
                 TokenTypes.LITERAL_DEFAULT -> pushValue(1);

            case TokenTypes.CTOR_DEF,
                 TokenTypes.METHOD_DEF,
                 TokenTypes.INSTANCE_INIT,
                 TokenTypes.STATIC_INIT,
                 TokenTypes.COMPACT_CTOR_DEF -> pushValue(0);

            default -> {
                // do nothing
            }
        }
    }

    @Override
    public void leaveToken(DetailAST ast) {
        switch (ast.getType()) {
            case TokenTypes.LITERAL_WHILE,
                 TokenTypes.LITERAL_DO,
                 TokenTypes.LITERAL_FOR,
                 TokenTypes.LITERAL_IF,
                 TokenTypes.LITERAL_SWITCH,
                 TokenTypes.LITERAL_WHEN -> leaveConditional();

            case TokenTypes.LITERAL_TRY -> leaveMultiplyingConditional();

            case TokenTypes.LITERAL_RETURN,
                 TokenTypes.QUESTION -> leaveUnitaryOperator();

            case TokenTypes.LITERAL_CATCH -> leaveAddingConditional();

            case TokenTypes.LITERAL_DEFAULT -> leaveBranch();

            case TokenTypes.LITERAL_ELSE,
                 TokenTypes.CASE_GROUP,
                 TokenTypes.SWITCH_RULE -> {
                leaveBranch();
                branchVisited = false;
            }

            case TokenTypes.CTOR_DEF,
                 TokenTypes.METHOD_DEF,
                 TokenTypes.INSTANCE_INIT,
                 TokenTypes.STATIC_INIT,
                 TokenTypes.COMPACT_CTOR_DEF -> leaveMethodDef(ast);

            default -> {
                // do nothing
            }
        }
    }

    /**
     * Visits if, while, do-while, for and switch tokens - all of them have expression in
     * parentheses which is used for calculation.
     *
     * @param ast visited token.
     * @param basicBranchingFactor default number of branches added.
     */
    private void visitConditional(DetailAST ast, int basicBranchingFactor) {
        int expressionValue = basicBranchingFactor;
        DetailAST bracketed;
        for (bracketed = ast.findFirstToken(TokenTypes.LPAREN);
                bracketed.getType() != TokenTypes.RPAREN;
                bracketed = bracketed.getNextSibling()) {
            expressionValue += countConditionalOperators(bracketed);
        }
        processingTokenEnd.setToken(bracketed);
        pushValue(expressionValue);
    }

    /**
     * Visits when expression token. There is no guarantee that when expression will be
     * bracketed, so we don't use visitConditional method.
     *
     * @param ast visited token.
     * @param basicBranchingFactor default number of branches added.
     */
    private void visitWhenExpression(DetailAST ast, int basicBranchingFactor) {
        final int expressionValue = basicBranchingFactor + countConditionalOperators(ast);
        processingTokenEnd.setToken(getLastToken(ast));
        pushValue(expressionValue);
    }

    /**
     * Visits ternary operator (?:) and return tokens. They differ from those processed by
     * visitConditional method in that their expression isn't bracketed.
     *
     * @param ast visited token.
     * @param basicBranchingFactor number of branches inherently added by this token.
     */
    private void visitUnitaryOperator(DetailAST ast, int basicBranchingFactor) {
        final boolean isAfter = processingTokenEnd.isAfter(ast);
        afterValues.push(isAfter);
        if (!isAfter) {
            processingTokenEnd.setToken(getLastToken(ast));
            final int expressionValue = basicBranchingFactor + countConditionalOperators(ast);
            pushValue(expressionValue);
        }
    }

    /**
     * Leaves ternary operator (?:) and return tokens.
     */
    private void leaveUnitaryOperator() {
        if (Boolean.FALSE.equals(afterValues.pop())) {
            final Values valuePair = popValue();
            BigInteger basicRangeValue = valuePair.getRangeValue();
            BigInteger expressionValue = valuePair.getExpressionValue();
            if (expressionValue.equals(BigInteger.ZERO)) {
                expressionValue = BigInteger.ONE;
            }
            if (basicRangeValue.equals(BigInteger.ZERO)) {
                basicRangeValue = BigInteger.ONE;
            }
            currentRangeValue = currentRangeValue.add(expressionValue).multiply(basicRangeValue);
        }
    }

    /** Leaves while, do, for, if, ternary (?::), return or switch. */
    private void leaveConditional() {
        final Values valuePair = popValue();
        final BigInteger expressionValue = valuePair.getExpressionValue();
        BigInteger basicRangeValue = valuePair.getRangeValue();
        if (currentRangeValue.equals(BigInteger.ZERO)) {
            currentRangeValue = BigInteger.ONE;
        }
        if (basicRangeValue.equals(BigInteger.ZERO)) {
            basicRangeValue = BigInteger.ONE;
        }
        currentRangeValue = currentRangeValue.add(expressionValue).multiply(basicRangeValue);
    }

    /** Leaves else, default or case group tokens. */
    private void leaveBranch() {
        final Values valuePair = popValue();
        final BigInteger basicRangeValue = valuePair.getRangeValue();
        final BigInteger expressionValue = valuePair.getExpressionValue();
        if (branchVisited && currentRangeValue.equals(BigInteger.ZERO)) {
            currentRangeValue = BigInteger.ONE;
        }
        currentRangeValue = currentRangeValue.subtract(BigInteger.ONE)
                .add(basicRangeValue)
                .add(expressionValue);
    }

    /**
     * Process the end of a method definition.
     *
     * @param ast the token type representing the method definition
     */
    private void leaveMethodDef(DetailAST ast) {
        final BigInteger bigIntegerMax = BigInteger.valueOf(max);
        if (currentRangeValue.compareTo(bigIntegerMax) > 0) {
            log(ast, MSG_KEY, currentRangeValue, bigIntegerMax);
        }
        popValue();
        currentRangeValue = INITIAL_VALUE;
    }

    /** Leaves catch. */
    private void leaveAddingConditional() {
        currentRangeValue = currentRangeValue.add(popValue().getRangeValue().add(BigInteger.ONE));
    }

    /**
     * Pushes the current range value on the range value stack. Pushes this token expression value
     * on the expression value stack.
     *
     * @param expressionValue value of expression calculated for current token.
     */
    private void pushValue(Integer expressionValue) {
        rangeValues.push(currentRangeValue);
        expressionValues.push(expressionValue);
        currentRangeValue = INITIAL_VALUE;
    }

    /**
     * Pops values from both stack of expression values and stack of range values.
     *
     * @return pair of head values from both of the stacks.
     */
    private Values popValue() {
        final int expressionValue = expressionValues.pop();
        return new Values(rangeValues.pop(), BigInteger.valueOf(expressionValue));
    }

    /** Leaves try. */
    private void leaveMultiplyingConditional() {
        currentRangeValue = currentRangeValue.add(BigInteger.ONE)
                .multiply(popValue().getRangeValue().add(BigInteger.ONE));
    }

    /**
     * Calculates number of conditional operators, including inline ternary operator, for a token.
     *
     * @param ast inspected token.
     * @return number of conditional operators.
     * @see <a href="https://docs.oracle.com/javase/specs/jls/se8/html/jls-15.html#jls-15.23">
     *     Java Language Specification, &sect;15.23</a>
     * @see <a href="https://docs.oracle.com/javase/specs/jls/se8/html/jls-15.html#jls-15.24">
     *     Java Language Specification, &sect;15.24</a>
     * @see <a href="https://docs.oracle.com/javase/specs/jls/se8/html/jls-15.html#jls-15.25">
     *     Java Language Specification, &sect;15.25</a>
     */
    private static int countConditionalOperators(DetailAST ast) {
        int number = 0;
        for (DetailAST child = ast.getFirstChild(); child != null;
                child = child.getNextSibling()) {
            final int type = child.getType();
            if (type == TokenTypes.LOR || type == TokenTypes.LAND) {
                number++;
            }
            else if (type == TokenTypes.QUESTION) {
                number += 2;
            }
            number += countConditionalOperators(child);
        }
        return number;
    }

    /**
     * Finds a leaf, which is the most distant from the root.
     *
     * @param ast the root of tree.
     * @return the leaf.
     */
    private static DetailAST getLastToken(DetailAST ast) {
        final DetailAST lastChild = ast.getLastChild();
        final DetailAST result;
        if (lastChild.getFirstChild() == null) {
            result = lastChild;
        }
        else {
            result = getLastToken(lastChild);
        }
        return result;
    }

    /**
     * Counts number of case tokens subject to a case group token.
     *
     * @param ast case group token.
     * @return number of case tokens.
     */
    private static int countCaseTokens(DetailAST ast) {
        int counter = 0;
        for (DetailAST iterator = ast.getFirstChild(); iterator != null;
                iterator = iterator.getNextSibling()) {
            if (iterator.getType() == TokenTypes.LITERAL_CASE) {
                counter++;
            }
        }
        return counter;
    }

    /**
     * Counts number of case constants tokens in a switch labeled rule.
     *
     * @param ast switch rule token.
     * @return number of case constant tokens.
     */
    private static int countCaseConstants(DetailAST ast) {
        int counter = 0;
        final DetailAST literalCase = ast.getFirstChild();

        for (DetailAST node = literalCase.getFirstChild(); node != null;
                    node = node.getNextSibling()) {
            if (TokenUtil.isOfType(node, CASE_LABEL_TOKENS)) {
                counter++;
            }
        }

        return counter;
    }

    /**
     * Coordinates of token end. Used to prevent inline ternary
     * operator from being processed twice.
     */
    private static final class TokenEnd {

        /** End line of token. */
        private int endLineNo;

        /** End column of token. */
        private int endColumnNo;

        /**
         * Sets end coordinates from given token.
         *
         * @param endToken token.
         */
        public void setToken(DetailAST endToken) {
            if (!isAfter(endToken)) {
                endLineNo = endToken.getLineNo();
                endColumnNo = endToken.getColumnNo();
            }
        }

        /** Sets end token coordinates to the start of the file. */
        public void reset() {
            endLineNo = 0;
            endColumnNo = 0;
        }

        /**
         * Checks if saved coordinates located after given token.
         *
         * @param ast given token.
         * @return true, if saved coordinates located after given token.
         */
        public boolean isAfter(DetailAST ast) {
            final int lineNo = ast.getLineNo();
            final int columnNo = ast.getColumnNo();
            return lineNo <= endLineNo
                && (lineNo != endLineNo
                || columnNo <= endColumnNo);
        }

    }

    /**
     * Class that store range value and expression value.
     */
    private static final class Values {

        /** NP value for range. */
        private final BigInteger rangeValue;

        /** NP value for expression. */
        private final BigInteger expressionValue;

        /**
         * Constructor that assigns all of class fields.
         *
         * @param valueOfRange NP value for range
         * @param valueOfExpression NP value for expression
         */
        private Values(BigInteger valueOfRange, BigInteger valueOfExpression) {
            rangeValue = valueOfRange;
            expressionValue = valueOfExpression;
        }

        /**
         * Returns NP value for range.
         *
         * @return NP value for range
         */
        public BigInteger getRangeValue() {
            return rangeValue;
        }

        /**
         * Returns NP value for expression.
         *
         * @return NP value for expression
         */
        public BigInteger getExpressionValue() {
            return expressionValue;
        }

    }

}