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
66
67
68
69
70
71
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
87
88
89
90
91
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
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
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
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
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
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
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
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
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
204 npath += caseRange;
205 return new Integer( boolCompSwitch + npath );
206 }
207
208 public Object visit(ASTTryStatement node, Object data) {
209
210
211
212
213
214
215
216
217
218
219
220
221
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
233
234
235
236
237
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 }