View Javadoc

1   /**
2    * BSD-style license; for more info see http://pmd.sourceforge.net/license.html
3    */
4   package net.sourceforge.pmd.lang.dfa.pathfinder;
5   
6   import javax.swing.tree.DefaultMutableTreeNode;
7   
8   import net.sourceforge.pmd.lang.dfa.DataFlowNode;
9   import net.sourceforge.pmd.lang.dfa.NodeType;
10  
11  /**
12   *         Finds all paths of a data flow. Each loop will be 0 or 2 times traversed ->
13   *         2 paths. This is special to the data flow anomaly analysis.
14   * @since Created on 09.08.2004
15   * @author raik
16   */
17  public class DAAPathFinder {
18      private static final int MAX_PATHS = 5000;
19  
20      private DataFlowNode 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(DataFlowNode rootNode, Executable shim) {
27          this.rootNode = rootNode;
28          this.shim = shim;
29          this.maxPaths = MAX_PATHS;
30      }
31      
32      public DAAPathFinder(DataFlowNode 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      /*
43       * Initialise the path search. Starts the searching.
44       * */
45      private void phase1() {
46          currentPath.addLast(rootNode);
47          int i = 0;
48          boolean flag = true;
49          do {
50              i++;
51  //            System.out.println("Building path from " + currentPath.getLast());
52              phase2(flag);
53              shim.execute(currentPath);
54              flag = false;
55          } while (i < maxPaths && phase3());
56      }
57  
58      /*
59       * Builds up the path.
60       * */
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                      // jump out of that loop
73                      addLastChild();
74                      continue;
75                  }
76              } else {
77                  addCurrentChild();
78              }
79          }
80      }
81  
82      /*
83       * Decompose the path until it finds a node which branches are not all 
84       * traversed.
85       * */
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(e.node.getChildren().get(i));
118                 break;
119             }
120         }
121     }
122 
123 
124     private void addCurrentChild() {
125         if (currentPath.isBranch()) { // TODO WHY????
126             PathElement last = (PathElement) stack.getLastLeaf().getUserObject();
127             DataFlowNode inode = currentPath.getLast();
128             if (inode.getChildren().size() > last.currentChild) { 
129                 // for some unknown reasons last.currentChild might not be a children of inode, see bug 1597987 
130         	DataFlowNode child = inode.getChildren().get(last.currentChild);
131                 this.currentPath.addLast(child);
132             }
133         } else {
134             DataFlowNode inode = currentPath.getLast();
135             DataFlowNode child = inode.getChildren().get(0); //TODO ???? IMPORTANT - ERROR?
136             this.currentPath.addLast(child);
137         }
138     }
139 
140 //  ----------------------------------------------------------------------------
141 //	TREE FUNCTIONS
142     
143     /*
144      * Adds a PathElement to a Tree, which contains information about
145      * loops and "local scopes - encapsulation".
146      * */
147     private void addNodeToTree() {
148         if (currentPath.isFirstDoStatement()) {
149             DefaultMutableTreeNode level = stack;
150             DataFlowNode 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 = this.isNodeInLevel(level);
190                         if (ref != 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         	// for some unknown reasons parent might be null, see bug 1597987
215             parent.remove(last);
216         }
217         last = stack.getLastLeaf();
218         if (last == null || last.getUserObject() == null) {
219             return;
220         }
221 
222         PathElement e = (PathElement) last.getUserObject();
223         if (e != null && e.isPseudoPathElement()) {
224             this.removeFromTree();
225         }
226     }
227 
228     private void addNewPathElement(DefaultMutableTreeNode level) {
229         addNode(level, new PathElement(currentPath.getLast()));
230     }
231 
232     /*
233      * Needed for do loops
234      * */
235     private void addNewPseudoPathElement(DefaultMutableTreeNode level, DataFlowNode ref) {
236         addNode(level, new PathElement(currentPath.getLast(), ref));
237     }
238 
239     /*
240      * Needed for do loops
241      * */
242     private void addRefPseudoPathElement(DefaultMutableTreeNode level, PathElement ref) {
243         addNode(level, ref);
244     }
245 
246     private boolean equalsPseudoPathElementWithDoBranchNodeInLevel(DefaultMutableTreeNode level) {
247 	DataFlowNode inode = currentPath.getLast();
248 
249         if (!inode.isType(NodeType.DO_EXPR)) {
250             return false;
251         }
252 
253         int childCount = level.getChildCount();
254         DefaultMutableTreeNode child;
255 
256         for (int i = 0; i < childCount; i++) {
257             child = (DefaultMutableTreeNode) level.getChildAt(i);
258             PathElement pe = (PathElement) child.getUserObject();
259             if (pe != null && pe.isPseudoPathElement() && pe.pseudoRef.equals(inode)) {
260                 return true;
261             }
262         }
263         return false;
264     }
265 
266     private PathElement getDoBranchNodeInLevel(DefaultMutableTreeNode level) {
267 	DataFlowNode inode = currentPath.getLast();
268         if (!inode.isType(NodeType.DO_EXPR)) {
269             return null;
270         }
271 
272         int childCount = level.getChildCount();
273         DefaultMutableTreeNode child;
274 
275         for (int i = 0; i < childCount; i++) {
276             child = (DefaultMutableTreeNode) level.getChildAt(i);
277             PathElement pe = (PathElement) child.getUserObject();
278             if (inode.equals(pe.node)) {
279                 return pe;
280             }
281         }
282         return null;
283     }
284 
285     private void addNode(DefaultMutableTreeNode level, PathElement element) {
286         DefaultMutableTreeNode node = new DefaultMutableTreeNode();
287         node.setUserObject(element);
288         level.add(node);
289     }
290 
291     private PathElement isNodeInLevel(DefaultMutableTreeNode level) {
292 	DataFlowNode inode = currentPath.getLast();
293         DefaultMutableTreeNode child = (DefaultMutableTreeNode) level.getFirstChild();
294 
295         if (child != null) {
296             PathElement levelElement = (PathElement) child.getUserObject();
297             if (inode.equals(levelElement.node)) {
298                 return levelElement;
299             }
300         }
301         return null;
302     }
303 
304     private DefaultMutableTreeNode getLastChildNode(DefaultMutableTreeNode node) {
305         if (node.getChildCount() != 0) {
306             return (DefaultMutableTreeNode) node.getLastChild();
307         }
308         return node;
309     }
310 
311     private int countLoops() {
312         DefaultMutableTreeNode treeNode = stack.getLastLeaf();
313         int counter = 0;
314         if (treeNode.getParent() != null) {
315             // for some unknown reasons the parent of treeNode might be null, see bug 1597987
316             int childCount = treeNode.getParent().getChildCount();
317             for (int i = 0; i < childCount; i++) {
318                 DefaultMutableTreeNode tNode = (DefaultMutableTreeNode) treeNode.getParent().getChildAt(i);
319                 PathElement e = (PathElement) tNode.getUserObject();
320                 if (e != null && !e.isPseudoPathElement()) {
321                     counter++;
322                 }
323             }
324         }
325         return counter;
326     }
327 
328     private void incChild() {
329         ((PathElement) stack.getLastLeaf().getUserObject()).currentChild++;
330     }
331 
332 }