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