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