KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > net > sourceforge > pmd > rules > design > NpathComplexity


1 package net.sourceforge.pmd.rules.design;
2
3 import java.util.ArrayList JavaDoc;
4 import java.util.Iterator JavaDoc;
5 import java.util.List JavaDoc;
6 import java.util.Set JavaDoc;
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 JavaDoc 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 JavaDoc) simpleNode.jjtAccept( this, data )).intValue();
45           }
46         
47         return npath;
48     }
49     
50     private int complexitySumOf(SimpleJavaNode node, int npathStart, Object JavaDoc 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 JavaDoc) simpleNode.jjtAccept( this, data )).intValue();
58           }
59         
60         return npath;
61     }
62     
63   public Object JavaDoc visit(ASTMethodDeclaration node, Object JavaDoc 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 JavaDoc( npath );
83   }
84
85   public Object JavaDoc visit(SimpleJavaNode node, Object JavaDoc 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 JavaDoc( npath );
97   }
98
99   public Object JavaDoc visit(ASTIfStatement node, Object JavaDoc 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 JavaDoc statementChildren = new ArrayList JavaDoc();
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 JavaDoc( "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 JavaDoc iter = statementChildren.iterator(); iter.hasNext(); ) {
125       SimpleJavaNode element = (SimpleJavaNode) iter.next();
126       complexity += ( (Integer JavaDoc) element.jjtAccept( this, data ) ).intValue();
127     }
128
129     return new Integer JavaDoc( boolCompIf + complexity );
130   }
131
132   public Object JavaDoc visit(ASTWhileStatement node, Object JavaDoc 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 JavaDoc nPathWhile = (Integer JavaDoc) ( (SimpleJavaNode) node.getFirstChildOfType( ASTStatement.class ) ).jjtAccept(
138         this, data );
139
140     return new Integer JavaDoc( boolCompWhile + nPathWhile.intValue() + 1 );
141   }
142
143   public Object JavaDoc visit(ASTDoStatement node, Object JavaDoc 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 JavaDoc nPathDo = (Integer JavaDoc) ( (SimpleJavaNode) node.getFirstChildOfType( ASTStatement.class ) ).jjtAccept(
149         this, data );
150
151     return new Integer JavaDoc( boolCompDo + nPathDo.intValue() + 1 );
152   }
153
154   public Object JavaDoc visit(ASTForStatement node, Object JavaDoc 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 JavaDoc nPathFor = (Integer JavaDoc) ( (SimpleJavaNode) node.getFirstChildOfType( ASTStatement.class ) ).jjtAccept(
160         this, data );
161
162     return new Integer JavaDoc( boolCompFor + nPathFor.intValue() + 1 );
163   }
164
165   public Object JavaDoc visit(ASTReturnStatement node, Object JavaDoc 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 JavaDoc andNodes = expr.findChildrenOfType( ASTConditionalAndExpression.class );
175     List JavaDoc orNodes = expr.findChildrenOfType( ASTConditionalOrExpression.class );
176     int boolCompReturn = andNodes.size() + orNodes.size();
177
178     if ( boolCompReturn > 0 ) {
179       return new Integer JavaDoc( boolCompReturn );
180     }
181     return NumericConstants.ONE;
182   }
183
184   public Object JavaDoc visit(ASTSwitchStatement node, Object JavaDoc 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 JavaDoc complexity = (Integer JavaDoc) simpleNode.jjtAccept( this, data );
200         caseRange *= complexity.intValue();
201       }
202     }
203     // add in npath of last label
204
npath += caseRange;
205     return new Integer JavaDoc( boolCompSwitch + npath );
206   }
207
208   public Object JavaDoc visit(ASTTryStatement node, Object JavaDoc 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 JavaDoc( npath );
227
228   }
229
230   public Object JavaDoc visit(ASTConditionalExpression node, Object JavaDoc 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 JavaDoc( 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 JavaDoc andNodes = expr.findChildrenOfType( ASTConditionalAndExpression.class );
265     List JavaDoc orNodes = expr.findChildrenOfType( ASTConditionalOrExpression.class );
266
267     int children = 0;
268
269     for ( Iterator JavaDoc iter = orNodes.iterator(); iter.hasNext(); ) {
270       ASTConditionalOrExpression element = (ASTConditionalOrExpression) iter.next();
271       children += element.jjtGetNumChildren();
272       children--;
273     }
274
275     for ( Iterator JavaDoc 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 JavaDoc p) {
285     Iterator JavaDoc points = p.iterator();
286     while ( points.hasNext() ) {
287       DataPoint point = (DataPoint) points.next();
288       addViolation( ctx, point.getNode(), new String JavaDoc[] {
289           ( (ASTMethodDeclaration) point.getNode() ).getMethodName(),
290           String.valueOf( (int) point.getScore() ) } );
291     }
292   }
293
294 }
295
Popular Tags