typeanalysis.java

A static analysis tool to find bugs in Java programs

			result.setValue(slot++, ObjectTypeFactory.getInstance(methodGen.getClassName()));

		// [Added: Support for Generics]
		// Get a parser that reads the generic signature of the method and
		// can be used to get the correct GenericObjectType if an argument
		// has a class type
		Iterator<String> iter = 
			GenericSignatureParser.getGenericSignatureIterator(method);

		// Add locals for parameters.
		// Note that long and double parameters need to be handled
		// specially because they occupy two locals.
		Type[] argumentTypes = methodGen.getArgumentTypes();		
		for (Type argType : argumentTypes) {
			// Add special "extra" type for long or double params.
			// These occupy the slot before the "plain" type.
			if (argType.getType() == Constants.T_LONG) {
				result.setValue(slot++, TypeFrame.getLongExtraType());
			} else if (argType.getType() == Constants.T_DOUBLE) {
				result.setValue(slot++, TypeFrame.getDoubleExtraType());
			}

			// [Added: Support for Generics]
			String s = ( iter == null  || !iter.hasNext() )? null : iter.next();
			if (	s != null && 
					(argType instanceof ObjectType || argType instanceof ArrayType) &&
					!(argType instanceof ExceptionObjectType) 
				) {
				// replace with a generic version of the type
				try { 
					argType = GenericUtilities.getType(s);
				} catch (RuntimeException e) {} // degrade gracefully
			}

			// Add the plain parameter type.
			result.setValue(slot++, argType);
		}

		// Set remaining locals to BOTTOM; this will cause any
		// uses of them to be flagged
		while (slot < methodGen.getMaxLocals())
			result.setValue(slot++, TypeFrame.getBottomType());
	}

	@Override
	public void copy(TypeFrame source, TypeFrame dest) {
		dest.copyFrom(source);
	}

	@Override
	public void initResultFact(TypeFrame result) {
		// This is important.  Sometimes we need to use a result value
		// before having a chance to initialize it.  We don't want such
		// values to corrupt other TypeFrame values that we merge them with.
		// So, all result values must be TOP.
		result.setTop();
	}

	@Override
	public void makeFactTop(TypeFrame fact) {
		fact.setTop();
	}

	@Override
	public boolean isFactValid(TypeFrame fact) {
		return fact.isValid();
	}

	@Override
	public boolean same(TypeFrame fact1, TypeFrame fact2) {
		return fact1.sameAs(fact2);
	}

	@Override
	public void transferInstruction(InstructionHandle handle, BasicBlock basicBlock, TypeFrame fact)
			throws DataflowAnalysisException {
		if (typeTable != null) {
			int pos = handle.getPosition();
			if (pos >= 0 && startOfLocalTypedVariables.get(pos))
			for(LocalVariable local : typeTable.getLocalVariableTable()) {
				if (local.getStartPC() == pos) {
					String signature = local.getSignature();
					Type t;
					try {
					 t = GenericUtilities.getType(signature);
					} catch (RuntimeException e) {
						AnalysisContext.logError("Bad signature " + signature + " for " + local.getName() + " in " 
								+  methodGen.getClassName() + "." + method.getName());
						continue;
					}
					if (t instanceof GenericObjectType) {
						int index = local.getIndex();
						Type currentValue = fact.getValue(index);
						if (!(currentValue instanceof GenericObjectType) && (currentValue instanceof ObjectType))
							fact.setValue(index, GenericUtilities.merge((GenericObjectType)t, (ObjectType)currentValue));
					}

				}
			}
		}
		visitor.setFrameAndLocation(fact, new Location(handle, basicBlock));
		visitor.analyzeInstruction(handle.getInstruction());
	}

	/* (non-Javadoc)
	 * @see edu.umd.cs.findbugs.ba.AbstractDataflowAnalysis#transfer(edu.umd.cs.findbugs.ba.BasicBlock, org.apache.bcel.generic.InstructionHandle, java.lang.Object, java.lang.Object)
	 */
	@Override
	public void transfer(BasicBlock basicBlock, @CheckForNull InstructionHandle end, TypeFrame start, TypeFrame result) throws DataflowAnalysisException {
		visitor.startBasicBlock();

		super.transfer(basicBlock, end, start, result);

		// Compute thrown exception types
		computeThrownExceptionTypes(basicBlock, end, result);
		if (DEBUG) {
			System.out.println("After " + basicBlock.getFirstInstruction() + " -> " + basicBlock.getLastInstruction());
			System.out.println("    frame: " + result);
		}

		// If this block ends with an instanceof check,
		// update the cached information about it.
		instanceOfCheckMap.remove(basicBlock);
		if (visitor.isInstanceOfFollowedByBranch()) {
			InstanceOfCheck check = new InstanceOfCheck(visitor.getInstanceOfValueNumber(), visitor.getInstanceOfType());
			instanceOfCheckMap.put(basicBlock, check);
		}
	}

	private void computeThrownExceptionTypes(BasicBlock basicBlock, @CheckForNull InstructionHandle end, TypeFrame result)
			throws DataflowAnalysisException {

		// Do nothing if we're not computing propagated exceptions
		if (!(FORCE_ACCURATE_EXCEPTIONS ||
				AnalysisContext.currentAnalysisContext().getBoolProperty(AnalysisFeatures.ACCURATE_EXCEPTIONS)))
			return;

		// Also, nothing to do if the block is not an exception thrower
		if (!basicBlock.isExceptionThrower())
			return;

		// If cached results are up to date, don't recompute.
		CachedExceptionSet cachedExceptionSet = getCachedExceptionSet(basicBlock);
		if (cachedExceptionSet.isUpToDate((TypeFrame) result))
			return;

		// Figure out what exceptions can be thrown out
		// of the basic block, and mark each exception edge
		// with the set of exceptions which can be propagated
		// along the edge.

		int exceptionEdgeCount = 0;
		Edge lastExceptionEdge = null;

		for (Iterator<Edge> i = cfg.outgoingEdgeIterator(basicBlock); i.hasNext();) {
			Edge e = i.next();
			if (e.isExceptionEdge()) {
				exceptionEdgeCount++;
				lastExceptionEdge = e;
			}
		}

		if (exceptionEdgeCount == 0) {
			// System.out.println("Shouldn't all blocks have an exception edge");
			return;
		}
		// Compute exceptions that can be thrown by the
		// basic block.
		cachedExceptionSet = computeBlockExceptionSet(basicBlock, (TypeFrame) result);

		if (exceptionEdgeCount == 1) {
			cachedExceptionSet.setEdgeExceptionSet(lastExceptionEdge, cachedExceptionSet.getExceptionSet());
			return;
		}


		// For each outgoing exception edge, compute exceptions
		// that can be thrown.  This assumes that the exception
		// edges are enumerated in decreasing order of priority.
		// In the process, this will remove exceptions from
		// the thrown exception set.
		ExceptionSet thrownExceptionSet = cachedExceptionSet.getExceptionSet();
		if (!thrownExceptionSet.isEmpty()) thrownExceptionSet = thrownExceptionSet.duplicate();
		for (Iterator<Edge> i = cfg.outgoingEdgeIterator(basicBlock); i.hasNext();) {
			Edge edge = i.next();
			if (edge.isExceptionEdge())
				cachedExceptionSet.setEdgeExceptionSet(edge, computeEdgeExceptionSet(edge, thrownExceptionSet));
		}
	}

	public void meetInto(TypeFrame fact, Edge edge, TypeFrame result) throws DataflowAnalysisException {
		BasicBlock basicBlock = edge.getTarget();

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

			// Handling an exception?
			if (basicBlock.isExceptionHandler()) {
				tmpFact = modifyFrame(fact, tmpFact);

				// Special case: when merging predecessor facts for entry to
				// an exception handler, we clear the stack and push a
				// single entry for the exception object.  That way, the locals
				// can still be merged.
				CodeExceptionGen exceptionGen = basicBlock.getExceptionGen();
				tmpFact.clearStack();

				// Determine the type of exception(s) caught.
				Type catchType = null;

				if (FORCE_ACCURATE_EXCEPTIONS ||
						AnalysisContext.currentAnalysisContext().getBoolProperty(AnalysisFeatures.ACCURATE_EXCEPTIONS)) {
					try {
						// Ideally, the exceptions that can be propagated
						// on this edge has already been computed.
						CachedExceptionSet cachedExceptionSet = getCachedExceptionSet(edge.getSource());
						ExceptionSet edgeExceptionSet = cachedExceptionSet.getEdgeExceptionSet(edge);
						if (!edgeExceptionSet.isEmpty()) {
							//System.out.println("Using computed edge exception set!");
							catchType = ExceptionObjectType.fromExceptionSet(edgeExceptionSet);
						}
					} catch (ClassNotFoundException e) {
						lookupFailureCallback.reportMissingClass(e);
					}
				}

				if (catchType == null) {
					// No information about propagated exceptions, so
					// pick a type conservatively using the handler catch type.
					catchType = exceptionGen.getCatchType();
					if (catchType == null)
						catchType = Type.THROWABLE; // handle catches anything throwable
				}

				tmpFact.pushValue(catchType);
			}

			// See if we can make some types more precise due to
			// a successful instanceof check in the source block.
			if (valueNumberDataflow != null) {
				tmpFact = handleInstanceOfBranch(fact, tmpFact, edge);
			}

			if (tmpFact != null) {
				fact = tmpFact;
			}
		}

		mergeInto(fact, result);
	}

	private TypeFrame handleInstanceOfBranch(TypeFrame fact, TypeFrame tmpFact, Edge edge) throws DataflowAnalysisException {

		InstanceOfCheck check = instanceOfCheckMap.get(edge.getSource());
		if (check == null) {
			//System.out.println("no instanceof check for block " + edge.getSource().getId());
			return tmpFact;
		}

		if (check.getValueNumber() == null) {
			//System.out.println("instanceof check for block " + edge.getSource().getId() + " has no value number");
			return tmpFact;
		}

		ValueNumber instanceOfValueNumber = check.getValueNumber();

		short branchOpcode = edge.getSource().getLastInstruction().getInstruction().getOpcode();

		int edgeType = edge.getType();
		if (    (edgeType == EdgeTypes.IFCMP_EDGE &&
						(branchOpcode == Constants.IFNE || branchOpcode == Constants.IFGT || branchOpcode == Constants.IFNULL))

			|| (edgeType == EdgeTypes.FALL_THROUGH_EDGE &&
						(branchOpcode == Constants.IFEQ || branchOpcode == Constants.IFLE || branchOpcode == Constants.IFNONNULL))
		) {
			//System.out.println("Successful check on edge " + edge);

			// Successful instanceof check.
			ValueNumberFrame vnaFrame = valueNumberDataflow.getStartFact(edge.getTarget());
			if (!vnaFrame.isValid())
				return tmpFact;

			Type instanceOfType = check.getType();
			if (!(instanceOfType instanceof ReferenceType || instanceOfType instanceof NullType))
				return tmpFact;

			int numSlots = Math.min(fact.getNumSlots(), vnaFrame.getNumSlots());
			for (int i = 0; i < numSlots; ++i) {
				if (!vnaFrame.getValue(i).equals(instanceOfValueNumber))
					continue;

				Type checkedType = fact.getValue(i);
				if (!(checkedType instanceof ReferenceType))
					continue;


				// Only refine the type if the cast is feasible: i.e., a downcast.
				// Otherwise, just set it to TOP.
				try {
					boolean feasibleCheck = instanceOfType.equals(NullType.instance()) 
						|| Hierarchy.isSubtype(
							(ReferenceType) instanceOfType,
							(ReferenceType) checkedType);
					if (!feasibleCheck && instanceOfType instanceof ObjectType 
							&& checkedType instanceof ObjectType) {
						double v = DeepSubtypeAnalysis.deepInstanceOf(((ObjectType)instanceOfType).getClassName(), 
								((ObjectType)checkedType).getClassName());
						if (v > 0.0) feasibleCheck = true;