typerepository.java

一个查找java程序里bug的程序的源代码,该程序本身也是java写的,对提高java编程水平很有用

		return floatType;
	}

	/**
	 * Get the double type.
	 *
	 * @return the double type
	 */
	public BasicType getDoubleType() {
		return doubleType;
	}

	/**
	 * Get the instance of the special TOP type.
	 *
	 * @return the TOP instance
	 */
	public Type getTopType() {
		return topType;
	}

	/**
	 * Get the instance of the special BOTTOM type.
	 *
	 * @return the BOTTOM instance
	 */
	public Type getBottomType() {
		return bottomType;
	}

	/**
	 * Get the instance of the special NULL type.
	 *
	 * @return the NULL type
	 */
	public Type getNullType() {
		return nullType;
	}

	/**
	 * Get the instance of the special long extra type.
	 *
	 * @return the long extra type
	 */
	public Type getLongExtraType() {
		return longExtraType;
	}

	/**
	 * Get the instance of the special double extra type.
	 *
	 * @return the double extra type
	 */
	public Type getDoubleExtraType() {
		return doubleExtraType;
	}

	/**
	 * Get the instance of the return address type.
	 *
	 * @return the return address type
	 */
	public Type getReturnAddressType() {
		return returnAddressType;
	}

	/**
	 * Add a direct superclass relationship to types in the repository.
	 *
	 * @param subclass   the subclass
	 * @param superclass the superclass
	 */
	public void addSuperclassLink(ObjectType subclass, ObjectType superclass) {
		if (DEBUG)
			System.out.println("Superclass link: " + subclass.getSignature() + " --> " + superclass.getSignature());
		inheritanceGraph.createEdge(subclass, superclass, InheritanceGraphEdgeTypes.CLASS_EDGE);
	}

	/**
	 * Add a direct implemented interface relationship to types in the repository.
	 *
	 * @param implementor the class or interface directly implementing the interface (i.e., the subtype)
	 * @param iface       the implemented interface (i.e., the supertype)
	 */
	public void addInterfaceLink(ObjectType implementor, ClassType iface) {
		if (DEBUG)
			System.out.println("Interface link: " + implementor.getSignature() + " --> " + iface.getSignature());
		inheritanceGraph.createEdge(implementor, iface, InheritanceGraphEdgeTypes.INTERFACE_EDGE);
	}

	/**
	 * Determine if one object type is a subtype of another.
	 *
	 * @param subtype   the potential subtype
	 * @param supertype the potential supertype
	 * @return true if subtype is really a subtype of supertype, false otherwise
	 */
	public boolean isSubtype(ObjectType subtype, ObjectType supertype) throws ClassNotFoundException {
		if (Debug.VERIFY_INTEGRITY) {
			if (!inheritanceGraph.containsVertex(subtype))
				throw new IllegalStateException("Inheritance graph does not contain node " +
				        subtype.getSignature());
			if (!inheritanceGraph.containsVertex(supertype))
				throw new IllegalStateException("Inheritance graph does not contain node " +
				        supertype.getSignature());
		}

		SubtypeQueryResult cachedResult = findSupertypes(subtype);
		return cachedResult.isSupertype(supertype);
	}

	/**
	 * Get the superclass of a class type.
	 *
	 * @param type the class type
	 * @return the ClassType representing the class's superclass,
	 *         or null if the type has no superclass (i.e., is java.lang.Object)
	 */
	public ClassType getSuperclass(ClassType type) throws ClassNotFoundException {
		resolveObjectType(type);

		for (Iterator<InheritanceGraphEdge> i = inheritanceGraph.outgoingEdgeIterator(type); i.hasNext();) {
			InheritanceGraphEdge edge = i.next();
			if (edge.getType() == InheritanceGraphEdgeTypes.CLASS_EDGE) {
				ObjectType supertype = edge.getTarget();
				if (!(supertype instanceof ClassType))
					throw new IllegalStateException("Class type " + type.getClassName() +
					        " has non-class type " + supertype.getSignature() + " as its superclass");
				// TODO: cache result
				return (ClassType) supertype;
			}
		}
		return null;
	}

	/**
	 * Get the first common superclass of two object types, in the
	 * sense used by the VM Spec.  This means that interfaces
	 * are always considered to have java.lang.Object as
	 * their common superclass, even if a more accurate interface
	 * type could be used.  Similarly, arrays of interface types
	 * of same dimensionality are considered to have an
	 * array of java.lang.Object as their common superclass.
	 * <p/>
	 * <p> This operation is commutative.
	 *
	 * @param a an ObjectType
	 * @param b another ObjectType
	 * @return the first common superclass of a and b
	 */
	public ObjectType getFirstCommonSuperclass(ObjectType a, ObjectType b) throws ClassNotFoundException {
		if (DEBUG) System.out.println("Get first common superclass for " + a + " and " + b);

		// Easy case
		if (a.equals(b))
			return a;

		// FIXME:
		// This algorithm could easily be extended to find the set
		// of common unrelated supertypes.  Just keep iterating
		// adding common supertypes to the set.  When a common
		// supertype is found, eliminate its supertypes from
		// consideration (since they would be not be "least" supertypes).

		// For now, we just use the stupid JVM bytecode verifier
		// algorithm that loses all sorts of information.

		SubtypeQueryResult cachedResultForA = findSupertypes(a);
		SubtypeQueryResult cachedResultForB = findSupertypes(b);

		for (Iterator<ObjectType> i = cachedResultForB.supertypeInBFSOrderIterator(); i.hasNext();) {
			ObjectType bSuper = i.next();
			if (DEBUG) System.out.print("  ....considering " + bSuper);
			if (bSuper.isInterface()) {
				// FIXME: stupid loss of information
				if (DEBUG) System.out.println(": INTERFACE, no");
				continue;
			}
			boolean isSuper = cachedResultForA.isSupertype(bSuper);
			if (DEBUG) System.out.println(": " + isSuper);
			if (isSuper) {
				return bSuper;
			}
		}

		// This should not be possible
		throw new IllegalStateException("Failed to find a common supertype: " +
		        " for object types " + a.getSignature() + " and " + b.getSignature() + ": impossible");
	}

	/* ----------------------------------------------------------------------
	 * Implementation
	 * ---------------------------------------------------------------------- */

	private void addBasicTypes() {
		signatureToTypeMap.put("Z", booleanType = new BasicType(Constants.T_BOOLEAN));
		signatureToTypeMap.put("B", byteType = new BasicType(Constants.T_BYTE));
		signatureToTypeMap.put("C", charType = new BasicType(Constants.T_CHAR));
		signatureToTypeMap.put("S", shortType = new BasicType(Constants.T_SHORT));
		signatureToTypeMap.put("I", intType = new BasicType(Constants.T_INT));
		signatureToTypeMap.put("J", longType = new BasicType(Constants.T_LONG));
		signatureToTypeMap.put("F", floatType = new BasicType(Constants.T_FLOAT));
		signatureToTypeMap.put("D", doubleType = new BasicType(Constants.T_DOUBLE));
		signatureToTypeMap.put("V", voidType = new BasicType(Constants.T_VOID));
	}

	private void addSpecialTypes() {
		signatureToTypeMap.put(SpecialTypeSignatures.NULL_TYPE_SIGNATURE, nullType = new NullType());
		signatureToTypeMap.put(SpecialTypeSignatures.TOP_TYPE_SIGNATURE, topType = new TopType());
		signatureToTypeMap.put(SpecialTypeSignatures.BOTTOM_TYPE_SIGNATURE, bottomType = new BottomType());
		signatureToTypeMap.put(SpecialTypeSignatures.LONG_EXTRA_TYPE_SIGNATURE, longExtraType = new LongExtraType());
		signatureToTypeMap.put(SpecialTypeSignatures.DOUBLE_EXTRA_TYPE_SIGNATURE, doubleExtraType = new DoubleExtraType());
		signatureToTypeMap.put(SpecialTypeSignatures.RETURN_ADDRESS_TYPE_SIGNATURE,
		        returnAddressType = new ReturnAddressType());
	}

	private ClassType createClassType(String signature) {
		ClassType type = (ClassType) signatureToTypeMap.get(signature);
		if (type == null) {
			type = new ClassType(signature);
			signatureToTypeMap.put(signature, type);
			inheritanceGraph.addVertex(type);
		}
		return type;
	}

	private ArrayType createArrayType(String signature) throws InvalidSignatureException {
		ArrayType type = (ArrayType) signatureToTypeMap.get(signature);
		if (type == null) {
			type = ArrayType.typeFromSignature(this, signature);
			signatureToTypeMap.put(signature, type);
			inheritanceGraph.addVertex(type);
		}
		return type;
	}

	private ArrayType createArrayType(int numDimensions, Type elementType) {
		String signature = ArrayType.makeArraySignature(numDimensions, elementType);
		ArrayType type = (ArrayType) signatureToTypeMap.get(signature);
		if (type == null) {
			type = new ArrayType(signature, numDimensions, elementType);
			signatureToTypeMap.put(signature, type);
			inheritanceGraph.addVertex(type);
		}
		return type;
	}

	private SubtypeQueryResult findSupertypes(ObjectType subtype) throws ClassNotFoundException {
		if (DEBUG) System.out.println("Computing supertypes for " + subtype);

		// See if there is a cached query result.
		SubtypeQueryResult cachedResult = subtype.getSubtypeQueryResult();

		if (cachedResult == null) {
			// Breadth first traversal of supertypes
	
			// Work queue
			LinkedList<ObjectType> work = new LinkedList<ObjectType>();
			work.add(subtype);
	
			// Keep track of where we've been
			HashSet<ObjectType> visited = new HashSet<ObjectType>();
	
			// Keep track of missing classes
			LinkedList<String> missingClassList = new LinkedList<String>();
	
			// Cached result for future queries
			cachedResult = new SubtypeQueryResult();
	
			// Keep going until we have examined all supertypes.
			while (!work.isEmpty()) {
				ObjectType type = work.removeFirst();
				if (!visited.add(type))
					continue;

				cachedResult.addSupertype(type);
				if (DEBUG) System.out.println("  ...added " + type);

				try {
					// Resolve the type so we know its supertypes.
					resolveObjectType(type);
	
					// Add all supertypes to work queue.
					for (Iterator<ObjectType> i = inheritanceGraph.successorIterator(type); i.hasNext();)
						work.add(i.next());
				} catch (ClassNotFoundException e) {
					String missingClassName = ClassNotFoundExceptionParser.getMissingClassName(e);
					if (missingClassName == null)
						missingClassName = "<unknown class>";
					missingClassList.add(missingClassName);
				}
			}

			cachedResult.finish(missingClassList.toArray(new String[missingClassList.size()]));
	
			// Cache result for future queries
			subtype.setSubtypeQueryResult(cachedResult);
		}

		return cachedResult;
	}

	/**
	 * Fill in supertype information for an object type.
	 * If it's a class type, also check whether it is
	 * a class or interface.
	 */
	private void resolveObjectType(ObjectType type) throws ClassNotFoundException {
		if (type.getState() != ObjectType.KNOWN) {
			if (type instanceof ArrayType) {
				resolveArrayClass((ArrayType) type);
			} else {
				resolveClass((ClassType) type);
			}
		}
	}

	private void resolveArrayClass(ArrayType type) throws ClassNotFoundException {
		// FIXME: avoid repeated failed attempts to resolve

		// The rule for arrays is:
		//
		// - Arrays whose element type is a basic type
		//   or java.lang.Object are direct subclasses of
		//   java.lang.Object
		//
		// - Arrays whose element type is a object type
		//   are direct subclasses arrays with the
		//   direct superclass of the element type as
		//   their element type

		ObjectType javaLangObjectType = classTypeFromSignature(JAVA_LANG_OBJECT_SIGNATURE);

		Type elementType = type.getElementType(this);

		if (elementType.isBasicType() || elementType.equals(javaLangObjectType)) {
			addSuperclassLink(type, javaLangObjectType);
		} else {
			ObjectType elementObjectType = (ObjectType) elementType;
			resolveObjectType(elementObjectType);
			for (Iterator<ObjectType> i = inheritanceGraph.successorIterator(elementObjectType); i.hasNext();) {
				ObjectType elementSupertype = i.next();
				ObjectType supertype = arrayTypeFromElementType(elementSupertype);
				addSuperclassLink(type, supertype);
			}
		}

		// All arrays implement Serializable and Cloneable
		addInterfaceLink(type, classTypeFromSignature("Ljava/io/Serializable;"));
		addInterfaceLink(type, classTypeFromSignature("Ljava/lang/Cloneable;"));

		type.setState(ObjectType.KNOWN);
	}

	private void resolveClass(ClassType type) throws ClassNotFoundException {
		// If previous attempt at resolution failed,
		// just throw an exception
		if (type.getState() == ObjectType.UNKNOWN)
			throw new ClassNotFoundException("Class " + type.getClassName() +
			        " cannot be resolved", type.getResolverFailure());

		// Delegate to the ClassResolver
		try {
			resolver.resolveClass(type, this);
			type.setState(ObjectType.KNOWN);

			// If the class is an interface, make it a direct
			// subclass of java.lang.Object.  This is a convenient
			// fiction that makes things a bit simpler.
			if (type.isInterface())
				addInterfaceLink(type, classTypeFromSignature(JAVA_LANG_OBJECT_SIGNATURE));
		} catch (ClassNotFoundException e) {
			type.setState(ObjectType.UNKNOWN);
			type.setResolverFailure(e);
			throw new ClassNotFoundException("Class " + type.getClassName() +
			        " cannot be resolved", e);
		}
	}
}

// vim:ts=4