View Javadoc

1   // CachedCallGraph.java, created Sat Mar 29  0:56:01 2003 by joewhaley
2   // Copyright (C) 2001-3 John Whaley <jwhaley@alum.mit.edu>
3   // Licensed under the terms of the GNU LGPL; see COPYING for details.
4   package joeq.Compiler.Quad;
5   
6   import java.util.Collection;
7   import java.util.Collections;
8   import java.util.HashSet;
9   import java.util.Iterator;
10  import java.util.LinkedHashSet;
11  import java.util.Set;
12  import joeq.Class.jq_Method;
13  import joeq.Compiler.Analysis.IPA.ProgramLocation;
14  import jwutil.collections.GenericInvertibleMultiMap;
15  import jwutil.collections.GenericMultiMap;
16  import jwutil.collections.InvertibleMultiMap;
17  import jwutil.collections.MultiMap;
18  
19  /***
20   * @author John Whaley <jwhaley@alum.mit.edu>
21   * @version $Id: CachedCallGraph.java 1931 2004-09-22 22:17:47Z joewhaley $
22   */
23  public class CachedCallGraph extends CallGraph {
24  
25      private final CallGraph delegate;
26  
27      private Set/*<jq_Method>*/ methods;
28      private MultiMap/*<jq_Method,ProgramLocation>*/ callSites;
29      private InvertibleMultiMap/*<ProgramLocation,jq_Method>*/ edges;
30  
31      public CachedCallGraph(CallGraph cg) {
32          this.delegate = cg;
33      }
34  
35      public void invalidateCache() {
36          this.edges = new GenericInvertibleMultiMap();
37          this.callSites = new GenericMultiMap();
38          for (Iterator i = delegate.getAllCallSites().iterator(); i.hasNext(); ) {
39              ProgramLocation p = (ProgramLocation) i.next();
40              Collection callees = this.edges.getValues(p);
41              Collection callees2 = delegate.getTargetMethods(p);
42              if (!callees2.isEmpty())
43                  callees.addAll(callees2);
44              else
45                  callSites.add(p.getMethod(), p);
46          }
47          this.methods = new HashSet(delegate.getRoots());
48          for (Iterator i = this.edges.keySet().iterator(); i.hasNext(); ) {
49              ProgramLocation p = (ProgramLocation) i.next();
50              jq_Method m = (jq_Method) p.getMethod();
51              methods.add(m);
52              methods.addAll(this.edges.getValues(p));
53              Collection c = callSites.getValues(m);
54              c.add(p);
55          }
56      }
57  
58      /* (non-Javadoc)
59       * @see joeq.Compiler.Quad.CallGraph#setRoots(java.util.Collection)
60       */
61      public void setRoots(Collection roots) {
62          delegate.setRoots(roots);
63          invalidateCache();
64      }
65  
66      /* (non-Javadoc)
67       * @see joeq.Compiler.Quad.CallGraph#entrySet()
68       */
69      public Set entrySet() {
70          if (edges == null) invalidateCache();
71          return edges.entrySet();
72      }
73  
74      /* (non-Javadoc)
75       * @see joeq.Compiler.Quad.CallGraph#getAllCallSites()
76       */
77      public Collection getAllCallSites() {
78          if (edges == null) invalidateCache();
79          if (true) {
80              return edges.keySet();
81          } else {
82              return callSites.values();
83          }
84      }
85  
86      /* (non-Javadoc)
87       * @see joeq.Compiler.Quad.CallGraph#getAllMethods()
88       */
89      public Collection getAllMethods() {
90          if (edges == null) invalidateCache();
91          if (true) {
92              return methods;
93          } else {
94              LinkedHashSet allMethods = new LinkedHashSet(edges.values());
95              allMethods.addAll(delegate.getRoots());
96              return allMethods;
97          }
98      }
99  
100     /* (non-Javadoc)
101      * @see joeq.Compiler.Quad.CallGraph#getCallees(joeq.Compiler.Quad.ControlFlowGraph)
102      */
103     public Collection getCallees(ControlFlowGraph cfg) {
104         return getCallees(cfg.getMethod());
105     }
106 
107     /* (non-Javadoc)
108      * @see joeq.Compiler.Quad.CallGraph#getCallees(joeq.Class.jq_Method)
109      */
110     public Collection getCallees(jq_Method caller) {
111         if (edges == null) invalidateCache();
112         return getFromMultiMap(callSites, edges, caller);
113     }
114 
115     public static Collection getFromMultiMap(MultiMap m1, MultiMap m2, jq_Method method) {
116         Collection c1 = m1.getValues(method);
117         Iterator i = c1.iterator();
118         if (!i.hasNext()) return Collections.EMPTY_SET;
119         Object o = i.next();
120         if (!i.hasNext()) return m2.getValues(o);
121         Set result = new LinkedHashSet();
122         for (;;) {
123             result.addAll(m2.getValues(o));
124             if (!i.hasNext()) break;
125             o = i.next();
126         }
127         return result;
128     }
129     
130     /* (non-Javadoc)
131      * @see joeq.Compiler.Quad.CallGraph#getCallerMethods(joeq.Class.jq_Method)
132      */
133     public Collection getCallers(jq_Method callee) {
134         if (edges == null) invalidateCache();
135         MultiMap m1 = edges.invert();
136         Collection c1 = m1.getValues(callee);
137         return c1;
138     }
139 
140     /* (non-Javadoc)
141      * @see joeq.Compiler.Quad.CallGraph#getCallerMethods(joeq.Class.jq_Method)
142      */
143     public Collection getCallerMethods(jq_Method callee) {
144         if (edges == null) invalidateCache();
145         MultiMap m1 = edges.invert();
146         Collection c1 = m1.getValues(callee);
147         Iterator i = c1.iterator();
148         if (!i.hasNext()) return Collections.EMPTY_SET;
149         ProgramLocation o = (ProgramLocation) i.next();
150         if (!i.hasNext()) return Collections.singleton(o.getMethod());
151         Set result = new LinkedHashSet();
152         for (;;) {
153             result.add(o.getMethod());
154             if (!i.hasNext()) break;
155             o = (ProgramLocation) i.next();
156         }
157         return result;
158     }
159 
160     /* (non-Javadoc)
161      * @see joeq.Compiler.Quad.CallGraph#getCallSites(joeq.Compiler.Quad.ControlFlowGraph)
162      */
163     public Collection getCallSites(ControlFlowGraph cfg) {
164         return getCallSites(cfg.getMethod());
165     }
166 
167     /* (non-Javadoc)
168      * @see joeq.Compiler.Quad.CallGraph#getCallSites(joeq.Class.jq_Method)
169      */
170     public Collection getCallSites(jq_Method caller) {
171         if (callSites == null) invalidateCache();
172         return callSites.getValues(caller);
173     }
174 
175     /* (non-Javadoc)
176      * @see joeq.Compiler.Quad.CallGraph#getTargetMethods(java.lang.Object, joeq.Compiler.Analysis.IPA.ProgramLocation)
177      */
178     public Collection getTargetMethods(Object context, ProgramLocation callSite) {
179         if (edges == null) invalidateCache();
180         return edges.getValues(callSite);
181     }
182     
183     /***
184      * Inline the given edge in the call graph.
185      * 
186      * @param caller  caller method
187      * @param callSite  call site to inline
188      * @param callee  callee method
189      */
190     public void inlineEdge(jq_Method caller, ProgramLocation callSite, jq_Method callee) {
191         if (false) System.out.println("Inlining edge "+callSite+" -> "+callee);
192         // remove call site from caller.
193         callSites.remove(caller, callSite);
194         // add all call sites in callee into caller.
195         callSites.addAll(caller, callSites.getValues(callee));
196     }
197 
198     /* (non-Javadoc)
199      * @see java.util.AbstractMap#keySet()
200      */
201     public Set keySet() {
202         if (edges == null) invalidateCache();
203         return edges.keySet();
204     }
205 
206     /* (non-Javadoc)
207      * @see joeq.Compiler.Quad.CallGraph#getRoots()
208      */
209     public Collection getRoots() {
210         return delegate.getRoots();
211     }
212 
213 }