001: /* Soot - a J*va Optimization Framework
002: * Copyright (C) 2003 Ondrej Lhotak
003: *
004: * This library is free software; you can redistribute it and/or
005: * modify it under the terms of the GNU Lesser General Public
006: * License as published by the Free Software Foundation; either
007: * version 2.1 of the License, or (at your option) any later version.
008: *
009: * This library is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
012: * Lesser General Public License for more details.
013: *
014: * You should have received a copy of the GNU Lesser General Public
015: * License along with this library; if not, write to the
016: * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
017: * Boston, MA 02111-1307, USA.
018: */
019:
020: package soot.jimple.toolkits.callgraph;
021:
022: import soot.*;
023: import java.util.*;
024: import soot.util.queue.*;
025:
026: /** Keeps track of the methods transitively reachable from the specified
027: * entry points through the given call graph edges.
028: * @author Ondrej Lhotak
029: */
030: public class ReachableMethods {
031: private CallGraph cg;
032: private Iterator<Edge> edgeSource;
033: private final ChunkedQueue<MethodOrMethodContext> reachables = new ChunkedQueue<MethodOrMethodContext>();
034: private final Set<MethodOrMethodContext> set = new HashSet<MethodOrMethodContext>();
035: private QueueReader<MethodOrMethodContext> unprocessedMethods;
036: private final QueueReader<MethodOrMethodContext> allReachables = reachables
037: .reader();
038: private Filter filter;
039:
040: public ReachableMethods(CallGraph graph,
041: Iterator<MethodOrMethodContext> entryPoints) {
042: this (graph, entryPoints, null);
043: }
044:
045: public ReachableMethods(CallGraph graph,
046: Iterator<MethodOrMethodContext> entryPoints, Filter filter) {
047: this .filter = filter;
048: this .cg = graph;
049: addMethods(entryPoints);
050: unprocessedMethods = reachables.reader();
051: this .edgeSource = graph.listener();
052: if (filter != null)
053: this .edgeSource = filter.wrap(this .edgeSource);
054: }
055:
056: public ReachableMethods(CallGraph graph,
057: Collection<MethodOrMethodContext> entryPoints) {
058: this (graph, entryPoints.iterator());
059: }
060:
061: private void addMethods(Iterator<MethodOrMethodContext> methods) {
062: while (methods.hasNext())
063: addMethod((MethodOrMethodContext) methods.next());
064: }
065:
066: private void addMethod(MethodOrMethodContext m) {
067: if (set.add(m)) {
068: reachables.add(m);
069: }
070: }
071:
072: /** Causes the QueueReader objects to be filled up with any methods
073: * that have become reachable since the last call. */
074: public void update() {
075: while (edgeSource.hasNext()) {
076: Edge e = (Edge) edgeSource.next();
077: if (set.contains(e.getSrc()))
078: addMethod(e.getTgt());
079: }
080: while (unprocessedMethods.hasNext()) {
081: MethodOrMethodContext m = (MethodOrMethodContext) unprocessedMethods
082: .next();
083: Iterator<Edge> targets = cg.edgesOutOf(m);
084: if (filter != null)
085: targets = filter.wrap(targets);
086: addMethods(new Targets(targets));
087: }
088: }
089:
090: /** Returns a QueueReader object containing all methods found reachable
091: * so far, and which will be informed of any new methods that are later
092: * found to be reachable. */
093: public QueueReader<MethodOrMethodContext> listener() {
094: return allReachables.clone();
095: }
096:
097: /** Returns a QueueReader object which will contain ONLY NEW methods
098: * which will be found to be reachable, but not those that have already
099: * been found to be reachable.
100: */
101: public QueueReader<MethodOrMethodContext> newListener() {
102: return reachables.reader();
103: }
104:
105: /** Returns true iff method is reachable. */
106: public boolean contains(MethodOrMethodContext m) {
107: return set.contains(m);
108: }
109:
110: /** Returns the number of methods that are reachable. */
111: public int size() {
112: return set.size();
113: }
114: }
|