/*
 * Copyright (C) 2007 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.android.dx.cf.code;

import com.android.dx.rop.cst.Constant;
import com.android.dx.rop.cst.ConstantPool;
import com.android.dx.rop.cst.CstDouble;
import com.android.dx.rop.cst.CstFloat;
import com.android.dx.rop.cst.CstInteger;
import com.android.dx.rop.cst.CstKnownNull;
import com.android.dx.rop.cst.CstLiteralBits;
import com.android.dx.rop.cst.CstLong;
import com.android.dx.rop.cst.CstType;
import com.android.dx.rop.type.Type;
import com.android.dx.util.Bits;
import com.android.dx.util.ByteArray;
import com.android.dx.util.Hex;
import java.util.ArrayList;

/**
 * Bytecode array, which is part of a standard <code>Code</code> attribute.
 */
public final class BytecodeArray {
    /** convenient no-op implementation of {@link Visitor} */
    public static final Visitor EMPTY_VISITOR = new BaseVisitor();

    /** non-null; underlying bytes */
    private final ByteArray bytes;

    /** non-null; constant pool to use when resolving constant pool indices */
    private final ConstantPool pool;

    /**
     * Constructs an instance.
     * 
     * @param bytes non-null; underlying bytes
     * @param pool non-null; constant pool to use when resolving constant
     * pool indices
     */
    public BytecodeArray(ByteArray bytes, ConstantPool pool) {
        if (bytes == null) {
            throw new NullPointerException("bytes == null");
        }

        if (pool == null) {
            throw new NullPointerException("pool == null");
        }

        this.bytes = bytes;
        this.pool = pool;
    }

    /**
     * Gets the underlying byte array.
     * 
     * @return non-null; the byte array
     */
    public ByteArray getBytes() {
        return bytes;
    }

    /**
     * Gets the size of the bytecode array, per se.
     * 
     * @return &gt;= 0; the length of the bytecode array
     */
    public int size() {
        return bytes.size();
    }

    /**
     * Gets the total length of this structure in bytes, when included in
     * a <code>Code</code> attribute. The returned value includes the
     * array size plus four bytes for <code>code_length</code>.
     * 
     * @return &gt;= 4; the total length, in bytes
     */
    public int byteLength() {
        return 4 + bytes.size();
    }

    /**
     * Parses each instruction in the array, in order.
     * 
     * @param visitor null-ok; visitor to call back to for each instruction
     */
    public void forEach(Visitor visitor) {
        int sz = bytes.size();
        int at = 0;

        while (at < sz) {
            /*
             * Don't record the previous offset here, so that we get to see the
             * raw code that initializes the array
             */
            at += parseInstruction(at, visitor);
        }
    }

    /**
     * Finds the offset to each instruction in the bytecode array. The
     * result is a bit set with the offset of each opcode-per-se flipped on.
     * 
     * @see Bits
     * @return non-null; appropriately constructed bit set
     */
    public int[] getInstructionOffsets() {
        int sz = bytes.size();
        int[] result = Bits.makeBitSet(sz);
        int at = 0;

        while (at < sz) {
            Bits.set(result, at, true);
            int length = parseInstruction(at, null);
            at += length;
        }

        return result;
    }

    /**
     * Processes the given "work set" by repeatedly finding the lowest bit
     * in the set, clearing it, and parsing and visiting the instruction at
     * the indicated offset (that is, the bit index), repeating until the
     * work set is empty. It is expected that the visitor will regularly
     * set new bits in the work set during the process.
     * 
     * @param workSet non-null; the work set to process
     * @param visitor non-null; visitor to call back to for each instruction
     */
    public void processWorkSet(int[] workSet, Visitor visitor) {
        if (visitor == null) {
            throw new NullPointerException("visitor == null");
        }

        for (;;) {
            int offset = Bits.findFirst(workSet, 0);
            if (offset < 0) {
                break;
            }
            Bits.clear(workSet, offset);
            parseInstruction(offset, visitor);
            visitor.setPreviousOffset(offset);
        }
    }

