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

package dotty.tools.dotc
package core

import util.HashSet
import Symbols._
import Flags._
import Names._
import Scopes._
import Constants._
import Contexts._
import Annotations._
import RefSets._
import Periods._
import scala.util.hashing.{MurmurHash3 => hashing}
import collection.mutable

trait Types { self: Context =>

  import Types._

  private val initialUniquesCapacity = 50000

  private[Types] val uniques = new util.HashSet[Type]("uniques", initialUniquesCapacity) {
    override def hash(x: Type): Int = x.hash
  }

}

object Types {

  /** The signature of a reference.
   *  Overloaded references with the same name are distinguished by
   *  their signatures. A signature is a list of the fully qualified names
   *  of the type symbols of the erasure of the parameters of the
   *  reference. For instance a reference to the definition
   *
   *      def f(x: Int)(y: List[String]): String
   *
   *  would have signature
   *
   *      List("scala.Int".toTypeName, "scala.collection.immutable.List".toTypeName)
   */
  type Signature = List[TypeName]

  val NullSignature = List(Names.EmptyTypeName)

  /** The variants constituting an overloaded reference.
   *  This is a set of non-overloaded references indexed by their
   *  signatures. All instances of Variants are assumed to
   *  have NoSymbol as default value.
   */
  type Variants = Map[Signature, RefType]

  /** The canonical creator of variants maps.
   *  Note that it adds NoSymbol as default value.
   */
  def Variants(bindings: (Signature, RefType)*): Variants =
    Map(bindings: _*) withDefaultValue NoType

  abstract class Type {

    def <:< (that: Type): Boolean = ???

    def hash = NotCached

    /** The type symbol associated with the type
     */
    def typeSymbol: Symbol = NoSymbol

    /** The term symbol associated with the type
     */
    def termSymbol: Symbol = NoSymbol

    /** Does this type denote a stable reference (i.e. singleton type)? */
    def isStableType: Boolean = false

    /** Is this type dangerous (i.e. it might contain conflicting
     *  type information when empty, so that it can be constructed
     *  so that type unsoundness results.) A dangerous type has an underlying
     *  type of the form T_1 with T_n { decls }, where one of the
     *  T_i (i > 1) is an abstract type.
     */
    def isVolatile: Boolean = false

    /** Is this type guaranteed not to have `null` as a value? */
    def isNotNull: Boolean = false

    /** Is this type produced as a repair for an error? */
    def isError(implicit ctx: Context): Boolean = (typeSymbol hasFlag Error) || (termSymbol hasFlag Error)

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

    /** Returns true if there is a part of this type that satisfies predicate `p`.
     */
    def exists(p: Type => Boolean): Boolean =
      new ExistsAccumulator(p)(false, this)

    /** For a class or intersection type, its parents.
     *  For a TypeBounds type, the parents of its hi bound.
     *  inherited by typerefs, singleton types, and refinement types,
     *  The empty list for all other types */
    def parents: List[Type] = List()

    def bounds(implicit ctx: Context): TypeBounds = TypeBounds(this, this)

    def decl(name: Name)(implicit ctx: Context): RefType =
      findClassDecl(name, typeSymbol.thisType, Flags.Empty)

    // need: NoSymbol is as good as any other
    def isAsGood(tp1: Type, tp2: Type)(implicit ctx: Context): Boolean = ???

    def member(name: Name)(implicit ctx: Context): Type =
      findMember(name, this, Flags.Empty)

    def nonPrivateMember(name: Name)(implicit ctx: Context): Type =
      findMember(name, this, Flags.Private)

    def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): RefType =
      throw new AssertionError(s"cannot find members of $this")

