1 cananian 1.1.4.1 // InterfaceMethodMap.java, created Tue Jan 19 17:10:17 1999 by pnkfelix
2 cananian 1.1.4.5 // Copyright (C) 1998 Felix S. Klock II <pnkfelix@mit.edu>
3 cananian 1.1.4.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1.4.1 package harpoon.Backend.Analysis;
5 cananian 1.1.4.1
6 cananian 1.1.4.1 import java.lang.reflect.Modifier;
7 cananian 1.1.4.1 import java.util.Collections;
8 cananian 1.1.4.1 import java.util.Enumeration;
9 cananian 1.1.4.1 import java.util.Hashtable;
10 cananian 1.1.4.1 import java.util.Vector;
11 cananian 1.1.4.1
12 cananian 1.1.4.1 import harpoon.ClassFile.HClass;
13 cananian 1.1.4.1 import harpoon.ClassFile.HConstructor;
14 cananian 1.1.4.1 import harpoon.ClassFile.HMethod;
15 cananian 1.1.4.1 import harpoon.Backend.Maps.MethodMap;
16 cananian 1.1.4.1
17 cananian 1.1.4.1 import harpoon.Util.Util;
18 cananian 1.5 import net.cscott.jutil.UniqueVector;
19 cananian 1.1.4.1
20 cananian 1.1.4.1 import harpoon.Analysis.ClassHierarchy;
21 cananian 1.1.4.1
22 cananian 1.1.4.1 import harpoon.Analysis.GraphColoring.Color;
23 cananian 1.1.4.1 import harpoon.Analysis.GraphColoring.ColorableNode;
24 cananian 1.1.4.1 import harpoon.Analysis.GraphColoring.ColorFactory;
25 cananian 1.1.4.1 import harpoon.Analysis.GraphColoring.SimpleGraphColorer;
26 pnkfelix 1.1.4.4 import harpoon.Analysis.GraphColoring.UnboundedGraphColorer;
27 cananian 1.1.4.1 import harpoon.Analysis.GraphColoring.SparseGraph;
28 cananian 1.1.4.1 import harpoon.Analysis.GraphColoring.SparseNode;
29 cananian 1.1.4.1 import harpoon.Analysis.GraphColoring.IllegalEdgeException;
30 cananian 1.1.4.1 /**
31 cananian 1.1.4.1 * <code>InterfaceMethodMap</code> provides a mapping from interface
32 cananian 1.1.4.1 * methods to the offset that the method-pointers should have on the
33 cananian 1.1.4.1 * object layout.
34 cananian 1.1.4.1 *
35 cananian 1.1.4.5 * @author Felix S. Klock II <pnkfelix@mit.edu>
36 cananian 1.5 * @version $Id: InterfaceMethodMap.java,v 1.5 2004/02/08 01:57:24 cananian Exp $
37 cananian 1.1.4.1 */
38 cananian 1.1.4.1
39 cananian 1.1.4.1 public class InterfaceMethodMap extends MethodMap {
40 cananian 1.1.4.1
41 cananian 1.1.4.1 private static boolean DEBUG = false;
42 cananian 1.1.4.1
43 cananian 1.1.4.1 // maps HMethod to HmNode
44 cananian 1.1.4.1 private Hashtable mtable;
45 cananian 1.1.4.1 private HmNodeFactory factory;
46 cananian 1.1.4.1
47 cananian 1.1.4.1 /** Creates a <code>InterfaceMethodMap</code> for interfaces in
48 cananian 1.1.4.1 <code>hclasses</code>.
49 cananian 1.1.4.1 <BR> <B>requires:</B> <code>hclasses</code> is an
50 cananian 1.1.4.1 <code>Enumeration</code> of
51 cananian 1.1.4.1 <code>HClass</code> objects.
52 cananian 1.1.4.1 <BR> <B>modifies:</B> <code>hclasses</code>
53 cananian 1.1.4.1 <BR> <B>effects:</B> Iterates through <code>hclasses</code>,
54 cananian 1.1.4.1 accumulating all of the interface-methods and
55 cananian 1.1.4.1 returns a method->int mapping, where the integer
56 cananian 1.1.4.1 returned represents the placement of the method.
57 cananian 1.1.4.1 This method is not guaranteed to use any
58 cananian 1.1.4.1 information besides what is passed to it;
59 cananian 1.1.4.1 methods from interfaces not in
60 cananian 1.1.4.1 <code>hclasses</code> are not required to be
61 cananian 1.1.4.1 included in the method map returned, and
62 cananian 1.1.4.1 interferences from classes not in
63 cananian 1.1.4.1 <code>hclasses</code> are not required to be
64 cananian 1.1.4.1 accounted for.
65 cananian 1.1.4.1 @see HClass
66 cananian 1.1.4.1 @see harpoon.Analysis.ClassHierarchy
67 cananian 1.1.4.1 @see harpoon.Main.CallGraph
68 cananian 1.1.4.1 */
69 cananian 1.1.4.1 public InterfaceMethodMap( Enumeration hclasses ) {
70 cananian 1.1.4.1 mtable = new Hashtable();
71 cananian 1.1.4.1 factory = new HmNodeFactory();
72 cananian 1.1.4.1
73 cananian 1.1.4.1 SparseGraph g = assembleGraph( hclasses );
74 pnkfelix 1.1.4.4 UnboundedGraphColorer colorer =
75 pnkfelix 1.1.4.4 new UnboundedGraphColorer(new SimpleGraphColorer(),
76 pnkfelix 1.1.4.4 new SlotColorFactory() );
77 cananian 1.1.4.1 colorer.findColoring( g );
78 cananian 1.1.4.1
79 cananian 1.1.4.1 }
80 cananian 1.1.4.1 /** Creates a <code>InterfaceMethodMap</code> for interfaces in
81 cananian 1.1.4.1 the given <code>ClassHierarchy</code> <code>ch</code>.
82 cananian 1.1.4.1 <BR> <B>effects:</B> Iterates through the class hierarchy
83 pnkfelix 1.1.4.4 accumulating all of the interface-methods and returns a
84 pnkfelix 1.1.4.4 method->int mapping, where the integer returned
85 pnkfelix 1.1.4.4 represents the placement of the method. This method is
86 pnkfelix 1.1.4.4 not guaranteed to use any information besides what is
87 pnkfelix 1.1.4.4 passed to it; methods from interfaces not in the class
88 pnkfelix 1.1.4.4 hierarchy are not required to be included in the method
89 pnkfelix 1.1.4.4 map returned, and interferences from classes not in
90 pnkfelix 1.1.4.4 the class hierarchy are not required to be accounted for.
91 cananian 1.1.4.1 @see HClass
92 cananian 1.1.4.1 @see harpoon.Analysis.ClassHierarchy
93 cananian 1.1.4.1 @see harpoon.Main.CallGraph
94 cananian 1.1.4.1 */
95 cananian 1.1.4.1 public InterfaceMethodMap( ClassHierarchy ch ) {
96 cananian 1.1.4.1 this(Collections.enumeration(ch.classes()));
97 cananian 1.1.4.1 }
98 cananian 1.1.4.1
99 cananian 1.1.4.1 /** Returns an ordering of the given method.
100 cananian 1.1.4.1 <BR> <B>requires:</B> <code>this</code> contains an ordering
101 cananian 1.1.4.1 for <code>hm</code>
102 cananian 1.1.4.1 <BR> <B>effects:</B> returns the zero-indexed integer
103 cananian 1.1.4.1 corresponding to <code>hm</code>'s
104 cananian 1.1.4.1 placement in the ordering.
105 cananian 1.1.4.1 */
106 cananian 1.1.4.1 public int methodOrder( HMethod hm ) {
107 cananian 1.1.4.1 // method must be an interface method and thus public,
108 cananian 1.1.4.1 // not static, and not a constructor.
109 cananian 1.3.2.1 assert hm.isInterfaceMethod() && !hm.isStatic();
110 cananian 1.3.2.1 assert Modifier.isPublic(hm.getModifiers());
111 cananian 1.3.2.1 assert !(hm instanceof HConstructor);
112 cananian 1.1.4.7 // also disallow methods inherited from java.lang.Object
113 cananian 1.3.2.1 assert includeMethod(hm) : hm;
114 cananian 1.1.4.1 HmNode node = (HmNode) mtable.get( hm );
115 cananian 1.3.2.1 assert node != null : "InterfaceMethodMap must contain "+
116 cananian 1.3.2.1 "a mapping for " + hm;
117 cananian 1.1.4.1 SlotColor c = (SlotColor) node.getColor();
118 cananian 1.1.4.1 return c.index;
119 cananian 1.1.4.1 }
120 cananian 1.1.4.1
121 cananian 1.1.4.1
122 cananian 1.1.4.1 // -- HELPER METHODS FOR CONSTUCTOR FOLLOW --
123 cananian 1.1.4.1
124 cananian 1.1.4.1 /** Assembles a graph for use by the graph colorer.
125 cananian 1.1.4.1 <BR> <B>requires:</B> <code>hclasses</code> is an enumeration of
126 cananian 1.1.4.1 <code>HClass</code> objects
127 cananian 1.1.4.1 <BR> <B>modifies:</B> <code>hclasses</code>
128 cananian 1.1.4.1 <BR> <B>effects:</B> Iterates through <code>hclasses</code>,
129 cananian 1.1.4.1 building up a graph with nodes
130 cananian 1.1.4.1 corresponding to the methods of the
131 cananian 1.1.4.1 interfaces in <code>hclasses</code> and
132 cananian 1.1.4.1 the edges corresponding to interferences
133 cananian 1.1.4.1 between the methods (due to being
134 cananian 1.1.4.1 implemented by the same classes).
135 cananian 1.1.4.1 */
136 cananian 1.1.4.1 private SparseGraph assembleGraph( Enumeration hclasses ) {
137 cananian 1.1.4.1 UniqueVector classes = new UniqueVector();
138 cananian 1.1.4.1 UniqueVector interfaces = new UniqueVector();
139 cananian 1.1.4.1 SparseGraph graph = new SparseGraph();
140 cananian 1.1.4.1
141 cananian 1.1.4.1 // MAKE NODES (methods of interfaces)
142 cananian 1.1.4.1 while ( hclasses.hasMoreElements() ) {
143 cananian 1.1.4.1 HClass hc = (HClass) hclasses.nextElement();
144 cananian 1.1.4.1 if (hc.isInterface()) { // INTERFACE
145 cananian 1.1.4.1 // make nodes for each method and add them to graph
146 cananian 1.1.4.1 if (DEBUG) System.out.println("Adding methods of interface " +
147 cananian 1.1.4.1 hc + " to graph");
148 cananian 1.1.4.1
149 cananian 1.1.4.1 interfaces.addElement( hc );
150 cananian 1.1.4.1 HMethod[] methods = hc.getMethods();
151 cananian 1.1.4.1 for (int i=0; i<methods.length; i++) {
152 cananian 1.1.4.1 if (includeMethod( methods[i] )) {
153 cananian 1.1.4.1 HmNode mnode = factory.getNode( methods[i] );
154 cananian 1.1.4.1 if (DEBUG) System.out.println
155 cananian 1.1.4.1 ("Adding method/node " +
156 cananian 1.1.4.1 methods[i] + " / " + mnode);
157 cananian 1.1.4.1 graph.addNode( mnode );
158 cananian 1.1.4.1 }
159 cananian 1.1.4.1 }
160 cananian 1.1.4.1 } else { // CLASS
161 cananian 1.1.4.1 // add hclasses to classes for later edge searching
162 cananian 1.1.4.1 if (DEBUG) System.out.println
163 cananian 1.1.4.1 ("Storing " + hc + " for later searching");
164 cananian 1.1.4.1 classes.addElement( hc );
165 cananian 1.1.4.1 }
166 cananian 1.1.4.1 }
167 cananian 1.1.4.1
168 cananian 1.1.4.1 // MAKE EDGES (between nodes belonging to interfaces
169 cananian 1.1.4.1 // implemented by same class)
170 cananian 1.1.4.1 for (int i=0; i<classes.size(); i++) {
171 cananian 1.1.4.1 HClass hc = (HClass) classes.elementAt(i);
172 cananian 1.1.4.1 UniqueVector cNodes = new UniqueVector();
173 cananian 1.1.4.1
174 cananian 1.1.4.1 // backtrack through hierarchy, adding all methods of all
175 cananian 1.1.4.1 // interfaces found.
176 cananian 1.1.4.1 while( hc != null ) {
177 cananian 1.1.4.1 HClass[] ifaces = hc.getInterfaces();
178 cananian 1.1.4.1 for (int j=0; j<ifaces.length; j++) {
179 cananian 1.1.4.1 Vector nodes = findNodesFor( ifaces[j] );
180 cananian 1.1.4.1 for(int k=0; k<nodes.size(); k++) {
181 cananian 1.1.4.1 cNodes.addElement( nodes.elementAt( k ));
182 cananian 1.1.4.1 }
183 cananian 1.1.4.1 }
184 cananian 1.1.4.1 hc = hc.getSuperclass();
185 cananian 1.1.4.1 }
186 cananian 1.1.4.1
187 cananian 1.1.4.1 for (int j=0; j<cNodes.size(); j++) {
188 cananian 1.1.4.1 HmNode nodeA = (HmNode) cNodes.elementAt(j);
189 cananian 1.1.4.1 for (int k=j+1; k<cNodes.size(); k++) {
190 cananian 1.1.4.1 HmNode nodeB = (HmNode) cNodes.elementAt(k);
191 cananian 1.1.4.1 try {
192 cananian 1.1.4.1 if (DEBUG) System.out.println
193 cananian 1.1.4.1 ("Making an edge between " + nodeA +
194 cananian 1.1.4.1 " and " + nodeB + " in graph.");
195 cananian 1.1.4.1 graph.makeEdge( nodeA, nodeB );
196 cananian 1.1.4.1 } catch (IllegalEdgeException e) {
197 cananian 1.1.4.1 // ignore (algorithm is dumb and doesn't know
198 cananian 1.1.4.1 // better.
199 cananian 1.1.4.1 }
200 cananian 1.1.4.1 }
201 cananian 1.1.4.1 }
202 cananian 1.1.4.1 }
203 cananian 1.1.4.1
204 cananian 1.1.4.1 return graph;
205 cananian 1.1.4.1 }
206 cananian 1.1.4.1
207 cananian 1.1.4.1
208 cananian 1.1.4.1 /** Checks suitability of an HMethod for inclusion in a graph.
209 cananian 1.1.4.1 <BR> <B>effects:</B> if <code>m</code> is a method of
210 cananian 1.1.4.1 <code>java.lang.Object</code> then
211 cananian 1.1.4.1 returns false. Else returns true.
212 cananian 1.1.4.1 */
213 cananian 1.1.4.1 private static boolean includeMethod(HMethod m) {
214 cananian 1.1.4.7 // can't just check m.getDeclaringClass() because some interfaces
215 cananian 1.1.4.7 // re-define methods from java.lang.Object. Try to find the
216 cananian 1.1.4.7 // method's signature in java.lang.Object instead.
217 cananian 1.1.4.7 try {
218 cananian 1.1.4.7 // safe to getLinker because m.getDeclaringClass() is non-primitive
219 cananian 1.1.4.7 m.getDeclaringClass().getLinker().forName("java.lang.Object")
220 cananian 1.1.4.7 .getMethod(m.getName(), m.getDescriptor());
221 cananian 1.1.4.7 // if this call succeeded, then *don't* include this method as
222 cananian 1.1.4.7 // an interface method!
223 cananian 1.1.4.7 return false;
224 cananian 1.1.4.7 } catch (NoSuchMethodError nsme) {
225 cananian 1.1.4.7 return true;
226 cananian 1.1.4.7 }
227 cananian 1.1.4.1 }
228 cananian 1.1.4.1
229 cananian 1.1.4.1 /** Generates a <code>Vector</code> of <code>HmNode</code>s for
230 cananian 1.1.4.1 methods in an interface.
231 cananian 1.1.4.1 <BR> <B>requires:</B> <code>interfce</code> is an HClass
232 cananian 1.1.4.1 representing an interface, and there are
233 cananian 1.1.4.1 no circular interface extensions
234 cananian 1.1.4.1 (ie "A extends B" and "B extends A")
235 cananian 1.1.4.1 <BR> <B>effects:</B> Iterates over the accessible methods of
236 cananian 1.1.4.1 <code>interfce</code>, accumulating them
237 cananian 1.1.4.1 in a <code>Vector</code> of
238 cananian 1.1.4.1 <code>HmNode</code>s. Methods of
239 cananian 1.1.4.1 superinterfaces are included, but the
240 cananian 1.1.4.1 methods of Object are not. Returns the
241 cananian 1.1.4.1 newly built <code>Vector</code> of
242 cananian 1.1.4.1 <code>HmNode</code>s.
243 cananian 1.1.4.1 */
244 cananian 1.1.4.1 private Vector findNodesFor( HClass interfce ) {
245 cananian 1.3.2.1 assert interfce.isInterface();
246 cananian 1.1.4.1 if (DEBUG) System.out.println("Finding nodes for " + interfce);
247 cananian 1.1.4.1 Vector nodes = new Vector();
248 cananian 1.1.4.1 HMethod[] methods = interfce.getMethods();
249 cananian 1.1.4.1 for (int i=0; i<methods.length; i++) {
250 cananian 1.1.4.1 if (includeMethod( methods[i] )) {
251 cananian 1.1.4.1 if (DEBUG) System.out.println
252 cananian 1.1.4.1 ("Adding method " + methods[ i ]);
253 cananian 1.1.4.1 nodes.addElement( factory.getNode( methods[ i ] ) );
254 cananian 1.1.4.1 }
255 cananian 1.1.4.1 }
256 cananian 1.1.4.1
257 cananian 1.1.4.1 // this sequence of code is unnecessary; HClass.getMethods()
258 cananian 1.1.4.1 // now performs according to spec.
259 cananian 1.1.4.1 /*
260 cananian 1.1.4.1 HClass[] superinterfaces = interfce.getInterfaces();
261 cananian 1.1.4.1 for (int i=0; i<superinterfaces.length; i++) {
262 cananian 1.1.4.1 Vector v = findNodesFor( superinterfaces[i] );
263 cananian 1.1.4.1 for (int j=0; j<v.size(); j++) {
264 cananian 1.1.4.1 nodes.addElement(v.elementAt(j));
265 cananian 1.1.4.1 }
266 cananian 1.1.4.1 }
267 cananian 1.1.4.1 */
268 cananian 1.1.4.1
269 cananian 1.1.4.1 return nodes;
270 cananian 1.1.4.1 }
271 cananian 1.1.4.1
272 cananian 1.1.4.1 /** Produces HmNodes from HMethods, enforcing a mapping from a
273 cananian 1.1.4.1 method's name and set of argument types to one unique node,
274 cananian 1.1.4.1 regardless of which interface the method appears in.
275 cananian 1.1.4.6 <p>
276 cananian 1.1.4.6 Interface methods with the same name and descriptor always
277 cananian 1.1.4.6 map to the same slot, either due to single or multiple inheritance.
278 cananian 1.1.4.6 For example, A.foo() maps to the same slot as B.foo() if interface
279 cananian 1.1.4.6 B extends interface A; if interface B also extends interface C
280 cananian 1.1.4.6 and C has C.foo() then all three methods would always map to the
281 cananian 1.1.4.6 same slot (it is impossible to give C.foo() a different
282 cananian 1.1.4.6 implementation from A.foo() in any class which implements both A
283 cananian 1.1.4.6 and C).
284 cananian 1.1.4.1 */
285 cananian 1.1.4.1 private class HmNodeFactory {
286 cananian 1.1.4.1 // maps HmNode to HmNode
287 cananian 1.1.4.1 Hashtable ntable;
288 cananian 1.1.4.1
289 cananian 1.1.4.1 HmNodeFactory() {
290 cananian 1.1.4.1 ntable = new Hashtable();
291 cananian 1.1.4.1 }
292 cananian 1.1.4.1
293 cananian 1.1.4.1 HmNode getNode( HMethod hm ) {
294 cananian 1.1.4.1 HmNode temp = new HmNode( hm );
295 cananian 1.1.4.1 HmNode real = (HmNode) ntable.get( temp );
296 cananian 1.1.4.1 HmNode rtrn;
297 cananian 1.1.4.1 if (real == null) {
298 cananian 1.1.4.1 ntable.put( temp, temp );
299 cananian 1.1.4.1 rtrn = temp;
300 cananian 1.1.4.1 } else {
301 cananian 1.1.4.1 rtrn = real;
302 cananian 1.1.4.1 }
303 cananian 1.1.4.1 mtable.put( hm, rtrn );
304 cananian 1.1.4.1 return rtrn;
305 cananian 1.1.4.1 }
306 cananian 1.1.4.1 }
307 cananian 1.1.4.1
308 cananian 1.1.4.1
309 cananian 1.1.4.1 /** HmNode is an extension of a SparseNode suitable for
310 cananian 1.1.4.1 representing a method of an interface.
311 cananian 1.1.4.1 */
312 cananian 1.1.4.1 private class HmNode extends SparseNode {
313 cananian 1.1.4.6 final String name, desc;
314 cananian 1.1.4.1 int hash;
315 cananian 1.1.4.1
316 cananian 1.1.4.1 HmNode( HMethod hm ) {
317 cananian 1.1.4.1 name = hm.getName();
318 cananian 1.1.4.6 desc = hm.getDescriptor();
319 cananian 1.1.4.6 hash = name.hashCode() ^ desc.hashCode();
320 cananian 1.1.4.1 }
321 cananian 1.1.4.1
322 cananian 1.1.4.1 public int hashCode() { return hash; }
323 cananian 1.1.4.1
324 cananian 1.1.4.1 public boolean equals(Object o) {
325 cananian 1.1.4.1 HmNode n;
326 cananian 1.1.4.1 if (o==null) return false;
327 cananian 1.1.4.1 if (this==o) return true;
328 cananian 1.1.4.1 try { n = (HmNode) o; }
329 cananian 1.1.4.1 catch (ClassCastException e) { return false; }
330 cananian 1.1.4.6 if (n.hash!=this.hash) return false;
331 cananian 1.1.4.6 return n.name.equals(this.name) && n.desc.equals(this.desc);
332 cananian 1.1.4.1 }
333 cananian 1.1.4.1
334 cananian 1.1.4.1 public String toString() {
335 cananian 1.1.4.6 return "HMethod Node [ " + name + desc + " " + hash +" ]";
336 cananian 1.1.4.1 }
337 cananian 1.1.4.1 }
338 cananian 1.1.4.1
339 cananian 1.1.4.1 /** Simple implementation of a ColorFactory for interface slots. */
340 cananian 1.1.4.1 private class SlotColorFactory extends ColorFactory {
341 cananian 1.1.4.1 int counter;
342 cananian 1.1.4.1
343 cananian 1.1.4.1 SlotColorFactory() {
344 cananian 1.1.4.1 counter = 0;
345 cananian 1.1.4.1 }
346 cananian 1.1.4.1
347 cananian 1.1.4.1 protected Color newColor() {
348 cananian 1.1.4.1 counter++;
349 cananian 1.1.4.1 return new SlotColor(counter);
350 cananian 1.1.4.1 }
351 cananian 1.1.4.1 }
352 cananian 1.1.4.1
353 cananian 1.1.4.1 /** Simple implementation of a Color for interface slots. */
354 cananian 1.1.4.1 private class SlotColor extends Color {
355 cananian 1.1.4.1 int index;
356 cananian 1.1.4.1 SlotColor(int i) { index = i; }
357 pnkfelix 1.1.4.3 public String toString() { return "SlotColor"+index; }
358 cananian 1.1.4.1 }
359 cananian 1.1.4.1 }
360 cananian 1.2