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