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