    /**
     * Parses the instruction at the indicated offset. Indicate the
     * result by calling the visitor if supplied and by returning the
     * number of bytes consumed by the instruction.
     * 
     * <p>In order to simplify further processing, the opcodes passed
     * to the visitor are canonicalized, altering the opcode to a more
     * universal one and making formerly implicit arguments
     * explicit. In particular:</p>
     * 
     * <ul>
     * <li>The opcodes to push literal constants of primitive types all become
     *   <code>ldc</code>.
     *   E.g., <code>fconst_0</code>, <code>sipush</code>, and 
     *   <code>lconst_0</code> qualify for this treatment.</li>
     * <li><code>aconst_null</code> becomes <code>ldc</code> of a
     *   "known null."</li>
     * <li>Shorthand local variable accessors become the corresponding
     *   longhand. E.g. <code>aload_2</code> becomes <code>aload</code>.</li>
     * <li><code>goto_w</code> and <code>jsr_w</code> become <code>goto</code>
     *   and <code>jsr</code> (respectively).</li>
     * <li><code>ldc_w</code> becomes <code>ldc</code>.</li>
     * <li><code>tableswitch</code> becomes <code>lookupswitch</code>.
     * <li>Arithmetic, array, and value-returning ops are collapsed
     *   to the <code>int</code> variant opcode, with the <code>type</code>
     *   argument set to indicate the actual type. E.g.,
     *   <code>fadd</code> becomes <code>iadd</code>, but
     *   <code>type</code> is passed as <code>Type.FLOAT</code> in that
     *   case. Similarly, <code>areturn</code> becomes
     *   <code>ireturn</code>. (However, <code>return</code> remains
     *   unchanged.</li>
     * <li>Local variable access ops are collapsed to the <code>int</code>
     *   variant opcode, with the <code>type</code> argument set to indicate
     *   the actual type. E.g., <code>aload</code> becomes <code>iload</code>,
     *   but <code>type</code> is passed as <code>Type.OBJECT</code> in
     *   that case.</li>
     * <li>Numeric conversion ops (<code>i2l</code>, etc.) are left alone
     *   to avoid too much confustion, but their <code>type</code> is
     *   the pushed type. E.g., <code>i2b</code> gets type
     *   <code>Type.INT</code>, and <code>f2d</code> gets type
     *   <code>Type.DOUBLE</code>. Other unaltered opcodes also get
     *   their pushed type. E.g., <code>arraylength</code> gets type
     *   <code>Type.INT</code>.</li>
     * </ul>
     * 
     * @param offset &gt;= 0, &lt; bytes.size(); offset to the start of the
     * instruction
     * @param visitor null-ok; visitor to call back to
     * @return the length of the instruction, in bytes
     */
    public int parseInstruction(int offset, Visitor visitor) {
        if (visitor == null) {
            visitor = EMPTY_VISITOR;
        }

        try {
            int opcode = bytes.getUnsignedByte(offset);
            int info = ByteOps.opInfo(opcode);
            int fmt = info & ByteOps.FMT_MASK;

            switch (opcode) {
                case ByteOps.NOP: {
                    visitor.visitNoArgs(opcode, offset, 1, Type.VOID);
                    return 1;
                }
                case ByteOps.ACONST_NULL: {
                    visitor.visitConstant(ByteOps.LDC, offset, 1,
                                          CstKnownNull.THE_ONE, 0);
                    return 1;
                }
                case ByteOps.ICONST_M1: {
                    visitor.visitConstant(ByteOps.LDC, offset, 1,
                                          CstInteger.VALUE_M1, -1);
                    return 1;
                }
                case ByteOps.ICONST_0: {
                    visitor.visitConstant(ByteOps.LDC, offset, 1,
                                          CstInteger.VALUE_0, 0);
                    return 1;
                }
                case ByteOps.ICONST_1: {
                    visitor.visitConstant(ByteOps.LDC, offset, 1,
                                          CstInteger.VALUE_1, 1);
                    return 1;
                }
                case ByteOps.ICONST_2: {
                    visitor.visitConstant(ByteOps.LDC, offset, 1,
                                          CstInteger.VALUE_2, 2);
                    return 1;
                }
                case ByteOps.ICONST_3: {
                    visitor.visitConstant(ByteOps.LDC, offset, 1,
                                          CstInteger.VALUE_3, 3);
                    return 1;
                }
                case ByteOps.ICONST_4: {
                    visitor.visitConstant(ByteOps.LDC, offset, 1,
                                          CstInteger.VALUE_4, 4);
                    return 1;
                }
                case ByteOps.ICONST_5:  {
                    visitor.visitConstant(ByteOps.LDC, offset, 1,
                                          CstInteger.VALUE_5, 5);
                    return 1;
                }
                case ByteOps.LCONST_0: {
                    visitor.visitConstant(ByteOps.LDC, offset, 1,
                                          CstLong.VALUE_0, 0);
                    return 1;
                }
                case ByteOps.LCONST_1: {
                    visitor.visitConstant(ByteOps.LDC, offset, 1,
                                          CstLong.VALUE_1, 0);
                    return 1;
                }
                case ByteOps.FCONST_0: {
                    visitor.visitConstant(ByteOps.LDC, offset, 1,
                                          CstFloat.VALUE_0, 0);
                    return 1;
                }
                case ByteOps.FCONST_1: {
                    visitor.visitConstant(ByteOps.LDC, offset, 1,
                                          CstFloat.VALUE_1, 0);
                    return 1;
                }
                case ByteOps.FCONST_2:  {
                    visitor.visitConstant(ByteOps.LDC, offset, 1,
                                          CstFloat.VALUE_2, 0);
                    return 1;
                }
                case ByteOps.DCONST_0: {
                    visitor.visitConstant(ByteOps.LDC, offset, 1,
                                          CstDouble.VALUE_0, 0);
                    return 1;
                }
                case ByteOps.DCONST_1: {
                    visitor.visitConstant(ByteOps.LDC, offset, 1,
                                          CstDouble.VALUE_1, 0);
                    return 1;
                }
                case ByteOps.BIPUSH: {
                    int value = bytes.getByte(offset + 1);
                    visitor.visitConstant(ByteOps.LDC, offset, 2,
                                          CstInteger.make(value), value);
                    return 2;
                }
                case ByteOps.SIPUSH: {
                    int value = bytes.getShort(offset + 1);
                    visitor.visitConstant(ByteOps.LDC, offset, 3,
                                          CstInteger.make(value), value);
                    return 3;
                }
                case ByteOps.LDC: {
                    int idx = bytes.getUnsignedByte(offset + 1);
                    Constant cst = pool.get(idx);
                    int value = (cst instanceof CstInteger) ? 
                        ((CstInteger) cst).getValue() : 0;
                    visitor.visitConstant(ByteOps.LDC, offset, 2, cst, value);
                    return 2;
                }
                case ByteOps.LDC_W: {
                    int idx = bytes.getUnsignedShort(offset + 1);
                    Constant cst = pool.get(idx);
                    int value = (cst instanceof CstInteger) ? 
                        ((CstInteger) cst).getValue() : 0;
                    visitor.visitConstant(ByteOps.LDC, offset, 3, cst, value);
                    return 3;
                }
                case ByteOps.LDC2_W: {
                    int idx = bytes.getUnsignedShort(offset + 1);
                    Constant cst = pool.get(idx);
                    visitor.visitConstant(ByteOps.LDC2_W, offset, 3, cst, 0);
                    return 3;
                }
                case ByteOps.ILOAD: {
                    int idx = bytes.getUnsignedByte(offset + 1);
                    visitor.visitLocal(ByteOps.ILOAD, offset, 2, idx,
                                       Type.INT, 0);
                    return 2;
                }
                case ByteOps.LLOAD: {
                    int idx = bytes.getUnsignedByte(offset + 1);
                    visitor.visitLocal(ByteOps.ILOAD, offset, 2, idx,
                                       Type.LONG, 0);
                    return 2;
                }
                case ByteOps.FLOAD: {
                    int idx = bytes.getUnsignedByte(offset + 1);
                    visitor.visitLocal(ByteOps.ILOAD, offset, 2, idx,
                                       Type.FLOAT, 0);
                    return 2;
                }
                case ByteOps.DLOAD: {
                    int idx = bytes.getUnsignedByte(offset + 1);
                    visitor.visitLocal(ByteOps.ILOAD, offset, 2, idx,
                                       Type.DOUBLE, 0);
                    return 2;
                }
                case ByteOps.ALOAD: {
                    int idx = bytes.getUnsignedByte(offset + 1);
                    visitor.visitLocal(ByteOps.ILOAD, offset, 2, idx,
                                       Type.OBJECT, 0);
                    return 2;
                }
                case ByteOps.ILOAD_0:
                case ByteOps.ILOAD_1:
                case ByteOps.ILOAD_2:
                case ByteOps.ILOAD_3: {
                    int idx = opcode - ByteOps.ILOAD_0;
                    visitor.visitLocal(ByteOps.ILOAD, offset, 1, idx,
                                       Type.INT, 0);
                    return 1;
                }
                case ByteOps.LLOAD_0:
                case ByteOps.LLOAD_1:
                case ByteOps.LLOAD_2:
                case ByteOps.LLOAD_3: {
                    int idx = opcode - ByteOps.LLOAD_0;
                    visitor.visitLocal(ByteOps.ILOAD, offset, 1, idx,
                                       Type.LONG, 0);
                    return 1;
                }
                case ByteOps.FLOAD_0:
                case ByteOps.FLOAD_1:
                case ByteOps.FLOAD_2:
                case ByteOps.FLOAD_3: {
                    int idx = opcode - ByteOps.FLOAD_0;
                    visitor.visitLocal(ByteOps.ILOAD, offset, 1, idx,
                                       Type.FLOAT, 0);
                    return 1;
                }
                case ByteOps.DLOAD_0:
                case ByteOps.DLOAD_1:
                case ByteOps.DLOAD_2:
                case ByteOps.DLOAD_3: {
                    int idx = opcode - ByteOps.DLOAD_0;
                    visitor.visitLocal(ByteOps.ILOAD, offset, 1, idx,
                                       Type.DOUBLE, 0);
                    return 1;
                }
                case ByteOps.ALOAD_0:
                case ByteOps.ALOAD_1:
                case ByteOps.ALOAD_2:
                case ByteOps.ALOAD_3: {
                    int idx = opcode - ByteOps.ALOAD_0;
                    visitor.visitLocal(ByteOps.ILOAD, offset, 1, idx,
                                       Type.OBJECT, 0);
                    return 1;
                }
                case ByteOps.IALOAD: {
                    visitor.visitNoArgs(ByteOps.IALOAD, offset, 1, Type.INT);
                    return 1;
                }
                case ByteOps.LALOAD: {
                    visitor.visitNoArgs(ByteOps.IALOAD, offset, 1, Type.LONG);
                    return 1;
                }
                case ByteOps.FALOAD: {
                    visitor.visitNoArgs(ByteOps.IALOAD, offset, 1,
                                        Type.FLOAT);
                    return 1;
                }
                case ByteOps.DALOAD: {
                    visitor.visitNoArgs(ByteOps.IALOAD, offset, 1,
                                        Type.DOUBLE);
                    return 1;
                }
                case ByteOps.AALOAD: {
                    visitor.visitNoArgs(ByteOps.IALOAD, offset, 1,
                                        Type.OBJECT);
                    return 1;
                }
                case ByteOps.BALOAD: {
                    visitor.visitNoArgs(ByteOps.IALOAD, offset, 1, Type.BYTE);
                    return 1;
                }
                case ByteOps.CALOAD: {
                    visitor.visitNoArgs(ByteOps.IALOAD, offset, 1, Type.CHAR);
                    return 1;
                }
                case ByteOps.SALOAD: {
                    visitor.visitNoArgs(ByteOps.IALOAD, offset, 1,
                                        Type.SHORT);
                    return 1;
                }
                case ByteOps.ISTORE: {
                    int idx = bytes.getUnsignedByte(offset + 1);
                    visitor.visitLocal(ByteOps.ISTORE, offset, 2, idx,
                                       Type.INT, 0);
                    return 2;
                }
                case ByteOps.LSTORE: {
                    int idx = bytes.getUnsignedByte(offset + 1);
                    visitor.visitLocal(ByteOps.ISTORE, offset, 2, idx,
                                       Type.LONG, 0);
                    return 2;
                }
                case ByteOps.FSTORE: {
                    int idx = bytes.getUnsignedByte(offset + 1);
                    visitor.visitLocal(ByteOps.ISTORE, offset, 2, idx,
                                       Type.FLOAT, 0);
                    return 2;
                }
                case ByteOps.DSTORE: {
                    int idx = bytes.getUnsignedByte(offset + 1);
                    visitor.visitLocal(ByteOps.ISTORE, offset, 2, idx,
                                       Type.DOUBLE, 0);
                    return 2;
                }
                case ByteOps.ASTORE: {
                    int idx = bytes.getUnsignedByte(offset + 1);
                    visitor.visitLocal(ByteOps.ISTORE, offset, 2, idx,
                                       Type.OBJECT, 0);
                    return 2;
                }
                case ByteOps.ISTORE_0:
                case ByteOps.ISTORE_1:
                case ByteOps.ISTORE_2:
                case ByteOps.ISTORE_3: {
                    int idx = opcode - ByteOps.ISTORE_0;
                    visitor.visitLocal(ByteOps.ISTORE, offset, 1, idx,
                                       Type.INT, 0);
                    return 1;
                }
                case ByteOps.LSTORE_0:
                case ByteOps.LSTORE_1:
                case ByteOps.LSTORE_2:
                case ByteOps.LSTORE_3: {
                    int idx = opcode - ByteOps.LSTORE_0;
                    visitor.visitLocal(ByteOps.ISTORE, offset, 1, idx,
                                       Type.LONG, 0);
                    return 1;
                }
                case ByteOps.FSTORE_0:
                case ByteOps.FSTORE_1:
                case ByteOps.FSTORE_2:
                case ByteOps.FSTORE_3: {
                    int idx = opcode - ByteOps.FSTORE_0;
                    visitor.visitLocal(ByteOps.ISTORE, offset, 1, idx,
                                       Type.FLOAT, 0);
                    return 1;
                }
                case ByteOps.DSTORE_0:
                case ByteOps.DSTORE_1:
                case ByteOps.DSTORE_2:
                case ByteOps.DSTORE_3: {
                    int idx = opcode - ByteOps.DSTORE_0;
                    visitor.visitLocal(ByteOps.ISTORE, offset, 1, idx,
                                       Type.DOUBLE, 0);
                    return 1;
                }
                case ByteOps.ASTORE_0:
                case ByteOps.ASTORE_1:
                case ByteOps.ASTORE_2:
                case ByteOps.ASTORE_3: {
                    int idx = opcode - ByteOps.ASTORE_0;
                    visitor.visitLocal(ByteOps.ISTORE, offset, 1, idx,
                                       Type.OBJECT, 0);
                    return 1;
                }
                case ByteOps.IASTORE: {
                    visitor.visitNoArgs(ByteOps.IASTORE, offset, 1, Type.INT);
                    return 1;
                }
                case ByteOps.LASTORE: {
                    visitor.visitNoArgs(ByteOps.IASTORE, offset, 1,
                                        Type.LONG);
                    return 1;
                }
                case ByteOps.FASTORE: {
                    visitor.visitNoArgs(ByteOps.IASTORE, offset, 1,
                                        Type.FLOAT);
                    return 1;
                }
                case ByteOps.DASTORE: {
                    visitor.visitNoArgs(ByteOps.IASTORE, offset, 1,
                                        Type.DOUBLE);
                    return 1;
                }
                case ByteOps.AASTORE: {
                    visitor.visitNoArgs(ByteOps.IASTORE, offset, 1,
                                        Type.OBJECT);
                    return 1;
                }
                case ByteOps.BASTORE: {
                    visitor.visitNoArgs(ByteOps.IASTORE, offset, 1,
                                        Type.BYTE);
                    return 1;
                }
                case ByteOps.CASTORE: {
                    visitor.visitNoArgs(ByteOps.IASTORE, offset, 1,
                                        Type.CHAR);
                    return 1;
                }
                case ByteOps.SASTORE: {
                    visitor.visitNoArgs(ByteOps.IASTORE, offset, 1,
                                        Type.SHORT);
                    return 1;
                }
                case ByteOps.POP:
                case ByteOps.POP2:
                case ByteOps.DUP:
                case ByteOps.DUP_X1:
                case ByteOps.DUP_X2:
                case ByteOps.DUP2:
                case ByteOps.DUP2_X1:
                case ByteOps.DUP2_X2:
                case ByteOps.SWAP: {
                    visitor.visitNoArgs(opcode, offset, 1, Type.VOID);
                    return 1;
                }
                case ByteOps.IADD:
                case ByteOps.ISUB:
                case ByteOps.IMUL:
                case ByteOps.IDIV:
                case ByteOps.IREM:
                case ByteOps.INEG:
                case ByteOps.ISHL:
                case ByteOps.ISHR:
                case ByteOps.IUSHR:
                case ByteOps.IAND:
                case ByteOps.IOR:
                case ByteOps.IXOR: {
                    visitor.visitNoArgs(opcode, offset, 1, Type.INT);
                    return 1;
                }
                case ByteOps.LADD:
                case ByteOps.LSUB:
                case ByteOps.LMUL:
                case ByteOps.LDIV:
                case ByteOps.LREM:
                case ByteOps.LNEG:
                case ByteOps.LSHL:
                case ByteOps.LSHR:
                case ByteOps.LUSHR:
                case ByteOps.LAND:
                case ByteOps.LOR:
                case ByteOps.LXOR: {
                    /*
                     * It's "opcode - 1" because, conveniently enough, all
                     * these long ops are one past the int variants.
                     */
                    visitor.visitNoArgs(opcode - 1, offset, 1, Type.LONG);
                    return 1;
                }
                case ByteOps.FADD:
                case ByteOps.FSUB:
                case ByteOps.FMUL:
                case ByteOps.FDIV:
                case ByteOps.FREM:
                case ByteOps.FNEG: {
                    /*
                     * It's "opcode - 2" because, conveniently enough, all
                     * these float ops are two past the int variants.
                     */
                    visitor.visitNoArgs(opcode - 2, offset, 1, Type.FLOAT);
                    return 1;
                }
                case ByteOps.DADD:
                case ByteOps.DSUB:
                case ByteOps.DMUL:
                case ByteOps.DDIV:
                case ByteOps.DREM:
                case ByteOps.DNEG: {
                    /*
                     * It's "opcode - 3" because, conveniently enough, all
                     * these double ops are three past the int variants.
                     */
                    visitor.visitNoArgs(opcode - 3, offset, 1, Type.DOUBLE);
                    return 1;
                }
                case ByteOps.IINC: {
                    int idx = bytes.getUnsignedByte(offset + 1);
                    int value = bytes.getByte(offset + 2);
                    visitor.visitLocal(opcode, offset, 3, idx,
                                       Type.INT, value);
                    return 3;
                }
                case ByteOps.I2L:
                case ByteOps.F2L:
                case ByteOps.D2L: {
                    visitor.visitNoArgs(opcode, offset, 1, Type.LONG);
                    return 1;
                }
                case ByteOps.I2F:
                case ByteOps.L2F:
                case ByteOps.D2F: {
                    visitor.visitNoArgs(opcode, offset, 1, Type.FLOAT);
                    return 1;
                }
                case ByteOps.I2D:
                case ByteOps.L2D:
                case ByteOps.F2D: {
                    visitor.visitNoArgs(opcode, offset, 1, Type.DOUBLE);
                    return 1;
                }
                case ByteOps.L2I:
                case ByteOps.F2I:
                case ByteOps.D2I:
                case ByteOps.I2B:
                case ByteOps.I2C:
                case ByteOps.I2S:
                case ByteOps.LCMP:
                case ByteOps.FCMPL:
                case ByteOps.FCMPG:
                case ByteOps.DCMPL:
                case ByteOps.DCMPG:
                case ByteOps.ARRAYLENGTH: {
                    visitor.visitNoArgs(opcode, offset, 1, Type.INT);
                    return 1;
                }
                case ByteOps.IFEQ:
                case ByteOps.IFNE:
                case ByteOps.IFLT:
                case ByteOps.IFGE:
                case ByteOps.IFGT:
                case ByteOps.IFLE:
                case ByteOps.IF_ICMPEQ:
                case ByteOps.IF_ICMPNE:
                case ByteOps.IF_ICMPLT:
                case ByteOps.IF_ICMPGE:
                case ByteOps.IF_ICMPGT:
                case ByteOps.IF_ICMPLE:
                case ByteOps.IF_ACMPEQ:
                case ByteOps.IF_ACMPNE:
                case ByteOps.GOTO:
                case ByteOps.JSR:
                case ByteOps.IFNULL:
                case ByteOps.IFNONNULL: {
                    int target = offset + bytes.getShort(offset + 1);
                    visitor.visitBranch(opcode, offset, 3, target);
                    return 3;
                }
                case ByteOps.RET: {
                    int idx = bytes.getUnsignedByte(offset + 1);
                    visitor.visitLocal(opcode, offset, 2, idx,
                                       Type.RETURN_ADDRESS, 0);
                    return 2;
                }
                case ByteOps.TABLESWITCH: {
                    return parseTableswitch(offset, visitor);
                }
                case ByteOps.LOOKUPSWITCH: {
                    return parseLookupswitch(offset, visitor);
                }
                case ByteOps.IRETURN: {
                    visitor.visitNoArgs(ByteOps.IRETURN, offset, 1, Type.INT);
                    return 1;
                }
                case ByteOps.LRETURN: {
                    visitor.visitNoArgs(ByteOps.IRETURN, offset, 1,
                                        Type.LONG);
                    return 1;
                }
                case ByteOps.FRETURN: {
                    visitor.visitNoArgs(ByteOps.IRETURN, offset, 1,
                                        Type.FLOAT);
                    return 1;
                }
                case ByteOps.DRETURN: {
                    visitor.visitNoArgs(ByteOps.IRETURN, offset, 1,
                                        Type.DOUBLE);
                    return 1;
                }
                case ByteOps.ARETURN: {
                    visitor.visitNoArgs(ByteOps.IRETURN, offset, 1,
                                        Type.OBJECT);
                    return 1;
                }
                case ByteOps.RETURN:
                case ByteOps.ATHROW:
                case ByteOps.MONITORENTER:
                case ByteOps.MONITOREXIT: {
                    visitor.visitNoArgs(opcode, offset, 1, Type.VOID);
                    return 1;
                }
                case ByteOps.GETSTATIC:
                case ByteOps.PUTSTATIC:
                case ByteOps.GETFIELD:
                case ByteOps.PUTFIELD:
                case ByteOps.INVOKEVIRTUAL:
                case ByteOps.INVOKESPECIAL:
                case ByteOps.INVOKESTATIC:
                case ByteOps.NEW:
                case ByteOps.ANEWARRAY:
                case ByteOps.CHECKCAST:
                case ByteOps.INSTANCEOF: {
                    int idx = bytes.getUnsignedShort(offset + 1);
                    Constant cst = pool.get(idx);
                    visitor.visitConstant(opcode, offset, 3, cst, 0);
                    return 3;
                }
                case ByteOps.INVOKEINTERFACE: {
                    int idx = bytes.getUnsignedShort(offset + 1);
                    int count = bytes.getUnsignedByte(offset + 3);
                    int expectZero = bytes.getUnsignedByte(offset + 4);
                    Constant cst = pool.get(idx);
                    visitor.visitConstant(opcode, offset, 5, cst,
                                          count | (expectZero << 8));
                    return 5;
                }
                case ByteOps.NEWARRAY: {
                    return parseNewarray(offset, visitor);
                }
                case ByteOps.WIDE: {
                    return parseWide(offset, visitor);
                }
                case ByteOps.MULTIANEWARRAY: {
                    int idx = bytes.getUnsignedShort(offset + 1);
                    int dimensions = bytes.getUnsignedByte(offset + 3);
                    Constant cst = pool.get(idx);
                    visitor.visitConstant(opcode, offset, 4, cst, dimensions);
                    return 4;
                }
                case ByteOps.GOTO_W:
                case ByteOps.JSR_W: {
                    int target = offset + bytes.getInt(offset + 1);
                    int newop =
                        (opcode == ByteOps.GOTO_W) ? ByteOps.GOTO :
                        ByteOps.JSR;
                    visitor.visitBranch(newop, offset, 5, target);
                    return 5;
                }
                default: {
                    visitor.visitInvalid(opcode, offset, 1);
                    return 1;
                }
            }
        } catch (SimException ex) {
            ex.addContext("...at bytecode offset " + Hex.u4(offset));
            throw ex;
        } catch (RuntimeException ex) {
            SimException se = new SimException(ex);
            se.addContext("...at bytecode offset " + Hex.u4(offset));
            throw se;
        }
    }

