1/* 2 * ProGuard -- shrinking, optimization, obfuscation, and preverification 3 * of Java bytecode. 4 * 5 * Copyright (c) 2002-2009 Eric Lafortune (eric@graphics.cornell.edu) 6 * 7 * This program is free software; you can redistribute it and/or modify it 8 * under the terms of the GNU General Public License as published by the Free 9 * Software Foundation; either version 2 of the License, or (at your option) 10 * any later version. 11 * 12 * This program is distributed in the hope that it will be useful, but WITHOUT 13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for 15 * more details. 16 * 17 * You should have received a copy of the GNU General Public License along 18 * with this program; if not, write to the Free Software Foundation, Inc., 19 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 20 */ 21package proguard.classfile.util; 22 23import proguard.classfile.*; 24import proguard.classfile.attribute.CodeAttribute; 25import proguard.classfile.constant.*; 26import proguard.classfile.constant.visitor.ConstantVisitor; 27import proguard.classfile.instruction.*; 28import proguard.classfile.instruction.visitor.InstructionVisitor; 29 30/** 31 * This InstructionVisitor checks whether a given pattern instruction sequence 32 * occurs in the instructions that are visited. The arguments of the 33 * instruction sequence can be wildcards that are matched. 34 * 35 * @author Eric Lafortune 36 */ 37public class InstructionSequenceMatcher 38extends SimplifiedVisitor 39implements InstructionVisitor, 40 ConstantVisitor 41{ 42 /* 43 private static boolean DEBUG = false; 44 public static boolean DEBUG_MORE = false; 45 /*/ 46 private static final boolean DEBUG = false; 47 private static final boolean DEBUG_MORE = false; 48 //*/ 49 50 public static final int X = 0x40000000; 51 public static final int Y = 0x40000001; 52 public static final int Z = 0x40000002; 53 54 public static final int A = 0x40000003; 55 public static final int B = 0x40000004; 56 public static final int C = 0x40000005; 57 public static final int D = 0x40000006; 58 59 60 private final Constant[] patternConstants; 61 private final Instruction[] patternInstructions; 62 63 private boolean matching; 64 private boolean matchingAnyWildCards; 65 private int patternInstructionIndex; 66 private final int[] matchedInstructionOffsets; 67 private int matchedArgumentFlags; 68 private final int[] matchedArguments = new int[7]; 69 private long matchedConstantFlags; 70 private final int[] matchedConstantIndices; 71 72 // Fields acting as a parameter and a return value for visitor methods. 73 private Constant patternConstant; 74 private boolean matchingConstant; 75 76 77 /** 78 * Creates a new InstructionSequenceMatcher. 79 * @param patternConstants any constants referenced by the pattern 80 * instruction. 81 * @param patternInstructions the pattern instruction sequence. 82 */ 83 public InstructionSequenceMatcher(Constant[] patternConstants, 84 Instruction[] patternInstructions) 85 { 86 this.patternConstants = patternConstants; 87 this.patternInstructions = patternInstructions; 88 89 matchedInstructionOffsets = new int[patternInstructions.length]; 90 matchedConstantIndices = new int[patternConstants.length]; 91 } 92 93 94 /** 95 * Starts matching from the first instruction again next time. 96 */ 97 public void reset() 98 { 99 patternInstructionIndex = 0; 100 matchedArgumentFlags = 0; 101 matchedConstantFlags = 0L; 102 } 103 104 105 public boolean isMatching() 106 { 107 return matching; 108 } 109 110 111 public boolean isMatchingAnyWildcards() 112 { 113 return matchingAnyWildCards; 114 } 115 116 117 public int instructionCount() 118 { 119 return patternInstructions.length; 120 } 121 122 123 public int matchedInstructionOffset(int index) 124 { 125 return matchedInstructionOffsets[index]; 126 } 127 128 129 public int matchedArgument(int argument) 130 { 131 int argumentIndex = argument - X; 132 return argumentIndex < 0 ? 133 argument : 134 matchedArguments[argumentIndex]; 135 } 136 137 138 public int[] matchedArguments(int[] arguments) 139 { 140 int[] matchedArguments = new int[arguments.length]; 141 142 for (int index = 0; index < arguments.length; index++) 143 { 144 matchedArguments[index] = matchedArgument(arguments[index]); 145 } 146 147 return matchedArguments; 148 } 149 150 151 public int matchedConstantIndex(int constantIndex) 152 { 153 int argumentIndex = constantIndex - X; 154 return argumentIndex < 0 ? 155 matchedConstantIndices[constantIndex] : 156 matchedArguments[argumentIndex]; 157 } 158 159 160 public int matchedBranchOffset(int offset, int branchOffset) 161 { 162 int argumentIndex = branchOffset - X; 163 return argumentIndex < 0 ? 164 branchOffset : 165 matchedArguments[argumentIndex] - offset; 166 } 167 168 169 public int[] matchedJumpOffsets(int offset, int[] jumpOffsets) 170 { 171 int[] matchedJumpOffsets = new int[jumpOffsets.length]; 172 173 for (int index = 0; index < jumpOffsets.length; index++) 174 { 175 matchedJumpOffsets[index] = matchedBranchOffset(offset, 176 jumpOffsets[index]); 177 } 178 179 return matchedJumpOffsets; 180 } 181 182 183 // Implementations for InstructionVisitor. 184 185 public void visitSimpleInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, SimpleInstruction simpleInstruction) 186 { 187 Instruction patternInstruction = patternInstructions[patternInstructionIndex]; 188 189 // Check if the instruction matches the next instruction in the sequence. 190 boolean condition = 191 matchingOpcodes(simpleInstruction, patternInstruction) && 192 matchingArguments(simpleInstruction.constant, 193 ((SimpleInstruction)patternInstruction).constant); 194 195 // Check if the instruction sequence is matching now. 196 checkMatch(condition, 197 clazz, 198 method, 199 codeAttribute, 200 offset, 201 simpleInstruction); 202 } 203 204 205 public void visitVariableInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, VariableInstruction variableInstruction) 206 { 207 Instruction patternInstruction = patternInstructions[patternInstructionIndex]; 208 209 // Check if the instruction matches the next instruction in the sequence. 210 boolean condition = 211 matchingOpcodes(variableInstruction, patternInstruction) && 212 matchingArguments(variableInstruction.variableIndex, 213 ((VariableInstruction)patternInstruction).variableIndex) && 214 matchingArguments(variableInstruction.constant, 215 ((VariableInstruction)patternInstruction).constant); 216 217 // Check if the instruction sequence is matching now. 218 checkMatch(condition, 219 clazz, 220 method, 221 codeAttribute, 222 offset, 223 variableInstruction); 224 } 225 226 227 public void visitConstantInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, ConstantInstruction constantInstruction) 228 { 229 Instruction patternInstruction = patternInstructions[patternInstructionIndex]; 230 231 // Check if the instruction matches the next instruction in the sequence. 232 boolean condition = 233 matchingOpcodes(constantInstruction, patternInstruction) && 234 matchingConstantIndices(clazz, 235 constantInstruction.constantIndex, 236 ((ConstantInstruction)patternInstruction).constantIndex) && 237 matchingArguments(constantInstruction.constant, 238 ((ConstantInstruction)patternInstruction).constant); 239 240 // Check if the instruction sequence is matching now. 241 checkMatch(condition, 242 clazz, 243 method, 244 codeAttribute, 245 offset, 246 constantInstruction); 247 } 248 249 250 public void visitBranchInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, BranchInstruction branchInstruction) 251 { 252 Instruction patternInstruction = patternInstructions[patternInstructionIndex]; 253 254 // Check if the instruction matches the next instruction in the from 255 // sequence. 256 boolean condition = 257 matchingOpcodes(branchInstruction, patternInstruction) && 258 matchingBranchOffsets(offset, 259 branchInstruction.branchOffset, 260 ((BranchInstruction)patternInstruction).branchOffset); 261 262 // Check if the instruction sequence is matching now. 263 checkMatch(condition, 264 clazz, 265 method, 266 codeAttribute, 267 offset, 268 branchInstruction); 269 } 270 271 272 public void visitTableSwitchInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, TableSwitchInstruction tableSwitchInstruction) 273 { 274 Instruction patternInstruction = patternInstructions[patternInstructionIndex]; 275 276 // Check if the instruction matches the next instruction in the sequence. 277 boolean condition = 278 matchingOpcodes(tableSwitchInstruction, patternInstruction) && 279 matchingBranchOffsets(offset, 280 tableSwitchInstruction.defaultOffset, 281 ((TableSwitchInstruction)patternInstruction).defaultOffset) && 282 matchingArguments(tableSwitchInstruction.lowCase, 283 ((TableSwitchInstruction)patternInstruction).lowCase) && 284 matchingArguments(tableSwitchInstruction.highCase, 285 ((TableSwitchInstruction)patternInstruction).highCase) && 286 matchingJumpOffsets(offset, 287 tableSwitchInstruction.jumpOffsets, 288 ((TableSwitchInstruction)patternInstruction).jumpOffsets); 289 290 // Check if the instruction sequence is matching now. 291 checkMatch(condition, 292 clazz, 293 method, 294 codeAttribute, 295 offset, 296 tableSwitchInstruction); 297 } 298 299 300 public void visitLookUpSwitchInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, LookUpSwitchInstruction lookUpSwitchInstruction) 301 { 302 Instruction patternInstruction = patternInstructions[patternInstructionIndex]; 303 304 // Check if the instruction matches the next instruction in the sequence. 305 boolean condition = 306 matchingOpcodes(lookUpSwitchInstruction, patternInstruction) && 307 matchingBranchOffsets(offset, 308 lookUpSwitchInstruction.defaultOffset, 309 ((LookUpSwitchInstruction)patternInstruction).defaultOffset) && 310 matchingArguments(lookUpSwitchInstruction.cases, 311 ((LookUpSwitchInstruction)patternInstruction).cases) && 312 matchingJumpOffsets(offset, 313 lookUpSwitchInstruction.jumpOffsets, 314 ((LookUpSwitchInstruction)patternInstruction).jumpOffsets); 315 316 // Check if the instruction sequence is matching now. 317 checkMatch(condition, 318 clazz, 319 method, 320 codeAttribute, 321 offset, 322 lookUpSwitchInstruction); 323 } 324 325 326 // Implementations for ConstantVisitor. 327 328 public void visitIntegerConstant(Clazz clazz, IntegerConstant integerConstant) 329 { 330 IntegerConstant integerPatternConstant = (IntegerConstant)patternConstant; 331 332 // Compare the integer values. 333 matchingConstant = integerConstant.getValue() == 334 integerPatternConstant.getValue(); 335 } 336 337 338 public void visitLongConstant(Clazz clazz, LongConstant longConstant) 339 { 340 LongConstant longPatternConstant = (LongConstant)patternConstant; 341 342 // Compare the long values. 343 matchingConstant = longConstant.getValue() == 344 longPatternConstant.getValue(); 345 } 346 347 348 public void visitFloatConstant(Clazz clazz, FloatConstant floatConstant) 349 { 350 FloatConstant floatPatternConstant = (FloatConstant)patternConstant; 351 352 // Compare the float values. 353 matchingConstant = floatConstant.getValue() == 354 floatPatternConstant.getValue(); 355 } 356 357 358 public void visitDoubleConstant(Clazz clazz, DoubleConstant doubleConstant) 359 { 360 DoubleConstant doublePatternConstant = (DoubleConstant)patternConstant; 361 362 // Compare the double values. 363 matchingConstant = doubleConstant.getValue() == 364 doublePatternConstant.getValue(); 365 } 366 367 368 public void visitStringConstant(Clazz clazz, StringConstant stringConstant) 369 { 370 StringConstant stringPatternConstant = (StringConstant)patternConstant; 371 372 // Check the UTF-8 constant. 373 matchingConstant = 374 matchingConstantIndices(clazz, 375 stringConstant.u2stringIndex, 376 stringPatternConstant.u2stringIndex); 377 } 378 379 380 public void visitUtf8Constant(Clazz clazz, Utf8Constant utf8Constant) 381 { 382 Utf8Constant utf8PatternConstant = (Utf8Constant)patternConstant; 383 384 // Compare the actual strings. 385 matchingConstant = utf8Constant.getString().equals( 386 utf8PatternConstant.getString()); 387 } 388 389 390 public void visitAnyRefConstant(Clazz clazz, RefConstant refConstant) 391 { 392 RefConstant refPatternConstant = (RefConstant)patternConstant; 393 394 // Check the class and the name and type. 395 matchingConstant = 396 matchingConstantIndices(clazz, 397 refConstant.getClassIndex(), 398 refPatternConstant.getClassIndex()) && 399 matchingConstantIndices(clazz, 400 refConstant.getNameAndTypeIndex(), 401 refPatternConstant.getNameAndTypeIndex()); 402 } 403 404 405 public void visitClassConstant(Clazz clazz, ClassConstant classConstant) 406 { 407 ClassConstant classPatternConstant = (ClassConstant)patternConstant; 408 409 // Check the class name. 410 matchingConstant = 411 matchingConstantIndices(clazz, 412 classConstant.u2nameIndex, 413 classPatternConstant.u2nameIndex); 414 } 415 416 417 public void visitNameAndTypeConstant(Clazz clazz, NameAndTypeConstant nameAndTypeConstant) 418 { 419 NameAndTypeConstant typePatternConstant = (NameAndTypeConstant)patternConstant; 420 421 // Check the name and the descriptor. 422 matchingConstant = 423 matchingConstantIndices(clazz, 424 nameAndTypeConstant.u2nameIndex, 425 typePatternConstant.u2nameIndex) && 426 matchingConstantIndices(clazz, 427 nameAndTypeConstant.u2descriptorIndex, 428 typePatternConstant.u2descriptorIndex); 429 } 430 431 432 // Small utility methods. 433 434 private boolean matchingOpcodes(Instruction instruction1, 435 Instruction instruction2) 436 { 437 // Check the opcode. 438 return instruction1.opcode == instruction2.opcode || 439 instruction1.canonicalOpcode() == instruction2.opcode; 440 } 441 442 443 private boolean matchingArguments(int argument1, 444 int argument2) 445 { 446 int argumentIndex = argument2 - X; 447 if (argumentIndex < 0) 448 { 449 // Check the literal argument. 450 return argument1 == argument2; 451 } 452 else if ((matchedArgumentFlags & (1 << argumentIndex)) == 0) 453 { 454 // Store a wildcard argument. 455 matchedArguments[argumentIndex] = argument1; 456 matchedArgumentFlags |= 1 << argumentIndex; 457 458 return true; 459 } 460 else 461 { 462 // Check the previously stored wildcard argument. 463 return matchedArguments[argumentIndex] == argument1; 464 } 465 } 466 467 468 private boolean matchingArguments(int[] arguments1, 469 int[] arguments2) 470 { 471 if (arguments1.length != arguments2.length) 472 { 473 return false; 474 } 475 476 for (int index = 0; index < arguments1.length; index++) 477 { 478 if (!matchingArguments(arguments1[index], arguments2[index])) 479 { 480 return false; 481 } 482 } 483 484 return true; 485 } 486 487 488 private boolean matchingConstantIndices(Clazz clazz, 489 int constantIndex1, 490 int constantIndex2) 491 { 492 if (constantIndex2 >= X) 493 { 494 // Check the constant index. 495 return matchingArguments(constantIndex1, constantIndex2); 496 } 497 else if ((matchedConstantFlags & (1L << constantIndex2)) == 0) 498 { 499 // Check the actual constant. 500 matchingConstant = false; 501 patternConstant = patternConstants[constantIndex2]; 502 503 if (clazz.getTag(constantIndex1) == patternConstant.getTag()) 504 { 505 clazz.constantPoolEntryAccept(constantIndex1, this); 506 507 if (matchingConstant) 508 { 509 // Store the constant index. 510 matchedConstantIndices[constantIndex2] = constantIndex1; 511 matchedConstantFlags |= 1L << constantIndex2; 512 } 513 } 514 515 return matchingConstant; 516 } 517 else 518 { 519 // Check a previously stored constant index. 520 return matchedConstantIndices[constantIndex2] == constantIndex1; 521 } 522 } 523 524 525 private boolean matchingBranchOffsets(int offset, 526 int branchOffset1, 527 int branchOffset2) 528 { 529 int argumentIndex = branchOffset2 - X; 530 if (argumentIndex < 0) 531 { 532 // Check the literal argument. 533 return branchOffset1 == branchOffset2; 534 } 535 else if ((matchedArgumentFlags & (1 << argumentIndex)) == 0) 536 { 537 // Store a wildcard argument. 538 matchedArguments[argumentIndex] = offset + branchOffset1; 539 matchedArgumentFlags |= 1 << argumentIndex; 540 541 return true; 542 } 543 else 544 { 545 // Check the previously stored wildcard argument. 546 return matchedArguments[argumentIndex] == offset + branchOffset1; 547 } 548 } 549 550 551 private boolean matchingJumpOffsets(int offset, 552 int[] jumpOffsets1, 553 int[] jumpOffsets2) 554 { 555 if (jumpOffsets1.length != jumpOffsets2.length) 556 { 557 return false; 558 } 559 560 for (int index = 0; index < jumpOffsets1.length; index++) 561 { 562 if (!matchingBranchOffsets(offset, 563 jumpOffsets1[index], 564 jumpOffsets2[index])) 565 { 566 return false; 567 } 568 } 569 570 return true; 571 } 572 573 574 private void checkMatch(boolean condition, 575 Clazz clazz, 576 Method method, 577 CodeAttribute codeAttribute, 578 int offset, 579 Instruction instruction) 580 { 581 if (DEBUG_MORE) 582 { 583 System.out.println("InstructionSequenceMatcher: ["+clazz.getName()+"."+method.getName(clazz)+method.getDescriptor(clazz)+"]: "+patternInstructions[patternInstructionIndex].toString(patternInstructionIndex)+(condition?"\t== ":"\t ")+instruction.toString(offset)); 584 } 585 586 // Did the instruction match? 587 if (condition) 588 { 589 // Remember the offset of the matching instruction. 590 matchedInstructionOffsets[patternInstructionIndex] = offset; 591 592 // Try to match the next instruction next time. 593 patternInstructionIndex++; 594 595 // Did we match all instructions in the sequence? 596 matching = patternInstructionIndex == patternInstructions.length; 597 598 // Did we match any wildcards along the way? 599 matchingAnyWildCards = matchedArgumentFlags != 0; 600 601 if (matching) 602 { 603 if (DEBUG) 604 { 605 System.out.println("InstructionSequenceMatcher: ["+clazz.getName()+"."+method.getName(clazz)+method.getDescriptor(clazz)+"]"); 606 for (int index = 0; index < patternInstructionIndex; index++) 607 { 608 System.out.println(" "+InstructionFactory.create(codeAttribute.code, matchedInstructionOffsets[index]).toString(matchedInstructionOffsets[index])); 609 } 610 } 611 612 // Start matching from the first instruction again next time. 613 reset(); 614 } 615 } 616 else 617 { 618 // The instruction didn't match. 619 matching = false; 620 621 // Is this a failed second instruction? 622 boolean retry = patternInstructionIndex == 1; 623 624 // Start matching from the first instruction next time. 625 reset(); 626 627 // Retry a failed second instruction as a first instruction. 628 if (retry) 629 { 630 instruction.accept(clazz, method, codeAttribute, offset, this); 631 } 632 } 633 } 634} 635