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 Denotations._
import References._
import Periods._
import References.{Reference, RefSet, RefUnion, ErrorRef}
import scala.util.hashing.{MurmurHash3 => hashing}
import collection.immutable.BitSet
import collection.mutable

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
  }

  /** A set for hash consing superclass bitsets */
  private[Types] val uniqueBits = new util.HashSet[BitSet]("superbits", 1024)
}

object Types {

  /** A hash value indicating that the underlying type is not
   *  cached in unbiques.
   */
  final val NotCached = 0

  /** An alternative value returned from `hash` if the
   *  computed hashCode would be `NotCached`.
   */
  final val NotCachedAlt = Int.MinValue

  abstract class Type extends DotClass {

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

    def hash = NotCached

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

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

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

    /** 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(implicit ctx: Context): List[Type] = List()

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

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

    def decls(implicit ctx: Context): Scope = unsupported("decls")

    def decl(name: Name)(implicit ctx: Context): Reference =
      decls.refsNamed(name).toRef

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

    def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): Reference =
      unsupported("findMember")

    protected def findMemberAmong(candidates: RefSet, pre: Type, owner: ClassSymbol, excluded: FlagSet)(implicit ctx: Context): Reference = {
      val resultSyms = candidates
        .filterAccessibleFrom(pre)
        .filterExcluded(excluded)
        .asSeenFrom(pre, owner)
      if (resultSyms.exists) resultSyms.toRef
      else ErrorRef // todo: refine
    }

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

    def widen: Type = ???

    def deconst: Type = ???

    def prefix: Type = ???

    def isTrivial: Boolean = ???

    def resultType: Type = ???

    def baseClasses: List[ClassSymbol] = ???

    def typeArgs: List[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 substThis(clazz: ClassSymbol, tp: Type): Type = ???
    def substThis(from: RefinedType, tp: Type): Type = ???

    def baseType(base: Symbol)(implicit ctx: Context): Type = base.info match {
      case cinfo: ClassInfoType => cinfo.baseTypeOf(this)
      case _ => NoType
    }

    def typeParams: List[TypeSymbol] = ???

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

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

    def | (that: Type)(implicit ctx: Context): Type =
      if (this eq that) this
      else if (this.isWrong) this
      else if (that.isWrong) that
      else {
        val t1 = mergeIfSuper(this, that)
        if (t1.exists) t1
        else {
          val t2 = mergeIfSuper(that, this)
          if (t2.exists) t2
          else OrType(this, that)
        }
      }

    /** Merge `t1` into `t2` if t1 is a subtype of some part of t2.
     */
    private def mergeIfSub(t1: Type, t2: Type)(implicit ctx: Context): Type =
      if (t1 <:< t2)
        if (t2 <:< t1) t2 else t1
      else t2 match {
        case t2 @ AndType(t21, t22) =>
          val lower1 = mergeIfSub(t1, t21)
          if (lower1 eq t21) t2
          else if (lower1.exists) lower1 & t22
          else {
            val lower2 = mergeIfSub(t1, t22)
            if (lower2 eq t22) t2
            else if (lower2.exists) t21 & lower2
            else NoType
          }
        case _ =>
          NoType
      }

   /** Merge `t1` into `t2` if t1 is a supertype of some part of t2.
    */
    private def mergeIfSuper(t1: Type, t2: Type)(implicit ctx: Context): Type =
      if (t2 <:< t1)
        if (t1 <:< t2) t2 else t1
      else t2 match {
        case t2 @ OrType(t21, t22) =>
          val higher1 = mergeIfSuper(t1, t21)
          if (higher1 eq t21) t2
          else if (higher1.exists) higher1 | t22
          else {
            val higher2 = mergeIfSuper(t1, t22)
            if (higher2 eq t22) t2
            else if (higher2.exists) t21 | higher2
            else NoType
          }
        case _ =>
          NoType
    }

    // hashing

    protected def hashSeed = getClass.hashCode

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

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

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

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

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

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

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

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

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

    protected def doHash(x1: Any, tp2: Type, tps3: List[Type]): Int =
      finishHash(hashing.mix(hashSeed, x1.hashCode), 1, tp2, tps3)
  } // end Type

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

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

