View Javadoc

    1   package net.sourceforge.pmd.rules.design;
    2
    3   import java.util.ArrayList;
    4   import java.util.List;
    5   import java.util.Set;
    6
    7   import net.sourceforge.pmd.RuleContext;
    8   import net.sourceforge.pmd.ast.ASTConditionalAndExpression;
    9   import net.sourceforge.pmd.ast.ASTConditionalExpression;
    10  import net.sourceforge.pmd.ast.ASTConditionalOrExpression;
    11  import net.sourceforge.pmd.ast.ASTDoStatement;
    12  import net.sourceforge.pmd.ast.ASTExpression;
    13  import net.sourceforge.pmd.ast.ASTForStatement;
    14  import net.sourceforge.pmd.ast.ASTIfStatement;
    15  import net.sourceforge.pmd.ast.ASTMethodDeclaration;
    16  import net.sourceforge.pmd.ast.ASTReturnStatement;
    17  import net.sourceforge.pmd.ast.ASTStatement;
    18  import net.sourceforge.pmd.ast.ASTSwitchLabel;
    19  import net.sourceforge.pmd.ast.ASTSwitchStatement;
    20  import net.sourceforge.pmd.ast.ASTTryStatement;
    21  import net.sourceforge.pmd.ast.ASTWhileStatement;
    22  import net.sourceforge.pmd.ast.SimpleJavaNode;
    23  import net.sourceforge.pmd.stat.DataPoint;
    24  import net.sourceforge.pmd.stat.StatisticalRule;
    25  import net.sourceforge.pmd.util.NumericConstants;
    26
    27  /**
    28   * NPath complexity is a measurement of the acyclic execution paths through a
    29   * function. See Nejmeh, Communications of the ACM Feb 1988 pp 188-200.
    30   *
    31   * @author Jason Bennett
    32   */
    33  public class NpathComplexity extends StatisticalRule {
    34
    35
    36  	private int complexityMultipleOf(SimpleJavaNode node, int npathStart, Object data) {
    37
    38  		int npath = npathStart;
    39  		SimpleJavaNode simpleNode;
    40
    41  	    for ( int i = 0; i < node.jjtGetNumChildren(); i++ ) {
    42  	        simpleNode = (SimpleJavaNode) node.jjtGetChild( i );
    43  	        npath *= ((Integer) simpleNode.jjtAccept( this, data ));
    44  	      }
    45
    46  	    return npath;
    47  	}
    48
    49  	private int complexitySumOf(SimpleJavaNode node, int npathStart, Object data) {
    50
    51  		int npath = npathStart;
    52  		SimpleJavaNode simpleNode;
    53
    54  	    for ( int i = 0; i < node.jjtGetNumChildren(); i++ ) {
    55  	        simpleNode = (SimpleJavaNode) node.jjtGetChild( i );
    56  	        npath += (Integer) simpleNode.jjtAccept( this, data );
    57  	      }
    58
    59  	    return npath;
    60  	}
    61
    62    public Object visit(ASTMethodDeclaration node, Object data) {
    63
    64  //    int npath = 1;
    65  //
    66  //    // Basic NPath functionality multiplies the complexity of peer nodes
    67  //    for ( int i = 0; i < node.jjtGetNumChildren(); i++ ) {
    68  //      SimpleJavaNode simpleNode = (SimpleJavaNode) node.jjtGetChild( i );
    69  //      Integer complexity = (Integer) simpleNode.jjtAccept( this, data );
    70  //      npath *= complexity.intValue();
    71  //    }
    72
    73  	  int npath = complexityMultipleOf(node, 1, data);
    74
    75      DataPoint point = new DataPoint();
    76      point.setNode( node );
    77      point.setScore( 1.0 * npath );
    78      point.setMessage( getMessage() );
    79      addDataPoint( point );
    80
    81      return Integer.valueOf( npath );
    82    }
    83
    84    public Object visit(SimpleJavaNode node, Object data) {
    85  //    int npath = 1;
    86  //
    87  //    for ( int i = 0; i < node.jjtGetNumChildren(); i++ ) {
    88  //      SimpleJavaNode simpleNode = (SimpleJavaNode) node.jjtGetChild( i );
    89  //      Integer complexity = (Integer) simpleNode.jjtAccept( this, data );
    90  //      npath *= complexity.intValue();
    91  //    }
    92
    93  	 int npath = complexityMultipleOf(node, 1, data);
    94
    95      return Integer.valueOf( npath );
    96    }
    97
    98    public Object visit(ASTIfStatement node, Object data) {
    99      // (npath of if + npath of else (or 1) + bool_comp of if) * npath of next
    100
    101     int boolCompIf = sumExpressionComplexity( node.getFirstChildOfType( ASTExpression.class ) );
    102
    103     int complexity = 0;
    104
    105     List<SimpleJavaNode> statementChildren = new ArrayList<SimpleJavaNode>();
    106     for ( int i = 0; i < node.jjtGetNumChildren(); i++ ) {
    107       if ( node.jjtGetChild( i ).getClass() == ASTStatement.class ) {
    108         statementChildren.add((SimpleJavaNode) node.jjtGetChild( i ) );
    109       }
    110     }
    111
    112     if ( statementChildren.isEmpty()
    113         || ( statementChildren.size() == 1 && node.hasElse() )
    114         || ( statementChildren.size() != 1 && !node.hasElse() ) ) {
    115       throw new IllegalStateException( "If node has wrong number of children" );
    116     }
    117
    118     // add path for not taking if
    119     if ( !node.hasElse() ) {
    120       complexity++;
    121     }
    122
    123     for (SimpleJavaNode element: statementChildren) {
    124       complexity += (Integer) element.jjtAccept( this, data );
    125     }
    126
    127     return Integer.valueOf( boolCompIf + complexity );
    128   }
    129
    130   public Object visit(ASTWhileStatement node, Object data) {
    131     // (npath of while + bool_comp of while + 1) * npath of next
    132
    133     int boolCompWhile = sumExpressionComplexity( node.getFirstChildOfType( ASTExpression.class ) );
    134
    135     Integer nPathWhile = (Integer) ( (SimpleJavaNode) node.getFirstChildOfType( ASTStatement.class ) ).jjtAccept(
    136         this, data );
    137
    138     return Integer.valueOf( boolCompWhile + nPathWhile + 1 );
    139   }
    140
    141   public Object visit(ASTDoStatement node, Object data) {
    142     // (npath of do + bool_comp of do + 1) * npath of next
    143
    144     int boolCompDo = sumExpressionComplexity( node.getFirstChildOfType( ASTExpression.class ) );
    145
    146     Integer nPathDo = (Integer) ( (SimpleJavaNode) node.getFirstChildOfType( ASTStatement.class ) ).jjtAccept(
    147         this, data );
    148
    149     return Integer.valueOf( boolCompDo + nPathDo + 1 );
    150   }
    151
    152   public Object visit(ASTForStatement node, Object data) {
    153     // (npath of for + bool_comp of for + 1) * npath of next
    154
    155     int boolCompFor = sumExpressionComplexity( node.getFirstChildOfType( ASTExpression.class ) );
    156
    157     Integer nPathFor = (Integer) ( (SimpleJavaNode) node.getFirstChildOfType( ASTStatement.class ) ).jjtAccept(
    158         this, data );
    159
    160     return Integer.valueOf( boolCompFor + nPathFor + 1 );
    161   }
    162
    163   public Object visit(ASTReturnStatement node, Object data) {
    164     // return statements are valued at 1, or the value of the boolean expression
    165
    166     ASTExpression expr = node.getFirstChildOfType( ASTExpression.class );
    167
    168     if ( expr == null ) {
    169       return NumericConstants.ONE;
    170     }
    171
    172     List andNodes = expr.findChildrenOfType( ASTConditionalAndExpression.class );
    173     List orNodes = expr.findChildrenOfType( ASTConditionalOrExpression.class );
    174     int boolCompReturn = andNodes.size() + orNodes.size();
    175
    176     if ( boolCompReturn > 0 ) {
    177       return Integer.valueOf( boolCompReturn );
    178     }
    179     return NumericConstants.ONE;
    180   }
    181
    182   public Object visit(ASTSwitchStatement node, Object data) {
    183     // bool_comp of switch + sum(npath(case_range))
    184
    185     int boolCompSwitch = sumExpressionComplexity( node.getFirstChildOfType( ASTExpression.class ) );
    186
    187     int npath = 0;
    188     int caseRange = 0;
    189     for ( int i = 0; i < node.jjtGetNumChildren(); i++ ) {
    190       SimpleJavaNode simpleNode = (SimpleJavaNode) node.jjtGetChild( i );
    191
    192       // Fall-through labels count as 1 for complexity
    193       if ( simpleNode instanceof ASTSwitchLabel ) {
    194         npath += caseRange;
    195         caseRange = 1;
    196       } else {
    197         Integer complexity = (Integer) simpleNode.jjtAccept( this, data );
    198         caseRange *= complexity;
    199       }
    200     }
    201     // add in npath of last label
    202     npath += caseRange;
    203     return Integer.valueOf( boolCompSwitch + npath );
    204   }
    205
    206   public Object visit(ASTTryStatement node, Object data) {
    207     /*
    208      * This scenario was not addressed by the original paper. Based on the
    209      * principles outlined in the paper, as well as the Checkstyle NPath
    210      * implementation, this code will add the complexity of the try to the
    211      * complexities of the catch and finally blocks.
    212      */
    213
    214 //    int npath = 0;
    215 //
    216 //    for ( int i = 0; i < node.jjtGetNumChildren(); i++ ) {
    217 //      SimpleJavaNode simpleNode = (SimpleJavaNode) node.jjtGetChild( i );
    218 //      Integer complexity = (Integer) simpleNode.jjtAccept( this, data );
    219 //      npath += complexity.intValue();
    220 //    }
    221
    222 	  int npath = complexitySumOf(node, 0, data);
    223
    224     return Integer.valueOf( npath );
    225
    226   }
    227
    228   public Object visit(ASTConditionalExpression node, Object data) {
    229     if ( node.isTernary() ) {
    230 //      int npath = 0;
    231 //
    232 //      for ( int i = 0; i < node.jjtGetNumChildren(); i++ ) {
    233 //        SimpleJavaNode simpleNode = (SimpleJavaNode) node.jjtGetChild( i );
    234 //        Integer complexity = (Integer) simpleNode.jjtAccept( this, data );
    235 //        npath += complexity.intValue();
    236 //      }
    237     	int npath = complexitySumOf(node, 0, data);
    238
    239       npath += 2;
    240       return Integer.valueOf( npath );
    241     }
    242     return NumericConstants.ONE;
    243   }
    244
    245   /**
    246    * Calculate the boolean complexity of the given expression. NPath boolean
    247    * complexity is the sum of && and || tokens. This is calculated by summing
    248    * the number of children of the &&'s (minus one) and the children of the ||'s
    249    * (minus one).
    250    * <p>
    251    * Note that this calculation applies to Cyclomatic Complexity as well.
    252    *
    253    * @param expr
    254    *          control structure expression
    255    * @return complexity of the boolean expression
    256    */
    257   public static int sumExpressionComplexity(ASTExpression expr) {
    258     if (expr == null) {
    259       return 0;
    260     }
    261
    262     List<ASTConditionalAndExpression> andNodes = expr.findChildrenOfType( ASTConditionalAndExpression.class );
    263     List<ASTConditionalOrExpression> orNodes = expr.findChildrenOfType( ASTConditionalOrExpression.class );
    264
    265     int children = 0;
    266
    267     for ( ASTConditionalOrExpression element: orNodes ) {
    268       children += element.jjtGetNumChildren();
    269       children--;
    270     }
    271
    272     for ( ASTConditionalAndExpression element: andNodes ) {
    273       children += element.jjtGetNumChildren();
    274       children--;
    275     }
    276
    277     return children;
    278   }
    279
    280   protected void makeViolations(RuleContext ctx, Set<DataPoint> p) {
    281     for ( DataPoint point: p ) {
    282       addViolation( ctx, point.getNode(), new String[] {
    283           ( (ASTMethodDeclaration) point.getNode() ).getMethodName(),
    284           String.valueOf( (int) point.getScore() ) } );
    285     }
    286   }
    287
    288 }