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   
8   import net.sourceforge.pmd.lang.DataFlowHandler;
9   import net.sourceforge.pmd.lang.ast.Node;
10  
11  /**
12   * @author raik
13   *         Links data flow nodes to each other.
14   */
15  public class Linker {
16  
17      private final DataFlowHandler dataFlowHandler;
18      private List<StackObject> braceStack;
19      private List<StackObject> continueBreakReturnStack;
20  
21      public Linker(DataFlowHandler dataFlowHandler, List<StackObject> braceStack, List<StackObject> continueBreakReturnStack) {
22  	this.dataFlowHandler = dataFlowHandler;
23  	this.braceStack = braceStack;
24  	this.continueBreakReturnStack = continueBreakReturnStack;
25      }
26  
27      /**
28       * Creates all the links between the data flow nodes.
29       */
30      public void computePaths() throws LinkerException, SequenceException {
31  	// Returns true if there are more sequences, computes the first and
32  	// the last index of the sequence.
33  	SequenceChecker sc = new SequenceChecker(braceStack);
34  	while (!sc.run()) {
35  	    if (sc.getFirstIndex() < 0 || sc.getLastIndex() < 0) {
36  		throw new SequenceException("computePaths(): return index <  0");
37  	    }
38  
39  	    StackObject firstStackObject = braceStack.get(sc.getFirstIndex());
40  
41  	    switch (firstStackObject.getType()) {
42  	    case NodeType.IF_EXPR:
43  		int x = sc.getLastIndex() - sc.getFirstIndex();
44  		if (x == 2) {
45  		    this.computeIf(sc.getFirstIndex(), sc.getFirstIndex() + 1, sc.getLastIndex());
46  		} else if (x == 1) {
47  		    this.computeIf(sc.getFirstIndex(), sc.getLastIndex());
48  		} else {
49  		    System.out.println("Error - computePaths 1");
50  		}
51  		break;
52  
53  	    case NodeType.WHILE_EXPR:
54  		this.computeWhile(sc.getFirstIndex(), sc.getLastIndex());
55  		break;
56  
57  	    case NodeType.SWITCH_START:
58  		this.computeSwitch(sc.getFirstIndex(), sc.getLastIndex());
59  		break;
60  
61  	    case NodeType.FOR_INIT:
62  	    case NodeType.FOR_EXPR:
63  	    case NodeType.FOR_UPDATE:
64  	    case NodeType.FOR_BEFORE_FIRST_STATEMENT:
65  		this.computeFor(sc.getFirstIndex(), sc.getLastIndex());
66  		break;
67  
68  	    case NodeType.DO_BEFORE_FIRST_STATEMENT:
69  		this.computeDo(sc.getFirstIndex(), sc.getLastIndex());
70  		break;
71  
72  	    default:
73  	    }
74  
75  	    for (int y = sc.getLastIndex(); y >= sc.getFirstIndex(); y--) {
76  		braceStack.remove(y);
77  	    }
78  	}
79  
80  	while (!continueBreakReturnStack.isEmpty()) {
81  	    StackObject stackObject = continueBreakReturnStack.get(0);
82  	    DataFlowNode node = stackObject.getDataFlowNode();
83  
84  	    switch (stackObject.getType()) {
85  	    case NodeType.THROW_STATEMENT:
86  		// do the same like a return
87  	    case NodeType.RETURN_STATEMENT:
88  		// remove all children (should contain only one child)
89  		node.removePathToChild(node.getChildren().get(0));
90  		DataFlowNode lastNode = node.getFlow().get(node.getFlow().size() - 1);
91  		node.addPathToChild(lastNode);
92  		continueBreakReturnStack.remove(0);
93  		break;
94  	    case NodeType.BREAK_STATEMENT:
95  		DataFlowNode last = getNodeToBreakStatement(node);
96  		node.removePathToChild(node.getChildren().get(0));
97  		node.addPathToChild(last);
98  		continueBreakReturnStack.remove(0);
99  		break;
100 
101 	    case NodeType.CONTINUE_STATEMENT:
102 		//List cList = node.getFlow();
103 		/* traverse up the tree and find the first loop start node
104 		 */
105 		/*
106 		                               for(int i = cList.indexOf(node)-1;i>=0;i--) {
107 		                                   IDataFlowNode n = (IDataFlowNode)cList.get(i);
108 
109 		                                   if(n.isType(NodeType.FOR_UPDATE) ||
110 		                                               n.isType(NodeType.FOR_EXPR) ||
111 		                                               n.isType(NodeType.WHILE_EXPR)) {
112 		*/
113 		/*
114 		 * while(..) {
115 		 *              while(...) {
116 		 *                      ...
117 		 *              }
118 		 *              continue;
119 		 * }
120 		 *
121 		 * Without this Expression he continues the second
122 		 * WHILE loop. The continue statement and the while loop
123 		 * have to be in different scopes.
124 		 *
125 		 * TODO An error occurs if "continue" is even nested in
126 		 * scopes other than local loop scopes, like "if".
127 		 * The result is, that the data flow isn't build right
128 		 * and the pathfinder runs in invinity loop.
129 		 * */
130 		/*                                     if(n.getNode().getScope().equals(node.getNode().getScope())) {
131 		                                               System.err.println("equals");
132 		                                               continue;
133 		                                       }
134 		                                       else {
135 		                                               System.err.println("don't equals");
136 		                                       }
137 
138 		                                               //remove all children (should contain only one child)
139 		                                       node.removePathToChild((IDataFlowNode)node.getChildren().get(0));
140 
141 		                                       node.addPathToChild(n);
142 		                                       cbrStack.remove(0);
143 		                                       break;
144 
145 		                                   }else if(n.isType(NodeType.DO_BEFOR_FIRST_STATEMENT)) {
146 
147 		                                       IDataFlowNode inode = (IDataFlowNode)n.getFlow().get(n.getIndex()1);
148 
149 		                                       for(int j=0;j<inode.getParents().size();j) {
150 		                                               IDataFlowNode parent = (IDataFlowNode)inode.getParents().get(j);
151 
152 		                                               if(parent.isType(NodeType.DO_EXPR)) {
153 		                                                       node.removePathToChild((IDataFlowNode)node.getChildren().get(0));
154 		                                               node.addPathToChild(parent);
155 
156 		                                               cbrStack.remove(0);
157 		                                                       break;
158 		                                               }
159 		                                       }
160 		                                       break;
161 		                                   }
162 		                               }
163 		*/
164 		continueBreakReturnStack.remove(0); // delete this statement if you uncomment the stuff above
165 		break;
166 		default:
167 		    // Do nothing
168 		    break;
169 	    }
170 	}
171     }
172 
173     private DataFlowNode getNodeToBreakStatement(DataFlowNode node) {
174 	// What about breaks to labels above if statements?
175 	List<DataFlowNode> bList = node.getFlow();
176 	int findEnds = 1; // ignore ends of other for's while's etc.
177 
178 	// find out index of the node where the path goes to after the break
179 	int index = bList.indexOf(node);
180 	for (; index < bList.size() - 2; index++) {
181 	    DataFlowNode n = bList.get(index);
182 	    if (n.isType(NodeType.DO_EXPR) || n.isType(NodeType.FOR_INIT) || n.isType(NodeType.WHILE_EXPR)
183 		    || n.isType(NodeType.SWITCH_START)) {
184 		findEnds++;
185 	    }
186 	    if (n.isType(NodeType.WHILE_LAST_STATEMENT) || n.isType(NodeType.SWITCH_END) || n.isType(NodeType.FOR_END)
187 		    || n.isType(NodeType.DO_EXPR)) {
188 		if (findEnds > 1) {
189 		    // thats not the right node
190 		    findEnds--;
191 		} else {
192 		    break;
193 		}
194 	    }
195 
196 	    if (n.isType(NodeType.LABEL_LAST_STATEMENT)) {
197 		Node parentNode = n.getNode().getFirstParentOfType(dataFlowHandler.getLabelStatementNodeClass());
198 		if (parentNode == null) {
199 		    break;
200 		} else {
201 		    String label = node.getNode().getImage();
202 		    if (label == null || label.equals(parentNode.getImage())) {
203 			node.removePathToChild(node.getChildren().get(0));
204 			DataFlowNode last = bList.get(index + 1);
205 			node.addPathToChild(last);
206 			break;
207 		    }
208 		}
209 	    }
210 	}
211 	return node.getFlow().get(index + 1);
212     }
213 
214     private void computeDo(int first, int last) {
215 	DataFlowNode doSt = this.braceStack.get(first).getDataFlowNode();
216 	DataFlowNode doExpr = this.braceStack.get(last).getDataFlowNode();
217 	DataFlowNode doFirst = doSt.getFlow().get(doSt.getIndex() + 1);
218 	if (doFirst.getIndex() != doExpr.getIndex()) {
219 	    doExpr.addPathToChild(doFirst);
220 	}
221     }
222 
223     private void computeFor(int firstIndex, int lastIndex) {
224 	DataFlowNode fExpr = null;
225 	DataFlowNode fUpdate = null;
226 	DataFlowNode fSt = null;
227 	DataFlowNode fEnd = null;
228 	boolean isUpdate = false;
229 
230 	for (int i = firstIndex; i <= lastIndex; i++) {
231 	    StackObject so = this.braceStack.get(i);
232 	    DataFlowNode node = so.getDataFlowNode();
233 
234 	    if (so.getType() == NodeType.FOR_EXPR) {
235 		fExpr = node;
236 	    } else if (so.getType() == NodeType.FOR_UPDATE) {
237 		fUpdate = node;
238 		isUpdate = true;
239 	    } else if (so.getType() == NodeType.FOR_BEFORE_FIRST_STATEMENT) {
240 		fSt = node;
241 	    } else if (so.getType() == NodeType.FOR_END) {
242 		fEnd = node;
243 	    }
244 	}
245 	DataFlowNode end = fEnd.getFlow().get(fEnd.getIndex() + 1);
246 
247 	DataFlowNode firstSt = fSt.getChildren().get(0);
248 
249 	if (isUpdate) {
250 	    if (fSt.getIndex() != fEnd.getIndex()) {
251 		end.reverseParentPathsTo(fUpdate);
252 		fExpr.removePathToChild(fUpdate);
253 		fUpdate.addPathToChild(fExpr);
254 		fUpdate.removePathToChild(firstSt);
255 		fExpr.addPathToChild(firstSt);
256 		fExpr.addPathToChild(end);
257 	    } else {
258 		fSt.removePathToChild(end);
259 		fExpr.removePathToChild(fUpdate);
260 		fUpdate.addPathToChild(fExpr);
261 		fExpr.addPathToChild(fUpdate);
262 		fExpr.addPathToChild(end);
263 	    }
264 	} else {
265 	    if (fSt.getIndex() != fEnd.getIndex()) {
266 		end.reverseParentPathsTo(fExpr);
267 		fExpr.addPathToChild(end);
268 	    }
269 	}
270     }
271 
272     private void computeSwitch(int firstIndex, int lastIndex) {
273 
274 	int diff = lastIndex - firstIndex;
275 	boolean defaultStatement = false;
276 
277 	DataFlowNode sStart = this.braceStack.get(firstIndex).getDataFlowNode();
278 	DataFlowNode sEnd = this.braceStack.get(lastIndex).getDataFlowNode();
279 	DataFlowNode end = sEnd.getChildren().get(0);
280 
281 	for (int i = 0; i < diff - 2; i++) {
282 	    StackObject so = this.braceStack.get(firstIndex + 2 + i);
283 	    DataFlowNode node = so.getDataFlowNode();
284 
285 	    sStart.addPathToChild(node.getChildren().get(0));
286 
287 	    if (so.getType() == NodeType.SWITCH_LAST_DEFAULT_STATEMENT) {
288 		defaultStatement = true;
289 	    }
290 	}
291 
292 	if (!defaultStatement) {
293 	    sStart.addPathToChild(end);
294 	}
295     }
296 
297     private void computeWhile(int first, int last) {
298 	DataFlowNode wStart = this.braceStack.get(first).getDataFlowNode();
299 	DataFlowNode wEnd = this.braceStack.get(last).getDataFlowNode();
300 
301 	DataFlowNode end = wEnd.getFlow().get(wEnd.getIndex() + 1);
302 
303 	if (wStart.getIndex() != wEnd.getIndex()) {
304 	    end.reverseParentPathsTo(wStart);
305 	    wStart.addPathToChild(end);
306 	}
307     }
308 
309     private void computeIf(int first, int second, int last) {
310 	DataFlowNode ifStart = this.braceStack.get(first).getDataFlowNode();
311 	DataFlowNode ifEnd = this.braceStack.get(second).getDataFlowNode();
312 	DataFlowNode elseEnd = this.braceStack.get(last).getDataFlowNode();
313 
314 	DataFlowNode elseStart = ifEnd.getFlow().get(ifEnd.getIndex() + 1);
315 	DataFlowNode end = elseEnd.getFlow().get(elseEnd.getIndex() + 1);
316 
317 	// if if-statement and else-statement contains statements or expressions
318 	if (ifStart.getIndex() != ifEnd.getIndex() && ifEnd.getIndex() != elseEnd.getIndex()) {
319 	    elseStart.reverseParentPathsTo(end);
320 	    ifStart.addPathToChild(elseStart);
321 	}
322 	// if only if-statement contains no expressions
323 	else if (ifStart.getIndex() == ifEnd.getIndex() && ifEnd.getIndex() != elseEnd.getIndex()) {
324 	    ifStart.addPathToChild(end);
325 	}
326 	// if only else-statement contains no expressions
327 	else if (ifEnd.getIndex() == elseEnd.getIndex() && ifStart.getIndex() != ifEnd.getIndex()) {
328 	    ifStart.addPathToChild(end);
329 	}
330     }
331 
332     private void computeIf(int first, int last) {
333 	DataFlowNode ifStart = this.braceStack.get(first).getDataFlowNode();
334 	DataFlowNode ifEnd = this.braceStack.get(last).getDataFlowNode();
335 
336 	// only if the if-statement contains another Statement or Expression
337 	if (ifStart.getIndex() != ifEnd.getIndex()) {
338 	    DataFlowNode end = ifEnd.getFlow().get(ifEnd.getIndex() + 1);
339 	    ifStart.addPathToChild(end);
340 	}
341     }
342 }