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