| /* |
| * ProGuard -- shrinking, optimization, obfuscation, and preverification |
| * of Java bytecode. |
| * |
| * Copyright (c) 2002-2014 Eric Lafortune (eric@graphics.cornell.edu) |
| * |
| * This program is free software; you can redistribute it and/or modify it |
| * under the terms of the GNU General Public License as published by the Free |
| * Software Foundation; either version 2 of the License, or (at your option) |
| * any later version. |
| * |
| * This program 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 General Public License for |
| * more details. |
| * |
| * You should have received a copy of the GNU General Public License along |
| * with this program; if not, write to the Free Software Foundation, Inc., |
| * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
| */ |
| package proguard.classfile.util; |
| |
| import proguard.classfile.*; |
| import proguard.classfile.attribute.CodeAttribute; |
| import proguard.classfile.constant.*; |
| import proguard.classfile.constant.visitor.ConstantVisitor; |
| import proguard.classfile.instruction.*; |
| import proguard.classfile.instruction.visitor.InstructionVisitor; |
| |
| import java.util.Arrays; |
| |
| /** |
| * This InstructionVisitor checks whether a given pattern instruction sequence |
| * occurs in the instructions that are visited. The arguments of the |
| * instruction sequence can be wildcards that are matched. |
| * |
| * @author Eric Lafortune |
| */ |
| public class InstructionSequenceMatcher |
| extends SimplifiedVisitor |
| implements InstructionVisitor, |
| ConstantVisitor |
| { |
| //* |
| private static final boolean DEBUG = false; |
| private static final boolean DEBUG_MORE = false; |
| /*/ |
| public static boolean DEBUG = true; |
| public static boolean DEBUG_MORE = true; |
| //*/ |
| |
| public static final int X = 0x40000000; |
| public static final int Y = 0x40000001; |
| public static final int Z = 0x40000002; |
| |
| public static final int A = 0x40000003; |
| public static final int B = 0x40000004; |
| public static final int C = 0x40000005; |
| public static final int D = 0x40000006; |
| |
| |
| private final Constant[] patternConstants; |
| private final Instruction[] patternInstructions; |
| |
| private boolean matching; |
| private int patternInstructionIndex; |
| private final int[] matchedInstructionOffsets; |
| private int matchedArgumentFlags; |
| private final int[] matchedArguments = new int[7]; |
| private final long[] matchedConstantFlags; |
| private final int[] matchedConstantIndices; |
| private int constantFlags; |
| private int previousConstantFlags; |
| |
| // Fields acting as a parameter and a return value for visitor methods. |
| private Constant patternConstant; |
| private boolean matchingConstant; |
| |
| |
| /** |
| * Creates a new InstructionSequenceMatcher. |
| * @param patternConstants any constants referenced by the pattern |
| * instruction. |
| * @param patternInstructions the pattern instruction sequence. |
| */ |
| public InstructionSequenceMatcher(Constant[] patternConstants, |
| Instruction[] patternInstructions) |
| { |
| this.patternConstants = patternConstants; |
| this.patternInstructions = patternInstructions; |
| |
| matchedInstructionOffsets = new int[patternInstructions.length]; |
| matchedConstantFlags = new long[(patternConstants.length + 63) / 64]; |
| matchedConstantIndices = new int[patternConstants.length]; |
| } |
| |
| |
| /** |
| * Starts matching from the first instruction again next time. |
| */ |
| public void reset() |
| { |
| patternInstructionIndex = 0; |
| matchedArgumentFlags = 0; |
| |
| Arrays.fill(matchedConstantFlags, 0L); |
| |
| previousConstantFlags = constantFlags; |
| constantFlags = 0; |
| } |
| |
| |
| /** |
| * Returns whether the complete pattern sequence has been matched. |
| */ |
| public boolean isMatching() |
| { |
| return matching; |
| } |
| |
| |
| /** |
| * Returns the number of instructions in the pattern sequence. |
| */ |
| public int instructionCount() |
| { |
| return patternInstructions.length; |
| } |
| |
| |
| /** |
| * Returns the matched instruction offset of the specified pattern |
| * instruction. |
| */ |
| public int matchedInstructionOffset(int index) |
| { |
| return matchedInstructionOffsets[index]; |
| } |
| |
| |
| /** |
| * Returns whether the specified wildcard argument was a constant from |
| * the constant pool in the most recent match. |
| */ |
| public boolean wasConstant(int argument) |
| { |
| return (previousConstantFlags & (1 << (argument - X))) != 0; |
| } |
| |
| |
| /** |
| * Returns the value of the specified matched argument (wildcard or not). |
| */ |
| public int matchedArgument(int argument) |
| { |
| int argumentIndex = argument - X; |
| return argumentIndex < 0 ? |
| argument : |
| matchedArguments[argumentIndex]; |
| } |
| |
| |
| /** |
| * Returns the values of the specified matched arguments (wildcard or not). |
| */ |
| public int[] matchedArguments(int[] arguments) |
| { |
| int[] matchedArguments = new int[arguments.length]; |
| |
| for (int index = 0; index < arguments.length; index++) |
| { |
| matchedArguments[index] = matchedArgument(arguments[index]); |
| } |
| |
| return matchedArguments; |
| } |
| |
| |
| /** |
| * Returns the index of the specified matched constant (wildcard or not). |
| */ |
| public int matchedConstantIndex(int constantIndex) |
| { |
| int argumentIndex = constantIndex - X; |
| return argumentIndex < 0 ? |
| matchedConstantIndices[constantIndex] : |
| matchedArguments[argumentIndex]; |
| } |
| |
| |
| /** |
| * Returns the value of the specified matched branch offset (wildcard or |
| * not). |
| */ |
| public int matchedBranchOffset(int offset, int branchOffset) |
| { |
| int argumentIndex = branchOffset - X; |
| return argumentIndex < 0 ? |
| branchOffset : |
| matchedArguments[argumentIndex] - offset; |
| } |
| |
| |
| /** |
| * Returns the values of the specified matched jump offsets (wildcard or |
| * not). |
| */ |
| public int[] matchedJumpOffsets(int offset, int[] jumpOffsets) |
| { |
| int[] matchedJumpOffsets = new int[jumpOffsets.length]; |
| |
| for (int index = 0; index < jumpOffsets.length; index++) |
| { |
| matchedJumpOffsets[index] = matchedBranchOffset(offset, |
| jumpOffsets[index]); |
| } |
| |
| return matchedJumpOffsets; |
| } |
| |
| |
| // Implementations for InstructionVisitor. |
| |
| public void visitSimpleInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, SimpleInstruction simpleInstruction) |
| { |
| Instruction patternInstruction = patternInstructions[patternInstructionIndex]; |
| |
| // Check if the instruction matches the next instruction in the sequence. |
| boolean condition = |
| matchingOpcodes(simpleInstruction, patternInstruction) && |
| matchingArguments(simpleInstruction.constant, |
| ((SimpleInstruction)patternInstruction).constant); |
| |
| // Check if the instruction sequence is matching now. |
| checkMatch(condition, |
| clazz, |
| method, |
| codeAttribute, |
| offset, |
| simpleInstruction); |
| } |
| |
| |
| public void visitVariableInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, VariableInstruction variableInstruction) |
| { |
| Instruction patternInstruction = patternInstructions[patternInstructionIndex]; |
| |
| // Check if the instruction matches the next instruction in the sequence. |
| boolean condition = |
| matchingOpcodes(variableInstruction, patternInstruction) && |
| matchingArguments(variableInstruction.variableIndex, |
| ((VariableInstruction)patternInstruction).variableIndex) && |
| matchingArguments(variableInstruction.constant, |
| ((VariableInstruction)patternInstruction).constant); |
| |
| // Check if the instruction sequence is matching now. |
| checkMatch(condition, |
| clazz, |
| method, |
| codeAttribute, |
| offset, |
| variableInstruction); |
| } |
| |
| |
| public void visitConstantInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, ConstantInstruction constantInstruction) |
| { |
| Instruction patternInstruction = patternInstructions[patternInstructionIndex]; |
| |
| // Check if the instruction matches the next instruction in the sequence. |
| boolean condition = |
| matchingOpcodes(constantInstruction, patternInstruction) && |
| matchingConstantIndices(clazz, |
| constantInstruction.constantIndex, |
| ((ConstantInstruction)patternInstruction).constantIndex) && |
| matchingArguments(constantInstruction.constant, |
| ((ConstantInstruction)patternInstruction).constant); |
| |
| // Check if the instruction sequence is matching now. |
| checkMatch(condition, |
| clazz, |
| method, |
| codeAttribute, |
| offset, |
| constantInstruction); |
| } |
| |
| |
| public void visitBranchInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, BranchInstruction branchInstruction) |
| { |
| Instruction patternInstruction = patternInstructions[patternInstructionIndex]; |
| |
| // Check if the instruction matches the next instruction in the from |
| // sequence. |
| boolean condition = |
| matchingOpcodes(branchInstruction, patternInstruction) && |
| matchingBranchOffsets(offset, |
| branchInstruction.branchOffset, |
| ((BranchInstruction)patternInstruction).branchOffset); |
| |
| // Check if the instruction sequence is matching now. |
| checkMatch(condition, |
| clazz, |
| method, |
| codeAttribute, |
| offset, |
| branchInstruction); |
| } |
| |
| |
| public void visitTableSwitchInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, TableSwitchInstruction tableSwitchInstruction) |
| { |
| Instruction patternInstruction = patternInstructions[patternInstructionIndex]; |
| |
| // Check if the instruction matches the next instruction in the sequence. |
| boolean condition = |
| matchingOpcodes(tableSwitchInstruction, patternInstruction) && |
| matchingBranchOffsets(offset, |
| tableSwitchInstruction.defaultOffset, |
| ((TableSwitchInstruction)patternInstruction).defaultOffset) && |
| matchingArguments(tableSwitchInstruction.lowCase, |
| ((TableSwitchInstruction)patternInstruction).lowCase) && |
| matchingArguments(tableSwitchInstruction.highCase, |
| ((TableSwitchInstruction)patternInstruction).highCase) && |
| matchingJumpOffsets(offset, |
| tableSwitchInstruction.jumpOffsets, |
| ((TableSwitchInstruction)patternInstruction).jumpOffsets); |
| |
| // Check if the instruction sequence is matching now. |
| checkMatch(condition, |
| clazz, |
| method, |
| codeAttribute, |
| offset, |
| tableSwitchInstruction); |
| } |
| |
| |
| public void visitLookUpSwitchInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, LookUpSwitchInstruction lookUpSwitchInstruction) |
| { |
| Instruction patternInstruction = patternInstructions[patternInstructionIndex]; |
| |
| // Check if the instruction matches the next instruction in the sequence. |
| boolean condition = |
| matchingOpcodes(lookUpSwitchInstruction, patternInstruction) && |
| matchingBranchOffsets(offset, |
| lookUpSwitchInstruction.defaultOffset, |
| ((LookUpSwitchInstruction)patternInstruction).defaultOffset) && |
| matchingArguments(lookUpSwitchInstruction.cases, |
| ((LookUpSwitchInstruction)patternInstruction).cases) && |
| matchingJumpOffsets(offset, |
| lookUpSwitchInstruction.jumpOffsets, |
| ((LookUpSwitchInstruction)patternInstruction).jumpOffsets); |
| |
| // Check if the instruction sequence is matching now. |
| checkMatch(condition, |
| clazz, |
| method, |
| codeAttribute, |
| offset, |
| lookUpSwitchInstruction); |
| } |
| |
| |
| // Implementations for ConstantVisitor. |
| |
| public void visitIntegerConstant(Clazz clazz, IntegerConstant integerConstant) |
| { |
| IntegerConstant integerPatternConstant = (IntegerConstant)patternConstant; |
| |
| // Compare the integer values. |
| matchingConstant = integerConstant.getValue() == |
| integerPatternConstant.getValue(); |
| } |
| |
| |
| public void visitLongConstant(Clazz clazz, LongConstant longConstant) |
| { |
| LongConstant longPatternConstant = (LongConstant)patternConstant; |
| |
| // Compare the long values. |
| matchingConstant = longConstant.getValue() == |
| longPatternConstant.getValue(); |
| } |
| |
| |
| public void visitFloatConstant(Clazz clazz, FloatConstant floatConstant) |
| { |
| FloatConstant floatPatternConstant = (FloatConstant)patternConstant; |
| |
| // Compare the float values. |
| matchingConstant = floatConstant.getValue() == |
| floatPatternConstant.getValue(); |
| } |
| |
| |
| public void visitDoubleConstant(Clazz clazz, DoubleConstant doubleConstant) |
| { |
| DoubleConstant doublePatternConstant = (DoubleConstant)patternConstant; |
| |
| // Compare the double values. |
| matchingConstant = doubleConstant.getValue() == |
| doublePatternConstant.getValue(); |
| } |
| |
| |
| public void visitStringConstant(Clazz clazz, StringConstant stringConstant) |
| { |
| StringConstant stringPatternConstant = (StringConstant)patternConstant; |
| |
| // Check the UTF-8 constant. |
| matchingConstant = |
| matchingConstantIndices(clazz, |
| stringConstant.u2stringIndex, |
| stringPatternConstant.u2stringIndex); |
| } |
| |
| |
| public void visitUtf8Constant(Clazz clazz, Utf8Constant utf8Constant) |
| { |
| Utf8Constant utf8PatternConstant = (Utf8Constant)patternConstant; |
| |
| // Compare the actual strings. |
| matchingConstant = utf8Constant.getString().equals( |
| utf8PatternConstant.getString()); |
| } |
| |
| |
| public void visitInvokeDynamicConstant(Clazz clazz, InvokeDynamicConstant invokeDynamicConstant) |
| { |
| InvokeDynamicConstant invokeDynamicPatternConstant = (InvokeDynamicConstant)patternConstant; |
| |
| // Check the bootstrap method and the name and type. |
| matchingConstant = |
| matchingConstantIndices(clazz, |
| invokeDynamicConstant.getBootstrapMethodAttributeIndex(), |
| invokeDynamicPatternConstant.getBootstrapMethodAttributeIndex()) && |
| matchingConstantIndices(clazz, |
| invokeDynamicConstant.getNameAndTypeIndex(), |
| invokeDynamicPatternConstant.getNameAndTypeIndex()); |
| } |
| |
| |
| public void visitMethodHandleConstant(Clazz clazz, MethodHandleConstant methodHandleConstant) |
| { |
| MethodHandleConstant methodHandlePatternConstant = (MethodHandleConstant)patternConstant; |
| |
| // Check the handle type and the name and type. |
| matchingConstant = |
| matchingArguments(methodHandleConstant.getReferenceKind(), |
| methodHandlePatternConstant.getReferenceKind()) && |
| matchingConstantIndices(clazz, |
| methodHandleConstant.getReferenceIndex(), |
| methodHandlePatternConstant.getReferenceIndex()); |
| } |
| |
| |
| public void visitAnyRefConstant(Clazz clazz, RefConstant refConstant) |
| { |
| RefConstant refPatternConstant = (RefConstant)patternConstant; |
| |
| // Check the class and the name and type. |
| matchingConstant = |
| matchingConstantIndices(clazz, |
| refConstant.getClassIndex(), |
| refPatternConstant.getClassIndex()) && |
| matchingConstantIndices(clazz, |
| refConstant.getNameAndTypeIndex(), |
| refPatternConstant.getNameAndTypeIndex()); |
| } |
| |
| |
| public void visitClassConstant(Clazz clazz, ClassConstant classConstant) |
| { |
| ClassConstant classPatternConstant = (ClassConstant)patternConstant; |
| |
| // Check the class name. |
| matchingConstant = |
| matchingConstantIndices(clazz, |
| classConstant.u2nameIndex, |
| classPatternConstant.u2nameIndex); |
| } |
| |
| |
| public void visitMethodTypeConstant(Clazz clazz, MethodTypeConstant methodTypeConstant) |
| { |
| MethodTypeConstant typePatternConstant = (MethodTypeConstant)patternConstant; |
| |
| // Check the descriptor. |
| matchingConstant = |
| matchingConstantIndices(clazz, |
| methodTypeConstant.u2descriptorIndex, |
| typePatternConstant.u2descriptorIndex); |
| } |
| |
| |
| public void visitNameAndTypeConstant(Clazz clazz, NameAndTypeConstant nameAndTypeConstant) |
| { |
| NameAndTypeConstant typePatternConstant = (NameAndTypeConstant)patternConstant; |
| |
| // Check the name and the descriptor. |
| matchingConstant = |
| matchingConstantIndices(clazz, |
| nameAndTypeConstant.u2nameIndex, |
| typePatternConstant.u2nameIndex) && |
| matchingConstantIndices(clazz, |
| nameAndTypeConstant.u2descriptorIndex, |
| typePatternConstant.u2descriptorIndex); |
| } |
| |
| |
| // Small utility methods. |
| |
| private boolean matchingOpcodes(Instruction instruction1, |
| Instruction instruction2) |
| { |
| // Check the opcode. |
| return instruction1.opcode == instruction2.opcode || |
| instruction1.canonicalOpcode() == instruction2.opcode; |
| } |
| |
| |
| private boolean matchingArguments(int argument1, |
| int argument2) |
| { |
| int argumentIndex = argument2 - X; |
| if (argumentIndex < 0) |
| { |
| // Check the literal argument. |
| return argument1 == argument2; |
| } |
| else if (!isMatchingArgumentIndex(argumentIndex)) |
| { |
| // Store the wildcard argument. |
| setMatchingArgument(argumentIndex, argument1); |
| |
| return true; |
| } |
| else |
| { |
| // Check the previously stored wildcard argument. |
| return matchedArguments[argumentIndex] == argument1; |
| } |
| } |
| |
| |
| /** |
| * Marks the specified argument (by index) as matching the specified |
| * argument value. |
| */ |
| private void setMatchingArgument(int argumentIndex, |
| int argument) |
| { |
| matchedArguments[argumentIndex] = argument; |
| matchedArgumentFlags |= 1 << argumentIndex; |
| } |
| |
| |
| /** |
| * Returns whether the specified wildcard argument (by index) has been |
| * matched. |
| */ |
| private boolean isMatchingArgumentIndex(int argumentIndex) |
| { |
| return (matchedArgumentFlags & (1 << argumentIndex)) != 0; |
| } |
| |
| |
| private boolean matchingArguments(int[] arguments1, |
| int[] arguments2) |
| { |
| if (arguments1.length != arguments2.length) |
| { |
| return false; |
| } |
| |
| for (int index = 0; index < arguments1.length; index++) |
| { |
| if (!matchingArguments(arguments1[index], arguments2[index])) |
| { |
| return false; |
| } |
| } |
| |
| return true; |
| } |
| |
| |
| private boolean matchingConstantIndices(Clazz clazz, |
| int constantIndex1, |
| int constantIndex2) |
| { |
| if (constantIndex2 >= X) |
| { |
| // Remember that we are trying to match a constant. |
| constantFlags |= 1 << (constantIndex2 - X); |
| |
| // Check the constant index. |
| return matchingArguments(constantIndex1, constantIndex2); |
| } |
| else if (!isMatchingConstantIndex(constantIndex2)) |
| { |
| // Check the actual constant. |
| matchingConstant = false; |
| patternConstant = patternConstants[constantIndex2]; |
| |
| if (clazz.getTag(constantIndex1) == patternConstant.getTag()) |
| { |
| clazz.constantPoolEntryAccept(constantIndex1, this); |
| |
| if (matchingConstant) |
| { |
| // Store the constant index. |
| setMatchingConstant(constantIndex2, constantIndex1); |
| } |
| } |
| |
| return matchingConstant; |
| } |
| else |
| { |
| // Check a previously stored constant index. |
| return matchedConstantIndices[constantIndex2] == constantIndex1; |
| } |
| } |
| |
| |
| /** |
| * Marks the specified constant (by index) as matching the specified |
| * constant index value. |
| */ |
| private void setMatchingConstant(int constantIndex, |
| int constantIndex1) |
| { |
| matchedConstantIndices[constantIndex] = constantIndex1; |
| matchedConstantFlags[constantIndex / 64] |= 1L << constantIndex; |
| } |
| |
| |
| /** |
| * Returns whether the specified wildcard constant has been matched. |
| */ |
| private boolean isMatchingConstantIndex(int constantIndex) |
| { |
| return (matchedConstantFlags[constantIndex / 64] & (1L << constantIndex)) != 0; |
| } |
| |
| |
| private boolean matchingBranchOffsets(int offset, |
| int branchOffset1, |
| int branchOffset2) |
| { |
| int argumentIndex = branchOffset2 - X; |
| if (argumentIndex < 0) |
| { |
| // Check the literal argument. |
| return branchOffset1 == branchOffset2; |
| } |
| else if (!isMatchingArgumentIndex(argumentIndex)) |
| { |
| // Store a wildcard argument. |
| setMatchingArgument(argumentIndex, offset + branchOffset1); |
| |
| return true; |
| } |
| else |
| { |
| // Check the previously stored wildcard argument. |
| return matchedArguments[argumentIndex] == offset + branchOffset1; |
| } |
| } |
| |
| |
| private boolean matchingJumpOffsets(int offset, |
| int[] jumpOffsets1, |
| int[] jumpOffsets2) |
| { |
| if (jumpOffsets1.length != jumpOffsets2.length) |
| { |
| return false; |
| } |
| |
| for (int index = 0; index < jumpOffsets1.length; index++) |
| { |
| if (!matchingBranchOffsets(offset, |
| jumpOffsets1[index], |
| jumpOffsets2[index])) |
| { |
| return false; |
| } |
| } |
| |
| return true; |
| } |
| |
| |
| private void checkMatch(boolean condition, |
| Clazz clazz, |
| Method method, |
| CodeAttribute codeAttribute, |
| int offset, |
| Instruction instruction) |
| { |
| if (DEBUG_MORE) |
| { |
| System.out.println("InstructionSequenceMatcher: ["+clazz.getName()+"."+method.getName(clazz)+method.getDescriptor(clazz)+"]: "+patternInstructions[patternInstructionIndex].toString(patternInstructionIndex)+(condition?"\t== ":"\t ")+instruction.toString(offset)); |
| } |
| |
| // Did the instruction match? |
| if (condition) |
| { |
| // Remember the offset of the matching instruction. |
| matchedInstructionOffsets[patternInstructionIndex] = offset; |
| |
| // Try to match the next instruction next time. |
| patternInstructionIndex++; |
| |
| // Did we match all instructions in the sequence? |
| matching = patternInstructionIndex == patternInstructions.length; |
| |
| if (matching) |
| { |
| if (DEBUG) |
| { |
| System.out.println("InstructionSequenceMatcher: ["+clazz.getName()+"."+method.getName(clazz)+method.getDescriptor(clazz)+"]"); |
| for (int index = 0; index < patternInstructionIndex; index++) |
| { |
| System.out.println(" "+InstructionFactory.create(codeAttribute.code, matchedInstructionOffsets[index]).toString(matchedInstructionOffsets[index])); |
| } |
| } |
| |
| // Start matching from the first instruction again next time. |
| reset(); |
| } |
| } |
| else |
| { |
| // The instruction didn't match. |
| matching = false; |
| |
| // Is this a failed second instruction? |
| boolean retry = patternInstructionIndex == 1; |
| |
| // Start matching from the first instruction next time. |
| reset(); |
| |
| // Retry a failed second instruction as a first instruction. |
| if (retry) |
| { |
| instruction.accept(clazz, method, codeAttribute, offset, this); |
| } |
| } |
| } |
| } |
