isnullvalueanalysis.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.npe;

import java.util.BitSet;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

import org.apache.bcel.Constants;
import org.apache.bcel.classfile.Method;
import org.apache.bcel.generic.CodeExceptionGen;
import org.apache.bcel.generic.Instruction;
import org.apache.bcel.generic.InstructionHandle;
import org.apache.bcel.generic.MethodGen;
import org.apache.bcel.generic.ObjectType;

import edu.umd.cs.findbugs.SystemProperties;
import edu.umd.cs.findbugs.annotations.CheckForNull;
import edu.umd.cs.findbugs.annotations.Nullable;
import edu.umd.cs.findbugs.ba.AnalysisContext;
import edu.umd.cs.findbugs.ba.AnalysisFeatures;
import edu.umd.cs.findbugs.ba.AssertionMethods;
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.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.JavaClassAndMethod;
import edu.umd.cs.findbugs.ba.Location;
import edu.umd.cs.findbugs.ba.NullnessAnnotation;
import edu.umd.cs.findbugs.ba.NullnessAnnotationDatabase;
import edu.umd.cs.findbugs.ba.XFactory;
import edu.umd.cs.findbugs.ba.XMethod;
import edu.umd.cs.findbugs.ba.XMethodParameter;
import edu.umd.cs.findbugs.ba.vna.AvailableLoad;
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 dataflow analysis to detect potential null pointer dereferences.
 *
 * @author David Hovemeyer
 * @see IsNullValue
 * @see IsNullValueFrame
 * @see IsNullValueFrameModelingVisitor
 */