    protected def findClassMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): RefType =
      findMemberAmong(typeSymbol.asClass.deref.memberRefsNamed(name), pre, excluded)

    protected def findClassDecl(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): RefType =
      findMemberAmong(typeSymbol.asClass.deref.declsNamed(name), pre, excluded)

    private def findMemberAmong(candidates: RefSet, pre: Type, excluded: FlagSet)(implicit ctx: Context): RefType = {
      val resultSyms = candidates.filterAccessibleFrom(pre).filterExcluded(excluded)
      def makeRef(refs: RefSet): RefType = refs match {
        case RefUnion(refs1, refs2) => makeRef(refs1) ref_& makeRef(refs2)
        case ref: SymRef => ref
      }
      if (resultSyms.isEmpty) ErrorRefType // todo: refine
      else makeRef(resultSyms)
    }

    def memberType(sym: Symbol): Type = ???
    def memberInfo(sym: Symbol): Type = ???

    def widen: Type = ???

    def deconst: Type = ???

    def prefix(implicit ctx: Context): Type = ???

    def isTrivial: Boolean = ???

    def resultType: Type = ???

    def isCachable: Boolean = false

    def asSeenFrom(pre: Type, clazz: Symbol)(implicit ctx: Context): Type =
      if (this.isTrivial || clazz.isStaticMono) this
      else new AsSeenFromMap(pre, clazz) apply (this)

    def subst(from: List[Symbol], to: List[Type]): Type = ???
    def subst(from: PolyType, to: PolyType): Type = ???
    def subst(from: MethodType, to: MethodType): Type = ???
    def substSym(from: List[Symbol], to: List[Symbol]): Type = ???

    def baseType(clazz: Symbol): Type = ???

    def typeParams: List[TypeSymbol] = ???

    def effectiveBounds: TypeBounds = ???
    def isWrong: Boolean = ???

    def & (that: Type)(implicit ctx: Context): Type =
      if (this eq that) this
      else if (this.isWrong) that
      else if (that.isWrong) this
      else (this, that) match {
        case (_, OrType(that1, that2)) =>
          this & that1 | this & that2
        case (OrType(this1, this2), _) =>
          this1 & that | this2 & that
        case _ =>
          val t1 = lower(this, that)
          if (t1 ne that) t1
          else {
            val t2 = lower(that, this)
            if (t2 ne this) t2
            else AndType(this, that)
          }
      }

   def | (that: Type)(implicit ctx: Context): Type =
      if (this eq that) this
      else if (this.isWrong) this
      else if (that.isWrong) that
      else {
        val t1 = higher(this, that)
        if (t1 ne that) t1
        else {
          val t2 = higher(that, this)
          if (t2 ne this) t2
          else {
            val t1w = t1.widen
            val t2w = t2.widen
            if ((t1w ne t1) || (t2w ne t2)) t1w | t2w
            else OrType(this, that)
          }
        }
      }

   private def lower(t1: Type, t2: Type)(implicit ctx: Context): Type =
      if (t1 <:< t2) t1
      else t2 match {
        case t2 @ AndType(t21, t22) => t2.derivedAndType(lower(t1, t21), lower(t1, t22))
        case _ => t2
      }

    private def higher(t1: Type, t2: Type)(implicit ctx: Context): Type =
      if (t2 <:< t1) t1
      else t2 match {
        case t2 @ OrType(t21, t22) => t2.derivedOrType(higher(t1, t21), higher(t1, t22))
        case _ => t2
      }

    // hashing

    def correctHash(h: Int) = if (h == NotCached) NotCachedAlt else h

    def hashSeed = correctHash(getClass.hashCode)

    protected def doHash(seed: Int, tp: Type): Int =
      if (seed == NotCached) NotCached
      else {
        val elemHash = tp.hash
        if (elemHash == NotCached) NotCached
        else correctHash(hashing.mix(seed, elemHash))
      }

    protected def doHash(seed: Int, x: Any): Int =
      if (seed == NotCached) NotCached
      else {
        val elemHash = x.hashCode
        if (elemHash == NotCached) NotCached
        else correctHash(hashing.mix(seed, elemHash))
      }

    protected def doHash(seed: Int, tps: List[Type]): Int =
      if (seed == NotCached) NotCached
      else {
        var h = seed
        var xs = tps
        while (xs.nonEmpty) {
          val elemHash = xs.head.hash
          if (elemHash == NotCached) return NotCached
          h = hashing.mix(h, elemHash)
          xs = xs.tail
        }
        correctHash(h)
    }

    protected def doHash(seed: Int, variants: Variants): Int =
      if (seed == NotCached) NotCached
      else {
        var h = seed
        val it = variants.valuesIterator
        while (it.hasNext) {
          val elemHash = it.next.hash
          if (elemHash == NotCached) return NotCached
          h = hashing.mix(h, elemHash)
        }
        correctHash(h)
    }

    protected def finishHash(hashCode: Int, arity: Int): Int =
      correctHash(hashing.finalizeHash(hashCode, arity))

    protected def hash1(x: Any): Int =
      finishHash(doHash(hashSeed, x), 1)

    protected def hash2(tp1: Type, tp2: Type) =
      finishHash(doHash(doHash(hashSeed, tp1), tp2), 2)

  } // end Type

  abstract class UniqueType extends Type {
    final override val hash = computeHash
    def computeHash: Int
  }

  def unique[T <: Type](tp: T)(implicit ctx: Context): T = {
    if (tp.hash == NotCached) tp
    else ctx.root.uniques.findEntryOrUpdate(tp).asInstanceOf[T]
  }


  trait RefType extends Type {
    def signature(implicit ctx: Context): Signature =
      throw new UnsupportedOperationException(this.getClass+".signature")

    def orElse(alt: => RefType): RefType = if (isWrong) alt else this

    def ref_& (that: RefType)(implicit ctx: Context): RefType =
      if (this eq that) this
      else if (this.isWrong) that
      else if (that.isWrong) this
      else (this, that) match {
        case (OverloadedType(vs1), OverloadedType(vs2)) =>
          OverloadedType(conj(vs1, vs2))
        case (_, OverloadedType(vs2)) =>
          OverloadedType(vs2 updated (this.signature, this ref_& vs2(this.signature)))
        case (OverloadedType(vs1), _) =>
          OverloadedType(vs1 updated (that.signature, vs1(that.signature) ref_& that))
        case (this1 @ TypeRef(pre1, sym1), that1 @ TypeRef(pre2, sym2)) =>
          val rawtpe =
            if (sym1.isAbstractType) this1
            else if (sym2.isAbstractType) that1
            else
              TypeRef(pre1, sym1.owner.newAbstractType(sym1.name.asTypeName, sym1.info.bounds))
          rawtpe withInfo (this1.bounds & that1.bounds)
        case (this1 @ TermRef(pre1, sym1), that1 @ TermRef(pre2, sym2)) =>
          if ((this.signature != that.signature))
            OverloadedType(Variants(this.signature -> this, that.signature -> that))
          else
            TermRef(this1.prefix, sym1, this1.info & that1.info)
      }

    def ref_| (that: RefType)(implicit ctx: Context): RefType =
      if (this eq that) this
      else if (this.isWrong) this
      else if (that.isWrong) that
      else (this, that) match {
        case (OverloadedType(vs1), OverloadedType(vs2)) =>
          OverloadedType(disj(vs1, vs2))
        case (_, OverloadedType(vs2)) =>
          this ref_| vs2(this.signature)
        case (OverloadedType(vs1), _) =>
          vs1(that.signature) ref_| that
        case (this1 @ TypeRef(pre1, sym1), that1 @ TypeRef(pre2, sym2)) =>
          val rbounds = this1.bounds | that1.bounds
          val rsym = lubSym(pre1, sym1, sym2) orElse {
            val rpre = RefinedType(pre1, newScope)
            val rsym = rpre.typeSymbol.newAbstractType(sym1.name, rbounds)
            rpre.decls.enter(rsym)
            rsym
          }
          TypeRef(pre1, rsym.asType)
        case (this1 @ TermRef(pre1, sym1), that1 @ TermRef(pre2, sym2)) =>
          val rtpe = this1.info | that1.info
          val rsym = lubSym(pre1, sym1, sym2) orElse {
            val rpre = RefinedType(pre1, newScope)
            val rsym = rpre.typeSymbol.newAbstractTerm(sym1.name, rtpe)
            rpre.decls.enter(rsym)
            rsym
          }
          TermRef(pre1, rsym.asTerm)
      }

    /** Conjunction of two variants sets */
    private def conj(vs1: Variants, vs2: Variants)(implicit ctx: Context): Variants =
      Variants(
        ((vs1.keySet | vs2.keySet) map (sig => (sig -> (vs1(sig) ref_& vs2(sig))))).toSeq: _*)

    /** Disjunction of two variants sets */
    private def disj(vs1: Variants, vs2: Variants)(implicit ctx: Context): Variants =
      Variants(
        ((vs1.keySet & vs2.keySet) map (sig => (sig -> (vs1(sig) ref_| vs2(sig))))).toSeq: _*)

    private def lubSym(pre: Type, sym1: Symbol, sym2: Symbol)(implicit ctx: Context): Symbol = {
      def qualifies(sym: Symbol) =
        (sym isAccessibleFrom pre) && (sym2.owner isSubClass sym.owner)
      sym1.allOverriddenSymbols find qualifies getOrElse NoSymbol
    }
  }

  case class OverloadedType(variants: Variants) extends UniqueType with RefType {
    override def computeHash: Int = finishHash(doHash(hashSeed, variants), variants.size)
  }

  abstract class SymRef extends SubType with RefType with RefSetSingleton {
    def prefix: Type
    def symbol: Symbol

    def isType: Boolean = symbol.isType
    def isTerm = !isType

    protected var infoVar: Type = null

    def info(implicit ctx: Context): Type = {
      if (infoVar == null) infoVar = symbol.info.asSeenFrom(prefix, symbol.owner)
        infoVar
    }

    def widen(implicit ctx: Context): Type = if (symbol.isTerm) info.widen else this

    def derivedSymRef(pre: Type, sym: Symbol)(implicit ctx: Context): Type =
      if (pre eq prefix)
        this
      else if (sym.isOverridable && (sym.owner ne pre.typeSymbol))
        pre.nonPrivateMember(sym.name)
      else
        SymRef(pre, sym)

    def underlying(implicit ctx: Context) = info

    override def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): RefType =
      if (symbol.isClass) findClassMember(name, pre, excluded)
      else info.findMember(name, pre, excluded)

    def withInfo(newinfo: Type)(implicit ctx: Context): SymRef =
     if (info eq newinfo) this else SymRef(prefix, symbol, info)

    override def computeHash = finishHash(doHash(doHash(hashSeed, prefix), symbol), 2)
  }

  abstract case class TypeRef(prefix: Type, symbol: TypeSymbol) extends SymRef {
    override def typeSymbol = symbol
    override def signature(implicit ctx: Context): Signature = NullSignature
  }

  final class UniqueTypeRef(prefix: Type, symbol: TypeSymbol) extends TypeRef(prefix, symbol)

  abstract case class TermRef(prefix: Type, symbol: TermSymbol) extends SymRef {
    override def termSymbol = symbol
    private var signatureVar: Signature = null
    private var signatureRun: RunId = NoRunId
    override def signature(implicit ctx: Context): Signature = {
      def paramSig(tp: Type): TypeName = ???
      def resultSig(tp: Type): Signature = {
        val s = sig(tp)
        if (s eq NullSignature) Nil else s
      }
      def sig(tp: Type): Signature = tp match {
        case tp: PolyType =>
          resultSig(tp.resultType)
        case tp: MethodType =>
          (tp.paramTypes map paramSig) ::: resultSig(tp.resultType)
        case _ => NullSignature
      }
      if (signatureRun != ctx.runId) {
        signatureVar = sig(info)
        signatureRun = ctx.runId
      }
      signatureVar
    }
  }

  final class UniqueTermRef(prefix: Type, symbol: TermSymbol) extends TermRef(prefix, symbol)

  object SymRef {
    def apply(prefix: Type, sym: Symbol)(implicit ctx: Context): SymRef =
      if (sym.isType) TypeRef(prefix, sym.asType) else TermRef(prefix, sym.asTerm)
    def apply(prefix: Type, sym: Symbol, info: Type)(implicit ctx: Context): SymRef = {
      if (sym.isType) TypeRef(prefix, sym.asType, info) else TermRef(prefix, sym.asTerm, info)
    }
  }

  object TypeRef {
    def apply(prefix: Type, sym: TypeSymbol)(implicit ctx: Context): TypeRef =
      unique(new UniqueTypeRef(prefix, sym))
    def apply(prefix: Type, sym: TypeSymbol, info: Type)(implicit ctx: Context): TypeRef = {
      val ref = apply(prefix, sym)
      ref.infoVar = info
      ref
    }
  }

  object TermRef {
    def apply(prefix: Type, sym: TermSymbol)(implicit ctx: Context): TermRef =
      unique(new UniqueTermRef(prefix, sym))
    def apply(prefix: Type, sym: TermSymbol, info: Type)(implicit ctx: Context): TermRef = {
      val ref = apply(prefix, sym)
      ref.infoVar = info
      ref
    }

    def make(pre: Type, sym: TermSymbol)(implicit ctx: Context) =
      if (ctx.phase.erasedTypes) sym.tpe.resultType
      else TermRef(pre, sym) // was more complicated; see singleType
  }

  abstract case class AppliedType(tycon: Type, typeArgs: List[Type]) extends UniqueType {
    assert(tycon.typeParams.length == typeArgs.length)
    def derivedAppliedType(tc: Type, args: List[Type])(implicit ctx: Context): Type =
      if ((tc eq tycon) && (args eq typeArgs)) this
      else AppliedType(tc, args)

    override def computeHash = finishHash(doHash(doHash(hashSeed, tycon), typeArgs), 2)
  }

  final class UniqueAppliedType(tycon: Type, typeArgs: List[Type]) extends AppliedType(tycon, typeArgs)

  object AppliedType {
    def apply(tycon: Type, typeArgs: List[Type])(implicit ctx: Context) =
      unique(new UniqueAppliedType(tycon, typeArgs))
  }

  abstract case class AndType(tp1: Type, tp2: Type) extends UniqueType {
    def derivedAndType(t1: Type, t2: Type)(implicit ctx: Context) =
      if ((t1 eq tp1) && (t2 eq tp2)) this
      else AndType(tp1, tp2)

    override def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): RefType =
      (tp1 findMember (name, pre, excluded)) ref_& (tp2 findMember (name, pre, excluded))

    override def computeHash = hash2(tp1, tp2)
  }

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

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

  abstract case class OrType(tp1: Type, tp2: Type) extends UniqueType {
    def derivedOrType(t1: Type, t2: Type)(implicit ctx: Context) =
      if ((t1 eq tp1) && (t2 eq tp2)) this
      else OrType(tp1, tp2)

    override def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): RefType =
      tp1.findMember(name, pre, excluded) ref_| tp2.findMember(name, pre, excluded)

    override def computeHash = hash2(tp1, tp2)
  }

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

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

  case object NoType extends SymRef {
    def prefix = NoPrefix
    def symbol = NoSymbol
  }

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

  abstract class ErrorType extends Type

  object ErrorType extends ErrorType
  object ErrorRefType extends ErrorType with RefType

  trait SubType extends UniqueType {
    def underlying(implicit ctx: Context): Type
  }

  abstract class SingletonType extends SubType

  abstract case class ThisType(clazz: ClassSymbol) extends SingletonType {
    def underlying(implicit ctx: Context) = clazz.typeOfThis
    override def computeHash = finishHash(doHash(hashSeed, clazz), 1)
  }

  final class UniqueThisType(clazz: ClassSymbol) extends ThisType(clazz)

  object ThisType {
    def apply(clazz: ClassSymbol)(implicit ctx: Context) =
      unique(new UniqueThisType(clazz))
  }

  abstract case class SuperType(thistpe: Type, supertpe: Type) extends SingletonType {
    def derivedSuperType(thistp: Type, supertp: Type)(implicit ctx: Context) =
      if ((thistp eq thistpe) && (supertp eq supertpe)) this
      else SuperType(thistp, supertp)
    def underlying(implicit ctx: Context) = supertpe
    override def computeHash = hash2(thistpe, supertpe)
  }

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

  object SuperType {
    def apply(thistpe: Type, supertpe: Type)(implicit ctx: Context) =
      unique(new UniqueSuperType(thistpe, supertpe))
  }

  abstract case class ConstantType(value: Constant) extends SingletonType {
    def underlying(implicit ctx: Context) = value.tpe
    override def computeHash = hash1(value)
  }

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

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

  case class RefinedType(parent: Type, decls: Scope) extends Type { // can make uniquetype ??? but need to special-case symbols
    def derivedRefinedType(parent1: Type, decls1: Scope): RefinedType =
      if ((parent1 eq parent) && (decls1 eq decls)) this
      else RefinedType(parent1, decls1)

    override def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): RefType =
      findClassDecl(name, pre, excluded) orElse parent.findMember(name, pre, excluded)
  }

  abstract case class MethodType(paramNames: List[TermName], paramTypes: List[Type], resultTypeExp: MethodType => Type) extends UniqueType {
    override lazy val resultType = resultTypeExp(this)
    lazy val isDependent = resultType exists {
      case MethodParam(mt, _) => mt eq this
      case _ => false
    }
    def instantiate(argTypes: List[Type])(implicit ctx: Context): Type =
      if (isDependent) new InstMethodMap(this, argTypes) apply resultType
      else resultType
    override def computeHash =
      finishHash(doHash(doHash(doHash(hashSeed, paramNames), paramTypes), resultType), paramTypes.length + 2)
  }

  final class UniqueMethodType(paramNames: List[TermName], paramTypes: List[Type], resultTypeExp: MethodType => Type) extends MethodType(paramNames, paramTypes, resultTypeExp)

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

  abstract case class ExprType(override val resultType: Type) extends UniqueType {
    def derivedExprType(rt: Type)(implicit ctx: Context) =
      if (rt eq resultType) this else ExprType(rt)
    override def computeHash = hash1(resultType)
  }

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

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

  case class PolyType(paramNames: List[TypeName], paramBoundsExp: PolyType => List[TypeBounds], resultTypeExp: PolyType => Type) extends Type {
    lazy val paramBounds = paramBoundsExp(this)
    override lazy val resultType = resultTypeExp(this)

    def derivedPolyType(pnames: List[TypeName], pboundsExp: PolyType => List[TypeBounds], restpeExp: PolyType => Type): Type = {
      val restpe = PolyType(pnames, pboundsExp, restpeExp)
      if ((pnames eq paramNames) &&
          (pboundsExp(this) eq paramBounds) &&
          (restpeExp(this) eq resultType)) this
      else restpe
    }
    def instantiate(argTypes: List[Type])(implicit ctx: Context): Type =
      new InstPolyMap(this, argTypes) apply resultType
  }

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

  case class PolyParam(pt: PolyType, paramNum: Int) extends Type {
  }

  abstract case class TypeBounds(lo: Type, hi: Type) extends UniqueType {
    def derivedTypeBounds(lo1: Type, hi1: Type)(implicit ctx: Context) =
      if ((lo1 eq lo) && (hi1 eq hi)) this
      else TypeBounds(lo, hi)

    def & (that: TypeBounds)(implicit ctx: Context): TypeBounds =
      TypeBounds(this.lo | that.lo, this.hi & that.hi)
    def | (that: TypeBounds)(implicit ctx: Context): TypeBounds =
      TypeBounds(this.lo & that.lo, this.hi | that.hi)
    override def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): RefType =
      hi.findMember(name, pre, excluded)
    def map(f: Type => Type)(implicit ctx: Context): TypeBounds =
      TypeBounds(f(lo), f(hi))
    override def computeHash = hash2(lo, hi)
  }

  final class UniqueTypeBounds(lo: Type, hi: Type) extends TypeBounds(lo, hi)

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

  case class AnnotatedType(annots: List[AnnotationInfo], underlying: Type) extends Type {
    def derivedAnnotatedType(annots1: List[AnnotationInfo], underlying1: Type) =
      if ((annots1 eq annots) && (underlying1 eq underlying)) this
      else AnnotatedType.make(annots1, underlying1)
  }

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

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

    /** Map this function over given type */
    def mapOver(tp: Type): Type = tp match {
      case tp: SymRef =>
        tp.derivedSymRef(this(tp.prefix), tp.symbol)

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

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

      case tp @ PolyType(pnames, pboundsExpr, restpeExpr) =>
        val pbounds = tp.paramBounds
        val pbounds1 = pbounds mapConserve (_ map this)
        val restpe = tp.resultType
        val restpe1 = this(restpe)
        if ((pbounds1 eq pbounds) && (restpe1 eq restpe))
          tp
        else PolyType(
          pnames,
          x => pbounds1 mapConserve (_ map (_.subst(tp, x))),
          x => restpe1.subst(tp, x))

      case tp @ MethodType(pnames, ptypes, restpeExpr) =>
        val ptypes1 = ptypes mapConserve this
        val restpe = tp.resultType
        val restpe1 = this(restpe)
        if ((ptypes1 eq ptypes) && (restpe1 eq restpe)) tp
        else MethodType(pnames, ptypes1, x => restpe1.subst(tp, x))

      case tp @ ExprType(restpe) =>
        tp.derivedExprType(this(restpe))

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

      case tp @ TypeBounds(lo, hi) =>
        if (lo eq hi) {
          val lo1 = this(lo)
          tp.derivedTypeBounds(lo1, lo1)
        } else {
          tp.derivedTypeBounds(this(lo), this(hi))
        }

      case tp @ RefinedType(parent, decls) =>
        tp.derivedRefinedType(this(parent), mapOver(decls))

      case tp @ OverloadedType(vs) =>
        val altTypes = (vs map (_._2)).toList
        val altTypes1 = altTypes mapConserve (t => this(t).asInstanceOf[RefType])
        if (altTypes eq altTypes1) tp
        else altTypes.reduceLeft(_ ref_& _)

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

      case _ =>
        tp
    }

    /** Map this function over given scope */
    def mapOver(scope: Scope): Scope = {
      val elems = scope.toList
      val elems1 = mapOver(elems)
      if (elems1 eq elems) scope
      else newScopeWith(elems1: _*)
    }

    /** Map this function over given list of symbols */
    def mapOver(syms: List[Symbol]): List[Symbol] = {
      val infos = syms map (_.info)
      val infos1 = infos mapConserve this
      if (infos eq infos1) syms
      else {
        val syms1 = syms map (_.cloneSymbol)
        (syms1, infos1).zipped.foreach { (sym1, info1) =>
          sym1 setDenotation sym1.deref.withType(info1 substSym (syms, syms1))
        }
        syms1
      }
    }

    def mapOverAnnotations(annots: List[AnnotationInfo]): List[AnnotationInfo] = ???

  }

  class InstMethodMap(mt: MethodType, argtypes: List[Type])(implicit ctx: Context) extends TypeMap {
    def apply(tp: Type) = tp match {
      case MethodParam(`mt`, n) => argtypes(n)
      case _ => mapOver(tp)
    }
  }

  class InstPolyMap(pt: PolyType, argtypes: List[Type])(implicit ctx: Context) extends TypeMap {
    def apply(tp: Type) = tp match {
      case PolyParam(`pt`, n) => argtypes(n)
      case _ => mapOver(tp)
    }
  }

