001/////////////////////////////////////////////////////////////////////////////////////////////// 002// checkstyle: Checks Java source code and other text files for adherence to a set of rules. 003// Copyright (C) 2001-2025 the original author or authors. 004// 005// This library is free software; you can redistribute it and/or 006// modify it under the terms of the GNU Lesser General Public 007// License as published by the Free Software Foundation; either 008// version 2.1 of the License, or (at your option) any later version. 009// 010// This library is distributed in the hope that it will be useful, 011// but WITHOUT ANY WARRANTY; without even the implied warranty of 012// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 013// Lesser General Public License for more details. 014// 015// You should have received a copy of the GNU Lesser General Public 016// License along with this library; if not, write to the Free Software 017// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 018/////////////////////////////////////////////////////////////////////////////////////////////// 019 020package com.puppycrawl.tools.checkstyle.checks.metrics; 021 022import java.math.BigInteger; 023import java.util.ArrayDeque; 024import java.util.Deque; 025 026import com.puppycrawl.tools.checkstyle.FileStatefulCheck; 027import com.puppycrawl.tools.checkstyle.api.AbstractCheck; 028import com.puppycrawl.tools.checkstyle.api.DetailAST; 029import com.puppycrawl.tools.checkstyle.api.TokenTypes; 030import com.puppycrawl.tools.checkstyle.utils.TokenUtil; 031 032/** 033 * <div> 034 * Checks the NPATH complexity against a specified limit. 035 * </div> 036 * 037 * <p> 038 * The NPATH metric computes the number of possible execution paths through a 039 * function(method). It takes into account the nesting of conditional statements 040 * and multipart boolean expressions (A && B, C || D, E ? F :G and 041 * their combinations). 042 * </p> 043 * 044 * <p> 045 * The NPATH metric was designed base on Cyclomatic complexity to avoid problem 046 * of Cyclomatic complexity metric like nesting level within a function(method). 047 * </p> 048 * 049 * <p> 050 * Metric was described at <a href="http://dl.acm.org/citation.cfm?id=42379"> 051 * "NPATH: a measure of execution pathcomplexity and its applications"</a>. 052 * If you need detailed description of algorithm, please read that article, 053 * it is well written and have number of examples and details. 054 * </p> 055 * 056 * <p> 057 * Here is some quotes: 058 * </p> 059 * <blockquote> 060 * An NPATH threshold value of 200 has been established for a function. 061 * The value 200 is based on studies done at AT&T Bell Laboratories [1988 year]. 062 * </blockquote> 063 * <blockquote> 064 * Some of the most effective methods of reducing the NPATH value include: 065 * <ul> 066 * <li> 067 * distributing functionality; 068 * </li> 069 * <li> 070 * implementing multiple if statements as a switch statement; 071 * </li> 072 * <li> 073 * creating a separate function for logical expressions with a high count of 074 * variables and (&&) and or (||) operators. 075 * </li> 076 * </ul> 077 * </blockquote> 078 * <blockquote> 079 * Although strategies to reduce the NPATH complexity of functions are important, 080 * care must be taken not to distort the logical clarity of the software by 081 * applying a strategy to reduce the complexity of functions. That is, there is 082 * a point of diminishing return beyond which a further attempt at reduction of 083 * complexity distorts the logical clarity of the system structure. 084 * </blockquote> 085 * <div class="wrapper"> 086 * <table> 087 * <caption>Examples</caption> 088 * <thead><tr><th>Structure</th><th>Complexity expression</th></tr></thead> 089 * <tr><td>if ([expr]) { [if-range] }</td><td>NP(if-range) + 1 + NP(expr)</td></tr> 090 * <tr><td>if ([expr]) { [if-range] } else { [else-range] }</td> 091 * <td>NP(if-range)+ NP(else-range) + NP(expr)</td></tr> 092 * <tr><td>while ([expr]) { [while-range] }</td><td>NP(while-range) + NP(expr) + 1</td></tr> 093 * <tr><td>do { [do-range] } while ([expr])</td><td>NP(do-range) + NP(expr) + 1</td></tr> 094 * <tr><td>for([expr1]; [expr2]; [expr3]) { [for-range] }</td> 095 * <td>NP(for-range) + NP(expr1)+ NP(expr2) + NP(expr3) + 1</td></tr> 096 * <tr><td>switch ([expr]) { case : [case-range] default: [default-range] }</td> 097 * <td>S(i=1:i=n)NP(case-range[i]) + NP(default-range) + NP(expr)</td></tr> 098 * <tr><td>when[expr]</td><td>NP(expr) + 1</td></tr> 099 * <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 * </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&T Bell Laboratories of 1988 year. 117 * </p> 118 * <ul> 119 * <li> 120 * Property {@code max} - Specify the maximum threshold allowed. 121 * Type is {@code int}. 122 * Default value is {@code 200}. 123 * </li> 124 * </ul> 125 * 126 * <p> 127 * Parent is {@code com.puppycrawl.tools.checkstyle.TreeWalker} 128 * </p> 129 * 130 * <p> 131 * Violation Message Keys: 132 * </p> 133 * <ul> 134 * <li> 135 * {@code npathComplexity} 136 * </li> 137 * </ul> 138 * 139 * @since 3.4 140 */ 141// -@cs[AbbreviationAsWordInName] Can't change check name 142@FileStatefulCheck 143public final class NPathComplexityCheck extends AbstractCheck { 144 145 /** 146 * A key is pointing to the warning message text in "messages.properties" 147 * file. 148 */ 149 public static final String MSG_KEY = "npathComplexity"; 150 151 /** Tokens that are considered as case labels. */ 152 private static final int[] CASE_LABEL_TOKENS = { 153 TokenTypes.EXPR, 154 TokenTypes.PATTERN_DEF, 155 TokenTypes.PATTERN_VARIABLE_DEF, 156 TokenTypes.RECORD_PATTERN_DEF, 157 }; 158 159 /** Default allowed complexity. */ 160 private static final int DEFAULT_MAX = 200; 161 162 /** The initial current value. */ 163 private static final BigInteger INITIAL_VALUE = BigInteger.ZERO; 164 165 /** 166 * Stack of NP values for ranges. 167 */ 168 private final Deque<BigInteger> rangeValues = new ArrayDeque<>(); 169 170 /** Stack of NP values for expressions. */ 171 private final Deque<Integer> expressionValues = new ArrayDeque<>(); 172 173 /** Stack of belongs to range values for question operator. */ 174 private final Deque<Boolean> afterValues = new ArrayDeque<>(); 175 176 /** 177 * Range of the last processed expression. Used for checking that ternary operation 178 * which is a part of expression won't be processed for second time. 179 */ 180 private final TokenEnd processingTokenEnd = new TokenEnd(); 181 182 /** NP value for current range. */ 183 private BigInteger currentRangeValue; 184 185 /** Specify the maximum threshold allowed. */ 186 private int max = DEFAULT_MAX; 187 188 /** True, when branch is visited, but not leaved. */ 189 private boolean branchVisited; 190 191 /** 192 * Setter to specify the maximum threshold allowed. 193 * 194 * @param max the maximum threshold 195 * @since 3.4 196 */ 197 public void setMax(int max) { 198 this.max = max; 199 } 200 201 @Override 202 public int[] getDefaultTokens() { 203 return getRequiredTokens(); 204 } 205 206 @Override 207 public int[] getAcceptableTokens() { 208 return getRequiredTokens(); 209 } 210 211 @Override 212 public int[] getRequiredTokens() { 213 return new int[] { 214 TokenTypes.CTOR_DEF, 215 TokenTypes.METHOD_DEF, 216 TokenTypes.STATIC_INIT, 217 TokenTypes.INSTANCE_INIT, 218 TokenTypes.LITERAL_WHILE, 219 TokenTypes.LITERAL_DO, 220 TokenTypes.LITERAL_FOR, 221 TokenTypes.LITERAL_IF, 222 TokenTypes.LITERAL_ELSE, 223 TokenTypes.LITERAL_SWITCH, 224 TokenTypes.CASE_GROUP, 225 TokenTypes.LITERAL_TRY, 226 TokenTypes.LITERAL_CATCH, 227 TokenTypes.QUESTION, 228 TokenTypes.LITERAL_RETURN, 229 TokenTypes.LITERAL_DEFAULT, 230 TokenTypes.COMPACT_CTOR_DEF, 231 TokenTypes.SWITCH_RULE, 232 TokenTypes.LITERAL_WHEN, 233 }; 234 } 235 236 @Override 237 public void beginTree(DetailAST rootAST) { 238 rangeValues.clear(); 239 expressionValues.clear(); 240 afterValues.clear(); 241 processingTokenEnd.reset(); 242 currentRangeValue = INITIAL_VALUE; 243 branchVisited = false; 244 } 245 246 @Override 247 public void visitToken(DetailAST ast) { 248 switch (ast.getType()) { 249 case TokenTypes.LITERAL_IF: 250 case TokenTypes.LITERAL_SWITCH: 251 case TokenTypes.LITERAL_WHILE: 252 case TokenTypes.LITERAL_DO: 253 case TokenTypes.LITERAL_FOR: 254 visitConditional(ast, 1); 255 break; 256 case TokenTypes.QUESTION: 257 visitUnitaryOperator(ast, 2); 258 break; 259 case TokenTypes.LITERAL_RETURN: 260 visitUnitaryOperator(ast, 0); 261 break; 262 case TokenTypes.LITERAL_WHEN: 263 visitWhenExpression(ast, 1); 264 break; 265 case TokenTypes.CASE_GROUP: 266 final int caseNumber = countCaseTokens(ast); 267 branchVisited = true; 268 pushValue(caseNumber); 269 break; 270 case TokenTypes.SWITCH_RULE: 271 final int caseConstantNumber = countCaseConstants(ast); 272 branchVisited = true; 273 pushValue(caseConstantNumber); 274 break; 275 case TokenTypes.LITERAL_ELSE: 276 branchVisited = true; 277 if (currentRangeValue.equals(BigInteger.ZERO)) { 278 currentRangeValue = BigInteger.ONE; 279 } 280 pushValue(0); 281 break; 282 case TokenTypes.LITERAL_TRY: 283 case TokenTypes.LITERAL_CATCH: 284 case TokenTypes.LITERAL_DEFAULT: 285 pushValue(1); 286 break; 287 case TokenTypes.CTOR_DEF: 288 case TokenTypes.METHOD_DEF: 289 case TokenTypes.INSTANCE_INIT: 290 case TokenTypes.STATIC_INIT: 291 case TokenTypes.COMPACT_CTOR_DEF: 292 pushValue(0); 293 break; 294 default: 295 break; 296 } 297 } 298 299 @Override 300 public void leaveToken(DetailAST ast) { 301 switch (ast.getType()) { 302 case TokenTypes.LITERAL_WHILE: 303 case TokenTypes.LITERAL_DO: 304 case TokenTypes.LITERAL_FOR: 305 case TokenTypes.LITERAL_IF: 306 case TokenTypes.LITERAL_SWITCH: 307 case TokenTypes.LITERAL_WHEN: 308 leaveConditional(); 309 break; 310 case TokenTypes.LITERAL_TRY: 311 leaveMultiplyingConditional(); 312 break; 313 case TokenTypes.LITERAL_RETURN: 314 case TokenTypes.QUESTION: 315 leaveUnitaryOperator(); 316 break; 317 case TokenTypes.LITERAL_CATCH: 318 leaveAddingConditional(); 319 break; 320 case TokenTypes.LITERAL_DEFAULT: 321 leaveBranch(); 322 break; 323 case TokenTypes.LITERAL_ELSE: 324 case TokenTypes.CASE_GROUP: 325 case TokenTypes.SWITCH_RULE: 326 leaveBranch(); 327 branchVisited = false; 328 break; 329 case TokenTypes.CTOR_DEF: 330 case TokenTypes.METHOD_DEF: 331 case TokenTypes.INSTANCE_INIT: 332 case TokenTypes.STATIC_INIT: 333 case TokenTypes.COMPACT_CTOR_DEF: 334 leaveMethodDef(ast); 335 break; 336 default: 337 break; 338 } 339 } 340 341 /** 342 * Visits if, while, do-while, for and switch tokens - all of them have expression in 343 * parentheses which is used for calculation. 344 * 345 * @param ast visited token. 346 * @param basicBranchingFactor default number of branches added. 347 */ 348 private void visitConditional(DetailAST ast, int basicBranchingFactor) { 349 int expressionValue = basicBranchingFactor; 350 DetailAST bracketed; 351 for (bracketed = ast.findFirstToken(TokenTypes.LPAREN); 352 bracketed.getType() != TokenTypes.RPAREN; 353 bracketed = bracketed.getNextSibling()) { 354 expressionValue += countConditionalOperators(bracketed); 355 } 356 processingTokenEnd.setToken(bracketed); 357 pushValue(expressionValue); 358 } 359 360 /** 361 * Visits when expression token. There is no guarantee that when expression will be 362 * bracketed, so we don't use visitConditional method. 363 * 364 * @param ast visited token. 365 * @param basicBranchingFactor default number of branches added. 366 */ 367 private void visitWhenExpression(DetailAST ast, int basicBranchingFactor) { 368 final int expressionValue = basicBranchingFactor + countConditionalOperators(ast); 369 processingTokenEnd.setToken(getLastToken(ast)); 370 pushValue(expressionValue); 371 } 372 373 /** 374 * Visits ternary operator (?:) and return tokens. They differ from those processed by 375 * visitConditional method in that their expression isn't bracketed. 376 * 377 * @param ast visited token. 378 * @param basicBranchingFactor number of branches inherently added by this token. 379 */ 380 private void visitUnitaryOperator(DetailAST ast, int basicBranchingFactor) { 381 final boolean isAfter = processingTokenEnd.isAfter(ast); 382 afterValues.push(isAfter); 383 if (!isAfter) { 384 processingTokenEnd.setToken(getLastToken(ast)); 385 final int expressionValue = basicBranchingFactor + countConditionalOperators(ast); 386 pushValue(expressionValue); 387 } 388 } 389 390 /** 391 * Leaves ternary operator (?:) and return tokens. 392 */ 393 private void leaveUnitaryOperator() { 394 if (Boolean.FALSE.equals(afterValues.pop())) { 395 final Values valuePair = popValue(); 396 BigInteger basicRangeValue = valuePair.getRangeValue(); 397 BigInteger expressionValue = valuePair.getExpressionValue(); 398 if (expressionValue.equals(BigInteger.ZERO)) { 399 expressionValue = BigInteger.ONE; 400 } 401 if (basicRangeValue.equals(BigInteger.ZERO)) { 402 basicRangeValue = BigInteger.ONE; 403 } 404 currentRangeValue = currentRangeValue.add(expressionValue).multiply(basicRangeValue); 405 } 406 } 407 408 /** Leaves while, do, for, if, ternary (?::), return or switch. */ 409 private void leaveConditional() { 410 final Values valuePair = popValue(); 411 final BigInteger expressionValue = valuePair.getExpressionValue(); 412 BigInteger basicRangeValue = valuePair.getRangeValue(); 413 if (currentRangeValue.equals(BigInteger.ZERO)) { 414 currentRangeValue = BigInteger.ONE; 415 } 416 if (basicRangeValue.equals(BigInteger.ZERO)) { 417 basicRangeValue = BigInteger.ONE; 418 } 419 currentRangeValue = currentRangeValue.add(expressionValue).multiply(basicRangeValue); 420 } 421 422 /** Leaves else, default or case group tokens. */ 423 private void leaveBranch() { 424 final Values valuePair = popValue(); 425 final BigInteger basicRangeValue = valuePair.getRangeValue(); 426 final BigInteger expressionValue = valuePair.getExpressionValue(); 427 if (branchVisited && currentRangeValue.equals(BigInteger.ZERO)) { 428 currentRangeValue = BigInteger.ONE; 429 } 430 currentRangeValue = currentRangeValue.subtract(BigInteger.ONE) 431 .add(basicRangeValue) 432 .add(expressionValue); 433 } 434 435 /** 436 * Process the end of a method definition. 437 * 438 * @param ast the token type representing the method definition 439 */ 440 private void leaveMethodDef(DetailAST ast) { 441 final BigInteger bigIntegerMax = BigInteger.valueOf(max); 442 if (currentRangeValue.compareTo(bigIntegerMax) > 0) { 443 log(ast, MSG_KEY, currentRangeValue, bigIntegerMax); 444 } 445 popValue(); 446 currentRangeValue = INITIAL_VALUE; 447 } 448 449 /** Leaves catch. */ 450 private void leaveAddingConditional() { 451 currentRangeValue = currentRangeValue.add(popValue().getRangeValue().add(BigInteger.ONE)); 452 } 453 454 /** 455 * Pushes the current range value on the range value stack. Pushes this token expression value 456 * on the expression value stack. 457 * 458 * @param expressionValue value of expression calculated for current token. 459 */ 460 private void pushValue(Integer expressionValue) { 461 rangeValues.push(currentRangeValue); 462 expressionValues.push(expressionValue); 463 currentRangeValue = INITIAL_VALUE; 464 } 465 466 /** 467 * Pops values from both stack of expression values and stack of range values. 468 * 469 * @return pair of head values from both of the stacks. 470 */ 471 private Values popValue() { 472 final int expressionValue = expressionValues.pop(); 473 return new Values(rangeValues.pop(), BigInteger.valueOf(expressionValue)); 474 } 475 476 /** Leaves try. */ 477 private void leaveMultiplyingConditional() { 478 currentRangeValue = currentRangeValue.add(BigInteger.ONE) 479 .multiply(popValue().getRangeValue().add(BigInteger.ONE)); 480 } 481 482 /** 483 * Calculates number of conditional operators, including inline ternary operator, for a token. 484 * 485 * @param ast inspected token. 486 * @return number of conditional operators. 487 * @see <a href="https://docs.oracle.com/javase/specs/jls/se8/html/jls-15.html#jls-15.23"> 488 * Java Language Specification, §15.23</a> 489 * @see <a href="https://docs.oracle.com/javase/specs/jls/se8/html/jls-15.html#jls-15.24"> 490 * Java Language Specification, §15.24</a> 491 * @see <a href="https://docs.oracle.com/javase/specs/jls/se8/html/jls-15.html#jls-15.25"> 492 * Java Language Specification, §15.25</a> 493 */ 494 private static int countConditionalOperators(DetailAST ast) { 495 int number = 0; 496 for (DetailAST child = ast.getFirstChild(); child != null; 497 child = child.getNextSibling()) { 498 final int type = child.getType(); 499 if (type == TokenTypes.LOR || type == TokenTypes.LAND) { 500 number++; 501 } 502 else if (type == TokenTypes.QUESTION) { 503 number += 2; 504 } 505 number += countConditionalOperators(child); 506 } 507 return number; 508 } 509 510 /** 511 * Finds a leaf, which is the most distant from the root. 512 * 513 * @param ast the root of tree. 514 * @return the leaf. 515 */ 516 private static DetailAST getLastToken(DetailAST ast) { 517 final DetailAST lastChild = ast.getLastChild(); 518 final DetailAST result; 519 if (lastChild.getFirstChild() == null) { 520 result = lastChild; 521 } 522 else { 523 result = getLastToken(lastChild); 524 } 525 return result; 526 } 527 528 /** 529 * Counts number of case tokens subject to a case group token. 530 * 531 * @param ast case group token. 532 * @return number of case tokens. 533 */ 534 private static int countCaseTokens(DetailAST ast) { 535 int counter = 0; 536 for (DetailAST iterator = ast.getFirstChild(); iterator != null; 537 iterator = iterator.getNextSibling()) { 538 if (iterator.getType() == TokenTypes.LITERAL_CASE) { 539 counter++; 540 } 541 } 542 return counter; 543 } 544 545 /** 546 * Counts number of case constants tokens in a switch labeled rule. 547 * 548 * @param ast switch rule token. 549 * @return number of case constant tokens. 550 */ 551 private static int countCaseConstants(DetailAST ast) { 552 int counter = 0; 553 final DetailAST literalCase = ast.getFirstChild(); 554 555 for (DetailAST node = literalCase.getFirstChild(); node != null; 556 node = node.getNextSibling()) { 557 if (TokenUtil.isOfType(node, CASE_LABEL_TOKENS)) { 558 counter++; 559 } 560 } 561 562 return counter; 563 } 564 565 /** 566 * Coordinates of token end. Used to prevent inline ternary 567 * operator from being processed twice. 568 */ 569 private static final class TokenEnd { 570 571 /** End line of token. */ 572 private int endLineNo; 573 574 /** End column of token. */ 575 private int endColumnNo; 576 577 /** 578 * Sets end coordinates from given token. 579 * 580 * @param endToken token. 581 */ 582 public void setToken(DetailAST endToken) { 583 if (!isAfter(endToken)) { 584 endLineNo = endToken.getLineNo(); 585 endColumnNo = endToken.getColumnNo(); 586 } 587 } 588 589 /** Sets end token coordinates to the start of the file. */ 590 public void reset() { 591 endLineNo = 0; 592 endColumnNo = 0; 593 } 594 595 /** 596 * Checks if saved coordinates located after given token. 597 * 598 * @param ast given token. 599 * @return true, if saved coordinates located after given token. 600 */ 601 public boolean isAfter(DetailAST ast) { 602 final int lineNo = ast.getLineNo(); 603 final int columnNo = ast.getColumnNo(); 604 return lineNo <= endLineNo 605 && (lineNo != endLineNo 606 || columnNo <= endColumnNo); 607 } 608 609 } 610 611 /** 612 * Class that store range value and expression value. 613 */ 614 private static final class Values { 615 616 /** NP value for range. */ 617 private final BigInteger rangeValue; 618 619 /** NP value for expression. */ 620 private final BigInteger expressionValue; 621 622 /** 623 * Constructor that assigns all of class fields. 624 * 625 * @param valueOfRange NP value for range 626 * @param valueOfExpression NP value for expression 627 */ 628 private Values(BigInteger valueOfRange, BigInteger valueOfExpression) { 629 rangeValue = valueOfRange; 630 expressionValue = valueOfExpression; 631 } 632 633 /** 634 * Returns NP value for range. 635 * 636 * @return NP value for range 637 */ 638 public BigInteger getRangeValue() { 639 return rangeValue; 640 } 641 642 /** 643 * Returns NP value for expression. 644 * 645 * @return NP value for expression 646 */ 647 public BigInteger getExpressionValue() { 648 return expressionValue; 649 } 650 651 } 652 653}