View Javadoc

1   /**
2    * BSD-style license; for more info see http://pmd.sourceforge.net/license.html
3    */
4   package net.sourceforge.pmd.lang.dfa;
5   
6   import java.util.List;
7   import java.util.logging.Level;
8   import java.util.logging.Logger;
9   
10  import net.sourceforge.pmd.lang.DataFlowHandler;
11  import net.sourceforge.pmd.lang.ast.Node;
12  
13  /**
14   * @author raik
15   *         Links data flow nodes to each other.
16   */
17  public class Linker {
18      private final static Logger LOGGER = Logger.getLogger(Linker.class.getName());
19      private final static String CLASS_NAME = Linker.class.getCanonicalName();
20  
21      private final DataFlowHandler dataFlowHandler;
22      private List<StackObject> braceStack;
23      private List<StackObject> continueBreakReturnStack;
24  
25      public Linker(DataFlowHandler dataFlowHandler, List<StackObject> braceStack, List<StackObject> continueBreakReturnStack) {
26  	this.dataFlowHandler = dataFlowHandler;
27  	this.braceStack = braceStack;
28  	this.continueBreakReturnStack = continueBreakReturnStack;
29      }
30  
31      /**
32       * Creates all the links between the data flow nodes.
33       */
34      public void computePaths() throws LinkerException, SequenceException {
35          LOGGER.entering(CLASS_NAME,"computePaths");
36  	// Returns true if there are more sequences, computes the first and
37  	// the last index of the sequence.
38          LOGGER.fine("SequenceChecking continueBreakReturnStack elements");
39  	SequenceChecker sc = new SequenceChecker(braceStack);
40  	while (!sc.run()) {
41  		if (LOGGER.isLoggable(Level.FINE)) {
42            LOGGER.fine("After sc.run - starting Sequence checking loop with firstIndex=" + sc.getFirstIndex() 
43                        + ", lastIndex " + sc.getLastIndex() 
44                        +" with this StackList "+dump("braceStack",braceStack)
45                       );
46  		}
47  	    if (sc.getFirstIndex() < 0 || sc.getLastIndex() < 0) {
48                  LOGGER.severe("Sequence Checker problem: getFirstIndex()==" 
49                                + sc.getFirstIndex() + ", getLastIndex()==" + sc.getLastIndex() 
50                               );
51  		throw new SequenceException("computePaths(): return index <  0");
52  	    }
53  
54  	    StackObject firstStackObject = braceStack.get(sc.getFirstIndex());
55  
56              LOGGER.fine("Checking first braceStack element of type=="+ NodeType.stringFromType(firstStackObject.getType()) );
57  	    switch (firstStackObject.getType()) {
58  	    case NodeType.IF_EXPR:
59                  LOGGER.finest("IF_EXPR");
60  		int x = sc.getLastIndex() - sc.getFirstIndex();
61  		if (x == 2) {
62  		    this.computeIf(sc.getFirstIndex(), sc.getFirstIndex() + 1, sc.getLastIndex());
63  		} else if (x == 1) {
64  		    this.computeIf(sc.getFirstIndex(), sc.getLastIndex());
65  		} else {
66                      LOGGER.severe("Error - computePaths 1");
67  		}
68  		break;
69  
70  	    case NodeType.WHILE_EXPR:
71                  LOGGER.finest("WHILE_EXPR");
72  		this.computeWhile(sc.getFirstIndex(), sc.getLastIndex());
73  		break;
74  
75  	    case NodeType.SWITCH_START:
76                  LOGGER.finest("SWITCH_START");
77  		this.computeSwitch(sc.getFirstIndex(), sc.getLastIndex());
78  		break;
79  
80  	    case NodeType.FOR_INIT:
81  	    case NodeType.FOR_EXPR:
82  	    case NodeType.FOR_UPDATE:
83  	    case NodeType.FOR_BEFORE_FIRST_STATEMENT:
84                  LOGGER.finest("FOR_EXPR");
85  		this.computeFor(sc.getFirstIndex(), sc.getLastIndex());
86  		break;
87  
88  	    case NodeType.DO_BEFORE_FIRST_STATEMENT:
89                  LOGGER.finest("DO_BEFORE_FIRST_STATEMENT");
90  		this.computeDo(sc.getFirstIndex(), sc.getLastIndex());
91  		break;
92  
93  	    default:
94  	    }
95  
96              LOGGER.finest("Removing braces from Last to first: " + sc.getLastIndex()  + " to " + sc.getFirstIndex());
97  	    for (int y = sc.getLastIndex(); y >= sc.getFirstIndex(); y--) {
98                  LOGGER.finest("Removing brace : " + y );
99  		braceStack.remove(y);
100               }
101           LOGGER.fine("Completed Sequence checking loop" + braceStack  );
102 	}
103         if (LOGGER.isLoggable(Level.FINER))
104         {
105           LOGGER.log(Level.FINER, "After Sequence checking loop : remaining braces=={0}",
106               dump("braceStack", braceStack));
107         }
108 
109 
110         LOGGER.fine("Processing continueBreakReturnStack elements");
111 	while (!continueBreakReturnStack.isEmpty()) {
112           LOGGER.fine("Starting continueBreakReturnStack processing loop" );
113 	    StackObject stackObject = continueBreakReturnStack.get(0);
114 	    DataFlowNode node = stackObject.getDataFlowNode();
115 
116 	    switch (stackObject.getType()) {
117 	    case NodeType.THROW_STATEMENT:
118                 LOGGER.finest("CBR: THROW_STATEMENT");
119 		// do the same like a return
120 	    case NodeType.RETURN_STATEMENT:
121                 LOGGER.finest("CBR: RETURN_STATEMENT");
122 		// remove all children (should contain only one child)
123 		node.removePathToChild(node.getChildren().get(0));
124 		DataFlowNode lastNode = node.getFlow().get(node.getFlow().size() - 1);
125 		node.addPathToChild(lastNode);
126 		continueBreakReturnStack.remove(0);
127 		break;
128 	    case NodeType.BREAK_STATEMENT:
129                 LOGGER.finest("CBR: BREAK_STATEMENT");
130 		DataFlowNode last = getNodeToBreakStatement(node);
131 		node.removePathToChild(node.getChildren().get(0));
132 		node.addPathToChild(last);
133 		continueBreakReturnStack.remove(0);
134 		break;
135 
136 	    case NodeType.CONTINUE_STATEMENT:
137                 LOGGER.finest("CBR: CONTINUE_STATEMENT");
138 		//List cList = node.getFlow();
139 		/* traverse up the tree and find the first loop start node
140 		 */
141 		/*
142 		                               for(int i = cList.indexOf(node)-1;i>=0;i--) {
143 		                                   IDataFlowNode n = (IDataFlowNode)cList.get(i);
144 
145 		                                   if(n.isType(NodeType.FOR_UPDATE) ||
146 		                                               n.isType(NodeType.FOR_EXPR) ||
147 		                                               n.isType(NodeType.WHILE_EXPR)) {
148 		*/
149 		/*
150 		 * while(..) {
151 		 *              while(...) {
152 		 *                      ...
153 		 *              }
154 		 *              continue;
155 		 * }
156 		 *
157 		 * Without this Expression he continues the second
158 		 * WHILE loop. The continue statement and the while loop
159 		 * have to be in different scopes.
160 		 *
161 		 * TODO An error occurs if "continue" is even nested in
162 		 * scopes other than local loop scopes, like "if".
163 		 * The result is, that the data flow isn't build right
164 		 * and the pathfinder runs in invinity loop.
165 		 * */
166 		/*                                     if(n.getNode().getScope().equals(node.getNode().getScope())) {
167 		                                               System.err.println("equals");
168 		                                               continue;
169 		                                       }
170 		                                       else {
171 		                                               System.err.println("don't equals");
172 		                                       }
173 
174 		                                               //remove all children (should contain only one child)
175 		                                       node.removePathToChild((IDataFlowNode)node.getChildren().get(0));
176 
177 		                                       node.addPathToChild(n);
178 		                                       cbrStack.remove(0);
179 		                                       break;
180 
181 		                                   }else if(n.isType(NodeType.DO_BEFOR_FIRST_STATEMENT)) {
182 
183 		                                       IDataFlowNode inode = (IDataFlowNode)n.getFlow().get(n.getIndex()1);
184 
185 		                                       for(int j=0;j<inode.getParents().size();j) {
186 		                                               IDataFlowNode parent = (IDataFlowNode)inode.getParents().get(j);
187 
188 		                                               if(parent.isType(NodeType.DO_EXPR)) {
189 		                                                       node.removePathToChild((IDataFlowNode)node.getChildren().get(0));
190 		                                               node.addPathToChild(parent);
191 
192 		                                               cbrStack.remove(0);
193 		                                                       break;
194 		                                               }
195 		                                       }
196 		                                       break;
197 		                                   }
198 		                               }
199 		*/
200 		continueBreakReturnStack.remove(0); // delete this statement if you uncomment the stuff above
201 		break;
202 		default:
203                 LOGGER.finest("CBR: default");
204 		    // Do nothing
205 		    break;
206 	    }
207           LOGGER.fine("Completed continueBreakReturnStack processing loop" );
208 	}
209         LOGGER.exiting(CLASS_NAME,"computePaths");
210     }
211 
212     private DataFlowNode getNodeToBreakStatement(DataFlowNode node) {
213         LOGGER.entering(CLASS_NAME,"getNodeToBreakStatement");
214 	// What about breaks to labels above if statements?
215 	List<DataFlowNode> bList = node.getFlow();
216 	int findEnds = 1; // ignore ends of other for's while's etc.
217 
218 	// find out index of the node where the path goes to after the break
219 	int index = bList.indexOf(node);
220 	for (; index < bList.size() - 2; index++) {
221 	    DataFlowNode n = bList.get(index);
222 	    if (n.isType(NodeType.DO_EXPR) || n.isType(NodeType.FOR_INIT) || n.isType(NodeType.WHILE_EXPR)
223 		    || n.isType(NodeType.SWITCH_START)) {
224 		findEnds++;
225 	    }
226 	    if (n.isType(NodeType.WHILE_LAST_STATEMENT) || n.isType(NodeType.SWITCH_END) || n.isType(NodeType.FOR_END)
227 		    || n.isType(NodeType.DO_EXPR)) {
228 		if (findEnds > 1) {
229 		    // thats not the right node
230 		    findEnds--;
231 		} else {
232 		    break;
233 		}
234 	    }
235 
236 	    if (n.isType(NodeType.LABEL_LAST_STATEMENT)) {
237 		Node parentNode = n.getNode().getFirstParentOfType(dataFlowHandler.getLabelStatementNodeClass());
238 		if (parentNode == null) {
239 		    break;
240 		} else {
241 		    String label = node.getNode().getImage();
242 		    if (label == null || label.equals(parentNode.getImage())) {
243 			node.removePathToChild(node.getChildren().get(0));
244 			DataFlowNode last = bList.get(index + 1);
245 			node.addPathToChild(last);
246 			break;
247 		    }
248 		}
249 	    }
250 	}
251         LOGGER.exiting(CLASS_NAME,"getNodeToBreakSttement");
252 	return node.getFlow().get(index + 1);
253     }
254 
255     private void computeDo(int first, int last) {
256         LOGGER.entering(CLASS_NAME,"computeDo");
257 	DataFlowNode doSt = this.braceStack.get(first).getDataFlowNode();
258 	DataFlowNode doExpr = this.braceStack.get(last).getDataFlowNode();
259 	DataFlowNode doFirst = doSt.getFlow().get(doSt.getIndex() + 1);
260 	if (doFirst.getIndex() != doExpr.getIndex()) {
261 	    doExpr.addPathToChild(doFirst);
262 	}
263         LOGGER.exiting(CLASS_NAME,"computeDo");
264     }
265 
266     private void computeFor(int firstIndex, int lastIndex) {
267         LOGGER.entering(CLASS_NAME,"computeFor");
268 	DataFlowNode fExpr = null;
269 	DataFlowNode fUpdate = null;
270 	DataFlowNode fSt = null;
271 	DataFlowNode fEnd = null;
272 	boolean isUpdate = false;
273 
274 	for (int i = firstIndex; i <= lastIndex; i++) {
275 	    StackObject so = this.braceStack.get(i);
276 	    DataFlowNode node = so.getDataFlowNode();
277 
278 	    if (so.getType() == NodeType.FOR_EXPR) {
279 		fExpr = node;
280 	    } else if (so.getType() == NodeType.FOR_UPDATE) {
281 		fUpdate = node;
282 		isUpdate = true;
283 	    } else if (so.getType() == NodeType.FOR_BEFORE_FIRST_STATEMENT) {
284 		fSt = node;
285 	    } else if (so.getType() == NodeType.FOR_END) {
286 		fEnd = node;
287 	    }
288 	}
289 	DataFlowNode end = fEnd.getFlow().get(fEnd.getIndex() + 1);
290 
291 	DataFlowNode firstSt = fSt.getChildren().get(0);
292 
293 	if (isUpdate) {
294 	    if (fSt.getIndex() != fEnd.getIndex()) {
295 		end.reverseParentPathsTo(fUpdate);
296 		fExpr.removePathToChild(fUpdate);
297 		fUpdate.addPathToChild(fExpr);
298 		fUpdate.removePathToChild(firstSt);
299 		fExpr.addPathToChild(firstSt);
300 		fExpr.addPathToChild(end);
301 	    } else {
302 		fSt.removePathToChild(end);
303 		fExpr.removePathToChild(fUpdate);
304 		fUpdate.addPathToChild(fExpr);
305 		fExpr.addPathToChild(fUpdate);
306 		fExpr.addPathToChild(end);
307 	    }
308 	} else {
309 	    if (fSt.getIndex() != fEnd.getIndex()) {
310 		end.reverseParentPathsTo(fExpr);
311 		fExpr.addPathToChild(end);
312 	    }
313 	}
314         LOGGER.exiting(CLASS_NAME,"computeFor");
315     }
316 
317     private void computeSwitch(int firstIndex, int lastIndex) {
318         LOGGER.entering(CLASS_NAME,"computeSwitch" );
319 
320 	int diff = lastIndex - firstIndex;
321 	boolean defaultStatement = false;
322 
323 	DataFlowNode sStart = this.braceStack.get(firstIndex).getDataFlowNode();
324 	DataFlowNode sEnd = this.braceStack.get(lastIndex).getDataFlowNode();
325 	DataFlowNode end = sEnd.getChildren().get(0);
326 
327         LOGGER.fine(
328                      "Stack(sStart)=>" + sStart
329                      +",Stack(sEnd)=>" + sEnd
330                      +",end=>" + end
331                    );
332 
333 	for (int i = 0; i < diff - 2; i++) {
334 	    StackObject so = this.braceStack.get(firstIndex + 2 + i);
335 	    DataFlowNode node = so.getDataFlowNode();
336 
337             LOGGER.fine( "so(" + (firstIndex + 2 + i) + ")=>" + so 
338                          +" has  dfn=>" + node 
339                          +" with first child =>" + node.getChildren().get(0)
340                        );
341 	    sStart.addPathToChild(node.getChildren().get(0));
342 
343 	    if (so.getType() == NodeType.SWITCH_LAST_DEFAULT_STATEMENT) {
344 		defaultStatement = true;
345 	    }
346 	}
347 
348 	if (!defaultStatement) {
349 	    sStart.addPathToChild(end);
350 	}
351         LOGGER.exiting(CLASS_NAME,"computeSwitch");
352     }
353 
354     private void computeWhile(int first, int last) {
355         LOGGER.entering(CLASS_NAME,"computeWhile with first and last of" 
356                         + first + "," + last
357                         );
358 	DataFlowNode wStart = this.braceStack.get(first).getDataFlowNode();
359 	DataFlowNode wEnd = this.braceStack.get(last).getDataFlowNode();
360 
361 	DataFlowNode end = wEnd.getFlow().get(wEnd.getIndex() + 1);
362 
363 	if (wStart.getIndex() != wEnd.getIndex()) {
364 	    end.reverseParentPathsTo(wStart);
365 	    wStart.addPathToChild(end);
366 	}
367         LOGGER.exiting(CLASS_NAME,"computeWhile");
368     }
369 
370     private void computeIf(int first, int second, int last) {
371         LOGGER.entering(CLASS_NAME,"computeIf(3)",first+","+ second +","+ last);
372 	DataFlowNode ifStart = this.braceStack.get(first).getDataFlowNode();
373 	DataFlowNode ifEnd = this.braceStack.get(second).getDataFlowNode();
374 	DataFlowNode elseEnd = this.braceStack.get(last).getDataFlowNode();
375 
376 	DataFlowNode elseStart = ifEnd.getFlow().get(ifEnd.getIndex() + 1);
377 	DataFlowNode end = elseEnd.getFlow().get(elseEnd.getIndex() + 1);
378 
379         LOGGER.log(Level.FINEST, "If ifstart={0}, ifEnd={1}, elseEnd={2}, elseStart={3}, end={4}"
380                    , new Object[]{ifStart, ifEnd, elseEnd, elseStart, end}
381                   );
382 
383 	// if if-statement and else-statement contains statements or expressions
384 	if (ifStart.getIndex() != ifEnd.getIndex() && ifEnd.getIndex() != elseEnd.getIndex()) {
385 	    elseStart.reverseParentPathsTo(end);
386 	    ifStart.addPathToChild(elseStart);
387 	}
388 	// if only if-statement contains no expressions
389 	else if (ifStart.getIndex() == ifEnd.getIndex() && ifEnd.getIndex() != elseEnd.getIndex()) {
390 	    ifStart.addPathToChild(end);
391 	}
392 	// if only else-statement contains no expressions
393 	else if (ifEnd.getIndex() == elseEnd.getIndex() && ifStart.getIndex() != ifEnd.getIndex()) {
394 	    ifStart.addPathToChild(end);
395 	}
396         LOGGER.exiting(CLASS_NAME,"computeIf(3)");
397     }
398 
399     private void computeIf(int first, int last) {
400         LOGGER.entering(CLASS_NAME,"computeIf(2)");
401 	DataFlowNode ifStart = this.braceStack.get(first).getDataFlowNode();
402 	DataFlowNode ifEnd = this.braceStack.get(last).getDataFlowNode();
403 
404 	// only if the if-statement contains another Statement or Expression
405 	if (ifStart.getIndex() != ifEnd.getIndex()) {
406 	    DataFlowNode end = ifEnd.getFlow().get(ifEnd.getIndex() + 1);
407 	    ifStart.addPathToChild(end);
408 	}
409         LOGGER.exiting(CLASS_NAME,"computeIf(2)");
410     }
411     /**
412      * 
413      * @return formatted dump of the StackList
414      */
415     private static String dump(String description, List<StackObject>  stackList) {
416       StringBuilder stringDump = new StringBuilder("Stack List (");
417       stringDump.append(description).append(") ListDump:\n");
418       for (StackObject stackObject  : stackList )
419       {
420 	stringDump.append ('\n').append(stackObject.toString());
421       }
422       return stringDump.toString();
423     }
424 
425 
426 }