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