findnullderef.java.mine

A static analysis tool to find bugs in Java programs

/*
 * FindBugs - Find bugs in Java programs
 * 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.detect;

import java.util.BitSet;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

import org.apache.bcel.Constants;
import org.apache.bcel.classfile.JavaClass;
import org.apache.bcel.classfile.Method;
import org.apache.bcel.generic.ATHROW;
import org.apache.bcel.generic.ConstantPoolGen;
import org.apache.bcel.generic.Instruction;
import org.apache.bcel.generic.InstructionHandle;
import org.apache.bcel.generic.InstructionTargeter;
import org.apache.bcel.generic.InvokeInstruction;
import org.apache.bcel.generic.MethodGen;
import org.apache.bcel.generic.PUTFIELD;
import org.apache.bcel.generic.ReturnInstruction;

import edu.umd.cs.findbugs.BugAnnotation;
import edu.umd.cs.findbugs.BugInstance;
import edu.umd.cs.findbugs.BugReporter;
import edu.umd.cs.findbugs.Detector;
import edu.umd.cs.findbugs.FieldAnnotation;
import edu.umd.cs.findbugs.FindBugsAnalysisFeatures;
import edu.umd.cs.findbugs.LocalVariableAnnotation;
import edu.umd.cs.findbugs.SourceLineAnnotation;
import edu.umd.cs.findbugs.SystemProperties;
import edu.umd.cs.findbugs.annotations.NonNull;
import edu.umd.cs.findbugs.ba.AnalysisContext;
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.DataflowAnalysisException;
import edu.umd.cs.findbugs.ba.DataflowValueChooser;
import edu.umd.cs.findbugs.ba.Edge;
import edu.umd.cs.findbugs.ba.Hierarchy;
import edu.umd.cs.findbugs.ba.JavaClassAndMethod;
import edu.umd.cs.findbugs.ba.Location;
import edu.umd.cs.findbugs.ba.MissingClassException;
import edu.umd.cs.findbugs.ba.NullnessAnnotation;
import edu.umd.cs.findbugs.ba.NullnessAnnotationDatabase;
import edu.umd.cs.findbugs.ba.SignatureConverter;
import edu.umd.cs.findbugs.ba.XFactory;
import edu.umd.cs.findbugs.ba.XField;
import edu.umd.cs.findbugs.ba.XMethod;
import edu.umd.cs.findbugs.ba.interproc.PropertyDatabase;
import edu.umd.cs.findbugs.ba.npe.IsNullValue;
import edu.umd.cs.findbugs.ba.npe.IsNullValueDataflow;
import edu.umd.cs.findbugs.ba.npe.IsNullValueFrame;
import edu.umd.cs.findbugs.ba.npe.NullDerefAndRedundantComparisonCollector;
import edu.umd.cs.findbugs.ba.npe.NullDerefAndRedundantComparisonFinder;
import edu.umd.cs.findbugs.ba.npe.ParameterNullnessProperty;
import edu.umd.cs.findbugs.ba.npe.ParameterNullnessPropertyDatabase;
import edu.umd.cs.findbugs.ba.npe.RedundantBranch;
import edu.umd.cs.findbugs.ba.npe.UsagesRequiringNonNullValues;
import edu.umd.cs.findbugs.ba.type.TypeDataflow;
import edu.umd.cs.findbugs.ba.type.TypeFrame;
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.props.GeneralWarningProperty;
import edu.umd.cs.findbugs.props.WarningPropertySet;
import edu.umd.cs.findbugs.props.WarningPropertyUtil;
import edu.umd.cs.findbugs.visitclass.Util;

/**
 * A Detector to find instructions where a NullPointerException
 * might be raised.  We also look for useless reference comparisons
 * involving null and non-null values.
 *
 * @author David Hovemeyer
 * @author William Pugh
 * @see edu.umd.cs.findbugs.ba.npe.IsNullValueAnalysis
 */
