path: root/src/dotty/tools/dotc/core/Types.scala

package dotty.tools.dotc
package core

import util.HashSet
import Symbols._
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 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
   *  cached in uniques.
   */
  final val NotCached = 0

  /** An alternative value returned from `hash` if the
   *  computed hashCode would be `NotCached`.
   */
  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
   */
  abstract class Type extends DotClass {

    def hash = NotCached

    /** The type symbol associated with the type */
    def typeSymbol(implicit ctx: Context): Symbol = NoSymbol

    /** The term symbol associated with the type */
    def termSymbol(implicit ctx: Context): Symbol = NoSymbol

    /** Does this type denote a stable reference (i.e. singleton type)? */
    def isStable(implicit ctx: Context): Boolean = 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 =
      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] =
      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] =
      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] =
      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()

    /** Is this type a TypeBounds instance, with lower and upper bounds
     *  that are not identical?
     */
    def isRealTypeBounds: Boolean = false

    /** 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
     *  be empty), one of the parent types Pi is an abstract type, and
     *  either decls or a different parent Pj, j != i, contributes
     *  an abstract member.
     *
     *  A type contributes an abstract member if it has an abstract member which
     *  is also a member of the whole refined type. A scope `decls` contributes
     *  an abstract member if it has an abstract definition which is also
     *  a member of the whole type.
     *
     *  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
      }
    }

    /** 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)

    /** 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 =
      if (from.isEmpty) this
      else {
        val from1 = from.tail
        if (from1.isEmpty) new SubstOps(this).subst1(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)
        }
      }

    /** 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)

    /** 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)
      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)

    /** 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)

    /** 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()

    /** The normalized prefix of this type is:
     *  For an alias type, the normalized prefix of its alias
     *  For all other named type and class infos: the prefix.
     *  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)

    /** 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

    /** The declaration of this type with given name */
    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 =
      findMember(name, this, Flags.Empty)

    /** The non-private member of this type with given name */
    def nonPrivateMember(name: Name)(implicit ctx: Context): Reference =
      findMember(name, this, Flags.Private)

    /** Find member of this type with given name and
     *  produce a reference that contains the type of the member
     *  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")

    /** Is this type a subtype of that type? */
    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 =
      ctx.subTyper.isSameType(this, that)

    /** Widen from singleton type to its underlying non-singleton
     *  base type by applying one or more `underlying` dereferences,
     *  identity for all other types. Example:
     *
     *  class Outer { class C ; val x: C }
     *  val o: Outer
     *  <o.x.type>.widen = o.C
     */
    def widen(implicit ctx: Context): Type = this

    /** Widen from constant type to its underlying non-constant
     *  base type.
     */
    def deconst: Type = this

    //def resultType: Type = ???

    /** The base classes of this type as determined by ClassDenotation.
     *  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
          }
      }
    }

    def signature: Signature = NullSignature
    def subSignature: Signature = List()

    def baseType(base: Symbol)(implicit ctx: Context): Type = base.deref match {
      case classd: ClassDenotation => classd.baseTypeOf(this)
      case _ => NoType
    }

    /** The type parameters of this type are:
     *  For a ClassInfo type, the type parameters of its denotation.
     *  For an applied type, the type parameters of its constructor
     *  that have not been instantiated yet.
     *  Inherited by type proxies.
     *  Empty list for all other types.
     */
    def typeParams(implicit ctx: Context): List[TypeSymbol] = 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)
              }
          }
      }

    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)
        }
      }

    /** 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
      }

   /** 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
      }

    // hashing

    protected def hashSeed = getClass.hashCode

    private def finishHash(hashCode: Int, arity: Int): Int = {
      val h = hashing.finalizeHash(hashCode, arity)
      if (h == NotCached) NotCachedAlt else h
    }

    private def finishHash(seed: Int, arity: Int, tp: Type): Int = {
      val elemHash = tp.hash
      if (elemHash == NotCached) return NotCached
      finishHash(hashing.mix(seed, elemHash), arity + 1)
    }

    private def finishHash(seed: Int, arity: Int, tps: List[Type]): Int = {
      var h = seed
      var xs = tps
      var len = arity
      while (xs.nonEmpty) {
        val elemHash = xs.head.hash
        if (elemHash == NotCached) return NotCached
        h = hashing.mix(h, elemHash)
        xs = xs.tail
        len += 1
      }
      finishHash(h, len)
    }

    private def finishHash(seed: Int, arity: Int, tp: Type, tps: List[Type]): Int = {
      val elemHash = tp.hash
      if (elemHash == NotCached) return NotCached
      finishHash(hashing.mix(seed, elemHash), arity + 1, tps)
    }

    protected def doHash(x: Any): Int =
      finishHash(hashing.mix(hashSeed, x.hashCode), 1)

    protected def doHash(tp: Type): Int =
      finishHash(hashSeed, 0, tp)

    protected def doHash(tp1: Type, tp2: Type): Int = {
      val elemHash = tp1.hash
      if (elemHash == NotCached) return NotCached
      finishHash(hashing.mix(hashSeed, elemHash), 1, tp2)
    }

    protected def doHash(x1: Any, tp2: Type): Int =
      finishHash(hashing.mix(hashSeed, x1.hashCode), 1, tp2)

    protected def doHash(tp1: Type, tps2: List[Type]): Int =
      finishHash(hashSeed, 0, tp1, tps2)

    protected def doHash(x1: Any, tp2: Type, tps3: List[Type]): Int =
      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
  }

  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 {
    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?
  }

  trait SubType extends UniqueType with TypeProxy {

  }

  trait SingletonType extends SubType {
    override def isStable(implicit ctx: Context) = true
    override def widen(implicit ctx: Context): Type = underlying.widen
  }

// --- NamedTypes ------------------------------------------------------------------

  /** A NamedType of the form Prefix # name
   */
  abstract class NamedType extends UniqueType with TypeProxy {

    val prefix: Type
    val name: Name

    private[this] var referencedVar: Reference = null
    protected[this] var validPeriods = Nowhere

    private def checkPrefix(sym: Symbol) =
      sym.isAbstractType || sym.isClass

    def referenced(implicit ctx: Context): Reference = {
      if (!containsPeriod(validPeriods, ctx.period)) {
        referencedVar = prefix.member(name)
        validPeriods = ctx.stableInterval
        if (checkPrefix(referencedVar.symbol) && !prefix.isLegalPrefix)
          throw new MalformedType(prefix, referencedVar.symbol)
      }
      referencedVar
    }

    def isType = name.isTypeName
    def isTerm = name.isTermName

    def symbol(implicit ctx: Context): Symbol = referenced.symbol
    def info(implicit ctx: Context): Type = referenced.info

    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)

    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 TypeRef(override val prefix: Type, name: TypeName) extends NamedType {
    override def typeSymbol(implicit ctx: Context): Symbol = symbol
  }

  trait NamedNoPrefix extends NamedType {
    protected val fixedSym: Symbol
    override def symbol(implicit ctx: Context): Symbol = fixedSym
    override def info(implicit ctx: Context): Type = fixedSym.info
    override def referenced(implicit ctx: Context): Reference = new UniqueSymRef(fixedSym, info)
  }

  final class TermRefNoPrefix(val fixedSym: TermSymbol)(implicit ctx: Context)
        extends TermRef(NoPrefix, fixedSym.name) with NamedNoPrefix {
    validPeriods = allPeriods(ctx.runId)
  }

  final class TermRefWithSignature(prefix: Type, name: TermName, override val signature: Signature) extends TermRef(prefix, name) {
    override def computeHash = doHash((name, signature), prefix)
    override def referenced(implicit ctx: Context): Reference =
      super.referenced.atSignature(signature)
  }

  final class TypeRefNoPrefix(val fixedSym: TypeSymbol)(implicit ctx: Context)
        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)

  object NamedType {
    def apply(prefix: Type, name: Name)(implicit ctx: Context) =
      if (name.isTermName) TermRef(prefix, name.asTermName)
      else TypeRef(prefix, name.asTypeName)
  }

  object TermRef {
    def apply(prefix: Type, name: TermName)(implicit ctx: Context) =
      unique(new UniqueTermRef(prefix, name))
    def apply(sym: TermSymbol)(implicit ctx: Context) =
      unique(new TermRefNoPrefix(sym))
    def apply(prefix: Type, name: TermName, signature: Signature)(implicit ctx: Context) =
      unique(new TermRefWithSignature(prefix, name, signature))
  }

  object TypeRef {
    def apply(prefix: Type, name: TypeName)(implicit ctx: Context) =
      unique(new UniqueTypeRef(prefix, name))
    def apply(sym: TypeSymbol)(implicit ctx: Context) =
      unique(new TypeRefNoPrefix(sym))
  }

