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