1
2
3
4 package net.sourceforge.pmd.dfa.pathfinder;
5
6 import net.sourceforge.pmd.dfa.IDataFlowNode;
7 import net.sourceforge.pmd.dfa.NodeType;
8
9 import javax.swing.tree.DefaultMutableTreeNode;
10 import java.util.LinkedList;
11
12 /***
13 * @author raik
14 * <p/>
15 * Finds all paths of a data flow. Each loop will be 0 or 2 times traversed ->
16 * 2 paths. This is special to the data flow anomaly analysis.
17 */
18 public class DAAPathFinder {
19
20 private IDataFlowNode rootNode;
21 private Executable shim;
22 private LinkedList currentPath = new LinkedList();
23 private DefaultMutableTreeNode stack = new DefaultMutableTreeNode();
24 private static final int MAX_PATHS = 5000;
25
26 private static class PathElement {
27 int currentChild;
28 IDataFlowNode node;
29 IDataFlowNode pseudoRef;
30 PathElement(IDataFlowNode node) {
31 this.node = node;
32 }
33 }
34
35 public DAAPathFinder(IDataFlowNode rootNode, Executable shim) {
36 this.rootNode = rootNode;
37 this.shim = shim;
38 }
39
40 public void run() {
41 phase1(rootNode);
42 }
43
44
45
46
47 private void phase1(IDataFlowNode startNode) {
48 this.currentPath.clear();
49 this.currentPath.addLast(startNode);
50
51 int i = 0;
52 boolean flag = true;
53 do {
54 i++;
55 phase2(flag);
56 shim.execute(currentPath);
57 flag = false;
58 } while (i < MAX_PATHS && phase3());
59
60 }
61
62
63
64
65 private void phase2(boolean flag) {
66 while (!isEndNode()) {
67 if (isBranch() || isFirstDoStatement()) {
68 if (flag) {
69 addNodeToTree();
70 }
71 flag = true;
72 if (countLoops() <= 2) {
73 addCurrentChild();
74 continue;
75 } else {
76 addSecondChild();
77 continue;
78 }
79 } else {
80 addCurrentChild();
81 }
82 }
83 }
84
85
86
87
88
89 private boolean phase3() {
90
91 while (!this.isEmpty()) {
92 if (this.isBranch()) {
93 if (this.countLoops() == 1) {
94 if (this.hasMoreChildren()) {
95 this.incChild();
96 return true;
97 } else {
98 this.removeFromTree();
99 this.removeFromList();
100 }
101 } else {
102 this.removeFromTree();
103 this.removeFromList();
104 }
105 } else {
106 this.removeFromList();
107 }
108 }
109
110 return false;
111 }
112
113 private void removeFromList() {
114 this.currentPath.removeLast();
115 }
116
117 private boolean isEmpty() {
118 return this.currentPath.isEmpty();
119 }
120
121 private boolean hasMoreChildren() {
122 DefaultMutableTreeNode last = this.getLastNode();
123 PathElement e = (PathElement) last.getUserObject();
124 return e.currentChild + 1 < e.node.getChildren().size();
125 }
126
127 private boolean isEndNode() {
128 IDataFlowNode inode = (IDataFlowNode) this.currentPath.getLast();
129
130 return inode.getChildren().size() == 0;
131 }
132
133 private boolean isBranch() {
134 IDataFlowNode inode = (IDataFlowNode) this.currentPath.getLast();
135 return inode.getChildren().size() > 1;
136 }
137
138 private boolean isFirstDoStatement() {
139 IDataFlowNode inode = (IDataFlowNode)this.currentPath.getLast();
140 return this.isFirstDoStatement(inode);
141 }
142
143 private void addSecondChild() {
144 PathElement e = (PathElement) this.getLastNode().getUserObject();
145 int secondChild;
146 if (e.currentChild == 1) {
147 secondChild = 0;
148 } else {
149 secondChild = 1;
150 }
151 IDataFlowNode child = (IDataFlowNode) e.node.getChildren().get(secondChild);
152 this.currentPath.addLast(child);
153 }
154
155 private void addCurrentChild() {
156 if (this.isBranch()) {
157 PathElement last = (PathElement) this.getLastNode().getUserObject();
158 IDataFlowNode inode = (IDataFlowNode) this.currentPath.getLast();
159 IDataFlowNode child = (IDataFlowNode) inode.getChildren().get(last.currentChild);
160 this.currentPath.addLast(child);
161 } else {
162 IDataFlowNode inode = (IDataFlowNode) this.currentPath.getLast();
163 IDataFlowNode child = (IDataFlowNode) inode.getChildren().get(0);
164 this.currentPath.addLast(child);
165 }
166 }
167
168 private boolean isFirstDoStatement(IDataFlowNode inode) {
169 int index = inode.getIndex() - 1;
170 if (index < 0) return false;
171
172 IDataFlowNode before = (IDataFlowNode) inode.getFlow().get(index);
173 return before.isType(NodeType.DO_BEFORE_FIRST_STATEMENT);
174 }
175
176 private boolean isDoBranchNode() {
177 IDataFlowNode last = (IDataFlowNode) this.currentPath.getLast();
178 return this.isDoBranch(last);
179 }
180
181 private boolean isDoBranch(IDataFlowNode inode) {
182 return inode.isType(NodeType.DO_EXPR);
183 }
184
185
186
187
188
189
190
191
192 private void addNodeToTree() {
193 if (this.isFirstDoStatement()) {
194 DefaultMutableTreeNode level = this.getRootNode();
195 IDataFlowNode doBranch = this.getDoBranchNodeFromFirstDoStatement();
196
197 while (true) {
198 if (this.hasTheLevelChildren(level)) {
199 PathElement ref;
200 if ((ref = this.isNodeInLevel(level)) != null) {
201
202 this.addRefPseudoPathElement(level, ref);
203 break;
204 } else {
205 level = this.getLastChildNode(level);
206 continue;
207 }
208 } else {
209
210 this.addNewPseudoPathElement(level, doBranch);
211 break;
212 }
213 }
214 }
215
216 if (this.isBranch()) {
217 DefaultMutableTreeNode level = this.getRootNode();
218
219 if (this.isDoBranchNode()) {
220 while (!this.equalsPseudoPathElementWithDoBranchNodeInLevel(level)) {
221 level = this.getLastChildNode(level);
222 }
223 PathElement ref;
224 if ((ref = this.getDoBranchNodeInLevel(level)) != null) {
225
226 this.addRefPathElement(level, ref);
227 } else {
228
229 this.addNewPathElement(level);
230 }
231
232 } else {
233 while (true) {
234 if (this.hasTheLevelChildren(level)) {
235 PathElement ref;
236 if ((ref = this.isNodeInLevel(level)) != null) {
237
238 this.addRefPathElement(level, ref);
239 break;
240 } else {
241 level = this.getLastChildNode(level);
242 continue;
243 }
244 } else {
245
246 this.addNewPathElement(level);
247 break;
248 }
249 }
250 }
251 }
252 }
253
254 private void removeFromTree() {
255 DefaultMutableTreeNode last = this.getLastNode();
256
257 if (last == null) {
258 System.out.println("removeFromTree - last == null");
259 return;
260 }
261
262 DefaultMutableTreeNode parent = (DefaultMutableTreeNode) last.getParent();
263 parent.remove(last);
264
265 last = this.getLastNode();
266
267 if (last == null) return;
268 if (last.getUserObject() == null) return;
269
270 PathElement e = (PathElement) last.getUserObject();
271 if (this.isPseudoPathElement(e)) {
272 this.removeFromTree();
273 }
274 }
275
276 private IDataFlowNode getDoBranchNodeFromFirstDoStatement() {
277 IDataFlowNode inode = (IDataFlowNode) this.currentPath.getLast();
278
279 if (!this.isFirstDoStatement()) return null;
280
281 for (int i = 0; i < inode.getParents().size(); i++) {
282 IDataFlowNode parent = (IDataFlowNode) inode.getParents().get(i);
283
284 if (this.isDoBranch(parent)) {
285 return parent;
286 }
287 }
288 return null;
289 }
290
291 private void addNewPathElement(DefaultMutableTreeNode level) {
292 IDataFlowNode last = (IDataFlowNode) this.currentPath.getLast();
293 PathElement e = new PathElement(last);
294 this.addNode(level, e);
295 }
296
297 private void addRefPathElement(DefaultMutableTreeNode level, PathElement ref) {
298 this.addNode(level, ref);
299 }
300
301
302
303
304 private void addNewPseudoPathElement(DefaultMutableTreeNode level, IDataFlowNode ref) {
305 IDataFlowNode last = (IDataFlowNode) this.currentPath.getLast();
306 PathElement e = new PathElement(last);
307 e.pseudoRef = ref;
308 this.addNode(level, e);
309 }
310
311
312
313
314 private void addRefPseudoPathElement(DefaultMutableTreeNode level, PathElement ref) {
315 this.addNode(level, ref);
316 }
317
318 private boolean equalsPseudoPathElementWithDoBranchNodeInLevel(DefaultMutableTreeNode level) {
319 IDataFlowNode inode = (IDataFlowNode) this.currentPath.getLast();
320
321 if (!this.isDoBranch(inode)) return false;
322
323 int childCount = level.getChildCount();
324 DefaultMutableTreeNode child;
325
326 for (int i = 0; i < childCount; i++) {
327 child = (DefaultMutableTreeNode) level.getChildAt(i);
328 PathElement pe = (PathElement) child.getUserObject();
329 if (isPseudoPathElement(pe) && pe.pseudoRef.equals(inode)) {
330 return true;
331 }
332 }
333 return false;
334 }
335
336 private PathElement getDoBranchNodeInLevel(DefaultMutableTreeNode level) {
337 IDataFlowNode inode = (IDataFlowNode) this.currentPath.getLast();
338
339 if (!this.isDoBranch(inode)) return null;
340
341 int childCount = level.getChildCount();
342 DefaultMutableTreeNode child;
343
344 for (int i = 0; i < childCount; i++) {
345 child = (DefaultMutableTreeNode) level.getChildAt(i);
346 PathElement pe = (PathElement) child.getUserObject();
347 if (inode.equals(pe.node)) {
348 return pe;
349 }
350 }
351 return null;
352 }
353
354 private void addNode(DefaultMutableTreeNode level, PathElement element) {
355 DefaultMutableTreeNode node = new DefaultMutableTreeNode();
356 node.setUserObject(element);
357 level.add(node);
358 }
359
360 private PathElement isNodeInLevel(DefaultMutableTreeNode level) {
361 IDataFlowNode inode = (IDataFlowNode) this.currentPath.getLast();
362 DefaultMutableTreeNode child = (DefaultMutableTreeNode) level.getFirstChild();
363
364 if (child != null) {
365 PathElement levelElement = (PathElement) child.getUserObject();
366 if (inode.equals(levelElement.node)) {
367 return levelElement;
368 }
369 }
370 return null;
371 }
372
373 private DefaultMutableTreeNode getLastChildNode(DefaultMutableTreeNode node) {
374 if (this.hasTheLevelChildren(node)) {
375 return (DefaultMutableTreeNode) node.getLastChild();
376 }
377 return node;
378 }
379
380 private DefaultMutableTreeNode getRootNode() {
381 return this.stack;
382 }
383
384 private boolean hasTheLevelChildren(DefaultMutableTreeNode level) {
385 return level.getChildCount() != 0;
386 }
387
388 private DefaultMutableTreeNode getLastNode() {
389 return this.stack.getLastLeaf();
390 }
391
392 private int countLoops() {
393 DefaultMutableTreeNode treeNode = this.getLastNode();
394 int counter = 0;
395 int childCount = treeNode.getParent().getChildCount();
396 for (int i = 0; i < childCount; i++) {
397 DefaultMutableTreeNode tNode = (DefaultMutableTreeNode) treeNode.getParent().getChildAt(i);
398 PathElement e = (PathElement) tNode.getUserObject();
399 if (!this.isPseudoPathElement(e)) {
400 counter++;
401 }
402 }
403 return counter;
404 }
405
406 private void incChild() {
407 DefaultMutableTreeNode last = this.getLastNode();
408 PathElement e = (PathElement) last.getUserObject();
409 e.currentChild++;
410 }
411
412 private boolean isPseudoPathElement(PathElement pe) {
413 return pe != null && pe.pseudoRef != null;
414 }
415 }