// --- 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
    override def computeHash = doHash(clazz)
  }

  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 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)

  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 deconst: Type = value.tpe
    override def computeHash = doHash(value)
  }

  final class UniqueConstantType(value: Constant) extends ConstantType(value)

  object ConstantType {
    def apply(value: Constant)(implicit ctx: Context) =
      unique(new UniqueConstantType(value))
  }

  // --- AppliedType -----------------------------------------------------------------

  abstract case class AppliedType(tycon: Type, targs: List[Type]) extends UniqueType with TypeProxy {

    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)

  object AppliedType {
    def apply(tycon: Type, targs: List[Type])(implicit ctx: Context) =
      unique(new UniqueAppliedType(tycon, targs))
    def make(tycon: Type, targs: List[Type])(implicit ctx: Context) =
      if (targs.isEmpty) tycon else apply(tycon, targs)
  }

// --- Refined Type ---------------------------------------------------------

  case class RefinedType(parent: Type, names: List[Name])(infosExpr: RefinedType => List[Type]) extends UniqueType with TypeProxy {

    def underlying(implicit ctx: Context) = parent

    lazy val infos = infosExpr(this)

    def derivedRefinedType(parent1: Type, names1: List[Name], infos1: List[Type])(implicit ctx: Context): RefinedType =
      if ((parent1 eq parent) && (names1 eq names) && (infos1 eq infos)) this
      else
        RefinedType(parent1, names1) { rt =>
          val thistp = RefinedThis(rt)
          infos1 map (_.substThis(this, thistp))
        }

    def findDecl(name: Name, pre: Type)(implicit ctx: Context): Reference = {
      var ns = names
      var is = infos
      var ref: Reference = NoRef
      while (ns.nonEmpty && (ref eq NoRef)) {
        if (ns.head == name)
          ref = new JointSymRef(NoSymbol, is.head.substThis(this, pre))
        ns = ns.tail
        is = is.tail
      }
      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)
  }


