diff options
Diffstat (limited to 'dx/src/com/android/dx/cf/code/Simulator.java')
| -rw-r--r-- | dx/src/com/android/dx/cf/code/Simulator.java | 772 |
1 files changed, 772 insertions, 0 deletions
diff --git a/dx/src/com/android/dx/cf/code/Simulator.java b/dx/src/com/android/dx/cf/code/Simulator.java new file mode 100644 index 0000000..c097831 --- /dev/null +++ b/dx/src/com/android/dx/cf/code/Simulator.java @@ -0,0 +1,772 @@ +/* + * Copyright (C) 2007 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.dx.cf.code; + +import com.android.dx.rop.cst.Constant; +import com.android.dx.rop.cst.CstFieldRef; +import com.android.dx.rop.cst.CstInteger; +import com.android.dx.rop.cst.CstInterfaceMethodRef; +import com.android.dx.rop.cst.CstMethodRef; +import com.android.dx.rop.cst.CstType; +import com.android.dx.rop.type.Prototype; +import com.android.dx.rop.type.Type; +import com.android.dx.rop.code.LocalItem; +import com.android.dx.util.Hex; + +import java.util.ArrayList; + +/** + * Class which knows how to simulate the effects of executing bytecode. + * + * <p><b>Note:</b> This class is not thread-safe. If multiple threads + * need to use a single instance, they must synchronize access explicitly + * between themselves.</p> + */ +public class Simulator { + /** + * {@code non-null;} canned error message for local variable + * table mismatches + */ + private static final String LOCAL_MISMATCH_ERROR = + "This is symptomatic of .class transformation tools that ignore " + + "local variable information."; + + /** {@code non-null;} machine to use when simulating */ + private final Machine machine; + + /** {@code non-null;} array of bytecode */ + private final BytecodeArray code; + + /** {@code non-null;} local variable information */ + private final LocalVariableList localVariables; + + /** {@code non-null;} visitor instance to use */ + private final SimVisitor visitor; + + /** + * Constructs an instance. + * + * @param machine {@code non-null;} machine to use when simulating + * @param method {@code non-null;} method data to use + */ + public Simulator(Machine machine, ConcreteMethod method) { + if (machine == null) { + throw new NullPointerException("machine == null"); + } + + if (method == null) { + throw new NullPointerException("method == null"); + } + + this.machine = machine; + this.code = method.getCode(); + this.localVariables = method.getLocalVariables(); + this.visitor = new SimVisitor(); + } + + /** + * Simulates the effect of executing the given basic block. This modifies + * the passed-in frame to represent the end result. + * + * @param bb {@code non-null;} the basic block + * @param frame {@code non-null;} frame to operate on + */ + public void simulate(ByteBlock bb, Frame frame) { + int end = bb.getEnd(); + + visitor.setFrame(frame); + + try { + for (int off = bb.getStart(); off < end; /*off*/) { + int length = code.parseInstruction(off, visitor); + visitor.setPreviousOffset(off); + off += length; + } + } catch (SimException ex) { + frame.annotate(ex); + throw ex; + } + } + + /** + * Simulates the effect of the instruction at the given offset, by + * making appropriate calls on the given frame. + * + * @param offset {@code >= 0;} offset of the instruction to simulate + * @param frame {@code non-null;} frame to operate on + * @return the length of the instruction, in bytes + */ + public int simulate(int offset, Frame frame) { + visitor.setFrame(frame); + return code.parseInstruction(offset, visitor); + } + + /** + * Constructs an "illegal top-of-stack" exception, for the stack + * manipulation opcodes. + */ + private static SimException illegalTos() { + return new SimException("stack mismatch: illegal " + + "top-of-stack for opcode"); + } + + /** + * Returns the required array type for an array load or store + * instruction, based on a given implied type and an observed + * actual array type. + * + * <p>The interesting cases here have to do with object arrays, + * <code>byte[]</code>s, <code>boolean[]</code>s, and + * known-nulls.</p> + * + * <p>In the case of arrays of objects, we want to narrow the type + * to the actual array present on the stack, as long as what is + * present is an object type. Similarly, due to a quirk of the + * original bytecode representation, the instructions for dealing + * with <code>byte[]</code> and <code>boolean[]</code> are + * undifferentiated, and we aim here to return whichever one was + * actually present on the stack.</p> + * + * <p>In the case where there is a known-null on the stack where + * an array is expected, we just fall back to the implied type of + * the instruction. Due to the quirk described above, this means + * that source code that uses <code>boolean[]</code> might get + * translated surprisingly -- but correctly -- into an instruction + * that specifies a <code>byte[]</code>. It will be correct, + * because should the code actually execute, it will necessarily + * throw a <code>NullPointerException</code>, and it won't matter + * what opcode variant is used to achieve that result.</p> + * + * @param impliedType {@code non-null;} type implied by the + * instruction; is <i>not</i> an array type + * @param foundArrayType {@code non-null;} type found on the + * stack; is either an array type or a known-null + * @return {@code non-null;} the array type that should be + * required in this context + */ + private static Type requiredArrayTypeFor(Type impliedType, + Type foundArrayType) { + if (foundArrayType == Type.KNOWN_NULL) { + return impliedType.getArrayType(); + } + + if ((impliedType == Type.OBJECT) + && foundArrayType.isArray() + && foundArrayType.getComponentType().isReference()) { + return foundArrayType; + } + + if ((impliedType == Type.BYTE) + && (foundArrayType == Type.BOOLEAN_ARRAY)) { + /* + * Per above, an instruction with implied byte[] is also + * allowed to be used on boolean[]. + */ + return Type.BOOLEAN_ARRAY; + } + + return impliedType.getArrayType(); + } + + /** + * Bytecode visitor used during simulation. + */ + private class SimVisitor implements BytecodeArray.Visitor { + /** + * {@code non-null;} machine instance to use (just to avoid excessive + * cross-object field access) + */ + private final Machine machine; + + /** + * {@code null-ok;} frame to use; set with each call to + * {@link Simulator#simulate} + */ + private Frame frame; + + /** offset of the previous bytecode */ + private int previousOffset; + + /** + * Constructs an instance. + */ + public SimVisitor() { + this.machine = Simulator.this.machine; + this.frame = null; + } + + /** + * Sets the frame to act on. + * + * @param frame {@code non-null;} the frame + */ + public void setFrame(Frame frame) { + if (frame == null) { + throw new NullPointerException("frame == null"); + } + + this.frame = frame; + } + + /** {@inheritDoc} */ + public void visitInvalid(int opcode, int offset, int length) { + throw new SimException("invalid opcode " + Hex.u1(opcode)); + } + + /** {@inheritDoc} */ + public void visitNoArgs(int opcode, int offset, int length, + Type type) { + switch (opcode) { + case ByteOps.NOP: { + machine.clearArgs(); + break; + } + case ByteOps.INEG: { + machine.popArgs(frame, type); + break; + } + case ByteOps.I2L: + case ByteOps.I2F: + case ByteOps.I2D: + case ByteOps.I2B: + case ByteOps.I2C: + case ByteOps.I2S: { + machine.popArgs(frame, Type.INT); + break; + } + case ByteOps.L2I: + case ByteOps.L2F: + case ByteOps.L2D: { + machine.popArgs(frame, Type.LONG); + break; + } + case ByteOps.F2I: + case ByteOps.F2L: + case ByteOps.F2D: { + machine.popArgs(frame, Type.FLOAT); + break; + } + case ByteOps.D2I: + case ByteOps.D2L: + case ByteOps.D2F: { + machine.popArgs(frame, Type.DOUBLE); + break; + } + case ByteOps.RETURN: { + machine.clearArgs(); + checkReturnType(Type.VOID); + break; + } + case ByteOps.IRETURN: { + Type checkType = type; + if (type == Type.OBJECT) { + /* + * For an object return, use the best-known + * type of the popped value. + */ + checkType = frame.getStack().peekType(0); + } + machine.popArgs(frame, type); + checkReturnType(checkType); + break; + } + case ByteOps.POP: { + Type peekType = frame.getStack().peekType(0); + if (peekType.isCategory2()) { + throw illegalTos(); + } + machine.popArgs(frame, 1); + break; + } + case ByteOps.ARRAYLENGTH: { + Type arrayType = frame.getStack().peekType(0); + if (!arrayType.isArrayOrKnownNull()) { + throw new SimException("type mismatch: expected " + + "array type but encountered " + + arrayType.toHuman()); + } + machine.popArgs(frame, Type.OBJECT); + break; + } + case ByteOps.ATHROW: + case ByteOps.MONITORENTER: + case ByteOps.MONITOREXIT: { + machine.popArgs(frame, Type.OBJECT); + break; + } + case ByteOps.IALOAD: { + /* + * See comment on requiredArrayTypeFor() for explanation + * about what's going on here. + */ + Type foundArrayType = frame.getStack().peekType(1); + Type requiredArrayType = + requiredArrayTypeFor(type, foundArrayType); + + // Make type agree with the discovered requiredArrayType. + type = requiredArrayType.getComponentType(); + + machine.popArgs(frame, requiredArrayType, Type.INT); + break; + } + case ByteOps.IADD: + case ByteOps.ISUB: + case ByteOps.IMUL: + case ByteOps.IDIV: + case ByteOps.IREM: + case ByteOps.IAND: + case ByteOps.IOR: + case ByteOps.IXOR: { + machine.popArgs(frame, type, type); + break; + } + case ByteOps.ISHL: + case ByteOps.ISHR: + case ByteOps.IUSHR: { + machine.popArgs(frame, type, Type.INT); + break; + } + case ByteOps.LCMP: { + machine.popArgs(frame, Type.LONG, Type.LONG); + break; + } + case ByteOps.FCMPL: + case ByteOps.FCMPG: { + machine.popArgs(frame, Type.FLOAT, Type.FLOAT); + break; + } + case ByteOps.DCMPL: + case ByteOps.DCMPG: { + machine.popArgs(frame, Type.DOUBLE, Type.DOUBLE); + break; + } + case ByteOps.IASTORE: { + /* + * See comment on requiredArrayTypeFor() for + * explanation about what's going on here. In + * addition to that, the category 1 vs. 2 thing + * below is to deal with the fact that, if the + * element type is category 2, we have to skip + * over one extra stack slot to find the array. + */ + ExecutionStack stack = frame.getStack(); + int peekDepth = type.isCategory1() ? 2 : 3; + Type foundArrayType = stack.peekType(peekDepth); + boolean foundArrayLocal = stack.peekLocal(peekDepth); + + Type requiredArrayType = + requiredArrayTypeFor(type, foundArrayType); + + /* + * Make type agree with the discovered requiredArrayType + * if it has local info. + */ + if (foundArrayLocal) { + type = requiredArrayType.getComponentType(); + } + + machine.popArgs(frame, requiredArrayType, Type.INT, type); + break; + } + case ByteOps.POP2: + case ByteOps.DUP2: { + ExecutionStack stack = frame.getStack(); + int pattern; + + if (stack.peekType(0).isCategory2()) { + // "form 2" in vmspec-2 + machine.popArgs(frame, 1); + pattern = 0x11; + } else if (stack.peekType(1).isCategory1()) { + // "form 1" + machine.popArgs(frame, 2); + pattern = 0x2121; + } else { + throw illegalTos(); + } + + if (opcode == ByteOps.DUP2) { + machine.auxIntArg(pattern); + } + break; + } + case ByteOps.DUP: { + Type peekType = frame.getStack().peekType(0); + + if (peekType.isCategory2()) { + throw illegalTos(); + } + + machine.popArgs(frame, 1); + machine.auxIntArg(0x11); + break; + } + case ByteOps.DUP_X1: { + ExecutionStack stack = frame.getStack(); + + if (!(stack.peekType(0).isCategory1() && + stack.peekType(1).isCategory1())) { + throw illegalTos(); + } + + machine.popArgs(frame, 2); + machine.auxIntArg(0x212); + break; + } + case ByteOps.DUP_X2: { + ExecutionStack stack = frame.getStack(); + + if (stack.peekType(0).isCategory2()) { + throw illegalTos(); + } + + if (stack.peekType(1).isCategory2()) { + // "form 2" in vmspec-2 + machine.popArgs(frame, 2); + machine.auxIntArg(0x212); + } else if (stack.peekType(2).isCategory1()) { + // "form 1" + machine.popArgs(frame, 3); + machine.auxIntArg(0x3213); + } else { + throw illegalTos(); + } + break; + } + case ByteOps.DUP2_X1: { + ExecutionStack stack = frame.getStack(); + + if (stack.peekType(0).isCategory2()) { + // "form 2" in vmspec-2 + if (stack.peekType(2).isCategory2()) { + throw illegalTos(); + } + machine.popArgs(frame, 2); + machine.auxIntArg(0x212); + } else { + // "form 1" + if (stack.peekType(1).isCategory2() || + stack.peekType(2).isCategory2()) { + throw illegalTos(); + } + machine.popArgs(frame, 3); + machine.auxIntArg(0x32132); + } + break; + } + case ByteOps.DUP2_X2: { + ExecutionStack stack = frame.getStack(); + + if (stack.peekType(0).isCategory2()) { + if (stack.peekType(2).isCategory2()) { + // "form 4" in vmspec-2 + machine.popArgs(frame, 2); + machine.auxIntArg(0x212); + } else if (stack.peekType(3).isCategory1()) { + // "form 2" + machine.popArgs(frame, 3); + machine.auxIntArg(0x3213); + } else { + throw illegalTos(); + } + } else if (stack.peekType(1).isCategory1()) { + if (stack.peekType(2).isCategory2()) { + // "form 3" + machine.popArgs(frame, 3); + machine.auxIntArg(0x32132); + } else if (stack.peekType(3).isCategory1()) { + // "form 1" + machine.popArgs(frame, 4); + machine.auxIntArg(0x432143); + } else { + throw illegalTos(); + } + } else { + throw illegalTos(); + } + break; + } + case ByteOps.SWAP: { + ExecutionStack stack = frame.getStack(); + + if (!(stack.peekType(0).isCategory1() && + stack.peekType(1).isCategory1())) { + throw illegalTos(); + } + + machine.popArgs(frame, 2); + machine.auxIntArg(0x12); + break; + } + default: { + visitInvalid(opcode, offset, length); + return; + } + } + + machine.auxType(type); + machine.run(frame, offset, opcode); + } + + /** + * Checks whether the prototype is compatible with returning the + * given type, and throws if not. + * + * @param encountered {@code non-null;} the encountered return type + */ + private void checkReturnType(Type encountered) { + Type returnType = machine.getPrototype().getReturnType(); + + /* + * Check to see if the prototype's return type is + * possibly assignable from the type we encountered. This + * takes care of all the salient cases (types are the same, + * they're compatible primitive types, etc.). + */ + if (!Merger.isPossiblyAssignableFrom(returnType, encountered)) { + throw new SimException("return type mismatch: prototype " + + "indicates " + returnType.toHuman() + + ", but encountered type " + encountered.toHuman()); + } + } + + /** {@inheritDoc} */ + public void visitLocal(int opcode, int offset, int length, + int idx, Type type, int value) { + /* + * Note that the "type" parameter is always the simplest + * type based on the original opcode, e.g., "int" for + * "iload" (per se) and "Object" for "aload". So, when + * possible, we replace the type with the one indicated in + * the local variable table, though we still need to check + * to make sure it's valid for the opcode. + * + * The reason we use (offset + length) for the localOffset + * for a store is because it is only after the store that + * the local type becomes valid. On the other hand, the + * type associated with a load is valid at the start of + * the instruction. + */ + int localOffset = + (opcode == ByteOps.ISTORE) ? (offset + length) : offset; + LocalVariableList.Item local = + localVariables.pcAndIndexToLocal(localOffset, idx); + Type localType; + + if (local != null) { + localType = local.getType(); + if (localType.getBasicFrameType() != + type.getBasicFrameType()) { + BaseMachine.throwLocalMismatch(type, localType); + return; + } + } else { + localType = type; + } + + switch (opcode) { + case ByteOps.ILOAD: + case ByteOps.RET: { + machine.localArg(frame, idx); + machine.localInfo(local != null); + machine.auxType(type); + break; + } + case ByteOps.ISTORE: { + LocalItem item + = (local == null) ? null : local.getLocalItem(); + machine.popArgs(frame, type); + machine.auxType(type); + machine.localTarget(idx, localType, item); + break; + } + case ByteOps.IINC: { + LocalItem item + = (local == null) ? null : local.getLocalItem(); + machine.localArg(frame, idx); + machine.localTarget(idx, localType, item); + machine.auxType(type); + machine.auxIntArg(value); + machine.auxCstArg(CstInteger.make(value)); + break; + } + default: { + visitInvalid(opcode, offset, length); + return; + } + } + + machine.run(frame, offset, opcode); + } + + /** {@inheritDoc} */ + public void visitConstant(int opcode, int offset, int length, + Constant cst, int value) { + switch (opcode) { + case ByteOps.ANEWARRAY: { + machine.popArgs(frame, Type.INT); + break; + } + case ByteOps.PUTSTATIC: { + Type fieldType = ((CstFieldRef) cst).getType(); + machine.popArgs(frame, fieldType); + break; + } + case ByteOps.GETFIELD: + case ByteOps.CHECKCAST: + case ByteOps.INSTANCEOF: { + machine.popArgs(frame, Type.OBJECT); + break; + } + case ByteOps.PUTFIELD: { + Type fieldType = ((CstFieldRef) cst).getType(); + machine.popArgs(frame, Type.OBJECT, fieldType); + break; + } + case ByteOps.INVOKEINTERFACE: { + /* + * Convert the interface method ref into a normal + * method ref. + */ + cst = ((CstInterfaceMethodRef) cst).toMethodRef(); + // and fall through... + } + case ByteOps.INVOKEVIRTUAL: + case ByteOps.INVOKESPECIAL: { + /* + * Get the instance prototype, and use it to direct + * the machine. + */ + Prototype prototype = + ((CstMethodRef) cst).getPrototype(false); + machine.popArgs(frame, prototype); + break; + } + case ByteOps.INVOKESTATIC: { + /* + * Get the static prototype, and use it to direct + * the machine. + */ + Prototype prototype = + ((CstMethodRef) cst).getPrototype(true); + machine.popArgs(frame, prototype); + break; + } + case ByteOps.MULTIANEWARRAY: { + /* + * The "value" here is the count of dimensions to + * create. Make a prototype of that many "int" + * types, and tell the machine to pop them. This + * isn't the most efficient way in the world to do + * this, but then again, multianewarray is pretty + * darn rare and so not worth much effort + * optimizing for. + */ + Prototype prototype = + Prototype.internInts(Type.VOID, value); + machine.popArgs(frame, prototype); + break; + } + default: { + machine.clearArgs(); + break; + } + } + + machine.auxIntArg(value); + machine.auxCstArg(cst); + machine.run(frame, offset, opcode); + } + + /** {@inheritDoc} */ + public void visitBranch(int opcode, int offset, int length, + int target) { + switch (opcode) { + case ByteOps.IFEQ: + case ByteOps.IFNE: + case ByteOps.IFLT: + case ByteOps.IFGE: + case ByteOps.IFGT: + case ByteOps.IFLE: { + machine.popArgs(frame, Type.INT); + break; + } + case ByteOps.IFNULL: + case ByteOps.IFNONNULL: { + machine.popArgs(frame, Type.OBJECT); + break; + } + case ByteOps.IF_ICMPEQ: + case ByteOps.IF_ICMPNE: + case ByteOps.IF_ICMPLT: + case ByteOps.IF_ICMPGE: + case ByteOps.IF_ICMPGT: + case ByteOps.IF_ICMPLE: { + machine.popArgs(frame, Type.INT, Type.INT); + break; + } + case ByteOps.IF_ACMPEQ: + case ByteOps.IF_ACMPNE: { + machine.popArgs(frame, Type.OBJECT, Type.OBJECT); + break; + } + case ByteOps.GOTO: + case ByteOps.JSR: + case ByteOps.GOTO_W: + case ByteOps.JSR_W: { + machine.clearArgs(); + break; + } + default: { + visitInvalid(opcode, offset, length); + return; + } + } + + machine.auxTargetArg(target); + machine.run(frame, offset, opcode); + } + + /** {@inheritDoc} */ + public void visitSwitch(int opcode, int offset, int length, + SwitchList cases, int padding) { + machine.popArgs(frame, Type.INT); + machine.auxIntArg(padding); + machine.auxSwitchArg(cases); + machine.run(frame, offset, opcode); + } + + /** {@inheritDoc} */ + public void visitNewarray(int offset, int length, CstType type, + ArrayList<Constant> initValues) { + machine.popArgs(frame, Type.INT); + machine.auxInitValues(initValues); + machine.auxCstArg(type); + machine.run(frame, offset, ByteOps.NEWARRAY); + } + + /** {@inheritDoc} */ + public void setPreviousOffset(int offset) { + previousOffset = offset; + } + + /** {@inheritDoc} */ + public int getPreviousOffset() { + return previousOffset; + } + } +} |