typeanalysis.java

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

/*
 * 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.*;

import org.apache.bcel.Constants;
import org.apache.bcel.classfile.Method;
import org.apache.bcel.generic.*;

/**
 * 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 {

	private static final boolean DEBUG = Boolean.getBoolean("ta.debug");

	/**
	 * Compute what kinds of exceptions can propagate
	 * on each exception edge.
	 */
	private static final boolean ACCURATE_EXCEPTIONS =
	        Boolean.getBoolean("ta.accurateExceptions") || ClassContext.PRUNE_INFEASIBLE_EXCEPTION_EDGES;

	/**
	 * 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;
		}
	}

	private MethodGen methodGen;
	private CFG cfg;
	private TypeMerger typeMerger;
	private TypeFrameModelingVisitor visitor;
	private Map<BasicBlock, CachedExceptionSet> thrownExceptionSetMap;
	private RepositoryLookupFailureCallback lookupFailureCallback;
	private ExceptionSetFactory exceptionSetFactory;

	/**
	 * Constructor.
	 *
	 * @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(MethodGen methodGen, CFG cfg, DepthFirstSearch dfs,
	                    TypeMerger typeMerger, TypeFrameModelingVisitor visitor,
	                    RepositoryLookupFailureCallback lookupFailureCallback,
	                    ExceptionSetFactory exceptionSetFactory) {
		super(dfs);
		this.methodGen = methodGen;
		this.cfg = cfg;
		this.typeMerger = typeMerger;
		this.visitor = visitor;
		this.thrownExceptionSetMap = new HashMap<BasicBlock, CachedExceptionSet>();
		this.lookupFailureCallback = lookupFailureCallback;
		this.exceptionSetFactory = exceptionSetFactory;
	}

	/**
	 * Constructor.
	 *
	 * @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(MethodGen methodGen, CFG cfg, DepthFirstSearch dfs,
	                    TypeMerger typeMerger, RepositoryLookupFailureCallback lookupFailureCallback,
	                    ExceptionSetFactory exceptionSetFactory) {
		this(methodGen, cfg, dfs, typeMerger,
		        new TypeFrameModelingVisitor(methodGen.getConstantPool()), lookupFailureCallback,
		        exceptionSetFactory);
	}

	/**
	 * Constructor which uses StandardTypeMerger.
	 *
	 * @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(MethodGen methodGen, CFG cfg, DepthFirstSearch dfs,
	                    RepositoryLookupFailureCallback lookupFailureCallback,
	                    ExceptionSetFactory exceptionSetFactory) {
		this(methodGen, cfg, dfs,
		        new StandardTypeMerger(lookupFailureCallback, exceptionSetFactory),
		        lookupFailureCallback, exceptionSetFactory);
	}

	/**
	 * 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())
			result.setValue(slot++, new ObjectType(methodGen.getClassName()));

		// Add locals for parameters.
		// Note that long and double parameters need to be handled
		// specially because they occupy two locals.
		Type[] argumentTypes = methodGen.getArgumentTypes();
		for (int i = 0; i < argumentTypes.length; ++i) {
			Type argType = argumentTypes[i];

			// Add special "extra" type for long or double params.
			// These occupy the slot before the "plain" type.
			if (argType.getType() == Constants.T_LONG) {
				result.setValue(slot++, TypeFrame.getLongExtraType());
			} else if (argType.getType() == Constants.T_DOUBLE) {
				result.setValue(slot++, TypeFrame.getDoubleExtraType());
			}

			// Add the plain parameter type.
			result.setValue(slot++, argType);
		}

		// Set remaining locals to BOTTOM; this will cause any
		// uses of them to be flagged
		while (slot < methodGen.getMaxLocals())
			result.setValue(slot++, TypeFrame.getBottomType());
	}

	public void copy(TypeFrame source, TypeFrame dest) {
		dest.copyFrom(source);
	}

	public void initResultFact(TypeFrame result) {
		// This is important.  Sometimes we need to use a result value
		// before having a chance to initialize it.  We don't want such
		// values to corrupt other TypeFrame values that we merge them with.
		// So, all result values must be TOP.
		result.setTop();
	}

	public void makeFactTop(TypeFrame fact) {
		fact.setTop();
	}

	public boolean isFactValid(TypeFrame fact) {
		return fact.isValid();
	}

	public boolean same(TypeFrame fact1, TypeFrame fact2) {
		return fact1.sameAs(fact2);
	}

	public void transferInstruction(InstructionHandle handle, BasicBlock basicBlock, TypeFrame fact)
	        throws DataflowAnalysisException {
		visitor.setFrame(fact);
		handle.getInstruction().accept(visitor);
	}

	public void endTransfer(BasicBlock basicBlock, InstructionHandle end, Object result)
	        throws DataflowAnalysisException {

		// Do nothing if we're not computing propagated exceptions
		if (!ACCURATE_EXCEPTIONS)
			return;

		// Also, nothing to do if the block is not an exception thrower
		if (!basicBlock.isExceptionThrower())
			return;

		// If cached results are up to date, don't recompute.
		CachedExceptionSet cachedExceptionSet = getCachedExceptionSet(basicBlock);
		if (cachedExceptionSet.isUpToDate((TypeFrame) result))
			return;

		// Figure out what exceptions can be thrown out
		// of the basic block, and mark each exception edge
		// with the set of exceptions which can be propagated
		// along the edge.

		// Compute exceptions that can be thrown by the
		// basic block.
		cachedExceptionSet = computeBlockExceptionSet(basicBlock, (TypeFrame) result);

		// For each outgoing exception edge, compute exceptions
		// that can be thrown.  This assumes that the exception
		// edges are enumerated in decreasing order of priority.
		// In the process, this will remove exceptions from
		// the thrown exception set.
		ExceptionSet thrownExceptionSet = cachedExceptionSet.getExceptionSet().duplicate();
		for (Iterator<Edge> i = cfg.outgoingEdgeIterator(basicBlock); i.hasNext();) {
			Edge edge = i.next();
			if (!edge.isExceptionEdge())
				continue;

			cachedExceptionSet.setEdgeExceptionSet(edge, computeEdgeExceptionSet(edge, thrownExceptionSet));
		}
	}

	public void meetInto(TypeFrame fact, Edge edge, TypeFrame result) throws DataflowAnalysisException {
		BasicBlock basicBlock = edge.getTarget();

		if (basicBlock.isExceptionHandler() && fact.isValid()) {
			// Special case: when merging predecessor facts for entry to
			// an exception handler, we clear the stack and push a
			// single entry for the exception object.  That way, the locals
			// can still be merged.
			CodeExceptionGen exceptionGen = basicBlock.getExceptionGen();
			TypeFrame tmpFact = createFact();
			tmpFact.copyFrom(fact);
			tmpFact.clearStack();

			// Determine the type of exception(s) caught.
			Type catchType = null;