Class 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 multipart 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.
    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
    Expressions Number of && and || operators in expression. No operators - 0
    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.

    Parent is

    Violation Message Keys:

    • npathComplexity
    • Method Detail

      • setMax

        public void setMax​(int max)
        Setter to specify the maximum threshold allowed.
        max - the maximum threshold
      • 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
        the token set this check is designed 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.
        beginTree in class AbstractCheck
        rootAST - the root of the tree
      • 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.
        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.
        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.
        ast - the token type representing the method definition
      • 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.
        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.
        pair of head values from both of the stacks.
      • getLastToken

        private static DetailAST getLastToken​(DetailAST ast)
        Finds a leaf, which is the most distant from the root.
        ast - the root of tree.
        the leaf.
      • countCaseTokens

        private static int countCaseTokens​(DetailAST ast)
        Counts number of case tokens subject to a case group token.
        ast - case group token.
        number of case tokens.
      • countCaseConstants

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