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