1 cananian 1.1.2.1 // QuadClassHierarchy.java, created Sun Oct 11 13:08:31 1998 by cananian
2 cananian 1.1.2.1 // Copyright (C) 1998 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1.2.1 package harpoon.Analysis.Quads;
5 cananian 1.1.2.1
6 cananian 1.1.2.16 import harpoon.ClassFile.HClass;
7 cananian 1.1.2.16 import harpoon.ClassFile.HCodeFactory;
8 cananian 1.1.2.16 import harpoon.ClassFile.HConstructor;
9 cananian 1.1.2.16 import harpoon.ClassFile.HField;
10 cananian 1.1.2.16 import harpoon.ClassFile.HMethod;
11 cananian 1.1.2.16 import harpoon.ClassFile.Linker;
12 cananian 1.1.2.16 import harpoon.IR.Quads.ANEW;
13 cananian 1.1.2.16 import harpoon.IR.Quads.CALL;
14 cananian 1.1.2.16 import harpoon.IR.Quads.CONST;
15 cananian 1.1.2.16 import harpoon.IR.Quads.Code;
16 cananian 1.1.2.16 import harpoon.IR.Quads.GET;
17 cananian 1.1.2.23 import harpoon.IR.Quads.HANDLER;
18 cananian 1.1.2.16 import harpoon.IR.Quads.INSTANCEOF;
19 cananian 1.1.2.16 import harpoon.IR.Quads.NEW;
20 cananian 1.1.2.16 import harpoon.IR.Quads.Quad;
21 cananian 1.1.2.28 import harpoon.IR.Quads.QuadVisitor;
22 cananian 1.1.2.16 import harpoon.IR.Quads.SET;
23 cananian 1.1.2.33 import harpoon.IR.Quads.TYPECAST;
24 cananian 1.1.2.20 import harpoon.IR.Quads.TYPESWITCH;
25 cananian 1.1.2.1 import harpoon.Util.ArraySet;
26 cananian 1.6 import net.cscott.jutil.Default;
27 cananian 1.1.2.3 import harpoon.Util.HClassUtil;
28 cananian 1.1.2.1 import harpoon.Util.Util;
29 cananian 1.1.2.34 import harpoon.Util.Collections.WorkSet;
30 cananian 1.1.2.1
31 cananian 1.1.2.12 import java.lang.reflect.Modifier;
32 cananian 1.1.2.12
33 cananian 1.1.2.8 import java.util.ArrayList;
34 cananian 1.1.2.4 import java.util.Arrays;
35 cananian 1.1.2.2 import java.util.Collection;
36 cananian 1.1.2.1 import java.util.Collections;
37 cananian 1.1.2.1 import java.util.HashSet;
38 cananian 1.1.2.1 import java.util.HashMap;
39 cananian 1.1.2.1 import java.util.Iterator;
40 cananian 1.1.2.8 import java.util.List;
41 cananian 1.1.2.1 import java.util.Map;
42 cananian 1.1.2.1 import java.util.Set;
43 cananian 1.1.2.1 /**
44 cananian 1.1.2.1 * <code>QuadClassHierarchy</code> computes a <code>ClassHierarchy</code>
45 cananian 1.1.2.1 * of classes possibly usable starting from some root method using
46 cananian 1.1.2.1 * quad form.
47 cananian 1.1.2.1 * Native methods are not analyzed.
48 cananian 1.1.2.1 *
49 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
50 cananian 1.7 * @version $Id: QuadClassHierarchy.java,v 1.7 2004/02/08 05:09:40 cananian Exp $
51 cananian 1.1.2.1 */
52 cananian 1.1.2.1
53 cananian 1.1.2.1 public class QuadClassHierarchy extends harpoon.Analysis.ClassHierarchy
54 cananian 1.1.2.1 implements java.io.Serializable {
55 cananian 1.3.2.2 private final Map<HClass,HClass[]> children =
56 cananian 1.3.2.2 new HashMap<HClass,HClass[]>();
57 cananian 1.3.2.2 private final Set<HMethod> methods = new HashSet<HMethod>();
58 cananian 1.1.2.1
59 cananian 1.1.2.1 /** Returns set of all callable methods.
60 cananian 1.1.2.1 @return <code>Set</code> of <code>HMethod</code>s.
61 cananian 1.1.2.1 */
62 cananian 1.3.2.2 public Set<HMethod> callableMethods() {
63 cananian 1.1.2.1 return _unmod_methods;
64 cananian 1.1.2.1 }
65 cananian 1.3.2.2 private final Set<HMethod> _unmod_methods =
66 cananian 1.3.2.2 Collections.unmodifiableSet(methods);
67 cananian 1.1.2.1
68 cananian 1.1.2.22 // inherit description from parent class.
69 cananian 1.3.2.2 public Set<HClass> children(HClass c) {
70 cananian 1.1.2.1 if (children.containsKey(c))
71 cananian 1.3.2.2 return new ArraySet<HClass>(children.get(c));
72 cananian 1.3.2.2 return Default.EMPTY_SET();
73 cananian 1.1.2.1 }
74 cananian 1.1.2.22 // inherit description from parent class.
75 cananian 1.3.2.2 public Set<HClass> classes() {
76 cananian 1.1.2.1 if (_classes == null) {
77 cananian 1.3.2.2 _classes = new HashSet<HClass>();
78 cananian 1.3.2.2 for(Iterator<HClass> it = children.keySet().iterator();
79 cananian 1.3.2.2 it.hasNext(); )
80 cananian 1.1.2.1 _classes.add(it.next());
81 cananian 1.7 for(HClass[] ch : children.values()) {
82 cananian 1.1.2.1 for (int i=0; i<ch.length; i++)
83 cananian 1.1.2.1 _classes.add(ch[i]);
84 cananian 1.1.2.1 }
85 cananian 1.1.2.1 _classes = Collections.unmodifiableSet(_classes);
86 cananian 1.1.2.1 }
87 cananian 1.1.2.1 return _classes;
88 cananian 1.1.2.1 }
89 cananian 1.3.2.2 private transient Set<HClass> _classes = null;
90 cananian 1.1.2.1 /** Returns the set of all classes instantiated.
91 cananian 1.1.2.1 (Actually only the list of classes for which an explicit NEW is found;
92 cananian 1.1.2.1 should include list of classes that are automatically created by JVM!) */
93 cananian 1.3.2.2 public Set<HClass> instantiatedClasses() {
94 cananian 1.1.2.1 return _unmod_insted;
95 cananian 1.1.2.1 }
96 cananian 1.3.2.2 private final Set<HClass> instedClasses = new HashSet<HClass>();
97 cananian 1.3.2.2 private final Set<HClass> _unmod_insted =
98 cananian 1.3.2.2 Collections.unmodifiableSet(instedClasses);
99 cananian 1.1.2.1
100 cananian 1.1.2.1 /** Returns a human-readable representation of the hierarchy. */
101 cananian 1.1.2.1 public String toString() {
102 cananian 1.1.2.1 // not the most intuitive representation...
103 cananian 1.1.2.1 StringBuffer sb = new StringBuffer("{");
104 cananian 1.3.2.2 for (Iterator<HClass> it=children.keySet().iterator(); it.hasNext(); ){
105 cananian 1.3.2.2 HClass c = it.next();
106 cananian 1.1.2.1 sb.append(c.toString());
107 cananian 1.1.2.1 sb.append("={");
108 cananian 1.3.2.2 for (Iterator<HClass> it2=children(c).iterator(); it2.hasNext(); ){
109 cananian 1.1.2.1 sb.append(it2.next().toString());
110 cananian 1.1.2.1 if (it2.hasNext())
111 cananian 1.1.2.1 sb.append(',');
112 cananian 1.1.2.1 }
113 cananian 1.1.2.1 sb.append('}');
114 cananian 1.1.2.1 if (it.hasNext())
115 cananian 1.1.2.1 sb.append(", ");
116 cananian 1.1.2.1 }
117 cananian 1.1.2.1 sb.append('}');
118 cananian 1.1.2.1 return sb.toString();
119 cananian 1.1.2.1 }
120 cananian 1.1.2.1
121 cananian 1.1.2.15 ////// hclass objects
122 cananian 1.1.2.15 private final HMethod HMstrIntern;
123 cananian 1.1.2.15 private final HMethod HMthrStart;
124 cananian 1.1.2.15 private final HMethod HMthrRun;
125 cananian 1.1.2.15 private QuadClassHierarchy(Linker linker) {
126 cananian 1.1.2.15 HMstrIntern = linker.forName("java.lang.String")
127 cananian 1.1.2.15 .getMethod("intern",new HClass[0]);
128 cananian 1.1.2.15 HMthrStart = linker.forName("java.lang.Thread")
129 cananian 1.1.2.15 .getMethod("start", new HClass[0]);
130 cananian 1.1.2.15 HMthrRun = linker.forName("java.lang.Thread")
131 cananian 1.1.2.15 .getMethod("run", new HClass[0]);
132 cananian 1.1.2.2 }
133 cananian 1.1.2.15
134 cananian 1.1.2.1 /** Creates a <code>ClassHierarchy</code> of all classes
135 cananian 1.1.2.13 * reachable/usable from <code>HMethod</code>s in the <code>roots</code>
136 cananian 1.1.2.13 * <code>Collection</code>. <code>HClass</code>es included in
137 cananian 1.1.2.13 * <code>roots</code> are guaranteed to be included in the
138 cananian 1.1.2.13 * <code>classes()</code> set of this class hierarchy, but they may
139 cananian 1.1.2.13 * not be included in the <code>instantiatedClasses</code> set
140 cananian 1.1.2.13 * (if an instantiation instruction is not found for them). To
141 cananian 1.1.2.13 * explicitly include an instantiated class in the hierarchy, add
142 cananian 1.1.2.13 * a constructor or non-static method of that class to the
143 cananian 1.1.2.13 * <code>roots</code> <code>Collection</code>.<p> <code>hcf</code>
144 cananian 1.1.2.1 * must be a code factory that generates quad form. */
145 cananian 1.1.2.15 public QuadClassHierarchy(Linker linker,
146 cananian 1.1.2.15 Collection roots, HCodeFactory hcf) {
147 cananian 1.1.2.15 this(linker); // initialize hclass objects.
148 cananian 1.1.2.22 if (hcf.getCodeName().equals(harpoon.IR.Quads.QuadWithTry.codename)) {
149 cananian 1.1.2.22 // add 'implicit' exceptions to root set when analyzing QuadWithTry
150 cananian 1.1.2.22 String[] implExcName = new String[] {
151 cananian 1.1.2.22 "java.lang.ArrayStoreException",
152 cananian 1.1.2.22 "java.lang.NullPointerException",
153 cananian 1.1.2.22 "java.lang.ArrayIndexOutOfBoundsException",
154 cananian 1.1.2.22 "java.lang.NegativeArraySizeException",
155 cananian 1.1.2.22 "java.lang.ArithmeticException",
156 cananian 1.1.2.22 "java.lang.ClassCastException"
157 cananian 1.1.2.22 };
158 cananian 1.1.2.22 roots = new HashSet(roots); // make mutable
159 cananian 1.1.2.22 for (int i=0; i<implExcName.length; i++)
160 cananian 1.1.2.22 roots.add(linker.forName(implExcName[i])
161 cananian 1.1.2.22 .getConstructor(new HClass[0]));
162 cananian 1.1.2.22 }
163 cananian 1.1.2.1 // state.
164 cananian 1.1.2.28 final State S = new State();
165 cananian 1.1.2.1
166 cananian 1.1.2.13 // make initial worklist from roots collection.
167 cananian 1.1.2.2 for (Iterator it=roots.iterator(); it.hasNext(); ) {
168 cananian 1.1.2.13 HClass rootC; HMethod rootM; boolean instantiated;
169 cananian 1.1.2.13 // deal with the different types of objects in the roots collection
170 cananian 1.1.2.13 Object o = it.next();
171 cananian 1.1.2.13 if (o instanceof HMethod) {
172 cananian 1.1.2.13 rootM = (HMethod) o;
173 cananian 1.1.2.13 rootC = rootM.getDeclaringClass();
174 cananian 1.1.2.13 // let's assume non-static roots have objects to go with 'em.
175 cananian 1.1.2.13 instantiated = !rootM.isStatic();
176 cananian 1.1.2.13 } else { // only HMethods and HClasses in roots, so must be HClass
177 cananian 1.1.2.13 rootM = null;
178 cananian 1.1.2.13 rootC = (HClass) o;
179 cananian 1.3.2.5 // no methods of an array. so mention of an array means
180 cananian 1.3.2.5 // it is instantiated. otherwise, it's not.
181 cananian 1.3.2.5 instantiated = rootC.isArray();
182 cananian 1.1.2.13 }
183 cananian 1.1.2.13 if (instantiated)
184 cananian 1.1.2.27 discoverInstantiatedClass(S, rootC);
185 cananian 1.1.2.13 else
186 cananian 1.1.2.27 discoverClass(S, rootC);
187 cananian 1.1.2.13 if (rootM!=null)
188 cananian 1.1.2.27 methodPush(S, rootM);
189 cananian 1.1.2.2 }
190 cananian 1.1.2.13
191 cananian 1.1.2.13 // worklist algorithm.
192 cananian 1.1.2.27 while (!S.W.isEmpty()) {
193 cananian 1.3.2.2 HMethod m = S.W.pull();
194 cananian 1.1.2.27 S.done.add(m); // mark us done with this method.
195 cananian 1.1.2.1 // This method should be marked as usable.
196 cananian 1.1.2.1 {
197 cananian 1.3.2.2 Set<HMethod> s = S.classMethodsUsed.get(m.getDeclaringClass());
198 cananian 1.3.2.1 assert s!=null;
199 cananian 1.3.2.1 assert s.contains(m);
200 cananian 1.1.2.1 }
201 cananian 1.1.2.1 // look at the hcode for the method.
202 cananian 1.1.2.1 harpoon.IR.Quads.Code hc = (harpoon.IR.Quads.Code) hcf.convert(m);
203 cananian 1.1.2.1 if (hc==null) { // native or unanalyzable method.
204 cananian 1.3.2.4 if(!m.getReturnType().isPrimitive() &&
205 cananian 1.3.2.4 !m.getReturnType().isInterface())
206 cananian 1.1.2.9 // be safe; assume the native method can make an object
207 cananian 1.1.2.9 // of its return type.
208 cananian 1.1.2.27 discoverInstantiatedClass(S, m.getReturnType());
209 cananian 1.1.2.2 } else { // look for CALLs, NEWs, and ANEWs
210 cananian 1.1.2.28 QuadVisitor qv = new QuadVisitor() {
211 cananian 1.1.2.28 public void visit(Quad q) { /* do nothing */ }
212 cananian 1.1.2.28 // creation of a (possibly-new) class
213 cananian 1.1.2.28 public void visit(ANEW q) {
214 cananian 1.1.2.28 discoverInstantiatedClass(S, q.hclass());
215 cananian 1.1.2.28 }
216 cananian 1.1.2.28 public void visit(NEW q) {
217 cananian 1.1.2.28 discoverInstantiatedClass(S, q.hclass());
218 cananian 1.1.2.28 }
219 cananian 1.1.2.28 public void visit(CONST q) {
220 cananian 1.1.2.28 if (q.type().isPrimitive()) return;
221 cananian 1.1.2.28 discoverInstantiatedClass(S, q.type());
222 cananian 1.5 if (q.type().getName().equals("java.lang.String"))
223 cananian 1.5 // string constants use intern()
224 cananian 1.5 discoverMethod(S,HMstrIntern,false/*non-virtual*/);
225 cananian 1.5 if (q.type().getName().equals("java.lang.Class"))
226 cananian 1.5 discoverClass(S, (HClass) q.value());
227 cananian 1.5 if (q.type().getName().equals("java.lang.reflect.Field"))
228 cananian 1.5 discoverClass(S, ((HField) q.value()).getDeclaringClass());
229 cananian 1.5 if (q.type().getName().equals("java.lang.reflect.Method"))
230 cananian 1.5 discoverClass(S, ((HMethod) q.value()).getDeclaringClass());
231 cananian 1.1.2.28 }
232 cananian 1.1.2.28 // CALLs:
233 cananian 1.1.2.28 public void visit(CALL q) {
234 cananian 1.1.2.1 if (q.isStatic() || !q.isVirtual())
235 cananian 1.1.2.29 discoverMethod(S, q.method(),false/*non-virtual*/);
236 cananian 1.1.2.1 else
237 cananian 1.1.2.29 discoverMethod(S, q.method(),true/*virtual*/);
238 cananian 1.1.2.1 }
239 cananian 1.1.2.7 // get and set discover classes (don't instantiate, though)
240 cananian 1.1.2.28 public void visit(GET q) {
241 cananian 1.1.2.28 discoverClass(S, q.field().getDeclaringClass());
242 cananian 1.1.2.28 }
243 cananian 1.1.2.28 public void visit(SET q) {
244 cananian 1.1.2.28 discoverClass(S, q.field().getDeclaringClass());
245 cananian 1.1.2.7 }
246 cananian 1.1.2.8 // make sure we have the class we're testing against
247 cananian 1.1.2.8 // handy.
248 cananian 1.1.2.28 public void visit(INSTANCEOF q) {
249 cananian 1.1.2.33 discoverClass(S, q.hclass());
250 cananian 1.1.2.33 }
251 cananian 1.1.2.33 public void visit(TYPECAST q) {
252 cananian 1.1.2.28 discoverClass(S, q.hclass());
253 cananian 1.1.2.20 }
254 cananian 1.1.2.28 public void visit(TYPESWITCH q) {
255 cananian 1.1.2.20 for (int i=0; i<q.keysLength(); i++)
256 cananian 1.1.2.27 discoverClass(S, q.keys(i));
257 cananian 1.1.2.23 }
258 cananian 1.1.2.28 public void visit(HANDLER q) {
259 cananian 1.1.2.28 if (q.caughtException()==null) return;
260 cananian 1.1.2.28 discoverClass(S, q.caughtException());
261 cananian 1.1.2.8 }
262 cananian 1.1.2.28 };
263 cananian 1.1.2.28 // iterate through quads with visitor.
264 cananian 1.3.2.2 for (Iterator<Quad> it = hc.getElementsI(); it.hasNext(); )
265 cananian 1.3.2.2 it.next().accept(qv);
266 cananian 1.1.2.1 }
267 cananian 1.1.2.1 } // END worklist.
268 cananian 1.1.2.1
269 cananian 1.1.2.3 // build method table from classMethodsUsed.
270 cananian 1.3.2.2 for (Iterator<Set<HMethod>> it= S.classMethodsUsed.values().iterator();
271 cananian 1.1.2.4 it.hasNext(); )
272 cananian 1.3.2.2 methods.addAll(it.next());
273 cananian 1.1.2.3 // now generate children set from classKnownChildren.
274 cananian 1.7 for (HClass c : S.classKnownChildren.keySet()) {
275 cananian 1.3.2.2 Set<HClass> s = S.classKnownChildren.get(c);
276 cananian 1.3.2.2 HClass ch[] = s.toArray(new HClass[s.size()]);
277 cananian 1.1.2.1 children.put(c, ch);
278 cananian 1.1.2.1 }
279 cananian 1.1.2.1 }
280 cananian 1.1.2.1
281 cananian 1.1.2.1 /* when we discover a new class nc:
282 cananian 1.1.2.1 for each superclass c or superinterface i of this class,
283 cananian 1.1.2.1 add all called methods of c/i to worklist of nc, if nc implements.
284 cananian 1.1.2.1 */
285 cananian 1.1.2.27 private void discoverClass(State S, HClass c) {
286 cananian 1.1.2.27 if (S.classKnownChildren.containsKey(c)) return; // not a new class.
287 cananian 1.1.2.1 // add to known-children lists.
288 cananian 1.3.2.1 assert !S.classKnownChildren.containsKey(c);
289 cananian 1.1.2.27 S.classKnownChildren.put(c, new HashSet());
290 cananian 1.3.2.1 assert !S.classMethodsUsed.containsKey(c);
291 cananian 1.1.2.27 S.classMethodsUsed.put(c, new HashSet());
292 cananian 1.3.2.1 assert !S.classMethodsPending.containsKey(c);
293 cananian 1.1.2.27 S.classMethodsPending.put(c, new HashSet());
294 cananian 1.1.2.4 // add class initializer (if it exists) to "called" methods.
295 cananian 1.1.2.4 HMethod ci = c.getClassInitializer();
296 cananian 1.1.2.27 if ((ci!=null) && (!S.done.contains(ci)))
297 cananian 1.1.2.27 methodPush(S, ci);
298 cananian 1.1.2.22 // mark component type of arrays
299 cananian 1.1.2.22 if (c.isArray())
300 cananian 1.1.2.27 discoverClass(S, c.getComponentType());
301 cananian 1.1.2.22 // work through parents (superclass and interfaces)
302 cananian 1.7 for (Object pO : parents(c)) {
303 cananian 1.7 HClass p = (HClass) pO;
304 cananian 1.1.2.27 discoverClass(S, p);
305 cananian 1.3.2.2 Set<HClass> knownChildren = S.classKnownChildren.get(p);
306 cananian 1.1.2.1 knownChildren.add(c); // kC non-null after discoverClass.
307 cananian 1.1.2.1 }
308 cananian 1.1.2.4 }
309 cananian 1.1.2.27 private void discoverInstantiatedClass(State S, HClass c) {
310 cananian 1.1.2.4 if (instedClasses.contains(c)) return; else instedClasses.add(c);
311 cananian 1.1.2.27 discoverClass(S, c);
312 salcianu 1.1.2.26
313 cananian 1.1.2.4 // collect superclasses and interfaces.
314 cananian 1.1.2.4 // new worklist.
315 cananian 1.3.2.2 WorkSet<HClass> sW = new WorkSet<HClass>();
316 cananian 1.1.2.4 // put superclass and interfaces on worklist.
317 cananian 1.1.2.22 sW.addAll(parents(c));
318 cananian 1.1.2.1
319 cananian 1.1.2.4 // first, wake up all methods of this class that were
320 cananian 1.1.2.4 // pending instantiation, and clear the pending list.
321 cananian 1.3.2.2 List<HMethod> ml =
322 cananian 1.3.2.2 new ArrayList<HMethod>(S.classMethodsPending.get(c));//copy list
323 cananian 1.3.2.2 for (Iterator<HMethod> it=ml.iterator(); it.hasNext(); )
324 cananian 1.3.2.2 methodPush(S, it.next());
325 cananian 1.1.2.4
326 cananian 1.1.2.4 // if instantiated,
327 cananian 1.1.2.1 // add all called methods of superclasses/interfaces to worklist.
328 cananian 1.1.2.1 while (!sW.isEmpty()) {
329 cananian 1.1.2.1 // pull a superclass or superinterface off the list.
330 cananian 1.3.2.2 HClass s = sW.pop();
331 cananian 1.1.2.1 // add superclasses/interfaces of this one to local worklist
332 cananian 1.1.2.22 sW.addAll(parents(s));
333 cananian 1.1.2.1 // now add called methods of s to top-level worklist.
334 cananian 1.3.2.2 Set<HMethod> calledMethods =
335 cananian 1.3.2.2 new WorkSet<HMethod>(S.classMethodsUsed.get(s));
336 cananian 1.3.2.2 calledMethods.addAll(S.classMethodsPending.get(s));
337 cananian 1.7 for (HMethod m : calledMethods){
338 cananian 1.1.2.12 if (!isVirtual(m)) continue; // not inheritable.
339 cananian 1.1.2.1 try {
340 cananian 1.1.2.4 HMethod nm = c.getMethod(m.getName(),
341 cananian 1.1.2.4 m.getDescriptor());
342 cananian 1.1.2.27 if (!S.done.contains(nm))
343 cananian 1.1.2.27 methodPush(S, nm);
344 cananian 1.1.2.1 } catch (NoSuchMethodError nsme) { }
345 cananian 1.1.2.1 }
346 cananian 1.1.2.1 }
347 cananian 1.1.2.1 // done with this class/interface.
348 cananian 1.1.2.1 }
349 cananian 1.1.2.1 /* when we hit a method call site (method in class c):
350 cananian 1.1.2.1 add method of c and all children of c to worklist.
351 cananian 1.1.2.1 if method in interface i:
352 cananian 1.1.2.1 add method of c and all implementations of c.
353 cananian 1.1.2.1 */
354 cananian 1.1.2.29 private void discoverMethod(State S, HMethod m, boolean isVirtual) {
355 cananian 1.1.2.29 if (isVirtual && S.nonvirtual.contains(m)) {
356 cananian 1.1.2.29 // this is the first virtual invocation of a previously
357 cananian 1.1.2.29 // nonvirtual method.
358 cananian 1.1.2.30 // [removing m from S.nonvirtual will be done below,
359 cananian 1.1.2.30 // near the call to methodPush(S, nm)]
360 cananian 1.1.2.29 } else if (S.done.contains(m) || S.W.contains(m)) {
361 cananian 1.1.2.29 // we've done this guy before
362 cananian 1.1.2.29 return;
363 cananian 1.1.2.29 }
364 cananian 1.1.2.27 discoverClass(S, m.getDeclaringClass());
365 cananian 1.1.2.14 // Thread.start() implicitly causes a call to Thread.run()
366 cananian 1.1.2.14 if (m.equals(HMthrStart))
367 cananian 1.1.2.29 discoverMethod(S, HMthrRun, true/*virtual*/);
368 cananian 1.1.2.29 if (!isVirtual) { // short-cut for non-virtual methods.
369 cananian 1.1.2.29 S.nonvirtual.add(m);
370 cananian 1.1.2.29 methodPush(S, m);
371 cananian 1.1.2.29 return; // that's all folks.
372 cananian 1.1.2.29 }
373 cananian 1.1.2.32 // mark as pending in its own class if not already used.
374 cananian 1.3.2.2 if (!S.classMethodsUsed.get(m.getDeclaringClass()).contains(m))
375 cananian 1.3.2.2 S.classMethodsPending.get(m.getDeclaringClass()).add(m);
376 cananian 1.1.2.4 // now add as 'used' to all instantiated children.
377 cananian 1.1.2.4 // (including itself, if its own class has been instantiated)
378 cananian 1.3.2.2 WorkSet<HClass> cW = new WorkSet<HClass>();
379 cananian 1.1.2.1 cW.push(m.getDeclaringClass());
380 cananian 1.1.2.1 while (!cW.isEmpty()) {
381 cananian 1.1.2.1 // pull a class from the worklist
382 cananian 1.3.2.2 HClass c = cW.pull();
383 cananian 1.1.2.1 // see if we should add method-of-c to method worklist.
384 cananian 1.1.2.11 if (c.isInterface() || instedClasses.contains(c))
385 cananian 1.1.2.4 try {
386 cananian 1.1.2.4 HMethod nm = c.getMethod(m.getName(),
387 cananian 1.1.2.4 m.getDescriptor());
388 cananian 1.3.2.1 assert isVirtual; // shouldn't be here otherwise.
389 cananian 1.1.2.30 if (!S.done.contains(nm))
390 cananian 1.1.2.30 methodPush(S, nm);
391 cananian 1.1.2.32 else if (!S.nonvirtual.contains(nm))
392 cananian 1.1.2.32 continue; // nothing new to discover.
393 cananian 1.1.2.32 else S.nonvirtual.remove(nm); // since we're virtual here.
394 cananian 1.1.2.4 } catch (NoSuchMethodError e) { }
395 cananian 1.1.2.1 // add all children to the worklist.
396 cananian 1.3.2.2 Set<HClass> knownChildren = S.classKnownChildren.get(c);
397 cananian 1.3.2.2 for (Iterator<HClass> it=knownChildren.iterator(); it.hasNext(); )
398 cananian 1.1.2.1 cW.push(it.next());
399 cananian 1.1.2.1 }
400 cananian 1.1.2.1 // done.
401 cananian 1.1.2.1 }
402 cananian 1.1.2.14
403 cananian 1.1.2.27 private void methodPush(State S, HMethod m) {
404 cananian 1.3.2.1 assert !S.done.contains(m);
405 cananian 1.1.2.27 if (S.W.contains(m)) return; // already on work list.
406 cananian 1.1.2.1 // Add to worklist
407 cananian 1.1.2.27 S.W.add(m);
408 cananian 1.1.2.4 // mark this method as used.
409 cananian 1.3.2.2 Set<HMethod> s1 = S.classMethodsUsed.get(m.getDeclaringClass());
410 cananian 1.1.2.4 s1.add(m);
411 cananian 1.1.2.4 // and no longer pending.
412 cananian 1.3.2.2 Set<HMethod> s2 = S.classMethodsPending.get(m.getDeclaringClass());
413 cananian 1.1.2.4 s2.remove(m);
414 cananian 1.1.2.27 }
415 cananian 1.1.2.27 // State for algorithm.
416 cananian 1.1.2.27 private static class State {
417 cananian 1.1.2.27 // keeps track of methods which are actually invoked at some point.
418 cananian 1.3.2.2 final Map<HClass,Set<HMethod>> classMethodsUsed
419 cananian 1.3.2.2 = new HashMap<HClass,Set<HMethod>>(); // class->set map.
420 cananian 1.1.2.27 // keeps track of methods which might be called, if someone gets
421 cananian 1.1.2.27 // around to instantiating an object of the proper type.
422 cananian 1.3.2.2 final Map<HClass,Set<HMethod>> classMethodsPending
423 cananian 1.3.2.2 = new HashMap<HClass,Set<HMethod>>(); // class->set map
424 cananian 1.1.2.27 // keeps track of all known children of a given class.
425 cananian 1.3.2.2 final Map<HClass,Set<HClass>> classKnownChildren
426 cananian 1.3.2.2 = new HashMap<HClass,Set<HClass>>(); // class->set map.
427 cananian 1.1.2.27 // keeps track of which methods we've done already.
428 cananian 1.3.2.2 final Set<HMethod> done = new HashSet<HMethod>();
429 cananian 1.1.2.29 // keeps track of methods we've only seen non-virtual invocations for.
430 cananian 1.3.2.2 final Set<HMethod> nonvirtual = new HashSet<HMethod>();
431 cananian 1.1.2.27
432 cananian 1.1.2.27 // Worklist.
433 cananian 1.3.2.2 final WorkSet<HMethod> W = new WorkSet<HMethod>();
434 cananian 1.1.2.12 }
435 cananian 1.1.2.12
436 cananian 1.1.2.12 // useful utility method
437 cananian 1.1.2.12 private static boolean isVirtual(HMethod m) {
438 cananian 1.1.2.12 if (m.isStatic()) return false;
439 cananian 1.1.2.12 if (Modifier.isPrivate(m.getModifiers())) return false;
440 cananian 1.1.2.12 if (m instanceof HConstructor) return false;
441 cananian 1.1.2.12 return true;
442 cananian 1.1.2.1 }
443 cananian 1.1.2.1
444 cananian 1.1.2.1 /* ALGORITHM:
445 cananian 1.1.2.1 for each class:
446 cananian 1.1.2.1 table of all methods used in that class.
447 cananian 1.1.2.1 list of known immediate children of the class.
448 cananian 1.1.2.1 when we discover a new class nc:
449 cananian 1.1.2.1 for each superclass c of this class,
450 cananian 1.1.2.1 add all called methods of c to worklist of nc, if nc implements.
451 cananian 1.1.2.1 when we hit a method call site (method in class c):
452 cananian 1.1.2.1 add method of c and all children of c to worklist.
453 cananian 1.1.2.1 for each method on worklist:
454 cananian 1.1.2.1 mark method as used in class.
455 cananian 1.1.2.1 for each NEW: add possibly new class.
456 cananian 1.1.2.1 for each CALL: add possibly new methods.
457 cananian 1.1.2.1 */
458 cananian 1.2 }