hierarchy.java

A static analysis tool to find bugs in Java programs

/*
 * Bytecode Analysis Framework
 * Copyright (C) 2003,2004 University of Maryland
 * 
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 * 
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

package edu.umd.cs.findbugs.ba;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import org.apache.bcel.Constants;
import org.apache.bcel.Repository;
import org.apache.bcel.classfile.ExceptionTable;
import org.apache.bcel.classfile.Field;
import org.apache.bcel.classfile.JavaClass;
import org.apache.bcel.classfile.Method;
import org.apache.bcel.generic.ArrayType;
import org.apache.bcel.generic.ConstantPoolGen;
import org.apache.bcel.generic.FieldInstruction;
import org.apache.bcel.generic.INVOKESTATIC;
import org.apache.bcel.generic.Instruction;
import org.apache.bcel.generic.InvokeInstruction;
import org.apache.bcel.generic.ObjectType;
import org.apache.bcel.generic.ReferenceType;
import org.apache.bcel.generic.Type;

import edu.umd.cs.findbugs.SystemProperties;
import edu.umd.cs.findbugs.annotations.CheckForNull;
import edu.umd.cs.findbugs.annotations.NonNull;
import edu.umd.cs.findbugs.ba.type.TypeFrame;

/**
 * Facade for class hierarchy queries.
 * These typically access the class hierarchy using
 * the {@link org.apache.bcel.Repository} class.  Callers should generally
 * expect to handle ClassNotFoundException for when referenced
 * classes can't be found.
 *
 * @author David Hovemeyer
 */
public class Hierarchy {
	private static final boolean DEBUG_METHOD_LOOKUP =
		SystemProperties.getBoolean("hier.lookup.debug");

	/**
	 * Type of java.lang.Exception.
	 */
	public static final ObjectType EXCEPTION_TYPE = ObjectTypeFactory.getInstance("java.lang.Exception");
	/**
	 * Type of java.lang.Error.
	 */
	public static final ObjectType ERROR_TYPE = ObjectTypeFactory.getInstance("java.lang.Error");
	/**
	 * Type of java.lang.RuntimeException.
	 */
	public static final ObjectType RUNTIME_EXCEPTION_TYPE = ObjectTypeFactory.getInstance("java.lang.RuntimeException");

	/**
	 * Determine whether one class (or reference type) is a subtype
	 * of another.
	 *
	 * @param clsName                    the name of the class or reference type
	 * @param possibleSupertypeClassName the name of the possible superclass
	 * @return true if clsName is a subtype of possibleSupertypeClassName,
	 *         false if not
	 */
	public static boolean isSubtype(String clsName, String possibleSupertypeClassName) throws ClassNotFoundException {
		ObjectType cls = ObjectTypeFactory.getInstance(clsName);
		ObjectType superCls = ObjectTypeFactory.getInstance(possibleSupertypeClassName);
		return isSubtype(cls, superCls);
	}

	/**
	 * Determine if one reference type is a subtype of another.
	 *
	 * @param t                 a reference type
	 * @param possibleSupertype the possible supertype
	 * @return true if t is a subtype of possibleSupertype,
	 *         false if not
	 */
	public static boolean isSubtype(ReferenceType t, ReferenceType possibleSupertype) throws ClassNotFoundException {
		Map<ReferenceType, Boolean> subtypes = subtypeCache.get(possibleSupertype);
		if (subtypes == null) {
			subtypes = new HashMap<ReferenceType, Boolean>();
			subtypeCache.put(possibleSupertype, subtypes);
		}
		Boolean result = subtypes.get(t);
		if (result == null) {
			result = Boolean.valueOf(t.isAssignmentCompatibleWith(possibleSupertype));
			subtypes.put(t, result);
		}
		return result;
	}

	static Map<ReferenceType, Map<ReferenceType, Boolean>> subtypeCache = new HashMap<ReferenceType, Map<ReferenceType, Boolean>> ();
	/**
	 * Determine if the given ObjectType reference represents
	 * a <em>universal</em> exception handler.  That is,
	 * one that will catch any kind of exception.
	 *
	 * @param catchType the ObjectType of the exception handler
	 * @return true if catchType is null, or if catchType is
	 *         java.lang.Throwable
	 */
	public static boolean isUniversalExceptionHandler(ObjectType catchType) {
		return catchType == null || catchType.equals(Type.THROWABLE);
	}

	/**
	 * Determine if the given ObjectType refers to an unchecked
	 * exception (RuntimeException or Error).
	 */
	public static boolean isUncheckedException(ObjectType type) throws ClassNotFoundException {
		return isSubtype(type, RUNTIME_EXCEPTION_TYPE) || isSubtype(type, ERROR_TYPE);
	}

	/**
	 * Determine if method whose name and signature is specified
	 * is a monitor wait operation.
	 *
	 * @param methodName name of the method
	 * @param methodSig  signature of the method
	 * @return true if the method is a monitor wait, false if not
	 */
	public static boolean isMonitorWait(String methodName, String methodSig) {
		return methodName.equals("wait") &&
				(methodSig.equals("()V") || methodSig.equals("(J)V") || methodSig.equals("(JI)V"));
	}

	/**
	 * Determine if given Instruction is a monitor wait.
	 * 
	 * @param ins the Instruction
	 * @param cpg the ConstantPoolGen for the Instruction
	 *
	 * @return true if the instruction is a monitor wait, false if not
	 */
	public static boolean isMonitorWait(Instruction ins, ConstantPoolGen cpg) {
		if (!(ins instanceof InvokeInstruction))
			return false;
		if (ins.getOpcode() == Constants.INVOKESTATIC)
			return false;

		InvokeInstruction inv = (InvokeInstruction) ins;
		String methodName = inv.getMethodName(cpg);
		String methodSig = inv.getSignature(cpg);

		return isMonitorWait(methodName, methodSig);
	}

