Simulator.java revision 9c907e0f7dd74ef351d0116783e088bb9ed68bdb 
1/*
2 * Copyright (C) 2007 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.android.dx.cf.code;
18
19import com.android.dx.rop.cst.Constant;
20import com.android.dx.rop.cst.CstFieldRef;
21import com.android.dx.rop.cst.CstInteger;
22import com.android.dx.rop.cst.CstInterfaceMethodRef;
23import com.android.dx.rop.cst.CstMethodRef;
24import com.android.dx.rop.cst.CstType;
25import com.android.dx.rop.cst.CstUtf8;
26import com.android.dx.rop.type.Prototype;
27import com.android.dx.rop.type.Type;
28import com.android.dx.rop.type.TypeBearer;
29import com.android.dx.rop.code.LocalItem;
30import com.android.dx.util.Hex;
31import com.android.dx.util.IntList;
32
33import java.util.List;
34import java.util.ArrayList;
35
36/**
37 * Class which knows how to simulate the effects of executing bytecode.
38 *
39 * <p><b>Note:</b> This class is not thread-safe. If multiple threads
40 * need to use a single instance, they must synchronize access explicitly
41 * between themselves.</p>
42 */
43public class Simulator {
44    /**
45     * {@code non-null;} canned error message for local variable
46     * table mismatches
47     */
48    private static final String LOCAL_MISMATCH_ERROR =
49        "This is symptomatic of .class transformation tools that ignore " +
50        "local variable information.";
51
52    /** {@code non-null;} machine to use when simulating */
53    private final Machine machine;
54
55    /** {@code non-null;} array of bytecode */
56    private final BytecodeArray code;
57
58    /** {@code non-null;} local variable information */
59    private final LocalVariableList localVariables;
60
61    /** {@code non-null;} visitor instance to use */
62    private final SimVisitor visitor;
63
64    /**
65     * Constructs an instance.
66     *
67     * @param machine {@code non-null;} machine to use when simulating
68     * @param method {@code non-null;} method data to use
69     */
70    public Simulator(Machine machine, ConcreteMethod method) {
71        if (machine == null) {
72            throw new NullPointerException("machine == null");
73        }
74
75        if (method == null) {
76            throw new NullPointerException("method == null");
77        }
78
79        this.machine = machine;
80        this.code = method.getCode();
81        this.localVariables = method.getLocalVariables();
82        this.visitor = new SimVisitor();
83    }
84
85    /**
86     * Simulates the effect of executing the given basic block. This modifies
87     * the passed-in frame to represent the end result.
88     *
89     * @param bb {@code non-null;} the basic block
90     * @param frame {@code non-null;} frame to operate on
91     */
92    public void simulate(ByteBlock bb, Frame frame) {
93        int end = bb.getEnd();
94
95        visitor.setFrame(frame);
96
97        try {
98            for (int off = bb.getStart(); off < end; /*off*/) {
99                int length = code.parseInstruction(off, visitor);
100                visitor.setPreviousOffset(off);
101                off += length;
102            }
103        } catch (SimException ex) {
104            frame.annotate(ex);
105            throw ex;
106        }
107    }
108
109    /**
110     * Simulates the effect of the instruction at the given offset, by
111     * making appropriate calls on the given frame.
112     *
113     * @param offset {@code >= 0;} offset of the instruction to simulate
114     * @param frame {@code non-null;} frame to operate on
115     * @return the length of the instruction, in bytes
116     */
117    public int simulate(int offset, Frame frame) {
118        visitor.setFrame(frame);
119        return code.parseInstruction(offset, visitor);
120    }
121
122    /**
123     * Constructs an "illegal top-of-stack" exception, for the stack
124     * manipulation opcodes.
125     */
126    private static SimException illegalTos() {
127        return new SimException("stack mismatch: illegal " +
128                "top-of-stack for opcode");
129    }
130
131    /**
132     * Returns the required array type for an array load or store
133     * instruction, based on a given implied type and an observed
134     * actual array type.
135     *
136     * <p>The interesting cases here have to do with object arrays,
137     * <code>byte[]</code>s, <code>boolean[]</code>s, and
138     * known-nulls.</p>
139     *
140     * <p>In the case of arrays of objects, we want to narrow the type
141     * to the actual array present on the stack, as long as what is
142     * present is an object type. Similarly, due to a quirk of the
143     * original bytecode representation, the instructions for dealing
144     * with <code>byte[]</code> and <code>boolean[]</code> are
145     * undifferentiated, and we aim here to return whichever one was
146     * actually present on the stack.</p>
147     *
148     * <p>In the case where there is a known-null on the stack where
149     * an array is expected, we just fall back to the implied type of
150     * the instruction. Due to the quirk described above, this means
151     * that source code that uses <code>boolean[]</code> might get
152     * translated surprisingly -- but correctly -- into an instruction
153     * that specifies a <code>byte[]</code>. It will be correct,
154     * because should the code actually execute, it will necessarily
155     * throw a <code>NullPointerException</code>, and it won't matter
156     * what opcode variant is used to achieve that result.</p>
157     *
158     * @param impliedType {@code non-null;} type implied by the
159     * instruction; is <i>not</i> an array type
160     * @param foundArrayType {@code non-null;} type found on the
161     * stack; is either an array type or a known-null
162     * @return {@code non-null;} the array type that should be
163     * required in this context
164     */
165    private static Type requiredArrayTypeFor(Type impliedType,
166            Type foundArrayType) {
167        if (foundArrayType == Type.KNOWN_NULL) {
168            return impliedType.getArrayType();
169        }
170
171        if ((impliedType == Type.OBJECT)
172                && foundArrayType.isArray()
173                && foundArrayType.getComponentType().isReference()) {
174            return foundArrayType;
175        }
176
177        if ((impliedType == Type.BYTE)
178                && (foundArrayType == Type.BOOLEAN_ARRAY)) {
179            /*
180             * Per above, an instruction with implied byte[] is also
181             * allowed to be used on boolean[].
182             */
183            return Type.BOOLEAN_ARRAY;
184        }
185
186        return impliedType.getArrayType();
187    }
188
189    /**
190     * Bytecode visitor used during simulation.
191     */
192    private class SimVisitor implements BytecodeArray.Visitor {
193        /**
194         * {@code non-null;} machine instance to use (just to avoid excessive
195         * cross-object field access)
196         */
197        private final Machine machine;
198
199        /**
200         * {@code null-ok;} frame to use; set with each call to
201         * {@link Simulator#simulate}
202         */
203        private Frame frame;
204
205        /** offset of the previous bytecode */
206        private int previousOffset;
207
208        /**
209         * Constructs an instance.
210         */
211        public SimVisitor() {
212            this.machine = Simulator.this.machine;
213            this.frame = null;
214        }
215
216        /**
217         * Sets the frame to act on.
218         *
219         * @param frame {@code non-null;} the frame
220         */
221        public void setFrame(Frame frame) {
222            if (frame == null) {
223                throw new NullPointerException("frame == null");
224            }
225
226            this.frame = frame;
227        }
228
229        /** {@inheritDoc} */
230        public void visitInvalid(int opcode, int offset, int length) {
231            throw new SimException("invalid opcode " + Hex.u1(opcode));
232        }
233
234        /** {@inheritDoc} */
235        public void visitNoArgs(int opcode, int offset, int length,
236                Type type) {
237            switch (opcode) {
238                case ByteOps.NOP: {
239                    machine.clearArgs();
240                    break;
241                }
242                case ByteOps.INEG: {
243                    machine.popArgs(frame, type);
244                    break;
245                }
246                case ByteOps.I2L:
247                case ByteOps.I2F:
248                case ByteOps.I2D:
249                case ByteOps.I2B:
250                case ByteOps.I2C:
251                case ByteOps.I2S: {
252                    machine.popArgs(frame, Type.INT);
253                    break;
254                }
255                case ByteOps.L2I:
256                case ByteOps.L2F:
257                case ByteOps.L2D: {
258                    machine.popArgs(frame, Type.LONG);
259                    break;
260                }
261                case ByteOps.F2I:
262                case ByteOps.F2L:
263                case ByteOps.F2D: {
264                    machine.popArgs(frame, Type.FLOAT);
265                    break;
266                }
267                case ByteOps.D2I:
268                case ByteOps.D2L:
269                case ByteOps.D2F: {
270                    machine.popArgs(frame, Type.DOUBLE);
271                    break;
272                }
273                case ByteOps.RETURN: {
274                    machine.clearArgs();
275                    checkReturnType(Type.VOID);
276                    break;
277                }
278                case ByteOps.IRETURN: {
279                    Type checkType = type;
280                    if (type == Type.OBJECT) {
281                        /*
282                         * For an object return, use the best-known
283                         * type of the popped value.
284                         */
285                        checkType = frame.getStack().peekType(0);
286                    }
287                    machine.popArgs(frame, type);
288                    checkReturnType(checkType);
289                    break;
290                }
291                case ByteOps.POP: {
292                    Type peekType = frame.getStack().peekType(0);
293                    if (peekType.isCategory2()) {
294                        throw illegalTos();
295                    }
296                    machine.popArgs(frame, 1);
297                    break;
298                }
299                case ByteOps.ARRAYLENGTH: {
300                    Type arrayType = frame.getStack().peekType(0);
301                    if (!arrayType.isArrayOrKnownNull()) {
302                        throw new SimException("type mismatch: expected " +
303                                "array type but encountered " +
304                                arrayType.toHuman());
305                    }
306                    machine.popArgs(frame, Type.OBJECT);
307                    break;
308                }
309                case ByteOps.ATHROW:
310                case ByteOps.MONITORENTER:
311                case ByteOps.MONITOREXIT: {
312                    machine.popArgs(frame, Type.OBJECT);
313                    break;
314                }
315                case ByteOps.IALOAD: {
316                    /*
317                     * See comment on requiredArrayTypeFor() for explanation
318                     * about what's going on here.
319                     */
320                    Type foundArrayType = frame.getStack().peekType(1);
321                    Type requiredArrayType =
322                        requiredArrayTypeFor(type, foundArrayType);
323
324                    // Make type agree with the discovered requiredArrayType.
325                    type = requiredArrayType.getComponentType();
326
327                    machine.popArgs(frame, requiredArrayType, Type.INT);
328                    break;
329                }
330                case ByteOps.IADD:
331                case ByteOps.ISUB:
332                case ByteOps.IMUL:
333                case ByteOps.IDIV:
334                case ByteOps.IREM:
335                case ByteOps.IAND:
336                case ByteOps.IOR:
337                case ByteOps.IXOR: {
338                    machine.popArgs(frame, type, type);
339                    break;
340                }
341                case ByteOps.ISHL:
342                case ByteOps.ISHR:
343                case ByteOps.IUSHR: {
344                    machine.popArgs(frame, type, Type.INT);
345                    break;
346                }
347                case ByteOps.LCMP: {
348                    machine.popArgs(frame, Type.LONG, Type.LONG);
349                    break;
350                }
351                case ByteOps.FCMPL:
352                case ByteOps.FCMPG: {
353                    machine.popArgs(frame, Type.FLOAT, Type.FLOAT);
354                    break;
355                }
356                case ByteOps.DCMPL:
357                case ByteOps.DCMPG: {
358                    machine.popArgs(frame, Type.DOUBLE, Type.DOUBLE);
359                    break;
360                }
361                case ByteOps.IASTORE: {
362                    /*
363                     * See comment on requiredArrayTypeFor() for
364                     * explanation about what's going on here. In
365                     * addition to that, the category 1 vs. 2 thing
366                     * below is to deal with the fact that, if the
367                     * element type is category 2, we have to skip
368                     * over one extra stack slot to find the array.
369                     */
370                    Type foundArrayType =
371                        frame.getStack().peekType(type.isCategory1() ? 2 : 3);
372                    Type requiredArrayType =
373                        requiredArrayTypeFor(type, foundArrayType);
374
375                    // Make type agree with the discovered requiredArrayType.
376                    type = requiredArrayType.getComponentType();
377
378                    machine.popArgs(frame, requiredArrayType, Type.INT, type);
379                    break;
380                }
381                case ByteOps.POP2:
382                case ByteOps.DUP2: {
383                    ExecutionStack stack = frame.getStack();
384                    int pattern;
385
386                    if (stack.peekType(0).isCategory2()) {
387                        // "form 2" in vmspec-2
388                        machine.popArgs(frame, 1);
389                        pattern = 0x11;
390                    } else if (stack.peekType(1).isCategory1()) {
391                        // "form 1"
392                        machine.popArgs(frame, 2);
393                        pattern = 0x2121;
394                    } else {
395                        throw illegalTos();
396                    }
397
398                    if (opcode == ByteOps.DUP2) {
399                        machine.auxIntArg(pattern);
400                    }
401                    break;
402                }
403                case ByteOps.DUP: {
404                    Type peekType = frame.getStack().peekType(0);
405
406                    if (peekType.isCategory2()) {
407                        throw illegalTos();
408                    }
409
410                    machine.popArgs(frame, 1);
411                    machine.auxIntArg(0x11);
412                    break;
413                }
414                case ByteOps.DUP_X1: {
415                    ExecutionStack stack = frame.getStack();
416
417                    if (!(stack.peekType(0).isCategory1() &&
418                          stack.peekType(1).isCategory1())) {
419                        throw illegalTos();
420                    }
421
422                    machine.popArgs(frame, 2);
423                    machine.auxIntArg(0x212);
424                    break;
425                }
426                case ByteOps.DUP_X2: {
427                    ExecutionStack stack = frame.getStack();
428
429                    if (stack.peekType(0).isCategory2()) {
430                        throw illegalTos();
431                    }
432
433                    if (stack.peekType(1).isCategory2()) {
434                        // "form 2" in vmspec-2
435                        machine.popArgs(frame, 2);
436                        machine.auxIntArg(0x212);
437                    } else if (stack.peekType(2).isCategory1()) {
438                        // "form 1"
439                        machine.popArgs(frame, 3);
440                        machine.auxIntArg(0x3213);
441                    } else {
442                        throw illegalTos();
443                    }
444                    break;
445                }
446                case ByteOps.DUP2_X1: {
447                    ExecutionStack stack = frame.getStack();
448
449                    if (stack.peekType(0).isCategory2()) {
450                        // "form 2" in vmspec-2
451                        if (stack.peekType(2).isCategory2()) {
452                            throw illegalTos();
453                        }
454                        machine.popArgs(frame, 2);
455                        machine.auxIntArg(0x212);
456                    } else {
457                        // "form 1"
458                        if (stack.peekType(1).isCategory2() ||
459                            stack.peekType(2).isCategory2()) {
460                            throw illegalTos();
461                        }
462                        machine.popArgs(frame, 3);
463                        machine.auxIntArg(0x32132);
464                    }
465                    break;
466                }
467                case ByteOps.DUP2_X2: {
468                    ExecutionStack stack = frame.getStack();
469
470                    if (stack.peekType(0).isCategory2()) {
471                        if (stack.peekType(2).isCategory2()) {
472                            // "form 4" in vmspec-2
473                            machine.popArgs(frame, 2);
474                            machine.auxIntArg(0x212);
475                        } else if (stack.peekType(3).isCategory1()) {
476                            // "form 2"
477                            machine.popArgs(frame, 3);
478                            machine.auxIntArg(0x3213);
479                        } else {
480                            throw illegalTos();
481                        }
482                    } else if (stack.peekType(1).isCategory1()) {
483                        if (stack.peekType(2).isCategory2()) {
484                            // "form 3"
485                            machine.popArgs(frame, 3);
486                            machine.auxIntArg(0x32132);
487                        } else if (stack.peekType(3).isCategory1()) {
488                            // "form 1"
489                            machine.popArgs(frame, 4);
490                            machine.auxIntArg(0x432143);
491                        } else {
492                            throw illegalTos();
493                        }
494                    } else {
495                        throw illegalTos();
496                    }
497                    break;
498                }
499                case ByteOps.SWAP: {
500                    ExecutionStack stack = frame.getStack();
501
502                    if (!(stack.peekType(0).isCategory1() &&
503                          stack.peekType(1).isCategory1())) {
504                        throw illegalTos();
505                    }
506
507                    machine.popArgs(frame, 2);
508                    machine.auxIntArg(0x12);
509                    break;
510                }
511                default: {
512                    visitInvalid(opcode, offset, length);
513                    return;
514                }
515            }
516
517            machine.auxType(type);
518            machine.run(frame, offset, opcode);
519        }
520
521        /**
522         * Checks whether the prototype is compatible with returning the
523         * given type, and throws if not.
524         *
525         * @param encountered {@code non-null;} the encountered return type
526         */
527        private void checkReturnType(Type encountered) {
528            Type returnType = machine.getPrototype().getReturnType();
529
530            /*
531             * Check to see if the prototype's return type is
532             * possibly assignable from the type we encountered. This
533             * takes care of all the salient cases (types are the same,
534             * they're compatible primitive types, etc.).
535             */
536            if (!Merger.isPossiblyAssignableFrom(returnType, encountered)) {
537                throw new SimException("return type mismatch: prototype " +
538                        "indicates " + returnType.toHuman() +
539                        ", but encountered type " + encountered.toHuman());
540            }
541        }
542
543        /** {@inheritDoc} */
544        public void visitLocal(int opcode, int offset, int length,
545                int idx, Type type, int value) {
546            /*
547             * Note that the "type" parameter is always the simplest
548             * type based on the original opcode, e.g., "int" for
549             * "iload" (per se) and "Object" for "aload". So, when
550             * possible, we replace the type with the one indicated in
551             * the local variable table, though we still need to check
552             * to make sure it's valid for the opcode.
553             *
554             * The reason we use (offset + length) for the localOffset
555             * for a store is because it is only after the store that
556             * the local type becomes valid. On the other hand, the
557             * type associated with a load is valid at the start of
558             * the instruction.
559             */
560            int localOffset =
561                (opcode == ByteOps.ISTORE) ? (offset + length) : offset;
562            LocalVariableList.Item local =
563                localVariables.pcAndIndexToLocal(localOffset, idx);
564            Type localType;
565
566            if (local != null) {
567                localType = local.getType();
568                if (localType.getBasicFrameType() !=
569                        type.getBasicFrameType()) {
570                    BaseMachine.throwLocalMismatch(type, localType);
571                    return;
572                }
573            } else {
574                localType = type;
575            }
576
577            switch (opcode) {
578                case ByteOps.ILOAD:
579                case ByteOps.RET: {
580                    machine.localArg(frame, idx);
581                    machine.auxType(type);
582                    break;
583                }
584                case ByteOps.ISTORE: {
585                    LocalItem item
586                            = (local == null) ? null : local.getLocalItem();
587                    machine.popArgs(frame, type);
588                    machine.auxType(type);
589                    machine.localTarget(idx, localType, item);
590                    break;
591                }
592                case ByteOps.IINC: {
593                    LocalItem item
594                            = (local == null) ? null : local.getLocalItem();
595                    machine.localArg(frame, idx);
596                    machine.localTarget(idx, localType, item);
597                    machine.auxType(type);
598                    machine.auxIntArg(value);
599                    machine.auxCstArg(CstInteger.make(value));
600                    break;
601                }
602                default: {
603                    visitInvalid(opcode, offset, length);
604                    return;
605                }
606            }
607
608            machine.run(frame, offset, opcode);
609        }
610
611        /** {@inheritDoc} */
612        public void visitConstant(int opcode, int offset, int length,
613                Constant cst, int value) {
614            switch (opcode) {
615                case ByteOps.ANEWARRAY: {
616                    machine.popArgs(frame, Type.INT);
617                    break;
618                }
619                case ByteOps.PUTSTATIC: {
620                    Type fieldType = ((CstFieldRef) cst).getType();
621                    machine.popArgs(frame, fieldType);
622                    break;
623                }
624                case ByteOps.GETFIELD:
625                case ByteOps.CHECKCAST:
626                case ByteOps.INSTANCEOF: {
627                    machine.popArgs(frame, Type.OBJECT);
628                    break;
629                }
630                case ByteOps.PUTFIELD: {
631                    Type fieldType = ((CstFieldRef) cst).getType();
632                    machine.popArgs(frame, Type.OBJECT, fieldType);
633                    break;
634                }
635                case ByteOps.INVOKEINTERFACE: {
636                    /*
637                     * Convert the interface method ref into a normal
638                     * method ref.
639                     */
640                    cst = ((CstInterfaceMethodRef) cst).toMethodRef();
641                    // and fall through...
642                }
643                case ByteOps.INVOKEVIRTUAL:
644                case ByteOps.INVOKESPECIAL: {
645                    /*
646                     * Get the instance prototype, and use it to direct
647                     * the machine.
648                     */
649                    Prototype prototype =
650                        ((CstMethodRef) cst).getPrototype(false);
651                    machine.popArgs(frame, prototype);
652                    break;
653                }
654                case ByteOps.INVOKESTATIC: {
655                    /*
656                     * Get the static prototype, and use it to direct
657                     * the machine.
658                     */
659                    Prototype prototype =
660                        ((CstMethodRef) cst).getPrototype(true);
661                    machine.popArgs(frame, prototype);
662                    break;
663                }
664                case ByteOps.MULTIANEWARRAY: {
665                    /*
666                     * The "value" here is the count of dimensions to
667                     * create. Make a prototype of that many "int"
668                     * types, and tell the machine to pop them. This
669                     * isn't the most efficient way in the world to do
670                     * this, but then again, multianewarray is pretty
671                     * darn rare and so not worth much effort
672                     * optimizing for.
673                     */
674                    Prototype prototype =
675                        Prototype.internInts(Type.VOID, value);
676                    machine.popArgs(frame, prototype);
677                    break;
678                }
679                default: {
680                    machine.clearArgs();
681                    break;
682                }
683            }
684
685            machine.auxIntArg(value);
686            machine.auxCstArg(cst);
687            machine.run(frame, offset, opcode);
688        }
689
690        /** {@inheritDoc} */
691        public void visitBranch(int opcode, int offset, int length,
692                int target) {
693            switch (opcode) {
694                case ByteOps.IFEQ:
695                case ByteOps.IFNE:
696                case ByteOps.IFLT:
697                case ByteOps.IFGE:
698                case ByteOps.IFGT:
699                case ByteOps.IFLE: {
700                    machine.popArgs(frame, Type.INT);
701                    break;
702                }
703                case ByteOps.IFNULL:
704                case ByteOps.IFNONNULL: {
705                    machine.popArgs(frame, Type.OBJECT);
706                    break;
707                }
708                case ByteOps.IF_ICMPEQ:
709                case ByteOps.IF_ICMPNE:
710                case ByteOps.IF_ICMPLT:
711                case ByteOps.IF_ICMPGE:
712                case ByteOps.IF_ICMPGT:
713                case ByteOps.IF_ICMPLE: {
714                    machine.popArgs(frame, Type.INT, Type.INT);
715                    break;
716                }
717                case ByteOps.IF_ACMPEQ:
718                case ByteOps.IF_ACMPNE: {
719                    machine.popArgs(frame, Type.OBJECT, Type.OBJECT);
720                    break;
721                }
722                case ByteOps.GOTO:
723                case ByteOps.JSR:
724                case ByteOps.GOTO_W:
725                case ByteOps.JSR_W: {
726                    machine.clearArgs();
727                    break;
728                }
729                default: {
730                    visitInvalid(opcode, offset, length);
731                    return;
732                }
733            }
734
735            machine.auxTargetArg(target);
736            machine.run(frame, offset, opcode);
737        }
738
739        /** {@inheritDoc} */
740        public void visitSwitch(int opcode, int offset, int length,
741                SwitchList cases, int padding) {
742            machine.popArgs(frame, Type.INT);
743            machine.auxIntArg(padding);
744            machine.auxSwitchArg(cases);
745            machine.run(frame, offset, opcode);
746        }
747
748        /** {@inheritDoc} */
749        public void visitNewarray(int offset, int length, CstType type,
750                ArrayList<Constant> initValues) {
751            machine.popArgs(frame, Type.INT);
752            machine.auxInitValues(initValues);
753            machine.auxCstArg(type);
754            machine.run(frame, offset, ByteOps.NEWARRAY);
755        }
756
757        /** {@inheritDoc} */
758        public void setPreviousOffset(int offset) {
759            previousOffset = offset;
760        }
761
762        /** {@inheritDoc} */
763        public int getPreviousOffset() {
764            return previousOffset;
765        }
766    }
767}
768