1
2
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.RETURN_STATEMENT:
84
85 node.removePathToChild((IDataFlowNode) node.getChildren().get(0));
86 IDataFlowNode lastNode = (IDataFlowNode) node.getFlow().get(node.getFlow().size() - 1);
87 node.addPathToChild(lastNode);
88 continueBreakReturnStack.remove(0);
89 break;
90 case NodeType.BREAK_STATEMENT:
91 IDataFlowNode last = getNodeToBreakStatement(node);
92 node.removePathToChild((IDataFlowNode) node.getChildren().get(0));
93 node.addPathToChild(last);
94 continueBreakReturnStack.remove(0);
95 break;
96
97 case NodeType.CONTINUE_STATEMENT:
98
99
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 continueBreakReturnStack.remove(0);
160 }
161 }
162 }
163
164 private IDataFlowNode getNodeToBreakStatement(IDataFlowNode node) {
165
166 List bList = node.getFlow();
167 int findEnds = 1;
168
169
170
171 int index = bList.indexOf(node);
172 for (; index < bList.size()-2; index++) {
173 IDataFlowNode n = (IDataFlowNode) bList.get(index);
174 if (n.isType(NodeType.DO_EXPR) ||
175 n.isType(NodeType.FOR_INIT) ||
176 n.isType(NodeType.WHILE_EXPR) ||
177 n.isType(NodeType.SWITCH_START)) {
178 findEnds++;
179 }
180 if (n.isType(NodeType.WHILE_LAST_STATEMENT) ||
181 n.isType(NodeType.SWITCH_END) ||
182 n.isType(NodeType.FOR_END) ||
183 n.isType(NodeType.DO_EXPR)) {
184 if (findEnds > 1) {
185
186 findEnds--;
187 } else {
188 break;
189 }
190 }
191
192 if (n.isType(NodeType.LABEL_LAST_STATEMENT)) {
193 SimpleNode parentNode = (SimpleNode) n.getSimpleNode().getFirstParentOfType(ASTLabeledStatement.class);
194 if (parentNode == null) {
195 break;
196 } else {
197 String label = node.getSimpleNode().getImage();
198 if (label == null || label.equals(parentNode.getImage())) {
199 node.removePathToChild((IDataFlowNode) node.getChildren().get(0));
200 IDataFlowNode last = (IDataFlowNode) bList.get(index + 1);
201 node.addPathToChild(last);
202 break;
203 }
204 }
205 }
206 }
207 return (IDataFlowNode)node.getFlow().get(index+1);
208 }
209
210 private void computeDo(int first, int last) {
211 IDataFlowNode doSt = ((StackObject) this.braceStack.get(first)).getDataFlowNode();
212 IDataFlowNode doExpr = ((StackObject) this.braceStack.get(last)).getDataFlowNode();
213 IDataFlowNode doFirst = (IDataFlowNode) doSt.getFlow().get(doSt.getIndex() + 1);
214 if (doFirst.getIndex() != doExpr.getIndex()) {
215 doExpr.addPathToChild(doFirst);
216 }
217 }
218
219 private void computeFor(int firstIndex, int lastIndex) {
220 IDataFlowNode fExpr = null;
221 IDataFlowNode fUpdate = null;
222 IDataFlowNode fSt = null;
223 IDataFlowNode fEnd = null;
224 boolean isUpdate = false;
225
226 for (int i = firstIndex; i <= lastIndex; i++) {
227 StackObject so = (StackObject) this.braceStack.get(i);
228 IDataFlowNode node = so.getDataFlowNode();
229
230 if (so.getType() == NodeType.FOR_EXPR) {
231 fExpr = node;
232 } else if (so.getType() == NodeType.FOR_UPDATE) {
233 fUpdate = node;
234 isUpdate = true;
235 } else if (so.getType() == NodeType.FOR_BEFORE_FIRST_STATEMENT) {
236 fSt = node;
237 } else if (so.getType() == NodeType.FOR_END) {
238 fEnd = node;
239 }
240 }
241 IDataFlowNode end = (IDataFlowNode) fEnd.getFlow().get(fEnd.getIndex() + 1);
242
243 IDataFlowNode firstSt = (IDataFlowNode) fSt.getChildren().get(0);
244
245 if (isUpdate) {
246 if (fSt.getIndex() != fEnd.getIndex()) {
247 end.reverseParentPathsTo(fUpdate);
248 fExpr.removePathToChild(fUpdate);
249 fUpdate.addPathToChild(fExpr);
250 fUpdate.removePathToChild(firstSt);
251 fExpr.addPathToChild(firstSt);
252 fExpr.addPathToChild(end);
253 } else {
254 fSt.removePathToChild(end);
255 fExpr.removePathToChild(fUpdate);
256 fUpdate.addPathToChild(fExpr);
257 fExpr.addPathToChild(fUpdate);
258 fExpr.addPathToChild(end);
259 }
260 } else {
261 if (fSt.getIndex() != fEnd.getIndex()) {
262 end.reverseParentPathsTo(fExpr);
263 fExpr.addPathToChild(end);
264 }
265 }
266 }
267
268 private void computeSwitch(int firstIndex, int lastIndex) {
269
270 int diff = lastIndex - firstIndex;
271 boolean defaultStatement = false;
272
273 IDataFlowNode sStart = ((StackObject) this.braceStack.get(firstIndex)).getDataFlowNode();
274 IDataFlowNode sEnd = ((StackObject) this.braceStack.get(lastIndex)).getDataFlowNode();
275 IDataFlowNode end = (IDataFlowNode) sEnd.getChildren().get(0);
276
277 for (int i = 0; i < diff - 2; i++) {
278 StackObject so = (StackObject) this.braceStack.get(firstIndex + 2 + i);
279 IDataFlowNode node = so.getDataFlowNode();
280
281 sStart.addPathToChild((IDataFlowNode) node.getChildren().get(0));
282
283 if (so.getType() == NodeType.SWITCH_LAST_DEFAULT_STATEMENT)
284 defaultStatement = true;
285 }
286
287 if (!defaultStatement)
288 sStart.addPathToChild(end);
289 }
290
291 private void computeWhile(int first, int last) {
292 IDataFlowNode wStart = ((StackObject) this.braceStack.get(first)).getDataFlowNode();
293 IDataFlowNode wEnd = ((StackObject) this.braceStack.get(last)).getDataFlowNode();
294
295 IDataFlowNode end = (IDataFlowNode) wEnd.getFlow().get(wEnd.getIndex() + 1);
296
297 if (wStart.getIndex() != wEnd.getIndex()) {
298 end.reverseParentPathsTo(wStart);
299 wStart.addPathToChild(end);
300 }
301 }
302
303 private void computeIf(int first, int second, int last) {
304 IDataFlowNode ifStart = ((StackObject) this.braceStack.get(first)).getDataFlowNode();
305 IDataFlowNode ifEnd = ((StackObject) this.braceStack.get(second)).getDataFlowNode();
306 IDataFlowNode elseEnd = ((StackObject) this.braceStack.get(last)).getDataFlowNode();
307
308 IDataFlowNode elseStart = (IDataFlowNode) ifEnd.getFlow().get(ifEnd.getIndex() + 1);
309 IDataFlowNode end = (IDataFlowNode) elseEnd.getFlow().get(elseEnd.getIndex() + 1);
310
311
312 if (ifStart.getIndex() != ifEnd.getIndex() &&
313 ifEnd.getIndex() != elseEnd.getIndex()) {
314 elseStart.reverseParentPathsTo(end);
315 ifStart.addPathToChild(elseStart);
316 }
317
318 else if (ifStart.getIndex() == ifEnd.getIndex() &&
319 ifEnd.getIndex() != elseEnd.getIndex()) {
320 ifStart.addPathToChild(end);
321 }
322
323 else if (ifEnd.getIndex() == elseEnd.getIndex() &&
324 ifStart.getIndex() != ifEnd.getIndex()) {
325 ifStart.addPathToChild(end);
326 }
327 }
328
329 private void computeIf(int first, int last) {
330 IDataFlowNode ifStart = ((StackObject) this.braceStack.get(first)).getDataFlowNode();
331 IDataFlowNode ifEnd = ((StackObject) this.braceStack.get(last)).getDataFlowNode();
332
333
334 if (ifStart.getIndex() != ifEnd.getIndex()) {
335 IDataFlowNode end = (IDataFlowNode) ifEnd.getFlow().get(ifEnd.getIndex() + 1);
336 ifStart.addPathToChild(end);
337 }
338 }
339 }