nullderefandredundantcomparisonfinder.java

A static analysis tool to find bugs in Java programs

/*
 * Bytecode analysis framework
 * Copyright (C) 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.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

import org.apache.bcel.Constants;
import org.apache.bcel.classfile.LineNumberTable;
import org.apache.bcel.classfile.Method;
import org.apache.bcel.generic.GETFIELD;
import org.apache.bcel.generic.GETSTATIC;
import org.apache.bcel.generic.Instruction;
import org.apache.bcel.generic.InstructionHandle;
import org.apache.bcel.generic.InvokeInstruction;

import edu.umd.cs.findbugs.BugAnnotation;
import edu.umd.cs.findbugs.FieldAnnotation;
import edu.umd.cs.findbugs.LocalVariableAnnotation;
import edu.umd.cs.findbugs.SystemProperties;
import edu.umd.cs.findbugs.TigerSubstitutes;
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.CFGBuilderException;
import edu.umd.cs.findbugs.ba.ClassContext;
import edu.umd.cs.findbugs.ba.DataflowAnalysisException;
import edu.umd.cs.findbugs.ba.Edge;
import edu.umd.cs.findbugs.ba.EdgeTypes;
import edu.umd.cs.findbugs.ba.Location;
import edu.umd.cs.findbugs.ba.PostDominatorsAnalysis;
import edu.umd.cs.findbugs.ba.XField;
import edu.umd.cs.findbugs.ba.deref.UnconditionalValueDerefDataflow;
import edu.umd.cs.findbugs.ba.deref.UnconditionalValueDerefSet;
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;
import edu.umd.cs.findbugs.classfile.CheckedAnalysisException;

/**
 * A user-friendly front end for finding null pointer dereferences
 * and redundant null comparisions.
 * 
 * @see IsNullValueAnalysis
 * @author David Hovemeyer
 */
public class NullDerefAndRedundantComparisonFinder {
	private static final boolean DEBUG = SystemProperties.getBoolean("fnd.debug");
	private static final boolean PRUNE_GUARANTEED_DEREFERENCES = SystemProperties.getBoolean("fnd.prune", true);

	private static final boolean DEBUG_DEREFS = SystemProperties.getBoolean("fnd.derefs.debug");

	private ClassContext classContext;
	private Method method;
	private NullDerefAndRedundantComparisonCollector collector;
	private final boolean findGuaranteedDerefs;

	private List<RedundantBranch> redundantBranchList;
	private BitSet definitelySameBranchSet;
	private BitSet definitelyDifferentBranchSet;
	private BitSet undeterminedBranchSet;
	private BitSet lineMentionedMultipleTimes;

	private IsNullValueDataflow invDataflow;
	private ValueNumberDataflow vnaDataflow;
	private UnconditionalValueDerefDataflow uvdDataflow;
	private AssertionMethods assertionMethods;

	static {
		if (DEBUG) System.out.println("fnd.debug enabled");
	}
	/**
	 * Constructor.
	 * 
	 * @param classContext the ClassContext
	 * @param method       the method to analyze
	 * @param collector    the NullDerefAndRedundantComparisonCollector used to report
	 *                     null derefs and redundant null comparisons
	 */
	public NullDerefAndRedundantComparisonFinder(
			ClassContext classContext,
			Method method,
			NullDerefAndRedundantComparisonCollector collector) {

		this.classContext = classContext;
		this.method = method;
		this.collector = collector;
		this.findGuaranteedDerefs = classContext.getAnalysisContext().getBoolProperty(
				AnalysisFeatures.TRACK_GUARANTEED_VALUE_DEREFS_IN_NULL_POINTER_ANALYSIS);
		this.lineMentionedMultipleTimes = ClassContext.linesMentionedMultipleTimes(method);

		this.redundantBranchList = new LinkedList<RedundantBranch>();
		this.definitelySameBranchSet = new BitSet();
		this.definitelyDifferentBranchSet = new BitSet();
		this.undeterminedBranchSet = new BitSet();
		this.assertionMethods = classContext.getAssertionMethods();
	}

