View Javadoc

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  //    int npath = 1;
65  //
66  //    // Basic NPath functionality multiplies the complexity of peer nodes
67  //    for ( int i = 0; i < node.jjtGetNumChildren(); i++ ) {
68  //      SimpleJavaNode simpleNode = (SimpleJavaNode) node.jjtGetChild( i );
69  //      Integer complexity = (Integer) simpleNode.jjtAccept( this, data );
70  //      npath *= complexity.intValue();
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  //    int npath = 1;
86  //
87  //    for ( int i = 0; i < node.jjtGetNumChildren(); i++ ) {
88  //      SimpleJavaNode simpleNode = (SimpleJavaNode) node.jjtGetChild( i );
89  //      Integer complexity = (Integer) simpleNode.jjtAccept( this, data );
90  //      npath *= complexity.intValue();
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      // (npath of if + npath of else (or 1) + bool_comp of if) * npath of next
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     // add path for not taking if
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     // (npath of while + bool_comp of while + 1) * npath of next
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     // (npath of do + bool_comp of do + 1) * npath of next
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     // (npath of for + bool_comp of for + 1) * npath of next
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     // return statements are valued at 1, or the value of the boolean expression
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     // bool_comp of switch + sum(npath(case_range))
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       // Fall-through labels count as 1 for complexity
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     // add in npath of last label
202     npath += caseRange;
203     return Integer.valueOf( boolCompSwitch + npath );
204   }
205 
206   public Object visit(ASTTryStatement node, Object data) {
207     /*
208      * This scenario was not addressed by the original paper. Based on the
209      * principles outlined in the paper, as well as the Checkstyle NPath
210      * implementation, this code will add the complexity of the try to the
211      * complexities of the catch and finally blocks.
212      */
213 
214 //    int npath = 0;
215 //
216 //    for ( int i = 0; i < node.jjtGetNumChildren(); i++ ) {
217 //      SimpleJavaNode simpleNode = (SimpleJavaNode) node.jjtGetChild( i );
218 //      Integer complexity = (Integer) simpleNode.jjtAccept( this, data );
219 //      npath += complexity.intValue();
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 //      int npath = 0;
231 //
232 //      for ( int i = 0; i < node.jjtGetNumChildren(); i++ ) {
233 //        SimpleJavaNode simpleNode = (SimpleJavaNode) node.jjtGetChild( i );
234 //        Integer complexity = (Integer) simpleNode.jjtAccept( this, data );
235 //        npath += complexity.intValue();
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 }