Package com.puppycrawl.tools.checkstyle.checks.metrics

Class NPathComplexityCheck

java.lang.Object
com.puppycrawl.tools.checkstyle.api.AutomaticBean
com.puppycrawl.tools.checkstyle.api.AbstractViolationReporter
com.puppycrawl.tools.checkstyle.api.AbstractCheck
com.puppycrawl.tools.checkstyle.checks.metrics.NPathComplexityCheck
All Implemented Interfaces:
Configurable, Contextualizable
public final class NPathComplexityCheck extends AbstractCheck

Checks the NPATH complexity against a specified limit.

The NPATH metric computes the number of possible execution paths through a function(method). It takes into account the nesting of conditional statements and multi-part boolean expressions (A && B, C || D, E ? F :G and their combinations).

The NPATH metric was designed base on Cyclomatic complexity to avoid problem of Cyclomatic complexity metric like nesting level within a function(method).

Metric was described at "NPATH: a measure of execution pathcomplexity and its applications". If you need detailed description of algorithm, please read that article, it is well written and have number of examples and details.

Here is some quotes:

An NPATH threshold value of 200 has been established for a function. The value 200 is based on studies done at AT&T Bell Laboratories [1988 year].
Some of the most effective methods of reducing the NPATH value include:
  • distributing functionality;
  • implementing multiple if statements as a switch statement;
  • creating a separate function for logical expressions with a high count of variables and (&&) and or (||) operators.
Although strategies to reduce the NPATH complexity of functions are important, care must be taken not to distort the logical clarity of the software by applying a strategy to reduce the complexity of functions. That is, there is a point of diminishing return beyond which a further attempt at reduction of complexity distorts the logical clarity of the system structure.
Examples
StructureComplexity expression
if ([expr]) { [if-range] }NP(if-range) + 1 + NP(expr)
if ([expr]) { [if-range] } else { [else-range] } NP(if-range)+ NP(else-range) + NP(expr)
while ([expr]) { [while-range] }NP(while-range) + NP(expr) + 1
do { [do-range] } while ([expr])NP(do-range) + NP(expr) + 1
for([expr1]; [expr2]; [expr3]) { [for-range] } NP(for-range) + NP(expr1)+ NP(expr2) + NP(expr3) + 1
switch ([expr]) { case : [case-range] default: [default-range] } S(i=1:i=n)NP(case-range[i]) + NP(default-range) + NP(expr)
[expr1] ? [expr2] : [expr3]NP(expr1) + NP(expr2) + NP(expr3) + 2
goto label1
break1
Expressions Number of && and || operators in expression. No operators - 0
continue1
return1
Statement (even sequential statements)1
Empty block {}1
Function call1
Function(Method) declaration or BlockP(i=1:i=N)NP(Statement[i])

Rationale: Nejmeh says that his group had an informal NPATH limit of 200 on individual routines; functions(methods) that exceeded this value were candidates for further decomposition - or at least a closer look. Please do not be fanatic with limit 200 - choose number that suites your project style. Limit 200 is empirical number base on some sources of at AT&T Bell Laboratories of 1988 year.

  • Property max - Specify the maximum threshold allowed. Type is int. Default value is 200.

To configure the check: 

 <module name="NPathComplexity"/>

