View Javadoc
1   ///////////////////////////////////////////////////////////////////////////////////////////////
2   // checkstyle: Checks Java source code and other text files for adherence to a set of rules.
3   // Copyright (C) 2001-2024 the original author or authors.
4   //
5   // This library is free software; you can redistribute it and/or
6   // modify it under the terms of the GNU Lesser General Public
7   // License as published by the Free Software Foundation; either
8   // version 2.1 of the License, or (at your option) any later version.
9   //
10  // This library is distributed in the hope that it will be useful,
11  // but WITHOUT ANY WARRANTY; without even the implied warranty of
12  // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13  // Lesser General Public License for more details.
14  //
15  // You should have received a copy of the GNU Lesser General Public
16  // License along with this library; if not, write to the Free Software
17  // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
18  ///////////////////////////////////////////////////////////////////////////////////////////////
19  
20  package com.puppycrawl.tools.checkstyle.checks.metrics;
21  
22  import java.math.BigInteger;
23  import java.util.ArrayDeque;
24  import java.util.Deque;
25  import java.util.concurrent.atomic.AtomicInteger;
26  
27  import com.puppycrawl.tools.checkstyle.FileStatefulCheck;
28  import com.puppycrawl.tools.checkstyle.api.AbstractCheck;
29  import com.puppycrawl.tools.checkstyle.api.DetailAST;
30  import com.puppycrawl.tools.checkstyle.api.TokenTypes;
31  import com.puppycrawl.tools.checkstyle.utils.TokenUtil;
32  
33  /**
34   * <p>
35   * Checks the NPATH complexity against a specified limit.
36   * </p>
37   * <p>
38   * The NPATH metric computes the number of possible execution paths through a
39   * function(method). It takes into account the nesting of conditional statements
40   * and multipart boolean expressions (A &amp;&amp; B, C || D, E ? F :G and
41   * their combinations).
42   * </p>
43   * <p>
44   * The NPATH metric was designed base on Cyclomatic complexity to avoid problem
45   * of Cyclomatic complexity metric like nesting level within a function(method).
46   * </p>
47   * <p>
48   * Metric was described at <a href="http://dl.acm.org/citation.cfm?id=42379">
49   * "NPATH: a measure of execution pathcomplexity and its applications"</a>.
50   * If you need detailed description of algorithm, please read that article,
51   * it is well written and have number of examples and details.
52   * </p>
53   * <p>
54   * Here is some quotes:
55   * </p>
56   * <blockquote>
57   * An NPATH threshold value of 200 has been established for a function.
58   * The value 200 is based on studies done at AT&amp;T Bell Laboratories [1988 year].
59   * </blockquote>
60   * <blockquote>
61   * Some of the most effective methods of reducing the NPATH value include:
62   * <ul>
63   * <li>
64   * distributing functionality;
65   * </li>
66   * <li>
67   * implementing multiple if statements as a switch statement;
68   * </li>
69   * <li>
70   * creating a separate function for logical expressions with a high count of
71   * variables and (&amp;&amp;) and or (||) operators.
72   * </li>
73   * </ul>
74   * </blockquote>
75   * <blockquote>
76   * Although strategies to reduce the NPATH complexity of functions are important,
77   * care must be taken not to distort the logical clarity of the software by
78   * applying a strategy to reduce the complexity of functions. That is, there is
79   * a point of diminishing return beyond which a further attempt at reduction of
80   * complexity distorts the logical clarity of the system structure.
81   * </blockquote>
82   * <table>
83   * <caption>Examples</caption>
84   * <thead><tr><th>Structure</th><th>Complexity expression</th></tr></thead>
85   * <tr><td>if ([expr]) { [if-range] }</td><td>NP(if-range) + 1 + NP(expr)</td></tr>
86   * <tr><td>if ([expr]) { [if-range] } else { [else-range] }</td>
87   * <td>NP(if-range)+ NP(else-range) + NP(expr)</td></tr>
88   * <tr><td>while ([expr]) { [while-range] }</td><td>NP(while-range) + NP(expr) + 1</td></tr>
89   * <tr><td>do { [do-range] } while ([expr])</td><td>NP(do-range) + NP(expr) + 1</td></tr>
90   * <tr><td>for([expr1]; [expr2]; [expr3]) { [for-range] }</td>
91   * <td>NP(for-range) + NP(expr1)+ NP(expr2) + NP(expr3) + 1</td></tr>
92   * <tr><td>switch ([expr]) { case : [case-range] default: [default-range] }</td>
93   * <td>S(i=1:i=n)NP(case-range[i]) + NP(default-range) + NP(expr)</td></tr>
94   * <tr><td>[expr1] ? [expr2] : [expr3]</td><td>NP(expr1) + NP(expr2) + NP(expr3) + 2</td></tr>
95   * <tr><td>goto label</td><td>1</td></tr><tr><td>break</td><td>1</td></tr>
96   * <tr><td>Expressions</td>
97   * <td>Number of &amp;&amp; and || operators in expression. No operators - 0</td></tr>
98   * <tr><td>continue</td><td>1</td></tr><tr><td>return</td><td>1</td></tr>
99   * <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
134 public 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 }