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
65
66
67
68
69
70
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
86
87
88
89
90
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
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
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
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
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
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
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
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
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
202 npath += caseRange;
203 return Integer.valueOf( boolCompSwitch + npath );
204 }
205
206 public Object visit(ASTTryStatement node, Object data) {
207
208
209
210
211
212
213
214
215
216
217
218
219
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
231
232
233
234
235
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 }