001 /*
002 * Created on 09.08.2004
003 */
004 package net.sourceforge.pmd.lang.dfa.pathfinder;
005
006 import javax.swing.tree.DefaultMutableTreeNode;
007
008 import net.sourceforge.pmd.lang.dfa.DataFlowNode;
009 import net.sourceforge.pmd.lang.dfa.NodeType;
010
011 /**
012 * @author raik
013 * <p/>
014 * Finds all paths of a data flow. Each loop will be 0 or 2 times traversed ->
015 * 2 paths. This is special to the data flow anomaly analysis.
016 */
017 public class DAAPathFinder {
018 private static final int MAX_PATHS = 5000;
019
020 private DataFlowNode rootNode;
021 private Executable shim;
022 private CurrentPath currentPath = new CurrentPath();
023 private DefaultMutableTreeNode stack = new DefaultMutableTreeNode();
024 private int maxPaths;
025
026 public DAAPathFinder(DataFlowNode rootNode, Executable shim) {
027 this.rootNode = rootNode;
028 this.shim = shim;
029 this.maxPaths = MAX_PATHS;
030 }
031
032 public DAAPathFinder(DataFlowNode rootNode, Executable shim, int maxPaths) {
033 this.rootNode = rootNode;
034 this.shim = shim;
035 this.maxPaths = maxPaths;
036 }
037
038 public void run() {
039 phase1();
040 }
041
042 /*
043 * Initialise the path search. Starts the searching.
044 * */
045 private void phase1() {
046 currentPath.addLast(rootNode);
047 int i = 0;
048 boolean flag = true;
049 do {
050 i++;
051 // System.out.println("Building path from " + currentPath.getLast());
052 phase2(flag);
053 shim.execute(currentPath);
054 flag = false;
055 } while (i < maxPaths && phase3());
056 }
057
058 /*
059 * Builds up the path.
060 * */
061 private void phase2(boolean flag) {
062 while (!currentPath.isEndNode()) {
063 if (currentPath.isBranch() || currentPath.isFirstDoStatement()) {
064 if (flag) {
065 addNodeToTree();
066 }
067 flag = true;
068 if (countLoops() <= 2) {
069 addCurrentChild();
070 continue;
071 } else {
072 // jump out of that loop
073 addLastChild();
074 continue;
075 }
076 } else {
077 addCurrentChild();
078 }
079 }
080 }
081
082 /*
083 * Decompose the path until it finds a node which branches are not all
084 * traversed.
085 * */
086 private boolean phase3() {
087 while (!currentPath.isEmpty()) {
088 if (currentPath.isBranch()) {
089 if (this.countLoops() == 1) {
090 if (this.hasMoreChildren()) {
091 this.incChild();
092 return true;
093 } else {
094 this.removeFromTree();
095 currentPath.removeLast();
096 }
097 } else {
098 this.removeFromTree();
099 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 }
|