1
2
3
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
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
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
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
136 protected Set
137 protected MultiMap
138 protected InvertibleMultiMap
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
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
252
253
254 public void setRoots(Collection roots) {
255
256 Assert._assert(this.roots.equals(roots));
257 }
258
259
260
261
262 public Collection getRoots() {
263 return roots;
264 }
265
266
267
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
277
278
279 public Set entrySet() {
280 return edges.entrySet();
281 }
282
283
284
285
286 public Collection getAllCallSites() {
287 return edges.keySet();
288 }
289
290
291
292
293 public Collection getAllMethods() {
294 return methods;
295 }
296
297
298
299
300 public Collection getCallees(jq_Method caller) {
301 Collection c = CachedCallGraph.getFromMultiMap(callSites, edges, caller);
302 return c;
303 }
304
305
306
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
315
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
338
339
340 public Collection getCallSites(jq_Method caller) {
341 Collection c = callSites.getValues(caller);
342 return c;
343 }
344
345
346
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
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
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 }