// --- AndType/OrType ---------------------------------------------------------------

  abstract case class AndType(tp1: Type, tp2: Type) extends UniqueType {

    type This <: AndType

    def derivedAndType(t1: Type, t2: Type)(implicit ctx: Context) =
      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)

  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(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)

  object OrType {
    def apply(tp1: Type, tp2: Type)(implicit ctx: Context) =
      unique(new UniqueOrType(tp1, tp2))
  }

// ----- Method types: MethodType/ExprType/PolyType/MethodParam/PolyParam ---------------

  abstract case class MethodType(paramNames: List[TermName], paramTypes: List[Type])(resultTypeExp: MethodType => Type) extends UniqueType {
    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

    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
      else {
        val restpeExpr = (x: MethodType) => restpe.subst(this, x)
        if (isJava) JavaMethodType(paramNames, paramTypes)(restpeExpr)
        else if (isImplicit) ImplicitMethodType(paramNames, paramTypes)(restpeExpr)
        else MethodType(paramNames, paramTypes)(restpeExpr)
      }

    def instantiate(argTypes: List[Type])(implicit ctx: Context): Type =
      if (isDependent) new InstMethodMap(this, argTypes) apply resultType
      else resultType

    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) {
    override def isJava = true
  }
  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))
  }
  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
    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)

  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)
    lazy val resultType = resultTypeExp(this)

    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
        PolyType(paramNames)(
          x => paramBounds mapConserve (_.substBounds(this, x)),
          x => restpe.subst(this, x))

    override def hashCode = System.identityHashCode(this)
    override def equals(other: Any) = other match {
      case that: PolyType => this eq that
      case _ => false
    }
  }

  case class MethodParam(mt: MethodType, paramNum: Int) extends SingletonType {
    def underlying(implicit ctx: Context) = mt.paramTypes(paramNum)
    override def computeHash = NotCached
  }

  case class RefinedThis(rt: RefinedType) extends SingletonType {
    def underlying(implicit ctx: Context) = rt.parent
    override def computeHash = NotCached
  }

  case class PolyParam(pt: PolyType, paramNum: Int) extends TypeProxy {
    def underlying(implicit ctx: Context) = pt.paramBounds(paramNum).hi
  }

// ------ ClassInfo, Type Bounds ------------------------------------------------------------

  abstract case class ClassInfo(prefix: Type, classd: ClassDenotation) extends UniqueType {
    override def typeSymbol(implicit ctx: Context) = classd.clazz

    def typeTemplate(implicit ctx: Context): Type =
      classd.typeTemplate asSeenFrom (prefix, classd.clazz)

    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
    // !!! 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)

  object ClassInfo {
    def apply(prefix: Type, classd: ClassDenotation)(implicit ctx: Context) =
      unique(new UniqueClassInfo(prefix, classd))
  }

  abstract case class TypeBounds(lo: Type, hi: Type) extends UniqueType with TypeProxy {
    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 =
      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)

    def substBounds(from: PolyType, to: PolyType)(implicit ctx: Context) =
      subst(from, to).asInstanceOf[TypeBounds]

    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)

  object TypeBounds {
    def apply(lo: Type, hi: Type)(implicit ctx: Context) =
      unique(new UniqueTypeBounds(lo, hi))
  }

