KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > proguard > classfile > util > InstructionSequenceMatcher


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