Types.scala

package dotty.tools
package dotc
package core

import util.common._
import Symbols._
import Flags._
import Names._
import StdNames._, NameOps._
import NameKinds.{ShadowedName, SkolemName}
import Scopes._
import Constants._
import Contexts._
import Annotations._
import SymDenotations._
import Decorators._
import Denotations._
import Periods._
import util.Positions.{Position, NoPosition}
import util.Stats._
import util.{DotClass, SimpleMap}
import reporting.diagnostic.Message
import reporting.diagnostic.messages.CyclicReferenceInvolving
import ast.tpd._
import ast.TreeTypeMap
import printing.Texts._
import ast.untpd
import dotty.tools.dotc.transform.Erasure
import printing.Printer
import Hashable._
import Uniques._
import collection.{mutable, Seq, breakOut}
import config.Config
import annotation.tailrec
import Flags.FlagSet
import language.implicitConversions
import scala.util.hashing.{ MurmurHash3 => hashing }
import config.Printers.{core, typr, cyclicErrors}

object Types {

  @sharable private var nextId = 0

  /** Main class representing types.
   *
   *  The principal subclasses and sub-objects are as follows:
   *
   *  ```none
   *  Type -+- ProxyType --+- NamedType ----+--- TypeRef
   *        |              |                 \
   *        |              +- SingletonType-+-+- TermRef
   *        |              |                |
   *        |              |                +--- ThisType
   *        |              |                +--- SuperType
   *        |              |                +--- ConstantType
   *        |              |                +--- TermParamRef
   *        |              |                +----RecThis
   *        |              |                +--- SkolemType
   *        |              +- TypeParamRef
   *        |              +- RefinedOrRecType -+-- RefinedType
   *        |              |                   -+-- RecType
   *        |              +- HKApply
   *        |              +- TypeBounds
   *        |              +- ExprType
   *        |              +- AnnotatedType
   *        |              +- TypeVar
   *        |              +- HKTypeLambda
   *        |
   *        +- GroundType -+- AndType
   *                       +- OrType
   *                       +- MethodOrPoly ---+-- PolyType
   *                                          +-- MethodType ---+- ImplicitMethodType
   *                       |                                    +- JavaMethodType
   *                       +- ClassInfo
   *                       |
   *                       +- NoType
   *                       +- NoPrefix
   *                       +- ErrorType
   *                       +- WildcardType
   *  ```
   *
   *  Note: please keep in sync with copy in `docs/docs/internals/type-system.md`.
   */
  abstract class Type extends DotClass with Hashable with printing.Showable {

// ----- Tests -----------------------------------------------------

    // debug only: a unique identifier for a type
    val uniqId = {
      nextId = nextId + 1
//      if (nextId == 19555)
//        println("foo")
      nextId
    }

    /** Is this type different from NoType? */
    def exists: Boolean = true

    /** This type, if it exists, otherwise `that` type */
    def orElse(that: => Type) = if (exists) this else that

    /** Is this type a value type? */
    final def isValueType: Boolean = this.isInstanceOf[ValueType]

    /** Is the is value type or type lambda? */
    final def isValueTypeOrLambda: Boolean = isValueType || this.isInstanceOf[TypeLambda]

    /** Does this type denote a stable reference (i.e. singleton type)? */
    final def isStable(implicit ctx: Context): Boolean = stripTypeVar match {
      case tp: TermRef => tp.termSymbol.isStable && tp.prefix.isStable || tp.info.isStable
      case _: SingletonType | NoPrefix => true
      case tp: RefinedOrRecType => tp.parent.isStable
      case tp: ExprType => tp.resultType.isStable
      case _ => false
    }

    /** Is this type a (possibly refined or applied or aliased) type reference
     *  to the given type symbol?
     *  @sym  The symbol to compare to. It must be a class symbol or abstract type.
     *        It makes no sense for it to be an alias type because isRef would always
     *        return false in that case.
     */
    def isRef(sym: Symbol)(implicit ctx: Context): Boolean = stripAnnots.stripTypeVar match {
      case this1: TypeRef =>
        this1.info match { // see comment in Namer#typeDefSig
          case TypeAlias(tp) => tp.isRef(sym)
          case _ =>  this1.symbol eq sym
        }
      case this1: RefinedOrRecType => this1.parent.isRef(sym)
      case this1: HKApply => this1.superType.isRef(sym)
      case _ => false
    }

    /** Is this type a (neither aliased nor applied) reference to class `sym`? */
    def isDirectRef(sym: Symbol)(implicit ctx: Context): Boolean = stripTypeVar match {
      case this1: TypeRef =>
        this1.name == sym.name && // avoid forcing info if names differ
        (this1.symbol eq sym)
      case _ =>
        false
    }

    /** Does this type refer exactly to class symbol `sym`, instead of to a subclass of `sym`?
     *  Implemented like `isRef`, but follows more types: all type proxies as well as and- and or-types
     */
    private[Types] def isTightPrefix(sym: Symbol)(implicit ctx: Context): Boolean = stripTypeVar match {
      case tp: NamedType => tp.info.isTightPrefix(sym)
      case tp: ClassInfo => tp.cls eq sym
      case tp: Types.ThisType => tp.cls eq sym
      case tp: TypeProxy => tp.underlying.isTightPrefix(sym)
      case tp: AndType => tp.tp1.isTightPrefix(sym) && tp.tp2.isTightPrefix(sym)
      case tp: OrType => tp.tp1.isTightPrefix(sym) || tp.tp2.isTightPrefix(sym)
      case _ => false
    }

    /** Is this type an instance of a non-bottom subclass of the given class `cls`? */
    final def derivesFrom(cls: Symbol)(implicit ctx: Context): Boolean = {
      def loop(tp: Type): Boolean = tp match {
        case tp: TypeRef =>
          val sym = tp.symbol
          if (sym.isClass) sym.derivesFrom(cls) else loop(tp.superType): @tailrec
        case tp: TypeProxy =>
          loop(tp.underlying): @tailrec
        case tp: AndType =>
          loop(tp.tp1) || loop(tp.tp2): @tailrec
        case tp: OrType =>
          loop(tp.tp1) && loop(tp.tp2): @tailrec
        case tp: JavaArrayType =>
          cls == defn.ObjectClass
        case _ =>
          false
      }
      cls == defn.AnyClass || loop(this)
    }

    /** Is this type guaranteed not to have `null` as a value?
     *  For the moment this is only true for modules, but it could
     *  be refined later.
     */
    final def isNotNull(implicit ctx: Context): Boolean =
      classSymbol is ModuleClass

    /** Is this type produced as a repair for an error? */
    final def isError(implicit ctx: Context): Boolean = stripTypeVar match {
      case _: ErrorType => true
      case tp => (tp.typeSymbol is Erroneous) || (tp.termSymbol is Erroneous)
    }

    /** Is some part of this type produced as a repair for an error? */
    final def isErroneous(implicit ctx: Context): Boolean = existsPart(_.isError, forceLazy = false)

    /** Does the type carry an annotation that is an instance of `cls`? */
    @tailrec final def hasAnnotation(cls: ClassSymbol)(implicit ctx: Context): Boolean = stripTypeVar match {
      case AnnotatedType(tp, annot) => (annot matches cls) || (tp hasAnnotation cls)
      case _ => false
    }

    /** Does this type occur as a part of type `that`? */
    final def occursIn(that: Type)(implicit ctx: Context): Boolean =
      that existsPart (this == _)

    /** Is this a type of a repeated parameter? */
    def isRepeatedParam(implicit ctx: Context): Boolean =
      typeSymbol eq defn.RepeatedParamClass

    /** Does this type carry an UnsafeNonvariant annotation? */
    final def isUnsafeNonvariant(implicit ctx: Context): Boolean = this match {
      case AnnotatedType(_, annot) => annot.symbol == defn.UnsafeNonvariantAnnot
      case _ => false
    }

    /** Does this type have an UnsafeNonvariant annotation on one of its parts? */
    final def hasUnsafeNonvariant(implicit ctx: Context): Boolean =
      new HasUnsafeNonAccumulator().apply(false, this)

    /** Is this the type of a method that has a repeated parameter type as
     *  last parameter type?
     */
    def isVarArgsMethod(implicit ctx: Context): Boolean = stripPoly match {
      case mt: MethodType => mt.paramInfos.nonEmpty && mt.paramInfos.last.isRepeatedParam
      case _ => false
    }

    /** Is this the type of a method with a leading empty parameter list?
     */
    def isNullaryMethod(implicit ctx: Context): Boolean = stripPoly match {
      case MethodType(Nil) => true
      case _ => false
    }

    /** Is this an alias TypeBounds? */
    def isAlias: Boolean = this.isInstanceOf[TypeAlias]

// ----- Higher-order combinators -----------------------------------

    /** Returns true if there is a part of this type that satisfies predicate `p`.
     */
    final def existsPart(p: Type => Boolean, forceLazy: Boolean = true)(implicit ctx: Context): Boolean =
      new ExistsAccumulator(p, forceLazy).apply(false, this)

    /** Returns true if all parts of this type satisfy predicate `p`.
     */
    final def forallParts(p: Type => Boolean)(implicit ctx: Context): Boolean =
      !existsPart(!p(_))

    /** Performs operation on all parts of this type */
    final def foreachPart(p: Type => Unit, stopAtStatic: Boolean = false)(implicit ctx: Context): Unit =
      new ForeachAccumulator(p, stopAtStatic).apply((), this)

    /** The parts of this type which are type or term refs */
    final def namedParts(implicit ctx: Context): collection.Set[NamedType] =
      namedPartsWith(alwaysTrue)

    /** The parts of this type which are type or term refs and which
     *  satisfy predicate `p`.
     *
     *  @param p                   The predicate to satisfy
     *  @param excludeLowerBounds  If set to true, the lower bounds of abstract
     *                             types will be ignored.
     */
    def namedPartsWith(p: NamedType => Boolean, excludeLowerBounds: Boolean = false)
      (implicit ctx: Context): collection.Set[NamedType] =
      new NamedPartsAccumulator(p, excludeLowerBounds).apply(mutable.LinkedHashSet(), this)

    /** Map function `f` over elements of an AndType, rebuilding with function `g` */
    def mapReduceAnd[T](f: Type => T)(g: (T, T) => T)(implicit ctx: Context): T = stripTypeVar match {
      case AndType(tp1, tp2) => g(tp1.mapReduceAnd(f)(g), tp2.mapReduceAnd(f)(g))
      case _ => f(this)
    }

    /** Map function `f` over elements of an OrType, rebuilding with function `g` */
    final def mapReduceOr[T](f: Type => T)(g: (T, T) => T)(implicit ctx: Context): T = stripTypeVar match {
      case OrType(tp1, tp2) => g(tp1.mapReduceOr(f)(g), tp2.mapReduceOr(f)(g))
      case _ => f(this)
    }

// ----- Associated symbols ----------------------------------------------

    /** The type symbol associated with the type */
    @tailrec final def typeSymbol(implicit ctx: Context): Symbol = this match {
      case tp: TypeRef => tp.symbol
      case tp: ClassInfo => tp.cls
//    case ThisType(cls) => cls // needed?
      case tp: SingletonType => NoSymbol
      case tp: TypeProxy => tp.underlying.typeSymbol
      case _ => NoSymbol
    }

    /** The least class or trait of which this type is a subtype or parameterized
     *  instance, or NoSymbol if none exists (either because this type is not a
     *  value type, or because superclasses are ambiguous).
     */
    final def classSymbol(implicit ctx: Context): Symbol = this match {
      case ConstantType(constant) =>
        constant.tpe.classSymbol: @tailrec
      case tp: TypeRef =>
        val sym = tp.symbol
        if (sym.isClass) sym else tp.superType.classSymbol: @tailrec
      case tp: ClassInfo =>
        tp.cls
      case tp: SingletonType =>
        NoSymbol
      case tp: TypeProxy =>
        tp.underlying.classSymbol: @tailrec
      case AndType(l, r) =>
        val lsym = l.classSymbol
        val rsym = r.classSymbol
        if (lsym isSubClass rsym) lsym
        else if (rsym isSubClass lsym) rsym
        else NoSymbol
      case OrType(l, r) => // TODO does not conform to spec
        val lsym = l.classSymbol
        val rsym = r.classSymbol
        if (lsym isSubClass rsym) rsym
        else if (rsym isSubClass lsym) lsym
        else NoSymbol
      case _ =>
        NoSymbol
    }

    /** The least (wrt <:<) set of class symbols of which this type is a subtype
     */
    final def classSymbols(implicit ctx: Context): List[ClassSymbol] = this match {
      case tp: ClassInfo =>
        tp.cls :: Nil
      case tp: TypeRef =>
        val sym = tp.symbol
        if (sym.isClass) sym.asClass :: Nil else tp.superType.classSymbols: @tailrec
      case tp: TypeProxy =>
        tp.underlying.classSymbols: @tailrec
      case AndType(l, r) =>
        l.classSymbols union r.classSymbols
      case OrType(l, r) =>
        l.classSymbols intersect r.classSymbols // TODO does not conform to spec
      case _ =>
        Nil
    }

    /** The term symbol associated with the type */
    @tailrec final def termSymbol(implicit ctx: Context): Symbol = this match {
      case tp: TermRef => tp.symbol
      case tp: TypeProxy => tp.underlying.termSymbol
      case _ => NoSymbol
    }

    /** The base classes of this type as determined by ClassDenotation
     *  in linearization order, with the class itself as first element.
     *  For AndTypes/OrTypes, the union/intersection of the operands' baseclasses.
     *  Inherited by all type proxies. `Nil` for all other types.
     */
    final def baseClasses(implicit ctx: Context): List[ClassSymbol] = track("baseClasses") {
      this match {
        case tp: TypeProxy =>
          tp.underlying.baseClasses
        case tp: ClassInfo =>
          tp.cls.baseClasses
        case AndType(tp1, tp2) =>
          tp1.baseClasses union tp2.baseClasses
        case OrType(tp1, tp2) =>
          tp1.baseClasses intersect tp2.baseClasses
        case _ => Nil
      }
    }

// ----- Member access -------------------------------------------------

    /** The scope of all declarations of this type.
     *  Defined by ClassInfo, inherited by type proxies.
     *  Empty scope for all other types.
     */
    @tailrec final def decls(implicit ctx: Context): Scope = this match {
      case tp: ClassInfo =>
        tp.decls
      case tp: TypeProxy =>
        tp.underlying.decls: @tailrec
      case _ =>
        EmptyScope
    }

    /** A denotation containing the declaration(s) in this type with the given name.
     *  The result is either a SymDenotation or a MultiDenotation of SymDenotations.
     *  The info(s) are the original symbol infos, no translation takes place.
     */
    final def decl(name: Name)(implicit ctx: Context): Denotation = track("decl") {
      findDecl(name, EmptyFlags)
    }

    /** A denotation containing the non-private declaration(s) in this type with the given name */
    final def nonPrivateDecl(name: Name)(implicit ctx: Context): Denotation = track("nonPrivateDecl") {
      findDecl(name, Private)
    }

    /** A denotation containing the declaration(s) in this type with the given
     *  name, as seen from prefix type `pre`. Declarations that have a flag
     *  in `excluded` are omitted.
     */
    @tailrec final def findDecl(name: Name, excluded: FlagSet)(implicit ctx: Context): Denotation = this match {
      case tp: ClassInfo =>
        tp.decls.denotsNamed(name).filterExcluded(excluded).toDenot(NoPrefix)
      case tp: TypeProxy =>
        tp.underlying.findDecl(name, excluded)
      case err: ErrorType =>
        ctx.newErrorSymbol(classSymbol orElse defn.RootClass, name, err.msg)
      case _ =>
        NoDenotation
    }

    /** The member of this type with the given name  */
    final def member(name: Name)(implicit ctx: Context): Denotation = /*>|>*/ track("member") /*<|<*/ {
      memberExcluding(name, EmptyFlags)
    }

    /** The non-private member of this type with the given name. */
    final def nonPrivateMember(name: Name)(implicit ctx: Context): Denotation = track("nonPrivateMember") {
      memberExcluding(name, Flags.Private)
    }

    final def memberExcluding(name: Name, excluding: FlagSet)(implicit ctx: Context): Denotation = {
      // We need a valid prefix for `asSeenFrom`
      val pre = this match {
        case tp: ClassInfo =>
          tp.typeRef
        case _ =>
          widenIfUnstable
      }
      findMember(name, pre, excluding)
    }

