patternmatcher.java

A static analysis tool to find bugs in Java programs

			// Create state to advance to matching next pattern element
			// at current basic block and instruction.
			State advance = new State(basicBlock, instructionIterator.duplicate(), patternElement.getNext(),
					0, currentMatch, bindingSet, true);

			// Now that this state has forked from this element
			// at this instruction, it must not do so again.
			this.canFork = false;

			return advance;
		}

		/**
		 * Determine if the current pattern element can continue
		 * to match instructions.
		 */
		public boolean currentElementCanContinue() {
			return matchCount < patternElement.maxOccur();
		}

		/**
		 * Determine if there are more instructions in the same basic block.
		 */
		public boolean moreInstructionsInBasicBlock() {
			return instructionIterator.hasNext();
		}

		/**
		 * Match current pattern element with next instruction
		 * in basic block.  Returns MatchResult if match succeeds,
		 * null otherwise.
		 */
		public MatchResult matchNextInBasicBlock() throws DataflowAnalysisException {
			if (!moreInstructionsInBasicBlock()) throw new IllegalStateException("At end of BB!");

			// Move to location of next instruction to be matched
			Location location = new Location(instructionIterator.next(), basicBlock);
			return matchLocation(location);
		}

		/**
		 * Determine if it is possible to continue matching
		 * in a successor basic block.
		 */
		public boolean canAdvanceToNextBasicBlock() {
			return currentMatch == null || currentMatch.allowTrailingEdges();
		}

		/**
		 * Get most recently matched instruction.
		 */
		public InstructionHandle getLastMatchedInstruction() {
			if (currentMatch == null) throw new IllegalStateException("no current match!");
			return currentMatch.getMatchedInstructionInstructionHandle();
		}

		/**
		 * Return a new State for continuing the overall pattern match
		 * in a successor basic block.
		 *
		 * @param edge        the Edge leading to the successor basic block
		 * @param matchResult a MatchResult representing the match of the
		 *                    last instruction in the predecessor block; null if none
		 */
		public State advanceToSuccessor(Edge edge, MatchResult matchResult) {
			// If we have just matched an instruction, then we allow the
			// matching PatternElement to choose which edges are acceptable.
			// This allows PatternElements to select particular control edges;
			// for example, only continue the pattern on the true branch
			// of an "if" comparison.
			if (matchResult != null &&
					!matchResult.getPatternElement().acceptBranch(edge, getLastMatchedInstruction()))
				return null;

			return new State(edge.getTarget(), edge.getTarget().instructionIterator(),
					patternElement, matchCount, currentMatch, bindingSet, canFork);
		}

		/**
		 * Determine if we need to look for a dominated instruction at
		 * this point in the search.
		 */
		public boolean lookForDominatedInstruction() {
			return patternElement.getDominatedBy() != null && matchCount == 0;
		}

		/**
		 * Return Iterator over states representing dominated instructions
		 * that continue the match.
		 */
		public Iterator<State> dominatedInstructionStateIterator() throws DataflowAnalysisException {
			if (!lookForDominatedInstruction()) throw new IllegalStateException();
			LinkedList<State> stateList = new LinkedList<State>();

			State dup = this.duplicate();

			if (currentMatch != null) {
				// Find the referenced instruction.
				PatternElementMatch dominator = currentMatch.getFirstLabeledMatch(patternElement.getDominatedBy());
				BasicBlock domBlock = dominator.getBasicBlock();

				// Find all basic blocks dominated by the dominator block.
				for (Iterator<BasicBlock> i = cfg.blockIterator(); i.hasNext();) {
					BasicBlock block = i.next();
					if (block == domBlock)
						continue;

					BitSet dominators = domAnalysis.getResultFact(block);
					if (dominators.get(domBlock.getId())) {
						// This block is dominated by the dominator block.
						// Each instruction in the block which matches the current pattern
						// element is a new state continuing the match.
						for (Iterator<InstructionHandle> j = block.instructionIterator(); j.hasNext();) {
							MatchResult matchResult = dup.matchLocation(new Location(j.next(), block));
							if (matchResult != null) {
								stateList.add(dup);
								dup = this.duplicate();
							}
						}
					}
				}
			}

			return stateList.iterator();
		}

		private MatchResult matchLocation(Location location) throws DataflowAnalysisException {
			// Get the ValueNumberFrames before and after the instruction
			ValueNumberFrame before = vnaDataflow.getFactAtLocation(location);
			ValueNumberFrame after = vnaDataflow.getFactAfterLocation(location);

			// Try to match the instruction against the pattern element.
			boolean debug = DEBUG && (!(patternElement instanceof Wild) || SHOW_WILD);
			if (debug)
				System.out.println("Match " + patternElement +
						" against " + location.getHandle() + " " +
						(bindingSet != null ? bindingSet.toString() : "[]") + "...");
			MatchResult matchResult = patternElement.match(location.getHandle(),
					cpg, before, after, bindingSet);
			if (debug)
				System.out.println("\t" +
						((matchResult != null) ? " ==> MATCH" : " ==> NOT A MATCH"));
			if (matchResult != null) {
				// Successful match!
				// Update state to reflect that the match has occurred.
				++matchCount;
				canFork = true;
				currentMatch = new PatternElementMatch(matchResult.getPatternElement(),
						location.getHandle(), location.getBasicBlock(), matchCount, currentMatch);
				bindingSet = matchResult.getBindingSet();
			}
			return matchResult;
		}
	}

	/**
	 * Match a sequence of pattern elements, starting at the given one.
	 * The InstructionIterator should generally be positioned just before
	 * the next instruction to be matched.  However, it may be positioned
	 * at the end of a basic block, in which case nothing will happen except
	 * that we will try to continue the match in the non-backedge successors
	 * of the basic block.
	 */
	private void work(State state) throws DataflowAnalysisException {
		// Have we reached the end of the pattern?
		if (state.isComplete()) {
			// This is a complete match.
			if (DEBUG) System.out.println("FINISHED A MATCH!");
			resultList.add(state.getResult());
			return;
		}

		// If we've reached the minimum number of occurrences for this
		// pattern element, we can advance to the next pattern element without trying
		// to match this instruction again.  We make sure that we only advance to
		// the next element once for this matchCount.
		State advance = state.advanceToNextElement();
		if (advance != null) {
			work(advance);
		}

		// If we've reached the maximum number of occurrences for this
		// pattern element, then we can't continue.
		if (!state.currentElementCanContinue())
			return;

		MatchResult matchResult = null;

		// Are we looking for an instruction dominated by an earlier
		// matched instruction?
		if (state.lookForDominatedInstruction()) {
			for (Iterator<State> i = state.dominatedInstructionStateIterator(); i.hasNext();)
				work(i.next());
			return;
		}

		// Is there another instruction in this basic block?
		if (state.moreInstructionsInBasicBlock()) {
			// Try to match it.
			matchResult = state.matchNextInBasicBlock();
			if (matchResult == null)
				return;
		}

		// Continue the match at each successor instruction,
		// using the same PatternElement.
		if (state.moreInstructionsInBasicBlock()) {
			// Easy case; continue matching in the same basic block.
			work(state);
		} else if (state.canAdvanceToNextBasicBlock()) {
			// We've reached the end of the basic block.
			// Try to advance to the successors of this basic block,
			// ignoring loop backedges.
			Iterator<Edge> i = cfg.outgoingEdgeIterator(state.getBasicBlock());
			BitSet visitedSuccessorSet = new BitSet();
			while (i.hasNext()) {
				Edge edge = i.next();
				if (dfs.getDFSEdgeType(edge) == BACK_EDGE)
					continue;

				BasicBlock destBlock = edge.getTarget();
				int destId = destBlock.getId();

				// CFGs can have duplicate edges
				if (visitedSuccessorSet.get(destId))
					continue;
				visitedSuccessorSet.set(destId, true);

				// See if we can continue matching in the successor basic block.
				State succState = state.advanceToSuccessor(edge, matchResult);
				if (succState != null) {
					work(succState);
				}
			}
		}

	}
}

// vim:ts=4