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 * <div>
35 * Checks the NPATH complexity against a specified limit.
36 * </div>
37 *
38 * <p>
39 * The NPATH metric computes the number of possible execution paths through a
40 * function(method). It takes into account the nesting of conditional statements
41 * and multipart boolean expressions (A && B, C || D, E ? F :G and
42 * their combinations).
43 * </p>
44 *
45 * <p>
46 * The NPATH metric was designed base on Cyclomatic complexity to avoid problem
47 * of Cyclomatic complexity metric like nesting level within a function(method).
48 * </p>
49 *
50 * <p>
51 * Metric was described at <a href="http://dl.acm.org/citation.cfm?id=42379">
52 * "NPATH: a measure of execution pathcomplexity and its applications"</a>.
53 * If you need detailed description of algorithm, please read that article,
54 * it is well written and have number of examples and details.
55 * </p>
56 *
57 * <p>
58 * Here is some quotes:
59 * </p>
60 * <blockquote>
61 * An NPATH threshold value of 200 has been established for a function.
62 * The value 200 is based on studies done at AT&T Bell Laboratories [1988 year].
63 * </blockquote>
64 * <blockquote>
65 * Some of the most effective methods of reducing the NPATH value include:
66 * <ul>
67 * <li>
68 * distributing functionality;
69 * </li>
70 * <li>
71 * implementing multiple if statements as a switch statement;
72 * </li>
73 * <li>
74 * creating a separate function for logical expressions with a high count of
75 * variables and (&&) and or (||) operators.
76 * </li>
77 * </ul>
78 * </blockquote>
79 * <blockquote>
80 * Although strategies to reduce the NPATH complexity of functions are important,
81 * care must be taken not to distort the logical clarity of the software by
82 * applying a strategy to reduce the complexity of functions. That is, there is
83 * a point of diminishing return beyond which a further attempt at reduction of
84 * complexity distorts the logical clarity of the system structure.
85 * </blockquote>
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 && 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&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
142 public 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, §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, §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, §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 }