    /** Find member of this type with given name and
     *  produce a denotation that contains the type of the member
     *  as seen from given prefix `pre`. Exclude all members that have
     *  flags in `excluded` from consideration.
     */
    final def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): Denotation = {
      @tailrec def go(tp: Type): Denotation = tp match {
        case tp: RefinedType =>
          if (name eq tp.refinedName) goRefined(tp) else go(tp.parent)
        case tp: ThisType =>
          goThis(tp)
        case tp: TypeRef =>
          tp.denot.findMember(name, pre, excluded)
        case tp: TermRef =>
          go (tp.underlying match {
            case mt: MethodType
            if mt.paramInfos.isEmpty && (tp.symbol is Stable) => mt.resultType
            case tp1 => tp1
          })
        case tp: TypeParamRef =>
          goParam(tp)
        case tp: RecType =>
          goRec(tp)
        case tp: HKApply =>
          goApply(tp)
        case tp: TypeProxy =>
          go(tp.underlying)
        case tp: ClassInfo =>
          tp.cls.findMember(name, pre, excluded)
        case AndType(l, r) =>
          goAnd(l, r)
        case tp: OrType =>
          // we need to keep the invariant that `pre <: tp`. Branch `union-types-narrow-prefix`
          // achieved that by narrowing `pre` to each alternative, but it led to merge errors in
          // lots of places. The present strategy is instead of widen `tp` using `join` to be a
          // supertype of `pre`.
          go(tp.join)
        case tp: JavaArrayType =>
          defn.ObjectType.findMember(name, pre, excluded)
        case err: ErrorType =>
          ctx.newErrorSymbol(pre.classSymbol orElse defn.RootClass, name, err.msg)
        case _ =>
          NoDenotation
      }
      def goRec(tp: RecType) =
        if (tp.parent == null) NoDenotation
        else {
          //println(s"find member $pre . $name in $tp")

          // We have to be careful because we might open the same (wrt eq) recursive type
          // twice during findMember which risks picking the wrong prefix in the `substRecThis(rt, pre)`
          // call below. To avoid this problem we do a defensive copy of the recursive
          // type first. But if we do this always we risk being inefficient and we ran into
          // stackoverflows when compiling pos/hk.scala under the refinement encoding
          // of hk-types. So we only do a copy if the type
          // is visited again in a recursive call to `findMember`, as tracked by `tp.opened`.
          // Furthermore, if this happens we mark the original recursive type with `openedTwice`
          // which means that we always defensively copy the type in the future. This second
          // measure is necessary because findMember calls might be cached, so do not
          // necessarily appear in nested order.
          // Without the defensive copy, Typer.scala fails to compile at the line
          //
          //      untpd.rename(lhsCore, setterName).withType(setterType), WildcardType)
          //
          // because the subtype check
          //
          //      ThisTree[Untyped]#ThisTree[Typed] <: Tree[Typed]
          //
          // fails (in fact it thinks the underlying type of the LHS is `Tree[Untyped]`.)
          //
          // Without the `openedTwice` trick, Typer.scala fails to Ycheck
          // at phase resolveSuper.
          val rt =
            if (tp.opened) { // defensive copy
              tp.openedTwice = true
              RecType(rt => tp.parent.substRecThis(tp, RecThis(rt)))
            } else tp
          rt.opened = true
          try go(rt.parent).mapInfo(_.substRecThis(rt, pre))
          finally {
            if (!rt.openedTwice) rt.opened = false
          }
        }

      def goRefined(tp: RefinedType) = {
        val pdenot = go(tp.parent)
        val rinfo = tp.refinedInfo
        if (name.isTypeName) { // simplified case that runs more efficiently
          val jointInfo =
            if (rinfo.isAlias) rinfo
            else if (pdenot.info.isAlias) pdenot.info
            else if (ctx.pendingMemberSearches.contains(name)) pdenot.info safe_& rinfo
            else
              try pdenot.info & rinfo
              catch {
                case ex: CyclicReference =>
                  // happens for tests/pos/sets.scala. findMember is called from baseTypeRef.
                  // The & causes a subtype check which calls baseTypeRef again with the same
                  // superclass. In the observed case, the superclass was Any, and
                  // the special shortcut for Any in derivesFrom was as yet absent. To reproduce,
                  // remove the special treatment of Any in derivesFrom and compile
                  // sets.scala.
                  pdenot.info safe_& rinfo
              }
          pdenot.asSingleDenotation.derivedSingleDenotation(pdenot.symbol, jointInfo)
        } else {
          pdenot & (
            new JointRefDenotation(NoSymbol, rinfo, Period.allInRun(ctx.runId)),
            pre,
            safeIntersection = ctx.pendingMemberSearches.contains(name))
        }
      }

      def goApply(tp: HKApply) = tp.tycon match {
        case tl: HKTypeLambda =>
          go(tl.resType).mapInfo(info =>
            tl.derivedLambdaAbstraction(tl.paramNames, tl.paramInfos, info).appliedTo(tp.args))
        case _ =>
          go(tp.superType)
      }

      def goThis(tp: ThisType) = {
        val d = go(tp.underlying)
        if (d.exists) d
        else
          // There is a special case to handle:
          //   trait Super { this: Sub => private class Inner {} println(this.Inner) }
          //   class Sub extends Super
          // When resolving Super.this.Inner, the normal logic goes to the self type and
          // looks for Inner from there. But this fails because Inner is private.
          // We fix the problem by having the following fallback case, which links up the
          // member in Super instead of Sub.
          // As an example of this in the wild, see
          // loadClassWithPrivateInnerAndSubSelf in ShowClassTests
          go(tp.cls.typeRef) orElse d
      }
      def goParam(tp: TypeParamRef) = {
        val next = tp.underlying
        ctx.typerState.constraint.entry(tp) match {
          case bounds: TypeBounds if bounds ne next =>
            ctx.typerState.ephemeral = true
            go(bounds.hi)
          case _ =>
            go(next)
        }
      }
      def goAnd(l: Type, r: Type) = {
        go(l) & (go(r), pre, safeIntersection = ctx.pendingMemberSearches.contains(name))
      }

      { val recCount = ctx.findMemberCount + 1
        ctx.findMemberCount = recCount
        if (recCount >= Config.LogPendingFindMemberThreshold) {
          ctx.pendingMemberSearches = name :: ctx.pendingMemberSearches
          if (ctx.property(TypeOps.findMemberLimit).isDefined &&
              ctx.findMemberCount > Config.PendingFindMemberLimit)
            return NoDenotation
        }
      }

      //assert(ctx.findMemberCount < 20)
      try go(this)
      catch {
        case ex: Throwable =>
          core.println(i"findMember exception for $this member $name, pre = $pre")
          throw ex // DEBUG
      }
      finally {
        val recCount = ctx.findMemberCount
        if (recCount >= Config.LogPendingFindMemberThreshold)
          ctx.pendingMemberSearches = ctx.pendingMemberSearches.tail
        ctx.findMemberCount = recCount - 1
      }
    }

    /** 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`.
     *  @note: OK to use a Set[Name] here because Name hashcodes are replayable,
     *         hence the Set will always give the same names in the same order.
     */
    final def memberNames(keepOnly: NameFilter, pre: Type = this)(implicit ctx: Context): Set[Name] = this match {
      case tp: ClassInfo =>
        tp.cls.memberNames(keepOnly) filter (keepOnly(pre, _))
      case tp: RefinedType =>
        val ns = tp.parent.memberNames(keepOnly, pre)
        if (keepOnly(pre, tp.refinedName)) ns + tp.refinedName else ns
      case tp: TypeProxy =>
        tp.underlying.memberNames(keepOnly, pre): @tailrec
      case tp: AndType =>
        tp.tp1.memberNames(keepOnly, pre) | tp.tp2.memberNames(keepOnly, pre)
      case tp: OrType =>
        tp.tp1.memberNames(keepOnly, pre) & tp.tp2.memberNames(keepOnly, pre)
      case _ =>
        Set()
    }

    def memberDenots(keepOnly: NameFilter, f: (Name, mutable.Buffer[SingleDenotation]) => Unit)(implicit ctx: Context): Seq[SingleDenotation] = {
      val buf = mutable.ArrayBuffer[SingleDenotation]()
      for (name <- memberNames(keepOnly)) f(name, buf)
      buf
    }

    /** The set of abstract term members of this type. */
    final def abstractTermMembers(implicit ctx: Context): Seq[SingleDenotation] = track("abstractTermMembers") {
      memberDenots(abstractTermNameFilter,
          (name, buf) => buf ++= nonPrivateMember(name).altsWith(_ is Deferred))
    }

    /** The set of abstract type members of this type. */
    final def abstractTypeMembers(implicit ctx: Context): Seq[SingleDenotation] = track("abstractTypeMembers") {
      memberDenots(abstractTypeNameFilter,
          (name, buf) => buf += nonPrivateMember(name).asSingleDenotation)
    }

    /** The set of abstract type members of this type. */
    final def nonClassTypeMembers(implicit ctx: Context): Seq[SingleDenotation] = track("nonClassTypeMembers") {
      memberDenots(nonClassTypeNameFilter,
          (name, buf) => buf += member(name).asSingleDenotation)
    }

    /** The set of type members of this type */
    final def typeMembers(implicit ctx: Context): Seq[SingleDenotation] = track("typeMembers") {
      memberDenots(typeNameFilter,
          (name, buf) => buf += member(name).asSingleDenotation)
    }

    /** The set of implicit members of this type */
    final def implicitMembers(implicit ctx: Context): List[TermRef] = track("implicitMembers") {
      memberDenots(implicitFilter,
          (name, buf) => buf ++= member(name).altsWith(_ is Implicit))
        .toList.map(d => TermRef.withSig(this, d.symbol.asTerm))
    }

    /** The set of member classes of this type */
    final def memberClasses(implicit ctx: Context): Seq[SingleDenotation] = track("implicitMembers") {
      memberDenots(typeNameFilter,
        (name, buf) => buf ++= member(name).altsWith(x => x.isClass))
    }

    final def fields(implicit ctx: Context): Seq[SingleDenotation] = track("fields") {
      memberDenots(fieldFilter,
        (name, buf) => buf ++= member(name).altsWith(x => !x.is(Method)))
    }

    /** The set of members of this type having at least one of `requiredFlags` but none of `excludedFlags` set */
    final def membersBasedOnFlags(requiredFlags: FlagSet, excludedFlags: FlagSet)(implicit ctx: Context): Seq[SingleDenotation] = track("implicitMembers") {
      memberDenots(takeAllFilter,
        (name, buf) => buf ++= memberExcluding(name, excludedFlags).altsWith(x => x.is(requiredFlags)))
    }

    /** The info of `sym`, seen as a member of this type. */
    final def memberInfo(sym: Symbol)(implicit ctx: Context): Type =
      sym.info.asSeenFrom(this, sym.owner)

    /** This type seen as if it were the type of a member of prefix type `pre`
     *  declared in class `cls`.
     */
    final def asSeenFrom(pre: Type, cls: Symbol)(implicit ctx: Context): Type = track("asSeenFrom") {
      if (!cls.membersNeedAsSeenFrom(pre)) this
      else ctx.asSeenFrom(this, pre, cls)
    }

// ----- Subtype-related --------------------------------------------

    /** Is this type a subtype of that type? */
    final def <:<(that: Type)(implicit ctx: Context): Boolean = track("<:<") {
      ctx.typeComparer.topLevelSubType(this, that)
    }

    /** Is this type a subtype of that type? */
    final def frozen_<:<(that: Type)(implicit ctx: Context): Boolean = track("frozen_<:<") {
      ctx.typeComparer.isSubTypeWhenFrozen(this, that)
    }

    /** Is this type the same as that type?
     *  This is the case iff `this <:< that` and `that <:< this`.
     */
    final def =:=(that: Type)(implicit ctx: Context): Boolean = track("=:=") {
      ctx.typeComparer.isSameType(this, that)
    }

    /** Is this type a primitive value type which can be widened to the primitive value type `that`? */
    def isValueSubType(that: Type)(implicit ctx: Context) = widen match {
      case self: TypeRef if self.symbol.isPrimitiveValueClass =>
        that.widenExpr match {
          case that: TypeRef if that.symbol.isPrimitiveValueClass =>
            defn.isValueSubClass(self.symbol, that.symbol)
          case _ =>
            false
        }
      case _ =>
        false
    }

    def relaxed_<:<(that: Type)(implicit ctx: Context) =
      (this <:< that) || (this isValueSubType that)

    /** Is this type a legal type for a member that overrides another
     *  member of type `that`? This is the same as `<:<`, except that
     *  the types `()T`, `=> T` and `T` are seen as overriding
     *  each other.
     */
    final def overrides(that: Type)(implicit ctx: Context) = {
      def result(tp: Type): Type = tp match {
        case ExprType(_) | MethodType(Nil) => tp.resultType
        case _ => tp
      }
      (this frozen_<:< that) || {
        val rthat = result(that)
        val rthis = result(this)
        (rthat.ne(that) || rthis.ne(this)) && (rthis frozen_<:< rthat)
      }
    }

    /** Is this type close enough to that type so that members
     *  with the two types would override each other?
     *  This means:
     *    - Either both types are polytypes with the same number of
     *      type parameters and their result types match after renaming
     *      corresponding type parameters
     *    - Or both types are method types with =:=-equivalent(*) parameter types
     *      and matching result types after renaming corresponding parameter types
     *      if the method types are dependent.
     *    - Or both types are =:=-equivalent
     *    - Or phase.erasedTypes is false, and neither type takes
     *      term or type parameters.
     *
     *  (*) when matching with a Java method, we also regard Any and Object as equivalent
     *      parameter types.
     */
    def matches(that: Type)(implicit ctx: Context): Boolean = track("matches") {
      ctx.typeComparer.matchesType(this, that, relaxed = !ctx.phase.erasedTypes)
    }

    /** This is the same as `matches` except that it also matches => T with T and
     *  vice versa.
     */
    def matchesLoosely(that: Type)(implicit ctx: Context): Boolean =
      (this matches that) || {
        val thisResult = this.widenExpr
        val thatResult = that.widenExpr
        (this eq thisResult) != (that eq thatResult) && (thisResult matchesLoosely thatResult)
      }

    /** The basetype TypeRef of this type with given class symbol,
     *  but without including any type arguments
     */
    final def baseTypeRef(base: Symbol)(implicit ctx: Context): Type = /*ctx.traceIndented(s"$this baseTypeRef $base")*/ /*>|>*/ track("baseTypeRef") /*<|<*/ {
      base.denot match {
        case classd: ClassDenotation => classd.baseTypeRefOf(this)
        case _ => NoType
      }
    }

    def & (that: Type)(implicit ctx: Context): Type = track("&") {
      ctx.typeComparer.glb(this, that)
    }

    /** Safer version of `&`.
     *
     *  This version does not simplify the upper bound of the intersection of
     *  two TypeBounds. The simplification done by `&` requires subtyping checks
     *  which may end up calling `&` again, in most cases this should be safe
     *  but because of F-bounded types, this can result in an infinite loop
     *  (which will be masked unless `-Yno-deep-subtypes` is enabled).
     */
    def safe_& (that: Type)(implicit ctx: Context): Type = (this, that) match {
      case (TypeBounds(lo1, hi1), TypeBounds(lo2, hi2)) => TypeBounds(lo1 | lo2, AndType(hi1, hi2))
      case _ => this & that
    }

    def | (that: Type)(implicit ctx: Context): Type = track("|") {
      ctx.typeComparer.lub(this, that)
    }

// ----- Unwrapping types -----------------------------------------------

    /** Map a TypeVar to either its instance if it is instantiated, or its origin,
     *  if not, until the result is no longer a TypeVar. Identity on all other types.
     */
    def stripTypeVar(implicit ctx: Context): Type = this

    /** Remove all AnnotatedTypes wrapping this type.
      */
    def stripAnnots(implicit ctx: Context): Type = this

    /** Strip PolyType prefix */
    def stripPoly(implicit ctx: Context): Type = this match {
      case tp: PolyType => tp.resType.stripPoly
      case _ => this
    }

    /** Widen from singleton type to its underlying non-singleton
     *  base type by applying one or more `underlying` dereferences,
     *  Also go from => T to T.
     *  Identity for all other types. Example:
     *
     *  class Outer { class C ; val x: C }
     *  def o: Outer
     *  <o.x.type>.widen = o.C
     */
    @tailrec final def widen(implicit ctx: Context): Type = widenSingleton match {
      case tp: ExprType => tp.resultType.widen
      case tp => tp
    }

    /** Widen from singleton type to its underlying non-singleton
     *  base type by applying one or more `underlying` dereferences.
     */
    @tailrec final def widenSingleton(implicit ctx: Context): Type = stripTypeVar match {
      case tp: SingletonType if !tp.isOverloaded => tp.underlying.widenSingleton
      case _ => this
    }

    /** Widen from TermRef to its underlying non-termref
     *  base type, while also skipping Expr types.
     */
    @tailrec final def widenTermRefExpr(implicit ctx: Context): Type = stripTypeVar match {
      case tp: TermRef if !tp.isOverloaded => tp.underlying.widenExpr.widenTermRefExpr
      case _ => this
    }

    /** Widen from ExprType type to its result type.
     *  (Note: no stripTypeVar needed because TypeVar's can't refer to ExprTypes.)
     */
    final def widenExpr: Type = this match {
      case tp: ExprType => tp.resType
      case _ => this
    }

    /** Widen type if it is unstable (i.e. an ExprType, or TermRef to unstable symbol */
    @tailrec final def widenIfUnstable(implicit ctx: Context): Type = stripTypeVar match {
      case tp: ExprType => tp.resultType.widenIfUnstable
      case tp: TermRef if !tp.symbol.isStable => tp.underlying.widenIfUnstable
      case _ => this
    }

    /** If this is a skolem, its underlying type, otherwise the type itself */
    final def widenSkolem(implicit ctx: Context): Type = this match {
      case tp: SkolemType => tp.underlying
      case _ => this
    }

    /** Eliminate anonymous classes */
    final def deAnonymize(implicit ctx: Context): Type = this match {
      case tp:TypeRef if tp.symbol.isAnonymousClass =>
        tp.symbol.asClass.typeRef.asSeenFrom(tp.prefix, tp.symbol.owner)
      case tp => tp
    }

    private def dealias(keepAnnots: Boolean)(implicit ctx: Context): Type = this match {
      case tp: TypeRef =>
        if (tp.symbol.isClass) tp
        else tp.info match {
          case TypeAlias(tp) => tp.dealias(keepAnnots): @tailrec
          case _ => tp
        }
      case tp: TypeVar =>
        val tp1 = tp.instanceOpt
        if (tp1.exists) tp1.dealias(keepAnnots): @tailrec else tp
      case tp: AnnotatedType =>
        val tp1 = tp.tpe.dealias(keepAnnots)
        if (keepAnnots) tp.derivedAnnotatedType(tp1, tp.annot) else tp1
      case tp: LazyRef =>
        tp.ref.dealias(keepAnnots): @tailrec
      case app @ HKApply(tycon, args) =>
        val tycon1 = tycon.dealias(keepAnnots)
        if (tycon1 ne tycon) app.superType.dealias(keepAnnots): @tailrec
        else this
      case _ => this
    }

    /** Follow aliases and dereferences LazyRefs and instantiated TypeVars until type
     *  is no longer alias type, LazyRef, or instantiated type variable.
     *  Goes through annotated types and rewraps annotations on the result.
     */
    final def dealiasKeepAnnots(implicit ctx: Context): Type =
      dealias(keepAnnots = true)

    /** Follow aliases and dereferences LazyRefs, annotated types and instantiated
     *  TypeVars until type is no longer alias type, annotated type, LazyRef,
     *  or instantiated type variable.
     */
    final def dealias(implicit ctx: Context): Type =
      dealias(keepAnnots = false)

    /** Perform successive widenings and dealiasings until none can be applied anymore */
    @tailrec final def widenDealias(implicit ctx: Context): Type = {
      val res = this.widen.dealias
      if (res eq this) res else res.widenDealias
    }

    /** Widen from constant type to its underlying non-constant
     *  base type.
     */
    final def deconst(implicit ctx: Context): Type = stripTypeVar match {
      case tp: ConstantType => tp.value.tpe
      case _ => this
    }

    /** If this is a (possibly aliased, annotated, and/or parameterized) reference to
     *  a class, the class type ref, otherwise NoType.
     *  @param  refinementOK   If `true` we also skip non-parameter refinements.
     */
    def underlyingClassRef(refinementOK: Boolean)(implicit ctx: Context): Type = dealias match {
      case tp: TypeRef =>
        if (tp.symbol.isClass) tp
        else if (tp.symbol.isAliasType) tp.underlying.underlyingClassRef(refinementOK)
        else NoType
      case tp: AnnotatedType =>
        tp.underlying.underlyingClassRef(refinementOK)
      case tp: RefinedType =>
        def isParamName = tp.classSymbol.typeParams.exists(_.name == tp.refinedName)
        if (refinementOK || isParamName) tp.underlying.underlyingClassRef(refinementOK)
        else NoType
      case tp: RecType =>
        tp.underlying.underlyingClassRef(refinementOK)
      case _ =>
        NoType
    }

    /** The iterator of underlying types as long as type is a TypeProxy.
     *  Useful for diagnostics
     */
    def underlyingIterator(implicit ctx: Context): Iterator[Type] = new Iterator[Type] {
      var current = Type.this
      var hasNext = true
      def next = {
        val res = current
        hasNext = current.isInstanceOf[TypeProxy]
        if (hasNext) current = current.asInstanceOf[TypeProxy].underlying
        res
      }
    }

    /** A prefix-less refined this or a termRef to a new skolem symbol
     *  that has the given type as info.
     */
    def narrow(implicit ctx: Context): TermRef =
      TermRef(NoPrefix, ctx.newSkolem(this))

    /** Useful for diagnostics: The underlying type if this type is a type proxy,
     *  otherwise NoType
     */
    def underlyingIfProxy(implicit ctx: Context) = this match {
      case this1: TypeProxy => this1.underlying
      case _ => NoType
    }

  	/** If this is a FunProto or PolyProto, WildcardType, otherwise this. */
    def notApplied: Type = this

    // ----- Normalizing typerefs over refined types ----------------------------

