1
2
3
4 package net.sourceforge.pmd.lang.dfa.pathfinder;
5
6 import javax.swing.tree.DefaultMutableTreeNode;
7
8 import net.sourceforge.pmd.lang.dfa.DataFlowNode;
9 import net.sourceforge.pmd.lang.dfa.NodeType;
10
11
12
13
14
15
16
17 public class DAAPathFinder {
18 private static final int MAX_PATHS = 5000;
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48 private void phase1() {
49 currentPath.addLast(rootNode);
50 int i = 0;
51 boolean flag = true;
52 do {
53 i++;
54
55 phase2(flag);
56 shim.execute(currentPath);
57 flag = false;
58 } while (i < maxPaths && phase3());
59 }
60
61
62
63
64 private void phase2(boolean flag) {
65 int i = 0;
66 while (!currentPath.isEndNode() && i < MAX_LOOPS) {
67 i++;
68 if (currentPath.isBranch() || currentPath.isFirstDoStatement()) {
69 if (flag) {
70 addNodeToTree();
71 }
72 flag = true;
73 if (countLoops() <= 2) {
74 addCurrentChild();
75 continue;
76 } else {
77
78 addLastChild();
79 continue;
80 }
81 } else {
82 addCurrentChild();
83 }
84 }
85 }
86
87
88
89
90
91 private boolean phase3() {
92 while (!currentPath.isEmpty()) {
93 if (currentPath.isBranch()) {
94 if (this.countLoops() == 1) {
95 if (this.hasMoreChildren()) {
96 this.incChild();
97 return true;
98 } else {
99 this.removeFromTree();
100 currentPath.removeLast();
101 }
102 } else {
103 this.removeFromTree();
104 currentPath.removeLast();
105 }
106 } else {
107 currentPath.removeLast();
108 }
109 }
110 return false;
111 }
112
113 private boolean hasMoreChildren() {
114 PathElement e = (PathElement) stack.getLastLeaf().getUserObject();
115 return e.currentChild + 1 < e.node.getChildren().size();
116 }
117
118 private void addLastChild() {
119 PathElement e = (PathElement) stack.getLastLeaf().getUserObject();
120 for (int i=e.node.getChildren().size()-1; i >= 0; i--) {
121 if (i != e.currentChild) {
122 currentPath.addLast(e.node.getChildren().get(i));
123 break;
124 }
125 }
126 }
127
128
129 private void addCurrentChild() {
130 if (currentPath.isBranch()) {
131 PathElement last = (PathElement) stack.getLastLeaf().getUserObject();
132 DataFlowNode inode = currentPath.getLast();
133 if (inode.getChildren().size() > last.currentChild) {
134
135
136 DataFlowNode child = inode.getChildren().get(last.currentChild);
137 this.currentPath.addLast(child);
138 }
139 } else {
140 DataFlowNode inode = currentPath.getLast();
141 DataFlowNode child = inode.getChildren().get(0);
142 this.currentPath.addLast(child);
143 }
144 }
145
146
147
148
149
150
151
152
153 private void addNodeToTree() {
154 if (currentPath.isFirstDoStatement()) {
155 DefaultMutableTreeNode level = stack;
156 DataFlowNode doBranch = currentPath.getDoBranchNodeFromFirstDoStatement();
157
158 while (true) {
159 if (level.getChildCount() != 0) {
160 PathElement ref = this.isNodeInLevel(level);
161 if (ref != null) {
162 this.addRefPseudoPathElement(level, ref);
163 break;
164 } else {
165 level = this.getLastChildNode(level);
166 continue;
167 }
168 } else {
169 this.addNewPseudoPathElement(level, doBranch);
170 break;
171 }
172 }
173 }
174
175 if (currentPath.isBranch()) {
176 DefaultMutableTreeNode level = stack;
177
178 if (currentPath.isDoBranchNode()) {
179 while (!this.equalsPseudoPathElementWithDoBranchNodeInLevel(level)) {
180 level = this.getLastChildNode(level);
181 if (level.getChildCount() == 0) {
182 break;
183 }
184 }
185 PathElement ref = this.getDoBranchNodeInLevel(level);
186 if (ref != null) {
187 addNode(level, ref);
188 } else {
189 this.addNewPathElement(level);
190 }
191
192 } else {
193 while (true) {
194 if (level.getChildCount() != 0) {
195 PathElement ref = this.isNodeInLevel(level);
196 if (ref != null) {
197 addNode(level, ref);
198 break;
199 } else {
200 level = this.getLastChildNode(level);
201 continue;
202 }
203 } else {
204 this.addNewPathElement(level);
205 break;
206 }
207 }
208 }
209 }
210 }
211
212 private void removeFromTree() {
213 DefaultMutableTreeNode last = stack.getLastLeaf();
214 if (last == null) {
215 System.out.println("removeFromTree - last == null");
216 return;
217 }
218 DefaultMutableTreeNode parent = (DefaultMutableTreeNode) last.getParent();
219 if (parent != null) {
220
221 parent.remove(last);
222 }
223 last = stack.getLastLeaf();
224 if (last == null || last.getUserObject() == null) {
225 return;
226 }
227
228 PathElement e = (PathElement) last.getUserObject();
229 if (e != null && e.isPseudoPathElement()) {
230 this.removeFromTree();
231 }
232 }
233
234 private void addNewPathElement(DefaultMutableTreeNode level) {
235 addNode(level, new PathElement(currentPath.getLast()));
236 }
237
238
239
240
241 private void addNewPseudoPathElement(DefaultMutableTreeNode level, DataFlowNode ref) {
242 addNode(level, new PathElement(currentPath.getLast(), ref));
243 }
244
245
246
247
248 private void addRefPseudoPathElement(DefaultMutableTreeNode level, PathElement ref) {
249 addNode(level, ref);
250 }
251
252 private boolean equalsPseudoPathElementWithDoBranchNodeInLevel(DefaultMutableTreeNode level) {
253 DataFlowNode inode = currentPath.getLast();
254
255 if (!inode.isType(NodeType.DO_EXPR)) {
256 return false;
257 }
258
259 int childCount = level.getChildCount();
260 DefaultMutableTreeNode child;
261
262 for (int i = 0; i < childCount; i++) {
263 child = (DefaultMutableTreeNode) level.getChildAt(i);
264 PathElement pe = (PathElement) child.getUserObject();
265 if (pe != null && pe.isPseudoPathElement() && pe.pseudoRef.equals(inode)) {
266 return true;
267 }
268 }
269 return false;
270 }
271
272 private PathElement getDoBranchNodeInLevel(DefaultMutableTreeNode level) {
273 DataFlowNode inode = currentPath.getLast();
274 if (!inode.isType(NodeType.DO_EXPR)) {
275 return null;
276 }
277
278 int childCount = level.getChildCount();
279 DefaultMutableTreeNode child;
280
281 for (int i = 0; i < childCount; i++) {
282 child = (DefaultMutableTreeNode) level.getChildAt(i);
283 PathElement pe = (PathElement) child.getUserObject();
284 if (inode.equals(pe.node)) {
285 return pe;
286 }
287 }
288 return null;
289 }
290
291 private void addNode(DefaultMutableTreeNode level, PathElement element) {
292 DefaultMutableTreeNode node = new DefaultMutableTreeNode();
293 node.setUserObject(element);
294 level.add(node);
295 }
296
297 private PathElement isNodeInLevel(DefaultMutableTreeNode level) {
298 DataFlowNode inode = currentPath.getLast();
299 DefaultMutableTreeNode child = (DefaultMutableTreeNode) level.getFirstChild();
300
301 if (child != null) {
302 PathElement levelElement = (PathElement) child.getUserObject();
303 if (inode.equals(levelElement.node)) {
304 return levelElement;
305 }
306 }
307 return null;
308 }
309
310 private DefaultMutableTreeNode getLastChildNode(DefaultMutableTreeNode node) {
311 if (node.getChildCount() != 0) {
312 return (DefaultMutableTreeNode) node.getLastChild();
313 }
314 return node;
315 }
316
317 private int countLoops() {
318 DefaultMutableTreeNode treeNode = stack.getLastLeaf();
319 int counter = 0;
320 if (treeNode.getParent() != null) {
321
322
323 int childCount = treeNode.getParent().getChildCount();
324 for (int i = 0; i < childCount; i++) {
325 DefaultMutableTreeNode tNode = (DefaultMutableTreeNode) treeNode.getParent().getChildAt(i);
326 PathElement e = (PathElement) tNode.getUserObject();
327 if (e != null && !e.isPseudoPathElement()) {
328 counter++;
329 }
330 }
331 }
332 return counter;
333 }
334
335 private void incChild() {
336 ((PathElement) stack.getLastLeaf().getUserObject()).currentChild++;
337 }
338
339 }