Example: 

 public abstract class Test {

 final int a = 0;
 int b = 0;

 public void foo() { // OK, NPath complexity is less than default threshold
   // function consists of one if-else block with an NPath Complexity of 3
   if (a > 10) {
     if (a > b) { // nested if-else decision tree adds 2 to the complexity count
       buzz();
     } else {
       fizz();
     }
   } else { // last possible outcome of the main if-else block, adds 1 to complexity
     buzz();
   }
 }

 public void boo() { // violation, NPath complexity is 217 (max allowed is 200)
   // looping through 3 switch statements produces 6^3 + 1 (217) possible outcomes
   for(int i = 0; i < b; i++) { // for statement adds 1 to final complexity
     switch(i) { // each independent switch statement multiplies complexity by 6
       case a:
         // ternary with && adds 3 to switch's complexity
         print(f(i) && g(i) ? fizz() : buzz());
       default:
         // ternary with || adds 3 to switch's complexity
         print(f(i) || g(i) ? fizz() : buzz());
     }
     switch(i - 1) { // multiplies complexity by 6
       case a:
         print(f(i) && g(i) ? fizz() : buzz());
       default:
         print(f(i) || g(i) ? fizz() : buzz());
     }
     switch(i + 1) { // multiplies complexity by 6
       case a:
         print(f(i) && g(i) ? fizz() : buzz());
       default:
         print(f(i) || g(i) ? fizz() : buzz());
     }
   }
 }

 public abstract boolean f(int x);
 public abstract boolean g(int x);
 public abstract String fizz();
 public abstract String buzz();
 public abstract void print(String str);
 }

To configure the check with a threshold of 100: 

 <module name="NPathComplexity">
   <property name="max" value="100"/>
 </module>

Example: 

 public abstract class Test1 {
 public void foo() { // violation, NPath complexity is 128 (max allowed is 100)
   int a,b,t,m,n;
   a=b=t=m=n = 0;

   // Complexity is achieved by choosing from 2 options 7 times (2^7 = 128 possible outcomes)
   if (a > b) { // non-nested if-else decision tree multiplies complexity by 2
     bar();
   } else {
     baz();
   }

   print(t > 1 ? bar() : baz()); // 5 ternary statements multiply complexity by 2^5
   print(t > 2 ? bar() : baz());
   print(t > 3 ? bar() : baz());
   print(t > 4 ? bar() : baz());
   print(t > 5 ? bar() : baz());

   if (m > n) { // multiplies complexity by 2
     baz();
   } else {
     bar();
   }
 }

 public abstract String bar();
 public abstract String baz();
 public abstract void print(String str);
 }

Parent is com.puppycrawl.tools.checkstyle.TreeWalker

Violation Message Keys:

  • npathComplexity