public class IsNullValueAnalysis
		extends FrameDataflowAnalysis<IsNullValue, IsNullValueFrame>
		implements EdgeTypes, IsNullValueAnalysisFeatures {
	static final boolean DEBUG = SystemProperties.getBoolean("inva.debug");

	static {
		if (DEBUG) System.out.println("inva.debug enabled");
	}

	private MethodGen methodGen;
	private IsNullValueFrameModelingVisitor visitor;
	private ValueNumberDataflow vnaDataflow;
	private int[] numNonExceptionSuccessorMap;
	private Set<LocationWhereValueBecomesNull> locationWhereValueBecomesNullSet;
	private final boolean trackValueNumbers;

	private IsNullValueFrame lastFrame;
	private IsNullValueFrame instanceOfFrame;
	private IsNullValueFrame cachedEntryFact;

	private JavaClassAndMethod classAndMethod;

	public IsNullValueAnalysis(MethodGen methodGen, CFG cfg, ValueNumberDataflow vnaDataflow, DepthFirstSearch dfs,
							   AssertionMethods assertionMethods) {
		super(dfs);

		this.trackValueNumbers = AnalysisContext.currentAnalysisContext().getBoolProperty(
				AnalysisFeatures.TRACK_VALUE_NUMBERS_IN_NULL_POINTER_ANALYSIS);

		this.methodGen = methodGen;
		this.visitor = new IsNullValueFrameModelingVisitor(
				methodGen.getConstantPool(),
				assertionMethods,
				vnaDataflow,
				trackValueNumbers);
		this.vnaDataflow = vnaDataflow;
		this.numNonExceptionSuccessorMap = new int[cfg.getNumBasicBlocks()];
		this.locationWhereValueBecomesNullSet = new HashSet<LocationWhereValueBecomesNull>();

	   // For each basic block, calculate the number of non-exception successors.
		Iterator<Edge> i = cfg.edgeIterator();
		while (i.hasNext()) {
			Edge edge = i.next();
			if (edge.isExceptionEdge())
				continue;
			int srcBlockId = edge.getSource().getId();
			numNonExceptionSuccessorMap[srcBlockId]++;
		}
		if (DEBUG) {
			System.out.println("IsNullValueAnalysis for " + methodGen.getClassName() + "." + methodGen.getName() + " : " + methodGen.getSignature());
		}
	}



	public void setClassAndMethod(JavaClassAndMethod classAndMethod) {
		this.classAndMethod = classAndMethod;
	}
	public JavaClassAndMethod getClassAndMethod( ) {
		return  classAndMethod;
	}
	public IsNullValueFrame createFact() {
		return new IsNullValueFrame(methodGen.getMaxLocals(), trackValueNumbers);
	}



	public void initEntryFact(IsNullValueFrame result) {
		if (cachedEntryFact ==  null) {

			cachedEntryFact = createFact();
			cachedEntryFact.setValid();

			int numLocals = methodGen.getMaxLocals();
			boolean instanceMethod = !methodGen.isStatic();
			XMethod xm = XFactory.createXMethod(methodGen.getClassName(), 
					methodGen.getName(), methodGen.getSignature(), methodGen.isStatic());
			NullnessAnnotationDatabase db = AnalysisContext.currentAnalysisContext().getNullnessAnnotationDatabase();
			int paramShift = instanceMethod ? 1 : 0;
			for (int i = 0; i < numLocals; ++i) {
				IsNullValue value;

				int paramIndex = i - paramShift;

				if (instanceMethod && i == 0) {
					value = IsNullValue.nonNullValue();
				} else if (paramIndex >= methodGen.getArgumentTypes().length) {
					value = IsNullValue.nonReportingNotNullValue();
				} else {
					XMethodParameter methodParameter = new XMethodParameter(xm, paramIndex);
					NullnessAnnotation n = db.getResolvedAnnotation(methodParameter, false);
					if (n == NullnessAnnotation.CHECK_FOR_NULL)
						// Parameter declared @CheckForNull
						value = IsNullValue.parameterMarkedAsMightBeNull(methodParameter);
					else if (n == NullnessAnnotation.NONNULL) 
						// Parameter declared @NonNull
						// TODO: label this so we don't report defensive programming
						value = IsNullValue.nonNullValue();
					else 
						// Don't know; use default value, normally non-reporting nonnull
						value = IsNullValue.nonReportingNotNullValue();
				}

				cachedEntryFact.setValue(i, value);
			}
		}
		copy(cachedEntryFact, result);
	}


	@Override
	public void transfer(BasicBlock basicBlock, @CheckForNull InstructionHandle end, IsNullValueFrame start, IsNullValueFrame result)
	throws DataflowAnalysisException {
		startTransfer();
		super.transfer(basicBlock, end, start, result);
		endTransfer(basicBlock, end, result);
		ValueNumberFrame vnaFrameAfter = vnaDataflow.getFactAfterLocation(Location.getLastLocation(basicBlock));
		// purge stale information
		if (!vnaFrameAfter.isTop())
			result.cleanStaleKnowledge(vnaFrameAfter);
	}

	public void startTransfer() throws DataflowAnalysisException {
		lastFrame = null;
		instanceOfFrame = null;
	}

	public void endTransfer(BasicBlock basicBlock, @CheckForNull InstructionHandle end, IsNullValueFrame result)
			throws DataflowAnalysisException {
		// Determine if this basic block ends in a redundant branch.
		if (end == null) {
			if (lastFrame == null)
				result.setDecision(null);
			else {
				IsNullConditionDecision decision = getDecision(basicBlock, lastFrame);
				//if (DEBUG) System.out.println("Decision=" + decision);
				result.setDecision(decision);
			}
		}
		lastFrame = null;
		instanceOfFrame = null;
	}

	@Override
	public void transferInstruction(InstructionHandle handle, BasicBlock basicBlock, IsNullValueFrame fact)
			throws DataflowAnalysisException {

		// If this is the last instruction in the block,
		// save the result immediately before the instruction.
		if (handle == basicBlock.getLastInstruction()) {
			lastFrame = createFact();
			lastFrame.copyFrom(fact);
		}

		if (handle.getInstruction().getOpcode() == Constants.INSTANCEOF) {
			instanceOfFrame = createFact();
			instanceOfFrame.copyFrom(fact);
		}

		// Model the instruction
		visitor.setFrameAndLocation(fact, new Location(handle, basicBlock));
		Instruction ins = handle.getInstruction();
		visitor.analyzeInstruction(ins);

		// Special case:
		// The instruction may have produced previously seen values
		// about which new is-null information is known.
		// If any other instances of the produced values exist,
		// update their is-null information.
		// Also, make a note of any newly-produced null values.

		int numProduced = ins.produceStack(methodGen.getConstantPool());
		if (numProduced == Constants.UNPREDICTABLE)
			throw new DataflowAnalysisException("Unpredictable stack production", methodGen, handle);

		int start = fact.getNumSlots() - numProduced;
		Location location = new Location(handle, basicBlock);
		ValueNumberFrame vnaFrameAfter = vnaDataflow.getFactAfterLocation(location);

		for (int i = start; i < fact.getNumSlots(); ++i) {
			ValueNumber value = vnaFrameAfter.getValue(i);
			IsNullValue isNullValue = fact.getValue(i);

			for (int j = 0; j < start; ++j) {
				ValueNumber otherValue = vnaFrameAfter.getValue(j);
				if (value.equals(otherValue)) {
					// Same value is in both slots.
					// Update the is-null information to match
					// the new information.
					fact.setValue(j, isNullValue);
				}
			}
		}

		if (visitor.getSlotContainingNewNullValue() >= 0) {
			ValueNumber newNullValue = vnaFrameAfter.getValue(visitor.getSlotContainingNewNullValue());
			addLocationWhereValueBecomesNull(new LocationWhereValueBecomesNull(
					location,
					newNullValue//,
					//handle
			));
		}

	}

	private static final BitSet nullComparisonInstructionSet = new BitSet();

	static {
		nullComparisonInstructionSet.set(Constants.IFNULL);

		nullComparisonInstructionSet.set(Constants.IFNONNULL);
		nullComparisonInstructionSet.set(Constants.IF_ACMPEQ);
		nullComparisonInstructionSet.set(Constants.IF_ACMPNE);
	}

	public void meetInto(IsNullValueFrame fact, Edge edge, IsNullValueFrame result)
	throws DataflowAnalysisException {
		meetInto(fact,edge,result,true);
	}
	public void meetInto(IsNullValueFrame fact, Edge edge, IsNullValueFrame result, boolean propagatePhiNodeInformation)
			throws DataflowAnalysisException {

		if (fact.isValid()) {
			IsNullValueFrame tmpFact = null;

			if (!NO_SPLIT_DOWNGRADE_NSP) {
				// Downgrade NSP to DNR on non-exception control splits
				if (!edge.isExceptionEdge()
						&& numNonExceptionSuccessorMap[edge.getSource().getId()] > 1) {
					tmpFact = modifyFrame(fact, tmpFact);
					tmpFact.downgradeOnControlSplit();
				}
			}

			if (!NO_SWITCH_DEFAULT_AS_EXCEPTION) {
				if (edge.getType() == SWITCH_DEFAULT_EDGE) {
					tmpFact = modifyFrame(fact, tmpFact);
					tmpFact.toExceptionValues();
				}
			}

			final BasicBlock destBlock = edge.getTarget();

			if (destBlock.isExceptionHandler()) {
				// Exception handler - clear stack and push a non-null value
				// to represent the exception.
				tmpFact = modifyFrame(fact, tmpFact);
				tmpFact.clearStack();

				// Downgrade NULL and NSP to DNR if the handler is for
				// CloneNotSupportedException or InterruptedException
				if (true) {
				CodeExceptionGen handler = destBlock.getExceptionGen();
				ObjectType catchType = handler.getCatchType();
				if (catchType != null) {
					String catchClass = catchType.getClassName();
					if (catchClass.equals("java.lang.CloneNotSupportedException") ||
							catchClass.equals("java.lang.InterruptedException")) {
						for (int i = 0; i < tmpFact.getNumSlots(); ++i) {
							IsNullValue value = tmpFact.getValue(i);
							if (value.isDefinitelyNull() || value.isNullOnSomePath())
								tmpFact.setValue(i, IsNullValue.nullOnComplexPathValue());
						}
					}
				}
				}

				// Mark all values as having occurred on an exception path
				tmpFact.toExceptionValues();

				// Push the exception value
				tmpFact.pushValue(IsNullValue.nonNullValue());
			} else {
				final int edgeType = edge.getType();
				final BasicBlock sourceBlock = edge.getSource();
				final BasicBlock targetBlock = edge.getTarget();
				final ValueNumberFrame targetVnaFrame = vnaDataflow.getStartFact(destBlock);
				final ValueNumberFrame sourceVnaFrame = vnaDataflow.getResultFact(sourceBlock);


				assert targetVnaFrame != null;

				// Determine if the edge conveys any information about the
				// null/non-null status of operands in the incoming frame.
				if (edgeType == IFCMP_EDGE || edgeType == FALL_THROUGH_EDGE) {
					IsNullConditionDecision decision = getResultFact(edge.getSource()).getDecision();
					if (decision != null) {
						if (!decision.isEdgeFeasible(edgeType)) {
							// The incoming edge is infeasible; just use TOP
							// as the start fact for this block.
							tmpFact = createFact();
							tmpFact.setTop();
						} else if (decision.getValue() != null) {
							// A value has been determined for this edge.
							// Use the value to update the is-null information in
							// the start fact for this block.

							if (DEBUG) {
								System.out.println("Updating edge information for " + decision.getValue());
							}
							final Location atIf = new Location(sourceBlock.getLastInstruction(), sourceBlock);
							// TODO: prevIsNullValueFrame is not used
							final IsNullValueFrame prevIsNullValueFrame = getFactAtLocation(atIf);
							final ValueNumberFrame prevVnaFrame = vnaDataflow.getFactAtLocation(atIf);

							IsNullValue decisionValue = decision.getDecision(edgeType);
							if (decisionValue != null) {
								if (decisionValue.isDefinitelyNull()) {
									// Make a note of the value that has become null
									// due to the if comparison.
									addLocationWhereValueBecomesNull(new LocationWhereValueBecomesNull(
											atIf,
											decision.getValue()
									));
								}
								if (DEBUG) {
									System.out.println("Set decision information");
									System.out.println("  " + decision.getValue() + " becomes " + decisionValue);
									System.out.println("  prev available loads: " + prevVnaFrame.availableLoadMapAsString());