//  Constraints: poly => tvars
//



  class AsSeenFromMap(pre: Type, clazz: Symbol)(implicit ctx: Context) extends TypeMap {
    private def skipPrefixOf(pre: Type, clazz: Symbol) =
      (pre eq NoType) || (pre eq NoPrefix) || clazz.isPackageClass
    def apply(tp: Type) = tp match {
      case ThisType(sym) =>
        def toPrefix(pre: Type, clazz: Symbol): Type =
          if (skipPrefixOf(pre, clazz))
            tp
          else if ((sym isNonBottomSubClass clazz) &&
            (pre.widen.typeSymbol isNonBottomSubClass sym))
            pre match {
              case SuperType(thistp, _) => thistp
              case _ => pre
            }
          else
            toPrefix(pre.baseType(clazz).prefix, clazz.owner)
        toPrefix(pre, clazz)
      case TypeRef(_, tparam) if tparam.isTypeParameter =>
        def toInstance(pre: Type, clazz: Symbol): Type = {
          if (skipPrefixOf(pre, clazz)) tp
          else {
            val tparamOwner = tparam.owner

            def throwError =
              if (tparamOwner.tpe.parents exists (_.isErroneous))
                ErrorType // don't be overzealous with throwing exceptions, see #2641
              else
                throw new Error(
                  s"something is wrong (wrong class file?): tp ${tparam.locationString} cannot be instantiated from ${pre.widen}")

            def prefixMatches = pre.typeSymbol isNonBottomSubClass tparamOwner

            val basePre = pre.baseType(clazz)

            def instParamFrom(typeInst: Type): Type = typeInst match {
              case ConstantType(_) =>
                // have to deconst because it may be a Class[T].
                instParamFrom(typeInst.deconst)
              case AppliedType(tycon, baseArgs) =>
                instParam(tycon.typeParams, baseArgs)
              case _ =>
                throwError
            }

            def instParam(ps: List[Symbol], as: List[Type]): Type =
              if (ps.isEmpty || as.isEmpty) throwError
              else if (tparam eq ps.head) as.head
              else throwError

            if (tparamOwner == clazz && prefixMatches) instParamFrom(basePre)
            else toInstance(basePre.prefix, clazz.owner)
          }
        }
        toInstance(pre, clazz)
      case _ =>
        if (tp.isTrivial) tp else mapOver(tp)
    }
  }

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

    def apply(x: T, sym: Symbol): T = apply(x, sym.info(NoContext))

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

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

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

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

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

      case MethodType(pnames, ptypes, restpeExpr) =>
        this((x /: ptypes) (this), tp.resultType)

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

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

      case TypeBounds(lo, hi) =>
        this(this(x, lo), hi)

      case RefinedType(parent, decls) =>
        (this(x, parent) /: decls.toList) (apply)

      case OverloadedType(vs) =>
        (x /: (vs map (_._2))) (this)

      case AnnotatedType(annots, underlying) =>
        this((x /: annots) (apply), underlying)

      case _ => x

    }

  }

  class ExistsAccumulator(p: Type => Boolean) extends TypeAccumulator[Boolean] {
    def apply(x: Boolean, tp: Type) = x || p(tp) || foldOver(x, tp)
  }

  /** like map2, but returns list `xs` itself - instead of a copy - if function
   *  `f` maps all elements to themselves.
   */
  def map2Conserve[A <: AnyRef, B](xs: List[A], ys: List[B])(f: (A, B) => A): List[A] =
    if (xs.isEmpty) xs
    else {
      val x1 = f(xs.head, ys.head)
      val xs1 = map2Conserve(xs.tail, ys.tail)(f)
      if ((x1 eq xs.head) && (xs1 eq xs.tail)) xs
      else x1 :: xs1
    }

  final val NotCached = 0
  final val NotCachedAlt = Int.MinValue

  /** Compute the hash of a product
  def productHash(x: Product): Int = {
    val arr = x.productArity
    var h = x.productPrefix.hashCode
    var i = 0
    while (i < arr) {
      val elemHash = x.productElement(i) match {
        case tp: Type => tp.hash
        case elem => elem.hashCode
      }
      if (elemHash == NotCached) return NotCached
      h = hashing.mix(h, elemHash)
      i += 1
    }
    finalizeHash(h, arr)
  }*/


}