bettercfgbuilder2.java

一个查找java程序里bug的程序的源代码,该程序本身也是java写的,对提高java编程水平很有用

		 * @param sourceBlock the source basic block
		 * @param target      the control target
		 * @param edgeType    the type of control edge
		 */
		public void addEdgeAndExplore(BasicBlock sourceBlock, InstructionHandle target, int edgeType) {
			if (usedInstructionSet.get(target.getPosition()) && !containsInstruction(target)) {
				// Control escapes this subroutine
				List<EscapeTarget> escapeTargetList = escapeTargetListMap.get(sourceBlock);
				if (escapeTargetList == null) {
					escapeTargetList = new LinkedList<EscapeTarget>();
					escapeTargetListMap.put(sourceBlock, escapeTargetList);
				}
				escapeTargetList.add(new EscapeTarget(target, edgeType));
			} else {
				// Edge within the current subroutine
				BasicBlock targetBlock = getBlock(target);
				addEdge(sourceBlock, targetBlock, edgeType);
			}
		}

		/**
		 * Add an edge to the subroutine's CFG.
		 *
		 * @param sourceBlock the source basic block
		 * @param destBlock   the destination basic block
		 * @param edgeType    the type of edge
		 */
		public void addEdge(BasicBlock sourceBlock, BasicBlock destBlock, int edgeType) {
			if (VERIFY_INTEGRITY) {
				if (destBlock.isExceptionHandler() && edgeType != HANDLED_EXCEPTION_EDGE)
					throw new IllegalStateException("In method " + SignatureConverter.convertMethodSignature(methodGen) +
					        ": exception handler " + destBlock.getFirstInstruction() + " reachable by non exception edge type " +
					        edgeType);
			}
			cfg.createEdge(sourceBlock, destBlock, edgeType);
		}

		/**
		 * Get an Iterator over the EscapeTargets of given basic block.
		 *
		 * @param sourceBlock the basic block
		 * @return an Iterator over the EscapeTargets
		 */
		public Iterator<EscapeTarget> escapeTargetIterator(BasicBlock sourceBlock) {
			List<EscapeTarget> escapeTargetList = escapeTargetListMap.get(sourceBlock);
			if (escapeTargetList == null)
				escapeTargetList = emptyEscapeTargetList;
			return escapeTargetList.iterator();
		}
	}

	/**
	 * Inlining context.
	 * This essentially consists of a inlining site and
	 * a subroutine to be inlined.  A stack of calling contexts
	 * is maintained in order to resolve EscapeTargets.
	 */
	private static class Context {
		private final Context caller;
		private final Subroutine subroutine;
		private final CFG result;
		private final IdentityHashMap<BasicBlock, BasicBlock> blockMap;
		private final LinkedList<BasicBlock> workList;

		/**
		 * Constructor.
		 *
		 * @param caller     the calling context
		 * @param subroutine the subroutine being inlined
		 * @param result     the result CFG
		 */
		public Context(Context caller, Subroutine subroutine, CFG result) {
			this.caller = caller;
			this.subroutine = subroutine;
			this.result = result;
			this.blockMap = new IdentityHashMap<BasicBlock, BasicBlock>();
			this.workList = new LinkedList<BasicBlock>();
		}

		/**
		 * Get the calling context.
		 */
		public Context getCaller() {
			return caller;
		}

		/**
		 * Get the subroutine being inlined.
		 */
		public Subroutine getSubroutine() {
			return subroutine;
		}

		/**
		 * Get the result CFG.
		 */
		public CFG getResult() {
			return result;
		}

		/**
		 * Add a basic block to the inlining work list.
		 */
		public void addItem(BasicBlock item) {
			workList.add(item);
		}

		/**
		 * Are there more work list items?
		 */
		public boolean hasMoreWork() {
			return !workList.isEmpty();
		}

		/**
		 * Get the next work list item (basic block to be inlined).
		 */
		public BasicBlock nextItem() {
			return workList.removeFirst();
		}

		/**
		 * Map a basic block in a subroutine to the corresponding block
		 * in the resulting CFG.
		 *
		 * @param subBlock    the subroutine block
		 * @param resultBlock the result CFG block
		 */
		public void mapBlock(BasicBlock subBlock, BasicBlock resultBlock) {
			blockMap.put(subBlock, resultBlock);
		}

		/**
		 * Get the block in the result CFG corresponding to the given
		 * subroutine block.
		 *
		 * @param subBlock the subroutine block
		 * @return the result CFG block
		 */
		public BasicBlock getBlock(BasicBlock subBlock) {
			BasicBlock resultBlock = blockMap.get(subBlock);
			if (resultBlock == null) {
				resultBlock = result.allocate();
				blockMap.put(subBlock, resultBlock);
				workList.add(subBlock);
			}
			return resultBlock;
		}

		/**
		 * Check to ensure that this context is not the result of recursion.
		 */
		public void checkForRecursion() throws CFGBuilderException {
			Context callerContext = caller;

			while (callerContext != null) {
				if (callerContext.subroutine == this.subroutine)
					throw new CFGBuilderException("JSR recursion detected!");
				callerContext = callerContext.caller;
			}
		}
	}

	/* ----------------------------------------------------------------------
	 * Instance data
	 * ---------------------------------------------------------------------- */

	private MethodGen methodGen;
	private ConstantPoolGen cpg;
	private ExceptionHandlerMap exceptionHandlerMap;
	private BitSet usedInstructionSet;
	private LinkedList<Subroutine> subroutineWorkList;
	private IdentityHashMap<InstructionHandle, Subroutine> jsrSubroutineMap;
	private Subroutine topLevelSubroutine;
	private CFG cfg;

	/* ----------------------------------------------------------------------
	 * Public methods
	 * ---------------------------------------------------------------------- */

	/**
	 * Constructor.
	 *
	 * @param methodGen the method to build a CFG for
	 */
	public BetterCFGBuilder2(MethodGen methodGen) {
		this.methodGen = methodGen;
		this.cpg = methodGen.getConstantPool();
		this.exceptionHandlerMap = new ExceptionHandlerMap(methodGen);
		this.usedInstructionSet = new BitSet();
		this.jsrSubroutineMap = new IdentityHashMap<InstructionHandle, Subroutine>();
		this.subroutineWorkList = new LinkedList<Subroutine>();
	}

	public void build() throws CFGBuilderException {
		topLevelSubroutine = new Subroutine(methodGen.getInstructionList().getStart());
		subroutineWorkList.add(topLevelSubroutine);

		// Build top level subroutine and all JSR subroutines
		while (!subroutineWorkList.isEmpty()) {
			Subroutine subroutine = subroutineWorkList.removeFirst();
			if (DEBUG) System.out.println("Starting subroutine " + subroutine.getStartInstruction());
			build(subroutine);
		}

		// Inline everything into the top level subroutine
		cfg = inlineAll();

		// Add a NOP instruction to the entry block.
		// This allows analyses to construct a Location
		// representing the entry to the method.
		BasicBlock entryBlock = cfg.getEntry();
		InstructionList il = new InstructionList();
		entryBlock.addInstruction(il.append(new NOP()));

		if (VERIFY_INTEGRITY)
			cfg.checkIntegrity();
	}

	public CFG getCFG() {
		return cfg;
	}

	/* ----------------------------------------------------------------------
	 * Implementation
	 * ---------------------------------------------------------------------- */

	/**
	 * Build a subroutine.
	 * We iteratively add basic blocks to the subroutine
	 * until there are no more blocks reachable from the calling context.
	 * As JSR instructions are encountered, new Subroutines are added
	 * to the subroutine work list.
	 *
	 * @param subroutine the subroutine
	 */
	private void build(Subroutine subroutine) throws CFGBuilderException {
		// Prime the work list
		subroutine.addEdgeAndExplore(subroutine.getEntry(), subroutine.getStartInstruction(), START_EDGE);

		// Keep going until all basic blocks in the subroutine have been added
		while (subroutine.hasMoreWork()) {
			WorkListItem item = subroutine.nextItem();

			InstructionHandle handle = item.getStartInstruction();
			BasicBlock basicBlock = item.getBasicBlock();

			// Add exception handler block (ETB) for exception-throwing instructions
			if (isPEI(handle)) {
				if (DEBUG) System.out.println("ETB block " + basicBlock.getId() + " for " + handle);
				handleExceptions(subroutine, handle, basicBlock);
				BasicBlock body = subroutine.allocateBasicBlock();
				subroutine.addEdge(basicBlock, body, FALL_THROUGH_EDGE);
				basicBlock = body;
			}

			if (DEBUG) System.out.println("BODY block " + basicBlock.getId() + " for " + handle);

			if (!basicBlock.isEmpty())
				throw new IllegalStateException("Block isn't empty!");

			// Add instructions until we get to the end of the block
			boolean endOfBasicBlock = false;
			do {
				Instruction ins = handle.getInstruction();

				// Add the instruction to the block
				if (DEBUG) System.out.println("BB " + basicBlock.getId() + ": adding" + handle);
				basicBlock.addInstruction(handle);
				subroutine.addInstruction(handle);

				short opcode = ins.getOpcode();

				// TODO: should check instruction to ensure that in a JSR subroutine
				// no assignments are made to the local containing the return address.
				// if (ins instanceof ASTORE) ...

				if (opcode == Constants.JSR || opcode == Constants.JSR_W) {
					// Find JSR subroutine, add it to subroutine work list if
					// we haven't built a CFG for it yet
					JsrInstruction jsr = (JsrInstruction) ins;
					InstructionHandle jsrTarget = jsr.getTarget();
					Subroutine jsrSubroutine = jsrSubroutineMap.get(jsrTarget);
					if (jsrSubroutine == null) {
						jsrSubroutine = new Subroutine(jsrTarget);
						jsrSubroutineMap.put(jsrTarget, jsrSubroutine);
						subroutineWorkList.add(jsrSubroutine);
					}

					// This ends the basic block.
					// Add a JSR_EDGE to the successor.
					// It will be replaced later by the inlined JSR subroutine.
					subroutine.addEdgeAndExplore(basicBlock, handle.getNext(), JSR_EDGE);
					endOfBasicBlock = true;
				} else if (opcode == Constants.RET) {
					// End of JSR subroutine
					subroutine.addEdge(basicBlock, subroutine.getExit(), RET_EDGE);
					endOfBasicBlock = true;
				} else {
					TargetEnumeratingVisitor visitor = new TargetEnumeratingVisitor(handle, cpg);
					if (visitor.isEndOfBasicBlock()) {
						endOfBasicBlock = true;

						// Add control edges as appropriate
						if (visitor.instructionIsThrow()) {
							handleExceptions(subroutine, handle, basicBlock);
						} else if (visitor.instructionIsExit()) {
							subroutine.setExitBlock(basicBlock);
						} else if (visitor.instructionIsReturn()) {
							subroutine.setReturnBlock(basicBlock);
						} else {
							Iterator<Target> i = visitor.targetIterator();
							while (i.hasNext()) {
								Target target = i.next();
								subroutine.addEdgeAndExplore(basicBlock, target.getTargetInstruction(),
								        target.getEdgeType());
							}
						}
					}
				}

				if (!endOfBasicBlock) {
					InstructionHandle next = handle.getNext();
					if (next == null)