	public void execute() {
		try {
		// Do the null-value analysis
		this.invDataflow = classContext.getIsNullValueDataflow(method);
		this.vnaDataflow = classContext.getValueNumberDataflow(method);
		if (findGuaranteedDerefs) {
			if (DEBUG_DEREFS) {
				System.out.println(
						"Checking for guaranteed derefs in " +
						method.getName());
			}
			this.uvdDataflow = classContext.getUnconditionalValueDerefDataflow(method);
		}

		// Check method and report potential null derefs and
		// redundant null comparisons.
		examineBasicBlocks();
		if (findGuaranteedDerefs) {
			examineNullValues();
		}
		examineRedundantBranches();
		}  catch (CheckedAnalysisException e) {
			AnalysisContext.logError("Error while for guaranteed derefs in " +
					method.getName(), e);
		}

	}

	/**
	 * Examine basic blocks for null checks and potentially-redundant
	 * null comparisons.
	 * 
	 * @throws DataflowAnalysisException
	 * @throws CFGBuilderException
	 */
	private void examineBasicBlocks() throws DataflowAnalysisException, CFGBuilderException {
		// Look for null check blocks where the reference being checked
		// is definitely null, or null on some path
		Iterator<BasicBlock> bbIter = invDataflow.getCFG().blockIterator();
		while (bbIter.hasNext()) {
			BasicBlock basicBlock = bbIter.next();

			if (basicBlock.isNullCheck()) {
				analyzeNullCheck(classContext, method, invDataflow, basicBlock);
			} else if (!basicBlock.isEmpty()) {
				// Look for all reference comparisons where
				//    - both values compared are definitely null, or
				//    - one value is definitely null and one is definitely not null
				// These cases are not null dereferences,
				// but they are quite likely to indicate an error, so while we've got
				// information about null values, we may as well report them.
				InstructionHandle lastHandle = basicBlock.getLastInstruction();
				Instruction last = lastHandle.getInstruction();
				switch (last.getOpcode()) {
				case Constants.IF_ACMPEQ:
				case Constants.IF_ACMPNE:
					analyzeRefComparisonBranch(basicBlock, lastHandle);
					break;
				case Constants.IFNULL:
				case Constants.IFNONNULL:
					analyzeIfNullBranch(basicBlock, lastHandle);
					break;
				}
			}
		}
	}

