View Javadoc

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  //    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( npath );
83    }
84  
85    public Object visit(SimpleJavaNode node, Object 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( npath );
97    }
98  
99    public Object visit(ASTIfStatement node, Object 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 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     // add path for not taking if
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     // (npath of while + bool_comp of while + 1) * npath of next
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     // (npath of do + bool_comp of do + 1) * npath of next
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     // (npath of for + bool_comp of for + 1) * npath of next
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     // 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 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     // 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 complexity = (Integer) simpleNode.jjtAccept( this, data );
200         caseRange *= complexity.intValue();
201       }
202     }
203     // add in npath of last label
204     npath += caseRange;
205     return new Integer( boolCompSwitch + npath );
206   }
207 
208   public Object visit(ASTTryStatement node, Object 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( npath );
227 
228   }
229 
230   public Object visit(ASTConditionalExpression node, Object 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( 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 }