    /**
     * Helper to deal with <code>tableswitch</code>.
     * 
     * @param offset the offset to the <code>tableswitch</code> opcode itself
     * @param visitor non-null; visitor to use
     * @return instruction length, in bytes
     */
    private int parseTableswitch(int offset, Visitor visitor) {
        int at = (offset + 4) & ~3; // "at" skips the padding.

        // Collect the padding.
        int padding = 0;
        for (int i = offset + 1; i < at; i++) {
            padding = (padding << 8) | bytes.getUnsignedByte(i);
        }

        int defaultTarget = offset + bytes.getInt(at);
        int low = bytes.getInt(at + 4);
        int high = bytes.getInt(at + 8);
        int count = high - low + 1;
        at += 12;

        if (low > high) {
            throw new SimException("low / high inversion");
        }

        SwitchList cases = new SwitchList(count);
        for (int i = 0; i < count; i++) {
            int target = offset + bytes.getInt(at);
            at += 4;
            cases.add(low + i, target);
        }
        cases.setDefaultTarget(defaultTarget);
        cases.removeSuperfluousDefaults();
        cases.setImmutable();

        int length = at - offset;
        visitor.visitSwitch(ByteOps.LOOKUPSWITCH, offset, length, cases,
                            padding);

        return length;
    }

    /**
     * Helper to deal with <code>lookupswitch</code>.
     * 
     * @param offset the offset to the <code>lookupswitch</code> opcode itself
     * @param visitor non-null; visitor to use
     * @return instruction length, in bytes
     */
    private int parseLookupswitch(int offset, Visitor visitor) {
        int at = (offset + 4) & ~3; // "at" skips the padding.

        // Collect the padding.
        int padding = 0;
        for (int i = offset + 1; i < at; i++) {
            padding = (padding << 8) | bytes.getUnsignedByte(i);
        }

        int defaultTarget = offset + bytes.getInt(at);
        int npairs = bytes.getInt(at + 4);
        at += 8;

        SwitchList cases = new SwitchList(npairs);
        for (int i = 0; i < npairs; i++) {
            int match = bytes.getInt(at);
            int target = offset + bytes.getInt(at + 4);
            at += 8;
            cases.add(match, target);
        }
        cases.setDefaultTarget(defaultTarget);
        cases.removeSuperfluousDefaults();
        cases.setImmutable();

        int length = at - offset;
        visitor.visitSwitch(ByteOps.LOOKUPSWITCH, offset, length, cases,
                            padding);

        return length;
    }

    /**
     * Helper to deal with <code>newarray</code>.
     *
     * @param offset the offset to the <code>newarray</code> opcode itself
     * @param visitor non-null; visitor to use
     * @return instruction length, in bytes
     */
    private int parseNewarray(int offset, Visitor visitor) {
        int value = bytes.getUnsignedByte(offset + 1);
        CstType type;
        switch (value) {
            case ByteOps.NEWARRAY_BOOLEAN: {
                type = CstType.BOOLEAN_ARRAY;
                break;
            }
            case ByteOps.NEWARRAY_CHAR: {
                type = CstType.CHAR_ARRAY;
                break;
            }
            case ByteOps.NEWARRAY_DOUBLE: {
                type = CstType.DOUBLE_ARRAY;
                break;
            }
            case ByteOps.NEWARRAY_FLOAT: {
                type = CstType.FLOAT_ARRAY;
                break;
            }
            case ByteOps.NEWARRAY_BYTE: {
                type = CstType.BYTE_ARRAY;
                break;
            }
            case ByteOps.NEWARRAY_SHORT: {
                type = CstType.SHORT_ARRAY;
                break;
            }
            case ByteOps.NEWARRAY_INT: {
                type = CstType.INT_ARRAY;
                break;
            }
            case ByteOps.NEWARRAY_LONG: {
                type = CstType.LONG_ARRAY;
                break;
            }
            default: {
                throw new SimException("bad newarray code " +
                        Hex.u1(value));
            }
        }

        // Revisit the previous bytecode to find out the length of the array
        int previousOffset = visitor.getPreviousOffset();
        ConstantParserVisitor constantVisitor = new ConstantParserVisitor();
        int arrayLength = 0;

        /*
         * For visitors that don't record the previous offset, -1 will be
         * seen here
         */
        if (previousOffset >= 0) {
            parseInstruction(previousOffset, constantVisitor);
            if (constantVisitor.cst instanceof CstInteger &&
                    constantVisitor.length + previousOffset == offset) {
                arrayLength = constantVisitor.value;

            }
        }

        /*
         * Try to match the array initialization idiom. For example, if the
         * subsequent code is initializing an int array, we are expecting the
         * following pattern repeatedly:
         *  dup
         *  push index
         *  push value
         *  *astore
         *
         * where the index value will be incrimented sequentially from 0 up.
         */
        int nInit = 0;
        int curOffset = offset+2;
        int lastOffset = curOffset;
        ArrayList<Constant> initVals = new ArrayList<Constant>();

        if (arrayLength != 0) {
            while (true) {
                boolean punt = false;

                // First check if the next bytecode is dup
                int nextByte = bytes.getUnsignedByte(curOffset++);
                if (nextByte != ByteOps.DUP)
                    break;

                // Next check if the expected array index is pushed to the stack
                parseInstruction(curOffset, constantVisitor);
                if (constantVisitor.length == 0 ||
                        !(constantVisitor.cst instanceof CstInteger) ||
                        constantVisitor.value != nInit)
                    break;

                // Next, fetch the init value and record it
                curOffset += constantVisitor.length;

                // Next find out what kind of constant is pushed onto the stack
                parseInstruction(curOffset, constantVisitor);
                if (constantVisitor.length == 0 ||
                        !(constantVisitor.cst instanceof CstLiteralBits))
                    break;

                curOffset += constantVisitor.length;
                initVals.add(constantVisitor.cst);

                nextByte = bytes.getUnsignedByte(curOffset++);
                // Now, check if the value is stored to the array properly
                switch (value) {
                    case ByteOps.NEWARRAY_BYTE:
                    case ByteOps.NEWARRAY_BOOLEAN: {
                        if (nextByte != ByteOps.BASTORE) {
                            punt = true;
                        }
                        break;
                    }
                    case ByteOps.NEWARRAY_CHAR: {
                        if (nextByte != ByteOps.CASTORE) {
                            punt = true;
                        }
                        break;
                    }
                    case ByteOps.NEWARRAY_DOUBLE: {
                        if (nextByte != ByteOps.DASTORE) {
                            punt = true;
                        }
                        break;
                    }
                    case ByteOps.NEWARRAY_FLOAT: {
                        if (nextByte != ByteOps.FASTORE) {
                            punt = true;
                        }
                        break;
                    }
                    case ByteOps.NEWARRAY_SHORT: {
                        if (nextByte != ByteOps.SASTORE) {
                            punt = true;
                        }
                        break;
                    }
                    case ByteOps.NEWARRAY_INT: {
                        if (nextByte != ByteOps.IASTORE) {
                            punt = true;
                        }
                        break;
                    }
                    case ByteOps.NEWARRAY_LONG: {
                        if (nextByte != ByteOps.LASTORE) {
                            punt = true;
                        }
                        break;
                    }
                    default:
                        punt = true;
                        break;
                }
                if (punt) {
                    break;
                }
                lastOffset = curOffset;
                nInit++;
            }
        }

        /*
         * For singleton arrays it is still more economical to
         * generate the aput.
         */
        if (nInit < 2 || nInit != arrayLength) {
            visitor.visitNewarray(offset, 2, type, null);
            return 2;
        } else {
            visitor.visitNewarray(offset, lastOffset - offset, type, initVals);
            return lastOffset - offset;
        }
     }

    
    /**
     * Helper to deal with <code>wide</code>.
     * 
     * @param offset the offset to the <code>wide</code> opcode itself
     * @param visitor non-null; visitor to use
     * @return instruction length, in bytes
     */
    private int parseWide(int offset, Visitor visitor) {
        int opcode = bytes.getUnsignedByte(offset + 1);
        int idx = bytes.getUnsignedShort(offset + 2);
        switch (opcode) {
            case ByteOps.ILOAD: {
                visitor.visitLocal(ByteOps.ILOAD, offset, 4, idx,
                                   Type.INT, 0);
                return 4;
            }
            case ByteOps.LLOAD: {
                visitor.visitLocal(ByteOps.ILOAD, offset, 4, idx,
                                   Type.LONG, 0);
                return 4;
            }
            case ByteOps.FLOAD: {
                visitor.visitLocal(ByteOps.ILOAD, offset, 4, idx,
                                   Type.FLOAT, 0);
                return 4;
            }
            case ByteOps.DLOAD: {
                visitor.visitLocal(ByteOps.ILOAD, offset, 4, idx,
                                   Type.DOUBLE, 0);
                return 4;
            }
            case ByteOps.ALOAD: {
                visitor.visitLocal(ByteOps.ILOAD, offset, 4, idx,
                                   Type.OBJECT, 0);
                return 4;
            }
            case ByteOps.ISTORE: {
                visitor.visitLocal(ByteOps.ISTORE, offset, 4, idx,
                                   Type.INT, 0);
                return 4;
            }
            case ByteOps.LSTORE: {
                visitor.visitLocal(ByteOps.ISTORE, offset, 4, idx,
                                   Type.LONG, 0);
                return 4;
            }
            case ByteOps.FSTORE: {
                visitor.visitLocal(ByteOps.ISTORE, offset, 4, idx,
                                   Type.FLOAT, 0);
                return 4;
            }
            case ByteOps.DSTORE: {
                visitor.visitLocal(ByteOps.ISTORE, offset, 4, idx,
                                   Type.DOUBLE, 0);
                return 4;
            }
            case ByteOps.ASTORE: {
                visitor.visitLocal(ByteOps.ISTORE, offset, 4, idx,
                                   Type.OBJECT, 0);
                return 4;
            }
            case ByteOps.RET: {
                visitor.visitLocal(opcode, offset, 4, idx,
                                   Type.RETURN_ADDRESS, 0);
                return 4;
            }
            case ByteOps.IINC: {
                int value = bytes.getShort(offset + 4);
                visitor.visitLocal(opcode, offset, 6, idx,
                                   Type.INT, value);
                return 6;
            }
            default: {
                visitor.visitInvalid(ByteOps.WIDE, offset, 1);
                return 1;
            }
        }
    }

