Refactored Types to move auxiliary operations into Context. Moved per-run state into RootContext.

1 files changed, 359 insertions, 520 deletions

diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala
index 9dc87711c..aee83ed28 100644
--- a/src/dotty/tools/dotc/core/Types.scala
+++ b/src/dotty/tools/dotc/core/Types.scala
@@ -7,31 +7,16 @@ import SubTypers._
 import Flags._
 import Names._
 import Scopes._
-import Substituters._
 import Constants._
 import Contexts._
 import Annotations._
 import Denotations._
 import References._
 import Periods._
-import References.{Reference, RefSet, RefUnion, ErrorRef}
-import scala.util.hashing.{MurmurHash3 => hashing}
+import References.{ Reference, RefSet, RefUnion, ErrorRef }
+import scala.util.hashing.{ MurmurHash3 => hashing }
 import collection.mutable
 
-trait Types { self: Context =>
-
-  import Types._
-
-  private val initialUniquesCapacity = 50000
-
-  private val uniques = new util.HashSet[Type]("uniques", initialUniquesCapacity) {
-    override def hash(x: Type): Int = x.hash
-  }
-
-  private var volatileRecursions: Int = 0
-  private val pendingVolatiles = new mutable.HashSet[Type]
-}
-
 object Types {
 
   /** A hash value indicating that the underlying type is not
@@ -44,88 +29,113 @@ object Types {
    */
   private final val NotCachedAlt = Int.MinValue
 
-  /** How many recursive calls to isVolatile are performed before
-   *  logging starts.
-   */
-  private final val LogVolatileThreshold = 50
-
   /** The class of types.
    *  The principal subclasses and sub-objects are as follows:
    *
-   *  Type -+- TypeProxy -+- NamedType ----+--- TypeRef
-   *        |             |                 \
-   *        |             +- SingletonType---+- TermRef
-   *        |             |
-   *        |             +- SingletonType --+- ThisType
-   *        |             |                  +- SuperType
-   *        |             |                  +- ConstantType
-   *        |             |                  +- MethodParam
-   *        |             |                  +- RefinedThis
-   *        |             |                  +- TypeBounds
-   *        |             |                  +- ExprType
-   *        |             |                  +- AnnotatedType
-   *        |             +- PolyParam
-   *        |             +- AppliedType
-   *        |             +- RefinedType
-   *        +- AndType
-   *        +- OrType
-   *        +- MethodType -+- ImplicitMethodType
-   *        |              +- JavaMethodType
-   *        +- PolyType
-   *        +- ClassInfo
-   *        |
-   *        +- NoType
-   *        +- ErrorType
-   *        +- WildcardType
+   *  Type -+- ProxyType --+- NamedType ----+--- TypeRef
+   *        |              |                 \
+   *        |              +- SingletonType---+- TermRef
+   *        |              |
+   *        |              +- SingletonType --+- ThisType
+   *        |                                 +- SuperType
+   *        |                                 +- ConstantType
+   *        |                                 +- MethodParam
+   *        |                                 +- RefinedThis
+   *        |                                 +- TypeBounds
+   *        |                                 +- ExprType
+   *        |                                 +- AnnotatedType
+   *        +- GroundType -+- PolyParam
+   *                       +- AppliedType
+   *                       +- RefinedType
+   *                       +- AndType
+   *                       +- OrType
+   *                       +- MethodType -----+- ImplicitMethodType
+   *                       |                  +- JavaMethodType
+   *                       +- PolyType
+   *                       +- ClassInfo
+   *                       |
+   *                       +- NoType
+   *                       +- ErrorType
+   *                       +- WildcardType
    */
   abstract class Type extends DotClass {
 
-    def hash = NotCached
-
     /** The type symbol associated with the type */
-    def typeSymbol(implicit ctx: Context): Symbol = NoSymbol
+    final def typeSymbol(implicit ctx: Context): Symbol = this match {
+      case tp: TypeRef => tp.symbol
+      case tp: ClassInfo => tp.classd.clazz
+      case _ => NoSymbol
+    }
 
     /** The term symbol associated with the type */
-    def termSymbol(implicit ctx: Context): Symbol = NoSymbol
+    final def termSymbol(implicit ctx: Context): Symbol = this match {
+      case tp: TermRef => tp.symbol
+      case _ => NoSymbol
+    }
 
     /** Does this type denote a stable reference (i.e. singleton type)? */
-    def isStable(implicit ctx: Context): Boolean = false
+    final def isStable(implicit ctx: Context): Boolean = this match {
+      case tp: TermRef => tp.prefix.isStable && tp.termSymbol.isStable
+      case _: SingletonType => true
+      case _ => false
+    }
 
     /** A type T is a legal prefix in a type selection T#A if
      *  T is stable or T contains no uninstantiated type variables.
      */
-    def isLegalPrefix(implicit ctx: Context): Boolean =
+    final def isLegalPrefix(implicit ctx: Context): Boolean =
       isStable || abstractTypeNames(this).isEmpty
 
     /** The set of names that denote an abstract type member of this type
      *  which is also an abstract type member of `pre`
      */
-    def abstractTypeNames(pre: Type)(implicit ctx: Context): Set[Name] =
+    final def abstractTypeNames(pre: Type)(implicit ctx: Context): Set[Name] =
       memberNames(pre, abstractTypeNameFilter)
 
     /** The set of names that denote an abstract term member of this type
      *  which is also an abstract term member of `pre`
      */
-    def abstractTermNames(pre: Type)(implicit ctx: Context): Set[Name] =
+    final def abstractTermNames(pre: Type)(implicit ctx: Context): Set[Name] =
       memberNames(pre, abstractTermNameFilter)
 
     /** The set of names that denote an abstract member of this type
      *  which is also an abstract member of `pre`
      */
-    def abstractMemberNames(pre: Type)(implicit ctx: Context): Set[Name] =
+    final def abstractMemberNames(pre: Type)(implicit ctx: Context): Set[Name] =
       abstractTypeNames(pre) | abstractTermNames(pre)
 
     /** The set of names of members of this type that pass the given name filter
      *  when seen as members of `pre`. More precisely, these are all
      *  of members `name` such that `keepOnly(pre, name)` is `true`.
      */
-    def memberNames(pre: Type, keepOnly: NameFilter)(implicit ctx: Context): Set[Name] =
-      Set()
+    final def memberNames(pre: Type, keepOnly: NameFilter)(implicit ctx: Context): Set[Name] = this match {
+      case tp: ClassInfo =>
+        tp.classd.memberNames(keepOnly) filter (keepOnly(pre, _))
+      case tp: RefinedType =>
+        tp.parent.memberNames(pre, keepOnly) ++ (tp.names filter (keepOnly(pre, _))).toSet
+      case tp: AndType =>
+        tp.tp1.memberNames(pre, keepOnly) | tp.tp2.memberNames(pre, keepOnly)
+      case tp: OrType =>
+        tp.tp1.memberNames(pre, keepOnly) & tp.tp2.memberNames(pre, keepOnly)
+      case tp: TypeProxy =>
+        tp.underlying.memberNames(pre, keepOnly)
+      case _ =>
+        Set()
+    }
 
     /** Is this type a TypeBounds instance, with lower and upper bounds
      *  that are not identical?
      */
-    def isRealTypeBounds: Boolean = false
+    final def isRealTypeBounds: Boolean = this match {
+      case tp: TypeBounds => tp.lo ne tp.hi
+      case _ => false
+    }
+
+    /** This type seen as a TypeBounds */
+    final def bounds(implicit ctx: Context): TypeBounds = this match {
+      case tp: TypeBounds => tp
+      case _ => TypeBounds(this, this)
+    }
 
     /** A type is volatile if it has an underlying type of the
      *  form P1 with ... with Pn { decls } (where n may be 1 or decls may
@@ -141,112 +151,82 @@ object Types {
      *  Lazy values are not allowed to have volatile type, as otherwise
      *  unsoundness can result.
      */
-    def isVolatile(implicit ctx: Context): Boolean = {
-      def isAbstractIntersection(tp: Type): Boolean = tp match {
-        case tp: TypeRef => tp.isAbstractType
-        case AndType(l, r) => isAbstractIntersection(l) | isAbstractIntersection(l)
-        case OrType(l, r) => isAbstractIntersection(l) & isAbstractIntersection(r)
-        case _ => false
-      }
-      def test = {
-        this match {
-          case ThisType(_) =>
-            false
-          case RefinedType(p, names) =>
-            p.isVolatile ||
-              isAbstractIntersection(p) &&
-              (names exists (abstractMemberNames(this) contains))
-          case tp: TypeProxy =>
-            tp.underlying.isVolatile
-          case AndType(l, r) =>
-            l.isVolatile || r.isVolatile ||
-              isAbstractIntersection(l) && r.abstractMemberNames(this).nonEmpty
-          case OrType(l, r) =>
-            l.isVolatile && r.isVolatile
-          case _ =>
-            false
-        }
-      }
-      // need to be careful not to fall into an infinite recursion here
-      // because volatile checking is done before all cycles are detected.
-      // the case to avoid is an abstract type directly or
-      // indirectly upper-bounded by itself. See #2918
-      import ctx.root.{volatileRecursions, pendingVolatiles}
-      try {
-        volatileRecursions += 1
-        if (volatileRecursions < LogVolatileThreshold)
-          test
-        else if (pendingVolatiles(this))
-          false // we can return false here, because a cycle will be detected
-                // here afterwards and an error will result anyway.
-        else
-          try {
-            pendingVolatiles += this
-            test
-          } finally {
-            pendingVolatiles -= this
-          }
-      } finally {
-        volatileRecursions -= 1
-      }
-    }
+    final def isVolatile(implicit ctx: Context): Boolean =
+      ctx.isVolatile(this)
 
     /** Is this type guaranteed not to have `null` as a value? */
-    def isNotNull: Boolean = false
+    final 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)
+    final 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)
+    final 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 =
+    final def exists(p: Type => Boolean): Boolean =
       new ExistsAccumulator(p)(false, this)
 
     /** Substitute all types that refer in their symbol attribute to
      *  one of the symbols in `from` by the corresponding types in `to`
      */
