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