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  
92          List<JavaNode> statementChildren = new ArrayList<>();
93          for (int i = 0; i < node.jjtGetNumChildren(); i++) {
94              if (node.jjtGetChild(i).getClass() == ASTStatement.class) {
95                  statementChildren.add((JavaNode) node.jjtGetChild(i));
96              }
97          }
98  
99          if (statementChildren.isEmpty() || statementChildren.size() == 1 && node.hasElse()
100                 || statementChildren.size() != 1 && !node.hasElse()) {
101             throw new IllegalStateException("If node has wrong number of children");
102         }
103 
104         // add path for not taking if
105         int complexity = 0;
106         if (!node.hasElse()) {
107             complexity++;
108         }
109 
110         for (JavaNode element : statementChildren) {
111             complexity += (Integer) element.jjtAccept(this, data);
112         }
113 
114         int boolCompIf = sumExpressionComplexity(node.getFirstChildOfType(ASTExpression.class));
115         return Integer.valueOf(boolCompIf + complexity);
116     }
117 
118     @Override
119     public Object visit(ASTWhileStatement node, Object data) {
120         // (npath of while + bool_comp of while + 1) * npath of next
121 
122         int boolCompWhile = sumExpressionComplexity(node.getFirstChildOfType(ASTExpression.class));
123 
124         Integer nPathWhile = (Integer) ((JavaNode) node.getFirstChildOfType(ASTStatement.class)).jjtAccept(this, data);
125 
126         return Integer.valueOf(boolCompWhile + nPathWhile + 1);
127     }
128 
129     @Override
130     public Object visit(ASTDoStatement node, Object data) {
131         // (npath of do + bool_comp of do + 1) * npath of next
132 
133         int boolCompDo = sumExpressionComplexity(node.getFirstChildOfType(ASTExpression.class));
134 
135         Integer nPathDo = (Integer) ((JavaNode) node.getFirstChildOfType(ASTStatement.class)).jjtAccept(this, data);
136 
137         return Integer.valueOf(boolCompDo + nPathDo + 1);
138     }
139 
140     @Override
141     public Object visit(ASTForStatement node, Object data) {
142         // (npath of for + bool_comp of for + 1) * npath of next
143 
144         int boolCompFor = sumExpressionComplexity(node.getFirstDescendantOfType(ASTExpression.class));
145 
146         Integer nPathFor = (Integer) ((JavaNode) node.getFirstChildOfType(ASTStatement.class)).jjtAccept(this, data);
147 
148         return Integer.valueOf(boolCompFor + nPathFor + 1);
149     }
150 
151     @Override
152     public Object visit(ASTReturnStatement node, Object data) {
153         // return statements are valued at 1, or the value of the boolean
154         // expression
155 
156         ASTExpression expr = node.getFirstChildOfType(ASTExpression.class);
157 
158         if (expr == null) {
159             return NumericConstants.ONE;
160         }
161 
162         int boolCompReturn = sumExpressionComplexity(expr);
163         int conditionalExpressionComplexity = complexityMultipleOf(expr, 1, data);
164 
165         if (conditionalExpressionComplexity > 1) {
166             boolCompReturn += conditionalExpressionComplexity;
167         }
168 
169         if (boolCompReturn > 0) {
170             return Integer.valueOf(boolCompReturn);
171         }
172         return NumericConstants.ONE;
173     }
174 
175     @Override
176     public Object visit(ASTSwitchStatement node, Object data) {
177         // bool_comp of switch + sum(npath(case_range))
178 
179         int boolCompSwitch = sumExpressionComplexity(node.getFirstChildOfType(ASTExpression.class));
180 
181         int npath = 0;
182         int caseRange = 0;
183         for (int i = 0; i < node.jjtGetNumChildren(); i++) {
184             JavaNode n = (JavaNode) node.jjtGetChild(i);
185 
186             // Fall-through labels count as 1 for complexity
187             if (n instanceof ASTSwitchLabel) {
188                 npath += caseRange;
189                 caseRange = 1;
190             } else {
191                 Integer complexity = (Integer) n.jjtAccept(this, data);
192                 caseRange *= complexity;
193             }
194         }
195         // add in npath of last label
196         npath += caseRange;
197         return Integer.valueOf(boolCompSwitch + npath);
198     }
199 
200     @Override
201     public Object visit(ASTTryStatement node, Object data) {
202         /*
203          * This scenario was not addressed by the original paper. Based on the
204          * principles outlined in the paper, as well as the Checkstyle NPath
205          * implementation, this code will add the complexity of the try to the
206          * complexities of the catch and finally blocks.
207          */
208         int npath = complexitySumOf(node, 0, data);
209 
210         return Integer.valueOf(npath);
211 
212     }
213 
214     @Override
215     public Object visit(ASTConditionalExpression node, Object data) {
216         if (node.isTernary()) {
217             int npath = complexitySumOf(node, 0, data);
218 
219             npath += 2;
220             return Integer.valueOf(npath);
221         }
222         return NumericConstants.ONE;
223     }
224 
225     /**
226      * Calculate the boolean complexity of the given expression. NPath boolean
227      * complexity is the sum of && and || tokens. This is calculated by summing
228      * the number of children of the &&'s (minus one) and the children of the
229      * ||'s (minus one).
230      * <p>
231      * Note that this calculation applies to Cyclomatic Complexity as well.
232      * 
233      * @param expr control structure expression
234      * @return complexity of the boolean expression
235      */
236     public static int sumExpressionComplexity(ASTExpression expr) {
237         if (expr == null) {
238             return 0;
239         }
240 
241         List<ASTConditionalAndExpression> andNodes = expr.findDescendantsOfType(ASTConditionalAndExpression.class);
242         List<ASTConditionalOrExpression> orNodes = expr.findDescendantsOfType(ASTConditionalOrExpression.class);
243 
244         int children = 0;
245 
246         for (ASTConditionalOrExpression element : orNodes) {
247             children += element.jjtGetNumChildren();
248             children--;
249         }
250 
251         for (ASTConditionalAndExpression element : andNodes) {
252             children += element.jjtGetNumChildren();
253             children--;
254         }
255 
256         return children;
257     }
258 
259     @Override
260     public Object[] getViolationParameters(DataPoint point) {
261         return new String[] { ((ASTMethodDeclaration) point.getNode()).getMethodName(),
262                 String.valueOf((int) point.getScore()) };
263     }
264 }