// ----- AnnotatedTypes -----------------------------------------------------------

  case class AnnotatedType(annots: List[AnnotationInfo], tpe: Type) extends TypeProxy {
    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)
  }

  object AnnotatedType {
    def make(annots: List[AnnotationInfo], underlying: Type) =
      if (annots.isEmpty) underlying
      else AnnotatedType(annots, underlying)
  }

// Special type objects ------------------------------------------------------------

  case object NoType extends Type {
    def symbol = NoSymbol
    def info = NoType
  }

  case object NoPrefix extends UniqueType {
    override def computeHash = hashSeed
  }

  abstract class ErrorType extends Type

  object ErrorType extends ErrorType

  case object WildcardType extends Type

// ----- TypeMaps --------------------------------------------------------------------

  abstract class TypeMap(implicit ctx: Context) extends (Type => Type) {
    def apply(tp: Type): Type

    def applyToBounds(tp: TypeBounds): TypeBounds =
      apply(tp: Type).asInstanceOf[TypeBounds]

    /** Map this function over given type */
    def mapOver(tp: Type): Type = tp match {
      case tp: NamedType   =>
        tp.derivedNamedType(this(tp.prefix), tp.name)

      case ThisType(_)
         | MethodParam(_, _)
         | PolyParam(_, _) => tp

      case tp @ AppliedType(tycon, targs) =>
        tp.derivedAppliedType(this(tycon), targs mapConserve this)

      case tp @ PolyType(pnames) =>
        tp.derivedPolyType(
          pnames, tp.paramBounds mapConserve applyToBounds, this(tp.resultType))

      case tp @ MethodType(pnames, ptypes) =>
        tp.derivedMethodType(pnames, ptypes mapConserve this, this(tp.resultType))

      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, names) =>
        tp.derivedRefinedType(this(parent), names, tp.infos mapConserve this)

      case tp @ AnnotatedType(annots, underlying) =>
        tp.derivedAnnotatedType(mapOverAnnotations(annots), this(underlying))

      case _ =>
        tp
    }

    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)
    }
  }

  class InstRefinedMap(rt: RefinedType)(implicit ctx: Context) extends TypeMap {
    def apply(tp: Type) = tp match {
      case RefinedThis(`rt`) => rt.parent
      case _ => mapOver(tp)
    }
  }

  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 ----------------------------------------------------

  abstract class TypeAccumulator[T] extends ((T, Type) => T) {
    def apply(x: T, tp: Type): T

    def apply(x: T, annot: AnnotationInfo): T = ???

    def foldOver(x: T, tp: Type): T = tp match {
      case tp: NamedType =>
        this(x, tp.prefix)

     case ThisType(_)
         | MethodParam(_, _)
         | PolyParam(_, _)
         | ConstantType(_)
         | NoPrefix => x

      case AppliedType(tycon, targs) =>
        (this(x, tycon) /: targs) (this)

      case tp @ PolyType(pnames) =>
        this((x /: tp.paramBounds) (this), tp.resultType)

      case tp @ MethodType(pnames, ptypes) =>
        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 tp @ RefinedType(parent, names) =>
        (this(x, parent) /: tp.infos) (apply)

      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)
  }

// ----- 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
   *  following invariant: If `keep` is a name filter, and `pre` has
   *  class `C` as a base class, then
   *
   *    keep(pre, name) => keep(C.this, name)
   */
  abstract class NameFilter {
    def apply(pre: Type, name: Name)(implicit ctx: Context): Boolean
  }

  /** A filter for names of abstract types of a given type */
  object abstractTypeNameFilter extends NameFilter {
    def apply(pre: Type, name: Name)(implicit ctx: Context): Boolean =
      name.isTypeName && (pre member name).info.isRealTypeBounds
  }

  /** A filter for names of deferred term definitions of a given type */
  object abstractTermNameFilter extends NameFilter {
    def apply(pre: Type, name: Name)(implicit ctx: Context): Boolean =
      name.isTermName && (pre member name).symbol.isDeferred
  }

// ----- 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 ---------------------------------------------------------

  /** 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
    }

  /** True if two lists have the same length.  Since calling length on linear sequences
   *  is O(n), it is an inadvisable way to test length equality.
   */
  final def sameLength[T](xs: List[T], ys: List[T]): Boolean = xs match {
    case _ :: xs1 =>
      ys match {
        case _ :: ys1 => sameLength(xs1, ys1)
        case _ => false
      }
    case _ => ys.isEmpty
  }
}