	/**
	 * Determine if method whose name and signature is specified
	 * is a monitor notify operation.
	 *
	 * @param methodName name of the method
	 * @param methodSig  signature of the method
	 * @return true if the method is a monitor notify, false if not
	 */
	public static boolean isMonitorNotify(String methodName, String methodSig) {
		return (methodName.equals("notify") || methodName.equals("notifyAll")) &&
				methodSig.equals("()V");
	}
	/**
	 * Determine if given Instruction is a monitor wait.
	 * 
	 * @param ins the Instruction
	 * @param cpg the ConstantPoolGen for the Instruction
	 *
	 * @return true if the instruction is a monitor wait, false if not
	 */
	public static boolean isMonitorNotify(Instruction ins, ConstantPoolGen cpg) {
		if (!(ins instanceof InvokeInstruction))
			return false;
		if (ins.getOpcode() == Constants.INVOKESTATIC)
			return false;

		InvokeInstruction inv = (InvokeInstruction) ins;
		String methodName = inv.getMethodName(cpg);
		String methodSig = inv.getSignature(cpg);

		return isMonitorNotify(methodName, methodSig);
	}

	/**
	 * Look up the method referenced by given InvokeInstruction.
	 * This method does <em>not</em> look for implementations in
	 * super or subclasses according to the virtual dispatch rules.
	 *
	 * @param inv the InvokeInstruction
	 * @param cpg the ConstantPoolGen used by the class the InvokeInstruction belongs to
	 * @return the JavaClassAndMethod, or null if no such method is defined in the class
	 */
	public static JavaClassAndMethod findExactMethod(InvokeInstruction inv, ConstantPoolGen cpg) throws ClassNotFoundException {
		return findExactMethod(inv, cpg, ANY_METHOD);
	}

	/**
	 * Look up the method referenced by given InvokeInstruction.
	 * This method does <em>not</em> look for implementations in
	 * super or subclasses according to the virtual dispatch rules.
	 *
	 * @param inv     the InvokeInstruction
	 * @param cpg     the ConstantPoolGen used by the class the InvokeInstruction belongs to
	 * @param chooser JavaClassAndMethodChooser to use to pick the method from among the candidates
	 * @return the JavaClassAndMethod, or null if no such method is defined in the class
	 */
	public static JavaClassAndMethod findExactMethod(
			InvokeInstruction inv,
			ConstantPoolGen cpg,
			JavaClassAndMethodChooser chooser) throws ClassNotFoundException {
		String className = inv.getClassName(cpg);
		String methodName = inv.getName(cpg);
		String methodSig = inv.getSignature(cpg);

		JavaClass jclass = Repository.lookupClass(className);
		return findMethod(jclass, methodName, methodSig, chooser);
	}

	/**
	 * Visit all superclass methods which the given method overrides. 
	 * 
	 * @param method  the method
	 * @param chooser chooser which visits each superclass method
	 * @return the chosen method, or null if no method is chosen
	 * @throws ClassNotFoundException
	 */
	public static JavaClassAndMethod visitSuperClassMethods(
			JavaClassAndMethod method, JavaClassAndMethodChooser chooser) throws ClassNotFoundException {
		return findMethod(
				method.getJavaClass().getSuperClasses(),
				method.getMethod().getName(),
				method.getMethod().getSignature(),
				chooser);
	}

	/**
	 * Visit all superinterface methods which the given method implements. 
	 * 
	 * @param method  the method
	 * @param chooser chooser which visits each superinterface method
	 * @return the chosen method, or null if no method is chosen
	 * @throws ClassNotFoundException
	 */
	public static JavaClassAndMethod visitSuperInterfaceMethods(
			JavaClassAndMethod method, JavaClassAndMethodChooser chooser) throws ClassNotFoundException {
		return findMethod(
				method.getJavaClass().getAllInterfaces(),
				method.getMethod().getName(),
				method.getMethod().getSignature(),
				chooser);
	}

	/**
	 * Find the least upper bound method in the class hierarchy
	 * which could be called by the given InvokeInstruction.
	 * One reason this method is useful is that it indicates 
	 * which declared exceptions are thrown by the called methods.
	 * 
	 * <p/>
	 * <ul>
	 * <li> For  invokespecial, this is simply an
	 * exact lookup.
	 * <li> For invokestatic and invokevirtual, the named class is searched,
	 * followed by superclasses  up to the root of the object
	 * hierarchy (java.lang.Object).  Yes, invokestatic really is declared
	 * to check superclasses.  See VMSpec, 2nd ed, sec. 5.4.3.3.
	 * <li> For invokeinterface, the named class is searched,
	 * followed by all interfaces transitively declared by the class.
	 * (Question: is the order important here? Maybe the VM spec
	 * requires that the actual interface desired is given,
	 * so the extended lookup will not be required. Should check.)
	 * </ul>
	 *
	 * @param inv           the InvokeInstruction
	 * @param cpg           the ConstantPoolGen used by the class the InvokeInstruction belongs to
	 * @return the JavaClassAndMethod, or null if no matching method can be found
	 */
	public static JavaClassAndMethod findInvocationLeastUpperBound(
			InvokeInstruction inv, ConstantPoolGen cpg)
			throws ClassNotFoundException {
		return findInvocationLeastUpperBound(inv, cpg, ANY_METHOD);
	}

	public static JavaClassAndMethod findInvocationLeastUpperBound(
			InvokeInstruction inv, ConstantPoolGen cpg, JavaClassAndMethodChooser methodChooser)
			throws ClassNotFoundException {
		JavaClassAndMethod result;

		if (DEBUG_METHOD_LOOKUP) {
			System.out.println("Find prototype method for " +