View Javadoc

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