-    def subst(from: List[Symbol], to: List[Type])(implicit ctx: Context): Type =
+    final def subst(from: List[Symbol], to: List[Type])(implicit ctx: Context): Type =
       if (from.isEmpty) this
       else {
         val from1 = from.tail
-        if (from1.isEmpty) new SubstOps(this).subst1(from.head, to.head, null)
+        if (from1.isEmpty) ctx.subst1(this, from.head, to.head, null)
         else {
           val from2 = from1.tail
-          if (from2.isEmpty) new SubstOps(this).subst2(from.head, to.head, from.tail.head, to.tail.head, null)
-          else new SubstOps(this).subst(from, to, null)
+          if (from2.isEmpty) ctx.subst2(this, from.head, to.head, from.tail.head, to.tail.head, null)
+          else ctx.subst(this, from, to, null)
         }
       }
 
     /** Substitute all types of the form `PolyParam(from, N)` by
      *  `PolyParam(to, N)`.
      */
-    def subst(from: PolyType, to: PolyType)(implicit ctx: Context): Type =
-      new SubstOps(this).subst(from, to, null)
+    final def subst(from: PolyType, to: PolyType)(implicit ctx: Context): Type =
+      ctx.subst(this, from, to, null)
 
     /** Substitute all types of the form `MethodParam(from, N)` by
      *  `MethodParam(to, N)`.
      */
-    def subst(from: MethodType, to: MethodType)(implicit ctx: Context): Type =
-      if (from.isDependent) new SubstOps(this).subst(from, to, null)
+    final def subst(from: MethodType, to: MethodType)(implicit ctx: Context): Type =
+      if (from.isDependent) ctx.subst(this, from, to, null)
       else this
 
     /** Substitute all references of the form `This(clazz)` by `tp` */
-    def substThis(clazz: ClassSymbol, tp: Type)(implicit ctx: Context): Type =
-      new SubstOps(this).substThis(clazz, tp, null)
+    final def substThis(clazz: ClassSymbol, tp: Type)(implicit ctx: Context): Type =
+      ctx.substThis(this, clazz, tp, null)
 
     /** Substitute all references of the form `RefinedThis(from)` by `tp` */
-    def substThis(from: RefinedType, tp: Type)(implicit ctx: Context): Type =
-      new SubstOps(this).substThis(from, tp, null)
+    final def substThis(from: RefinedType, tp: Type)(implicit ctx: Context): Type =
+      ctx.substThis(this, from, tp, null)
 
     /** For a ClassInfo type, its parents,
      *  For an AndType, its operands,
      *  For an applied type, the instantiated parents of its base type.
      *  Inherited by all type proxies. Empty for all other types.
      */
-    def parents(implicit ctx: Context): List[Type] = List()
+    final def parents(implicit ctx: Context): List[Type] = this match {
+      case tp: AppliedType =>
+        val tycon = tp.tycon
+        tycon.parents.mapConserve(_.subst(tycon.typeParams, tp.targs))
+      case tp: AndType =>
+        def components(tp: Type): List[Type] = tp match {
+          case AndType(tp1, tp2) => components(tp1) ++ components(tp2)
+          case _ => List(tp)
+        }
+        components(tp)
+      case tp: ClassInfo =>
+        if (tp.parentsCache == null)
+          tp.parentsCache = tp.classd.parents.mapConserve(_.substThis(tp.classd.clazz, tp.prefix))
+        tp.parentsCache
+      case tp: TypeProxy =>
+        tp.underlying.parents
+      case _ => List()
+    }
 
     /** The normalized prefix of this type is:
      *  For an alias type, the normalized prefix of its alias
@@ -254,27 +234,40 @@ object Types {
      *  Inherited by all other type proxies.
      *  `NoType` for all other types.
      */
-    def normalizedPrefix(implicit ctx: Context): Type = NoType
-
-    /** This type seen as a TypeBounds */
-    def bounds(implicit ctx: Context): TypeBounds = TypeBounds(this, this)
+    final def normalizedPrefix(implicit ctx: Context): Type = this match {
+      case tp: NamedType =>
+        if (tp.isAbstractType) tp.info.normalizedPrefix else tp.prefix
+      case tp: ClassInfo =>
+        tp.prefix
+      case tp: TypeProxy =>
+        tp.underlying.normalizedPrefix
+      case _ =>
+        NoType
+    }
 
     /** The scope of all declarations of this type.
      *  Defined by ClassInfo, inherited by type proxies.
      *  Empty scope for all other types.
      */