Since:
3.4

  • Field Details

    • MSG_KEY

      public static final String MSG_KEY
      A key is pointing to the warning message text in "messages.properties" file.
      See Also:

    • DEFAULT_MAX

      private static final int DEFAULT_MAX
      Default allowed complexity.
      See Also:

    • INITIAL_VALUE

      private static final BigInteger INITIAL_VALUE
      The initial current value.

    • rangeValues

      private final Deque<BigInteger> rangeValues
      Stack of NP values for ranges.

    • expressionValues

      private final Deque<Integer> expressionValues
      Stack of NP values for expressions.

    • afterValues

      private final Deque<Boolean> afterValues
      Stack of belongs to range values for question operator.

    • processingTokenEnd

      private final NPathComplexityCheck.TokenEnd processingTokenEnd
      Range of the last processed expression. Used for checking that ternary operation which is a part of expression won't be processed for second time.

    • currentRangeValue

      private BigInteger currentRangeValue
      NP value for current range.

    • max

      private int max
      Specify the maximum threshold allowed.

    • branchVisited

      private boolean branchVisited
      True, when branch is visited, but not leaved.

  • Constructor Details

    • NPathComplexityCheck

      public NPathComplexityCheck()

  • Method Details

    • setMax

      public void setMax(int max)
      Setter to specify the maximum threshold allowed.
      Parameters:
      max - the maximum threshold

    • getDefaultTokens

      public int[] getDefaultTokens()
      Description copied from class: AbstractCheck
      Returns the default token a check is interested in. Only used if the configuration for a check does not define the tokens.
      Specified by:
      getDefaultTokens in class AbstractCheck
      Returns:
      the default tokens
      See Also:

    • getAcceptableTokens

      public int[] getAcceptableTokens()
      Description copied from class: AbstractCheck
      The configurable token set. Used to protect Checks against malicious users who specify an unacceptable token set in the configuration file. The default implementation returns the check's default tokens.
      Specified by:
      getAcceptableTokens in class AbstractCheck
      Returns:
      the token set this check is designed for.
      See Also:

    • getRequiredTokens

      public int[] getRequiredTokens()
      Description copied from class: AbstractCheck
      The tokens that this check must be registered for.
      Specified by:
      getRequiredTokens in class AbstractCheck
      Returns:
      the token set this must be registered for.
      See Also:

    • beginTree

      public void beginTree(DetailAST rootAST)
      Description copied from class: AbstractCheck
      Called before the starting to process a tree. Ideal place to initialize information that is to be collected whilst processing a tree.
      Overrides:
      beginTree in class AbstractCheck
      Parameters:
      rootAST - the root of the tree

    • visitToken

      public void visitToken(DetailAST ast)
      Description copied from class: AbstractCheck
      Called to process a token.
      Overrides:
      visitToken in class AbstractCheck
      Parameters:
      ast - the token to process

    • leaveToken

      public void leaveToken(DetailAST ast)
      Description copied from class: AbstractCheck
      Called after all the child nodes have been process.
      Overrides:
      leaveToken in class AbstractCheck
      Parameters:
      ast - the token leaving

    • visitConditional

      private void visitConditional(DetailAST ast, int basicBranchingFactor)
      Visits if, while, do-while, for and switch tokens - all of them have expression in parentheses which is used for calculation.
      Parameters:
      ast - visited token.
      basicBranchingFactor - default number of branches added.

    • visitUnitaryOperator

      private void visitUnitaryOperator(DetailAST ast, int basicBranchingFactor)
      Visits ternary operator (?:) and return tokens. They differ from those processed by visitConditional method in that their expression isn't bracketed.
      Parameters:
      ast - visited token.
      basicBranchingFactor - number of branches inherently added by this token.

    • leaveUnitaryOperator

      private void leaveUnitaryOperator()
      Leaves ternary operator (?:) and return tokens.

    • leaveConditional

      private void leaveConditional()
      Leaves while, do, for, if, ternary (?::), return or switch.

    • leaveBranch

      private void leaveBranch()
      Leaves else, default or case group tokens.

    • leaveMethodDef

      private void leaveMethodDef(DetailAST ast)
      Process the end of a method definition.
      Parameters:
      ast - the token type representing the method definition

    • leaveAddingConditional

      private void leaveAddingConditional()
      Leaves catch.

    • pushValue

      private void pushValue(Integer expressionValue)
      Pushes the current range value on the range value stack. Pushes this token expression value on the expression value stack.
      Parameters:
      expressionValue - value of expression calculated for current token.

    • popValue

      private NPathComplexityCheck.Values popValue()
      Pops values from both stack of expression values and stack of range values.
      Returns:
      pair of head values from both of the stacks.

    • leaveMultiplyingConditional

      private void leaveMultiplyingConditional()
      Leaves try.

    • countConditionalOperators

      private static int countConditionalOperators(DetailAST ast)
      Calculates number of conditional operators, including inline ternary operator, for a token.
      Parameters:
      ast - inspected token.
      Returns:
      number of conditional operators.
      See Also:

    • getLastToken

      private static DetailAST getLastToken(DetailAST ast)
      Finds a leaf, which is the most distant from the root.
      Parameters:
      ast - the root of tree.
      Returns:
      the leaf.

    • countCaseTokens

      private static int countCaseTokens(DetailAST ast)
      Counts number of case tokens subject to a case group token.
      Parameters:
      ast - case group token.
      Returns:
      number of case tokens.

    • countCaseConstants

      private static int countCaseConstants(DetailAST ast)
      Counts number of case constants (EXPR) tokens in a switch labeled rule.
      Parameters:
      ast - switch rule token.
      Returns:
      number of case constant (EXPR) tokens.