From 7427c671f9a5321dd13a74b5175bba512699b385 Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Fri, 21 Nov 2014 14:45:01 +0100 Subject: Fixes in TypeComparer for RefinedTypes. The previous scheme did not propagate bounds correctly. More generally, given a comparison T { X <: A } <: U { X <: B } it would errenously decompose this to T <: U, A <: B But we really need to check whether the total constraint for X in T { X <: A } subsumes the total constraint for X in T { X <: B } The new scheme propagates only if the binding in the lower type is an alias. E.g. T { X = A } <: Y { X <: B } decomposes to T { A = A } <: U, A <: B The change uncovered another bug, where in the slow path we too a member relative to a refined type; We need to "narrow" the type to a RefinedThis instead. (See use of "narrow" in TypeComparer). That change uncovered a third bug concerning the underlying type of a RefinedThis. The last bug was fixed in a previous commit (84f32cd814f2e07725b6ad1f6bff23d4ee38c397). Two tests (1048, 1843) which were pos tests for scalac but failed compling in dotc have changed their status and location. They typecheck now, but fail later. They have been moved to pending. There's a lot of diagnostic code in TypeComparer to figure out the various problems. I left it in to be able to come back to the commit in case there are more problems. The checks and diagnostics will be removed in a subsequent commit. --- src/dotty/tools/dotc/core/TypeComparer.scala | 108 ++++++++++++++++----------- src/dotty/tools/dotc/core/TypeOps.scala | 4 +- src/dotty/tools/dotc/core/Types.scala | 7 +- 3 files changed, 73 insertions(+), 46 deletions(-) (limited to 'src/dotty/tools/dotc') diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala index 52abc99a3..51c6f7271 100644 --- a/src/dotty/tools/dotc/core/TypeComparer.scala +++ b/src/dotty/tools/dotc/core/TypeComparer.scala @@ -307,6 +307,11 @@ class TypeComparer(initctx: Context) extends DotClass { } } + private def narrowRefined(tp: Type): Type = tp match { + case tp: RefinedType => RefinedThis(tp) + case _ => tp + } + /** If the prefix of a named type is `this` (i.e. an instance of type * `ThisType` or `RefinedThis`), and there is a refinement type R that * "refines" (transitively contains as its parent) a class reference @@ -650,52 +655,71 @@ class TypeComparer(initctx: Context) extends DotClass { } 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) + || + { // special case for situations like: + // foo <: C { type T = foo.T } + tp2.refinedInfo match { + case TypeBounds(lo, hi) if lo eq hi => + !ctx.phase.erasedTypes && (tp1r select name) =:= lo + case _ => false + } + }) + } + val matchesParent = { + val saved = pendingRefinedBases + try { + addPendingName(name2, tp2, tp2) + isSubType(tp1, parent2) + } 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 => - // optimized case; all info on tp1.name1 is in refinement tp1.refinedInfo. - isSubType(normalizedInfo(tp1), tp2.refinedInfo) && { - val saved = pendingRefinedBases - try { - addPendingName(name1, tp1, tp2) - isSubType(parent1, parent2) - } - finally pendingRefinedBases = saved + normalizedInfo(tp1) match { + case bounds1 @ TypeBounds(lo1, hi1) => + val fastResult = isSubType(bounds1, tp2.refinedInfo) && { + val saved = pendingRefinedBases + try { + addPendingName(name1, tp1, tp2) + isSubType(parent1, parent2) + } finally pendingRefinedBases = saved + } + if (lo1 eq hi1) fastResult + else { + val slowResult = compareRefinedSlow + if (fastResult != slowResult) { + println(i"!!! difference for $tp1 <: $tp2, fast = $fastResult, ${memberMatches(tp1.member(name1))}, slow = $slowResult ${lo1.getClass} ${hi1.getClass}") + println(TypeComparer.explained(implicit ctx => tp1 <:< parent2)) + val tp1r = rebaseQual(tp1, name1) + println(s"rebased = $tp1r / ${narrowRefined(tp1r)}") + val mbr = narrowRefined(tp1r) member name1 + println(i"member = $mbr : ${mbr.info} / ${mbr.getClass}") + val mbr2 = (tp1r) member name1 + println(i"member = $mbr2 : ${mbr2.info} / ${mbr2.getClass}") + println(TypeComparer.explained(implicit ctx => mbr.info <:< tp2.refinedInfo)) + compareRefinedSlow + } + slowResult + } + case _ => + compareRefinedSlow } case _ => - 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 hasMatchingMember(name: Name): Boolean = /*>|>*/ ctx.traceIndented(s"hasMatchingMember($name) ${tp1.member(name).info.show}", subtyping) /*<|<*/ { - val tp1r = rebaseQual(tp1, name) - ( memberMatches(tp1r member name) - || - { // special case for situations like: - // foo <: C { type T = foo.T } - tp2.refinedInfo match { - case TypeBounds(lo, hi) if lo eq hi => - !ctx.phase.erasedTypes && (tp1r select name) =:= lo - case _ => false - } - } - ) - } - val matchesParent = { - val saved = pendingRefinedBases - try { - addPendingName(name2, tp2, tp2) - isSubType(tp1, parent2) - } - finally pendingRefinedBases = saved - } - ( matchesParent && ( - name2 == nme.WILDCARD - || hasMatchingMember(name2) - || fourthTry(tp1, tp2) - ) - || needsEtaLift(tp1, tp2) && tp1.testLifted(tp2.typeParams, isSubType(_, tp2)) - ) + compareRefinedSlow } compareRefined case OrType(tp21, tp22) => diff --git a/src/dotty/tools/dotc/core/TypeOps.scala b/src/dotty/tools/dotc/core/TypeOps.scala index 1ef997684..687ca9ef0 100644 --- a/src/dotty/tools/dotc/core/TypeOps.scala +++ b/src/dotty/tools/dotc/core/TypeOps.scala @@ -12,7 +12,7 @@ trait TypeOps { this: Context => final def asSeenFrom(tp: Type, pre: Type, cls: Symbol, theMap: AsSeenFromMap): Type = { - def toPrefix(pre: Type, cls: Symbol, thiscls: ClassSymbol): Type = /*>|>*/ ctx.debugTraceIndented(s"toPrefix($pre, $cls, $thiscls)") /*<|<*/ { + def toPrefix(pre: Type, cls: Symbol, thiscls: ClassSymbol): Type = /*>|>*/ ctx.conditionalTraceIndented(TypeOps.track, s"toPrefix($pre, $cls, $thiscls)") /*<|<*/ { if ((pre eq NoType) || (pre eq NoPrefix) || (cls is PackageClass)) tp else if (thiscls.derivesFrom(cls) && pre.baseTypeRef(thiscls).exists) @@ -24,7 +24,7 @@ trait TypeOps { this: Context => toPrefix(pre.baseTypeRef(cls).normalizedPrefix, cls.owner, thiscls) } - /*>|>*/ ctx.conditionalTraceIndented(TypeOps.track , s"asSeen ${tp.show} from (${pre.show}, ${cls.show})", show = true) /*<|<*/ { // !!! DEBUG + /*>|>*/ ctx.conditionalTraceIndented(TypeOps.track, s"asSeen ${tp.show} from (${pre.show}, ${cls.show})", show = true) /*<|<*/ { // !!! DEBUG tp match { case tp: NamedType => val sym = tp.symbol diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala index 57aca3c5e..33d108540 100644 --- a/src/dotty/tools/dotc/core/Types.scala +++ b/src/dotty/tools/dotc/core/Types.scala @@ -719,8 +719,11 @@ object Types { case _ => Nil } - /** A prefix-less termRef to a new skolem symbol that has the given type as info */ - def narrow(implicit ctx: Context): TermRef = TermRef(NoPrefix, ctx.newSkolem(this)) + /** A prefix-less refined this or a termRef to a new skolem symbol + * that has the given type as info + */ + def narrow(implicit ctx: Context): TermRef = + TermRef(NoPrefix, ctx.newSkolem(this)) // ----- Normalizing typerefs over refined types ---------------------------- -- cgit v1.2.3