-    def decls(implicit ctx: Context): Scope = EmptyScope
+    final def decls(implicit ctx: Context): Scope = this match {
+      case tp: ClassInfo =>
+        tp.classd.decls
+      case tp: TypeProxy =>
+        tp.underlying.decls
+      case _ =>
+        EmptyScope
+    }
 
     /** The declaration of this type with given name */
-    def decl(name: Name)(implicit ctx: Context): Reference =
+    final def decl(name: Name)(implicit ctx: Context): Reference =
       decls.refsNamed(name).toRef
 
     /** The member of this type with given name  */
-    def member(name: Name)(implicit ctx: Context): Reference =
+    final def member(name: Name)(implicit ctx: Context): Reference =
       findMember(name, this, Flags.Empty)
 
     /** The non-private member of this type with given name */
-    def nonPrivateMember(name: Name)(implicit ctx: Context): Reference =
+    final def nonPrivateMember(name: Name)(implicit ctx: Context): Reference =
       findMember(name, this, Flags.Private)
 
     /** Find member of this type with given name and
@@ -282,17 +275,35 @@ object Types {
      *  as seen from given prefix `pre`. Exclude all members with one
      *  of the flags in `excluded` from consideration.
      */
-    def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): Reference =
-      unsupported("findMember")
+    final def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): Reference = this match {
+      case tp: RefinedType =>
+        tp.parent.findMember(name, pre, excluded | Flags.Private) &
+          tp.findDecl(name, pre)
+      case tp: TypeProxy =>
+        tp.underlying.findMember(name, pre, excluded)
+      case tp: ClassInfo =>
+        val classd = tp.classd
+        val candidates = classd.memberRefsNamed(name)
+        val resultSyms = candidates
+          .filterAccessibleFrom(pre)
+          .filterExcluded(excluded)
+          .asSeenFrom(pre, classd.clazz)
+        if (resultSyms.exists) resultSyms.toRef
+        else ErrorRef // todo: refine
+      case tp: AndType =>
+        tp.tp1.findMember(name, pre, excluded) & tp.tp2.findMember(name, pre, excluded)
+      case tp: OrType =>
+        (tp.tp1.findMember(name, pre, excluded) | tp.tp2.findMember(name, pre, excluded))(pre)
+    }
 
     /** Is this type a subtype of that type? */
-    def <:< (that: Type)(implicit ctx: Context): Boolean =
+    final def <:<(that: Type)(implicit ctx: Context): Boolean =
       ctx.subTyper.isSubType(this, that)
 
     /** Is this type the same as that type?
      *  This is the case iff `this <:< that` and `that <:< this`.
      */
-    def =:= (that: Type)(implicit ctx: Context): Boolean =
+    final def =:=(that: Type)(implicit ctx: Context): Boolean =
       ctx.subTyper.isSameType(this, that)
 
     /** Widen from singleton type to its underlying non-singleton
@@ -303,12 +314,18 @@ object Types {
      *  val o: Outer
      *  <o.x.type>.widen = o.C
      */
-    def widen(implicit ctx: Context): Type = this
+    final def widen(implicit ctx: Context): Type = this match {
+      case tp: SingletonType => tp.underlying.widen
+      case _ => this
+    }
 
     /** Widen from constant type to its underlying non-constant
      *  base type.
      */
-    def deconst: Type = this
+    final def deconst: Type = this match {
+      case tp: ConstantType => tp.value.tpe
+      case _ => this
+    }
 
     //def resultType: Type = ???
 
