fixes a bug of stackmap generation. The bug was reported here: https://github.com/jboss-javassist/javassist/issues/83

6 files changed, 342 insertions, 118 deletions

diff --git a/Readme.html b/Readme.html
index 3015f7ad..7e16e186 100644
--- a/Readme.html
+++ b/Readme.html
@@ -286,6 +286,7 @@ see javassist.Dump.
 <li>JIRA JASSIST-244, 245, 248, 250, 255, 256, 259, 262.
 <li><code>javassist.tools.Callback</code> was modified to be Java 1.4 compatible.
 The parameter type of <code>Callback#result()</code> was changed.
+<li>The algorithm for generating a stack-map table was modified to fix github issue #83. 
 </ul>
 </p>
 
diff --git a/src/main/javassist/bytecode/stackmap/TypeData.java b/src/main/javassist/bytecode/stackmap/TypeData.java
index b83c9f69..206fd52a 100644
--- a/src/main/javassist/bytecode/stackmap/TypeData.java
+++ b/src/main/javassist/bytecode/stackmap/TypeData.java
@@ -78,7 +78,17 @@ public abstract class TypeData {
     public abstract String getName();
     public abstract void setType(String s, ClassPool cp) throws BadBytecode;
 
-    // depth-first search
+    /**
+     * @param dim		array dimension.  It may be negative.
+     */
+    public abstract TypeData getArrayType(int dim) throws NotFoundException;
+
+    /**
+     * Depth-first search by Tarjan's algorithm
+     *
+     * @param order			a node stack in the order in which nodes are visited.
+     * @param index			the index used by the algorithm.
+     */
     public int dfs(ArrayList order, int index, ClassPool cp)
         throws NotFoundException
     {
@@ -89,32 +99,42 @@ public abstract class TypeData {
      * Returns this if it is a TypeVar or a TypeVar that this
      * type depends on.  Otherwise, this method returns null.
      * It is used by dfs().
+     *
+     * @param dim		dimension
      */
-    protected TypeVar toTypeVar() { return null; }
+    protected TypeVar toTypeVar(int dim) { return null; }
 
     // see UninitTypeVar and UninitData
     public void constructorCalled(int offset) {}
 
+    public String toString() {
+        return super.toString() + "(" + toString2(new HashSet()) + ")";
+    }
+
+    abstract String toString2(HashSet set);
+
     /**
      * Primitive types.
      */
     protected static class BasicType extends TypeData {
         private String name;
         private int typeTag;
+        private char decodedName;
 
-        public BasicType(String type, int tag) {
+        public BasicType(String type, int tag, char decoded) {
             name = type;
             typeTag = tag;
+            decodedName = decoded;
         }
 
         public int getTypeTag() { return typeTag; }
         public int getTypeData(ConstPool cp) { return 0; }
 
         public TypeData join() {
-        	if (this == TypeTag.TOP)
-        		return this;
-        	else
-        		return super.join();
+            if (this == TypeTag.TOP)
+                return this;
+            else
+                return super.join();
         }
 
         public BasicType isBasicType() { return this; }
@@ -130,11 +150,33 @@ public abstract class TypeData {
             return name;
         }
 
+        public char getDecodedName() { return decodedName; }
+
         public void setType(String s, ClassPool cp) throws BadBytecode {
             throw new BadBytecode("conflict: " + name + " and " + s);
         }
 
-        public String toString() { return name; }
+        /**
+         * @param dim		array dimension.  It may be negative.
+         */
+        public TypeData getArrayType(int dim) throws NotFoundException {
+            if (this == TypeTag.TOP)
+                return this;
+            else if (dim < 0)
+                throw new NotFoundException("no element type: " + name);
+            else if (dim == 0)
+                return this;
+            else {
+                char[] name = new char[dim + 1];
+                for (int i = 0; i < dim; i++)
+                    name[i] = '[';
+
+                name[dim] = decodedName;
+                return new ClassName(new String(name));
+            }
+        }
+
+        String toString2(HashSet set) { return name; }
     }
 
     // a type variable
@@ -206,9 +248,9 @@ public abstract class TypeData {
         }
 
         public void merge(TypeData t) {
-        	lowers.add(t);
-        	if (t instanceof TypeVar)
-        	    ((TypeVar)t).usedBy.add(this);
+            lowers.add(t);
+            if (t instanceof TypeVar)
+                ((TypeVar)t).usedBy.add(this);
         }
 
         public int getTypeTag() {
@@ -235,46 +277,68 @@ public abstract class TypeData {
             uppers.add(typeName);
         }
 
-        protected TypeVar toTypeVar() { return this; }
-
         private int visited = 0;
         private int smallest = 0;
         private boolean inList = false;
+        private int dimension = 0;
+
+        protected TypeVar toTypeVar(int dim) {
+            dimension = dim;
+            return this;
+        }
+
+        /* When fixTypes() is called, getName() will return the correct
+         * (i.e. fixed) type name.
+         */
+        public TypeData getArrayType(int dim) throws NotFoundException {
+            if (dim == 0)
+                return this;
+            else {
+                BasicType bt = isBasicType();
+                if (bt == null)
+                    if (isNullType())
+                        return new NullType();
+                    else
+                        return new ClassName(getName()).getArrayType(dim);
+                else
+                    return bt.getArrayType(dim);
+            }
+        }
 
         // depth-first serach
         public int dfs(ArrayList preOrder, int index, ClassPool cp) throws NotFoundException {
-        	if (visited > 0)
-        		return index;		// MapMaker.make() may call an already visited node.
-
-        	visited = smallest = ++index;
-        	preOrder.add(this);
-        	inList = true;
-        	int n = lowers.size();
-        	for (int i = 0; i < n; i++) {
-        		TypeVar child = ((TypeData)lowers.get(i)).toTypeVar();
-        		if (child != null)
-        			if (child.visited == 0) {
-        				index = child.dfs(preOrder, index, cp);
-        				if (child.smallest < smallest)
-        					smallest = child.smallest;
-        			}
-        			else if (child.inList)
-        				if (child.visited < smallest)
-        					smallest = child.visited;
-        	}
-
-        	if (visited == smallest) {
+            if (visited > 0)
+                return index;		// MapMaker.make() may call an already visited node.
+
+            visited = smallest = ++index;
+            preOrder.add(this);
+            inList = true;
+            int n = lowers.size();
+            for (int i = 0; i < n; i++) {
+                TypeVar child = ((TypeData)lowers.get(i)).toTypeVar(dimension);
+                if (child != null)
+                    if (child.visited == 0) {
+                        index = child.dfs(preOrder, index, cp);
+                        if (child.smallest < smallest)
+                            smallest = child.smallest;
+                    }
+                    else if (child.inList)
+                        if (child.visited < smallest)
+                            smallest = child.visited;
+            }
+
+            if (visited == smallest) {
                 ArrayList scc = new ArrayList();    // strongly connected component
-        		TypeVar cv;
-        		do {
-        			cv = (TypeVar)preOrder.remove(preOrder.size() - 1);
-        			cv.inList = false;
-        			scc.add(cv);
-        		} while (cv != this);
-        		fixTypes(scc, cp);
-        	}
+                TypeVar cv;
+                do {
+                    cv = (TypeVar)preOrder.remove(preOrder.size() - 1);
+                    cv.inList = false;
+                    scc.add(cv);
+                } while (cv != this);
+                fixTypes(scc, cp);
+            }
 
-        	return index;
+            return index;
         }
 
         private void fixTypes(ArrayList scc, ClassPool cp) throws NotFoundException {
@@ -283,10 +347,12 @@ public abstract class TypeData {
             TypeData kind = null;
             int size = scc.size();
             for (int i = 0; i < size; i++) {
-                ArrayList tds = ((TypeVar)scc.get(i)).lowers;
+                TypeVar tvar = (TypeVar)scc.get(i);
+                ArrayList tds = tvar.lowers;
                 int size2 = tds.size();
                 for (int j = 0; j < size2; j++) {
-                    TypeData d = (TypeData)tds.get(j);
+                    TypeData td = (TypeData)tds.get(j);
+                    TypeData d = td.getArrayType(tvar.dimension);
                     BasicType bt = d.isBasicType();
                     if (kind == null) {
                         if (bt == null) {
@@ -305,12 +371,11 @@ public abstract class TypeData {
                         }
                     }
                     else {
-                        if ((bt == null && isBasicType)
-                            || (bt != null && kind != bt)) {
+                        if ((bt == null && isBasicType) || (bt != null && kind != bt)) {
                             isBasicType = true;
                             kind = TypeTag.TOP;
                             break;
-                        }
+                         }
                     }
 
                     if (bt == null && !d.isNullType())
@@ -319,19 +384,26 @@ public abstract class TypeData {
             }
 
             if (isBasicType) {
-                is2WordType = kind.is2WordType();
-                for (int i = 0; i < size; i++) {
-                    TypeVar cv = (TypeVar)scc.get(i);
-                    cv.lowers.clear();
-                    cv.lowers.add(kind);
-                    cv.is2WordType = kind.is2WordType();
-                }
+                is2WordType = kind.is2WordType();	// necessary?
+                fixTypes1(scc, kind);
             }
             else {
                 String typeName = fixTypes2(scc, lowersSet, cp);
-                for (int i = 0; i < size; i++) {
-                    TypeVar cv = (TypeVar)scc.get(i);
-                    cv.fixedType = typeName;
+                fixTypes1(scc, new ClassName(typeName));
+            }
+        }
+
+        private void fixTypes1(ArrayList scc, TypeData kind) throws NotFoundException {
+            int size = scc.size();
+            for (int i = 0; i < size; i++) {
+                TypeVar cv = (TypeVar)scc.get(i);
+                TypeData kind2 = kind.getArrayType(-cv.dimension);
+                if (kind2.isBasicType() == null)
+                    cv.fixedType = kind2.getName();
+                else {
+                    cv.lowers.clear();
+                    cv.lowers.add(kind2);
+                    cv.is2WordType = kind2.is2WordType();
                 }
             }
         }
@@ -343,17 +415,17 @@ public abstract class TypeData {
             else if (lowersSet.size() == 1)
                 return (String)it.next(); 
             else {
-            	CtClass cc = cp.get((String)it.next());
-            	while (it.hasNext())
-            		cc = commonSuperClassEx(cc, cp.get((String)it.next()));
+                CtClass cc = cp.get((String)it.next());
+                while (it.hasNext())
+                    cc = commonSuperClassEx(cc, cp.get((String)it.next()));
 
-            	if (cc.getSuperclass() == null || isObjectArray(cc))
-            	    cc = fixByUppers(scc, cp, new HashSet(), cc);
+                if (cc.getSuperclass() == null || isObjectArray(cc))
+                    cc = fixByUppers(scc, cp, new HashSet(), cc);
 
-            	if (cc.isArray())
-            	    return Descriptor.toJvmName(cc);
-            	else
-            	    return cc.getName();
+                if (cc.isArray())
+                    return Descriptor.toJvmName(cc);
+                else
+                    return cc.getName();
             }
         }
 
@@ -387,6 +459,18 @@ public abstract class TypeData {
 
             return type;
         }
+
+        String toString2(HashSet hash) {
+            hash.add(this);
+            if (lowers.size() > 0) {
+                TypeData e = (TypeData)lowers.get(0);
+                if (e != null && !hash.contains(e)) {
+                    return e.toString2(hash);
+                }
+            }
+
+            return "?";
+        }
     }
 
     /**
@@ -522,14 +606,14 @@ public abstract class TypeData {
         }
 
         public void merge(TypeData t) {
-        	try {
-        	    if (!t.isNullType())
-        	        element.merge(ArrayElement.make(t));
-        	}
-        	catch (BadBytecode e) {
-        		// never happens
-        		throw new RuntimeException("fatal: " + e);
-        	}
+            try {
+                if (!t.isNullType())
+                    element.merge(ArrayElement.make(t));
+            }
+            catch (BadBytecode e) {
+                // never happens
+                throw new RuntimeException("fatal: " + e);
+            }
         }
 
         public String getName() {
@@ -555,10 +639,18 @@ public abstract class TypeData {
             element.setType(ArrayElement.typeName(s), cp);
         }
 
-        protected TypeVar toTypeVar() { return element.toTypeVar(); }
+        protected TypeVar toTypeVar(int dim) { return element.toTypeVar(dim + 1); }
+
+        public TypeData getArrayType(int dim) throws NotFoundException {
+            return element.getArrayType(dim + 1);
+        }
 
         public int dfs(ArrayList order, int index, ClassPool cp) throws NotFoundException {
-        	return element.dfs(order, index, cp);
+            return element.dfs(order, index, cp);
+        }
+
+        String toString2(HashSet set) {
+            return "[" + element.toString2(set);
         }
     }
 
@@ -585,14 +677,14 @@ public abstract class TypeData {
         }
 
         public void merge(TypeData t) {
-        	try {
-        	    if (!t.isNullType())
-        	        array.merge(ArrayType.make(t));
-        	}
-        	catch (BadBytecode e) {
-        		// never happens
-        		throw new RuntimeException("fatal: " + e);
-        	}
+            try {
+                if (!t.isNullType())
+                    array.merge(ArrayType.make(t));
+            }
+            catch (BadBytecode e) {
+                // never happens
+                throw new RuntimeException("fatal: " + e);
+            }
         }
 
         public String getName() {
@@ -625,10 +717,18 @@ public abstract class TypeData {
             array.setType(ArrayType.typeName(s), cp);
         }
 
-        protected TypeVar toTypeVar() { return array.toTypeVar(); }
+        protected TypeVar toTypeVar(int dim) { return array.toTypeVar(dim - 1); }
+
+        public TypeData getArrayType(int dim) throws NotFoundException {
+            return array.getArrayType(dim - 1);
+        }
 
         public int dfs(ArrayList order, int index, ClassPool cp) throws NotFoundException {
-        	return array.dfs(order, index, cp);
+            return array.dfs(order, index, cp);
+        }
+
+        String toString2(HashSet set) {
+            return "*" + array.toString2(set);
         }
     }
 
@@ -644,7 +744,7 @@ public abstract class TypeData {
         public boolean eq(TypeData d) { return type.eq(d); }
         public String getName() { return type.getName(); }
 
-        protected TypeVar toTypeVar() { return null; }
+        protected TypeVar toTypeVar(int dim) { return null; }
         public TypeData join() { return type.join(); }
 
         public void setType(String s, ClassPool cp) throws BadBytecode {
@@ -666,6 +766,12 @@ public abstract class TypeData {
             else // if type == TypeTag.TOP
                 throw new RuntimeException("not available");
         }
+
+        public TypeData getArrayType(int dim) throws NotFoundException {
+            return type.getArrayType(dim);
+        }
+
+        String toString2(HashSet set) { return ""; }
     }
 
     /**
@@ -695,6 +801,45 @@ public abstract class TypeData {
         public boolean eq(TypeData d) { return name.equals(d.getName()); }
 
         public void setType(String typeName, ClassPool cp) throws BadBytecode {}
+
+        public TypeData getArrayType(int dim) throws NotFoundException {
+            if (dim == 0)
+                return this;
+            else if (dim > 0) {
+                char[] dimType = new char[dim];
+                for (int i = 0; i < dim; i++)
+                    dimType[i] = '[';
+
+                String elementType = getName();
+                if (elementType.charAt(0) != '[')
+                    elementType = "L" + elementType.replace('.', '/') + ";";
+
+                return new ClassName(new String(dimType) + elementType);
+            }
+            else {
+                for (int i = 0; i < -dim; i++)
+                    if (name.charAt(i) != '[')
+                        throw new NotFoundException("no " + dim + " dimensional array type: " + getName());
+
+                char type = name.charAt(-dim);
+                if (type == '[')
+                    return new ClassName(name.substring(-dim));
+                else if (type == 'L')
+                    return new ClassName(name.substring(-dim + 1, name.length() - 1).replace('/', '.')); 
+                else if (type == TypeTag.DOUBLE.decodedName)
+                    return TypeTag.DOUBLE;
+                else if (type == TypeTag.FLOAT.decodedName)
+                    return TypeTag.FLOAT;
+                else if (type == TypeTag.LONG.decodedName)
+                    return TypeTag.LONG;
+                else
+                    return TypeTag.INTEGER;
+            }
+        }
+
+        String toString2(HashSet set) {
+            return name;
+        }
     }
 
     /**
@@ -713,6 +858,8 @@ public abstract class TypeData {
 
         public boolean isNullType() { return true; }
         public int getTypeData(ConstPool cp) { return 0; }
+
+        public TypeData getArrayType(int dim) { return this; }
     }
 
     /**
@@ -756,14 +903,14 @@ public abstract class TypeData {
                 return false;
         }
 
-        public String toString() { return "uninit:" + getName() + "@" + offset; }
-
         public int offset() { return offset; }
 
         public void constructorCalled(int offset) {
             if (offset == this.offset)
                 initialized = true;
         }
+
+        String toString2(HashSet set) { return getName() + "," + offset; }
     }
 
     public static class UninitThis extends UninitData {
@@ -781,6 +928,6 @@ public abstract class TypeData {
             return 0;
         }
 
-        public String toString() { return "uninit:this"; }
+        String toString2(HashSet set) { return "uninit:this"; }
     }
 }
diff --git a/src/main/javassist/bytecode/stackmap/TypeTag.java b/src/main/javassist/bytecode/stackmap/TypeTag.java
index 2a90d147..6fcdb243 100644
--- a/src/main/javassist/bytecode/stackmap/TypeTag.java
+++ b/src/main/javassist/bytecode/stackmap/TypeTag.java
@@ -20,11 +20,11 @@ import javassist.bytecode.StackMapTable;
 
 public interface TypeTag {
     String TOP_TYPE = "*top*";
-    TypeData TOP = new TypeData.BasicType(TOP_TYPE, StackMapTable.TOP);
-    TypeData INTEGER = new TypeData.BasicType("int", StackMapTable.INTEGER);
-    TypeData FLOAT = new TypeData.BasicType("float", StackMapTable.FLOAT);
-    TypeData DOUBLE = new TypeData.BasicType("double", StackMapTable.DOUBLE);
-    TypeData LONG = new TypeData.BasicType("long", StackMapTable.LONG);
+    TypeData.BasicType TOP = new TypeData.BasicType(TOP_TYPE, StackMapTable.TOP, ' ');
+    TypeData.BasicType INTEGER = new TypeData.BasicType("int", StackMapTable.INTEGER, 'I');
+    TypeData.BasicType FLOAT = new TypeData.BasicType("float", StackMapTable.FLOAT, 'F');
+    TypeData.BasicType DOUBLE = new TypeData.BasicType("double", StackMapTable.DOUBLE, 'D');
+    TypeData.BasicType LONG = new TypeData.BasicType("long", StackMapTable.LONG, 'J');
 
     // and NULL, THIS, OBJECT, UNINIT
 }
diff --git a/src/test/Test.java b/src/test/Test.java
index 2e6f5c3d..c21d930f 100644
--- a/src/test/Test.java
+++ b/src/test/Test.java
@@ -1,31 +1,54 @@
+import java.util.ArrayList;
+import java.util.List;
 import javassist.*;
-import javassist.bytecode.*;
-import javassist.bytecode.annotation.*;
 
-@interface Entity {}
+class InvalidStackMapFrame {
 
-@interface Table { String[] textValues() default {}; }
+	public void bytecodeVerifyError1() {
+        String[] newLine = new String[10];
+        for (int i = 0; i < 5; i++) {
+        	String a = newLine[1];
+        	newLine[4] = a;
+        }
+	}
+
+	public void bytecodeVerifyError() {
+        // javassist bug : invalid stack map frame
+        List<Integer> test = new ArrayList<Integer>();
+        String[] newLine = new String[10];
+        for (Integer idx : test) {
+            // invalid stackMapFrame
+            // FRAME FULL [bug_regression_jdk7/javassist/InvalidStackMapFrame java/util/ArrayList java/lang/Object java/util/Iterator T T T I] []
+            // java/lang/Object is wrong ->  [Ljava/lang/String; is correct
+            String address = newLine[1];
+            int tabPos = -1;
+            if (tabPos != -1) {
+                address = address.substring(tabPos + 1);
+            }
+            newLine[4] = address;
+        }
+
+    }
+}
 
 public class Test {
+    private static final String INVALID_STACK_MAP_FRAME = "InvalidStackMapFrame";
+
     public static void main(String[] args) throws Exception {
+
+        // CustomURLClassLoader classLoader = new CustomURLClassLoader(new URL[]{}, Thread.currentThread().getContextClassLoader());
+
         ClassPool classPool = ClassPool.getDefault();
-        ClassFile cf = classPool.makeClass("TestSub").getClassFile();
-        ConstPool constPool = cf.getConstPool();
-        Annotation[] annotations = new Annotation[2];
-        AnnotationsAttribute attrib =
-                new AnnotationsAttribute(constPool, AnnotationsAttribute.visibleTag);
-        Annotation annotation = new Annotation(constPool, classPool.get("Entity"));
-        annotations[0] = annotation;
-        // Add @Table(name="",schema="") to class
-        annotation = new Annotation(constPool, classPool.get("Table"));
-        annotation.addMemberValue("name", new StringMemberValue("name", constPool));
-        annotation.addMemberValue("schema", new StringMemberValue("schema", constPool));
-//        ArrayMemberValue blankMemberValueArray = new ArrayMemberValue(new AnnotationMemberValue(constPool), constPool);
-//        blankMemberValueArray.setValue(new MemberValue[0]);
-//        annotation.addMemberValue("textValues", blankMemberValueArray);
-        annotations[1] = annotation;
-        attrib.setAnnotations(annotations);
-        cf.addAttribute(attrib);
-        System.out.println("done");
+        // classPool.appendClassPath(new LoaderClassPath(classLoader));
+
+        final CtClass ctClass = classPool.get(INVALID_STACK_MAP_FRAME);
+        final CtMethod method = ctClass.getDeclaredMethod("bytecodeVerifyError");
+        method.addLocalVariable("test_localVariable", CtClass.intType);
+        method.insertBefore("{ test_localVariable = 1; }");
+        ctClass.debugWriteFile();
+        Class<?> cc = ctClass.toClass();
+        System.out.println(cc.getName());
+        InvalidStackMapFrame obj = (InvalidStackMapFrame)cc.newInstance();
+        obj.bytecodeVerifyError();
     }
 }
diff --git a/src/test/javassist/JvstTest5.java b/src/test/javassist/JvstTest5.java
index 1af027fd..792fed6e 100644
--- a/src/test/javassist/JvstTest5.java
+++ b/src/test/javassist/JvstTest5.java
@@ -220,4 +220,19 @@ public class JvstTest5 extends JvstTestRoot {
         Class clazzz = badClass.toClass();
         Object obj = clazzz.newInstance(); // <-- falls here
     }
+
+    public void test83StackmapWithArrayType() throws Exception {
+    	final CtClass ctClass = sloader.get("test5.StackmapWithArray83");
+        final CtMethod method = ctClass.getDeclaredMethod("bytecodeVerifyError");
+        method.addLocalVariable("test_localVariable", CtClass.intType);
+        method.insertBefore("{ test_localVariable = 1; }");
+
+        final CtMethod method2 = ctClass.getDeclaredMethod("bytecodeVerifyError2");
+        method2.addLocalVariable("test_localVariable", CtClass.intType);
+        method2.insertBefore("{ test_localVariable = 1; }");
+
+        ctClass.writeFile();
+        Object obj = make(ctClass.getName());
+        assertEquals(1, invoke(obj, "run"));
+    }
 }
diff --git a/src/test/test5/StackmapWithArray83.java b/src/test/test5/StackmapWithArray83.java
new file mode 100644
index 00000000..c8333d81
--- /dev/null
+++ b/src/test/test5/StackmapWithArray83.java
@@ -0,0 +1,38 @@
+package test5;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public class StackmapWithArray83 {
+	public int run() {
+		bytecodeVerifyError();
+		bytecodeVerifyError2();
+		return 1;
+	}
+
+	public void bytecodeVerifyError() {
+        List<Integer> test = new ArrayList<Integer>();
+        String[] newLine = new String[10];
+        for (Integer idx : test) {
+            String address = newLine[1];
+            int tabPos = -1;
+            if (tabPos != -1) {
+                address = address.substring(tabPos + 1);
+            }
+            newLine[4] = address;
+        }
+    }
+
+	public void bytecodeVerifyError2() {
+        List<Integer> test = new ArrayList<Integer>();
+        int[] newLine = new int[10];
+        for (Integer idx : test) {
+            int address = newLine[1];
+            int tabPos = -1;
+            if (tabPos != -1) {
+                address = address + tabPos;
+            }
+            newLine[4] = address;
+        }
+    }
+}