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