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