typeframemodelingvisitor.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 org.apache.bcel.Constants;
import org.apache.bcel.classfile.Attribute;
import org.apache.bcel.classfile.Field;
import org.apache.bcel.classfile.Signature;
import org.apache.bcel.generic.*;

import edu.umd.cs.findbugs.ba.AbstractFrameModelingVisitor;
import edu.umd.cs.findbugs.ba.AnalysisContext;
import edu.umd.cs.findbugs.ba.DataflowAnalysisException;
import edu.umd.cs.findbugs.ba.Debug;
import edu.umd.cs.findbugs.ba.Hierarchy;
import edu.umd.cs.findbugs.ba.InvalidBytecodeException;
import edu.umd.cs.findbugs.ba.Location;
import edu.umd.cs.findbugs.ba.ObjectTypeFactory;
import edu.umd.cs.findbugs.ba.XField;
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;

/**
 * Visitor to model the effects of bytecode instructions on the
 * types of the values (local and operand stack) in Java stack frames.
 * This visitor does not verify that the types are sensible
 * for the bytecodes executed.  In other words, this isn't a bytecode
 * verifier, although it wouldn't be too hard to turn it into
 * something vaguely verifier-like.
 *
 * @author David Hovemeyer
 * @see TypeFrame
 * @see TypeAnalysis
 */
