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