0001: /*
0002: * FindBugs - Find Bugs in Java programs
0003: * Copyright (C) 2003-2007 University of Maryland
0004: *
0005: * This library is free software; you can redistribute it and/or
0006: * modify it under the terms of the GNU Lesser General Public
0007: * License as published by the Free Software Foundation; either
0008: * version 2.1 of the License, or (at your option) any later version.
0009: *
0010: * This library is distributed in the hope that it will be useful,
0011: * but WITHOUT ANY WARRANTY; without even the implied warranty of
0012: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
0013: * Lesser General Public License for more details.
0014: *
0015: * You should have received a copy of the GNU Lesser General Public
0016: * License along with this library; if not, write to the Free Software
0017: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
0018: */
0019:
0020: package edu.umd.cs.findbugs.ba.ch;
0021:
0022: import java.util.ArrayList;
0023: import java.util.Collection;
0024: import java.util.Collections;
0025: import java.util.HashMap;
0026: import java.util.HashSet;
0027: import java.util.Iterator;
0028: import java.util.LinkedList;
0029: import java.util.Map;
0030: import java.util.Set;
0031:
0032: import org.apache.bcel.classfile.JavaClass;
0033: import org.apache.bcel.generic.ArrayType;
0034: import org.apache.bcel.generic.BasicType;
0035: import org.apache.bcel.generic.ObjectType;
0036: import org.apache.bcel.generic.ReferenceType;
0037: import org.apache.bcel.generic.Type;
0038:
0039: import edu.umd.cs.findbugs.SystemProperties;
0040: import edu.umd.cs.findbugs.annotations.CheckForNull;
0041: import edu.umd.cs.findbugs.annotations.DefaultAnnotationForParameters;
0042: import edu.umd.cs.findbugs.annotations.NonNull;
0043: import edu.umd.cs.findbugs.ba.AnalysisContext;
0044: import edu.umd.cs.findbugs.ba.ObjectTypeFactory;
0045: import edu.umd.cs.findbugs.ba.XClass;
0046: import edu.umd.cs.findbugs.bcel.BCELUtil;
0047: import edu.umd.cs.findbugs.classfile.ClassDescriptor;
0048: import edu.umd.cs.findbugs.classfile.DescriptorFactory;
0049: import edu.umd.cs.findbugs.internalAnnotations.DottedClassName;
0050: import edu.umd.cs.findbugs.util.DualKeyHashMap;
0051: import edu.umd.cs.findbugs.util.MapCache;
0052:
0053: /**
0054: * Class for performing class hierarchy queries.
0055: * Does <em>not</em> require JavaClass objects to be in memory.
0056: * Instead, uses XClass objects.
0057: *
0058: * @author David Hovemeyer
0059: */
0060: @javax.annotation.ParametersAreNonnullByDefault
0061: @DefaultAnnotationForParameters(NonNull.class)
0062: public class Subtypes2 {
0063: public static final boolean ENABLE_SUBTYPES2 = true;
0064: public static final boolean ENABLE_SUBTYPES2_FOR_COMMON_SUPERCLASS_QUERIES = true; //SystemProperties.getBoolean("findbugs.subtypes2.superclass");
0065: public static final boolean DEBUG = SystemProperties
0066: .getBoolean("findbugs.subtypes2.debug");
0067: public static final boolean DEBUG_QUERIES = SystemProperties
0068: .getBoolean("findbugs.subtypes2.debugqueries");
0069:
0070: private final InheritanceGraph graph;
0071: private final Map<ClassDescriptor, ClassVertex> classDescriptorToVertexMap;
0072: private final Map<ClassDescriptor, SupertypeQueryResults> super typeSetMap;
0073: private final Map<ClassDescriptor, Set<ClassDescriptor>> subtypeSetMap;
0074: private final Set<XClass> xclassSet;
0075: private final DualKeyHashMap<ReferenceType, ReferenceType, ReferenceType> firstCommonSuperclassQueryCache;
0076:
0077: private final ObjectType SERIALIZABLE;
0078: private final ObjectType CLONEABLE;
0079:
0080: /**
0081: * Object to record the results of a supertype search.
0082: */
0083: private static class SupertypeQueryResults {
0084: private Set<ClassDescriptor> super typeSet = new HashSet<ClassDescriptor>();
0085: private boolean encounteredMissingClasses = false;
0086:
0087: public void addSupertype(ClassDescriptor classDescriptor) {
0088: super typeSet.add(classDescriptor);
0089: }
0090:
0091: public void setEncounteredMissingClasses(
0092: boolean encounteredMissingClasses) {
0093: this .encounteredMissingClasses = encounteredMissingClasses;
0094: }
0095:
0096: public boolean containsType(
0097: ClassDescriptor possibleSupertypeClassDescriptor)
0098: throws ClassNotFoundException {
0099: if (super typeSet.contains(possibleSupertypeClassDescriptor)) {
0100: return true;
0101: } else if (!encounteredMissingClasses) {
0102: return false;
0103: } else {
0104: // We don't really know which class was missing.
0105: // However, any missing classes will already have been reported.
0106: throw new ClassNotFoundException();
0107: }
0108: }
0109: }
0110:
0111: /**
0112: * Constructor.
0113: */
0114: public Subtypes2() {
0115: this .graph = new InheritanceGraph();
0116: this .classDescriptorToVertexMap = new HashMap<ClassDescriptor, ClassVertex>();
0117: this .super typeSetMap = new MapCache<ClassDescriptor, SupertypeQueryResults>(
0118: 500);// XXX: use MapCache?
0119: this .subtypeSetMap = new MapCache<ClassDescriptor, Set<ClassDescriptor>>(
0120: 500);// XXX: use MapCache?
0121: this .xclassSet = new HashSet<XClass>();
0122: this .SERIALIZABLE = ObjectTypeFactory
0123: .getInstance("java.io.Serializable");
0124: this .CLONEABLE = ObjectTypeFactory
0125: .getInstance("java.lang.Cloneable");
0126: this .firstCommonSuperclassQueryCache = new DualKeyHashMap<ReferenceType, ReferenceType, ReferenceType>();
0127: }
0128:
0129: /**
0130: * @return Returns the graph.
0131: */
0132: public InheritanceGraph getGraph() {
0133: return graph;
0134: }
0135:
0136: public static boolean instanceOf(@DottedClassName
0137: String dottedSubtype, @DottedClassName
0138: String dottedSupertype) {
0139: Subtypes2 subtypes2 = AnalysisContext.currentAnalysisContext()
0140: .getSubtypes2();
0141: ClassDescriptor subDescriptor = DescriptorFactory
0142: .createClassDescriptorFromDottedClassName(dottedSubtype);
0143: ClassDescriptor super Descriptor = DescriptorFactory
0144: .createClassDescriptorFromDottedClassName(dottedSupertype);
0145: try {
0146: return subtypes2.isSubtype(subDescriptor, super Descriptor);
0147: } catch (ClassNotFoundException e) {
0148: AnalysisContext.reportMissingClass(e);
0149: return false;
0150: }
0151: }
0152:
0153: public static boolean instanceOf(JavaClass subtype,
0154: @DottedClassName
0155: String dottedSupertype) {
0156: Subtypes2 subtypes2 = AnalysisContext.currentAnalysisContext()
0157: .getSubtypes2();
0158: ClassDescriptor subDescriptor = DescriptorFactory
0159: .createClassDescriptor(subtype);
0160: ClassDescriptor super Descriptor = DescriptorFactory
0161: .createClassDescriptorFromDottedClassName(dottedSupertype);
0162: try {
0163: return subtypes2.isSubtype(subDescriptor, super Descriptor);
0164: } catch (ClassNotFoundException e) {
0165: AnalysisContext.reportMissingClass(e);
0166: return false;
0167: }
0168: }
0169:
0170: /**
0171: * Add an application class, and its transitive supertypes, to the inheritance graph.
0172: *
0173: * @param appXClass application XClass to add to the inheritance graph
0174: */
0175: public void addApplicationClass(XClass appXClass) {
0176: ClassVertex vertex = addClassAndGetClassVertex(appXClass);
0177: vertex.markAsApplicationClass();
0178:
0179: }
0180:
0181: public boolean isApplicationClass(ClassDescriptor descriptor) {
0182: assert descriptor != null;
0183: try {
0184: return resolveClassVertex(descriptor).isApplicationClass();
0185: } catch (ClassNotFoundException e) {
0186: AnalysisContext.reportMissingClass(e);
0187: return true;
0188: }
0189: }
0190:
0191: /**
0192: * Add a class or interface, and its transitive supertypes, to the inheritance graph.
0193: *
0194: * @param xclass XClass to add to the inheritance graph
0195: */
0196: public void addClass(XClass xclass) {
0197: addClassAndGetClassVertex(xclass);
0198: }
0199:
0200: /**
0201: * Add an XClass and all of its supertypes to
0202: * the InheritanceGraph.
0203: *
0204: * @param xclass an XClass
0205: * @return the ClassVertex representing the class in
0206: * the InheritanceGraph
0207: */
0208: private ClassVertex addClassAndGetClassVertex(XClass xclass) {
0209: if (xclass == null) {
0210: throw new IllegalStateException();
0211: }
0212:
0213: LinkedList<XClass> workList = new LinkedList<XClass>();
0214: workList.add(xclass);
0215:
0216: while (!workList.isEmpty()) {
0217: XClass work = workList.removeFirst();
0218: ClassVertex vertex = classDescriptorToVertexMap.get(work
0219: .getClassDescriptor());
0220: if (vertex != null && vertex.isFinished()) {
0221: // This class has already been processed.
0222: continue;
0223: }
0224:
0225: if (vertex == null) {
0226: vertex = ClassVertex.createResolvedClassVertex(work
0227: .getClassDescriptor(), work);
0228: addVertexToGraph(work.getClassDescriptor(), vertex);
0229: }
0230:
0231: addSupertypeEdges(vertex, workList);
0232:
0233: vertex.setFinished(true);
0234: }
0235:
0236: return classDescriptorToVertexMap.get(xclass
0237: .getClassDescriptor());
0238: }
0239:
0240: private void addVertexToGraph(ClassDescriptor classDescriptor,
0241: ClassVertex vertex) {
0242: assert classDescriptorToVertexMap.get(classDescriptor) == null;
0243:
0244: if (DEBUG) {
0245: System.out.println("Adding "
0246: + classDescriptor.toDottedClassName()
0247: + " to inheritance graph");
0248: }
0249:
0250: graph.addVertex(vertex);
0251: classDescriptorToVertexMap.put(classDescriptor, vertex);
0252:
0253: if (vertex.isResolved()) {
0254: xclassSet.add(vertex.getXClass());
0255: }
0256:
0257: if (vertex.isInterface()) {
0258: // There is no need to add additional worklist nodes because java/lang/Object has no supertypes.
0259: addInheritanceEdge(vertex, DescriptorFactory.instance()
0260: .getClassDescriptor("java/lang/Object"), false,
0261: null);
0262: }
0263: }
0264:
0265: /**
0266: * Determine whether or not a given ReferenceType is a subtype of another.
0267: * Throws ClassNotFoundException if the question cannot be answered
0268: * definitively due to a missing class.
0269: *
0270: * @param type a ReferenceType
0271: * @param possibleSupertype another Reference type
0272: * @return true if <code>type</code> is a subtype of <code>possibleSupertype</code>, false if not
0273: * @throws ClassNotFoundException if a missing class prevents a definitive answer
0274: */
0275: public boolean isSubtype(ReferenceType type,
0276: ReferenceType possibleSupertype)
0277: throws ClassNotFoundException {
0278:
0279: // Eliminate some easy cases
0280: if (type.equals(possibleSupertype)) {
0281: return true;
0282: }
0283: // others?
0284:
0285: boolean typeIsObjectType = (type instanceof ObjectType);
0286: boolean possibleSupertypeIsObjectType = (possibleSupertype instanceof ObjectType);
0287:
0288: if (typeIsObjectType && possibleSupertypeIsObjectType) {
0289: // Both types are ordinary object (non-array) types.
0290: return isSubtype((ObjectType) type,
0291: (ObjectType) possibleSupertype);
0292: }
0293:
0294: boolean typeIsArrayType = (type instanceof ArrayType);
0295: boolean possibleSupertypeIsArrayType = (possibleSupertype instanceof ArrayType);
0296:
0297: if (typeIsArrayType) {
0298: // Check superclass/interfaces
0299: if (possibleSupertype.equals(ObjectType.OBJECT)
0300: || possibleSupertype.equals(SERIALIZABLE)
0301: || possibleSupertype.equals(CLONEABLE)) {
0302: return true;
0303: }
0304:
0305: // We checked all of the possible class/interface supertypes,
0306: // so if possibleSupertype is not an array type,
0307: // then we can definitively say no
0308: if (!possibleSupertypeIsArrayType) {
0309: return false;
0310: }
0311:
0312: // Check array/array subtype relationship
0313:
0314: ArrayType typeAsArrayType = (ArrayType) type;
0315: ArrayType possibleSupertypeAsArrayType = (ArrayType) possibleSupertype;
0316:
0317: // Must have same number of dimensions
0318: if (typeAsArrayType.getDimensions() < possibleSupertypeAsArrayType
0319: .getDimensions()) {
0320: return false;
0321: }
0322: Type possibleSupertypeBasicType = possibleSupertypeAsArrayType
0323: .getBasicType();
0324: if (!(possibleSupertypeBasicType instanceof ObjectType)) {
0325: return false;
0326: }
0327: Type typeBasicType = typeAsArrayType.getBasicType();
0328:
0329: // If dimensions differ, see if element types are compatible.
0330: if (typeAsArrayType.getDimensions() > possibleSupertypeAsArrayType
0331: .getDimensions()) {
0332: return isSubtype(new ArrayType(typeBasicType,
0333: typeAsArrayType.getDimensions()
0334: - possibleSupertypeAsArrayType
0335: .getDimensions()),
0336: (ObjectType) possibleSupertypeBasicType);
0337: }
0338:
0339: // type's base type must be a subtype of possibleSupertype's base type.
0340: // Note that neither base type can be a non-ObjectType if we are to answer yes.
0341:
0342: if (!(typeBasicType instanceof ObjectType)) {
0343: return false;
0344: }
0345:
0346: return isSubtype((ObjectType) typeBasicType,
0347: (ObjectType) possibleSupertypeBasicType);
0348: }
0349:
0350: // OK, we've exhausted the possibilities now
0351: return false;
0352: }
0353:
0354: public boolean isSubtype(ClassDescriptor subDesc,
0355: ClassDescriptor super Desc) throws ClassNotFoundException {
0356: assert subDesc != null;
0357: assert super Desc != null;
0358: SupertypeQueryResults super typeQueryResults = getSupertypeQueryResults(subDesc);
0359: return super typeQueryResults.containsType(super Desc);
0360: }
0361:
0362: /**
0363: * Determine whether or not a given ObjectType is a subtype of another.
0364: * Throws ClassNotFoundException if the question cannot be answered
0365: * definitively due to a missing class.
0366: *
0367: * @param type a ReferenceType
0368: * @param possibleSupertype another Reference type
0369: * @return true if <code>type</code> is a subtype of <code>possibleSupertype</code>, false if not
0370: * @throws ClassNotFoundException if a missing class prevents a definitive answer
0371: */
0372: public boolean isSubtype(ObjectType type,
0373: ObjectType possibleSupertype) throws ClassNotFoundException {
0374: if (DEBUG_QUERIES) {
0375: System.out.println("isSubtype: check " + type
0376: + " subtype of " + possibleSupertype);
0377: }
0378:
0379: if (type.equals(possibleSupertype)) {
0380: if (DEBUG_QUERIES) {
0381: System.out.println(" ==> yes, types are same");
0382: }
0383: return true;
0384: }
0385: ClassDescriptor typeClassDescriptor = BCELUtil
0386: .getClassDescriptor(type);
0387: ClassDescriptor possibleSuperclassClassDescriptor = BCELUtil
0388: .getClassDescriptor(possibleSupertype);
0389:
0390: // In principle, we should be able to answer no if the ObjectType objects
0391: // are not equal and possibleSupertype is final.
0392: // However, internally FindBugs creates special "subtypes" of java.lang.String
0393: // (DynamicStringType, StaticStringType, etc.)---see FindRefComparison detector.
0394: // These will end up resolving to the same ClassVertex as java.lang.String,
0395: // which will Do The Right Thing.
0396: if (false) {
0397: ClassVertex possibleSuperclassClassVertex = resolveClassVertex(possibleSuperclassClassDescriptor);
0398: if (possibleSuperclassClassVertex.isResolved()
0399: && possibleSuperclassClassVertex.getXClass()
0400: .isFinal()) {
0401: if (DEBUG_QUERIES) {
0402: System.out.println(" ==> no, "
0403: + possibleSuperclassClassDescriptor
0404: + " is final");
0405: }
0406: return false;
0407: }
0408: }
0409:
0410: // Get the supertype query results
0411: SupertypeQueryResults super typeQueryResults = getSupertypeQueryResults(typeClassDescriptor);
0412: if (DEBUG_QUERIES) {
0413: System.out.println(" Superclass set: "
0414: + super typeQueryResults.super typeSet);
0415: }
0416:
0417: boolean isSubtype = super typeQueryResults
0418: .containsType(possibleSuperclassClassDescriptor);
0419: if (DEBUG_QUERIES) {
0420: if (isSubtype) {
0421: System.out.println(" ==> yes, "
0422: + possibleSuperclassClassDescriptor
0423: + " is in superclass set");
0424: } else {
0425: System.out.println(" ==> no, "
0426: + possibleSuperclassClassDescriptor
0427: + " is not in superclass set");
0428: }
0429: }
0430: return isSubtype;
0431: }
0432:
0433: /**
0434: * Get the first common superclass of the given reference types.
0435: * Note that an interface type is never returned unless <code>a</code> and <code>b</code> are the
0436: * same type. Otherwise, we try to return as accurate a type as possible.
0437: * This method is used as the meet operator in TypeDataflowAnalysis,
0438: * and is intended to follow (more or less) the JVM bytecode verifier
0439: * semantics.
0440: *
0441: * <p>This method should be used in preference to the getFirstCommonSuperclass()
0442: * method in {@link ReferenceType}.</p>
0443: *
0444: * @param a a ReferenceType
0445: * @param b another ReferenceType
0446: * @return the first common superclass of <code>a</code> and <code>b</code>
0447: * @throws ClassNotFoundException
0448: */
0449: public ReferenceType getFirstCommonSuperclass(ReferenceType a,
0450: ReferenceType b) throws ClassNotFoundException {
0451: // Easy case: same types
0452: if (a.equals(b)) {
0453: return a;
0454: }
0455:
0456: ReferenceType answer = checkFirstCommonSuperclassQueryCache(a,
0457: b);
0458: if (answer == null) {
0459: answer = computeFirstCommonSuperclassOfReferenceTypes(a, b);
0460: putFirstCommonSuperclassQueryCache(a, b, answer);
0461: }
0462: return answer;
0463: }
0464:
0465: private ReferenceType computeFirstCommonSuperclassOfReferenceTypes(
0466: ReferenceType a, ReferenceType b)
0467: throws ClassNotFoundException {
0468: boolean aIsArrayType = (a instanceof ArrayType);
0469: boolean bIsArrayType = (b instanceof ArrayType);
0470:
0471: if (aIsArrayType && bIsArrayType) {
0472: // Merging array types - kind of a pain.
0473:
0474: ArrayType aArrType = (ArrayType) a;
0475: ArrayType bArrType = (ArrayType) b;
0476:
0477: if (aArrType.getDimensions() == bArrType.getDimensions()) {
0478: return computeFirstCommonSuperclassOfSameDimensionArrays(
0479: aArrType, bArrType);
0480: } else {
0481: return computeFirstCommonSuperclassOfDifferentDimensionArrays(
0482: aArrType, bArrType);
0483: }
0484: }
0485:
0486: if (aIsArrayType || bIsArrayType) {
0487: // One of a and b is an array type, but not both.
0488: // Common supertype is Object.
0489: return ObjectType.OBJECT;
0490: }
0491:
0492: // Neither a nor b is an array type.
0493: // Find first common supertypes of ObjectTypes.
0494: return getFirstCommonSuperclass((ObjectType) a, (ObjectType) b);
0495: }
0496:
0497: /**
0498: * Get first common supertype of arrays with the same number of dimensions.
0499: *
0500: * @param aArrType an ArrayType
0501: * @param bArrType another ArrayType with the same number of dimensions
0502: * @return first common supertype
0503: * @throws ClassNotFoundException
0504: */
0505: private ReferenceType computeFirstCommonSuperclassOfSameDimensionArrays(
0506: ArrayType aArrType, ArrayType bArrType)
0507: throws ClassNotFoundException {
0508: assert aArrType.getDimensions() == bArrType.getDimensions();
0509:
0510: Type aBaseType = aArrType.getBasicType();
0511: Type bBaseType = bArrType.getBasicType();
0512: boolean aBaseIsObjectType = (aBaseType instanceof ObjectType);
0513: boolean bBaseIsObjectType = (bBaseType instanceof ObjectType);
0514:
0515: if (!aBaseIsObjectType || !bBaseIsObjectType) {
0516: assert (aBaseType instanceof BasicType)
0517: || (bBaseType instanceof BasicType);
0518:
0519: if (aArrType.getDimensions() > 1) {
0520: // E.g.: first common supertype of int[][] and WHATEVER[][] is Object[]
0521: return new ArrayType(Type.OBJECT, aArrType
0522: .getDimensions() - 1);
0523: } else {
0524: assert aArrType.getDimensions() == 1;
0525: // E.g.: first common supertype type of int[] and WHATEVER[] is Object
0526: return Type.OBJECT;
0527: }
0528: } else {
0529: assert (aBaseType instanceof ObjectType);
0530: assert (bBaseType instanceof ObjectType);
0531:
0532: // Base types are both ObjectTypes, and number of dimensions is same.
0533: // We just need to find the first common supertype of base types
0534: // and return a new ArrayType using that base type.
0535: ObjectType firstCommonBaseType = getFirstCommonSuperclass(
0536: (ObjectType) aBaseType, (ObjectType) bBaseType);
0537: return new ArrayType(firstCommonBaseType, aArrType
0538: .getDimensions());
0539: }
0540: }
0541:
0542: /**
0543: * Get the first common superclass of
0544: * arrays with different numbers of dimensions.
0545: *
0546: * @param aArrType an ArrayType
0547: * @param bArrType another ArrayType
0548: * @return ReferenceType representing first common superclass
0549: */
0550: private ReferenceType computeFirstCommonSuperclassOfDifferentDimensionArrays(
0551: ArrayType aArrType, ArrayType bArrType) {
0552: assert aArrType.getDimensions() != bArrType.getDimensions();
0553:
0554: boolean aBaseTypeIsPrimitive = (aArrType.getBasicType() instanceof BasicType);
0555: boolean bBaseTypeIsPrimitive = (bArrType.getBasicType() instanceof BasicType);
0556:
0557: if (aBaseTypeIsPrimitive || bBaseTypeIsPrimitive) {
0558: int minDimensions, maxDimensions;
0559: if (aArrType.getDimensions() < bArrType.getDimensions()) {
0560: minDimensions = aArrType.getDimensions();
0561: maxDimensions = bArrType.getDimensions();
0562: } else {
0563: minDimensions = bArrType.getDimensions();
0564: maxDimensions = aArrType.getDimensions();
0565: }
0566:
0567: if (minDimensions == 1) {
0568: // One of the types was something like int[].
0569: // The only possible common supertype is Object.
0570: return Type.OBJECT;
0571: } else {
0572: // Weird case: e.g.,
0573: // - first common supertype of int[][] and char[][][] is Object[]
0574: // because f.c.s. of int[] and char[][] is Object
0575: // - first common supertype of int[][][] and char[][][][][] is Object[][]
0576: // because f.c.s. of int[] and char[][][] is Object
0577: return new ArrayType(Type.OBJECT, maxDimensions
0578: - minDimensions);
0579: }
0580: } else {
0581: // Both a and b have base types which are ObjectTypes.
0582: // Since the arrays have different numbers of dimensions, the
0583: // f.c.s. will have Object as its base type.
0584: // E.g., f.c.s. of Cat[] and Dog[][] is Object[]
0585: return new ArrayType(Type.OBJECT, Math.min(aArrType
0586: .getDimensions(), bArrType.getDimensions()));
0587: }
0588: }
0589:
0590: /**
0591: * Get the first common superclass of the given object types.
0592: * Note that an interface type is never returned unless <code>a</code> and <code>b</code> are the
0593: * same type. Otherwise, we try to return as accurate a type as possible.
0594: * This method is used as the meet operator in TypeDataflowAnalysis,
0595: * and is intended to follow (more or less) the JVM bytecode verifier
0596: * semantics.
0597: *
0598: * <p>This method should be used in preference to the getFirstCommonSuperclass()
0599: * method in {@link ReferenceType}.</p>
0600: *
0601: * @param a an ObjectType
0602: * @param b another ObjectType
0603: * @return the first common superclass of <code>a</code> and <code>b</code>
0604: * @throws ClassNotFoundException
0605: */
0606: public ObjectType getFirstCommonSuperclass(ObjectType a,
0607: ObjectType b) throws ClassNotFoundException {
0608: // Easy case
0609: if (a.equals(b)) {
0610: return a;
0611: }
0612:
0613: ObjectType firstCommonSupertype = (ObjectType) checkFirstCommonSuperclassQueryCache(
0614: a, b);
0615: if (firstCommonSupertype == null) {
0616: firstCommonSupertype = computeFirstCommonSuperclassOfObjectTypes(
0617: a, b);
0618: firstCommonSuperclassQueryCache.put(a, b,
0619: firstCommonSupertype);
0620: }
0621:
0622: return firstCommonSupertype;
0623: }
0624:
0625: private ObjectType computeFirstCommonSuperclassOfObjectTypes(
0626: ObjectType a, ObjectType b) throws ClassNotFoundException {
0627: ObjectType firstCommonSupertype;
0628: ClassDescriptor aDesc = BCELUtil.getClassDescriptor(a);
0629: ClassDescriptor bDesc = BCELUtil.getClassDescriptor(b);
0630:
0631: ClassVertex aVertex = resolveClassVertex(aDesc);
0632: ClassVertex bVertex = resolveClassVertex(bDesc);
0633:
0634: Set<ClassDescriptor> aSuperTypes = computeKnownSupertypes(aDesc);
0635: Set<ClassDescriptor> bSuperTypes = computeKnownSupertypes(bDesc);
0636: if (bSuperTypes.contains(aDesc))
0637: return a;
0638: if (aSuperTypes.contains(bDesc))
0639: return b;
0640: ArrayList<ClassVertex> aSuperList = getAllSuperclassVertices(aVertex);
0641: ArrayList<ClassVertex> bSuperList = getAllSuperclassVertices(bVertex);
0642:
0643: // Work backwards until the lists diverge.
0644: // The last element common to both lists is the first
0645: // common superclass.
0646: int aIndex = aSuperList.size() - 1;
0647: int bIndex = bSuperList.size() - 1;
0648:
0649: ClassVertex lastCommonInBackwardsSearch = null;
0650: while (aIndex >= 0 && bIndex >= 0) {
0651: if (aSuperList.get(aIndex) != bSuperList.get(bIndex)) {
0652: break;
0653: }
0654: lastCommonInBackwardsSearch = aSuperList.get(aIndex);
0655: aIndex--;
0656: bIndex--;
0657: }
0658: if (lastCommonInBackwardsSearch == null)
0659: firstCommonSupertype = ObjectType.OBJECT;
0660: else
0661: firstCommonSupertype = ObjectTypeFactory
0662: .getInstance(lastCommonInBackwardsSearch
0663: .getClassDescriptor().toDottedClassName());
0664: if (firstCommonSupertype.equals(ObjectType.OBJECT)) {
0665: // see if we can't do better
0666: ClassDescriptor objDesc = BCELUtil
0667: .getClassDescriptor(ObjectType.OBJECT);
0668: aSuperTypes.retainAll(bSuperTypes);
0669: aSuperTypes.remove(objDesc);
0670: for (ClassDescriptor c : aSuperTypes)
0671: if (c.getPackageName().equals(aDesc.getPackageName())
0672: || c.getPackageName().equals(
0673: bDesc.getPackageName()))
0674: return ObjectTypeFactory.getInstance(c
0675: .toDottedClassName());
0676:
0677: for (ClassDescriptor c : aSuperTypes)
0678: return ObjectTypeFactory.getInstance(c
0679: .toDottedClassName());
0680: }
0681:
0682: return firstCommonSupertype;
0683: }
0684:
0685: private void putFirstCommonSuperclassQueryCache(ReferenceType a,
0686: ReferenceType b, ReferenceType answer) {
0687: if (a.getSignature().compareTo(b.getSignature()) > 0) {
0688: ReferenceType tmp = a;
0689: a = b;
0690: b = tmp;
0691: }
0692: firstCommonSuperclassQueryCache.put(a, b, answer);
0693: }
0694:
0695: private ReferenceType checkFirstCommonSuperclassQueryCache(
0696: ReferenceType a, ReferenceType b) {
0697: if (a.getSignature().compareTo(b.getSignature()) > 0) {
0698: ReferenceType tmp = a;
0699: a = b;
0700: b = tmp;
0701: }
0702: return firstCommonSuperclassQueryCache.get(a, b);
0703: }
0704:
0705: /**
0706: * Get list of all superclasses of class represented by given class vertex,
0707: * in order, including the class itself (which is trivially its own superclass
0708: * as far as "first common superclass" queries are concerned.)
0709: *
0710: * @param vertex a ClassVertex
0711: * @return list of all superclass vertices in order
0712: */
0713: private ArrayList<ClassVertex> getAllSuperclassVertices(
0714: ClassVertex vertex) throws ClassNotFoundException {
0715: ArrayList<ClassVertex> result = new ArrayList<ClassVertex>();
0716: ClassVertex cur = vertex;
0717: while (cur != null) {
0718: if (!cur.isResolved()) {
0719: BCELUtil.throwClassNotFoundException(cur
0720: .getClassDescriptor());
0721: }
0722: result.add(cur);
0723: cur = cur.getDirectSuperclass();
0724: }
0725: return result;
0726: }
0727:
0728: /**
0729: * Get known subtypes of given class.
0730: *
0731: * @param classDescriptor ClassDescriptor naming a class
0732: * @return Set of ClassDescriptors which are the known subtypes of the class
0733: * @throws ClassNotFoundException
0734: */
0735: public Set<ClassDescriptor> getSubtypes(
0736: ClassDescriptor classDescriptor)
0737: throws ClassNotFoundException {
0738: Set<ClassDescriptor> result = subtypeSetMap
0739: .get(classDescriptor);
0740: if (result == null) {
0741: result = computeKnownSubtypes(classDescriptor);
0742: subtypeSetMap.put(classDescriptor, result);
0743: }
0744: return result;
0745: }
0746:
0747: /**
0748: * Get known subtypes of given class.
0749: *
0750: * @param classDescriptor ClassDescriptor naming a class
0751: * @return Set of ClassDescriptors which are the known subtypes of the class
0752: * @throws ClassNotFoundException
0753: */
0754: public Set<ClassDescriptor> getDirectSubtypes(
0755: ClassDescriptor classDescriptor)
0756: throws ClassNotFoundException {
0757:
0758: ClassVertex startVertex = resolveClassVertex(classDescriptor);
0759:
0760: Set<ClassDescriptor> result = new HashSet<ClassDescriptor>();
0761: // Add all known subtype vertices to the work list
0762: Iterator<InheritanceEdge> i = graph
0763: .incomingEdgeIterator(startVertex);
0764: while (i.hasNext()) {
0765: InheritanceEdge edge = i.next();
0766: result.add(edge.getSource().getClassDescriptor());
0767: }
0768:
0769: return result;
0770: }
0771:
0772: public Set<ClassDescriptor> getTransitiveCommonSubtypes(
0773: ClassDescriptor classDescriptor1,
0774: ClassDescriptor classDescriptor2)
0775: throws ClassNotFoundException {
0776: Set<ClassDescriptor> subtypes1 = getSubtypes(classDescriptor1);
0777: Set<ClassDescriptor> result = new HashSet<ClassDescriptor>(
0778: subtypes1);
0779: Set<ClassDescriptor> subtypes2 = getSubtypes(classDescriptor2);
0780: result.retainAll(subtypes2);
0781: return result;
0782: }
0783:
0784: /**
0785: * Get Collection of all XClass objects (resolved classes)
0786: * seen so far.
0787: *
0788: * @return Collection of all XClass objects
0789: */
0790: public Collection<XClass> getXClassCollection() {
0791: return Collections.unmodifiableCollection(xclassSet);
0792: }
0793:
0794: /**
0795: * An in-progress traversal of one path from a class or interface
0796: * to java.lang.Object.
0797: */
0798: private static class SupertypeTraversalPath {
0799: ClassVertex next;
0800: Set<ClassDescriptor> seen;
0801:
0802: public SupertypeTraversalPath(@CheckForNull
0803: ClassVertex next) {
0804: this .next = next;
0805: this .seen = new HashSet<ClassDescriptor>();
0806: }
0807:
0808: @Override
0809: public String toString() {
0810: return next.toString() + ":" + seen;
0811: }
0812:
0813: public ClassVertex getNext() {
0814: return next;
0815: }
0816:
0817: public boolean hasBeenSeen(ClassDescriptor classDescriptor) {
0818: return seen.contains(classDescriptor);
0819: }
0820:
0821: public void markSeen(ClassDescriptor classDescriptor) {
0822: seen.add(classDescriptor);
0823: }
0824:
0825: public void setNext(ClassVertex next) {
0826: assert !hasBeenSeen(next.getClassDescriptor());
0827: this .next = next;
0828: }
0829:
0830: public SupertypeTraversalPath fork(ClassVertex next) {
0831: SupertypeTraversalPath dup = new SupertypeTraversalPath(
0832: null);
0833: dup.seen.addAll(this .seen);
0834: dup.setNext(next);
0835: return dup;
0836: }
0837:
0838: }
0839:
0840: /**
0841: * Starting at the class or interface named by the given ClassDescriptor,
0842: * traverse the inheritance graph, exploring all paths from
0843: * the class or interface to java.lang.Object.
0844: *
0845: * @param start ClassDescriptor naming the class where the traversal should start
0846: * @param visitor an InheritanceGraphVisitor
0847: * @throws ClassNotFoundException
0848: */
0849: public void traverseSupertypes(ClassDescriptor start,
0850: InheritanceGraphVisitor visitor)
0851: throws ClassNotFoundException {
0852: LinkedList<SupertypeTraversalPath> workList = new LinkedList<SupertypeTraversalPath>();
0853:
0854: ClassVertex startVertex = resolveClassVertex(start);
0855: workList.addLast(new SupertypeTraversalPath(startVertex));
0856:
0857: while (!workList.isEmpty()) {
0858: SupertypeTraversalPath cur = workList.removeFirst();
0859:
0860: ClassVertex vertex = cur.getNext();
0861: assert !cur.hasBeenSeen(vertex.getClassDescriptor());
0862: cur.markSeen(vertex.getClassDescriptor());
0863:
0864: if (!visitor.visitClass(vertex.getClassDescriptor(), vertex
0865: .getXClass())) {
0866: // Visitor doesn't want to continue on this path
0867: continue;
0868: }
0869:
0870: if (!vertex.isResolved()) {
0871: // Unknown class - so, we don't know its immediate supertypes
0872: continue;
0873: }
0874:
0875: // Advance to direct superclass
0876: ClassDescriptor super classDescriptor = vertex.getXClass()
0877: .getSuperclassDescriptor();
0878: if (super classDescriptor != null
0879: && traverseEdge(vertex, super classDescriptor,
0880: false, visitor)) {
0881: addToWorkList(workList, cur, super classDescriptor);
0882: }
0883:
0884: // Advance to directly-implemented interfaces
0885: for (ClassDescriptor ifaceDesc : vertex.getXClass()
0886: .getInterfaceDescriptorList()) {
0887: if (traverseEdge(vertex, ifaceDesc, true, visitor)) {
0888: addToWorkList(workList, cur, ifaceDesc);
0889: }
0890: }
0891: }
0892: }
0893:
0894: private void addToWorkList(
0895: LinkedList<SupertypeTraversalPath> workList,
0896: SupertypeTraversalPath curPath,
0897: ClassDescriptor super typeDescriptor) {
0898: ClassVertex vertex = classDescriptorToVertexMap
0899: .get(super typeDescriptor);
0900:
0901: // The vertex should already have been added to the graph
0902: assert vertex != null;
0903:
0904: if (curPath.hasBeenSeen(vertex.getClassDescriptor())) {
0905: // This can only happen when the inheritance graph has a cycle
0906: return;
0907: }
0908:
0909: SupertypeTraversalPath newPath = curPath.fork(vertex);
0910: workList.addLast(newPath);
0911: }
0912:
0913: private boolean traverseEdge(ClassVertex vertex, @CheckForNull
0914: ClassDescriptor super typeDescriptor, boolean isInterfaceEdge,
0915: InheritanceGraphVisitor visitor) {
0916: if (super typeDescriptor == null) {
0917: // We reached java.lang.Object
0918: return false;
0919: }
0920:
0921: ClassVertex super typeVertex = classDescriptorToVertexMap
0922: .get(super typeDescriptor);
0923: if (super typeVertex == null) {
0924: try {
0925: super typeVertex = resolveClassVertex(super typeDescriptor);
0926: } catch (ClassNotFoundException e) {
0927: super typeVertex = addClassVertexForMissingClass(
0928: super typeDescriptor, isInterfaceEdge);
0929: }
0930: }
0931: assert super typeVertex != null;
0932:
0933: return visitor.visitEdge(vertex.getClassDescriptor(), vertex
0934: .getXClass(), super typeDescriptor, super typeVertex
0935: .getXClass());
0936: }
0937:
0938: /**
0939: * Compute set of known subtypes of class named by given ClassDescriptor.
0940: *
0941: * @param classDescriptor a ClassDescriptor
0942: * @throws ClassNotFoundException
0943: */
0944: private Set<ClassDescriptor> computeKnownSubtypes(
0945: ClassDescriptor classDescriptor)
0946: throws ClassNotFoundException {
0947: LinkedList<ClassVertex> workList = new LinkedList<ClassVertex>();
0948:
0949: ClassVertex startVertex = resolveClassVertex(classDescriptor);
0950: workList.addLast(startVertex);
0951:
0952: Set<ClassDescriptor> result = new HashSet<ClassDescriptor>();
0953:
0954: while (!workList.isEmpty()) {
0955: ClassVertex current = workList.removeFirst();
0956:
0957: if (result.contains(current.getClassDescriptor())) {
0958: // Already added this class
0959: continue;
0960: }
0961:
0962: // Add class to the result
0963: result.add(current.getClassDescriptor());
0964:
0965: // Add all known subtype vertices to the work list
0966: Iterator<InheritanceEdge> i = graph
0967: .incomingEdgeIterator(current);
0968: while (i.hasNext()) {
0969: InheritanceEdge edge = i.next();
0970: workList.addLast(edge.getSource());
0971: }
0972: }
0973:
0974: return result;
0975: }
0976:
0977: private Set<ClassDescriptor> computeKnownSupertypes(
0978: ClassDescriptor classDescriptor)
0979: throws ClassNotFoundException {
0980: LinkedList<ClassVertex> workList = new LinkedList<ClassVertex>();
0981:
0982: ClassVertex startVertex = resolveClassVertex(classDescriptor);
0983: workList.addLast(startVertex);
0984:
0985: Set<ClassDescriptor> result = new HashSet<ClassDescriptor>();
0986:
0987: while (!workList.isEmpty()) {
0988: ClassVertex current = workList.removeFirst();
0989:
0990: if (result.contains(current.getClassDescriptor())) {
0991: // Already added this class
0992: continue;
0993: }
0994:
0995: // Add class to the result
0996: result.add(current.getClassDescriptor());
0997:
0998: // Add all known subtype vertices to the work list
0999: Iterator<InheritanceEdge> i = graph
1000: .outgoingEdgeIterator(current);
1001: while (i.hasNext()) {
1002: InheritanceEdge edge = i.next();
1003: workList.addLast(edge.getTarget());
1004: }
1005: }
1006:
1007: return result;
1008: }
1009:
1010: /**
1011: * Look up or compute the SupertypeQueryResults for class
1012: * named by given ClassDescriptor.
1013: *
1014: * @param classDescriptor a ClassDescriptor
1015: * @return SupertypeQueryResults for the class named by the ClassDescriptor
1016: * @throws ClassNotFoundException
1017: */
1018: public SupertypeQueryResults getSupertypeQueryResults(
1019: ClassDescriptor classDescriptor)
1020: throws ClassNotFoundException {
1021: SupertypeQueryResults super typeQueryResults = super typeSetMap
1022: .get(classDescriptor);
1023: if (super typeQueryResults == null) {
1024: super typeQueryResults = computeSupertypes(classDescriptor);
1025: super typeSetMap.put(classDescriptor, super typeQueryResults);
1026: }
1027: return super typeQueryResults;
1028: }
1029:
1030: /**
1031: * Compute supertypes for class named by given ClassDescriptor.
1032: *
1033: * @param classDescriptor a ClassDescriptor
1034: * @return SupertypeQueryResults containing known supertypes of the class
1035: * @throws ClassNotFoundException if the class can't be found
1036: */
1037: private SupertypeQueryResults computeSupertypes(
1038: ClassDescriptor classDescriptor)
1039: throws ClassNotFoundException {
1040: if (DEBUG_QUERIES) {
1041: System.out.println("Computing supertypes for "
1042: + classDescriptor.toDottedClassName());
1043: }
1044:
1045: // Try to fully resolve the class and its superclasses/superinterfaces.
1046: ClassVertex typeVertex = resolveClassVertex(classDescriptor);
1047:
1048: // Create new empty SupertypeQueryResults.
1049: SupertypeQueryResults super typeSet = new SupertypeQueryResults();
1050:
1051: // Add all known superclasses/superinterfaces.
1052: // The ClassVertexes for all of them should be in the
1053: // InheritanceGraph by now.
1054: LinkedList<ClassVertex> workList = new LinkedList<ClassVertex>();
1055: workList.addLast(typeVertex);
1056: while (!workList.isEmpty()) {
1057: ClassVertex vertex = workList.removeFirst();
1058: if (vertex.isResolved()) {
1059: if (DEBUG_QUERIES) {
1060: System.out.println(" Adding supertype "
1061: + vertex.getClassDescriptor()
1062: .toDottedClassName());
1063: }
1064: super typeSet.addSupertype(vertex.getClassDescriptor());
1065: } else {
1066: if (DEBUG_QUERIES) {
1067: System.out
1068: .println(" Encountered unresolved class "
1069: + vertex.getClassDescriptor()
1070: .toDottedClassName()
1071: + " in supertype query");
1072: }
1073: super typeSet.setEncounteredMissingClasses(true);
1074: }
1075:
1076: Iterator<InheritanceEdge> i = graph
1077: .outgoingEdgeIterator(vertex);
1078: while (i.hasNext()) {
1079: InheritanceEdge edge = i.next();
1080: workList.addLast(edge.getTarget());
1081: }
1082: }
1083:
1084: return super typeSet;
1085: }
1086:
1087: /**
1088: * Resolve a class named by given ClassDescriptor and return
1089: * its resolved ClassVertex.
1090: *
1091: * @param classDescriptor a ClassDescriptor
1092: * @return resolved ClassVertex representing the class in the InheritanceGraph
1093: * @throws ClassNotFoundException if the class named by the ClassDescriptor does not exist
1094: */
1095: private ClassVertex resolveClassVertex(
1096: ClassDescriptor classDescriptor)
1097: throws ClassNotFoundException {
1098: ClassVertex typeVertex = classDescriptorToVertexMap
1099: .get(classDescriptor);
1100: if (typeVertex == null) {
1101: // We have never tried to resolve this ClassVertex before.
1102: // Try to find the XClass for this class.
1103: XClass xclass = AnalysisContext.currentXFactory()
1104: .getXClass(classDescriptor);
1105: if (xclass == null) {
1106: // Class we're trying to resolve doesn't exist.
1107: // XXX: unfortunately, we don't know if the missing class is a class or interface
1108: typeVertex = addClassVertexForMissingClass(
1109: classDescriptor, false);
1110: } else {
1111: // Add the class and all its superclasses/superinterfaces to the inheritance graph.
1112: // This will result in a resolved ClassVertex.
1113: typeVertex = addClassAndGetClassVertex(xclass);
1114: }
1115: }
1116:
1117: if (!typeVertex.isResolved()) {
1118: BCELUtil.throwClassNotFoundException(classDescriptor);
1119: }
1120:
1121: assert typeVertex.isResolved();
1122: return typeVertex;
1123: }
1124:
1125: /**
1126: * Add supertype edges to the InheritanceGraph
1127: * for given ClassVertex. If any direct supertypes
1128: * have not been processed, add them to the worklist.
1129: *
1130: * @param vertex a ClassVertex whose supertype edges need to be added
1131: * @param workList work list of ClassVertexes that need to have
1132: * their supertype edges added
1133: */
1134: private void addSupertypeEdges(ClassVertex vertex,
1135: LinkedList<XClass> workList) {
1136: XClass xclass = vertex.getXClass();
1137:
1138: // Direct superclass
1139: ClassDescriptor super classDescriptor = xclass
1140: .getSuperclassDescriptor();
1141: if (super classDescriptor != null)
1142: addInheritanceEdge(vertex, super classDescriptor, false,
1143: workList);
1144:
1145: // Directly implemented interfaces
1146: for (ClassDescriptor ifaceDesc : xclass
1147: .getInterfaceDescriptorList()) {
1148: addInheritanceEdge(vertex, ifaceDesc, true, workList);
1149: }
1150: }
1151:
1152: /**
1153: * Add supertype edge to the InheritanceGraph.
1154: *
1155: * @param vertex source ClassVertex (subtype)
1156: * @param superclassDescriptor ClassDescriptor of a direct supertype
1157: * @param isInterfaceEdge true if supertype is (as far as we know) an interface
1158: * @param workList work list of ClassVertexes that need to have
1159: * their supertype edges added (null if no further work will be generated)
1160: */
1161: private void addInheritanceEdge(ClassVertex vertex,
1162: ClassDescriptor super classDescriptor,
1163: boolean isInterfaceEdge, @CheckForNull
1164: LinkedList<XClass> workList) {
1165: if (super classDescriptor == null) {
1166: return;
1167: }
1168:
1169: ClassVertex super classVertex = classDescriptorToVertexMap
1170: .get(super classDescriptor);
1171: if (super classVertex == null) {
1172: // Haven't encountered this class previously.
1173:
1174: XClass super classXClass = AnalysisContext.currentXFactory()
1175: .getXClass(super classDescriptor);
1176: if (super classXClass == null) {
1177: // Inheritance graph will be incomplete.
1178: // Add a dummy node to inheritance graph and report missing class.
1179: super classVertex = addClassVertexForMissingClass(
1180: super classDescriptor, isInterfaceEdge);
1181: } else {
1182: // Haven't seen this class before.
1183: super classVertex = ClassVertex
1184: .createResolvedClassVertex(
1185: super classDescriptor, super classXClass);
1186: addVertexToGraph(super classDescriptor, super classVertex);
1187:
1188: if (workList != null) {
1189: // We'll want to recursively process the superclass.
1190: workList.addLast(super classXClass);
1191: }
1192: }
1193: }
1194: assert super classVertex != null;
1195:
1196: if (graph.lookupEdge(vertex, super classVertex) == null) {
1197: if (DEBUG) {
1198: System.out.println(" Add edge "
1199: + vertex.getClassDescriptor()
1200: .toDottedClassName() + " -> "
1201: + super classDescriptor.toDottedClassName());
1202: }
1203: graph.createEdge(vertex, super classVertex);
1204: }
1205: }
1206:
1207: /**
1208: * Add a ClassVertex representing a missing class.
1209: *
1210: * @param missingClassDescriptor ClassDescriptor naming a missing class
1211: * @param isInterfaceEdge
1212: * @return the ClassVertex representing the missing class
1213: */
1214: private ClassVertex addClassVertexForMissingClass(
1215: ClassDescriptor missingClassDescriptor,
1216: boolean isInterfaceEdge) {
1217: ClassVertex missingClassVertex = ClassVertex
1218: .createMissingClassVertex(missingClassDescriptor,
1219: isInterfaceEdge);
1220: missingClassVertex.setFinished(true);
1221: addVertexToGraph(missingClassDescriptor, missingClassVertex);
1222:
1223: AnalysisContext.currentAnalysisContext()
1224: .getLookupFailureCallback().reportMissingClass(
1225: missingClassDescriptor);
1226:
1227: return missingClassVertex;
1228: }
1229: }
|