KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > edu > umd > cs > findbugs > ba > SimplePathEnumerator


1 /*
2  * Bytecode Analysis Framework
3  * Copyright (C) 2003,2004 University of Maryland
4  *
5  * This library is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Lesser General Public
7  * License as published by the Free Software Foundation; either
8  * version 2.1 of the License, or (at your option) any later version.
9  *
10  * This library is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  * Lesser General Public License for more details.
14  *
15  * You should have received a copy of the GNU Lesser General Public
16  * License along with this library; if not, write to the Free Software
17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18  */
19
20 package edu.umd.cs.findbugs.ba;
21
22 import java.util.Iterator JavaDoc;
23 import java.util.LinkedList JavaDoc;
24 import java.util.List JavaDoc;
25
26 import edu.umd.cs.findbugs.SystemProperties;
27
28 /**
29  * Object to enumerate (some subset of) the simple paths in a CFG.
30  * A simple path is a path from entry to exit, ignoring backedges
31  * and unhandled exceptions.
32  * <p/>
33  * <p> FIXME: instead of storing the simple paths,
34  * should invoke a callback as each simple path is produced.
35  * That would save memory.
36  *
37  * @author David Hovemeyer
38  * @see CFG
39  */
40 public class SimplePathEnumerator implements EdgeTypes, DFSEdgeTypes {
41     private CFG cfg;
42     private DepthFirstSearch dfs;
43     private int maxPaths;
44     private int maxWork;
45     private int work;
46     private List JavaDoc<List JavaDoc<Edge>> pathList;
47
48     private static final boolean DEBUG = SystemProperties.getBoolean("spe.debug");
49
50     /**
51      * Default number of steps to be performed in path enumeration.
52      */
53     public static final int DEFAULT_MAX_WORK = 200000;
54
55     /**
56      * Constructor.
57      *
58      * @param cfg the control flow graph to enumerate simple paths of
59      * @param maxPaths maximum number of simple paths to find
60      * @param maxWork maximum number of steps to be performed in the path
61      * enumeration (to handle exponential blowup of search space)
62      */
63     public SimplePathEnumerator(CFG cfg, int maxPaths, int maxWork) {
64         this.cfg = cfg;
65         this.dfs = new DepthFirstSearch(cfg);
66         dfs.search();
67         this.maxPaths = maxPaths;
68         this.maxWork = maxWork;
69         this.work = 0;
70         this.pathList = new LinkedList JavaDoc<List JavaDoc<Edge>>();
71     }
72
73     /**
74      * Constructor; max work is set to DEFAULT_MAX_WORK.
75      *
76      * @param cfg the control flow graph to enumerate simple paths of
77      * @param maxPaths maximum number of simple paths to find
78      */
79     public SimplePathEnumerator(CFG cfg, int maxPaths) {
80         this(cfg, maxPaths, DEFAULT_MAX_WORK);
81     }
82
83     /**
84      * Enumerate the simple paths.
85      *
86      * @return this object
87      */
88     public SimplePathEnumerator enumerate() {
89         Iterator JavaDoc<Edge> entryOut = cfg.outgoingEdgeIterator(cfg.getEntry());
90         if (!entryOut.hasNext()) throw new IllegalStateException JavaDoc();
91         Edge entryEdge = entryOut.next();
92
93         LinkedList JavaDoc<Edge> init = new LinkedList JavaDoc<Edge>();
94         init.add(entryEdge);
95
96         work(init);
97         if (DEBUG && work == maxWork) System.out.println("**** Reached max work! ****");
98
99         return this;
100     }
101
102     /**
103      * Iterate over simple paths.
104      */
105     public Iterator JavaDoc<List JavaDoc<Edge>> iterator() {
106         return pathList.iterator();
107     }
108
109     private void work(LinkedList JavaDoc<Edge> partialPath) {
110         if (pathList.size() == maxPaths)
111             return;
112
113         Edge last = partialPath.getLast();
114
115         // Is this a complete path?
116 if (last.getTarget() == cfg.getExit()) {
117             pathList.add(new LinkedList JavaDoc<Edge>(partialPath));
118             return;
119         }
120
121         // Look for non-backedge, non-unhandled-exception outgoing edges, and recur.
122 Iterator JavaDoc<Edge> i = cfg.outgoingEdgeIterator(last.getTarget());
123         while (i.hasNext()) {
124             Edge outEdge = i.next();
125
126             // Ignore back edges and unhandled exception edges
127 if (dfs.getDFSEdgeType(outEdge) == BACK_EDGE || outEdge.getType() == UNHANDLED_EXCEPTION_EDGE)
128                 continue;
129
130             // Add the edge to the current partial path, and recur
131 partialPath.add(outEdge);
132             work(partialPath);
133             partialPath.removeLast();
134
135             // Have we done the maximum amount of work?
136 if (work == maxWork)
137                 return;
138             ++work;
139
140             // Did we reach the maximum number of simple paths?
141 if (pathList.size() == maxPaths)
142                 return;
143         }
144     }
145 }
146
147 // vim:ts=4
148
Popular Tags