bettercfgbuilder2.java

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

/*
 * Bytecode Analysis Framework
 * Copyright (C) 2003,2004 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.ba;

import java.util.*;

import org.apache.bcel.Constants;
import org.apache.bcel.classfile.ClassParser;
import org.apache.bcel.classfile.JavaClass;
import org.apache.bcel.classfile.Method;
import org.apache.bcel.generic.*;

/**
 * A CFGBuilder that really tries to construct accurate control flow graphs.
 * The CFGs it creates have accurate exception edges, and have accurately
 * inlined JSR subroutines.
 *
 * @author David Hovemeyer
 * @see CFG
 */
public class BetterCFGBuilder2 implements CFGBuilder, EdgeTypes, Debug {

	private static final boolean DEBUG = Boolean.getBoolean("cfgbuilder.debug");

	private static final boolean NO_STATIC_FIELD_EXCEPTIONS =
	        !Boolean.getBoolean("cfgbuilder.staticFieldExceptions");

	private static final boolean NO_LOAD_CONSTANT_EXCEPTIONS =
	        !Boolean.getBoolean("cfgbuilder.ldcExceptions");

	// TODO: don't forget to change BasicBlock so ATHROW is considered to have a null check

	/* ----------------------------------------------------------------------
	 * Helper classes
	 * ---------------------------------------------------------------------- */

	/**
	 * A work list item for creating the CFG for a subroutine.
	 */
	private static class WorkListItem {
		private final InstructionHandle start;
		private final BasicBlock basicBlock;

		/**
		 * Constructor.
		 *
		 * @param start      first instruction in the basic block
		 * @param basicBlock the basic block to build
		 */
		public WorkListItem(InstructionHandle start, BasicBlock basicBlock) {
			this.start = start;
			this.basicBlock = basicBlock;
		}

		/**
		 * Get the start instruction.
		 */
		public InstructionHandle getStartInstruction() {
			return start;
		}

		/**
		 * Get the basic block.
		 */
		public BasicBlock getBasicBlock() {
			return basicBlock;
		}
	}

	/**
	 * A placeholder for a control edge that escapes its subroutine to return
	 * control back to an outer (calling) subroutine.  It will turn into a
	 * real edge during inlining.
	 */
	private static class EscapeTarget {
		private final InstructionHandle target;
		private final int edgeType;

		/**
		 * Constructor.
		 *
		 * @param target   the target instruction in a calling subroutine
		 * @param edgeType the type of edge that should be created when the
		 *                 subroutine is inlined into its calling context
		 */
		public EscapeTarget(InstructionHandle target, int edgeType) {
			this.target = target;
			this.edgeType = edgeType;
		}

		/**
		 * Get the target instruction.
		 */
		public InstructionHandle getTarget() {
			return target;
		}

		/**
		 * Get the edge type.
		 */
		public int getEdgeType() {
			return edgeType;
		}
	}

	private static final LinkedList<EscapeTarget> emptyEscapeTargetList = new LinkedList<EscapeTarget>();

	/**
	 * JSR subroutine.  The top level subroutine is where execution starts.
	 * Each subroutine has its own CFG.  Eventually,
	 * all JSR subroutines will be inlined into the top level subroutine,
	 * resulting in an accurate CFG for the overall method.
	 */
	private class Subroutine {
		private final InstructionHandle start;
		private final BitSet instructionSet;
		private final CFG cfg;
		private IdentityHashMap<InstructionHandle, BasicBlock> blockMap;
		private IdentityHashMap<BasicBlock, List<EscapeTarget>> escapeTargetListMap;
		private BitSet returnBlockSet;
		private BitSet exitBlockSet;
		private BitSet unhandledExceptionBlockSet;
		private LinkedList<WorkListItem> workList;

		/**
		 * Constructor.
		 *
		 * @param start the start instruction for the subroutine
		 */
		public Subroutine(InstructionHandle start) {
			this.start = start;
			this.instructionSet = new BitSet();
			this.cfg = new CFG();
			this.blockMap = new IdentityHashMap<InstructionHandle, BasicBlock>();
			this.escapeTargetListMap = new IdentityHashMap<BasicBlock, List<EscapeTarget>>();
			this.returnBlockSet = new BitSet();
			this.exitBlockSet = new BitSet();
			this.unhandledExceptionBlockSet = new BitSet();
			this.workList = new LinkedList<WorkListItem>();
		}

