nullderefandredundantcomparisonfinder.java

A static analysis tool to find bugs in Java programs

					variableAnnotation, e.getValue(),  npeIfStatementCovered.contains(valueNumber));
		}
	}

	private void removeStrictlyPostDominatedLocations(Set<Location> locations, PostDominatorsAnalysis postDomAnalysis) {
		BitSet strictlyDominated = new BitSet();
		for(Location loc : locations) {
			BitSet allDominatedBy = postDomAnalysis.getAllDominatedBy(loc.getBasicBlock());
			allDominatedBy.clear(loc.getBasicBlock().getId());
			strictlyDominated.or(allDominatedBy);
		}
		LinkedList<Location> locations2 = new LinkedList<Location>(locations);

		for(Iterator<Location> i = locations.iterator(); i.hasNext(); ) {
			Location loc = i.next();
			if (strictlyDominated.get(loc.getBasicBlock().getId())) { 
				i.remove();
				continue;
			}
			for(Location loc2 : locations2) {
				if (loc.getBasicBlock().equals(loc2.getBasicBlock()) && loc.getHandle().getPosition() > loc2.getHandle().getPosition()) {
					i.remove();
					break;
				}
			}
		}
	}

	private static final boolean MY_DEBUG = false;
	/**
	 * Check for unconditionally dereferenced null values
	 * at a particular location in the CFG.
	 * @param thisLocation TODO
	 * @param knownNullAndDoomedAt TODO
	 * @param nullValueGuaranteedDerefMap map to be populated with null values and where they are derefed 
	 * @param vnaFrame                    value number frame to check
	 * @param invFrame                    null-value frame to check
	 * @param derefSet                    set of unconditionally derefed values at this location 
	 */
	private void checkForUnconditionallyDereferencedNullValues(
			Location thisLocation,
			Map<ValueNumber, SortedSet<Location>> knownNullAndDoomedAt,
			Map<ValueNumber, NullValueUnconditionalDeref> nullValueGuaranteedDerefMap,
			ValueNumberFrame vnaFrame, IsNullValueFrame invFrame, UnconditionalValueDerefSet derefSet) {

		if (DEBUG_DEREFS) {
			System.out.println("vna *** " + vnaFrame);
			System.out.println("inv *** " + invFrame);
			System.out.println("deref * " + derefSet);
		}

		// Make sure the frames contain meaningful information
		if (!vnaFrame.isValid() || !invFrame.isValid() || vnaFrame.getNumSlots() != invFrame.getNumSlots())  {
			return;
		}
		if (derefSet.isEmpty()) return;
		// See if there are any definitely-null values in the frame
		for (int j = 0; j < invFrame.getNumSlots(); j++) {
			IsNullValue isNullValue = invFrame.getValue(j); 
			ValueNumber valueNumber = vnaFrame.getValue(j);
			if ((isNullValue.isDefinitelyNull() || isNullValue.isNullOnSomePath() && isNullValue.isReturnValue()) && (derefSet.isUnconditionallyDereferenced(valueNumber) 
				  )) {
				if (MY_DEBUG) {
					System.out.println("Found NP bug");
					System.out.println("Location: " + thisLocation);
					System.out.println("Value number: " + valueNumber);
					System.out.println("IsNullValue frame: " + invFrame);
					System.out.println("IsNullValue value: " + isNullValue);
					System.out.println("Unconditional dere framef: " + derefSet);
					System.out.println("Unconditionally dereferenced: " + derefSet.isUnconditionallyDereferenced(valueNumber) );

				}
				noteUnconditionallyDereferencedNullValue(
						thisLocation,
						knownNullAndDoomedAt,
						nullValueGuaranteedDerefMap,
						derefSet, isNullValue, valueNumber);
			}
		}

		// See if there are any known-null values in the heap that
		// will be dereferenced in the future.
		for (Map.Entry<ValueNumber, IsNullValue> entry : invFrame.getKnownValueMapEntrySet()) {
			ValueNumber valueNumber = entry.getKey();
			IsNullValue isNullValue = entry.getValue();
			if ((isNullValue.isDefinitelyNull() || isNullValue.isNullOnSomePath() && isNullValue.isReturnValue()) && derefSet.isUnconditionallyDereferenced(valueNumber) ) {
			   noteUnconditionallyDereferencedNullValue(
						thisLocation,
						knownNullAndDoomedAt,
						nullValueGuaranteedDerefMap,
						derefSet, isNullValue, valueNumber);
			}
		}
	}

	/**
	 * Note the locations where a known-null value is unconditionally
	 * dereferenced.
	 * @param thisLocation TODO
	 * @param bugLocations TODO
	 * @param nullValueGuaranteedDerefMap map of null values to sets of Locations where they are derefed
	 * @param derefSet                    set of values known to be unconditionally dereferenced
	 * @param isNullValue                 the null value
	 * @param valueNumber                 the value number of the null value
	 */
	private void noteUnconditionallyDereferencedNullValue(
			Location thisLocation, 
			Map<ValueNumber, SortedSet<Location>> bugLocations, 
			Map<ValueNumber, NullValueUnconditionalDeref> nullValueGuaranteedDerefMap, 
			UnconditionalValueDerefSet derefSet, 
			IsNullValue isNullValue, 
			ValueNumber valueNumber) {
		if (DEBUG) {
			System.out.println("%%% HIT for value number " + valueNumber + " @ " + thisLocation);
		}

		// OK, we have a null value that is unconditionally
		// derferenced.  Make a note of the locations where it
		// will be dereferenced.
		NullValueUnconditionalDeref thisNullValueDeref = nullValueGuaranteedDerefMap.get(valueNumber);
		if (thisNullValueDeref == null) {
			thisNullValueDeref = new NullValueUnconditionalDeref();
			nullValueGuaranteedDerefMap.put(valueNumber, thisNullValueDeref);
		}
		thisNullValueDeref.add(isNullValue, derefSet.getUnconditionalDerefLocationSet(valueNumber));

		if (thisLocation != null) {
			SortedSet<Location> locationsForThisBug = bugLocations.get(valueNumber);

			if (locationsForThisBug == null) {
				locationsForThisBug = new TreeSet<Location>();
				bugLocations.put(valueNumber, locationsForThisBug);
			}
			locationsForThisBug.add(thisLocation);
		}
	}

	/**
	 * Examine redundant branches.
	 */
	private void examineRedundantBranches() {
		for (RedundantBranch redundantBranch : redundantBranchList) {
			if (DEBUG) System.out.println("Redundant branch: " + redundantBranch);
			int lineNumber = redundantBranch.lineNumber;

			// The source to bytecode compiler may sometimes duplicate blocks of
			// code along different control paths.  So, to report the bug,
			// we check to ensure that the branch is REALLY determined each
			// place it is duplicated, and that it is determined in the same way.

			boolean confused = undeterminedBranchSet.get(lineNumber) ||
					(definitelySameBranchSet.get(lineNumber) && definitelyDifferentBranchSet.get(lineNumber));

			// confused if there is JSR confusion or multiple null checks with different results on the same line

			boolean reportIt = true;
			if (lineMentionedMultipleTimes.get(lineNumber) && confused)
				reportIt = false;
			if (redundantBranch.location.getBasicBlock().isInJSRSubroutine() /* occurs in a JSR */
					&& confused)
				reportIt = false;
			if (reportIt) {
				collector.foundRedundantNullCheck(redundantBranch.location, redundantBranch);
			}
		}
	}

	private void analyzeRefComparisonBranch(
			BasicBlock basicBlock,
			InstructionHandle lastHandle) throws DataflowAnalysisException {

		Location location = new Location(lastHandle, basicBlock);

		IsNullValueFrame frame = invDataflow.getFactAtLocation(location);
		if (!frame.isValid()) {
			// Probably dead code due to pruning infeasible exception edges.
			return;
		}
		if (frame.getStackDepth() < 2)
			throw new DataflowAnalysisException("Stack underflow at " + lastHandle);

		// Find the line number.
		int lineNumber = getLineNumber(method, lastHandle);
		if (lineNumber < 0)
			return;

		int numSlots = frame.getNumSlots();
		IsNullValue top = frame.getValue(numSlots - 1);
		IsNullValue topNext = frame.getValue(numSlots - 2);

		boolean definitelySame = top.isDefinitelyNull() && topNext.isDefinitelyNull();
		boolean definitelyDifferent =
				(top.isDefinitelyNull() && topNext.isDefinitelyNotNull()) ||
				(top.isDefinitelyNotNull() && topNext.isDefinitelyNull());

		if (definitelySame || definitelyDifferent) {
			if (definitelySame) {
				if (DEBUG) System.out.println("Line " + lineNumber + " always same");
				definitelySameBranchSet.set(lineNumber);
			}
			if (definitelyDifferent) {
				if (DEBUG) System.out.println("Line " + lineNumber + " always different");
				definitelyDifferentBranchSet.set(lineNumber);
			}

			RedundantBranch redundantBranch = new RedundantBranch(location, lineNumber, top, topNext);

			// Figure out which control edge is made infeasible by the redundant comparison
			boolean wantSame = (lastHandle.getInstruction().getOpcode() == Constants.IF_ACMPEQ);
			int infeasibleEdgeType = (wantSame == definitelySame)
					? EdgeTypes.FALL_THROUGH_EDGE : EdgeTypes.IFCMP_EDGE;
			Edge infeasibleEdge = invDataflow.getCFG().getOutgoingEdgeWithType(basicBlock, infeasibleEdgeType);
			redundantBranch.setInfeasibleEdge(infeasibleEdge);

			if (DEBUG) System.out.println("Adding redundant branch: " + redundantBranch);
			redundantBranchList.add(redundantBranch);
		} else {
			if (DEBUG) System.out.println("Line " + lineNumber + " undetermined");
			undeterminedBranchSet.set(lineNumber);
		}
	}

	// This is called for both IFNULL and IFNONNULL instructions.
	private void analyzeIfNullBranch(
			BasicBlock basicBlock,
			InstructionHandle lastHandle) throws DataflowAnalysisException {

		Location location = new Location(lastHandle, basicBlock);

		IsNullValueFrame frame = invDataflow.getFactAtLocation(location);

		if (!frame.isValid()) {
			// This is probably dead code due to an infeasible exception edge.
			return;
		}

		IsNullValue top = frame.getTopValue();

		// Find the line number.
		int lineNumber = getLineNumber(method, lastHandle);
		if (lineNumber < 0)
			return;

		if (!(top.isDefinitelyNull() || top.isDefinitelyNotNull())) {
			if (DEBUG) System.out.println("Line " + lineNumber + " undetermined");
			undeterminedBranchSet.set(lineNumber);
			return;
		}

		// Figure out if the branch is always taken
		// or always not taken.
		short opcode = lastHandle.getInstruction().getOpcode();
		boolean definitelySame = top.isDefinitelyNull();
		if (opcode != Constants.IFNULL) definitelySame = !definitelySame;

		if (definitelySame) {
			if (DEBUG) System.out.println("Line " + lineNumber + " always same");
			definitelySameBranchSet.set(lineNumber);
		} else {
			if (DEBUG) System.out.println("Line " + lineNumber + " always different");
			definitelyDifferentBranchSet.set(lineNumber);
		}

		RedundantBranch redundantBranch = new RedundantBranch(location, lineNumber, top);

		// Determine which control edge is made infeasible by the redundant comparison
		boolean wantNull = (opcode == Constants.IFNULL);
		int infeasibleEdgeType = (wantNull == top.isDefinitelyNull())
				? EdgeTypes.FALL_THROUGH_EDGE : EdgeTypes.IFCMP_EDGE;
		Edge infeasibleEdge = invDataflow.getCFG().getOutgoingEdgeWithType(basicBlock, infeasibleEdgeType);
		redundantBranch.setInfeasibleEdge(infeasibleEdge);

		if (DEBUG) System.out.println("Adding redundant branch: " + redundantBranch);
		redundantBranchList.add(redundantBranch);
	}

	private void analyzeNullCheck(ClassContext classContext, Method method, IsNullValueDataflow invDataflow,
			BasicBlock basicBlock)
		throws DataflowAnalysisException, CFGBuilderException {
		// Look for null checks where the value checked is definitely
		// null or null on some path.

		InstructionHandle exceptionThrowerHandle = basicBlock.getExceptionThrower();
		Instruction exceptionThrower = exceptionThrowerHandle.getInstruction();

		// Get the stack values at entry to the null check.
		IsNullValueFrame frame = invDataflow.getStartFact(basicBlock);
		if (!frame.isValid())
			return;


		// Could the reference be null?
		IsNullValue refValue = frame.getInstance(exceptionThrower, classContext.getConstantPoolGen());
		if (DEBUG) {
			System.out.println("For basic block " + basicBlock + " value is " + refValue);
		}
		if (!refValue.mightBeNull())
			return;

		// if (!refValue.isDefinitelyNull()) return;
		// Get the value number
		ValueNumberFrame vnaFrame = classContext.getValueNumberDataflow(method).getStartFact(basicBlock);
		if (!vnaFrame.isValid())
			return;
		ValueNumber valueNumber = vnaFrame.getInstance(exceptionThrower, classContext.getConstantPoolGen());
		Location location = new Location(exceptionThrowerHandle, basicBlock);
		if (DEBUG) System.out.println("Warning: VN " + valueNumber + " invf: " + frame + " @ " + location);

		// Issue a warning
		collector.foundNullDeref(classContext, location, valueNumber, refValue, vnaFrame);
	}

	public static XField findXFieldFromValueNumber(Method method,
			Location location, ValueNumber valueNumber,
			ValueNumberFrame vnaFrame) {
		if (vnaFrame == null || vnaFrame.isBottom() || vnaFrame.isTop())
			return null;

		AvailableLoad load = vnaFrame.getLoad(valueNumber);
		if (load != null) {
			return load.getField();
		}
		return null;
	}

	public static FieldAnnotation findFieldAnnotationFromValueNumber(
			Method method, Location location, ValueNumber valueNumber,
			ValueNumberFrame vnaFrame) {
		XField field = NullDerefAndRedundantComparisonFinder.findXFieldFromValueNumber(method, location, valueNumber,
				vnaFrame);
		if (field == null)
			return null;
		return FieldAnnotation.fromXField(field);
	}

	public static LocalVariableAnnotation findLocalAnnotationFromValueNumber(
			Method method, Location location, ValueNumber valueNumber,
			ValueNumberFrame vnaFrame) {

		if (vnaFrame == null || vnaFrame.isBottom() || vnaFrame.isTop())
			return null;

		LocalVariableAnnotation localAnnotation = null;
		for (int i = 0; i < vnaFrame.getNumLocals(); i++) {
			if (valueNumber.equals(vnaFrame.getValue(i))) {
				InstructionHandle handle = location.getHandle();
				int position1 = handle.getPrev().getPosition();
				int position2 = handle.getPosition();
				localAnnotation = LocalVariableAnnotation
						.getLocalVariableAnnotation(method, i, position1,
								position2);
				if (localAnnotation != null)
					return localAnnotation;
			}
		}
		return null;
	}

	/**
	 * @param method
	 *            TODO
	 * @param location
	 * @param valueNumber
	 * @param vnaFrame
	 * @return
	 */
	public static BugAnnotation findAnnotationFromValueNumber(Method method,
			Location location, ValueNumber valueNumber,
			ValueNumberFrame vnaFrame) {
		LocalVariableAnnotation ann = NullDerefAndRedundantComparisonFinder.findLocalAnnotationFromValueNumber(
				method, location, valueNumber, vnaFrame);
		if (ann != null && ann.isSignificant())
			return ann;
		FieldAnnotation field = NullDerefAndRedundantComparisonFinder.findFieldAnnotationFromValueNumber(method,
				location, valueNumber, vnaFrame);
		if (field != null)
			return field;
		return ann;
	}

	private static int getLineNumber(Method method, InstructionHandle handle) {
		LineNumberTable table = method.getCode().getLineNumberTable();
		if (table == null)
			return -1;
		return table.getSourceLine(handle.getPosition());
	}
}