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