View Javadoc

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