View Javadoc

1   // CHACallGraph.java, created Mon Mar  3 18:01:33 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.Arrays;
7   import java.util.Collection;
8   import java.util.Collections;
9   import java.util.Iterator;
10  import java.util.LinkedHashSet;
11  import java.util.LinkedList;
12  import java.util.Set;
13  import joeq.Class.PrimordialClassLoader;
14  import joeq.Class.jq_Class;
15  import joeq.Class.jq_Method;
16  import joeq.Class.jq_Type;
17  import joeq.Compiler.Analysis.IPA.ProgramLocation;
18  import jwutil.collections.SizedArrayList;
19  
20  /***
21   * A simple call graph implementation based on class-hierarchy analysis with
22   * optional rapid type analysis.
23   * 
24   * @author John Whaley <jwhaley@alum.mit.edu>
25   * @version $Id: CHACallGraph.java 2264 2005-05-19 00:18:05Z joewhaley $
26   */
27  public class CHACallGraph extends CallGraph {
28  
29      public static final CHACallGraph INSTANCE = new CHACallGraph();
30  
31      protected final Set classes;
32  
33      /***
34       * Construct a call graph assuming only the given types are
35       * used by the program, i.e. rapid type analysis.
36       * 
37       * @param classes set of types from which to build the call graph
38       */
39      public CHACallGraph(Set/*jq_Type*/ classes) { this.classes = classes; }
40      protected CHACallGraph() { this.classes = null; }
41  
42      /***
43       * @see joeq.Compiler.Quad.CallGraph#getTargetMethods(java.lang.Object, joeq.Compiler.Analysis.IPA.ProgramLocation)
44       */
45      public Collection getTargetMethods(Object context, ProgramLocation callSite) {
46          callSite.resolveTargetMethod();
47          jq_Method method = (jq_Method) callSite.getTargetMethod();
48          if (callSite.isSingleTarget())
49              return Collections.singleton(method);
50          
51          Collection result;
52          if (callSite.isInterfaceCall()) {
53              result = new LinkedHashSet();
54              Collection s = classes;
55              if (s == null) {
56                  s = new SizedArrayList(PrimordialClassLoader.loader.getAllTypes(),
57                      PrimordialClassLoader.loader.getNumTypes());
58              }
59              for (Iterator i = s.iterator(); i.hasNext(); ) {
60                  jq_Type t = (jq_Type) i.next();
61                  if (t instanceof jq_Class) {
62                      jq_Class c = (jq_Class) t;
63                      try {
64                          c.prepare();
65                          if (c.implementsInterface(method.getDeclaringClass())) {
66                              jq_Method m2 = c.getVirtualMethod(method.getNameAndDesc());
67                              if (m2 != null && !m2.isAbstract()) result.add(m2);
68                          }
69                      } catch (NoClassDefFoundError x) {
70                          // Class could not be found!  Skipping.
71                      }
72                  }
73              }
74          } else {
75              result = new LinkedList();
76              LinkedList worklist = new LinkedList();
77              worklist.add(method.getDeclaringClass());
78              while (!worklist.isEmpty()) {
79                  jq_Class c = (jq_Class) worklist.removeFirst();
80                  try {
81                      c.load();
82                      jq_Method m2 = (jq_Method) c.getDeclaredMember(method.getNameAndDesc());
83                      if (m2 != null) {
84                          if (!m2.isAbstract()) {
85                              result.add(m2);
86                          }
87                          if (m2.isFinal() || m2.isPrivate()) {
88                              continue;
89                          }
90                      }
91                      for (Iterator i=Arrays.asList(c.getSubClasses()).iterator(); i.hasNext(); ) {
92                          jq_Class c2 = (jq_Class) i.next();
93                          if (classes == null || classes.contains(c2)) worklist.add(c2);
94                      }
95                  } catch (NoClassDefFoundError x) {
96                      // Class could not be found!  Skipping.
97                  }
98              }
99          }
100         return result;
101     }
102 
103     /* (non-Javadoc)
104      * @see joeq.Compiler.Quad.CallGraph#getRoots()
105      */
106     public Collection getRoots() {
107         throw new UnsupportedOperationException();
108     }
109 
110     /* (non-Javadoc)
111      * @see joeq.Compiler.Quad.CallGraph#setRoots(java.util.Collection)
112      */
113     public void setRoots(Collection roots) {
114         throw new UnsupportedOperationException();
115     }
116 
117 }