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 = (JavaNode) node.jjtGetChild(i);
045 npath *= (Integer) n.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 = (JavaNode) node.jjtGetChild(i);
058 npath += (Integer) n.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((JavaNode) node.jjtGetChild(i));
095 }
096 }
097
098 if (statementChildren.isEmpty() || statementChildren.size() == 1 && node.hasElse()
099 || statementChildren.size() != 1 && !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 += (Integer) element.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) ((JavaNode) node.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) ((JavaNode) node.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) ((JavaNode) node.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 = (JavaNode) node.jjtGetChild(i);
178
179 // Fall-through labels count as 1 for complexity
180 if (n instanceof ASTSwitchLabel) {
181 npath += caseRange;
182 caseRange = 1;
183 } else {
184 Integer complexity = (Integer) n.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[] { ((ASTMethodDeclaration) point.getNode()).getMethodName(),
256 String.valueOf((int) point.getScore()) };
257 }
258 }
|