finddeadlocalstores.java

A static analysis tool to find bugs in Java programs

/*
 * FindBugs - Find bugs in Java programs
 * Copyright (C) 2004,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.Arrays;
import java.util.BitSet;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.apache.bcel.Constants;
import org.apache.bcel.classfile.Field;
import org.apache.bcel.classfile.JavaClass;
import org.apache.bcel.classfile.LocalVariable;
import org.apache.bcel.classfile.LocalVariableTable;
import org.apache.bcel.classfile.Method;
import org.apache.bcel.generic.ACONST_NULL;
import org.apache.bcel.generic.ALOAD;
import org.apache.bcel.generic.ANEWARRAY;
import org.apache.bcel.generic.ASTORE;
import org.apache.bcel.generic.BasicType;
import org.apache.bcel.generic.ConstantPushInstruction;
import org.apache.bcel.generic.GETFIELD;
import org.apache.bcel.generic.IINC;
import org.apache.bcel.generic.INVOKESPECIAL;
import org.apache.bcel.generic.IndexedInstruction;
import org.apache.bcel.generic.Instruction;
import org.apache.bcel.generic.InstructionHandle;
import org.apache.bcel.generic.InvokeInstruction;
import org.apache.bcel.generic.LDC;
import org.apache.bcel.generic.LoadInstruction;
import org.apache.bcel.generic.MULTIANEWARRAY;
import org.apache.bcel.generic.MethodGen;
import org.apache.bcel.generic.NEWARRAY;
import org.apache.bcel.generic.StoreInstruction;
import org.apache.bcel.generic.Type;

import edu.umd.cs.findbugs.BugAccumulator;
import edu.umd.cs.findbugs.BugInstance;
import edu.umd.cs.findbugs.BugReporter;
import edu.umd.cs.findbugs.Detector;
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.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.LiveLocalStoreAnalysis;
import edu.umd.cs.findbugs.ba.Location;
import edu.umd.cs.findbugs.ba.type.TypeDataflow;
import edu.umd.cs.findbugs.ba.type.TypeFrame;
import edu.umd.cs.findbugs.props.WarningPropertySet;
import edu.umd.cs.findbugs.props.WarningPropertyUtil;
import edu.umd.cs.findbugs.visitclass.PreorderVisitor;

/**
 * Find dead stores to local variables.
 * 
 * @author David Hovemeyer
 * @author Bill Pugh
 */
public class FindDeadLocalStores implements Detector {

	private static final boolean DEBUG = SystemProperties.getBoolean("fdls.debug");

	// Define the name of the property that is used to exclude named local
	// variables
	// from Dead Local Storage detection...
	private static final String FINDBUGS_EXCLUDED_LOCALS_PROP_NAME = "findbugs.dls.exclusions";

	// Define a collection of excluded local variables...
	private static final Set<String> EXCLUDED_LOCALS = new HashSet<String>();

	private static final boolean DO_EXCLUDE_LOCALS = SystemProperties.getProperty(FINDBUGS_EXCLUDED_LOCALS_PROP_NAME) != null;
	static {
		// Get the value of the property...
		String exclLocalsProperty = SystemProperties.getProperty(FINDBUGS_EXCLUDED_LOCALS_PROP_NAME);

		// If we have one, then split its contents into a table...
		if (exclLocalsProperty != null) {
			EXCLUDED_LOCALS.addAll((List<String>) Arrays.asList(exclLocalsProperty.split(",")));
			EXCLUDED_LOCALS.remove("");
		}
	}

	/**
	 * System property to enable a feature that suppresses warnings if
	 * there is at least one live store on the line where the warning
	 * would be reported.  Eliminates some FPs due to inlining/duplication
	 * of finally blocks.  But, kills some legitimate warnings where
	 * there are truly multiple stores on the same line.
	 */
	private static final boolean SUPPRESS_IF_AT_LEAST_ONE_LIVE_STORE_ON_LINE =
		SystemProperties.getBoolean("findbugs.dls.suppressIfOneLiveStore");

	// private static final Set<String> classesAlreadyReportedOn = new
	// HashSet<String>();
	/**
	 * Opcodes of instructions that load constant values that often indicate
	 * defensive programming.
	 */
	private static final BitSet defensiveConstantValueOpcodes = new BitSet();
	static {
		defensiveConstantValueOpcodes.set(Constants.DCONST_0);
		defensiveConstantValueOpcodes.set(Constants.DCONST_1);
		defensiveConstantValueOpcodes.set(Constants.FCONST_0);
		defensiveConstantValueOpcodes.set(Constants.FCONST_1);
		defensiveConstantValueOpcodes.set(Constants.ACONST_NULL);
		defensiveConstantValueOpcodes.set(Constants.ICONST_0);
		defensiveConstantValueOpcodes.set(Constants.ICONST_1);
		defensiveConstantValueOpcodes.set(Constants.LDC);
	}

	private BugReporter bugReporter;

	public FindDeadLocalStores(BugReporter bugReporter) {
		this.bugReporter = bugReporter;
		if (DEBUG)
			System.out.println("Debugging FindDeadLocalStores detector");
	}

	private boolean prescreen(ClassContext classContext, Method method) {
		return true;
	}

