001/////////////////////////////////////////////////////////////////////////////////////////////// 002// checkstyle: Checks Java source code and other text files for adherence to a set of rules. 003// Copyright (C) 2001-2026 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 * 119 * @since 3.4 120 */ 121// -@cs[AbbreviationAsWordInName] Can't change check name 122@FileStatefulCheck 123public 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}