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 * <table> 086 * <caption>Examples</caption> 087 * <thead><tr><th>Structure</th><th>Complexity expression</th></tr></thead> 088 * <tr><td>if ([expr]) { [if-range] }</td><td>NP(if-range) + 1 + NP(expr)</td></tr> 089 * <tr><td>if ([expr]) { [if-range] } else { [else-range] }</td> 090 * <td>NP(if-range)+ NP(else-range) + NP(expr)</td></tr> 091 * <tr><td>while ([expr]) { [while-range] }</td><td>NP(while-range) + NP(expr) + 1</td></tr> 092 * <tr><td>do { [do-range] } while ([expr])</td><td>NP(do-range) + NP(expr) + 1</td></tr> 093 * <tr><td>for([expr1]; [expr2]; [expr3]) { [for-range] }</td> 094 * <td>NP(for-range) + NP(expr1)+ NP(expr2) + NP(expr3) + 1</td></tr> 095 * <tr><td>switch ([expr]) { case : [case-range] default: [default-range] }</td> 096 * <td>S(i=1:i=n)NP(case-range[i]) + NP(default-range) + NP(expr)</td></tr> 097 * <tr><td>when[expr]</td><td>NP(expr) + 1</td></tr> 098 * <tr><td>[expr1] ? [expr2] : [expr3]</td><td>NP(expr1) + NP(expr2) + NP(expr3) + 2</td></tr> 099 * <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 141public 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}