diff options
Diffstat (limited to 'src/dotty/tools/dotc')
-rw-r--r-- | src/dotty/tools/dotc/core/Substituters.scala | 2 | ||||
-rw-r--r-- | src/dotty/tools/dotc/core/TypeComparer.scala | 878 | ||||
-rw-r--r-- | src/dotty/tools/dotc/core/Types.scala | 42 | ||||
-rw-r--r-- | src/dotty/tools/dotc/printing/PlainPrinter.scala | 2 |
4 files changed, 479 insertions, 445 deletions
diff --git a/src/dotty/tools/dotc/core/Substituters.scala b/src/dotty/tools/dotc/core/Substituters.scala index 02810733a..205188507 100644 --- a/src/dotty/tools/dotc/core/Substituters.scala +++ b/src/dotty/tools/dotc/core/Substituters.scala @@ -181,7 +181,7 @@ trait Substituters { this: Context => final def substThis(tp: Type, from: RefinedType, to: Type, theMap: SubstRefinedThisMap): Type = tp match { - case tp @ RefinedThis(rt) => + case tp @ RefinedThis(rt, _) => if (rt eq from) to else tp case tp: NamedType => if (tp.currentSymbol.isStatic) tp diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala index 7eb1af127..b8cc45fa7 100644 --- a/src/dotty/tools/dotc/core/TypeComparer.scala +++ b/src/dotty/tools/dotc/core/TypeComparer.scala @@ -328,7 +328,7 @@ class TypeComparer(initctx: Context) extends DotClass { } } tp.prefix match { - case RefinedThis(rt) => rebaseFrom(rt) + case RefinedThis(rt, _) => rebaseFrom(rt) case pre: ThisType => rebaseFrom(pre.cls.info) case _ => tp } @@ -357,317 +357,247 @@ class TypeComparer(initctx: Context) extends DotClass { (tp2 eq AnyType) && tp1.isValueType) return true isSubType(tp1, tp2) } - - def isSubTypeWhenFrozen(tp1: Type, tp2: Type): Boolean = { + + protected def isSubTypeWhenFrozen(tp1: Type, tp2: Type): Boolean = isSubTypeWhenFrozen(tp1, tp2, tp1) + protected def isSubTypeWhenFrozen(tp1: Type, tp2: Type, pre: Type): Boolean = { val saved = frozenConstraint frozenConstraint = true - try isSubType(tp1, tp2) + try isSubType(tp1, tp2, pre) finally frozenConstraint = saved } - def isNonBottomSubType(tp1: Type, tp2: Type): Boolean = - !(tp2 isRef NothingClass) && isSubType(tp1, tp2) - private def traceInfo(tp1: Type, tp2: Type) = s"${tp1.show} <:< ${tp2.show}" + (if (ctx.settings.verbose.value) s" ${tp1.getClass} ${tp2.getClass}${if (frozenConstraint) " frozen" else ""}" else "") + + def isSubType(tp1: Type, tp2: Type): Boolean = isSubType(tp1, tp2, tp1) + def isSubType(tp1: Type, tp2: Type, pre: Type): Boolean = /*>|>*/ ctx.traceIndented(s"isSubType ${traceInfo(tp1, tp2)}", subtyping) /*<|<*/ { - 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 < LogPendingSubTypesThreshold) firstTry(tp1, tp2) - else monitoredIsSubType(tp1, tp2) - recCount = recCount - 1 - if (!result) constraint = saved - else if (recCount == 0 && needsGc) state.gc() - - def recordStatistics = { - // Stats.record(s"isSubType ${tp1.show} <:< ${tp2.show}") - totalCount += 1 - if (result) successCount += 1 else successCount = savedSuccessCount - if (recCount == 0) { - Stats.record("successful subType", successCount) - Stats.record("total subType", totalCount) - successCount = 0 - totalCount = 0 + def firstTry(tp1: Type, tp2: Type): Boolean = { + tp2 match { + case tp2: NamedType => + def isHKSubType = tp2.name == tpnme.Apply && { + val lambda2 = tp2.prefix.LambdaClass(forcing = true) + lambda2.exists && !tp1.isLambda && + tp1.testLifted(lambda2.typeParams, isSubType(_, tp2.prefix)) } - } - if (Stats.monitored) recordStatistics - - result - } catch { - case NonFatal(ex) => - def showState = { - println(disambiguated(implicit ctx => s"assertion failure for ${tp1.show} <:< ${tp2.show}, frozen = $frozenConstraint")) - def explainPoly(tp: Type) = tp match { - case tp: PolyParam => println(s"polyparam ${tp.show} found in ${tp.binder.show}") - case tp: TypeRef if tp.symbol.exists => println(s"typeref ${tp.show} found in ${tp.symbol.owner.show}") - case tp: TypeVar => println(s"typevar ${tp.show}, origin = ${tp.origin}") - case _ => println(s"${tp.show} is a ${tp.getClass}") + def compareNamed = { + implicit val ctx: Context = this.ctx // Dotty deviation: implicits need explicit type + tp1 match { + case tp1: NamedType => + val sym1 = tp1.symbol + (if ((sym1 ne NoSymbol) && (sym1 eq tp2.symbol)) ( + ctx.erasedTypes + || sym1.isStaticOwner + || { // Implements: A # X <: B # X + // if either A =:= B (i.e. A <: B and B <: A), or the following three conditions hold: + // 1. X is a class type, + // 2. B is a class type without abstract type members. + // 3. A <: B. + // Dealiasing is taken care of elsewhere. + val pre1 = tp1.prefix + val pre2 = tp2.prefix + ( isSameType(pre1, pre2) + || sym1.isClass + && pre2.classSymbol.exists + && pre2.abstractTypeMembers.isEmpty + && isSubType(pre1, pre2) + ) + } + ) + else (tp1.name eq tp2.name) && isSameType(tp1.prefix, tp2.prefix) + ) || isHKSubType || secondTryNamed(tp1, tp2) + case tp1: ThisType if tp1.cls eq tp2.symbol.moduleClass => + isSubType(tp1.cls.owner.thisType, tp2.prefix) + case _ => + isHKSubType || secondTry(tp1, tp2) } - explainPoly(tp1) - explainPoly(tp2) } - if (ex.isInstanceOf[AssertionError]) showState - recCount -= 1 - constraint = saved - successCount = savedSuccessCount - throw ex - } - } - } - - 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}") - 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 - } - } - } - - def firstTry(tp1: Type, tp2: Type): Boolean = { - tp2 match { - case tp2: NamedType => - def isHKSubType = tp2.name == tpnme.Apply && { - val lambda2 = tp2.prefix.LambdaClass(forcing = true) - lambda2.exists && !tp1.isLambda && - tp1.testLifted(lambda2.typeParams, isSubType(_, tp2.prefix)) - } - def compareNamed = { - implicit val ctx: Context = this.ctx // Dotty deviation: implicits need explicit type + compareNamed + case tp2: ProtoType => + isMatchedByProto(tp2, tp1) + case tp2: PolyParam => + def comparePolyParam = + tp2 == tp1 || { + if (solvedConstraint && (constraint contains tp2)) isSubType(tp1, bounds(tp2).lo, pre) + else + isSubTypeWhenFrozen(tp1, bounds(tp2).lo) || { + if (isConstrained(tp2)) addConstraint(tp2, tp1.widenExpr, fromBelow = true) + else (ctx.mode is Mode.TypevarsMissContext) || secondTry(tp1, tp2) + } + } + comparePolyParam + case tp2: BoundType => + tp2 == tp1 || secondTry(tp1, tp2) + case tp2: TypeVar => + isSubType(tp1, tp2.underlying, pre) + case tp2: WildcardType => + def compareWild = tp2.optBounds match { + case TypeBounds(_, hi) => isSubType(tp1, hi, pre) + case NoType => true + } + compareWild + case tp2: LazyRef => + isSubType(tp1, tp2.ref, pre) + case tp2: AnnotatedType => + isSubType(tp1, tp2.tpe, pre) // todo: refine? + case tp2: ThisType => tp1 match { - case tp1: NamedType => - val sym1 = tp1.symbol - (if ((sym1 ne NoSymbol) && (sym1 eq tp2.symbol)) ( - ctx.erasedTypes - || sym1.isStaticOwner - || { // Implements: A # X <: B # X - // if either A =:= B (i.e. A <: B and B <: A), or the following three conditions hold: - // 1. X is a class type, - // 2. B is a class type without abstract type members. - // 3. A <: B. - // Dealiasing is taken care of elsewhere. - val pre1 = tp1.prefix - val pre2 = tp2.prefix - ( isSameType(pre1, pre2) - || sym1.isClass - && pre2.classSymbol.exists - && pre2.abstractTypeMembers.isEmpty - && isSubType(pre1, pre2) - ) - } - ) - else (tp1.name eq tp2.name) && isSameType(tp1.prefix, tp2.prefix) - ) || isHKSubType || secondTryNamed(tp1, tp2) - case tp1: ThisType if tp1.cls eq tp2.symbol.moduleClass => - isSubType(tp1.cls.owner.thisType, tp2.prefix) + 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. + tp1.cls.classInfo.selfType.derivesFrom(tp2.cls) && + tp2.cls.classInfo.selfType.derivesFrom(tp1.cls) case _ => - isHKSubType || secondTry(tp1, tp2) + secondTry(tp1, tp2) } + case tp2: SuperType => + tp1 match { + case tp1: SuperType => + isSubType(tp1.thistpe, tp2.thistpe, pre) && + isSameType(tp1.supertpe, tp2.supertpe) + case _ => + secondTry(tp1, tp2) + } + case AndType(tp21, tp22) => + isSubType(tp1, tp21, pre) && isSubType(tp1, tp22, pre) + case ErrorType => + true + case _ => + secondTry(tp1, tp2) + } + } + + def secondTry(tp1: Type, tp2: Type): Boolean = tp1 match { + case tp1: NamedType => + tp2 match { + case tp2: ThisType if tp2.cls eq tp1.symbol.moduleClass => + isSubType(tp1.prefix, tp2.cls.owner.thisType) + case _ => + secondTryNamed(tp1, tp2) } - compareNamed - case tp2: ProtoType => - isMatchedByProto(tp2, tp1) - case tp2: PolyParam => + case OrType(tp11, tp12) => + isSubType(tp11, tp2, pre) && isSubType(tp12, tp2, pre) + case tp1: PolyParam => def comparePolyParam = - tp2 == tp1 || { - if (solvedConstraint && (constraint contains tp2)) isSubType(tp1, bounds(tp2).lo) + tp1 == tp2 || { + if (solvedConstraint && (constraint contains tp1)) isSubType(bounds(tp1).lo, tp2, pre) else - isSubTypeWhenFrozen(tp1, bounds(tp2).lo) || { - if (isConstrained(tp2)) addConstraint(tp2, tp1.widenExpr, fromBelow = true) - else (ctx.mode is Mode.TypevarsMissContext) || secondTry(tp1, tp2) + isSubTypeWhenFrozen(bounds(tp1).hi, tp2, pre) || { + if (isConstrained(tp1)) + addConstraint(tp1, tp2, fromBelow = false) && { + if ((!frozenConstraint) && + (tp2 isRef defn.NothingClass) && + state.isGlobalCommittable) { + def msg = s"!!! instantiated to Nothing: $tp1, constraint = ${constraint.show}" + if (Config.flagInstantiationToNothing) assert(false, msg) + else ctx.log(msg) + } + true + } + else (ctx.mode is Mode.TypevarsMissContext) || thirdTry(tp1, tp2) } } comparePolyParam - 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 => - isSubType(tp1, tp2.ref) - case tp2: AnnotatedType => - isSubType(tp1, tp2.tpe) // todo: refine? - case tp2: ThisType => - 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. - tp1.cls.classInfo.selfType.derivesFrom(tp2.cls) && - tp2.cls.classInfo.selfType.derivesFrom(tp1.cls) - case _ => - secondTry(tp1, tp2) + case tp1: RefinedThis => + tp2 match { + case tp2: RefinedThis if tp1.binder.parent =:= tp2.binder.parent => true + case _ => thirdTry(tp1, tp2) } - case tp2: SuperType => - tp1 match { - case tp1: SuperType => - isSubType(tp1.thistpe, tp2.thistpe) && - isSameType(tp1.supertpe, tp2.supertpe) - case _ => - secondTry(tp1, tp2) + case tp1: BoundType => + tp1 == tp2 || thirdTry(tp1, tp2) + case tp1: TypeVar => + (tp1 eq tp2) || isSubType(tp1.underlying, tp2, pre) + case tp1: WildcardType => + def compareWild = tp1.optBounds match { + case TypeBounds(lo, _) => isSubType(lo, tp2, pre) + case _ => true } - case AndType(tp21, tp22) => - isSubType(tp1, tp21) && isSubType(tp1, tp22) + compareWild + case tp1: LazyRef => + isSubType(tp1.ref, tp2, pre) + case tp1: AnnotatedType => + isSubType(tp1.tpe, tp2, pre) case ErrorType => true case _ => - secondTry(tp1, tp2) + thirdTry(tp1, tp2) } - } - - def secondTry(tp1: Type, tp2: Type): Boolean = tp1 match { - case tp1: NamedType => - tp2 match { - case tp2: ThisType if tp2.cls eq tp1.symbol.moduleClass => - isSubType(tp1.prefix, tp2.cls.owner.thisType) - case _ => - secondTryNamed(tp1, tp2) - } - case OrType(tp11, tp12) => - isSubType(tp11, tp2) && isSubType(tp12, tp2) - case tp1: PolyParam => - def comparePolyParam = - tp1 == tp2 || { - if (solvedConstraint && (constraint contains tp1)) isSubType(bounds(tp1).lo, tp2) - else - isSubTypeWhenFrozen(bounds(tp1).hi, tp2) || { - if (isConstrained(tp1)) - addConstraint(tp1, tp2, fromBelow = false) && { - if ((!frozenConstraint) && - (tp2 isRef defn.NothingClass) && - state.isGlobalCommittable) { - def msg = s"!!! instantiated to Nothing: $tp1, constraint = ${constraint.show}" - if (Config.flagInstantiationToNothing) assert(false, msg) - else ctx.log(msg) - } - true - } - else (ctx.mode is Mode.TypevarsMissContext) || thirdTry(tp1, tp2) - } - } - comparePolyParam - case tp1: RefinedThis => - tp2 match { - case tp2: RefinedThis if tp1.binder.parent =:= tp2.binder.parent => true - case _ => thirdTry(tp1, tp2) - } - case tp1: BoundType => - tp1 == tp2 || thirdTry(tp1, tp2) - case tp1: TypeVar => - (tp1 eq tp2) || isSubType(tp1.underlying, tp2) - case tp1: WildcardType => - def compareWild = tp1.optBounds match { - case TypeBounds(lo, _) => isSubType(lo, tp2) - case _ => true - } - compareWild - case tp1: LazyRef => - isSubType(tp1.ref, tp2) - case tp1: AnnotatedType => - isSubType(tp1.tpe, tp2) - case ErrorType => - true - case _ => - thirdTry(tp1, tp2) - } - def secondTryNamed(tp1: NamedType, tp2: Type): Boolean = { - def tryRebase2nd = { - val tp1rebased = rebase(tp1) - if (tp1rebased ne tp1) isSubType(tp1rebased, tp2) - else thirdTry(tp1, tp2) - } - tp1.info match { - // There was the following code, which was meant to implement this logic: - // If x has type A | B, then x.type <: C if - // x.type <: C assuming x has type A, and - // x.type <: C assuming x has type B. - // But it did not work, because derivedRef would always give back the same - // type and cache the denotation. So it ended up copmparing just one branch. - // The code seems to be unncessary for the tests and does not seems to help performance. - // So it is commented out. If we ever need to come back to this, we would have - // to create unchached TermRefs in order to avoid cross talk between the branches. - /* + def secondTryNamed(tp1: NamedType, tp2: Type): Boolean = { + def tryRebase2nd = { + val tp1rebased = rebase(tp1) + if (tp1rebased ne tp1) isSubType(tp1rebased, tp2) + else thirdTry(tp1, tp2) + } + tp1.info match { + // There was the following code, which was meant to implement this logic: + // If x has type A | B, then x.type <: C if + // x.type <: C assuming x has type A, and + // x.type <: C assuming x has type B. + // But it did not work, because derivedRef would always give back the same + // type and cache the denotation. So it ended up copmparing just one branch. + // The code seems to be unncessary for the tests and does not seems to help performance. + // So it is commented out. If we ever need to come back to this, we would have + // to create unchached TermRefs in order to avoid cross talk between the branches. + /* case OrType(tp11, tp12) => val sd = tp1.denot.asSingleDenotation def derivedRef(tp: Type) = NamedType(tp1.prefix, tp1.name, sd.derivedSingleDenotation(sd.symbol, tp)) secondTry(OrType.make(derivedRef(tp11), derivedRef(tp12)), tp2) */ - case TypeBounds(lo1, hi1) => - val gbounds1 = ctx.gadt.bounds(tp1.symbol) - if (gbounds1 != null) - isSubTypeWhenFrozen(gbounds1.hi, tp2) || - (ctx.mode is Mode.GADTflexible) && - narrowGADTBounds(tp1, TypeBounds(gbounds1.lo, gbounds1.hi & tp2)) || + case TypeBounds(lo1, hi1) => + val gbounds1 = ctx.gadt.bounds(tp1.symbol) + if (gbounds1 != null) + isSubTypeWhenFrozen(gbounds1.hi, tp2, pre) || + (ctx.mode is Mode.GADTflexible) && + narrowGADTBounds(tp1, TypeBounds(gbounds1.lo, gbounds1.hi & tp2)) || tryRebase2nd - else if (lo1 eq hi1) isSubType(hi1, tp2) + else if (lo1 eq hi1) isSubType(hi1, tp2, pre) else tryRebase2nd - case _ => + case _ => tryRebase2nd + } } - } - def thirdTry(tp1: Type, tp2: Type): Boolean = tp2 match { - case tp2: NamedType => - def tryRebase3rd = { - val tp2rebased = rebase(tp2) - if (tp2rebased ne tp2) isSubType(tp1, tp2rebased) - else fourthTry(tp1, tp2) - } - def compareNamed: Boolean = tp2.info match { - case TypeBounds(lo2, hi2) => - val gbounds2 = ctx.gadt.bounds(tp2.symbol) - if (gbounds2 != null) - isSubTypeWhenFrozen(tp1, gbounds2.lo) || - (ctx.mode is Mode.GADTflexible) && - narrowGADTBounds(tp2, TypeBounds(gbounds2.lo | tp1, gbounds2.hi)) || - tryRebase3rd - else - ((frozenConstraint || !isCappable(tp1)) && isSubType(tp1, lo2) - || tryRebase3rd) + def thirdTry(tp1: Type, tp2: Type): Boolean = tp2 match { + case tp2: NamedType => + def tryRebase3rd = { + val tp2rebased = rebase(tp2) + if (tp2rebased ne tp2) isSubType(tp1, tp2rebased) + else fourthTry(tp1, tp2) + } + def compareNamed: Boolean = tp2.info match { + case TypeBounds(lo2, hi2) => + val gbounds2 = ctx.gadt.bounds(tp2.symbol) + if (gbounds2 != null) + isSubTypeWhenFrozen(tp1, gbounds2.lo, pre) || + (ctx.mode is Mode.GADTflexible) && + narrowGADTBounds(tp2, TypeBounds(gbounds2.lo | tp1, gbounds2.hi)) || + fourthTry(tp1, tp2) + else + ((frozenConstraint || !isCappable(tp1)) && isSubType(tp1, lo2, pre) + || tryRebase3rd) - 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 - } + case _ => + val cls2 = tp2.symbol + if (cls2.isClass) { + val base = tp1.baseTypeRef(cls2) + if (base.exists && (base ne tp1)) return isSubType(base, tp2, pre) + if (cls2 == defn.SingletonClass && tp1.isStable) return true + } tryRebase3rd - } - compareNamed - case tp2 @ RefinedType(parent2, name2) => - def qualifies(m: SingleDenotation) = isSubType(m.info, tp2.refinedInfo) - def memberMatches(mbr: Denotation): Boolean = mbr match { // inlined hasAltWith for performance - case mbr: SingleDenotation => qualifies(mbr) - case _ => mbr hasAltWith qualifies - } - def compareRefinedSlow: Boolean = { - def hasMatchingMember(name: Name): Boolean = /*>|>*/ ctx.traceIndented(s"hasMatchingMember($name) ${tp1.member(name).info.show}", subtyping) /*<|<*/ { + } + compareNamed + case tp2 @ RefinedType(parent2, name2) => + def qualifies(m: SingleDenotation) = isSubType(m.info, tp2.refinedInfo) + def memberMatches(mbr: Denotation): Boolean = mbr match { // inlined hasAltWith for performance + case mbr: SingleDenotation => qualifies(mbr) + case _ => mbr hasAltWith qualifies + } + def compareRefinedSlow: Boolean = { + def hasMatchingMember(name: Name): Boolean = /*>|>*/ ctx.traceIndented(s"hasMatchingMember($name) ${tp1.member(name).info.show}", subtyping) /*<|<*/ { val tp1r = rebaseQual(tp1, name) (memberMatches(narrowRefined(tp1r) member name) || @@ -684,196 +614,266 @@ class TypeComparer(initctx: Context) extends DotClass { val saved = pendingRefinedBases try { addPendingName(name2, tp2, tp2) - isSubType(tp1, parent2) + isSubType(tp1, parent2, pre) } finally pendingRefinedBases = saved } (matchesParent && ( - name2 == nme.WILDCARD - || hasMatchingMember(name2) - || fourthTry(tp1, tp2)) - || needsEtaLift(tp1, tp2) && tp1.testLifted(tp2.typeParams, isSubType(_, tp2))) - } - def compareRefined: Boolean = tp1.widen match { - case tp1 @ RefinedType(parent1, name1) if name1 == name2 && name1.isTypeName => - normalizedInfo(tp1) match { - case bounds1 @ TypeBounds(lo1, hi1) if lo1 eq hi1 => - isSubType(bounds1, tp2.refinedInfo) && { + name2 == nme.WILDCARD + || hasMatchingMember(name2) + || fourthTry(tp1, tp2)) + || needsEtaLift(tp1, tp2) && tp1.testLifted(tp2.typeParams, isSubType(_, tp2, pre))) + } + def compareRefined: Boolean = tp1.widen match { + case tp1 @ RefinedType(parent1, name1) if name1 == name2 && name1.isTypeName => + normalizedInfo(tp1) match { + case bounds1: TypeAlias => + isSubType(bounds1, tp2.refinedInfo) && { val saved = pendingRefinedBases try { addPendingName(name1, tp1, tp2) - isSubType(parent1, parent2) + isSubType(parent1, parent2, pre) } finally pendingRefinedBases = saved } - case _ => - compareRefinedSlow - } - case _ => - compareRefinedSlow - } - compareRefined - case OrType(tp21, tp22) => - eitherIsSubType(tp1, tp21, tp1, tp22) || fourthTry(tp1, tp2) - case tp2 @ MethodType(_, formals2) => - def compareMethod = tp1 match { - case tp1 @ MethodType(_, formals1) => - (tp1.signature sameParams tp2.signature) && - (if (Config.newMatch) subsumeParams(formals1, formals2, tp1.isJava, tp2.isJava) - else 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 sameParams 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 || isSubType(lo2, lo1)) && - (tp2.variance < 0 && tp1.variance <= 0 || isSubType(hi1, hi2)) - case tp1: ClassInfo => - val tt = tp1.typeRef - isSubType(lo2, tt) && isSubType(tt, hi2) - case _ => - false - } - compareTypeBounds - case ClassInfo(pre2, cls2, _, _, _) => - def compareClassInfo = tp1 match { - case ClassInfo(pre1, cls1, _, _, _) => - (cls1 eq cls2) && isSubType(pre2, pre1) - case _ => - false - } - compareClassInfo - case JavaArrayType(elem2) => - def compareJavaArray = tp1 match { - case JavaArrayType(elem1) => isSubType(elem1, elem2) - case _ => fourthTry(tp1, tp2) - } - compareJavaArray - case _ => - fourthTry(tp1, tp2) - } - - def fourthTry(tp1: Type, tp2: Type): Boolean = tp1 match { - case tp1: TypeRef => - tp1.info match { - case TypeBounds(lo1, hi1) => - isSubType(hi1, tp2) - case _ => - def isNullable(tp: Type): Boolean = tp.dealias match { - case tp: TypeRef => tp.symbol.isNullableClass - case RefinedType(parent, _) => isNullable(parent) - case AndType(tp1, tp2) => isNullable(tp1) && isNullable(tp2) - case OrType(tp1, tp2) => isNullable(tp1) || isNullable(tp2) - case _ => println(i"$tp of class ${tp.getClass} is not nullable"); false - } - (tp1.symbol eq NothingClass) && tp2.isInstanceOf[ValueType] || - (tp1.symbol eq NullClass) && isNullable(tp2) - } - case tp1: SingletonType => - isNewSubType(tp1.underlying.widenExpr, tp2) || { - // if tp2 == p.type and p: q.type then try tp1 <:< q.type as a last effort. - 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) => - isSubType(tp1, tp2i) case _ => - false + compareRefinedSlow } case _ => + compareRefinedSlow + } + compareRefined + case OrType(tp21, tp22) => + eitherIsSubType(tp1, tp21, tp1, tp22) || fourthTry(tp1, tp2) + case tp2 @ MethodType(_, formals2) => + def compareMethod = tp1 match { + case tp1 @ MethodType(_, formals1) => + (tp1.signature sameParams tp2.signature) && + (if (Config.newMatch) subsumeParams(formals1, formals2, tp1.isJava, tp2.isJava) + else matchingParams(formals1, formals2, tp1.isJava, tp2.isJava)) && + tp1.isImplicit == tp2.isImplicit && // needed? + isSubType(tp1.resultType, tp2.resultType.subst(tp2, tp1)) + case _ => false } - } - case tp1: RefinedType => + compareMethod + case tp2: PolyType => + def comparePoly = tp1 match { + case tp1: PolyType => + (tp1.signature sameParams 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, pre) + case _ => isSubType(tp1.widenExpr, restpe2, pre) + } + compareExpr + case tp2 @ TypeBounds(lo2, hi2) => + def compareTypeBounds = tp1 match { + case tp1 @ TypeBounds(lo1, hi1) => + (tp2.variance > 0 && tp1.variance >= 0 || isSubType(lo2, lo1)) && + (tp2.variance < 0 && tp1.variance <= 0 || isSubType(hi1, hi2, pre)) + case tp1: ClassInfo => + val tt = tp1.typeRef + isSubType(lo2, tt) && isSubType(tt, hi2, pre) + case _ => + false + } + compareTypeBounds + case ClassInfo(pre2, cls2, _, _, _) => + def compareClassInfo = tp1 match { + case ClassInfo(pre1, cls1, _, _, _) => + (cls1 eq cls2) && isSubType(pre2, pre1) + case _ => + false + } + compareClassInfo + case JavaArrayType(elem2) => + def compareJavaArray = tp1 match { + case JavaArrayType(elem1) => isSubType(elem1, elem2) + case _ => fourthTry(tp1, tp2) + } + compareJavaArray + case _ => + fourthTry(tp1, tp2) + } + + def fourthTry(tp1: Type, tp2: Type): Boolean = tp1 match { + case tp1: TypeRef => + tp1.info match { + case TypeBounds(lo1, hi1) => + isSubType(hi1, tp2, pre) + case _ => + def isNullable(tp: Type): Boolean = tp.dealias match { + case tp: TypeRef => tp.symbol.isNullableClass + case RefinedType(parent, _) => isNullable(parent) + case AndType(tp1, tp2) => isNullable(tp1) && isNullable(tp2) + case OrType(tp1, tp2) => isNullable(tp1) || isNullable(tp2) + case _ => println(i"$tp of class ${tp.getClass} is not nullable"); false + } + (tp1.symbol eq NothingClass) && tp2.isInstanceOf[ValueType] || + (tp1.symbol eq NullClass) && isNullable(tp2) + } + case tp1: SingletonType => + isNewSubType(tp1.underlying.widenExpr, tp2) || { + // if tp2 == p.type and p: q.type then try tp1 <:< q.type as a last effort. + tp2 match { + case tp2: TermRef => + tp2.info match { + case tp2i: TermRef => + isSubType(tp1, tp2i, pre) + case ExprType(tp2i: TermRef) if (ctx.phase.id > ctx.gettersPhase.id) => + isSubType(tp1, tp2i, pre) + case _ => + false + } + case _ => + false + } + } + case tp1: RefinedType => { val saved = pendingRefinedBases try { addPendingName(tp1.refinedName, tp1, tp1) isNewSubType(tp1.parent, tp2) } finally pendingRefinedBases = saved - } || needsEtaLift(tp2, tp1) && tp2.testLifted(tp1.typeParams, isSubType(tp1, _)) - case AndType(tp11, tp12) => - eitherIsSubType(tp11, tp2, tp12, tp2) - case JavaArrayType(elem1) => - tp2 isRef ObjectClass - case _ => - false - } + } || needsEtaLift(tp2, tp1) && tp2.testLifted(tp1.typeParams, isSubType(tp1, _, pre)) + case AndType(tp11, tp12) => + eitherIsSubType(tp11, tp2, tp12, tp2) + case JavaArrayType(elem1) => + tp2 isRef ObjectClass + case _ => + false + } - /** Returns true iff either `tp11 <:< tp21` or `tp12 <:< tp22`, trying at the same time - * to keep the constraint as wide as possible. Specifically, 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. - */ - def eitherIsSubType(tp11: Type, tp21: Type, tp12: Type, tp22: Type) = { - val preConstraint = constraint - isSubType(tp11, tp21) && { - val leftConstraint = constraint - constraint = preConstraint - if (isSubType(tp12, tp22) && !subsumes(leftConstraint, constraint, preConstraint)) - constraint = leftConstraint - true - } || isSubType(tp12, tp22) - } + /** Returns true iff either `tp11 <:< tp21` or `tp12 <:< tp22`, trying at the same time + * to keep the constraint as wide as possible. Specifically, 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. + */ + def eitherIsSubType(tp11: Type, tp21: Type, tp12: Type, tp22: Type) = { + val preConstraint = constraint + isSubType(tp11, tp21, pre) && { + val leftConstraint = constraint + constraint = preConstraint + if (isSubType(tp12, tp22, pre) && !subsumes(leftConstraint, constraint, preConstraint)) + constraint = leftConstraint + true + } || isSubType(tp12, tp22, pre) + } - /** 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 + /** Like tp1 <:< tp2, but returns false immediately if we know that + * the case was covered previously during subtyping. + */ + def isNewSubType(tp1: Type, tp2: Type): Boolean = + if (isCovered(tp1) && isCovered(tp2)) { + //println(s"useless subtype: $tp1 <:< $tp2") + false + } else isSubType(tp1, tp2, pre) + + 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}") + 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 + } + } + } + + // begin isSubType + 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 < LogPendingSubTypesThreshold) firstTry(tp1, tp2) + else monitoredIsSubType(tp1, tp2) + recCount = recCount - 1 + if (!result) constraint = saved + else if (recCount == 0 && needsGc) state.gc() + + def recordStatistics = { + // Stats.record(s"isSubType ${tp1.show} <:< ${tp2.show}") + totalCount += 1 + if (result) successCount += 1 else successCount = savedSuccessCount + if (recCount == 0) { + Stats.record("successful subType", successCount) + Stats.record("total subType", totalCount) + successCount = 0 + totalCount = 0 + } + } + if (Stats.monitored) recordStatistics + + result + } catch { + case NonFatal(ex) => + def showState = { + println(disambiguated(implicit ctx => s"assertion failure for ${tp1.show} <:< ${tp2.show}, frozen = $frozenConstraint")) + def explainPoly(tp: Type) = tp match { + case tp: PolyParam => println(s"polyparam ${tp.show} found in ${tp.binder.show}") + case tp: TypeRef if tp.symbol.exists => println(s"typeref ${tp.show} found in ${tp.symbol.owner.show}") + case tp: TypeVar => println(s"typevar ${tp.show}, origin = ${tp.origin}") + case _ => println(s"${tp.show} is a ${tp.getClass}") + } + explainPoly(tp1) + explainPoly(tp2) + } + if (ex.isInstanceOf[AssertionError]) showState + recCount -= 1 + constraint = saved + successCount = savedSuccessCount + throw ex + } } - else isSubType(tp1, tp2) + } /** A type has been covered previously in subtype checking if it * is some combination of TypeRefs that point to classes, where the diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala index b8e0a48c1..469e8ca01 100644 --- a/src/dotty/tools/dotc/core/Types.scala +++ b/src/dotty/tools/dotc/core/Types.scala @@ -761,12 +761,12 @@ object Types { def lookupRefined(name: Name)(implicit ctx: Context): Type = { def dependsOnRefinedThis(tp: Type): Boolean = tp.stripTypeVar match { - case tp @ TypeRef(RefinedThis(rt), _) if rt refines this => + case tp @ TypeRef(RefinedThis(rt, _), _) if rt refines this => tp.info match { case TypeAlias(alias) => dependsOnRefinedThis(alias) case _ => true } - case RefinedThis(rt) => rt refines this + case RefinedThis(rt, _) => rt refines this case tp: NamedType => !tp.symbol.isStatic && dependsOnRefinedThis(tp.prefix) case tp: RefinedType => dependsOnRefinedThis(tp.refinedInfo) || dependsOnRefinedThis(tp.parent) @@ -783,7 +783,7 @@ object Types { case TypeAlias(tp) if !dependsOnRefinedThis(tp) => tp case _ => NoType } - case RefinedThis(rt) => + case RefinedThis(rt, _) => rt.lookupRefined(name) case pre: WildcardType => WildcardType @@ -1741,6 +1741,40 @@ object Types { extends CachedProxyType with BindingType with ValueType { val refinedInfo: Type + + private var containsRefinedThisCache: Boolean = _ + private var containsRefinedThisKnown: Boolean = false + + def containsRefinedThis(implicit ctx: Context): Boolean = { + def recur(tp: Type, level: Int): Boolean = tp.stripTypeVar match { + case tp @ TypeRef(RefinedThis(rt, `level`), _) => + tp.info match { + case TypeAlias(alias) => recur(alias, level) + case _ => true + } + case RefinedThis(rt, `level`) => + true + case tp: NamedType => + !tp.symbol.isStatic && recur(tp.prefix, level) + case tp: RefinedType => + recur(tp.refinedInfo, level + 1) || + recur(tp.parent, level) + case tp: TypeBounds => + recur(tp.lo, level) || + recur(tp.hi, level) + case tp: AnnotatedType => + recur(tp.underlying, level) + case tp: AndOrType => + recur(tp.tp1, level) || recur(tp.tp2, level) + case _ => + false + } + if (!containsRefinedThisKnown) { + containsRefinedThisCache = recur(refinedInfo, 0) + containsRefinedThisKnown = true + } + containsRefinedThisCache + } override def underlying(implicit ctx: Context) = parent @@ -2167,7 +2201,7 @@ object Types { override def computeHash = doHash(paramNum, binder) } - case class RefinedThis(binder: RefinedType) extends BoundType with SingletonType { + case class RefinedThis(binder: RefinedType, level: Int = 0) extends BoundType with SingletonType { type BT = RefinedType override def underlying(implicit ctx: Context) = binder def copyBoundType(bt: BT) = RefinedThis(bt) diff --git a/src/dotty/tools/dotc/printing/PlainPrinter.scala b/src/dotty/tools/dotc/printing/PlainPrinter.scala index e58775b65..a125de780 100644 --- a/src/dotty/tools/dotc/printing/PlainPrinter.scala +++ b/src/dotty/tools/dotc/printing/PlainPrinter.scala @@ -207,7 +207,7 @@ class PlainPrinter(_ctx: Context) extends Printer { toText(value) case MethodParam(mt, idx) => nameString(mt.paramNames(idx)) - case RefinedThis(_) => + case RefinedThis(_, _) => "this" } } |