    /**
     * Instruction visitor interface.
     */
    public interface Visitor {
        /**
         * Visits an invalid instruction.
         * 
         * @param opcode the opcode
         * @param offset offset to the instruction
         * @param length length of the instruction, in bytes
         */
        public void visitInvalid(int opcode, int offset, int length);

        /**
         * Visits an instruction which has no inline arguments
         * (implicit or explicit).
         * 
         * @param opcode the opcode
         * @param offset offset to the instruction
         * @param length length of the instruction, in bytes
         * @param type non-null; type the instruction operates on
         */
        public void visitNoArgs(int opcode, int offset, int length,
                Type type);

        /**
         * Visits an instruction which has a local variable index argument.
         * 
         * @param opcode the opcode
         * @param offset offset to the instruction
         * @param length length of the instruction, in bytes
         * @param idx the local variable index
         * @param type non-null; the type of the accessed value
         * @param value additional literal integer argument, if salient (i.e.,
         * for <code>iinc</code>)
         */
        public void visitLocal(int opcode, int offset, int length,
                int idx, Type type, int value);

        /**
         * Visits an instruction which has a (possibly synthetic)
         * constant argument, and possibly also an
         * additional literal integer argument. In the case of
         * <code>multianewarray</code>, the argument is the count of
         * dimensions. In the case of <code>invokeinterface</code>,
         * the argument is the parameter count or'ed with the
         * should-be-zero value left-shifted by 8. In the case of entries
         * of type <code>int</code>, the <code>value</code> field always
         * holds the raw value (for convenience of clients).
         * 
         * <p><b>Note:</b> In order to avoid giving it a barely-useful
         * visitor all its own, <code>newarray</code> also uses this
         * form, passing <code>value</code> as the array type code and
         * <code>cst</code> as a {@link CstType} instance
         * corresponding to the array type.</p>
         * 
         * @param opcode the opcode
         * @param offset offset to the instruction
         * @param length length of the instruction, in bytes
         * @param cst non-null; the constant
         * @param value additional literal integer argument, if salient
         * (ignore if not)
         */
        public void visitConstant(int opcode, int offset, int length,
                Constant cst, int value);

