001///////////////////////////////////////////////////////////////////////////////////////////////
002// checkstyle: Checks Java source code and other text files for adherence to a set of rules.
003// Copyright (C) 2001-2024 the original author or authors.
004//
005// This library is free software; you can redistribute it and/or
006// modify it under the terms of the GNU Lesser General Public
007// License as published by the Free Software Foundation; either
008// version 2.1 of the License, or (at your option) any later version.
009//
010// This library is distributed in the hope that it will be useful,
011// but WITHOUT ANY WARRANTY; without even the implied warranty of
012// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
013// Lesser General Public License for more details.
014//
015// You should have received a copy of the GNU Lesser General Public
016// License along with this library; if not, write to the Free Software
017// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
018///////////////////////////////////////////////////////////////////////////////////////////////
019
020package com.puppycrawl.tools.checkstyle.checks.metrics;
021
022import java.math.BigInteger;
023import java.util.ArrayDeque;
024import java.util.Deque;
025import java.util.concurrent.atomic.AtomicInteger;
026
027import com.puppycrawl.tools.checkstyle.FileStatefulCheck;
028import com.puppycrawl.tools.checkstyle.api.AbstractCheck;
029import com.puppycrawl.tools.checkstyle.api.DetailAST;
030import com.puppycrawl.tools.checkstyle.api.TokenTypes;
031import com.puppycrawl.tools.checkstyle.utils.TokenUtil;
032
033/**
034 * <div>
035 * Checks the NPATH complexity against a specified limit.
036 * </div>
037 *
038 * <p>
039 * The NPATH metric computes the number of possible execution paths through a
040 * function(method). It takes into account the nesting of conditional statements
041 * and multipart boolean expressions (A &amp;&amp; B, C || D, E ? F :G and
042 * their combinations).
043 * </p>
044 *
045 * <p>
046 * The NPATH metric was designed base on Cyclomatic complexity to avoid problem
047 * of Cyclomatic complexity metric like nesting level within a function(method).
048 * </p>
049 *
050 * <p>
051 * Metric was described at <a href="http://dl.acm.org/citation.cfm?id=42379">
052 * "NPATH: a measure of execution pathcomplexity and its applications"</a>.
053 * If you need detailed description of algorithm, please read that article,
054 * it is well written and have number of examples and details.
055 * </p>
056 *
057 * <p>
058 * Here is some quotes:
059 * </p>
060 * <blockquote>
061 * An NPATH threshold value of 200 has been established for a function.
062 * The value 200 is based on studies done at AT&amp;T Bell Laboratories [1988 year].
063 * </blockquote>
064 * <blockquote>
065 * Some of the most effective methods of reducing the NPATH value include:
066 * <ul>
067 * <li>
068 * distributing functionality;
069 * </li>
070 * <li>
071 * implementing multiple if statements as a switch statement;
072 * </li>
073 * <li>
074 * creating a separate function for logical expressions with a high count of
075 * variables and (&amp;&amp;) and or (||) operators.
076 * </li>
077 * </ul>
078 * </blockquote>
079 * <blockquote>
080 * Although strategies to reduce the NPATH complexity of functions are important,
081 * care must be taken not to distort the logical clarity of the software by
082 * applying a strategy to reduce the complexity of functions. That is, there is
083 * a point of diminishing return beyond which a further attempt at reduction of
084 * complexity distorts the logical clarity of the system structure.
085 * </blockquote>
086 * <table>
087 * <caption>Examples</caption>
088 * <thead><tr><th>Structure</th><th>Complexity expression</th></tr></thead>
089 * <tr><td>if ([expr]) { [if-range] }</td><td>NP(if-range) + 1 + NP(expr)</td></tr>
090 * <tr><td>if ([expr]) { [if-range] } else { [else-range] }</td>
091 * <td>NP(if-range)+ NP(else-range) + NP(expr)</td></tr>
092 * <tr><td>while ([expr]) { [while-range] }</td><td>NP(while-range) + NP(expr) + 1</td></tr>
093 * <tr><td>do { [do-range] } while ([expr])</td><td>NP(do-range) + NP(expr) + 1</td></tr>
094 * <tr><td>for([expr1]; [expr2]; [expr3]) { [for-range] }</td>
095 * <td>NP(for-range) + NP(expr1)+ NP(expr2) + NP(expr3) + 1</td></tr>
096 * <tr><td>switch ([expr]) { case : [case-range] default: [default-range] }</td>
097 * <td>S(i=1:i=n)NP(case-range[i]) + NP(default-range) + NP(expr)</td></tr>
098 * <tr><td>when[expr]</td><td>NP(expr) + 1</td></tr>
099 * <tr><td>[expr1] ? [expr2] : [expr3]</td><td>NP(expr1) + NP(expr2) + NP(expr3) + 2</td></tr>
100 * <tr><td>goto label</td><td>1</td></tr><tr><td>break</td><td>1</td></tr>
101 * <tr><td>Expressions</td>
102 * <td>Number of &amp;&amp; and || operators in expression. No operators - 0</td></tr>
103 * <tr><td>continue</td><td>1</td></tr><tr><td>return</td><td>1</td></tr>
104 * <tr><td>Statement (even sequential statements)</td><td>1</td></tr>
105 * <tr><td>Empty block {}</td><td>1</td></tr><tr><td>Function call</td><td>1</td>
106 * </tr><tr><td>Function(Method) declaration or Block</td><td>P(i=1:i=N)NP(Statement[i])</td></tr>
107 * </table>
108 *
109 * <p>
110 * <b>Rationale:</b> Nejmeh says that his group had an informal NPATH limit of
111 * 200 on individual routines; functions(methods) that exceeded this value were
112 * candidates for further decomposition - or at least a closer look.
113 * <b>Please do not be fanatic with limit 200</b> - choose number that suites
114 * your project style. Limit 200 is empirical number base on some sources of at
115 * AT&amp;T Bell Laboratories of 1988 year.
116 * </p>
117 * <ul>
118 * <li>
119 * Property {@code max} - Specify the maximum threshold allowed.
120 * Type is {@code int}.
121 * Default value is {@code 200}.
122 * </li>
123 * </ul>
124 *
125 * <p>
126 * Parent is {@code com.puppycrawl.tools.checkstyle.TreeWalker}
127 * </p>
128 *
129 * <p>
130 * Violation Message Keys:
131 * </p>
132 * <ul>
133 * <li>
134 * {@code npathComplexity}
135 * </li>
136 * </ul>
137 *
138 * @since 3.4
139 */
140// -@cs[AbbreviationAsWordInName] Can't change check name
141@FileStatefulCheck
142public final class NPathComplexityCheck extends AbstractCheck {
143
144    /**
145     * A key is pointing to the warning message text in "messages.properties"
146     * file.
147     */
148    public static final String MSG_KEY = "npathComplexity";
149
150    /** Tokens that are considered as case labels. */
151    private static final int[] CASE_LABEL_TOKENS = {
152        TokenTypes.EXPR,
153        TokenTypes.PATTERN_DEF,
154        TokenTypes.PATTERN_VARIABLE_DEF,
155        TokenTypes.RECORD_PATTERN_DEF,
156    };
157
158    /** Default allowed complexity. */
159    private static final int DEFAULT_MAX = 200;
160
161    /** The initial current value. */
162    private static final BigInteger INITIAL_VALUE = BigInteger.ZERO;
163
164    /**
165     * Stack of NP values for ranges.
166     */
167    private final Deque<BigInteger> rangeValues = new ArrayDeque<>();
168
169    /** Stack of NP values for expressions. */
170    private final Deque<Integer> expressionValues = new ArrayDeque<>();
171
172    /** Stack of belongs to range values for question operator. */
173    private final Deque<Boolean> afterValues = new ArrayDeque<>();
174
175    /**
176     * Range of the last processed expression. Used for checking that ternary operation
177     * which is a part of expression won't be processed for second time.
178     */
179    private final TokenEnd processingTokenEnd = new TokenEnd();
180
181    /** NP value for current range. */
182    private BigInteger currentRangeValue;
183
184    /** Specify the maximum threshold allowed. */
185    private int max = DEFAULT_MAX;
186
187    /** True, when branch is visited, but not leaved. */
188    private boolean branchVisited;
189
190    /**
191     * Setter to specify the maximum threshold allowed.
192     *
193     * @param max the maximum threshold
194     * @since 3.4
195     */
196    public void setMax(int max) {
197        this.max = max;
198    }
199
200    @Override
201    public int[] getDefaultTokens() {
202        return getRequiredTokens();
203    }
204
205    @Override
206    public int[] getAcceptableTokens() {
207        return getRequiredTokens();
208    }
209
210    @Override
211    public int[] getRequiredTokens() {
212        return new int[] {
213            TokenTypes.CTOR_DEF,
214            TokenTypes.METHOD_DEF,
215            TokenTypes.STATIC_INIT,
216            TokenTypes.INSTANCE_INIT,
217            TokenTypes.LITERAL_WHILE,
218            TokenTypes.LITERAL_DO,
219            TokenTypes.LITERAL_FOR,
220            TokenTypes.LITERAL_IF,
221            TokenTypes.LITERAL_ELSE,
222            TokenTypes.LITERAL_SWITCH,
223            TokenTypes.CASE_GROUP,
224            TokenTypes.LITERAL_TRY,
225            TokenTypes.LITERAL_CATCH,
226            TokenTypes.QUESTION,
227            TokenTypes.LITERAL_RETURN,
228            TokenTypes.LITERAL_DEFAULT,
229            TokenTypes.COMPACT_CTOR_DEF,
230            TokenTypes.SWITCH_RULE,
231            TokenTypes.LITERAL_WHEN,
232        };
233    }
234
235    @Override
236    public void beginTree(DetailAST rootAST) {
237        rangeValues.clear();
238        expressionValues.clear();
239        afterValues.clear();
240        processingTokenEnd.reset();
241        currentRangeValue = INITIAL_VALUE;
242        branchVisited = false;
243    }
244
245    @Override
246    public void visitToken(DetailAST ast) {
247        switch (ast.getType()) {
248            case TokenTypes.LITERAL_IF:
249            case TokenTypes.LITERAL_SWITCH:
250            case TokenTypes.LITERAL_WHILE:
251            case TokenTypes.LITERAL_DO:
252            case TokenTypes.LITERAL_FOR:
253                visitConditional(ast, 1);
254                break;
255            case TokenTypes.QUESTION:
256                visitUnitaryOperator(ast, 2);
257                break;
258            case TokenTypes.LITERAL_RETURN:
259                visitUnitaryOperator(ast, 0);
260                break;
261            case TokenTypes.LITERAL_WHEN:
262                visitWhenExpression(ast, 1);
263                break;
264            case TokenTypes.CASE_GROUP:
265                final int caseNumber = countCaseTokens(ast);
266                branchVisited = true;
267                pushValue(caseNumber);
268                break;
269            case TokenTypes.SWITCH_RULE:
270                final int caseConstantNumber = countCaseConstants(ast);
271                branchVisited = true;
272                pushValue(caseConstantNumber);
273                break;
274            case TokenTypes.LITERAL_ELSE:
275                branchVisited = true;
276                if (currentRangeValue.equals(BigInteger.ZERO)) {
277                    currentRangeValue = BigInteger.ONE;
278                }
279                pushValue(0);
280                break;
281            case TokenTypes.LITERAL_TRY:
282            case TokenTypes.LITERAL_CATCH:
283            case TokenTypes.LITERAL_DEFAULT:
284                pushValue(1);
285                break;
286            case TokenTypes.CTOR_DEF:
287            case TokenTypes.METHOD_DEF:
288            case TokenTypes.INSTANCE_INIT:
289            case TokenTypes.STATIC_INIT:
290            case TokenTypes.COMPACT_CTOR_DEF:
291                pushValue(0);
292                break;
293            default:
294                break;
295        }
296    }
297
298    @Override
299    public void leaveToken(DetailAST ast) {
300        switch (ast.getType()) {
301            case TokenTypes.LITERAL_WHILE:
302            case TokenTypes.LITERAL_DO:
303            case TokenTypes.LITERAL_FOR:
304            case TokenTypes.LITERAL_IF:
305            case TokenTypes.LITERAL_SWITCH:
306            case TokenTypes.LITERAL_WHEN:
307                leaveConditional();
308                break;
309            case TokenTypes.LITERAL_TRY:
310                leaveMultiplyingConditional();
311                break;
312            case TokenTypes.LITERAL_RETURN:
313            case TokenTypes.QUESTION:
314                leaveUnitaryOperator();
315                break;
316            case TokenTypes.LITERAL_CATCH:
317                leaveAddingConditional();
318                break;
319            case TokenTypes.LITERAL_DEFAULT:
320                leaveBranch();
321                break;
322            case TokenTypes.LITERAL_ELSE:
323            case TokenTypes.CASE_GROUP:
324            case TokenTypes.SWITCH_RULE:
325                leaveBranch();
326                branchVisited = false;
327                break;
328            case TokenTypes.CTOR_DEF:
329            case TokenTypes.METHOD_DEF:
330            case TokenTypes.INSTANCE_INIT:
331            case TokenTypes.STATIC_INIT:
332            case TokenTypes.COMPACT_CTOR_DEF:
333                leaveMethodDef(ast);
334                break;
335            default:
336                break;
337        }
338    }
339
340    /**
341     * Visits if, while, do-while, for and switch tokens - all of them have expression in
342     * parentheses which is used for calculation.
343     *
344     * @param ast visited token.
345     * @param basicBranchingFactor default number of branches added.
346     */
347    private void visitConditional(DetailAST ast, int basicBranchingFactor) {
348        int expressionValue = basicBranchingFactor;
349        DetailAST bracketed;
350        for (bracketed = ast.findFirstToken(TokenTypes.LPAREN);
351                bracketed.getType() != TokenTypes.RPAREN;
352                bracketed = bracketed.getNextSibling()) {
353            expressionValue += countConditionalOperators(bracketed);
354        }
355        processingTokenEnd.setToken(bracketed);
356        pushValue(expressionValue);
357    }
358
359    /**
360     * Visits when expression token. There is no guarantee that when expression will be
361     * bracketed, so we don't use visitConditional method.
362     *
363     * @param ast visited token.
364     * @param basicBranchingFactor default number of branches added.
365     */
366    private void visitWhenExpression(DetailAST ast, int basicBranchingFactor) {
367        final int expressionValue = basicBranchingFactor + countConditionalOperators(ast);
368        processingTokenEnd.setToken(getLastToken(ast));
369        pushValue(expressionValue);
370    }
371
372    /**
373     * Visits ternary operator (?:) and return tokens. They differ from those processed by
374     * visitConditional method in that their expression isn't bracketed.
375     *
376     * @param ast visited token.
377     * @param basicBranchingFactor number of branches inherently added by this token.
378     */
379    private void visitUnitaryOperator(DetailAST ast, int basicBranchingFactor) {
380        final boolean isAfter = processingTokenEnd.isAfter(ast);
381        afterValues.push(isAfter);
382        if (!isAfter) {
383            processingTokenEnd.setToken(getLastToken(ast));
384            final int expressionValue = basicBranchingFactor + countConditionalOperators(ast);
385            pushValue(expressionValue);
386        }
387    }
388
389    /**
390     * Leaves ternary operator (?:) and return tokens.
391     */
392    private void leaveUnitaryOperator() {
393        if (Boolean.FALSE.equals(afterValues.pop())) {
394            final Values valuePair = popValue();
395            BigInteger basicRangeValue = valuePair.getRangeValue();
396            BigInteger expressionValue = valuePair.getExpressionValue();
397            if (expressionValue.equals(BigInteger.ZERO)) {
398                expressionValue = BigInteger.ONE;
399            }
400            if (basicRangeValue.equals(BigInteger.ZERO)) {
401                basicRangeValue = BigInteger.ONE;
402            }
403            currentRangeValue = currentRangeValue.add(expressionValue).multiply(basicRangeValue);
404        }
405    }
406
407    /** Leaves while, do, for, if, ternary (?::), return or switch. */
408    private void leaveConditional() {
409        final Values valuePair = popValue();
410        final BigInteger expressionValue = valuePair.getExpressionValue();
411        BigInteger basicRangeValue = valuePair.getRangeValue();
412        if (currentRangeValue.equals(BigInteger.ZERO)) {
413            currentRangeValue = BigInteger.ONE;
414        }
415        if (basicRangeValue.equals(BigInteger.ZERO)) {
416            basicRangeValue = BigInteger.ONE;
417        }
418        currentRangeValue = currentRangeValue.add(expressionValue).multiply(basicRangeValue);
419    }
420
421    /** Leaves else, default or case group tokens. */
422    private void leaveBranch() {
423        final Values valuePair = popValue();
424        final BigInteger basicRangeValue = valuePair.getRangeValue();
425        final BigInteger expressionValue = valuePair.getExpressionValue();
426        if (branchVisited && currentRangeValue.equals(BigInteger.ZERO)) {
427            currentRangeValue = BigInteger.ONE;
428        }
429        currentRangeValue = currentRangeValue.subtract(BigInteger.ONE)
430                .add(basicRangeValue)
431                .add(expressionValue);
432    }
433
434    /**
435     * Process the end of a method definition.
436     *
437     * @param ast the token type representing the method definition
438     */
439    private void leaveMethodDef(DetailAST ast) {
440        final BigInteger bigIntegerMax = BigInteger.valueOf(max);
441        if (currentRangeValue.compareTo(bigIntegerMax) > 0) {
442            log(ast, MSG_KEY, currentRangeValue, bigIntegerMax);
443        }
444        popValue();
445        currentRangeValue = INITIAL_VALUE;
446    }
447
448    /** Leaves catch. */
449    private void leaveAddingConditional() {
450        currentRangeValue = currentRangeValue.add(popValue().getRangeValue().add(BigInteger.ONE));
451    }
452
453    /**
454     * Pushes the current range value on the range value stack. Pushes this token expression value
455     * on the expression value stack.
456     *
457     * @param expressionValue value of expression calculated for current token.
458     */
459    private void pushValue(Integer expressionValue) {
460        rangeValues.push(currentRangeValue);
461        expressionValues.push(expressionValue);
462        currentRangeValue = INITIAL_VALUE;
463    }
464
465    /**
466     * Pops values from both stack of expression values and stack of range values.
467     *
468     * @return pair of head values from both of the stacks.
469     */
470    private Values popValue() {
471        final int expressionValue = expressionValues.pop();
472        return new Values(rangeValues.pop(), BigInteger.valueOf(expressionValue));
473    }
474
475    /** Leaves try. */
476    private void leaveMultiplyingConditional() {
477        currentRangeValue = currentRangeValue.add(BigInteger.ONE)
478                .multiply(popValue().getRangeValue().add(BigInteger.ONE));
479    }
480
481    /**
482     * Calculates number of conditional operators, including inline ternary operator, for a token.
483     *
484     * @param ast inspected token.
485     * @return number of conditional operators.
486     * @see <a href="https://docs.oracle.com/javase/specs/jls/se8/html/jls-15.html#jls-15.23">
487     * Java Language Specification, &sect;15.23</a>
488     * @see <a href="https://docs.oracle.com/javase/specs/jls/se8/html/jls-15.html#jls-15.24">
489     * Java Language Specification, &sect;15.24</a>
490     * @see <a href="https://docs.oracle.com/javase/specs/jls/se8/html/jls-15.html#jls-15.25">
491     * Java Language Specification, &sect;15.25</a>
492     */
493    private static int countConditionalOperators(DetailAST ast) {
494        int number = 0;
495        for (DetailAST child = ast.getFirstChild(); child != null;
496                child = child.getNextSibling()) {
497            final int type = child.getType();
498            if (type == TokenTypes.LOR || type == TokenTypes.LAND) {
499                number++;
500            }
501            else if (type == TokenTypes.QUESTION) {
502                number += 2;
503            }
504            number += countConditionalOperators(child);
505        }
506        return number;
507    }
508
509    /**
510     * Finds a leaf, which is the most distant from the root.
511     *
512     * @param ast the root of tree.
513     * @return the leaf.
514     */
515    private static DetailAST getLastToken(DetailAST ast) {
516        final DetailAST lastChild = ast.getLastChild();
517        final DetailAST result;
518        if (lastChild.getFirstChild() == null) {
519            result = lastChild;
520        }
521        else {
522            result = getLastToken(lastChild);
523        }
524        return result;
525    }
526
527    /**
528     * Counts number of case tokens subject to a case group token.
529     *
530     * @param ast case group token.
531     * @return number of case tokens.
532     */
533    private static int countCaseTokens(DetailAST ast) {
534        int counter = 0;
535        for (DetailAST iterator = ast.getFirstChild(); iterator != null;
536                iterator = iterator.getNextSibling()) {
537            if (iterator.getType() == TokenTypes.LITERAL_CASE) {
538                counter++;
539            }
540        }
541        return counter;
542    }
543
544    /**
545     * Counts number of case constants tokens in a switch labeled rule.
546     *
547     * @param ast switch rule token.
548     * @return number of case constant tokens.
549     */
550    private static int countCaseConstants(DetailAST ast) {
551        final AtomicInteger counter = new AtomicInteger();
552        final DetailAST literalCase = ast.getFirstChild();
553
554        for (DetailAST node = literalCase.getFirstChild(); node != null;
555                    node = node.getNextSibling()) {
556            if (TokenUtil.isOfType(node, CASE_LABEL_TOKENS)) {
557                counter.getAndIncrement();
558            }
559        }
560
561        return counter.get();
562    }
563
564    /**
565     * Coordinates of token end. Used to prevent inline ternary
566     * operator from being processed twice.
567     */
568    private static final class TokenEnd {
569
570        /** End line of token. */
571        private int endLineNo;
572
573        /** End column of token. */
574        private int endColumnNo;
575
576        /**
577         * Sets end coordinates from given token.
578         *
579         * @param endToken token.
580         */
581        public void setToken(DetailAST endToken) {
582            if (!isAfter(endToken)) {
583                endLineNo = endToken.getLineNo();
584                endColumnNo = endToken.getColumnNo();
585            }
586        }
587
588        /** Sets end token coordinates to the start of the file. */
589        public void reset() {
590            endLineNo = 0;
591            endColumnNo = 0;
592        }
593
594        /**
595         * Checks if saved coordinates located after given token.
596         *
597         * @param ast given token.
598         * @return true, if saved coordinates located after given token.
599         */
600        public boolean isAfter(DetailAST ast) {
601            final int lineNo = ast.getLineNo();
602            final int columnNo = ast.getColumnNo();
603            return lineNo <= endLineNo
604                && (lineNo != endLineNo
605                || columnNo <= endColumnNo);
606        }
607
608    }
609
610    /**
611     * Class that store range value and expression value.
612     */
613    private static final class Values {
614
615        /** NP value for range. */
616        private final BigInteger rangeValue;
617
618        /** NP value for expression. */
619        private final BigInteger expressionValue;
620
621        /**
622         * Constructor that assigns all of class fields.
623         *
624         * @param valueOfRange NP value for range
625         * @param valueOfExpression NP value for expression
626         */
627        private Values(BigInteger valueOfRange, BigInteger valueOfExpression) {
628            rangeValue = valueOfRange;
629            expressionValue = valueOfExpression;
630        }
631
632        /**
633         * Returns NP value for range.
634         *
635         * @return NP value for range
636         */
637        public BigInteger getRangeValue() {
638            return rangeValue;
639        }
640
641        /**
642         * Returns NP value for expression.
643         *
644         * @return NP value for expression
645         */
646        public BigInteger getExpressionValue() {
647            return expressionValue;
648        }
649
650    }
651
652}