    /** If this normalizes* to a refinement type that has a refinement for `name` (which might be followed
     *  by other refinements), and the refined info is a type alias, return the alias,
     *  otherwise return NoType. Used to reduce types of the form
     *
     *    P { ... type T = / += / -= U ... } # T
     *
     *  to just U. Does not perform the reduction if the resulting type would contain
     *  a reference to the "this" of the current refined type, except in the following situation
     *
     *  (1) The "this" reference can be avoided by following an alias. Example:
     *
     *      P { type T = String, type R = P{...}.T } # R  -->  String
     *
     *  (*) normalizes means: follow instantiated typevars and aliases.
     */
    def lookupRefined(name: Name)(implicit ctx: Context): Type = {
      @tailrec def loop(pre: Type): Type = pre.stripTypeVar match {
        case pre: RefinedType =>
          pre.refinedInfo match {
            case TypeAlias(alias) =>
              if (pre.refinedName ne name) loop(pre.parent) else alias
            case _ => loop(pre.parent)
          }
        case pre: RecType =>
          val candidate = pre.parent.lookupRefined(name)
          if (candidate.exists && !pre.isReferredToBy(candidate)) {
            //println(s"lookupRefined ${this.toString} . $name, pre: $pre ---> $candidate / ${candidate.toString}")
            candidate
          }
          else NoType
        case SkolemType(tp) =>
          loop(tp)
        case pre: WildcardType =>
          WildcardType
        case pre: TypeRef =>
          pre.info match {
            case TypeAlias(alias) => loop(alias)
            case _ => NoType
          }
        case _ =>
          NoType
      }

      loop(this)
    }

    /** The type <this . name> , reduced if possible */
    def select(name: Name)(implicit ctx: Context): Type = name match {
      case name: TermName => TermRef.all(this, name)
      case name: TypeName => TypeRef(this, name).reduceProjection
    }

    /** The type <this . name> , reduced if possible, with given denotation if unreduced */
    def select(name: Name, denot: Denotation)(implicit ctx: Context): Type = name match {
      case name: TermName => TermRef(this, name, denot)
      case name: TypeName => TypeRef(this, name, denot).reduceProjection
    }

    /** The type <this . name> with given symbol, reduced if possible */
    def select(sym: Symbol)(implicit ctx: Context): Type =
      if (sym.isTerm) TermRef(this, sym.asTerm)
      else TypeRef(this, sym.asType).reduceProjection

// ----- Access to parts --------------------------------------------

    /** 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.
     */
    @tailrec final def normalizedPrefix(implicit ctx: Context): Type = this match {
      case tp: NamedType =>
        if (tp.symbol.info.isAlias) tp.info.normalizedPrefix else tp.prefix
      case tp: ClassInfo =>
        tp.prefix
      case tp: TypeProxy =>
        tp.underlying.normalizedPrefix
      case _ =>
        NoType
    }

    /** For a ClassInfo type, its parents,
     *  Inherited by all type proxies. Empty for all other types.
     *  Overwritten in ClassInfo, where parents is cached.
     */
    def parents(implicit ctx: Context): List[TypeRef] = this match {
      case tp: TypeProxy => tp.underlying.parents
      case _ => List()
    }

    /** The full parent types, including all type arguments */
    def parentsWithArgs(implicit ctx: Context): List[Type] = this match {
      case tp: TypeProxy => tp.superType.parentsWithArgs
      case _ => List()
    }

    /** The first parent of this type, AnyRef if list of parents is empty */
    def firstParent(implicit ctx: Context): TypeRef = parents match {
      case p :: _ => p
      case _ => defn.AnyType
    }

    /** the self type of the underlying classtype */
    def givenSelfType(implicit ctx: Context): Type = this match {
      case tp: RefinedType => tp.wrapIfMember(tp.parent.givenSelfType)
      case tp: ThisType => tp.tref.givenSelfType
      case tp: TypeProxy => tp.superType.givenSelfType
      case _ => NoType
    }

    /** The parameter types of a PolyType or MethodType, Empty list for others */
    final def paramInfoss(implicit ctx: Context): List[List[Type]] = stripPoly match {
      case mt: MethodType => mt.paramInfos :: mt.resultType.paramInfoss
      case _ => Nil
    }

    /** The parameter names of a PolyType or MethodType, Empty list for others */
    final def paramNamess(implicit ctx: Context): List[List[TermName]] = stripPoly match {
      case mt: MethodType => mt.paramNames :: mt.resultType.paramNamess
      case _ => Nil
    }


    /** The parameter types in the first parameter section of a generic type or MethodType, Empty list for others */
    final def firstParamTypes(implicit ctx: Context): List[Type] = stripPoly match {
      case mt: MethodType => mt.paramInfos
      case _ => Nil
    }

    /** Is this either not a method at all, or a parameterless method? */
    final def isParameterless(implicit ctx: Context): Boolean = stripPoly match {
      case mt: MethodType => false
      case _ => true
    }

    /** The resultType of a LambdaType, or ExprType, the type itself for others */
    def resultType(implicit ctx: Context): Type = this

    /** The final result type of a PolyType, MethodType, or ExprType, after skipping
     *  all parameter sections, the type itself for all others.
     */
    def finalResultType(implicit ctx: Context): Type = resultType.stripPoly match {
      case mt: MethodType => mt.resultType.finalResultType
      case _ => resultType
    }

    /** This type seen as a TypeBounds */
    final def bounds(implicit ctx: Context): TypeBounds = this match {
      case tp: TypeBounds => tp
      case ci: ClassInfo => TypeAlias(ci.typeRef)
      case wc: WildcardType =>
        wc.optBounds match {
          case bounds: TypeBounds => bounds
          case NoType => TypeBounds.empty
        }
      case _ => TypeAlias(this)
    }

    /** The type parameter with given `name`. This tries first `decls`
     *  in order not to provoke a cycle by forcing the info. If that yields
     *  no symbol it tries `member` as an alternative.
     */
    def typeParamNamed(name: TypeName)(implicit ctx: Context): Symbol =
      classSymbol.unforcedDecls.lookup(name) orElse member(name).symbol

    /** If this is a prototype with some ignored component, reveal one more
     *  layer of it. Otherwise the type itself.
     */
    def deepenProto(implicit ctx: Context): Type = this

// ----- Substitutions -----------------------------------------------------

    /** Substitute all types that refer in their symbol attribute to
     *  one of the symbols in `from` by the corresponding types in `to`.
     */
    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) ctx.subst1(this, from.head, to.head, null)
        else {
          val from2 = from1.tail
          if (from2.isEmpty) ctx.subst2(this, from.head, to.head, from1.head, to.tail.head, null)
          else ctx.subst(this, from, to, null)
        }
      }

    /** Same as `subst` but follows aliases as a fallback. When faced with a reference
     *  to an alias type, where normal substitution does not yield a new type, the
     *  substitution is instead applied to the alias. If that yields a new type,
     *  this type is returned, otherwise the original type (not the alias) is returned.
     *  A use case for this method is if one wants to substitute the type parameters
     *  of a class and also wants to substitute any parameter accessors that alias
     *  the type parameters.
     */
    final def substDealias(from: List[Symbol], to: List[Type])(implicit ctx: Context): Type =
      ctx.substDealias(this, from, to, null)

    /** Substitute all types of the form `TypeParamRef(from, N)` by
     *  `TypeParamRef(to, N)`.
     */
    final def subst(from: BindingType, to: BindingType)(implicit ctx: Context): Type =
      ctx.subst(this, from, to, null)

    /** Substitute all occurrences of `This(cls)` by `tp` */
    final def substThis(cls: ClassSymbol, tp: Type)(implicit ctx: Context): Type =
      ctx.substThis(this, cls, tp, null)

    /** As substThis, but only is class is a static owner (i.e. a globally accessible object) */
    final def substThisUnlessStatic(cls: ClassSymbol, tp: Type)(implicit ctx: Context): Type =
      if (cls.isStaticOwner) this else ctx.substThis(this, cls, tp, null)

    /** Substitute all occurrences of `RecThis(binder)` by `tp` */
    final def substRecThis(binder: RecType, tp: Type)(implicit ctx: Context): Type =
      ctx.substRecThis(this, binder, tp, null)

    /** Substitute a bound type by some other type */
    final def substParam(from: ParamRef, to: Type)(implicit ctx: Context): Type =
      ctx.substParam(this, from, to, null)

    /** Substitute bound types by some other types */
    final def substParams(from: BindingType, to: List[Type])(implicit ctx: Context): Type =
      ctx.substParams(this, from, to, null)

    /** Substitute all occurrences of symbols in `from` by references to corresponding symbols in `to`
     */
    final def substSym(from: List[Symbol], to: List[Symbol])(implicit ctx: Context): Type =
      ctx.substSym(this, from, to, null)

// ----- misc -----------------------------------------------------------

    /** Turn type into a function type.
     *  @pre this is a non-dependent method type.
     *  @param dropLast  The number of trailing parameters that should be dropped
     *                   when forming the function type.
     */
    def toFunctionType(dropLast: Int = 0)(implicit ctx: Context): Type = this match {
      case mt: MethodType if !mt.isDependent || ctx.mode.is(Mode.AllowDependentFunctions) =>
        val formals1 = if (dropLast == 0) mt.paramInfos else mt.paramInfos dropRight dropLast
        defn.FunctionOf(
          formals1 mapConserve (_.underlyingIfRepeated(mt.isJava)), mt.resultType, mt.isImplicit && !ctx.erasedTypes)
    }

    /** The signature of this type. This is by default NotAMethod,
     *  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(implicit ctx: Context): Signature = Signature.NotAMethod

    /** Convert to text */
    def toText(printer: Printer): Text = printer.toText(this)

    /** Utility method to show the underlying type of a TypeProxy chain together
     *  with the proxy type itself.
     */
    def showWithUnderlying(n: Int = 1)(implicit ctx: Context): String = this match {
      case tp: TypeProxy if n > 0 => s"$show with underlying ${tp.underlying.showWithUnderlying(n - 1)}"
      case _ => show
    }

    /** A simplified version of this type which is equivalent wrt =:= to this type.
     *  This applies a typemap to the type which (as all typemaps) follows type
     *  variable instances and reduces typerefs over refined types. It also
     *  re-evaluates all occurrences of And/OrType with &/| because
     *  what was a union or intersection of type variables might be a simpler type
     *  after the type variables are instantiated. Finally, it
     *  maps poly params in the current constraint set back to their type vars.
     */
    def simplified(implicit ctx: Context) = ctx.simplify(this, null)

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