        /**
         * Visits an instruction which has a branch target argument.
         * 
         * @param opcode the opcode
         * @param offset offset to the instruction
         * @param length length of the instruction, in bytes
         * @param target the absolute (not relative) branch target
         */
        public void visitBranch(int opcode, int offset, int length,
                int target);

        /**
         * Visits a switch instruction.
         * 
         * @param opcode the opcode
         * @param offset offset to the instruction
         * @param length length of the instruction, in bytes
         * @param cases non-null; list of (value, target) pairs, plus the
         * default target
         * @param padding the bytes found in the padding area (if any),
         * packed
         */
        public void visitSwitch(int opcode, int offset, int length,
                SwitchList cases, int padding);

        /**
         * Visits a newarray instruction.
         *
         * @param offset   offset to the instruction
         * @param length   length of the instruction, in bytes
         * @param type non-null; the type of the array
         * @param initVals non-null; list of bytecode offsets for init values
         */
        public void visitNewarray(int offset, int length, CstType type,
                ArrayList<Constant> initVals);

        /**
         * Set previous bytecode offset
         * @param offset    offset of the previous fully parsed bytecode
         */
        public void setPreviousOffset(int offset);

        /**
         * Get previous bytecode offset
         * @return return the recored offset of the previous bytecode
         */
        public int getPreviousOffset();
    }

