0001: /* Copyright (C) 2004 - 2007 db4objects Inc. http://www.db4o.com
0002:
0003: This file is part of the db4o open source object database.
0004:
0005: db4o is free software; you can redistribute it and/or modify it under
0006: the terms of version 2 of the GNU General Public License as published
0007: by the Free Software Foundation and as clarified by db4objects' GPL
0008: interpretation policy, available at
0009: http://www.db4o.com/about/company/legalpolicies/gplinterpretation/
0010: Alternatively you can write to db4objects, Inc., 1900 S Norfolk Street,
0011: Suite 350, San Mateo, CA 94403, USA.
0012:
0013: db4o is distributed in the hope that it will be useful, but WITHOUT ANY
0014: WARRANTY; without even the implied warranty of MERCHANTABILITY or
0015: FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0016: for more details.
0017:
0018: You should have received a copy of the GNU General Public License along
0019: with this program; if not, write to the Free Software Foundation, Inc.,
0020: 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
0021: package EDU.purdue.cs.bloat.editor;
0022:
0023: import java.io.*;
0024: import java.util.*;
0025:
0026: import EDU.purdue.cs.bloat.reflect.*;
0027: import EDU.purdue.cs.bloat.util.*;
0028:
0029: /**
0030: * ClassHierarchy maintains a graph of the subclass relationships of the classes
0031: * loaded by the ClassInfoLoader.
0032: *
0033: * @see ClassInfoLoader
0034: */
0035: public class ClassHierarchy {
0036: public static final Type POS_SHORT = Type.getType("L+short!;");
0037:
0038: public static final Type POS_BYTE = Type.getType("L+byte!;");
0039:
0040: static final int MAX_INT = 8;
0041:
0042: static final int MAX_SHORT = 7;
0043:
0044: static final int MAX_CHAR = 6;
0045:
0046: static final int MAX_BYTE = 5;
0047:
0048: static final int MAX_BOOL = 4;
0049:
0050: static final int MIN_CHAR = 3;
0051:
0052: static final int MIN_BOOL = 3;
0053:
0054: static final int ZERO = 3;
0055:
0056: static final int MIN_BYTE = 2;
0057:
0058: static final int MIN_SHORT = 1;
0059:
0060: static final int MIN_INT = 0;
0061:
0062: public static boolean DEBUG = false;
0063:
0064: public static boolean RELAX = false;
0065:
0066: Set classes; // The Types of the classes in hierarchy
0067:
0068: Graph extendsGraph; // "Who extends who" graph
0069:
0070: Graph implements Graph; // "Who implements what" graph
0071:
0072: boolean closure; // Do we visit all referenced classes?
0073:
0074: // Maps methods to the methods they may resolve to
0075: private Map resolvesToCache;
0076:
0077: // These are only needed during construction.
0078: EditorContext context;
0079:
0080: LinkedList worklist;
0081:
0082: Set inWorklist;
0083:
0084: private void db(final String s) {
0085: if (ClassHierarchy.DEBUG) {
0086: System.out.println(s);
0087: }
0088: }
0089:
0090: /**
0091: * Constructor.
0092: *
0093: * @param context
0094: * The context in which to access an <Tt>Editor</tt> and other
0095: * such things.
0096: * @param initial
0097: * The names of the classes that initially constitue the
0098: * hierarchy.
0099: * @param closure
0100: * Do we get the maximum amount of class information?
0101: */
0102: public ClassHierarchy(final EditorContext context,
0103: final Collection initial, final boolean closure) {
0104: this .context = context;
0105: this .closure = closure;
0106:
0107: classes = new HashSet();
0108: extendsGraph = new Graph();
0109: implements Graph = new Graph();
0110:
0111: worklist = new LinkedList();
0112: inWorklist = new HashSet();
0113:
0114: this .resolvesToCache = new HashMap();
0115:
0116: // Need new ArrayList to avoid ConcurrentModificationException
0117: final Iterator iter = new ArrayList(initial).iterator();
0118:
0119: while (iter.hasNext()) {
0120: final String name = (String) iter.next();
0121: addClass(name);
0122: }
0123: }
0124:
0125: /**
0126: * Adds a class of a given name to the ClassHierarchy.
0127: */
0128: public void addClassNamed(final String name) {
0129: addClass(name);
0130: }
0131:
0132: /**
0133: * Returns the immediate subclasses of a given <tt>Type</tt> as a
0134: * <tt>Collection</tt> of <tt>Type</tt>s.
0135: *
0136: * <p>
0137: *
0138: * The subclass relationship at the classfile level is a little screwy with
0139: * respect to interfaces. An interface that extends another interface is
0140: * compiled into an interface that extends java.lang.Object and implements
0141: * the superinterface. As a result, the interface-subinterface is not
0142: * captured in <tt>subclasses</tt> as one may expect. Instead, you have to
0143: * look at <tt>implementors</tt> and filter out the classes.
0144: */
0145: public Collection subclasses(final Type type) {
0146: final TypeNode node = getExtendsNode(type);
0147:
0148: if (node != null) {
0149: final List list = new ArrayList(extendsGraph.preds(node));
0150:
0151: final ListIterator iter = list.listIterator();
0152:
0153: while (iter.hasNext()) {
0154: final TypeNode v = (TypeNode) iter.next();
0155: iter.set(v.type);
0156: }
0157:
0158: return list;
0159: }
0160:
0161: return new ArrayList();
0162: }
0163:
0164: /**
0165: * Returns the superclass of a given <tt>Type</tt>. If the <tt>Type</tt>
0166: * has no superclass (that is it is <tt>Type.OBJECT</tt>), then null is
0167: * returned.
0168: */
0169: public Type super class(final Type type) {
0170: final TypeNode node = getExtendsNode(type);
0171:
0172: if (node != null) {
0173: final Collection succs = extendsGraph.succs(node);
0174:
0175: final Iterator iter = succs.iterator();
0176:
0177: if (iter.hasNext()) {
0178: final TypeNode v = (TypeNode) iter.next();
0179: return v.type;
0180: }
0181: }
0182:
0183: return null;
0184: }
0185:
0186: /**
0187: * Returns the interfaces that a given <tt>Type</tt> implements as a
0188: * <tt>Collection</tt> of <tt>Types</tt>
0189: */
0190: public Collection interfaces(final Type type) {
0191: final TypeNode node = getImplementsNode(type);
0192:
0193: if (node != null) {
0194: final List list = new ArrayList(implements Graph.succs(node));
0195:
0196: final ListIterator iter = list.listIterator();
0197:
0198: while (iter.hasNext()) {
0199: final TypeNode v = (TypeNode) iter.next();
0200: iter.set(v.type);
0201: }
0202:
0203: return list;
0204: }
0205:
0206: return new ArrayList();
0207: }
0208:
0209: /**
0210: * Returns the classes (<tt>Type</tt>s) that implement a given interface
0211: * as a <tt>Collection</tt> of <Tt>Type</tt>s.
0212: *
0213: * <p>
0214: *
0215: * See note in <tt>subclasses</tt> for information about the interface
0216: * hierarchy.
0217: */
0218: public Collection implementors(final Type type) {
0219: final TypeNode node = getImplementsNode(type);
0220:
0221: if (node != null) {
0222: final List list = new ArrayList(implements Graph.preds(node));
0223:
0224: final ListIterator iter = list.listIterator();
0225:
0226: while (iter.hasNext()) {
0227: final TypeNode v = (TypeNode) iter.next();
0228: iter.set(v.type);
0229: }
0230:
0231: return list;
0232: }
0233:
0234: return new ArrayList();
0235: }
0236:
0237: /**
0238: * Returns whether or not a is a subclass of b.
0239: */
0240: public boolean subclassOf(final Type a, final Type b) {
0241: // Is a <= b?
0242: Assert.isTrue(a.isReference() && b.isReference(),
0243: "Cannot compare " + a + " and " + b);
0244:
0245: // a <= a: true
0246: if (a.equals(b)) {
0247: return true;
0248: }
0249:
0250: // a <= java.lang.Object: true
0251: if (b.equals(Type.OBJECT)) {
0252: return true;
0253: }
0254:
0255: // null <= null: true
0256: // a <= null: false
0257: if (b.isNull()) {
0258: return a.isNull();
0259: }
0260:
0261: if (a.isArray()) {
0262: if (b.isArray()) {
0263: // Both reference arrays.
0264: // a <= b -> a[] <= b[]
0265: if (a.elementType().isReference()
0266: && b.elementType().isReference()) {
0267:
0268: return subclassOf(a.elementType(), b.elementType());
0269: }
0270:
0271: // a[] <= a[]: true
0272: return a.elementType().equals(b.elementType());
0273: }
0274:
0275: // Only one is an array (and b is not Object--tested above).
0276: return false;
0277: }
0278:
0279: // a <= b[]: false
0280: if (b.isArray()) {
0281: // Only one is an array.
0282: return false;
0283: }
0284:
0285: // Neither is an array. Look at all of the superclasses of a. If
0286: // one of those superclasses is b, then a is a subclass of b.
0287: for (Type t = a; t != null; t = super class(t)) {
0288: if (t.equals(b)) {
0289: return true;
0290: }
0291: }
0292:
0293: return false;
0294: }
0295:
0296: /**
0297: * Returns (the <tt>Type</tt>s of) all of the classes and interfaces in
0298: * the hierarchy.
0299: */
0300: public Collection classes() {
0301: Assert.isTrue(classes != null);
0302: return classes;
0303: }
0304:
0305: /**
0306: * Returns <tt>true</tt> if class closure has been computed
0307: */
0308: public boolean closure() {
0309: return (this .closure);
0310: }
0311:
0312: /**
0313: * Obtains a node from the extends graph. If it is not in the graph, we try
0314: * to "bring it in".
0315: */
0316: private TypeNode getExtendsNode(final Type type) {
0317: final GraphNode node = extendsGraph.getNode(type);
0318:
0319: if ((node == null) && type.isObject()) {
0320: this .addClassNamed(type.className());
0321: }
0322:
0323: return ((TypeNode) extendsGraph.getNode(type));
0324: }
0325:
0326: /**
0327: * Obtains a node from the class graph. If it is not in the graph, we try to
0328: * "bring it in".
0329: */
0330: private TypeNode getImplementsNode(final Type type) {
0331: final GraphNode node = implements Graph.getNode(type);
0332:
0333: if ((node == null) && type.isObject()) {
0334: this .addClassNamed(type.className());
0335: }
0336:
0337: return ((TypeNode) implements Graph.getNode(type));
0338: }
0339:
0340: /**
0341: * Adds a type (and all types it references) to the extends and implements
0342: * graphs.
0343: */
0344: private void addClass(final String name) {
0345: Type type = Type.getType(Type.classDescriptor(name));
0346:
0347: if (classes.contains(type)) {
0348: return;
0349: }
0350:
0351: if (inWorklist.contains(type)) {
0352: return;
0353: }
0354:
0355: db("ClassHierarchy: Adding " + name + " to hierarchy");
0356:
0357: worklist.add(type);
0358: inWorklist.add(type);
0359:
0360: while (!worklist.isEmpty()) {
0361: type = (Type) worklist.removeFirst();
0362: inWorklist.remove(type);
0363:
0364: if (classes.contains(type)) {
0365: continue;
0366: }
0367:
0368: classes.add(type);
0369:
0370: // Add a node in the extends graph for the type of interest
0371: TypeNode extendsNode = getExtendsNode(type);
0372:
0373: if (extendsNode == null) {
0374: // Add a new node to the class graph
0375: extendsNode = new TypeNode(type);
0376: extendsGraph.addNode(type, extendsNode);
0377: }
0378:
0379: // TypeNode implementsNode = (TypeNode) getImplementsNode(type);
0380:
0381: // if (implementsNode == null) {
0382: // // Add a new node to the interface graph
0383: // implementsNode = new TypeNode(type);
0384: // implementsGraph.addNode(type, implementsNode);
0385: // }
0386:
0387: // Obtain a ClassEditor for the class
0388: ClassEditor c;
0389:
0390: try {
0391: c = context.editClass(type.className());
0392:
0393: } catch (final ClassNotFoundException ex) {
0394: if (ClassHierarchy.RELAX) {
0395: continue;
0396: }
0397:
0398: throw new RuntimeException("Class not found: "
0399: + ex.getMessage());
0400: }
0401:
0402: final Type[] interfaces = c.interfaces();
0403:
0404: if (c.super class() != null) {
0405: // Add an edge from the superclass to the class in the extends
0406: // graph.
0407:
0408: if (!c.isInterface() || (interfaces.length == 0)) {
0409: // Ignore interfaces that implement (really extend, see
0410: // below) other interfaces. This way interfaces are put in
0411: // the extends graph twice.
0412:
0413: TypeNode super Node = getExtendsNode(c.super class());
0414:
0415: if (super Node == null) {
0416: super Node = new TypeNode(c.super class());
0417: extendsGraph.addNode(c.super class(), super Node);
0418: }
0419:
0420: // Make sure that we're not making java.lang.Object a
0421: // superclass of itself. We assume that the java.lang.Object
0422: // has no successors in the extendsGraph.
0423: if (!extendsNode.type.equals(Type.OBJECT)) {
0424: extendsGraph.addEdge(extendsNode, super Node);
0425: }
0426: }
0427:
0428: } else {
0429: // Only java.lang.Object has no superclass
0430: if (!type.equals(Type.OBJECT) && !ClassHierarchy.RELAX) {
0431: throw new RuntimeException("Null superclass for "
0432: + type);
0433: }
0434: }
0435:
0436: // Consider the interfaces c implements
0437: if (c.isInterface()) {
0438: // Interfaces that extend other interfaces are compiled into
0439: // classes that implement those other interfaces. So,
0440: // interfaces that implement other interfaces really extend
0441: // them. Yes, this makes the extends graph an inverted tree.
0442: for (int i = 0; i < interfaces.length; i++) {
0443: final Type iType = interfaces[i];
0444: TypeNode iNode = getExtendsNode(iType);
0445: if (iNode == null) {
0446: iNode = new TypeNode(iType);
0447: extendsGraph.addNode(iType, iNode);
0448: }
0449: extendsGraph.addEdge(extendsNode, iNode);
0450: }
0451:
0452: } else {
0453: // Class c implements its interfaces
0454: TypeNode implements Node = null;
0455: if (interfaces.length > 0) {
0456: implements Node = getImplementsNode(type);
0457: if (implements Node == null) {
0458: implements Node = new TypeNode(type);
0459: implements Graph.addNode(type, implements Node);
0460: }
0461: }
0462: for (int i = 0; i < interfaces.length; i++) {
0463: final Type iType = interfaces[i];
0464: TypeNode iNode = getImplementsNode(iType);
0465: if (iNode == null) {
0466: iNode = new TypeNode(iType);
0467: implements Graph.addNode(iType, iNode);
0468: }
0469: implements Graph.addEdge(implements Node, iNode);
0470: }
0471: }
0472:
0473: if (c.super class() != null) {
0474: // Add the super type to the worklist
0475:
0476: // db("typeref " + type + " -> " + c.superclass());
0477:
0478: addType(c.super class());
0479: }
0480:
0481: for (int i = 0; i < c.interfaces().length; i++) {
0482: // Add all of the interface types to the worklist
0483:
0484: // db("typeref " + type + " -> " + c.interfaces()[i]);
0485:
0486: addType(c.interfaces()[i]);
0487: }
0488:
0489: if (!this .closure) {
0490: context.release(c.classInfo());
0491: continue;
0492: }
0493:
0494: for (int i = 0; i < c.methods().length; i++) {
0495: // TODO: Add an enumeration to ClassEditor to get this list.
0496:
0497: // Add all of the methods types. Actually, we only add the
0498: // type involved with the methods.
0499: final MethodInfo m = c.methods()[i];
0500: final int typeIndex = m.typeIndex();
0501:
0502: final String desc = (String) c.constants().constantAt(
0503: typeIndex);
0504: final Type t = Type.getType(desc);
0505:
0506: // db("typeref " + type + " -> " + t);
0507:
0508: addType(t);
0509: }
0510:
0511: for (int i = 0; i < c.fields().length; i++) {
0512: // Add the types of all of the fields
0513:
0514: final FieldInfo f = c.fields()[i];
0515: final int typeIndex = f.typeIndex();
0516:
0517: final String desc = (String) c.constants().constantAt(
0518: typeIndex);
0519: final Type t = Type.getType(desc);
0520:
0521: // db("typeref " + type + " -> " + t);
0522:
0523: addType(t);
0524: }
0525:
0526: for (int i = 0; i < c.constants().numConstants(); i++) {
0527: // Look through the constant pool for interesting (non-LONG
0528: // and non-DOUBLE) constants and add them to the worklist.
0529:
0530: final int tag = c.constants().constantTag(i);
0531:
0532: if ((tag == Constant.LONG) || (tag == Constant.DOUBLE)) {
0533: i++;
0534:
0535: } else if (tag == Constant.CLASS) {
0536: final Type t = (Type) c.constants().constantAt(i);
0537:
0538: // db("typeref " + type + " -> " + t);
0539:
0540: addType(t);
0541:
0542: } else if (tag == Constant.NAME_AND_TYPE) {
0543: final NameAndType t = (NameAndType) c.constants()
0544: .constantAt(i);
0545:
0546: // db("typeref " + type + " -> " + t.type());
0547:
0548: addType(t.type());
0549: }
0550: }
0551:
0552: // We're done editing the class
0553: context.release(c.classInfo());
0554:
0555: }
0556:
0557: /*
0558: * // Now that we've entered the class (and at least all of its //
0559: * subclasses) into the hierarchy, notify superclasses that // they've
0560: * been subclassses. This will invalidate the TypeNodes // in the
0561: * dependence graph. DependenceGraph dg =
0562: * BloatContext.getContext().dependenceGraph();
0563: *
0564: * for(Type superclass = superclass(type); superclass != null;
0565: * superclass = superclass(superclass)) { db("ClassHierarchy:
0566: * Invalidating superclass " + superclass);
0567: *
0568: * EDU.purdue.cs.bloat.depend.TypeNode typeNode =
0569: * dg.getTypeNode(superclass); typeNode.invalidate(); }
0570: */
0571: }
0572:
0573: // Adds a Type to the worklist. If the type is a method, then all
0574: // of the parameters types and the return types are added.
0575: private void addType(final Type type) {
0576: if (type.isMethod()) {
0577: // Add all of the types of the parameters and the return type
0578:
0579: final Type[] paramTypes = type.paramTypes();
0580:
0581: for (int i = 0; i < paramTypes.length; i++) {
0582: // db("typeref " + type + " -> " + paramTypes[i]);
0583:
0584: addType(paramTypes[i]);
0585: }
0586:
0587: final Type returnType = type.returnType();
0588:
0589: // db("typeref " + type + " -> " + returnType);
0590:
0591: addType(returnType);
0592:
0593: return;
0594: }
0595:
0596: if (type.isArray()) {
0597: // TODO: Add the supertypes of the array and make it implement
0598: // SERIALIZABLE and CLONEABLE. Since we're only concerned with
0599: // fields and since arrays have no fields, we can ignore this
0600: // for now.
0601:
0602: // db("typeref " + type + " -> " + type.elementType());
0603:
0604: addType(type.elementType());
0605:
0606: return;
0607: }
0608:
0609: if (!type.isObject()) {
0610: return;
0611: }
0612:
0613: if (classes.contains(type)) {
0614: return;
0615: }
0616:
0617: if (inWorklist.contains(type)) {
0618: return;
0619: }
0620:
0621: worklist.add(type);
0622: inWorklist.add(type);
0623: }
0624:
0625: /**
0626: * Returns the intersection of two types. Basically, the interstion of two
0627: * types is the type (if any) to which both types may be assigned. So, if a
0628: * is a subtype of b, a is returned. Otherwise, <tt>Type.NULL</tt> is
0629: * returned.
0630: */
0631: public Type intersectType(final Type a, final Type b) {
0632: Assert.isTrue(a.isReference() && b.isReference(),
0633: "Cannot intersect " + a + " and " + b);
0634:
0635: if (a.equals(b)) {
0636: return a;
0637: }
0638:
0639: if (a.isNull() || b.isNull()) {
0640: return Type.NULL;
0641: }
0642:
0643: if (a.equals(Type.OBJECT)) {
0644: return b;
0645: }
0646:
0647: if (b.equals(Type.OBJECT)) {
0648: return a;
0649: }
0650:
0651: if (a.isArray()) {
0652: if (b.isArray()) {
0653: // Both reference arrays.
0654: if (a.elementType().isReference()
0655: && b.elementType().isReference()) {
0656:
0657: final Type t = intersectType(a.elementType(), b
0658: .elementType());
0659:
0660: if (t.isNull()) {
0661: return Type.NULL;
0662: }
0663:
0664: return t.arrayType();
0665: }
0666:
0667: // Only one is a reference array.
0668: if (a.elementType().isReference()
0669: || b.elementType().isReference()) {
0670: return Type.NULL;
0671: }
0672:
0673: // Both primitive arrays, not equal.
0674: return Type.NULL;
0675: }
0676:
0677: // Only one is an array.
0678: return Type.NULL;
0679: }
0680:
0681: if (b.isArray()) {
0682: // Only one is an array.
0683: return Type.NULL;
0684: }
0685:
0686: // Neither is an array.
0687:
0688: for (Type t = a; t != null; t = super class(t)) {
0689: if (t.equals(b)) {
0690: // If a is a subtype of b, then return a.
0691: return a;
0692: }
0693: }
0694:
0695: for (Type t = b; t != null; t = super class(t)) {
0696: if (t.equals(a)) {
0697: // If b is a subtype of a, then return b
0698: return b;
0699: }
0700: }
0701:
0702: return Type.NULL;
0703: }
0704:
0705: /**
0706: * Returns the most refined common supertype for a bunch of <tt>Type</tt>s.
0707: */
0708: public Type unionTypes(final Collection types) {
0709: if (types.size() <= 0) {
0710: return (Type.OBJECT);
0711: }
0712:
0713: final Iterator ts = types.iterator();
0714: Type type = (Type) ts.next();
0715:
0716: while (ts.hasNext()) {
0717: type = this .unionType(type, (Type) ts.next());
0718: }
0719:
0720: return (type);
0721: }
0722:
0723: /**
0724: * Returns the union of two types. The union of two types is their most
0725: * refined common supertype. At worst, the union is <tt>Type.OBJECT</tt>
0726: */
0727: public Type unionType(final Type a, final Type b) {
0728:
0729: if (a.equals(b)) {
0730: return a;
0731: }
0732:
0733: if (a.equals(Type.OBJECT) || b.equals(Type.OBJECT)) {
0734: return Type.OBJECT;
0735: }
0736:
0737: if (a.isNull()) {
0738: return b;
0739: }
0740:
0741: if (b.isNull()) {
0742: return a;
0743: }
0744:
0745: // Handle funky integral types introduced during type inferencing.
0746: if ((a.isIntegral() || a.equals(ClassHierarchy.POS_BYTE) || a
0747: .equals(ClassHierarchy.POS_SHORT))
0748: && (b.isIntegral() || b.equals(ClassHierarchy.POS_BYTE) || b
0749: .equals(ClassHierarchy.POS_SHORT))) {
0750:
0751: final BitSet v1 = ClassHierarchy.typeToSet(a);
0752: final BitSet v2 = ClassHierarchy.typeToSet(b);
0753: v1.or(v2);
0754: return (ClassHierarchy.setToType(v1));
0755: }
0756:
0757: Assert.isTrue(a.isReference() && b.isReference(),
0758: "Cannot union " + a + " and " + b);
0759:
0760: if (a.isArray()) {
0761: if (b.isArray()) {
0762: // Both reference arrays.
0763: if (a.elementType().isReference()
0764: && b.elementType().isReference()) {
0765:
0766: final Type t = unionType(a.elementType(), b
0767: .elementType());
0768: return t.arrayType();
0769: }
0770:
0771: // Only one is a reference array.
0772: if (a.elementType().isReference()
0773: || b.elementType().isReference()) {
0774: return Type.OBJECT;
0775: }
0776:
0777: // Both primitive arrays, not equal.
0778: return Type.OBJECT;
0779: }
0780:
0781: // Only one is an array.
0782: return Type.OBJECT;
0783: }
0784:
0785: if (b.isArray()) {
0786: // Only one is an array.
0787: return Type.OBJECT;
0788: }
0789:
0790: // Neither is an array.
0791: final Set super OfA = new HashSet();
0792: final Set super OfB = new HashSet();
0793:
0794: for (Type t = a; t != null; t = super class(t)) {
0795: // if(TypeInference.DEBUG)
0796: // System.out.println(" Superclass of " + a + " is " + t);
0797: super OfA.add(t);
0798: }
0799:
0800: for (Type t = b; t != null; t = super class(t)) {
0801: if (super OfA.contains(t)) {
0802: return t;
0803: }
0804:
0805: // if(TypeInference.DEBUG)
0806: // System.out.println(" Superclass of " + b + " is " + t);
0807:
0808: super OfB.add(t);
0809: }
0810:
0811: // if(TypeInference.DEBUG) {
0812: // System.out.println("Superclasses of A: " + superOfA);
0813: // System.out.println("Superclasses of B: " + superOfB);
0814: // }
0815:
0816: for (Type t = a; t != null; t = super class(t)) {
0817: if (super OfB.contains(t)) {
0818: // Found a common superclass...
0819: return t;
0820: }
0821: }
0822:
0823: throw new RuntimeException("No common super type for " + a
0824: + " (" + super OfA + ")" + " and " + b + " (" + super OfB
0825: + ")");
0826: }
0827:
0828: class TypeNode extends GraphNode {
0829: Type type;
0830:
0831: public TypeNode(final Type type) {
0832: // if(DEBUG)
0833: // System.out.println("Creating TypeNode for: " + type);
0834: this .type = type;
0835: }
0836:
0837: public String toString() {
0838: return ("[" + type + "]");
0839: }
0840: }
0841:
0842: /**
0843: * Prints the class hierarchy (i.e. the "extends" hierarchy, interfaces may
0844: * extends other interfaces) to a <tt>PrintWriter</tt>.
0845: */
0846: public void printClasses(final PrintWriter out, final int indent) {
0847: final TypeNode objectNode = this .getExtendsNode(Type.OBJECT);
0848: indent(out, indent);
0849: out.println(objectNode.type);
0850: printSubclasses(objectNode.type, out, true, indent + 2);
0851: }
0852:
0853: /**
0854: * Prints the implements hierarchy to a <tt>PrintWriter</tt>.
0855: */
0856: public void printImplements(final PrintWriter out, int indent) {
0857: // There are multiple roots to the implements graph.
0858: indent += 2;
0859: final Iterator roots = this .implements Graph.roots().iterator();
0860: while (roots.hasNext()) {
0861: final TypeNode iNode = (TypeNode) roots.next();
0862: indent(out, indent);
0863: out.println(iNode.type);
0864: printImplementors(iNode.type, out, true, indent + 2);
0865: }
0866: }
0867:
0868: /**
0869: * Print the implementors of a given interface. Do we even have more than
0870: * one level?
0871: */
0872: private void printImplementors(final Type iType,
0873: final PrintWriter out, final boolean recurse,
0874: final int indent) {
0875: final Iterator implementors = this .implementors(iType)
0876: .iterator();
0877: while (implementors.hasNext()) {
0878: final Type implementor = (Type) implementors.next();
0879: indent(out, indent);
0880: out.println(implementor);
0881: if (recurse) {
0882: printImplementors(implementor, out, recurse, indent + 2);
0883: }
0884: }
0885: }
0886:
0887: /**
0888: * Prints a bunch of spaces to a PrintWriter.
0889: */
0890: private void indent(final PrintWriter out, final int indent) {
0891: for (int i = 0; i < indent; i++) {
0892: out.print(" ");
0893: }
0894: }
0895:
0896: /**
0897: * Prints the subclasses of a given to a PrintWriter.
0898: *
0899: * @param recurse
0900: * Are all subclasses printed or only direct ones?
0901: */
0902: private void printSubclasses(final Type classType,
0903: final PrintWriter out, final boolean recurse,
0904: final int indent) {
0905: final Iterator iter = this .subclasses(classType).iterator();
0906: while (iter.hasNext()) {
0907: final Type subclass = (Type) iter.next();
0908: indent(out, indent);
0909: out.println(subclass);
0910: if (recurse) {
0911: printSubclasses(subclass, out, recurse, indent + 2);
0912: }
0913:
0914: }
0915: }
0916:
0917: /**
0918: * Determines whether or not a class's method is overriden by any of its
0919: * subclasses.
0920: */
0921: public boolean methodIsOverridden(final Type classType,
0922: final NameAndType nat) {
0923: final String methodName = nat.name();
0924: final Type methodType = nat.type();
0925:
0926: db("ClassHierarchy: Is " + classType + "." + methodName
0927: + methodType + " overridden?");
0928:
0929: final Collection subclasses = this .subclasses(classType);
0930:
0931: final Iterator iter = subclasses.iterator();
0932: while (iter.hasNext()) {
0933: final Type subclass = (Type) iter.next();
0934:
0935: db("Examining subclass " + subclass);
0936:
0937: // Obtain a ClassEditor for the class
0938: ClassEditor ce = null;
0939:
0940: try {
0941: ce = context.editClass(subclass.className());
0942:
0943: } catch (final ClassNotFoundException ex) {
0944: db(ex.getMessage());
0945: return (true);
0946: }
0947:
0948: // Examine each method in the subclass
0949: final MethodInfo[] methods = ce.methods();
0950: for (int i = 0; i < methods.length; i++) {
0951: final MethodEditor me = context.editMethod(methods[i]);
0952: if (me.name().equals(methodName)
0953: && me.type().equals(methodType)) {
0954: db(" " + methodName + methodType
0955: + " is overridden by " + me.name()
0956: + me.type());
0957: context.release(ce.classInfo());
0958: return (true); // Method is overridden
0959: }
0960: }
0961:
0962: // Recurse over subclasses
0963: if (methodIsOverridden(subclass, nat)) {
0964: context.release(ce.classInfo());
0965: return (true);
0966: }
0967:
0968: context.release(ce.classInfo());
0969: }
0970:
0971: // Got through all subclasses and method was not overridden
0972: db(" NO!");
0973:
0974: return (false);
0975: }
0976:
0977: /**
0978: * Returns the <tt>MemberRef</tt> of the method that would be invoked if a
0979: * given method of a given type was invoked. Basically, dynamic dispatch is
0980: * simulated.
0981: */
0982: public MemberRef methodInvoked(final Type receiver,
0983: final NameAndType method) {
0984: // Search up class hierarchy for a class that implements the
0985: // method
0986: for (Type type = receiver; type != null; type = super class(type)) {
0987: // Construct a MemberRef for the possible method
0988: final MemberRef m = new MemberRef(type, method);
0989: try {
0990: context.editMethod(m);
0991: return (m);
0992:
0993: } catch (final NoSuchMethodException ex) {
0994: continue; // Try superclass
0995: }
0996: }
0997:
0998: // Hmm. No superclass method was found!
0999: throw new IllegalArgumentException("No implementation of "
1000: + receiver + "." + method);
1001: }
1002:
1003: /**
1004: * Given a set of bits representing the range of values some type has,
1005: * determines what that Type is.
1006: */
1007: public static Type setToType(final BitSet v) {
1008: if (v.get(ClassHierarchy.MAX_INT)) {
1009: return Type.INTEGER;
1010: }
1011:
1012: if (v.get(ClassHierarchy.MAX_CHAR)) {
1013: if (v.get(ClassHierarchy.MIN_INT)
1014: || v.get(ClassHierarchy.MIN_SHORT)
1015: || v.get(ClassHierarchy.MIN_BYTE)) {
1016: return Type.INTEGER;
1017:
1018: } else {
1019: return Type.CHARACTER;
1020: }
1021: }
1022:
1023: if (v.get(ClassHierarchy.MAX_SHORT)) {
1024: if (v.get(ClassHierarchy.MIN_INT)) {
1025: return Type.INTEGER;
1026:
1027: } else if (v.get(ClassHierarchy.MIN_SHORT)
1028: || v.get(ClassHierarchy.MIN_BYTE)) {
1029: return Type.SHORT;
1030:
1031: } else {
1032: return ClassHierarchy.POS_SHORT;
1033: }
1034: }
1035:
1036: if (v.get(ClassHierarchy.MAX_BYTE)) {
1037: if (v.get(ClassHierarchy.MIN_INT)) {
1038: return Type.INTEGER;
1039:
1040: } else if (v.get(ClassHierarchy.MIN_SHORT)) {
1041: return Type.SHORT;
1042:
1043: } else if (v.get(ClassHierarchy.MIN_BYTE)) {
1044: return Type.BYTE;
1045:
1046: } else {
1047: return ClassHierarchy.POS_BYTE;
1048: }
1049: }
1050:
1051: if (v.get(ClassHierarchy.MAX_BOOL)) {
1052: if (v.get(ClassHierarchy.MIN_INT)) {
1053: return Type.INTEGER;
1054:
1055: } else if (v.get(ClassHierarchy.MIN_SHORT)) {
1056: return Type.SHORT;
1057:
1058: } else if (v.get(ClassHierarchy.MIN_BYTE)) {
1059: return Type.BYTE;
1060:
1061: } else {
1062: return Type.BOOLEAN;
1063: }
1064: }
1065:
1066: if (v.get(ClassHierarchy.MIN_INT)) {
1067: return Type.INTEGER;
1068: }
1069:
1070: if (v.get(ClassHierarchy.MIN_SHORT)) {
1071: return Type.SHORT;
1072: }
1073:
1074: if (v.get(ClassHierarchy.MIN_BYTE)) {
1075: return Type.BYTE;
1076: }
1077:
1078: return Type.BOOLEAN;
1079: }
1080:
1081: /**
1082: * Returns a BitSet representing the possible values of a given integral
1083: * type.
1084: */
1085: public static BitSet typeToSet(final Type type) {
1086: final BitSet v = new BitSet(ClassHierarchy.MAX_INT);
1087: int lo;
1088: int hi;
1089:
1090: if (type.equals(Type.INTEGER)) {
1091: lo = ClassHierarchy.MIN_INT;
1092: hi = ClassHierarchy.MAX_INT;
1093:
1094: } else if (type.equals(Type.CHARACTER)) {
1095: lo = ClassHierarchy.MIN_CHAR;
1096: hi = ClassHierarchy.MAX_CHAR;
1097:
1098: } else if (type.equals(Type.SHORT)) {
1099: lo = ClassHierarchy.MIN_SHORT;
1100: hi = ClassHierarchy.MAX_SHORT;
1101:
1102: } else if (type.equals(ClassHierarchy.POS_SHORT)) {
1103: lo = ClassHierarchy.ZERO;
1104: hi = ClassHierarchy.MAX_SHORT;
1105:
1106: } else if (type.equals(Type.BYTE)) {
1107: lo = ClassHierarchy.MIN_BYTE;
1108: hi = ClassHierarchy.MAX_BYTE;
1109:
1110: } else if (type.equals(ClassHierarchy.POS_BYTE)) {
1111: lo = ClassHierarchy.ZERO;
1112: hi = ClassHierarchy.MAX_BYTE;
1113:
1114: } else if (type.equals(Type.BOOLEAN)) {
1115: lo = ClassHierarchy.ZERO;
1116: hi = ClassHierarchy.MAX_BOOL;
1117:
1118: } else {
1119: throw new RuntimeException();
1120: }
1121:
1122: for (int i = lo; i <= hi; i++) {
1123: v.set(i);
1124: }
1125:
1126: return v;
1127: }
1128:
1129: /**
1130: * Represents a method and a set of <tt>Type</tt>s. When the method is
1131: * invoked on a receiver of any of these types, the method will resolve to
1132: * that method.
1133: */
1134: public class ResolvesToWith {
1135: /**
1136: * The method to which a call resolves
1137: */
1138: public MemberRef method;
1139:
1140: /**
1141: * The types with which the call resolves to the above method
1142: */
1143: public HashSet rTypes;
1144: }
1145:
1146: /**
1147: * Returns a set of <tt>ResolvesToWith</tt> that represent all subclass
1148: * methods that override a given method and the subclasses that when used as
1149: * receivers resolve to that method.
1150: *
1151: * @see ResolvesToWith
1152: */
1153: public Set resolvesToWith(final MemberRef method) {
1154: Set resolvesTo = (Set) this .resolvesToCache.get(method);
1155:
1156: if (resolvesTo == null) {
1157: db("Resolving " + method);
1158:
1159: resolvesTo = new HashSet(); // All methods it could resolve to
1160: final ResolvesToWith rtw = new ResolvesToWith();
1161: rtw.method = method;
1162: rtw.rTypes = new HashSet();
1163:
1164: // Remember that the method may be abstract, so the declaring
1165: // class is not necessarily a resolving type.
1166:
1167: // Basically, we go down the class and/or interface hierarchies
1168: // looking for concrete implementations of this method.
1169: MethodEditor me = null;
1170: try {
1171: me = context.editMethod(method);
1172:
1173: } catch (final NoSuchMethodException ex1) {
1174: // A method may not necessarily be implemented by its
1175: // declaring class. For instance, an abstract class that
1176: // implements an interface need not implement every method of
1177: // the interface. Really?
1178: db(" Hmm. Method is not implemented in declaring class");
1179: }
1180:
1181: // If the method is static or is a constructor, then it can only
1182: // resolve to itself.
1183: if ((me != null) && (me.isStatic() || me.isConstructor())) {
1184: rtw.rTypes.add(method.declaringClass());
1185: resolvesTo.add(rtw);
1186: db(" Static method or constructor, resolves to itself");
1187:
1188: } else {
1189: // Now let's play with types. Examine every type that could
1190: // implement this method. If it does, add it to the resolvesTo
1191: // set. Make sure to take things like interfaces into account.
1192: // When we find a overriding method, make a recursive call so
1193: // we'll have that information in the cache.
1194: final List types = new LinkedList();
1195: types.add(method.declaringClass());
1196: while (!types.isEmpty()) {
1197: final Type type = (Type) types.remove(0);
1198:
1199: db(" Examining type " + type);
1200:
1201: ClassEditor ce = null;
1202: try {
1203: ce = context.editClass(type);
1204:
1205: } catch (final ClassNotFoundException ex1) {
1206: System.err.println("** Class not found: "
1207: + ex1.getMessage());
1208: ex1.printStackTrace(System.err);
1209: System.exit(1);
1210: }
1211:
1212: if (ce.isInterface()) {
1213: // Consider all subinterfaces of this interface and all
1214: // classes that implement this interface.
1215: final Iterator subinterfaces = this .subclasses(
1216: type).iterator();
1217: while (subinterfaces.hasNext()) {
1218: final Type subinterface = (Type) subinterfaces
1219: .next();
1220: types.add(subinterface);
1221: db(" Noting subinterface " + subinterface);
1222: }
1223:
1224: final Iterator implementors = this
1225: .implementors(type).iterator();
1226: while (implementors.hasNext()) {
1227: final Type implementor = (Type) implementors
1228: .next();
1229: types.add(implementor);
1230: db(" Noting implementor " + implementor);
1231: }
1232:
1233: } else {
1234: // We've got a class. Does it override the method?
1235: final NameAndType nat = method.nameAndType();
1236: final MethodInfo[] methods = ce.methods();
1237: boolean overridden = false;
1238: for (int i = 0; i < methods.length; i++) {
1239: final MethodEditor over = context
1240: .editMethod(methods[i]);
1241: final MemberRef ref = over.memberRef();
1242: if (ref.nameAndType().equals(nat)) {
1243: // This class implements the method.
1244: if (!method.declaringClass().equals(
1245: type)) {
1246: // Make a recursive call.
1247: db(" Class " + type
1248: + " overrides " + method);
1249: resolvesTo
1250: .addAll(resolvesToWith(ref));
1251: overridden = true;
1252: }
1253: }
1254: }
1255:
1256: if (!overridden) {
1257: db(" " + rtw.method + " called with "
1258: + type);
1259: rtw.rTypes.add(type);
1260: resolvesTo.add(rtw);
1261:
1262: // Examine all subclasses of this class. They may
1263: // override
1264: // the method also.
1265: final Iterator subclasses = this
1266: .subclasses(type).iterator();
1267: while (subclasses.hasNext()) {
1268: final Type subclass = (Type) subclasses
1269: .next();
1270: types.add(subclass);
1271: db(" Noting subclass " + subclass);
1272: }
1273: }
1274: }
1275: }
1276: }
1277:
1278: resolvesToCache.put(method, resolvesTo);
1279: }
1280:
1281: return (resolvesTo);
1282: }
1283: }
|