typeanalysis.java

A static analysis tool to find bugs in Java programs

/*
 * Bytecode Analysis Framework
 * Copyright (C) 2003-2005 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.type;

import java.util.BitSet;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

import org.apache.bcel.Constants;
import org.apache.bcel.classfile.Attribute;
import org.apache.bcel.classfile.Code;
import org.apache.bcel.classfile.LocalVariable;
import org.apache.bcel.classfile.LocalVariableTypeTable;
import org.apache.bcel.classfile.Method;
import org.apache.bcel.generic.ATHROW;
import org.apache.bcel.generic.ArrayType;
import org.apache.bcel.generic.CodeExceptionGen;
import org.apache.bcel.generic.ConstantPoolGen;
import org.apache.bcel.generic.ExceptionThrower;
import org.apache.bcel.generic.Instruction;
import org.apache.bcel.generic.InstructionHandle;
import org.apache.bcel.generic.InvokeInstruction;
import org.apache.bcel.generic.MethodGen;
import org.apache.bcel.generic.ObjectType;
import org.apache.bcel.generic.ReferenceType;
import org.apache.bcel.generic.Type;

import edu.umd.cs.findbugs.DeepSubtypeAnalysis;
import edu.umd.cs.findbugs.SystemProperties;
import edu.umd.cs.findbugs.annotations.CheckForNull;
import edu.umd.cs.findbugs.ba.AnalysisContext;
import edu.umd.cs.findbugs.ba.AnalysisFeatures;
import edu.umd.cs.findbugs.ba.BasicBlock;
import edu.umd.cs.findbugs.ba.CFG;
import edu.umd.cs.findbugs.ba.CFGBuilderException;
import edu.umd.cs.findbugs.ba.ClassContext;
import edu.umd.cs.findbugs.ba.Dataflow;
import edu.umd.cs.findbugs.ba.DataflowAnalysis;
import edu.umd.cs.findbugs.ba.DataflowAnalysisException;
import edu.umd.cs.findbugs.ba.DataflowTestDriver;
import edu.umd.cs.findbugs.ba.DepthFirstSearch;
import edu.umd.cs.findbugs.ba.Edge;
import edu.umd.cs.findbugs.ba.EdgeTypes;
import edu.umd.cs.findbugs.ba.FrameDataflowAnalysis;
import edu.umd.cs.findbugs.ba.Hierarchy;
import edu.umd.cs.findbugs.ba.Location;
import edu.umd.cs.findbugs.ba.MissingClassException;
import edu.umd.cs.findbugs.ba.ObjectTypeFactory;
import edu.umd.cs.findbugs.ba.RepositoryLookupFailureCallback;
import edu.umd.cs.findbugs.ba.SignatureConverter;
import edu.umd.cs.findbugs.ba.generic.GenericObjectType;
import edu.umd.cs.findbugs.ba.generic.GenericSignatureParser;
import edu.umd.cs.findbugs.ba.generic.GenericUtilities;
import edu.umd.cs.findbugs.ba.vna.ValueNumber;
import edu.umd.cs.findbugs.ba.vna.ValueNumberDataflow;
import edu.umd.cs.findbugs.ba.vna.ValueNumberFrame;

/**
 * A forward dataflow analysis to determine the types of all values
 * in the Java stack frame at all points in a Java method.
 * The values include local variables and values on the Java operand stack.
 * <p/>
 * <p> As a side effect, the analysis computes the exception
 * set throwable on each exception edge in the CFG.
 * This information can be used to prune infeasible exception
 * edges, and mark exception edges which propagate only
 * implicit exceptions.
 *
 * @author David Hovemeyer
 * @see Dataflow
 * @see DataflowAnalysis
 * @see TypeFrame
 */
