001: /*
002: * Created on 09.08.2004
003: */
004: package net.sourceforge.pmd.dfa.pathfinder;
005:
006: import net.sourceforge.pmd.dfa.IDataFlowNode;
007: import net.sourceforge.pmd.dfa.NodeType;
008:
009: import javax.swing.tree.DefaultMutableTreeNode;
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 IDataFlowNode 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(IDataFlowNode rootNode, Executable shim) {
027: this .rootNode = rootNode;
028: this .shim = shim;
029: this .maxPaths = MAX_PATHS;
030: }
031:
032: public DAAPathFinder(IDataFlowNode rootNode, Executable shim,
033: int maxPaths) {
034: this .rootNode = rootNode;
035: this .shim = shim;
036: this .maxPaths = maxPaths;
037: }
038:
039: public void run() {
040: phase1();
041: }
042:
043: /*
044: * Initialise the path search. Starts the searching.
045: * */
046: private void phase1() {
047: currentPath.addLast(rootNode);
048: int i = 0;
049: boolean flag = true;
050: do {
051: i++;
052: // System.out.println("Building path from " + currentPath.getLast());
053: phase2(flag);
054: shim.execute(currentPath);
055: flag = false;
056: } while (i < maxPaths && phase3());
057: }
058:
059: /*
060: * Builds up the path.
061: * */
062: private void phase2(boolean flag) {
063: while (!currentPath.isEndNode()) {
064: if (currentPath.isBranch()
065: || currentPath.isFirstDoStatement()) {
066: if (flag) {
067: addNodeToTree();
068: }
069: flag = true;
070: if (countLoops() <= 2) {
071: addCurrentChild();
072: continue;
073: } else {
074: // jump out of that loop
075: addLastChild();
076: continue;
077: }
078: } else {
079: addCurrentChild();
080: }
081: }
082: }
083:
084: /*
085: * Decompose the path until it finds a node which branches are not all
086: * traversed.
087: * */
088: private boolean phase3() {
089: while (!currentPath.isEmpty()) {
090: if (currentPath.isBranch()) {
091: if (this .countLoops() == 1) {
092: if (this .hasMoreChildren()) {
093: this .incChild();
094: return true;
095: } else {
096: this .removeFromTree();
097: currentPath.removeLast();
098: }
099: } else {
100: this .removeFromTree();
101: currentPath.removeLast();
102: }
103: } else {
104: currentPath.removeLast();
105: }
106: }
107: return false;
108: }
109:
110: private boolean hasMoreChildren() {
111: PathElement e = (PathElement) stack.getLastLeaf()
112: .getUserObject();
113: return e.currentChild + 1 < e.node.getChildren().size();
114: }
115:
116: private void addLastChild() {
117: PathElement e = (PathElement) stack.getLastLeaf()
118: .getUserObject();
119: for (int i = e.node.getChildren().size() - 1; i >= 0; i--) {
120: if (i != e.currentChild) {
121: currentPath.addLast(e.node.getChildren().get(i));
122: break;
123: }
124: }
125: }
126:
127: private void addCurrentChild() {
128: if (currentPath.isBranch()) { // TODO WHY????
129: PathElement last = (PathElement) stack.getLastLeaf()
130: .getUserObject();
131: IDataFlowNode inode = currentPath.getLast();
132: if (inode.getChildren().size() > last.currentChild) {
133: // for some unknown reasons last.currentChild might not be a children of inode, see bug 1597987
134: IDataFlowNode child = inode.getChildren().get(
135: last.currentChild);
136: this .currentPath.addLast(child);
137: }
138: } else {
139: IDataFlowNode inode = currentPath.getLast();
140: IDataFlowNode child = inode.getChildren().get(0); //TODO ???? IMPORTANT - ERROR?
141: this .currentPath.addLast(child);
142: }
143: }
144:
145: // ----------------------------------------------------------------------------
146: // TREE FUNCTIONS
147:
148: /*
149: * Adds a PathElement to a Tree, which contains information about
150: * loops and "local scopes - encapsulation".
151: * */
152: private void addNodeToTree() {
153: if (currentPath.isFirstDoStatement()) {
154: DefaultMutableTreeNode level = stack;
155: IDataFlowNode doBranch = currentPath
156: .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
180: .equalsPseudoPathElementWithDoBranchNodeInLevel(level)) {
181: level = this .getLastChildNode(level);
182: if (level.getChildCount() == 0) {
183: break;
184: }
185: }
186: PathElement ref = this .getDoBranchNodeInLevel(level);
187: if (ref != null) {
188: addNode(level, ref);
189: } else {
190: this .addNewPathElement(level);
191: }
192:
193: } else {
194: while (true) {
195: if (level.getChildCount() != 0) {
196: PathElement ref;
197: if ((ref = this .isNodeInLevel(level)) != null) {
198: addNode(level, ref);
199: break;
200: } else {
201: level = this .getLastChildNode(level);
202: continue;
203: }
204: } else {
205: this .addNewPathElement(level);
206: break;
207: }
208: }
209: }
210: }
211: }
212:
213: private void removeFromTree() {
214: DefaultMutableTreeNode last = stack.getLastLeaf();
215: if (last == null) {
216: System.out.println("removeFromTree - last == null");
217: return;
218: }
219: DefaultMutableTreeNode parent = (DefaultMutableTreeNode) last
220: .getParent();
221: if (parent != null) {
222: // for some unknown reasons parent might be null, see bug 1597987
223: parent.remove(last);
224: }
225: last = stack.getLastLeaf();
226: if (last == null || last.getUserObject() == null)
227: return;
228:
229: PathElement e = (PathElement) last.getUserObject();
230: if (e != null && e.isPseudoPathElement()) {
231: this .removeFromTree();
232: }
233: }
234:
235: private void addNewPathElement(DefaultMutableTreeNode level) {
236: addNode(level, new PathElement(currentPath.getLast()));
237: }
238:
239: /*
240: * Needed for do loops
241: * */
242: private void addNewPseudoPathElement(DefaultMutableTreeNode level,
243: IDataFlowNode ref) {
244: addNode(level, new PathElement(currentPath.getLast(), ref));
245: }
246:
247: /*
248: * Needed for do loops
249: * */
250: private void addRefPseudoPathElement(DefaultMutableTreeNode level,
251: PathElement ref) {
252: addNode(level, ref);
253: }
254:
255: private boolean equalsPseudoPathElementWithDoBranchNodeInLevel(
256: DefaultMutableTreeNode level) {
257: IDataFlowNode inode = currentPath.getLast();
258:
259: if (!inode.isType(NodeType.DO_EXPR))
260: return false;
261:
262: int childCount = level.getChildCount();
263: DefaultMutableTreeNode child;
264:
265: for (int i = 0; i < childCount; i++) {
266: child = (DefaultMutableTreeNode) level.getChildAt(i);
267: PathElement pe = (PathElement) child.getUserObject();
268: if (pe != null && pe.isPseudoPathElement()
269: && pe.pseudoRef.equals(inode)) {
270: return true;
271: }
272: }
273: return false;
274: }
275:
276: private PathElement getDoBranchNodeInLevel(
277: DefaultMutableTreeNode level) {
278: IDataFlowNode inode = currentPath.getLast();
279: if (!inode.isType(NodeType.DO_EXPR))
280: return null;
281:
282: int childCount = level.getChildCount();
283: DefaultMutableTreeNode child;
284:
285: for (int i = 0; i < childCount; i++) {
286: child = (DefaultMutableTreeNode) level.getChildAt(i);
287: PathElement pe = (PathElement) child.getUserObject();
288: if (inode.equals(pe.node)) {
289: return pe;
290: }
291: }
292: return null;
293: }
294:
295: private void addNode(DefaultMutableTreeNode level,
296: PathElement element) {
297: DefaultMutableTreeNode node = new DefaultMutableTreeNode();
298: node.setUserObject(element);
299: level.add(node);
300: }
301:
302: private PathElement isNodeInLevel(DefaultMutableTreeNode level) {
303: IDataFlowNode inode = currentPath.getLast();
304: DefaultMutableTreeNode child = (DefaultMutableTreeNode) level
305: .getFirstChild();
306:
307: if (child != null) {
308: PathElement levelElement = (PathElement) child
309: .getUserObject();
310: if (inode.equals(levelElement.node)) {
311: return levelElement;
312: }
313: }
314: return null;
315: }
316:
317: private DefaultMutableTreeNode getLastChildNode(
318: DefaultMutableTreeNode node) {
319: if (node.getChildCount() != 0) {
320: return (DefaultMutableTreeNode) node.getLastChild();
321: }
322: return node;
323: }
324:
325: private int countLoops() {
326: DefaultMutableTreeNode treeNode = stack.getLastLeaf();
327: int counter = 0;
328: if (treeNode.getParent() != null) {
329: // for some unknown reasons the parent of treeNode might be null, see bug 1597987
330: int childCount = treeNode.getParent().getChildCount();
331: for (int i = 0; i < childCount; i++) {
332: DefaultMutableTreeNode tNode = (DefaultMutableTreeNode) treeNode
333: .getParent().getChildAt(i);
334: PathElement e = (PathElement) tNode.getUserObject();
335: if (e != null && !e.isPseudoPathElement()) {
336: counter++;
337: }
338: }
339: }
340: return counter;
341: }
342:
343: private void incChild() {
344: ((PathElement) stack.getLastLeaf().getUserObject()).currentChild++;
345: }
346:
347: }
|