/*
 * Javassist, a Java-bytecode translator toolkit.
 * Copyright (C) 1999- Shigeru Chiba. All Rights Reserved.
 *
 * The contents of this file are subject to the Mozilla Public License Version
 * 1.1 (the "License"); you may not use this file except in compliance with
 * the License.  Alternatively, the contents of this file may be used under
 * the terms of the GNU Lesser General Public License Version 2.1 or later,
 * or the Apache License Version 2.0.
 *
 * Software distributed under the License is distributed on an "AS IS" basis,
 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
 * for the specific language governing rights and limitations under the
 * License.
 */

package javassist.bytecode;

/**
 * Utility for computing <code>max_stack</code>.
 */
class CodeAnalyzer implements Opcode {
    private ConstPool constPool;
    private CodeAttribute codeAttr;

    public CodeAnalyzer(CodeAttribute ca) {
        codeAttr = ca;
        constPool = ca.getConstPool();
    }

    public int computeMaxStack()
        throws BadBytecode
    {
        /* d = stack[i]
         * d == 0: not visited
         * d > 0: the depth is d - 1 after executing the bytecode at i.
         * d < 0: not visited. the initial depth (before execution) is 1 - d.
         */
        CodeIterator ci = codeAttr.iterator();
        int length = ci.getCodeLength();
        int[] stack = new int[length];
        constPool = codeAttr.getConstPool();
        initStack(stack, codeAttr);
        boolean repeat;
        do {
            repeat = false;
            for (int i = 0; i < length; ++i)
                if (stack[i] < 0) {
                    repeat = true;
                    visitBytecode(ci, stack, i);
                }
        } while (repeat);

        int maxStack = 1;
        for (int i = 0; i < length; ++i)
            if (stack[i] > maxStack)
                maxStack = stack[i];

        return maxStack - 1;    // the base is 1.
    }

    private void initStack(int[] stack, CodeAttribute ca) {
        stack[0] = -1;
        ExceptionTable et = ca.getExceptionTable();
        if (et != null) {
            int size = et.size();
            for (int i = 0; i < size; ++i)
                stack[et.handlerPc(i)] = -2;    // an exception is on stack
        }
    }

    private void visitBytecode(CodeIterator ci, int[] stack, int index)
        throws BadBytecode
    {
        int codeLength = stack.length;
        ci.move(index);
        int stackDepth = -stack[index];
        int[] jsrDepth = new int[1];
        jsrDepth[0] = -1;
        while (ci.hasNext()) {
            index = ci.next();
            stack[index] = stackDepth;
            int op = ci.byteAt(index);
            stackDepth = visitInst(op, ci, index, stackDepth);
            if (stackDepth < 1)
                throw new BadBytecode("stack underflow at " + index);

            if (processBranch(op, ci, index, codeLength, stack, stackDepth, jsrDepth))
                break;

            if (isEnd(op))     // return, ireturn, athrow, ...
                break;

            if (op == JSR || op == JSR_W)
                --stackDepth;
        }
    }

