added computeMaxStack() in CodeAttribute.

git-svn-id: http://anonsvn.jboss.org/repos/javassist/trunk@105 30ef5769-5b8d-40dd-aea6-55b5d6557bb3

3 files changed, 256 insertions, 1 deletions

diff --git a/src/main/javassist/CtClass.java b/src/main/javassist/CtClass.java
index 98775f47..001269a8 100644
--- a/src/main/javassist/CtClass.java
+++ b/src/main/javassist/CtClass.java
@@ -35,7 +35,7 @@ public abstract class CtClass {
     /**
      * The version number of this release.
      */
-    public static final String version = "3.0 RC0";
+    public static final String version = "3.0 beta";
 
     /**
      * Prints the version number and the copyright notice.
diff --git a/src/main/javassist/bytecode/CodeAnalyzer.java b/src/main/javassist/bytecode/CodeAnalyzer.java
new file mode 100644
index 00000000..4f034ae5
--- /dev/null
+++ b/src/main/javassist/bytecode/CodeAnalyzer.java
@@ -0,0 +1,243 @@
+/*
+ * Javassist, a Java-bytecode translator toolkit.
+ * Copyright (C) 1999-2004 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.
+ *
+ * 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];
+        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))
+                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)
+        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);
+                if (stackDepth == 2)    // stackDepth is 1 if empty
+                    return false;
+                else
+                    throw new BadBytecode(
+                        "sorry, cannot compute this data flow due to JSR");
+            case RET :
+                if (stackDepth == 1)    // stackDepth is 1 if empty
+                    return true;
+                else
+                    throw new BadBytecode(
+                        "sorry, cannot compute this data flow due to RET");
+            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 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);
+    }
+}
diff --git a/src/main/javassist/bytecode/CodeAttribute.java b/src/main/javassist/bytecode/CodeAttribute.java
index 4e170d60..ec1f9a58 100644
--- a/src/main/javassist/bytecode/CodeAttribute.java
+++ b/src/main/javassist/bytecode/CodeAttribute.java
@@ -220,6 +220,18 @@ public class CodeAttribute extends AttributeInfo implements Opcode {
     }
 
     /**
+     * Computes the maximum stack size and sets <code>max_stack</code>
+     * to the computed size.
+     *
+     * @throws BadBytecode      if this method fails in computing.
+     * @return the newly computed value of <code>max_stack</code>
+     */
+    public int computeMaxStack() throws BadBytecode {
+        maxStack = new CodeAnalyzer(this).computeMaxStack();
+        return maxStack;
+    }
+
+    /**
      * Returns <code>max_locals</code>.
      */
     public int getMaxLocals() {