    /**
     * Base implementation of {@link Visitor}, which has empty method
     * bodies for all methods.
     */
    public static class BaseVisitor implements Visitor {

        /** offset of the previously parsed bytecode */
        private int previousOffset;

        BaseVisitor() {
            previousOffset = -1;
        }

        /** {@inheritDoc} */
        public void visitInvalid(int opcode, int offset, int length) {
            // This space intentionally left blank.
        }

        /** {@inheritDoc} */
        public void visitNoArgs(int opcode, int offset, int length,
                Type type) {
            // This space intentionally left blank.
        }

        /** {@inheritDoc} */
        public void visitLocal(int opcode, int offset, int length,
                int idx, Type type, int value) {
            // This space intentionally left blank.
        }

        /** {@inheritDoc} */
        public void visitConstant(int opcode, int offset, int length,
                Constant cst, int value) {
            // This space intentionally left blank.
        }

        /** {@inheritDoc} */
        public void visitBranch(int opcode, int offset, int length,
                int target) {
            // This space intentionally left blank.
        }

        /** {@inheritDoc} */
        public void visitSwitch(int opcode, int offset, int length,
                SwitchList cases, int padding) {
            // This space intentionally left blank.
        }

        /** {@inheritDoc} */
        public void visitNewarray(int offset, int length, CstType type,
                ArrayList<Constant> initValues) {
            // This space intentionally left blank.
        }

