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