  trait TypeProxy extends Type {
    def underlying(implicit ctx: Context): Type
    override def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): Reference =
      underlying.findMember(name, pre, excluded)
    override def parents(implicit ctx: Context) = underlying.parents
    override def decls(implicit ctx: Context) = underlying.decls
  }

  trait TransformingProxy extends TypeProxy {

  }

  trait SubType extends UniqueType with TypeProxy {

  }

  trait SingletonType extends SubType

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

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

    val name: Name

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

    private def needsStablePrefix(sym: Symbol) =
      sym.isAbstractType || sym.isClass && !sym.isJava

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

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

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

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

    override def parents(implicit ctx: Context) = {
      val ps = info.parents
      val sym = symbol
      if (sym.isClass) ps.mapConserve(_.substThis(sym.asClass, prefix)) else ps
    }

    def derivedNamedType(pre: Type, name: Name)(implicit ctx: Context): Type =
      if (pre eq prefix) this
      else NamedType(pre, name)

    override def computeHash = doHash(name, prefix)
  }

  abstract case class TermRef(override val prefix: Type, name: TermName) extends NamedType with SingletonType {
    override def termSymbol(implicit ctx: Context): Symbol = symbol
    override def isStable(implicit ctx: Context) = prefix.isStable && termSymbol.isStable
  }

  abstract case class TypeRef(override val prefix: Type, name: TypeName) extends NamedType {
    override def typeSymbol(implicit ctx: Context): Symbol = symbol
  }

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

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

  final class TypeRefNoPrefix(val fixedSym: TypeSymbol)(implicit ctx: Context)
        extends TypeRef(NoPrefix, fixedSym.name) with NamedNoPrefix {
    validPeriods = allPeriods(ctx.runId)
  }

  final class UniqueTermRef(prefix: Type, name: TermName) extends TermRef(prefix, name)
  final class UniqueTypeRef(prefix: Type, name: TypeName) extends TypeRef(prefix, name)

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

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

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

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

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

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

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

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

  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 = doHash(value)
  }

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

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

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

  abstract case class AppliedType(tycon: Type, override val 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 = doHash(tycon, typeArgs)
  }

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

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

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

    def underlying(implicit ctx: Context) = parent

    lazy val infos = infosExpr(this)

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

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

    override def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): Reference =
      parent.findMember(name, pre, excluded | Flags.Private) &
      findDecl(name, pre)

    def computeHash = doHash(names, parent, infos)
  }

