|
1
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
17 public class DAAPathFinder {
18 private static final int MAX_PATHS = 5000;
19
20 private IDataFlowNode 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(IDataFlowNode rootNode, Executable shim) {
27 this.rootNode = rootNode;
28 this.shim = shim;
29 this.maxPaths = MAX_PATHS;
30 }
31
32 public DAAPathFinder(IDataFlowNode 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
45 private void phase1() {
46 currentPath.addLast(rootNode);
47 int i = 0;
48 boolean flag = true;
49 do {
50 i++;
51 phase2(flag);
53 shim.execute(currentPath);
54 flag = false;
55 } while (i < maxPaths && phase3());
56 }
57
58
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 addLastChild();
74 continue;
75 }
76 } else {
77 addCurrentChild();
78 }
79 }
80 }
81
82
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((IDataFlowNode) e.node.getChildren().get(i));
118 break;
119 }
120 }
121 }
122
123
124 private void addCurrentChild() {
125 if (currentPath.isBranch()) { PathElement last = (PathElement) stack.getLastLeaf().getUserObject();
127 IDataFlowNode inode = currentPath.getLast();
128 if (inode.getChildren().size() > last.currentChild) {
129 IDataFlowNode child = (IDataFlowNode) inode.getChildren().get(last.currentChild);
131 this.currentPath.addLast(child);
132 }
133 } else {
134 IDataFlowNode inode = currentPath.getLast();
135 IDataFlowNode child = (IDataFlowNode) inode.getChildren().get(0); this.currentPath.addLast(child);
137 }
138 }
139
140
143
147 private void addNodeToTree() {
148 if (currentPath.isFirstDoStatement()) {
149 DefaultMutableTreeNode level = stack;
150 IDataFlowNode 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;
190 if ((ref = this.isNodeInLevel(level)) != 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 parent.remove(last);
216 }
217 last = stack.getLastLeaf();
218 if (last == null || last.getUserObject() == null) return;
219
220 PathElement e = (PathElement) last.getUserObject();
221 if (e != null && e.isPseudoPathElement()) {
222 this.removeFromTree();
223 }
224 }
225
226 private void addNewPathElement(DefaultMutableTreeNode level) {
227 addNode(level, new PathElement(currentPath.getLast()));
228 }
229
230
233 private void addNewPseudoPathElement(DefaultMutableTreeNode level, IDataFlowNode ref) {
234 addNode(level, new PathElement(currentPath.getLast(), ref));
235 }
236
237
240 private void addRefPseudoPathElement(DefaultMutableTreeNode level, PathElement ref) {
241 addNode(level, ref);
242 }
243
244 private boolean equalsPseudoPathElementWithDoBranchNodeInLevel(DefaultMutableTreeNode level) {
245 IDataFlowNode inode = currentPath.getLast();
246
247 if (!inode.isType(NodeType.DO_EXPR)) return false;
248
249 int childCount = level.getChildCount();
250 DefaultMutableTreeNode child;
251
252 for (int i = 0; i < childCount; i++) {
253 child = (DefaultMutableTreeNode ) level.getChildAt(i);
254 PathElement pe = (PathElement) child.getUserObject();
255 if (pe != null && pe.isPseudoPathElement() && pe.pseudoRef.equals(inode)) {
256 return true;
257 }
258 }
259 return false;
260 }
261
262 private PathElement getDoBranchNodeInLevel(DefaultMutableTreeNode level) {
263 IDataFlowNode inode = currentPath.getLast();
264 if (!inode.isType(NodeType.DO_EXPR)) return null;
265
266 int childCount = level.getChildCount();
267 DefaultMutableTreeNode child;
268
269 for (int i = 0; i < childCount; i++) {
270 child = (DefaultMutableTreeNode ) level.getChildAt(i);
271 PathElement pe = (PathElement) child.getUserObject();
272 if (inode.equals(pe.node)) {
273 return pe;
274 }
275 }
276 return null;
277 }
278
279 private void addNode(DefaultMutableTreeNode level, PathElement element) {
280 DefaultMutableTreeNode node = new DefaultMutableTreeNode ();
281 node.setUserObject(element);
282 level.add(node);
283 }
284
285 private PathElement isNodeInLevel(DefaultMutableTreeNode level) {
286 IDataFlowNode inode = currentPath.getLast();
287 DefaultMutableTreeNode child = (DefaultMutableTreeNode ) level.getFirstChild();
288
289 if (child != null) {
290 PathElement levelElement = (PathElement) child.getUserObject();
291 if (inode.equals(levelElement.node)) {
292 return levelElement;
293 }
294 }
295 return null;
296 }
297
298 private DefaultMutableTreeNode getLastChildNode(DefaultMutableTreeNode node) {
299 if (node.getChildCount() != 0) {
300 return (DefaultMutableTreeNode ) node.getLastChild();
301 }
302 return node;
303 }
304
305 private int countLoops() {
306 DefaultMutableTreeNode treeNode = stack.getLastLeaf();
307 int counter = 0;
308 if (treeNode.getParent() != null) {
309 int childCount = treeNode.getParent().getChildCount();
311 for (int i = 0; i < childCount; i++) {
312 DefaultMutableTreeNode tNode = (DefaultMutableTreeNode ) treeNode.getParent().getChildAt(i);
313 PathElement e = (PathElement) tNode.getUserObject();
314 if (e != null && !e.isPseudoPathElement()) {
315 counter++;
316 }
317 }
318 }
319 return counter;
320 }
321
322 private void incChild() {
323 ((PathElement) stack.getLastLeaf().getUserObject()).currentChild++;
324 }
325
326 }
327 |
Popular Tags |
Java API By Example, From Geeks To Geeks.