1
2
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
15
16 public class Linker {
17 private final static Logger LOGGER = Logger.getLogger(Linker.class.getName());
18 private final static String CLASS_NAME = Linker.class.getCanonicalName();
19
20 private final DataFlowHandler dataFlowHandler;
21 private List<StackObject> braceStack;
22 private List<StackObject> continueBreakReturnStack;
23
24 public Linker(DataFlowHandler dataFlowHandler, List<StackObject> braceStack,
25 List<StackObject> continueBreakReturnStack) {
26 this.dataFlowHandler = dataFlowHandler;
27 this.braceStack = braceStack;
28 this.continueBreakReturnStack = continueBreakReturnStack;
29 }
30
31
32
33
34 public void computePaths() throws LinkerException, SequenceException {
35 LOGGER.entering(CLASS_NAME, "computePaths");
36
37
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() + " with this StackList " + dump("braceStack", braceStack));
44 }
45 if (sc.getFirstIndex() < 0 || sc.getLastIndex() < 0) {
46 if (LOGGER.isLoggable(Level.SEVERE)) {
47 LOGGER.severe("Sequence Checker problem: getFirstIndex()==" + sc.getFirstIndex()
48 + ", getLastIndex()==" + sc.getLastIndex());
49 }
50 throw new SequenceException("computePaths(): return index < 0");
51 }
52
53 StackObject firstStackObject = braceStack.get(sc.getFirstIndex());
54
55 if (LOGGER.isLoggable(Level.FINE)) {
56 LOGGER.fine("Checking first braceStack element of type=="
57 + NodeType.stringFromType(firstStackObject.getType()));
58 }
59 switch (firstStackObject.getType()) {
60 case NodeType.IF_EXPR:
61 LOGGER.finest("IF_EXPR");
62 int x = sc.getLastIndex() - sc.getFirstIndex();
63 if (x == 2) {
64 this.computeIf(sc.getFirstIndex(), sc.getFirstIndex() + 1, sc.getLastIndex());
65 } else if (x == 1) {
66 this.computeIf(sc.getFirstIndex(), sc.getLastIndex());
67 } else {
68 LOGGER.severe("Error - computePaths 1");
69 }
70 break;
71
72 case NodeType.WHILE_EXPR:
73 LOGGER.finest("WHILE_EXPR");
74 this.computeWhile(sc.getFirstIndex(), sc.getLastIndex());
75 break;
76
77 case NodeType.SWITCH_START:
78 LOGGER.finest("SWITCH_START");
79 this.computeSwitch(sc.getFirstIndex(), sc.getLastIndex());
80 break;
81
82 case NodeType.FOR_INIT:
83 case NodeType.FOR_EXPR:
84 case NodeType.FOR_UPDATE:
85 case NodeType.FOR_BEFORE_FIRST_STATEMENT:
86 LOGGER.finest("FOR_EXPR");
87 this.computeFor(sc.getFirstIndex(), sc.getLastIndex());
88 break;
89
90 case NodeType.DO_BEFORE_FIRST_STATEMENT:
91 LOGGER.finest("DO_BEFORE_FIRST_STATEMENT");
92 this.computeDo(sc.getFirstIndex(), sc.getLastIndex());
93 break;
94
95 default:
96 }
97
98 if (LOGGER.isLoggable(Level.FINEST)) {
99 LOGGER.finest("Removing braces from Last to first: " + sc.getLastIndex() + " to " + sc.getFirstIndex());
100 }
101 for (int y = sc.getLastIndex(); y >= sc.getFirstIndex(); y--) {
102 if (LOGGER.isLoggable(Level.FINEST)) {
103 LOGGER.finest("Removing brace : " + y);
104 }
105 braceStack.remove(y);
106 }
107 if (LOGGER.isLoggable(Level.FINE)) {
108 LOGGER.fine("Completed Sequence checking loop" + braceStack);
109 }
110 }
111 if (LOGGER.isLoggable(Level.FINER)) {
112 LOGGER.log(Level.FINER, "After Sequence checking loop : remaining braces=={0}",
113 dump("braceStack", braceStack));
114 }
115
116 LOGGER.fine("Processing continueBreakReturnStack elements");
117 while (!continueBreakReturnStack.isEmpty()) {
118 LOGGER.fine("Starting continueBreakReturnStack processing loop");
119 StackObject stackObject = continueBreakReturnStack.get(0);
120 DataFlowNode node = stackObject.getDataFlowNode();
121
122 switch (stackObject.getType()) {
123 case NodeType.THROW_STATEMENT:
124
125 case NodeType.RETURN_STATEMENT:
126 if (LOGGER.isLoggable(Level.FINEST)) {
127 LOGGER.finest("CBR: " + NodeType.stringFromType(stackObject.getType()));
128 }
129
130 node.removePathToChild(node.getChildren().get(0));
131 DataFlowNode lastNode = node.getFlow().get(node.getFlow().size() - 1);
132 node.addPathToChild(lastNode);
133 continueBreakReturnStack.remove(0);
134 break;
135 case NodeType.BREAK_STATEMENT:
136 LOGGER.finest("CBR: BREAK_STATEMENT");
137 DataFlowNode last = getNodeToBreakStatement(node);
138 node.removePathToChild(node.getChildren().get(0));
139 node.addPathToChild(last);
140 continueBreakReturnStack.remove(0);
141 break;
142
143 case NodeType.CONTINUE_STATEMENT:
144 LOGGER.finest("CBR: CONTINUE_STATEMENT");
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195 continueBreakReturnStack.remove(0);
196
197
198 break;
199 default:
200 LOGGER.finest("CBR: default");
201
202 break;
203 }
204 LOGGER.fine("Completed continueBreakReturnStack processing loop");
205 }
206 LOGGER.exiting(CLASS_NAME, "computePaths");
207 }
208
209 private DataFlowNode getNodeToBreakStatement(DataFlowNode node) {
210 LOGGER.entering(CLASS_NAME, "getNodeToBreakStatement");
211
212 List<DataFlowNode> bList = node.getFlow();
213 int findEnds = 1;
214
215
216 int index = bList.indexOf(node);
217 for (; index < bList.size() - 2; index++) {
218 DataFlowNode n = bList.get(index);
219 if (n.isType(NodeType.DO_EXPR) || n.isType(NodeType.FOR_INIT) || n.isType(NodeType.WHILE_EXPR)
220 || n.isType(NodeType.SWITCH_START)) {
221 findEnds++;
222 }
223 if (n.isType(NodeType.WHILE_LAST_STATEMENT) || n.isType(NodeType.SWITCH_END) || n.isType(NodeType.FOR_END)
224 || n.isType(NodeType.DO_EXPR)) {
225 if (findEnds > 1) {
226
227 findEnds--;
228 } else {
229 break;
230 }
231 }
232
233 if (n.isType(NodeType.LABEL_LAST_STATEMENT)) {
234 Node parentNode = n.getNode().getFirstParentOfType(dataFlowHandler.getLabelStatementNodeClass());
235 if (parentNode == null) {
236 break;
237 } else {
238 String label = node.getNode().getImage();
239 if (label == null || label.equals(parentNode.getImage())) {
240 node.removePathToChild(node.getChildren().get(0));
241 DataFlowNode last = bList.get(index + 1);
242 node.addPathToChild(last);
243 break;
244 }
245 }
246 }
247 }
248 LOGGER.exiting(CLASS_NAME, "getNodeToBreakSttement");
249 return node.getFlow().get(index + 1);
250 }
251
252 private void computeDo(int first, int last) {
253 LOGGER.entering(CLASS_NAME, "computeDo");
254 DataFlowNode doSt = this.braceStack.get(first).getDataFlowNode();
255 DataFlowNode doExpr = this.braceStack.get(last).getDataFlowNode();
256 DataFlowNode doFirst = doSt.getFlow().get(doSt.getIndex() + 1);
257 if (doFirst.getIndex() != doExpr.getIndex()) {
258 doExpr.addPathToChild(doFirst);
259 }
260 LOGGER.exiting(CLASS_NAME, "computeDo");
261 }
262
263 private void computeFor(int firstIndex, int lastIndex) {
264 LOGGER.entering(CLASS_NAME, "computeFor");
265 DataFlowNode fExpr = null;
266 DataFlowNode fUpdate = null;
267 DataFlowNode fSt = null;
268 DataFlowNode fEnd = null;
269 boolean isUpdate = false;
270
271 for (int i = firstIndex; i <= lastIndex; i++) {
272 StackObject so = this.braceStack.get(i);
273 DataFlowNode node = so.getDataFlowNode();
274
275 if (so.getType() == NodeType.FOR_EXPR) {
276 fExpr = node;
277 } else if (so.getType() == NodeType.FOR_UPDATE) {
278 fUpdate = node;
279 isUpdate = true;
280 } else if (so.getType() == NodeType.FOR_BEFORE_FIRST_STATEMENT) {
281 fSt = node;
282 } else if (so.getType() == NodeType.FOR_END) {
283 fEnd = node;
284 }
285 }
286 DataFlowNode end = fEnd.getFlow().get(fEnd.getIndex() + 1);
287
288 DataFlowNode firstSt = fSt.getChildren().get(0);
289
290 if (isUpdate) {
291 if (fSt.getIndex() != fEnd.getIndex()) {
292 end.reverseParentPathsTo(fUpdate);
293 fExpr.removePathToChild(fUpdate);
294 fUpdate.addPathToChild(fExpr);
295 fUpdate.removePathToChild(firstSt);
296 fExpr.addPathToChild(firstSt);
297 fExpr.addPathToChild(end);
298 } else {
299 fSt.removePathToChild(end);
300 fExpr.removePathToChild(fUpdate);
301 fUpdate.addPathToChild(fExpr);
302 fExpr.addPathToChild(fUpdate);
303 fExpr.addPathToChild(end);
304 }
305 } else {
306 if (fSt.getIndex() != fEnd.getIndex()) {
307 end.reverseParentPathsTo(fExpr);
308 fExpr.addPathToChild(end);
309 }
310 }
311 LOGGER.exiting(CLASS_NAME, "computeFor");
312 }
313
314 private void computeSwitch(int firstIndex, int lastIndex) {
315 LOGGER.entering(CLASS_NAME, "computeSwitch");
316
317 int diff = lastIndex - firstIndex;
318 boolean defaultStatement = false;
319
320 DataFlowNode sStart = this.braceStack.get(firstIndex).getDataFlowNode();
321 DataFlowNode sEnd = this.braceStack.get(lastIndex).getDataFlowNode();
322 DataFlowNode end = sEnd.getChildren().get(0);
323
324 if (LOGGER.isLoggable(Level.FINE)) {
325 LOGGER.fine("Stack(sStart)=>" + sStart + ",Stack(sEnd)=>" + sEnd + ",end=>" + end);
326 }
327
328 for (int i = 0; i < diff - 2; i++) {
329 StackObject so = this.braceStack.get(firstIndex + 2 + i);
330 DataFlowNode node = so.getDataFlowNode();
331
332 if (LOGGER.isLoggable(Level.FINE)) {
333 LOGGER.fine("so(" + (firstIndex + 2 + i) + ")=>" + so + " has dfn=>" + node + " with first child =>"
334 + node.getChildren().get(0));
335 }
336 sStart.addPathToChild(node.getChildren().get(0));
337
338 if (so.getType() == NodeType.SWITCH_LAST_DEFAULT_STATEMENT) {
339 defaultStatement = true;
340 }
341 }
342
343 if (!defaultStatement) {
344 sStart.addPathToChild(end);
345 }
346 LOGGER.exiting(CLASS_NAME, "computeSwitch");
347 }
348
349 private void computeWhile(int first, int last) {
350 LOGGER.entering(CLASS_NAME, "computeWhile with first and last of" + first + "," + last);
351 DataFlowNode wStart = this.braceStack.get(first).getDataFlowNode();
352 DataFlowNode wEnd = this.braceStack.get(last).getDataFlowNode();
353
354 DataFlowNode end = wEnd.getFlow().get(wEnd.getIndex() + 1);
355
356 if (wStart.getIndex() != wEnd.getIndex()) {
357 end.reverseParentPathsTo(wStart);
358 wStart.addPathToChild(end);
359 }
360 LOGGER.exiting(CLASS_NAME, "computeWhile");
361 }
362
363 private void computeIf(int first, int second, int last) {
364 LOGGER.entering(CLASS_NAME, "computeIf(3)", first + "," + second + "," + last);
365 DataFlowNode ifStart = this.braceStack.get(first).getDataFlowNode();
366 DataFlowNode ifEnd = this.braceStack.get(second).getDataFlowNode();
367 DataFlowNode elseEnd = this.braceStack.get(last).getDataFlowNode();
368
369 DataFlowNode elseStart = ifEnd.getFlow().get(ifEnd.getIndex() + 1);
370 DataFlowNode end = elseEnd.getFlow().get(elseEnd.getIndex() + 1);
371
372 LOGGER.log(Level.FINEST, "If ifstart={0}, ifEnd={1}, elseEnd={2}, elseStart={3}, end={4}", new Object[] {
373 ifStart, ifEnd, elseEnd, elseStart, end });
374
375
376 if (ifStart.getIndex() != ifEnd.getIndex() && ifEnd.getIndex() != elseEnd.getIndex()) {
377 elseStart.reverseParentPathsTo(end);
378 ifStart.addPathToChild(elseStart);
379 }
380
381 else if (ifStart.getIndex() == ifEnd.getIndex() && ifEnd.getIndex() != elseEnd.getIndex()) {
382 ifStart.addPathToChild(end);
383 }
384
385 else if (ifEnd.getIndex() == elseEnd.getIndex() && ifStart.getIndex() != ifEnd.getIndex()) {
386 ifStart.addPathToChild(end);
387 }
388 LOGGER.exiting(CLASS_NAME, "computeIf(3)");
389 }
390
391 private void computeIf(int first, int last) {
392 LOGGER.entering(CLASS_NAME, "computeIf(2)");
393 DataFlowNode ifStart = this.braceStack.get(first).getDataFlowNode();
394 DataFlowNode ifEnd = this.braceStack.get(last).getDataFlowNode();
395
396
397 if (ifStart.getIndex() != ifEnd.getIndex()) {
398 DataFlowNode end = ifEnd.getFlow().get(ifEnd.getIndex() + 1);
399 ifStart.addPathToChild(end);
400 }
401 LOGGER.exiting(CLASS_NAME, "computeIf(2)");
402 }
403
404
405
406
407
408 private static String dump(String description, List<StackObject> stackList) {
409 StringBuilder stringDump = new StringBuilder("Stack List (");
410 stringDump.append(description).append(") ListDump:\n");
411 for (StackObject stackObject : stackList) {
412 stringDump.append('\n').append(stackObject.toString());
413 }
414 return stringDump.toString();
415 }
416
417 }