// ----- Type categories ----------------------------------------------

  /** A marker trait for cached types */
  trait CachedType 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

    /** The closest supertype of this type. This is the same as `underlying`,
     *  except that
     *    - instead of a TyperBounds type it returns its upper bound, and
     *    - for HKApplys it returns the upper bound of the constructor re-applied to the arguments.
     */
    def superType(implicit ctx: Context): Type = underlying match {
      case TypeBounds(_, hi) => hi
      case st => st
    }
  }

  // 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 {
    private[this] var myHash = HashUnknown
    final def hash = {
      if (myHash == HashUnknown) {
        myHash = computeHash
        assert(myHash != HashUnknown)
      }
      myHash
    }
    override final def hashCode =
      if (hash == NotCached) System.identityHashCode(this) else hash
    def computeHash: Int
  }

  /**  Instances of this class are cached and are proxies. */
  abstract class CachedProxyType extends TypeProxy with CachedType {
    protected[this] var myHash = HashUnknown
    final def hash = {
      if (myHash == HashUnknown) {
        myHash = computeHash
        assert(myHash != HashUnknown)
      }
      myHash
    }
    override final def hashCode =
      if (hash == NotCached) System.identityHashCode(this) else hash
    def computeHash: Int
  }

  /**  Instances of this class are uncached and are not proxies. */
  abstract class UncachedGroundType extends Type {
    final def hash = NotCached
    if (monitored) {
      record(s"uncachable")
      record(s"uncachable: $getClass")
    }
  }

  /**  Instances of this class are uncached and are proxies. */
  abstract class UncachedProxyType extends TypeProxy {
    final def hash = NotCached
    if (monitored) {
      record(s"uncachable")
      record(s"uncachable: $getClass")
    }
  }

  /** A marker trait for types that apply only to type symbols */
  trait TypeType extends Type

  /** A marker trait for types that apply only to term symbols or that
   *  represent higher-kinded types.
   */
  trait TermType extends Type

  /** A marker trait for types that can be types of values or prototypes of value types */
  trait ValueTypeOrProto extends TermType

  /** A marker trait for types that can be types of values or that are higher-kinded  */
  trait ValueType extends ValueTypeOrProto

  /** 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 with ValueType {
    def isOverloaded(implicit ctx: Context) = false
  }

  /** A marker trait for types that bind other types that refer to them.
   *  Instances are: LambdaType, RecType.
   */
  trait BindingType extends Type

  /** A trait for proto-types, used as expected types in typer */
  trait ProtoType extends Type {
    def isMatchedBy(tp: Type)(implicit ctx: Context): Boolean
    def fold[T](x: T, ta: TypeAccumulator[T])(implicit ctx: Context): T
    def map(tm: TypeMap)(implicit ctx: Context): ProtoType
  }

  /** Implementations of this trait cache the results of `narrow`. */
  trait NarrowCached extends Type {
    private var myNarrow: TermRef = null
    override def narrow(implicit ctx: Context): TermRef = {
      if (myNarrow eq null) myNarrow = super.narrow
      myNarrow
    }
  }

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

  /** A NamedType of the form Prefix # name */
  abstract class NamedType extends CachedProxyType with ValueType {

    val prefix: Type
    val name: Name

    type ThisType >: this.type <: NamedType

    assert(prefix.isValueType || (prefix eq NoPrefix), s"invalid prefix $prefix")

    private[this] var lastDenotation: Denotation = _
    private[this] var lastSymbol: Symbol = _
    private[this] var checkedPeriod = Nowhere

    // Invariants:
    // (1) checkedPeriod != Nowhere  =>  lastDenotation != null
    // (2) lastDenotation != null    =>  lastSymbol != null

    /** There is a denotation computed which is valid (somewhere in) the
     *  current run.
     */
    def denotationIsCurrent(implicit ctx: Context) =
      lastDenotation != null && lastDenotation.validFor.runId == ctx.runId

    /** The denotation is current, its symbol, otherwise NoDenotation.
     *
     *  Note: This operation does not force the denotation, and is therefore
     *  timing dependent. It should only be used if the outcome of the
     *  essential computation does not depend on the symbol being present or not.
     *  It's currently used to take an optimized path in substituters and
     *  type accumulators, as well as to be safe in diagnostic printing.
     *  Normally, it's better to use `symbol`, not `currentSymbol`.
     */
    def currentSymbol(implicit ctx: Context) =
      if (denotationIsCurrent) symbol else NoSymbol

    /** The denotation currently denoted by this type */
    final def denot(implicit ctx: Context): Denotation = {
      val now = ctx.period
      if (checkedPeriod == now) lastDenotation else denotAt(now)
    }

    /** A first fall back to do a somewhat more expensive calculation in case the first
     *  attempt in `denot` does not yield a denotation.
     */
    private def denotAt(now: Period)(implicit ctx: Context): Denotation = {
      val d = lastDenotation
      if (d != null && (d.validFor contains now)) {
        checkedPeriod = now
        d
      }
      else computeDenot
    }

    /** Hook for adding debug check code when denotations are assigned */
    final def checkDenot()(implicit ctx: Context) = {}

    /** A second fallback to recompute the denotation if necessary */
    private def computeDenot(implicit ctx: Context): Denotation = {
      val savedEphemeral = ctx.typerState.ephemeral
      ctx.typerState.ephemeral = false
      try {
        val d = lastDenotation match {
          case null =>
            val sym = lastSymbol
            if (sym == null) loadDenot else denotOfSym(sym)
          case d: SymDenotation =>
            if (this.isInstanceOf[WithFixedSym]) d.current
            else if (d.validFor.runId == ctx.runId || ctx.stillValid(d))
              if (d.exists && prefix.isTightPrefix(d.owner) || d.isConstructor) d.current
              else recomputeMember(d) // symbol could have been overridden, recompute membership
            else {
              val newd = loadDenot
              if (newd.exists) newd else d.staleSymbolError
            }
          case d =>
            if (d.validFor.runId != ctx.period.runId) loadDenot
            else d.current
        }
        if (ctx.typerState.ephemeral) record("ephemeral cache miss: loadDenot")
        else if (d.exists) {
          // Avoid storing NoDenotations in the cache - we will not be able to recover from
          // them. The situation might arise that a type has NoDenotation in some later
          // phase but a defined denotation earlier (e.g. a TypeRef to an abstract type
          // is undefined after erasure.) We need to be able to do time travel back and
          // forth also in these cases.

          // Don't use setDenot here; double binding checks can give spurious failures after erasure
          lastDenotation = d
          checkDenot()
          lastSymbol = d.symbol
          checkedPeriod = ctx.period
        }
        d
      }
      finally ctx.typerState.ephemeral |= savedEphemeral
    }

    /** A member of `prefix` (disambiguated by `d.signature`) or, if none was found, `d.current`. */
    private def recomputeMember(d: SymDenotation)(implicit ctx: Context): Denotation =
      asMemberOf(prefix, allowPrivate = d.is(Private)) match {
        case NoDenotation => d.current
        case newd: SingleDenotation => newd
        case newd =>
          newd.atSignature(d.signature) match {
            case newd1: SingleDenotation if newd1.exists => newd1
            case _ => d.current
          }
      }

    private def denotOfSym(sym: Symbol)(implicit ctx: Context): Denotation = {
      val d = sym.denot
      val owner = d.owner
      if (owner.isTerm) d else d.asSeenFrom(prefix)
    }

    private def checkSymAssign(sym: Symbol)(implicit ctx: Context) = {
      def selfTypeOf(sym: Symbol) = sym.owner.info match {
        case info: ClassInfo => info.givenSelfType
        case _ => NoType
      }
      assert(
        (lastSymbol eq sym)
        ||
        (lastSymbol eq null)
        || {
          val lastDefRunId = lastDenotation match {
            case d: SymDenotation => d.validFor.runId
            case _ => lastSymbol.defRunId
          }
          (lastDefRunId != sym.defRunId) ||
          (lastDefRunId == NoRunId)
        }
        ||
        lastSymbol.infoOrCompleter.isInstanceOf[ErrorType]
        ||
        sym.isPackageObject // package objects can be visited before we get around to index them
        ||
        sym.owner != lastSymbol.owner &&
          (sym.owner.derivesFrom(lastSymbol.owner)
           ||
           selfTypeOf(sym).derivesFrom(lastSymbol.owner)
           ||
           selfTypeOf(lastSymbol).derivesFrom(sym.owner)
          ),
        i"""data race? overwriting symbol of type $this,
           |long form = $toString of class $getClass,
           |last sym id = ${lastSymbol.id}, new sym id = ${sym.id},
           |last owner = ${lastSymbol.owner}, new owner = ${sym.owner},
           |period = ${ctx.phase} at run ${ctx.runId}""")
    }

    protected def sig: Signature = Signature.NotAMethod

    private[dotc] def withDenot(denot: Denotation)(implicit ctx: Context): ThisType =
      if (sig != denot.signature)
        withSig(denot.signature).withDenot(denot).asInstanceOf[ThisType]
      else {
        setDenot(denot)
        this
      }

    private[dotc] final def setDenot(denot: Denotation)(implicit ctx: Context): Unit = {
      if (Config.checkNoDoubleBindings)
        if (ctx.settings.YnoDoubleBindings.value)
          checkSymAssign(denot.symbol)

      // additional checks that intercept `denot` can be added here

      lastDenotation = denot
      checkDenot()
      lastSymbol = denot.symbol
      checkedPeriod = Nowhere
    }

    private[dotc] def withSym(sym: Symbol, signature: Signature)(implicit ctx: Context): ThisType =
      if (sig != signature)
        withSig(signature).withSym(sym, signature).asInstanceOf[ThisType]
      else {
        setSym(sym)
        this
      }

    private[dotc] final def setSym(sym: Symbol)(implicit ctx: Context): Unit = {
      if (Config.checkNoDoubleBindings)
        if (ctx.settings.YnoDoubleBindings.value)
          checkSymAssign(sym)
      uncheckedSetSym(sym)
    }

    private[dotc] final def uncheckedSetSym(sym: Symbol): Unit = {
      lastDenotation = null
      lastSymbol = sym
      checkedPeriod = Nowhere
    }

    private def withSig(sig: Signature)(implicit ctx: Context): NamedType =
      TermRef.withSig(prefix, name.asTermName, sig)

    protected def loadDenot(implicit ctx: Context): Denotation = {
      val d = asMemberOf(prefix, allowPrivate = true)
      if (d.exists || ctx.phaseId == FirstPhaseId || !lastDenotation.isInstanceOf[SymDenotation])
        d
      else { // name has changed; try load in earlier phase and make current
        val d = loadDenot(ctx.withPhase(ctx.phaseId - 1)).current
        if (d.exists) d
        else throw new Error(s"failure to reload $this of class $getClass")
      }
    }

    protected def asMemberOf(prefix: Type, allowPrivate: Boolean)(implicit ctx: Context): Denotation =
      if (name.is(ShadowedName)) prefix.nonPrivateMember(name.exclude(ShadowedName))
      else if (!allowPrivate) prefix.nonPrivateMember(name)
      else prefix.member(name)

    /** (1) Reduce a type-ref `W # X` or `W { ... } # U`, where `W` is a wildcard type
     *  to an (unbounded) wildcard type.
     *
     *  (2) Reduce a type-ref `T { X = U; ... } # X`  to   `U`
     *  provided `U` does not refer with a RecThis to the
     *  refinement type `T { X = U; ... }`
     */
    def reduceProjection(implicit ctx: Context): Type = {
      val reduced = prefix.lookupRefined(name)
      if (reduced.exists) reduced else this
    }

    def symbol(implicit ctx: Context): Symbol = {
      val now = ctx.period
      if (checkedPeriod == now ||
          lastDenotation == null && lastSymbol != null) lastSymbol
      else denot.symbol
    }

    /** Retrieves currently valid symbol without necessarily updating denotation.
     *  Assumes that symbols do not change between periods in the same run.
     *  Used to get the class underlying a ThisType.
     */
    private[Types] def stableInRunSymbol(implicit ctx: Context): Symbol =
      if (checkedPeriod.runId == ctx.runId) lastSymbol
      else symbol

    def info(implicit ctx: Context): Type = denot.info

    def isType = isInstanceOf[TypeRef]
    def isTerm = isInstanceOf[TermRef]

    /** Guard against cycles that can arise if given `op`
     *  follows info. The problematic cases are a type alias to itself or
     *  bounded by itself or a val typed as itself:
     *
     *  type T <: T
     *  val x: x.type
     *
     *  These are errors but we have to make sure that operations do
     *  not loop before the error is detected.
     */
    final def controlled[T](op: => T)(implicit ctx: Context): T = try {
      ctx.underlyingRecursions += 1
      if (ctx.underlyingRecursions < Config.LogPendingUnderlyingThreshold)
        op
      else if (ctx.pendingUnderlying contains this)
        throw CyclicReference(symbol)
      else
        try {
          ctx.pendingUnderlying += this
          op
        } finally {
          ctx.pendingUnderlying -= this
        }
    } finally {
      ctx.underlyingRecursions -= 1
    }

    /** A selection of the same kind, but with potentially a different prefix.
     *  The following normalizations are performed for type selections T#A:
     *
     *     T#A --> B                if A is bound to an alias `= B` in T
     *
     *  If Config.splitProjections is set:
     *
     *     (S & T)#A --> S#A        if T does not have a member named A
     *               --> T#A        if S does not have a member named A
     *               --> S#A & T#A  otherwise
     *     (S | T)#A --> S#A | T#A
     */
    def derivedSelect(prefix: Type)(implicit ctx: Context): Type =
      if (prefix eq this.prefix) this
      else if (isType) {
        val res = prefix.lookupRefined(name)
        if (res.exists) res
        else if (Config.splitProjections)
          prefix match {
            case prefix: AndType =>
              def isMissing(tp: Type) = tp match {
                case tp: TypeRef => !tp.info.exists
                case _ => false
              }
              val derived1 = derivedSelect(prefix.tp1)
              val derived2 = derivedSelect(prefix.tp2)
              return (
                if (isMissing(derived1)) derived2
                else if (isMissing(derived2)) derived1
                else prefix.derivedAndType(derived1, derived2))
            case prefix: OrType =>
              val derived1 = derivedSelect(prefix.tp1)
              val derived2 = derivedSelect(prefix.tp2)
              return prefix.derivedOrType(derived1, derived2)
            case _ =>
              newLikeThis(prefix)
          }
        else newLikeThis(prefix)
      }
      else prefix match {
        case _: WildcardType => WildcardType
        case _ => newLikeThis(prefix)
      }

    /** Create a NamedType of the same kind as this type, but with a new prefix.
     */
    def newLikeThis(prefix: Type)(implicit ctx: Context): NamedType =
      NamedType(prefix, name)

    /** Create a NamedType of the same kind as this type, but with a "inherited name".
     *  This is necessary to in situations like the following:
     *
     *    class B { def m: T1 }
     *    class C extends B { private def m: T2; ... C.m }
     *    object C extends C
     *    object X { ... C.m }
     *
     *  The two references of C.m in class C and object X refer to different
     *  definitions: The one in C refers to C#m whereas the one in X refers to B#m.
     *  But the type C.m must have only one denotation, so it can't refer to two
     *  members depending on context.
     *
     *  In situations like this, the reference in X would get the type
     *  `<C.m>.shadowed` to make clear that we mean the inherited member, not
     *  the private one.
     *
     *  Note: An alternative, possibly more robust scheme would be to give
     *  private members special names. A private definition would have a special
     *  name (say m' in the example above), but would be entered in its enclosing
     *  under both private and public names, so it could still be found by looking up
     *  the public name.
     */
    def shadowed(implicit ctx: Context): NamedType =
      NamedType(prefix, name.derived(ShadowedName))

    override def equals(that: Any) = that match {
      case that: NamedType =>
        this.name == that.name &&
        this.prefix == that.prefix &&
        !that.isInstanceOf[TermRefWithSignature] &&
        !that.isInstanceOf[WithFixedSym]
      case _ =>
        false
    }

    /* A version of toString which also prints aliases. Can be used for debugging
    override def toString =
      if (isTerm) s"TermRef($prefix, $name)"
      else s"TypeRef($prefix, $name)${
        if (lastDenotation != null && lastDenotation.infoOrCompleter.isAlias)
          s"@@@ ${lastDenotation.infoOrCompleter.asInstanceOf[TypeAlias].hi}"
        else ""}"
    */
  }

  abstract case class TermRef(override val prefix: Type, name: TermName) extends NamedType with SingletonType {

    type ThisType = TermRef

    //assert(name.toString != "<local Coder>")
    override def underlying(implicit ctx: Context): Type = {
      val d = denot
      if (d.isOverloaded) NoType else d.info
    }

    override def signature(implicit ctx: Context): Signature = denot.signature

    override def isOverloaded(implicit ctx: Context) = denot.isOverloaded

    private def rewrap(sd: SingleDenotation)(implicit ctx: Context) =
      TermRef.withSigAndDenot(prefix, name, sd.signature, sd)

    def alternatives(implicit ctx: Context): List[TermRef] =
      denot.alternatives map rewrap

    def altsWith(p: Symbol => Boolean)(implicit ctx: Context): List[TermRef] =
      denot.altsWith(p) map rewrap
  }

  abstract case class TypeRef(override val prefix: Type, name: TypeName) extends NamedType {

    type ThisType = TypeRef

    override def underlying(implicit ctx: Context): Type = info
  }

  final class TermRefWithSignature(prefix: Type, name: TermName, override val sig: Signature) extends TermRef(prefix, name) {
    assert(prefix ne NoPrefix)
    override def signature(implicit ctx: Context) = sig
    override def loadDenot(implicit ctx: Context): Denotation = {
      val d = super.loadDenot
      if (sig eq Signature.OverloadedSignature) d
      else d.atSignature(sig).checkUnique
    }

    private def fixDenot(candidate: TermRef, prefix: Type)(implicit ctx: Context): TermRef =
      if (symbol.exists && !candidate.symbol.exists) { // recompute from previous symbol
        val ownSym = symbol
        val newd = asMemberOf(prefix, allowPrivate = ownSym.is(Private))
        candidate.withDenot(newd.suchThat(_.signature == ownSym.signature))
      }
      else candidate

    override def newLikeThis(prefix: Type)(implicit ctx: Context): TermRef =
      fixDenot(TermRef.withSig(prefix, name, sig), prefix)

    override def shadowed(implicit ctx: Context): NamedType =
      fixDenot(TermRef.withSig(prefix, name.derived(ShadowedName), sig), prefix)

    override def equals(that: Any) = that match {
      case that: TermRefWithSignature =>
        this.prefix == that.prefix &&
        this.name == that.name &&
        this.sig == that.sig
      case _ =>
        false
    }
    override def computeHash = doHash((name, sig), prefix)
    override def toString = super.toString ++ s"/withSig($sig)"
  }

  trait WithFixedSym extends NamedType {
    def fixedSym: Symbol
    assert(fixedSym ne NoSymbol)
    uncheckedSetSym(fixedSym)

    override def withDenot(denot: Denotation)(implicit ctx: Context): ThisType = {
      assert(denot.symbol eq fixedSym)
      setDenot(denot)
      this
    }

    override def withSym(sym: Symbol, signature: Signature)(implicit ctx: Context): ThisType =
      unsupported("withSym")

    override def newLikeThis(prefix: Type)(implicit ctx: Context): NamedType =
      NamedType.withFixedSym(prefix, fixedSym)

    override def equals(that: Any) = that match {
      case that: WithFixedSym => this.prefix == that.prefix && (this.fixedSym eq that.fixedSym)
      case _ => false
    }
    override def computeHash = doHash(fixedSym, prefix)
  }

  final class CachedTermRef(prefix: Type, name: TermName, hc: Int) extends TermRef(prefix, name) {
    assert(prefix ne NoPrefix)
    myHash = hc
    override def computeHash = unsupported("computeHash")
  }

  final class CachedTypeRef(prefix: Type, name: TypeName, hc: Int) extends TypeRef(prefix, name) {
    assert(prefix ne NoPrefix)
    myHash = hc
    override def computeHash = unsupported("computeHash")
  }

  // Those classes are non final as Linker extends them.
  class TermRefWithFixedSym(prefix: Type, name: TermName, val fixedSym: TermSymbol) extends TermRef(prefix, name) with WithFixedSym
  class TypeRefWithFixedSym(prefix: Type, name: TypeName, val fixedSym: TypeSymbol) extends TypeRef(prefix, name) with WithFixedSym

  /** Assert current phase does not have erasure semantics */
  private def assertUnerased()(implicit ctx: Context) =
    if (Config.checkUnerased) assert(!ctx.phase.erasedTypes)

  object NamedType {
    def apply(prefix: Type, name: Name)(implicit ctx: Context) =
      if (name.isTermName) TermRef.all(prefix, name.asTermName)
      else TypeRef(prefix, name.asTypeName)
    def apply(prefix: Type, name: Name, denot: Denotation)(implicit ctx: Context) =
      if (name.isTermName) TermRef(prefix, name.asTermName, denot)
      else TypeRef(prefix, name.asTypeName, denot)
    def withFixedSym(prefix: Type, sym: Symbol)(implicit ctx: Context) =
      if (sym.isType) TypeRef.withFixedSym(prefix, sym.name.asTypeName, sym.asType)
      else TermRef.withFixedSym(prefix, sym.name.asTermName, sym.asTerm)
    def withSymAndName(prefix: Type, sym: Symbol, name: Name)(implicit ctx: Context): NamedType =
      if (sym.isType) TypeRef.withSymAndName(prefix, sym.asType, name.asTypeName)
      else TermRef.withSymAndName(prefix, sym.asTerm, name.asTermName)
  }

  object TermRef {

    private def symbolicRefs(implicit ctx: Context) = ctx.phase.symbolicRefs

    /** Create term ref with given name, without specifying a signature.
     *  Its meaning is the (potentially multi-) denotation of the member(s)
     *  of prefix with given name.
     */
    def all(prefix: Type, name: TermName)(implicit ctx: Context): TermRef = {
      ctx.uniqueNamedTypes.enterIfNew(prefix, name).asInstanceOf[TermRef]
    }

    /** Create term ref referring to given symbol, taking the signature
     *  from the symbol if it is completed, or creating a term ref without
     *  signature, if symbol is not yet completed.
     */
    def apply(prefix: Type, sym: TermSymbol)(implicit ctx: Context): TermRef =
      withSymAndName(prefix, sym, sym.name)

    /** Create term ref to given initial denotation, taking the signature
     *  from the denotation if it is completed, or creating a term ref without
     *  signature, if denotation is not yet completed.
     */
    def apply(prefix: Type, name: TermName, denot: Denotation)(implicit ctx: Context): TermRef = {
      if ((prefix eq NoPrefix) || denot.symbol.isFresh || symbolicRefs)
        apply(prefix, denot.symbol.asTerm)
      else denot match {
        case denot: SymDenotation if denot.isCompleted => withSig(prefix, name, denot.signature)
        case _ => all(prefix, name)
      }
    } withDenot denot

    /** Create a non-member term ref (which cannot be reloaded using `member`),
     *  with given prefix, name, and signature
     */
    def withFixedSym(prefix: Type, name: TermName, sym: TermSymbol)(implicit ctx: Context): TermRef =
      unique(new TermRefWithFixedSym(prefix, name, sym))

    /** Create a term ref referring to given symbol with given name, taking the signature
     *  from the symbol if it is completed, or creating a term ref without
     *  signature, if symbol is not yet completed. This is very similar to TermRef(Type, Symbol),
     *  except for two differences:
     *  (1) The symbol might not yet have a denotation, so the name needs to be given explicitly.
     *  (2) The name in the term ref need not be the same as the name of the Symbol.
     */
    def withSymAndName(prefix: Type, sym: TermSymbol, name: TermName)(implicit ctx: Context): TermRef =
      if ((prefix eq NoPrefix) || sym.isFresh || symbolicRefs)
        withFixedSym(prefix, name, sym)
      else if (sym.defRunId != NoRunId && sym.isCompleted)
        withSig(prefix, name, sym.signature) withSym (sym, sym.signature)
        // Linker note:
        // this is problematic, as withSig method could return a hash-consed refference
        // that could have symbol already set making withSym trigger a double-binding error
        // ./tests/run/absoverride.scala demonstates this
      else
        all(prefix, name) withSym (sym, Signature.NotAMethod)

    /** Create a term ref to given symbol, taking the signature from the symbol
     *  (which must be completed).
     */
    def withSig(prefix: Type, sym: TermSymbol)(implicit ctx: Context): TermRef =
      if ((prefix eq NoPrefix) || sym.isFresh || symbolicRefs) withFixedSym(prefix, sym.name, sym)
      else withSig(prefix, sym.name, sym.signature).withSym(sym, sym.signature)

    /** Create a term ref with given prefix, name and signature */
    def withSig(prefix: Type, name: TermName, sig: Signature)(implicit ctx: Context): TermRef =
      unique(new TermRefWithSignature(prefix, name, sig))

    /** Create a term ref with given prefix, name, signature, and initial denotation */
    def withSigAndDenot(prefix: Type, name: TermName, sig: Signature, denot: Denotation)(implicit ctx: Context): TermRef = {
      if ((prefix eq NoPrefix) || denot.symbol.isFresh || symbolicRefs)
        withFixedSym(prefix, denot.symbol.asTerm.name, denot.symbol.asTerm)
      else
        withSig(prefix, name, sig)
    } withDenot denot
  }

  object TypeRef {
    /** Create type ref with given prefix and name */
    def apply(prefix: Type, name: TypeName)(implicit ctx: Context): TypeRef =
      ctx.uniqueNamedTypes.enterIfNew(prefix, name).asInstanceOf[TypeRef]

    /** Create type ref to given symbol */
    def apply(prefix: Type, sym: TypeSymbol)(implicit ctx: Context): TypeRef =
      withSymAndName(prefix, sym, sym.name)

    /** Create a non-member type ref  (which cannot be reloaded using `member`),
     *  with given prefix, name, and symbol.
     */
    def withFixedSym(prefix: Type, name: TypeName, sym: TypeSymbol)(implicit ctx: Context): TypeRef =
      unique(new TypeRefWithFixedSym(prefix, name, sym))

    /** Create a type ref referring to given symbol with given name.
     *  This is very similar to TypeRef(Type, Symbol),
     *  except for two differences:
     *  (1) The symbol might not yet have a denotation, so the name needs to be given explicitly.
     *  (2) The name in the type ref need not be the same as the name of the Symbol.
     */
    def withSymAndName(prefix: Type, sym: TypeSymbol, name: TypeName)(implicit ctx: Context): TypeRef =
      if ((prefix eq NoPrefix) || sym.isFresh) withFixedSym(prefix, name, sym)
      else apply(prefix, name).withSym(sym, Signature.NotAMethod)

    /** Create a type ref with given name and initial denotation */
    def apply(prefix: Type, name: TypeName, denot: Denotation)(implicit ctx: Context): TypeRef = {
      if ((prefix eq NoPrefix) || denot.symbol.isFresh) apply(prefix, denot.symbol.asType)
      else apply(prefix, name)
    } withDenot denot
  }

  // --- Other SingletonTypes: ThisType/SuperType/ConstantType ---------------------------

  /** The type cls.this
   *  @param tref    A type ref which indicates the class `cls`.
   *  Note: we do not pass a class symbol directly, because symbols
   *  do not survive runs whereas typerefs do.
   */
  abstract case class ThisType(tref: TypeRef) extends CachedProxyType with SingletonType {
    def cls(implicit ctx: Context): ClassSymbol = tref.stableInRunSymbol.asClass
    override def underlying(implicit ctx: Context): Type =
      if (ctx.erasedTypes) tref else cls.classInfo.selfType
    override def computeHash = doHash(tref)
  }

  final class CachedThisType(tref: TypeRef) extends ThisType(tref)

  object ThisType {
    /** Normally one should use ClassSymbol#thisType instead */
    def raw(tref: TypeRef)(implicit ctx: Context) =
      unique(new CachedThisType(tref))
  }

  /** The type of a super reference cls.super where
   *  `thistpe` is cls.this and `supertpe` is the type of the value referenced
   *  by `super`.
   */
  abstract case class SuperType(thistpe: Type, supertpe: Type) extends CachedProxyType with SingletonType {
    override def underlying(implicit ctx: Context) = supertpe
    def derivedSuperType(thistpe: Type, supertpe: Type)(implicit ctx: Context) =
      if ((thistpe eq this.thistpe) && (supertpe eq this.supertpe)) this
      else SuperType(thistpe, supertpe)
    override def computeHash = doHash(thistpe, supertpe)
  }

  final class CachedSuperType(thistpe: Type, supertpe: Type) extends SuperType(thistpe, supertpe)

  object SuperType {
    def apply(thistpe: Type, supertpe: Type)(implicit ctx: Context): Type = {
      assert(thistpe != NoPrefix)
      unique(new CachedSuperType(thistpe, supertpe))
    }
  }

  /** A constant type with  single `value`. */
  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 CachedConstantType(value: Constant) extends ConstantType(value)

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

  case class LazyRef(refFn: () => Type) extends UncachedProxyType with ValueType {
    private var myRef: Type = null
    private var computed = false
    def ref = {
      if (computed) assert(myRef != null)
      else {
        computed = true
        myRef = refFn()
      }
      myRef
    }
    def evaluating = computed && myRef == null
    override def underlying(implicit ctx: Context) = ref
    override def toString = s"LazyRef($ref)"
    override def equals(other: Any) = other match {
      case other: LazyRef => this.ref.equals(other.ref)
      case _ => false
    }
    override def hashCode = ref.hashCode + 37
  }

  // --- Refined Type and RecType ------------------------------------------------

  abstract class RefinedOrRecType extends CachedProxyType with ValueType {
    def parent: Type
  }

  /** A refined type parent { refinement }
   *  @param refinedName  The name of the refinement declaration
   *  @param infoFn: A function that produces the info of the refinement declaration,
   *                 given the refined type itself.
   */
  abstract case class RefinedType(parent: Type, refinedName: Name, refinedInfo: Type) extends RefinedOrRecType {

    if (refinedName.isTermName) assert(refinedInfo.isInstanceOf[TermType])
    else assert(refinedInfo.isInstanceOf[TypeType])

    override def underlying(implicit ctx: Context) = parent

    private def badInst =
      throw new AssertionError(s"bad instantiation: $this")

    def checkInst(implicit ctx: Context): this.type = this // debug hook

    def derivedRefinedType(parent: Type, refinedName: Name, refinedInfo: Type)(implicit ctx: Context): Type =
      if ((parent eq this.parent) && (refinedName eq this.refinedName) && (refinedInfo eq this.refinedInfo)) this
      else RefinedType(parent, refinedName, refinedInfo)

    /** Add this refinement to `parent`, provided If `refinedName` is a member of `parent`. */
    def wrapIfMember(parent: Type)(implicit ctx: Context): Type =
      if (parent.member(refinedName).exists) derivedRefinedType(parent, refinedName, refinedInfo)
      else parent

    override def equals(that: Any) = that match {
      case that: RefinedType =>
        this.parent == that.parent &&
        this.refinedName == that.refinedName &&
        this.refinedInfo == that.refinedInfo
      case _ =>
        false
    }
    override def computeHash = doHash(refinedName, refinedInfo, parent)
    override def toString = s"RefinedType($parent, $refinedName, $refinedInfo)"
  }

  class CachedRefinedType(parent: Type, refinedName: Name, refinedInfo: Type, hc: Int)
  extends RefinedType(parent, refinedName, refinedInfo) {
    myHash = hc
    override def computeHash = unsupported("computeHash")
  }

  object RefinedType {
    @tailrec def make(parent: Type, names: List[Name], infos: List[Type])(implicit ctx: Context): Type =
      if (names.isEmpty) parent
      else make(RefinedType(parent, names.head, infos.head), names.tail, infos.tail)

    def apply(parent: Type, name: Name, info: Type)(implicit ctx: Context): RefinedType = {
      assert(!ctx.erasedTypes)
      ctx.base.uniqueRefinedTypes.enterIfNew(parent, name, info).checkInst
    }
  }

  class RecType(parentExp: RecType => Type) extends RefinedOrRecType with BindingType {

    // See discussion in findMember#goRec why these vars are needed
    private[Types] var opened: Boolean = false
    private[Types] var openedTwice: Boolean = false

    val parent = parentExp(this)

    override def underlying(implicit ctx: Context): Type = parent

    def derivedRecType(parent: Type)(implicit ctx: Context): RecType =
      if (parent eq this.parent) this
      else RecType(rt => parent.substRecThis(this, RecThis(rt)))

    def rebind(parent: Type)(implicit ctx: Context): Type =
      if (parent eq this.parent) this
      else RecType.closeOver(rt => parent.substRecThis(this, RecThis(rt)))

    override def equals(other: Any) = other match {
      case other: RecType => other.parent == this.parent
      case _ => false
    }

    def isReferredToBy(tp: Type)(implicit ctx: Context): Boolean = {
      val refacc = new TypeAccumulator[Boolean] {
        override def apply(x: Boolean, tp: Type) = x || {
          tp match {
            case tp: TypeRef => apply(x, tp.prefix)
            case tp: RecThis => RecType.this eq tp.binder
            case tp: LazyRef => true // To be safe, assume a reference exists
            case _ => foldOver(x, tp)
          }
        }
      }
      refacc.apply(false, tp)
    }

    override def computeHash = doHash(parent)
    override def toString = s"RecType($parent | $hashCode)"

    private def checkInst(implicit ctx: Context): this.type = this // debug hook
  }

  object RecType {

    /** Create a RecType, normalizing its contents. This means:
     *
     *   1. Nested Rec types on the type's spine are merged with the outer one.
     *   2. Any refinement of the form `type T = z.T` on the spine of the type
     *      where `z` refers to the created rec-type is replaced by
     *      `type T`. This avoids infinite recursons later when we
     *      try to follow these references.
     *   TODO: Figure out how to guarantee absence of cycles
     *         of length > 1
     */
    def apply(parentExp: RecType => Type)(implicit ctx: Context): RecType = {
      val rt = new RecType(parentExp)
      def normalize(tp: Type): Type = tp.stripTypeVar match {
        case tp: RecType =>
          normalize(tp.parent.substRecThis(tp, RecThis(rt)))
        case tp @ RefinedType(parent, rname, rinfo) =>
          val rinfo1 = rinfo match {
            case TypeAlias(TypeRef(RecThis(`rt`), `rname`)) => TypeBounds.empty
            case _ => rinfo
          }
          tp.derivedRefinedType(normalize(parent), rname, rinfo1)
        case tp =>
          tp
      }
      unique(rt.derivedRecType(normalize(rt.parent))).checkInst
    }
    def closeOver(parentExp: RecType => Type)(implicit ctx: Context) = {
      val rt = this(parentExp)
      if (rt.isReferredToBy(rt.parent)) rt else rt.parent
    }
  }

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

  trait AndOrType extends ValueType { // todo: check where we can simplify using AndOrType
    def tp1: Type
    def tp2: Type
    def isAnd: Boolean
    def derivedAndOrType(tp1: Type, tp2: Type)(implicit ctx: Context): Type  // needed?
  }

  abstract case class AndType(tp1: Type, tp2: Type) extends CachedGroundType with AndOrType {

    def isAnd = true

    def derivedAndType(tp1: Type, tp2: Type)(implicit ctx: Context): Type =
      if ((tp1 eq this.tp1) && (tp2 eq this.tp2)) this
      else AndType.make(tp1, tp2, checkValid = true)

    def derived_& (tp1: Type, tp2: Type)(implicit ctx: Context): Type =
      if ((tp1 eq this.tp1) && (tp2 eq this.tp2)) this
      else tp1 & tp2

    def derivedAndOrType(tp1: Type, tp2: Type)(implicit ctx: Context): Type =
      derivedAndType(tp1, tp2)

    override def computeHash = doHash(tp1, tp2)
  }

  final class CachedAndType(tp1: Type, tp2: Type) extends AndType(tp1, tp2)

  object AndType {
    def apply(tp1: Type, tp2: Type)(implicit ctx: Context): AndType = {
      assert(tp1.isValueType && tp2.isValueType, i"$tp1 & $tp2 / " + s"$tp1 & $tp2")
      unchecked(tp1, tp2)
    }

    def unchecked(tp1: Type, tp2: Type)(implicit ctx: Context): AndType = {
      assertUnerased()
      unique(new CachedAndType(tp1, tp2))
    }

    /** Make an AndType using `op` unless clearly unnecessary (i.e. without
     *  going through `&`).
     */
    def make(tp1: Type, tp2: Type, checkValid: Boolean = false)(implicit ctx: Context): Type =
      if ((tp1 eq tp2) || (tp2 eq defn.AnyType))
        tp1
      else if (tp1 eq defn.AnyType)
        tp2
      else
        if (checkValid) apply(tp1, tp2) else unchecked(tp1, tp2)
  }

  abstract case class OrType(tp1: Type, tp2: Type) extends CachedGroundType with AndOrType {

    assert(tp1.isInstanceOf[ValueType] && tp2.isInstanceOf[ValueType])
    def isAnd = false

    private[this] var myJoin: Type = _
    private[this] var myJoinPeriod: Period = Nowhere

    /** Replace or type by the closest non-or type above it */
    def join(implicit ctx: Context): Type = {
      if (myJoinPeriod != ctx.period) {
        myJoin = ctx.orDominator(this)
        core.println(i"join of $this == $myJoin")
        assert(myJoin != this)
        myJoinPeriod = ctx.period
      }
      myJoin
    }

    def derivedOrType(tp1: Type, tp2: Type)(implicit ctx: Context): Type =
      if ((tp1 eq this.tp1) && (tp2 eq this.tp2)) this
      else OrType.make(tp1, tp2)

    def derivedAndOrType(tp1: Type, tp2: Type)(implicit ctx: Context): Type =
      derivedOrType(tp1, tp2)

    override def computeHash = doHash(tp1, tp2)
  }

  final class CachedOrType(tp1: Type, tp2: Type) extends OrType(tp1, tp2)

  object OrType {
    def apply(tp1: Type, tp2: Type)(implicit ctx: Context) = {
      assertUnerased()
      unique(new CachedOrType(tp1, tp2))
    }
    def make(tp1: Type, tp2: Type)(implicit ctx: Context): Type =
      if (tp1 eq tp2) tp1 else apply(tp1, tp2)
  }

  // ----- ExprType and LambdaTypes -----------------------------------

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

  /** A trait that mixes in functionality for signature caching */
  trait MethodicType extends TermType {

    private[this] var mySignature: Signature = _
    private[this] var mySignatureRunId: Int = NoRunId

    protected def computeSignature(implicit ctx: Context): Signature

    protected def resultSignature(implicit ctx: Context) = try resultType match {
      case rtp: MethodicType => rtp.signature
      case tp =>
        if (tp.isRef(defn.UnitClass)) Signature(Nil, defn.UnitClass.fullName.asTypeName)
        else Signature(tp, isJava = false)
    }
    catch {
      case ex: AssertionError =>
        println(i"failure while taking result signature of $this: $resultType")
        throw ex
    }

    final override def signature(implicit ctx: Context): Signature = {
      if (ctx.runId != mySignatureRunId) {
        mySignature = computeSignature
        if (!mySignature.isUnderDefined) mySignatureRunId = ctx.runId
      }
      mySignature
    }
  }

  /** A by-name parameter type of the form `=> T`, or the type of a method with no parameter list. */
  abstract case class ExprType(resType: Type)
  extends CachedProxyType with TermType with MethodicType {
    override def resultType(implicit ctx: Context): Type = resType
    override def underlying(implicit ctx: Context): Type = resType
    protected def computeSignature(implicit ctx: Context): Signature = resultSignature
    def derivedExprType(resType: Type)(implicit ctx: Context) =
      if (resType eq this.resType) this else ExprType(resType)
    override def computeHash = doHash(resType)
  }

  final class CachedExprType(resultType: Type) extends ExprType(resultType)

  object ExprType {
    def apply(resultType: Type)(implicit ctx: Context) = {
      assertUnerased()
      unique(new CachedExprType(resultType))
    }
  }

  /** The lambda type square:
   *
   *    LambdaType   |   TermLambda      |   TypeLambda
   *    -------------+-------------------+------------------
   *    HKLambda     |   HKTermLambda    |   HKTypeLambda
   *    MethodOrPoly |   MethodType	     |   PolyType
   */
  trait LambdaType extends BindingType with MethodicType { self =>
    type ThisName <: Name
    type PInfo <: Type
    type This <: LambdaType{type PInfo = self.PInfo}

    def paramNames: List[ThisName]
    def paramInfos: List[PInfo]
    def resType: Type
    def newParamRef(n: Int): ParamRef

    override def resultType(implicit ctx: Context) = resType

    def isJava: Boolean = false
    def isImplicit = false

    def isDependent(implicit ctx: Context): Boolean
    def isParamDependent(implicit ctx: Context): Boolean

    final def isTermLambda = isInstanceOf[TermLambda]
    final def isTypeLambda = isInstanceOf[TypeLambda]
    final def isHigherKinded = isInstanceOf[TypeProxy]

    lazy val paramRefs: List[ParamRef] = paramNames.indices.toList.map(newParamRef)

    protected def computeSignature(implicit ctx: Context) = resultSignature

    final def instantiate(argTypes: => List[Type])(implicit ctx: Context): Type =
      if (isDependent) resultType.substParams(this, argTypes)
      else resultType

    def companion: LambdaTypeCompanion[ThisName, PInfo, This]

    /** The type `[tparams := paramRefs] tp`, where `tparams` can be
     *  either a list of type parameter symbols or a list of lambda parameters
     */
    def integrate(tparams: List[ParamInfo], tp: Type)(implicit ctx: Context): Type =
      tparams match {
        case LambdaParam(lam, _) :: _ => tp.subst(lam, this)
        case tparams: List[Symbol @unchecked] => tp.subst(tparams, paramRefs)
      }

    final def derivedLambdaType(paramNames: List[ThisName] = this.paramNames,
                          paramInfos: List[PInfo] = this.paramInfos,
                          resType: Type = this.resType)(implicit ctx: Context) =
      if ((paramNames eq this.paramNames) && (paramInfos eq this.paramInfos) && (resType eq this.resType)) this
      else newLikeThis(paramNames, paramInfos, resType)

    final def newLikeThis(paramNames: List[ThisName], paramInfos: List[PInfo], resType: Type)(implicit ctx: Context): This =
      companion(paramNames)(
          x => paramInfos.mapConserve(_.subst(this, x).asInstanceOf[PInfo]),
          x => resType.subst(this, x))

    protected def prefixString: String
    final override def toString = s"$prefixString($paramNames, $paramInfos, $resType)"
  }

  abstract class HKLambda extends CachedProxyType with LambdaType {
    final override def underlying(implicit ctx: Context) = resType

    final override def computeHash = doHash(paramNames, resType, paramInfos)

    // Defined here instead of in LambdaType for efficiency
    final override def equals(that: Any) = that match {
      case that: HKLambda =>
        this.paramNames == that.paramNames &&
        this.paramInfos == that.paramInfos &&
        this.resType == that.resType &&
        (this.companion eq that.companion)
      case _ =>
        false
    }
  }

  abstract class MethodOrPoly extends CachedGroundType with LambdaType with TermType {
    final override def computeHash = doHash(paramNames, resType, paramInfos)

    // Defined here instead of in LambdaType for efficiency
    final override def equals(that: Any) = that match {
      case that: MethodOrPoly =>
        this.paramNames == that.paramNames &&
        this.paramInfos == that.paramInfos &&
        this.resType == that.resType &&
        (this.companion eq that.companion)
      case _ =>
        false
    }
  }

  trait TermLambda extends LambdaType { thisLambdaType =>
    import DepStatus._
    type ThisName = TermName
    type PInfo = Type
    type This <: TermLambda

    override def resultType(implicit ctx: Context): Type =
      if (dependencyStatus == FalseDeps) { // dealias all false dependencies
        val dealiasMap = new TypeMap {
          def apply(tp: Type) = tp match {
            case tp @ TypeRef(pre, name) =>
              tp.info match {
                case TypeAlias(alias) if depStatus(NoDeps, pre) == TrueDeps => apply(alias)
                case _ => mapOver(tp)
              }
            case _ =>
              mapOver(tp)
          }
        }
        dealiasMap(resType)
      }
      else resType

    private var myDependencyStatus: DependencyStatus = Unknown
    private var myParamDependencyStatus: DependencyStatus = Unknown

    private def depStatus(initial: DependencyStatus, tp: Type)(implicit ctx: Context): DependencyStatus = {
      def combine(x: DependencyStatus, y: DependencyStatus) = {
        val status = (x & StatusMask) max (y & StatusMask)
        val provisional = (x | y) & Provisional
        (if (status == TrueDeps) status else status | provisional).toByte
      }
      val depStatusAcc = new TypeAccumulator[DependencyStatus] {
        def apply(status: DependencyStatus, tp: Type) =
          if (status == TrueDeps) status
          else
            tp match {
              case TermParamRef(`thisLambdaType`, _) => TrueDeps
              case tp: TypeRef =>
                val status1 = foldOver(status, tp)
                tp.info match { // follow type alias to avoid dependency
                  case TypeAlias(alias) if status1 == TrueDeps && status != TrueDeps =>
                    combine(apply(status, alias), FalseDeps)
                  case _ =>
                    status1
                }
              case tp: TypeVar if !tp.isInstantiated => combine(status, Provisional)
              case _ => foldOver(status, tp)
            }
      }
      depStatusAcc(initial, tp)
    }

    /** The dependency status of this method. Some examples:
     *
     *    class C extends { type S; type T = String }
     *    def f(x: C)(y: Boolean)   // dependencyStatus = NoDeps
     *    def f(x: C)(y: x.S)       // dependencyStatus = TrueDeps
     *    def f(x: C)(y: x.T)       // dependencyStatus = FalseDeps, i.e.
     *                              // dependency can be eliminated by dealiasing.
     */
    private def dependencyStatus(implicit ctx: Context): DependencyStatus = {
      if (myDependencyStatus != Unknown) myDependencyStatus
      else {
        val result = depStatus(NoDeps, resType)
        if ((result & Provisional) == 0) myDependencyStatus = result
        (result & StatusMask).toByte
      }
    }

    /** The parameter dependency status of this method. Analogous to `dependencyStatus`,
     *  but tracking dependencies in same parameter list.
     */
    private def paramDependencyStatus(implicit ctx: Context): DependencyStatus = {
      if (myParamDependencyStatus != Unknown) myParamDependencyStatus
      else {
        val result =
          if (paramInfos.isEmpty) NoDeps
          else (NoDeps /: paramInfos.tail)(depStatus(_, _))
        if ((result & Provisional) == 0) myParamDependencyStatus = result
        (result & StatusMask).toByte
      }
    }

    /** Does result type contain references to parameters of this method type,
     *  which cannot be eliminated by de-aliasing?
     */
    def isDependent(implicit ctx: Context): Boolean = dependencyStatus == TrueDeps

    /** Does one of the parameter types contain references to earlier parameters
     *  of this method type which cannot be eliminated by de-aliasing?
     */
    def isParamDependent(implicit ctx: Context): Boolean = paramDependencyStatus == TrueDeps

    def newParamRef(n: Int) = TermParamRef(this, n)
  }

  abstract case class MethodType(paramNames: List[TermName])(
      paramInfosExp: MethodType => List[Type],
      resultTypeExp: MethodType => Type)
    extends MethodOrPoly with TermLambda with NarrowCached { thisMethodType =>
    import MethodType._

    type This = MethodType

    val paramInfos = paramInfosExp(this)
    val resType = resultTypeExp(this)
    assert(resType.exists)

    override def computeSignature(implicit ctx: Context): Signature =
      resultSignature.prepend(paramInfos, isJava)

    protected def prefixString = "MethodType"
  }

  final class CachedMethodType(paramNames: List[TermName])(paramInfosExp: MethodType => List[Type], resultTypeExp: MethodType => Type)
    extends MethodType(paramNames)(paramInfosExp, resultTypeExp) {
    def companion = MethodType
  }

  final class JavaMethodType(paramNames: List[TermName])(paramInfosExp: MethodType => List[Type], resultTypeExp: MethodType => Type)
    extends MethodType(paramNames)(paramInfosExp, resultTypeExp) {
    def companion = JavaMethodType
    override def isJava = true
    override protected def prefixString = "JavaMethodType"
  }

  final class ImplicitMethodType(paramNames: List[TermName])(paramInfosExp: MethodType => List[Type], resultTypeExp: MethodType => Type)
    extends MethodType(paramNames)(paramInfosExp, resultTypeExp) {
    def companion = ImplicitMethodType
    override def isImplicit = true
    override protected def prefixString = "ImplicitMethodType"
  }

  abstract class LambdaTypeCompanion[N <: Name, PInfo <: Type, LT <: LambdaType] {
    def syntheticParamName(n: Int): N

    @sharable private val memoizedNames = new mutable.HashMap[Int, List[N]]
    def syntheticParamNames(n: Int): List[N] = synchronized {
      memoizedNames.getOrElseUpdate(n, (0 until n).map(syntheticParamName).toList)
    }

    def apply(paramNames: List[N])(paramInfosExp: LT => List[PInfo], resultTypeExp: LT => Type)(implicit ctx: Context): LT
    def apply(paramNames: List[N], paramInfos: List[PInfo], resultType: Type)(implicit ctx: Context): LT =
      apply(paramNames)(_ => paramInfos, _ => resultType)
    def apply(paramInfos: List[PInfo])(resultTypeExp: LT => Type)(implicit ctx: Context): LT =
      apply(syntheticParamNames(paramInfos.length))(_ => paramInfos, resultTypeExp)
    def apply(paramInfos: List[PInfo], resultType: Type)(implicit ctx: Context): LT =
      apply(syntheticParamNames(paramInfos.length), paramInfos, resultType)

    protected def paramName(param: ParamInfo.Of[N])(implicit ctx: Context): N =
      param.paramName

    def fromParams[PI <: ParamInfo.Of[N]](params: List[PI], resultType: Type)(implicit ctx: Context): Type =
      if (params.isEmpty) resultType
      else apply(params.map(paramName))(
        tl => params.map(param => tl.integrate(params, param.paramInfo).asInstanceOf[PInfo]),
        tl => tl.integrate(params, resultType))
  }

  abstract class TermLambdaCompanion[LT <: TermLambda]
  extends LambdaTypeCompanion[TermName, Type, LT] {
    def syntheticParamName(n: Int) = nme.syntheticParamName(n)
  }

  abstract class TypeLambdaCompanion[LT <: TypeLambda]
  extends LambdaTypeCompanion[TypeName, TypeBounds, LT] {
    def syntheticParamName(n: Int) = tpnme.syntheticTypeParamName(n)
  }

  abstract class MethodTypeCompanion extends TermLambdaCompanion[MethodType] {

    /** Produce method type from parameter symbols, with special mappings for repeated
     *  and inline parameters:
     *   - replace @repeated annotations on Seq or Array types by <repeated> types
     *   - add @inlineParam to inline call-by-value parameters
     */
    def fromSymbols(params: List[Symbol], resultType: Type)(implicit ctx: Context) = {
      def translateRepeated(tp: Type): Type = tp match {
        case tp @ ExprType(tp1) => tp.derivedExprType(translateRepeated(tp1))
        case AnnotatedType(tp, annot) if annot matches defn.RepeatedAnnot =>
          val typeSym = tp.typeSymbol.asClass
          assert(typeSym == defn.SeqClass || typeSym == defn.ArrayClass)
          tp.translateParameterized(typeSym, defn.RepeatedParamClass)
        case tp =>
          tp
      }
      def translateInline(tp: Type): Type = tp match {
        case _: ExprType => tp
        case _ => AnnotatedType(tp, Annotation(defn.InlineParamAnnot))
      }
      def paramInfo(param: Symbol) = {
        val paramType = translateRepeated(param.info)
        if (param.is(Inline)) translateInline(paramType) else paramType
      }

      apply(params.map(_.name.asTermName))(
         tl => params.map(p => tl.integrate(params, paramInfo(p))),
         tl => tl.integrate(params, resultType))
    }

    def checkValid(mt: MethodType)(implicit ctx: Context): mt.type = {
      if (Config.checkMethodTypes)
        for ((paramInfo, idx) <- mt.paramInfos.zipWithIndex)
          paramInfo.foreachPart {
            case TermParamRef(`mt`, j) => assert(j < idx, mt)
            case _ =>
          }
      mt
    }
  }

  object MethodType extends MethodTypeCompanion {
    def apply(paramNames: List[TermName])(paramInfosExp: MethodType => List[Type], resultTypeExp: MethodType => Type)(implicit ctx: Context): MethodType =
      checkValid(unique(new CachedMethodType(paramNames)(paramInfosExp, resultTypeExp)))
  }

  object JavaMethodType extends MethodTypeCompanion {
    def apply(paramNames: List[TermName])(paramInfosExp: MethodType => List[Type], resultTypeExp: MethodType => Type)(implicit ctx: Context): MethodType =
      unique(new JavaMethodType(paramNames)(paramInfosExp, resultTypeExp))
  }

  object ImplicitMethodType extends MethodTypeCompanion {
    def apply(paramNames: List[TermName])(paramInfosExp: MethodType => List[Type], resultTypeExp: MethodType => Type)(implicit ctx: Context): MethodType =
      checkValid(unique(new ImplicitMethodType(paramNames)(paramInfosExp, resultTypeExp)))
  }

  /** A ternary extractor for MethodType */
  object MethodTpe {
    def unapply(mt: MethodType)(implicit ctx: Context) =
      Some((mt.paramNames, mt.paramInfos, mt.resultType))
  }

  trait TypeLambda extends LambdaType {
    type ThisName = TypeName
    type PInfo = TypeBounds
    type This <: TypeLambda

    def isDependent(implicit ctx: Context): Boolean = true
    def isParamDependent(implicit ctx: Context): Boolean = true

    def newParamRef(n: Int) = TypeParamRef(this, n)

    lazy val typeParams: List[LambdaParam] =
      paramNames.indices.toList.map(new LambdaParam(this, _))

    /** Instantiate parameter bounds by substituting parameters with given arguments */
    final def instantiateBounds(argTypes: List[Type])(implicit ctx: Context): List[Type] =
      paramInfos.mapConserve(_.substParams(this, argTypes))

    def derivedLambdaAbstraction(paramNames: List[TypeName], paramInfos: List[TypeBounds], resType: Type)(implicit ctx: Context): Type =
      resType match {
        case resType @ TypeAlias(alias) =>
          resType.derivedTypeAlias(newLikeThis(paramNames, paramInfos, alias))
        case resType @ TypeBounds(lo, hi) =>
          resType.derivedTypeBounds(
            if (lo.isRef(defn.NothingClass)) lo else newLikeThis(paramNames, paramInfos, lo),
            newLikeThis(paramNames, paramInfos, hi))
        case _ =>
          derivedLambdaType(paramNames, paramInfos, resType)
      }
  }

  /** A type lambda of the form `[X_0 B_0, ..., X_n B_n] => T`
   *  Variances are encoded in parameter names. A name starting with `+`
   *  designates a covariant parameter, a name starting with `-` designates
   *  a contravariant parameter, and every other name designates a non-variant parameter.
   *
   *  @param  paramNames      The names `X_0`, ..., `X_n`
   *  @param  paramInfosExp  A function that, given the polytype itself, returns the
   *                          parameter bounds `B_1`, ..., `B_n`
   *  @param  resultTypeExp   A function that, given the polytype itself, returns the
   *                          result type `T`.
   */
  class HKTypeLambda(val paramNames: List[TypeName])(
      paramInfosExp: HKTypeLambda => List[TypeBounds], resultTypeExp: HKTypeLambda => Type)
  extends HKLambda with TypeLambda {
    type This = HKTypeLambda
    def companion = HKTypeLambda

    val paramInfos: List[TypeBounds] = paramInfosExp(this)
    val resType: Type = resultTypeExp(this)

    assert(resType.isInstanceOf[TermType], this)
    assert(paramNames.nonEmpty)

    protected def prefixString = "HKTypeLambda"
  }

  /** The type of a polymorphic method. It has the same form as HKTypeLambda,
   *  except it applies to terms and parameters do not have variances.
   */
  class PolyType(val paramNames: List[TypeName])(
      paramInfosExp: PolyType => List[TypeBounds], resultTypeExp: PolyType => Type)
  extends MethodOrPoly with TypeLambda {

    type This = PolyType
    def companion = PolyType

    val paramInfos: List[TypeBounds] = paramInfosExp(this)
    val resType: Type = resultTypeExp(this)

    assert(resType.isInstanceOf[TermType], this)
    assert(paramNames.nonEmpty)

    /** Merge nested polytypes into one polytype. nested polytypes are normally not supported
     *  but can arise as temporary data structures.
     */
    def flatten(implicit ctx: Context): PolyType = resType match {
      case that: PolyType =>
        val shift = new TypeMap {
          def apply(t: Type) = t match {
            case TypeParamRef(`that`, n) => TypeParamRef(that, n + paramNames.length)
            case t => mapOver(t)
          }
        }
        PolyType(paramNames ++ that.paramNames)(
          x => this.paramInfos.mapConserve(_.subst(this, x).bounds) ++
               that.paramInfos.mapConserve(shift(_).subst(that, x).bounds),
          x => shift(that.resultType).subst(that, x).subst(this, x))
      case _ => this
    }

    protected def prefixString = "PolyType"
  }

  object HKTypeLambda extends TypeLambdaCompanion[HKTypeLambda] {
    def apply(paramNames: List[TypeName])(
        paramInfosExp: HKTypeLambda => List[TypeBounds],
        resultTypeExp: HKTypeLambda => Type)(implicit ctx: Context): HKTypeLambda = {
      unique(new HKTypeLambda(paramNames)(paramInfosExp, resultTypeExp))
    }

    def unapply(tl: HKTypeLambda): Some[(List[LambdaParam], Type)] =
      Some((tl.typeParams, tl.resType))

    def any(n: Int)(implicit ctx: Context) =
      apply(syntheticParamNames(n))(
        pt => List.fill(n)(TypeBounds.empty), pt => defn.AnyType)

    override def paramName(param: ParamInfo.Of[TypeName])(implicit ctx: Context): TypeName =
      param.paramName.withVariance(param.paramVariance)

    /** Distributes Lambda inside type bounds. Examples:
  	 *
   	 *      type T[X] = U        becomes    type T = [X] -> U
   	 *      type T[X] <: U       becomes    type T >: Nothign <: ([X] -> U)
     *      type T[X] >: L <: U  becomes    type T >: ([X] -> L) <: ([X] -> U)
     */
    override def fromParams[PI <: ParamInfo.Of[TypeName]](params: List[PI], resultType: Type)(implicit ctx: Context): Type = {
      def expand(tp: Type) = super.fromParams(params, tp)
      resultType match {
        case rt: TypeAlias =>
          rt.derivedTypeAlias(expand(rt.alias))
        case rt @ TypeBounds(lo, hi) =>
          rt.derivedTypeBounds(
            if (lo.isRef(defn.NothingClass)) lo else expand(lo), expand(hi))
        case rt =>
          expand(rt)
      }
    }
  }

  object PolyType extends TypeLambdaCompanion[PolyType] {
    def apply(paramNames: List[TypeName])(
        paramInfosExp: PolyType => List[TypeBounds],
        resultTypeExp: PolyType => Type)(implicit ctx: Context): PolyType = {
      unique(new PolyType(paramNames)(paramInfosExp, resultTypeExp))
    }

    def unapply(tl: PolyType): Some[(List[LambdaParam], Type)] =
      Some((tl.typeParams, tl.resType))

    def any(n: Int)(implicit ctx: Context) =
      apply(syntheticParamNames(n))(
        pt => List.fill(n)(TypeBounds.empty), pt => defn.AnyType)
  }

  private object DepStatus {
    type DependencyStatus = Byte
    final val Unknown: DependencyStatus = 0   // not yet computed
    final val NoDeps: DependencyStatus = 1    // no dependent parameters found
    final val FalseDeps: DependencyStatus = 2 // all dependent parameters are prefixes of non-depended alias types
    final val TrueDeps: DependencyStatus = 3  // some truly dependent parameters exist
    final val StatusMask: DependencyStatus = 3 // the bits indicating actual dependency status
    final val Provisional: DependencyStatus = 4  // set if dependency status can still change due to type variable instantiations
  }

  // ----- HK types: LambdaParam, HKApply ---------------------

  /** The parameter of a type lambda */
  case class LambdaParam(tl: TypeLambda, n: Int) extends ParamInfo {
    type ThisName = TypeName
    def isTypeParam(implicit ctx: Context) = tl.paramNames.head.isTypeName
    def paramName(implicit ctx: Context) = tl.paramNames(n)
    def paramInfo(implicit ctx: Context) = tl.paramInfos(n)
    def paramInfoAsSeenFrom(pre: Type)(implicit ctx: Context) = paramInfo
    def paramInfoOrCompleter(implicit ctx: Context): Type = paramInfo
    def paramVariance(implicit ctx: Context): Int = tl.paramNames(n).variance
    def toArg: Type = TypeParamRef(tl, n)
    def paramRef(implicit ctx: Context): Type = TypeParamRef(tl, n)
  }

  /** A higher kinded type application `C[T_1, ..., T_n]` */
  abstract case class HKApply(tycon: Type, args: List[Type])
  extends CachedProxyType with ValueType {

    private var validSuper: Period = Nowhere
    private var cachedSuper: Type = _

    override def underlying(implicit ctx: Context): Type = tycon

    override def superType(implicit ctx: Context): Type = {
      if (ctx.period != validSuper) {
        cachedSuper = tycon match {
          case tp: HKTypeLambda => defn.AnyType
          case tp: TypeVar if !tp.inst.exists =>
            // supertype not stable, since underlying might change
            return tp.underlying.applyIfParameterized(args)
          case tp: TypeProxy => tp.superType.applyIfParameterized(args)
          case _ => defn.AnyType
        }
        validSuper = ctx.period
      }
      cachedSuper
    }

    def lowerBound(implicit ctx: Context) = tycon.stripTypeVar match {
      case tycon: TypeRef =>
        tycon.info match {
          case TypeBounds(lo, hi) =>
            if (lo eq hi) superType // optimization, can profit from caching in this case
            else lo.applyIfParameterized(args)
          case _ => NoType
        }
      case _ =>
        NoType
    }

    def typeParams(implicit ctx: Context): List[ParamInfo] = {
      val tparams = tycon.typeParams
      if (tparams.isEmpty) HKTypeLambda.any(args.length).typeParams else tparams
    }

    def derivedAppliedType(tycon: Type, args: List[Type])(implicit ctx: Context): Type =
      if ((tycon eq this.tycon) && (args eq this.args)) this
      else tycon.appliedTo(args)

    override def computeHash = doHash(tycon, args)

    protected def checkInst(implicit ctx: Context): this.type = {
      def check(tycon: Type): Unit = tycon.stripTypeVar match {
        case tycon: TypeRef if !tycon.symbol.isClass =>
        case _: TypeParamRef | _: ErrorType | _: WildcardType =>
        case _: TypeLambda =>
          assert(args.exists(_.isInstanceOf[TypeBounds]), s"unreduced type apply: $this")
        case tycon: AnnotatedType =>
          check(tycon.underlying)
        case _ =>
          assert(false, s"illegal type constructor in $this")
      }
      if (Config.checkHKApplications) check(tycon)
      this
    }
  }

  final class CachedHKApply(tycon: Type, args: List[Type]) extends HKApply(tycon, args)

  object HKApply {
    def apply(tycon: Type, args: List[Type])(implicit ctx: Context) =
      unique(new CachedHKApply(tycon, args)).checkInst
  }

  // ----- BoundTypes: ParamRef, RecThis ----------------------------------------

  abstract class BoundType extends CachedProxyType with ValueType {
    type BT <: Type
    val binder: BT
    def copyBoundType(bt: BT): Type
  }

  abstract class ParamRef extends BoundType {
    type BT <: LambdaType
    def paramNum: Int
    def paramName: binder.ThisName = binder.paramNames(paramNum)

    override def underlying(implicit ctx: Context): Type = {
      val infos = binder.paramInfos
      if (infos == null) NoType // this can happen if the referenced generic type is not initialized yet
      else infos(paramNum)
    }

    override def computeHash = doHash(paramNum, binder.identityHash)
    override def equals(that: Any) = that match {
      case that: ParamRef =>
        (this.binder eq that.binder) && this.paramNum == that.paramNum
      case _ =>
        false
    }

    override def toString =
      try s"ParamRef($paramName)"
      catch {
        case ex: IndexOutOfBoundsException => s"ParamRef(<bad index: $paramNum>)"
      }
  }

  case class TermParamRef(binder: TermLambda, paramNum: Int) extends ParamRef {
    type BT = TermLambda
    def copyBoundType(bt: BT) = TermParamRef(bt, paramNum)
  }

  case class TypeParamRef(binder: TypeLambda, paramNum: Int) extends ParamRef {
    type BT = TypeLambda
    def copyBoundType(bt: BT) = TypeParamRef(bt, paramNum)

    /** Looking only at the structure of `bound`, is one of the following true?
     *     - fromBelow and param <:< bound
     *     - !fromBelow and param >:> bound
     */
    def occursIn(bound: Type, fromBelow: Boolean)(implicit ctx: Context): Boolean = bound.stripTypeVar match {
      case bound: ParamRef => bound == this
      case bound: AndOrType =>
        def occ1 = occursIn(bound.tp1, fromBelow)
        def occ2 = occursIn(bound.tp2, fromBelow)
        if (fromBelow == bound.isAnd) occ1 && occ2 else occ1 || occ2
      case _ => false
    }
  }

  /** a self-reference to an enclosing recursive type. */
  case class RecThis(binder: RecType) extends BoundType with SingletonType {
    type BT = RecType
    override def underlying(implicit ctx: Context) = binder
    def copyBoundType(bt: BT) = RecThis(bt)

    // need to customize hashCode and equals to prevent infinite recursion
    // between RecTypes and RecRefs.
    override def computeHash = addDelta(binder.identityHash, 41)
    override def equals(that: Any) = that match {
      case that: RecThis => this.binder eq that.binder
      case _ => false
    }
    override def toString =
      try s"RecThis(${binder.hashCode})"
      catch {
        case ex: NullPointerException => s"RecThis(<under construction>)"
      }
  }

  // ----- Skolem types -----------------------------------------------

  /** A skolem type reference with underlying type `binder`. */
  case class SkolemType(info: Type) extends UncachedProxyType with ValueType with SingletonType {
    override def underlying(implicit ctx: Context) = info
    def derivedSkolemType(info: Type)(implicit ctx: Context) =
      if (info eq this.info) this else SkolemType(info)
    override def hashCode: Int = identityHash
    override def equals(that: Any) = this eq that.asInstanceOf[AnyRef]

    private var myRepr: Name = null
    def repr(implicit ctx: Context): Name = {
      if (myRepr == null) myRepr = SkolemName.fresh()
      myRepr
    }

    override def toString = s"Skolem($hashCode)"
  }

  // ------------ Type variables ----------------------------------------

  /** In a TypeApply tree, a TypeVar is created for each argument type to be inferred.
   *  Every type variable is referred to by exactly one inferred type parameter of some
   *  TypeApply tree.
   *
   *  A type variable is essentially a switch that models some part of a substitution.
   *  It is first linked to `origin`, a poly param that's in the current constraint set.
   *  It can then be (once) instantiated to some other type. The instantiation is
   *  recorded in the type variable itself, or else, if the current type state
   *  is different from the variable's creation state (meaning unrolls are possible)
   *  in the current typer state.
   *
   *  @param  origin        The parameter that's tracked by the type variable.
   *  @param  creatorState  The typer state in which the variable was created.
   *  @param  bindingTree   The TypeTree which introduces the type variable, or EmptyTree
   *                        if the type variable does not correspond to a source term.
   *  @paran  owner         The current owner if the context where the variable was created.
   *
   *  `owningTree` and `owner` are used to determine whether a type-variable can be instantiated
   *  at some given point. See `Inferencing#interpolateUndetVars`.
   */
  final class TypeVar(val origin: TypeParamRef, creatorState: TyperState, val bindingTree: untpd.Tree, val owner: Symbol) extends CachedProxyType with ValueType {

    /** The permanent instance type of the variable, or NoType is none is given yet */
    private[core] var inst: Type = NoType

    /** The state owning the variable. This is at first `creatorState`, but it can
     *  be changed to an enclosing state on a commit.
     */
    private[core] var owningState = creatorState

    /** The instance type of this variable, or NoType if the variable is currently
     *  uninstantiated
     */
    def instanceOpt(implicit ctx: Context): Type =
      if (inst.exists) inst else {
        ctx.typerState.ephemeral = true
        ctx.typerState.instType(this)
      }

    /** Is the variable already instantiated? */
    def isInstantiated(implicit ctx: Context) = instanceOpt.exists

    /** Instantiate variable with given type */
    private def instantiateWith(tp: Type)(implicit ctx: Context): Type = {
      assert(tp ne this, s"self instantiation of ${tp.show}, constraint = ${ctx.typerState.constraint.show}")
      typr.println(s"instantiating ${this.show} with ${tp.show}")
      assert(ctx.typerState.constraint contains this) // !!! DEBUG
      if ((ctx.typerState eq owningState) && !ctx.typeComparer.subtypeCheckInProgress)
        inst = tp
      ctx.typerState.constraint = ctx.typerState.constraint.replace(origin, tp)
      tp
    }

    /** Instantiate variable from the constraints over its `origin`.
     *  If `fromBelow` is true, the variable is instantiated to the lub
     *  of its lower bounds in the current constraint; otherwise it is
     *  instantiated to the glb of its upper bounds. However, a lower bound
     *  instantiation can be a singleton type only if the upper bound
     *  is also a singleton type.
     */
    def instantiate(fromBelow: Boolean)(implicit ctx: Context): Type =
      instantiateWith(ctx.typeComparer.instanceType(origin, fromBelow))

    /** Unwrap to instance (if instantiated) or origin (if not), until result
     *  is no longer a TypeVar
     */
    override def stripTypeVar(implicit ctx: Context): Type = {
      val inst = instanceOpt
      if (inst.exists) inst.stripTypeVar else origin
    }

    /** If the variable is instantiated, its instance, otherwise its origin */
    override def underlying(implicit ctx: Context): Type = {
      val inst = instanceOpt
      if (inst.exists) inst
      else {
        ctx.typerState.ephemeral = true
        origin
      }
    }

    override def computeHash: Int = identityHash
    override def equals(that: Any) = this eq that.asInstanceOf[AnyRef]

    override def toString = {
      def instStr = if (inst.exists) s" -> $inst" else ""
      s"TypeVar($origin$instStr)"
    }
  }

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

  /** Roughly: the info of a class during a period.
   *  @param prefix       The prefix on which parents, decls, and selfType need to be rebased.
   *  @param cls          The class symbol.
   *  @param classParents The parent types of this class.
   *                      These are all normalized to be TypeRefs by moving any refinements
   *                      to be member definitions of the class itself.
   *  @param decls        The symbols defined directly in this class.
   *  @param selfInfo     The type of `this` in this class, if explicitly given,
   *                      NoType otherwise. If class is compiled from source, can also
   *                      be a reference to the self symbol containing the type.
   */
  abstract case class ClassInfo(
      prefix: Type,
      cls: ClassSymbol,
      classParents: List[TypeRef],
      decls: Scope,
      selfInfo: DotClass /* should be: Type | Symbol */) extends CachedGroundType with TypeType {

    /** The self type of a class is the conjunction of
     *   - the explicit self type if given (or the info of a given self symbol), and
     *   - the fully applied reference to the class itself.
     */
    def selfType(implicit ctx: Context): Type = {
      if (selfTypeCache == null)
        selfTypeCache = {
          def fullRef = fullyAppliedRef
          val given = givenSelfType
          val raw =
            if (!given.exists) fullRef
            else if (cls is Module) given
            else if (ctx.erasedTypes) fullRef
            else AndType(given, fullRef)
          raw//.asSeenFrom(prefix, cls.owner)
        }
      selfTypeCache
    }

    /** The explicitly given self type (self types of modules are assumed to be
     *  explcitly given here).
     */
    override def givenSelfType(implicit ctx: Context): Type = selfInfo match {
      case tp: Type => tp
      case self: Symbol => self.info
    }

    private var selfTypeCache: Type = null

    private def fullyAppliedRef(base: Type, tparams: List[TypeSymbol])(implicit ctx: Context): Type = tparams match {
      case tparam :: tparams1 =>
        fullyAppliedRef(
          RefinedType(base, tparam.name, TypeRef(cls.thisType, tparam).toBounds(tparam)),
          tparams1)
      case nil =>
        base
    }

    /** The class type with all type parameters */
    def fullyAppliedRef(implicit ctx: Context): Type = fullyAppliedRef(cls.typeRef, cls.typeParams)

    private var typeRefCache: TypeRef = null

    def typeRef(implicit ctx: Context): TypeRef = {
      def clsDenot = if (prefix eq cls.owner.thisType) cls.denot else cls.denot.copySymDenotation(info = this)
      if (typeRefCache == null)
        typeRefCache =
          if ((cls is PackageClass) || cls.owner.isTerm) symbolicTypeRef
          else TypeRef(prefix, cls.name, clsDenot)
      typeRefCache
    }

    def symbolicTypeRef(implicit ctx: Context): TypeRef = TypeRef(prefix, cls)

    // cached because baseType needs parents
    private var parentsCache: List[TypeRef] = null

    /** The parent type refs as seen from the given prefix */
    override def parents(implicit ctx: Context): List[TypeRef] = {
      if (parentsCache == null)
        parentsCache = cls.classParents.mapConserve(_.asSeenFrom(prefix, cls.owner).asInstanceOf[TypeRef])
      parentsCache
    }

    /** The parent types with all type arguments */
    override def parentsWithArgs(implicit ctx: Context): List[Type] =
      parents mapConserve { pref =>
        ((pref: Type) /: pref.classSymbol.typeParams) { (parent, tparam) =>
          val targSym = decls.lookup(tparam.name)
          if (targSym.exists) RefinedType(parent, targSym.name, targSym.info)
          else parent
        }
      }

    def derivedClassInfo(prefix: Type)(implicit ctx: Context) =
      if (prefix eq this.prefix) this
      else ClassInfo(prefix, cls, classParents, decls, selfInfo)

    def derivedClassInfo(prefix: Type = this.prefix, classParents: List[TypeRef] = classParents, decls: Scope = this.decls, selfInfo: DotClass = this.selfInfo)(implicit ctx: Context) =
      if ((prefix eq this.prefix) && (classParents eq this.classParents) && (decls eq this.decls) && (selfInfo eq this.selfInfo)) this
      else ClassInfo(prefix, cls, classParents, decls, selfInfo)

    override def computeHash = doHash(cls, prefix)

    override def toString = s"ClassInfo($prefix, $cls)"
  }

  class CachedClassInfo(prefix: Type, cls: ClassSymbol, classParents: List[TypeRef], decls: Scope, selfInfo: DotClass)
    extends ClassInfo(prefix, cls, classParents, decls, selfInfo)

  /** A class for temporary class infos where `parents` are not yet known. */
  final class TempClassInfo(prefix: Type, cls: ClassSymbol, decls: Scope, selfInfo: DotClass)
  extends CachedClassInfo(prefix, cls, Nil, decls, selfInfo) {

    /** A list of actions that were because they rely on the class info of `cls` to
     *  be no longer temporary. These actions will be performed once `cls` gets a real
     *  ClassInfo.
     */
    private var suspensions: List[Context => Unit] = Nil

    def addSuspension(suspension: Context => Unit): Unit = suspensions ::= suspension

    /** Install classinfo with known parents in `denot` and resume all suspensions */
    def finalize(denot: SymDenotation, parents: List[TypeRef])(implicit ctx: Context) = {
      denot.info = derivedClassInfo(classParents = parents)
      suspensions.foreach(_(ctx))
    }
  }

  object ClassInfo {
    def apply(prefix: Type, cls: ClassSymbol, classParents: List[TypeRef], decls: Scope, selfInfo: DotClass = NoType)(implicit ctx: Context) =
      unique(new CachedClassInfo(prefix, cls, classParents, decls, selfInfo))
  }

  /** Type bounds >: lo <: hi */
  abstract case class TypeBounds(lo: Type, hi: Type) extends CachedProxyType with TypeType {

    assert(lo.isInstanceOf[TermType])
    assert(hi.isInstanceOf[TermType])

    def variance: Int = 0

    override def underlying(implicit ctx: Context): Type = hi

    /** The non-alias type bounds type with given bounds */
    def derivedTypeBounds(lo: Type, hi: Type)(implicit ctx: Context) =
      if ((lo eq this.lo) && (hi eq this.hi) && (variance == 0)) this
      else TypeBounds(lo, hi)

    /** If this is an alias, a derived alias with the new variance,
     *  Otherwise the type itself.
     */
    def withVariance(variance: Int)(implicit ctx: Context) = this match {
      case tp: TypeAlias => tp.derivedTypeAlias(tp.alias, variance)
      case _ => this
    }

    def contains(tp: Type)(implicit ctx: Context): Boolean = tp match {
      case tp: TypeBounds => lo <:< tp.lo && tp.hi <:< hi
      case tp: ClassInfo =>
        // Note: Taking a normal typeRef does not work here. A normal ref might contain
        // also other information about the named type (e.g. bounds).
        contains(tp.symbolicTypeRef)
      case _ => lo <:< tp && tp <:< hi
    }

    def & (that: TypeBounds)(implicit ctx: Context): TypeBounds =
      if ((this.lo frozen_<:< that.lo) && (that.hi frozen_<:< this.hi)) that
      else if ((that.lo frozen_<:< this.lo) && (this.hi frozen_<:< that.hi)) this
      else TypeBounds(this.lo | that.lo, this.hi & that.hi)

    def | (that: TypeBounds)(implicit ctx: Context): TypeBounds =
      if ((this.lo frozen_<:< that.lo) && (that.hi frozen_<:< this.hi)) this
      else if ((that.lo frozen_<:< this.lo) && (this.hi frozen_<:< that.hi)) that
      else TypeBounds(this.lo & that.lo, this.hi | that.hi)

    override def & (that: Type)(implicit ctx: Context) = that match {
      case that: TypeBounds => this & that
      case _ => super.& (that)
    }

    override def | (that: Type)(implicit ctx: Context) = that match {
      case that: TypeBounds => this | that
      case _ => super.| (that)
    }

    /** The implied bounds, where aliases are mapped to intervals from
     *  Nothing/Any
     */
    def boundsInterval(implicit ctx: Context): TypeBounds = this

    /** If this type and that type have the same variance, this variance, otherwise 0 */
    final def commonVariance(that: TypeBounds): Int = (this.variance + that.variance) / 2

    override def computeHash = doHash(variance, lo, hi)
    override def equals(that: Any): Boolean = that match {
      case that: TypeBounds =>
        (this.lo eq that.lo) && (this.hi eq that.hi) && (this.variance == that.variance)
      case _ =>
        false
    }

    override def toString =
      if (lo eq hi) s"TypeAlias($lo, $variance)" else s"TypeBounds($lo, $hi)"
  }

  class RealTypeBounds(lo: Type, hi: Type) extends TypeBounds(lo, hi)

  abstract class TypeAlias(val alias: Type, override val variance: Int) extends TypeBounds(alias, alias) {
    /** pre: this is a type alias */
    def derivedTypeAlias(alias: Type, variance: Int = this.variance)(implicit ctx: Context) =
      if ((alias eq this.alias) && (variance == this.variance)) this
      else TypeAlias(alias, variance)

    override def & (that: TypeBounds)(implicit ctx: Context): TypeBounds = {
      val v = this commonVariance that
      if (v > 0) derivedTypeAlias(this.hi & that.hi, v)
      else if (v < 0) derivedTypeAlias(this.lo | that.lo, v)
      else super.& (that)
    }

    override def | (that: TypeBounds)(implicit ctx: Context): TypeBounds = {
      val v = this commonVariance that
      if (v > 0) derivedTypeAlias(this.hi | that.hi, v)
      else if (v < 0) derivedTypeAlias(this.lo & that.lo, v)
      else super.| (that)
    }

    override def boundsInterval(implicit ctx: Context): TypeBounds =
      if (variance == 0) this
      else if (variance < 0) TypeBounds.lower(alias)
      else TypeBounds.upper(alias)
  }

  class CachedTypeAlias(alias: Type, variance: Int, hc: Int) extends TypeAlias(alias, variance) {
    myHash = hc
  }

  object TypeBounds {
    def apply(lo: Type, hi: Type)(implicit ctx: Context): TypeBounds =
      unique(new RealTypeBounds(lo, hi))
    def empty(implicit ctx: Context) = apply(defn.NothingType, defn.AnyType)
    def upper(hi: Type)(implicit ctx: Context) = apply(defn.NothingType, hi)
    def lower(lo: Type)(implicit ctx: Context) = apply(lo, defn.AnyType)
  }

  object TypeAlias {
    def apply(alias: Type, variance: Int = 0)(implicit ctx: Context) =
      ctx.uniqueTypeAliases.enterIfNew(alias, variance)
    def unapply(tp: TypeAlias): Option[Type] = Some(tp.alias)
  }

  // ----- Annotated and Import types -----------------------------------------------

  /** An annotated type tpe @ annot */
  case class AnnotatedType(tpe: Type, annot: Annotation)
      extends UncachedProxyType with ValueType {
    // todo: cache them? but this makes only sense if annotations and trees are also cached.
    override def underlying(implicit ctx: Context): Type = tpe
    def derivedAnnotatedType(tpe: Type, annot: Annotation) =
      if ((tpe eq this.tpe) && (annot eq this.annot)) this
      else AnnotatedType(tpe, annot)

    override def stripTypeVar(implicit ctx: Context): Type =
      derivedAnnotatedType(tpe.stripTypeVar, annot)
    override def stripAnnots(implicit ctx: Context): Type = tpe.stripAnnots
  }

  object AnnotatedType {
    def make(underlying: Type, annots: List[Annotation]) =
      (underlying /: annots)(AnnotatedType(_, _))
  }

  // Special type objects and classes -----------------------------------------------------

  /** The type of an erased array */
  abstract case class JavaArrayType(elemType: Type) extends CachedGroundType with ValueType {
    override def computeHash = doHash(elemType)
    def derivedJavaArrayType(elemtp: Type)(implicit ctx: Context) =
      if (elemtp eq this.elemType) this else JavaArrayType(elemtp)
  }
  final class CachedJavaArrayType(elemType: Type) extends JavaArrayType(elemType)
  object JavaArrayType {
    def apply(elemType: Type)(implicit ctx: Context) = unique(new CachedJavaArrayType(elemType))
  }

  /** The type of an import clause tree */
  case class ImportType(expr: Tree) extends UncachedGroundType

  /** Sentinel for "missing type" */
  @sharable case object NoType extends CachedGroundType {
    override def exists = false
    override def computeHash = hashSeed
  }

  /** Missing prefix */
  @sharable case object NoPrefix extends CachedGroundType {
    override def computeHash = hashSeed
  }

  /** A common superclass of `ErrorType` and `TryDynamicCallSite`. Instances of this
   *  class are at the same time subtypes and supertypes of every other type.
   */
  abstract class FlexType extends UncachedGroundType with ValueType

  class ErrorType(_msg: => Message) extends FlexType {
    val msg = _msg
  }

  object UnspecifiedErrorType extends ErrorType("unspecified error")

  /* Type used to track Select nodes that could not resolve a member and their qualifier is a scala.Dynamic. */
  object TryDynamicCallType extends FlexType

  /** Wildcard type, possibly with bounds */
  abstract case class WildcardType(optBounds: Type) extends CachedGroundType with TermType {
    def derivedWildcardType(optBounds: Type)(implicit ctx: Context) =
      if (optBounds eq this.optBounds) this
      else if (!optBounds.exists) WildcardType
      else WildcardType(optBounds.asInstanceOf[TypeBounds])
    override def computeHash = doHash(optBounds)
  }

  final class CachedWildcardType(optBounds: Type) extends WildcardType(optBounds)

  @sharable object WildcardType extends WildcardType(NoType) {
    def apply(bounds: TypeBounds)(implicit ctx: Context) = unique(new CachedWildcardType(bounds))
  }

  /** An extractor for single abstract method types.
   *  A type is a SAM type if it is a reference to a class or trait, which
   *
   *   - has a single abstract method with a method type (ExprType
   *     and PolyType not allowed!)
   *   - can be instantiated without arguments or with just () as argument.
   *
   *  The pattern `SAMType(denot)` matches a SAM type, where `denot` is the
   *  denotation of the single abstract method as a member of the type.
   */
  object SAMType {
    def zeroParamClass(tp: Type)(implicit ctx: Context): Type = tp match {
      case tp: ClassInfo =>
        def zeroParams(tp: Type): Boolean = tp.stripPoly match {
          case mt: MethodType => mt.paramInfos.isEmpty && !mt.resultType.isInstanceOf[MethodType]
          case et: ExprType => true
          case _ => false
        }
        if ((tp.cls is Trait) || zeroParams(tp.cls.primaryConstructor.info)) tp // !!! needs to be adapted once traits have parameters
        else NoType
      case tp: TypeRef =>
        zeroParamClass(tp.underlying)
      case tp: RefinedType =>
        zeroParamClass(tp.underlying)
      case tp: TypeBounds =>
        zeroParamClass(tp.underlying)
      case tp: TypeVar =>
        zeroParamClass(tp.underlying)
      case tp: HKApply =>
        zeroParamClass(tp.superType)
      case _ =>
        NoType
    }
    def isInstantiatable(tp: Type)(implicit ctx: Context): Boolean = zeroParamClass(tp) match {
      case cinfo: ClassInfo =>
        val tref = tp.narrow
        val selfType = cinfo.selfType.asSeenFrom(tref, cinfo.cls)
        tref <:< selfType
      case _ =>
        false
    }
    def unapply(tp: Type)(implicit ctx: Context): Option[SingleDenotation] =
      if (isInstantiatable(tp)) {
        val absMems = tp.abstractTermMembers
        // println(s"absMems: ${absMems map (_.show) mkString ", "}")
        if (absMems.size == 1)
          absMems.head.info match {
            case mt: MethodType if !mt.isDependent => Some(absMems.head)
            case _ => None
          }
        else if (tp isRef defn.PartialFunctionClass)
          // To maintain compatibility with 2.x, we treat PartialFunction specially,
          // pretending it is a SAM type. In the future it would be better to merge
          // Function and PartialFunction, have Function1 contain a isDefinedAt method
          //     def isDefinedAt(x: T) = true
          // and overwrite that method whenever the function body is a sequence of
          // case clauses.
          absMems.find(_.symbol.name == nme.apply)
        else None
      }
      else None
  }

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

  abstract class TypeMap(implicit protected val ctx: Context) extends (Type => Type) { thisMap =>

    protected def stopAtStatic = true

    def apply(tp: Type): Type

    protected[core] var variance = 1

    protected def derivedSelect(tp: NamedType, pre: Type): Type =
      tp.derivedSelect(pre)
    protected def derivedRefinedType(tp: RefinedType, parent: Type, info: Type): Type =
      tp.derivedRefinedType(parent, tp.refinedName, info)
    protected def derivedRecType(tp: RecType, parent: Type): Type =
      tp.rebind(parent)
    protected def derivedTypeAlias(tp: TypeAlias, alias: Type): Type =
      tp.derivedTypeAlias(alias)
    protected def derivedTypeBounds(tp: TypeBounds, lo: Type, hi: Type): Type =
      tp.derivedTypeBounds(lo, hi)
    protected def derivedSuperType(tp: SuperType, thistp: Type, supertp: Type): Type =
      tp.derivedSuperType(thistp, supertp)
    protected def derivedAppliedType(tp: HKApply, tycon: Type, args: List[Type]): Type =
      tp.derivedAppliedType(tycon, args)
    protected def derivedAndOrType(tp: AndOrType, tp1: Type, tp2: Type): Type =
      tp.derivedAndOrType(tp1, tp2)
    protected def derivedAnnotatedType(tp: AnnotatedType, underlying: Type, annot: Annotation): Type =
      tp.derivedAnnotatedType(underlying, annot)
    protected def derivedWildcardType(tp: WildcardType, bounds: Type): Type =
      tp.derivedWildcardType(bounds)
    protected def derivedClassInfo(tp: ClassInfo, pre: Type): Type =
      tp.derivedClassInfo(pre)
    protected def derivedJavaArrayType(tp: JavaArrayType, elemtp: Type): Type =
      tp.derivedJavaArrayType(elemtp)
    protected def derivedExprType(tp: ExprType, restpe: Type): Type =
      tp.derivedExprType(restpe)
    // note: currying needed  because Scala2 does not support param-dependencies
    protected def derivedLambdaType(tp: LambdaType)(formals: List[tp.PInfo], restpe: Type): Type =
      tp.derivedLambdaType(tp.paramNames, formals, restpe)

    /** Map this function over given type */
    def mapOver(tp: Type): Type = {
      implicit val ctx = this.ctx
      tp match {
        case tp: NamedType =>
          if (stopAtStatic && tp.symbol.isStatic) tp
          else derivedSelect(tp, this(tp.prefix))

        case _: ThisType
          | _: BoundType
          | NoPrefix => tp

        case tp: RefinedType =>
          derivedRefinedType(tp, this(tp.parent), this(tp.refinedInfo))

        case tp: TypeAlias =>
          val saved = variance
          variance = variance * tp.variance
          val alias1 = this(tp.alias)
          variance = saved
          derivedTypeAlias(tp, alias1)

        case tp: TypeBounds =>
          variance = -variance
          val lo1 = this(tp.lo)
          variance = -variance
          derivedTypeBounds(tp, lo1, this(tp.hi))

        case tp: RecType =>
          derivedRecType(tp, this(tp.parent))

        case tp: TypeVar =>
          val inst = tp.instanceOpt
          if (inst.exists) apply(inst) else tp

        case tp: HKApply =>
          def mapArg(arg: Type, tparam: ParamInfo): Type = {
            val saved = variance
            variance *= tparam.paramVariance
            try this(arg)
            finally variance = saved
          }
          derivedAppliedType(tp, this(tp.tycon),
              tp.args.zipWithConserve(tp.typeParams)(mapArg))

        case tp: ExprType =>
          derivedExprType(tp, this(tp.resultType))

        case tp: LambdaType =>
          def mapOverLambda = {
            variance = -variance
            val ptypes1 = tp.paramInfos.mapConserve(this).asInstanceOf[List[tp.PInfo]]
            variance = -variance
            derivedLambdaType(tp)(ptypes1, this(tp.resultType))
          }
          mapOverLambda

        case tp @ SuperType(thistp, supertp) =>
          derivedSuperType(tp, this(thistp), this(supertp))

        case tp: LazyRef =>
          LazyRef(() => this(tp.ref))

        case tp: ClassInfo =>
          mapClassInfo(tp)

         case tp: AndOrType =>
          derivedAndOrType(tp, this(tp.tp1), this(tp.tp2))

        case tp: SkolemType =>
          tp

        case tp @ AnnotatedType(underlying, annot) =>
          val underlying1 = this(underlying)
          if (underlying1 eq underlying) tp
          else derivedAnnotatedType(tp, underlying1, mapOver(annot))

        case tp @ WildcardType =>
          derivedWildcardType(tp, mapOver(tp.optBounds))

        case tp: JavaArrayType =>
          derivedJavaArrayType(tp, this(tp.elemType))

        case tp: ProtoType =>
          tp.map(this)

        case _ =>
          tp
      }
    }

    private def treeTypeMap = new TreeTypeMap(typeMap = this)

    def mapOver(syms: List[Symbol]): List[Symbol] = ctx.mapSymbols(syms, treeTypeMap)

    def mapOver(scope: Scope): Scope = {
      val elems = scope.toList
      val elems1 = mapOver(elems)
      if (elems1 eq elems) scope
      else newScopeWith(elems1: _*)
    }

    def mapOver(annot: Annotation): Annotation =
      annot.derivedAnnotation(mapOver(annot.tree))

    def mapOver(tree: Tree): Tree = treeTypeMap(tree)

    /** Can be overridden. By default, only the prefix is mapped. */
    protected def mapClassInfo(tp: ClassInfo): Type =
      derivedClassInfo(tp, this(tp.prefix))

    def andThen(f: Type => Type): TypeMap = new TypeMap {
      override def stopAtStatic = thisMap.stopAtStatic
      def apply(tp: Type) = f(thisMap(tp))
    }
  }

  /** A type map that maps also parents and self type of a ClassInfo */
  abstract class DeepTypeMap(implicit ctx: Context) extends TypeMap {
    override def mapClassInfo(tp: ClassInfo) = {
      val prefix1 = this(tp.prefix)
      val parents1 = (tp.parents mapConserve this).asInstanceOf[List[TypeRef]]
      val selfInfo1 = tp.selfInfo match {
        case selfInfo: Type => this(selfInfo)
        case selfInfo => selfInfo
      }
      tp.derivedClassInfo(prefix1, parents1, tp.decls, selfInfo1)
    }
  }

  @sharable object IdentityTypeMap extends TypeMap()(NoContext) {
    override def stopAtStatic = true
    def apply(tp: Type) = tp
  }

  /** A type map that approximates NoTypes by upper or lower known bounds depending on
   *  variance.
   *
   *  if variance > 0 : approximate by upper bound
   *     variance < 0 : approximate by lower bound
   *     variance = 0 : propagate NoType to next outer level
   */
  abstract class ApproximatingTypeMap(implicit ctx: Context) extends TypeMap { thisMap =>
    def approx(lo: Type = defn.NothingType, hi: Type = defn.AnyType) =
      if (variance == 0) NoType
      else apply(if (variance < 0) lo else hi)

    override protected def derivedSelect(tp: NamedType, pre: Type) =
      if (pre eq tp.prefix) tp
      else tp.info match {
        case TypeAlias(alias) => apply(alias) // try to heal by following aliases
        case _ =>
          if (pre.exists && !pre.isRef(defn.NothingClass) && variance > 0) tp.derivedSelect(pre)
          else tp.info match {
            case TypeBounds(lo, hi) => approx(lo, hi)
            case _ => approx()
          }
      }
    override protected def derivedRefinedType(tp: RefinedType, parent: Type, info: Type) =
      if (parent.exists && info.exists) tp.derivedRefinedType(parent, tp.refinedName, info)
      else approx(hi = parent)
    override protected def derivedRecType(tp: RecType, parent: Type) =
      if (parent.exists) tp.rebind(parent)
      else approx()
    override protected def derivedTypeAlias(tp: TypeAlias, alias: Type) =
      if (alias.exists) tp.derivedTypeAlias(alias)
      else approx(NoType, TypeBounds.empty)
    override protected def derivedTypeBounds(tp: TypeBounds, lo: Type, hi: Type) =
      if (lo.exists && hi.exists) tp.derivedTypeBounds(lo, hi)
      else approx(NoType,
        if (lo.exists) TypeBounds.lower(lo)
        else if (hi.exists) TypeBounds.upper(hi)
        else TypeBounds.empty)
    override protected def derivedSuperType(tp: SuperType, thistp: Type, supertp: Type) =
      if (thistp.exists && supertp.exists) tp.derivedSuperType(thistp, supertp)
      else NoType
    override protected def derivedAppliedType(tp: HKApply, tycon: Type, args: List[Type]): Type =
      if (tycon.exists && args.forall(_.exists)) tp.derivedAppliedType(tycon, args)
      else approx() // This is rather coarse, but to do better is a bit complicated
    override protected def derivedAndOrType(tp: AndOrType, tp1: Type, tp2: Type) =
      if (tp1.exists && tp2.exists) tp.derivedAndOrType(tp1, tp2)
      else if (tp.isAnd) approx(hi = tp1 & tp2)  // if one of tp1d, tp2d exists, it is the result of tp1d & tp2d
      else approx(lo = tp1 & tp2)
    override protected def derivedAnnotatedType(tp: AnnotatedType, underlying: Type, annot: Annotation) =
      if (underlying.exists) tp.derivedAnnotatedType(underlying, annot)
      else NoType
    override protected def derivedWildcardType(tp: WildcardType, bounds: Type) =
      if (bounds.exists) tp.derivedWildcardType(bounds)
      else WildcardType
    override protected def derivedClassInfo(tp: ClassInfo, pre: Type): Type =
      if (pre.exists) tp.derivedClassInfo(pre)
      else NoType
  }

  // ----- TypeAccumulators ----------------------------------------------------

  abstract class TypeAccumulator[T](implicit protected val ctx: Context) extends ((T, Type) => T) {

    protected def stopAtStatic = true

    def apply(x: T, tp: Type): T

    protected def applyToAnnot(x: T, annot: Annotation): T = x // don't go into annotations

    protected var variance = 1

    protected def applyToPrefix(x: T, tp: NamedType) = {
      val saved = variance
      variance = 0
      val result = this(x, tp.prefix)
      variance = saved
      result
    }

    def foldOver(x: T, tp: Type): T = tp match {
      case tp: TypeRef =>
        if (stopAtStatic && tp.symbol.isStatic) x
        else {
          val tp1 = tp.prefix.lookupRefined(tp.name)
          if (tp1.exists) this(x, tp1) else applyToPrefix(x, tp)
        }
      case tp: TermRef =>
        if (stopAtStatic && tp.currentSymbol.isStatic) x
        else applyToPrefix(x, tp)

      case _: ThisType
         | _: BoundType
         | NoPrefix => x

      case tp: RefinedType =>
        this(this(x, tp.parent), tp.refinedInfo)

      case bounds @ TypeBounds(lo, hi) =>
        if (lo eq hi) {
          val saved = variance
          variance = variance * bounds.variance
          val result = this(x, lo)
          variance = saved
          result
        }
        else {
          variance = -variance
          val y = this(x, lo)
          variance = -variance
          this(y, hi)
        }

      case tp: RecType =>
        this(x, tp.parent)

      case ExprType(restpe) =>
        this(x, restpe)

      case tp: TypeVar =>
        this(x, tp.underlying)

      case SuperType(thistp, supertp) =>
        this(this(x, thistp), supertp)

      case tp @ ClassInfo(prefix, _, _, _, _) =>
        this(x, prefix)

      case tp @ HKApply(tycon, args) =>
        @tailrec def foldArgs(x: T, tparams: List[ParamInfo], args: List[Type]): T =
          if (args.isEmpty) {
            assert(tparams.isEmpty)
            x
          }
          else {
            val tparam = tparams.head
            val saved = variance
            variance *= tparam.paramVariance
            val acc =
              try this(x, args.head)
              finally variance = saved
            foldArgs(acc, tparams.tail, args.tail)
          }
        foldArgs(this(x, tycon), tp.typeParams, args)

      case tp: LambdaType =>
        variance = -variance
        val y = foldOver(x, tp.paramInfos)
        variance = -variance
        this(y, tp.resultType)

      case tp: AndOrType =>
        this(this(x, tp.tp1), tp.tp2)

      case tp: SkolemType =>
        this(x, tp.info)

      case AnnotatedType(underlying, annot) =>
        this(applyToAnnot(x, annot), underlying)

      case tp: WildcardType =>
        this(x, tp.optBounds)

      case tp: JavaArrayType =>
        this(x, tp.elemType)

      case tp: LazyRef =>
        this(x, tp.ref)

      case tp: ProtoType =>
        tp.fold(x, this)

      case _ => x
    }

    @tailrec final def foldOver(x: T, ts: List[Type]): T = ts match {
      case t :: ts1 => foldOver(apply(x, t), ts1)
      case nil => x
    }
  }

  abstract class TypeTraverser(implicit ctx: Context) extends TypeAccumulator[Unit] {
    def traverse(tp: Type): Unit
    def apply(x: Unit, tp: Type): Unit = traverse(tp)
    protected def traverseChildren(tp: Type) = foldOver((), tp)
  }

  class ExistsAccumulator(p: Type => Boolean, forceLazy: Boolean = true)(implicit ctx: Context) extends TypeAccumulator[Boolean] {
    override def stopAtStatic = false
    def apply(x: Boolean, tp: Type) =
      x || p(tp) || (forceLazy || !tp.isInstanceOf[LazyRef]) && foldOver(x, tp)
  }

  class ForeachAccumulator(p: Type => Unit, override val stopAtStatic: Boolean)(implicit ctx: Context) extends TypeAccumulator[Unit] {
    def apply(x: Unit, tp: Type): Unit = foldOver(p(tp), tp)
  }

  class HasUnsafeNonAccumulator(implicit ctx: Context) extends TypeAccumulator[Boolean] {
    def apply(x: Boolean, tp: Type) = x || tp.isUnsafeNonvariant || foldOver(x, tp)
  }

  class NamedPartsAccumulator(p: NamedType => Boolean, excludeLowerBounds: Boolean = false)
    (implicit ctx: Context) extends TypeAccumulator[mutable.Set[NamedType]] {
    override def stopAtStatic = false
    def maybeAdd(x: mutable.Set[NamedType], tp: NamedType) = if (p(tp)) x += tp else x
    val seen: mutable.Set[Type] = mutable.Set()
    def apply(x: mutable.Set[NamedType], tp: Type): mutable.Set[NamedType] =
      if (seen contains tp) x
      else {
        seen += tp
        tp match {
          case tp: TermRef =>
            apply(foldOver(maybeAdd(x, tp), tp), tp.underlying)
          case tp: TypeRef =>
            foldOver(maybeAdd(x, tp), tp)
          case TypeBounds(lo, hi) =>
            if (!excludeLowerBounds) apply(x, lo)
            apply(x, hi)
          case tp: ThisType =>
            apply(x, tp.tref)
          case tp: ConstantType =>
            apply(x, tp.underlying)
          case tp: ParamRef =>
            apply(x, tp.underlying)
          case _ =>
            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)  implies  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 && {
        val mbr = pre.nonPrivateMember(name)
        (mbr.symbol is Deferred) && mbr.info.isInstanceOf[RealTypeBounds]
      }
  }

  /** A filter for names of abstract types of a given type */
  object nonClassTypeNameFilter extends NameFilter {
    def apply(pre: Type, name: Name)(implicit ctx: Context): Boolean =
      name.isTypeName && {
        val mbr = pre.member(name)
        mbr.symbol.isType && !mbr.symbol.isClass
      }
  }

  /** 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.nonPrivateMember(name).hasAltWith(_.symbol is Deferred)
  }

  object typeNameFilter extends NameFilter {
    def apply(pre: Type, name: Name)(implicit ctx: Context): Boolean = name.isTypeName
  }

  object fieldFilter extends NameFilter {
    def apply(pre: Type, name: Name)(implicit ctx: Context): Boolean =
      name.isTermName && (pre member name).hasAltWith(!_.symbol.is(Method))
  }

  object takeAllFilter extends NameFilter {
    def apply(pre: Type, name: Name)(implicit ctx: Context): Boolean = true
  }

  object implicitFilter extends NameFilter {
    /** A dummy filter method.
     *  Implicit filtering is handled specially in computeMemberNames, so
     *  no post-filtering is needed.
     */
    def apply(pre: Type, name: Name)(implicit ctx: Context): Boolean = true
  }

  // ----- Exceptions -------------------------------------------------------------

  class TypeError(msg: String) extends Exception(msg)

  class MalformedType(pre: Type, denot: Denotation, absMembers: Set[Name])
    extends TypeError(
      s"malformed type: $pre is not a legal prefix for $denot because it contains abstract type member${if (absMembers.size == 1) "" else "s"} ${absMembers.mkString(", ")}")

  class MissingType(pre: Type, name: Name)(implicit ctx: Context) extends TypeError(
    i"""cannot resolve reference to type $pre.$name
       |the classfile defining the type might be missing from the classpath${otherReason(pre)}""") {
    if (ctx.debug) printStackTrace()
  }

  private def otherReason(pre: Type)(implicit ctx: Context): String = pre match {
    case pre: ThisType if pre.givenSelfType.exists =>
      i"\nor the self type of $pre might not contain all transitive dependencies"
    case _ => ""
  }

  class CyclicReference private (val denot: SymDenotation)
    extends TypeError(s"cyclic reference involving $denot") {
    def toMessage(implicit ctx: Context) = CyclicReferenceInvolving(denot)
  }

  object CyclicReference {
    def apply(denot: SymDenotation)(implicit ctx: Context): CyclicReference = {
      val ex = new CyclicReference(denot)
      if (!(ctx.mode is Mode.CheckCyclic)) {
        cyclicErrors.println(ex.getMessage)
        for (elem <- ex.getStackTrace take 200)
          cyclicErrors.println(elem.toString)
      }
      ex
    }
  }

  class MergeError(msg: String, val tp1: Type, val tp2: Type) extends TypeError(msg)

  // ----- Debug ---------------------------------------------------------

  @sharable var debugTrace = false

  val watchList = List[String](
  ) map (_.toTypeName)

  def isWatched(tp: Type) = tp match {
    case TypeRef(_, name) => watchList contains name
    case _ => false
  }

  // ----- Decorator implicits --------------------------------------------

  implicit def decorateTypeApplications(tpe: Type): TypeApplications = new TypeApplications(tpe)
}