		/**
		 * Get the start instruction.
		 */
		public InstructionHandle getStartInstruction() {
			return start;
		}

		/**
		 * Allocate a new basic block in the subroutine.
		 */
		public BasicBlock allocateBasicBlock() {
			return cfg.allocate();
		}

		/**
		 * Add a work list item for a basic block to be constructed.
		 */
		public void addItem(WorkListItem item) {
			workList.add(item);
		}

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

		/**
		 * Get the next work list item.
		 */
		public WorkListItem nextItem() {
			return workList.removeFirst();
		}

		/**
		 * Get the entry block for the subroutine's CFG.
		 */
		public BasicBlock getEntry() {
			return cfg.getEntry();
		}

		/**
		 * Get the exit block for the subroutine's CFG.
		 */
		public BasicBlock getExit() {
			return cfg.getExit();
		}

		/**
		 * Get the start block for the subroutine's CFG.
		 * (I.e., the block containing the start instruction.)
		 */
		public BasicBlock getStartBlock() {
			return getBlock(start);
		}

		/**
		 * Get the subroutine's CFG.
		 */
		public CFG getCFG() {
			return cfg;
		}

		/**
		 * Add an instruction to the subroutine.
		 * We keep track of which instructions are part of which subroutines.
		 * No instruction may be part of more than one subroutine.
		 *
		 * @param handle the instruction to be added to the subroutine
		 */
		public void addInstruction(InstructionHandle handle) throws CFGBuilderException {
			int position = handle.getPosition();
			if (usedInstructionSet.get(position))
				throw new CFGBuilderException("Instruction " + handle + " visited in multiple subroutines");
			instructionSet.set(position);
			usedInstructionSet.set(position);
		}

		/**
		 * Is the given instruction part of this subroutine?
		 */
		public boolean containsInstruction(InstructionHandle handle) {
			return instructionSet.get(handle.getPosition());
		}

		/**
		 * Get the basic block in the subroutine for the given instruction.
		 * If the block doesn't exist yet, it is created, and a work list
		 * item is added which will populate it.  Note that if start is
		 * an exception thrower, the block returned will be its ETB.
		 *
		 * @param start the start instruction for the block
		 * @return the basic block for the instruction
		 */
		public BasicBlock getBlock(InstructionHandle start) {
			BasicBlock block = blockMap.get(start);
			if (block == null) {
				block = allocateBasicBlock();
				blockMap.put(start, block);

				// Block is an exception handler?
				CodeExceptionGen exceptionGen = exceptionHandlerMap.getHandlerForStartInstruction(start);
				if (exceptionGen != null)
					block.setExceptionGen(exceptionGen);

				addItem(new WorkListItem(start, block));
			}
			return block;
		}

		/**
		 * Indicate that the method returns at the end of the given block.
		 *
		 * @param block the returning block
		 */
		public void setReturnBlock(BasicBlock block) {
			returnBlockSet.set(block.getId());
		}

		/**
		 * Does the method return at the end of this block?
		 */
		public boolean isReturnBlock(BasicBlock block) {
			return returnBlockSet.get(block.getId());
		}

		/**
		 * Indicate that System.exit() is called at the end of the given block.
		 *
		 * @param block the exiting block
		 */
		public void setExitBlock(BasicBlock block) {
			exitBlockSet.set(block.getId());
		}

		/**
		 * Is System.exit() called at the end of this block?
		 */
		public boolean isExitBlock(BasicBlock block) {
			return exitBlockSet.get(block.getId());
		}

		/**
		 * Indicate that an unhandled exception may be thrown by
		 * the given block.
		 *
		 * @param block the block throwing an unhandled exception
		 */
		public void setUnhandledExceptionBlock(BasicBlock block) {
			unhandledExceptionBlockSet.set(block.getId());
		}

		/**
		 * Does this block throw an unhandled exception?
		 */
		public boolean isUnhandledExceptionBlock(BasicBlock block) {
			return unhandledExceptionBlockSet.get(block.getId());
		}

		/**
		 * Add a control flow edge to the subroutine.
		 * If the control target has not yet been added to the subroutine,
		 * a new work list item is added.  If the control target is in
		 * another subroutine, an EscapeTarget is added.
		 *