1 cananian 1.1.2.1 // InitializerOrdering.java, created Thu Oct 14 12:42:50 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.Backend.Analysis;
5 cananian 1.1.2.1
6 cananian 1.1.2.3 import harpoon.Analysis.CallGraph;
7 cananian 1.1.2.1 import harpoon.Analysis.ClassHierarchy;
8 cananian 1.1.2.1 import harpoon.ClassFile.HClass;
9 cananian 1.1.2.1 import harpoon.ClassFile.HInitializer;
10 cananian 1.1.2.1 import harpoon.ClassFile.HMethod;
11 cananian 1.5 import net.cscott.jutil.UniqueVector;
12 cananian 1.1.2.1 import harpoon.Util.Util;
13 cananian 1.5 import net.cscott.jutil.WorkSet;
14 cananian 1.1.2.1
15 cananian 1.1.2.1 import java.util.ArrayList;
16 cananian 1.1.2.1 import java.util.Collections;
17 cananian 1.1.2.1 import java.util.HashSet;
18 cananian 1.1.2.1 import java.util.Iterator;
19 cananian 1.1.2.1 import java.util.List;
20 cananian 1.1.2.1 import java.util.Set;
21 cananian 1.1.2.1 /**
22 cananian 1.1.2.1 * <code>InitializerOrdering</code> computes a topological sort of
23 cananian 1.1.2.1 * the static initializer call graph designed to ensure that
24 cananian 1.1.2.1 * classes are initialized in the correct order. Cycles in
25 cananian 1.1.2.1 * the initializer call graph will emit warnings; executing the
26 cananian 1.1.2.1 * static initializers in the order given is not guaranteed
27 cananian 1.1.2.1 * to produce the same results as executing them on demand
28 cananian 1.1.2.1 * in that case.
29 cananian 1.1.2.1 *
30 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
31 cananian 1.6 * @version $Id: InitializerOrdering.java,v 1.6 2004/02/08 03:20:42 cananian Exp $
32 cananian 1.1.2.1 */
33 cananian 1.1.2.1 public class InitializerOrdering {
34 cananian 1.1.2.1 public final List sorted;
35 cananian 1.1.2.1 /** Creates a <code>InitializerOrdering</code>. */
36 cananian 1.1.2.1 public InitializerOrdering(ClassHierarchy ch, CallGraph cg) {
37 cananian 1.1.2.1 List _sorted = new ArrayList();
38 cananian 1.1.2.1 Set touched = new HashSet(), added = new HashSet();
39 cananian 1.6 for (Object hcO : ch.classes()) {
40 cananian 1.6 HClass hc = (HClass) hcO;
41 cananian 1.1.2.1 if (!added.contains(hc))
42 cananian 1.1.2.1 examineClass(ch, cg, hc, touched, added, _sorted);
43 cananian 1.1.2.1 }
44 cananian 1.1.2.1 this.sorted = Collections.unmodifiableList(_sorted);
45 cananian 1.1.2.1 }
46 cananian 1.1.2.1 private void examineClass(ClassHierarchy ch, CallGraph cg, HClass c,
47 cananian 1.1.2.1 Set touched, Set added, List _sorted) {
48 cananian 1.3.2.1 assert ch.classes().contains(c) : ("Being examined, although it's not in hierarchy:"+c);
49 cananian 1.3.2.1 assert !added.contains(c);
50 cananian 1.3.2.1 assert !touched.contains(c);
51 cananian 1.1.2.1 touched.add(c);
52 cananian 1.1.2.1 // first, all superclass initializers must be called.
53 cananian 1.1.2.1 for (HClass hcp=c.getSuperclass(); hcp!=null; hcp=hcp.getSuperclass())
54 cananian 1.1.2.1 if (!touched.contains(hcp))
55 cananian 1.1.2.1 examineClass(ch, cg, hcp, touched, added, _sorted);
56 cananian 1.1.2.1 else if (!added.contains(hcp))
57 cananian 1.1.2.1 warnCircle(hcp);
58 cananian 1.1.2.1 // now, all methods called by this static initializer must be examined
59 cananian 1.1.2.1 HMethod m = c.getClassInitializer();
60 cananian 1.1.2.4 if (m!=null && !touched.contains(m))
61 cananian 1.1.2.4 examineMethod(ch, cg, c, m, touched, added, _sorted);
62 cananian 1.1.2.1 // okay, all dependencies have been added, so now add this initializer
63 cananian 1.1.2.1 if (m!=null) _sorted.add(m);
64 cananian 1.1.2.1 added.add(c);
65 cananian 1.1.2.1 }
66 cananian 1.1.2.1 private void examineMethod(ClassHierarchy ch, CallGraph cg,
67 cananian 1.1.2.1 HClass initClass, HMethod m,
68 cananian 1.1.2.1 Set touched, Set added, List _sorted) {
69 cananian 1.3.2.1 assert ch.callableMethods().contains(m) : ("Being examined, although it's not callable:"+m);
70 cananian 1.3.2.1 assert !touched.contains(m);
71 cananian 1.1.2.1 touched.add(m);
72 cananian 1.1.2.1 // first check that the class containing this method has been init'ed.
73 cananian 1.1.2.1 // this class is *being* init'ed if m is an initializer, so skip then.
74 cananian 1.1.2.1 HClass hc = m.getDeclaringClass();
75 cananian 1.1.2.1 if (hc != initClass) { // we're already initializing this class.
76 cananian 1.1.2.1 if (!touched.contains(hc))
77 cananian 1.1.2.1 examineClass(ch, cg, hc, touched, added, _sorted);
78 cananian 1.1.2.1 else if (!added.contains(hc))
79 cananian 1.1.2.1 warnCircle(hc);
80 cananian 1.1.2.1 }
81 cananian 1.1.2.1 // now recursively invoke all the methods which this guy calls.
82 cananian 1.1.2.1 HMethod[] deps = cg.calls(m);
83 cananian 1.1.2.1 for (int i=0; i<deps.length; i++) {
84 cananian 1.1.2.1 if (!touched.contains(deps[i]))// could be recursive functions here
85 cananian 1.1.2.1 examineMethod(ch, cg, initClass, deps[i],
86 cananian 1.1.2.1 touched, added, _sorted);
87 cananian 1.1.2.1 }
88 cananian 1.1.2.2 // XXX: ACCESSED FIELDS ALSO TRIGGER INITIALIZERS!
89 cananian 1.1.2.1 // okay, done looking at this method.
90 cananian 1.1.2.1 }
91 cananian 1.1.2.1 private void warnCircle(HClass hc) {
92 cananian 1.1.2.1 System.err.println("WARNING: circular dependency on " +
93 cananian 1.1.2.1 hc.getName() + " in static initializers.");
94 cananian 1.1.2.1 }
95 cananian 1.2 }