	/**
	 * Examine null values.
	 * Report any that are guaranteed to be dereferenced on
	 * non-implicit-exception paths.
	 * 
	 * @throws CFGBuilderException 
	 * @throws DataflowAnalysisException 
	 */
	private void examineNullValues() throws CFGBuilderException, DataflowAnalysisException {
		Set<LocationWhereValueBecomesNull> locationWhereValueBecomesNullSet =
			invDataflow.getAnalysis().getLocationWhereValueBecomesNullSet();
		if (DEBUG_DEREFS) {
			System.out.println("----------------------- examineNullValues " + locationWhereValueBecomesNullSet.size());
		}

		Map<ValueNumber, SortedSet<Location>> bugStatementLocationMap =
			new HashMap<ValueNumber, SortedSet<Location>>();
		// Inspect the method for locations where a null value is guaranteed to
		// be dereferenced.  Add the dereference locations
		Map<ValueNumber, NullValueUnconditionalDeref> nullValueGuaranteedDerefMap =
			new HashMap<ValueNumber, NullValueUnconditionalDeref>();

	   // Check every location
		for (Iterator<Location> i = classContext.getCFG(method).locationIterator(); i.hasNext();) {
			Location location = i.next();

			if (DEBUG_DEREFS) {
				System.out.println("At location " + location);
			}
			if (false) {
				Instruction in = location.getHandle().getInstruction();

			   if (in instanceof InvokeInstruction && in.produceStack(classContext.getConstantPoolGen()) == 1 || in instanceof GETFIELD || in instanceof GETSTATIC) {
					IsNullValueFrame invFrame = invDataflow.getFactAfterLocation(location);
					if (invFrame.getStackDepth() > 0) {
					IsNullValue isNullValue = invFrame.getTopValue();
					if (isNullValue.isNullOnSomePath()) {
						// OK, must be from return value
						ValueNumber vn = vnaDataflow.getFactAfterLocation(location).getTopValue();
						UnconditionalValueDerefSet uvd = uvdDataflow.getFactAfterLocation(location);
						if (uvd.isUnconditionallyDereferenced(vn)) {
							// System.out.println("Found it");
							SortedSet<Location> knownNullAndDoomedAt = bugStatementLocationMap.get(vn);
							noteUnconditionallyDereferencedNullValue(  location,
									bugStatementLocationMap,
									nullValueGuaranteedDerefMap,
									uvd, isNullValue, vn);
						}
					}
					}
				}


				if (assertionMethods.isAssertionInstruction (in, classContext.getConstantPoolGen()) ) {
					if (DEBUG_DEREFS) 
						System.out.println("Skipping because it is an assertion method ");
					continue;
				}

			}

			checkForUnconditionallyDereferencedNullValues(
					location,
					bugStatementLocationMap,
					nullValueGuaranteedDerefMap,
					vnaDataflow.getFactAtLocation(location), invDataflow.getFactAtLocation(location), uvdDataflow.getFactAfterLocation(location));
		}
		HashSet<ValueNumber> npeIfStatementCovered = new HashSet<ValueNumber>(nullValueGuaranteedDerefMap.keySet());
		Map<ValueNumber, SortedSet<Location>> bugEdgeLocationMap =
			new HashMap<ValueNumber, SortedSet<Location>>();

		// Check every non-exception control edge
		for (Iterator<Edge> i = classContext.getCFG(method).edgeIterator(); i.hasNext();) {
			Edge edge = i.next();

			if (edge.isExceptionEdge()) {
				continue;
			}

			if (DEBUG_DEREFS) {
				System.out.println("On edge " + edge.formatAsString(false));
			}

			ValueNumberFrame vnaFact = vnaDataflow.getResultFact(edge.getSource());
			ValueNumberFrame vnaEdgeFact = vnaDataflow.getFactOnEdge(edge);
			ValueNumberFrame vnaTargetFact = vnaDataflow.getStartFact(edge.getTarget());

			IsNullValueFrame invFact = invDataflow.getFactAtMidEdge(edge);

				IsNullValueFrame invSourceFact = invDataflow.getResultFact(edge.getSource());
				IsNullValueFrame invTargetFact = invDataflow.getStartFact(edge.getTarget());
				UnconditionalValueDerefSet uvdSourceFact = uvdDataflow.getStartFact(edge.getSource());
				UnconditionalValueDerefSet uvdTargetFact = uvdDataflow.getResultFact(edge.getTarget());
				Location location = Location.getLastLocation(edge.getSource());

			UnconditionalValueDerefSet uvdFact = uvdDataflow.getFactOnEdge(edge);
			// UnconditionalValueDerefSet uvdFact = uvdDataflow.getStartFact(edge.getTarget());


			if (uvdFact.isEmpty()) continue;
			if (location != null) {


				Instruction in = location.getHandle().getInstruction();
				if (assertionMethods.isAssertionInstruction(in, classContext.getConstantPoolGen())) {
					if (DEBUG_DEREFS) 
						System.out.println("Skipping because it is an assertion method ");
					continue;
				}


			checkForUnconditionallyDereferencedNullValues(
					location,
					bugEdgeLocationMap,
					nullValueGuaranteedDerefMap,
					vnaFact, invFact, uvdFact);
			}
		}
		Map<ValueNumber, SortedSet<Location>> bugLocationMap = bugEdgeLocationMap;
		bugLocationMap.putAll(bugStatementLocationMap);
		//	For each value number that is null somewhere in the
		// method, collect the set of locations where it becomes null.
		// FIXME: we may see some locations that are not guaranteed to be dereferenced (how to fix this?)
		Map<ValueNumber, Set<Location>> nullValueAssignmentMap =
			new HashMap<ValueNumber, Set<Location>>();
		for (LocationWhereValueBecomesNull lwvbn : locationWhereValueBecomesNullSet) {
			if (DEBUG_DEREFS) System.out.println("OOO " + lwvbn);
			Set<Location> locationSet = nullValueAssignmentMap.get(lwvbn.getValueNumber());
			if (locationSet == null) {
				locationSet = new HashSet<Location>();
				nullValueAssignmentMap.put(lwvbn.getValueNumber(), locationSet);
			}
			locationSet.add(lwvbn.getLocation());
			if (DEBUG_DEREFS)
				System.out.println(lwvbn.getValueNumber() + " becomes null at " + lwvbn.getLocation());
		}

		// Report 
		for (Map.Entry<ValueNumber, NullValueUnconditionalDeref> e  : nullValueGuaranteedDerefMap.entrySet()) {
			ValueNumber valueNumber = e.getKey();
			Set<Location> derefLocationSet = e.getValue().getDerefLocationSet();
			Set<Location> assignedNullLocationSet = nullValueAssignmentMap.get(valueNumber);
			if (assignedNullLocationSet == null) {
				if (DEBUG_DEREFS) {
					String where = classContext.getJavaClass().getClassName() + "." + method.getName() + ":" + method.getSignature();
					System.out.println("Problem at " + where);
					for (Location loc : derefLocationSet) {
						System.out.println("Dereference at " + loc);
					}
				}
				// TODO: figure out why this is failing
				if (false) 
				assert false: "No assigned NullLocationSet for " + valueNumber + " in " + nullValueAssignmentMap.keySet()
				+ " while analyzing " + classContext.getJavaClass().getClassName() + "." + method.getName();
				assignedNullLocationSet = TigerSubstitutes.emptySet();
			}
			SortedSet<Location> knownNullAndDoomedAt = bugLocationMap.get(valueNumber);

			BugAnnotation variableAnnotation = null;
			try {
				for (Location loc : derefLocationSet)  {
					variableAnnotation = NullDerefAndRedundantComparisonFinder.findAnnotationFromValueNumber(method, loc, valueNumber, vnaDataflow.getFactAtLocation(loc));
					if (variableAnnotation != null) break;
				}
				if (variableAnnotation == null) for (Location loc : knownNullAndDoomedAt) {
					variableAnnotation = NullDerefAndRedundantComparisonFinder.findAnnotationFromValueNumber(method, loc, valueNumber, vnaDataflow.getFactAtLocation(loc));
					if (variableAnnotation != null) break;
				}
				if (variableAnnotation == null) for (Location loc : assignedNullLocationSet) {
					variableAnnotation = NullDerefAndRedundantComparisonFinder.findAnnotationFromValueNumber(method, loc, valueNumber, vnaDataflow.getFactAtLocation(loc));
					if (variableAnnotation != null) break;
				}


			} catch (DataflowAnalysisException e2) {
			}
			if (variableAnnotation == null) variableAnnotation = new LocalVariableAnnotation("?",-1,-1);



			if (PRUNE_GUARANTEED_DEREFERENCES) {
				PostDominatorsAnalysis postDomAnalysis =
					classContext.getNonExceptionPostDominatorsAnalysis(method);
			removeStrictlyPostDominatedLocations(derefLocationSet, postDomAnalysis);

			removeStrictlyPostDominatedLocations(knownNullAndDoomedAt, postDomAnalysis);

			removeStrictlyPostDominatedLocations(assignedNullLocationSet, postDomAnalysis);
			}


			collector.foundGuaranteedNullDeref(
					assignedNullLocationSet,
					derefLocationSet,
					knownNullAndDoomedAt,
					vnaDataflow, valueNumber,