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 }