Simulator.java revision de75089fb7216d19e9c22cce4dc62a49513477d3 
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     * Bytecode visitor used during simulation.
133     */
134    private class SimVisitor implements BytecodeArray.Visitor {
135        /**
136         * {@code non-null;} machine instance to use (just to avoid excessive
137         * cross-object field access)
138         */
139        private final Machine machine;
140
141        /**
142         * {@code null-ok;} frame to use; set with each call to
143         * {@link Simulator#simulate}
144         */
145        private Frame frame;
146
147        /** offset of the previous bytecode */
148        private int previousOffset;
149
150        /**
151         * Constructs an instance.
152         */
153        public SimVisitor() {
154            this.machine = Simulator.this.machine;
155            this.frame = null;
156        }
157
158        /**
159         * Sets the frame to act on.
160         *
161         * @param frame {@code non-null;} the frame
162         */
163        public void setFrame(Frame frame) {
164            if (frame == null) {
165                throw new NullPointerException("frame == null");
166            }
167
168            this.frame = frame;
169        }
170
171        /** {@inheritDoc} */
172        public void visitInvalid(int opcode, int offset, int length) {
173            throw new SimException("invalid opcode " + Hex.u1(opcode));
174        }
175
176        /** {@inheritDoc} */
177        public void visitNoArgs(int opcode, int offset, int length,
178                Type type) {
179            switch (opcode) {
180                case ByteOps.NOP: {
181                    machine.clearArgs();
182                    break;
183                }
184                case ByteOps.INEG: {
185                    machine.popArgs(frame, type);
186                    break;
187                }
188                case ByteOps.I2L:
189                case ByteOps.I2F:
190                case ByteOps.I2D:
191                case ByteOps.I2B:
192                case ByteOps.I2C:
193                case ByteOps.I2S: {
194                    machine.popArgs(frame, Type.INT);
195                    break;
196                }
197                case ByteOps.L2I:
198                case ByteOps.L2F:
199                case ByteOps.L2D: {
200                    machine.popArgs(frame, Type.LONG);
201                    break;
202                }
203                case ByteOps.F2I:
204                case ByteOps.F2L:
205                case ByteOps.F2D: {
206                    machine.popArgs(frame, Type.FLOAT);
207                    break;
208                }
209                case ByteOps.D2I:
210                case ByteOps.D2L:
211                case ByteOps.D2F: {
212                    machine.popArgs(frame, Type.DOUBLE);
213                    break;
214                }
215                case ByteOps.RETURN: {
216                    machine.clearArgs();
217                    checkReturnType(Type.VOID);
218                    break;
219                }
220                case ByteOps.IRETURN: {
221                    Type checkType = type;
222                    if (type == Type.OBJECT) {
223                        /*
224                         * For an object return, use the best-known
225                         * type of the popped value.
226                         */
227                        checkType = frame.getStack().peekType(0);
228                    }
229                    machine.popArgs(frame, type);
230                    checkReturnType(checkType);
231                    break;
232                }
233                case ByteOps.POP: {
234                    Type peekType = frame.getStack().peekType(0);
235                    if (peekType.isCategory2()) {
236                        throw illegalTos();
237                    }
238                    machine.popArgs(frame, 1);
239                    break;
240                }
241                case ByteOps.ARRAYLENGTH: {
242                    Type arrayType = frame.getStack().peekType(0);
243                    if (!arrayType.isArrayOrKnownNull()) {
244                        throw new SimException("type mismatch: expected " +
245                                "array type but encountered " +
246                                arrayType.toHuman());
247                    }
248                    machine.popArgs(frame, Type.OBJECT);
249                    break;
250                }
251                case ByteOps.ATHROW:
252                case ByteOps.MONITORENTER:
253                case ByteOps.MONITOREXIT: {
254                    machine.popArgs(frame, Type.OBJECT);
255                    break;
256                }
257                case ByteOps.IALOAD: {
258                    /*
259                     * Change the type (which is to be pushed) to
260                     * reflect the actual component type of the array
261                     * being popped, unless it turns out to be a
262                     * known-null, in which case we just use the type
263                     * implied by the original instruction.
264                     */
265                    Type foundArrayType = frame.getStack().peekType(1);
266                    Type requireArrayType;
267
268                    if (foundArrayType != Type.KNOWN_NULL) {
269                        requireArrayType = foundArrayType;
270                        type = foundArrayType.getComponentType();
271                    } else {
272                        requireArrayType = type.getArrayType();
273                    }
274
275                    machine.popArgs(frame, requireArrayType, Type.INT);
276                    break;
277                }
278                case ByteOps.IADD:
279                case ByteOps.ISUB:
280                case ByteOps.IMUL:
281                case ByteOps.IDIV:
282                case ByteOps.IREM:
283                case ByteOps.IAND:
284                case ByteOps.IOR:
285                case ByteOps.IXOR: {
286                    machine.popArgs(frame, type, type);
287                    break;
288                }
289                case ByteOps.ISHL:
290                case ByteOps.ISHR:
291                case ByteOps.IUSHR: {
292                    machine.popArgs(frame, type, Type.INT);
293                    break;
294                }
295                case ByteOps.LCMP: {
296                    machine.popArgs(frame, Type.LONG, Type.LONG);
297                    break;
298                }
299                case ByteOps.FCMPL:
300                case ByteOps.FCMPG: {
301                    machine.popArgs(frame, Type.FLOAT, Type.FLOAT);
302                    break;
303                }
304                case ByteOps.DCMPL:
305                case ByteOps.DCMPG: {
306                    machine.popArgs(frame, Type.DOUBLE, Type.DOUBLE);
307                    break;
308                }
309                case ByteOps.IASTORE: {
310                    /*
311                     * Change the type (which is the type of the
312                     * element) to reflect the actual component type
313                     * of the array being popped, unless it turns out
314                     * to be a known-null, in which case we just use
315                     * the type implied by the original instruction.
316                     * The category 1 vs. 2 thing here is that, if the
317                     * element type is category 2, we have to skip over
318                     * one extra stack slot to find the array.
319                     */
320                    Type foundArrayType =
321                        frame.getStack().peekType(type.isCategory1() ? 2 : 3);
322                    Type requireArrayType;
323
324                    if (foundArrayType != Type.KNOWN_NULL) {
325                        requireArrayType = foundArrayType;
326                        type = foundArrayType.getComponentType();
327                    } else {
328                        requireArrayType = type.getArrayType();
329                    }
330
331                    machine.popArgs(frame, requireArrayType, Type.INT, type);
332                    break;
333                }
334                case ByteOps.POP2:
335                case ByteOps.DUP2: {
336                    ExecutionStack stack = frame.getStack();
337                    int pattern;
338
339                    if (stack.peekType(0).isCategory2()) {
340                        // "form 2" in vmspec-2
341                        machine.popArgs(frame, 1);
342                        pattern = 0x11;
343                    } else if (stack.peekType(1).isCategory1()) {
344                        // "form 1"
345                        machine.popArgs(frame, 2);
346                        pattern = 0x2121;
347                    } else {
348                        throw illegalTos();
349                    }
350
351                    if (opcode == ByteOps.DUP2) {
352                        machine.auxIntArg(pattern);
353                    }
354                    break;
355                }
356                case ByteOps.DUP: {
357                    Type peekType = frame.getStack().peekType(0);
358
359                    if (peekType.isCategory2()) {
360                        throw illegalTos();
361                    }
362
363                    machine.popArgs(frame, 1);
364                    machine.auxIntArg(0x11);
365                    break;
366                }
367                case ByteOps.DUP_X1: {
368                    ExecutionStack stack = frame.getStack();
369
370                    if (! (stack.peekType(0).isCategory1() &&
371                           stack.peekType(1).isCategory1())) {
372                        throw illegalTos();
373                    }
374
375                    machine.popArgs(frame, 2);
376                    machine.auxIntArg(0x212);
377                    break;
378                }
379                case ByteOps.DUP_X2: {
380                    ExecutionStack stack = frame.getStack();
381
382                    if (stack.peekType(0).isCategory2()) {
383                        throw illegalTos();
384                    }
385
386                    if (stack.peekType(1).isCategory2()) {
387                        // "form 2" in vmspec-2
388                        machine.popArgs(frame, 2);
389                        machine.auxIntArg(0x212);
390                    } else if (stack.peekType(2).isCategory1()) {
391                        // "form 1"
392                        machine.popArgs(frame, 3);
393                        machine.auxIntArg(0x3213);
394                    } else {
395                        throw illegalTos();
396                    }
397                    break;
398                }
399                case ByteOps.DUP2_X1: {
400                    ExecutionStack stack = frame.getStack();
401
402                    if (stack.peekType(0).isCategory2()) {
403                        // "form 2" in vmspec-2
404                        if (stack.peekType(2).isCategory2()) {
405                            throw illegalTos();
406                        }
407                        machine.popArgs(frame, 2);
408                        machine.auxIntArg(0x212);
409                    } else {
410                        // "form 1"
411                        if (stack.peekType(1).isCategory2() ||
412                            stack.peekType(2).isCategory2()) {
413                            throw illegalTos();
414                        }
415                        machine.popArgs(frame, 3);
416                        machine.auxIntArg(0x32132);
417                    }
418                    break;
419                }
420                case ByteOps.DUP2_X2: {
421                    ExecutionStack stack = frame.getStack();
422
423                    if (stack.peekType(0).isCategory2()) {
424                        if (stack.peekType(2).isCategory2()) {
425                            // "form 4" in vmspec-2
426                            machine.popArgs(frame, 2);
427                            machine.auxIntArg(0x212);
428                        } else if (stack.peekType(3).isCategory1()) {
429                            // "form 2"
430                            machine.popArgs(frame, 3);
431                            machine.auxIntArg(0x3213);
432                        } else {
433                            throw illegalTos();
434                        }
435                    } else if (stack.peekType(1).isCategory1()) {
436                        if (stack.peekType(2).isCategory2()) {
437                            // "form 3"
438                            machine.popArgs(frame, 3);
439                            machine.auxIntArg(0x32132);
440                        } else if (stack.peekType(3).isCategory1()) {
441                            // "form 1"
442                            machine.popArgs(frame, 4);
443                            machine.auxIntArg(0x432143);
444                        } else {
445                            throw illegalTos();
446                        }
447                    } else {
448                        throw illegalTos();
449                    }
450                    break;
451                }
452                case ByteOps.SWAP: {
453                    ExecutionStack stack = frame.getStack();
454
455                    if (! (stack.peekType(0).isCategory1() &&
456                           stack.peekType(1).isCategory1())) {
457                        throw illegalTos();
458                    }
459
460                    machine.popArgs(frame, 2);
461                    machine.auxIntArg(0x12);
462                    break;
463                }
464                default: {
465                    visitInvalid(opcode, offset, length);
466                    return;
467                }
468            }
469
470            machine.auxType(type);
471            machine.run(frame, offset, opcode);
472        }
473
474        /**
475         * Checks whether the prototype is compatible with returning the
476         * given type, and throws if not.
477         *
478         * @param encountered {@code non-null;} the encountered return type
479         */
480        private void checkReturnType(Type encountered) {
481            Type returnType = machine.getPrototype().getReturnType();
482
483            /*
484             * Check to see if the prototype's return type is
485             * possibly assignable from the type we encountered. This
486             * takes care of all the salient cases (types are the same,
487             * they're compatible primitive types, etc.).
488             */
489            if (! Merger.isPossiblyAssignableFrom(returnType, encountered)) {
490                throw new SimException("return type mismatch: prototype " +
491                        "indicates " + returnType.toHuman() +
492                        ", but encountered type " + encountered.toHuman());
493            }
494        }
495
496        /** {@inheritDoc} */
497        public void visitLocal(int opcode, int offset, int length,
498                int idx, Type type, int value) {
499            /*
500             * Note that the "type" parameter is always the simplest
501             * type based on the original opcode, e.g., "int" for
502             * "iload" (per se) and "Object" for "aload". So, when
503             * possible, we replace the type with the one indicated in
504             * the local variable table, though we still need to check
505             * to make sure it's valid for the opcode.
506             *
507             * The reason we use (offset + length) for the localOffset
508             * for a store is because it is only after the store that
509             * the local type becomes valid. On the other hand, the
510             * type associated with a load is valid at the start of
511             * the instruction.
512             */
513            int localOffset =
514                (opcode == ByteOps.ISTORE) ? (offset + length) : offset;
515            LocalVariableList.Item local =
516                localVariables.pcAndIndexToLocal(localOffset, idx);
517            Type localType;
518
519            if (local != null) {
520                localType = local.getType();
521                if (localType.getBasicFrameType() !=
522                        type.getBasicFrameType()) {
523                    BaseMachine.throwLocalMismatch(type, localType);
524                    return;
525                }
526            } else {
527                localType = type;
528            }
529
530            switch (opcode) {
531                case ByteOps.ILOAD:
532                case ByteOps.RET: {
533                    machine.localArg(frame, idx);
534                    machine.auxType(type);
535                    break;
536                }
537                case ByteOps.ISTORE: {
538                    LocalItem item
539                            = (local == null) ? null : local.getLocalItem();
540                    machine.popArgs(frame, type);
541                    machine.auxType(type);
542                    machine.localTarget(idx, localType, item);
543                    break;
544                }
545                case ByteOps.IINC: {
546                    LocalItem item
547                            = (local == null) ? null : local.getLocalItem();
548                    machine.localArg(frame, idx);
549                    machine.localTarget(idx, localType, item);
550                    machine.auxType(type);
551                    machine.auxIntArg(value);
552                    machine.auxCstArg(CstInteger.make(value));
553                    break;
554                }
555                default: {
556                    visitInvalid(opcode, offset, length);
557                    return;
558                }
559            }
560
561            machine.run(frame, offset, opcode);
562        }
563
564        /** {@inheritDoc} */
565        public void visitConstant(int opcode, int offset, int length,
566                Constant cst, int value) {
567            switch (opcode) {
568                case ByteOps.ANEWARRAY: {
569                    machine.popArgs(frame, Type.INT);
570                    break;
571                }
572                case ByteOps.PUTSTATIC: {
573                    Type fieldType = ((CstFieldRef) cst).getType();
574                    machine.popArgs(frame, fieldType);
575                    break;
576                }
577                case ByteOps.GETFIELD:
578                case ByteOps.CHECKCAST:
579                case ByteOps.INSTANCEOF: {
580                    machine.popArgs(frame, Type.OBJECT);
581                    break;
582                }
583                case ByteOps.PUTFIELD: {
584                    Type fieldType = ((CstFieldRef) cst).getType();
585                    machine.popArgs(frame, Type.OBJECT, fieldType);
586                    break;
587                }
588                case ByteOps.INVOKEINTERFACE: {
589                    /*
590                     * Convert the interface method ref into a normal
591                     * method ref.
592                     */
593                    cst = ((CstInterfaceMethodRef) cst).toMethodRef();
594                    // and fall through...
595                }
596                case ByteOps.INVOKEVIRTUAL:
597                case ByteOps.INVOKESPECIAL: {
598                    /*
599                     * Get the instance prototype, and use it to direct
600                     * the machine.
601                     */
602                    Prototype prototype =
603                        ((CstMethodRef) cst).getPrototype(false);
604                    machine.popArgs(frame, prototype);
605                    break;
606                }
607                case ByteOps.INVOKESTATIC: {
608                    /*
609                     * Get the static prototype, and use it to direct
610                     * the machine.
611                     */
612                    Prototype prototype =
613                        ((CstMethodRef) cst).getPrototype(true);
614                    machine.popArgs(frame, prototype);
615                    break;
616                }
617                case ByteOps.MULTIANEWARRAY: {
618                    /*
619                     * The "value" here is the count of dimensions to
620                     * create. Make a prototype of that many "int"
621                     * types, and tell the machine to pop them. This
622                     * isn't the most efficient way in the world to do
623                     * this, but then again, multianewarray is pretty
624                     * darn rare and so not worth much effort
625                     * optimizing for.
626                     */
627                    Prototype prototype =
628                        Prototype.internInts(Type.VOID, value);
629                    machine.popArgs(frame, prototype);
630                    break;
631                }
632                default: {
633                    machine.clearArgs();
634                    break;
635                }
636            }
637
638            machine.auxIntArg(value);
639            machine.auxCstArg(cst);
640            machine.run(frame, offset, opcode);
641        }
642
643        /** {@inheritDoc} */
644        public void visitBranch(int opcode, int offset, int length,
645                int target) {
646            switch (opcode) {
647                case ByteOps.IFEQ:
648                case ByteOps.IFNE:
649                case ByteOps.IFLT:
650                case ByteOps.IFGE:
651                case ByteOps.IFGT:
652                case ByteOps.IFLE: {
653                    machine.popArgs(frame, Type.INT);
654                    break;
655                }
656                case ByteOps.IFNULL:
657                case ByteOps.IFNONNULL: {
658                    machine.popArgs(frame, Type.OBJECT);
659                    break;
660                }
661                case ByteOps.IF_ICMPEQ:
662                case ByteOps.IF_ICMPNE:
663                case ByteOps.IF_ICMPLT:
664                case ByteOps.IF_ICMPGE:
665                case ByteOps.IF_ICMPGT:
666                case ByteOps.IF_ICMPLE: {
667                    machine.popArgs(frame, Type.INT, Type.INT);
668                    break;
669                }
670                case ByteOps.IF_ACMPEQ:
671                case ByteOps.IF_ACMPNE: {
672                    machine.popArgs(frame, Type.OBJECT, Type.OBJECT);
673                    break;
674                }
675                case ByteOps.GOTO:
676                case ByteOps.JSR:
677                case ByteOps.GOTO_W:
678                case ByteOps.JSR_W: {
679                    machine.clearArgs();
680                    break;
681                }
682                default: {
683                    visitInvalid(opcode, offset, length);
684                    return;
685                }
686            }
687
688            machine.auxTargetArg(target);
689            machine.run(frame, offset, opcode);
690        }
691
692        /** {@inheritDoc} */
693        public void visitSwitch(int opcode, int offset, int length,
694                SwitchList cases, int padding) {
695            machine.popArgs(frame, Type.INT);
696            machine.auxIntArg(padding);
697            machine.auxSwitchArg(cases);
698            machine.run(frame, offset, opcode);
699        }
700
701        /** {@inheritDoc} */
702        public void visitNewarray(int offset, int length, CstType type,
703                ArrayList<Constant> initValues) {
704            machine.popArgs(frame, Type.INT);
705            machine.auxInitValues(initValues);
706            machine.auxCstArg(type);
707            machine.run(frame, offset, ByteOps.NEWARRAY);
708        }
709
710        /** {@inheritDoc} */
711        public void setPreviousOffset(int offset) {
712            previousOffset = offset;
713        }
714
715        /** {@inheritDoc} */
716        public int getPreviousOffset() {
717            return previousOffset;
718        }
719    }
720}
721