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 +- test/dotc/tests.scala | 3 +- tests/disabled/t1048.scala | 14 ---- tests/neg/boundspropagation.scala | 14 ++++ tests/neg/t1048.scala | 21 ------ tests/neg/t1843.scala | 25 ------- tests/pending/pos/t1048.scala | 14 ++++ tests/pending/pos/t1843.scala | 24 ++++++ 10 files changed, 126 insertions(+), 108 deletions(-) delete mode 100644 tests/disabled/t1048.scala delete mode 100644 tests/neg/t1048.scala delete mode 100644 tests/neg/t1843.scala create mode 100644 tests/pending/pos/t1048.scala create mode 100644 tests/pending/pos/t1843.scala 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 ---------------------------- diff --git a/test/dotc/tests.scala b/test/dotc/tests.scala index 4b7d124d0..4999e5e4b 100644 --- a/test/dotc/tests.scala +++ b/test/dotc/tests.scala @@ -95,9 +95,7 @@ class tests extends CompilerTest { @Test def neg_tailcall = compileFile(negDir, "tailcall/tailrec", xerrors = 7) @Test def neg_tailcall2 = compileFile(negDir, "tailcall/tailrec-2", xerrors = 2) @Test def neg_tailcall3 = compileFile(negDir, "tailcall/tailrec-3", xerrors = 2) - @Test def neg_t1048 = compileFile(negDir, "t1048", xerrors = 1) @Test def nef_t1279a = compileFile(negDir, "t1279a", xerrors = 1) - @Test def neg_t1843 = compileFile(negDir, "t1843", xerrors = 1) @Test def neg_t1843_variances = compileFile(negDir, "t1843-variances", xerrors = 1) @Test def neg_t2660_ambi = compileFile(negDir, "t2660", xerrors = 2) @Test def neg_t2994 = compileFile(negDir, "t2994", xerrors = 2) @@ -107,6 +105,7 @@ class tests extends CompilerTest { @Test def neg_typetest = compileFile(negDir, "typetest", xerrors = 1) @Test def neg_t1569_failedAvoid = compileFile(negDir, "t1569-failedAvoid", xerrors = 1) @Test def neg_cycles = compileFile(negDir, "cycles", xerrors = 6) + @Test def neg_boundspropagation = compileFile(negDir, "boundspropagation", xerrors = 3) @Test def dotc = compileDir(dotcDir + "tools/dotc", twice)(allowDeepSubtypes) @Test def dotc_ast = compileDir(dotcDir + "tools/dotc/ast", twice) diff --git a/tests/disabled/t1048.scala b/tests/disabled/t1048.scala deleted file mode 100644 index b8694b38e..000000000 --- a/tests/disabled/t1048.scala +++ /dev/null @@ -1,14 +0,0 @@ -trait T[U] { - def x: T[_ <: U] -} - -object T { - def unapply[U](t: T[U]): Option[T[_ <: U]] = Some(t.x) -} - -object Test { - def f[W](t: T[W]) = t match { - case T(T(_)) => () - } -} - diff --git a/tests/neg/boundspropagation.scala b/tests/neg/boundspropagation.scala index 560d5416c..bc39e042e 100644 --- a/tests/neg/boundspropagation.scala +++ b/tests/neg/boundspropagation.scala @@ -24,3 +24,17 @@ object test3 { case y: Tree[_] => y } } + +// Example contributed by Jason. I believe this should not typecheck, +// even though scalac does typecheck it. +object test4 { + class Base { + type N + + class Tree[-S, -T >: Option[S]] + + def g(x: Any): Tree[_, _ <: Option[N]] = x match { + case y: Tree[_, _] => y + } + } +} diff --git a/tests/neg/t1048.scala b/tests/neg/t1048.scala deleted file mode 100644 index 4b8e78b4c..000000000 --- a/tests/neg/t1048.scala +++ /dev/null @@ -1,21 +0,0 @@ -trait T[U] { - def x: T[_ <: U] -} - -object T { - def unapply[U](t: T[U]): Option[T[_ <: U]] = Some(t.x) -} - -object Test { - def f[W](t: T[W]) = t match { - case T(T(_)) => () -// Gives: -// t1048.scala:11: error: There is no best instantiation of pattern type T[Any'] -// that makes it a subtype of selector type T[_ <: W]. -// Non-variant type variable U cannot be uniquely instantiated. -// case T(T(_)) => () -// ^ -// one error found - } -} - diff --git a/tests/neg/t1843.scala b/tests/neg/t1843.scala deleted file mode 100644 index 8504bf342..000000000 --- a/tests/neg/t1843.scala +++ /dev/null @@ -1,25 +0,0 @@ -/** -* Scala Compiler Will Crash On this File -* ... Or Will It? -* -*/ - -object Crash { - trait UpdateType[A] - case class StateUpdate[A](updateType : UpdateType[A], value : A) - case object IntegerUpdateType extends UpdateType[Integer] - - //However this method will cause a crash - def crash(updates: List[StateUpdate[_]]): Unit = { - updates match { - case Nil => - case u::us => - u match { - //Line below seems to be the crashing line - case StateUpdate(key, newValue) if (key == IntegerUpdateType) => - println("Requires a statement to induce the crash") - case _ => - } - } - } -} diff --git a/tests/pending/pos/t1048.scala b/tests/pending/pos/t1048.scala new file mode 100644 index 000000000..b8694b38e --- /dev/null +++ b/tests/pending/pos/t1048.scala @@ -0,0 +1,14 @@ +trait T[U] { + def x: T[_ <: U] +} + +object T { + def unapply[U](t: T[U]): Option[T[_ <: U]] = Some(t.x) +} + +object Test { + def f[W](t: T[W]) = t match { + case T(T(_)) => () + } +} + diff --git a/tests/pending/pos/t1843.scala b/tests/pending/pos/t1843.scala new file mode 100644 index 000000000..871b21346 --- /dev/null +++ b/tests/pending/pos/t1843.scala @@ -0,0 +1,24 @@ +/** +* Scala Compiler Will Crash On this File +* ... Or Will It? +* +*/ +object Crash { + trait UpdateType[A] + case class StateUpdate[A](updateType : UpdateType[A], value : A) + case object IntegerUpdateType extends UpdateType[Integer] + + //However this method will cause a crash + def crash(updates: List[StateUpdate[_]]): Unit = { + updates match { + case Nil => + case u::us => + u match { + //Line below seems to be the crashing line + case StateUpdate(key, newValue) if (key == IntegerUpdateType) => + println("Requires a statement to induce the crash") + case _ => + } + } + } +} -- cgit v1.2.3