View Javadoc

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