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