// --- ClassInfo Type ---------------------------------------------------------

  case class ClassInfoType(_parents: List[Type], _decls: Scope, clazz: ClassSymbol) extends UniqueType {
    import NameFilter._
    import util.LRU8Cache

    override def parents(implicit ctx: Context) = _parents
    override def decls(implicit ctx: Context) = _decls

    private var memberCacheVar: LRU8Cache[Name, RefSet] = null

    private def memberCache: LRU8Cache[Name, RefSet] = {
      if (memberCacheVar == null) memberCacheVar = new LRU8Cache
      memberCacheVar
    }

    def thisType: Type = ???

    private var baseClassesVar: List[ClassSymbol] = null
    private var superClassBitsVar: BitSet = null

    private def computeSuperClassBits(implicit ctx: Context): Unit = {
      val seen = new mutable.BitSet
      val locked = new mutable.BitSet
      def addBaseClasses(bcs: List[ClassSymbol], to: List[ClassSymbol])
          : List[ClassSymbol] = bcs match {
        case bc :: bcs1 =>
          val id = bc.superId
          if (seen contains id) to
          else if (locked contains id) throw new CyclicReference(clazz)
          else {
            locked += id
            val bcs1added = addBaseClasses(bcs1, to)
            seen += id
            if (bcs1added eq bcs1) bcs else bc :: bcs1added
          }
        case _ =>
          to
      }
      def addParentBaseClasses(ps: List[Type], to: List[ClassSymbol]): List[ClassSymbol] = ps match {
        case p :: ps1 =>
          addBaseClasses(p.baseClasses, addParentBaseClasses(ps1, to))
        case _ =>
          to
      }
      baseClassesVar = clazz :: addParentBaseClasses(parents, Nil)
      superClassBitsVar = ctx.root.uniqueBits.findEntryOrUpdate(seen.toImmutable)
    }

    def superClassBits(implicit ctx: Context): BitSet = {
      if (superClassBitsVar == null) computeSuperClassBits
      superClassBitsVar
    }

    def baseClasses(implicit ctx: Context): List[ClassSymbol] = {
      if (baseClassesVar == null) computeSuperClassBits
      baseClassesVar
    }

    /** Is this class a subclass of `clazz`? */
    final def isSubClass(clazz: ClassSymbol)(implicit ctx: Context): Boolean = {
      superClassBits contains clazz.superId
    }

    private var definedFingerPrintCache: FingerPrint = null

    private def computeDefinedFingerPrint(implicit ctx: Context): FingerPrint = {
      var bits = newNameFilter
      var e = decls.lastEntry
      while (e != null) {
        includeName(bits, clazz.name)
        e = e.prev
      }
      var ps = parents
      while (ps.nonEmpty) {
        val parent = ps.head.typeSymbol
        parent.info match {
          case cinfo: ClassInfoType =>
            includeFingerPrint(bits, cinfo.definedFingerPrint)
            parent.deref setFlag Frozen
          case _ =>
        }
        ps = ps.tail
      }
      definedFingerPrintCache = bits
      bits
    }

    /** Enter a symbol in current scope.
     *  Note: We require that this does not happen after the first time
     *  someone does a findMember on a subclass.
     */
    def enter(sym: Symbol)(implicit ctx: Context) = {
      require((clazz.flags & Frozen) == Flags.Empty)
      decls enter sym
      if (definedFingerPrintCache != null)
        includeName(definedFingerPrintCache, sym.name)
      if (memberCacheVar != null)
        memberCache invalidate sym.name
    }

    /** Delete symbol from current scope.
     *  Note: We require that this does not happen after the first time
     *  someone does a findMember on a subclass.
     */
    def delete(sym: Symbol)(implicit ctx: Context) = {
      require((clazz.flags & Frozen) == Flags.Empty)
      decls unlink sym
      if (definedFingerPrintCache != null)
        computeDefinedFingerPrint
      if (memberCacheVar != null)
        memberCache invalidate sym.name
    }

    def definedFingerPrint(implicit ctx: Context): FingerPrint = {
      val fp = definedFingerPrintCache
      if (fp != null) fp else computeDefinedFingerPrint
    }

    final def memberRefsNamed(name: Name)(implicit ctx: Context): RefSet = {
      var refs: RefSet = memberCache lookup name
      if (refs == null) {
        if (containsName(definedFingerPrint, name)) {
          val ownRefs = decls.refsNamed(name)
          refs = ownRefs
          var ps = parents
          while (ps.nonEmpty) {
            val parentSym = ps.head.typeSymbol
            parentSym.info match {
              case pinfo: ClassInfoType =>
                refs = refs union
                  pinfo.memberRefsNamed(name)
                    .filterExcluded(Flags.Private)
                    .asSeenFrom(thisType, parentSym)
                    .filterDisjoint(ownRefs)
              case _ =>
            }
          }
        } else {
          refs = NoRef
        }
        memberCache enter (name, refs)
      }
      refs
    }

    private var baseTypeCache: java.util.HashMap[UniqueType, Type] = null

    final def baseTypeOf(tp: Type)(implicit ctx: Context): Type = {

      def computeBaseTypeOf(tp: Type): Type = tp match {
        case tp: NamedType =>
          val sym = tp.symbol
          val bt = baseTypeOf(tp.info)
          if (sym.isClass) bt.substThis(sym.asClass, tp.prefix)
          else bt
        case AppliedType(tycon, args) =>
          baseTypeOf(tycon).subst(tycon.typeParams, args)
        case AndType(tp1, tp2) =>
          baseTypeOf(tp1) & baseTypeOf(tp2)
        case OrType(tp1, tp2) =>
          baseTypeOf(tp1) | baseTypeOf(tp2)
        case ClassInfoType(parents, _, _) =>
          def reduce(bt: Type, ps: List[Type]): Type = ps match {
            case p :: ps1 => reduce(bt & baseTypeOf(p), ps1)
            case _ => bt
          }
          reduce(NoType, parents)
        case tp: TypeProxy =>
          baseTypeOf(tp.underlying)
      }

      if (clazz.isStatic && clazz.typeParams.isEmpty) clazz.tpe
      else tp match {
        case tp: UniqueType =>
          if (baseTypeCache == null)
            baseTypeCache = new java.util.HashMap[UniqueType, Type]
          var basetp = baseTypeCache get tp
          if (basetp == null) {
            baseTypeCache.put(tp, NoType)
            basetp = computeBaseTypeOf(tp)
            baseTypeCache.put(tp, basetp)
          } else if (basetp == NoType) {
            throw new CyclicReference(clazz)
          }
          basetp
        case _ =>
          computeBaseTypeOf(tp)
      }
    }
    override def typeSymbol(implicit ctx: Context) = clazz

    override def findMember(name: Name, pre: Type, excluded: FlagSet)(implicit ctx: Context): Reference =
      findMemberAmong(memberRefsNamed(name), pre, clazz, excluded)

    def computeHash = clazz.hashCode

  }

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

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

    type This <: AndType

    def derivedAndType(t1: Type, t2: Type)(implicit ctx: Context) =
      if ((t1 eq tp1) && (t2 eq tp2)) this
      else AndType(t1, t2)

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

    override def computeHash = doHash(tp1, tp2)
  }

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

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

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

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

    override def computeHash = doHash(tp1, tp2)
  }

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

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

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

  abstract case class MethodType(paramNames: List[TermName], paramTypes: List[Type])(resultTypeExp: MethodType => Type) extends UniqueType {
    override lazy val resultType = resultTypeExp(this)
    lazy val isDependent = resultType exists {
      case MethodParam(mt, _) => mt eq this
      case _ => false
    }
    def paramSig(tp: Type): TypeName = ???
    lazy val signature: Signature = {
      val sig = paramTypes map paramSig
      resultType match {
        case mt: MethodType => sig ++ mt.signature
        case _ => sig
      }
    }
    def instantiate(argTypes: List[Type])(implicit ctx: Context): Type =
      if (isDependent) new InstMethodMap(this, argTypes) apply resultType
      else resultType
    override def computeHash = doHash(paramNames, resultType, paramTypes)
  }

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

  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 = doHash(resultType)
  }

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

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

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

    def instantiate(argTypes: List[Type])(implicit ctx: Context): Type =
      new InstPolyMap(this, argTypes) apply resultType

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

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

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

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

