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