1
2
3
4 package joeq.Compiler.Quad;
5
6 import java.util.AbstractSet;
7 import java.util.Collection;
8 import java.util.Collections;
9 import java.util.Comparator;
10 import java.util.HashMap;
11 import java.util.HashSet;
12 import java.util.Iterator;
13 import java.util.LinkedHashSet;
14 import java.util.LinkedList;
15 import java.util.Map;
16 import java.util.Set;
17 import java.util.TreeSet;
18 import joeq.Class.jq_Method;
19 import joeq.Compiler.Analysis.IPA.ProgramLocation;
20 import joeq.Compiler.Quad.Operator.Invoke;
21 import jwutil.collections.GenericInvertibleMultiMap;
22 import jwutil.collections.HashWorklist;
23 import jwutil.collections.InvertibleMultiMap;
24 import jwutil.collections.MultiMap;
25 import jwutil.collections.UnmodifiableIterator;
26 import jwutil.collections.UnmodifiableMultiMap;
27 import jwutil.graphs.Graph;
28 import jwutil.graphs.Navigator;
29 import jwutil.strings.Strings;
30 import jwutil.util.Assert;
31
32 /***
33 * Abstract representation of a call graph.
34 *
35 * @author John Whaley <jwhaley@alum.mit.edu>
36 * @version $Id: CallGraph.java 2238 2005-03-21 05:01:17Z joewhaley $
37 */
38 public abstract class CallGraph extends UnmodifiableMultiMap implements Graph {
39
40 /***
41 * Sets up the root methods to be the given set. Later call graph queries
42 * use the value that you pass in here. Implementing this method is
43 * optional -- it is only necessary if you use methods that require a root
44 * set, like getReachableMethods().
45 *
46 * @param roots collection of root methods
47 */
48 public abstract void setRoots(Collection
49
50 /*** Returns the collection of root methods for this call graph. */
51 public abstract Collection
52
53 /***
54 * Returns the collection of all methods in the call graph.
55 * The default implementation recalculates the reachable
56 * methods based on the root set.
57 *
58 * @return Collection of all call sites in the call graph
59 */
60 public Collection
61 return calculateReachableMethods(getRoots());
62 }
63
64 /***
65 * Returns the collection of all call sites in the call graph.
66 * The default implementation just iterates through all of the methods
67 * to build up the collection.
68 *
69 * @return Collection of all call sites in the call graph
70 */
71 public Collection
72 LinkedList list = new LinkedList();
73 for (Iterator i = getAllMethods().iterator(); i.hasNext(); ) {
74 jq_Method m = (jq_Method) i.next();
75 if (m == null) continue;
76 list.addAll(getCallSites(m));
77 }
78 return list;
79 }
80
81 /***
82 * Returns the possible target methods of the given call site under the given context.
83 * The interpretation of the context object is specific to the type of call graph.
84 *
85 * @param context
86 * @param callSite
87 * @return Collection of jq_Methods that are the possible targets
88 */
89 public abstract Collection
90
91 /***
92 * Returns the possible target methods of the given call site.
93 *
94 * @param callSite
95 * @return Collection of jq_Methods that are the possible targets
96 */
97 public Collection
98 return getTargetMethods(null, callSite);
99 }
100
101 /***
102 * Returns the number of possible target methods of the given call site under
103 * the given context. The interpretation of the context object is specific to
104 * the type of call graph.
105 *
106 * @param context
107 * @param callSite
108 * @return number of possible targets
109 */
110 public int numberOfTargetMethods(Object context, ProgramLocation callSite) {
111 return getTargetMethods(context, callSite).size();
112 }
113
114 /***
115 * Returns the number of possible target methods of the given call site.
116 *
117 * @param callSite
118 * @return number of possible targets
119 */
120 public int numberOfTargetMethods(ProgramLocation callSite) {
121 return numberOfTargetMethods(null, callSite);
122 }
123
124 /***
125 * Returns the target method of the given call site under the given context, assuming
126 * that it is a single target.
127 * The interpretation of the context object is specific to the type of call graph.
128 *
129 * @param context
130 * @param callSite
131 * @return target method
132 */
133 public jq_Method getTargetMethod(Object context, ProgramLocation callSite) {
134 Collection c = getTargetMethods(context, callSite);
135 Assert._assert(c.size() == 1);
136 return (jq_Method) c.iterator().next();
137 }
138
139 /***
140 * Returns the set of call sites in the given method.
141 *
142 * @param caller
143 * @return set of call sites
144 */
145 public Collection
146 return getCallSites0(caller);
147 }
148 public static Collection
149 caller.getDeclaringClass().load();
150 if (caller.getBytecode() == null) return Collections.EMPTY_SET;
151 ControlFlowGraph cfg = CodeCache.getCode(caller);
152 return getCallSites0(cfg);
153 }
154
155 /***
156 * Returns the set of call sites in the given CFG.
157 *
158 * @param cfg
159 * @return set of call sites
160 */
161 public Collection
162 return getCallSites0(cfg);
163 }
164 public static Collection
165 LinkedList result = new LinkedList();
166 for (QuadIterator i = new QuadIterator(cfg); i.hasNext(); ) {
167 Quad q = i.nextQuad();
168 if (q.getOperator() instanceof Invoke)
169 result.add(new ProgramLocation.QuadProgramLocation(cfg.getMethod(), q));
170 }
171 return result;
172 }
173 public static Collection
174 int total = 0;
175 for (QuadIterator i = new QuadIterator(cfg); i.hasNext(); ) {
176 Quad q = i.nextQuad();
177 if (q.getOperator() instanceof Invoke)
178 ++total;
179 }
180 final int size = total;
181 final QuadIterator i = new QuadIterator(cfg);
182 return new AbstractSet() {
183 public int size() { return size; }
184 public Iterator iterator() {
185 return new UnmodifiableIterator() {
186 Quad _next;
187 { advance(); }
188 private void advance() {
189 while (i.hasNext()) {
190 Quad q = i.nextQuad();
191 if (q.getOperator() instanceof Invoke) {
192 _next = q;
193 return;
194 }
195 }
196 _next = null;
197 }
198 public boolean hasNext() { return _next != null; }
199 public Object next() {
200 Quad n = _next;
201 if (n == null)
202 throw new java.util.NoSuchElementException();
203 advance();
204 return n;
205 }
206 };
207 }
208 };
209 }
210
211 /***
212 * Returns the set of methods that are called by the given method.
213 *
214 * @param caller
215 * @return set of callee methods
216 */
217 public Collection getCallees(jq_Method caller) {
218 caller.getDeclaringClass().load();
219 if (caller.getBytecode() == null) return Collections.EMPTY_SET;
220 ControlFlowGraph cfg = CodeCache.getCode(caller);
221 return getCallees(cfg);
222 }
223
224 /***
225 * Returns the set of methods that are called by the given CFG.
226 *
227 * @param cfg
228 * @return set of callee methods
229 */
230 public Collection getCallees(ControlFlowGraph cfg) {
231 LinkedHashSet result = new LinkedHashSet();
232 for (QuadIterator i = new QuadIterator(cfg); i.hasNext(); ) {
233 Quad q = i.nextQuad();
234 if (q.getOperator() instanceof Invoke) {
235 ProgramLocation p = new ProgramLocation.QuadProgramLocation(cfg.getMethod(), q);
236 result.addAll(getTargetMethods(p));
237 }
238 }
239 return result;
240 }
241
242 /***
243 * Returns the set of call sites that can call the given method.
244 *
245 * @param callee
246 * @return set of callers
247 */
248 public Collection
249 LinkedList result = new LinkedList();
250 for (Iterator i = getAllCallSites().iterator(); i.hasNext(); ) {
251 ProgramLocation p = (ProgramLocation) i.next();
252 if (getTargetMethods(p).contains(callee))
253 result.add(p);
254 }
255 return result;
256 }
257
258 /***
259 * Returns the set of methods that can call the given method.
260 *
261 * @param callee
262 * @return set of caller methods
263 */
264 public Collection
265 LinkedList result = new LinkedList();
266 for (Iterator i = getAllCallSites().iterator(); i.hasNext(); ) {
267 ProgramLocation p = (ProgramLocation) i.next();
268 if (getTargetMethods(p).contains(callee))
269 result.add(p.getMethod());
270 }
271 return result;
272 }
273
274 /***
275 * Returns the set of methods that are reachable from the given method root set.
276 *
277 * @param roots
278 * @return set of reachable methods
279 */
280 public Set
281 HashWorklist worklist = new HashWorklist(true);
282 worklist.addAll(roots);
283 while (!worklist.isEmpty()) {
284 jq_Method m = (jq_Method) worklist.pull();
285 Collection c = getCallees(m);
286 worklist.addAll(c);
287 }
288 return worklist.getVisitedSet();
289 }
290
291 /***
292 * Returns a string representation of this call graph.
293 */
294 public String toString() {
295 TreeSet ts = new TreeSet(
296 new Comparator() {
297 public int compare(Object o1, Object o2) {
298 ProgramLocation cs1 = (ProgramLocation) o1;
299 Collection s1 = getTargetMethods(cs1);
300 ProgramLocation cs2 = (ProgramLocation) o2;
301 Collection s2 = getTargetMethods(cs2);
302 int s1s = s1.size(); int s2s = s2.size();
303 if (s1s < s2s) return 1;
304 else if (s1s > s2s) return -1;
305 else return cs1.toString().compareTo(cs2.toString());
306 }
307 });
308 ts.addAll(getAllCallSites());
309 StringBuffer sb = new StringBuffer();
310 for (Iterator i=ts.iterator(); i.hasNext(); ) {
311 ProgramLocation cs = (ProgramLocation) i.next();
312 Collection s = (Collection) getTargetMethods(cs);
313 sb.append(cs.toString());
314 sb.append(": {");
315 int x = s.size();
316 sb.append(x);
317 sb.append("} ");
318 sb.append(s.toString());
319 sb.append(Strings.lineSep);
320 }
321 return sb.toString();
322 }
323
324 /*** Calculate a multimap between methods and their callers. */
325 public Map calculateCallerRelation() {
326 Collection roots = getRoots();
327 Map backEdges = new HashMap();
328 LinkedList worklist = new LinkedList();
329 for (Iterator i=roots.iterator(); i.hasNext(); ) {
330 jq_Method m = (jq_Method) i.next();
331 if (m == null) continue;
332 backEdges.put(m, new HashSet());
333 worklist.add(m);
334 }
335 while (!worklist.isEmpty()) {
336 jq_Method caller = (jq_Method) worklist.removeFirst();
337 Collection callsites = this.getCallSites(caller);
338 for (Iterator i=callsites.iterator(); i.hasNext(); ) {
339 ProgramLocation cs = (ProgramLocation) i.next();
340 Collection callees = this.getTargetMethods(cs);
341 for (Iterator j=callees.iterator(); j.hasNext(); ) {
342 jq_Method callee = (jq_Method) i.next();
343 if (callee == null) continue;
344 Set s = (Set) backEdges.get(callee);
345 if (s == null) {
346 backEdges.put(callee, s = new HashSet());
347 worklist.add(callee);
348 }
349 s.add(cs);
350 }
351 }
352 }
353 return backEdges;
354 }
355
356 /***
357 * Returns the call graph edge relation in the form of an invertible multi-map.
358 * The edge relation contains both the relations between methods and their call
359 * sites and between call sites and their target methods.
360 *
361 * @return set of caller methods
362 */
363 public InvertibleMultiMap calculateEdgeRelation() {
364 InvertibleMultiMap edges = new GenericInvertibleMultiMap();
365 for (Iterator i = this.getAllMethods().iterator(); i.hasNext(); ) {
366 jq_Method caller = (jq_Method) i.next();
367 if (caller == null) continue;
368 Collection callsites = edges.getValues(caller);
369 Collection callsites2 = this.getCallSites(caller);
370 callsites.addAll(callsites2);
371 for (Iterator j = callsites2.iterator(); j.hasNext(); ) {
372 ProgramLocation cs = (ProgramLocation) j.next();
373 Collection callees = edges.getValues(cs);
374 Collection callees2 = this.getTargetMethods(cs);
375 callees.addAll(callees2);
376 }
377 }
378 return edges;
379 }
380
381 public Collection[] findDepths() {
382 Collection roots = getRoots();
383 HashSet visited = new HashSet();
384 LinkedList result = new LinkedList();
385 LinkedList previous = new LinkedList();
386 visited.addAll(roots);
387 previous.addAll(roots);
388 while (!previous.isEmpty()) {
389 result.add(previous);
390 LinkedList current = new LinkedList();
391 for (Iterator i=previous.iterator(); i.hasNext(); ) {
392 jq_Method caller = (jq_Method) i.next();
393 if (caller == null) continue;
394 for (Iterator j=getCallSites(caller).iterator(); j.hasNext(); ) {
395 ProgramLocation cs = (ProgramLocation) j.next();
396 for (Iterator k=getTargetMethods(cs).iterator(); k.hasNext(); ) {
397 jq_Method callee = (jq_Method) k.next();
398 if (visited.contains(callee)) {
399
400 continue;
401 }
402 visited.add(callee);
403 current.add(callee);
404 }
405 }
406 }
407 previous = current;
408 }
409
410 return (Collection[]) result.toArray(new Collection[result.size()]);
411 }
412
413 public Navigator getNavigator() {
414 return getMethodNavigator();
415 }
416
417 public Navigator getMethodNavigator() {
418 return new CallGraphMethodNavigator();
419 }
420
421 public Navigator getCallSiteNavigator() {
422 return new CallGraphCSNavigator();
423 }
424
425 public MultiMap getCallSiteMap() {
426 Set methods = (Set) getAllMethods();
427 CallSiteMap csm = new CallSiteMap(methods);
428 return csm;
429 }
430
431
432
433
434
435
436
437
438
439 public MultiMap getCallGraphMap() {
440 Set methods = (Set) getAllMethods();
441 CallSiteMap csm = new CallSiteMap(methods);
442 CallTargetMap ctm = new CallTargetMap((Set)csm.values());
443 return new CallGraphMap(csm, ctm);
444 }
445
446 public static class CallSiteMap extends UnmodifiableMultiMap {
447
448 public static final CallSiteMap INSTANCE = new CallSiteMap();
449
450 private final Set methods;
451
452 public CallSiteMap(Set methods) {
453 Assert._assert(methods != null);
454 this.methods = methods;
455 }
456 private CallSiteMap() {
457 this.methods = null;
458 }
459
460
461
462
463 public Set entrySet() {
464 if (methods == null)
465 throw new UnsupportedOperationException();
466 return entrySetHelper(methods);
467 }
468
469
470
471
472 public Collection getValues(Object key) {
473 jq_Method m = (jq_Method) key;
474 return getCallSites0(m);
475 }
476
477
478
479
480 public boolean contains(Object a, Object b) {
481 ProgramLocation cs = (ProgramLocation) b;
482 if (methods != null && !methods.contains(a)) return false;
483 return cs.getMethod() == a;
484 }
485 }
486
487 public class CallTargetMap extends UnmodifiableMultiMap {
488
489 private final Set callSites;
490
491 public CallTargetMap(Set callSites) {
492 this.callSites = callSites;
493 }
494 public CallTargetMap() {
495 this.callSites = null;
496 }
497
498
499
500
501 public Set entrySet() {
502 if (callSites == null)
503 throw new UnsupportedOperationException();
504 return entrySetHelper(callSites);
505 }
506
507
508
509
510 public Collection getValues(Object key) {
511 ProgramLocation cs = (ProgramLocation) key;
512 return getTargetMethods(cs);
513 }
514
515
516
517
518 public boolean contains(Object a, Object b) {
519 return getValues(a).contains(b);
520 }
521 }
522
523 public static class CallGraphMap extends UnmodifiableMultiMap {
524
525 private final MultiMap methodToCallSite;
526 private final MultiMap callSiteToTarget;
527
528 public CallGraphMap(MultiMap methodToCallSite, MultiMap callSiteToTarget) {
529 this.methodToCallSite = methodToCallSite;
530 this.callSiteToTarget = callSiteToTarget;
531 }
532
533
534
535
536 public Set entrySet() {
537 return entrySetHelper(methodToCallSite.keySet());
538 }
539
540
541
542
543 public Collection getValues(Object key) {
544 Collection c1 = methodToCallSite.getValues(key);
545 Iterator i = c1.iterator();
546 if (!i.hasNext()) return c1;
547 Object o = i.next();
548 if (!i.hasNext()) return callSiteToTarget.getValues(o);
549 Collection result = new LinkedHashSet();
550 for (;;) {
551 result.addAll(callSiteToTarget.getValues(o));
552 if (!i.hasNext()) break;
553 o = i.next();
554 }
555 return result;
556 }
557
558
559
560
561 public boolean contains(Object a, Object b) {
562 return getValues(a).contains(b);
563 }
564
565 }
566
567 public class CallGraphMethodNavigator implements Navigator {
568
569 /***
570 * @see jwutil.graphs.Navigator#next(java.lang.Object)
571 */
572 public Collection next(Object node) {
573 jq_Method caller = (jq_Method) node;
574 Collection s = getCallees(caller);
575 return s;
576 }
577
578 /***
579 * @see jwutil.graphs.Navigator#prev(java.lang.Object)
580 */
581 public Collection prev(Object node) {
582 jq_Method callee = (jq_Method) node;
583 Collection s = getCallerMethods(callee);
584 return s;
585 }
586
587 }
588
589 public class CallGraphCSNavigator implements Navigator {
590
591 /***
592 * @see jwutil.graphs.Navigator#next(java.lang.Object)
593 */
594 public Collection next(Object node) {
595 if (node instanceof jq_Method)
596 return getCallSites((jq_Method) node);
597 else
598 return getTargetMethods((ProgramLocation) node);
599 }
600
601 /***
602 * @see jwutil.graphs.Navigator#prev(java.lang.Object)
603 */
604 public Collection prev(Object node) {
605 if (node instanceof jq_Method)
606 return getCallers((jq_Method) node);
607 else
608 return Collections.singleton(((ProgramLocation) node).getMethod());
609 }
610
611 }
612
613
614
615
616 public Set entrySet() {
617 return entrySetHelper((Set) getAllCallSites());
618 }
619
620
621
622
623 public boolean contains(Object a, Object b) {
624 ProgramLocation p = (ProgramLocation) a;
625 return getTargetMethods(p).contains(b);
626 }
627
628
629
630
631 public Collection getValues(Object key) {
632 ProgramLocation p = (ProgramLocation) key;
633 return getTargetMethods(p);
634 }
635
636 public static CallGraph makeCallGraph(Collection rootMethods, Map callsToTargets) {
637
638 final Collection roots = rootMethods;
639 final Map callSiteToTargets = callsToTargets;
640
641 return new CallGraph() {
642
643 /***
644 * @see joeq.Compiler.Quad.CallGraph#getTargetMethods(java.lang.Object, joeq.Compiler.Analysis.IPA.ProgramLocation)
645 */
646 public Collection getTargetMethods(Object context, ProgramLocation callSite) {
647 jq_Method method = (jq_Method) callSite.getTargetMethod();
648 if (callSite.isSingleTarget()) {
649 return Collections.singleton(method);
650 }
651 Collection targets = (Collection) callSiteToTargets.get(callSite);
652 if (targets != null) {
653 return targets;
654 } else {
655 return Collections.EMPTY_SET;
656 }
657 }
658
659
660
661
662 public void setRoots(Collection newRoots) {
663 Assert._assert(roots.equals(newRoots));
664 }
665
666
667
668
669 public Collection getRoots() {
670 return roots;
671 }
672
673
674
675
676 public Collection getAllCallSites() {
677 return callSiteToTargets.keySet();
678 }
679
680
681
682
683 public Collection getAllMethods() {
684 LinkedHashSet s = new LinkedHashSet();
685 s.addAll(roots);
686 for (Iterator i = callSiteToTargets.values().iterator(); i.hasNext(); ) {
687 Collection c = (Collection) i.next();
688 s.addAll(c);
689 }
690 return s;
691 }
692
693 };
694 }
695
696 }