View Javadoc

1   // LoadedCallGraph.java, created Jun 27, 2003 12:46:40 AM by joewhaley
2   // Copyright (C) 2003 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.Comparator;
9   import java.util.Iterator;
10  import java.util.LinkedHashSet;
11  import java.util.Map;
12  import java.util.Set;
13  import java.util.StringTokenizer;
14  import java.util.TreeMap;
15  import java.io.BufferedWriter;
16  import java.io.DataInput;
17  import java.io.DataInputStream;
18  import java.io.FileInputStream;
19  import java.io.IOException;
20  import joeq.Class.jq_Class;
21  import joeq.Class.jq_FakeInstanceMethod;
22  import joeq.Class.jq_Member;
23  import joeq.Class.jq_Method;
24  import joeq.Class.jq_Type;
25  import joeq.Compiler.Analysis.IPA.ProgramLocation;
26  import joeq.Compiler.Analysis.IPA.ProgramLocation.BCProgramLocation;
27  import jwutil.collections.GenericInvertibleMultiMap;
28  import jwutil.collections.GenericMultiMap;
29  import jwutil.collections.InvertibleMultiMap;
30  import jwutil.collections.MapFactory;
31  import jwutil.collections.MultiMap;
32  import jwutil.collections.SetFactory;
33  import jwutil.collections.SortedArraySet;
34  import jwutil.util.Assert;
35  
36  /***
37   * A call graph that is loaded from a file.
38   * 
39   * @author John Whaley
40   * @version $Id: LoadedCallGraph.java 2456 2006-04-06 02:31:41Z mcmartin $
41   */
42  public class LoadedCallGraph extends CallGraph {
43  
44      public static Comparator type_comparator = new Comparator() {
45          public int compare(Object o1, Object o2) {
46              String s1 = ((jq_Type) o1).getDesc().toString();
47              String s2 = ((jq_Type) o2).getDesc().toString();
48              return s1.compareTo(s2);
49          }
50      };
51      public static Comparator member_comparator = new Comparator() {
52          public int compare(Object o1, Object o2) {
53              String s1 = ((jq_Member) o1).getNameAndDesc().toString();
54              String s2 = ((jq_Member) o2).getNameAndDesc().toString();
55              return s1.compareTo(s2);
56          }
57      };
58      public static Comparator callsite_comparator = new Comparator() {
59          public int compare(Object o1, Object o2) {
60              ProgramLocation p1 = (ProgramLocation) o1;
61              ProgramLocation p2 = (ProgramLocation) o2;
62              Assert._assert(p1.getMethod() == p2.getMethod());
63              int i1 = p1.getBytecodeIndex();
64              int i2 = p2.getBytecodeIndex();
65              if (i1 < i2) return -1;
66              if (i1 > i2) return 1;
67  //            Assert._assert(o1 == o2);
68              return 0;
69          }
70      };
71      
72      public static final MapFactory treeMapFactory = new MapFactory() {
73          public Map makeMap(Map map) {
74              TreeMap m = new TreeMap(type_comparator);
75              m.putAll(map);
76              return m;
77          }
78      };
79      
80      public static final SortedArraySetFactory sortedArraySetFactory = new SortedArraySetFactory();
81      
82      public static class SortedArraySetFactory extends SetFactory {
83          /***
84           * Version ID for serialization.
85           */
86          private static final long serialVersionUID = 3906646414531702833L;
87          
88          public Set makeSet(Comparator c1, Collection c2) {
89              Set s = SortedArraySet.FACTORY.makeSet(c1);
90              s.addAll(c2);
91              return s;
92          }
93          public Set makeSet(Collection c) {
94              return makeSet(member_comparator, c);
95          }
96      }
97      
98      public static void write(CallGraph cg, BufferedWriter out) throws IOException {
99          Assert._assert(cg.getAllMethods().containsAll(cg.getRoots()));
100         MultiMap classesToMethods = new GenericMultiMap(treeMapFactory, sortedArraySetFactory);
101         for (Iterator i = cg.getAllMethods().iterator(); i.hasNext(); ) {
102             jq_Method m = (jq_Method) i.next();
103             if (m == null) continue;
104             classesToMethods.add(m.getDeclaringClass(), m);
105         }
106         for (Iterator i = classesToMethods.keySet().iterator(); i.hasNext(); ) {
107             jq_Class klass = (jq_Class) i.next();
108             out.write("CLASS "+klass.getJDKName().replace('.', '/')+"\n");
109             for (Iterator j = classesToMethods.getValues(klass).iterator(); j.hasNext(); ) {
110                 jq_Method m = (jq_Method) j.next();
111                 out.write(" METHOD "+m.getName()+" "+m.getDesc());
112                 if (cg.getRoots().contains(m)) out.write(" ROOT");
113                 if (m instanceof jq_FakeInstanceMethod) out.write(" FAKE");
114                 out.write('\n');
115                 // put them in a set for deterministic iteration.
116                 Set s = sortedArraySetFactory.makeSet(callsite_comparator, cg.getCallSites(m));
117                 for (Iterator k = s.iterator(); k.hasNext(); ) {
118                     ProgramLocation pl = (ProgramLocation) k.next();
119                     out.write("  CALLSITE "+pl.getBytecodeIndex()+"\n");
120                     // put them in a set for deterministic iteration.
121                     Set s2 = sortedArraySetFactory.makeSet(cg.getTargetMethods(pl));
122                     for (Iterator l = s2.iterator(); l.hasNext(); ) {
123                         jq_Method target = (jq_Method) l.next();
124                         if (target == null) continue;
125                         out.write("   TARGET "+target.getDeclaringClass().getJDKName().replace('.', '/')+"."+target.getName()+" "+target.getDesc());
126                         if (target instanceof jq_FakeInstanceMethod)
127                             out.write(" FAKE");
128                         out.write("\n");
129                     }
130                 }
131             }
132         }
133     }
134 
135     protected Set/*<jq_Method>*/ methods;
136     protected Set/*<jq_Method>*/ roots;
137     protected MultiMap/*<jq_Method,Integer>*/ callSites;
138     protected InvertibleMultiMap/*<ProgramLocation,jq_Method>*/ edges;
139     protected boolean bcCallSites;
140     private static final boolean MAPPING_OFF = false;
141 
142     public LoadedCallGraph(String filename) throws IOException {
143         this.methods = new LinkedHashSet();
144         this.roots = new LinkedHashSet();
145         this.callSites = new GenericMultiMap();
146         this.edges = new GenericInvertibleMultiMap();
147         DataInput in = new DataInputStream(new FileInputStream(filename));
148         read(in);
149     }
150     
151     protected void read(DataInput in) throws IOException {
152         jq_Class k = null;
153         jq_Method m = null;
154         int bcIndex = -1;
155         for (;;) {
156             String s = in.readLine();
157             if (s == null)
158                 break;
159             s = s.trim();
160             StringTokenizer st = new StringTokenizer(s, ". ");
161             if (!st.hasMoreTokens())
162                 break;
163             String id = st.nextToken();
164             if (id.equals("CLASS")) {
165                 if (!st.hasMoreTokens())
166                     throw new IOException();
167                 String className = st.nextToken();
168                 k = (jq_Class) jq_Type.parseType(className);
169                 k.load();
170                 continue;
171             }
172             if (id.equals("METHOD")) {
173                 if (!st.hasMoreTokens())
174                     throw new IOException();
175                 String methodName = st.nextToken();
176                 if (!st.hasMoreTokens())
177                     throw new IOException();
178                 String methodDesc = st.nextToken();
179                 boolean isroot = false;
180                 boolean isfake = false;
181                 while (st.hasMoreTokens()) {
182                     String arg = st.nextToken();
183                     if (arg.equals("ROOT")) isroot = true;
184                     if (arg.equals("FAKE")) isfake = true;
185                 }
186                 if (isfake)
187                     m = jq_FakeInstanceMethod.fakeMethod(k, methodName, methodDesc);
188                 else
189                     m = (jq_Method) k.getDeclaredMember(methodName, methodDesc);
190                 if (m == null) {
191                     System.err.println("Cannot find \""+methodName+"\" \""+methodDesc+"\" in "+k);
192                     continue;
193                 }
194                 methods.add(m);
195                 if (isroot)
196                     roots.add(m);
197                 continue;
198             }
199             if (id.equals("CALLSITE")) {
200                 if (!st.hasMoreTokens())
201                     throw new IOException();
202                 String num = st.nextToken();
203                 bcIndex = Integer.parseInt(num);
204                 bcCallSites = true;
205                 continue;
206             }
207             if (id.equals("TARGET")) {
208                 if (!st.hasMoreTokens())
209                     throw new IOException();
210                 String className = st.nextToken();
211                 if (!st.hasMoreTokens())
212                     throw new IOException();
213                 String methodName = st.nextToken();
214                 if (!st.hasMoreTokens())
215                     throw new IOException();
216                 String methodDesc = st.nextToken();
217                 boolean isfake = false;
218                 if (st.hasMoreTokens()) {
219                     String arg = st.nextToken();
220                     if (arg.equals("FAKE"))
221                         isfake = true;
222                 }
223                     
224                 jq_Class targetClass = (jq_Class) jq_Type.parseType(className);
225                 targetClass.load();
226                 jq_Method targetMethod;
227                 if (isfake)
228                     targetMethod = jq_FakeInstanceMethod.fakeMethod(targetClass, methodName, methodDesc);
229                 else
230                     targetMethod = (jq_Method) targetClass.getDeclaredMember(methodName, methodDesc);
231                 if (m == null) {
232                     // reported above.
233                     continue;
234                 }
235                 if (targetMethod == null) {
236                     System.err.println("Cannot find \""+methodName+"\" \""+methodDesc+"\" in "+targetClass);
237                     continue;
238                 }
239                 add(m, bcIndex, targetMethod);
240                 continue;
241             }
242         }
243     }
244 
245     public void add(jq_Method caller, int bcIndex, jq_Method callee) {
246         ProgramLocation pl = new BCProgramLocation(caller, bcIndex);
247         callSites.add(caller, pl);
248         edges.add(pl, callee);
249     }
250 
251     /* (non-Javadoc)
252      * @see joeq.Compiler.Quad.CallGraph#setRoots(java.util.Collection)
253      */
254     public void setRoots(Collection roots) {
255         // Root set should be the same!
256         Assert._assert(this.roots.equals(roots));
257     }
258 
259     /* (non-Javadoc)
260      * @see joeq.Compiler.Quad.CallGraph#getRoots()
261      */
262     public Collection getRoots() {
263         return roots;
264     }
265 
266     /* (non-Javadoc)
267      * @see joeq.Compiler.Quad.CallGraph#getTargetMethods(java.lang.Object, Compiler.Quad.ProgramLocation)
268      */
269     public Collection getTargetMethods(Object context, ProgramLocation callSite) {
270         if (callSite instanceof ProgramLocation.QuadProgramLocation) {
271             callSite = mapCall(callSite);
272         }
273         return edges.getValues(callSite);
274     }
275 
276     /* (non-Javadoc)
277      * @see joeq.Compiler.Quad.CallGraph#entrySet()
278      */
279     public Set entrySet() {
280         return edges.entrySet();
281     }
282 
283     /* (non-Javadoc)
284      * @see joeq.Compiler.Quad.CallGraph#getAllCallSites()
285      */
286     public Collection getAllCallSites() {
287         return edges.keySet();
288     }
289 
290     /* (non-Javadoc)
291      * @see joeq.Compiler.Quad.CallGraph#getAllMethods()
292      */
293     public Collection getAllMethods() {
294         return methods;
295     }
296 
297     /* (non-Javadoc)
298      * @see joeq.Compiler.Quad.CallGraph#getCallees(joeq.Class.jq_Method)
299      */
300     public Collection getCallees(jq_Method caller) {
301         Collection c = CachedCallGraph.getFromMultiMap(callSites, edges, caller);
302         return c;
303     }
304     
305     /* (non-Javadoc)
306      * @see joeq.Compiler.Quad.CallGraph#getCallers(joeq.Class.jq_Method)
307      */
308     public Collection getCallers(jq_Method callee) {
309         MultiMap m1 = edges.invert();
310         Collection c1 = m1.getValues(callee);
311         return c1;
312     }
313     
314     /* (non-Javadoc)
315      * @see joeq.Compiler.Quad.CallGraph#getCallerMethods(joeq.Class.jq_Method)
316      */
317     public Collection getCallerMethods(jq_Method callee) {
318         MultiMap m1 = edges.invert();
319         Collection c1 = m1.getValues(callee);
320         Iterator i = c1.iterator();
321         if (!i.hasNext()) {
322             return Collections.EMPTY_SET;
323         }
324         ProgramLocation o = (ProgramLocation) i.next();
325         if (!i.hasNext()) {
326             return Collections.singleton(o.getMethod());
327         }
328         Set result = new LinkedHashSet();
329         for (;;) {
330             result.add(o.getMethod());
331             if (!i.hasNext()) break;
332             o = (ProgramLocation) i.next();
333         }
334         return result;
335     }
336     
337     /* (non-Javadoc)
338      * @see joeq.Compiler.Quad.CallGraph#getCallSites(joeq.Class.jq_Method)
339      */
340     public Collection getCallSites(jq_Method caller) {
341         Collection c = callSites.getValues(caller);
342         return c;
343     }
344 
345     /* (non-Javadoc)
346      * @see java.util.AbstractMap#keySet()
347      */
348     public Set keySet() {
349         return edges.keySet();
350     }
351 
352     public static ProgramLocation mapCall(ProgramLocation callSite) {
353         if(!MAPPING_OFF){
354             if (callSite instanceof ProgramLocation.QuadProgramLocation) {
355                 jq_Method m = (jq_Method) callSite.getMethod();
356                 Map map = CodeCache.getBCMap(m);
357                 //CodeCache.invalidateBCMap(m);
358                 Quad q = ((ProgramLocation.QuadProgramLocation) callSite).getQuad();
359                 if (q == null) {
360                     Assert.UNREACHABLE("Error: cannot find call site "+callSite);
361                 }
362                 Integer i = (Integer) map.get(q);
363                 if (i == null) {
364 //                    Assert.UNREACHABLE("Error: no mapping for quad "+q);
365                     return new ProgramLocation.FakeProgramLocation(m, "Fake location " + callSite.toString());
366                 }
367                 int bcIndex = i.intValue();
368                 callSite = new ProgramLocation.BCProgramLocation(m, bcIndex);
369             }
370         }
371         return callSite;        
372     }    
373 }