Initial commit

19 files changed, 2727 insertions, 0 deletions

diff --git a/src/dotty/tools/dotc/core/Annotations.scala b/src/dotty/tools/dotc/core/Annotations.scala
new file mode 100644
index 000000000..48165f488
--- /dev/null
+++ b/src/dotty/tools/dotc/core/Annotations.scala
@@ -0,0 +1,7 @@
+package dotty.tools.dotc.core
+
+object Annotations {
+
+  abstract class AnnotationInfo
+
+}
\ No newline at end of file
diff --git a/src/dotty/tools/dotc/core/Constants.scala b/src/dotty/tools/dotc/core/Constants.scala
new file mode 100644
index 000000000..94e22cdd4
--- /dev/null
+++ b/src/dotty/tools/dotc/core/Constants.scala
@@ -0,0 +1,12 @@
+package dotty.tools.dotc
+package core
+
+import Types._
+
+object Constants {
+
+  case class Constant(value: Any) {
+    def tpe: Type = ???
+  }
+
+}
\ No newline at end of file
diff --git a/src/dotty/tools/dotc/core/Contexts.scala b/src/dotty/tools/dotc/core/Contexts.scala
new file mode 100644
index 000000000..b13594f0b
--- /dev/null
+++ b/src/dotty/tools/dotc/core/Contexts.scala
@@ -0,0 +1,47 @@
+package dotty.tools.dotc
+package core
+
+import Decorators._
+import Periods._
+import Names._
+import Phases._
+import Types._
+
+object Contexts {
+
+  val NoContext: Context = null
+
+  abstract class Context extends Periods {
+    val underlying: Context
+    val root: RootContext
+    val period: Period
+    def names: NameTable
+    def phase: Phase = ???
+
+  }
+
+  abstract class SubContext(val underlying: Context) extends Context {
+    val root: RootContext = underlying.root
+    val period: Period = underlying.period
+    def names: NameTable = root.names
+  }
+
+  class RootContext extends Context
+                       with Symbols
+                       with Denotations
+                       with DenotationTransformers
+                       with Types {
+
+    val underlying: Context = throw new UnsupportedOperationException("RootContext.underlying")
+
+    val root: RootContext = this
+    val period = periodOf(NoRunId, NoPhaseId)
+    val names: NameTable = new NameTable
+    val variance = 1
+
+    var lastPhaseId: Int = NoPhaseId
+
+  }
+
+  private final val initialUniquesCapacity = 4096
+}
\ No newline at end of file
diff --git a/src/dotty/tools/dotc/core/Decorators.scala b/src/dotty/tools/dotc/core/Decorators.scala
new file mode 100644
index 000000000..ba3123358
--- /dev/null
+++ b/src/dotty/tools/dotc/core/Decorators.scala
@@ -0,0 +1,37 @@
+package dotty.tools.dotc
+package core
+
+import Contexts._, Names._
+
+object Decorators {
+
+  implicit class toTypeNameDecorator(val s: String) extends AnyVal {
+    def toTypeName(implicit context: Context): TypeName =
+      context.names.newTypeName(s)
+  }
+
+  implicit class toTermNameDecorator(val s: String) extends AnyVal {
+    def toTermName(implicit context: Context): TermName =
+      context.names.newTermName(s)
+  }
+
+  final val MaxRecursions = 1000
+
+  implicit class ListDecorator[T](val xs: List[T]) extends AnyVal {
+    def filterConserve(p: T => Boolean): List[T] = {
+      def loop(xs: List[T], nrec: Int): List[T] = xs match {
+        case Nil => xs
+        case x :: xs1 =>
+          if (nrec < MaxRecursions) {
+            val ys1 = loop(xs1, nrec + 1)
+            if (p(x))
+              if (ys1 eq xs1) xs else x :: ys1
+            else
+              ys1
+          } else xs filter p
+      }
+      loop(xs, 0)
+    }
+  }
+}
+
diff --git a/src/dotty/tools/dotc/core/Denotations.scala b/src/dotty/tools/dotc/core/Denotations.scala
new file mode 100644
index 000000000..aa3768a99
--- /dev/null
+++ b/src/dotty/tools/dotc/core/Denotations.scala
@@ -0,0 +1,241 @@
+package dotty.tools.dotc
+package core
+
+import Periods._, Contexts._, Symbols._, RefSets._, Names._
+import Types._, Flags._, Decorators._
+import Scopes.Scope
+import collection.immutable.BitSet
+import collection.mutable
+import util.LRU8Cache
+
+trait Denotations { self: Context =>
+
+  /** A set for hash consing superclass bitsets */
+  private val uniqueBits = new util.HashSet[BitSet]("superbits", 1024)
+
+}
+
+object Denotations {
+
+  abstract class Denotation {
+
+    /** The validity interval of this symbol */
+    var valid: Interval = Nowhere
+
+    /** The next instance of this symbol in the same run */
+    private[core] var nextInRun: Denotation = this
+
+    /**
+     * The version of this symbol that was valid in the first phase
+     *  of this run
+     */
+    def initial: Denotation = {
+      var sym = nextInRun
+      while (sym.valid > this.valid) sym = sym.nextInRun
+      sym
+    }
+
+    def owner: Symbol = ???
+
+    def name: Name = ???
+
+    def flags: Long = ???
+
+    def setFlag(flag: Long): Unit = ???
+
+    def tpe: Type = ???
+
+    def info: Type = ???
+
+    /* Validity and instance handling:
+     *
+     * Symbols have an interval of validity, defined
+     * by their `valid` fields.
+     *
+     * There may be several symbols with different validity
+     * representing the same underlying symbol at different phases.
+     * These are called a "flock". Flock members are generated by
+     * @see SymRef.trackSym. Flock members are connected in a ring
+     * with their `nextInFlock` fields.
+     *
+     * There are the following invariants converning flock members
+     *
+     * 1) validity intervals must be non-overlapping
+     * 2) the union of all validity intervals must be a contiguous
+     *    interval starting in FirstPhaseId.
+     */
+
+    /** is this symbol a type? */
+    def isType: Boolean = false
+
+    /** is this symbol a class? */
+    def isClass: Boolean = false
+
+    /** is this symbol a method? */
+    def isMethod: Boolean = false
+
+    /** is this symbol the result of an erroneous definition? */
+    def isError: Boolean = false
+
+    def asClass: ClassDenotation = ???
+
+    def withType(tp: Type): Denotation = ???
+  }
+
+  object NameFilter {
+    final val WordSizeLog = 6
+    final val DefinedNamesWords = 16
+    final val DefinedNamesSize = DefinedNamesWords << WordSizeLog
+    final val DefinedNamesMask = DefinedNamesSize - 1
+
+    type FingerPrint = Array[Long]
+
+    def includeName(bits: FingerPrint, name: Name): Unit = {
+      val hash = name.start & DefinedNamesMask
+      bits(hash >> 6) |= (1 << hash)
+    }
+
+    def includeFingerPrint(bits1: FingerPrint, bits2: FingerPrint): Unit =
+      for (i <- 0 until DefinedNamesWords) bits1(i) |= bits2(i)
+
+    def containsName(bits: FingerPrint, name: Name): Boolean = {
+      val hash = name.start & DefinedNamesMask
+      (bits(hash >> 6) & (1 << hash)) != 0
+    }
+
+    def newNameFilter: FingerPrint = new Array[Long](DefinedNamesWords)
+  }
+
+  class ClassDenotation(parents: List[Type], decls: Scope) extends Denotation {
+
+    import NameFilter._
+
+    lazy val baseClasses: List[ClassSymbol] = ???
+
+    private var memberCacheVar: LRU8Cache[Name, RefSet] = null
+
+    private def memberCache: LRU8Cache[Name, RefSet] = {
+      if (memberCacheVar == null) memberCacheVar = new LRU8Cache
+      memberCacheVar
+    }
+
+    def thisType: Type = ???
+
+    private var superClassBitsCache: BitSet = null
+
+    private def computeSuperClassBits(implicit ctx: Context): BitSet = {
+      val b = BitSet.newBuilder
+      for (bc <- baseClasses) b += bc.superId
+      val bits = ctx.root.uniqueBits.findEntryOrUpdate(b.result())
+      superClassBitsCache = bits
+      bits
+    }
+
+    def superClassBits(implicit ctx: Context): BitSet = {
+      val bits = superClassBitsCache
+      if (bits != null) bits else computeSuperClassBits
+    }
+
+    /** Is this class a subclass of `clazz`? */
+    final def isSubClass(clazz: ClassSymbol)(implicit ctx: Context): Boolean = {
+      superClassBits contains clazz.superId
+    }
+
+    private var definedFingerPrintCache: FingerPrint = null
+
+    private def computeDefinedFingerPrint(implicit ctx: Context): FingerPrint = {
+      var bits = newNameFilter
+      var e = decls.lastEntry
+      while (e != null) {
+        includeName(bits, name)
+        e = e.prev
+      }
+      var ps = parents
+      while (ps.nonEmpty) {
+        val parent = ps.head.typeSymbol.asClass.deref
+        includeFingerPrint(bits, parent.definedFingerPrint)
+        parent setFlag Frozen
+        ps = ps.tail
+      }
+      definedFingerPrintCache = bits
+      bits
+    }
+
+    /** Enter a symbol in current scope.
+     *  Note: We require that this does not happen after the first time
+     *  someone does a findMember on a subclass.
+     */
+    def enter(sym: Symbol)(implicit ctx: Context) = {
+      require((flags & Frozen) == 0)
+      decls enter sym
+      if (definedFingerPrintCache != null)
+        includeName(definedFingerPrintCache, sym.name)
+      if (memberCacheVar != null)
+        memberCache invalidate sym.name
+    }
+
+    /** Delete symbol from current scope.
+     *  Note: We require that this does not happen after the first time
+     *  someone does a findMember on a subclass.
+     */
+    def delete(sym: Symbol)(implicit ctx: Context) = {
+      require((flags & Frozen) == 0)
+      decls unlink sym
+      if (definedFingerPrintCache != null)
+        computeDefinedFingerPrint
+      if (memberCacheVar != null)
+        memberCache invalidate sym.name
+    }
+
+    def definedFingerPrint(implicit ctx: Context): FingerPrint = {
+      val fp = definedFingerPrintCache
+      if (fp != null) fp else computeDefinedFingerPrint
+    }
+
+    final def declsNamed(name: Name)(implicit ctx: Context): RefSet = {
+      var syms: RefSet = NoType
+      var e = decls lookupEntry name
+      while (e != null) {
+        syms = syms union e.sym.refType
+        e = decls lookupNextEntry e
+      }
+      syms
+    }
+
+    final def memberRefsNamed(name: Name)(implicit ctx: Context): RefSet = {
+      var refs: RefSet = memberCache lookup name
+      if (refs == null) {
+        if (containsName(definedFingerPrint, name)) {
+          val ownRefs = declsNamed(name)
+          refs = ownRefs
+          var ps = parents
+          val ownType = thisType
+          while (ps.nonEmpty) {
+            val parentSym = ps.head.typeSymbol.asClass
+            val parent = parentSym.deref
+            refs = refs union
+              parent.memberRefsNamed(name)
+                .filterExcluded(Flags.Private)
+                .seenFrom(thisType, parentSym)
+                .filterDisjoint(ownRefs)
+            ps = ps.tail
+          }
+        } else {
+          refs = NoType
+        }
+        memberCache enter (name, refs)
+      }
+      refs
+    }
+  }
+
+  object NoDenotation extends Denotation {
+    override def owner: Symbol = throw new AssertionError("NoDenotation.owner")
+    override def name: Name = BootNameTable.newTermName("<none>")
+    override def flags: Long = 0
+    override def tpe: Type = NoType
+    override def info: Type = NoType
+  }
+
+
+}
\ No newline at end of file
diff --git a/src/dotty/tools/dotc/core/Flags.scala b/src/dotty/tools/dotc/core/Flags.scala
new file mode 100644
index 000000000..3b8f05eab
--- /dev/null
+++ b/src/dotty/tools/dotc/core/Flags.scala
@@ -0,0 +1,13 @@
+package dotty.tools.dotc.core
+
+object Flags {
+
+  type FlagSet = Long
+
+  final val Empty = 0
+
+  final val Error = 1 << 32
+  final val Frozen: Int = ???
+  final val Private: Int = ???
+
+}
\ No newline at end of file
diff --git a/src/dotty/tools/dotc/core/Names.scala b/src/dotty/tools/dotc/core/Names.scala
new file mode 100644
index 000000000..291dc2877
--- /dev/null
+++ b/src/dotty/tools/dotc/core/Names.scala
@@ -0,0 +1,223 @@
+package dotty.tools.dotc
+package core
+
+import scala.io.Codec
+import util.NameTransformer
+import Decorators._
+import Contexts._
+
+object Names {
+
+  /** A name is essentially a string, with three differences
+   *  1. Names belong in one of two universes: they are type names or term names.
+   *     The same string can correspond both to a type name and to a term name.
+   *  2. In each universe, names are hash-consed per basis. Two names
+   *     representing the same string in the same basis are always reference identical.
+   *  3. Names are intended to be encoded strings. @see dotc.util.NameTransformer.
+   *     The encoding will be applied when converting a string to a name.
+   */
+  abstract class Name {
+
+    /** The basis in which this name is stored */
+    val basis: NameTable
+
+    /** The start index in the character array */
+    val start: Int
+
+    /** The length of the names */
+    val length: Int
+
+    /** Is this name a type name? */
+    def isTypeName: Boolean
+
+    /** Is this name a term name? */
+    def isTermName: Boolean
+
+    /** This name converted to a type name */
+    def toTypeName: TypeName
+
+    /** This name converted to a term name */
+    def toTermName: TermName
+
+    /** This name downcasted to a type name */
+    def asTypeName: TypeName
+
+    /** This name downcasted to a term name */
+    def asTermName: TermName
+
+    /** This name in the given basis */
+    def in(basis: NameTable) =
+      if (this.basis eq basis) this
+      else newName(basis, this.basis.chrs, start, length)
+
+    /** Create a new name of same kind as this one, in the given
+     *  basis, with `len` characters taken from `cs` starting at `offset`.
+     */
+    protected def newName(basis: NameTable, cs: Array[Char], offset: Int, len: Int): Name
+
+    /** A dummy equals method to catch all comparisons of names
+     *  to other entities (e.g. strings).
+     *  One always should use the ==(Name) method instead.
+     */
+    final override def equals(that: Any): Boolean = ??? // do not implement
+
+    /** The only authorized == method on names */
+    def == (that: Name): Boolean = (
+      (this eq that)
+      ||
+      (this.basis ne that.basis) &&
+      (this == (that in this.basis))
+    )
+
+    override def toString = new String(basis.chrs, start, length)
+
+    /** Write to UTF8 representation of this name to given character array.
+     *  Start copying to index `to`. Return index of next free byte in array.
+     *  Array must have enough remaining space for all bytes
+     *  (i.e. maximally 3*length bytes).
+     */
+    final def copyUTF8(bs: Array[Byte], offset: Int): Int = {
+      val bytes = Codec.toUTF8(basis.chrs, start, length)
+      scala.compat.Platform.arraycopy(bytes, 0, bs, offset, bytes.length)
+      offset + bytes.length
+    }
+
+    /** Convert to string replacing operator symbols by corresponding \$op_name. */
+    def decode: String = NameTransformer.decode(toString)
+  }
+
+  class TermName(val basis: NameTable, val start: Int, val length: Int, val next: TermName) extends Name {
+    def isTypeName = false
+    def isTermName = true
+    lazy val toTypeName: TypeName = new TypeName(basis, start, length, this)
+    def toTermName = this
+    def asTypeName = throw new ClassCastException(this+" is not a type name")
+    def asTermName = this
+
+    protected def newName(basis: NameTable, cs: Array[Char], offset: Int, len: Int): Name =
+      basis.newTermName(cs, offset, len)
+  }
+
+  class TypeName(val basis: NameTable, val start: Int, val length: Int, val toTermName: TermName) extends Name {
+    def isTypeName = true
+    def isTermName = false
+    def toTypeName = this
+    def asTypeName = this
+    def asTermName = throw new ClassCastException(this+" is not a term name")
+
+    protected def newName(basis: NameTable, cs: Array[Char], offset: Int, len: Int): Name =
+      basis.newTypeName(cs, offset, len)
+  }
+
+  class NameTable {
+
+    private final val HASH_SIZE = 0x8000
+    private final val HASH_MASK = 0x7FFF
+    private final val NAME_SIZE = 0x20000
+    final val nameDebug = false
+
+    /** Memory to store all names sequentially. */
+    private[Names] var chrs: Array[Char] = new Array[Char](NAME_SIZE)
+    private var nc = 0
+
+    /** Hashtable for finding term names quickly. */
+    private val table = new Array[Names.TermName](HASH_SIZE)
+
+    /** The hashcode of a name. */
+    private def hashValue(cs: Array[Char], offset: Int, len: Int): Int =
+      if (len > 0)
+        (len * (41 * 41 * 41) +
+          cs(offset) * (41 * 41) +
+          cs(offset + len - 1) * 41 +
+          cs(offset + (len >> 1)))
+      else 0
+
+    /**
+     * Is (the ASCII representation of) name at given index equal to
+     *  cs[offset..offset+len-1]?
+     */
+    private def equals(index: Int, cs: Array[Char], offset: Int, len: Int): Boolean = {
+      var i = 0
+      while ((i < len) && (chrs(index + i) == cs(offset + i)))
+        i += 1;
+      i == len
+    }
+
+    /** Enter characters into chrs array. */
+    private def enterChars(cs: Array[Char], offset: Int, len: Int) {
+      var i = 0
+      while (i < len) {
+        if (nc + i == chrs.length) {
+          val newchrs = new Array[Char](chrs.length * 2)
+          scala.compat.Platform.arraycopy(chrs, 0, newchrs, 0, chrs.length)
+          chrs = newchrs
+        }
+        chrs(nc + i) = cs(offset + i)
+        i += 1
+      }
+      if (len == 0) nc += 1
+      else nc = nc + len
+    }
+
+    /**
+     * Create a term name from the characters in cs[offset..offset+len-1].
+     *  Assume they are already encoded.
+     */
+    def newTermName(cs: Array[Char], offset: Int, len: Int): TermName = /* sync if parallel */ {
+      val h = hashValue(cs, offset, len) & HASH_MASK
+      val next = table(h)
+      var name = next
+      while ((name ne null) && (name.length != len || !equals(name.start, cs, offset, len)))
+        name = name.next
+
+      if (name eq null) /* needs sync if parallel */ {
+        name = new TermName(this, nc, len, next)
+        enterChars(cs, offset, len)
+        table(h) = name
+        name
+      }
+
+      name
+    }
+
+    /**
+     * Create a type name from the characters in cs[offset..offset+len-1].
+     *  Assume they are already encoded.
+     */
+    def newTypeName(cs: Array[Char], offset: Int, len: Int): TypeName =
+      newTermName(cs, offset, len).toTypeName
+
+    /**
+     * Create a term name from the UTF8 encoded bytes in bs[offset..offset+len-1].
+     *  Assume they are already encoded.
+     */
+    def newTermName(bs: Array[Byte], offset: Int, len: Int): TermName = {
+      val chars = Codec.fromUTF8(bs, offset, len)
+      newTermName(chars, 0, chars.length)
+    }
+
+    /**
+     * Create a type name from the UTF8 encoded bytes in bs[offset..offset+len-1].
+     *  Assume they are already encoded.
+     */
+    def newTypeName(bs: Array[Byte], offset: Int, len: Int): TypeName =
+      newTermName(bs, offset, len).toTypeName
+
+    /** Create a term name from a string, encode if necessary*/
+    def newTermName(s: String): TermName = {
+      val es = NameTransformer.encode(s)
+      newTermName(es.toCharArray, 0, es.length)
+    }
+
+    /** Create a type name from a string, encode if necessary */
+    def newTypeName(s: String): TypeName = {
+      val es = NameTransformer.encode(s)
+      newTypeName(es.toCharArray, 0, es.length)
+    }
+  }
+
+  object BootNameTable extends NameTable
+
+  val EmptyTypeName = BootNameTable.newTypeName("")
+  val EmptyTermName = BootNameTable.newTermName("")
+}
\ No newline at end of file
diff --git a/src/dotty/tools/dotc/core/Periods.scala b/src/dotty/tools/dotc/core/Periods.scala
new file mode 100644
index 000000000..61dedb015
--- /dev/null
+++ b/src/dotty/tools/dotc/core/Periods.scala
@@ -0,0 +1,99 @@
+package dotty.tools.dotc.core
+
+import Contexts._
+
+/** Periods are the central "clock" of the compiler.
+ *  A period consists of a run id and a phase id.
+ *  run ids represent compiler runs
+ *  phase ids represent compiler phases
+ */
+abstract class Periods { self: Context =>
+  import Periods._
+
+  /** The current phase identifier */
+  def phaseId = phaseIdOf(period)
+
+  /** The current run identifier */
+  def runId = runIdOf(period)
+
+  /** A new context that differs from the current one in its period */
+  def withPeriod(pd: Period): Context =
+    if (period == pd) this
+    else new SubContext(self) {
+      override val period = pd
+    }
+
+  /** Execute `op` at given period */
+  def atPeriod[T](pd: Period)(op: Context => T)(implicit ctx: Context) =
+    op(ctx withPeriod pd)
+
+  /** Execute `op` at given phase id */
+  def atPhase[T](pid: PhaseId)(op: Context => T)(implicit ctx: Context) =
+    op(ctx withPeriod periodOf(period, pid))
+}
+
+object Periods {
+
+  /** A period is an ordinal number for a phase in a run.
+   *  Phases in later runs have higher periods than phases in earlier runs.
+   *  Later phases have higher periods than earlier phases in the same run.
+   *  Periods are coded (in big endian) as:
+   *
+   *     sign, always 0        1 bit
+   *     runid                21 bits
+   *     phase id:             5 bits
+   *     unused:               5 bits
+   */
+  type Period = Int
+  final val NoPeriod = 0
+
+  /** A period interval is an interval between two periods that share the same runid.
+   *  It is coded as follows:
+   *
+   *     sign, always 0        1 bit
+   *     runid                21 bits
+   *     last phase id:        5 bits
+   *     #phases before last:  5 bits
+   */
+  type Interval = Int
+  final val Nowhere = NoPeriod
+
+  /** An ordinal number for compiler runs. First run has number 1. */
+  type RunId = Int
+  final val NoRunId = 0
+
+  /** An ordinal number for phases. First phase has number 1. */
+  type PhaseId = Int
+  final val NoPhaseId = 0
+  final val FirstPhaseId = 1
+
+  /** The number of bits needed to encode a phase identifier. */
+  final val PhaseWidth = 5
+  final val PhaseMask = (1 << PhaseWidth) - 1
+
+  /** The run identifier of the given period. */
+  final def runIdOf(period: Period): RunId = period >>> (PhaseWidth * 2)
+
+  /** The phase identifier of the given period. */
+  final def phaseIdOf(period: Period): PhaseId = (period >>> PhaseWidth) & PhaseMask
+
+  /** The last phase of the given interval */
+  final def lastPhaseIdOf(ivl: Interval) = phaseIdOf(ivl)
+
+  /** The first phase of the given interval */
+  final def firstPhaseIdOf(ivl: Interval) = lastPhaseIdOf(ivl) - (ivl & PhaseMask)
+
+  /** Does given interval contain given period */
+  final def containsPeriod(ivl: Interval, period: Period): Boolean =
+    ((ivl - period) >>> PhaseWidth) <= (ivl & PhaseMask)
+
+  final def intervalsOverlap(ivl1: Interval, ivl2: Interval): Boolean = ???
+
+ /** The period consisting of given run id and phase id */
+  final def periodOf(rid: RunId, pid: PhaseId): Period =
+    ((rid << PhaseWidth) | pid) << PhaseWidth
+
+  /** The interval consisting of given run id, and lo/hi phase ids */
+  final def intervalOf(rid: RunId, loPid: PhaseId, hiPid: PhaseId): Interval =
+    periodOf(rid, hiPid) | (hiPid - loPid)
+}
\ No newline at end of file
diff --git a/src/dotty/tools/dotc/core/Phases.scala b/src/dotty/tools/dotc/core/Phases.scala
new file mode 100644
index 000000000..f9b8eaa9f
--- /dev/null
+++ b/src/dotty/tools/dotc/core/Phases.scala
@@ -0,0 +1,11 @@
+package dotty.tools.dotc
+package core
+
+object Phases {
+
+  abstract class Phase {
+    def erasedTypes: Boolean
+  }
+
+
+}
\ No newline at end of file
diff --git a/src/dotty/tools/dotc/core/RefSets.scala b/src/dotty/tools/dotc/core/RefSets.scala
new file mode 100644
index 000000000..04432e09f
--- /dev/null
+++ b/src/dotty/tools/dotc/core/RefSets.scala
@@ -0,0 +1,59 @@
+package dotty.tools.dotc
+package core
+
+import Symbols._, Flags._, Types._, Contexts._
+
+object RefSets {
+
+  trait RefSet {
+    def isEmpty: Boolean
+    def containsSig(sig: Signature)(implicit ctx: Context): Boolean
+    def filter(p: Symbol => Boolean)(implicit ctx: Context): RefSet
+    def filterDisjoint(syms: RefSet)(implicit ctx: Context): RefSet
+    def filterExcluded(flags: FlagSet)(implicit ctx: Context): RefSet
+    def filterAccessibleFrom(pre: Type)(implicit ctx: Context): RefSet
+    def seenFrom(pre: Type, owner: Symbol)(implicit ctx: Context): RefSet
+    def union(that: RefSet) =
+      if (this.isEmpty) that
+      else if (that.isEmpty) this
+      else RefUnion(this, that)
+  }
+
+  case class RefUnion(syms1: RefSet, syms2: RefSet) extends RefSet {
+    assert(!syms1.isEmpty && !syms2.isEmpty)
+    private def derivedUnion(s1: RefSet, s2: RefSet) =
+      if (s1.isEmpty) s2
+      else if (s2.isEmpty) s1
+      else if ((s1 eq syms2) && (s2 eq syms2)) this
+      else new RefUnion(s1, s2)
+    def isEmpty = false
+    def containsSig(sig: Signature)(implicit ctx: Context) =
+      (syms1 containsSig sig) || (syms2 containsSig sig)
+    def filter(p: Symbol => Boolean)(implicit ctx: Context) =
+      derivedUnion(syms1 filter p, syms2 filter p)
+    def filterDisjoint(syms: RefSet)(implicit ctx: Context): RefSet =
+      derivedUnion(syms1 filterDisjoint syms, syms2 filterDisjoint syms)
+    def filterExcluded(flags: FlagSet)(implicit ctx: Context): RefSet =
+      derivedUnion(syms1 filterExcluded flags, syms2 filterExcluded flags)
+    def filterAccessibleFrom(pre: Type)(implicit ctx: Context): RefSet =
+      derivedUnion(syms1 filterAccessibleFrom pre, syms2 filterAccessibleFrom pre)
+    def seenFrom(pre: Type, owner: Symbol)(implicit ctx: Context): RefSet =
+      derivedUnion(syms1.seenFrom(pre, owner), syms2.seenFrom(pre, owner))
+  }
+
+  trait RefSetSingleton extends RefSet { this: SymRef =>
+    def isEmpty = isWrong
+    def containsSig(sig: Signature)(implicit ctx: Context) =
+      signature == sig
+    def filter(p: Symbol => Boolean)(implicit ctx: Context): RefSet =
+      if (p(symbol)) this else NoType
+    def filterDisjoint(syms: RefSet)(implicit ctx: Context): RefSet =
+      if (syms.containsSig(signature)) NoType else this
+    def filterExcluded(flags: FlagSet)(implicit ctx: Context): RefSet =
+      if (symbol.hasFlag(flags)) NoType else this
+    def filterAccessibleFrom(pre: Type)(implicit ctx: Context): RefSet =
+      if (symbol.isAccessibleFrom(pre)) this else NoType
+    def seenFrom(pre: Type, owner: Symbol)(implicit ctx: Context): RefSet =
+      asSeenFrom(pre, owner).asInstanceOf[RefSet]
+  }
+}
\ No newline at end of file
diff --git a/src/dotty/tools/dotc/core/Scopes.scala b/src/dotty/tools/dotc/core/Scopes.scala
new file mode 100644
index 000000000..cc50e9072
--- /dev/null
+++ b/src/dotty/tools/dotc/core/Scopes.scala
@@ -0,0 +1,299 @@
+/* NSC -- new Scala compiler
+ * Copyright 2005-2012 LAMP/EPFL
+ * @author  Martin Odersky
+ */
+
+package dotty.tools.dotc
+package core
+
+import Symbols._
+import Names._
+import Periods._
+import Decorators._
+import Contexts._
+
+object Scopes {
+
+  /** Maximal fill factor of hash table */
+  private final val FillFactor = 2.0/3.0
+
+  /** A hashtable is created once current size exceeds MinHash * FillFactor
+   *  The initial hash table has twice that size (i.e 24).
+   */
+  private final val MinHash = 12
+
+  /** The maximal permissible number of recursions when creating
+   *  a hashtable
+   */
+  private final val MaxRecursions = 1000
+
+  class ScopeEntry private[Scopes] (val sym: Symbol, val owner: Scope) {
+
+    /** the next entry in the hash bucket
+     */
+    var tail: ScopeEntry = null
+
+    /** the preceding entry in this scope
+     */
+    var prev: ScopeEntry = null
+
+    override def toString: String = sym.toString
+  }
+
+  /** Note: constructor is protected to force everyone to use the factory methods newScope or newNestedScope instead.
+   *  This is necessary because when run from reflection every scope needs to have a
+   *  SynchronizedScope as mixin.
+   */
+  class Scope protected[Scopes](initElems: ScopeEntry, initSize: Int, val nestingLevel: Int = 0)
+      extends Iterable[Symbol] {
+
+    protected[Scopes] def this(base: Scope)(implicit ctx: Context) = {
+      this(base.lastEntry, base.size, base.nestingLevel + 1)
+      ensureCapacity(MinHash)(ctx) // WTH??? it seems the implicit is not in scope for a secondary constructor call.
+    }
+
+    def this() = this(null, 0, 0)
+
+    private[dotc] var lastEntry: ScopeEntry = initElems
+
+    /** The size of the scope */
+    private[this] var _size = initSize
+
+    override def size = _size
+    private def size_= (x: Int) = _size = x
+
+    /** the hash table
+     */
+    private var hashTable: Array[ScopeEntry] = null
+
+    /** a cache for all elements, to be used by symbol iterator.
+     */
+    private var elemsCache: List[Symbol] = null
+
+    /** Returns a new scope with the same content as this one. */
+    def cloneScope(implicit ctx: Context): Scope = newScopeWith(this.toList: _*)
+
+    /** is the scope empty? */
+    override def isEmpty: Boolean = lastEntry eq null
+
+    /** create and enter a scope entry */
+    protected def newScopeEntry(sym: Symbol)(implicit ctx: Context): ScopeEntry = {
+      val e = new ScopeEntry(sym, this)
+      e.prev = lastEntry
+      lastEntry = e
+      size += 1
+      elemsCache = null
+      if (hashTable ne null) {
+        ensureCapacity(hashTable.length)
+        enterInHash(e)
+      } else {
+        ensureCapacity(MinHash)
+      }
+      e
+    }
+
+    private def enterInHash(e: ScopeEntry)(implicit ctx: Context): Unit = {
+      val i = e.sym.name.start & (hashTable.length - 1)
+      e.tail = hashTable(i)
+      hashTable(i) = e
+    }
+
+    /** enter a symbol
+     *
+     *  @param sym ...
+     */
+    def enter[T <: Symbol](sym: T)(implicit ctx: Context): T = {
+      newScopeEntry(sym)
+      sym
+    }
+
+    /** enter a symbol, asserting that no symbol with same name exists in scope
+     *
+     *  @param sym ...
+     */
+    def enterUnique(sym: Symbol)(implicit ctx: Context) {
+      assert(lookup(sym.name) == NoSymbol, (sym.locatedFullString, lookup(sym.name).locatedFullString))
+      enter(sym)
+    }
+
+    private def ensureCapacity(tableSize: Int)(implicit ctx: Context): Unit =
+      if (size > tableSize * FillFactor) createHash(tableSize * 2)
+
+    private def createHash(tableSize: Int)(implicit ctx: Context): Unit =
+      if (size > tableSize * FillFactor) createHash(tableSize * 2)
+      else {
+        hashTable = new Array[ScopeEntry](tableSize)
+        enterAllInHash(lastEntry)
+      }
+
+    private def enterAllInHash(e: ScopeEntry, n: Int = 0)(implicit ctx: Context) {
+      if (e ne null) {
+        if (n < MaxRecursions) {
+          enterAllInHash(e.prev, n + 1)
+          enterInHash(e)
+        } else {
+          var entries: List[ScopeEntry] = List()
+          var ee = e
+          while (ee ne null) {
+            entries = ee :: entries
+            ee = ee.prev
+          }
+          entries foreach enterInHash
+        }
+      }
+    }
+
+    /** remove entry from this scope. */
+    def unlink(e: ScopeEntry)(implicit ctx: Context) {
+      if (lastEntry == e) {
+        lastEntry = e.prev
+      } else {
+        var e1 = lastEntry
+        while (e1.prev != e) e1 = e1.prev
+        e1.prev = e.prev
+      }
+      if (hashTable ne null) {
+        val index = e.sym.name.start & (hashTable.length - 1)
+        var e1 = hashTable(index)
+        if (e1 == e)
+          hashTable(index) = e.tail
+        else {
+          while (e1.tail != e) e1 = e1.tail;
+          e1.tail = e.tail
+        }
+      }
+      elemsCache = null
+      size -= 1
+    }
+
+    /** remove symbol from this scope */
+    def unlink(sym: Symbol)(implicit ctx: Context) {
+      var e = lookupEntry(sym.name)
+      while (e ne null) {
+        if (e.sym == sym) unlink(e);
+        e = lookupNextEntry(e)
+      }
+    }
+
+    /** lookup a symbol
+     *
+     *  @param name ...
+     *  @return     ...
+     */
+    def lookup(name: Name)(implicit ctx: Context): Symbol = {
+      val e = lookupEntry(name)
+      if (e eq null) NoSymbol else e.sym
+    }
+
+    /** Returns an iterator yielding every symbol with given name in this scope.
+     */
+    def lookupAll(name: Name)(implicit ctx: Context): Iterator[Symbol] = new Iterator[Symbol] {
+      var e = lookupEntry(name)
+      def hasNext: Boolean = e ne null
+      def next(): Symbol = { val r = e.sym; e = lookupNextEntry(e); r }
+    }
+
+    /** lookup a symbol entry matching given name.
+     *  @note from Martin: I believe this is a hotspot or will be one
+     *  in future versions of the type system. I have reverted the previous
+     *  change to use iterators as too costly.
+     */
+    def lookupEntry(name: Name)(implicit ctx: Context): ScopeEntry = {
+      var e: ScopeEntry = null
+      if (hashTable ne null) {
+        e = hashTable(name.start & (hashTable.length - 1))
+        while ((e ne null) && e.sym.name != name) {
+          e = e.tail
+        }
+      } else {
+        e = lastEntry
+        while ((e ne null) && e.sym.name != name) {
+          e = e.prev
+        }
+      }
+      e
+    }
+
+    /** lookup next entry with same name as this one */
+    def lookupNextEntry(entry: ScopeEntry)(implicit ctx: Context): ScopeEntry = {
+      var e = entry
+      if (hashTable ne null)
+        do { e = e.tail } while ((e ne null) && e.sym.name != entry.sym.name)
+      else
+        do { e = e.prev } while ((e ne null) && e.sym.name != entry.sym.name);
+      e
+    }
+
+    /** Return all symbols as a list in the order they were entered in this scope.
+     */
+    override def toList: List[Symbol] = {
+      if (elemsCache eq null) {
+        elemsCache = Nil
+        var e = lastEntry
+        while ((e ne null) && e.owner == this) {
+          elemsCache = e.sym :: elemsCache
+          e = e.prev
+        }
+      }
+      elemsCache
+    }
+
+    /** Vanilla scope - symbols are stored in declaration order.
+     */
+    def sorted: List[Symbol] = toList
+
+    /** Return all symbols as an iterator in the order they were entered in this scope.
+     */
+    def iterator: Iterator[Symbol] = toList.iterator
+
+    override def foreach[U](p: Symbol => U): Unit = toList foreach p
+
+    def filteredScope(p: Symbol => Boolean)(implicit ctx: Context): Scope = {
+      val unfiltered = toList
+      val filtered = unfiltered filterConserve p
+      if (filtered eq unfiltered) this
+      else newScopeWith(filtered: _*)
+    }
+
+    @deprecated("Use `toList.reverse` instead", "2.10.0")
+    def reverse: List[Symbol] = toList.reverse
+
+    override def mkString(start: String, sep: String, end: String) =
+      toList.map(_.defString).mkString(start, sep, end)
+
+    override def toString(): String = mkString("Scope{\n  ", ";\n  ", "\n}")
+  }
+
+  /** Create a new scope */
+  def newScope: Scope = new Scope()
+
+  /** Create a new scope nested in another one with which it shares its elements */
+  def newNestedScope(outer: Scope)(implicit ctx: Context): Scope = new Scope(outer)
+
+  /** Create a new scope with given initial elements */
+  def newScopeWith(elems: Symbol*)(implicit ctx: Context): Scope = {
+    val scope = newScope
+    elems foreach scope.enter
+    scope
+  }
+
+  /** Create new scope for the members of package `pkg` */
+  def newPackageScope(pkgClass: Symbol): Scope = newScope
+
+  /** Transform scope of members of `owner` using operation `op`
+   *  This is overridden by the reflective compiler to avoid creating new scopes for packages
+   */
+  def scopeTransform(owner: Symbol)(op: => Scope): Scope = op
+
+  /** The empty scope (immutable).
+   */
+  object EmptyScope extends Scope {
+    override def newScopeEntry(sym: Symbol)(implicit ctx: Context): ScopeEntry = {
+      throw new AssertionError("EmptyScope.newScopeEntry")
+    }
+  }
+
+  /** The error scope (mutable)
+   */
+  class ErrorScope(owner: Symbol) extends Scope
+}
diff --git a/src/dotty/tools/dotc/core/SymTransformers.scala b/src/dotty/tools/dotc/core/SymTransformers.scala
new file mode 100644
index 000000000..ec2e4d357
--- /dev/null
+++ b/src/dotty/tools/dotc/core/SymTransformers.scala
@@ -0,0 +1,39 @@
+package dotty.tools.dotc.core
+
+import Periods._, Denotations._, Contexts._
+import java.lang.AssertionError
+
+trait DenotationTransformers { self: RootContext =>
+
+  import DenotationTransformers._
+
+  def lastPhaseId: PhaseId
+
+  private val nxTransformer =
+    Array.fill[DenotationTransformer](lastPhaseId + 1)(NoTransformer)
+
+  object NoTransformer extends DenotationTransformer {
+    val phaseId = lastPhaseId + 1
+    def transform(enot: Denotation): Denotation =
+      throw new AssertionError("NoTransformer.transform")
+  }
+
+  def install(pid: PhaseId, trans: DenotationTransformer): Unit = {
+    if ((pid > NoPhaseId) && (nxTransformer(pid).phaseId > pid)) {
+      nxTransformer(pid) = trans
+      install(pid - 1, trans)
+    }
+  }
+
+  def nextTransformer(i: Int) = nxTransformer(i)
+}
+
+object DenotationTransformers {
+
+  abstract class DenotationTransformer {
+    val phaseId: PhaseId
+    def transform(denot: Denotation): Denotation
+  }
+
+
+}
\ No newline at end of file
diff --git a/src/dotty/tools/dotc/core/Symbols.scala b/src/dotty/tools/dotc/core/Symbols.scala
new file mode 100644
index 000000000..52cc29603
--- /dev/null
+++ b/src/dotty/tools/dotc/core/Symbols.scala
@@ -0,0 +1,275 @@
+package dotty.tools.dotc
+package core
+
+import Periods._
+import DenotationTransformers._
+import Names._
+import java.lang.AssertionError
+import Decorators._
+import Symbols._
+import Contexts._
+import Denotations._
+import Types._
+import collection.mutable
+
+trait Symbols { self: Context =>
+
+  import Symbols._
+
+  // Infrastructure to assign unique superclass idents to class symbols that are superclasses of
+  // some other class
+
+  private final val InitialSuperIdsSize = 4096
+
+  /** A map from a superclass id to the class that has it */
+  private var classOfId = Array.ofDim[ClassSymbol](InitialSuperIdsSize)
+
+  /** A map from a superclass to its superclass id */
+  private val superIdOfClass = new mutable.HashMap[ClassSymbol, Int]
+
+  /** The last allocate superclass id */
+  private var lastSuperId = -1
+
+  /** Allocate and return next free superclass id */
+  private def nextSuperId: Int = { lastSuperId += 1; lastSuperId }
+}
+
+object Symbols {
+
+
+  /**
+   * A SymRef is a period-dependent reference to a denotation.
+   *  Given a period, its `deref` method resolves to a Symbol.
+   */
+  abstract class Symbol {
+
+    def overriddenSymbol(inclass: ClassSymbol)(implicit ctx: Context): Symbol =
+      if (owner isSubClass inclass) ???
+      else NoSymbol
+
+    def isProtected: Boolean = ???
+    def isStable: Boolean = ???
+    def accessBoundary: ClassSymbol = ???
+    def isContainedIn(boundary: ClassSymbol) = ???
+    def baseClasses: List[ClassSymbol] = ???
+    def exists = true
+
+
+    def orElse(that: => Symbol) = if (exists) this else that
+
+    /** A isAbove B   iff  A can always be used instead of B
+     */
+    def isAbove(that: Symbol)(implicit ctx: Context): Boolean =
+      (that.owner isSubClass this.owner) &&
+      (this isAsAccessible that)
+
+    /** A isBelow B   iff the reference A & B can always be simplified to A
+     */
+    def isBelow(that: Symbol)(implicit ctx: Context): Boolean =
+      (this.owner isSubClass that.owner) ||
+      (this isAsAccessible that)
+
+    def isAsAccessible(that: Symbol)(implicit ctx: Context): Boolean =
+      !this.isProtected && !that.isProtected && // protected members are incomparable
+      (that.accessBoundary isContainedIn this.accessBoundary) &&
+      this.isStable || !that.isStable
+
+
+    /** Set the denotation of this symbol.
+     */
+    def setDenotation(denot: Denotation) =
+      lastDenot = denot
+
+    /** The last denotation of this symbol */
+    protected[this] var lastDenot: Denotation = null
+
+    /** Load denotation of this symbol */
+    protected def loadDenot(implicit ctx: Context): Denotation
+
+    /** The denotation of this symbol
+     */
+    def deref(implicit ctx: Context): Denotation = {
+      val denot = lastDenot
+      if (denot != null && containsPeriod(denot.valid, ctx.period))
+        denot
+      else
+        trackedDenot
+    }
+
+    /** Get referenced denotation if lastDenot points to a different instance */
+    private def trackedDenot(implicit ctx: Context): Denotation = {
+      var denot = lastDenot
+      if (denot == null) {
+        denot = loadDenot
+      } else {
+        val currentPeriod = ctx.period
+        val valid = denot.valid
+        val currentRunId = runIdOf(currentPeriod)
+        val validRunId = runIdOf(valid)
+        if (currentRunId != validRunId) {
+          reloadDenot
+        } else if (currentPeriod > valid) {
+          // search for containing interval as long as nextInRun
+          // increases.
+          var nextDenot = denot.nextInRun
+          while (nextDenot.valid > valid && !containsPeriod(nextDenot.valid, currentPeriod)) {
+            denot = nextDenot
+            nextDenot = nextDenot.nextInRun
+          }
+          if (nextDenot.valid > valid) {
+            // in this case, containsPeriod(nextDenot.valid, currentPeriod)
+            denot = nextDenot
+          } else {
+            // not found, denot points to highest existing variant
+            var startPid = lastPhaseIdOf(denot.valid) + 1
+            val endPid = ctx.root.nextTransformer(startPid + 1).phaseId - 1
+            nextDenot = ctx.root.nextTransformer(startPid) transform denot
+            if (nextDenot eq denot)
+              startPid = firstPhaseIdOf(denot.valid)
+            else {
+              denot.nextInRun = nextDenot
+              denot = nextDenot
+            }
+            denot.valid = intervalOf(currentRunId, startPid, endPid)
+          }
+        } else {
+          // currentPeriod < valid; in this case a denotation must exist
+          do {
+            denot = denot.nextInRun
+          } while (!containsPeriod(denot.valid, currentPeriod))
+        }
+      }
+       denot
+    }
+
+    /**
+     * Get loaded denotation if lastDenot points to a denotation from
+     *  a different run.
+     */
+    private def reloadDenot(implicit ctx: Context): Denotation = {
+      val initDenot = lastDenot.initial
+      val newSym: Symbol =
+        ctx.atPhase(FirstPhaseId) { implicit ctx =>
+          def relink(ref: RefType): Symbol = ref match {
+            case ref: SymRef => ref.symbol
+            case OverloadedType(variants) => relink(variants(refType.signature))
+          }
+          relink(initDenot.owner.info.decl(initDenot.name))
+        }
+      if (newSym eq this) { // no change, change validity
+        var d = initDenot
+        do {
+          d.valid = intervalOf(ctx.runId, firstPhaseIdOf(d.valid), lastPhaseIdOf(d.valid))
+          d = d.nextInRun
+        } while (d ne initDenot)
+      }
+      newSym.deref
+    }
+
+    def isType: Boolean
+    def isTerm = !isType
+
+    def refType(implicit ctx: Context): SymRef = SymRef(owner.thisType, this)
+
+    // forwarders for sym methods
+    def owner(implicit ctx: Context): Symbol = deref.owner
+    def name(implicit ctx: Context): Name = deref.name
+    def flags(implicit ctx: Context): Long = deref.flags
+    def info(implicit ctx: Context): Type = deref.info
+    def tpe(implicit ctx: Context): Type = info
+
+    def prefix(implicit ctx: Context) = owner.thisType
+    def allOverriddenSymbols: Iterator[Symbol] = ???
+    def isAsAccessibleAs(other: Symbol): Boolean = ???
+    def isAccessibleFrom(pre: Type)(implicit ctx: Context): Boolean = ???
+    def locationString: String = ???
+    def locatedFullString: String = ???
+    def defString: String = ???
+    def typeParams: List[TypeSymbol] = ???
+    def thisType: Type = ???
+    def isStaticMono = isStatic && typeParams.isEmpty
+    def isPackageClass: Boolean = ???
+    def isRoot: Boolean = ???
+    def moduleClass: Symbol = ???
+    def cloneSymbol: Symbol = ???
+
+    def asTerm: TermSymbol = ???
+    def asType: TypeSymbol = ???
+    def asClass: ClassSymbol = ???
+    def isStatic: Boolean = ???
+    def isTypeParameter: Boolean = ???
+    def isOverridable: Boolean = ???
+    def isCovariant: Boolean = ???
+    def isContravariant: Boolean = ???
+    def isSkolem: Boolean = ???
+
+    def isSubClass(that: Symbol): Boolean = ???
+    def isNonBottomSubClass(that: Symbol): Boolean = ???
+    def isProperSubClass(that: Symbol): Boolean =
+      (this ne that) && (this isSubClass that)
+
+    def isAbstractType: Boolean = ???
+    def newAbstractType(name: TypeName, info: TypeBounds): TypeSymbol = ???
+    def newAbstractTerm(name: TermName, tpe: Type): TypeSymbol = ???
+
+    def isClass: Boolean = false
+    def isMethod(implicit ctx: Context): Boolean = deref.isMethod
+    def hasFlag(required: Long)(implicit ctx: Context): Boolean = (flags & required) != 0
+    def hasAllFlags(required: Long)(implicit ctx: Context): Boolean = (flags & required) == flags
+  }
+
+  abstract class TermSymbol extends Symbol {
+    def name: TermName
+    def isType = true
+  }
+
+  trait RefinementSymbol extends Symbol {
+    override def deref(implicit ctx: Context) = lastDenot
+  }
+
+  abstract class RefinementTermSymbol extends TermSymbol with RefinementSymbol
+
+  abstract class RefinementTypeSymbol extends TypeSymbol with RefinementSymbol
+
+  abstract class TypeSymbol extends Symbol {
+    def name: TypeName
+    def isType = false
+  }
+
+  abstract class ClassSymbol extends TypeSymbol {
+    override def isClass = true
+    private var superIdHint: Int = -1
+
+    override def deref(implicit ctx: Context): ClassDenotation = ???
+
+    def typeOfThis(implicit ctx: Context): Type = ???
+
+    /** The unique, densely packed identifier of this class symbol. Should be called
+     *  only if class is a super class of some other class.
+     */
+    def superId(implicit ctx: Context): Int = {
+      val hint = superIdHint
+      val rctx = ctx.root
+      if (hint >= 0 && hint <= rctx.lastSuperId && (rctx.classOfId(hint) eq this)) hint
+      else {
+        val id = rctx.superIdOfClass get this match {
+          case Some(id) =>
+            id
+          case None =>
+            val id = rctx.nextSuperId
+            rctx.superIdOfClass(this) = id
+            rctx.classOfId(id) = this
+            id
+        }
+        superIdHint = id
+        id
+      }
+    }
+  }
+
+  object NoSymbol extends Symbol {
+    def loadDenot(implicit ctx: Context): Denotation = NoDenotation
+    override def exists = false
+    def isType = false
+  }
+}
\ No newline at end of file
diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala
new file mode 100644
index 000000000..f11bc5cff
--- /dev/null
+++ b/src/dotty/tools/dotc/core/Types.scala
@@ -0,0 +1,943 @@
+package dotty.tools.dotc
+package core
+
+import util.HashSet
+import Symbols._
+import Flags._
+import Names._
+import Scopes._
+import Constants._
+import Contexts._
+import Annotations._
+import RefSets._
+import Periods._
+import scala.util.hashing.{MurmurHash3 => hashing}
+import collection.mutable
+
+trait Types { self: Context =>
+
+  import Types._
+
+  private val initialUniquesCapacity = 50000
+
+  private[Types] val uniques = new util.HashSet[Type]("uniques", initialUniquesCapacity) {
+    override def hash(x: Type): Int = x.hash
+  }
+
+}
+
+object Types {
+
+  /** The signature of a reference.
+   *  Overloaded references with the same name are distinguished by
+   *  their signatures. A signature is a list of the fully qualified names
+   *  of the type symbols of the erasure of the parameters of the
+   *  reference. For instance a reference to the definition
+   *
+   *      def f(x: Int)(y: List[String]): String
+   *
+   *  would have signature
+   *
+   *      List("scala.Int".toTypeName, "scala.collection.immutable.List".toTypeName)
+   */
+  type Signature = List[TypeName]
+
+  val NullSignature = List(Names.EmptyTypeName)
+
+  /** The variants constituting an overloaded reference.
+   *  This is a set of non-overloaded references indexed by their
+   *  signatures. All instances of Variants are assumed to
+   *  have NoSymbol as default value.
+   */
+  type Variants = Map[Signature, RefType]
+
+  /** The canonical creator of variants maps.
+   *  Note that it adds NoSymbol as default value.
+   */
+  def Variants(bindings: (Signature, RefType)*): Variants =
+    Map(bindings: _*) withDefaultValue NoType
+
+  abstract class Type {
+
+    def <:< (that: Type): Boolean = ???
+
+    def hash = NotCached
+
+    /** The type symbol associated with the type
+     */
+    def typeSymbol: Symbol = NoSymbol
+
+    /** The term symbol associated with the type
+     */
+    def termSymbol: Symbol = NoSymbol
+
+    /** Does this type denote a stable reference (i.e. singleton type)? */
+    def isStableType: Boolean = false
+
+    /** Is this type dangerous (i.e. it might contain conflicting
+     *  type information when empty, so that it can be constructed
+     *  so that type unsoundness results.) A dangerous type has an underlying
+     *  type of the form T_1 with T_n { decls }, where one of the
+     *  T_i (i > 1) is an abstract type.
+     */
+    def isVolatile: Boolean = false
+
+    /** Is this type guaranteed not to have `null` as a value? */
+    def isNotNull: Boolean = false
+
+    /** Is this type produced as a repair for an error? */
+    def isError(implicit ctx: Context): Boolean = (typeSymbol hasFlag Error) || (termSymbol hasFlag Error)
+
+    /** Is some part of this type produced as a repair for an error? */
+    def isErroneous(implicit ctx: Context): Boolean = exists(_.isError)
+
+    /** Returns true if there is a part of this type that satisfies predicate `p`.
+     */
+    def exists(p: Type => Boolean): Boolean =
+      new ExistsAccumulator(p)(false, this)
+
+    /** For a class or intersection type, its parents.
+     *  For a TypeBounds type, the parents of its hi bound.
+     *  inherited by typerefs, singleton types, and refinement types,
+     *  The empty list for all other types */
+    def parents: List[Type] = List()
+
+    def bounds(implicit ctx: Context): TypeBounds = TypeBounds(this, this)
+
+    def decl(name: Name)(implicit ctx: Context): RefType =
+      findClassDecl(name, typeSymbol.thisType, Flags.Empty)
+
+    // need: NoSymbol is as good as any other
+    def isAsGood(tp1: Type, tp2: Type)(implicit ctx: Context): Boolean = ???
+
+    def member(name: Name)(implicit ctx: Context): Type =
+      findMember(name, this, Flags.Empty)
+
+    def nonPrivateMember(name: Name)(implicit ctx: Context): Type =
+      findMember(name, this, Flags.Private)
+
+    def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): RefType =
+      throw new AssertionError(s"cannot find members of $this")
+
+    protected def findClassMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): RefType =
+      findMemberAmong(typeSymbol.asClass.deref.memberRefsNamed(name), pre, excluded)
+
+    protected def findClassDecl(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): RefType =
+      findMemberAmong(typeSymbol.asClass.deref.declsNamed(name), pre, excluded)
+
+    private def findMemberAmong(candidates: RefSet, pre: Type, excluded: FlagSet)(implicit ctx: Context): RefType = {
+      val resultSyms = candidates.filterAccessibleFrom(pre).filterExcluded(excluded)
+      def makeRef(refs: RefSet): RefType = refs match {
+        case RefUnion(refs1, refs2) => makeRef(refs1) ref_& makeRef(refs2)
+        case ref: SymRef => ref
+      }
+      if (resultSyms.isEmpty) ErrorRefType // todo: refine
+      else makeRef(resultSyms)
+    }
+
+    def memberType(sym: Symbol): Type = ???
+    def memberInfo(sym: Symbol): Type = ???
+
+    def widen: Type = ???
+
+    def deconst: Type = ???
+
+    def prefix(implicit ctx: Context): Type = ???
+
+    def isTrivial: Boolean = ???
+
+    def resultType: Type = ???
+
+    def isCachable: Boolean = false
+
+    def asSeenFrom(pre: Type, clazz: Symbol)(implicit ctx: Context): Type =
+      if (this.isTrivial || clazz.isStaticMono) this
+      else new AsSeenFromMap(pre, clazz) apply (this)
+
+    def subst(from: List[Symbol], to: List[Type]): Type = ???
+    def subst(from: PolyType, to: PolyType): Type = ???
+    def subst(from: MethodType, to: MethodType): Type = ???
+    def substSym(from: List[Symbol], to: List[Symbol]): Type = ???
+
+    def baseType(clazz: Symbol): Type = ???
+
+    def typeParams: List[TypeSymbol] = ???
+
+    def effectiveBounds: TypeBounds = ???
+    def isWrong: Boolean = ???
+
+    def & (that: Type)(implicit ctx: Context): Type =
+      if (this eq that) this
+      else if (this.isWrong) that
+      else if (that.isWrong) this
+      else (this, that) match {
+        case (_, OrType(that1, that2)) =>
+          this & that1 | this & that2
+        case (OrType(this1, this2), _) =>
+          this1 & that | this2 & that
+        case _ =>
+          val t1 = lower(this, that)
+          if (t1 ne that) t1
+          else {
+            val t2 = lower(that, this)
+            if (t2 ne this) t2
+            else AndType(this, that)
+          }
+      }
+
+   def | (that: Type)(implicit ctx: Context): Type =
+      if (this eq that) this
+      else if (this.isWrong) this
+      else if (that.isWrong) that
+      else {
+        val t1 = higher(this, that)
+        if (t1 ne that) t1
+        else {
+          val t2 = higher(that, this)
+          if (t2 ne this) t2
+          else {
+            val t1w = t1.widen
+            val t2w = t2.widen
+            if ((t1w ne t1) || (t2w ne t2)) t1w | t2w
+            else OrType(this, that)
+          }
+        }
+      }
+
+   private def lower(t1: Type, t2: Type)(implicit ctx: Context): Type =
+      if (t1 <:< t2) t1
+      else t2 match {
+        case t2 @ AndType(t21, t22) => t2.derivedAndType(lower(t1, t21), lower(t1, t22))
+        case _ => t2
+      }
+
+    private def higher(t1: Type, t2: Type)(implicit ctx: Context): Type =
+      if (t2 <:< t1) t1
+      else t2 match {
+        case t2 @ OrType(t21, t22) => t2.derivedOrType(higher(t1, t21), higher(t1, t22))
+        case _ => t2
+      }
+
+    // hashing
+
+    def correctHash(h: Int) = if (h == NotCached) NotCachedAlt else h
+
+    def hashSeed = correctHash(getClass.hashCode)
+
+    protected def doHash(seed: Int, tp: Type): Int =
+      if (seed == NotCached) NotCached
+      else {
+        val elemHash = tp.hash
+        if (elemHash == NotCached) NotCached
+        else correctHash(hashing.mix(seed, elemHash))
+      }
+
+    protected def doHash(seed: Int, x: Any): Int =
+      if (seed == NotCached) NotCached
+      else {
+        val elemHash = x.hashCode
+        if (elemHash == NotCached) NotCached
+        else correctHash(hashing.mix(seed, elemHash))
+      }
+
+    protected def doHash(seed: Int, tps: List[Type]): Int =
+      if (seed == NotCached) NotCached
+      else {
+        var h = seed
+        var xs = tps
+        while (xs.nonEmpty) {
+          val elemHash = xs.head.hash
+          if (elemHash == NotCached) return NotCached
+          h = hashing.mix(h, elemHash)
+          xs = xs.tail
+        }
+        correctHash(h)
+    }
+
+    protected def doHash(seed: Int, variants: Variants): Int =
+      if (seed == NotCached) NotCached
+      else {
+        var h = seed
+        val it = variants.valuesIterator
+        while (it.hasNext) {
+          val elemHash = it.next.hash
+          if (elemHash == NotCached) return NotCached
+          h = hashing.mix(h, elemHash)
+        }
+        correctHash(h)
+    }
+
+    protected def finishHash(hashCode: Int, arity: Int): Int =
+      correctHash(hashing.finalizeHash(hashCode, arity))
+
+    protected def hash1(x: Any): Int =
+      finishHash(doHash(hashSeed, x), 1)
+
+    protected def hash2(tp1: Type, tp2: Type) =
+      finishHash(doHash(doHash(hashSeed, tp1), tp2), 2)
+
+  } // end Type
+
+  abstract class UniqueType extends Type {
+    final override val hash = computeHash
+    def computeHash: Int
+  }
+
+  def unique[T <: Type](tp: T)(implicit ctx: Context): T = {
+    if (tp.hash == NotCached) tp
+    else ctx.root.uniques.findEntryOrUpdate(tp).asInstanceOf[T]
+  }
+
+
+  trait RefType extends Type {
+    def signature(implicit ctx: Context): Signature =
+      throw new UnsupportedOperationException(this.getClass+".signature")
+
+    def orElse(alt: => RefType): RefType = if (isWrong) alt else this
+
+    def ref_& (that: RefType)(implicit ctx: Context): RefType =
+      if (this eq that) this
+      else if (this.isWrong) that
+      else if (that.isWrong) this
+      else (this, that) match {
+        case (OverloadedType(vs1), OverloadedType(vs2)) =>
+          OverloadedType(conj(vs1, vs2))
+        case (_, OverloadedType(vs2)) =>
+          OverloadedType(vs2 updated (this.signature, this ref_& vs2(this.signature)))
+        case (OverloadedType(vs1), _) =>
+          OverloadedType(vs1 updated (that.signature, vs1(that.signature) ref_& that))
+        case (this1 @ TypeRef(pre1, sym1), that1 @ TypeRef(pre2, sym2)) =>
+          val rawtpe =
+            if (sym1.isAbstractType) this1
+            else if (sym2.isAbstractType) that1
+            else
+              TypeRef(pre1, sym1.owner.newAbstractType(sym1.name.asTypeName, sym1.info.bounds))
+          rawtpe withInfo (this1.bounds & that1.bounds)
+        case (this1 @ TermRef(pre1, sym1), that1 @ TermRef(pre2, sym2)) =>
+          if ((this.signature != that.signature))
+            OverloadedType(Variants(this.signature -> this, that.signature -> that))
+          else
+            TermRef(this1.prefix, sym1, this1.info & that1.info)
+      }
+
+    def ref_| (that: RefType)(implicit ctx: Context): RefType =
+      if (this eq that) this
+      else if (this.isWrong) this
+      else if (that.isWrong) that
+      else (this, that) match {
+        case (OverloadedType(vs1), OverloadedType(vs2)) =>
+          OverloadedType(disj(vs1, vs2))
+        case (_, OverloadedType(vs2)) =>
+          this ref_| vs2(this.signature)
+        case (OverloadedType(vs1), _) =>
+          vs1(that.signature) ref_| that
+        case (this1 @ TypeRef(pre1, sym1), that1 @ TypeRef(pre2, sym2)) =>
+          val rbounds = this1.bounds | that1.bounds
+          val rsym = lubSym(pre1, sym1, sym2) orElse {
+            val rpre = RefinedType(pre1, newScope)
+            val rsym = rpre.typeSymbol.newAbstractType(sym1.name, rbounds)
+            rpre.decls.enter(rsym)
+            rsym
+          }
+          TypeRef(pre1, rsym.asType)
+        case (this1 @ TermRef(pre1, sym1), that1 @ TermRef(pre2, sym2)) =>
+          val rtpe = this1.info | that1.info
+          val rsym = lubSym(pre1, sym1, sym2) orElse {
+            val rpre = RefinedType(pre1, newScope)
+            val rsym = rpre.typeSymbol.newAbstractTerm(sym1.name, rtpe)
+            rpre.decls.enter(rsym)
+            rsym
+          }
+          TermRef(pre1, rsym.asTerm)
+      }
+
+    /** Conjunction of two variants sets */
+    private def conj(vs1: Variants, vs2: Variants)(implicit ctx: Context): Variants =
+      Variants(
+        ((vs1.keySet | vs2.keySet) map (sig => (sig -> (vs1(sig) ref_& vs2(sig))))).toSeq: _*)
+
+    /** Disjunction of two variants sets */
+    private def disj(vs1: Variants, vs2: Variants)(implicit ctx: Context): Variants =
+      Variants(
+        ((vs1.keySet & vs2.keySet) map (sig => (sig -> (vs1(sig) ref_| vs2(sig))))).toSeq: _*)
+
+    private def lubSym(pre: Type, sym1: Symbol, sym2: Symbol)(implicit ctx: Context): Symbol = {
+      def qualifies(sym: Symbol) =
+        (sym isAccessibleFrom pre) && (sym2.owner isSubClass sym.owner)
+      sym1.allOverriddenSymbols find qualifies getOrElse NoSymbol
+    }
+  }
+
+  case class OverloadedType(variants: Variants) extends UniqueType with RefType {
+    override def computeHash: Int = finishHash(doHash(hashSeed, variants), variants.size)
+  }
+
+  abstract class SymRef extends SubType with RefType with RefSetSingleton {
+    def prefix: Type
+    def symbol: Symbol
+
+    def isType: Boolean = symbol.isType
+    def isTerm = !isType
+
+    protected var infoVar: Type = null
+
+    def info(implicit ctx: Context): Type = {
+      if (infoVar == null) infoVar = symbol.info.asSeenFrom(prefix, symbol.owner)
+        infoVar
+    }
+
+    def widen(implicit ctx: Context): Type = if (symbol.isTerm) info.widen else this
+
+    def derivedSymRef(pre: Type, sym: Symbol)(implicit ctx: Context): Type =
+      if (pre eq prefix)
+        this
+      else if (sym.isOverridable && (sym.owner ne pre.typeSymbol))
+        pre.nonPrivateMember(sym.name)
+      else
+        SymRef(pre, sym)
+
+    def underlying(implicit ctx: Context) = info
+
+    override def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): RefType =
+      if (symbol.isClass) findClassMember(name, pre, excluded)
+      else info.findMember(name, pre, excluded)
+
+    def withInfo(newinfo: Type)(implicit ctx: Context): SymRef =
+     if (info eq newinfo) this else SymRef(prefix, symbol, info)
+
+    override def computeHash = finishHash(doHash(doHash(hashSeed, prefix), symbol), 2)
+  }
+
+  abstract case class TypeRef(prefix: Type, symbol: TypeSymbol) extends SymRef {
+    override def typeSymbol = symbol
+    override def signature(implicit ctx: Context): Signature = NullSignature
+  }
+
+  final class UniqueTypeRef(prefix: Type, symbol: TypeSymbol) extends TypeRef(prefix, symbol)
+
+  abstract case class TermRef(prefix: Type, symbol: TermSymbol) extends SymRef {
+    override def termSymbol = symbol
+    private var signatureVar: Signature = null
+    private var signatureRun: RunId = NoRunId
+    override def signature(implicit ctx: Context): Signature = {
+      def paramSig(tp: Type): TypeName = ???
+      def resultSig(tp: Type): Signature = {
+        val s = sig(tp)
+        if (s eq NullSignature) Nil else s
+      }
+      def sig(tp: Type): Signature = tp match {
+        case tp: PolyType =>
+          resultSig(tp.resultType)
+        case tp: MethodType =>
+          (tp.paramTypes map paramSig) ::: resultSig(tp.resultType)
+        case _ => NullSignature
+      }
+      if (signatureRun != ctx.runId) {
+        signatureVar = sig(info)
+        signatureRun = ctx.runId
+      }
+      signatureVar
+    }
+  }
+
+  final class UniqueTermRef(prefix: Type, symbol: TermSymbol) extends TermRef(prefix, symbol)
+
+  object SymRef {
+    def apply(prefix: Type, sym: Symbol)(implicit ctx: Context): SymRef =
+      if (sym.isType) TypeRef(prefix, sym.asType) else TermRef(prefix, sym.asTerm)
+    def apply(prefix: Type, sym: Symbol, info: Type)(implicit ctx: Context): SymRef = {
+      if (sym.isType) TypeRef(prefix, sym.asType, info) else TermRef(prefix, sym.asTerm, info)
+    }
+  }
+
+  object TypeRef {
+    def apply(prefix: Type, sym: TypeSymbol)(implicit ctx: Context): TypeRef =
+      unique(new UniqueTypeRef(prefix, sym))
+    def apply(prefix: Type, sym: TypeSymbol, info: Type)(implicit ctx: Context): TypeRef = {
+      val ref = apply(prefix, sym)
+      ref.infoVar = info
+      ref
+    }
+  }
+
+  object TermRef {
+    def apply(prefix: Type, sym: TermSymbol)(implicit ctx: Context): TermRef =
+      unique(new UniqueTermRef(prefix, sym))
+    def apply(prefix: Type, sym: TermSymbol, info: Type)(implicit ctx: Context): TermRef = {
+      val ref = apply(prefix, sym)
+      ref.infoVar = info
+      ref
+    }
+
+    def make(pre: Type, sym: TermSymbol)(implicit ctx: Context) =
+      if (ctx.phase.erasedTypes) sym.tpe.resultType
+      else TermRef(pre, sym) // was more complicated; see singleType
+  }
+
+  abstract case class AppliedType(tycon: Type, typeArgs: List[Type]) extends UniqueType {
+    assert(tycon.typeParams.length == typeArgs.length)
+    def derivedAppliedType(tc: Type, args: List[Type])(implicit ctx: Context): Type =
+      if ((tc eq tycon) && (args eq typeArgs)) this
+      else AppliedType(tc, args)
+
+    override def computeHash = finishHash(doHash(doHash(hashSeed, tycon), typeArgs), 2)
+  }
+
+  final class UniqueAppliedType(tycon: Type, typeArgs: List[Type]) extends AppliedType(tycon, typeArgs)
+
+  object AppliedType {
+    def apply(tycon: Type, typeArgs: List[Type])(implicit ctx: Context) =
+      unique(new UniqueAppliedType(tycon, typeArgs))
+  }
+
+  abstract case class AndType(tp1: Type, tp2: Type) extends UniqueType {
+    def derivedAndType(t1: Type, t2: Type)(implicit ctx: Context) =
+      if ((t1 eq tp1) && (t2 eq tp2)) this
+      else AndType(tp1, tp2)
+
+    override def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): RefType =
+      (tp1 findMember (name, pre, excluded)) ref_& (tp2 findMember (name, pre, excluded))
+
+    override def computeHash = hash2(tp1, tp2)
+  }
+
+  final class UniqueAndType(tp1: Type, tp2: Type) extends AndType(tp1, tp2)
+
+  object AndType {
+    def apply(tp1: Type, tp2: Type)(implicit ctx: Context) =
+      unique(new UniqueAndType(tp1, tp2))
+  }
+
+  abstract case class OrType(tp1: Type, tp2: Type) extends UniqueType {
+    def derivedOrType(t1: Type, t2: Type)(implicit ctx: Context) =
+      if ((t1 eq tp1) && (t2 eq tp2)) this
+      else OrType(tp1, tp2)
+
+    override def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): RefType =
+      tp1.findMember(name, pre, excluded) ref_| tp2.findMember(name, pre, excluded)
+
+    override def computeHash = hash2(tp1, tp2)
+  }
+
+  final class UniqueOrType(tp1: Type, tp2: Type) extends OrType(tp1, tp2)
+
+  object OrType {
+    def apply(tp1: Type, tp2: Type)(implicit ctx: Context) =
+      unique(new UniqueOrType(tp1, tp2))
+  }
+
+  case object NoType extends SymRef {
+    def prefix = NoPrefix
+    def symbol = NoSymbol
+  }
+
+  case object NoPrefix extends UniqueType {
+    override def computeHash = hashSeed
+  }
+
+  abstract class ErrorType extends Type
+
+  object ErrorType extends ErrorType
+  object ErrorRefType extends ErrorType with RefType
+
+  trait SubType extends UniqueType {
+    def underlying(implicit ctx: Context): Type
+  }
+
+  abstract class SingletonType extends SubType
+
+  abstract case class ThisType(clazz: ClassSymbol) extends SingletonType {
+    def underlying(implicit ctx: Context) = clazz.typeOfThis
+    override def computeHash = finishHash(doHash(hashSeed, clazz), 1)
+  }
+
+  final class UniqueThisType(clazz: ClassSymbol) extends ThisType(clazz)
+
+  object ThisType {
+    def apply(clazz: ClassSymbol)(implicit ctx: Context) =
+      unique(new UniqueThisType(clazz))
+  }
+
+  abstract case class SuperType(thistpe: Type, supertpe: Type) extends SingletonType {
+    def derivedSuperType(thistp: Type, supertp: Type)(implicit ctx: Context) =
+      if ((thistp eq thistpe) && (supertp eq supertpe)) this
+      else SuperType(thistp, supertp)
+    def underlying(implicit ctx: Context) = supertpe
+    override def computeHash = hash2(thistpe, supertpe)
+  }
+
+  final class UniqueSuperType(thistpe: Type, supertpe: Type) extends SuperType(thistpe, supertpe)
+
+  object SuperType {
+    def apply(thistpe: Type, supertpe: Type)(implicit ctx: Context) =
+      unique(new UniqueSuperType(thistpe, supertpe))
+  }
+
+  abstract case class ConstantType(value: Constant) extends SingletonType {
+    def underlying(implicit ctx: Context) = value.tpe
+    override def computeHash = hash1(value)
+  }
+
+  final class UniqueConstantType(value: Constant) extends ConstantType(value)
+
+  object ConstantType {
+    def apply(value: Constant)(implicit ctx: Context) =
+      unique(new UniqueConstantType(value))
+  }
+
+  case class RefinedType(parent: Type, decls: Scope) extends Type { // can make uniquetype ??? but need to special-case symbols
+    def derivedRefinedType(parent1: Type, decls1: Scope): RefinedType =
+      if ((parent1 eq parent) && (decls1 eq decls)) this
+      else RefinedType(parent1, decls1)
+
+    override def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): RefType =
+      findClassDecl(name, pre, excluded) orElse parent.findMember(name, pre, excluded)
+  }
+
+  abstract case class MethodType(paramNames: List[TermName], paramTypes: List[Type], resultTypeExp: MethodType => Type) extends UniqueType {
+    override lazy val resultType = resultTypeExp(this)
+    lazy val isDependent = resultType exists {
+      case MethodParam(mt, _) => mt eq this
+      case _ => false
+    }
+    def instantiate(argTypes: List[Type])(implicit ctx: Context): Type =
+      if (isDependent) new InstMethodMap(this, argTypes) apply resultType
+      else resultType
+    override def computeHash =
+      finishHash(doHash(doHash(doHash(hashSeed, paramNames), paramTypes), resultType), paramTypes.length + 2)
+  }
+
+  final class UniqueMethodType(paramNames: List[TermName], paramTypes: List[Type], resultTypeExp: MethodType => Type) extends MethodType(paramNames, paramTypes, resultTypeExp)
+
+  object MethodType {
+    def apply(paramNames: List[TermName], paramTypes: List[Type], resultTypeExp: MethodType => Type)(implicit ctx: Context) =
+      unique(new UniqueMethodType(paramNames, paramTypes, resultTypeExp))
+  }
+
+  abstract case class ExprType(override val resultType: Type) extends UniqueType {
+    def derivedExprType(rt: Type)(implicit ctx: Context) =
+      if (rt eq resultType) this else ExprType(rt)
+    override def computeHash = hash1(resultType)
+  }
+
+  final class UniqueExprType(resultType: Type) extends ExprType(resultType)
+
+  object ExprType {
+    def apply(resultType: Type)(implicit ctx: Context) =
+      unique(new UniqueExprType(resultType))
+  }
+
+  case class PolyType(paramNames: List[TypeName], paramBoundsExp: PolyType => List[TypeBounds], resultTypeExp: PolyType => Type) extends Type {
+    lazy val paramBounds = paramBoundsExp(this)
+    override lazy val resultType = resultTypeExp(this)
+
+    def derivedPolyType(pnames: List[TypeName], pboundsExp: PolyType => List[TypeBounds], restpeExp: PolyType => Type): Type = {
+      val restpe = PolyType(pnames, pboundsExp, restpeExp)
+      if ((pnames eq paramNames) &&
+          (pboundsExp(this) eq paramBounds) &&
+          (restpeExp(this) eq resultType)) this
+      else restpe
+    }
+    def instantiate(argTypes: List[Type])(implicit ctx: Context): Type =
+      new InstPolyMap(this, argTypes) apply resultType
+  }
+
+  case class MethodParam(mt: MethodType, paramNum: Int) extends SingletonType {
+    def underlying(implicit ctx: Context) = mt.paramTypes(paramNum)
+    override def computeHash = NotCached
+  }
+
+  case class PolyParam(pt: PolyType, paramNum: Int) extends Type {
+  }
+
+  abstract case class TypeBounds(lo: Type, hi: Type) extends UniqueType {
+    def derivedTypeBounds(lo1: Type, hi1: Type)(implicit ctx: Context) =
+      if ((lo1 eq lo) && (hi1 eq hi)) this
+      else TypeBounds(lo, hi)
+
+    def & (that: TypeBounds)(implicit ctx: Context): TypeBounds =
+      TypeBounds(this.lo | that.lo, this.hi & that.hi)
+    def | (that: TypeBounds)(implicit ctx: Context): TypeBounds =
+      TypeBounds(this.lo & that.lo, this.hi | that.hi)
+    override def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): RefType =
+      hi.findMember(name, pre, excluded)
+    def map(f: Type => Type)(implicit ctx: Context): TypeBounds =
+      TypeBounds(f(lo), f(hi))
+    override def computeHash = hash2(lo, hi)
+  }
+
+  final class UniqueTypeBounds(lo: Type, hi: Type) extends TypeBounds(lo, hi)
+
+  object TypeBounds {
+    def apply(lo: Type, hi: Type)(implicit ctx: Context) =
+      unique(new UniqueTypeBounds(lo, hi))
+  }
+
+  case class AnnotatedType(annots: List[AnnotationInfo], underlying: Type) extends Type {
+    def derivedAnnotatedType(annots1: List[AnnotationInfo], underlying1: Type) =
+      if ((annots1 eq annots) && (underlying1 eq underlying)) this
+      else AnnotatedType.make(annots1, underlying1)
+  }
+
+  object AnnotatedType {
+    def make(annots: List[AnnotationInfo], underlying: Type) =
+      if (annots.isEmpty) underlying
+      else AnnotatedType(annots, underlying)
+  }
+
+  abstract class TypeMap(implicit ctx: Context) extends (Type => Type) {
+    def apply(tp: Type): Type
+
+    /** Map this function over given type */
+    def mapOver(tp: Type): Type = tp match {
+      case tp: SymRef =>
+        tp.derivedSymRef(this(tp.prefix), tp.symbol)
+
+      case ThisType(_)
+         | MethodParam(_, _)
+         | PolyParam(_, _)
+         | ConstantType(_) => tp
+
+      case tp @ AppliedType(tycon, targs) =>
+        tp.derivedAppliedType(this(tycon), targs mapConserve this)
+
+      case tp @ PolyType(pnames, pboundsExpr, restpeExpr) =>
+        val pbounds = tp.paramBounds
+        val pbounds1 = pbounds mapConserve (_ map this)
+        val restpe = tp.resultType
+        val restpe1 = this(restpe)
+        if ((pbounds1 eq pbounds) && (restpe1 eq restpe))
+          tp
+        else PolyType(
+          pnames,
+          x => pbounds1 mapConserve (_ map (_.subst(tp, x))),
+          x => restpe1.subst(tp, x))
+
+      case tp @ MethodType(pnames, ptypes, restpeExpr) =>
+        val ptypes1 = ptypes mapConserve this
+        val restpe = tp.resultType
+        val restpe1 = this(restpe)
+        if ((ptypes1 eq ptypes) && (restpe1 eq restpe)) tp
+        else MethodType(pnames, ptypes1, x => restpe1.subst(tp, x))
+
+      case tp @ ExprType(restpe) =>
+        tp.derivedExprType(this(restpe))
+
+      case tp @ SuperType(thistp, supertp) =>
+        tp.derivedSuperType(this(thistp), this(supertp))
+
+      case tp @ TypeBounds(lo, hi) =>
+        if (lo eq hi) {
+          val lo1 = this(lo)
+          tp.derivedTypeBounds(lo1, lo1)
+        } else {
+          tp.derivedTypeBounds(this(lo), this(hi))
+        }
+
+      case tp @ RefinedType(parent, decls) =>
+        tp.derivedRefinedType(this(parent), mapOver(decls))
+
+      case tp @ OverloadedType(vs) =>
+        val altTypes = (vs map (_._2)).toList
+        val altTypes1 = altTypes mapConserve (t => this(t).asInstanceOf[RefType])
+        if (altTypes eq altTypes1) tp
+        else altTypes.reduceLeft(_ ref_& _)
+
+      case tp @ AnnotatedType(annots, underlying) =>
+        tp.derivedAnnotatedType(mapOverAnnotations(annots), this(underlying))
+
+      case _ =>
+        tp
+    }
+
+    /** Map this function over given scope */
+    def mapOver(scope: Scope): Scope = {
+      val elems = scope.toList
+      val elems1 = mapOver(elems)
+      if (elems1 eq elems) scope
+      else newScopeWith(elems1: _*)
+    }
+
+    /** Map this function over given list of symbols */
+    def mapOver(syms: List[Symbol]): List[Symbol] = {
+      val infos = syms map (_.info)
+      val infos1 = infos mapConserve this
+      if (infos eq infos1) syms
+      else {
+        val syms1 = syms map (_.cloneSymbol)
+        (syms1, infos1).zipped.foreach { (sym1, info1) =>
+          sym1 setDenotation sym1.deref.withType(info1 substSym (syms, syms1))
+        }
+        syms1
+      }
+    }
+
+    def mapOverAnnotations(annots: List[AnnotationInfo]): List[AnnotationInfo] = ???
+
+  }
+
+  class InstMethodMap(mt: MethodType, argtypes: List[Type])(implicit ctx: Context) extends TypeMap {
+    def apply(tp: Type) = tp match {
+      case MethodParam(`mt`, n) => argtypes(n)
+      case _ => mapOver(tp)
+    }
+  }
+
+  class InstPolyMap(pt: PolyType, argtypes: List[Type])(implicit ctx: Context) extends TypeMap {
+    def apply(tp: Type) = tp match {
+      case PolyParam(`pt`, n) => argtypes(n)
+      case _ => mapOver(tp)
+    }
+  }
+
+//  Constraints: poly => tvars
+//
+
+
+
+  class AsSeenFromMap(pre: Type, clazz: Symbol)(implicit ctx: Context) extends TypeMap {
+    private def skipPrefixOf(pre: Type, clazz: Symbol) =
+      (pre eq NoType) || (pre eq NoPrefix) || clazz.isPackageClass
+    def apply(tp: Type) = tp match {
+      case ThisType(sym) =>
+        def toPrefix(pre: Type, clazz: Symbol): Type =
+          if (skipPrefixOf(pre, clazz))
+            tp
+          else if ((sym isNonBottomSubClass clazz) &&
+            (pre.widen.typeSymbol isNonBottomSubClass sym))
+            pre match {
+              case SuperType(thistp, _) => thistp
+              case _ => pre
+            }
+          else
+            toPrefix(pre.baseType(clazz).prefix, clazz.owner)
+        toPrefix(pre, clazz)
+      case TypeRef(_, tparam) if tparam.isTypeParameter =>
+        def toInstance(pre: Type, clazz: Symbol): Type = {
+          if (skipPrefixOf(pre, clazz)) tp
+          else {
+            val tparamOwner = tparam.owner
+
+            def throwError =
+              if (tparamOwner.tpe.parents exists (_.isErroneous))
+                ErrorType // don't be overzealous with throwing exceptions, see #2641
+              else
+                throw new Error(
+                  s"something is wrong (wrong class file?): tp ${tparam.locationString} cannot be instantiated from ${pre.widen}")
+
+            def prefixMatches = pre.typeSymbol isNonBottomSubClass tparamOwner
+
+            val basePre = pre.baseType(clazz)
+
+            def instParamFrom(typeInst: Type): Type = typeInst match {
+              case ConstantType(_) =>
+                // have to deconst because it may be a Class[T].
+                instParamFrom(typeInst.deconst)
+              case AppliedType(tycon, baseArgs) =>
+                instParam(tycon.typeParams, baseArgs)
+              case _ =>
+                throwError
+            }
+
+            def instParam(ps: List[Symbol], as: List[Type]): Type =
+              if (ps.isEmpty || as.isEmpty) throwError
+              else if (tparam eq ps.head) as.head
+              else throwError
+
+            if (tparamOwner == clazz && prefixMatches) instParamFrom(basePre)
+            else toInstance(basePre.prefix, clazz.owner)
+          }
+        }
+        toInstance(pre, clazz)
+      case _ =>
+        if (tp.isTrivial) tp else mapOver(tp)
+    }
+  }
+
+  abstract class TypeAccumulator[T] extends ((T, Type) => T) {
+    def apply(x: T, tp: Type): T
+
+    def apply(x: T, sym: Symbol): T = apply(x, sym.info(NoContext))
+
+    def apply(x: T, annot: AnnotationInfo): T = ???
+
+    def foldOver(x: T, tp: Type): T = tp match {
+      case tp: SymRef =>
+        this(x, tp.prefix)
+
+      case ThisType(_)
+         | MethodParam(_, _)
+         | PolyParam(_, _)
+         | ConstantType(_) => x
+
+      case AppliedType(tycon, targs) =>
+        (this(x, tycon) /: targs) (this)
+
+      case tp @ PolyType(pnames, pboundsExpr, restpeExpr) =>
+        this((x /: tp.paramBounds) (this), tp.resultType)
+
+      case MethodType(pnames, ptypes, restpeExpr) =>
+        this((x /: ptypes) (this), tp.resultType)
+
+      case ExprType(restpe) =>
+        this(x, restpe)
+
+      case SuperType(thistp, supertp) =>
+        this(this(x, thistp), supertp)
+
+      case TypeBounds(lo, hi) =>
+        this(this(x, lo), hi)
+
+      case RefinedType(parent, decls) =>
+        (this(x, parent) /: decls.toList) (apply)
+
+      case OverloadedType(vs) =>
+        (x /: (vs map (_._2))) (this)
+
+      case AnnotatedType(annots, underlying) =>
+        this((x /: annots) (apply), underlying)
+
+      case _ => x
+
+    }
+
+  }
+
+  class ExistsAccumulator(p: Type => Boolean) extends TypeAccumulator[Boolean] {
+    def apply(x: Boolean, tp: Type) = x || p(tp) || foldOver(x, tp)
+  }
+
+  /** like map2, but returns list `xs` itself - instead of a copy - if function
+   *  `f` maps all elements to themselves.
+   */
+  def map2Conserve[A <: AnyRef, B](xs: List[A], ys: List[B])(f: (A, B) => A): List[A] =
+    if (xs.isEmpty) xs
+    else {
+      val x1 = f(xs.head, ys.head)
+      val xs1 = map2Conserve(xs.tail, ys.tail)(f)
+      if ((x1 eq xs.head) && (xs1 eq xs.tail)) xs
+      else x1 :: xs1
+    }
+
+  final val NotCached = 0
+  final val NotCachedAlt = Int.MinValue
+
+  /** Compute the hash of a product
+  def productHash(x: Product): Int = {
+    val arr = x.productArity
+    var h = x.productPrefix.hashCode
+    var i = 0
+    while (i < arr) {
+      val elemHash = x.productElement(i) match {
+        case tp: Type => tp.hash
+        case elem => elem.hashCode
+      }
+      if (elemHash == NotCached) return NotCached
+      h = hashing.mix(h, elemHash)
+      i += 1
+    }
+    finalizeHash(h, arr)
+  }*/
+
+
+}
\ No newline at end of file
diff --git a/src/dotty/tools/dotc/core/test.sc b/src/dotty/tools/dotc/core/test.sc
new file mode 100644
index 000000000..b7b18e132
--- /dev/null
+++ b/src/dotty/tools/dotc/core/test.sc
@@ -0,0 +1,19 @@
+package dotty.tools.dotc.core
+
+import Periods._
+
+object test {
+  val rid = 223                                   //> rid  : Int = 223
+  val p = periodOf(rid, 2)                        //> p  : dotty.tools.dotc.core.Periods.Period = 228416
+  val ivl = intervalOf(rid, 2, 4)                 //> ivl  : dotty.tools.dotc.core.Periods.Interval = 228482
+  containsPeriod(ivl, p)                          //> res0: Boolean = true
+  containsPeriod(ivl, periodOf(rid, 1))           //> res1: Boolean = false
+  containsPeriod(ivl, periodOf(rid, 5))           //> res2: Boolean = false
+	containsPeriod(ivl, periodOf(rid, 4))     //> res3: Boolean = true
+	containsPeriod(ivl, periodOf(rid+1, 2))   //> res4: Boolean = false
+	containsPeriod(ivl, periodOf(rid-1, 2))   //> res5: Boolean = false
+  phaseIdOf(p)                                    //> res6: dotty.tools.dotc.core.Periods.PhaseId = 2
+  phaseIdOf(ivl)                                  //> res7: dotty.tools.dotc.core.Periods.PhaseId = 4
+  runIdOf(p)                                      //> res8: dotty.tools.dotc.core.Periods.RunId = 223
+  containsPeriod(intervalOf(rid, 2, 2), p)        //> res9: Boolean = true
+}
\ No newline at end of file
diff --git a/src/dotty/tools/dotc/util/HashSet.scala b/src/dotty/tools/dotc/util/HashSet.scala
new file mode 100644
index 000000000..589cc1f41
--- /dev/null
+++ b/src/dotty/tools/dotc/util/HashSet.scala
@@ -0,0 +1,108 @@
+/* NSC -- new Scala compiler
+ * Copyright 2005-2012 LAMP/EPFL
+ * @author  Martin Odersky
+ */
+
+package dotty.tools.dotc.util
+
+object HashSet {
+  def apply[T >: Null <: AnyRef](): HashSet[T] = this(16)
+  def apply[T >: Null <: AnyRef](label: String): HashSet[T] = this(label, 16)
+  def apply[T >: Null <: AnyRef](initialCapacity: Int): HashSet[T] = this("No Label", initialCapacity)
+  def apply[T >: Null <: AnyRef](label: String, initialCapacity: Int): HashSet[T] =
+    new HashSet[T](label, initialCapacity)
+}
+
+class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) extends Set[T] with scala.collection.generic.Clearable {
+  private var used = 0
+  private var table = new Array[AnyRef](initialCapacity)
+  private def index(x: Int): Int = math.abs(x % table.length)
+
+  def hash(x: T): Int = x.hashCode
+
+  def size: Int = used
+  def clear() {
+    used = 0
+    table = new Array[AnyRef](initialCapacity)
+  }
+
+  def findEntryOrUpdate(x: T): T = {
+    var h = index(hash(x))
+    var entry = table(h)
+    while (entry ne null) {
+      if (x == entry)
+        return entry.asInstanceOf[T]
+
+      h = index(h + 1)
+      entry = table(h)
+    }
+    table(h) = x
+    used += 1
+    if (used > (table.length >> 2)) growTable()
+    x
+  }
+
+  def findEntry(x: T): T = {
+    var h = index(hash(x))
+    var entry = table(h)
+    while ((entry ne null) && x != entry) {
+      h = index(h + 1)
+      entry = table(h)
+    }
+    entry.asInstanceOf[T]
+  }
+
+  def addEntry(x: T) {
+    var h = index(hash(x))
+    var entry = table(h)
+    while (entry ne null) {
+      if (x == entry) return
+      h = index(h + 1)
+      entry = table(h)
+    }
+    table(h) = x
+    used += 1
+    if (used > (table.length >> 2)) growTable()
+  }
+  def addEntries(xs: TraversableOnce[T]) {
+    xs foreach addEntry
+  }
+
+  def iterator = new Iterator[T] {
+    private var i = 0
+    def hasNext: Boolean = {
+      while (i < table.length && (table(i) eq null)) i += 1
+      i < table.length
+    }
+    def next(): T =
+      if (hasNext) { i += 1; table(i - 1).asInstanceOf[T] }
+      else null
+  }
+
+  private def addOldEntry(x: T) {
+    var h = index(hash(x))
+    var entry = table(h)
+    while (entry ne null) {
+      h = index(h + 1)
+      entry = table(h)
+    }
+    table(h) = x
+  }
+
+  private def growTable() {
+    val oldtable = table
+    val growthFactor =
+      if (table.length <= initialCapacity) 8
+      else if (table.length <= (initialCapacity * 8)) 4
+      else 2
+
+    table = new Array[AnyRef](table.length * growthFactor)
+    var i = 0
+    while (i < oldtable.length) {
+      val entry = oldtable(i)
+      if (entry ne null) addOldEntry(entry.asInstanceOf[T])
+      i += 1
+    }
+  }
+  override def toString() = "HashSet %s(%d / %d)".format(label, used, table.length)
+}
diff --git a/src/dotty/tools/dotc/util/LRUCache.scala b/src/dotty/tools/dotc/util/LRUCache.scala
new file mode 100644
index 000000000..b9d96a061
--- /dev/null
+++ b/src/dotty/tools/dotc/util/LRUCache.scala
@@ -0,0 +1,111 @@
+package dotty.tools.dotc.util
+
+import reflect.ClassTag
+
+class LRU8Cache[Key >: Null, Value >: Null] {
+
+  import LRU8Cache._
+
+  private var key0, key1, key2, key3, key4, key5, key6, key7: Key = null
+  private var val0, val1, val2, val3, val4, val5, val6, val7: Value = null
+  private var hits = 0
+  private var entered = 0
+
+  private def incr(n: Int): Unit = {
+    val shift = n * width
+    hits = (hits ^ (mask << shift)) | (next((hits >>> shift) & mask) << shift)
+  }
+
+  private def decr(n: Int): Unit = {
+    val shift = n * width
+    hits = (hits ^ (mask << shift)) | (prev((hits >>> shift) & mask) << shift)
+  }
+
+  private def init(n: Int): Unit = {
+    val shift = n * width
+    hits = (hits ^ (mask << shift)) | (1 << shift)
+  }
+
+  private def clear(n: Int): Unit = {
+    val shift = n * width
+    hits = (hits ^ (mask << shift))
+  }
+
+  private def evict(): Int = {
+    var min = hits & mask
+    var minIdx = 0
+    hits = hits >>> width
+    if ((hits & mask) < min) { min = hits & mask; minIdx = 1 }
+    hits = hits >>> width
+    if ((hits & mask) < min) { min = hits & mask; minIdx = 2 }
+    hits = hits >>> width
+    if ((hits & mask) < min) { min = hits & mask; minIdx = 3 }
+    hits = hits >>> width
+    if ((hits & mask) < min) { min = hits & mask; minIdx = 4 }
+    hits = hits >>> width
+    if ((hits & mask) < min) { min = hits & mask; minIdx = 5 }
+    hits = hits >>> width
+    if ((hits & mask) < min) { min = hits & mask; minIdx = 6 }
+    hits = hits >>> width
+    if ((hits & mask) < min) { min = hits & mask; minIdx = 7 }
+    minIdx
+  }
+
+  /** Return value associated with key, or `null` if key not present.
+   *  Key must be different from `null`.
+   */
+  def lookup(key: Key): Value = {
+    if (key == key0) { incr(0); return val0 }
+    if (key == key1) { incr(1); return val1 }
+    if (key == key2) { incr(2); return val2 }
+    if (key == key3) { incr(3); return val3 }
+    if (key == key4) { incr(4); return val4 }
+    if (key == key5) { incr(5); return val5 }
+    if (key == key6) { incr(6); return val6 }
+    if (key == key7) { incr(7); return val7 }
+    null
+  }
+
+  /** Enter key/value association in cache */
+  def enter(key: Key, value: Value): Unit = {
+    val idx = if ((entered & 7) == entered) entered else evict()
+    idx match {
+      case 0 => key0 = key; val0 = value
+      case 1 => key1 = key; val1 = value
+      case 2 => key2 = key; val2 = value
+      case 3 => key3 = key; val3 = value
+      case 4 => key4 = key; val4 = value
+      case 5 => key5 = key; val5 = value
+      case 6 => key6 = key; val6 = value
+      case 7 => key7 = key; val7 = value
+    }
+    init(idx)
+    entered += 1
+    if (entered % 8 == 0) {
+      var i = 0
+      while (i < 8) { decr(i); i += 1 }
+    }
+  }
+
+  /** Remove entry for `key` from cache if it was present */
+  def invalidate(key: Key): Unit = {
+    if (key == key0) { clear(0); key0 = null }
+    if (key == key1) { clear(1); key1 = null }
+    if (key == key2) { clear(2); key2 = null }
+    if (key == key3) { clear(3); key3 = null }
+    if (key == key4) { clear(4); key4 = null }
+    if (key == key5) { clear(5); key5 = null }
+    if (key == key6) { clear(6); key6 = null }
+    if (key == key7) { clear(7); key7 = null }
+  }
+
+
+}
+
+object LRU8Cache {
+  private final val width = 32 / 8        // width of a counter in bits
+  private final val mask = (1 << width) - 1
+
+  private val next: Array[Int] = (1 to mask).toArray :+ mask
+  private val prev: Array[Int] = 0 +: (0 until mask).toArray
+}
\ No newline at end of file
diff --git a/src/dotty/tools/dotc/util/NameTransformer.scala b/src/dotty/tools/dotc/util/NameTransformer.scala
new file mode 100644
index 000000000..287c7660c
--- /dev/null
+++ b/src/dotty/tools/dotc/util/NameTransformer.scala
@@ -0,0 +1,158 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2011, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+package dotty.tools.dotc
+package util
+
+/** Provides functions to encode and decode Scala symbolic names.
+ *  Also provides some constants.
+ */
+object NameTransformer {
+  // XXX Short term: providing a way to alter these without having to recompile
+  // the compiler before recompiling the compiler.
+  val MODULE_SUFFIX_STRING = sys.props.getOrElse("SCALA_MODULE_SUFFIX_STRING", "$")
+  val NAME_JOIN_STRING     = sys.props.getOrElse("SCALA_NAME_JOIN_STRING", "$")
+  val MODULE_INSTANCE_NAME = "MODULE$"
+
+  private val nops = 128
+  private val ncodes = 26 * 26
+
+  private class OpCodes(val op: Char, val code: String, val next: OpCodes)
+
+  private val op2code = new Array[String](nops)
+  private val code2op = new Array[OpCodes](ncodes)
+  private def enterOp(op: Char, code: String) = {
+    op2code(op) = code
+    val c = (code.charAt(1) - 'a') * 26 + code.charAt(2) - 'a'
+    code2op(c) = new OpCodes(op, code, code2op(c))
+  }
+
+  /* Note: decoding assumes opcodes are only ever lowercase. */
+  enterOp('~', "$tilde")
+  enterOp('=', "$eq")
+  enterOp('<', "$less")
+  enterOp('>', "$greater")
+  enterOp('!', "$bang")
+  enterOp('#', "$hash")
+  enterOp('%', "$percent")
+  enterOp('^', "$up")
+  enterOp('&', "$amp")
+  enterOp('|', "$bar")
+  enterOp('*', "$times")
+  enterOp('/', "$div")
+  enterOp('+', "$plus")
+  enterOp('-', "$minus")
+  enterOp(':', "$colon")
+  enterOp('\\', "$bslash")
+  enterOp('?', "$qmark")
+  enterOp('@', "$at")
+
+  /** Replace operator symbols by corresponding `\$opname`.
+   *
+   *  @param name the string to encode
+   *  @return     the string with all recognized opchars replaced with their encoding
+   */
+  def encode(name: String): String = {
+    var buf: StringBuilder = null
+    val len = name.length()
+    var i = 0
+    while (i < len) {
+      val c = name charAt i
+      if (c < nops && (op2code(c) ne null)) {
+        if (buf eq null) {
+          buf = new StringBuilder()
+          buf.append(name.substring(0, i))
+        }
+        buf.append(op2code(c))
+      /* Handle glyphs that are not valid Java/JVM identifiers */
+      }
+      else if (!Character.isJavaIdentifierPart(c)) {
+        if (buf eq null) {
+          buf = new StringBuilder()
+          buf.append(name.substring(0, i))
+        }
+        buf.append("$u%04X".format(c.toInt))
+      }
+      else if (buf ne null) {
+        buf.append(c)
+      }
+      i += 1
+    }
+    if (buf eq null) name else buf.toString()
+  }
+
+  /** Replace `\$opname` by corresponding operator symbol.
+   *
+   *  @param name0 the string to decode
+   *  @return      the string with all recognized operator symbol encodings replaced with their name
+   */
+  def decode(name0: String): String = {
+    //System.out.println("decode: " + name);//DEBUG
+    val name = if (name0.endsWith("<init>")) name0.substring(0, name0.length() - ("<init>").length()) + "this"
+               else name0;
+    var buf: StringBuilder = null
+    val len = name.length()
+    var i = 0
+    while (i < len) {
+      var ops: OpCodes = null
+      var unicode = false
+      val c = name charAt i
+      if (c == '$' && i + 2 < len) {
+        val ch1 = name.charAt(i+1)
+        if ('a' <= ch1 && ch1 <= 'z') {
+          val ch2 = name.charAt(i+2)
+          if ('a' <= ch2 && ch2 <= 'z') {
+            ops = code2op((ch1 - 'a') * 26 + ch2 - 'a')
+            while ((ops ne null) && !name.startsWith(ops.code, i)) ops = ops.next
+            if (ops ne null) {
+              if (buf eq null) {
+                buf = new StringBuilder()
+                buf.append(name.substring(0, i))
+              }
+              buf.append(ops.op)
+              i += ops.code.length()
+            }
+            /* Handle the decoding of Unicode glyphs that are
+             * not valid Java/JVM identifiers */
+          } else if ((len - i) >= 6 && // Check that there are enough characters left
+                     ch1 == 'u' &&
+                     ((Character.isDigit(ch2)) ||
+                     ('A' <= ch2 && ch2 <= 'F'))) {
+            /* Skip past "$u", next four should be hexadecimal */
+            val hex = name.substring(i+2, i+6)
+            try {
+              val str = Integer.parseInt(hex, 16).toChar
+              if (buf eq null) {
+                buf = new StringBuilder()
+                buf.append(name.substring(0, i))
+              }
+              buf.append(str)
+              /* 2 for "$u", 4 for hexadecimal number */
+              i += 6
+              unicode = true
+            } catch {
+              case _:NumberFormatException =>
+                /* `hex` did not decode to a hexadecimal number, so
+                 * do nothing. */
+            }
+          }
+        }
+      }
+      /* If we didn't see an opcode or encoded Unicode glyph, and the
+        buffer is non-empty, write the current character and advance
+         one */
+      if ((ops eq null) && !unicode) {
+        if (buf ne null)
+          buf.append(c)
+        i += 1
+      }
+    }
+    //System.out.println("= " + (if (buf == null) name else buf.toString()));//DEBUG
+    if (buf eq null) name else buf.toString()
+  }
+}
diff --git a/src/dotty/tools/dotc/util/Set.scala b/src/dotty/tools/dotc/util/Set.scala
new file mode 100644
index 000000000..4183186ed
--- /dev/null
+++ b/src/dotty/tools/dotc/util/Set.scala
@@ -0,0 +1,26 @@
+/* NSC -- new Scala compiler
+ * Copyright 2005-2012 LAMP/EPFL
+ * @author  Martin Odersky
+ */
+package dotty.tools.dotc.util
+
+/** A common class for lightweight sets.
+ */
+abstract class Set[T <: AnyRef] {
+
+  def findEntry(x: T): T
+
+  def addEntry(x: T): Unit
+
+  def iterator: Iterator[T]
+
+  def foreach[U](f: T => U): Unit = iterator foreach f
+
+  def apply(x: T): Boolean = contains(x)
+
+  def contains(x: T): Boolean =
+    findEntry(x) ne null
+
+  def toList = iterator.toList
+
+}