Coverage Report - com.puppycrawl.tools.checkstyle.checks.metrics.NPathComplexityCheck
 
Classes in this File Line Coverage Branch Coverage Complexity
NPathComplexityCheck
100%
139/139
100%
52/52
3.077
NPathComplexityCheck$1
N/A
N/A
3.077
NPathComplexityCheck$TokenEnd
100%
14/14
100%
8/8
3.077
NPathComplexityCheck$Values
100%
6/6
N/A
3.077
 
 1  
 ////////////////////////////////////////////////////////////////////////////////
 2  
 // checkstyle: Checks Java source code for adherence to a set of rules.
 3  
 // Copyright (C) 2001-2017 the original author or authors.
 4  
 //
 5  
 // This library is free software; you can redistribute it and/or
 6  
 // modify it under the terms of the GNU Lesser General Public
 7  
 // License as published by the Free Software Foundation; either
 8  
 // version 2.1 of the License, or (at your option) any later version.
 9  
 //
 10  
 // This library is distributed in the hope that it will be useful,
 11  
 // but WITHOUT ANY WARRANTY; without even the implied warranty of
 12  
 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 13  
 // Lesser General Public License for more details.
 14  
 //
 15  
 // You should have received a copy of the GNU Lesser General Public
 16  
 // License along with this library; if not, write to the Free Software
 17  
 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 18  
 ////////////////////////////////////////////////////////////////////////////////
 19  
 
 20  
 package com.puppycrawl.tools.checkstyle.checks.metrics;
 21  
 
 22  
 import java.math.BigInteger;
 23  
 import java.util.ArrayDeque;
 24  
 import java.util.Deque;
 25  
 
 26  
 import com.puppycrawl.tools.checkstyle.FileStatefulCheck;
 27  
 import com.puppycrawl.tools.checkstyle.api.AbstractCheck;
 28  
 import com.puppycrawl.tools.checkstyle.api.DetailAST;
 29  
 import com.puppycrawl.tools.checkstyle.api.TokenTypes;
 30  
 
 31  
 /**
 32  
  * Checks the npath complexity against a specified limit (default = 200).
 33  
  * The npath metric computes the number of possible execution paths
 34  
  * through a function. Similar to the cyclomatic complexity but also
 35  
  * takes into account the nesting of conditional statements and
 36  
  * multi-part boolean expressions.
 37  
  *
 38  
  * @author <a href="mailto:simon@redhillconsulting.com.au">Simon Harris</a>
 39  
  * @author o_sukhodolsky
 40  
  */
 41  
 // -@cs[AbbreviationAsWordInName] Can't change check name
 42  
 @FileStatefulCheck
 43  21
 public final class NPathComplexityCheck extends AbstractCheck {
 44  
 
 45  
     /**
 46  
      * A key is pointing to the warning message text in "messages.properties"
 47  
      * file.
 48  
      */
 49  
     public static final String MSG_KEY = "npathComplexity";
 50  
 
 51  
     /** Default allowed complexity. */
 52  
     private static final int DEFAULT_MAX = 200;
 53  
 
 54  
     /** The initial current value. */
 55  1
     private static final BigInteger INITIAL_VALUE = BigInteger.ZERO;
 56  
 
 57  
     /**
 58  
      * Stack of NP values for ranges.
 59  
      */
 60  21
     private final Deque<BigInteger> rangeValues = new ArrayDeque<>();
 61  
 
 62  
     /** Stack of NP values for expressions. */
 63  21
     private final Deque<Integer> expressionValues = new ArrayDeque<>();
 64  
 
 65  
     /** Stack of belongs to range values for question operator. */
 66  21
     private final Deque<Boolean> isAfterValues = new ArrayDeque<>();
 67  
 
 68  
     /**
 69  
      * Range of the last processed expression. Used for checking that ternary operation
 70  
      * which is a part of expression won't be processed for second time.
 71  
      */
 72  21
     private final TokenEnd processingTokenEnd = new TokenEnd();
 73  
 
 74  
     /** NP value for current range. */
 75  21
     private BigInteger currentRangeValue = INITIAL_VALUE;
 76  
 
 77  
     /** Threshold to report error for. */
 78  21
     private int max = DEFAULT_MAX;
 79  
 
 80  
     /** True, when branch is visited, but not leaved. */
 81  
     private boolean branchVisited;
 82  
 
 83  
     /**
 84  
      * Set the maximum threshold allowed.
 85  
      * @param max the maximum threshold
 86  
      */
 87  
     public void setMax(int max) {
 88  4
         this.max = max;
 89  4
     }
 90  
 
 91  
     @Override
 92  
     public int[] getDefaultTokens() {
 93  20
         return getRequiredTokens();
 94  
     }
 95  
 
 96  
     @Override
 97  
     public int[] getAcceptableTokens() {
 98  5
         return getRequiredTokens();
 99  
     }
 100  
 
 101  
     @Override
 102  
     public int[] getRequiredTokens() {
 103  46
         return new int[] {
 104  
             TokenTypes.CTOR_DEF,
 105  
             TokenTypes.METHOD_DEF,
 106  
             TokenTypes.STATIC_INIT,
 107  
             TokenTypes.INSTANCE_INIT,
 108  
             TokenTypes.LITERAL_WHILE,
 109  
             TokenTypes.LITERAL_DO,
 110  
             TokenTypes.LITERAL_FOR,
 111  
             TokenTypes.LITERAL_IF,
 112  
             TokenTypes.LITERAL_ELSE,
 113  
             TokenTypes.LITERAL_SWITCH,
 114  
             TokenTypes.CASE_GROUP,
 115  
             TokenTypes.LITERAL_TRY,
 116  
             TokenTypes.LITERAL_CATCH,
 117  
             TokenTypes.QUESTION,
 118  
             TokenTypes.LITERAL_RETURN,
 119  
             TokenTypes.LITERAL_DEFAULT,
 120  
         };
 121  
     }
 122  
 
 123  
     @Override
 124  
     public void beginTree(DetailAST rootAST) {
 125  13
         rangeValues.clear();
 126  13
         expressionValues.clear();
 127  13
         isAfterValues.clear();
 128  13
         processingTokenEnd.reset();
 129  13
         currentRangeValue = INITIAL_VALUE;
 130  13
         branchVisited = false;
 131  13
     }
 132  
 
 133  
     @Override
 134  
     public void visitToken(DetailAST ast) {
 135  264
         switch (ast.getType()) {
 136  
             case TokenTypes.LITERAL_IF:
 137  
             case TokenTypes.LITERAL_SWITCH:
 138  
             case TokenTypes.LITERAL_WHILE:
 139  
             case TokenTypes.LITERAL_DO:
 140  
             case TokenTypes.LITERAL_FOR:
 141  142
                 visitConditional(ast, 1);
 142  142
                 break;
 143  
             case TokenTypes.QUESTION:
 144  26
                 visitUnitaryOperator(ast, 2);
 145  26
                 break;
 146  
             case TokenTypes.LITERAL_RETURN:
 147  10
                 visitUnitaryOperator(ast, 0);
 148  10
                 break;
 149  
             case TokenTypes.CASE_GROUP:
 150  12
                 final int caseNumber = countCaseTokens(ast);
 151  12
                 branchVisited = true;
 152  12
                 pushValue(caseNumber);
 153  12
                 break;
 154  
             case TokenTypes.LITERAL_ELSE:
 155  27
                 branchVisited = true;
 156  27
                 if (currentRangeValue.equals(BigInteger.ZERO)) {
 157  26
                     currentRangeValue = BigInteger.ONE;
 158  
                 }
 159  27
                 pushValue(0);
 160  27
                 break;
 161  
             case TokenTypes.LITERAL_TRY:
 162  
             case TokenTypes.LITERAL_CATCH:
 163  
             case TokenTypes.LITERAL_DEFAULT:
 164  5
                 pushValue(1);
 165  5
                 break;
 166  
             case TokenTypes.CTOR_DEF:
 167  
             case TokenTypes.METHOD_DEF:
 168  
             case TokenTypes.INSTANCE_INIT:
 169  
             case TokenTypes.STATIC_INIT:
 170  41
                 pushValue(0);
 171  41
                 break;
 172  
             default:
 173  
                 break;
 174  
         }
 175  264
     }
 176  
 
 177  
     @Override
 178  
     public void leaveToken(DetailAST ast) {
 179  258
         switch (ast.getType()) {
 180  
             case TokenTypes.LITERAL_WHILE:
 181  
             case TokenTypes.LITERAL_DO:
 182  
             case TokenTypes.LITERAL_FOR:
 183  
             case TokenTypes.LITERAL_IF:
 184  
             case TokenTypes.LITERAL_SWITCH:
 185  141
                 leaveConditional();
 186  141
                 break;
 187  
             case TokenTypes.LITERAL_TRY:
 188  1
                 leaveMultiplyingConditional();
 189  1
                 break;
 190  
             case TokenTypes.LITERAL_RETURN:
 191  
             case TokenTypes.QUESTION:
 192  33
                 leaveUnitaryOperator();
 193  33
                 break;
 194  
             case TokenTypes.LITERAL_CATCH:
 195  1
                 leaveAddingConditional();
 196  1
                 break;
 197  
             case TokenTypes.LITERAL_DEFAULT:
 198  3
                 leaveBranch();
 199  3
                 break;
 200  
             case TokenTypes.LITERAL_ELSE:
 201  
             case TokenTypes.CASE_GROUP:
 202  37
                 leaveBranch();
 203  37
                 branchVisited = false;
 204  37
                 break;
 205  
             case TokenTypes.CTOR_DEF:
 206  
             case TokenTypes.METHOD_DEF:
 207  
             case TokenTypes.INSTANCE_INIT:
 208  
             case TokenTypes.STATIC_INIT:
 209  41
                 leaveMethodDef(ast);
 210  41
                 break;
 211  
             default:
 212  
                 break;
 213  
         }
 214  258
     }
 215  
 
 216  
     /**
 217  
      * Visits if, while, do-while, for and switch tokens - all of them have expression in
 218  
      * parentheses which is used for calculation.
 219  
      * @param ast visited token.
 220  
      * @param basicBranchingFactor default number of branches added.
 221  
      */
 222  
     private void visitConditional(DetailAST ast, int basicBranchingFactor) {
 223  142
         int expressionValue = basicBranchingFactor;
 224  
         DetailAST bracketed;
 225  142
         for (bracketed = ast.findFirstToken(TokenTypes.LPAREN).getNextSibling();
 226  300
                 bracketed.getType() != TokenTypes.RPAREN;
 227  158
                 bracketed = bracketed.getNextSibling()) {
 228  158
             expressionValue += countConditionalOperators(bracketed);
 229  
         }
 230  142
         processingTokenEnd.setToken(bracketed);
 231  142
         pushValue(expressionValue);
 232  142
     }
 233  
 
 234  
     /**
 235  
      * Visits ternary operator (?:) and return tokens. They differ from those processed by
 236  
      * visitConditional method in that their expression isn't bracketed.
 237  
      * @param ast visited token.
 238  
      * @param basicBranchingFactor number of branches inherently added by this token.
 239  
      */
 240  
     private void visitUnitaryOperator(DetailAST ast, int basicBranchingFactor) {
 241  36
         final boolean isAfter = processingTokenEnd.isAfter(ast);
 242  36
         isAfterValues.push(isAfter);
 243  36
         if (!isAfter) {
 244  21
             processingTokenEnd.setToken(getLastToken(ast));
 245  21
             final int expressionValue = basicBranchingFactor + countConditionalOperators(ast);
 246  21
             pushValue(expressionValue);
 247  
         }
 248  36
     }
 249  
 
 250  
     /**
 251  
      * Leaves ternary operator (?:) and return tokens.
 252  
      */
 253  
     private void leaveUnitaryOperator() {
 254  33
         if (!isAfterValues.pop()) {
 255  19
             final Values valuePair = popValue();
 256  19
             BigInteger basicRangeValue = valuePair.getRangeValue();
 257  19
             BigInteger expressionValue = valuePair.getExpressionValue();
 258  19
             if (expressionValue.equals(BigInteger.ZERO)) {
 259  6
                 expressionValue = BigInteger.ONE;
 260  
             }
 261  19
             if (basicRangeValue.equals(BigInteger.ZERO)) {
 262  12
                 basicRangeValue = BigInteger.ONE;
 263  
             }
 264  19
             currentRangeValue = currentRangeValue.add(expressionValue).multiply(basicRangeValue);
 265  
         }
 266  33
     }
 267  
 
 268  
     /** Leaves while, do, for, if, ternary (?::), return or switch. */
 269  
     private void leaveConditional() {
 270  141
         final Values valuePair = popValue();
 271  141
         final BigInteger expressionValue = valuePair.getExpressionValue();
 272  141
         BigInteger basicRangeValue = valuePair.getRangeValue();
 273  141
         if (currentRangeValue.equals(BigInteger.ZERO)) {
 274  36
             currentRangeValue = BigInteger.ONE;
 275  
         }
 276  141
         if (basicRangeValue.equals(BigInteger.ZERO)) {
 277  121
             basicRangeValue = BigInteger.ONE;
 278  
         }
 279  141
         currentRangeValue = currentRangeValue.add(expressionValue).multiply(basicRangeValue);
 280  141
     }
 281  
 
 282  
     /** Leaves else, default or case group tokens. */
 283  
     private void leaveBranch() {
 284  40
         final Values valuePair = popValue();
 285  40
         final BigInteger basicRangeValue = valuePair.getRangeValue();
 286  40
         final BigInteger expressionValue = valuePair.getExpressionValue();
 287  40
         if (branchVisited && currentRangeValue.equals(BigInteger.ZERO)) {
 288  19
             currentRangeValue = BigInteger.ONE;
 289  
         }
 290  40
         currentRangeValue = currentRangeValue.subtract(BigInteger.ONE)
 291  40
                 .add(basicRangeValue)
 292  40
                 .add(expressionValue);
 293  40
     }
 294  
 
 295  
     /**
 296  
      * Process the end of a method definition.
 297  
      * @param ast the token type representing the method definition
 298  
      */
 299  
     private void leaveMethodDef(DetailAST ast) {
 300  41
         final BigInteger bigIntegerMax = BigInteger.valueOf(max);
 301  41
         if (currentRangeValue.compareTo(bigIntegerMax) > 0) {
 302  27
             log(ast, MSG_KEY, currentRangeValue, bigIntegerMax);
 303  
         }
 304  41
         popValue();
 305  41
         currentRangeValue = INITIAL_VALUE;
 306  41
     }
 307  
 
 308  
     /** Leaves catch. */
 309  
     private void leaveAddingConditional() {
 310  1
         currentRangeValue = currentRangeValue.add(popValue().getRangeValue().add(BigInteger.ONE));
 311  1
     }
 312  
 
 313  
     /**
 314  
      * Pushes the current range value on the range value stack. Pushes this token expression value
 315  
      * on the expression value stack.
 316  
      * @param expressionValue value of expression calculated for current token.
 317  
      */
 318  
     private void pushValue(Integer expressionValue) {
 319  248
         rangeValues.push(currentRangeValue);
 320  248
         expressionValues.push(expressionValue);
 321  248
         currentRangeValue = INITIAL_VALUE;
 322  248
     }
 323  
 
 324  
     /**
 325  
      * Pops values from both stack of expression values and stack of range values.
 326  
      * @return pair of head values from both of the stacks.
 327  
      */
 328  
     private Values popValue() {
 329  243
         final int expressionValue = expressionValues.pop();
 330  243
         return new Values(rangeValues.pop(), BigInteger.valueOf(expressionValue));
 331  
     }
 332  
 
 333  
     /** Leaves try. */
 334  
     private void leaveMultiplyingConditional() {
 335  1
         currentRangeValue = currentRangeValue.add(BigInteger.ONE)
 336  1
                 .multiply(popValue().getRangeValue().add(BigInteger.ONE));
 337  1
     }
 338  
 
 339  
     /**
 340  
      * Calculates number of conditional operators, including inline ternary operator, for a token.
 341  
      * @param ast inspected token.
 342  
      * @return number of conditional operators.
 343  
      * @see <a href="https://docs.oracle.com/javase/specs/jls/se8/html/jls-15.html#jls-15.23">
 344  
      * Java Language Specification, &sect;15.23</a>
 345  
      * @see <a href="https://docs.oracle.com/javase/specs/jls/se8/html/jls-15.html#jls-15.24">
 346  
      * Java Language Specification, &sect;15.24</a>
 347  
      * @see <a href="https://docs.oracle.com/javase/specs/jls/se8/html/jls-15.html#jls-15.25">
 348  
      * Java Language Specification, &sect;15.25</a>
 349  
      */
 350  
     private static int countConditionalOperators(DetailAST ast) {
 351  1084
         int number = 0;
 352  1084
         for (DetailAST child = ast.getFirstChild(); child != null;
 353  905
                 child = child.getNextSibling()) {
 354  905
             final int type = child.getType();
 355  905
             if (type == TokenTypes.LOR || type == TokenTypes.LAND) {
 356  37
                 number++;
 357  
             }
 358  868
             else if (type == TokenTypes.QUESTION) {
 359  14
                 number += 2;
 360  
             }
 361  905
             number += countConditionalOperators(child);
 362  
         }
 363  1084
         return number;
 364  
     }
 365  
 
 366  
     /**
 367  
      * Finds a leaf, which is the most distant from the root.
 368  
      * @param ast the root of tree.
 369  
      * @return the leaf.
 370  
      */
 371  
     private static DetailAST getLastToken(DetailAST ast) {
 372  32
         final DetailAST lastChild = ast.getLastChild();
 373  
         final DetailAST result;
 374  32
         if (lastChild.getFirstChild() == null) {
 375  21
             result = lastChild;
 376  
         }
 377  
         else {
 378  11
             result = getLastToken(lastChild);
 379  
         }
 380  32
         return result;
 381  
     }
 382  
 
 383  
     /**
 384  
      * Counts number of case tokens subject to a case group token.
 385  
      * @param ast case group token.
 386  
      * @return number of case tokens.
 387  
      */
 388  
     private static int countCaseTokens(DetailAST ast) {
 389  12
         int counter = 0;
 390  12
         for (DetailAST iterator = ast.getFirstChild(); iterator != null;
 391  27
                 iterator = iterator.getNextSibling()) {
 392  27
             if (iterator.getType() == TokenTypes.LITERAL_CASE) {
 393  12
                 counter++;
 394  
             }
 395  
         }
 396  12
         return counter;
 397  
     }
 398  
 
 399  
     /**
 400  
      * Coordinates of token end. Used to prevent inline ternary
 401  
      * operator from being processed twice.
 402  
      */
 403  42
     private static class TokenEnd {
 404  
         /** End line of token. */
 405  
         private int endLineNo;
 406  
 
 407  
         /** End column of token. */
 408  
         private int endColumnNo;
 409  
 
 410  
         /**
 411  
          * Sets end coordinates from given token.
 412  
          * @param endToken token.
 413  
          */
 414  
         public void setToken(DetailAST endToken) {
 415  163
             if (!isAfter(endToken)) {
 416  161
                 endLineNo = endToken.getLineNo();
 417  161
                 endColumnNo = endToken.getColumnNo();
 418  
             }
 419  163
         }
 420  
 
 421  
         /** Sets end token coordinates to the start of the file. */
 422  
         public void reset() {
 423  13
             endLineNo = 0;
 424  13
             endColumnNo = 0;
 425  13
         }
 426  
 
 427  
         /**
 428  
          * Checks if saved coordinates located after given token.
 429  
          * @param ast given token.
 430  
          * @return true, if saved coordinates located after given token.
 431  
          */
 432  
         public boolean isAfter(DetailAST ast) {
 433  200
             final int lineNo = ast.getLineNo();
 434  200
             final int columnNo = ast.getColumnNo();
 435  200
             boolean isAfter = true;
 436  200
             if (lineNo > endLineNo
 437  
                     || lineNo == endLineNo
 438  
                     && columnNo > endColumnNo) {
 439  182
                 isAfter = false;
 440  
             }
 441  200
             return isAfter;
 442  
         }
 443  
     }
 444  
 
 445  
     /**
 446  
      * Class that store range value and expression value.
 447  
      */
 448  
     private static class Values {
 449  
 
 450  
         /** NP value for range. */
 451  
         private final BigInteger rangeValue;
 452  
 
 453  
         /** NP value for expression. */
 454  
         private final BigInteger expressionValue;
 455  
 
 456  
         /**
 457  
          * Constructor that assigns all of class fields.
 458  
          * @param valueOfRange NP value for range
 459  
          * @param valueOfExpression NP value for expression
 460  
          */
 461  243
         Values(BigInteger valueOfRange, BigInteger valueOfExpression) {
 462  243
             rangeValue = valueOfRange;
 463  243
             expressionValue = valueOfExpression;
 464  243
         }
 465  
 
 466  
         /**
 467  
          * Returns NP value for range.
 468  
          * @return NP value for range
 469  
          */
 470  
         public BigInteger getRangeValue() {
 471  202
             return rangeValue;
 472  
         }
 473  
 
 474  
         /**
 475  
          * Returns NP value for expression.
 476  
          * @return NP value for expression
 477  
          */
 478  
         public BigInteger getExpressionValue() {
 479  200
             return expressionValue;
 480  
         }
 481  
 
 482  
     }
 483  
 
 484  
 }