patternmatcher.java

A static analysis tool to find bugs in Java programs

/*
 * 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.bcp;

import java.util.BitSet;
import java.util.IdentityHashMap;
import java.util.Iterator;
import java.util.LinkedList;

import org.apache.bcel.classfile.Method;
import org.apache.bcel.generic.ConstantPoolGen;
import org.apache.bcel.generic.InstructionHandle;

import edu.umd.cs.findbugs.SystemProperties;
import edu.umd.cs.findbugs.annotations.Nullable;
import edu.umd.cs.findbugs.ba.BasicBlock;
import edu.umd.cs.findbugs.ba.CFG;
import edu.umd.cs.findbugs.ba.CFGBuilderException;
import edu.umd.cs.findbugs.ba.ClassContext;
import edu.umd.cs.findbugs.ba.DFSEdgeTypes;
import edu.umd.cs.findbugs.ba.DataflowAnalysisException;
import edu.umd.cs.findbugs.ba.DepthFirstSearch;
import edu.umd.cs.findbugs.ba.DominatorsAnalysis;
import edu.umd.cs.findbugs.ba.Edge;
import edu.umd.cs.findbugs.ba.Location;
import edu.umd.cs.findbugs.ba.vna.ValueNumberDataflow;
import edu.umd.cs.findbugs.ba.vna.ValueNumberFrame;

/**
 * Match a ByteCodePattern against the code of a method, represented
 * by a CFG.  Produces some number of ByteCodePatternMatch objects, which
 * indicate how the pattern matched the bytecode instructions in the method.
 * <p/>
 * <p> This code is a hack and should probably be rewritten.
 *
 * @author David Hovemeyer
 * @see ByteCodePattern
 */
public class PatternMatcher implements DFSEdgeTypes {
	private static final boolean DEBUG = SystemProperties.getBoolean("bcp.debug");
	private static final boolean SHOW_WILD = SystemProperties.getBoolean("bcp.showWild");

	private ByteCodePattern pattern;
	private CFG cfg;
	private ConstantPoolGen cpg;
	private DepthFirstSearch dfs;
	private ValueNumberDataflow vnaDataflow;
	private DominatorsAnalysis domAnalysis;
	private LinkedList<BasicBlock> workList;
	private IdentityHashMap<BasicBlock, BasicBlock> visitedBlockMap;
	private LinkedList<ByteCodePatternMatch> resultList;

	/**
	 * Constructor.
	 *
	 * @param pattern      the ByteCodePattern to look for examples of
	 * @param classContext ClassContext for the class to analyze
	 * @param method       the Method to analyze
	 */
	public PatternMatcher(ByteCodePattern pattern, ClassContext classContext, Method method)
			throws CFGBuilderException, DataflowAnalysisException {
		this.pattern = pattern;
		this.cfg = classContext.getCFG(method);
		this.cpg = classContext.getConstantPoolGen();
		this.dfs = classContext.getDepthFirstSearch(method);
		this.vnaDataflow = classContext.getValueNumberDataflow(method);
		this.domAnalysis = classContext.getNonExceptionDominatorsAnalysis(method);
		this.workList = new LinkedList<BasicBlock>();
		this.visitedBlockMap = new IdentityHashMap<BasicBlock, BasicBlock>();
		this.resultList = new LinkedList<ByteCodePatternMatch>();
	}

	/**
	 * Search for examples of the ByteCodePattern.
	 *
	 * @return this object
	 * @throws DataflowAnalysisException if the ValueNumberAnalysis did not produce useful
	 *                                   values for the method
	 */
	public PatternMatcher execute() throws DataflowAnalysisException {
		workList.addLast(cfg.getEntry());

		while (!workList.isEmpty()) {
			BasicBlock basicBlock = workList.removeLast();
			visitedBlockMap.put(basicBlock, basicBlock);

			// Scan instructions of basic block for possible matches
			BasicBlock.InstructionIterator i = basicBlock.instructionIterator();
			while (i.hasNext()) {
				attemptMatch(basicBlock, i.duplicate());
				i.next();
			}

			// Add successors of the basic block (which haven't been visited already)
			Iterator<BasicBlock> succIterator = cfg.successorIterator(basicBlock);
			while (succIterator.hasNext()) {
				BasicBlock succ = succIterator.next();
				if (visitedBlockMap.get(succ) == null)
					workList.addLast(succ);
			}
		}

		return this;
	}

