001 /**
002 * BSD-style license; for more info see http://pmd.sourceforge.net/license.html
003 */
004 package net.sourceforge.pmd.lang.dfa;
005
006 import java.util.List;
007
008 import net.sourceforge.pmd.lang.DataFlowHandler;
009 import net.sourceforge.pmd.lang.ast.Node;
010
011 /**
012 * @author raik
013 * Links data flow nodes to each other.
014 */
015 public class Linker {
016
017 private final DataFlowHandler dataFlowHandler;
018 private List<StackObject> braceStack;
019 private List<StackObject> continueBreakReturnStack;
020
021 public Linker(DataFlowHandler dataFlowHandler, List<StackObject> braceStack, List<StackObject> continueBreakReturnStack) {
022 this.dataFlowHandler = dataFlowHandler;
023 this.braceStack = braceStack;
024 this.continueBreakReturnStack = continueBreakReturnStack;
025 }
026
027 /**
028 * Creates all the links between the data flow nodes.
029 */
030 public void computePaths() throws LinkerException, SequenceException {
031 // Returns true if there are more sequences, computes the first and
032 // the last index of the sequence.
033 SequenceChecker sc = new SequenceChecker(braceStack);
034 while (!sc.run()) {
035 if (sc.getFirstIndex() < 0 || sc.getLastIndex() < 0) {
036 throw new SequenceException("computePaths(): return index < 0");
037 }
038
039 StackObject firstStackObject = braceStack.get(sc.getFirstIndex());
040
041 switch (firstStackObject.getType()) {
042 case NodeType.IF_EXPR:
043 int x = sc.getLastIndex() - sc.getFirstIndex();
044 if (x == 2) {
045 this.computeIf(sc.getFirstIndex(), sc.getFirstIndex() + 1, sc.getLastIndex());
046 } else if (x == 1) {
047 this.computeIf(sc.getFirstIndex(), sc.getLastIndex());
048 } else {
049 System.out.println("Error - computePaths 1");
050 }
051 break;
052
053 case NodeType.WHILE_EXPR:
054 this.computeWhile(sc.getFirstIndex(), sc.getLastIndex());
055 break;
056
057 case NodeType.SWITCH_START:
058 this.computeSwitch(sc.getFirstIndex(), sc.getLastIndex());
059 break;
060
061 case NodeType.FOR_INIT:
062 case NodeType.FOR_EXPR:
063 case NodeType.FOR_UPDATE:
064 case NodeType.FOR_BEFORE_FIRST_STATEMENT:
065 this.computeFor(sc.getFirstIndex(), sc.getLastIndex());
066 break;
067
068 case NodeType.DO_BEFORE_FIRST_STATEMENT:
069 this.computeDo(sc.getFirstIndex(), sc.getLastIndex());
070 break;
071
072 default:
073 }
074
075 for (int y = sc.getLastIndex(); y >= sc.getFirstIndex(); y--) {
076 braceStack.remove(y);
077 }
078 }
079
080 while (!continueBreakReturnStack.isEmpty()) {
081 StackObject stackObject = continueBreakReturnStack.get(0);
082 DataFlowNode node = stackObject.getDataFlowNode();
083
084 switch (stackObject.getType()) {
085 case NodeType.THROW_STATEMENT:
086 // do the same like a return
087 case NodeType.RETURN_STATEMENT:
088 // remove all children (should contain only one child)
089 node.removePathToChild(node.getChildren().get(0));
090 DataFlowNode lastNode = node.getFlow().get(node.getFlow().size() - 1);
091 node.addPathToChild(lastNode);
092 continueBreakReturnStack.remove(0);
093 break;
094 case NodeType.BREAK_STATEMENT:
095 DataFlowNode last = getNodeToBreakStatement(node);
096 node.removePathToChild(node.getChildren().get(0));
097 node.addPathToChild(last);
098 continueBreakReturnStack.remove(0);
099 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 }
|