    private boolean processBranch(int opcode, CodeIterator ci, int index,
                                  int codeLength, int[] stack, int stackDepth, int[] jsrDepth)
        throws BadBytecode
    {
        if ((IFEQ <= opcode && opcode <= IF_ACMPNE)
                            || opcode == IFNULL || opcode == IFNONNULL) {
            int target = index + ci.s16bitAt(index + 1);
            checkTarget(index, target, codeLength, stack, stackDepth);
        }
        else {
            int target, index2;
            switch (opcode) {
            case GOTO :
                target = index + ci.s16bitAt(index + 1);
                checkTarget(index, target, codeLength, stack, stackDepth);
                return true;
            case GOTO_W :
                target = index + ci.s32bitAt(index + 1);
                checkTarget(index, target, codeLength, stack, stackDepth);
                return true;
            case JSR :
            case JSR_W :
                if (opcode == JSR)
                    target = index + ci.s16bitAt(index + 1);
                else
                    target = index + ci.s32bitAt(index + 1);

                checkTarget(index, target, codeLength, stack, stackDepth);
                /*
                 * It is unknown which RET comes back to this JSR.
                 * So we assume that if the stack depth at one JSR instruction
                 * is N, then it is also N at other JSRs and N - 1 at all RET
                 * instructions.  Note that STACK_GROW[JSR] is 1 since it pushes
                 * a return address on the operand stack.
                 */
                if (jsrDepth[0] < 0) {
                    jsrDepth[0] = stackDepth;
                    return false;
                }
                else if (stackDepth == jsrDepth[0])
                    return false;
                else
                    throw new BadBytecode(
                        "sorry, cannot compute this data flow due to JSR: "
                            + stackDepth + "," + jsrDepth[0]);
            case RET :
                if (jsrDepth[0] < 0) {
                    jsrDepth[0] = stackDepth + 1;
                    return false;
                }
                else if (stackDepth + 1 == jsrDepth[0])
                    return true;
                else
                    throw new BadBytecode(
                        "sorry, cannot compute this data flow due to RET: "
                            + stackDepth + "," + jsrDepth[0]);
            case LOOKUPSWITCH :
            case TABLESWITCH :
                index2 = (index & ~3) + 4;
                target = index + ci.s32bitAt(index2);
                checkTarget(index, target, codeLength, stack, stackDepth);
                if (opcode == LOOKUPSWITCH) {
                    int npairs = ci.s32bitAt(index2 + 4);
                    index2 += 12;
                    for (int i = 0; i < npairs; ++i) {
                        target = index + ci.s32bitAt(index2);
                        checkTarget(index, target, codeLength,
                                    stack, stackDepth);
                        index2 += 8;
                    }
                }
                else {
                    int low = ci.s32bitAt(index2 + 4);
                    int high = ci.s32bitAt(index2 + 8);
                    int n = high - low + 1;
                    index2 += 12;
                    for (int i = 0; i < n; ++i) {
                        target = index + ci.s32bitAt(index2);
                        checkTarget(index, target, codeLength,
                                    stack, stackDepth);
                        index2 += 4;
                    }
                }

                return true;    // always branch.
            }
        }

        return false;   // may not branch.
    }

    private void checkTarget(int opIndex, int target, int codeLength,
                             int[] stack, int stackDepth)
        throws BadBytecode
    {
        if (target < 0 || codeLength <= target)
            throw new BadBytecode("bad branch offset at " + opIndex);

        int d = stack[target];
        if (d == 0)
            stack[target] = -stackDepth;
        else if (d != stackDepth && d != -stackDepth)
            throw new BadBytecode("verification error (" + stackDepth +
                                  "," + d + ") at " + opIndex);
    }
                             
    private static boolean isEnd(int opcode) {
        return (IRETURN <= opcode && opcode <= RETURN) || opcode == ATHROW; 
    }

    /**
     * Visits an instruction.
     */
    private int visitInst(int op, CodeIterator ci, int index, int stack)
        throws BadBytecode
    {
        String desc;
        switch (op) {
        case GETFIELD :
            stack += getFieldSize(ci, index) - 1;
            break;
        case PUTFIELD :
            stack -= getFieldSize(ci, index) + 1;
            break;
        case GETSTATIC :
            stack += getFieldSize(ci, index);
            break;
        case PUTSTATIC :
            stack -= getFieldSize(ci, index);
            break;
        case INVOKEVIRTUAL :
        case INVOKESPECIAL :
            desc = constPool.getMethodrefType(ci.u16bitAt(index + 1));
            stack += Descriptor.dataSize(desc) - 1;
            break;
        case INVOKESTATIC :
            desc = constPool.getMethodrefType(ci.u16bitAt(index + 1));
            stack += Descriptor.dataSize(desc);
            break;
        case INVOKEINTERFACE :
            desc = constPool.getInterfaceMethodrefType(
                                            ci.u16bitAt(index + 1));
            stack += Descriptor.dataSize(desc) - 1;
            break;
        case INVOKEDYNAMIC :
            desc = constPool.getInvokeDynamicType(ci.u16bitAt(index + 1));
            stack += Descriptor.dataSize(desc);     // assume CosntPool#REF_invokeStatic
            break;
        case ATHROW :
            stack = 1;      // the stack becomes empty (1 means no values).
            break;
        case MULTIANEWARRAY :
            stack += 1 - ci.byteAt(index + 3);
            break;
        case WIDE :
            op = ci.byteAt(index + 1);
            // don't break here.
        default :
            stack += STACK_GROW[op];
        }

        return stack;
    }

    private int getFieldSize(CodeIterator ci, int index) {
        String desc = constPool.getFieldrefType(ci.u16bitAt(index + 1));
        return Descriptor.dataSize(desc);
    }
}