public class TypeFrameModelingVisitor extends AbstractFrameModelingVisitor<Type, TypeFrame>
		implements Constants, Debug {

	static private final  ObjectType COLLECTION_TYPE = ObjectTypeFactory.getInstance("java.util.Collection");

	private ValueNumberDataflow valueNumberDataflow;

	// Fields for precise modeling of instanceof instructions.
	private short lastOpcode;
	private boolean instanceOfFollowedByBranch;
	private Type instanceOfType;
	private ValueNumber instanceOfValueNumber;

	private FieldStoreTypeDatabase database;

	/**
	 * Constructor.
	 *
	 * @param cpg the ConstantPoolGen of the method whose instructions we are examining
	 */
	public TypeFrameModelingVisitor(ConstantPoolGen cpg) {
		super(cpg);
	}

	/**
	 * Set ValueNumberDataflow for the method being analyzed.
	 * This is optional; if set, we will use the information to more
	 * accurately model the effects of instanceof instructions.
	 * 
	 * @param valueNumberDataflow the ValueNumberDataflow
	 */
	public void setValueNumberDataflow(ValueNumberDataflow valueNumberDataflow) {
		this.valueNumberDataflow = valueNumberDataflow;
	}

	/**
	 * Get the last opcode analyzed by this visitor.
	 * The TypeAnalysis may use this to get more precise types in
	 * the resulting frame.
	 * 
	 * @return the last opcode analyzed by this visitor
	 */
	public short getLastOpcode() {
		return lastOpcode;
	}

	/**
	 * Return whether an instanceof instruction was followed by a branch.
	 * The TypeAnalysis may use this to get more precise types in
	 * the resulting frame.
	 * 
	 * @return true if an instanceof instruction was followed by a branch,
	 *         false if not
	 */
	public boolean isInstanceOfFollowedByBranch() {
		return instanceOfFollowedByBranch;
	}

	/**
	 * Get the type of the most recent instanceof instruction modeled.
	 * The TypeAnalysis may use this to get more precise types in
	 * the resulting frame.
	 * 
	 * @return the Type checked by the most recent instanceof instruction
	 */
	public Type getInstanceOfType() {
		return instanceOfType;
	}

	/**
	 * Get the value number of the most recent instanceof instruction modeled.
	 * The TypeAnalysis may use this to get more precise types in
	 * the resulting frame.
	 * 
	 * @return the ValueNumber checked by the most recent instanceof instruction
	 */
	public ValueNumber getInstanceOfValueNumber() {
		return instanceOfValueNumber;
	}

	/**
	 * Set the field store type database.
	 * We can use this to get more accurate types for values loaded
	 * from fields.
	 * 
	 * @param database the FieldStoreTypeDatabase
	 */
	public void setFieldStoreTypeDatabase(FieldStoreTypeDatabase database) {
		this.database = database;
	}

	@Override
	public Type getDefaultValue() {
		return TypeFrame.getBottomType();
	}

	@Override
	public void analyzeInstruction(Instruction ins) throws DataflowAnalysisException {
		instanceOfFollowedByBranch = false;
		super.analyzeInstruction(ins);
		lastOpcode = ins.getOpcode();
	}

	/**
	 * This method must be called at the beginning of modeling
	 * a basic block in order to clear information cached
	 * for instanceof modeling.
	 */
	public void startBasicBlock() {
		lastOpcode = -1;
		instanceOfType = null;
		instanceOfValueNumber = null;
	}

	/**
	 * Consume stack.  This is a convenience method for instructions
	 * where the types of popped operands can be ignored.
	 */
	protected void consumeStack(Instruction ins) {
		ConstantPoolGen cpg = getCPG();
		TypeFrame frame = getFrame();

		int numWordsConsumed = ins.consumeStack(cpg);
		if (numWordsConsumed == Constants.UNPREDICTABLE)
			throw new InvalidBytecodeException("Unpredictable stack consumption for " + ins);
		try {
			while (numWordsConsumed-- > 0) {
				frame.popValue();
			}
		} catch (DataflowAnalysisException e) {
			throw new InvalidBytecodeException("Stack underflow for " + ins + ": " + e.getMessage());
		}
	}

	/**
	 * Work around some weirdness in BCEL (inherited from JVM Spec 1):
	 * BCEL considers long and double types to consume two slots on the
	 * stack.  This method ensures that we push two types for
	 * each double or long value.
	 */
	protected void pushValue(Type type) {
		TypeFrame frame = getFrame();
		if (type.getType() == T_LONG) {
			frame.pushValue(Type.LONG);
			frame.pushValue(TypeFrame.getLongExtraType());
		} else if (type.getType() == T_DOUBLE) {
			frame.pushValue(Type.DOUBLE);
			frame.pushValue(TypeFrame.getDoubleExtraType());
		} else
			frame.pushValue(type);
	}

	/**
	 * Helper for pushing the return type of an invoke instruction.
	 */
	protected void pushReturnType(InvokeInstruction ins) {
		ConstantPoolGen cpg = getCPG();
		Type type = ins.getType(cpg);
		if (type.getType() != T_VOID)
			pushValue(type);
	}

	/**
	 * This is overridden only to ensure that we don't rely on the
	 * base class to handle instructions that produce stack operands.
	 */
	@Override
	public void modelNormalInstruction(Instruction ins, int numWordsConsumed, int numWordsProduced) {
		if (VERIFY_INTEGRITY) {
			if (numWordsProduced > 0)
				throw new InvalidBytecodeException("missing visitor method for " + ins);
		}
		super.modelNormalInstruction(ins, numWordsConsumed, numWordsProduced);
	}

	// ----------------------------------------------------------------------
	// Instruction visitor methods
	// ----------------------------------------------------------------------

	// NOTES:
	// - Instructions that only consume operands need not be overridden,
	//   because the base class visit methods handle them correctly.
	// - Instructions that simply move values around in the frame,
	//   such as DUP, xLOAD, etc., do not need to be overridden because
	//   the base class handles them.
	// - Instructions that consume and produce should call
	//   consumeStack(Instruction) and then explicitly push produced operands.

	@Override
	public void visitATHROW(ATHROW obj) {
		// do nothing. The same value remains on the stack (but we jump to a new location)
	}

	@Override
	public void visitACONST_NULL(ACONST_NULL obj) {
		pushValue(TypeFrame.getNullType());
	}

	@Override
	public void visitDCONST(DCONST obj) {
		pushValue(Type.DOUBLE);
	}

	@Override
	public void visitFCONST(FCONST obj) {
		pushValue(Type.FLOAT);
	}

	@Override
	public void visitICONST(ICONST obj) {
		pushValue(Type.INT);
	}

	@Override
	public void visitLCONST(LCONST obj) {
		pushValue(Type.LONG);
	}

	@Override
	public void visitLDC(LDC obj) {
		pushValue(obj.getType(getCPG()));
	}

	@Override
	public void visitLDC2_W(LDC2_W obj) {
		pushValue(obj.getType(getCPG()));
	}

	@Override
	public void visitBIPUSH(BIPUSH obj) {
		pushValue(Type.INT);
	}

	@Override
	public void visitSIPUSH(SIPUSH obj) {
		pushValue(Type.INT);
	}

	@Override
	public void visitGETSTATIC(GETSTATIC obj) {
		modelFieldLoad(obj);
	}

	@Override
		 public void visitGETFIELD(GETFIELD obj) {
		modelFieldLoad(obj);
	}

	public void modelFieldLoad(FieldInstruction obj) {
		consumeStack(obj);

		Type loadType = obj.getType(getCPG());
		Type originalLoadType = loadType;

		try {
			// Check the field store type database to see if we can
			// get a more precise type for this load.
			XField xfield = Hierarchy.findXField(obj, getCPG());
			if (database != null && (loadType instanceof ReferenceType) && xfield != null) {
				FieldStoreType property = database.getProperty(xfield);
				if (property != null) {
					loadType = property.getLoadType((ReferenceType) loadType);
				}
			}

			// [Added: Support for Generics]
			// XXX If the loadType was not changed by the FieldStoreTypeDatabase, then
			// we can assume, that the signature for obj is still relevant. This should
			// be updated by inserting generic information in the FieldStoreTypeDatabase
			if (originalLoadType.equals(loadType) && xfield != null) {
				// find the field and its signature
				Field field = Hierarchy.findField(xfield.getClassName(), xfield.getName());
				String signature = null;
				for (Attribute a : field.getAttributes()) {
					if (a instanceof Signature) {
						signature = ((Signature) a).getSignature();
						break;
					}
				}

				// replace loadType with information from field signature (conservative)
				if (signature != null && 
					(loadType instanceof ObjectType || loadType instanceof ArrayType) &&
					!(loadType instanceof ExceptionObjectType)
					) {
					loadType = GenericUtilities.getType( signature );
				}
			}
		} catch (ClassNotFoundException e) {
			AnalysisContext.reportMissingClass(e);
		} catch (RuntimeException e) {} // degrade gracefully

		pushValue(loadType);
	}

	@Override
	public void visitINVOKESTATIC(INVOKESTATIC obj) {
		consumeStack(obj);
		pushReturnType(obj);
	}

	@Override
	public void visitINVOKESPECIAL(INVOKESPECIAL obj) {
		consumeStack(obj);
		pushReturnType(obj);
	}

	@Override
	public void visitINVOKEINTERFACE(INVOKEINTERFACE obj) {
		if (handleToArray(obj)) return;
		consumeStack(obj);
		pushReturnType(obj);
	}

	@Override
	public void visitINVOKEVIRTUAL(INVOKEVIRTUAL obj) {
		TypeFrame frame = getFrame();
		if (obj.getMethodName(cpg).equals("initCause") && obj.getSignature(cpg).equals("(Ljava/lang/Throwable;)Ljava/lang/Throwable;") && obj.getClassName(cpg).endsWith("Exception")) {
			try {

				frame.popValue();
				return;
			} catch (DataflowAnalysisException e) {

			}
		}
		if (handleToArray(obj)) return;
		consumeStack(obj);
		pushReturnType(obj);
	}

	private boolean handleToArray(InvokeInstruction obj) {
		try {
		TypeFrame frame = getFrame();
		if (obj.getName(getCPG()).equals("toArray")) {
			ReferenceType target = obj.getReferenceType(getCPG());
			String signature = obj.getSignature(getCPG());
			if (signature.equals("([Ljava/lang/Object;)[Ljava/lang/Object;") && target.isAssignmentCompatibleWith(COLLECTION_TYPE)) {

				boolean topIsExact = frame.isExact(frame.getStackLocation(0));
				Type resultType = frame.popValue();
				frame.popValue();
				frame.pushValue(resultType);
				frame.setExact(frame.getStackLocation(0), topIsExact);
				return true;
			} else if (signature.equals("()[Ljava/lang/Object;")) {
				consumeStack(obj);
				pushReturnType(obj);
				frame.setExact(frame.getStackLocation(0), true);
				return true;
			}
		}
		return false;
		} catch (DataflowAnalysisException e) {
			return false;
		} catch (ClassNotFoundException e) {
			AnalysisContext.reportMissingClass(e);
			return false;
		}
	}
	@Override
	public void visitCHECKCAST(CHECKCAST obj) {
		consumeStack(obj);
		pushValue(obj.getType(getCPG()));
	}

	@Override
	public void visitINSTANCEOF(INSTANCEOF obj) {
		if (valueNumberDataflow != null) {
			// Record the value number of the value checked by this instruction,
			// and the type the value was compared to.
			try {
				ValueNumberFrame vnaFrame = valueNumberDataflow.getFactAtLocation(getLocation());
				if (vnaFrame.isValid()) {
					instanceOfValueNumber = vnaFrame.getTopValue();
					instanceOfType = obj.getType(getCPG());
				}
			} catch (DataflowAnalysisException e) {
				// Ignore
			}
		}


		consumeStack(obj);
		pushValue(Type.INT);
	}

	@Override
	public void visitIFNULL(IFNULL obj) {

		if (valueNumberDataflow != null) {
			// Record the value number of the value checked by this instruction,
			// and the type the value was compared to.
			try {
				ValueNumberFrame vnaFrame = valueNumberDataflow
						.getFactAtLocation(getLocation());
				if (vnaFrame.isValid()) {
					instanceOfValueNumber = vnaFrame.getTopValue();

					instanceOfType = NullType.instance();
					instanceOfFollowedByBranch = true;
				}
			} catch (DataflowAnalysisException e) {
				// Ignore
			}
		}

		consumeStack(obj);
	}
	@Override
	public void visitIFNONNULL(IFNONNULL obj) {

		if (valueNumberDataflow != null) {
			// Record the value number of the value checked by this instruction,
			// and the type the value was compared to.
			try {
				ValueNumberFrame vnaFrame = valueNumberDataflow
						.getFactAtLocation(getLocation());
				if (vnaFrame.isValid()) {
					instanceOfValueNumber = vnaFrame.getTopValue();

					instanceOfType = NullType.instance();
					instanceOfFollowedByBranch = true;
				}
			} catch (DataflowAnalysisException e) {
				// Ignore
			}
		}

		consumeStack(obj);
	}
	@Override
	public void visitFCMPL(FCMPL obj) {
		consumeStack(obj);
		pushValue(Type.INT);