// ------ Type Bounds ------------------------------------------------------------

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

    def & (that: TypeBounds)(implicit ctx: Context): TypeBounds =
      TypeBounds(this.lo | that.lo, this.hi & that.hi)
    def | (that: TypeBounds)(implicit ctx: Context): TypeBounds =
      TypeBounds(this.lo & that.lo, this.hi | that.hi)
    def map(f: Type => Type)(implicit ctx: Context): TypeBounds =
      TypeBounds(f(lo), f(hi))
    override def computeHash = doHash(lo, hi)
  }

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

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

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

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

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

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

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

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

  abstract class ErrorType extends Type

  object ErrorType extends ErrorType

  case object WildcardType extends Type

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

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

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

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

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

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

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

      case _ =>
        tp
    }

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

  }

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

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

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

  class AsSeenFromMap(pre: Type, clazz: Symbol)(implicit ctx: Context) extends TypeMap {

    private def skipPrefixOf(pre: Type, clazz: Symbol) =
      (pre eq NoType) || (pre eq NoPrefix) || clazz.isPackageClass

    private def toPrefix(pre: Type, clazz: Symbol, thisclazz: ClassSymbol, tp: Type): Type =
      if (skipPrefixOf(pre, clazz))
        tp
      else if ((thisclazz isNonBottomSubClass clazz) &&
        (pre.widen.typeSymbol isNonBottomSubClass thisclazz))
        pre match {
          case SuperType(thistp, _) => thistp
          case _ => pre
        }
      else
        toPrefix(pre.baseType(clazz).prefix, clazz.owner, thisclazz, tp)

    private def toInstance(pre: Type, clazz: Symbol, tparam: Symbol, tp: Type): 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, tparam, tp)
      }
    }

    def apply(tp: Type) = tp match {
      case ThisType(thisclazz) =>
        toPrefix(pre, clazz, thisclazz, tp)
      case _ =>
        tp.widen match {
          case tp: TypeRef if tp.typeSymbol.isTypeParameter =>
            toInstance(pre, clazz, tp.typeSymbol, tp)
          case _ =>
            if (tp.isTrivial) tp else mapOver(tp)
        }
    }
  }

