- changed the format of the ancestor code, to s...

- changed the format of the ancestor code, to shrink it (hopefully),
- put only non-trivial types in the ancestor cache, pass only strongly
- non-trivial parents to instantiation methods,

3 files changed, 115 insertions, 96 deletions

diff --git a/sources/scala/runtime/types/ScalaClassType.java b/sources/scala/runtime/types/ScalaClassType.java
index cc070ac398..728ac1b582 100644
--- a/sources/scala/runtime/types/ScalaClassType.java
+++ b/sources/scala/runtime/types/ScalaClassType.java
@@ -21,14 +21,14 @@ public class ScalaClassType extends ClassType {
     public static final ScalaClassType[] EMPTY_ARRAY =
         new ScalaClassType[0];
 
-    private static final ScalaClassType[][] EMPTY_ANCESTOR =
+    private static final ScalaClassType[][] EMPTY_ANCESTORS =
         new ScalaClassType[0][];
 
     private final TypeConstructor constr;
     private final Type[] inst;
 
-    private ScalaClassType[] parents = null;
-    private ScalaClassType[][] ancestor = null;
+    private ScalaClassType[] parents;
+    private ScalaClassType[][] ancestors = null;
 
     private final int hashCode;
 
@@ -48,17 +48,20 @@ public class ScalaClassType extends ClassType {
         }
         this.hashCode = hash;
         this.parents = parents;
+        this.ancestors = constr.isStronglyTrivial ? EMPTY_ANCESTORS : null;
     }
 
     public boolean isInstance(Object o) {
         return super.isInstance(o)
-            && ((ScalaObject)o).getType().weakIsSubScalaClassType(this);
+            && (isTrivial
+                || ((ScalaObject)o).getType().weakIsSubScalaClassType(this));
     }
 
     protected boolean isSubClassType(ClassType that) {
-        return super.isSubClassType(that)
-            && (that.isTrivial
-                || weakIsSubScalaClassType((ScalaClassType)that));
+        return (this == that)
+            || (super.isSubClassType(that)
+                && (that.isTrivial
+                    || weakIsSubScalaClassType((ScalaClassType)that)));
     }
 
     private boolean weakIsSubScalaClassType(ScalaClassType that) {
@@ -83,21 +86,24 @@ public class ScalaClassType extends ClassType {
         // invariant parameters
         final int firstM = this.constr.zCount;
         while (i < firstM) {
-            if (!thisInst[i].isSameType(thatInst[i]))
+            Type thisTp = thisInst[i], thatTp = thatInst[i];
+            if (!(thisTp == thatTp || thisTp.isSameType(thatTp)))
                 return false;
             ++i;
         }
         // contravariant parameters
         final int firstP = firstM + this.constr.mCount;
         while (i < firstP) {
-            if (!thatInst[i].isSubType(thisInst[i]))
+            Type thisTp = thisInst[i], thatTp = thatInst[i];
+            if (!(thisTp == thatTp || thatTp.isSubType(thisTp)))
                 return false;
             ++i;
         }
         // covariant parameters
         final int firstOutside = firstP + this.constr.pCount;
         while (i < firstOutside) {
-            if (!thisInst[i].isSubType(thatInst[i]))
+            Type thisTp = thisInst[i], thatTp = thatInst[i];
+            if (!(thisTp == thatTp || thisTp.isSubType(thatTp)))
                 return false;
             ++i;
         }
@@ -105,24 +111,7 @@ public class ScalaClassType extends ClassType {
     }
 
     public boolean isSameType(Type that) {
-        if (super.isSameType(that)) {
-            ScalaClassType thatCT = (ScalaClassType)that;
-            ScalaClassType parentCT = myInstantiationFor(thatCT);
-            return (parentCT != null)
-                && (parentCT.hasSameInstantiation(thatCT));
-        } else
-            return false;
-    }
-
-    private boolean hasSameInstantiation(ScalaClassType that) {
-        final Type[] thisInst = this.inst;
-        final Type[] thatInst = that.inst;
-
-        for (int i = 0; i < thisInst.length; ++i) {
-            if (!thisInst[i].isSameType(thatInst[i]))
-                return false;
-        }
-        return true;
+        return this == that;
     }
 
     private ScalaClassType myInstantiationFor(ScalaClassType that) {
@@ -186,34 +175,39 @@ public class ScalaClassType extends ClassType {
     }
 
     private ScalaClassType[][] getAncestors() {
-        if (ancestor == null)
+        if (ancestors == null)
             computeAncestors();
-        return ancestor;
+        return ancestors;
     }
 
     private void computeAncestors() {
         final int level = constr.level;
+        final int ancestorDepth = constr.ancestorCacheDepth;
         final int[] ancestorCode = constr.ancestorCode;
         ScalaClassType[] parents = getParents();
 
-        ancestor = new ScalaClassType[level + 1][];
-        ScalaClassType[][] initialAncestor = parents.length > 0
+        ancestors = new ScalaClassType[ancestorDepth][];
+        ScalaClassType[][] initialAncestors = parents.length > 0
             ? parents[0].getAncestors()
-            : EMPTY_ANCESTOR;
+            : EMPTY_ANCESTORS;
 
-        for (int l = 0, dci = 0; l <= level; ++l) {
-            int toAddParents = ancestorCode[dci++];
-            int toAddSelf = (l == level) ? 1 : 0;
+        for (int l = 0, dci = 0; l < ancestorDepth; ++l) {
+            int toAddParents = 0;
+            if (dci < ancestorCode.length && ancestorCode[dci] == l) {
+                dci++;
+                toAddParents = ancestorCode[dci++];
+            }
+            int toAddSelf = (!constr.isTrivial) && (l == level) ? 1 : 0;
             int toAdd = toAddParents + toAddSelf;
             ScalaClassType[] initialRow;
 
-            if (l < initialAncestor.length)
-                initialRow = initialAncestor[l];
+            if (l < initialAncestors.length)
+                initialRow = initialAncestors[l];
             else
                 initialRow = ScalaClassType.EMPTY_ARRAY;
 
             if (toAdd == 0) {
-                ancestor[l] = initialRow;
+                ancestors[l] = initialRow;
             } else {
                 int initialLen = initialRow.length;
                 ScalaClassType[] newRow =
@@ -229,7 +223,7 @@ public class ScalaClassType extends ClassType {
                     newRow[toAddSelf + initialLen + i] =
                         parents[p].getAncestors()[l][o];
                 }
-                ancestor[l] = newRow;
+                ancestors[l] = newRow;
             }
         }
     }
diff --git a/sources/scala/runtime/types/TypeConstructor.java b/sources/scala/runtime/types/TypeConstructor.java
index 338d49312e..83bbd93460 100644
--- a/sources/scala/runtime/types/TypeConstructor.java
+++ b/sources/scala/runtime/types/TypeConstructor.java
@@ -50,19 +50,21 @@ public class TypeConstructor implements java.io.Serializable {
      * no enclosing class, and no type arguments.
      */
     public final boolean isTrivial;
+    public final boolean isStronglyTrivial;
 
+    public final int ancestorCacheDepth;
     /**
      * "Code" to compute the ancestors for an instance of this
-     * constructor, based on the ancestors of its parents. This code is
-     * structured as follows:
+     * constructor, based on the ancestors of its not-strongly-trivial
+     * parents. This code is structured as follows:
      *
-     * n1 p1,1 o1,1 p1,2 o1,2 ... p1,n o1,n  n2 p2,1 ...  nl pl,1 ol,2 ...
+     * l1 n1 p1,0 o1,0 p1,1 o1,1 ... l2 n2 p2,0 o2,0 ...
      *
-     * where all n, p and o are integers, and l is the level of this
-     * constructor. ni gives the number of additional entries to add
-     * to the ancestors of the super-class at level i. pi gives the
-     * index of the parent in which to pick this additional entry, and
-     * oi gives the offset of this entry in the parent's ancestors.
+     * where all l, n, p and o are integers. ni gives the number of
+     * additional entries to add to the ancestors of the super-class
+     * at level li. pi gives the index of the parent in which to pick
+     * this additional entry, and oi gives the offset of this entry in
+     * the parent's ancestors.
      */
     public final int[] ancestorCode;
 
@@ -79,6 +81,7 @@ public class TypeConstructor implements java.io.Serializable {
                            int zCount,
                            int mCount,
                            int pCount,
+                           int ancestorCacheDepth,
                            int[] ancestorCode) {
         this.level = level;
         this.outer = outer;
@@ -86,10 +89,12 @@ public class TypeConstructor implements java.io.Serializable {
         this.mCount = mCount;
         this.pCount = pCount;
 
-        this.isTrivial = (outer == null) && (zCount + pCount + mCount == 0);
-
+        this.ancestorCacheDepth = ancestorCacheDepth;
         this.ancestorCode = ancestorCode;
 
+        this.isTrivial = (outer == null) && (zCount + pCount + mCount == 0);
+        this.isStronglyTrivial = (ancestorCacheDepth == 0);
+
         try {
             this.clazz = Class.forName(fullName, false, loader);
         } catch (ClassNotFoundException e) {
diff --git a/sources/scalac/transformer/TypesAsValuesPhase.java b/sources/scalac/transformer/TypesAsValuesPhase.java
index 24b8e4a4cb..015b0a1f92 100644
--- a/sources/scalac/transformer/TypesAsValuesPhase.java
+++ b/sources/scalac/transformer/TypesAsValuesPhase.java
@@ -419,7 +419,7 @@ public class TypesAsValuesPhase extends Phase {
                     assert targs.length == 1 && vargs.length == 0;
                     Type type = targs[0].type;
                     Tree expr = transform(qualifierOf(fun));
-                    return isTrivialType(type)
+                    return isTrivial(type)
                         ? super.transform(tree)
                         : genInstanceTest(tree.pos, expr, type);
                 } else if (funSym == defs.ANY_AS) {
@@ -433,7 +433,7 @@ public class TypesAsValuesPhase extends Phase {
                     assert targs.length == 1 && vargs.length == 0;
                     Type type = targs[0].type;
                     Tree expr = transform(qualifierOf(fun));
-                    return isTrivialType(type)
+                    return isTrivial(type)
                         ? super.transform(tree)
                         : genTypeCast(tree.pos, expr, type);
                 } else if (!monoPrimitive(funSym)) {
@@ -592,8 +592,7 @@ public class TypesAsValuesPhase extends Phase {
                     ++zCount;
             }
 
-            Ancestor[][] disp = computeAncestors(clsSym);
-            int[] ancestorCode = getAncestorCode(computeAncestors(clsSym));
+            Ancestor[][] ancestors = computeAncestors(clsSym);
 
             Tree outer = isNestedClass(clsSym)
                 ? (clsSym.owner().isClass()
@@ -609,7 +608,8 @@ public class TypesAsValuesPhase extends Phase {
                 gen.mkIntLit(pos, zCount),
                 gen.mkIntLit(pos, mCount),
                 gen.mkIntLit(pos, pCount),
-                mkNewIntLitArray(pos, ancestorCode, owner)
+                gen.mkIntLit(pos, ancestors.length),
+                mkNewIntLitArray(pos, getAncestorCode(ancestors), owner)
             };
 
             Symbol tcConst = defs.TYPECONSTRUCTOR_CLASS.primaryConstructor();
@@ -686,7 +686,7 @@ public class TypesAsValuesPhase extends Phase {
             TreeList parentTypes = new TreeList();
             for (int i = 0; i < parents.length; ++i) {
                 Type parent = parents[i];
-                if (!parent.symbol().isJava())
+                if (!isStronglyTrivial(parent))
                     parentTypes.append(typeAsValue(pos, parent, insSym, tEnv));
             }
             boolean emptyParents = (parentTypes.length() == 0);
@@ -744,25 +744,34 @@ public class TypesAsValuesPhase extends Phase {
         }
 
         /**
-         * Return true iff the given type is "trivial", that is if it
-         * is representable as a Java type without loss of
-         * information.
+         * Return true iff the given type is trivial, that is if it
+         * has neither a prefix, nor type parameters.
          */
-        private boolean isTrivialType(Type tp) {
+        private boolean isTrivial(Type tp) {
             switch (tp) {
-            case ConstantType(Type base, _):
-                return isTrivialType(base);
             case TypeRef(_, Symbol sym, Type[] args):
                 return sym.isStatic() && args.length == 0;
             case SingleType(_, _):
-            case ThisType(_):   // TODO check
-            case CompoundType(_, _): // TODO check
+            case ThisType(_):
+            case CompoundType(_, _):
                 return false;
             default:
                 throw Debug.abort("unexpected type", tp);
             }
         }
 
+        private boolean isStronglyTrivial(Type tp) {
+            if (isTrivial(tp)) {
+                Type[] parents = tp.parents();
+                for (int i = 0; i < parents.length; ++i) {
+                    if (!isStronglyTrivial(parents[i]))
+                        return false;
+                }
+                return true;
+            } else
+                return false;
+        }
+
         /**
          * Transform a type into a tree representing it.
          */
@@ -939,31 +948,32 @@ public class TypesAsValuesPhase extends Phase {
         }
 
         private Ancestor[][] computeAncestors0(Symbol classSym) {
-            Symbol[] scalaParents = scalaParents(classSym);
+            Symbol[] nstParents = notStronglyTrivialParents(classSym);
             int level = level(classSym);
             ArrayList/*<Ancestor>*/[] ancestor = new ArrayList[level + 1];
 
             for (int l = 0; l < ancestor.length; ++l)
                 ancestor[l] = new ArrayList();
 
-            ancestor[level].add(new Ancestor(classSym, -1, -1));
+            if (!isTrivial(classSym.type()))
+                ancestor[level].add(new Ancestor(classSym, -1, -1));
 
             // Go over parents from left to right and add missing
-            // ancestors to the ancestor, remembering where they come
-            // from.
-            for (int p = 0; p < scalaParents.length; ++p) {
-                Symbol parentSymbol = scalaParents[p];
-                assert parentSymbol != Symbol.NONE;
-
-                Ancestor[][] parentAncestor = computeAncestors(parentSymbol);
-                assert parentAncestor.length <= ancestor.length;
+            // ancestors to the set, remembering where they come from.
+            for (int p = 0; p < nstParents.length; ++p) {
+                Symbol parentSymbol = nstParents[p];
+                Ancestor[][] parentAncestors = computeAncestors(parentSymbol);
+                assert parentAncestors.length <= ancestor.length;
 
-                for (int l = 0; l < parentAncestor.length; ++l) {
+                for (int l = 0; l < parentAncestors.length; ++l) {
                     ArrayList/*<Ancestor>*/ myRow = ancestor[l];
-                    Ancestor[] parentRow = parentAncestor[l];
+                    Ancestor[] parentRow = parentAncestors[l];
                     for (int i = 0; i < parentRow.length; ++i) {
                         Symbol sym = parentRow[i].symbol;
 
+                        if (isTrivial(sym.type()))
+                            continue;
+
                         Iterator myRowIt = myRow.iterator();
                         boolean alreadyExists = false;
                         while (!alreadyExists && myRowIt.hasNext()) {
@@ -978,7 +988,11 @@ public class TypesAsValuesPhase extends Phase {
                 }
             }
 
-            Ancestor[][] finalAncestor = new Ancestor[level + 1][];
+            int ancestorsLen = ancestor.length;
+            while (ancestorsLen > 0 && ancestor[ancestorsLen - 1].isEmpty())
+                --ancestorsLen;
+
+            Ancestor[][] finalAncestor = new Ancestor[ancestorsLen][];
             for (int i = 0; i < finalAncestor.length; ++i) {
                 finalAncestor[i] = (Ancestor[])
                     ancestor[i].toArray(new Ancestor[ancestor[i].size()]);
@@ -987,6 +1001,7 @@ public class TypesAsValuesPhase extends Phase {
             return finalAncestor;
         }
 
+        /** Return the non-trivial ancestors of the class */
         private Ancestor[][] computeAncestors(Symbol classSym) {
             Ancestor[][] ancestor = (Ancestor[][])ancestorCache.get(classSym);
             if (ancestor == null) {
@@ -997,20 +1012,21 @@ public class TypesAsValuesPhase extends Phase {
             return ancestor;
         }
 
-        private Symbol[] scalaParents(Symbol classSym) {
+        /** Return the parents which are not strongly trivial. */
+        private Symbol[] notStronglyTrivialParents(Symbol classSym) {
             Type[] parentTypes = classSym.parents();
-            ArrayList scalaParents = new ArrayList();
+            ArrayList nstParents = new ArrayList();
             for (int i = 0; i < parentTypes.length; ++i) {
-                Symbol parentSym = parentTypes[i].symbol();
-                if (!parentSym.isJava())
-                    scalaParents.add(parentSym);
+                if (!isStronglyTrivial(parentTypes[i]))
+                    nstParents.add(parentTypes[i].symbol());
             }
             return (Symbol[])
-                scalaParents.toArray(new Symbol[scalaParents.size()]);
+                nstParents.toArray(new Symbol[nstParents.size()]);
         }
 
         private int[] getAncestorCode(Ancestor[][] ancestor) {
-            ArrayList/*<List<Ancestor>>*/ prunedRows = new ArrayList();
+            ArrayList/*<Ancestor>*/[] prunedRows =
+                new ArrayList[ancestor.length];
 
             int totalSize = 0;
             for (int l = 0; l < ancestor.length; ++l) {
@@ -1020,22 +1036,24 @@ public class TypesAsValuesPhase extends Phase {
                     if (row[i].parentIndex > 0)
                         prunedRow.add(row[i]);
                 }
-
-                prunedRows.add(prunedRow);
-                totalSize += 1 + 2 * prunedRow.size();
+                prunedRows[l] = prunedRow;
+                if (!prunedRow.isEmpty())
+                    totalSize += 2 + 2 * prunedRow.size();
             }
 
             int[] res = new int[totalSize];
             int i = 0;
-            Iterator rowsIt = prunedRows.iterator();
-            while (rowsIt.hasNext()) {
-                ArrayList row = (ArrayList)rowsIt.next();
-                res[i++] = row.size();
-                Iterator ancIt = row.iterator();
-                while (ancIt.hasNext()) {
-                    Ancestor anc = (Ancestor)ancIt.next();
-                    res[i++] = anc.parentIndex;
-                    res[i++] = anc.position;
+            for (int l = 0; l < prunedRows.length; ++l) {
+                ArrayList row = prunedRows[l];
+                if (!row.isEmpty()) {
+                    res[i++] = l;
+                    res[i++] = row.size();
+                    Iterator ancIt = row.iterator();
+                    while (ancIt.hasNext()) {
+                        Ancestor anc = (Ancestor)ancIt.next();
+                        res[i++] = anc.parentIndex;
+                        res[i++] = anc.position;
+                    }
                 }
             }
             assert i == totalSize;
@@ -1055,6 +1073,8 @@ public class TypesAsValuesPhase extends Phase {
                                    + "/par" + ancestor[l][i].parentIndex
                                    + "/pos" + ancestor[l][i].position);
             }
+            if (ancestor[l].length == 0)
+                System.out.println("<empty>");
         }
     }