001: /*
002: * Bytecode Analysis Framework
003: * Copyright (C) 2003,2004 University of Maryland
004: *
005: * This library is free software; you can redistribute it and/or
006: * modify it under the terms of the GNU Lesser General Public
007: * License as published by the Free Software Foundation; either
008: * version 2.1 of the License, or (at your option) any later version.
009: *
010: * This library is distributed in the hope that it will be useful,
011: * but WITHOUT ANY WARRANTY; without even the implied warranty of
012: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
013: * Lesser General Public License for more details.
014: *
015: * You should have received a copy of the GNU Lesser General Public
016: * License along with this library; if not, write to the Free Software
017: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
018: */
019:
020: package edu.umd.cs.findbugs.ba;
021:
022: import java.util.Iterator;
023: import java.util.LinkedList;
024: import java.util.List;
025:
026: import edu.umd.cs.findbugs.SystemProperties;
027:
028: /**
029: * Object to enumerate (some subset of) the simple paths in a CFG.
030: * A simple path is a path from entry to exit, ignoring backedges
031: * and unhandled exceptions.
032: * <p/>
033: * <p> FIXME: instead of storing the simple paths,
034: * should invoke a callback as each simple path is produced.
035: * That would save memory.
036: *
037: * @author David Hovemeyer
038: * @see CFG
039: */
040: public class SimplePathEnumerator implements EdgeTypes, DFSEdgeTypes {
041: private CFG cfg;
042: private DepthFirstSearch dfs;
043: private int maxPaths;
044: private int maxWork;
045: private int work;
046: private List<List<Edge>> pathList;
047:
048: private static final boolean DEBUG = SystemProperties
049: .getBoolean("spe.debug");
050:
051: /**
052: * Default number of steps to be performed in path enumeration.
053: */
054: public static final int DEFAULT_MAX_WORK = 200000;
055:
056: /**
057: * Constructor.
058: *
059: * @param cfg the control flow graph to enumerate simple paths of
060: * @param maxPaths maximum number of simple paths to find
061: * @param maxWork maximum number of steps to be performed in the path
062: * enumeration (to handle exponential blowup of search space)
063: */
064: public SimplePathEnumerator(CFG cfg, int maxPaths, int maxWork) {
065: this .cfg = cfg;
066: this .dfs = new DepthFirstSearch(cfg);
067: dfs.search();
068: this .maxPaths = maxPaths;
069: this .maxWork = maxWork;
070: this .work = 0;
071: this .pathList = new LinkedList<List<Edge>>();
072: }
073:
074: /**
075: * Constructor; max work is set to DEFAULT_MAX_WORK.
076: *
077: * @param cfg the control flow graph to enumerate simple paths of
078: * @param maxPaths maximum number of simple paths to find
079: */
080: public SimplePathEnumerator(CFG cfg, int maxPaths) {
081: this (cfg, maxPaths, DEFAULT_MAX_WORK);
082: }
083:
084: /**
085: * Enumerate the simple paths.
086: *
087: * @return this object
088: */
089: public SimplePathEnumerator enumerate() {
090: Iterator<Edge> entryOut = cfg.outgoingEdgeIterator(cfg
091: .getEntry());
092: if (!entryOut.hasNext())
093: throw new IllegalStateException();
094: Edge entryEdge = entryOut.next();
095:
096: LinkedList<Edge> init = new LinkedList<Edge>();
097: init.add(entryEdge);
098:
099: work(init);
100: if (DEBUG && work == maxWork)
101: System.out.println("**** Reached max work! ****");
102:
103: return this ;
104: }
105:
106: /**
107: * Iterate over simple paths.
108: */
109: public Iterator<List<Edge>> iterator() {
110: return pathList.iterator();
111: }
112:
113: private void work(LinkedList<Edge> partialPath) {
114: if (pathList.size() == maxPaths)
115: return;
116:
117: Edge last = partialPath.getLast();
118:
119: // Is this a complete path?
120: if (last.getTarget() == cfg.getExit()) {
121: pathList.add(new LinkedList<Edge>(partialPath));
122: return;
123: }
124:
125: // Look for non-backedge, non-unhandled-exception outgoing edges, and recur.
126: Iterator<Edge> i = cfg.outgoingEdgeIterator(last.getTarget());
127: while (i.hasNext()) {
128: Edge outEdge = i.next();
129:
130: // Ignore back edges and unhandled exception edges
131: if (dfs.getDFSEdgeType(outEdge) == BACK_EDGE
132: || outEdge.getType() == UNHANDLED_EXCEPTION_EDGE)
133: continue;
134:
135: // Add the edge to the current partial path, and recur
136: partialPath.add(outEdge);
137: work(partialPath);
138: partialPath.removeLast();
139:
140: // Have we done the maximum amount of work?
141: if (work == maxWork)
142: return;
143: ++work;
144:
145: // Did we reach the maximum number of simple paths?
146: if (pathList.size() == maxPaths)
147: return;
148: }
149: }
150: }
151:
152: // vim:ts=4
|