package dotty.tools
package dotc
package core
import Types._, Contexts._, Symbols._, Flags._, Names._, NameOps._, Denotations._
import Decorators._
import StdNames.{nme, tpnme}
import collection.mutable
import printing.Disambiguation.disambiguated
import util.{Stats, DotClass, SimpleMap}
import config.Config
import config.Printers._
import TypeErasure.{erasedLub, erasedGlb}
import TypeApplications._
import scala.util.control.NonFatal
/** Provides methods to compare types.
*/
class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling {
implicit val ctx: Context = initctx
val state = ctx.typerState
import state.constraint
private var pendingSubTypes: mutable.Set[(Type, Type)] = null
private var recCount = 0
private var needsGc = false
/** Is a subtype check in progress? In that case we may not
* permanently instantiate type variables, because the corresponding
* constraint might still be retracted and the instantiation should
* then be reversed.
*/
def subtypeCheckInProgress: Boolean = {
val result = recCount > 0
if (result) {
constr.println("*** needsGC ***")
needsGc = true
}
result
}
/** For statistics: count how many isSubTypes are part of successful comparisons */
private var successCount = 0
private var totalCount = 0
private var myAnyClass: ClassSymbol = null
private var myNothingClass: ClassSymbol = null
private var myNullClass: ClassSymbol = null
private var myObjectClass: ClassSymbol = null
private var myAnyType: TypeRef = null
private var myNothingType: TypeRef = null
def AnyClass = {
if (myAnyClass == null) myAnyClass = defn.AnyClass
myAnyClass
}
def NothingClass = {
if (myNothingClass == null) myNothingClass = defn.NothingClass
myNothingClass
}
def NullClass = {
if (myNullClass == null) myNullClass = defn.NullClass
myNullClass
}
def ObjectClass = {
if (myObjectClass == null) myObjectClass = defn.ObjectClass
myObjectClass
}
def AnyType = {
if (myAnyType == null) myAnyType = AnyClass.typeRef
myAnyType
}
def NothingType = {
if (myNothingType == null) myNothingType = NothingClass.typeRef
myNothingType
}
// Subtype testing `<:<`
def topLevelSubType(tp1: Type, tp2: Type): Boolean = {
if (tp2 eq NoType) return false
if ((tp2 eq tp1) || (tp2 eq WildcardType)) return true
try isSubType(tp1, tp2)
finally
if (Config.checkConstraintsSatisfiable)
assert(isSatisfiable, constraint.show)
}
protected def isSubType(tp1: Type, tp2: Type): Boolean = ctx.traceIndented(s"isSubType ${traceInfo(tp1, tp2)}", subtyping) {
if (tp2 eq NoType) false
else if (tp1 eq tp2) true
else {
val saved = constraint
val savedSuccessCount = successCount
try {
recCount = recCount + 1
val result =
if (recCount < Config.LogPendingSubTypesThreshold) firstTry(tp1, tp2)
else monitoredIsSubType(tp1, tp2)
recCount = recCount - 1
if (!result) constraint = saved
else if (recCount == 0 && needsGc) {
state.gc()
needsGc = false
}
if (Stats.monitored) recordStatistics(result, savedSuccessCount)
result
} catch {
case NonFatal(ex) =>
if (ex.isInstanceOf[AssertionError]) showGoal(tp1, tp2)
recCount -= 1
constraint = saved
successCount = savedSuccessCount
throw ex
}
}
}
private def monitoredIsSubType(tp1: Type, tp2: Type) = {
if (pendingSubTypes == null) {
pendingSubTypes = new mutable.HashSet[(Type, Type)]
ctx.log(s"!!! deep subtype recursion involving ${tp1.show} <:< ${tp2.show}, constraint = ${state.constraint.show}")
ctx.log(s"!!! constraint = ${constraint.show}")
//if (ctx.settings.YnoDeepSubtypes.value) {
// new Error("deep subtype").printStackTrace()
//}
assert(!ctx.settings.YnoDeepSubtypes.value)
if (Config.traceDeepSubTypeRecursions && !this.isInstanceOf[ExplainingTypeComparer])
ctx.log(TypeComparer.explained(implicit ctx => ctx.typeComparer.isSubType(tp1, tp2)))
}
val p = (tp1, tp2)
!pendingSubTypes(p) && {
try {
pendingSubTypes += p
firstTry(tp1, tp2)
} finally {
pendingSubTypes -= p
}
}
}
private def firstTry(tp1: Type, tp2: Type): Boolean = tp2 match {
case tp2: NamedType =>
def compareNamed(tp1: Type, tp2: NamedType): Boolean = {
implicit val ctx: Context = this.ctx
tp2.info match {
case info2: TypeAlias => isSubType(tp1, info2.alias)
case _ => tp1 match {
case tp1: NamedType =>
tp1.info match {
case info1: TypeAlias =>
if (isSubType(info1.alias, tp2)) return true
if (tp1.prefix.isStable) return false
// If tp1.prefix is stable, the alias does contain all information about the original ref, so
// there's no need to try something else. (This is important for performance).
// To see why we cannot in general stop here, consider:
//
// trait C { type A }
// trait D { type A = String }
// (C & D)#A <: C#A
//
// Following the alias leads to the judgment `String <: C#A` which is false.
// However the original judgment should be true.
case _ =>
}
val sym1 = tp1.symbol
if ((sym1 ne NoSymbol) && (sym1 eq tp2.symbol))
ctx.erasedTypes ||
sym1.isStaticOwner ||
isSubType(tp1.prefix, tp2.prefix) ||
thirdTryNamed(tp1, tp2)
else
( (tp1.name eq tp2.name)
&& isSubType(tp1.prefix, tp2.prefix)
&& tp1.signature == tp2.signature
&& !tp1.isInstanceOf[WithFixedSym]
&& !tp2.isInstanceOf[WithFixedSym]
) ||
thirdTryNamed(tp1, tp2)
case _ =>
secondTry(tp1, tp2)
}
}
}
compareNamed(tp1, tp2)
case tp2: ProtoType =>
isMatchedByProto(tp2, tp1)
case tp2: BoundType =>
tp2 == tp1 || secondTry(tp1, tp2)
case tp2: TypeVar =>
isSubType(tp1, tp2.underlying)
case tp2: WildcardType =>
def compareWild = tp2.optBounds match {
case TypeBounds(_, hi) => isSubType(tp1, hi)
case NoType => true
}
compareWild
case tp2: LazyRef =>
!tp2.evaluating && isSubType(tp1, tp2.ref)
case tp2: AnnotatedType =>
isSubType(tp1, tp2.tpe) // todo: refine?
case tp2: ThisType =>
def compareThis = {
val cls2 = tp2.cls
tp1 match {
case tp1: ThisType =>
// We treat two prefixes A.this, B.this as equivalent if
// A's selftype derives from B and B's selftype derives from A.
val cls1 = tp1.cls
cls1.classInfo.selfType.derivesFrom(cls2) &&
cls2.classInfo.selfType.derivesFrom(cls1)
case tp1: NamedType if cls2.is(Module) && cls2.eq(tp1.widen.typeSymbol) =>
cls2.isStaticOwner ||
isSubType(tp1.prefix, cls2.owner.thisType) ||
secondTry(tp1, tp2)
case _ =>
secondTry(tp1, tp2)
}
}
compareThis
case tp2: SuperType =>
def compareSuper = tp1 match {
case tp1: SuperType =>
isSubType(tp1.thistpe, tp2.thistpe) &&
isSameType(tp1.supertpe, tp2.supertpe)
case _ =>
secondTry(tp1, tp2)
}
compareSuper
case AndType(tp21, tp22) =>
isSubType(tp1, tp21) && isSubType(tp1, tp22)
case OrType(tp21, tp22) =>
if (tp21.stripTypeVar eq tp22.stripTypeVar) isSubType(tp1, tp21)
else secondTry(tp1, tp2)
case TypeErasure.ErasedValueType(tycon1, underlying2) =>
def compareErasedValueType = tp1 match {
case TypeErasure.ErasedValueType(tycon2, underlying1) =>
(tycon1.symbol eq tycon2.symbol) && isSameType(underlying1, underlying2)
case _ =>
secondTry(tp1, tp2)
}
compareErasedValueType
case ErrorType =>
true
case _ =>
secondTry(tp1, tp2)
}
private def secondTry(tp1: Type, tp2: Type): Boolean = tp1 match {
case tp1: NamedType =>
tp1.info match {
case info1: TypeAlias =>
if (isSubType(info1.alias, tp2)) return true
if (tp1.prefix.isStable) return false
case _ =>
}
thirdTry(tp1, tp2)
case tp1: PolyParam =>
def flagNothingBound = {
if (!frozenConstraint && tp2.isRef(defn.NothingClass) && state.isGlobalCommittable) {
def msg = s"!!! instantiated to Nothing: $tp1, constraint = ${constraint.show}"
if (Config.failOnInstantiationToNothing) assert(false, msg)
else ctx.log(msg)
}
true
}
def comparePolyParam =
ctx.mode.is(Mode.TypevarsMissContext) ||
isSubTypeWhenFrozen(bounds(tp1).hi, tp2) || {
if (canConstrain(tp1)) addConstraint(tp1, tp2, fromBelow = false) && flagNothingBound
else thirdTry(tp1, tp2)
}
comparePolyParam
case tp1: ThisType =>
val cls1 = tp1.cls
tp2 match {
case tp2: TermRef if cls1.is(Module) && cls1.eq(tp2.widen.typeSymbol) =>
cls1.isStaticOwner ||
isSubType(cls1.owner.thisType, tp2.prefix) ||
thirdTry(tp1, tp2)
case _ =>
thirdTry(tp1, tp2)
}
case tp1: SkolemType =>
tp2 match {
case tp2: SkolemType if !ctx.phase.isTyper && tp1.info <:< tp2.info => true
case _ => thirdTry(tp1, tp2)
}
case tp1: TypeVar =>
isSubType(tp1.underlying, tp2)
case tp1: WildcardType =>
def compareWild = tp1.optBounds match {
case TypeBounds(lo, _) => isSubType(lo, tp2)
case _ => true
}
compareWild
case tp1: LazyRef =>
// If `tp1` is in train of being evaluated, don't force it
// because that would cause an assertionError. Return false instead.
// See i859.scala for an example where we hit this case.
!tp1.evaluating && isSubType(tp1.ref, tp2)
case tp1: AnnotatedType =>
isSubType(tp1.tpe, tp2)
case AndType(tp11, tp12) =>
if (tp11.stripTypeVar eq tp12.stripTypeVar) isSubType(tp11, tp2)
else thirdTry(tp1, tp2)
case OrType(tp11, tp12) =>
isSubType(tp11, tp2) && isSubType(tp12, tp2)
case ErrorType =>
true
case _ =>
thirdTry(tp1, tp2)
}
private def thirdTryNamed(tp1: Type, tp2: NamedType): Boolean = tp2.info match {
case TypeBounds(lo2, _) =>
def compareGADT: Boolean = {
val gbounds2 = ctx.gadt.bounds(tp2.symbol)
(gbounds2 != null) &&
(isSubTypeWhenFrozen(tp1, gbounds2.lo) ||
narrowGADTBounds(tp2, tp1, isUpper = false))
}
((frozenConstraint || !isCappable(tp1)) && isSubType(tp1, lo2) ||
compareGADT ||
fourthTry(tp1, tp2))
case _ =>
val cls2 = tp2.symbol
if (cls2.isClass) {
val base = tp1.baseTypeRef(cls2)
if (base.exists && (base ne tp1)) return isSubType(base, tp2)
if (cls2 == defn.SingletonClass && tp1.isStable) return true
}
fourthTry(tp1, tp2)
}
private def thirdTry(tp1: Type, tp2: Type): Boolean = tp2 match {
case tp2: NamedType =>
thirdTryNamed(tp1, tp2)
case tp2: PolyParam =>
def comparePolyParam =
(ctx.mode is Mode.TypevarsMissContext) ||
isSubTypeWhenFrozen(tp1, bounds(tp2).lo) || {
if (canConstrain(tp2)) addConstraint(tp2, tp1.widenExpr, fromBelow = true)
else fourthTry(tp1, tp2)
}
comparePolyParam
case tp2: RefinedType =>
def compareRefinedSlow: Boolean = {
val name2 = tp2.refinedName
isSubType(tp1, tp2.parent) &&
(name2 == nme.WILDCARD || hasMatchingMember(name2, tp1, tp2))
}
def compareRefined: Boolean = {
val tp1w = tp1.widen
val skipped2 = skipMatching(tp1w, tp2)
if ((skipped2 eq tp2) || !Config.fastPathForRefinedSubtype)
tp1 match {
case tp1: AndType =>
// Delay calling `compareRefinedSlow` because looking up a member
// of an `AndType` can lead to a cascade of subtyping checks
// This twist is needed to make collection/generic/ParFactory.scala compile
fourthTry(tp1, tp2) || compareRefinedSlow
case _ =>
compareRefinedSlow || fourthTry(tp1, tp2)
}
else // fast path, in particular for refinements resulting from parameterization.
isSubRefinements(tp1w.asInstanceOf[RefinedType], tp2, skipped2) &&
isSubType(tp1, skipped2)
}
compareRefined
case tp2: RecType =>
def compareRec = tp1.safeDealias match {
case tp1: RecType =>
val rthis1 = RecThis(tp1)
isSubType(tp1.parent, tp2.parent.substRecThis(tp2, rthis1))
case _ =>
val tp1stable = ensureStableSingleton(tp1)
isSubType(fixRecs(tp1stable, tp1stable.widenExpr), tp2.parent.substRecThis(tp2, tp1stable))
}
compareRec
case tp2 @ HKApply(tycon2, args2) =>
compareHkApply2(tp1, tp2, tycon2, args2)
case tp2 @ TypeLambda(tparams2, body2) =>
def compareHkLambda: Boolean = tp1.stripTypeVar match {
case tp1 @ TypeLambda(tparams1, body1) =>
// Don't compare bounds of lambdas, or t2994 will fail
// The issue is that, logically, bounds should compare contravariantly,
// so the bounds checking should look like this:
//
// tparams1.corresponds(tparams2)((tparam1, tparam2) =>
// isSubType(tparam2.paramBounds.subst(tp2, tp1), tparam1.paramBounds))
//
// But that would invalidate a pattern such as
// `[X0 <: Number] -> Number <:< [X0] -> Any`
// This wpuld mean that there is no convenient means anymore to express a kind
// as a supertype. The fix is to delay the checking of bounds so that only
// bounds of * types are checked.
val saved = comparingLambdas
comparingLambdas = true
try
variancesConform(tparams1, tparams2) &&
isSubType(body1, body2.subst(tp2, tp1))
finally comparingLambdas = saved
case _ =>
if (!tp1.isHK) {
tp2 match {
case EtaExpansion(tycon2) if tycon2.symbol.isClass =>
return isSubType(tp1, tycon2)
case _ =>
}
}
fourthTry(tp1, tp2)
}
compareHkLambda
case OrType(tp21, tp22) =>
// Rewrite T1 <: (T211 & T212) | T22 to T1 <: (T211 | T22) and T1 <: (T212 | T22)
// and analogously for T1 <: T21 | (T221 & T222)
// `|' types to the right of <: are problematic, because
// we have to choose one constraint set or another, which might cut off
// solutions. The rewriting delays the point where we have to choose.
tp21 match {
case AndType(tp211, tp212) =>
return isSubType(tp1, OrType(tp211, tp22)) && isSubType(tp1, OrType(tp212, tp22))
case _ =>
}
tp22 match {
case AndType(tp221, tp222) =>
return isSubType(tp1, OrType(tp21, tp221)) && isSubType(tp1, OrType(tp21, tp222))
case _ =>
}
either(isSubType(tp1, tp21), isSubType(tp1, tp22)) || fourthTry(tp1, tp2)
case tp2 @ MethodType(_, formals2) =>
def compareMethod = tp1 match {
case tp1 @ MethodType(_, formals1) =>
(tp1.signature consistentParams tp2.signature) &&
matchingParams(formals1, formals2, tp1.isJava, tp2.isJava) &&
tp1.isImplicit == tp2.isImplicit && // needed?
isSubType(tp1.resultType, tp2.resultType.subst(tp2, tp1))
case _ =>
false
}
compareMethod
case tp2: PolyType =>
def comparePoly = tp1 match {
case tp1: PolyType =>
(tp1.signature consistentParams tp2.signature) &&
matchingTypeParams(tp1, tp2) &&
isSubType(tp1.resultType, tp2.resultType.subst(tp2, tp1))
case _ =>
false
}
comparePoly
case tp2 @ ExprType(restpe2) =>
def compareExpr = tp1 match {
// We allow ()T to be a subtype of => T.
// We need some subtype relationship between them so that e.g.
// def toString and def toString() don't clash when seen
// as members of the same type. And it seems most logical to take
// ()T <:< => T, since everything one can do with a => T one can
// also do with a ()T by automatic () insertion.
case tp1 @ MethodType(Nil, _) => isSubType(tp1.resultType, restpe2)
case _ => isSubType(tp1.widenExpr, restpe2)
}
compareExpr
case tp2 @ TypeBounds(lo2, hi2) =>
def compareTypeBounds = tp1 match {
case tp1 @ TypeBounds(lo1, hi1) =>
(tp2.variance > 0 && tp1.variance >= 0 || (lo2 eq NothingType) || isSubType(lo2, lo1)) &&
(tp2.variance < 0 && tp1.variance <= 0 || (hi2 eq AnyType) || isSubType(hi1, hi2))
case tp1: ClassInfo =>
tp2 contains tp1
case _ =>
false
}
compareTypeBounds
case ClassInfo(pre2, cls2, _, _, _) =>
def compareClassInfo = tp1 match {
case ClassInfo(pre1, cls1, _, _, _) =>
(cls1 eq cls2) && isSubType(pre1, pre2)
case _ =>
false
}
compareClassInfo
case _ =>
fourthTry(tp1, tp2)
}
private def fourthTry(tp1: Type, tp2: Type): Boolean = tp1 match {
case tp1: TypeRef =>
tp1.info match {
case TypeBounds(_, hi1) =>
def compareGADT = {
val gbounds1 = ctx.gadt.bounds(tp1.symbol)
(gbounds1 != null) &&
(isSubTypeWhenFrozen(gbounds1.hi, tp2) ||
narrowGADTBounds(tp1, tp2, isUpper = true))
}
isSubType(hi1, tp2) || compareGADT
case _ =>
def isNullable(tp: Type): Boolean = tp.dealias match {
case tp: TypeRef => tp.symbol.isNullableClass
case tp: RefinedOrRecType => isNullable(tp.parent)
case AndType(tp1, tp2) => isNullable(tp1) && isNullable(tp2)
case OrType(tp1, tp2) => isNullable(tp1) || isNullable(tp2)
case _ => false
}
(tp1.symbol eq NothingClass) && tp2.isInstanceOf[ValueType] ||
(tp1.symbol eq NullClass) && isNullable(tp2)
}
case tp1: SingletonType =>
/** if `tp2 == p.type` and `p: q.type` then try `tp1 <:< q.type` as a last effort.*/
def comparePaths = tp2 match {
case tp2: TermRef =>
tp2.info match {
case tp2i: TermRef =>
isSubType(tp1, tp2i)
case ExprType(tp2i: TermRef) if (ctx.phase.id > ctx.gettersPhase.id) =>
// After getters, val x: T becomes def x: T
isSubType(tp1, tp2i)
case _ =>
false
}
case _ =>
false
}
isNewSubType(tp1.underlying.widenExpr, tp2) || comparePaths
case tp1: RefinedType =>
isNewSubType(tp1.parent, tp2)
case tp1: RecType =>
isNewSubType(tp1.parent, tp2)
case tp1 @ HKApply(tycon1, args1) =>
compareHkApply1(tp1, tycon1, args1, tp2)
case EtaExpansion(tycon1) =>
isSubType(tycon1, tp2)
case AndType(tp11, tp12) =>
// Rewrite (T111 | T112) & T12 <: T2 to (T111 & T12) <: T2 and (T112 | T12) <: T2
// and analogously for T11 & (T121 | T122) & T12 <: T2
// `&' types to the left of <: are problematic, because
// we have to choose one constraint set or another, which might cut off
// solutions. The rewriting delays the point where we have to choose.
tp11 match {
case OrType(tp111, tp112) =>
return isSubType(AndType(tp111, tp12), tp2) && isSubType(AndType(tp112, tp12), tp2)
case _ =>
}
tp12 match {
case OrType(tp121, tp122) =>
return isSubType(AndType(tp11, tp121), tp2) && isSubType(AndType(tp11, tp122), tp2)
case _ =>
}
either(isSubType(tp11, tp2), isSubType(tp12, tp2))
case JavaArrayType(elem1) =>
def compareJavaArray = tp2 match {
case JavaArrayType(elem2) => isSubType(elem1, elem2)
case _ => tp2 isRef ObjectClass
}
compareJavaArray
case tp1: ExprType if ctx.phase.id > ctx.gettersPhase.id =>
// getters might have converted T to => T, need to compensate.
isSubType(tp1.widenExpr, tp2)
case _ =>
false
}
/** Subtype test for the hk application `tp2 = tycon2[args2]`.
*/
def compareHkApply2(tp1: Type, tp2: HKApply, tycon2: Type, args2: List[Type]): Boolean = {
val tparams = tycon2.typeParams
assert(tparams.nonEmpty)
/** True if `tp1` and `tp2` have compatible type constructors and their
* corresponding arguments are subtypes relative to their variance (see `isSubArgs`).
*/
def isMatchingApply(tp1: Type): Boolean = tp1 match {
case HKApply(tycon1, args1) =>
tycon1.dealias match {
case tycon1: PolyParam =>
(tycon1 == tycon2 ||
canConstrain(tycon1) && tryInstantiate(tycon1, tycon2)) &&
isSubArgs(args1, args2, tparams)
case tycon1: TypeRef =>
tycon2.dealias match {
case tycon2: TypeRef if tycon1.symbol == tycon2.symbol =>
isSubType(tycon1.prefix, tycon2.prefix) &&
isSubArgs(args1, args2, tparams)
case _ =>
false
}
case tycon1: TypeVar =>
isMatchingApply(tycon1.underlying)
case tycon1: AnnotatedType =>
isMatchingApply(tycon1.underlying)
case _ =>
false
}
case _ =>
false
}
/** `param2` can be instantiated to a type application prefix of the LHS
* or to a type application prefix of one of the LHS base class instances
* and the resulting type application is a supertype of `tp1`,
* or fallback to fourthTry.
*/
def canInstantiate(tycon2: PolyParam): Boolean = {
/** Let
*
* `tparams_1, ..., tparams_k-1` be the type parameters of the rhs
* `tparams1_1, ..., tparams1_n-1` be the type parameters of the constructor of the lhs
* `args1_1, ..., args1_n-1` be the type arguments of the lhs
* `d = n - k`
*
* Returns `true` iff `d >= 0` and `tycon2` can be instantiated to
*
* [tparams1_d, ... tparams1_n-1] -> tycon1a[args_1, ..., args_d-1, tparams_d, ... tparams_n-1]
*
* such that the resulting type application is a supertype of `tp1`.
*/
def tyconOK(tycon1a: Type, args1: List[Type]) = {
var tycon1b = tycon1a
val tparams1a = tycon1a.typeParams
val lengthDiff = tparams1a.length - tparams.length
lengthDiff >= 0 && {
val tparams1 = tparams1a.drop(lengthDiff)
variancesConform(tparams1, tparams) && {
if (lengthDiff > 0)
tycon1b = tycon1a
.appliedTo(args1.take(lengthDiff) ++ tparams1.map(_.paramRef))
.LambdaAbstract(tparams1)
(ctx.mode.is(Mode.TypevarsMissContext) ||
tryInstantiate(tycon2, tycon1b.ensureHK)) &&
isSubType(tp1, tycon1b.appliedTo(args2))
}
}
}
tp1.widen match {
case tp1w @ HKApply(tycon1, args1) =>
tyconOK(tycon1, args1)
case tp1w =>
tp1w.typeSymbol.isClass && {
val classBounds = tycon2.classSymbols
def liftToBase(bcs: List[ClassSymbol]): Boolean = bcs match {
case bc :: bcs1 =>
classBounds.exists(bc.derivesFrom) &&
tyconOK(tp1w.baseTypeRef(bc), tp1w.baseArgInfos(bc)) ||
liftToBase(bcs1)
case _ =>
false
}
liftToBase(tp1w.baseClasses)
} ||
fourthTry(tp1, tp2)
}
}
/** Let `tycon2bounds` be the bounds of the RHS type constructor `tycon2`.
* Let `app2 = tp2` where the type constructor of `tp2` is replaced by
* `tycon2bounds.lo`.
* If both bounds are the same, continue with `tp1 <:< app2`.
* otherwise continue with either
*
* tp1 <:< tp2 using fourthTry (this might instantiate params in tp1)
* tp1 <:< app2 using isSubType (this might instantiate params in tp2)
*/
def compareLower(tycon2bounds: TypeBounds): Boolean = {
val app2 = tycon2bounds.lo.applyIfParameterized(args2)
if (tycon2bounds.lo eq tycon2bounds.hi) isSubType(tp1, app2)
else either(fourthTry(tp1, tp2), isSubType(tp1, app2))
}
tycon2 match {
case param2: PolyParam =>
isMatchingApply(tp1) || {
if (canConstrain(param2)) canInstantiate(param2)
else compareLower(bounds(param2))
}
case tycon2: TypeRef =>
isMatchingApply(tp1) ||
compareLower(tycon2.info.bounds)
case tycon2: TypeVar =>
isSubType(tp1, tycon2.underlying.appliedTo(args2))
case tycon2: AnnotatedType =>
compareHkApply2(tp1, tp2, tycon2.underlying, args2)
case _ =>
false
}
}
/** Subtype test for the hk application `tp1 = tycon1[args1]`.
*/
def compareHkApply1(tp1: HKApply, tycon1: Type, args1: List[Type], tp2: Type): Boolean =
tycon1 match {
case param1: PolyParam =>
def canInstantiate = tp2 match {
case AppliedType(tycon2, args2) =>
tryInstantiate(param1, tycon2.ensureHK) && isSubArgs(args1, args2, tycon2.typeParams)
case _ =>
false
}
canConstrain(param1) && canInstantiate ||
isSubType(bounds(param1).hi.applyIfParameterized(args1), tp2)
case tycon1: TypeProxy =>
isSubType(tycon1.superType.applyIfParameterized(args1), tp2)
case _ =>
false
}
/** Subtype test for corresponding arguments in `args1`, `args2` according to
* variances in type parameters `tparams`.
*/
def isSubArgs(args1: List[Type], args2: List[Type], tparams: List[TypeParamInfo]): Boolean =
if (args1.isEmpty) args2.isEmpty
else args2.nonEmpty && {
val v = tparams.head.paramVariance
(v > 0 || isSubType(args2.head, args1.head)) &&
(v < 0 || isSubType(args1.head, args2.head))
} && isSubArgs(args1.tail, args2.tail, tparams)
/** Test whether `tp1` has a base type of the form `B[T1, ..., Tn]` where
* - `B` derives from one of the class symbols of `tp2`,
* - the type parameters of `B` match one-by-one the variances of `tparams`,
* - `B` satisfies predicate `p`.
*/
private def testLifted(tp1: Type, tp2: Type, tparams: List[TypeParamInfo], p: Type => Boolean): Boolean = {
val classBounds = tp2.classSymbols
def recur(bcs: List[ClassSymbol]): Boolean = bcs match {
case bc :: bcs1 =>
val baseRef = tp1.baseTypeRef(bc)
(classBounds.exists(bc.derivesFrom) &&
variancesConform(baseRef.typeParams, tparams) &&
p(baseRef.appliedTo(tp1.baseArgInfos(bc)))
||
recur(bcs1))
case nil =>
false
}
recur(tp1.baseClasses)
}
/** Replace any top-level recursive type `{ z => T }` in `tp` with
* `[z := anchor]T`.
*/
private def fixRecs(anchor: SingletonType, tp: Type): Type = {
def fix(tp: Type): Type = tp.stripTypeVar match {
case tp: RecType => fix(tp.parent).substRecThis(tp, anchor)
case tp @ RefinedType(parent, rname, rinfo) => tp.derivedRefinedType(fix(parent), rname, rinfo)
case tp: PolyParam => fixOrElse(bounds(tp).hi, tp)
case tp: TypeProxy => fixOrElse(tp.underlying, tp)
case tp: AndOrType => tp.derivedAndOrType(fix(tp.tp1), fix(tp.tp2))
case tp => tp
}
def fixOrElse(tp: Type, fallback: Type) = {
val tp1 = fix(tp)
if (tp1 ne tp) tp1 else fallback
}
fix(tp)
}
/** Returns true iff the result of evaluating either `op1` or `op2` is true,
* trying at the same time to keep the constraint as wide as possible.
* E.g, if
*
* tp11 <:< tp12 = true with post-constraint c1
* tp12 <:< tp22 = true with post-constraint c2
*
* and c1 subsumes c2, then c2 is kept as the post-constraint of the result,
* otherwise c1 is kept.
*
* This method is used to approximate a solution in one of the following cases
*
* T1 & T2 <:< T3
* T1 <:< T2 | T3
*
* In the first case (the second one is analogous), we have a choice whether we
* want to establish the subtyping judgement using
*
* T1 <:< T3 or T2 <:< T3
*
* as a precondition. Either precondition might constrain type variables.
* The purpose of this method is to pick the precondition that constrains less.
* The method is not complete, because sometimes there is no best solution. Example:
*
* A? & B? <: T
*
* Here, each precondition leads to a different constraint, and neither of
* the two post-constraints subsumes the other.
*/
private def either(op1: => Boolean, op2: => Boolean): Boolean = {
val preConstraint = constraint
op1 && {
val leftConstraint = constraint
constraint = preConstraint
if (!(op2 && subsumes(leftConstraint, constraint, preConstraint)))
constraint = leftConstraint
true
} || op2
}
/** Like tp1 <:< tp2, but returns false immediately if we know that
* the case was covered previously during subtyping.
*/
private def isNewSubType(tp1: Type, tp2: Type): Boolean =
if (isCovered(tp1) && isCovered(tp2)) {
//println(s"useless subtype: $tp1 <:< $tp2")
false
} else isSubType(tp1, tp2)
/** Does type `tp1` have a member with name `name` whose normalized type is a subtype of
* the normalized type of the refinement `tp2`?
* Normalization is as follows: If `tp2` contains a skolem to its refinement type,
* rebase both itself and the member info of `tp` on a freshly created skolem type.
*/
protected def hasMatchingMember(name: Name, tp1: Type, tp2: RefinedType): Boolean = {
val rinfo2 = tp2.refinedInfo
val mbr = tp1.member(name)
def qualifies(m: SingleDenotation) = isSubType(m.info, rinfo2)
def memberMatches: Boolean = mbr match { // inlined hasAltWith for performance
case mbr: SingleDenotation => qualifies(mbr)
case _ => mbr hasAltWith qualifies
}
// special case for situations like:
// class C { type T }
// val foo: C
// foo.type <: C { type T = foo.T }
def selfReferentialMatch = tp1.isInstanceOf[SingletonType] && {
rinfo2 match {
case rinfo2: TypeAlias =>
!defn.isBottomType(tp1.widen) && (tp1 select name) =:= rinfo2.alias
case _ => false
}
}
/*>|>*/ ctx.traceIndented(i"hasMatchingMember($tp1 . $name :? ${tp2.refinedInfo}) ${mbr.info.show} $rinfo2", subtyping) /*<|<*/ {
memberMatches || selfReferentialMatch
}
}
final def ensureStableSingleton(tp: Type): SingletonType = tp.stripTypeVar match {
case tp: SingletonType if tp.isStable => tp
case tp: ValueType => SkolemType(tp)
case tp: TypeProxy => ensureStableSingleton(tp.underlying)
}
/** Skip refinements in `tp2` which match corresponding refinements in `tp1`.
* "Match" means:
* - they appear in the same order,
* - they refine the same names,
* - the refinement in `tp1` is an alias type, and
* - neither refinement refers back to the refined type via a refined this.
* @return The parent type of `tp2` after skipping the matching refinements.
*/
private def skipMatching(tp1: Type, tp2: RefinedType): Type = tp1 match {
case tp1 @ RefinedType(parent1, name1, rinfo1: TypeAlias) if name1 == tp2.refinedName =>
tp2.parent match {
case parent2: RefinedType => skipMatching(parent1, parent2)
case parent2 => parent2
}
case _ => tp2
}
/** Are refinements in `tp1` pairwise subtypes of the refinements of `tp2`
* up to parent type `limit`?
* @pre `tp1` has the necessary number of refinements, they are type aliases,
* and their names match the corresponding refinements in `tp2`.
* Further, no refinement refers back to the refined type via a refined this.
* The precondition is established by `skipMatching`.
*/
private def isSubRefinements(tp1: RefinedType, tp2: RefinedType, limit: Type): Boolean = {
def hasSubRefinement(tp1: RefinedType, refine2: Type): Boolean = {
isSubType(tp1.refinedInfo, refine2) || {
// last effort: try to adapt variances of higher-kinded types if this is sound.
val adapted2 = refine2.adaptHkVariances(tp1.parent.member(tp1.refinedName).symbol.info)
adapted2.ne(refine2) && hasSubRefinement(tp1, adapted2)
}
}
hasSubRefinement(tp1, tp2.refinedInfo) && (
(tp2.parent eq limit) ||
isSubRefinements(
tp1.parent.asInstanceOf[RefinedType], tp2.parent.asInstanceOf[RefinedType], limit))
}
/** A type has been covered previously in subtype checking if it
* is some combination of TypeRefs that point to classes, where the
* combiners are RefinedTypes, RecTypes, AndTypes or AnnotatedTypes.
* One exception: Refinements referring to basetype args are never considered
* to be already covered. This is necessary because such refined types might
* still need to be compared with a compareAliasRefined.
*/
private def isCovered(tp: Type): Boolean = tp.dealias.stripTypeVar match {
case tp: TypeRef => tp.symbol.isClass && tp.symbol != NothingClass && tp.symbol != NullClass
case tp: ProtoType => false
case tp: RefinedOrRecType => isCovered(tp.parent)
case tp: AnnotatedType => isCovered(tp.underlying)
case AndType(tp1, tp2) => isCovered(tp1) && isCovered(tp2)
case _ => false
}
/** Defer constraining type variables when compared against prototypes */
def isMatchedByProto(proto: ProtoType, tp: Type) = tp.stripTypeVar match {
case tp: PolyParam if constraint contains tp => true
case _ => proto.isMatchedBy(tp)
}
/** Can type `tp` be constrained from above by adding a constraint to
* a typevar that it refers to? In that case we have to be careful not
* to approximate with the lower bound of a type in `thirdTry`. Instead,
* we should first unroll `tp1` until we hit the type variable and bind the
* type variable with (the corresponding type in) `tp2` instead.
*/
private def isCappable(tp: Type): Boolean = tp match {
case tp: PolyParam => constraint contains tp
case tp: TypeProxy => isCappable(tp.underlying)
case tp: AndOrType => isCappable(tp.tp1) || isCappable(tp.tp2)
case _ => false
}
/** Narrow gadt.bounds for the type parameter referenced by `tr` to include
* `bound` as an upper or lower bound (which depends on `isUpper`).
* Test that the resulting bounds are still satisfiable.
*/
private def narrowGADTBounds(tr: NamedType, bound: Type, isUpper: Boolean): Boolean =
ctx.mode.is(Mode.GADTflexible) && {
val tparam = tr.symbol
typr.println(s"narrow gadt bound of $tparam: ${tparam.info} from ${if (isUpper) "above" else "below"} to $bound ${bound.isRef(tparam)}")
!bound.isRef(tparam) && {
val oldBounds = ctx.gadt.bounds(tparam)
val newBounds =
if (isUpper) TypeBounds(oldBounds.lo, oldBounds.hi & bound)
else TypeBounds(oldBounds.lo | bound, oldBounds.hi)
isSubType(newBounds.lo, newBounds.hi) &&
{ ctx.gadt.setBounds(tparam, newBounds); true }
}
}
// Tests around `matches`
/** A function implementing `tp1` matches `tp2`. */
final def matchesType(tp1: Type, tp2: Type, relaxed: Boolean): Boolean = tp1.widen match {
case tp1: MethodType =>
tp2.widen match {
case tp2: MethodType =>
tp1.isImplicit == tp2.isImplicit &&
matchingParams(tp1.paramTypes, tp2.paramTypes, tp1.isJava, tp2.isJava) &&
matchesType(tp1.resultType, tp2.resultType.subst(tp2, tp1), relaxed)
case tp2 =>
relaxed && tp1.paramNames.isEmpty &&
matchesType(tp1.resultType, tp2, relaxed)
}
case tp1: PolyType =>
tp2.widen match {
case tp2: PolyType =>
sameLength(tp1.paramNames, tp2.paramNames) &&
matchesType(tp1.resultType, tp2.resultType.subst(tp2, tp1), relaxed)
case _ =>
false
}
case _ =>
tp2.widen match {
case _: PolyType =>
false
case tp2: MethodType =>
relaxed && tp2.paramNames.isEmpty &&
matchesType(tp1, tp2.resultType, relaxed)
case tp2 =>
relaxed || isSameType(tp1, tp2)
}
}
/** Are `syms1` and `syms2` parameter lists with pairwise equivalent types? */
private def matchingParams(formals1: List[Type], formals2: List[Type], isJava1: Boolean, isJava2: Boolean): Boolean = formals1 match {
case formal1 :: rest1 =>
formals2 match {
case formal2 :: rest2 =>
(isSameTypeWhenFrozen(formal1, formal2)
|| isJava1 && (formal2 isRef ObjectClass) && (formal1 isRef AnyClass)
|| isJava2 && (formal1 isRef ObjectClass) && (formal2 isRef AnyClass)) &&
matchingParams(rest1, rest2, isJava1, isJava2)
case nil =>
false
}
case nil =>
formals2.isEmpty
}
/** Do generic types `poly1` and `poly2` have type parameters that
* have the same bounds (after renaming one set to the other)?
*/
private def matchingTypeParams(poly1: GenericType, poly2: GenericType): Boolean =
(poly1.paramBounds corresponds poly2.paramBounds)((b1, b2) =>
isSameType(b1, b2.subst(poly2, poly1)))
// Type equality =:=
/** Two types are the same if are mutual subtypes of each other */
def isSameType(tp1: Type, tp2: Type): Boolean =
if (tp1 eq NoType) false
else if (tp1 eq tp2) true
else isSubType(tp1, tp2) && isSubType(tp2, tp1)
/** Same as `isSameType` but also can be applied to overloaded TermRefs, where
* two overloaded refs are the same if they have pairwise equal alternatives
*/
def isSameRef(tp1: Type, tp2: Type): Boolean = ctx.traceIndented(s"isSameRef($tp1, $tp2") {
def isSubRef(tp1: Type, tp2: Type): Boolean = tp1 match {
case tp1: TermRef if tp1.isOverloaded =>
tp1.alternatives forall (isSubRef(_, tp2))
case _ =>
tp2 match {
case tp2: TermRef if tp2.isOverloaded =>
tp2.alternatives exists (isSubRef(tp1, _))
case _ =>
isSubType(tp1, tp2)
}
}
isSubRef(tp1, tp2) && isSubRef(tp2, tp1)
}
/** The greatest lower bound of two types */
def glb(tp1: Type, tp2: Type): Type = /*>|>*/ ctx.traceIndented(s"glb(${tp1.show}, ${tp2.show})", subtyping, show = true) /*<|<*/ {
if (tp1 eq tp2) tp1
else if (!tp1.exists) tp2
else if (!tp2.exists) tp1
else if ((tp1 isRef AnyClass) || (tp2 isRef NothingClass)) tp2
else if ((tp2 isRef AnyClass) || (tp1 isRef NothingClass)) tp1
else tp2 match { // normalize to disjunctive normal form if possible.
case OrType(tp21, tp22) =>
tp1 & tp21 | tp1 & tp22
case _ =>
tp1 match {
case OrType(tp11, tp12) =>
tp11 & tp2 | tp12 & tp2
case _ =>
val t1 = mergeIfSub(tp1, tp2)
if (t1.exists) t1
else {
val t2 = mergeIfSub(tp2, tp1)
if (t2.exists) t2
else tp1 match {
case tp1: ConstantType =>
tp2 match {
case tp2: ConstantType =>
// Make use of the fact that the intersection of two constant types
// types which are not subtypes of each other is known to be empty.
// Note: The same does not apply to singleton types in general.
// E.g. we could have a pattern match against `x.type & y.type`
// which might succeed if `x` and `y` happen to be the same ref
// at run time. It would not work to replace that with `Nothing`.
// However, maybe we can still apply the replacement to
// types which are not explicitly written.
defn.NothingType
case _ => andType(tp1, tp2)
}
case _ => andType(tp1, tp2)
}
}
}
}
}
/** The greatest lower bound of a list types */
final def glb(tps: List[Type]): Type =
((defn.AnyType: Type) /: tps)(glb)
/** The least upper bound of two types
* @note We do not admit singleton types in or-types as lubs.
*/
def lub(tp1: Type, tp2: Type): Type = /*>|>*/ ctx.traceIndented(s"lub(${tp1.show}, ${tp2.show})", subtyping, show = true) /*<|<*/ {
if (tp1 eq tp2) tp1
else if (!tp1.exists) tp1
else if (!tp2.exists) tp2
else if ((tp1 isRef AnyClass) || (tp2 isRef NothingClass)) tp1
else if ((tp2 isRef AnyClass) || (tp1 isRef NothingClass)) tp2
else {
val t1 = mergeIfSuper(tp1, tp2)
if (t1.exists) t1
else {
val t2 = mergeIfSuper(tp2, tp1)
if (t2.exists) t2
else {
val tp1w = tp1.widen
val tp2w = tp2.widen
if ((tp1 ne tp1w) || (tp2 ne tp2w)) lub(tp1w, tp2w)
else orType(tp1w, tp2w) // no need to check subtypes again
}
}
}
}
/** The least upper bound of a list of types */
final def lub(tps: List[Type]): Type =
((defn.NothingType: Type) /: tps)(lub)
/** Merge `t1` into `tp2` if t1 is a subtype of some &-summand of tp2.
*/
private def mergeIfSub(tp1: Type, tp2: Type): Type =
if (isSubTypeWhenFrozen(tp1, tp2))
if (isSubTypeWhenFrozen(tp2, tp1)) tp2 else tp1 // keep existing type if possible
else tp2 match {
case tp2 @ AndType(tp21, tp22) =>
val lower1 = mergeIfSub(tp1, tp21)
if (lower1 eq tp21) tp2
else if (lower1.exists) lower1 & tp22
else {
val lower2 = mergeIfSub(tp1, tp22)
if (lower2 eq tp22) tp2
else if (lower2.exists) tp21 & lower2
else NoType
}
case _ =>
NoType
}
/** Merge `tp1` into `tp2` if tp1 is a supertype of some |-summand of tp2.
*/
private def mergeIfSuper(tp1: Type, tp2: Type): Type =
if (isSubTypeWhenFrozen(tp2, tp1))
if (isSubTypeWhenFrozen(tp1, tp2)) tp2 else tp1 // keep existing type if possible
else tp2 match {
case tp2 @ OrType(tp21, tp22) =>
val higher1 = mergeIfSuper(tp1, tp21)
if (higher1 eq tp21) tp2
else if (higher1.exists) higher1 | tp22
else {
val higher2 = mergeIfSuper(tp1, tp22)
if (higher2 eq tp22) tp2
else if (higher2.exists) tp21 | higher2
else NoType
}
case _ =>
NoType
}
/** Form a normalized conjunction of two types.
* Note: For certain types, `&` is distributed inside the type. This holds for
* all types which are not value types (e.g. TypeBounds, ClassInfo,
* ExprType, MethodType, PolyType). Also, when forming an `&`,
* instantiated TypeVars are dereferenced and annotations are stripped.
* Finally, refined types with the same refined name are
* opportunistically merged.
*
* Sometimes, the conjunction of two types cannot be formed because
* the types are in conflict of each other. In particular:
*
* 1. Two different class types are conflicting.
* 2. A class type conflicts with a type bounds that does not include the class reference.
* 3. Two method or poly types with different (type) parameters but the same
* signature are conflicting
*
* In these cases, a MergeError is thrown.
*/
final def andType(tp1: Type, tp2: Type, erased: Boolean = ctx.erasedTypes) = ctx.traceIndented(s"glb(${tp1.show}, ${tp2.show})", subtyping, show = true) {
val t1 = distributeAnd(tp1, tp2)
if (t1.exists) t1
else {
val t2 = distributeAnd(tp2, tp1)
if (t2.exists) t2
else if (erased) erasedGlb(tp1, tp2, isJava = false)
else liftIfHK(tp1, tp2, AndType(_, _), _ & _)
}
}
/** Form a normalized conjunction of two types.
* Note: For certain types, `|` is distributed inside the type. This holds for
* all types which are not value types (e.g. TypeBounds, ClassInfo,
* ExprType, MethodType, PolyType). Also, when forming an `|`,
* instantiated TypeVars are dereferenced and annotations are stripped.
*
* Sometimes, the disjunction of two types cannot be formed because
* the types are in conflict of each other. (@see `andType` for an enumeration
* of these cases). In cases of conflict a `MergeError` is raised.
*
* @param erased Apply erasure semantics. If erased is true, instead of creating
* an OrType, the lub will be computed using TypeCreator#erasedLub.
*/
final def orType(tp1: Type, tp2: Type, erased: Boolean = ctx.erasedTypes) = {
val t1 = distributeOr(tp1, tp2)
if (t1.exists) t1
else {
val t2 = distributeOr(tp2, tp1)
if (t2.exists) t2
else if (erased) erasedLub(tp1, tp2)
else liftIfHK(tp1, tp2, OrType(_, _), _ | _)
}
}
/** `op(tp1, tp2)` unless `tp1` and `tp2` are type-constructors with at least
* some unnamed type parameters.
* In the latter case, combine `tp1` and `tp2` under a type lambda like this:
*
* [X1, ..., Xn] -> op(tp1[X1, ..., Xn], tp2[X1, ..., Xn])
*
* Note: There is a tension between named and positional parameters here, which
* is impossible to resolve completely. Say you have
*
* C[type T], D[type U]
*
* Then do you expand `C & D` to `[T] -> C[T] & D[T]` or not? Under the named
* type parameter interpretation, this would be wrong whereas under the traditional
* higher-kinded interpretation this would be required. The problem arises from
* allowing both interpretations. A possible remedy is to be somehow stricter
* in where we allow which interpretation.
*/
private def liftIfHK(tp1: Type, tp2: Type, op: (Type, Type) => Type, original: (Type, Type) => Type) = {
val tparams1 = tp1.typeParams
val tparams2 = tp2.typeParams
if (tparams1.isEmpty)
if (tparams2.isEmpty) op(tp1, tp2)
else original(tp1, tp2.appliedTo(tp2.typeParams.map(_.paramBoundsAsSeenFrom(tp2))))
else if (tparams2.isEmpty)
original(tp1.appliedTo(tp1.typeParams.map(_.paramBoundsAsSeenFrom(tp1))), tp2)
else
TypeLambda(
paramNames = tpnme.syntheticLambdaParamNames(tparams1.length),
variances = (tparams1, tparams2).zipped.map((tparam1, tparam2) =>
(tparam1.paramVariance + tparam2.paramVariance) / 2))(
paramBoundsExp = tl => (tparams1, tparams2).zipped.map((tparam1, tparam2) =>
tl.lifted(tparams1, tparam1.paramBoundsAsSeenFrom(tp1)).bounds &
tl.lifted(tparams2, tparam2.paramBoundsAsSeenFrom(tp2)).bounds),
resultTypeExp = tl =>
original(tl.lifted(tparams1, tp1).appliedTo(tl.paramRefs),
tl.lifted(tparams2, tp2).appliedTo(tl.paramRefs)))
}
/** Try to distribute `&` inside type, detect and handle conflicts
* @pre !(tp1 <: tp2) && !(tp2 <:< tp1) -- these cases were handled before
*/
private def distributeAnd(tp1: Type, tp2: Type): Type = tp1 match {
// opportunistically merge same-named refinements
// this does not change anything semantically (i.e. merging or not merging
// gives =:= types), but it keeps the type smaller.
case tp1: RefinedType =>
tp2 match {
case tp2: RefinedType if tp1.refinedName == tp2.refinedName =>
// Given two refinements `T1 { X = S1 }` and `T2 { X = S2 }`, if `S1 =:= S2`
// (possibly by instantiating type parameters), rewrite to `T1 & T2 { X = S1 }`.
// Otherwise rewrite to `T1 & T2 { X B }` where `B` is the conjunction of
// the bounds of `X` in `T1` and `T2`.
// The first rule above is contentious because it cuts the constraint set.
// But without it we would replace the two aliases by
// `T { X >: S1 | S2 <: S1 & S2 }`, which looks weird and is probably
// not what's intended.
val rinfo1 = tp1.refinedInfo
val rinfo2 = tp2.refinedInfo
val parent = tp1.parent & tp2.parent
val rinfo =
if (rinfo1.isAlias && rinfo2.isAlias && isSameType(rinfo1, rinfo2))
rinfo1
else
rinfo1 & rinfo2
tp1.derivedRefinedType(parent, tp1.refinedName, rinfo)
case _ =>
NoType
}
case tp1: RecType =>
tp1.rebind(distributeAnd(tp1.parent, tp2))
case tp1: TypeBounds =>
tp2 match {
case tp2: TypeBounds => tp1 & tp2
case tp2: ClassInfo if tp1 contains tp2 => tp2
case _ => mergeConflict(tp1, tp2)
}
case tp1: ClassInfo =>
tp2 match {
case tp2: ClassInfo if tp1.cls eq tp2.cls => tp1.derivedClassInfo(tp1.prefix & tp2.prefix)
case tp2: TypeBounds if tp2 contains tp1 => tp1
case _ => mergeConflict(tp1, tp2)
}
case tp1 @ MethodType(names1, formals1) =>
tp2 match {
case tp2 @ MethodType(names2, formals2)
if matchingParams(formals1, formals2, tp1.isJava, tp2.isJava) &&
tp1.isImplicit == tp2.isImplicit =>
tp1.derivedMethodType(
mergeNames(names1, names2, nme.syntheticParamName),
formals1, tp1.resultType & tp2.resultType.subst(tp2, tp1))
case _ =>
mergeConflict(tp1, tp2)
}
case tp1: PolyType =>
tp2 match {
case tp2: PolyType if matchingTypeParams(tp1, tp2) =>
tp1.derivedPolyType(
mergeNames(tp1.paramNames, tp2.paramNames, tpnme.syntheticTypeParamName),
tp1.paramBounds, tp1.resultType & tp2.resultType.subst(tp2, tp1))
case _ =>
mergeConflict(tp1, tp2)
}
case ExprType(rt1) =>
tp2 match {
case ExprType(rt2) =>
ExprType(rt1 & rt2)
case _ =>
rt1 & tp2
}
case tp1: TypeVar if tp1.isInstantiated =>
tp1.underlying & tp2
case tp1: AnnotatedType =>
tp1.underlying & tp2
case _ =>
NoType
}
/** Try to distribute `|` inside type, detect and handle conflicts
* Note that, unlike for `&`, a disjunction cannot be pushed into
* a refined or applied type. Example:
*
* List[T] | List[U] is not the same as List[T | U].
*
* The rhs is a proper supertype of the lhs.
*/
private def distributeOr(tp1: Type, tp2: Type): Type = tp1 match {
case tp1: TypeBounds =>
tp2 match {
case tp2: TypeBounds => tp1 | tp2
case tp2: ClassInfo if tp1 contains tp2 => tp1
case _ => mergeConflict(tp1, tp2)
}
case tp1: ClassInfo =>
tp2 match {
case tp2: ClassInfo if tp1.cls eq tp2.cls => tp1.derivedClassInfo(tp1.prefix | tp2.prefix)
case tp2: TypeBounds if tp2 contains tp1 => tp2
case _ => mergeConflict(tp1, tp2)
}
case tp1 @ MethodType(names1, formals1) =>
tp2 match {
case tp2 @ MethodType(names2, formals2)
if matchingParams(formals1, formals2, tp1.isJava, tp2.isJava) &&
tp1.isImplicit == tp2.isImplicit =>
tp1.derivedMethodType(
mergeNames(names1, names2, nme.syntheticParamName),
formals1, tp1.resultType | tp2.resultType.subst(tp2, tp1))
case _ =>
mergeConflict(tp1, tp2)
}
case tp1: GenericType =>
tp2 match {
case tp2: GenericType if matchingTypeParams(tp1, tp2) =>
tp1.derivedGenericType(
mergeNames(tp1.paramNames, tp2.paramNames, tpnme.syntheticTypeParamName),
tp1.paramBounds, tp1.resultType | tp2.resultType.subst(tp2, tp1))
case _ =>
mergeConflict(tp1, tp2)
}
case ExprType(rt1) =>
ExprType(rt1 | tp2.widenExpr)
case tp1: TypeVar if tp1.isInstantiated =>
tp1.underlying | tp2
case tp1: AnnotatedType =>
tp1.underlying | tp2
case _ =>
NoType
}
/** Handle merge conflict by throwing a `MergeError` exception */
private def mergeConflict(tp1: Type, tp2: Type): Type = {
def showType(tp: Type) = tp match {
case ClassInfo(_, cls, _, _, _) => cls.showLocated
case bounds: TypeBounds => i"type bounds $bounds"
case _ => tp.show
}
if (true) throw new MergeError(s"cannot merge ${showType(tp1)} with ${showType(tp2)}", tp1, tp2)
else throw new Error(s"cannot merge ${showType(tp1)} with ${showType(tp2)}") // flip condition for debugging
}
/** Merge two lists of names. If names in corresponding positions match, keep them,
* otherwise generate new synthetic names.
*/
private def mergeNames[N <: Name](names1: List[N], names2: List[N], syntheticName: Int => N): List[N] = {
for ((name1, name2, idx) <- (names1, names2, 0 until names1.length).zipped)
yield if (name1 == name2) name1 else syntheticName(idx)
}.toList
/** Show type, handling type types better than the default */
private def showType(tp: Type)(implicit ctx: Context) = tp match {
case ClassInfo(_, cls, _, _, _) => cls.showLocated
case bounds: TypeBounds => "type bounds" + bounds.show
case _ => tp.show
}
/** A comparison function to pick a winner in case of a merge conflict */
private def isAsGood(tp1: Type, tp2: Type): Boolean = tp1 match {
case tp1: ClassInfo =>
tp2 match {
case tp2: ClassInfo =>
isSubTypeWhenFrozen(tp1.prefix, tp2.prefix) || (tp1.cls.owner derivesFrom tp2.cls.owner)
case _ =>
false
}
case tp1: PolyType =>
tp2 match {
case tp2: PolyType =>
tp1.typeParams.length == tp2.typeParams.length &&
isAsGood(tp1.resultType, tp2.resultType.subst(tp2, tp1))
case _ =>
false
}
case tp1: MethodType =>
tp2 match {
case tp2: MethodType =>
def asGoodParams(formals1: List[Type], formals2: List[Type]) =
(formals2 corresponds formals1)(isSubTypeWhenFrozen)
asGoodParams(tp1.paramTypes, tp2.paramTypes) &&
(!asGoodParams(tp2.paramTypes, tp1.paramTypes) ||
isAsGood(tp1.resultType, tp2.resultType))
case _ =>
false
}
case _ =>
false
}
/** A new type comparer of the same type as this one, using the given context. */
def copyIn(ctx: Context) = new TypeComparer(ctx)
// ----------- Diagnostics --------------------------------------------------
/** A hook for showing subtype traces. Overridden in ExplainingTypeComparer */
def traceIndented[T](str: String)(op: => T): T = op
private def traceInfo(tp1: Type, tp2: Type) =
s"${tp1.show} <:< ${tp2.show}" + {
if (ctx.settings.verbose.value || Config.verboseExplainSubtype) {
s" ${tp1.getClass}, ${tp2.getClass}" +
(if (frozenConstraint) " frozen" else "") +
(if (ctx.mode is Mode.TypevarsMissContext) " tvars-miss-ctx" else "")
}
else ""
}
/** Show subtype goal that led to an assertion failure */
def showGoal(tp1: Type, tp2: Type)(implicit ctx: Context) = {
println(disambiguated(implicit ctx => s"assertion failure for ${tp1.show} <:< ${tp2.show}, frozen = $frozenConstraint"))
def explainPoly(tp: Type) = tp match {
case tp: PolyParam => ctx.echo(s"polyparam ${tp.show} found in ${tp.binder.show}")
case tp: TypeRef if tp.symbol.exists => ctx.echo(s"typeref ${tp.show} found in ${tp.symbol.owner.show}")
case tp: TypeVar => ctx.echo(s"typevar ${tp.show}, origin = ${tp.origin}")
case _ => ctx.echo(s"${tp.show} is a ${tp.getClass}")
}
explainPoly(tp1)
explainPoly(tp2)
}
/** Record statistics about the total number of subtype checks
* and the number of "successful" subtype checks, i.e. checks
* that form part of a subtype derivation tree that's ultimately successful.
*/
def recordStatistics(result: Boolean, prevSuccessCount: Int) = {
// Stats.record(s"isSubType ${tp1.show} <:< ${tp2.show}")
totalCount += 1
if (result) successCount += 1 else successCount = prevSuccessCount
if (recCount == 0) {
Stats.record("successful subType", successCount)
Stats.record("total subType", totalCount)
successCount = 0
totalCount = 0
}
}
}
object TypeComparer {
/** Show trace of comparison operations when performing `op` as result string */
def explained[T](op: Context => T)(implicit ctx: Context): String = {
val nestedCtx = ctx.fresh.setTypeComparerFn(new ExplainingTypeComparer(_))
op(nestedCtx)
nestedCtx.typeComparer.toString
}
}
/** A type comparer that can record traces of subtype operations */
class ExplainingTypeComparer(initctx: Context) extends TypeComparer(initctx) {
private var indent = 0
private val b = new StringBuilder
private var skipped = false
override def traceIndented[T](str: String)(op: => T): T =
if (skipped) op
else {
indent += 2
b append "\n" append (" " * indent) append "==> " append str
val res = op
b append "\n" append (" " * indent) append "<== " append str append " = " append show(res)
indent -= 2
res
}
private def show(res: Any) = res match {
case res: printing.Showable if !ctx.settings.Yexplainlowlevel.value => res.show
case _ => String.valueOf(res)
}
override def isSubType(tp1: Type, tp2: Type) =
traceIndented(s"${show(tp1)} <:< ${show(tp2)}${if (Config.verboseExplainSubtype) s" ${tp1.getClass} ${tp2.getClass}" else ""}${if (frozenConstraint) " frozen" else ""}") {
super.isSubType(tp1, tp2)
}
override def hasMatchingMember(name: Name, tp1: Type, tp2: RefinedType): Boolean =
traceIndented(s"hasMatchingMember(${show(tp1)} . $name, ${show(tp2.refinedInfo)}), member = ${show(tp1.member(name).info)}") {
super.hasMatchingMember(name, tp1, tp2)
}
override def lub(tp1: Type, tp2: Type) =
traceIndented(s"lub(${show(tp1)}, ${show(tp2)})") {
super.lub(tp1, tp2)
}
override def glb(tp1: Type, tp2: Type) =
traceIndented(s"glb(${show(tp1)}, ${show(tp2)})") {
super.glb(tp1, tp2)
}
override def addConstraint(param: PolyParam, bound: Type, fromBelow: Boolean): Boolean =
traceIndented(i"add constraint $param ${if (fromBelow) ">:" else "<:"} $bound $frozenConstraint, constraint = ${ctx.typerState.constraint}") {
super.addConstraint(param, bound, fromBelow)
}
override def copyIn(ctx: Context) = new ExplainingTypeComparer(ctx)
override def compareHkApply2(tp1: Type, tp2: HKApply, tycon2: Type, args2: List[Type]): Boolean = {
def addendum = ""
traceIndented(i"compareHkApply $tp1, $tp2$addendum") {
super.compareHkApply2(tp1, tp2, tycon2, args2)
}
}
override def toString = "Subtype trace:" + { try b.toString finally b.clear() }
}