1 cananian 1.1.2.1 // ClassHierarchy.java, created Wed Sep 8 14:34:46 1999 by cananian
2 cananian 1.1.2.1 // Copyright (C) 1999 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;
5 cananian 1.1.2.1
6 cananian 1.1.2.1 import harpoon.ClassFile.HClass;
7 cananian 1.1.2.4 import harpoon.ClassFile.HConstructor;
8 cananian 1.1.2.4 import harpoon.ClassFile.HMethod;
9 cananian 1.1.2.3 import harpoon.Util.ArraySet;
10 cananian 1.5 import net.cscott.jutil.Default;
11 cananian 1.1.2.3 import harpoon.Util.HClassUtil;
12 cananian 1.1.2.5 import harpoon.Util.Util;
13 cananian 1.5 import net.cscott.jutil.WorkSet;
14 cananian 1.1.2.1
15 cananian 1.1.2.4 import java.lang.reflect.Modifier;
16 cananian 1.1.2.3 import java.util.Collections;
17 cananian 1.1.2.4 import java.util.Iterator;
18 cananian 1.1.2.1 import java.util.Set;
19 cananian 1.1.2.1 /**
20 cananian 1.1.2.1 * A <code>ClassHierarchy</code> enumerates reachable/usable classes
21 cananian 1.1.2.1 * and methods.
22 cananian 1.1.2.1 *
23 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
24 cananian 1.5 * @version $Id: ClassHierarchy.java,v 1.5 2004/02/08 01:49:03 cananian Exp $
25 cananian 1.1.2.1 */
26 cananian 1.1.2.1 public abstract class ClassHierarchy {
27 cananian 1.1.2.1 // tree of callable classes
28 cananian 1.1.2.1 /** Returns all usable/reachable children of an <code>HClass</code>.
29 cananian 1.1.2.3 * For an interface class <code>c</code>, the children include all
30 cananian 1.1.2.3 * reachable classes which implement it as well as any reachable
31 cananian 1.1.2.3 * interfaces which extend it. For a non-interface class, children
32 cananian 1.1.2.3 * are all reachable subclasses.
33 cananian 1.1.2.1 * @return <code>Set</code> of <code>HClass</code>es.
34 cananian 1.1.2.1 */
35 cananian 1.3.2.2 public abstract Set<HClass> children(HClass c);
36 cananian 1.1.2.3 /** Return the parents of an <code>HClass</code>.
37 cananian 1.1.2.3 * The parents of a class <code>c</code> are its superclass and
38 cananian 1.1.2.3 * interfaces. The results should be complementary to the
39 cananian 1.1.2.3 * <code>children()</code> method:
40 cananian 1.1.2.3 * <code>parent(c)</code> of any class <code>c</code> returned
41 cananian 1.1.2.3 * by <code>children(cc)</code> should include <code>cc</code>.
42 cananian 1.1.2.3 */
43 cananian 1.3.2.2 public final Set<HClass> parents(HClass c) {
44 cananian 1.1.2.5 // odd inheritance properties:
45 cananian 1.1.2.5 // interfaces: all instances of an interface are also instances of
46 cananian 1.1.2.5 // java.lang.Object, so root all interfaces there.
47 cananian 1.1.2.5 // arrays: Integer[][]->Number[][]->Object[][]->Object[]->Object
48 cananian 1.1.2.5 // but also Set[][]->Collection[][]->Object[][]->Object[]->Object
49 cananian 1.1.2.5 // (i.e. interfaces are just as rooted here)
50 cananian 1.1.2.5 // note every use of c.getLinker() below is safe because c is
51 cananian 1.1.2.5 // guaranteed non-primitive in every context.
52 cananian 1.1.2.5 HClass base = HClassUtil.baseClass(c); int dims=HClassUtil.dims(c);
53 cananian 1.1.2.5 HClass su = base.getSuperclass();
54 cananian 1.1.2.5 HClass[] interfaces = base.getInterfaces();
55 cananian 1.1.2.5 boolean isObjArray = c.getDescriptor().endsWith("[Ljava/lang/Object;");
56 cananian 1.1.2.6 boolean isPrimArray = c.isArray() && base.isPrimitive();
57 cananian 1.1.2.5 // root interface inheritance hierarchy at Object.
58 cananian 1.1.2.5 if (interfaces.length==0 && base.isInterface())
59 cananian 1.1.2.5 su = c.getLinker().forName("java.lang.Object");// c not prim.
60 cananian 1.1.2.5 // create return value array.
61 cananian 1.1.2.5 HClass[] parents = new HClass[interfaces.length +
62 cananian 1.1.2.6 ((su!=null || isObjArray || isPrimArray)
63 cananian 1.1.2.6 ? 1 : 0)];
64 cananian 1.1.2.5 int n=0;
65 cananian 1.1.2.5 if (su!=null)
66 cananian 1.1.2.5 parents[n++] = HClassUtil.arrayClass(c.getLinker(),//c not prim.
67 cananian 1.1.2.5 su, dims);
68 cananian 1.1.2.5 for (int i=0; i<interfaces.length; i++)
69 cananian 1.1.2.5 parents[n++] = HClassUtil.arrayClass(c.getLinker(),//c not prim.
70 cananian 1.1.2.5 interfaces[i], dims);
71 cananian 1.1.2.5 // don't forget Object[][]->Object[]->Object
72 cananian 1.1.2.5 // (but remember also Object[][]->Cloneable->Object)
73 cananian 1.1.2.5 if (isObjArray)
74 cananian 1.1.2.5 parents[n++] = HClassUtil.arrayClass(c.getLinker(), base, dims-1);
75 cananian 1.1.2.6 // also! int[] -> Object.
76 cananian 1.1.2.6 if (isPrimArray) // c not prim.
77 cananian 1.1.2.6 parents[n++] = c.getLinker().forName("java.lang.Object");
78 cananian 1.1.2.5 // okay, done. Did we size the array correctly?
79 cananian 1.3.2.1 assert n==parents.length;
80 cananian 1.1.2.5 // okay, return as Set.
81 cananian 1.3.2.2 return new ArraySet<HClass>(parents);
82 cananian 1.1.2.4 }
83 cananian 1.1.2.4 /** Returns a set of methods in the hierarchy (not necessary reachable
84 cananian 1.1.2.4 * methods) which override the given method. The set is only one
85 cananian 1.1.2.4 * level deep; invoke children() again on each member of the returned
86 cananian 1.1.2.4 * set to find the rest of the possible overriding methods. Note
87 cananian 1.1.2.4 * however that interface methods may introduce some imprecision:
88 cananian 1.1.2.4 * in particular, for some hm2 in children(hm1) (where hm1 is an
89 cananian 1.1.2.4 * interface method), hm2.getDeclaringClass() may not implement
90 cananian 1.1.2.4 * hm1.getDeclaringClass(). For example, ListIterator.next() may
91 cananian 1.1.2.4 * be implemented by A, but B (a subclass of A which doesn't override
92 cananian 1.1.2.4 * A.next()) may be the class which implements ListIterator. */
93 cananian 1.3.2.2 public final Set<HMethod> overrides(HMethod hm) {
94 cananian 1.1.2.4 return overrides(hm.getDeclaringClass(), hm, false);
95 cananian 1.1.2.4 }
96 cananian 1.1.2.4 /** Returns the set of methods, excluding <code>hm</code>, declared
97 cananian 1.1.2.4 * in classes which are instances of <code>hc</code>, which override
98 cananian 1.1.2.4 * <code>hm</code>. If <code>all</code> is true, returns all such
99 cananian 1.1.2.4 * methods in the class hierarchy; otherwise returns only the methods
100 cananian 1.1.2.4 * which *immediately* override <code>hm</code>. */
101 cananian 1.3.2.2 public Set<HMethod> overrides(HClass hc, HMethod hm, boolean all) {
102 cananian 1.1.2.4 // non-virtual methods have no overrides.
103 cananian 1.1.2.4 if (hm.isStatic() || Modifier.isPrivate(hm.getModifiers()) ||
104 cananian 1.3.2.2 hm instanceof HConstructor) return Default.EMPTY_SET();
105 cananian 1.1.2.4 // determine overrides for virtual methods.
106 cananian 1.3.2.2 Set<HMethod> result = new WorkSet<HMethod>();
107 cananian 1.3.2.2 WorkSet<HClass> ws = new WorkSet<HClass>(this.children(hc));
108 cananian 1.1.2.4 while (!ws.isEmpty()) {
109 cananian 1.3.2.2 HClass hcc = ws.pop();
110 cananian 1.1.2.4 // note we don't catch MethodNotFoundError 'cuz we should find hm.
111 cananian 1.1.2.4 HMethod hmm = hcc.getMethod(hm.getName(), hm.getDescriptor());
112 cananian 1.1.2.4 if (!hm.equals(hmm)) {
113 cananian 1.1.2.4 // this is an overriding method!
114 cananian 1.1.2.4 result.add(hmm);
115 cananian 1.1.2.4 if (all) result.addAll(overrides(hcc, hmm, all));
116 cananian 1.1.2.4 } else
117 cananian 1.1.2.4 // keep looking for subclasses that declare method:
118 cananian 1.1.2.4 // add all subclasses of this one to the worklist.
119 cananian 1.1.2.4 ws.addAll(this.children(hcc));
120 cananian 1.1.2.4 }
121 cananian 1.1.2.4 return result;
122 cananian 1.1.2.3 }
123 cananian 1.1.2.1
124 cananian 1.1.2.1 // other methods.
125 cananian 1.1.2.1 /** Returns set of all callable methods.
126 cananian 1.1.2.1 * @return <code>Set</code> of <code>HMethod</code>s.
127 cananian 1.1.2.1 */
128 cananian 1.3.2.2 public abstract Set<HMethod> callableMethods();
129 cananian 1.1.2.1 /** Returns the set of all reachable/usable classes.
130 cananian 1.1.2.2 * If any method in a class is callable (including static methods),
131 cananian 1.1.2.2 * then the class will be a member of the returned set.
132 cananian 1.1.2.1 * @return <code>Set</code> of <code>HClass</code>es.
133 cananian 1.1.2.1 */
134 cananian 1.3.2.2 public abstract Set<HClass> classes();
135 cananian 1.1.2.2 /** Returns the set of all *instantiated* classes.
136 cananian 1.1.2.2 * This is a subset of the set returned by the <code>classes()</code>
137 cananian 1.1.2.2 * method. A class is included in the return set only if an
138 cananian 1.1.2.2 * object of that type is at some point created.
139 cananian 1.1.2.2 */
140 cananian 1.3.2.2 public abstract Set<HClass> instantiatedClasses();
141 cananian 1.2 }