@@ -316,90 +333,27 @@ object Types {
      *  Inherited by all type proxies.
      *  `Nil` for all other types.
      */
-    def baseClasses(implicit ctx: Context): List[ClassSymbol] = Nil
-
-
-    def asSeenFrom(pre: Type, clazz: Symbol)(implicit ctx: Context): Type =
-      if (clazz.isStaticMono || ctx.erasedTypes && clazz != defn.ArrayClass ) this
-      else asSeenFrom(pre, clazz, null)
-
-    def asSeenFrom(pre: Type, clazz: Symbol, theMap: AsSeenFromMap)(implicit ctx: Context): Type = {
-
-      def skipPrefixOf(pre: Type, clazz: Symbol) =
-        (pre eq NoType) || (pre eq NoPrefix) || clazz.isPackageClass
-
-      def toPrefix(pre: Type, clazz: Symbol, thisclazz: ClassSymbol): Type =
-        if (skipPrefixOf(pre, clazz))
-          this
-        else if ((thisclazz isNonBottomSubClass clazz) &&
-          (pre.widen.typeSymbol isNonBottomSubClass thisclazz))
-          pre match {
-            case SuperType(thistp, _) => thistp
-            case _ => pre
-          }
-        else
-          toPrefix(pre.baseType(clazz).normalizedPrefix, clazz.owner, thisclazz)
-
-      def toInstance(pre: Type, clazz: Symbol, tparam: Symbol): Type = {
-        if (skipPrefixOf(pre, clazz)) this
-        else {
-          val tparamOwner = tparam.owner
-
-          def throwError =
-            if (tparamOwner.info.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.normalizedPrefix, clazz.owner, tparam)
-        }
-      }
-
-      this match {
-        case tp: NamedType =>
-          val sym = tp.symbol
-          if (tp.symbol.isTypeParameter) toInstance(pre, clazz, sym)
-          else if (sym.isStatic) this
-          else tp.derivedNamedType(tp.prefix.asSeenFrom(pre, clazz, theMap), tp.name)
-        case ThisType(thisclazz) =>
-          toPrefix(pre, clazz, thisclazz)
-        case _ =>
-          val asSeenFromMap = if (theMap != null) theMap else new AsSeenFromMap(pre, clazz)
-          this match {
-            case tp: AppliedType =>
-              tp.derivedAppliedType(
-                asSeenFromMap(tp.tycon), tp.targs mapConserve asSeenFromMap)
-            case _ =>
-              asSeenFromMap mapOver this
-          }
-      }
+    final def baseClasses(implicit ctx: Context): List[ClassSymbol] = this match {
+      case tp: TypeProxy =>
+        tp.underlying.baseClasses
+      case tp: ClassInfo =>
+        tp.classd.baseClasses
+      case _ => Nil
     }
 
+    final def asSeenFrom(pre: Type, clazz: Symbol)(implicit ctx: Context): Type =
+      if (clazz.isStaticMono || ctx.erasedTypes && clazz != defn.ArrayClass) this
+      else ctx.asSeenFrom(this, pre, clazz, null)
+
+    /** The signature of this type. This is by default NullSignature,
+     *  but is overridden for PolyTypes, MethodTypes, and TermRefWithSignature types.
+     *  (the reason why we deviate from the "final-method-with-pattern-match-in-base-class"
+     *   pattern is that method signatures use caching, so encapsulation
+     *   is improved using an OO scheme).
+     */
     def signature: Signature = NullSignature
-    def subSignature: Signature = List()
 
-    def baseType(base: Symbol)(implicit ctx: Context): Type = base.deref match {
+    final def baseType(base: Symbol)(implicit ctx: Context): Type = base.deref match {
       case classd: ClassDenotation => classd.baseTypeOf(this)
       case _ => NoType
     }
@@ -411,96 +365,46 @@ object Types {
      *  Inherited by type proxies.
      *  Empty list for all other types.
      */
-    def typeParams(implicit ctx: Context): List[TypeSymbol] = Nil
+    final def typeParams(implicit ctx: Context): List[TypeSymbol] = this match {
+      case tp: AppliedType =>
+        tp.tycon.typeParams drop tp.targs.length
+      case tp: TypeProxy =>
+        tp.underlying.typeParams
+      case tp: ClassInfo =>
+        tp.classd.typeParams
+      case _ => Nil
+    }
 
     /** The type arguments of this type are:
      *  For an Applied type, its type arguments.
      *  Inherited by type proxies.
      *  Empty list for all other types.
      */
-    def typeArgs(implicit ctx: Context): List[Type] = Nil
-
-    def isWrong: Boolean = !exists // !!! needed?
-    def exists: Boolean = true
-
-    def & (that: Type)(implicit ctx: Context): Type =
-      if (this eq that) this
-      else if (this.isWrong) that
-      else if (that.isWrong) this
-      else that match {
-        case OrType(that1, that2) =>
-          this & that1 | this & that2
-        case _ =>
-          this match {
-            case OrType(this1, this2) =>
-              this1 & that | this2 & that
-            case _ =>
-              val t1 = mergeIfSub(this, that)
-              if (t1.exists) t1
-              else {
-                val t2 = mergeIfSub(that, this)
-                if (t2.exists) t2
-                else AndType(this, that)
-              }
-          }
-      }
+    final def typeArgs(implicit ctx: Context): List[Type] = this match {
+      case tp: AppliedType =>
+        tp.targs
+      case tp: TypeProxy =>
+        tp.underlying.typeArgs
+      case _ => Nil
+    }
 
-    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 = mergeIfSuper(this, that)
-        if (t1.exists) t1
-        else {
-          val t2 = mergeIfSuper(that, this)
-          if (t2.exists) t2
-          else OrType(this, that)
-        }
-      }
+    final def isWrong: Boolean = !exists // !!! needed?
+    final def exists: Boolean = true
 
-    /** Merge `t1` into `t2` if t1 is a subtype of some part of t2.
-     */
-    private def mergeIfSub(t1: Type, t2: Type)(implicit ctx: Context): Type =
-      if (t1 <:< t2)
-        if (t2 <:< t1) t2 else t1
-      else t2 match {
-        case t2 @ AndType(t21, t22) =>
-          val lower1 = mergeIfSub(t1, t21)
-          if (lower1 eq t21) t2
-          else if (lower1.exists) lower1 & t22
-          else {
-            val lower2 = mergeIfSub(t1, t22)
-            if (lower2 eq t22) t2
-            else if (lower2.exists) t21 & lower2
-            else NoType
-          }
-        case _ =>
-          NoType
-      }
+    final def &(that: Type)(implicit ctx: Context): Type =
+      ctx.glb(this, that)
 
-   /** Merge `t1` into `t2` if t1 is a supertype of some part of t2.
-    */
-    private def mergeIfSuper(t1: Type, t2: Type)(implicit ctx: Context): Type =
-      if (t2 <:< t1)
-        if (t1 <:< t2) t2 else t1
-      else t2 match {
-        case t2 @ OrType(t21, t22) =>
-          val higher1 = mergeIfSuper(t1, t21)
-          if (higher1 eq t21) t2
-          else if (higher1.exists) higher1 | t22
-          else {
-            val higher2 = mergeIfSuper(t1, t22)
-            if (higher2 eq t22) t2
-            else if (higher2.exists) t21 | higher2
-            else NoType
-          }
-        case _ =>
-          NoType
-      }
+    def |(that: Type)(implicit ctx: Context): Type =
+      ctx.lub(this, that)
 
     // hashing
 
+    /** customized hash code of this type.
+     *  NotCached for uncached types. Cached types
+     *  compute hash and use it as the type's hashCode.
+     */
+    def hash: Int
+
     protected def hashSeed = getClass.hashCode
 
     private def finishHash(hashCode: Int, arity: Int): Int = {
@@ -556,50 +460,61 @@ object Types {
       finishHash(hashing.mix(hashSeed, x1.hashCode), 1, tp2, tps3)
   } // end Type
 
-  abstract class UniqueType extends Type {
-    final override val hash = computeHash
-    override def hashCode = hash
-    def computeHash: Int
-  }
+  /** A marker trait for cached types */
+  trait CachedType extends Type
 
   def unique[T <: Type](tp: T)(implicit ctx: Context): T = {
     if (tp.hash == NotCached) tp
     else ctx.root.uniques.findEntryOrUpdate(tp).asInstanceOf[T]
   }
 
-  trait TypeProxy extends Type {
+  /** A marker trait for type proxies.
+   *  Each implementation is expected to redefine the `underlying` method.
+   */
+  abstract class TypeProxy extends Type {
+    /** The type to which this proxy forwards operations. */
     def underlying(implicit ctx: Context): Type
-    override def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): Reference =
-      underlying.findMember(name, pre, excluded)
-    override def parents(implicit ctx: Context) = underlying.parents
-    override def decls(implicit ctx: Context) = underlying.decls
-    override def baseClasses(implicit ctx: Context) = underlying.baseClasses
-    override def memberNames(pre: Type, keepOnly: NameFilter)(implicit ctx: Context) =
-      underlying.memberNames(pre, keepOnly)
-    override def isVolatile(implicit ctx: Context): Boolean = underlying.isVolatile
-    override def normalizedPrefix(implicit ctx: Context) = underlying.normalizedPrefix
-    override def typeParams(implicit ctx: Context) = underlying.typeParams
-    override def typeArgs(implicit ctx: Context) = underlying.typeArgs
   }
 
-  trait TransformingProxy extends TypeProxy {
-    // needed?
+  // Every type has to inherit one of the following four abstract type classes.,
+  // which determine whether the type is cached, and whether
+  // it is a proxy of some other type. The duplication in their methods
+  // is for efficiency.
+
+  /**  Instances of this class are cached and are not proxies. */
+  abstract class CachedGroundType extends Type with CachedType {
+    final val hash = computeHash
+    override final def hashCode = hash
+    def computeHash: Int
   }
 
-  trait SubType extends UniqueType with TypeProxy {
+  /**  Instances of this class are cached and are proxies. */
+  abstract class CachedProxyType extends TypeProxy with CachedType {
+    final val hash = computeHash
+    override final def hashCode = hash
+    def computeHash: Int
+  }
 
+  /**  Instances of this class are uncached and are not proxies. */
+  abstract class UncachedGroundType extends Type {
+    final def hash = NotCached
   }
 
-  trait SingletonType extends SubType {
-    override def isStable(implicit ctx: Context) = true
-    override def widen(implicit ctx: Context): Type = underlying.widen
+  /**  Instances of this class are uncached and are proxies. */
+  abstract class UncachedProxyType extends TypeProxy {
+    final def hash = NotCached
   }
 
-// --- NamedTypes ------------------------------------------------------------------
+  /** A marker trait for types that are guaranteed to contain only a
+   *  single non-null value (they might contain null in addition).
+   */
+  trait SingletonType extends TypeProxy
+
+  // --- NamedTypes ------------------------------------------------------------------
 
   /** A NamedType of the form Prefix # name
    */
-  abstract class NamedType extends UniqueType with TypeProxy {
+  abstract class NamedType extends CachedProxyType {
 
     val prefix: Type
     val name: Name
@@ -626,13 +541,10 @@ object Types {
     def symbol(implicit ctx: Context): Symbol = referenced.symbol
     def info(implicit ctx: Context): Type = referenced.info
 
-    def underlying(implicit ctx: Context): Type = info
+    override def underlying(implicit ctx: Context): Type = info
 
     def isAbstractType(implicit ctx: Context) = info.isRealTypeBounds
 
-    override def normalizedPrefix(implicit ctx: Context) =
-      if (isAbstractType) info.normalizedPrefix else prefix
-
     def derivedNamedType(prefix: Type, name: Name)(implicit ctx: Context): Type =
       if (prefix eq this.prefix) this
       else NamedType(prefix, name)
@@ -640,14 +552,9 @@ object Types {
     override def computeHash = doHash(name, prefix)
   }
 
-  abstract case class TermRef(override val prefix: Type, name: TermName) extends NamedType with SingletonType {
-    override def termSymbol(implicit ctx: Context): Symbol = symbol
-    override def isStable(implicit ctx: Context) = prefix.isStable && termSymbol.isStable
-  }
+  abstract case class TermRef(override val prefix: Type, name: TermName) extends NamedType with SingletonType
 
-  abstract case class TypeRef(override val prefix: Type, name: TypeName) extends NamedType {
-    override def typeSymbol(implicit ctx: Context): Symbol = symbol
-  }
+  abstract case class TypeRef(override val prefix: Type, name: TypeName) extends NamedType
 
   trait NamedNoPrefix extends NamedType {
     protected val fixedSym: Symbol
@@ -657,7 +564,7 @@ object Types {
   }
 
   final class TermRefNoPrefix(val fixedSym: TermSymbol)(implicit ctx: Context)
-        extends TermRef(NoPrefix, fixedSym.name) with NamedNoPrefix {
+    extends TermRef(NoPrefix, fixedSym.name) with NamedNoPrefix {
     validPeriods = allPeriods(ctx.runId)
   }
 
@@ -668,12 +575,12 @@ object Types {
   }
 
   final class TypeRefNoPrefix(val fixedSym: TypeSymbol)(implicit ctx: Context)
-        extends TypeRef(NoPrefix, fixedSym.name) with NamedNoPrefix {
+    extends TypeRef(NoPrefix, fixedSym.name) with NamedNoPrefix {
     validPeriods = allPeriods(ctx.runId)
   }
 
-  final class UniqueTermRef(prefix: Type, name: TermName) extends TermRef(prefix, name)
-  final class UniqueTypeRef(prefix: Type, name: TypeName) extends TypeRef(prefix, name)
+  final class CachedTermRef(prefix: Type, name: TermName) extends TermRef(prefix, name)
+  final class CachedTypeRef(prefix: Type, name: TypeName) extends TypeRef(prefix, name)
 
   object NamedType {
     def apply(prefix: Type, name: Name)(implicit ctx: Context) =
@@ -683,7 +590,7 @@ object Types {
 
   object TermRef {
     def apply(prefix: Type, name: TermName)(implicit ctx: Context) =
-      unique(new UniqueTermRef(prefix, name))
+      unique(new CachedTermRef(prefix, name))
     def apply(sym: TermSymbol)(implicit ctx: Context) =
       unique(new TermRefNoPrefix(sym))
     def apply(prefix: Type, name: TermName, signature: Signature)(implicit ctx: Context) =
@@ -692,89 +599,79 @@ object Types {
 
   object TypeRef {
     def apply(prefix: Type, name: TypeName)(implicit ctx: Context) =
-      unique(new UniqueTypeRef(prefix, name))
+      unique(new CachedTypeRef(prefix, name))
     def apply(sym: TypeSymbol)(implicit ctx: Context) =
       unique(new TypeRefNoPrefix(sym))
   }
 
-// --- Other SingletonTypes: ThisType/SuperType/ConstantType ---------------------------
+  // --- Other SingletonTypes: ThisType/SuperType/ConstantType ---------------------------
 
-  abstract case class ThisType(clazz: ClassSymbol) extends SingletonType {
-    def underlying(implicit ctx: Context) = clazz.typeOfThis
-    override def isVolatile(implicit ctx: Context): Boolean = false
+  abstract case class ThisType(clazz: ClassSymbol) extends CachedProxyType with SingletonType {
+    override def underlying(implicit ctx: Context) = clazz.typeOfThis
     override def computeHash = doHash(clazz)
   }
 
-  final class UniqueThisType(clazz: ClassSymbol) extends ThisType(clazz)
+  final class CachedThisType(clazz: ClassSymbol) extends ThisType(clazz)
 
   object ThisType {
     def apply(clazz: ClassSymbol)(implicit ctx: Context) =
-      unique(new UniqueThisType(clazz))
+      unique(new CachedThisType(clazz))
   }
 
-  abstract case class SuperType(thistpe: Type, supertpe: Type) extends SingletonType {
-    def underlying(implicit ctx: Context) = supertpe
+  abstract case class SuperType(thistpe: Type, supertpe: Type) extends CachedProxyType with SingletonType {
+    override def underlying(implicit ctx: Context) = supertpe
     def derivedSuperType(thistp: Type, supertp: Type)(implicit ctx: Context) =
       if ((thistp eq thistpe) && (supertp eq supertpe)) this
       else SuperType(thistp, supertp)
     override def computeHash = doHash(thistpe, supertpe)
   }
 
-  final class UniqueSuperType(thistpe: Type, supertpe: Type) extends SuperType(thistpe, supertpe)
+  final class CachedSuperType(thistpe: Type, supertpe: Type) extends SuperType(thistpe, supertpe)
 
   object SuperType {
     def apply(thistpe: Type, supertpe: Type)(implicit ctx: Context) =
-      unique(new UniqueSuperType(thistpe, supertpe))
+      unique(new CachedSuperType(thistpe, supertpe))
   }
 
-  abstract case class ConstantType(value: Constant) extends SingletonType {
-    def underlying(implicit ctx: Context) = value.tpe
-    override def deconst: Type = value.tpe
+  abstract case class ConstantType(value: Constant) extends CachedProxyType with SingletonType {
+    override def underlying(implicit ctx: Context) = value.tpe
     override def computeHash = doHash(value)
   }
 
-  final class UniqueConstantType(value: Constant) extends ConstantType(value)
+  final class CachedConstantType(value: Constant) extends ConstantType(value)
 
   object ConstantType {
     def apply(value: Constant)(implicit ctx: Context) =
-      unique(new UniqueConstantType(value))
+      unique(new CachedConstantType(value))
   }
 
   // --- AppliedType -----------------------------------------------------------------
 
-  abstract case class AppliedType(tycon: Type, targs: List[Type]) extends UniqueType with TypeProxy {
+  abstract case class AppliedType(tycon: Type, targs: List[Type]) extends CachedProxyType {
 
-    def underlying(implicit ctx: Context) = tycon
+    override def underlying(implicit ctx: Context) = tycon
 
     def derivedAppliedType(tycon: Type, targs: List[Type])(implicit ctx: Context): Type =
       if ((tycon eq this.tycon) && (targs eq this.targs)) this
       else AppliedType(tycon, targs)
 
     override def computeHash = doHash(tycon, targs)
-
-    override def typeParams(implicit ctx: Context): List[TypeSymbol] =
-      tycon.typeParams drop targs.length
-
-    override def typeArgs(implicit ctx: Context): List[Type] = targs
-
-    override def parents(implicit ctx: Context) =
-      tycon.parents.mapConserve(_.subst(tycon.typeParams, targs))
-
   }
-  final class UniqueAppliedType(tycon: Type, targs: List[Type]) extends AppliedType(tycon, targs)
+
+  final class CachedAppliedType(tycon: Type, targs: List[Type]) extends AppliedType(tycon, targs)
 
   object AppliedType {
     def apply(tycon: Type, targs: List[Type])(implicit ctx: Context) =
-      unique(new UniqueAppliedType(tycon, targs))
+      unique(new CachedAppliedType(tycon, targs))
     def make(tycon: Type, targs: List[Type])(implicit ctx: Context) =
       if (targs.isEmpty) tycon else apply(tycon, targs)
   }
 
-// --- Refined Type ---------------------------------------------------------
+  // --- Refined Type ---------------------------------------------------------
 
-  case class RefinedType(parent: Type, names: List[Name])(infosExpr: RefinedType => List[Type]) extends UniqueType with TypeProxy {
+  case class RefinedType(parent: Type, names: List[Name])(infosExpr: RefinedType => List[Type]) extends CachedProxyType {
 
-    def underlying(implicit ctx: Context) = parent
+    override def underlying(implicit ctx: Context) = parent
 
     lazy val infos = infosExpr(this)
 
@@ -799,20 +696,12 @@ object Types {
       ref
     }
 
-    override def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): Reference =
-      parent.findMember(name, pre, excluded | Flags.Private) &
-      findDecl(name, pre)
-
-    override def memberNames(pre: Type, keepOnly: NameFilter)(implicit ctx: Context): Set[Name] =
-      parent.memberNames(pre, keepOnly) ++ (names filter (keepOnly(pre, _))).toSet
-
-    def computeHash = doHash(names, parent, infos)
+    override def computeHash = doHash(names, parent, infos)
   }
 
+  // --- AndType/OrType ---------------------------------------------------------------
 
-// --- AndType/OrType ---------------------------------------------------------------
-
-  abstract case class AndType(tp1: Type, tp2: Type) extends UniqueType {
+  abstract case class AndType(tp1: Type, tp2: Type) extends CachedGroundType {
 
     type This <: AndType
 
@@ -820,65 +709,55 @@ object Types {
       if ((t1 eq tp1) && (t2 eq tp2)) this
       else AndType(t1, t2)
 
-    override def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): Reference =
-      tp1.findMember(name, pre, excluded) & tp2.findMember(name, pre, excluded)
-
-    override def memberNames(pre: Type, keepOnly: NameFilter)(implicit ctx: Context): Set[Name] =
-      tp1.memberNames(pre, keepOnly) | tp2.memberNames(pre, keepOnly)
-
-    override def parents(implicit ctx: Context): List[Type] = {
-      def components(tp: Type): List[Type] = tp match {
-        case AndType(tp1, tp2) => components(tp1) ++ components(tp2)
-        case _ => List(tp)
-      }
-      components(this)
-    }
-
     override def computeHash = doHash(tp1, tp2)
   }
 
-  final class UniqueAndType(tp1: Type, tp2: Type) extends AndType(tp1, tp2)
+  final class CachedAndType(tp1: Type, tp2: Type) extends AndType(tp1, tp2)
 
   object AndType {
     def apply(tp1: Type, tp2: Type)(implicit ctx: Context) =
-      unique(new UniqueAndType(tp1, tp2))
+      unique(new CachedAndType(tp1, tp2))
   }
 
-  abstract case class OrType(tp1: Type, tp2: Type) extends UniqueType {
+  abstract case class OrType(tp1: Type, tp2: Type) extends CachedGroundType {
     def derivedOrType(t1: Type, t2: Type)(implicit ctx: Context) =
       if ((t1 eq tp1) && (t2 eq tp2)) this
       else OrType(t1, t2)
 
-    override def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): Reference = {
-      (tp1.findMember(name, pre, excluded) | tp2.findMember(name, pre, excluded))(pre)
-    }
-
-    override def memberNames(pre: Type, keepOnly: NameFilter)(implicit ctx: Context): Set[Name] =
-      tp1.memberNames(pre, keepOnly) & tp2.memberNames(pre, keepOnly)
-
     override def computeHash = doHash(tp1, tp2)
   }
 
-  final class UniqueOrType(tp1: Type, tp2: Type) extends OrType(tp1, tp2)
+  final class CachedOrType(tp1: Type, tp2: Type) extends OrType(tp1, tp2)
 
   object OrType {
     def apply(tp1: Type, tp2: Type)(implicit ctx: Context) =
-      unique(new UniqueOrType(tp1, tp2))
+      unique(new CachedOrType(tp1, tp2))
   }
 
-// ----- Method types: MethodType/ExprType/PolyType/MethodParam/PolyParam ---------------
+  // ----- Method types: MethodType/ExprType/PolyType/MethodParam/PolyParam ---------------
+
+  // Note: method types are cached whereas poly types are not.
+  // The reason is that most poly types are cyclic via poly params,
+  // and therefore two different poly types would never be equal.
 
-  abstract case class MethodType(paramNames: List[TermName], paramTypes: List[Type])(resultTypeExp: MethodType => Type) extends UniqueType {
+  abstract case class MethodType(paramNames: List[TermName], paramTypes: List[Type])(resultTypeExp: MethodType => Type) extends CachedGroundType {
     lazy val resultType = resultTypeExp(this)
     def isJava = false
     def isImplicit = false
+
     lazy val isDependent = resultType exists {
       case MethodParam(mt, _) => mt eq this
       case _ => false
     }
-    def paramSig(tp: Type): TypeName = ???
-    override lazy val signature: Signature =
-      (paramTypes map paramSig) ++ resultType.subSignature
+
+    override lazy val signature: List[TypeName] = {
+      def paramSig(tp: Type): TypeName = ???
+      val followSig = resultType match {
+        case rtp: MethodType => rtp.signature
+        case _ => Nil
+      }
+      (paramTypes map paramSig) ++ followSig
+    }
 
     def derivedMethodType(paramNames: List[TermName], paramTypes: List[Type], restpe: Type)(implicit ctx: Context) =
       if ((paramNames eq this.paramNames) && (paramTypes eq this.paramTypes) && (restpe eq this.resultType)) this
@@ -896,52 +775,53 @@ object Types {
     override def computeHash = doHash(paramNames, resultType, paramTypes)
   }
 
-  final class UniqueMethodType(paramNames: List[TermName], paramTypes: List[Type])
-      (resultTypeExp: MethodType => Type)
-      extends MethodType(paramNames, paramTypes)(resultTypeExp)
-  final class JavaMethodType(paramNames: List[TermName], paramTypes: List[Type])
-      (resultTypeExp: MethodType => Type)
-      extends MethodType(paramNames, paramTypes)(resultTypeExp) {
+  final class CachedMethodType(paramNames: List[TermName], paramTypes: List[Type])(resultTypeExp: MethodType => Type)
+    extends MethodType(paramNames, paramTypes)(resultTypeExp)
+
+  final class JavaMethodType(paramNames: List[TermName], paramTypes: List[Type])(resultTypeExp: MethodType => Type)
+    extends MethodType(paramNames, paramTypes)(resultTypeExp) {
     override def isJava = true
   }
-  final class ImplicitMethodType(paramNames: List[TermName], paramTypes: List[Type])
-      (resultTypeExp: MethodType => Type)
-      extends MethodType(paramNames, paramTypes)(resultTypeExp) {
+
+  final class ImplicitMethodType(paramNames: List[TermName], paramTypes: List[Type])(resultTypeExp: MethodType => Type)
+    extends MethodType(paramNames, paramTypes)(resultTypeExp) {
     override def isImplicit = true
   }
 
   object MethodType {
     def apply(paramNames: List[TermName], paramTypes: List[Type])(resultTypeExp: MethodType => Type)(implicit ctx: Context) =
-      unique(new UniqueMethodType(paramNames, paramTypes)(resultTypeExp))
+      unique(new CachedMethodType(paramNames, paramTypes)(resultTypeExp))
   }
+
   def JavaMethodType(paramNames: List[TermName], paramTypes: List[Type])(resultTypeExp: MethodType => Type)(implicit ctx: Context) =
     unique(new JavaMethodType(paramNames, paramTypes)(resultTypeExp))
+
   def ImplicitMethodType(paramNames: List[TermName], paramTypes: List[Type])(resultTypeExp: MethodType => Type)(implicit ctx: Context) =
     unique(new ImplicitMethodType(paramNames, paramTypes)(resultTypeExp))
 
-  abstract case class ExprType(resultType: Type) extends UniqueType with TypeProxy {
-    def underlying(implicit ctx: Context): Type = resultType
+  abstract case class ExprType(resultType: Type) extends CachedProxyType {
+    override def underlying(implicit ctx: Context): Type = resultType
     def derivedExprType(rt: Type)(implicit ctx: Context) =
       if (rt eq resultType) this else ExprType(rt)
     override def computeHash = doHash(resultType)
   }
 
-  final class UniqueExprType(resultType: Type) extends ExprType(resultType)
+  final class CachedExprType(resultType: Type) extends ExprType(resultType)
 
   object ExprType {
     def apply(resultType: Type)(implicit ctx: Context) =
-      unique(new UniqueExprType(resultType))
+      unique(new CachedExprType(resultType))
   }
 
-  case class PolyType(paramNames: List[TypeName])(paramBoundsExp: PolyType => List[TypeBounds], resultTypeExp: PolyType => Type) extends Type {
+  case class PolyType(paramNames: List[TypeName])(paramBoundsExp: PolyType => List[TypeBounds], resultTypeExp: PolyType => Type) extends UncachedGroundType {
     lazy val paramBounds = paramBoundsExp(this)
     lazy val resultType = resultTypeExp(this)
 
+    override def signature = resultType.signature
+
     def instantiate(argTypes: List[Type])(implicit ctx: Context): Type =
       new InstPolyMap(this, argTypes) apply resultType
 
-    override def signature: Signature = resultType.subSignature
-
     def derivedPolyType(paramNames: List[TypeName], paramBounds: List[TypeBounds], restpe: Type)(implicit ctx: Context) =
       if ((paramNames eq this.paramNames) && (paramBounds eq this.paramBounds) && (restpe eq this.resultType)) this
       else
@@ -949,6 +829,8 @@ object Types {
           x => paramBounds mapConserve (_.substBounds(this, x)),
           x => restpe.subst(this, x))
 
+    // need to override hashCode and equals to be object identity
+    // because paramNames by itself is not discriminatory enough
     override def hashCode = System.identityHashCode(this)
     override def equals(other: Any) = other match {
       case that: PolyType => this eq that
@@ -956,24 +838,24 @@ object Types {
     }
   }
 
-  case class MethodParam(mt: MethodType, paramNum: Int) extends SingletonType {
-    def underlying(implicit ctx: Context) = mt.paramTypes(paramNum)
-    override def computeHash = NotCached
+  case class MethodParam(mt: MethodType, paramNum: Int) extends UncachedProxyType with SingletonType {
+    override def underlying(implicit ctx: Context) = mt.paramTypes(paramNum)
+    override def hashCode = doHash(System.identityHashCode(mt) + paramNum)
   }
 
-  case class RefinedThis(rt: RefinedType) extends SingletonType {
-    def underlying(implicit ctx: Context) = rt.parent
-    override def computeHash = NotCached
+  case class RefinedThis(rt: RefinedType) extends UncachedProxyType with SingletonType {
+    override def underlying(implicit ctx: Context) = rt.parent
+    override def hashCode = doHash(System.identityHashCode(rt))
   }
 
-  case class PolyParam(pt: PolyType, paramNum: Int) extends TypeProxy {
-    def underlying(implicit ctx: Context) = pt.paramBounds(paramNum).hi
+  case class PolyParam(pt: PolyType, paramNum: Int) extends UncachedProxyType {
+    override def underlying(implicit ctx: Context) = pt.paramBounds(paramNum).hi
+    // no hashCode needed because cycle is broken in PolyType
   }
 
-// ------ ClassInfo, Type Bounds ------------------------------------------------------------
+  // ------ ClassInfo, Type Bounds ------------------------------------------------------------
 
-  abstract case class ClassInfo(prefix: Type, classd: ClassDenotation) extends UniqueType {
-    override def typeSymbol(implicit ctx: Context) = classd.clazz
+  abstract case class ClassInfo(prefix: Type, classd: ClassDenotation) extends CachedGroundType {
 
     def typeTemplate(implicit ctx: Context): Type =
       classd.typeTemplate asSeenFrom (prefix, classd.clazz)
@@ -981,62 +863,28 @@ object Types {
     def typeConstructor(implicit ctx: Context): Type =
       NamedType(prefix, classd.clazz.name)
 
-    override def normalizedPrefix(implicit ctx: Context) = prefix
-
-    override def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): Reference =
-      findMemberAmong(classd.memberRefsNamed(name), pre, classd.clazz, excluded)
-
-    private def findMemberAmong(candidates: RefSet, pre: Type, owner: ClassSymbol, excluded: FlagSet)
-        (implicit ctx: Context): Reference = {
-      val resultSyms = candidates
-        .filterAccessibleFrom(pre)
-        .filterExcluded(excluded)
-        .asSeenFrom(pre, owner)
-      if (resultSyms.exists) resultSyms.toRef
-      else ErrorRef // todo: refine
-    }
-
-    override def baseClasses(implicit ctx: Context): List[ClassSymbol] =
-      classd.baseClasses
-
-    override def memberNames(pre: Type, keepOnly: NameFilter)(implicit ctx: Context): Set[Name] =
-      classd.memberNames(keepOnly) filter (keepOnly(pre, _))
-
-    private var parentsCache: List[Type] = null
+    private[Types] var parentsCache: List[Type] = null
     // !!! caching needed here? If yes, cache AppliedType as well?
 
-    override def decls(implicit ctx: Context) = classd.decls
-
-    override def parents(implicit ctx: Context) = {
-      if (parentsCache == null)
-        parentsCache = classd.parents.mapConserve(_.substThis(classd.clazz, prefix))
-      parentsCache
-    }
-
-    override def typeParams(implicit ctx: Context) = classd.typeParams
-
     override def computeHash = doHash(classd.clazz, prefix)
   }
 
-  final class UniqueClassInfo(prefix: Type, classd: ClassDenotation) extends ClassInfo(prefix, classd)
+  final class CachedClassInfo(prefix: Type, classd: ClassDenotation) extends ClassInfo(prefix, classd)
 
   object ClassInfo {
     def apply(prefix: Type, classd: ClassDenotation)(implicit ctx: Context) =
-      unique(new UniqueClassInfo(prefix, classd))
+      unique(new CachedClassInfo(prefix, classd))
   }
 
-  abstract case class TypeBounds(lo: Type, hi: Type) extends UniqueType with TypeProxy {
-    def underlying(implicit ctx: Context): Type = hi
+  abstract case class TypeBounds(lo: Type, hi: Type) extends CachedProxyType {
+    override def underlying(implicit ctx: Context): Type = hi
     def derivedTypeBounds(lo1: Type, hi1: Type)(implicit ctx: Context) =
       if ((lo1 eq lo) && (hi1 eq hi)) this
       else TypeBounds(lo, hi)
 
-    override def isRealTypeBounds = lo ne hi
-    override def bounds(implicit ctx: Context): TypeBounds = this
-
-    def & (that: TypeBounds)(implicit ctx: Context): TypeBounds =
+    def &(that: TypeBounds)(implicit ctx: Context): TypeBounds =
       TypeBounds(this.lo | that.lo, this.hi & that.hi)
-    def | (that: TypeBounds)(implicit ctx: Context): TypeBounds =
+    def |(that: TypeBounds)(implicit ctx: Context): TypeBounds =
       TypeBounds(this.lo & that.lo, this.hi | that.hi)
 
     def substBounds(from: PolyType, to: PolyType)(implicit ctx: Context) =
@@ -1044,20 +892,21 @@ object Types {
 
     def map(f: Type => Type)(implicit ctx: Context): TypeBounds =
       TypeBounds(f(lo), f(hi))
+
     override def computeHash = doHash(lo, hi)
   }
 
-  final class UniqueTypeBounds(lo: Type, hi: Type) extends TypeBounds(lo, hi)
+  final class CachedTypeBounds(lo: Type, hi: Type) extends TypeBounds(lo, hi)
 
   object TypeBounds {
     def apply(lo: Type, hi: Type)(implicit ctx: Context) =
-      unique(new UniqueTypeBounds(lo, hi))
+      unique(new CachedTypeBounds(lo, hi))
   }
 
-// ----- AnnotatedTypes -----------------------------------------------------------
+  // ----- AnnotatedTypes -----------------------------------------------------------
 
-  case class AnnotatedType(annots: List[AnnotationInfo], tpe: Type) extends TypeProxy {
-    def underlying(implicit ctx: Context): Type = tpe
+  case class AnnotatedType(annots: List[AnnotationInfo], tpe: Type) extends UncachedProxyType {
+    override def underlying(implicit ctx: Context): Type = tpe
     def derivedAnnotatedType(annots1: List[AnnotationInfo], tpe1: Type) =
       if ((annots1 eq annots) && (tpe1 eq tpe)) this
       else AnnotatedType.make(annots1, tpe1)
@@ -1069,24 +918,25 @@ object Types {
       else AnnotatedType(annots, underlying)
   }
 
-// Special type objects ------------------------------------------------------------
+  // Special type objects ------------------------------------------------------------
 
-  case object NoType extends Type {
+  case object NoType extends UncachedGroundType {
     def symbol = NoSymbol
     def info = NoType
   }
 
-  case object NoPrefix extends UniqueType {
+  /** Cached for efficiency because hashing is faster */
+  case object NoPrefix extends CachedGroundType {
     override def computeHash = hashSeed
   }
 
-  abstract class ErrorType extends Type
+  abstract class ErrorType extends UncachedGroundType
 
   object ErrorType extends ErrorType
 
-  case object WildcardType extends Type
+  case object WildcardType extends UncachedGroundType
 
-// ----- TypeMaps --------------------------------------------------------------------
+  // ----- TypeMaps --------------------------------------------------------------------
 
   abstract class TypeMap(implicit ctx: Context) extends (Type => Type) {
     def apply(tp: Type): Type
@@ -1096,12 +946,12 @@ object Types {
 
     /** Map this function over given type */
     def mapOver(tp: Type): Type = tp match {
-      case tp: NamedType   =>
+      case tp: NamedType =>
         tp.derivedNamedType(this(tp.prefix), tp.name)
 
       case ThisType(_)
-         | MethodParam(_, _)
-         | PolyParam(_, _) => tp
+        | MethodParam(_, _)
+        | PolyParam(_, _) => tp
 
       case tp @ AppliedType(tycon, targs) =>
         tp.derivedAppliedType(this(tycon), targs mapConserve this)
@@ -1162,14 +1012,7 @@ object Types {
     }
   }
 
-  class AsSeenFromMap(pre: Type, clazz: Symbol)(implicit ctx: Context) extends TypeMap {
-    def apply(tp: Type) = tp.asSeenFrom(pre, clazz, this)
-  }
-
-// todo: prevent unstable prefixes in variables?
-
-
-// ----- TypeAccumulators ----------------------------------------------------
+  // ----- TypeAccumulators ----------------------------------------------------
 
   abstract class TypeAccumulator[T] extends ((T, Type) => T) {
     def apply(x: T, tp: Type): T
@@ -1180,20 +1023,20 @@ object Types {
       case tp: NamedType =>
         this(x, tp.prefix)
 
-     case ThisType(_)
-         | MethodParam(_, _)
-         | PolyParam(_, _)
-         | ConstantType(_)
-         | NoPrefix => x
+      case ThisType(_)
+        | MethodParam(_, _)
+        | PolyParam(_, _)
+        | ConstantType(_)
+        | NoPrefix => x
 
       case AppliedType(tycon, targs) =>
-        (this(x, tycon) /: targs) (this)
+        (this(x, tycon) /: targs)(this)
 
       case tp @ PolyType(pnames) =>
-        this((x /: tp.paramBounds) (this), tp.resultType)
+        this((x /: tp.paramBounds)(this), tp.resultType)
 
       case tp @ MethodType(pnames, ptypes) =>
-        this((x /: ptypes) (this), tp.resultType)
+        this((x /: ptypes)(this), tp.resultType)
 
       case ExprType(restpe) =>
         this(x, restpe)
@@ -1205,10 +1048,10 @@ object Types {
         this(this(x, lo), hi)
 
       case tp @ RefinedType(parent, names) =>
-        (this(x, parent) /: tp.infos) (apply)
+        (this(x, parent) /: tp.infos)(apply)
 
       case AnnotatedType(annots, underlying) =>
-        this((x /: annots) (apply), underlying)
+        this((x /: annots)(apply), underlying)
 
       case _ => x
     }
@@ -1218,7 +1061,7 @@ object Types {
     def apply(x: Boolean, tp: Type) = x || p(tp) || foldOver(x, tp)
   }
 
-// ----- Name Filters --------------------------------------------------
+  // ----- Name Filters --------------------------------------------------
 
   /** A name filter selects or discards a member name of a type `pre`.
    *  To enable efficient caching, name filters have to satisfy the
@@ -1243,18 +1086,14 @@ object Types {
       name.isTermName && (pre member name).symbol.isDeferred
   }
 
-// ----- Exceptions -------------------------------------------------------------
+  // ----- Exceptions -------------------------------------------------------------
 
   class TypeError(msg: String) extends Exception(msg)
   class FatalTypeError(msg: String) extends TypeError(msg)
   class MalformedType(pre: Type, sym: Symbol) extends FatalTypeError(s"malformed type: $pre.$sym")
   class CyclicReference(sym: Symbol) extends FatalTypeError("cyclic reference involving $sym")
 
-// ----- Implicit decorators ---------------------------------------------------
-
-  implicit def substOps(tp: Type): SubstOps = new SubstOps(tp)
-
-// ----- Misc utilities ---------------------------------------------------------
+  // ----- Misc utilities ---------------------------------------------------------
 
   /** like map2, but returns list `xs` itself - instead of a copy - if function
    *  `f` maps all elements to themselves.