PatternMatcher


1   /*
2    * Bytecode Analysis Framework
3    * Copyright (C) 2003,2004 University of Maryland
4    * 
5    * This library is free software; you can redistribute it and/or
6    * modify it under the terms of the GNU Lesser General Public
7    * License as published by the Free Software Foundation; either
8    * version 2.1 of the License, or (at your option) any later version.
9    * 
10   * This library is distributed in the hope that it will be useful,
11   * but WITHOUT ANY WARRANTY; without even the implied warranty of
12   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13   * Lesser General Public License for more details.
14   * 
15   * You should have received a copy of the GNU Lesser General Public
16   * License along with this library; if not, write to the Free Software
17   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
18   */
19  
20  package edu.umd.cs.findbugs.ba.bcp;
21  
22  import java.util.BitSet  ;
23  import java.util.IdentityHashMap  ;
24  import java.util.Iterator  ;
25  import java.util.LinkedList  ;
26  
27  import org.apache.bcel.classfile.Method;
28  import org.apache.bcel.generic.ConstantPoolGen;
29  import org.apache.bcel.generic.InstructionHandle;
30  
31  import edu.umd.cs.findbugs.SystemProperties;
32  import edu.umd.cs.findbugs.annotations.Nullable;
33  import edu.umd.cs.findbugs.ba.BasicBlock;
34  import edu.umd.cs.findbugs.ba.CFG;
35  import edu.umd.cs.findbugs.ba.CFGBuilderException;
36  import edu.umd.cs.findbugs.ba.ClassContext;
37  import edu.umd.cs.findbugs.ba.DFSEdgeTypes;
38  import edu.umd.cs.findbugs.ba.DataflowAnalysisException;
39  import edu.umd.cs.findbugs.ba.DepthFirstSearch;
40  import edu.umd.cs.findbugs.ba.DominatorsAnalysis;
41  import edu.umd.cs.findbugs.ba.Edge;
42  import edu.umd.cs.findbugs.ba.Location;
43  import edu.umd.cs.findbugs.ba.vna.ValueNumberDataflow;
44  import edu.umd.cs.findbugs.ba.vna.ValueNumberFrame;
45  
46  /**
47   * Match a ByteCodePattern against the code of a method, represented
48   * by a CFG.  Produces some number of ByteCodePatternMatch objects, which
49   * indicate how the pattern matched the bytecode instructions in the method.
50   * <p/>
51   * <p> This code is a hack and should probably be rewritten.
52   *
53   * @author David Hovemeyer
54   * @see ByteCodePattern
55   */
56  public class PatternMatcher implements DFSEdgeTypes {
57      private static final boolean DEBUG = SystemProperties.getBoolean("bcp.debug");
58      private static final boolean SHOW_WILD = SystemProperties.getBoolean("bcp.showWild");
59  
60      private ByteCodePattern pattern;
61      private CFG cfg;
62      private ConstantPoolGen cpg;
63      private DepthFirstSearch dfs;
64      private ValueNumberDataflow vnaDataflow;
65      private DominatorsAnalysis domAnalysis;
66      private LinkedList  <BasicBlock> workList;
67      private IdentityHashMap  <BasicBlock, BasicBlock> visitedBlockMap;
68      private LinkedList  <ByteCodePatternMatch> resultList;
69  
70      /**
71       * Constructor.
72       *
73       * @param pattern      the ByteCodePattern to look for examples of
74       * @param classContext ClassContext for the class to analyze
75       * @param method       the Method to analyze
76       */
77      public PatternMatcher(ByteCodePattern pattern, ClassContext classContext, Method method)
78              throws CFGBuilderException, DataflowAnalysisException {
79          this.pattern = pattern;
80          this.cfg = classContext.getCFG(method);
81          this.cpg = classContext.getConstantPoolGen();
82          this.dfs = classContext.getDepthFirstSearch(method);
83          this.vnaDataflow = classContext.getValueNumberDataflow(method);
84          this.domAnalysis = classContext.getNonExceptionDominatorsAnalysis(method);
85          this.workList = new LinkedList  <BasicBlock>();
86          this.visitedBlockMap = new IdentityHashMap  <BasicBlock, BasicBlock>();
87          this.resultList = new LinkedList  <ByteCodePatternMatch>();
88      }
89  
90      /**
91       * Search for examples of the ByteCodePattern.
92       *
93       * @return this object
94       * @throws DataflowAnalysisException if the ValueNumberAnalysis did not produce useful
95       *                                   values for the method
96       */
97      public PatternMatcher execute() throws DataflowAnalysisException {
98          workList.addLast(cfg.getEntry());
99  
100         while (!workList.isEmpty()) {
101             BasicBlock basicBlock = workList.removeLast();
102             visitedBlockMap.put(basicBlock, basicBlock);
103 
104             // Scan instructions of basic block for possible matches
105             BasicBlock.InstructionIterator i = basicBlock.instructionIterator();
106             while (i.hasNext()) {
107                 attemptMatch(basicBlock, i.duplicate());
108                 i.next();
109             }
110 
111             // Add successors of the basic block (which haven't been visited already)
112             Iterator  <BasicBlock> succIterator = cfg.successorIterator(basicBlock);
113             while (succIterator.hasNext()) {
114                 BasicBlock succ = succIterator.next();
115                 if (visitedBlockMap.get(succ) == null)
116                     workList.addLast(succ);
117             }
118         }
119 
120         return this;
121     }
122 
123     /**
124      * Return an Iterator over the ByteCodePatternMatch objects representing
125      * successful matches of the ByteCodePattern.
126      */
127     public Iterator  <ByteCodePatternMatch> byteCodePatternMatchIterator() {
128         return resultList.iterator();
129     }
130 
131     /**
132      * Attempt to begin a match.
133      *
134      * @param basicBlock          the basic block
135      * @param instructionIterator the instruction iterator positioned just before
136      *                            the first instruction to be matched
137      */
138     private void attemptMatch(BasicBlock basicBlock, BasicBlock.InstructionIterator instructionIterator)
139             throws DataflowAnalysisException {
140         work(new State(basicBlock, instructionIterator, pattern.getFirst()));
141     }
142 
143     /**
144      * Object representing the current state of the
145      * matching algorithm.  Provides convenient methods to
146      * implement the various steps of the algorithm.
147      */
148     private class State {
149         private BasicBlock basicBlock;
150         private BasicBlock.InstructionIterator instructionIterator;
151         private PatternElement patternElement;
152         private int matchCount;
153         private PatternElementMatch currentMatch;
154         private BindingSet bindingSet;
155         private boolean canFork;
156 
157         /**
158          * Constructor.
159          * Builds the start state.
160          *
161          * @param basicBlock          the initial basic block
162          * @param instructionIterator the instructionIterator indicating where
163          *                            to start matching
164          * @param patternElement      the first PatternElement of the pattern
165          */
166         public State(BasicBlock basicBlock, BasicBlock.InstructionIterator instructionIterator,
167                      PatternElement patternElement) {
168             this(basicBlock, instructionIterator, patternElement, 0, null, null, true);
169         }
170 
171         /**
172          * Constructor.
173          */
174         public State(BasicBlock basicBlock, BasicBlock.InstructionIterator instructionIterator,
175                      PatternElement patternElement, int matchCount, @Nullable PatternElementMatch currentMatch,
176                      @Nullable BindingSet bindingSet, boolean canFork) {
177             this.basicBlock = basicBlock;
178             this.instructionIterator = instructionIterator;
179             this.patternElement = patternElement;
180             this.matchCount = matchCount;
181             this.currentMatch = currentMatch;
182             this.bindingSet = bindingSet;
183             this.canFork = canFork;
184         }
185 
186         /**
187          * Make an exact copy of this object.
188          */
189         public State duplicate() {
190             return new State(basicBlock, instructionIterator, patternElement, matchCount, currentMatch, bindingSet, canFork);
191         }
192 
193         /**
194          * Get basic block.
195          */
196         public BasicBlock getBasicBlock() {
197             return basicBlock;
198         }
199 
200         /**
201          * Get current pattern element.
202          */
203         public PatternElement getPatternElement() {
204             return patternElement;
205         }
206 
207         /**
208          * Get current pattern element match.
209          */
210         public PatternElementMatch getCurrentMatch() {
211             return currentMatch;
212         }
213 
214         /**
215          * Determine if the match is complete.
216          */
217         public boolean isComplete() {
218             // We're done when we reach the end of the chain
219             // of pattern elements.
220             return patternElement == null;
221         }
222 
223         /**
224          * Get a ByteCodePatternMatch representing the complete match.
225          */
226         public ByteCodePatternMatch getResult() {
227             if (!isComplete()) throw new IllegalStateException  ("match not complete!");
228             return new ByteCodePatternMatch(bindingSet, currentMatch);
229         }
230 
231         /**
232          * Try to produce a new state that will finish matching
233          * the current element and start matching the next element.
234          * Returns null if the current element is not complete.
235          */
236         public State advanceToNextElement() {
237             if (!canFork || matchCount < patternElement.minOccur())
238             // Current element is not complete, or we already
239             // forked at this point
240                 return null;
241 
242             // Create state to advance to matching next pattern element
243             // at current basic block and instruction.
244             State advance = new State(basicBlock, instructionIterator.duplicate(), patternElement.getNext(),
245                     0, currentMatch, bindingSet, true);
246 
247             // Now that this state has forked from this element
248             // at this instruction, it must not do so again.
249             this.canFork = false;
250 
251             return advance;
252         }
253 
254         /**
255          * Determine if the current pattern element can continue
256          * to match instructions.
257          */
258         public boolean currentElementCanContinue() {
259             return matchCount < patternElement.maxOccur();
260         }
261 
262         /**
263          * Determine if there are more instructions in the same basic block.
264          */
265         public boolean moreInstructionsInBasicBlock() {
266             return instructionIterator.hasNext();
267         }
268 
269         /**
270          * Match current pattern element with next instruction
271          * in basic block.  Returns MatchResult if match succeeds,
272          * null otherwise.
273          */
274         public MatchResult matchNextInBasicBlock() throws DataflowAnalysisException {
275             if (!moreInstructionsInBasicBlock()) throw new IllegalStateException  ("At end of BB!");
276 
277             // Move to location of next instruction to be matched
278             Location location = new Location(instructionIterator.next(), basicBlock);
279             return matchLocation(location);
280         }
281 
282         /**
283          * Determine if it is possible to continue matching
284          * in a successor basic block.
285          */
286         public boolean canAdvanceToNextBasicBlock() {
287             return currentMatch == null || currentMatch.allowTrailingEdges();
288         }
289 
290         /**
291          * Get most recently matched instruction.
292          */
293         public InstructionHandle getLastMatchedInstruction() {
294             if (currentMatch == null) throw new IllegalStateException  ("no current match!");
295             return currentMatch.getMatchedInstructionInstructionHandle();
296         }
297 
298         /**
299          * Return a new State for continuing the overall pattern match
300          * in a successor basic block.
301          *
302          * @param edge        the Edge leading to the successor basic block
303          * @param matchResult a MatchResult representing the match of the
304          *                    last instruction in the predecessor block; null if none
305          */
306         public State advanceToSuccessor(Edge edge, MatchResult matchResult) {
307             // If we have just matched an instruction, then we allow the
308             // matching PatternElement to choose which edges are acceptable.
309             // This allows PatternElements to select particular control edges;
310             // for example, only continue the pattern on the true branch
311             // of an "if" comparison.
312             if (matchResult != null &&
313                     !matchResult.getPatternElement().acceptBranch(edge, getLastMatchedInstruction()))
314                 return null;
315 
316             return new State(edge.getTarget(), edge.getTarget().instructionIterator(),
317                     patternElement, matchCount, currentMatch, bindingSet, canFork);
318         }
319 
320         /**
321          * Determine if we need to look for a dominated instruction at
322          * this point in the search.
323          */
324         public boolean lookForDominatedInstruction() {
325             return patternElement.getDominatedBy() != null && matchCount == 0;
326         }
327 
328         /**
329          * Return Iterator over states representing dominated instructions
330          * that continue the match.
331          */
332         public Iterator  <State> dominatedInstructionStateIterator() throws DataflowAnalysisException {
333             if (!lookForDominatedInstruction()) throw new IllegalStateException  ();
334             LinkedList  <State> stateList = new LinkedList  <State>();
335 
336             State dup = this.duplicate();
337 
338             if (currentMatch != null) {
339                 // Find the referenced instruction.
340                 PatternElementMatch dominator = currentMatch.getFirstLabeledMatch(patternElement.getDominatedBy());
341                 BasicBlock domBlock = dominator.getBasicBlock();
342 
343                 // Find all basic blocks dominated by the dominator block.
344                 for (Iterator  <BasicBlock> i = cfg.blockIterator(); i.hasNext();) {
345                     BasicBlock block = i.next();
346                     if (block == domBlock)
347                         continue;
348 
349                     BitSet   dominators = domAnalysis.getResultFact(block);
350                     if (dominators.get(domBlock.getId())) {
351                         // This block is dominated by the dominator block.
352                         // Each instruction in the block which matches the current pattern
353                         // element is a new state continuing the match.
354                         for (Iterator  <InstructionHandle> j = block.instructionIterator(); j.hasNext();) {
355                             MatchResult matchResult = dup.matchLocation(new Location(j.next(), block));
356                             if (matchResult != null) {
357                                 stateList.add(dup);
358                                 dup = this.duplicate();
359                             }
360                         }
361                     }
362                 }
363             }
364 
365             return stateList.iterator();
366         }
367 
368         private MatchResult matchLocation(Location location) throws DataflowAnalysisException {
369             // Get the ValueNumberFrames before and after the instruction
370             ValueNumberFrame before = vnaDataflow.getFactAtLocation(location);
371             ValueNumberFrame after = vnaDataflow.getFactAfterLocation(location);
372 
373             // Try to match the instruction against the pattern element.
374             boolean debug = DEBUG && (!(patternElement instanceof Wild) || SHOW_WILD);
375             if (debug)
376                 System.out.println("Match " + patternElement +
377                         " against " + location.getHandle() + " " +
378                         (bindingSet != null ? bindingSet.toString() : "[]") + "...");
379             MatchResult matchResult = patternElement.match(location.getHandle(),
380                     cpg, before, after, bindingSet);
381             if (debug)
382                 System.out.println("\t" +
383                         ((matchResult != null) ? " ==> MATCH" : " ==> NOT A MATCH"));
384             if (matchResult != null) {
385                 // Successful match!
386                 // Update state to reflect that the match has occurred.
387                 ++matchCount;
388                 canFork = true;
389                 currentMatch = new PatternElementMatch(matchResult.getPatternElement(),
390                         location.getHandle(), location.getBasicBlock(), matchCount, currentMatch);
391                 bindingSet = matchResult.getBindingSet();
392             }
393             return matchResult;
394         }
395     }
396 
397     /**
398      * Match a sequence of pattern elements, starting at the given one.
399      * The InstructionIterator should generally be positioned just before
400      * the next instruction to be matched.  However, it may be positioned
401      * at the end of a basic block, in which case nothing will happen except
402      * that we will try to continue the match in the non-backedge successors
403      * of the basic block.
404      */
405     private void work(State state) throws DataflowAnalysisException {
406         // Have we reached the end of the pattern?
407         if (state.isComplete()) {
408             // This is a complete match.
409             if (DEBUG) System.out.println("FINISHED A MATCH!");
410             resultList.add(state.getResult());
411             return;
412         }
413 
414         // If we've reached the minimum number of occurrences for this
415         // pattern element, we can advance to the next pattern element without trying
416         // to match this instruction again.  We make sure that we only advance to
417         // the next element once for this matchCount.
418         State advance = state.advanceToNextElement();
419         if (advance != null) {
420             work(advance);
421         }
422 
423         // If we've reached the maximum number of occurrences for this
424         // pattern element, then we can't continue.
425         if (!state.currentElementCanContinue())
426             return;
427 
428         MatchResult matchResult = null;
429 
430         // Are we looking for an instruction dominated by an earlier
431         // matched instruction?
432         if (state.lookForDominatedInstruction()) {
433             for (Iterator  <State> i = state.dominatedInstructionStateIterator(); i.hasNext();)
434                 work(i.next());
435             return;
436         }
437 
438         // Is there another instruction in this basic block?
439         if (state.moreInstructionsInBasicBlock()) {
440             // Try to match it.
441             matchResult = state.matchNextInBasicBlock();
442             if (matchResult == null)
443                 return;
444         }
445 
446         // Continue the match at each successor instruction,
447         // using the same PatternElement.
448         if (state.moreInstructionsInBasicBlock()) {
449             // Easy case; continue matching in the same basic block.
450             work(state);
451         } else if (state.canAdvanceToNextBasicBlock()) {
452             // We've reached the end of the basic block.
453             // Try to advance to the successors of this basic block,
454             // ignoring loop backedges.
455             Iterator  <Edge> i = cfg.outgoingEdgeIterator(state.getBasicBlock());
456             BitSet   visitedSuccessorSet = new BitSet  ();
457             while (i.hasNext()) {
458                 Edge edge = i.next();
459                 if (dfs.getDFSEdgeType(edge) == BACK_EDGE)
460                     continue;
461 
462                 BasicBlock destBlock = edge.getTarget();
463                 int destId = destBlock.getId();
464 
465                 // CFGs can have duplicate edges
466                 if (visitedSuccessorSet.get(destId))
467                     continue;
468                 visitedSuccessorSet.set(destId, true);
469 
470                 // See if we can continue matching in the successor basic block.
471                 State succState = state.advanceToSuccessor(edge, matchResult);
472                 if (succState != null) {
473                     work(succState);
474                 }
475             }
476         }
477 
478     }
479 }
480 
481 // vim:ts=4
482
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags