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