View Javadoc

1   /**
2    * BSD-style license; for more info see http://pmd.sourceforge.net/license.html
3    */
4   package net.sourceforge.pmd.lang.java.rule.codesize;
5   
6   import java.util.ArrayList;
7   import java.util.List;
8   
9   import net.sourceforge.pmd.lang.java.ast.ASTConditionalAndExpression;
10  import net.sourceforge.pmd.lang.java.ast.ASTConditionalExpression;
11  import net.sourceforge.pmd.lang.java.ast.ASTConditionalOrExpression;
12  import net.sourceforge.pmd.lang.java.ast.ASTDoStatement;
13  import net.sourceforge.pmd.lang.java.ast.ASTExpression;
14  import net.sourceforge.pmd.lang.java.ast.ASTForStatement;
15  import net.sourceforge.pmd.lang.java.ast.ASTIfStatement;
16  import net.sourceforge.pmd.lang.java.ast.ASTMethodDeclaration;
17  import net.sourceforge.pmd.lang.java.ast.ASTReturnStatement;
18  import net.sourceforge.pmd.lang.java.ast.ASTStatement;
19  import net.sourceforge.pmd.lang.java.ast.ASTSwitchLabel;
20  import net.sourceforge.pmd.lang.java.ast.ASTSwitchStatement;
21  import net.sourceforge.pmd.lang.java.ast.ASTTryStatement;
22  import net.sourceforge.pmd.lang.java.ast.ASTWhileStatement;
23  import net.sourceforge.pmd.lang.java.ast.JavaNode;
24  import net.sourceforge.pmd.lang.java.rule.AbstractStatisticalJavaRule;
25  import net.sourceforge.pmd.stat.DataPoint;
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 NPathComplexityRule extends AbstractStatisticalJavaRule {
35  
36      public NPathComplexityRule() {
37          super();
38          setProperty(MINIMUM_DESCRIPTOR, 200d);
39      }
40  
41      private int complexityMultipleOf(JavaNode node, int npathStart, Object data) {
42  
43          int npath = npathStart;
44          JavaNode n;
45  
46          for (int i = 0; i < node.jjtGetNumChildren(); i++) {
47              n = (JavaNode) node.jjtGetChild(i);
48              npath *= (Integer) n.jjtAccept(this, data);
49          }
50  
51          return npath;
52      }
53  
54      private int complexitySumOf(JavaNode node, int npathStart, Object data) {
55  
56          int npath = npathStart;
57          JavaNode n;
58  
59          for (int i = 0; i < node.jjtGetNumChildren(); i++) {
60              n = (JavaNode) node.jjtGetChild(i);
61              npath += (Integer) n.jjtAccept(this, data);
62          }
63  
64          return npath;
65      }
66  
67      @Override
68      public Object visit(ASTMethodDeclaration node, Object data) {
69          int npath = complexityMultipleOf(node, 1, data);
70  
71          DataPoint point = new DataPoint();
72          point.setNode(node);
73          point.setScore(1.0 * npath);
74          point.setMessage(getMessage());
75          addDataPoint(point);
76  
77          return Integer.valueOf(npath);
78      }
79  
80      @Override
81      public Object visit(JavaNode node, Object data) {
82          int npath = complexityMultipleOf(node, 1, data);
83          return Integer.valueOf(npath);
84      }
85  
86      @Override
87      public Object visit(ASTIfStatement node, Object data) {
88          // (npath of if + npath of else (or 1) + bool_comp of if) * npath of
89          // next
90  
91          int boolCompIf = sumExpressionComplexity(node.getFirstChildOfType(ASTExpression.class));
92  
93          int complexity = 0;
94  
95          List<JavaNode> statementChildren = new ArrayList<JavaNode>();
96          for (int i = 0; i < node.jjtGetNumChildren(); i++) {
97              if (node.jjtGetChild(i).getClass() == ASTStatement.class) {
98                  statementChildren.add((JavaNode) node.jjtGetChild(i));
99              }
100         }
101 
102         if (statementChildren.isEmpty() || statementChildren.size() == 1 && node.hasElse()
103                 || statementChildren.size() != 1 && !node.hasElse()) {
104             throw new IllegalStateException("If node has wrong number of children");
105         }
106 
107         // add path for not taking if
108         if (!node.hasElse()) {
109             complexity++;
110         }
111 
112         for (JavaNode element : statementChildren) {
113             complexity += (Integer) element.jjtAccept(this, data);
114         }
115 
116         return Integer.valueOf(boolCompIf + complexity);
117     }
118 
119     @Override
120     public Object visit(ASTWhileStatement node, Object data) {
121         // (npath of while + bool_comp of while + 1) * npath of next
122 
123         int boolCompWhile = sumExpressionComplexity(node.getFirstChildOfType(ASTExpression.class));
124 
125         Integer nPathWhile = (Integer) ((JavaNode) node.getFirstChildOfType(ASTStatement.class)).jjtAccept(this, data);
126 
127         return Integer.valueOf(boolCompWhile + nPathWhile + 1);
128     }
129 
130     @Override
131     public Object visit(ASTDoStatement node, Object data) {
132         // (npath of do + bool_comp of do + 1) * npath of next
133 
134         int boolCompDo = sumExpressionComplexity(node.getFirstChildOfType(ASTExpression.class));
135 
136         Integer nPathDo = (Integer) ((JavaNode) node.getFirstChildOfType(ASTStatement.class)).jjtAccept(this, data);
137 
138         return Integer.valueOf(boolCompDo + nPathDo + 1);
139     }
140 
141     @Override
142     public Object visit(ASTForStatement node, Object data) {
143         // (npath of for + bool_comp of for + 1) * npath of next
144 
145         int boolCompFor = sumExpressionComplexity(node.getFirstDescendantOfType(ASTExpression.class));
146 
147         Integer nPathFor = (Integer) ((JavaNode) node.getFirstChildOfType(ASTStatement.class)).jjtAccept(this, data);
148 
149         return Integer.valueOf(boolCompFor + nPathFor + 1);
150     }
151 
152     @Override
153     public Object visit(ASTReturnStatement node, Object data) {
154         // return statements are valued at 1, or the value of the boolean
155         // expression
156 
157         ASTExpression expr = node.getFirstChildOfType(ASTExpression.class);
158 
159         if (expr == null) {
160             return NumericConstants.ONE;
161         }
162 
163         int boolCompReturn = sumExpressionComplexity(expr);
164         int conditionalExpressionComplexity = complexityMultipleOf(expr, 1, data);
165 
166         if (conditionalExpressionComplexity > 1) {
167             boolCompReturn += conditionalExpressionComplexity;
168         }
169 
170         if (boolCompReturn > 0) {
171             return Integer.valueOf(boolCompReturn);
172         }
173         return NumericConstants.ONE;
174     }
175 
176     @Override
177     public Object visit(ASTSwitchStatement node, Object data) {
178         // bool_comp of switch + sum(npath(case_range))
179 
180         int boolCompSwitch = sumExpressionComplexity(node.getFirstChildOfType(ASTExpression.class));
181 
182         int npath = 0;
183         int caseRange = 0;
184         for (int i = 0; i < node.jjtGetNumChildren(); i++) {
185             JavaNode n = (JavaNode) node.jjtGetChild(i);
186 
187             // Fall-through labels count as 1 for complexity
188             if (n instanceof ASTSwitchLabel) {
189                 npath += caseRange;
190                 caseRange = 1;
191             } else {
192                 Integer complexity = (Integer) n.jjtAccept(this, data);
193                 caseRange *= complexity;
194             }
195         }
196         // add in npath of last label
197         npath += caseRange;
198         return Integer.valueOf(boolCompSwitch + npath);
199     }
200 
201     @Override
202     public Object visit(ASTTryStatement node, Object data) {
203         /*
204          * This scenario was not addressed by the original paper. Based on the
205          * principles outlined in the paper, as well as the Checkstyle NPath
206          * implementation, this code will add the complexity of the try to the
207          * complexities of the catch and finally blocks.
208          */
209         int npath = complexitySumOf(node, 0, data);
210 
211         return Integer.valueOf(npath);
212 
213     }
214 
215     @Override
216     public Object visit(ASTConditionalExpression node, Object data) {
217         if (node.isTernary()) {
218             int npath = complexitySumOf(node, 0, data);
219 
220             npath += 2;
221             return Integer.valueOf(npath);
222         }
223         return NumericConstants.ONE;
224     }
225 
226     /**
227      * Calculate the boolean complexity of the given expression. NPath boolean
228      * complexity is the sum of && and || tokens. This is calculated by summing
229      * the number of children of the &&'s (minus one) and the children of the
230      * ||'s (minus one).
231      * <p>
232      * Note that this calculation applies to Cyclomatic Complexity as well.
233      * 
234      * @param expr control structure expression
235      * @return complexity of the boolean expression
236      */
237     public static int sumExpressionComplexity(ASTExpression expr) {
238         if (expr == null) {
239             return 0;
240         }
241 
242         List<ASTConditionalAndExpression> andNodes = expr.findDescendantsOfType(ASTConditionalAndExpression.class);
243         List<ASTConditionalOrExpression> orNodes = expr.findDescendantsOfType(ASTConditionalOrExpression.class);
244 
245         int children = 0;
246 
247         for (ASTConditionalOrExpression element : orNodes) {
248             children += element.jjtGetNumChildren();
249             children--;
250         }
251 
252         for (ASTConditionalAndExpression element : andNodes) {
253             children += element.jjtGetNumChildren();
254             children--;
255         }
256 
257         return children;
258     }
259 
260     @Override
261     public Object[] getViolationParameters(DataPoint point) {
262         return new String[] { ((ASTMethodDeclaration) point.getNode()).getMethodName(),
263                 String.valueOf((int) point.getScore()) };
264     }
265 }