	public void visitClassContext(ClassContext classContext) {
		JavaClass javaClass = classContext.getJavaClass();
		Method[] methodList = javaClass.getMethods();

		for (Method method : methodList) {
			MethodGen methodGen = classContext.getMethodGen(method);
			if (methodGen == null)
				continue;

			if (!prescreen(classContext, method))
				continue;

			try {
				analyzeMethod(classContext, method);
			} catch (DataflowAnalysisException e) {
				bugReporter.logError("Error analyzing " + method.toString(), e);
			} catch (CFGBuilderException e) {
				bugReporter.logError("Error analyzing " + method.toString(), e);
			}
		}
	}

	private void analyzeMethod(ClassContext classContext, Method method) throws DataflowAnalysisException, CFGBuilderException {

		if (DEBUG) {
			System.out.println("    Analyzing method " + classContext.getJavaClass().getClassName() + "." + method.getName());
		}

		JavaClass javaClass = classContext.getJavaClass();

		BugAccumulator accumulator = new BugAccumulator(bugReporter);
		Dataflow<BitSet, LiveLocalStoreAnalysis> llsaDataflow = classContext.getLiveLocalStoreDataflow(method);

		int numLocals = method.getCode().getMaxLocals();
		int[] localStoreCount = new int[numLocals];
		int[] localLoadCount = new int[numLocals];
		int[] localIncrementCount = new int[numLocals];
		MethodGen methodGen = classContext.getMethodGen(method);
		CFG cfg = classContext.getCFG(method);
		BitSet liveStoreSetAtEntry = llsaDataflow.getAnalysis().getResultFact(cfg.getEntry());
		BitSet complainedAbout = new BitSet();
		TypeDataflow typeDataflow = classContext.getTypeDataflow(method);

		// Get number of locals that are parameters.
		int localsThatAreParameters = PreorderVisitor.getNumberArguments(method.getSignature());
		if (!method.isStatic())
			localsThatAreParameters++;

		// Scan method to determine number of loads, stores, and increments
		// of local variables.
		countLocalStoresLoadsAndIncrements(localStoreCount, localLoadCount, localIncrementCount, cfg);
		for (int i = 0; i < localsThatAreParameters; i++)
			localStoreCount[i]++;

		// For each source line, keep track of # times
		// the line was a live store.  This can eliminate false positives
		// due to inlining of finally blocks.
		BitSet liveStoreSourceLineSet = new BitSet();

		// Scan method for
		// - dead stores
		// - stores to parameters that are dead upon entry to the method
		for (Iterator<Location> i = cfg.locationIterator(); i.hasNext();) {
			Location location = i.next();

			BugInstance pendingBugReportAboutOverwrittenParameter = null;
			try {
				WarningPropertySet propertySet = new WarningPropertySet();
				// Skip any instruction which is not a store
				if (!isStore(location))
					continue;

				// Heuristic: exception handler blocks often contain
				// dead stores generated by the compiler.
				if (location.getBasicBlock().isExceptionHandler())
					propertySet.addProperty(DeadLocalStoreProperty.EXCEPTION_HANDLER);

				IndexedInstruction ins = (IndexedInstruction) location.getHandle().getInstruction();

				int local = ins.getIndex();

				// Get live stores at this instruction.
				// Note that the analysis also computes which stores were
				// killed by a subsequent unconditional store.
				BitSet liveStoreSet = llsaDataflow.getAnalysis().getFactAtLocation(location);

				// Is store alive?
				boolean storeLive = llsaDataflow.getAnalysis().isStoreAlive(liveStoreSet, local);

				LocalVariableAnnotation lvAnnotation = LocalVariableAnnotation.getLocalVariableAnnotation(method, location, ins);

				SourceLineAnnotation sourceLineAnnotation = SourceLineAnnotation.fromVisitedInstruction(classContext,
						methodGen, javaClass.getSourceFileName(), location.getHandle());

				if (DEBUG) {
					System.out.println("    Store at " + sourceLineAnnotation.getStartLine() + "@" +
							location.getHandle().getPosition() + " is " +
							(storeLive ? "live" : "dead"));
				}

				// Note source lines of live stores.
				if (storeLive && sourceLineAnnotation.getStartLine() > 0) {
					liveStoreSourceLineSet.set(sourceLineAnnotation.getStartLine());
				}

				String name = lvAnnotation.getName();
				if (name.charAt(0) == '$' || name.charAt(0) == '_')
					propertySet.addProperty(DeadLocalStoreProperty.SYNTHETIC_NAME);
				if (EXCLUDED_LOCALS.contains(name))
					continue;
				propertySet.setProperty(DeadLocalStoreProperty.LOCAL_NAME, name);

				boolean isParameter = local < localsThatAreParameters;
				if (isParameter)
					propertySet.addProperty(DeadLocalStoreProperty.IS_PARAMETER);

				// Is this a store to a parameter which was dead on entry to the
				// method?
				boolean parameterThatIsDeadAtEntry = isParameter
				&& !llsaDataflow.getAnalysis().isStoreAlive(liveStoreSetAtEntry, local);
				if (parameterThatIsDeadAtEntry && !complainedAbout.get(local)) {

					// TODO: add warning properties?
					pendingBugReportAboutOverwrittenParameter = new BugInstance(this, "IP_PARAMETER_IS_DEAD_BUT_OVERWRITTEN",
							storeLive ? NORMAL_PRIORITY : HIGH_PRIORITY).addClassAndMethod(methodGen,
									javaClass.getSourceFileName()).add(lvAnnotation).addSourceLine(classContext, methodGen,