View Javadoc

1   // CallGraph.java, created Mon Mar  3 18:01:32 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.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/*<jq_Method>*/ roots);
49      
50      /*** Returns the collection of root methods for this call graph. */
51      public abstract Collection/*<jq_Method>*/ getRoots();
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/*<jq_Method>*/ getAllMethods() {
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/*<ProgramLocation>*/ getAllCallSites() {
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/*<jq_Method>*/ getTargetMethods(Object context, ProgramLocation callSite);
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/*<jq_Method>*/ getTargetMethods(ProgramLocation callSite) {
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/*<ProgramLocation>*/ getCallSites(jq_Method caller) {
146         return getCallSites0(caller);
147     }
148     public static Collection/*<ProgramLocation>*/ getCallSites0(jq_Method caller) {
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/*<ProgramLocation>*/ getCallSites(ControlFlowGraph cfg) {
162         return getCallSites0(cfg);
163     }
164     public static Collection/*<ProgramLocation>*/ getCallSites0(ControlFlowGraph cfg) {
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/*<ProgramLocation>*/ getCallSites1(ControlFlowGraph cfg) {
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/*ProgramLocation*/ getCallers(jq_Method callee) {
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/*jq_Method*/ getCallerMethods(jq_Method callee) {
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/*jq_Method*/ calculateReachableMethods(Collection roots) {
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                             // back or cross edge in call graph.
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     public MultiMap getCallTargetMap() {
433         Set callSites = (Set) getAllCallSites();
434         CallTargetMap ctm = new CallTargetMap(callSites);
435         return ctm;
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         /* (non-Javadoc)
461          * @see java.util.Map#entrySet()
462          */
463         public Set entrySet() {
464             if (methods == null)
465                 throw new UnsupportedOperationException();
466             return entrySetHelper(methods);
467         }
468 
469         /* (non-Javadoc)
470          * @see jwutil.collections.MultiMap#getValues(java.lang.Object)
471          */
472         public Collection getValues(Object key) {
473             jq_Method m = (jq_Method) key;
474             return getCallSites0(m);
475         }
476 
477         /* (non-Javadoc)
478          * @see jwutil.collections.BinaryRelation#contains(java.lang.Object, java.lang.Object)
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         /* (non-Javadoc)
499          * @see java.util.Map#entrySet()
500          */
501         public Set entrySet() {
502             if (callSites == null)
503                 throw new UnsupportedOperationException();
504             return entrySetHelper(callSites);
505         }
506 
507         /* (non-Javadoc)
508          * @see jwutil.collections.MultiMap#getValues(java.lang.Object)
509          */
510         public Collection getValues(Object key) {
511             ProgramLocation cs = (ProgramLocation) key;
512             return getTargetMethods(cs);
513         }
514 
515         /* (non-Javadoc)
516          * @see jwutil.collections.BinaryRelation#contains(java.lang.Object, java.lang.Object)
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         /* (non-Javadoc)
534          * @see java.util.Map#entrySet()
535          */
536         public Set entrySet() {
537             return entrySetHelper(methodToCallSite.keySet());
538         }
539         
540         /* (non-Javadoc)
541          * @see jwutil.collections.MultiMap#getValues(java.lang.Object)
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         /* (non-Javadoc)
559          * @see jwutil.collections.BinaryRelation#contains(java.lang.Object, java.lang.Object)
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     /* (non-Javadoc)
614      * @see java.util.Map#entrySet()
615      */
616     public Set entrySet() {
617         return entrySetHelper((Set) getAllCallSites());
618     }
619 
620     /* (non-Javadoc)
621      * @see jwutil.collections.BinaryRelation#contains(java.lang.Object, java.lang.Object)
622      */
623     public boolean contains(Object a, Object b) {
624         ProgramLocation p = (ProgramLocation) a;
625         return getTargetMethods(p).contains(b);
626     }
627 
628     /* (non-Javadoc)
629      * @see jwutil.collections.MultiMap#getValues(java.lang.Object)
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             /* (non-Javadoc)
660              * @see joeq.Compiler.Quad.CallGraph#setRoots(java.util.Collection)
661              */
662             public void setRoots(Collection newRoots) {
663                 Assert._assert(roots.equals(newRoots));
664             }
665 
666             /* (non-Javadoc)
667              * @see joeq.Compiler.Quad.CallGraph#getRoots()
668              */
669             public Collection getRoots() {
670                 return roots;
671             }
672         
673             /* (non-Javadoc)
674              * @see joeq.Compiler.Quad.CallGraph#getAllCallSites()
675              */
676             public Collection getAllCallSites() {
677                 return callSiteToTargets.keySet();
678             }
679 
680             /* (non-Javadoc)
681              * @see joeq.Compiler.Quad.CallGraph#getAllMethods()
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 }