public class FindNullDeref
		implements Detector, NullDerefAndRedundantComparisonCollector {

	private static final boolean DEBUG = SystemProperties.getBoolean("fnd.debug");
	private static final boolean DEBUG_NULLARG = SystemProperties.getBoolean("fnd.debug.nullarg");
	private static final boolean DEBUG_NULLRETURN = SystemProperties.getBoolean("fnd.debug.nullreturn");
	private static final boolean REPORT_SAFE_METHOD_TARGETS = true;

	private static final String METHOD = SystemProperties.getProperty("fnd.method");
	private static final String CLASS = SystemProperties.getProperty("fnd.class");
	
	// Fields
	private BugReporter bugReporter;
	
	// Cached database stuff
	private ParameterNullnessPropertyDatabase unconditionalDerefParamDatabase;
	private boolean checkedDatabases = false;

	
	// Transient state
	private ClassContext classContext;
	private Method method;
	private IsNullValueDataflow invDataflow;
	private BitSet previouslyDeadBlocks;
	private NullnessAnnotation methodAnnotation;

	public FindNullDeref(BugReporter bugReporter) {
		this.bugReporter = bugReporter;
	}

	public void visitClassContext(ClassContext classContext) {
		this.classContext = classContext;
		
		String currentMethod = null;

		JavaClass jclass = classContext.getJavaClass();
		String className = jclass.getClassName();
		if (CLASS != null && !className.equals(CLASS)) return;
		Method[] methodList = jclass.getMethods();
		for (Method method : methodList) {
			try {
				if (method.isAbstract() || method.isNative()
						|| method.getCode() == null)
					continue;
				
				MethodGen mg = classContext.getMethodGen(method);
				if (mg == null) {
					continue;
				}
				currentMethod = SignatureConverter.convertMethodSignature(mg);


				if (METHOD != null && !method.getName().equals(METHOD))
					continue;
				if (DEBUG)
					System.out
							.println("Checking for NP in " + currentMethod);
				analyzeMethod(classContext, method);
			} catch (MissingClassException e) {
				bugReporter.reportMissingClass(e.getClassNotFoundException());
			} catch (DataflowAnalysisException e) {
				bugReporter.logError("While analyzing " + currentMethod + ": FindNullDeref caught dae exception", e);
			} catch (CFGBuilderException e) {
				bugReporter.logError("While analyzing " + currentMethod + ": FindNullDeref caught cfgb exception", e);
			}

		}
	}

	private void analyzeMethod(ClassContext classContext, Method method)
	        throws CFGBuilderException, DataflowAnalysisException {
		if (DEBUG || DEBUG_NULLARG)
			System.out.println("Pre FND ");

		MethodGen methodGen = classContext.getMethodGen(method);
		if (methodGen == null)
			return;
		if (!checkedDatabases) {
			checkDatabases();
			checkedDatabases = true;
		}
		
        // UsagesRequiringNonNullValues uses = classContext.getUsagesRequiringNonNullValues(method);
		this.method = method;
		this.methodAnnotation = getMethodNullnessAnnotation();


		if (DEBUG || DEBUG_NULLARG)
			System.out.println("FND: " + SignatureConverter.convertMethodSignature(methodGen));

		this.previouslyDeadBlocks = findPreviouslyDeadBlocks();
		
		// Get the IsNullValueDataflow for the method from the ClassContext
		invDataflow = classContext.getIsNullValueDataflow(method);
		
		// Create a NullDerefAndRedundantComparisonFinder object to do the actual
		// work.  It will call back to report null derefs and redundant null comparisons
		// through the NullDerefAndRedundantComparisonCollector interface we implement.
		NullDerefAndRedundantComparisonFinder worker = new NullDerefAndRedundantComparisonFinder(
				classContext,
				method,
				this);
		worker.execute();


		checkCallSitesAndReturnInstructions();
		
	}

	/**
	 * Find set of blocks which were known to be dead before doing the
	 * null pointer analysis.
	 * 
	 * @return set of previously dead blocks, indexed by block id
	 * @throws CFGBuilderException 
	 * @throws DataflowAnalysisException 
	 */
	private BitSet findPreviouslyDeadBlocks() throws DataflowAnalysisException, CFGBuilderException {
		BitSet deadBlocks = new BitSet();
		ValueNumberDataflow vnaDataflow = classContext.getValueNumberDataflow(method);
		for (Iterator<BasicBlock> i = vnaDataflow.getCFG().blockIterator(); i.hasNext();) {
			BasicBlock block = i.next();
			ValueNumberFrame vnaFrame = vnaDataflow.getStartFact(block);
			if (vnaFrame.isTop()) {
				deadBlocks.set(block.getId());
			}
		}
		
		return deadBlocks;
	}

	/**
	 * Check whether or not the various interprocedural databases we can
	 * use exist and are nonempty.
	 */
	private void checkDatabases() {
		AnalysisContext analysisContext = AnalysisContext.currentAnalysisContext();
		unconditionalDerefParamDatabase = analysisContext.getUnconditionalDerefParamDatabase();	
	}

	private<
		DatabaseType extends PropertyDatabase<?,?>> boolean isDatabaseNonEmpty(DatabaseType database) {
		return database != null && !database.isEmpty();
	}

	/**
	 * See if the currently-visited method declares a @NonNull annotation,
	 * or overrides a method which declares a @NonNull annotation.
	 */
	private NullnessAnnotation getMethodNullnessAnnotation() {
		
		if (method.getSignature().indexOf(")L") >= 0 || method.getSignature().indexOf(")[") >= 0 ) {
			if (DEBUG_NULLRETURN) {
				System.out.println("Checking return annotation for " +
						SignatureConverter.convertMethodSignature(classContext.getJavaClass(), method));
			}
			
			XMethod m = XFactory.createXMethod(classContext.getJavaClass(), method);
			return AnalysisContext.currentAnalysisContext().getNullnessAnnotationDatabase()
			.getResolvedAnnotation(m, false);
		}
		return NullnessAnnotation.UNKNOWN_NULLNESS;
	}

	private void checkCallSitesAndReturnInstructions()
			throws CFGBuilderException, DataflowAnalysisException {
		ConstantPoolGen cpg = classContext.getConstantPoolGen();
		TypeDataflow typeDataflow = classContext.getTypeDataflow(method);
		
		for (Iterator<Location> i = classContext.getCFG(method).locationIterator(); i.hasNext();) {
			Location location = i.next();
			Instruction ins = location.getHandle().getInstruction();
			try {
				if (ins instanceof InvokeInstruction) {
					examineCallSite(location, cpg, typeDataflow);
				} else if (methodAnnotation == NullnessAnnotation.NONNULL && ins.getOpcode() == Constants.ARETURN) {
					examineReturnInstruction(location);
				} else if (ins instanceof PUTFIELD) {
					examinePutfieldInstruction(location, (PUTFIELD) ins, cpg);
				}
			} catch (ClassNotFoundException e) {
				bugReporter.reportMissingClass(e);
			}
		}
	}

	private void examineCallSite(
			Location location,
			ConstantPoolGen cpg,
			TypeDataflow typeDataflow)
			throws DataflowAnalysisException, CFGBuilderException, ClassNotFoundException {
		
		InvokeInstruction invokeInstruction = (InvokeInstruction)
			location.getHandle().getInstruction();
		
		
		String methodName = invokeInstruction.getName(cpg);
		String signature = invokeInstruction.getSignature(cpg);
		
		// Don't check equals() calls.
		// If an equals() call unconditionally dereferences the parameter,
		// it is the fault of the method, not the caller.
		if (methodName.equals("equals") && signature.equals("(Ljava/lang/Object;)Z"))
			return;
		
		int returnTypeStart = signature.indexOf(')');
		if (returnTypeStart < 0)
			return;
		String paramList = signature.substring(0, returnTypeStart + 1);
		
		if (paramList.equals("()") ||
				(paramList.indexOf("L") < 0 && paramList.indexOf('[') < 0))
			// Method takes no arguments, or takes no reference arguments
			return;

		// See if any null arguments are passed
		IsNullValueFrame frame =
			classContext.getIsNullValueDataflow(method).getFactAtLocation(location);
		if (!frame.isValid())
			return;
		BitSet nullArgSet =  
            frame.getArgumentSet(invokeInstruction, cpg, new DataflowValueChooser<IsNullValue>() {
			public boolean choose(IsNullValue value) {
				// Only choose non-exception values.
				// Values null on an exception path might be due to
				// infeasible control flow.
				return value.mightBeNull() && !value.isException() && !value.isReturnValue();
			}
		});
		BitSet definitelyNullArgSet = frame.getArgumentSet(invokeInstruction, cpg, new DataflowValueChooser<IsNullValue>() {
			public boolean choose(IsNullValue value) {
				return value.isDefinitelyNull();
			}
		});
        nullArgSet.and(definitelyNullArgSet);
		if (nullArgSet.isEmpty())
			return;
		if (DEBUG_NULLARG) {
			System.out.println("Null arguments passed: " + nullArgSet);
			System.out.println("Frame is: " + frame);
			System.out.println("# arguments: " + frame.getNumArguments(invokeInstruction, cpg));
			XMethod xm = XFactory.createXMethod(invokeInstruction, cpg);
			System.out.print("Signature: " + xm.getSignature());
		}
		
        
		if (unconditionalDerefParamDatabase != null) {
			checkUnconditionallyDereferencedParam(location, cpg, typeDataflow, invokeInstruction, nullArgSet, definitelyNullArgSet);
		}
		
		
		if (DEBUG_NULLARG) {
			System.out.println("Checking nonnull params");
		}