// todo: prevent unstable prefixes in variables?


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

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

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

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

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

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

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

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

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

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

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

      case tp @ RefinedType(parent, names) =>
        (this(x, parent) /: tp.infos) (apply)

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

      case _ => x

    }

  }

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

// ----- Subtyping -----------------------------------------------------------

  type Constraints = Map[PolyParam, TypeBounds]

  class SubTyper(val constraints: Constraints = Map(), explain: Boolean = false) {

    /**
     *   isSubRefinement(T1, T2) =
     *     val clazz = T1.clazz
     *
     *
     */
    def isSubRefinement(tp1: Type, tp2: Type)(implicit ctx: Context): Boolean = {
      val clazz = tp1.typeSymbol
      assert(clazz eq tp2.typeSymbol)
      if (tp1.prefix != tp2.prefix) return false
      tp1 match {
        case AppliedType(tycon2, args2) =>
          isSubArgs(clazz.typeParams, tp1.typeArgs, args2) &&
          isSubRefinement(tp1, tycon2)
        case RefinedType(tycon2, names) =>
          ???

      }
    }

    def isSubArgs(tparams: List[TypeSymbol], subargs: List[Type], superargs: List[Type]): Boolean = ???

    /**
     *   NoType is not a sub or superType of Anything
     *
     *   T <: ?
     *   ? <: T
     *   T <: Error
     *   Error <: T
     *
     *   T1 <: T2[U2s] :-
     *       T1 <: T2 /\
     *       val T[U1s] = T1 baseType T2.typeSymbol
     *       and for all i:
     *       if !(Ui contravariant in T)      U1i <: U2i
     *       if !(Ui covariant in T)          U2i <: U1i
     *
     *   T1[U1s] <: T2 if
     *       T1 <: T2
     *
     *   P#A <: P#A  if A is no a class, or both types have same symbol
     *
     *   T1 <: T2  if class C = T2.typeSymbol
     *             /\ T1' = t1 baseType C
     *             /\ T1' isSubRefinement T2
     *
     *   T1 <: T2 { Ds }
     *     if T1 <: T2 and forall i, T1 specializesSym Di
     *
     *
     */
    def isSubType(tp1: Type, tp2: Type)(implicit ctx: Context): Boolean = {
???
/*
      if (tp1 == NoType || tp2 == NoType) return false
      if (tp1 eq tp2) return true

      tp2 match {
        case tp2 @ NamedType(pre2, name2) =>
          val ref2 = tp2.referenced
          if (name2.isTerm && ref2.isStable) return isSubType(tp1, ref2.info)
      }

      tp1 match {
        case tp1 @ NamedType(pre1, name1) =>
          val ref1 = tp1.referenced
          val sym1 = ref1.symbol
          if (sym1 != NoSymbol) {
            tp2 match {
              case tp2 @ NamedType(pre2, name2) =>
                val ref2 = tp2.referenced
                val sym2 = ref2.symbol
                if (sym1 eq sym2) return true





                if (sym1.isTerm) {
                  val expanded2 = if (ref2.info.isStable) return ref2.info else tp2
                  return isSubType(ref1.info, expanded2)
                }

            }
          }
      }

      (tp1, tp2) match {
        case (tp1 @ NamedType(pre1, name1), tp2 @ NamedType(pre2, name2)) =>
          if (!(pre1 =:= pre2)) return false
          val ref1 = tp1.referenced
          val ref2 = tp2.referenced
          val sym1 = ref1.symbol
          val sym2 = ref2.symbol
          if (sym1 != NoSymbol && sym2 != NoSymbol) {
            if (sym1 eq sym2) return true
            if (sym2.isTerm && ref2.isStable) return isSubType(tp1, ref2.info)
            if (sym1.isTerm) return isSubType(ref1.info, tp2)
            if (sym1.isClass) {
              if (sym1 == NothingClass) return true
              if (sym2.isClass) return sym1.isNonBottomSubClass(sym2) || sym1 == NullClass
            } else if (isSubType(ref1.upperBound, tp2)) return true
            // !sym1.isClass || !sym2.isClass
            if (name1  == name2) return true
            val lo = ref2.info.lowerBound
            return lo.typeSymbol != NothingClass && isSubType(tp1, lo)




          }
          if (sym1 == NothingClass) return true
          if ()
            if (sym1.isClass)
              if (sym1 == NothingClass) true
              if (sym2.isClass) sym1 isSubClass sym2
              else if (name1 eq name2) true
              else if
          }

            if (name1 == name2)

          }

        (!(tp1.symbol.isClass && tp2.symbol.isClass) || tp1.symbol == tp2.symbol)



      }

    }

    /** First try, on the right:
     *   - unwrap Annotated types, BoundedWildcardTypes,
     *   - bind TypeVars  on the right, if lhs is not Annotated nor BoundedWildcard
     *   - handle common cases for first-kind TypeRefs on both sides as a fast path.
     */
    def firstTry(tp1: Type, tp2: Type)(implicit ctx: Context): Boolean = tp2 match {
      case tp2: NamedType =>
        firstTry(tp1, tp2.underlying)
      case tp2: TypeRef =>

      case tr2: TypeRef =>
        tp1 match {
          case tr1: TypeRef =>
            val sym1 = tr1.sym
            val sym2 = tr2.sym
            val pre1 = tr1.pre
            val pre2 = tr2.pre
            (((if (sym1 == sym2) phase.erasedTypes || sym1.owner.hasPackageFlag || isSubType(pre1, pre2, depth)
               else (sym1.name == sym2.name && !sym1.isModuleClass && !sym2.isModuleClass &&
                     (isUnifiable(pre1, pre2) ||
                      isSameSpecializedSkolem(sym1, sym2, pre1, pre2) ||
                      sym2.isAbstractType && isSubPre(pre1, pre2, sym2)))) &&
                    isSubArgs(tr1.args, tr2.args, sym1.typeParams, depth))
             ||
             sym2.isClass && {
               val base = tr1 baseType sym2
               (base ne tr1) && isSubType(base, tr2, depth)
             }
             ||
             thirdTryRef(tr1, tr2))
          case _ =>
            secondTry
        }
      case AnnotatedType(_, _, _) =>
        isSubType(tp1.withoutAnnotations, tp2.withoutAnnotations, depth) &&
        annotationsConform(tp1, tp2)
      case BoundedWildcardType(bounds) =>
        isSubType(tp1, bounds.hi, depth)
      case tv2 @ TypeVar(_, constr2) =>
        tp1 match {
          case AnnotatedType(_, _, _) | BoundedWildcardType(_) =>
            secondTry
          case _ =>
            tv2.registerBound(tp1, true)
        }
      case _ =>
        secondTry*/
    }


  }

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

  class TypeError(msg: String) extends Exception(msg)
  class FatalTypeError(msg: String) extends TypeError(msg)
  class MalformedType(pre: Type, sym: Symbol) extends FatalTypeError(s"malformed type: $pre.$sym")
  class CyclicReference(sym: Symbol) extends FatalTypeError("cyclic reference involving $sym")

// ----- Misc utilities ---------------------------------------------------------

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

  def NothingType(implicit ctx: Context) = ctx.root.definitions.NothingType
  def AnyType(implicit ctx: Context) = ctx.root.definitions.AnyType
  lazy val SingletonType: Type = ???
}