001: /*
002: * ProGuard -- shrinking, optimization, obfuscation, and preverification
003: * of Java bytecode.
004: *
005: * Copyright (c) 2002-2007 Eric Lafortune (eric@graphics.cornell.edu)
006: *
007: * This program is free software; you can redistribute it and/or modify it
008: * under the terms of the GNU General Public License as published by the Free
009: * Software Foundation; either version 2 of the License, or (at your option)
010: * any later version.
011: *
012: * This program is distributed in the hope that it will be useful, but WITHOUT
013: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
014: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
015: * more details.
016: *
017: * You should have received a copy of the GNU General Public License along
018: * with this program; if not, write to the Free Software Foundation, Inc.,
019: * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
020: */
021: package proguard.classfile.util;
022:
023: import proguard.classfile.*;
024: import proguard.classfile.attribute.CodeAttribute;
025: import proguard.classfile.constant.*;
026: import proguard.classfile.constant.visitor.ConstantVisitor;
027: import proguard.classfile.instruction.*;
028: import proguard.classfile.instruction.visitor.InstructionVisitor;
029:
030: /**
031: * This InstructionVisitor checks whether a given pattern instruction sequence
032: * occurs in the instructions that are visited. The arguments of the
033: * instruction sequence can be wildcards that are matched.
034: *
035: * @author Eric Lafortune
036: */
037: public class InstructionSequenceMatcher extends SimplifiedVisitor
038: implements InstructionVisitor, ConstantVisitor {
039: /*
040: private static boolean DEBUG = false;
041: public static boolean DEBUG_MORE = false;
042: /*/
043: private static final boolean DEBUG = false;
044: private static final boolean DEBUG_MORE = false;
045: //*/
046:
047: public static final int X = 0x40000000;
048: public static final int Y = 0x40000001;
049: public static final int Z = 0x40000002;
050:
051: public static final int A = 0x40000003;
052: public static final int B = 0x40000004;
053: public static final int C = 0x40000005;
054: public static final int D = 0x40000006;
055:
056: private final Constant[] patternConstants;
057: private final Instruction[] patternInstructions;
058:
059: private boolean matching;
060: private int patternInstructionIndex;
061: private final int[] matchedInstructionOffsets;
062: private int matchedArgumentFlags;
063: private final int[] matchedArguments = new int[7];
064: private int matchedConstantFlags;
065: private final int[] matchedConstantIndices;
066:
067: // Fields acting as a parameter and a return value for visitor methods.
068: private Constant patternConstant;
069: private boolean matchingConstant;
070:
071: /**
072: * Creates a new InstructionSequenceMatcher.
073: * @param patternConstants any constants referenced by the pattern
074: * instruction.
075: * @param patternInstructions the pattern instruction sequence.
076: */
077: public InstructionSequenceMatcher(Constant[] patternConstants,
078: Instruction[] patternInstructions) {
079: this .patternConstants = patternConstants;
080: this .patternInstructions = patternInstructions;
081:
082: matchedInstructionOffsets = new int[patternInstructions.length];
083: matchedConstantIndices = new int[patternConstants.length];
084: }
085:
086: /**
087: * Starts matching from the first instruction again next time.
088: */
089: public void reset() {
090: patternInstructionIndex = 0;
091: matchedArgumentFlags = 0;
092: matchedConstantFlags = 0;
093: }
094:
095: public boolean isMatching() {
096: return matching;
097: }
098:
099: public int instructionCount() {
100: return patternInstructions.length;
101: }
102:
103: public int matchedInstructionOffset(int index) {
104: return matchedInstructionOffsets[index];
105: }
106:
107: public int matchedArgument(int argument) {
108: int argumentIndex = argument - X;
109: return argumentIndex < 0 ? argument
110: : matchedArguments[argumentIndex];
111: }
112:
113: public int[] matchedArguments(int[] arguments) {
114: int[] matchedArguments = new int[arguments.length];
115:
116: for (int index = 0; index < arguments.length; index++) {
117: matchedArguments[index] = matchedArgument(arguments[index]);
118: }
119:
120: return matchedArguments;
121: }
122:
123: public int matchedConstantIndex(int constantIndex) {
124: int argumentIndex = constantIndex - X;
125: return argumentIndex < 0 ? matchedConstantIndices[constantIndex]
126: : matchedArguments[argumentIndex];
127: }
128:
129: public int matchedBranchOffset(int offset, int branchOffset) {
130: int argumentIndex = branchOffset - X;
131: return argumentIndex < 0 ? branchOffset
132: : matchedArguments[argumentIndex] - offset;
133: }
134:
135: public int[] matchedJumpOffsets(int offset, int[] jumpOffsets) {
136: int[] matchedJumpOffsets = new int[jumpOffsets.length];
137:
138: for (int index = 0; index < jumpOffsets.length; index++) {
139: matchedJumpOffsets[index] = matchedBranchOffset(offset,
140: jumpOffsets[index]);
141: }
142:
143: return matchedJumpOffsets;
144: }
145:
146: // Implementations for InstructionVisitor.
147:
148: public void visitSimpleInstruction(Clazz clazz, Method method,
149: CodeAttribute codeAttribute, int offset,
150: SimpleInstruction simpleInstruction) {
151: Instruction patternInstruction = patternInstructions[patternInstructionIndex];
152:
153: // Check if the instruction matches the next instruction in the sequence.
154: boolean condition = matchingOpcodes(simpleInstruction,
155: patternInstruction)
156: && matchingArguments(
157: simpleInstruction.constant,
158: ((SimpleInstruction) patternInstruction).constant);
159:
160: // Check if the instruction sequence is matching now.
161: checkMatch(condition, clazz, method, codeAttribute, offset,
162: simpleInstruction);
163: }
164:
165: public void visitVariableInstruction(Clazz clazz, Method method,
166: CodeAttribute codeAttribute, int offset,
167: VariableInstruction variableInstruction) {
168: Instruction patternInstruction = patternInstructions[patternInstructionIndex];
169:
170: // Check if the instruction matches the next instruction in the sequence.
171: boolean condition = matchingOpcodes(variableInstruction,
172: patternInstruction)
173: && matchingArguments(
174: variableInstruction.variableIndex,
175: ((VariableInstruction) patternInstruction).variableIndex)
176: && matchingArguments(
177: variableInstruction.constant,
178: ((VariableInstruction) patternInstruction).constant);
179:
180: // Check if the instruction sequence is matching now.
181: checkMatch(condition, clazz, method, codeAttribute, offset,
182: variableInstruction);
183: }
184:
185: public void visitConstantInstruction(Clazz clazz, Method method,
186: CodeAttribute codeAttribute, int offset,
187: ConstantInstruction constantInstruction) {
188: Instruction patternInstruction = patternInstructions[patternInstructionIndex];
189:
190: // Check if the instruction matches the next instruction in the sequence.
191: boolean condition = matchingOpcodes(constantInstruction,
192: patternInstruction)
193: && matchingConstantIndices(
194: clazz,
195: constantInstruction.constantIndex,
196: ((ConstantInstruction) patternInstruction).constantIndex)
197: && matchingArguments(
198: constantInstruction.constant,
199: ((ConstantInstruction) patternInstruction).constant);
200:
201: // Check if the instruction sequence is matching now.
202: checkMatch(condition, clazz, method, codeAttribute, offset,
203: constantInstruction);
204: }
205:
206: public void visitBranchInstruction(Clazz clazz, Method method,
207: CodeAttribute codeAttribute, int offset,
208: BranchInstruction branchInstruction) {
209: Instruction patternInstruction = patternInstructions[patternInstructionIndex];
210:
211: // Check if the instruction matches the next instruction in the from
212: // sequence.
213: boolean condition = matchingOpcodes(branchInstruction,
214: patternInstruction)
215: && matchingBranchOffsets(
216: offset,
217: branchInstruction.branchOffset,
218: ((BranchInstruction) patternInstruction).branchOffset);
219:
220: // Check if the instruction sequence is matching now.
221: checkMatch(condition, clazz, method, codeAttribute, offset,
222: branchInstruction);
223: }
224:
225: public void visitTableSwitchInstruction(Clazz clazz, Method method,
226: CodeAttribute codeAttribute, int offset,
227: TableSwitchInstruction tableSwitchInstruction) {
228: Instruction patternInstruction = patternInstructions[patternInstructionIndex];
229:
230: // Check if the instruction matches the next instruction in the sequence.
231: boolean condition = matchingOpcodes(tableSwitchInstruction,
232: patternInstruction)
233: && matchingBranchOffsets(
234: offset,
235: tableSwitchInstruction.defaultOffset,
236: ((TableSwitchInstruction) patternInstruction).defaultOffset)
237: && matchingArguments(
238: tableSwitchInstruction.lowCase,
239: ((TableSwitchInstruction) patternInstruction).lowCase)
240: && matchingArguments(
241: tableSwitchInstruction.highCase,
242: ((TableSwitchInstruction) patternInstruction).highCase)
243: && matchingJumpOffsets(
244: offset,
245: tableSwitchInstruction.jumpOffsets,
246: ((TableSwitchInstruction) patternInstruction).jumpOffsets);
247:
248: // Check if the instruction sequence is matching now.
249: checkMatch(condition, clazz, method, codeAttribute, offset,
250: tableSwitchInstruction);
251: }
252:
253: public void visitLookUpSwitchInstruction(Clazz clazz,
254: Method method, CodeAttribute codeAttribute, int offset,
255: LookUpSwitchInstruction lookUpSwitchInstruction) {
256: Instruction patternInstruction = patternInstructions[patternInstructionIndex];
257:
258: // Check if the instruction matches the next instruction in the sequence.
259: boolean condition = matchingOpcodes(lookUpSwitchInstruction,
260: patternInstruction)
261: && matchingBranchOffsets(
262: offset,
263: lookUpSwitchInstruction.defaultOffset,
264: ((LookUpSwitchInstruction) patternInstruction).defaultOffset)
265: && matchingArguments(
266: lookUpSwitchInstruction.cases,
267: ((LookUpSwitchInstruction) patternInstruction).cases)
268: && matchingJumpOffsets(
269: offset,
270: lookUpSwitchInstruction.jumpOffsets,
271: ((LookUpSwitchInstruction) patternInstruction).jumpOffsets);
272:
273: // Check if the instruction sequence is matching now.
274: checkMatch(condition, clazz, method, codeAttribute, offset,
275: lookUpSwitchInstruction);
276: }
277:
278: // Implementations for ConstantVisitor.
279:
280: public void visitIntegerConstant(Clazz clazz,
281: IntegerConstant integerConstant) {
282: IntegerConstant integerPatternConstant = (IntegerConstant) patternConstant;
283:
284: // Compare the integer values.
285: matchingConstant = integerConstant.getValue() == integerPatternConstant
286: .getValue();
287: }
288:
289: public void visitLongConstant(Clazz clazz, LongConstant longConstant) {
290: LongConstant longPatternConstant = (LongConstant) patternConstant;
291:
292: // Compare the long values.
293: matchingConstant = longConstant.getValue() == longPatternConstant
294: .getValue();
295: }
296:
297: public void visitFloatConstant(Clazz clazz,
298: FloatConstant floatConstant) {
299: FloatConstant floatPatternConstant = (FloatConstant) patternConstant;
300:
301: // Compare the float values.
302: matchingConstant = floatConstant.getValue() == floatPatternConstant
303: .getValue();
304: }
305:
306: public void visitDoubleConstant(Clazz clazz,
307: DoubleConstant doubleConstant) {
308: DoubleConstant doublePatternConstant = (DoubleConstant) patternConstant;
309:
310: // Compare the double values.
311: matchingConstant = doubleConstant.getValue() == doublePatternConstant
312: .getValue();
313: }
314:
315: public void visitStringConstant(Clazz clazz,
316: StringConstant stringConstant) {
317: StringConstant stringPatternConstant = (StringConstant) patternConstant;
318:
319: // Check the UTF-8 constant.
320: matchingConstant = matchingConstantIndices(clazz,
321: stringConstant.u2stringIndex,
322: stringPatternConstant.u2stringIndex);
323: }
324:
325: public void visitUtf8Constant(Clazz clazz, Utf8Constant utf8Constant) {
326: Utf8Constant utf8PatternConstant = (Utf8Constant) patternConstant;
327:
328: // Compare the actual strings.
329: matchingConstant = utf8Constant.getString().equals(
330: utf8PatternConstant.getString());
331: }
332:
333: public void visitAnyRefConstant(Clazz clazz, RefConstant refConstant) {
334: RefConstant refPatternConstant = (RefConstant) patternConstant;
335:
336: // Check the class and the name and type.
337: matchingConstant = matchingConstantIndices(clazz, refConstant
338: .getClassIndex(), refPatternConstant.getClassIndex())
339: && matchingConstantIndices(clazz, refConstant
340: .getNameAndTypeIndex(), refPatternConstant
341: .getNameAndTypeIndex());
342: }
343:
344: public void visitClassConstant(Clazz clazz,
345: ClassConstant classConstant) {
346: ClassConstant classPatternConstant = (ClassConstant) patternConstant;
347:
348: // Check the class name.
349: matchingConstant = matchingConstantIndices(clazz,
350: classConstant.u2nameIndex,
351: classPatternConstant.u2nameIndex);
352: }
353:
354: public void visitNameAndTypeConstant(Clazz clazz,
355: NameAndTypeConstant nameAndTypeConstant) {
356: NameAndTypeConstant typePatternConstant = (NameAndTypeConstant) patternConstant;
357:
358: // Check the name and the descriptor.
359: matchingConstant = matchingConstantIndices(clazz,
360: nameAndTypeConstant.u2nameIndex,
361: typePatternConstant.u2nameIndex)
362: && matchingConstantIndices(clazz,
363: nameAndTypeConstant.u2descriptorIndex,
364: typePatternConstant.u2descriptorIndex);
365: }
366:
367: // Small utility methods.
368:
369: private boolean matchingOpcodes(Instruction instruction1,
370: Instruction instruction2) {
371: // Check the opcode.
372: return instruction1.opcode == instruction2.opcode
373: || instruction1.canonicalOpcode() == instruction2.opcode;
374: }
375:
376: private boolean matchingArguments(int argument1, int argument2) {
377: int argumentIndex = argument2 - X;
378: if (argumentIndex < 0) {
379: // Check the literal argument.
380: return argument1 == argument2;
381: } else if ((matchedArgumentFlags & (1 << argumentIndex)) == 0) {
382: // Store a wildcard argument.
383: matchedArguments[argumentIndex] = argument1;
384: matchedArgumentFlags |= 1 << argumentIndex;
385:
386: return true;
387: } else {
388: // Check the previously stored wildcard argument.
389: return matchedArguments[argumentIndex] == argument1;
390: }
391: }
392:
393: private boolean matchingArguments(int[] arguments1, int[] arguments2) {
394: if (arguments1.length != arguments2.length) {
395: return false;
396: }
397:
398: for (int index = 0; index < arguments1.length; index++) {
399: if (!matchingArguments(arguments1[index], arguments2[index])) {
400: return false;
401: }
402: }
403:
404: return true;
405: }
406:
407: private boolean matchingConstantIndices(Clazz clazz,
408: int constantIndex1, int constantIndex2) {
409: if (constantIndex2 >= X) {
410: // Check the constant index.
411: return matchingArguments(constantIndex1, constantIndex2);
412: } else if ((matchedConstantFlags & (1 << constantIndex2)) == 0) {
413: // Check the actual constant.
414: matchingConstant = false;
415: patternConstant = patternConstants[constantIndex2];
416:
417: if (clazz.getTag(constantIndex1) == patternConstant
418: .getTag()) {
419: clazz.constantPoolEntryAccept(constantIndex1, this );
420:
421: if (matchingConstant) {
422: // Store the constant index.
423: matchedConstantIndices[constantIndex2] = constantIndex1;
424: matchedConstantFlags |= 1 << constantIndex2;
425: }
426: }
427:
428: return matchingConstant;
429: } else {
430: // Check a previously stored constant index.
431: return matchedConstantIndices[constantIndex2] == constantIndex1;
432: }
433: }
434:
435: private boolean matchingBranchOffsets(int offset,
436: int branchOffset1, int branchOffset2) {
437: int argumentIndex = branchOffset2 - X;
438: if (argumentIndex < 0) {
439: // Check the literal argument.
440: return branchOffset1 == branchOffset2;
441: } else if ((matchedArgumentFlags & (1 << argumentIndex)) == 0) {
442: // Store a wildcard argument.
443: matchedArguments[argumentIndex] = offset + branchOffset1;
444: matchedArgumentFlags |= 1 << argumentIndex;
445:
446: return true;
447: } else {
448: // Check the previously stored wildcard argument.
449: return matchedArguments[argumentIndex] == offset
450: + branchOffset1;
451: }
452: }
453:
454: private boolean matchingJumpOffsets(int offset, int[] jumpOffsets1,
455: int[] jumpOffsets2) {
456: if (jumpOffsets1.length != jumpOffsets2.length) {
457: return false;
458: }
459:
460: for (int index = 0; index < jumpOffsets1.length; index++) {
461: if (!matchingBranchOffsets(offset, jumpOffsets1[index],
462: jumpOffsets2[index])) {
463: return false;
464: }
465: }
466:
467: return true;
468: }
469:
470: private void checkMatch(boolean condition, Clazz clazz,
471: Method method, CodeAttribute codeAttribute, int offset,
472: Instruction instruction) {
473: if (DEBUG_MORE) {
474: System.out.println("InstructionSequenceMatcher: ["
475: + clazz.getName()
476: + "."
477: + method.getName(clazz)
478: + method.getDescriptor(clazz)
479: + "]: "
480: + patternInstructions[patternInstructionIndex]
481: .toString(patternInstructionIndex)
482: + (condition ? "\t== " : "\t ")
483: + instruction.toString(offset));
484: }
485:
486: // Did the instruction match?
487: if (condition) {
488: // Remember the offset of the matching instruction.
489: matchedInstructionOffsets[patternInstructionIndex] = offset;
490:
491: // Try to match the next instruction next time.
492: patternInstructionIndex++;
493:
494: // Did we match all instructions in the sequence?
495: matching = patternInstructionIndex == patternInstructions.length;
496:
497: if (matching) {
498: if (DEBUG) {
499: System.out.println("InstructionSequenceMatcher: ["
500: + clazz.getName() + "."
501: + method.getName(clazz)
502: + method.getDescriptor(clazz) + "]");
503: for (int index = 0; index < patternInstructionIndex; index++) {
504: System.out
505: .println(" "
506: + InstructionFactory
507: .create(
508: codeAttribute.code,
509: matchedInstructionOffsets[index])
510: .toString(
511: matchedInstructionOffsets[index]));
512: }
513: }
514:
515: // Start matching from the first instruction again next time.
516: reset();
517: }
518: } else {
519: // The instruction didn't match.
520: matching = false;
521:
522: // Is this a failed second instruction?
523: boolean retry = patternInstructionIndex == 1;
524:
525: // Start matching from the first instruction next time.
526: reset();
527:
528: // Retry a failed second instruction as a first instruction.
529: if (retry) {
530: instruction.accept(clazz, method, codeAttribute,
531: offset, this);
532: }
533: }
534: }
535: }
|