1 ///////////////////////////////////////////////////////////////////////////////////////////////
2 // checkstyle: Checks Java source code and other text files for adherence to a set of rules.
3 // Copyright (C) 2001-2026 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 ({@code 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{@literal &}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 ({@literal &&}) 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 * <div class="wrapper">
86 * <table>
87 * <caption>Examples</caption>
88 * <thead><tr><th>Structure</th><th>Complexity expression</th></tr></thead>
89 * <tr><td>if ([expr]) { [if-range] }</td><td>NP(if-range) + 1 + NP(expr)</td></tr>
90 * <tr><td>if ([expr]) { [if-range] } else { [else-range] }</td>
91 * <td>NP(if-range)+ NP(else-range) + NP(expr)</td></tr>
92 * <tr><td>while ([expr]) { [while-range] }</td><td>NP(while-range) + NP(expr) + 1</td></tr>
93 * <tr><td>do { [do-range] } while ([expr])</td><td>NP(do-range) + NP(expr) + 1</td></tr>
94 * <tr><td>for([expr1]; [expr2]; [expr3]) { [for-range] }</td>
95 * <td>NP(for-range) + NP(expr1)+ NP(expr2) + NP(expr3) + 1</td></tr>
96 * <tr><td>switch ([expr]) { case : [case-range] default: [default-range] }</td>
97 * <td>S(i=1:i=n)NP(case-range[i]) + NP(default-range) + NP(expr)</td></tr>
98 * <tr><td>when[expr]</td><td>NP(expr) + 1</td></tr>
99 * <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 {@literal &&} 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 * </div>
109 *
110 * <p>
111 * <b>Rationale:</b> Nejmeh says that his group had an informal NPATH limit of
112 * 200 on individual routines; functions(methods) that exceeded this value were
113 * candidates for further decomposition - or at least a closer look.
114 * <b>Please do not be fanatic with limit 200</b> - choose number that suites
115 * your project style. Limit 200 is empirical number base on some sources of at
116 * AT{@literal &}T Bell Laboratories of 1988 year.
117 * </p>
118 *
119 * @since 3.4
120 */
121 // -@cs[AbbreviationAsWordInName] Can't change check name
122 @FileStatefulCheck
123 public final class NPathComplexityCheck extends AbstractCheck {
124
125 /**
126 * A key is pointing to the warning message text in "messages.properties"
127 * file.
128 */
129 public static final String MSG_KEY = "npathComplexity";
130
131 /** Tokens that are considered as case labels. */
132 private static final int[] CASE_LABEL_TOKENS = {
133 TokenTypes.EXPR,
134 TokenTypes.PATTERN_DEF,
135 TokenTypes.PATTERN_VARIABLE_DEF,
136 TokenTypes.RECORD_PATTERN_DEF,
137 };
138
139 /** Default allowed complexity. */
140 private static final int DEFAULT_MAX = 200;
141
142 /** The initial current value. */
143 private static final BigInteger INITIAL_VALUE = BigInteger.ZERO;
144
145 /**
146 * Stack of NP values for ranges.
147 */
148 private final Deque<BigInteger> rangeValues = new ArrayDeque<>();
149
150 /** Stack of NP values for expressions. */
151 private final Deque<Integer> expressionValues = new ArrayDeque<>();
152
153 /** Stack of belongs to range values for question operator. */
154 private final Deque<Boolean> afterValues = new ArrayDeque<>();
155
156 /**
157 * Range of the last processed expression. Used for checking that ternary operation
158 * which is a part of expression won't be processed for second time.
159 */
160 private final TokenEnd processingTokenEnd = new TokenEnd();
161
162 /** NP value for current range. */
163 private BigInteger currentRangeValue;
164
165 /** Specify the maximum threshold allowed. */
166 private int max = DEFAULT_MAX;
167
168 /** True, when branch is visited, but not leaved. */
169 private boolean branchVisited;
170
171 /**
172 * Creates a new {@code NPathComplexityCheck} instance.
173 */
174 public NPathComplexityCheck() {
175 // no code by default
176 }
177
178 /**
179 * Setter to specify the maximum threshold allowed.
180 *
181 * @param max the maximum threshold
182 * @since 3.4
183 */
184 public void setMax(int max) {
185 this.max = max;
186 }
187
188 @Override
189 public int[] getDefaultTokens() {
190 return getRequiredTokens();
191 }
192
193 @Override
194 public int[] getAcceptableTokens() {
195 return getRequiredTokens();
196 }
197
198 @Override
199 public int[] getRequiredTokens() {
200 return new int[] {
201 TokenTypes.CTOR_DEF,
202 TokenTypes.METHOD_DEF,
203 TokenTypes.STATIC_INIT,
204 TokenTypes.INSTANCE_INIT,
205 TokenTypes.LITERAL_WHILE,
206 TokenTypes.LITERAL_DO,
207 TokenTypes.LITERAL_FOR,
208 TokenTypes.LITERAL_IF,
209 TokenTypes.LITERAL_ELSE,
210 TokenTypes.LITERAL_SWITCH,
211 TokenTypes.CASE_GROUP,
212 TokenTypes.LITERAL_TRY,
213 TokenTypes.LITERAL_CATCH,
214 TokenTypes.QUESTION,
215 TokenTypes.LITERAL_RETURN,
216 TokenTypes.LITERAL_DEFAULT,
217 TokenTypes.COMPACT_CTOR_DEF,
218 TokenTypes.SWITCH_RULE,
219 TokenTypes.LITERAL_WHEN,
220 };
221 }
222
223 @Override
224 public void beginTree(DetailAST rootAST) {
225 rangeValues.clear();
226 expressionValues.clear();
227 afterValues.clear();
228 processingTokenEnd.reset();
229 currentRangeValue = INITIAL_VALUE;
230 branchVisited = false;
231 }
232
233 @Override
234 public void visitToken(DetailAST ast) {
235 switch (ast.getType()) {
236 case TokenTypes.LITERAL_IF, TokenTypes.LITERAL_SWITCH,
237 TokenTypes.LITERAL_WHILE, TokenTypes.LITERAL_DO,
238 TokenTypes.LITERAL_FOR -> visitConditional(ast, 1);
239
240 case TokenTypes.QUESTION -> visitUnitaryOperator(ast, 2);
241
242 case TokenTypes.LITERAL_RETURN -> visitUnitaryOperator(ast, 0);
243
244 case TokenTypes.LITERAL_WHEN -> visitWhenExpression(ast, 1);
245
246 case TokenTypes.CASE_GROUP -> {
247 final int caseNumber = countCaseTokens(ast);
248 branchVisited = true;
249 pushValue(caseNumber);
250 }
251
252 case TokenTypes.SWITCH_RULE -> {
253 final int caseConstantNumber = countCaseConstants(ast);
254 branchVisited = true;
255 pushValue(caseConstantNumber);
256 }
257
258 case TokenTypes.LITERAL_ELSE -> {
259 branchVisited = true;
260 if (currentRangeValue.equals(BigInteger.ZERO)) {
261 currentRangeValue = BigInteger.ONE;
262 }
263 pushValue(0);
264 }
265
266 case TokenTypes.LITERAL_TRY,
267 TokenTypes.LITERAL_CATCH,
268 TokenTypes.LITERAL_DEFAULT -> pushValue(1);
269
270 case TokenTypes.CTOR_DEF,
271 TokenTypes.METHOD_DEF,
272 TokenTypes.INSTANCE_INIT,
273 TokenTypes.STATIC_INIT,
274 TokenTypes.COMPACT_CTOR_DEF -> pushValue(0);
275
276 default -> {
277 // do nothing
278 }
279 }
280 }
281
282 @Override
283 public void leaveToken(DetailAST ast) {
284 switch (ast.getType()) {
285 case TokenTypes.LITERAL_WHILE,
286 TokenTypes.LITERAL_DO,
287 TokenTypes.LITERAL_FOR,
288 TokenTypes.LITERAL_IF,
289 TokenTypes.LITERAL_SWITCH,
290 TokenTypes.LITERAL_WHEN -> leaveConditional();
291
292 case TokenTypes.LITERAL_TRY -> leaveMultiplyingConditional();
293
294 case TokenTypes.LITERAL_RETURN,
295 TokenTypes.QUESTION -> leaveUnitaryOperator();
296
297 case TokenTypes.LITERAL_CATCH -> leaveAddingConditional();
298
299 case TokenTypes.LITERAL_DEFAULT -> leaveBranch();
300
301 case TokenTypes.LITERAL_ELSE,
302 TokenTypes.CASE_GROUP,
303 TokenTypes.SWITCH_RULE -> {
304 leaveBranch();
305 branchVisited = false;
306 }
307
308 case TokenTypes.CTOR_DEF,
309 TokenTypes.METHOD_DEF,
310 TokenTypes.INSTANCE_INIT,
311 TokenTypes.STATIC_INIT,
312 TokenTypes.COMPACT_CTOR_DEF -> leaveMethodDef(ast);
313
314 default -> {
315 // do nothing
316 }
317 }
318 }
319
320 /**
321 * Visits if, while, do-while, for and switch tokens - all of them have expression in
322 * parentheses which is used for calculation.
323 *
324 * @param ast visited token.
325 * @param basicBranchingFactor default number of branches added.
326 */
327 private void visitConditional(DetailAST ast, int basicBranchingFactor) {
328 int expressionValue = basicBranchingFactor;
329 DetailAST bracketed;
330 for (bracketed = ast.findFirstToken(TokenTypes.LPAREN);
331 bracketed.getType() != TokenTypes.RPAREN;
332 bracketed = bracketed.getNextSibling()) {
333 expressionValue += countConditionalOperators(bracketed);
334 }
335 processingTokenEnd.setToken(bracketed);
336 pushValue(expressionValue);
337 }
338
339 /**
340 * Visits when expression token. There is no guarantee that when expression will be
341 * bracketed, so we don't use visitConditional method.
342 *
343 * @param ast visited token.
344 * @param basicBranchingFactor default number of branches added.
345 */
346 private void visitWhenExpression(DetailAST ast, int basicBranchingFactor) {
347 final int expressionValue = basicBranchingFactor + countConditionalOperators(ast);
348 processingTokenEnd.setToken(getLastToken(ast));
349 pushValue(expressionValue);
350 }
351
352 /**
353 * Visits ternary operator (?:) and return tokens. They differ from those processed by
354 * visitConditional method in that their expression isn't bracketed.
355 *
356 * @param ast visited token.
357 * @param basicBranchingFactor number of branches inherently added by this token.
358 */
359 private void visitUnitaryOperator(DetailAST ast, int basicBranchingFactor) {
360 final boolean isAfter = processingTokenEnd.isAfter(ast);
361 afterValues.push(isAfter);
362 if (!isAfter) {
363 processingTokenEnd.setToken(getLastToken(ast));
364 final int expressionValue = basicBranchingFactor + countConditionalOperators(ast);
365 pushValue(expressionValue);
366 }
367 }
368
369 /**
370 * Leaves ternary operator (?:) and return tokens.
371 */
372 private void leaveUnitaryOperator() {
373 if (Boolean.FALSE.equals(afterValues.pop())) {
374 final Values valuePair = popValue();
375 BigInteger basicRangeValue = valuePair.rangeValue();
376 BigInteger expressionValue = valuePair.expressionValue();
377 if (expressionValue.equals(BigInteger.ZERO)) {
378 expressionValue = BigInteger.ONE;
379 }
380 if (basicRangeValue.equals(BigInteger.ZERO)) {
381 basicRangeValue = BigInteger.ONE;
382 }
383 currentRangeValue = currentRangeValue.add(expressionValue).multiply(basicRangeValue);
384 }
385 }
386
387 /** Leaves while, do, for, if, ternary (?::), return or switch. */
388 private void leaveConditional() {
389 final Values valuePair = popValue();
390 final BigInteger expressionValue = valuePair.expressionValue();
391 BigInteger basicRangeValue = valuePair.rangeValue();
392 if (currentRangeValue.equals(BigInteger.ZERO)) {
393 currentRangeValue = BigInteger.ONE;
394 }
395 if (basicRangeValue.equals(BigInteger.ZERO)) {
396 basicRangeValue = BigInteger.ONE;
397 }
398 currentRangeValue = currentRangeValue.add(expressionValue).multiply(basicRangeValue);
399 }
400
401 /** Leaves else, default or case group tokens. */
402 private void leaveBranch() {
403 final Values valuePair = popValue();
404 final BigInteger basicRangeValue = valuePair.rangeValue();
405 final BigInteger expressionValue = valuePair.expressionValue();
406 if (branchVisited && currentRangeValue.equals(BigInteger.ZERO)) {
407 currentRangeValue = BigInteger.ONE;
408 }
409 currentRangeValue = currentRangeValue.subtract(BigInteger.ONE)
410 .add(basicRangeValue)
411 .add(expressionValue);
412 }
413
414 /**
415 * Process the end of a method definition.
416 *
417 * @param ast the token type representing the method definition
418 */
419 private void leaveMethodDef(DetailAST ast) {
420 final BigInteger bigIntegerMax = BigInteger.valueOf(max);
421 if (currentRangeValue.compareTo(bigIntegerMax) > 0) {
422 log(ast, MSG_KEY, currentRangeValue, bigIntegerMax);
423 }
424 popValue();
425 currentRangeValue = INITIAL_VALUE;
426 }
427
428 /** Leaves catch. */
429 private void leaveAddingConditional() {
430 currentRangeValue = currentRangeValue.add(popValue().rangeValue().add(BigInteger.ONE));
431 }
432
433 /**
434 * Pushes the current range value on the range value stack. Pushes this token expression value
435 * on the expression value stack.
436 *
437 * @param expressionValue value of expression calculated for current token.
438 */
439 private void pushValue(Integer expressionValue) {
440 rangeValues.push(currentRangeValue);
441 expressionValues.push(expressionValue);
442 currentRangeValue = INITIAL_VALUE;
443 }
444
445 /**
446 * Pops values from both stack of expression values and stack of range values.
447 *
448 * @return pair of head values from both of the stacks.
449 */
450 private Values popValue() {
451 final int expressionValue = expressionValues.pop();
452 return new Values(rangeValues.pop(), BigInteger.valueOf(expressionValue));
453 }
454
455 /** Leaves try. */
456 private void leaveMultiplyingConditional() {
457 currentRangeValue = currentRangeValue.add(BigInteger.ONE)
458 .multiply(popValue().rangeValue().add(BigInteger.ONE));
459 }
460
461 /**
462 * Calculates number of conditional operators, including inline ternary operator, for a token.
463 *
464 * @param ast inspected token.
465 * @return number of conditional operators.
466 * @see <a href="https://docs.oracle.com/javase/specs/jls/se8/html/jls-15.html#jls-15.23">
467 * Java Language Specification, §15.23</a>
468 * @see <a href="https://docs.oracle.com/javase/specs/jls/se8/html/jls-15.html#jls-15.24">
469 * Java Language Specification, §15.24</a>
470 * @see <a href="https://docs.oracle.com/javase/specs/jls/se8/html/jls-15.html#jls-15.25">
471 * Java Language Specification, §15.25</a>
472 */
473 private static int countConditionalOperators(DetailAST ast) {
474 int number = 0;
475 for (DetailAST child = ast.getFirstChild(); child != null;
476 child = child.getNextSibling()) {
477 final int type = child.getType();
478 if (type == TokenTypes.LOR || type == TokenTypes.LAND) {
479 number++;
480 }
481 else if (type == TokenTypes.QUESTION) {
482 number += 2;
483 }
484 number += countConditionalOperators(child);
485 }
486 return number;
487 }
488
489 /**
490 * Finds a leaf, which is the most distant from the root.
491 *
492 * @param ast the root of tree.
493 * @return the leaf.
494 */
495 private static DetailAST getLastToken(DetailAST ast) {
496 final DetailAST lastChild = ast.getLastChild();
497 final DetailAST result;
498 if (lastChild.getFirstChild() == null) {
499 result = lastChild;
500 }
501 else {
502 result = getLastToken(lastChild);
503 }
504 return result;
505 }
506
507 /**
508 * Counts number of case tokens subject to a case group token.
509 *
510 * @param ast case group token.
511 * @return number of case tokens.
512 */
513 private static int countCaseTokens(DetailAST ast) {
514 int counter = 0;
515 for (DetailAST iterator = ast.getFirstChild(); iterator != null;
516 iterator = iterator.getNextSibling()) {
517 if (iterator.getType() == TokenTypes.LITERAL_CASE) {
518 counter++;
519 }
520 }
521 return counter;
522 }
523
524 /**
525 * Counts number of case constants tokens in a switch labeled rule.
526 *
527 * @param ast switch rule token.
528 * @return number of case constant tokens.
529 */
530 private static int countCaseConstants(DetailAST ast) {
531 int counter = 0;
532 final DetailAST literalCase = ast.getFirstChild();
533
534 for (DetailAST node = literalCase.getFirstChild(); node != null;
535 node = node.getNextSibling()) {
536 if (TokenUtil.isOfType(node, CASE_LABEL_TOKENS)) {
537 counter++;
538 }
539 }
540
541 return counter;
542 }
543
544 /**
545 * Coordinates of token end. Used to prevent inline ternary
546 * operator from being processed twice.
547 */
548 private static final class TokenEnd {
549
550 /** End line of token. */
551 private int endLineNo;
552
553 /** End column of token. */
554 private int endColumnNo;
555
556 /**
557 * Creates a new {@code TokenEnd} instance.
558 */
559 private TokenEnd() {
560 // no code by default
561 }
562
563 /**
564 * Sets end coordinates from given token.
565 *
566 * @param endToken token.
567 */
568 /* package */ void setToken(DetailAST endToken) {
569 if (!isAfter(endToken)) {
570 endLineNo = endToken.getLineNo();
571 endColumnNo = endToken.getColumnNo();
572 }
573 }
574
575 /** Sets end token coordinates to the start of the file. */
576 /* package */ void reset() {
577 endLineNo = 0;
578 endColumnNo = 0;
579 }
580
581 /**
582 * Checks if saved coordinates located after given token.
583 *
584 * @param ast given token.
585 * @return true, if saved coordinates located after given token.
586 */
587 /* package */ boolean isAfter(DetailAST ast) {
588 final int lineNo = ast.getLineNo();
589 final int columnNo = ast.getColumnNo();
590 return lineNo <= endLineNo
591 && (lineNo != endLineNo
592 || columnNo <= endColumnNo);
593 }
594
595 }
596
597 /**
598 * Class that store range value and expression value.
599 *
600 * @param rangeValue NP value for range.
601 * @param expressionValue NP value for expression.
602 */
603 private record Values(BigInteger rangeValue, BigInteger expressionValue) {
604 }
605
606 }