findpattern.java

代码是一个分类器的实现,其中使用了部分weka的源代码。可以将项目导入eclipse运行

package de.fub.bytecode.generic;

import de.fub.bytecode.Constants;
import de.fub.bytecode.classfile.*;
import gnu.regexp.*;
import com.sun.org.apache.regexp.internal.*;
/** 
 * This class is an utility to search for given patterns, i.e., regular expressions
 * in an instruction list. This can be used in order to implement a
 * peep hole optimizer that looks for code patterns and replaces them with
 * faster equivalents.
 *
 * This class internally uses the package
 * <a href="http://www.cacas.org/~wes/java/">
 * gnu.regexp</a> to search for regular expressions.
 *
 * @version $Id: FindPattern.java,v 1.5 2001/10/11 11:59:27 dahm Exp $
 * @author  <A HREF="http://www.berlin.de/~markus.dahm/">M. Dahm</A>
 * @see     Instruction
 * @see     InstructionList
 * @see     CodeConstraint
 */
public class FindPattern {
  private static final int OFFSET     = 32767; // char + OFFSET is outside of LATIN-1
  private static final int NO_OPCODES = 256;   // Potential number, some are not used

  private static final String[] patterns = {
    "instruction", "branchinstruction", "if_icmp__", "if__", "push",
    "iload__", "aload__", "fload__", "dload__", "lload__",
    "istore__", "astore__", "fstore__", "dstore__", "lstore__",
    "invokeinstruction", "returninstruction", "ifinstruction"
  };

  private static String[] pattern_map; // filled in by static initializer, see below

  private InstructionList     il;
  private String              il_string;    // instruction list as string
  private InstructionHandle[] handles;      // map instruction list to array
  private int                 match_length; // Number of matched instructions
  private int                 matched_from; // Index of match in instruction list

  /**
   * @param il instruction list to search for given patterns
   */
  public FindPattern(InstructionList il) {
    this.il = il;
    reread();
  }

  /**
   * Rereads the instruction list, e.g., after you've altered the list upon a match.
   */
  public final void reread() {
    int    size  = il.getLength();
    char[] buf   = new char[size]; // Create a string with length equal to il length
    handles      = il.getInstructionHandles();

    match_length = -1; // reset match_length

    // Map opcodes to characters
    for(int i=0; i < size; i++)
      buf[i] = makeChar(handles[i].getInstruction().getOpcode());

    il_string = new String(buf);
  }

  /**
   * Map symbolic strings like `branchinstruction' or `'a regular expression string
   * such as (a|b|z) (where a,b,c whil be non-printable characters in LATIN-1)
   *
   * @param pattern instruction pattern in lower case
   * @return encoded string for a pattern such as "BranchInstruction".
   */
  private static final String getPattern(String pattern) {
    // Check for abbreviations
    for(int i=0; i < patterns.length; i++) {
      if(pattern.equals(patterns[i]))
	return pattern_map[i]; // return the string mapped to that name
    }

    // Check for opcode names
    for(short i=0; i < NO_OPCODES; i++)
      if(pattern.equals(Constants.OPCODE_NAMES[i]))
	return new String(new char[] { makeChar(i) });

    return null; // Failed to match
  }

  /**
   * Replace all occurences of `something' with the appropiate pattern, the `' chars
   * are used as an escape sequence.
   * Other characters than the escaped one will be ignored, in particular the meta
   * characters used for regular expression such as *, +, [, etc.
   *
   * @param pattern The pattern to compile
   * @return complete regular expression string
   */
  private static final String makePattern(String pattern) {
    String       lower      = pattern.toLowerCase();
    StringBuffer buf        = new StringBuffer();
    int          size       = pattern.length();
    boolean      in_pattern = false; // remember current state
    StringBuffer collect    = null;

    try {
      for(int i=0; i < size; i++) {
	char ch = lower.charAt(i);
	
	switch(ch) {
	case '`': // Start of instruction pattern
	  if(in_pattern)
	    throw new ClassGenException("` within `' block.");

	  collect    = new StringBuffer();
	  in_pattern = true; // remember current state
	  break;

	case '\'': // end of instruction pattern
	  if(!in_pattern)
	    throw new ClassGenException("' without starting `.");
	  
	  in_pattern = false;
	  String str = collect.toString(); // String within the `'
	  String pat = getPattern(str);

	  if(pat == null)
	    throw new ClassGenException("Unknown instruction pattern: \"" + str +
					"\"" + " at index " + i);
	  buf.append(pat);
	  break;

	default:
	  if(in_pattern)
	    collect.append(ch);
	  else
	    buf.append(ch); // Just append it (meta character)
	}
      }
    } catch(StringIndexOutOfBoundsException e) {
      e.printStackTrace();
    }

    return buf.toString();
  }

