View Javadoc

1   /**
2    * BSD-style license; for more info see http://pmd.sourceforge.net/license.html
3    */
4   package net.sourceforge.pmd.lang.plsql.rule.codesize;
5   
6   import java.util.ArrayList;
7   import java.util.List;
8   import java.util.logging.Logger;
9   
10  import net.sourceforge.pmd.lang.plsql.ast.ASTCaseStatement;
11  import net.sourceforge.pmd.lang.plsql.ast.ASTCaseWhenClause;
12  import net.sourceforge.pmd.lang.plsql.ast.ASTConditionalAndExpression;
13  import net.sourceforge.pmd.lang.plsql.ast.ASTConditionalOrExpression;
14  import net.sourceforge.pmd.lang.plsql.ast.ASTElseClause;
15  import net.sourceforge.pmd.lang.plsql.ast.ASTElsifClause;
16  import net.sourceforge.pmd.lang.plsql.ast.ASTExpression;
17  import net.sourceforge.pmd.lang.plsql.ast.ASTForStatement;
18  import net.sourceforge.pmd.lang.plsql.ast.ASTIfStatement;
19  import net.sourceforge.pmd.lang.plsql.ast.ASTLoopStatement;
20  import net.sourceforge.pmd.lang.plsql.ast.ASTMethodDeclaration;
21  import net.sourceforge.pmd.lang.plsql.ast.ASTProgramUnit;
22  import net.sourceforge.pmd.lang.plsql.ast.ASTReturnStatement;
23  import net.sourceforge.pmd.lang.plsql.ast.ASTStatement;
24  import net.sourceforge.pmd.lang.plsql.ast.ASTTriggerTimingPointSection;
25  import net.sourceforge.pmd.lang.plsql.ast.ASTTriggerUnit;
26  import net.sourceforge.pmd.lang.plsql.ast.ASTTypeMethod;
27  import net.sourceforge.pmd.lang.plsql.ast.ASTWhileStatement;
28  import net.sourceforge.pmd.lang.plsql.ast.ExecutableCode;
29  import net.sourceforge.pmd.lang.plsql.ast.PLSQLNode;
30  import net.sourceforge.pmd.lang.plsql.rule.AbstractStatisticalPLSQLRule;
31  import net.sourceforge.pmd.stat.DataPoint;
32  import net.sourceforge.pmd.util.NumericConstants;
33  
34  /**
35   * NPath complexity is a measurement of the acyclic execution paths through a
36   * function. See Nejmeh, Communications of the ACM Feb 1988 pp 188-200.
37   *
38   * @author Jason Bennett
39   */
40  public class NPathComplexityRule extends AbstractStatisticalPLSQLRule {
41      private final static String CLASS_NAME =  NPathComplexityRule.class.getCanonicalName() ;
42      private final static Logger LOGGER = Logger.getLogger(NPathComplexityRule.class.getName()); 
43      
44      public NPathComplexityRule() {
45  	super();
46  	setProperty(MINIMUM_DESCRIPTOR, 200d);
47      }
48  
49      private int complexityMultipleOf(PLSQLNode node, int npathStart, Object data) {
50          LOGGER.entering(CLASS_NAME,"complexityMultipleOf(SimpleNode)");
51  
52  	int npath = npathStart;
53  	PLSQLNode n;
54  
55  	for (int i = 0; i < node.jjtGetNumChildren(); i++) {
56  	    n = (PLSQLNode) node.jjtGetChild(i);
57  	    npath *= (Integer) n.jjtAccept(this, data);
58  	}
59  
60          LOGGER.exiting(CLASS_NAME,"complexityMultipleOf(SimpleNode)", npath);
61  	return npath;
62      }
63  
64      private int complexitySumOf(PLSQLNode node, int npathStart, Object data) {
65          LOGGER.entering(CLASS_NAME,"complexitySumOf(SimpleNode)", npathStart );
66  
67  	int npath = npathStart;
68  	PLSQLNode n;
69  
70  	for (int i = 0; i < node.jjtGetNumChildren(); i++) {
71  	    n = (PLSQLNode) node.jjtGetChild(i);
72  	    npath += (Integer) n.jjtAccept(this, data);
73  	}
74  
75          LOGGER.exiting(CLASS_NAME,"complexitySumOf(SimpleNode)", npath);
76  	return npath;
77      }
78  
79      @Override
80      public Object visit(ASTMethodDeclaration node, Object data) {
81          LOGGER.entering(CLASS_NAME,"visit(ASTMethodDeclaration)");
82  	int npath = complexityMultipleOf(node, 1, data);
83  
84  	DataPoint point = new DataPoint();
85  	point.setNode(node);
86  	point.setScore(1.0 * npath);
87  	point.setMessage(getMessage());
88  	addDataPoint(point);
89  
90          LOGGER.finest("NPath complexity:  " + npath + " for line " + node.getBeginLine() +", column " + node.getBeginColumn());
91          LOGGER.exiting(CLASS_NAME,"visit(ASTMethodDeclaration)", npath);
92  	return Integer.valueOf(npath);
93      }
94  
95      @Override
96      public Object visit(ASTProgramUnit node, Object data) {
97          LOGGER.entering(CLASS_NAME,"visit(ASTProgramUnit)");
98  	int npath = complexityMultipleOf(node, 1, data);
99  
100 	DataPoint point = new DataPoint();
101 	point.setNode(node);
102 	point.setScore(1.0 * npath);
103 	point.setMessage(getMessage());
104 	addDataPoint(point);
105 
106         LOGGER.finest("NPath complexity:  " + npath + " for line " + node.getBeginLine() +", column " + node.getBeginColumn());
107         LOGGER.exiting(CLASS_NAME,"visit(ASTProgramUnit)", npath);
108 	return Integer.valueOf(npath);
109     }
110 
111     @Override
112     public Object visit(ASTTypeMethod node, Object data) {
113         LOGGER.entering(CLASS_NAME,"visit(ASTTypeMethod)");
114 	int npath = complexityMultipleOf(node, 1, data);
115 
116 	DataPoint point = new DataPoint();
117 	point.setNode(node);
118 	point.setScore(1.0 * npath);
119 	point.setMessage(getMessage());
120 	addDataPoint(point);
121 
122         LOGGER.finest("NPath complexity:  " + npath + " for line " + node.getBeginLine() +", column " + node.getBeginColumn());
123         LOGGER.exiting(CLASS_NAME,"visit(ASTTypeMethod)", npath);
124 	return Integer.valueOf(npath);
125     }
126 
127     @Override
128     public Object visit(ASTTriggerUnit node, Object data) {
129         LOGGER.entering(CLASS_NAME,"visit(ASTTriggerUnit)");
130 	int npath = complexityMultipleOf(node, 1, data);
131 
132 	DataPoint point = new DataPoint();
133 	point.setNode(node);
134 	point.setScore(1.0 * npath);
135 	point.setMessage(getMessage());
136 	addDataPoint(point);
137 
138         LOGGER.finest("NPath complexity:  " + npath + " for line " + node.getBeginLine() +", column " + node.getBeginColumn());
139         LOGGER.exiting(CLASS_NAME,"visit(ASTTriggerUnit)", npath);
140 	return Integer.valueOf(npath);
141     }
142 
143     @Override
144     public Object visit(ASTTriggerTimingPointSection node, Object data) {
145         LOGGER.entering(CLASS_NAME,"visit(ASTTriggerTimingPointSection)");
146 	int npath = complexityMultipleOf(node, 1, data);
147 
148 	DataPoint point = new DataPoint();
149 	point.setNode(node);
150 	point.setScore(1.0 * npath);
151 	point.setMessage(getMessage());
152 	addDataPoint(point);
153 
154         LOGGER.finest("NPath complexity:  " + npath + " for line " + node.getBeginLine() +", column " + node.getBeginColumn());
155         LOGGER.exiting(CLASS_NAME,"visit(ASTTriggerTimingPointSection)", npath);
156 	return Integer.valueOf(npath);
157     }
158 
159     @Override
160     public Object visit(PLSQLNode node, Object data) {
161         LOGGER.entering(CLASS_NAME,"visit(SimpleNode)");
162 	int npath = complexityMultipleOf(node, 1, data);
163         LOGGER.exiting(CLASS_NAME,"visit(SimpleNode)" ,npath );
164 	return Integer.valueOf(npath);
165     }
166 
167     @Override
168     public Object visit(ASTIfStatement node, Object data) {
169         LOGGER.entering(CLASS_NAME,"visit(ASTIfStatement)");
170 	// (npath of if + npath of else (or 1) + bool_comp of if) * npath of next
171 
172 	int boolCompIf = sumExpressionComplexity(node.getFirstChildOfType(ASTExpression.class));
173 
174 	int complexity = 0;
175 
176 	List<PLSQLNode> statementChildren = new ArrayList<PLSQLNode>();
177 	for (int i = 0; i < node.jjtGetNumChildren(); i++) {
178 	    if (
179                 node.jjtGetChild(i).getClass() == ASTStatement.class
180                 ||node.jjtGetChild(i).getClass() == ASTElsifClause.class
181                 ||node.jjtGetChild(i).getClass() == ASTElseClause.class
182                ) {
183 		statementChildren.add((PLSQLNode) node.jjtGetChild(i));
184 	    }
185 	}
186         LOGGER.finest(statementChildren.size() + " statementChildren found for IF statement " + node.getBeginLine() +", column " + node.getBeginColumn());
187 
188         /* SRT 
189 	if (statementChildren.isEmpty() 
190             || statementChildren.size() == 1 &&  ( null !=  node.getFirstChildOfType(ASTElseClause.class) ) //.hasElse()
191 	    || statementChildren.size() != 1 && ( null ==  node.getFirstChildOfType(ASTElseClause.class) ) // !node.hasElse()
192            ) {
193 	    throw new IllegalStateException("If node has wrong number of children");
194 	}
195         */
196 
197         /* @TODO Any explicit Elsif clause(s) and Else clause are included in the list of statements 
198 	// add path for not taking if
199 	if (null ==  node.getFirstChildOfType(ASTElsifClause.class) ) // !node.hasElse()!node.hasElse()) 
200         {
201 	    complexity++;
202 	}
203 
204 	if (null ==  node.getFirstChildOfType(ASTElseClause.class) ) // !node.hasElse()!node.hasElse()) 
205         {
206 	    complexity++;
207 	}
208         * */
209 
210 	for (PLSQLNode element : statementChildren) {
211 	    complexity += (Integer) element.jjtAccept(this, data);
212 	}
213 
214         LOGGER.exiting(CLASS_NAME,"visit(ASTIfStatement)", (boolCompIf + complexity));
215 	return Integer.valueOf(boolCompIf + complexity);
216     }
217 
218     @Override
219     public Object visit(ASTElsifClause node, Object data) {
220         LOGGER.entering(CLASS_NAME,"visit(ASTElsifClause)");
221 	// (npath of if + npath of else (or 1) + bool_comp of if) * npath of next
222 
223 	int boolCompIf = sumExpressionComplexity(node.getFirstChildOfType(ASTExpression.class));
224 
225 	int complexity = 0;
226 
227 	List<PLSQLNode> statementChildren = new ArrayList<PLSQLNode>();
228 	for (int i = 0; i < node.jjtGetNumChildren(); i++) {
229 	    if (
230                 node.jjtGetChild(i).getClass() == ASTStatement.class
231                ) {
232 		statementChildren.add((PLSQLNode) node.jjtGetChild(i));
233 	    }
234 	}
235         LOGGER.finest(statementChildren.size() + " statementChildren found for ELSIF statement " + node.getBeginLine() +", column " + node.getBeginColumn());
236 
237         /* SRT 
238 	if (statementChildren.isEmpty() 
239             || statementChildren.size() == 1 &&  ( null !=  node.getFirstChildOfType(ASTElseClause.class) ) //.hasElse()
240 	    || statementChildren.size() != 1 && ( null ==  node.getFirstChildOfType(ASTElseClause.class) ) // !node.hasElse()
241            ) {
242 	    throw new IllegalStateException("If node has wrong number of children");
243 	}
244         */
245 
246 	for (PLSQLNode element : statementChildren) {
247 	    complexity += (Integer) element.jjtAccept(this, data);
248 	}
249 
250         LOGGER.exiting(CLASS_NAME,"visit(ASTElsifClause)", (boolCompIf + complexity));
251 	return Integer.valueOf(boolCompIf + complexity);
252     }
253 
254     @Override
255     public Object visit(ASTElseClause node, Object data) {
256         LOGGER.entering(CLASS_NAME,"visit(ASTElseClause)");
257 	// (npath of if + npath of else (or 1) + bool_comp of if) * npath of next
258 
259 	int complexity = 0;
260 
261 	List<PLSQLNode> statementChildren = new ArrayList<PLSQLNode>();
262 	for (int i = 0; i < node.jjtGetNumChildren(); i++) {
263 	    if (
264                 node.jjtGetChild(i).getClass() == ASTStatement.class
265                ) {
266 		statementChildren.add((PLSQLNode) node.jjtGetChild(i));
267 	    }
268 	}
269         LOGGER.finest(statementChildren.size() + " statementChildren found for ELSE clause statement " + node.getBeginLine() +", column " + node.getBeginColumn());
270 
271 	for (PLSQLNode element : statementChildren) {
272 	    complexity += (Integer) element.jjtAccept(this, data);
273 	}
274 
275         LOGGER.exiting(CLASS_NAME,"visit(ASTElseClause)", complexity);
276 	return Integer.valueOf(complexity);
277     }
278 
279     @Override
280     public Object visit(ASTWhileStatement node, Object data) {
281         LOGGER.entering(CLASS_NAME,"visit(ASTWhileStatement)");
282 	// (npath of while + bool_comp of while + 1) * npath of next
283 
284 	int boolCompWhile = sumExpressionComplexity(node.getFirstChildOfType(ASTExpression.class));
285 
286 	Integer nPathWhile = (Integer) ((PLSQLNode) node.getFirstChildOfType(ASTStatement.class)).jjtAccept(this, data);
287 
288         LOGGER.exiting(CLASS_NAME,"visit(ASTWhileStatement)", (boolCompWhile + nPathWhile + 1));
289 	return Integer.valueOf(boolCompWhile + nPathWhile + 1);
290     }
291 
292     @Override
293     public Object visit(ASTLoopStatement node, Object data) {
294         LOGGER.entering(CLASS_NAME,"visit(ASTLoopStatement)");
295 	// (npath of do + bool_comp of do + 1) * npath of next
296 
297 	int boolCompDo = sumExpressionComplexity(node.getFirstChildOfType(ASTExpression.class));
298 
299 	Integer nPathDo = (Integer) ((PLSQLNode) node.getFirstChildOfType(ASTStatement.class)).jjtAccept(this, data);
300 
301         LOGGER.exiting(CLASS_NAME,"visit(ASTLoopStatement)" ,(boolCompDo + nPathDo + 1)  );
302 	return Integer.valueOf(boolCompDo + nPathDo + 1);
303     }
304 
305     @Override
306     public Object visit(ASTForStatement node, Object data) {
307         LOGGER.entering(CLASS_NAME,"visit(ASTForStatement)");
308 	// (npath of for + bool_comp of for + 1) * npath of next
309 
310 	int boolCompFor = sumExpressionComplexity(node.getFirstDescendantOfType(ASTExpression.class));
311 
312 	Integer nPathFor = (Integer) ((PLSQLNode) node.getFirstChildOfType(ASTStatement.class)).jjtAccept(this, data);
313 
314         LOGGER.exiting(CLASS_NAME,"visit(ASTForStatement)",(boolCompFor + nPathFor + 1)  );
315 	return Integer.valueOf(boolCompFor + nPathFor + 1);
316     }
317 
318     @Override
319     public Object visit(ASTReturnStatement node, Object data) {
320         LOGGER.entering(CLASS_NAME,"visit(ASTReturnStatement)");
321 	// return statements are valued at 1, or the value of the boolean expression
322 
323 	ASTExpression expr = node.getFirstChildOfType(ASTExpression.class);
324 
325 	if (expr == null) {
326 	    return NumericConstants.ONE;
327 	}
328 
329 	int boolCompReturn = sumExpressionComplexity(expr);
330 	int conditionalExpressionComplexity = complexityMultipleOf(expr, 1, data);
331 
332 	if (conditionalExpressionComplexity > 1) {
333 	    boolCompReturn += conditionalExpressionComplexity;
334 	}
335 
336 	if (boolCompReturn > 0) {
337 	    return Integer.valueOf(boolCompReturn);
338 	}
339         LOGGER.entering(CLASS_NAME,"visit(ASTReturnStatement)", NumericConstants.ONE);
340 	return NumericConstants.ONE;
341     }
342 
343     @Override
344     public Object visit(ASTCaseWhenClause node, Object data) {
345         LOGGER.entering(CLASS_NAME,"visit(ASTCaseWhenClause)");
346 	// bool_comp of switch + sum(npath(case_range))
347 
348 	int boolCompSwitch = sumExpressionComplexity(node.getFirstChildOfType(ASTExpression.class));
349 
350 	int npath = 1;
351 	int caseRange = 0;
352 	for (int i = 0; i < node.jjtGetNumChildren(); i++) {
353 		PLSQLNode n = (PLSQLNode) node.jjtGetChild(i);
354 
355 	    // Fall-through labels count as 1 for complexity
356             Integer complexity = (Integer) n.jjtAccept(this, data);
357             caseRange *= complexity;
358 	}
359 	// add in npath of last label
360 	npath += caseRange;
361         LOGGER.exiting(CLASS_NAME,"visit(ASTCaseWhenClause)", (boolCompSwitch + npath) );
362 	return Integer.valueOf(boolCompSwitch + npath);
363     }
364 
365     @Override
366     public Object visit(ASTCaseStatement node, Object data) {
367         LOGGER.entering(CLASS_NAME,"visit(ASTCaseStatement)");
368 	// bool_comp of switch + sum(npath(case_range))
369 
370 	int boolCompSwitch = sumExpressionComplexity(node.getFirstChildOfType(ASTExpression.class));
371 
372 	int npath = 0;
373 	int caseRange = 0;
374 	for (int i = 0; i < node.jjtGetNumChildren(); i++) {
375 		PLSQLNode n = (PLSQLNode) node.jjtGetChild(i);
376 
377 	    // Fall-through labels count as 1 for complexity
378             Integer complexity = (Integer) n.jjtAccept(this, data);
379             caseRange *= complexity;
380 	}
381 	// add in npath of last label
382 	npath += caseRange;
383         LOGGER.exiting(CLASS_NAME,"visit(ASTCaseStatement)", (boolCompSwitch + npath));
384 	return Integer.valueOf(boolCompSwitch + npath);
385     }
386 
387     @Override
388     public Object visit(ASTConditionalOrExpression node, Object data) {
389 	return NumericConstants.ONE;
390     }
391 
392     /**
393      * Calculate the boolean complexity of the given expression. NPath boolean
394      * complexity is the sum of && and || tokens. This is calculated by summing
395      * the number of children of the &&'s (minus one) and the children of the ||'s
396      * (minus one).
397      * <p>
398      * Note that this calculation applies to Cyclomatic Complexity as well.
399      *
400      * @param expr
401      *          control structure expression
402      * @return complexity of the boolean expression
403      */
404     public static int sumExpressionComplexity(ASTExpression expr) {
405         LOGGER.entering(CLASS_NAME,"visit(ASTExpression)");
406 	if (expr == null) {
407           LOGGER.exiting(CLASS_NAME,"visit(ASTExpression)", 0);
408 	    return 0;
409 	}
410 
411 	List<ASTConditionalAndExpression> andNodes = expr.findDescendantsOfType(ASTConditionalAndExpression.class);
412 	List<ASTConditionalOrExpression> orNodes = expr.findDescendantsOfType(ASTConditionalOrExpression.class);
413 
414 	int children = 0;
415 
416 	for (ASTConditionalOrExpression element : orNodes) {
417 	    children += element.jjtGetNumChildren();
418 	    children--;
419 	}
420 
421 	for (ASTConditionalAndExpression element : andNodes) {
422 	    children += element.jjtGetNumChildren();
423 	    children--;
424 	}
425 
426         LOGGER.exiting(CLASS_NAME,"visit(ASTExpression)", children );
427 	return children;
428     }
429 
430     @Override
431     public Object[] getViolationParameters(DataPoint point) {
432 	return new String[] { ((ExecutableCode) point.getNode()).getMethodName(),
433 		String.valueOf((int) point.getScore()) };
434     }
435 }