        /** {@inheritDoc} */
        public void setPreviousOffset(int offset) {
            previousOffset = offset;
        }

        /** {@inheritDoc} */
        public int getPreviousOffset() {
            return previousOffset;
        }
    }
    
    /**
     * Base implementation of {@link Visitor}, which has empty method
     * bodies for all methods.
     */
    class ConstantParserVisitor extends BaseVisitor {
        Constant cst;
        int length;
        int value;

        /** Empty constructor */
        ConstantParserVisitor() {
        }

        private void clear() {
            length = 0;
        }

        /** {@inheritDoc} */
        public void visitInvalid(int opcode, int offset, int length) {
            clear();
        }

        /** {@inheritDoc} */
        public void visitNoArgs(int opcode, int offset, int length,
                Type type) {
            clear();
        }

        /** {@inheritDoc} */
        public void visitLocal(int opcode, int offset, int length,
                int idx, Type type, int value) {
            clear();
        }

        /** {@inheritDoc} */
        public void visitConstant(int opcode, int offset, int length,
                Constant cst, int value) {
            this.cst = cst;
            this.length = length;
            this.value = value;
        }

        /** {@inheritDoc} */
        public void visitBranch(int opcode, int offset, int length,
                int target) {
            clear();
        }

        /** {@inheritDoc} */
        public void visitSwitch(int opcode, int offset, int length,
                SwitchList cases, int padding) {
            clear();
        }

        /** {@inheritDoc} */
        public void visitNewarray(int offset, int length, CstType type,
                ArrayList<Constant> initVals) {
            clear();
        }

        /** {@inheritDoc} */
        public void setPreviousOffset(int offset) {
            // Intentionally left empty
        }

        /** {@inheritDoc} */
        public int getPreviousOffset() {
            // Intentionally left empty
            return -1;
        }
    }
}
