NPathComplexityRule.java
001 package net.sourceforge.pmd.lang.java.rule.codesize;
002 
003 import java.util.ArrayList;
004 import java.util.List;
005 
006 import net.sourceforge.pmd.lang.java.ast.ASTConditionalAndExpression;
007 import net.sourceforge.pmd.lang.java.ast.ASTConditionalExpression;
008 import net.sourceforge.pmd.lang.java.ast.ASTConditionalOrExpression;
009 import net.sourceforge.pmd.lang.java.ast.ASTDoStatement;
010 import net.sourceforge.pmd.lang.java.ast.ASTExpression;
011 import net.sourceforge.pmd.lang.java.ast.ASTForStatement;
012 import net.sourceforge.pmd.lang.java.ast.ASTIfStatement;
013 import net.sourceforge.pmd.lang.java.ast.ASTMethodDeclaration;
014 import net.sourceforge.pmd.lang.java.ast.ASTReturnStatement;
015 import net.sourceforge.pmd.lang.java.ast.ASTStatement;
016 import net.sourceforge.pmd.lang.java.ast.ASTSwitchLabel;
017 import net.sourceforge.pmd.lang.java.ast.ASTSwitchStatement;
018 import net.sourceforge.pmd.lang.java.ast.ASTTryStatement;
019 import net.sourceforge.pmd.lang.java.ast.ASTWhileStatement;
020 import net.sourceforge.pmd.lang.java.ast.JavaNode;
021 import net.sourceforge.pmd.lang.java.rule.AbstractStatisticalJavaRule;
022 import net.sourceforge.pmd.stat.DataPoint;
023 import net.sourceforge.pmd.util.NumericConstants;
024 
025 /**
026  * NPath complexity is a measurement of the acyclic execution paths through a
027  * function. See Nejmeh, Communications of the ACM Feb 1988 pp 188-200.
028  *
029  @author Jason Bennett
030  */
031 public class NPathComplexityRule extends AbstractStatisticalJavaRule {
032     
033     public NPathComplexityRule() {
034   super();
035   setProperty(MINIMUM_DESCRIPTOR, 200d);
036     }
037 
038     private int complexityMultipleOf(JavaNode node, int npathStart, Object data) {
039 
040   int npath = npathStart;
041   JavaNode n;
042 
043   for (int i = 0; i < node.jjtGetNumChildren(); i++) {
044       n = (JavaNodenode.jjtGetChild(i);
045       npath *= (Integern.jjtAccept(this, data);
046   }
047 
048   return npath;
049     }
050 
051     private int complexitySumOf(JavaNode node, int npathStart, Object data) {
052 
053   int npath = npathStart;
054   JavaNode n;
055 
056   for (int i = 0; i < node.jjtGetNumChildren(); i++) {
057       n = (JavaNodenode.jjtGetChild(i);
058       npath += (Integern.jjtAccept(this, data);
059   }
060 
061   return npath;
062     }
063 
064     @Override
065     public Object visit(ASTMethodDeclaration node, Object data) {
066   int npath = complexityMultipleOf(node, 1, data);
067 
068   DataPoint point = new DataPoint();
069   point.setNode(node);
070   point.setScore(1.0 * npath);
071   point.setMessage(getMessage());
072   addDataPoint(point);
073 
074   return Integer.valueOf(npath);
075     }
076 
077     @Override
078     public Object visit(JavaNode node, Object data) {
079   int npath = complexityMultipleOf(node, 1, data);
080   return Integer.valueOf(npath);
081     }
082 
083     @Override
084     public Object visit(ASTIfStatement node, Object data) {
085   // (npath of if + npath of else (or 1) + bool_comp of if) * npath of next
086 
087   int boolCompIf = sumExpressionComplexity(node.getFirstChildOfType(ASTExpression.class));
088 
089   int complexity = 0;
090 
091   List<JavaNode> statementChildren = new ArrayList<JavaNode>();
092   for (int i = 0; i < node.jjtGetNumChildren(); i++) {
093       if (node.jjtGetChild(i).getClass() == ASTStatement.class) {
094     statementChildren.add((JavaNodenode.jjtGetChild(i));
095       }
096   }
097 
098   if (statementChildren.isEmpty() || statementChildren.size() == && node.hasElse()
099     || statementChildren.size() != && !node.hasElse()) {
100       throw new IllegalStateException("If node has wrong number of children");
101   }
102 
103   // add path for not taking if
104   if (!node.hasElse()) {
105       complexity++;
106   }
107 
108   for (JavaNode element : statementChildren) {
109       complexity += (Integerelement.jjtAccept(this, data);
110   }
111 
112   return Integer.valueOf(boolCompIf + complexity);
113     }
114 
115     @Override
116     public Object visit(ASTWhileStatement node, Object data) {
117   // (npath of while + bool_comp of while + 1) * npath of next
118 
119   int boolCompWhile = sumExpressionComplexity(node.getFirstChildOfType(ASTExpression.class));
120 
121   Integer nPathWhile = (Integer) ((JavaNodenode.getFirstChildOfType(ASTStatement.class)).jjtAccept(this, data);
122 
123   return Integer.valueOf(boolCompWhile + nPathWhile + 1);
124     }
125 
126     @Override
127     public Object visit(ASTDoStatement node, Object data) {
128   // (npath of do + bool_comp of do + 1) * npath of next
129 
130   int boolCompDo = sumExpressionComplexity(node.getFirstChildOfType(ASTExpression.class));
131 
132   Integer nPathDo = (Integer) ((JavaNodenode.getFirstChildOfType(ASTStatement.class)).jjtAccept(this, data);
133 
134   return Integer.valueOf(boolCompDo + nPathDo + 1);
135     }
136 
137     @Override
138     public Object visit(ASTForStatement node, Object data) {
139   // (npath of for + bool_comp of for + 1) * npath of next
140 
141   int boolCompFor = sumExpressionComplexity(node.getFirstDescendantOfType(ASTExpression.class));
142 
143   Integer nPathFor = (Integer) ((JavaNodenode.getFirstChildOfType(ASTStatement.class)).jjtAccept(this, data);
144 
145   return Integer.valueOf(boolCompFor + nPathFor + 1);
146     }
147 
148     @Override
149     public Object visit(ASTReturnStatement node, Object data) {
150   // return statements are valued at 1, or the value of the boolean expression
151 
152   ASTExpression expr = node.getFirstChildOfType(ASTExpression.class);
153 
154   if (expr == null) {
155       return NumericConstants.ONE;
156   }
157 
158   List<ASTConditionalAndExpression> andNodes = expr.findDescendantsOfType(ASTConditionalAndExpression.class);
159   List<ASTConditionalOrExpression> orNodes = expr.findDescendantsOfType(ASTConditionalOrExpression.class);
160   int boolCompReturn = andNodes.size() + orNodes.size();
161 
162   if (boolCompReturn > 0) {
163       return Integer.valueOf(boolCompReturn);
164   }
165   return NumericConstants.ONE;
166     }
167 
168     @Override
169     public Object visit(ASTSwitchStatement node, Object data) {
170   // bool_comp of switch + sum(npath(case_range))
171 
172   int boolCompSwitch = sumExpressionComplexity(node.getFirstChildOfType(ASTExpression.class));
173 
174   int npath = 0;
175   int caseRange = 0;
176   for (int i = 0; i < node.jjtGetNumChildren(); i++) {
177       JavaNode n = (JavaNodenode.jjtGetChild(i);
178 
179       // Fall-through labels count as 1 for complexity
180       if (instanceof ASTSwitchLabel) {
181     npath += caseRange;
182     caseRange = 1;
183       else {
184     Integer complexity = (Integern.jjtAccept(this, data);
185     caseRange *= complexity;
186       }
187   }
188   // add in npath of last label
189   npath += caseRange;
190   return Integer.valueOf(boolCompSwitch + npath);
191     }
192 
193     @Override
194     public Object visit(ASTTryStatement node, Object data) {
195   /*
196    * This scenario was not addressed by the original paper. Based on the
197    * principles outlined in the paper, as well as the Checkstyle NPath
198    * implementation, this code will add the complexity of the try to the
199    * complexities of the catch and finally blocks.
200    */
201   int npath = complexitySumOf(node, 0, data);
202 
203   return Integer.valueOf(npath);
204 
205     }
206 
207     @Override
208     public Object visit(ASTConditionalExpression node, Object data) {
209   if (node.isTernary()) {
210       int npath = complexitySumOf(node, 0, data);
211 
212       npath += 2;
213       return Integer.valueOf(npath);
214   }
215   return NumericConstants.ONE;
216     }
217 
218     /**
219      * Calculate the boolean complexity of the given expression. NPath boolean
220      * complexity is the sum of && and || tokens. This is calculated by summing
221      * the number of children of the &&'s (minus one) and the children of the ||'s
222      * (minus one).
223      <p>
224      * Note that this calculation applies to Cyclomatic Complexity as well.
225      *
226      @param expr
227      *          control structure expression
228      @return complexity of the boolean expression
229      */
230     public static int sumExpressionComplexity(ASTExpression expr) {
231   if (expr == null) {
232       return 0;
233   }
234 
235   List<ASTConditionalAndExpression> andNodes = expr.findDescendantsOfType(ASTConditionalAndExpression.class);
236   List<ASTConditionalOrExpression> orNodes = expr.findDescendantsOfType(ASTConditionalOrExpression.class);
237 
238   int children = 0;
239 
240   for (ASTConditionalOrExpression element : orNodes) {
241       children += element.jjtGetNumChildren();
242       children--;
243   }
244 
245   for (ASTConditionalAndExpression element : andNodes) {
246       children += element.jjtGetNumChildren();
247       children--;
248   }
249 
250   return children;
251     }
252 
253     @Override
254     public Object[] getViolationParameters(DataPoint point) {
255   return new String[] { ((ASTMethodDeclarationpoint.getNode()).getMethodName(),
256     String.valueOf((intpoint.getScore()) };
257     }
258 }