public class TypeAnalysis extends FrameDataflowAnalysis<Type, TypeFrame>
		implements EdgeTypes {

	public static final boolean DEBUG = SystemProperties.getBoolean("ta.debug");

	/**
	 * Force computation of accurate exceptions.
	 */
	public static final boolean FORCE_ACCURATE_EXCEPTIONS =SystemProperties.getBoolean("ta.accurateExceptions");

	/**
	 * Repository of information about thrown exceptions computed for
	 * a basic block and its outgoing exception edges.
	 * It contains a result TypeFrame, which is used to detect
	 * when the exception information needs to be recomputed
	 * for the block.
	 */
	private class CachedExceptionSet {
		private TypeFrame result;
		private ExceptionSet exceptionSet;
		private Map<Edge, ExceptionSet> edgeExceptionMap;

		public CachedExceptionSet(TypeFrame result, ExceptionSet exceptionSet) {
			this.result = result;
			this.exceptionSet = exceptionSet;
			this.edgeExceptionMap = new HashMap<Edge, ExceptionSet>();
		}

		public boolean isUpToDate(TypeFrame result) {
			return this.result.equals(result);
		}

		public ExceptionSet getExceptionSet() {
			return exceptionSet;
		}

		public void setEdgeExceptionSet(Edge edge, ExceptionSet exceptionSet) {
			edgeExceptionMap.put(edge, exceptionSet);
		}

		public ExceptionSet getEdgeExceptionSet(Edge edge) {
			ExceptionSet edgeExceptionSet = edgeExceptionMap.get(edge);
			if (edgeExceptionSet == null) {
				edgeExceptionSet = exceptionSetFactory.createExceptionSet();
				edgeExceptionMap.put(edge, edgeExceptionSet);
			}
			return edgeExceptionSet;
		}
	}

	/**
	 * Cached information about an instanceof check.
	 */
	static class InstanceOfCheck {
		final ValueNumber valueNumber;
		final Type type;

		InstanceOfCheck(ValueNumber valueNumber, Type type) {
			this.valueNumber = valueNumber;
			this.type = type;
		}

		/**
		 * @return Returns the valueNumber.
		 */
		public ValueNumber getValueNumber() {
			return valueNumber;
		}

		/**
		 * @return Returns the type.
		 */
		public Type getType() {
			return type;
		}
	}

	protected MethodGen methodGen;
	private final Method method;
	protected CFG cfg;
	private TypeMerger typeMerger;
	private TypeFrameModelingVisitor visitor;
	private LocalVariableTypeTable typeTable;
	private BitSet startOfLocalTypedVariables = new BitSet();
	private Map<BasicBlock, CachedExceptionSet> thrownExceptionSetMap;
	private RepositoryLookupFailureCallback lookupFailureCallback;
	private ExceptionSetFactory exceptionSetFactory;
	private ValueNumberDataflow valueNumberDataflow;
	private Map<BasicBlock, InstanceOfCheck> instanceOfCheckMap;

	/**
	 * Constructor.
	 * @param method TODO
	 * @param methodGen             the MethodGen whose CFG we'll be analyzing
	 * @param cfg                   the control flow graph
	 * @param dfs                   DepthFirstSearch of the method
	 * @param typeMerger            object to merge types
	 * @param visitor               a TypeFrameModelingVisitor to use to model the effect
	 *                              of instructions
	 * @param lookupFailureCallback lookup failure callback
	 * @param exceptionSetFactory   factory for creating ExceptionSet objects
	 */
	public TypeAnalysis(Method method, MethodGen methodGen, CFG cfg,
						DepthFirstSearch dfs, TypeMerger typeMerger,
						TypeFrameModelingVisitor visitor,
						RepositoryLookupFailureCallback lookupFailureCallback, ExceptionSetFactory exceptionSetFactory) {
		super(dfs);
		this.method = method;
		Code code = method.getCode();
		if (code == null) throw new IllegalArgumentException(method.getName() + " has no code");
		for(Attribute a : code.getAttributes()) {
			if (a instanceof LocalVariableTypeTable) {
				typeTable = (LocalVariableTypeTable) a;
				for (LocalVariable v : typeTable.getLocalVariableTable()) {
					int startPC = v.getStartPC();
					if (startPC >= 0) startOfLocalTypedVariables.set(startPC);
				}
			}
		}
		this.methodGen = methodGen;
		this.cfg = cfg;
		this.typeMerger = typeMerger;
		this.visitor = visitor;
		this.thrownExceptionSetMap = new HashMap<BasicBlock, CachedExceptionSet>();
		this.lookupFailureCallback = lookupFailureCallback;
		this.exceptionSetFactory = exceptionSetFactory;
		this.instanceOfCheckMap = new HashMap<BasicBlock, InstanceOfCheck>();
		if (DEBUG) {
			System.out.println("\n\nAnalyzing " + methodGen);
		}
	}

	/**
	 * Constructor.
	 * @param method TODO
	 * @param methodGen             the MethodGen whose CFG we'll be analyzing
	 * @param cfg                   the control flow graph
	 * @param dfs                   DepthFirstSearch of the method
	 * @param typeMerger            object to merge types
	 * @param lookupFailureCallback lookup failure callback
	 * @param exceptionSetFactory   factory for creating ExceptionSet objects
	 */
	public TypeAnalysis(Method method, MethodGen methodGen, CFG cfg,
						DepthFirstSearch dfs, TypeMerger typeMerger,
						RepositoryLookupFailureCallback lookupFailureCallback, ExceptionSetFactory exceptionSetFactory) {
		this(method, methodGen, cfg, dfs,
				typeMerger, new TypeFrameModelingVisitor(methodGen.getConstantPool()),
				lookupFailureCallback, exceptionSetFactory);
	}

	/**
	 * Constructor which uses StandardTypeMerger.
	 * @param method TODO
	 * @param methodGen             the MethodGen whose CFG we'll be analyzing
	 * @param cfg                   the control flow graph
	 * @param dfs                   DepthFirstSearch of the method
	 * @param lookupFailureCallback callback for Repository lookup failures
	 * @param exceptionSetFactory   factory for creating ExceptionSet objects
	 */
	public TypeAnalysis(Method method, MethodGen methodGen, CFG cfg,
						DepthFirstSearch dfs,
						RepositoryLookupFailureCallback lookupFailureCallback, ExceptionSetFactory exceptionSetFactory) {
		this(method, methodGen, cfg, dfs,
				new StandardTypeMerger(lookupFailureCallback, exceptionSetFactory),
				lookupFailureCallback, exceptionSetFactory);
	}

	/**
	 * Set the ValueNumberDataflow for the method being analyzed.
	 * This is optional; if set, it will be used to make instanceof
	 * instructions more precise.
	 * 
	 * @param valueNumberDataflow the ValueNumberDataflow
	 */
	public void setValueNumberDataflow(ValueNumberDataflow valueNumberDataflow) {
		this.valueNumberDataflow = valueNumberDataflow;
		this.visitor.setValueNumberDataflow(valueNumberDataflow);
	}

	/**
	 * Set the FieldStoreTypeDatabase.
	 * This can be used to get more accurate types for values loaded
	 * from fields.
	 * 
	 * @param database the FieldStoreTypeDatabase 
	 */
	public void setFieldStoreTypeDatabase(FieldStoreTypeDatabase database) {
		visitor.setFieldStoreTypeDatabase(database);
	}

	/**
	 * Get the set of exceptions that can be thrown on given edge.
	 * This should only be called after the analysis completes.
	 *
	 * @param edge the Edge
	 * @return the ExceptionSet
	 */
	public ExceptionSet getEdgeExceptionSet(Edge edge) {
		CachedExceptionSet cachedExceptionSet = thrownExceptionSetMap.get(edge.getSource());
		return cachedExceptionSet.getEdgeExceptionSet(edge);
	}

	public TypeFrame createFact() {
		return new TypeFrame(methodGen.getMaxLocals());
	}

	public void initEntryFact(TypeFrame result) {
		// Make the frame valid
		result.setValid();

		int slot = 0;

		// Clear the stack slots in the frame
		result.clearStack();

		// Add local for "this" pointer, if present
		if (!methodGen.isStatic())