  /**
   * Search for the given pattern in the InstructionList. You may use the following
   * special expressions in your pattern string which match instructions that belong
   * to the denoted class. The `' are an escape and <b>must not</b> be omitted.
   *
   * You can use the Instruction names directly:
   *
   * `ILOAD_1', `GOTO', 'NOP', etc..
   *
   * For convenience there exist some abbreviations for instructions that belong
   * to the same group (underscores _ are used as some kind of wildcards):
   *
   * `Instruction', `BranchInstruction', `InvokeInstruction', `ReturnInstruction',
   * `IfInstruction' correspond to their classes.
   *
   * `IF_ICMP__', `IF__', where __ stands for EQ, LE, etc.
   * `xLOAD__', `xSTORE__', where x stands for I, D, F, L or A. __ is 0..3 or empty
   * `PUSH' stands for any LDC, xCONST__, SIPUSH or BIPUSH instruction
   *
   * You <B>must</B> put the `' around these words or they can't be matched correctly.
   *
   * For the rest the usual (PERL) pattern matching rules apply.<P>
   * Example pattern:
   * <pre>
     search("(`BranchInstruction')`NOP'((`IF_ICMP__'|`GOTO')+`ISTORE__'`Instruction')*");
   * </pre>
   *
   *
   * @param pattern the instruction pattern to search for, case is ignored
   * @param from where to start the search in the instruction list
   * @param constraint optional CodeConstraint to check the found code pattern for
   * given constraints
   * @return instruction handle or `null' if the matching fails
   */
  public final InstructionHandle search(String pattern, InstructionHandle from,
					CodeConstraint constraint) {
    String search = makePattern(pattern);
    int  start    = -1;

    match_length = matched_from = -1; // reset

    for(int i=0; i < handles.length; i++) {
      if(handles[i] == from) {
	start = i; // Where to start search from (index)
	break;
      }
    }

    if(start == -1)
      throw new ClassGenException("Instruction handle " + from + 
				  " not found in instruction list.");

    try {
      gnu.regexp.RE regex = new gnu.regexp.RE(search);
   
      REMatch r     = regex.getMatch(il_string, start);
      
      if(r != null) {
	matched_from = r.getStartIndex();
	match_length = (r.getEndIndex() - matched_from);

	if((constraint == null) || constraint.checkCode(getMatch()))
	  return handles[matched_from];
      }
    } catch(REException e) {
      System.err.println(e);
    }

    return null;
  }

  /**
   * Start search beginning from the start of the given instruction list.
   *
   * @param pattern the instruction pattern to search for, case is ignored
   * @return instruction handle or `null' if the matching fails
   */
  public final InstructionHandle search(String pattern) {
    return search(pattern, il.getStart(), null);
  }

  /**
   * Start search beginning from `from'.
   *
   * @param pattern the instruction pattern to search for, case is ignored
   * @param from where to start the search in the instruction list
   * @return instruction handle or `null' if the matching fails
   */
  public final InstructionHandle search(String pattern, InstructionHandle from) {
    return search(pattern, from, null);
  }

  /**
   * Start search beginning from the start of the given instruction list.
   * Check found matches with the constraint object.
   *
   * @param pattern the instruction pattern to search for, case is ignored
   * @param constraint constraints to be checked on matching code
   * @return instruction handle or `null' if the match failed
   */
  public final InstructionHandle search(String pattern, CodeConstraint constraint) {
    return search(pattern, il.getStart(), constraint);
  }