	/**
	 * Return an Iterator over the ByteCodePatternMatch objects representing
	 * successful matches of the ByteCodePattern.
	 */
	public Iterator<ByteCodePatternMatch> byteCodePatternMatchIterator() {
		return resultList.iterator();
	}

	/**
	 * Attempt to begin a match.
	 *
	 * @param basicBlock          the basic block
	 * @param instructionIterator the instruction iterator positioned just before
	 *                            the first instruction to be matched
	 */
	private void attemptMatch(BasicBlock basicBlock, BasicBlock.InstructionIterator instructionIterator)
			throws DataflowAnalysisException {
		work(new State(basicBlock, instructionIterator, pattern.getFirst()));
	}

	/**
	 * Object representing the current state of the
	 * matching algorithm.  Provides convenient methods to
	 * implement the various steps of the algorithm.
	 */
	private class State {
		private BasicBlock basicBlock;
		private BasicBlock.InstructionIterator instructionIterator;
		private PatternElement patternElement;
		private int matchCount;
		private PatternElementMatch currentMatch;
		private BindingSet bindingSet;
		private boolean canFork;

		/**
		 * Constructor.
		 * Builds the start state.
		 *
		 * @param basicBlock          the initial basic block
		 * @param instructionIterator the instructionIterator indicating where
		 *                            to start matching
		 * @param patternElement      the first PatternElement of the pattern
		 */
		public State(BasicBlock basicBlock, BasicBlock.InstructionIterator instructionIterator,
					 PatternElement patternElement) {
			this(basicBlock, instructionIterator, patternElement, 0, null, null, true);
		}

		/**
		 * Constructor.
		 */
		public State(BasicBlock basicBlock, BasicBlock.InstructionIterator instructionIterator,
					 PatternElement patternElement, int matchCount, @Nullable PatternElementMatch currentMatch,
					 @Nullable BindingSet bindingSet, boolean canFork) {
			this.basicBlock = basicBlock;
			this.instructionIterator = instructionIterator;
			this.patternElement = patternElement;
			this.matchCount = matchCount;
			this.currentMatch = currentMatch;
			this.bindingSet = bindingSet;
			this.canFork = canFork;
		}

		/**
		 * Make an exact copy of this object.
		 */
		public State duplicate() {
			return new State(basicBlock, instructionIterator, patternElement, matchCount, currentMatch, bindingSet, canFork);
		}

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

		/**
		 * Get current pattern element.
		 */
		public PatternElement getPatternElement() {
			return patternElement;
		}

		/**
		 * Get current pattern element match.
		 */
		public PatternElementMatch getCurrentMatch() {
			return currentMatch;
		}

		/**
		 * Determine if the match is complete.
		 */
		public boolean isComplete() {
			// We're done when we reach the end of the chain
			// of pattern elements.
			return patternElement == null;
		}

		/**
		 * Get a ByteCodePatternMatch representing the complete match.
		 */
		public ByteCodePatternMatch getResult() {
			if (!isComplete()) throw new IllegalStateException("match not complete!");
			return new ByteCodePatternMatch(bindingSet, currentMatch);
		}

		/**
		 * Try to produce a new state that will finish matching
		 * the current element and start matching the next element.
		 * Returns null if the current element is not complete.
		 */
		public State advanceToNextElement() {
			if (!canFork || matchCount < patternElement.minOccur())
			// Current element is not complete, or we already
			// forked at this point
				return null;