typeanalysis.java

A static analysis tool to find bugs in Java programs

					}
					tmpFact = modifyFrame(fact, tmpFact);
					tmpFact.setValue(i, feasibleCheck ? instanceOfType : TopType.instance());
				} catch (ClassNotFoundException e) {
					lookupFailureCallback.reportMissingClass(e);
					throw new MissingClassException(e);
				}
			}
		}

		return tmpFact;
	}

	@Override
	protected void mergeValues(TypeFrame otherFrame, TypeFrame resultFrame, int slot) throws DataflowAnalysisException {
		Type value = typeMerger.mergeTypes(resultFrame.getValue(slot), otherFrame.getValue(slot));
		resultFrame.setValue(slot, value);

		// Result type is exact IFF types are identical and both are exact

		boolean typesAreIdentical =
			otherFrame.getValue(slot).equals(resultFrame.getValue(slot));

		boolean bothExact =
			resultFrame.isExact(slot) && otherFrame.isExact(slot);

		resultFrame.setExact(slot, typesAreIdentical && bothExact);
	}

	/**
	 * Get the cached set of exceptions that can be thrown
	 * from given basic block.  If this information hasn't
	 * been computed yet, then an empty exception set is
	 * returned.
	 *
	 * @param basicBlock the block to get the cached exception set for
	 * @return the CachedExceptionSet for the block
	 */
	private CachedExceptionSet getCachedExceptionSet(BasicBlock basicBlock) {
		CachedExceptionSet cachedExceptionSet = thrownExceptionSetMap.get(basicBlock);
		if (cachedExceptionSet == null) {
			// When creating the cached exception type set for the first time:
			// - the block result is set to TOP, so it won't match
			//   any block result that has actually been computed
			//   using the analysis transfer function
			// - the exception set is created as empty (which makes it
			//   return TOP as its common superclass)

			TypeFrame top = createFact();
			makeFactTop(top);
			cachedExceptionSet = new CachedExceptionSet(top, exceptionSetFactory.createExceptionSet());

			thrownExceptionSetMap.put(basicBlock, cachedExceptionSet);
		}

		return cachedExceptionSet;
	}

	/**
	 * Compute the set of exceptions that can be
	 * thrown from the given basic block.
	 * This should only be called if the existing cached
	 * exception set is out of date.
	 *
	 * @param basicBlock the basic block
	 * @param result     the result fact for the block; this is used
	 *                   to determine whether or not the cached exception
	 *                   set is up to date
	 * @return the cached exception set for the block
	 */
	private CachedExceptionSet computeBlockExceptionSet(BasicBlock basicBlock, TypeFrame result)
			throws DataflowAnalysisException {

		ExceptionSet exceptionSet;
		try {
			exceptionSet = computeThrownExceptionTypes(basicBlock);
		} catch (ClassNotFoundException e) {
			// Special case: be as conservative as possible
			// if a class hierarchy lookup fails.
			lookupFailureCallback.reportMissingClass(e);
			exceptionSet = exceptionSetFactory.createExceptionSet();
			exceptionSet.addExplicit(Type.THROWABLE);
		}

		TypeFrame copyOfResult = createFact();
		copy(result, copyOfResult);

		CachedExceptionSet cachedExceptionSet = new CachedExceptionSet(copyOfResult, exceptionSet);
		thrownExceptionSetMap.put(basicBlock, cachedExceptionSet);

		return cachedExceptionSet;
	}

	/**
	 * Based on the set of exceptions that can be thrown
	 * from the source basic block,
	 * compute the set of exceptions that can propagate
	 * along given exception edge.  This method should be
	 * called for each outgoing exception edge in sequence,
	 * so the caught exceptions can be removed from the
	 * thrown exception set as needed.
	 *
	 * @param edge               the exception edge
	 * @param thrownExceptionSet current set of exceptions that
	 *                           can be thrown, taking earlier (higher priority)
	 *                           exception edges into account
	 * @return the set of exceptions that can propagate
	 *         along this edge
	 */
	private ExceptionSet computeEdgeExceptionSet(Edge edge, ExceptionSet thrownExceptionSet) {


		if (thrownExceptionSet.isEmpty()) return thrownExceptionSet;
		ExceptionSet result = exceptionSetFactory.createExceptionSet();

		if (edge.getType() == UNHANDLED_EXCEPTION_EDGE) {
			// The unhandled exception edge always comes
			// after all of the handled exception edges.
			result.addAll(thrownExceptionSet);
			thrownExceptionSet.clear();
			return result;
		}

		BasicBlock handlerBlock = edge.getTarget();
		CodeExceptionGen handler = handlerBlock.getExceptionGen();
		ObjectType catchType = handler.getCatchType();

		if (Hierarchy.isUniversalExceptionHandler(catchType)) {
			result.addAll(thrownExceptionSet);
			thrownExceptionSet.clear();
		} else {
			// Go through the set of thrown exceptions.
			// Any that will DEFINITELY be caught be this handler, remove.
			// Any that MIGHT be caught, but won't definitely be caught,
			// remain.

			for (ExceptionSet.ThrownExceptionIterator i = thrownExceptionSet.iterator(); i.hasNext();) {
				//ThrownException thrownException = i.next();
				ObjectType thrownType = i.next();
				boolean explicit = i.isExplicit();

				if (DEBUG)
					System.out.println("\texception type " + thrownType +
							", catch type " + catchType);

				try {
					if (Hierarchy.isSubtype(thrownType, catchType)) {
						// Exception can be thrown along this edge
						result.add(thrownType, explicit);

						// And it will definitely be caught
						i.remove();

						if (DEBUG)
							System.out.println("\tException is subtype of catch type: " +
									"will definitely catch");
					} else if (Hierarchy.isSubtype(catchType, thrownType)) {
						// Exception possibly thrown along this edge
						result.add(thrownType, explicit);

						if (DEBUG)
							System.out.println("\tException is supertype of catch type: " +
									"might catch");
					}
				} catch (ClassNotFoundException e) {
					// As a special case, if a class hierarchy lookup
					// fails, then we will conservatively assume that the
					// exception in question CAN, but WON'T NECESSARILY
					// be caught by the handler.
					AnalysisContext.reportMissingClass(e);
					result.add(thrownType, explicit);
				}
			}
		}

		return result;
	}

	/**
	 * Compute the set of exception types that can
	 * be thrown by given basic block.
	 *
	 * @param basicBlock the basic block
	 * @return the set of exceptions that can be thrown by the block
	 */
	private ExceptionSet computeThrownExceptionTypes(BasicBlock basicBlock)
			throws ClassNotFoundException, DataflowAnalysisException {

		ExceptionSet exceptionTypeSet = exceptionSetFactory.createExceptionSet();
		InstructionHandle pei = basicBlock.getExceptionThrower();
		Instruction ins = pei.getInstruction();

		// Get the exceptions that BCEL knows about.
		// Note that all of these are unchecked.
		ExceptionThrower exceptionThrower = (ExceptionThrower) ins;
		Class[] exceptionList = exceptionThrower.getExceptions();
		for (Class aExceptionList : exceptionList) {
			exceptionTypeSet.addImplicit(ObjectTypeFactory.getInstance(aExceptionList.getName()));
		}

		// Assume that an Error may be thrown by any instruction.
		exceptionTypeSet.addImplicit(Hierarchy.ERROR_TYPE);

		if (ins instanceof ATHROW) {
			// For ATHROW instructions, we generate *two* blocks
			// for which the ATHROW is an exception thrower.
			//
			// - The first, empty basic block, does the null check
			// - The second block, which actually contains the ATHROW,
			//   throws the object on the top of the operand stack
			//
			// We make a special case of the block containing the ATHROW,
			// by removing all of the implicit exceptions,
			// and using type information to figure out what is thrown.

			if (basicBlock.containsInstruction(pei)) {
				// This is the actual ATHROW, not the null check
				// and implicit exceptions.
				exceptionTypeSet.clear();

				// The frame containing the thrown value is the start fact
				// for the block, because ATHROW is guaranteed to be
				// the only instruction in the block.
				TypeFrame frame = getStartFact(basicBlock);

				// Check whether or not the frame is valid.
				// Sun's javac sometimes emits unreachable code.
				// For example, it will emit code that follows a JSR
				// subroutine call that never returns.
				// If the frame is invalid, then we can just make
				// a conservative assumption that anything could be
				// thrown at this ATHROW.
				if (!frame.isValid()) {
					exceptionTypeSet.addExplicit(Type.THROWABLE);
				} else if (frame.getStackDepth() == 0) {
					throw new IllegalStateException("empty stack " +
							" thrown by " + pei + " in " +
							SignatureConverter.convertMethodSignature(methodGen));
				} else {

					Type throwType = frame.getTopValue();
					if (throwType instanceof ObjectType) {
						exceptionTypeSet.addExplicit((ObjectType) throwType);
					} else if (throwType instanceof ExceptionObjectType) {
						exceptionTypeSet.addAll(((ExceptionObjectType) throwType).getExceptionSet());
					} else {
						// Not sure what is being thrown here.
						// Be conservative.
						if (DEBUG) {
							System.out.println("Non object type " + throwType +
									" thrown by " + pei + " in " +
									SignatureConverter.convertMethodSignature(methodGen));
						}
						exceptionTypeSet.addExplicit(Type.THROWABLE);
					}
				}
			}
		}

		// If it's an InvokeInstruction, add declared exceptions and RuntimeException
		if (ins instanceof InvokeInstruction) {
			ConstantPoolGen cpg = methodGen.getConstantPool();

			InvokeInstruction inv = (InvokeInstruction) ins;
			ObjectType[] declaredExceptionList = Hierarchy.findDeclaredExceptions(inv, cpg);
			if (declaredExceptionList == null) {
				// Couldn't find declared exceptions,
				// so conservatively assume it could thrown any checked exception.
				if (DEBUG)
					System.out.println("Couldn't find declared exceptions for " +
							SignatureConverter.convertMethodSignature(inv, cpg));
				exceptionTypeSet.addExplicit(Hierarchy.EXCEPTION_TYPE);
			} else {
				for (ObjectType aDeclaredExceptionList : declaredExceptionList) {
					exceptionTypeSet.addExplicit(aDeclaredExceptionList);
				}
			}

			exceptionTypeSet.addImplicit(Hierarchy.RUNTIME_EXCEPTION_TYPE);
		}

		if (DEBUG) System.out.println(pei + " can throw " + exceptionTypeSet);

		return exceptionTypeSet;
	}

	public static void main(String[] argv) throws Exception {
		if (argv.length != 1) {
			System.err.println("Usage: " + TypeAnalysis.class.getName() + " <class file>");
			System.exit(1);
		}

		DataflowTestDriver<TypeFrame, TypeAnalysis> driver = new DataflowTestDriver<TypeFrame, TypeAnalysis>() {
			@Override
			public Dataflow<TypeFrame, TypeAnalysis> createDataflow(ClassContext classContext, Method method)
					throws CFGBuilderException, DataflowAnalysisException {
				return classContext.getTypeDataflow(method);
			}
		};

		driver.execute(argv[0]);
	}
}

// vim:ts=3