*** empty log message ***

17 files changed, 1001 insertions, 0 deletions

diff --git a/sources/scala/runtime/AtomicReference.java b/sources/scala/runtime/AtomicReference.java
new file mode 100644
index 0000000000..37d0aff4d3
--- /dev/null
+++ b/sources/scala/runtime/AtomicReference.java
@@ -0,0 +1,44 @@
+package scala.runtime;
+
+/**
+ * Blocking (i.e. non-atomic) placeholder for Java 1.5's
+ * java.util.concurrent.atomic.AtomicReference class.
+ */
+
+public class AtomicReference {
+    private Object value;
+
+    public AtomicReference(Object value) {
+        this.value = value;
+    }
+
+    public Object get() {
+        return value;
+    }
+
+    public Object getAndSet(Object update) {
+        Object previousValue = value;
+        value = update;
+        return previousValue;
+    }
+
+    public void set(Object update) {
+        value = update;
+    }
+
+    public synchronized boolean compareAndSet(Object expected, Object update) {
+        if (value == expected) {
+            value = update;
+            return true;
+        } else
+            return false;
+    }
+
+    public boolean weakCompareAndSet(Object expected, Object update) {
+        return compareAndSet(expected, update);
+    }
+
+    public String toString() {
+        return value.toString();
+    }
+}
diff --git a/sources/scala/runtime/FNV_Hash.java b/sources/scala/runtime/FNV_Hash.java
new file mode 100644
index 0000000000..5d1ab003f4
--- /dev/null
+++ b/sources/scala/runtime/FNV_Hash.java
@@ -0,0 +1,44 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id$
+
+package scala.runtime;
+
+/**
+ * Provide methods to compute the various kinds of Fowler / Noll / Vo
+ * (FNV) hash.
+ *
+ * @author Michel Schinz
+ */
+
+public class FNV_Hash {
+    public static final int INIT = -2128831035;
+
+    public static int hashStep(int current, int newByte) {
+        return (current * 16777619) ^ newByte;
+    }
+
+    public static int hash32(byte[] bytes) {
+        final int len = bytes.length;
+
+        int h = INIT;
+        for (int i = 0; i < len; ++i)
+            h = hashStep(h, bytes[i]);
+
+        return h;
+    }
+
+    public static int hash32(String str) {
+        try {
+            return hash32(str.getBytes("UTF-8"));
+        } catch (java.io.UnsupportedEncodingException e) {
+            throw new Error(e);
+        }
+    }
+}
diff --git a/sources/scala/runtime/IOMap.java b/sources/scala/runtime/IOMap.java
new file mode 100644
index 0000000000..e132941353
--- /dev/null
+++ b/sources/scala/runtime/IOMap.java
@@ -0,0 +1,171 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id$
+
+package scala.runtime;
+
+/**
+ * Purely functional maps from integers to objects. Implemented as
+ * red-black trees.
+ *
+ * @author Michel Schinz
+ * @version 1.0
+ */
+
+public class IOMap {
+
+    /** The map class itself */
+    public static class T {
+        public case N(int c, T l, T r, int k, Object v);
+        public case E;
+    }
+
+    public static final T EMPTY = T.E;
+
+    // Node colors (Black and Red)
+    private static final int B = 0;
+    private static final int R = 1;
+
+    public static class ConflictException extends Exception {
+        public final int key;
+        public final Object oldValue, newValue;
+
+        public ConflictException(int key, Object oldValue, Object newValue) {
+            this.key = key;
+            this.oldValue = oldValue;
+            this.newValue = newValue;
+        }
+        public Throwable fillInStackTrace() {
+            // do nothing, to speed up things
+            return this;
+        }
+    }
+
+    public Object resolveConflict(int k, Object oldV, Object newV)
+        throws ConflictException {
+        throw new ConflictException(k, oldV, newV);
+    }
+
+    public T put(T map, int key, Object value) throws ConflictException {
+        switch (putAux(map, key, value)) {
+        case N(_, T l, T r, int k, Object v):
+            return T.N(B, l, r, k, v);
+        default:
+            throw new Error();
+        }
+    }
+
+    private T putAux(T map, int key, Object value) throws ConflictException {
+        switch (map) {
+        case N(int c, T l, T r, int k, Object v):
+            if (key < k)
+                return balance(T.N(c, putAux(l, key, value), r, k, v));
+            else if (key > k)
+                return balance(T.N(c, l, putAux(r, key, value), k, v));
+            else
+                return T.N(c, l, r, k, resolveConflict(k, v, value));
+        case E:
+            return T.N(R, T.E, T.E, key, value);
+        default:
+            throw new Error();
+        }
+    }
+
+    private T balance(T t) {
+        switch (t) {
+        case N(B,
+               N(R, N(R, T a, T b, int xK, Object xV), T c, int yK, Object yV),
+               T d,
+               int zK, Object zV):
+            return T.N(R, T.N(B, a, b, xK, xV), T.N(B, c, d, zK, zV), yK, yV);
+        case N(B,
+               N(R, T a, N(R, T b, T c, int yK, Object yV), int xK, Object xV),
+               T d,
+               int zK, Object zV):
+            return T.N(R, T.N(B, a, b, xK, xV), T.N(B, c, d, zK, zV), yK, yV);
+        case N(B,
+               T a,
+               N(R, N(R, T b, T c, int yK, Object yV), T d, int zK, Object zV),
+               int xK, Object xV):
+            return T.N(R, T.N(B, a, b, xK, xV), T.N(B, c, d, zK, zV), yK, yV);
+        case N(B,
+               T a,
+               N(R, T b, N(R, T c, T d, int zK, Object zV), int yK, Object yV),
+               int xK, Object xV):
+            return T.N(R, T.N(B, a, b, xK, xV), T.N(B, c, d, zK, zV), yK, yV);
+        default:
+            return t;
+        }
+    }
+
+    public Object get(T map, int key) {
+        switch (map) {
+        case N(_, T l, T r, int k, Object v):
+            if (key < k)
+                return get(l, key);
+            else if (key > k)
+                return get(r, key);
+            else
+                return v;
+        case E:
+            return null;
+        default:
+            throw new Error("unexpected node " + this);
+        }
+    }
+
+    public int size(T map) {
+        switch (map) {
+        case N(_, T l, T r, _, _):
+            return size(l) + size(r) + 1;
+        case E:
+            return 0;
+        default:
+            throw new Error("unexpected node " + this);
+        }
+    }
+
+    public int depth(T map) {
+        switch (map) {
+        case N(_, T l, T r, _, _):
+            return Math.max(depth(l), depth(r)) + 1;
+        case E:
+            return 0;
+        default:
+            throw new Error("unexpected node " + this);
+        }
+    }
+}
+
+// class RBTest {
+//     static class MyIOMap extends IOMap {
+//         public Object resolveConflict(int k, Object oldV, Object newV) {
+//             throw new Error("conflict!!!");
+//         }
+//     }
+
+//     public static void main(String[] args) {
+//         MyIOMap map = new MyIOMap();
+//         MyIOMap.T t = map.EMPTY;
+
+//         long start = System.currentTimeMillis();
+//         for (int i = 0; i < args.length; ++i) {
+//             t = map.put(t, FNV_Hash.hash32(args[i]), new Integer(i));
+//         }
+
+//         for (int i = 0; i < args.length; ++i) {
+//             map.get(t, FNV_Hash.hash32(args[i]));
+//         }
+//         long end = System.currentTimeMillis();
+//         System.out.println("time: " + (end - start) + "ms");
+
+//         System.out.println("size  = " + map.size(t));
+//         System.out.println("depth = " + map.depth(t));
+//     }
+// }
diff --git a/sources/scala/runtime/types/ClassType.java b/sources/scala/runtime/types/ClassType.java
new file mode 100644
index 0000000000..16d956e042
--- /dev/null
+++ b/sources/scala/runtime/types/ClassType.java
@@ -0,0 +1,49 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id$
+
+package scala.runtime.types;
+
+import scala.Type;
+import scala.Array;
+import scala.runtime.RunTime;
+
+public class ClassType extends Type {
+    public final Class clazz;
+    public final boolean isTrivial;
+
+    public ClassType(Class clazz, boolean isTrivial) {
+        this.clazz = clazz;
+        this.isTrivial = isTrivial;
+    }
+
+    public Array newArray(int size) {
+        // TODO is that correct if we have type arguments?
+        Object[] array =
+            (Object[])java.lang.reflect.Array.newInstance(clazz, size);
+        return RunTime.box_oarray(array);
+    }
+
+    public Object defaultValue() {
+        return null;
+    }
+
+    public boolean isInstance(Object o) {
+        return clazz.isInstance(o);
+    }
+
+    public boolean isSubType(Type that) {
+        return (that instanceof ClassType)
+            && ((ClassType)that).clazz.isAssignableFrom(this.clazz);
+    }
+
+    public String toString() {
+        return clazz.getName();
+    }
+}
diff --git a/sources/scala/runtime/types/JavaClassType.java b/sources/scala/runtime/types/JavaClassType.java
new file mode 100644
index 0000000000..858386fa83
--- /dev/null
+++ b/sources/scala/runtime/types/JavaClassType.java
@@ -0,0 +1,17 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id$
+
+package scala.runtime.types;
+
+public class JavaClassType extends ClassType {
+    public JavaClassType(Class clazz) {
+        super(clazz, true);
+    }
+}
diff --git a/sources/scala/runtime/types/JavaTypeRepository.java b/sources/scala/runtime/types/JavaTypeRepository.java
new file mode 100644
index 0000000000..a3fce50e5a
--- /dev/null
+++ b/sources/scala/runtime/types/JavaTypeRepository.java
@@ -0,0 +1,55 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id$
+
+package scala.runtime.types;
+
+import scala.Type;
+import scala.Array;
+
+import java.util.HashMap;
+import java.util.Map;
+
+public class JavaTypeRepository {
+//     public static JavaClassType DOUBLE = new JavaClassType(double.class);
+//     public static JavaClassType FLOAT  = new JavaClassType(float.class);
+//     public static JavaClassType LONG   = new JavaClassType(long.class);
+//     public static JavaClassType INT    = new JavaClassType(int.class);
+//     public static JavaClassType SHORT  = new JavaClassType(short.class);
+//     public static JavaClassType CHAR   = new JavaClassType(char.class);
+//     public static JavaClassType BYTE   = new JavaClassType(byte.class);
+//     public static JavaClassType VOID   = new JavaClassType(void.class);
+
+    private static Map/*<String,JavaClassType>*/ map = new HashMap();
+
+    private static final ClassLoader loader =
+        ClassLoader.getSystemClassLoader();
+
+    // TODO utiliser des hash
+    public static JavaClassType get(String name) {
+        JavaClassType jt;
+        synchronized (map) { jt = (JavaClassType)map.get(name); }
+
+        if (jt == null) {
+            try {
+                jt = new JavaClassType(Class.forName(name, false, loader));
+            } catch (ClassNotFoundException e) {
+                throw new Error(e);
+            }
+
+            synchronized (map) {
+                if (map.containsKey(name))
+                    jt = (JavaClassType)map.get(name);
+                else
+                    map.put(name, jt);
+            }
+        }
+        return jt;
+    }
+}
diff --git a/sources/scala/runtime/types/ScalaClassType.java b/sources/scala/runtime/types/ScalaClassType.java
new file mode 100644
index 0000000000..ed0c1ab711
--- /dev/null
+++ b/sources/scala/runtime/types/ScalaClassType.java
@@ -0,0 +1,157 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id$
+
+package scala.runtime.types;
+
+import scala.Type;
+import scala.Array;
+import scala.ScalaObject;
+import scala.runtime.RunTime;
+
+public class ScalaClassType extends ClassType {
+    private static ScalaClassType[] EMPTY_DISPLAY_ROW =
+        new ScalaClassType[0];
+    private static ScalaClassType[][] EMPTY_DISPLAY =
+        new ScalaClassType[0][];
+
+    private final TypeConstructor constr;
+    private final Type[] inst;
+    private final ScalaClassType[] parents;
+
+    private ScalaClassType[][] display = EMPTY_DISPLAY;
+
+    public ScalaClassType(TypeConstructor constr,
+                          Type[] inst,
+                          ScalaClassType[] parents) {
+        super(constr.clazz, constr.isTrivial);
+
+        this.constr = constr;
+        this.inst = inst;
+        this.parents = parents;
+
+        computeDisplay();       // TODO do this lazily
+    }
+
+    public String toString() {
+        StringBuffer buf = new StringBuffer();
+        if (constr.outer != null)
+            buf.append(constr.outer).append(".");
+        buf.append(constr).append("[");
+        for (int i = 0; i < inst.length; ++i) {
+            if (i > 0) buf.append(", ");
+            buf.append(inst[i]);
+        }
+        return buf.append("]").toString();
+    }
+
+    public boolean weakIsSubScalaClassType(ScalaClassType that) {
+        // Find our instantiation for the other type, if any.
+        ScalaClassType[] thisSlice = display[that.constr.level];
+        ScalaClassType parentCT = null;
+
+        for (int i = 0; i < thisSlice.length; ++i) {
+            if (thisSlice[i].constr == that.constr) {
+                parentCT = thisSlice[i];
+                break;
+            }
+        }
+
+        // At this stage, if parentCT is null, it means that the
+        // constructors had different prefixes, hence we return false.
+
+        return (parentCT != null)
+            && (parentCT == that || parentCT.hasSubInstantiation(that));
+    }
+
+    public boolean isInstance(Object o) {
+        return super.isInstance(o)
+            && ((ScalaObject)o).getType().weakIsSubScalaClassType(this);
+    }
+
+    public boolean isSubType(ClassType that) {
+        return that.isTrivial || weakIsSubScalaClassType((ScalaClassType)that);
+    }
+
+    public boolean isSubType(Type that) {
+        return super.isSubType(that) && isSubType((ClassType)that);
+    }
+
+    // Return true iff the instantiation of THIS is "smaller" than the
+    // one of THAT.
+    private boolean hasSubInstantiation(ScalaClassType that) {
+        assert this.constr == that.constr;
+
+        final Type[] thisInst = this.inst;
+        final Type[] thatInst = that.inst;
+
+        int i = 0;
+
+        // invariant parameters
+        final int firstM = this.constr.zCount;
+        while (i < firstM) {
+            if (thisInst[i] != thatInst[i])
+                return false;
+            ++i;
+        }
+        // contravariant parameters
+        final int firstP = firstM + this.constr.mCount;
+        while (i < firstP) {
+            if (!thatInst[i].isSubType(thisInst[i]))
+                return false;
+            ++i;
+        }
+        // covariant parameters
+        final int firstOutside = firstP + this.constr.pCount;
+        while (i < firstOutside) {
+            if (!thisInst[i].isSubType(thatInst[i]))
+                return false;
+            ++i;
+        }
+        return true;
+    }
+
+    private void computeDisplay() {
+        final int level = constr.level;
+        final int[] displayCode = constr.displayCode;
+
+        display = new ScalaClassType[level + 1][];
+        ScalaClassType[][] superClassDisplay =
+            parents.length > 0 ? parents[0].display : EMPTY_DISPLAY;
+
+        for (int l = 0, dci = 0; l <= level; ++l) {
+            int additionalEntries = displayCode[dci++];
+            ScalaClassType[] initialRow;
+
+            if (l < superClassDisplay.length)
+                initialRow = superClassDisplay[l];
+            else if (l == level)
+                initialRow = new ScalaClassType[] { this };
+            else
+                initialRow = EMPTY_DISPLAY_ROW;
+
+            if (additionalEntries == 0) {
+                display[l] = initialRow;
+            } else {
+                int superLen = initialRow.length;
+                ScalaClassType[] newRow =
+                    new ScalaClassType[superLen + additionalEntries];
+
+                System.arraycopy(initialRow, 0, newRow, 0, superLen);
+                for (int i = 0; i < additionalEntries; ++i) {
+                    int p = displayCode[dci++];
+                    int o = displayCode[dci++];
+                    newRow[superLen + i] = parents[p].display[l][o];
+                }
+
+                display[l] = newRow;
+            }
+        }
+    }
+}
diff --git a/sources/scala/runtime/types/SingleType.java b/sources/scala/runtime/types/SingleType.java
new file mode 100644
index 0000000000..f94d583c94
--- /dev/null
+++ b/sources/scala/runtime/types/SingleType.java
@@ -0,0 +1,42 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id$
+
+package scala.runtime.types;
+
+import scala.Type;
+import scala.Array;
+
+class SingleType extends Type {
+    private final Object instance;
+
+    public SingleType(Object instance) {
+        this.instance = instance;
+    }
+
+    public Array newArray(int size) {
+        throw new Error();      // TODO
+    }
+
+    public Object defaultValue() {
+        throw new Error();      // TODO
+    }
+
+    public boolean isInstance(Object o) {
+        return (o == instance); // TODO inclure null ?
+    }
+
+    public boolean equals(Object that) {
+        return false;           // TODO
+    }
+
+    public boolean isSubType(Type that) {
+        return false;           // TODO
+    }
+}
diff --git a/sources/scala/runtime/types/TypeBoolean.java b/sources/scala/runtime/types/TypeBoolean.java
new file mode 100644
index 0000000000..6012dcc601
--- /dev/null
+++ b/sources/scala/runtime/types/TypeBoolean.java
@@ -0,0 +1,30 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id$
+
+package scala.runtime.types;
+
+import scala.runtime.RunTime;
+import scala.Type;
+import scala.Array;
+import scala.Boolean;
+
+public class TypeBoolean extends Type {
+    private final Boolean ZERO = RunTime.box_zvalue(false);
+    public Array newArray(int size) {
+        return RunTime.box_zarray(new boolean[size]);
+    }
+    public Object defaultValue() { return ZERO; }
+    public boolean isInstance(Object o) {
+        throw new UnsupportedOperationException();
+    }
+    public boolean isSubType(Type that) {
+        return false;           // TODO
+    }
+};
diff --git a/sources/scala/runtime/types/TypeByte.java b/sources/scala/runtime/types/TypeByte.java
new file mode 100644
index 0000000000..0174397e8c
--- /dev/null
+++ b/sources/scala/runtime/types/TypeByte.java
@@ -0,0 +1,30 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id$
+
+package scala.runtime.types;
+
+import scala.runtime.RunTime;
+import scala.Type;
+import scala.Array;
+import scala.Byte;
+
+public class TypeByte extends Type {
+    private final Byte ZERO = RunTime.box_bvalue((byte)0);
+    public Array newArray(int size) {
+        return RunTime.box_barray(new byte[size]);
+    }
+    public Object defaultValue() { return ZERO; }
+    public boolean isInstance(Object o) {
+        throw new UnsupportedOperationException();
+    }
+    public boolean isSubType(Type that) {
+        return false;           // TODO
+    }
+};
diff --git a/sources/scala/runtime/types/TypeChar.java b/sources/scala/runtime/types/TypeChar.java
new file mode 100644
index 0000000000..74519c636d
--- /dev/null
+++ b/sources/scala/runtime/types/TypeChar.java
@@ -0,0 +1,30 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id$
+
+package scala.runtime.types;
+
+import scala.runtime.RunTime;
+import scala.Type;
+import scala.Array;
+import scala.Char;
+
+public class TypeChar extends Type {
+    private final Char ZERO = RunTime.box_cvalue((char)0);
+    public Array newArray(int size) {
+        return RunTime.box_carray(new char[size]);
+    }
+    public Object defaultValue() { return ZERO; }
+    public boolean isInstance(Object o) {
+        throw new UnsupportedOperationException();
+    }
+    public boolean isSubType(Type that) {
+        return false;           // TODO
+    }
+};
diff --git a/sources/scala/runtime/types/TypeConstructor.java b/sources/scala/runtime/types/TypeConstructor.java
new file mode 100644
index 0000000000..54403a5cf5
--- /dev/null
+++ b/sources/scala/runtime/types/TypeConstructor.java
@@ -0,0 +1,184 @@
+/*                     __                                               * \
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id$
+
+package scala.runtime.types;
+
+import scala.Type;
+import scala.Array;
+import scala.runtime.AtomicReference;
+import scala.runtime.IOMap;
+import scala.runtime.FNV_Hash;
+
+/**
+ * Class modelling a type constructor (this includes non-polymorphic
+ * types, which are handled as polymorphic types with zero arguments).
+ *
+ * @author Michel Schinz
+ * @version 1.0
+ */
+
+public class TypeConstructor {
+    public final static TypeConstructor[] EMPTY_ARRAY =
+        new TypeConstructor[0];
+
+    /** Full (qualified) name for this constructor. */
+    public final String fullName;
+
+    /** Java class corresponding to this constructor. */
+    public Class clazz;
+
+    /** Enclosing class for this type constructor */
+    public final Object outer;
+
+    /**
+     * Number of invariant (z), contravariant (m) and covariant (p)
+     * type arguments.
+     */
+    public final int zCount, mCount, pCount;
+
+    /**
+     * Level of this type in the hierarchy (scala.AnyRef is at 0, its
+     * direct children at 1, and so on).
+     */
+    public final int level;
+
+    /**
+     * Indication of triviality: a constructor is trivial iff it has
+     * no enclosing class, and no type arguments.
+     */
+    public final boolean isTrivial;
+
+    /**
+     * "Code" to compute the display for an instance of this
+     * constructor, based on the display of its 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 ...
+     *
+     * 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 display 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 display.
+     */
+    public final int[] displayCode;
+
+    private final InstantiationMap instMapModule = new InstantiationMap();
+    private final AtomicReference/*<InstantiationMap.T>*/ instances =
+        new AtomicReference(IOMap.EMPTY);
+
+    private static final ClassLoader loader =
+        ClassLoader.getSystemClassLoader();
+
+    public TypeConstructor(int level,
+                           String fullName,
+                           Object outer,
+                           int zCount,
+                           int mCount,
+                           int pCount,
+                           int[] displayCode) {
+        this.level = level;
+        this.fullName = fullName;
+        this.outer = outer;
+        this.zCount = zCount;
+        this.mCount = mCount;
+        this.pCount = pCount;
+
+        this.isTrivial = (outer == null) && (zCount + pCount + mCount == 0);
+
+        this.displayCode = displayCode;
+
+        try {
+            this.clazz = Class.forName(fullName, false, loader);
+        } catch (ClassNotFoundException e) {
+            throw new Error(e);
+        }
+
+        assert (zCount >= 0) && (mCount >= 0) && (pCount >= 0);
+    }
+
+    public String toString() {
+        return fullName;
+    }
+
+    public ScalaClassType getInstantiation(Type[] args) {
+        return instMapModule.get((InstantiationMap.T)instances.get(), args);
+    }
+
+    public ScalaClassType instantiate(Type[] args, ScalaClassType[] parents) {
+        ScalaClassType tp = new ScalaClassType(this, args, parents);
+
+        try {
+            InstantiationMap.T oldMap, newMap;
+            do {
+                oldMap = (InstantiationMap.T)instances.get();
+                newMap = instMapModule.put(oldMap, args, tp);
+            } while (!instances.compareAndSet(oldMap, newMap));
+        } catch (IOMap.ConflictException e) {
+            return (ScalaClassType)e.oldValue;
+        }
+        return tp;
+    }
+
+
+    //////////////////////////////////////////////////////////////////////
+
+    private static class InstantiationMap extends IOMap {
+        public T put(T map, Type[] inst, ScalaClassType value)
+            throws ConflictException {
+            return super.put(map, hashInst(inst), value);
+        }
+
+        public ScalaClassType get(T map, Type[] inst) {
+            return (ScalaClassType)super.get(map, hashInst(inst));
+        }
+
+        // Random permutation of [0;255], used for Pearson's hashing.
+        private int[] table = new int[] {
+            251, 117, 191, 48, 37, 199, 178, 157, 9, 50, 183, 197, 42, 40, 104,
+            83, 156, 250, 215, 14, 233, 33, 74, 253, 128, 10, 36, 73, 217, 224,
+            116, 86, 132, 204, 20, 2, 80, 55, 222, 5, 207, 201, 129, 216, 165,
+            155, 159, 236, 19, 146, 108, 124, 112, 0, 58, 92, 70, 152, 135, 88,
+            97, 122, 61, 255, 184, 211, 214, 141, 67, 79, 18, 62, 101, 173,
+            238, 154, 170, 164, 130, 229, 252, 205, 43, 81, 94, 149, 59, 151,
+            93, 45, 25, 166, 139, 44, 143, 16, 188, 30, 91, 218, 77, 60, 142,
+            168, 47, 176, 13, 49, 34, 102, 31, 65, 203, 76, 240, 78, 115, 84,
+            244, 32, 11, 175, 247, 209, 242, 71, 163, 167, 35, 136, 22, 237,
+            134, 56, 181, 17, 4, 24, 206, 192, 105, 63, 89, 239, 6, 72, 53,
+            219, 69, 227, 133, 15, 161, 68, 120, 12, 111, 179, 245, 100, 103,
+            8, 148, 107, 144, 127, 160, 26, 241, 162, 213, 1, 220, 150, 82,
+            190, 96, 98, 137, 174, 145, 46, 243, 125, 198, 231, 66, 234, 177,
+            212, 210, 226, 95, 228, 21, 254, 27, 28, 121, 196, 187, 54, 249,
+            109, 208, 153, 232, 194, 113, 23, 140, 235, 158, 248, 182, 202,
+            186, 147, 119, 225, 87, 126, 64, 221, 193, 246, 169, 189, 90, 180,
+            138, 57, 38, 75, 230, 41, 123, 110, 223, 118, 106, 7, 172, 114,
+            131, 99, 51, 185, 39, 171, 195, 52, 29, 200, 3, 85
+        };
+
+        // Pearson's algorithm, used to hash an integer into a single
+        // byte.
+        private int hashInt(int i) {
+            final int h1 = table[i & 0xFF];
+            final int h2 = table[h1 ^ ((i >>>  8) & 0xFF)];
+            final int h3 = table[h2 ^ ((i >>> 16) & 0xFF)];
+            return table[h3 ^ (i >>> 24)];
+        }
+
+        private int hashInst(Type[] inst) {
+            final int len = inst.length;
+
+            int h = FNV_Hash.INIT;
+            for (int i = 0; i < len; ++i)
+                h = FNV_Hash.hashStep(h, hashInt(inst[i].hashCode()));
+
+            return h;
+        }
+    }
+}
diff --git a/sources/scala/runtime/types/TypeDouble.java b/sources/scala/runtime/types/TypeDouble.java
new file mode 100644
index 0000000000..b3b5290cef
--- /dev/null
+++ b/sources/scala/runtime/types/TypeDouble.java
@@ -0,0 +1,30 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id$
+
+package scala.runtime.types;
+
+import scala.runtime.RunTime;
+import scala.Type;
+import scala.Array;
+
+public public class TypeDouble extends Type {
+    private final scala.Double ZERO = RunTime.box_dvalue(0.0);
+    public Array newArray(int size) {
+        return RunTime.box_darray(new double[size]);
+    }
+    public Object defaultValue() { return ZERO; }
+    public boolean isInstance(Object o) {
+        throw new UnsupportedOperationException();
+    }
+    public boolean isSubType(Type that) {
+        return false;           // TODO
+    }
+};
+
diff --git a/sources/scala/runtime/types/TypeFloat.java b/sources/scala/runtime/types/TypeFloat.java
new file mode 100644
index 0000000000..75a3d91b96
--- /dev/null
+++ b/sources/scala/runtime/types/TypeFloat.java
@@ -0,0 +1,30 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id$
+
+package scala.runtime.types;
+
+import scala.runtime.RunTime;
+import scala.Type;
+import scala.Array;
+
+public class TypeFloat extends Type {
+    private final scala.Float ZERO = RunTime.box_fvalue(0.0f);
+    public Array newArray(int size) {
+        return RunTime.box_farray(new float[size]);
+    }
+    public Object defaultValue() { return ZERO; }
+    public boolean isInstance(Object o) {
+        throw new UnsupportedOperationException();
+    }
+    public boolean isSubType(Type that) {
+        return false;           // TODO
+    }
+};
+
diff --git a/sources/scala/runtime/types/TypeInt.java b/sources/scala/runtime/types/TypeInt.java
new file mode 100644
index 0000000000..6491e94fe6
--- /dev/null
+++ b/sources/scala/runtime/types/TypeInt.java
@@ -0,0 +1,30 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id$
+
+package scala.runtime.types;
+
+import scala.runtime.RunTime;
+import scala.Type;
+import scala.Array;
+import scala.Int;
+
+public class TypeInt extends Type {
+    private final Int ZERO = RunTime.box_ivalue(0);
+    public Array newArray(int size) {
+        return RunTime.box_iarray(new int[size]);
+    }
+    public Object defaultValue() { return ZERO; }
+    public boolean isInstance(Object o) {
+        throw new UnsupportedOperationException();
+    }
+    public boolean isSubType(Type that) {
+        return false;           // TODO
+    }
+};
diff --git a/sources/scala/runtime/types/TypeLong.java b/sources/scala/runtime/types/TypeLong.java
new file mode 100644
index 0000000000..38caac802a
--- /dev/null
+++ b/sources/scala/runtime/types/TypeLong.java
@@ -0,0 +1,29 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id$
+
+package scala.runtime.types;
+
+import scala.runtime.RunTime;
+import scala.Type;
+import scala.Array;
+
+public class TypeLong extends Type {
+    private final scala.Long ZERO = RunTime.box_lvalue(0l);
+    public Array newArray(int size) {
+        return RunTime.box_larray(new long[size]);
+    }
+    public Object defaultValue() { return ZERO; }
+    public boolean isInstance(Object o) {
+        throw new UnsupportedOperationException();
+    }
+    public boolean isSubType(Type that) {
+        return false;           // TODO
+    }
+};
diff --git a/sources/scala/runtime/types/TypeShort.java b/sources/scala/runtime/types/TypeShort.java
new file mode 100644
index 0000000000..d959f83be6
--- /dev/null
+++ b/sources/scala/runtime/types/TypeShort.java
@@ -0,0 +1,29 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id$
+
+package scala.runtime.types;
+
+import scala.runtime.RunTime;
+import scala.Type;
+import scala.Array;
+
+public class TypeShort extends Type {
+    private final scala.Short ZERO = RunTime.box_svalue((short)0);
+    public Array newArray(int size) {
+        return RunTime.box_sarray(new short[size]);
+    }
+    public Object defaultValue() { return ZERO; }
+    public boolean isInstance(Object o) {
+        throw new UnsupportedOperationException();
+    }
+    public boolean isSubType(Type that) {
+        return false;           // TODO
+    }
+};