From 7c40b03aa9210dc1989cc08c0f03f7d4dd4e9e47 Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Sun, 21 Dec 2014 12:59:28 +0100 Subject: test reorg Moved working tests to pos, annotated non-working ones. --- tests/pending/pos/bounds.scala | 11 ----------- tests/pending/pos/caseClassInMethod.scala | 5 ----- tests/pending/pos/channels.scala | 4 +++- tests/pending/pos/class-dependent-extension-method.scala | 3 --- 4 files changed, 3 insertions(+), 20 deletions(-) delete mode 100644 tests/pending/pos/bounds.scala delete mode 100644 tests/pending/pos/caseClassInMethod.scala delete mode 100644 tests/pending/pos/class-dependent-extension-method.scala (limited to 'tests/pending') diff --git a/tests/pending/pos/bounds.scala b/tests/pending/pos/bounds.scala deleted file mode 100644 index 26bc84a1b..000000000 --- a/tests/pending/pos/bounds.scala +++ /dev/null @@ -1,11 +0,0 @@ -trait Map[A, +C] { - def ++ [B1 >: C] (kvs: Iterable[Tuple2[A, B1]]): Map[A, B1] = this - def ++ [B1 >: C] (kvs: Iterator[Tuple2[A, B1]]): Map[A, B1] = this -} - -class ListMap[A, +B] extends Map[A, B] {} - -object ListMap { - def empty[X, Y] = new ListMap[X, Y] - def apply[A1, B2](elems: Tuple2[A1, B2]*): Map[A1, B2] = empty[A1,B2].++(elems.iterator) -} diff --git a/tests/pending/pos/caseClassInMethod.scala b/tests/pending/pos/caseClassInMethod.scala deleted file mode 100644 index 958e5dd47..000000000 --- a/tests/pending/pos/caseClassInMethod.scala +++ /dev/null @@ -1,5 +0,0 @@ -object t { - def f = { object C; case class C(); 1 } - // pending: def g = { case class D(x: Int); object D; 2 } - def h = { case class E(y: Int = 10); 3 } -} diff --git a/tests/pending/pos/channels.scala b/tests/pending/pos/channels.scala index b2f0cdc32..77736305f 100644 --- a/tests/pending/pos/channels.scala +++ b/tests/pending/pos/channels.scala @@ -1,3 +1,5 @@ +// To compile this test, we need some more elaborate GADT capabilities. +// Not sure yet we should invest to get them. class Channel[a] import collection.mutable.Set @@ -16,7 +18,7 @@ object Test extends App { def f[b](x: ![b]): Int = x match { case send: ![c] => send.chan match { - case IC => send.data + case IC => send.data // Here, from the fact that `chan` is an IC, we need to conclude that `c` is Int. } } } diff --git a/tests/pending/pos/class-dependent-extension-method.scala b/tests/pending/pos/class-dependent-extension-method.scala deleted file mode 100644 index b557dfa8f..000000000 --- a/tests/pending/pos/class-dependent-extension-method.scala +++ /dev/null @@ -1,3 +0,0 @@ -class C(val a: String) extends AnyVal { - def foo[U <: a.type]: Unit = foo[U] -} -- cgit v1.2.3 From e3a43806a2b5b17982e942a82cabe139c09d971e Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Thu, 1 Jan 2015 13:45:08 +0100 Subject: Reorg of subtyping. Plus, RefinedThis gets a second parameter, `level`. This will replace the first one in due time. --- src/dotty/tools/dotc/core/Substituters.scala | 2 +- src/dotty/tools/dotc/core/TypeComparer.scala | 878 +++++++++++------------ src/dotty/tools/dotc/core/Types.scala | 42 +- src/dotty/tools/dotc/printing/PlainPrinter.scala | 2 +- tests/pending/pos/compound.scala | 4 + tests/pending/pos/subtypcycle.scala | 10 + tests/pos/Patterns.scala | 2 +- tests/pos/refinedSubtyping.scala | 11 + 8 files changed, 505 insertions(+), 446 deletions(-) create mode 100644 tests/pending/pos/subtypcycle.scala (limited to 'tests/pending') 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" } } diff --git a/tests/pending/pos/compound.scala b/tests/pending/pos/compound.scala index 60890f910..308ffdfd9 100644 --- a/tests/pending/pos/compound.scala +++ b/tests/pending/pos/compound.scala @@ -7,3 +7,7 @@ abstract class Test { var xx: A with B { type T; val xz: T } = null; xx = yy; } +abstract class Test2 { + var yy: A with B { type T; val xz: T } = null; + val xx: A with B { type T; val xz: T } = yy +} diff --git a/tests/pending/pos/subtypcycle.scala b/tests/pending/pos/subtypcycle.scala new file mode 100644 index 000000000..76eb7ffec --- /dev/null +++ b/tests/pending/pos/subtypcycle.scala @@ -0,0 +1,10 @@ +object subtypcycle { + trait Y { + type A <: { type T >: B } + type B >: { type T >: A } + } + + val y: Y = ??? + val a: y.A = ??? + val b: y.B = a +} diff --git a/tests/pos/Patterns.scala b/tests/pos/Patterns.scala index 54c4d8ab2..98af1cddb 100644 --- a/tests/pos/Patterns.scala +++ b/tests/pos/Patterns.scala @@ -6,7 +6,7 @@ object Patterns { private def rebase(tp: NamedType): Type = { def rebaseFrom(prefix: Type): Type = ??? tp.prefix match { - case RefinedThis(rt) => rebaseFrom(rt) + case RefinedThis(rt, _) => rebaseFrom(rt) case pre: ThisType => rebaseFrom(pre) case _ => tp } diff --git a/tests/pos/refinedSubtyping.scala b/tests/pos/refinedSubtyping.scala index a01be181d..329c62314 100644 --- a/tests/pos/refinedSubtyping.scala +++ b/tests/pos/refinedSubtyping.scala @@ -60,3 +60,14 @@ class Test3 { y = x } +/* Does not work yet: +class Test4 { + + abstract class A { type T; val xz: Any } + + val yy: A { val xz: T } = null; +// val xx: A { val xz: T } = null; + val zz: A { val xz: T } = yy; + +} +*/ -- cgit v1.2.3 From 0a35baa8a1ed91a71398887ae7a1a08910e4faf0 Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Thu, 8 Jan 2015 11:36:32 +0100 Subject: New scheme for subtyping refined types. - Instead of rebasing, use the DeBrujn level of a RefiendThis. - Make sure lower type is a singleton by skolemizing it if necessary. - Do the correct rebinding of the upper type's RefinedThis. Remarks: - The new scheme discovered quite a lot of errors which are mostly fixded in other commits of this branch. i0268 (GADT matching) still does not work, moved to pending. - Some optimizations are currently missing: (1) fast path refined subtyping (2) faster operations for substituting refined thistypes which explot the fact that RefinedThis is relatively rare. --- src/dotty/tools/dotc/core/TypeComparer.scala | 187 +++++++++++++++++++-------- src/dotty/tools/dotc/typer/Implicits.scala | 5 +- tests/pending/pos/i0268.scala | 15 +++ tests/pos/i0268.scala | 15 --- 4 files changed, 154 insertions(+), 68 deletions(-) create mode 100644 tests/pending/pos/i0268.scala delete mode 100644 tests/pos/i0268.scala (limited to 'tests/pending') diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala index 9807af901..1a873c348 100644 --- a/src/dotty/tools/dotc/core/TypeComparer.scala +++ b/src/dotty/tools/dotc/core/TypeComparer.scala @@ -25,6 +25,9 @@ class TypeComparer(initctx: Context) extends DotClass { private var pendingSubTypes: mutable.Set[(Type, Type)] = null private var recCount = 0 + var newScheme = true + var cmpSchemes = false + /** If the constraint is frozen we cannot add new bounds to the constraint. */ protected var frozenConstraint = false @@ -185,7 +188,7 @@ class TypeComparer(initctx: Context) extends DotClass { finally ignoreConstraint = saved val res = (param == bound) || (oldBounds eq newBounds) || updateConstraint(param, newBounds) - constr.println(s"added1 constraint $param ${if (fromBelow) ">:" else "<:"} $bound = $res") + //constr.println(s"added1 constraint $param ${if (fromBelow) ">:" else "<:"} $bound = $res") if (res) constr.println(constraint.show) res } @@ -210,33 +213,43 @@ class TypeComparer(initctx: Context) extends DotClass { */ def addConstraint(param: PolyParam, bound0: Type, fromBelow: Boolean): Boolean = { assert(!frozenConstraint) - val bound = bound0.dealias.stripTypeVar - def description = s"${param.show} ${if (fromBelow) ">:>" else "<:<"} ${bound.show} (${bound.getClass}) to ${constraint.show}" - constr.println(s"adding $description") - val res = bound match { - case bound: PolyParam if constraint contains bound => - val TypeBounds(lo, hi) = constraint.bounds(bound) - if (lo eq hi) - addConstraint(param, lo, fromBelow) - else if (param == bound) + def recur(bound0: Type): Boolean = { + assert(bound0.exists) + val bound = bound0.dealias.stripTypeVar + def description = s"${param.show} ${if (fromBelow) ">:>" else "<:<"} ${bound.show} (${bound.getClass}) to ${constraint.show}" + constr.println(s"adding $description") + constraint.bounds(param) match { + case TypeBounds(plo: PolyParam, phi) if constraint.contains(plo) && (plo eq phi) => + addConstraint(plo, bound, fromBelow) + case _ => + + val res = bound match { + case bound: PolyParam if constraint contains bound => + val TypeBounds(lo, hi) = constraint.bounds(bound) + if (lo eq hi) + addConstraint(param, lo, fromBelow) + else if (param == bound) + true + else if (fromBelow && param.occursIn(lo, fromBelow = true)) + unify(param, bound) + else if (!fromBelow && param.occursIn(hi, fromBelow = false)) + unify(bound, param) + else + addConstraint1(param, bound, fromBelow) && + addConstraint1(bound, param, !fromBelow) + case bound: AndOrType if fromBelow != bound.isAnd => + addConstraint(param, bound.tp1, fromBelow) && + addConstraint(param, bound.tp2, fromBelow) + case bound: WildcardType => true - else if (fromBelow && param.occursIn(lo, fromBelow = true)) - unify(param, bound) - else if (!fromBelow && param.occursIn(hi, fromBelow = false)) - unify(bound, param) - else - addConstraint1(param, bound, fromBelow) && - addConstraint1(bound, param, !fromBelow) - case bound: AndOrType if fromBelow != bound.isAnd => - addConstraint(param, bound.tp1, fromBelow) && - addConstraint(param, bound.tp2, fromBelow) - case bound: WildcardType => - true - case bound => // !!! remove to keep the originals - addConstraint1(param, bound, fromBelow) - } - constr.println(s"added $description = ${constraint.show}") - res + case bound => // !!! remove to keep the originals + addConstraint1(param, bound, fromBelow) + } + constr.println(s"added $description") + if (Config.checkConstraintsNonCyclicTrans) constraint.checkNonCyclicTrans() + res + }} + recur(bound0) // ctx.deSkolemize(bound0, toSuper = fromBelow)) } def isConstrained(param: PolyParam): Boolean = @@ -322,7 +335,8 @@ class TypeComparer(initctx: Context) extends DotClass { case _ => tp } } - tp.prefix match { + if (newScheme) tp + else tp.prefix match { case RefinedThis(rt, _) => rebaseFrom(rt) case pre: ThisType => rebaseFrom(pre.cls.info) case _ => tp @@ -350,7 +364,27 @@ class TypeComparer(initctx: Context) extends DotClass { if ((tp2 eq tp1) || (tp2 eq WildcardType) || (tp2 eq AnyType) && tp1.isValueType) return true - isSubType(tp1, tp2) + val saved = newScheme + try { + if (cmpSchemes) { + newScheme = false + val old = isSubType(tp1, tp2) + newScheme = true + val now = isSubType(tp1, tp2) + if (old != now) { + println(i"subtyping discrepancy for $tp1 <:< $tp2, was $old, now $now") + println(TypeComparer.explained(implicit ctx => { + ctx.typeComparer.newScheme = true + ctx.typeComparer.isSubType(tp1, tp2) + })) + println("================\nwhere previously:") + println(TypeComparer.explained(implicit ctx => ctx.typeComparer.isSubType(tp1, tp2))) + } + now + } + else isSubType(tp1, tp2) + } + finally newScheme = saved } protected def isSubTypeWhenFrozen(tp1: Type, tp2: Type): Boolean = { @@ -366,7 +400,7 @@ class TypeComparer(initctx: Context) extends DotClass { def isSubType(orig1: Type, orig2: Type): Boolean = { - def ctdSubType(tp1: Type, tp2: Type): Boolean = /*>|>*/ ctx.traceIndented(s"isSubType ${traceInfo(orig1, tp2)}, orig1 = ${orig1.show}, class2 = ${tp2.getClass}", subtyping) /*<|<*/ { + def ctdSubType(tp1: Type, tp2: Type): Boolean = /*>|>*/ ctx.traceIndented(s"isSubType ${traceInfo(tp1, tp2)}, class1 = ${tp1.getClass}, class2 = ${tp2.getClass}", subtyping) /*<|<*/ { if (tp2 eq NoType) false else if (tp1 eq tp2) true else { @@ -530,13 +564,13 @@ class TypeComparer(initctx: Context) extends DotClass { secondTryNamed(tp1, tp2) } case OrType(tp11, tp12) => - ctdSubType(tp11, tp2) && ctdSubType(tp12, tp2) + isSubType(tp11, tp2) && isSubType(tp12, tp2) case tp1: PolyParam => def comparePolyParam = tp1 == tp2 || { - if (solvedConstraint && (constraint contains tp1)) ctdSubType(bounds(tp1).lo, tp2) + if (solvedConstraint && (constraint contains tp1)) isSubType(bounds(tp1).lo, tp2) else - ctdSubTypeWhenFrozen(bounds(tp1).hi, tp2) || { + isSubTypeWhenFrozen(bounds(tp1).hi, tp2) || { if (isConstrained(tp1)) addConstraint(tp1, tp2, fromBelow = false) && { if ((!frozenConstraint) && @@ -554,23 +588,25 @@ class TypeComparer(initctx: Context) extends DotClass { comparePolyParam case tp1: RefinedThis => tp2 match { - case tp2: RefinedThis if tp1.binder.parent =:= tp2.binder.parent => true - case _ => thirdTry(tp1, tp2) + case tp2: RefinedThis + if (if (newScheme) tp1.level == tp2.level + else 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) || ctdSubType(tp1.underlying, tp2) + (tp1 eq tp2) || isSubType(tp1.underlying, tp2) case tp1: WildcardType => def compareWild = tp1.optBounds match { - case TypeBounds(lo, _) => ctdSubType(lo, tp2) + case TypeBounds(lo, _) => isSubType(lo, tp2) case _ => true } compareWild case tp1: LazyRef => - ctdSubType(tp1.ref, tp2) + isSubType(tp1.ref, tp2) case tp1: AnnotatedType => - ctdSubType(tp1.tpe, tp2) + isSubType(tp1.tpe, tp2) case ErrorType => true case _ => @@ -604,9 +640,8 @@ class TypeComparer(initctx: Context) extends DotClass { val gbounds1 = ctx.gadt.bounds(tp1.symbol) if (gbounds1 != null) ctdSubTypeWhenFrozen(gbounds1.hi, tp2) || - (ctx.mode is Mode.GADTflexible) && - narrowGADTBounds(tp1, TypeBounds(gbounds1.lo, gbounds1.hi & tp2)) || - tryRebase2nd + narrowGADTBounds(tp1, tp2, fromBelow = false) || + tryRebase2nd else if (lo1 eq hi1) ctdSubType(hi1, tp2) else tryRebase2nd case _ => @@ -626,9 +661,8 @@ class TypeComparer(initctx: Context) extends DotClass { val gbounds2 = ctx.gadt.bounds(tp2.symbol) if (gbounds2 != null) ctdSubTypeWhenFrozen(tp1, gbounds2.lo) || - (ctx.mode is Mode.GADTflexible) && - narrowGADTBounds(tp2, TypeBounds(gbounds2.lo | tp1, gbounds2.hi)) || - fourthTry(tp1, tp2) + narrowGADTBounds(tp2, tp1, fromBelow = true) || + fourthTry(tp1, tp2) else ((frozenConstraint || !isCappable(tp1)) && ctdSubType(tp1, lo2) || tryRebase3rd) @@ -651,7 +685,7 @@ class TypeComparer(initctx: Context) extends DotClass { } def compareRefinedSlow: Boolean = { def hasMatchingMember(name: Name): Boolean = /*>|>*/ ctx.traceIndented(s"hasMatchingMember($name) ${tp1.member(name).info.show}", subtyping) /*<|<*/ { - val tp1r = rebaseQual(tp1, name) + val tp1r = rebaseQual(tp1, name) //val old = memberMatches(narrowRefined(tp1r) member name) //val now = memberMatches(orig1.ensureSingleton member name) //if (old != now) @@ -679,9 +713,20 @@ class TypeComparer(initctx: Context) extends DotClass { name2 == nme.WILDCARD || hasMatchingMember(name2) || fourthTry(tp1, tp2)) - || needsEtaLift(tp1, tp2) && tp1.testLifted(tp2.typeParams, ctdSubType(_, tp2))) + || needsEtaLift(tp1, tp2) && tp1.testLifted(tp2.typeParams, ctdSubType(_, tp2))) } - def compareRefined: Boolean = tp1.widen match { + def compareRefined: Boolean = + if (newScheme) { + val normalPath = + ctdSubType(tp1, parent2) && ( + name2 == nme.WILDCARD + || hasMatchingMember(name2, tp1, tp2) + || fourthTry(tp1, tp2) + ) + normalPath || + needsEtaLift(tp1, tp2) && tp1.testLifted(tp2.typeParams, isSubType(_, tp2)) + } + else tp1.widen match { case tp1 @ RefinedType(parent1, name1) if name1 == name2 && name1.isTypeName => normalizedInfo(tp1) match { case bounds1: TypeAlias => @@ -892,6 +937,26 @@ class TypeComparer(initctx: Context) extends DotClass { ctdSubType(orig1, orig2) } + def hasMatchingMember(name: Name, orig1: Type, tp2: RefinedType): Boolean = /*>|>*/ ctx.traceIndented(s"hasMatchingMember($orig1 . $name, ${tp2.refinedInfo}) ${orig1.member(name).info.show}", subtyping) /*<|<*/ { + val base = orig1.ensureSingleton + var rinfo2 = tp2.refinedInfo.substRefinedThis(0, base) + def qualifies(m: SingleDenotation) = isSubType(m.info, rinfo2) + def memberMatches(mbr: Denotation): Boolean = mbr match { // inlined hasAltWith for performance + case mbr: SingleDenotation => qualifies(mbr) + case _ => mbr hasAltWith qualifies + } + memberMatches(base member name) || + orig1.isInstanceOf[SingletonType] && + { // special case for situations like: + // foo <: C { type T = foo.T } + rinfo2 match { + case rinfo2: TypeAlias => + !ctx.phase.erasedTypes && (base select name) =:= rinfo2.alias + case _ => false + } + } + } + /** 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, AndTypes or AnnotatedTypes. @@ -931,15 +996,28 @@ class TypeComparer(initctx: Context) extends DotClass { } /** Does `tp` need to be eta lifted to be comparable to `target`? */ - def needsEtaLift(tp: Type, target: RefinedType) = { + def needsEtaLift(tp: Type, target: RefinedType): Boolean = { + //default.echo(i"needs eta $tp $target?", { val name = target.refinedName (name.isLambdaArgName || (name eq tpnme.Apply)) && target.isLambda && tp.exists && !tp.isLambda + //}) } - def narrowGADTBounds(tr: NamedType, bounds: TypeBounds): Boolean = - isSubType(bounds.lo, bounds.hi) && - { ctx.gadt.setBounds(tr.symbol, bounds); true } + def narrowGADTBounds(tr: NamedType, bound: Type, fromBelow: Boolean): Boolean = + ctx.mode.is(Mode.GADTflexible) && { + val tparam = tr.symbol + val bound1 = bound // ctx.deSkolemize(bound, toSuper = fromBelow) + println(s"narrow gadt bound of $tparam: ${tparam.info} from ${if (fromBelow) "below" else "above"} to $bound1 ${bound1.isRef(tparam)}") + !bound1.isRef(tparam) && { + val oldBounds = ctx.gadt.bounds(tparam) + val newBounds = + if (fromBelow) TypeBounds(oldBounds.lo | bound1, oldBounds.hi) + else TypeBounds(oldBounds.lo, oldBounds.hi & bound1) + isSubType(newBounds.lo, newBounds.hi) && + { ctx.gadt.setBounds(tparam, newBounds); true } + } + } // Tests around `matches` @@ -1484,6 +1562,11 @@ class ExplainingTypeComparer(initctx: Context) extends TypeComparer(initctx) { super.isSubType(tp1, tp2) } + override def hasMatchingMember(name: Name, orig1: Type, tp2: RefinedType): Boolean = + traceIndented(s"hasMatchingMember(${show(orig1)} . $name, ${show(tp2.refinedInfo)}), member = ${show(orig1.member(name).info)}") { + super.hasMatchingMember(name, orig1, tp2) + } + override def lub(tp1: Type, tp2: Type) = traceIndented(s"lub(${show(tp1)}, ${show(tp2)})") { super.lub(tp1, tp2) diff --git a/src/dotty/tools/dotc/typer/Implicits.scala b/src/dotty/tools/dotc/typer/Implicits.scala index 82424164a..93043610e 100644 --- a/src/dotty/tools/dotc/typer/Implicits.scala +++ b/src/dotty/tools/dotc/typer/Implicits.scala @@ -450,7 +450,10 @@ trait Implicits { self: Typer => private def nestedContext = ctx.fresh.setMode(ctx.mode &~ Mode.ImplicitsEnabled) private def implicitProto(resultType: Type, f: Type => Type) = - if (argument.isEmpty) f(resultType) else ViewProto(f(argument.tpe.widen), f(resultType)) + if (argument.isEmpty) f(resultType) else ViewProto(f(argument.tpe/*.widen*/), f(resultType)) + // !!! TODO: check performance implications + // If we do the widen, SyntheticMethods, line 66 fails to compile + // val synthetic = sym.copy(...) assert(argument.isEmpty || argument.tpe.isValueType || argument.tpe.isInstanceOf[ExprType], d"found: ${argument.tpe}, expected: $pt") diff --git a/tests/pending/pos/i0268.scala b/tests/pending/pos/i0268.scala new file mode 100644 index 000000000..6ac0c5c90 --- /dev/null +++ b/tests/pending/pos/i0268.scala @@ -0,0 +1,15 @@ +package typespatmat + +sealed trait Box2[T] +final case class Int2(x: Int) extends Box2[Int] +final case class Str2(x: String) + extends Box2[String] +final case class Gen[T](x: T) extends Box2[T] + +object Box2 { + def double2[T](x: Box2[T]): T = x match { + case Int2(i) => i * 2 + case Str2(s) => s + s + case Gen(x) => x + } +} diff --git a/tests/pos/i0268.scala b/tests/pos/i0268.scala deleted file mode 100644 index 6ac0c5c90..000000000 --- a/tests/pos/i0268.scala +++ /dev/null @@ -1,15 +0,0 @@ -package typespatmat - -sealed trait Box2[T] -final case class Int2(x: Int) extends Box2[Int] -final case class Str2(x: String) - extends Box2[String] -final case class Gen[T](x: T) extends Box2[T] - -object Box2 { - def double2[T](x: Box2[T]): T = x match { - case Int2(i) => i * 2 - case Str2(s) => s + s - case Gen(x) => x - } -} -- cgit v1.2.3 From 979ff5e0dbffc66fd008be0544690dbd194fe066 Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Thu, 8 Jan 2015 11:40:59 +0100 Subject: Simplify and fix bounds propagation in constraints. The previous scheme did not ensure that transitivity was eliminated. Example scenario: We have in the constraint P <: Q for constrained variables P, Q and add Q <: T Previous propagation added the constraint and then tested whether the bounds of all variables were satisfiable. For Q we test P <: T but that is true because P <: Q and we already added the constraint Q <: T. So we fail to add the constraint P <: T, and transitivity is no longer eliminated. Instead we now test the new bounds (in this case P <: T) *before* adding the new constraint Q <: T. This is also simpler than the previous scheme. --- src/dotty/tools/dotc/core/TypeComparer.scala | 263 +++++++++++++++------------ test/dotc/tests.scala | 2 +- tests/pending/pos/t0674.scala | 49 +++++ tests/pos/t0674.scala | 48 ----- 4 files changed, 196 insertions(+), 166 deletions(-) create mode 100644 tests/pending/pos/t0674.scala delete mode 100644 tests/pos/t0674.scala (limited to 'tests/pending') diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala index 1a873c348..25c53e39c 100644 --- a/src/dotty/tools/dotc/core/TypeComparer.scala +++ b/src/dotty/tools/dotc/core/TypeComparer.scala @@ -43,6 +43,14 @@ class TypeComparer(initctx: Context) extends DotClass { protected var solvedConstraint = false private var needsGc = false + + /** Bounds for constrained parameters yet to be added to the constraint */ + private var pendingBoundss: SimpleMap[PolyParam, TypeBounds] = SimpleMap.Empty + + /** If `param` is in `needsSatCheck` then the constraint should be checked + * for satisfiability after `param`'s bound are updated. + */ + private var needsSatCheck: Set[PolyParam] = Set() /** Is a subtype check in course? In that case we may not * permanently instantiate type variables, because the corresponding @@ -89,7 +97,30 @@ class TypeComparer(initctx: Context) extends DotClass { myAnyType } - // Constraint handling + /* Constraint handling: + * + * Constraints are required to be in normalized form. This means + * (1) if P <: Q in C then also Q >: P in C + * (2) if P r Q in C and Q r R in C then also P r R in C, where r is <: or :> + * + * "P <: Q in C" means here: There is a constraint P <: H[Q], + * where H is the multi-hole context given by: + * + * H = [] + * H & T + * T & H + * H | H + * + * (the idea is that a parameter Q in a H context is guaranteed to be a supertype of P). + * + * "P >: Q in C" means: There is a constraint P >: L[Q], + * where L is the multi-hole context given by: + * + * L = [] + * L | T + * T | L + * L & L + */ /** Map that approximates each param in constraint by its lower bound. * Currently only used for diagnostics. @@ -103,96 +134,24 @@ class TypeComparer(initctx: Context) extends DotClass { } } - /** If `param` is contained in constraint, test whether its - * bounds are non-empty. Otherwise return `true`. - */ - private def checkBounds(param: PolyParam): Boolean = constraint.at(param) match { - case TypeBounds(lo, hi) => - if (Stats.monitored) Stats.record("checkBounds") - isSubType(lo, hi) - case _ => true - } - - /** Test validity of constraint for parameter `changed` and of all - * parameters that depend on it. - */ - private def propagate(changed: PolyParam): Boolean = - if (Config.trackConstrDeps) - checkBounds(changed) && - propagate(constraint.dependentParams(changed) - changed, Set(changed)) - else - constraint forallParams checkBounds - - /** Ensure validity of constraints for parameters `params` and of all - * parameters that depend on them and that have not been tested - * now or before. If `trackConstrDeps` is not set, do this for all - * parameters in the constraint. - * @param seen the set of parameters that have been tested before. - */ - private def propagate(params: Set[PolyParam], seen: Set[PolyParam]): Boolean = - params.isEmpty || - (params forall checkBounds) && { - val seen1 = seen ++ params - val nextParams = (Set[PolyParam]() /: params) { (ps, p) => - ps ++ (constraint.dependentParams(p) -- seen1) - } - propagate(nextParams, seen1) - } - - /** Check whether the lower bounds of all parameters in this + /** Test whether the lower bounds of all parameters in this * constraint are a solution to the constraint. - * As an optimization, when `trackConstrDeps` is set, we - * only test that the solutions satisfy the constraints `changed` - * and all parameters that depend on it. */ - def isSatisfiable(changed: PolyParam): Boolean = { + def isSatisfiable: Boolean = { val saved = solvedConstraint solvedConstraint = true try - if (Config.trackConstrDeps) propagate(changed) - else - constraint.forallParams { param => - checkBounds(param) || { - val TypeBounds(lo, hi) = constraint.bounds(param) - ctx.log(i"sub fail $lo <:< $hi") - ctx.log(i"approximated = ${approxParams(lo)} <:< ${approxParams(hi)}") - false - } + constraint.forallParams { param => + val TypeBounds(lo, hi) = constraint.at(param) + isSubType(lo, hi) || { + ctx.log(i"sub fail $lo <:< $hi") + ctx.log(i"approximated = ${approxParams(lo)} <:< ${approxParams(hi)}") + false } + } finally solvedConstraint = saved } - /** Update constraint for `param` to `bounds`, check that - * new constraint is still satisfiable. - */ - private def updateConstraint(param: PolyParam, bounds: TypeBounds): Boolean = { - val saved = constraint - constraint = constraint.updated(param, bounds) - if (propagate(param)) { - if (isSatisfiable(param)) return true - ctx.log(i"SAT $constraint produced by $param $bounds is not satisfiable") - } - constraint = saved // don't leave the constraint in unsatisfiable state - false - } - - private def addConstraint1(param: PolyParam, bound: Type, fromBelow: Boolean): Boolean = { - val oldBounds = constraint.bounds(param) - assert(!bound.isInstanceOf[TypeVar]) - val saved = ignoreConstraint - ignoreConstraint = true - val newBounds = - try - if (fromBelow) oldBounds.derivedTypeBounds(oldBounds.lo | bound, oldBounds.hi) - else oldBounds.derivedTypeBounds(oldBounds.lo, oldBounds.hi & bound) - finally ignoreConstraint = saved - val res = - (param == bound) || (oldBounds eq newBounds) || updateConstraint(param, newBounds) - //constr.println(s"added1 constraint $param ${if (fromBelow) ">:" else "<:"} $bound = $res") - if (res) constr.println(constraint.show) - res - } - /** Make p2 = p1, transfer all bounds of p2 to p1 */ private def unify(p1: PolyParam, p2: PolyParam): Boolean = { constr.println(s"unifying $p1 $p2") @@ -200,7 +159,7 @@ class TypeComparer(initctx: Context) extends DotClass { val bounds = constraint1.bounds(p1) isSubType(bounds.lo, bounds.hi) && { constraint = constraint1; true } } - + /** If current constraint set is not frozen, add the constraint * * param >: bound if fromBelow is true @@ -212,44 +171,114 @@ class TypeComparer(initctx: Context) extends DotClass { * @return Whether the augmented constraint is still satisfiable. */ def addConstraint(param: PolyParam, bound0: Type, fromBelow: Boolean): Boolean = { - assert(!frozenConstraint) - def recur(bound0: Type): Boolean = { - assert(bound0.exists) - val bound = bound0.dealias.stripTypeVar - def description = s"${param.show} ${if (fromBelow) ">:>" else "<:<"} ${bound.show} (${bound.getClass}) to ${constraint.show}" - constr.println(s"adding $description") + + /** Add bidirectional constraint. If new constraint implies 'A <: B' we also + * make sure 'B >: A' gets added and vice versa. Furthermore, if the constraint + * implies 'A <: B <: A', A and B get unified. + */ + def addBi(param: PolyParam, bound: Type, fromBelow: Boolean): Boolean = constraint.bounds(param) match { - case TypeBounds(plo: PolyParam, phi) if constraint.contains(plo) && (plo eq phi) => - addConstraint(plo, bound, fromBelow) + case TypeBounds(plo: PolyParam, phi) if (plo eq phi) && constraint.contains(plo) => + addBi(plo, bound, fromBelow) case _ => - - val res = bound match { - case bound: PolyParam if constraint contains bound => - val TypeBounds(lo, hi) = constraint.bounds(bound) - if (lo eq hi) - addConstraint(param, lo, fromBelow) - else if (param == bound) - true - else if (fromBelow && param.occursIn(lo, fromBelow = true)) - unify(param, bound) - else if (!fromBelow && param.occursIn(hi, fromBelow = false)) - unify(bound, param) - else - addConstraint1(param, bound, fromBelow) && - addConstraint1(bound, param, !fromBelow) - case bound: AndOrType if fromBelow != bound.isAnd => - addConstraint(param, bound.tp1, fromBelow) && - addConstraint(param, bound.tp2, fromBelow) - case bound: WildcardType => + bound match { + case bound: PolyParam if constraint contains bound => + val TypeBounds(lo, hi) = constraint.bounds(bound) + if (lo eq hi) + addBi(param, lo, fromBelow) + else if (param == bound) + true + else if (fromBelow && param.occursIn(lo, fromBelow = true)) + unify(param, bound) + else if (!fromBelow && param.occursIn(hi, fromBelow = false)) + unify(bound, param) + else + addUni(param, bound, fromBelow) && + addUni(bound, param, !fromBelow) + case bound: AndOrType if fromBelow != bound.isAnd => + addBi(param, bound.tp1, fromBelow) && + addBi(param, bound.tp2, fromBelow) + case bound: WildcardType => + true + case bound => // !!! remove to keep the originals + addUni(param, bound, fromBelow) + } + } + + /** Add constraint without propagating in the other direction or unifying */ + def addUni(param: PolyParam, bound: Type, fromBelow: Boolean): Boolean = { + val oldBounds = constraint.bounds(param) + def narrowedBounds(bounds: TypeBounds): TypeBounds = { + val savedIgnore = ignoreConstraint + val savedFrozen = frozenConstraint + ignoreConstraint = true + frozenConstraint = true + try + if (fromBelow) bounds.derivedTypeBounds(bounds.lo | bound, bounds.hi) + else bounds.derivedTypeBounds(bounds.lo, bounds.hi & bound) + finally { + ignoreConstraint = savedIgnore + frozenConstraint = savedFrozen + } + } + val newBounds = narrowedBounds(oldBounds) + (param == bound) || + (oldBounds eq newBounds) || + { val pendingBounds = pendingBoundss(param) + if (pendingBounds == null) + // Why the pendingBoundss tests? It is possible that recursive subtype invocations + // come back to param instead. An example came up when compiling ElimRepeated where + // we got the constraint + // + // Coll <: IterableLike[Tree, Coll] + // + // and added + // + // List[Tree] <: Coll + // + // The recursive bounds test is then + // + // List[Tree] <: IterableLike[Tree, Coll] + // + // and because of the F-bounded polymorphism in the supertype of List, + // i.e. List[T] <: IterableLike[T, List[T]], this leads again to + // + // List[Tree] <: Coll + try { + pendingBoundss = pendingBoundss.updated(param, newBounds) + isSubType(newBounds.lo, newBounds.hi) && { + constraint = constraint.updated(param, pendingBoundss(param)) + if (needsSatCheck(param)) { + assert(isSatisfiable) + needsSatCheck -= param + } + true + } + } + finally pendingBoundss = pendingBoundss.remove(param) + else { + // TODO: investigate - if the last line in this comment is uncommented, we get a cyclic + // constraint error in tools/io. For now, we do without even though this + // risks allowing unsatisfiable constraints to get through. + // Unsatisfiable constraints are caught by an assertion that is executed later + // in case we got here. + //pendingBoundss = pendingBoundss.updated(param, narrowedBounds(pendingBounds)) + + needsSatCheck += param true - case bound => // !!! remove to keep the originals - addConstraint1(param, bound, fromBelow) + } } - constr.println(s"added $description") - if (Config.checkConstraintsNonCyclicTrans) constraint.checkNonCyclicTrans() - res - }} - recur(bound0) // ctx.deSkolemize(bound0, toSuper = fromBelow)) + } + + val bound = (if (false) ctx.deSkolemize(bound0, toSuper = fromBelow) else bound0) + .dealias.stripTypeVar + def description = s"${param.show} ${if (fromBelow) ">:>" else "<:<"} ${bound.show} to ${constraint.show}" + constr.println(s"adding $description") + val res = addBi(param, bound, fromBelow) + constr.println(s"added $description") + if (Config.checkConstraintsNonCyclicTrans) constraint.checkNonCyclicTrans() + if (needsSatCheck(param)) assert(isSatisfiable) + res } def isConstrained(param: PolyParam): Boolean = diff --git a/test/dotc/tests.scala b/test/dotc/tests.scala index e12becd0c..71668823a 100644 --- a/test/dotc/tests.scala +++ b/test/dotc/tests.scala @@ -126,7 +126,7 @@ class tests extends CompilerTest { @Test def dotc_core_pickling = compileDir(dotcDir + "tools/dotc/core/pickling", failedOther)(allowDeepSubtypes) // Cannot emit primitive conversion from V to Z - @Test def dotc_transform = compileDir(dotcDir + "tools/dotc/transform", failedbyName)(allowDeepSubtypes) + @Test def dotc_transform = compileDir(dotcDir + "tools/dotc/transform", failedbyName) @Test def dotc_parsing = compileDir(dotcDir + "tools/dotc/parsing", failedOther) // Expected primitive types I - Ljava/lang/Object diff --git a/tests/pending/pos/t0674.scala b/tests/pending/pos/t0674.scala new file mode 100644 index 000000000..e405f4b8d --- /dev/null +++ b/tests/pending/pos/t0674.scala @@ -0,0 +1,49 @@ +object Test extends App { +println( +for(a <- Some(1); + b <- Some(2); + c <- Some(3); + d <- Some(4); + e <- Some(5); + f <- Some(6); + g <- Some(7); + h <- Some(8); + i <- Some(9); + j <- Some(10); + k <- Some(11); + l <- Some(12) +/* + m <- Some(13); + n <- Some(14); + o <- Some(15); + p <- Some(16); + q <- Some(17); + r <- Some(18); + s <- Some(19); + d <- Some(4); + e <- Some(5); + f <- Some(6); + g <- Some(7); + h <- Some(8); + i <- Some(9); + j <- Some(10); + k <- Some(11); + l <- Some(12); + m <- Some(13); + n <- Some(14); + o <- Some(15); + p <- Some(16); + q <- Some(17); + r <- Some(18); + s <- Some(19); + k <- Some(11); + l <- Some(12); + m <- Some(13); + n <- Some(14); + o <- Some(15)*/ +// p <- Some(16); +// q <- Some(17) +// r <- Some(18); +// s <- Some(19) + ) yield a) +} diff --git a/tests/pos/t0674.scala b/tests/pos/t0674.scala deleted file mode 100644 index 589eeec9f..000000000 --- a/tests/pos/t0674.scala +++ /dev/null @@ -1,48 +0,0 @@ -object Test extends App { -println( -for(a <- Some(1); - b <- Some(2); - c <- Some(3); - d <- Some(4); - e <- Some(5); - f <- Some(6); - g <- Some(7); - h <- Some(8); - i <- Some(9); - j <- Some(10); - k <- Some(11); - l <- Some(12); - m <- Some(13); - n <- Some(14); - o <- Some(15); - p <- Some(16); - q <- Some(17); - r <- Some(18); - s <- Some(19); - d <- Some(4); - e <- Some(5); - f <- Some(6); - g <- Some(7); - h <- Some(8); - i <- Some(9); - j <- Some(10); - k <- Some(11); - l <- Some(12); - m <- Some(13); - n <- Some(14); - o <- Some(15); - p <- Some(16); - q <- Some(17); - r <- Some(18); - s <- Some(19); - k <- Some(11); - l <- Some(12); - m <- Some(13); - n <- Some(14); - o <- Some(15) -// p <- Some(16); -// q <- Some(17) -// r <- Some(18); -// s <- Some(19) - ) yield a) -} -- cgit v1.2.3 From 9b260d087a4c63c39e404fd6ba7ade286fdfd8e8 Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Sun, 18 Jan 2015 19:04:05 +0100 Subject: Moved previously failing tests to pos GADTs now work again (they stopped workign when we went to the inductive satisfiability checks). The deep for expression also works, even with some more levels added. --- tests/pending/pos/i0268.scala | 15 ------------ tests/pending/pos/t0674.scala | 49 -------------------------------------- tests/pending/pos/t1208.scala | 7 ------ tests/pending/pos/t2624.scala | 4 ---- tests/pending/pos/t267.scala | 55 ------------------------------------------- tests/pos/i0268.scala | 15 ++++++++++++ tests/pos/t0674.scala | 48 +++++++++++++++++++++++++++++++++++++ tests/pos/t1208.scala | 7 ++++++ 8 files changed, 70 insertions(+), 130 deletions(-) delete mode 100644 tests/pending/pos/i0268.scala delete mode 100644 tests/pending/pos/t0674.scala delete mode 100644 tests/pending/pos/t1208.scala delete mode 100644 tests/pending/pos/t2624.scala delete mode 100644 tests/pending/pos/t267.scala create mode 100644 tests/pos/i0268.scala create mode 100644 tests/pos/t0674.scala create mode 100644 tests/pos/t1208.scala (limited to 'tests/pending') diff --git a/tests/pending/pos/i0268.scala b/tests/pending/pos/i0268.scala deleted file mode 100644 index 6ac0c5c90..000000000 --- a/tests/pending/pos/i0268.scala +++ /dev/null @@ -1,15 +0,0 @@ -package typespatmat - -sealed trait Box2[T] -final case class Int2(x: Int) extends Box2[Int] -final case class Str2(x: String) - extends Box2[String] -final case class Gen[T](x: T) extends Box2[T] - -object Box2 { - def double2[T](x: Box2[T]): T = x match { - case Int2(i) => i * 2 - case Str2(s) => s + s - case Gen(x) => x - } -} diff --git a/tests/pending/pos/t0674.scala b/tests/pending/pos/t0674.scala deleted file mode 100644 index e405f4b8d..000000000 --- a/tests/pending/pos/t0674.scala +++ /dev/null @@ -1,49 +0,0 @@ -object Test extends App { -println( -for(a <- Some(1); - b <- Some(2); - c <- Some(3); - d <- Some(4); - e <- Some(5); - f <- Some(6); - g <- Some(7); - h <- Some(8); - i <- Some(9); - j <- Some(10); - k <- Some(11); - l <- Some(12) -/* - m <- Some(13); - n <- Some(14); - o <- Some(15); - p <- Some(16); - q <- Some(17); - r <- Some(18); - s <- Some(19); - d <- Some(4); - e <- Some(5); - f <- Some(6); - g <- Some(7); - h <- Some(8); - i <- Some(9); - j <- Some(10); - k <- Some(11); - l <- Some(12); - m <- Some(13); - n <- Some(14); - o <- Some(15); - p <- Some(16); - q <- Some(17); - r <- Some(18); - s <- Some(19); - k <- Some(11); - l <- Some(12); - m <- Some(13); - n <- Some(14); - o <- Some(15)*/ -// p <- Some(16); -// q <- Some(17) -// r <- Some(18); -// s <- Some(19) - ) yield a) -} diff --git a/tests/pending/pos/t1208.scala b/tests/pending/pos/t1208.scala deleted file mode 100644 index 7b14aadca..000000000 --- a/tests/pending/pos/t1208.scala +++ /dev/null @@ -1,7 +0,0 @@ -object Test { - object Foo - val f: Option[Foo.type] = Some(Foo) -} - -// unsupported with current typing rules. -// on the other hand, we need a way to refer to a module class. diff --git a/tests/pending/pos/t2624.scala b/tests/pending/pos/t2624.scala deleted file mode 100644 index 76f0e3036..000000000 --- a/tests/pending/pos/t2624.scala +++ /dev/null @@ -1,4 +0,0 @@ -object Test { - List(1).map(identity(_)) - List(1).map(identity) // this didn't typecheck before the fix -} diff --git a/tests/pending/pos/t267.scala b/tests/pending/pos/t267.scala deleted file mode 100644 index 7e5876eae..000000000 --- a/tests/pending/pos/t267.scala +++ /dev/null @@ -1,55 +0,0 @@ -package expAbstractData - -/** A base class consisting of - * - a root trait (i.e. abstract class) `Exp' with an `eval' function - * - an abstract type `exp' bounded by `Exp' - * - a concrete instance class `Num' of `Exp' for numeric literals - */ -trait Base { - type exp <: Exp - - trait Exp { - def eval: Int - } - class Num(v: Int) extends Exp { self: exp => - val value = v - def eval = value - } -} - -object testBase extends App with Base { - type exp = Exp - val term = new Num(2); - Console.println(term.eval) -} - -/** Data extension: An extension of `Base' with `Plus' expressions - */ -trait BasePlus extends Base { - class Plus(l: exp, r: exp) extends Exp { self: exp => - val left = l - val right = r - def eval = left.eval + right.eval - } -} - -/** Operation extension: An extension of `Base' with 'show' methods. - */ -trait Show extends Base { - type exp <: Exp1 - - trait Exp1 extends Exp { - def show: String - } - class Num1(v: Int) extends Num(v) with Exp1 { self: exp with Num1 => - def show = value.toString() - } -} - -/** Operation extension: An extension of `BasePlus' with 'show' methods. - */ -trait ShowPlus extends BasePlus with Show { - class Plus1(l: exp, r: exp) extends Plus(l, r) with Exp1 { self: exp with Plus1 => - def show = left.show + " + " + right.show - } -} diff --git a/tests/pos/i0268.scala b/tests/pos/i0268.scala new file mode 100644 index 000000000..6ac0c5c90 --- /dev/null +++ b/tests/pos/i0268.scala @@ -0,0 +1,15 @@ +package typespatmat + +sealed trait Box2[T] +final case class Int2(x: Int) extends Box2[Int] +final case class Str2(x: String) + extends Box2[String] +final case class Gen[T](x: T) extends Box2[T] + +object Box2 { + def double2[T](x: Box2[T]): T = x match { + case Int2(i) => i * 2 + case Str2(s) => s + s + case Gen(x) => x + } +} diff --git a/tests/pos/t0674.scala b/tests/pos/t0674.scala new file mode 100644 index 000000000..a734091da --- /dev/null +++ b/tests/pos/t0674.scala @@ -0,0 +1,48 @@ +object Test extends App { +println( +for(a <- Some(1); + b <- Some(2); + c <- Some(3); + d <- Some(4); + e <- Some(5); + f <- Some(6); + g <- Some(7); + h <- Some(8); + i <- Some(9); + j <- Some(10); + k <- Some(11); + l <- Some(12); + m <- Some(13); + n <- Some(14); + o <- Some(15); + p <- Some(16); + q <- Some(17); + r <- Some(18); + s <- Some(19); + d <- Some(4); + e <- Some(5); + f <- Some(6); + g <- Some(7); + h <- Some(8); + i <- Some(9); + j <- Some(10); + k <- Some(11); + l <- Some(12); + m <- Some(13); + n <- Some(14); + o <- Some(15); + p <- Some(16); + q <- Some(17); + r <- Some(18); + s <- Some(19); + k <- Some(11); + l <- Some(12); + m <- Some(13); + n <- Some(14); + o <- Some(15); + p <- Some(16); + q <- Some(17); + r <- Some(18); + s <- Some(19) + ) yield a) +} diff --git a/tests/pos/t1208.scala b/tests/pos/t1208.scala new file mode 100644 index 000000000..7b14aadca --- /dev/null +++ b/tests/pos/t1208.scala @@ -0,0 +1,7 @@ +object Test { + object Foo + val f: Option[Foo.type] = Some(Foo) +} + +// unsupported with current typing rules. +// on the other hand, we need a way to refer to a module class. -- cgit v1.2.3 From 37918e5d1eb53014b1116ea65381a56e93a3c855 Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Wed, 28 Jan 2015 18:55:51 +0100 Subject: Cleanups prompted by reviews. --- src/dotty/tools/dotc/config/Config.scala | 2 +- src/dotty/tools/dotc/core/ConstraintHandling.scala | 67 +++++++++------------- src/dotty/tools/dotc/core/Symbols.scala | 4 +- src/dotty/tools/dotc/core/TypeComparer.scala | 2 +- src/dotty/tools/dotc/typer/Mode.scala | 6 ++ src/dotty/tools/dotc/typer/ProtoTypes.scala | 3 +- tests/pending/pos/compound.scala | 5 +- 7 files changed, 43 insertions(+), 46 deletions(-) (limited to 'tests/pending') diff --git a/src/dotty/tools/dotc/config/Config.scala b/src/dotty/tools/dotc/config/Config.scala index fe4e88829..a599b5892 100644 --- a/src/dotty/tools/dotc/config/Config.scala +++ b/src/dotty/tools/dotc/config/Config.scala @@ -37,7 +37,7 @@ object Config { * on only for specific debugging as normally instantiation to Nothing * is not an error consdition. */ - final val flagInstantiationToNothing = false + final val failOnInstantiationToNothing = false /** Enable noDoubleDef checking if option "-YnoDoubleDefs" is set. * The reason to have an option as well as the present global switch is diff --git a/src/dotty/tools/dotc/core/ConstraintHandling.scala b/src/dotty/tools/dotc/core/ConstraintHandling.scala index 478fc5740..796960337 100644 --- a/src/dotty/tools/dotc/core/ConstraintHandling.scala +++ b/src/dotty/tools/dotc/core/ConstraintHandling.scala @@ -9,27 +9,14 @@ import config.Printers._ /** Methods for adding constraints and solving them. * - * Constraints are required to be in normalized form. This means - * (1) if P <: Q in C then also Q >: P in C - * (2) if P r Q in C and Q r R in C then also P r R in C, where r is <: or :> - * - * "P <: Q in C" means here: There is a constraint P <: H[Q], - * where H is the multi-hole context given by: - * - * H = [] - * H & T - * T & H - * H | H - * - * (the idea is that a parameter Q in a H context is guaranteed to be a supertype of P). - * - * "P >: Q in C" means: There is a constraint P >: L[Q], - * where L is the multi-hole context given by: - * - * L = [] - * L | T - * T | L - * L & L + * What goes into a Constraint as opposed to a ConstrainHandler? + * + * Constraint code is purely functional: Operations get constraints and produce new ones. + * Constraint code does not have access to a type-comparer. Anything regarding lubs and glbs has to be done + * elsewhere. + * + * By comparison: Constraint handlers are parts of type comparers and can use their functionality. + * Constraint handlers update the current constraint as a side effect. */ trait ConstraintHandling { @@ -59,7 +46,7 @@ trait ConstraintHandling { def description = i"constraint $param <: $bound to\n$constraint" if (bound.isRef(defn.NothingClass) && ctx.typerState.isGlobalCommittable) { def msg = s"!!! instantiated to Nothing: $param, constraint = ${constraint.show}" - if (Config.flagInstantiationToNothing) assert(false, msg) + if (Config.failOnInstantiationToNothing) assert(false, msg) else ctx.log(msg) } constr.println(i"adding $description") @@ -86,9 +73,6 @@ trait ConstraintHandling { def description = i"ordering $p1 <: $p2 to\n$constraint" val res = if (constraint.isLess(p2, p1)) unify(p2, p1) - // !!! this is direction dependent - unify(p1, p2) makes i94-nada loop forever. - // Need to investigate why this is the case. - // The symptom is that we get a subtyping constraint of the form P { ... } <: P else { val down1 = p1 :: constraint.exclusiveLower(p1, p2) val up2 = p2 :: constraint.exclusiveUpper(p2, p1) @@ -193,20 +177,24 @@ trait ConstraintHandling { case _ => param.binder.paramBounds(param.paramNum) } - /** If `p` is a parameter of `pt`, propagate the non-parameter bounds - * of `p` to the parameters known to be less or greater than `p`. + /** Add polytype `pt`, possibly with type variables `tvars`, to current constraint + * and propagate all bounds. + * @param tvars See Constraint#add */ - def initialize(pt: PolyType): Boolean = - checkPropagated(i"initialized $pt") { - pt.paramNames.indices.forall { i => - val param = PolyParam(pt, i) - val bounds = constraint.nonParamBounds(param) - val lower = constraint.lower(param) - val upper = constraint.upper(param) - if (lower.nonEmpty && !bounds.lo.isRef(defn.NothingClass) || - upper.nonEmpty && !bounds.hi.isRef(defn.AnyClass)) println(i"INIT*** $pt") - lower.forall(addOneBound(_, bounds.hi, isUpper = true)) && - upper.forall(addOneBound(_, bounds.lo, isUpper = false)) + def addToConstraint(pt: PolyType, tvars: List[TypeVar]): Unit = + assert { + checkPropagated(i"initialized $pt") { + constraint = constraint.add(pt, tvars) + pt.paramNames.indices.forall { i => + val param = PolyParam(pt, i) + val bounds = constraint.nonParamBounds(param) + val lower = constraint.lower(param) + val upper = constraint.upper(param) + if (lower.nonEmpty && !bounds.lo.isRef(defn.NothingClass) || + upper.nonEmpty && !bounds.hi.isRef(defn.AnyClass)) println(i"INIT*** $pt") + lower.forall(addOneBound(_, bounds.hi, isUpper = true)) && + upper.forall(addOneBound(_, bounds.lo, isUpper = false)) + } } } @@ -239,6 +227,7 @@ trait ConstraintHandling { /** Check that constraint is fully propagated. See comment in Config.checkConstraintsPropagated */ def checkPropagated(msg: => String)(result: Boolean): Boolean = { if (Config.checkConstraintsPropagated && result && addConstraintInvocations == 0) { + val saved = frozenConstraint frozenConstraint = true for (p <- constraint.domainParams) { def check(cond: => Boolean, q: PolyParam, ordering: String, explanation: String): Unit = @@ -250,7 +239,7 @@ trait ConstraintHandling { check(constraint.isLess(l, p), l, ">:", "reverse ordering (<:) missing") } } - frozenConstraint = false + frozenConstraint = saved } result } diff --git a/src/dotty/tools/dotc/core/Symbols.scala b/src/dotty/tools/dotc/core/Symbols.scala index 2854d7d2f..bff743fea 100644 --- a/src/dotty/tools/dotc/core/Symbols.scala +++ b/src/dotty/tools/dotc/core/Symbols.scala @@ -256,8 +256,8 @@ trait Symbols { this: Context => tparams } - /** Create a new skolem symbol. This is not the same as SkolemType, even thouggh the - * motivation (create a singleton referencing to a type)= is similar. + /** Create a new skolem symbol. This is not the same as SkolemType, even though the + * motivation (create a singleton referencing to a type) is similar. */ def newSkolem(tp: Type) = newSymbol(defn.RootClass, nme.SKOLEM, SyntheticArtifact | Permanent, tp) diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala index 06f03b9f9..1d0ea03c1 100644 --- a/src/dotty/tools/dotc/core/TypeComparer.scala +++ b/src/dotty/tools/dotc/core/TypeComparer.scala @@ -249,7 +249,7 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling wi def flagNothingBound = { if (!frozenConstraint && tp2.isRef(defn.NothingClass) && state.isGlobalCommittable) { def msg = s"!!! instantiated to Nothing: $tp1, constraint = ${constraint.show}" - if (Config.flagInstantiationToNothing) assert(false, msg) + if (Config.failOnInstantiationToNothing) assert(false, msg) else ctx.log(msg) } true diff --git a/src/dotty/tools/dotc/typer/Mode.scala b/src/dotty/tools/dotc/typer/Mode.scala index 8e62adfdd..1a57fdc54 100644 --- a/src/dotty/tools/dotc/typer/Mode.scala +++ b/src/dotty/tools/dotc/typer/Mode.scala @@ -31,6 +31,12 @@ object Mode { val ImplicitsEnabled = newMode(2, "ImplicitsEnabled") val InferringReturnType = newMode(3, "InferringReturnType") + /** This mode bit is set if we collect information without reference to a valid + * context with typerstate and constraint. This is typically done when we + * cache the eligibility of implicits. Caching needs to be done across different constraints. + * Therefore, if TypevarsMissContext is set, subtyping becomes looser, and assumes + * that PolyParams can be sub- and supertypes of anything. See TypeComparer. + */ val TypevarsMissContext = newMode(4, "TypevarsMissContext") val CheckCyclic = newMode(5, "CheckCyclic") diff --git a/src/dotty/tools/dotc/typer/ProtoTypes.scala b/src/dotty/tools/dotc/typer/ProtoTypes.scala index e4d58cb19..24b4cb423 100644 --- a/src/dotty/tools/dotc/typer/ProtoTypes.scala +++ b/src/dotty/tools/dotc/typer/ProtoTypes.scala @@ -324,8 +324,7 @@ object ProtoTypes { if (state.constraint contains pt) pt.duplicate(pt.paramNames, pt.paramBounds, pt.resultType) else pt val tvars = if (owningTree.isEmpty) Nil else newTypeVars(added) - state.constraint = state.constraint.add(added, tvars) - ctx.typeComparer.initialize(added) + ctx.typeComparer.addToConstraint(added, tvars) (added, tvars) } diff --git a/tests/pending/pos/compound.scala b/tests/pending/pos/compound.scala index 308ffdfd9..16dbf9a08 100644 --- a/tests/pending/pos/compound.scala +++ b/tests/pending/pos/compound.scala @@ -1,3 +1,5 @@ +// There's still a problem with var's here, presumably because they are not paths. +// Needs some more investigation. abstract class A { type T } abstract class B { val xz: Any } @@ -7,7 +9,8 @@ abstract class Test { var xx: A with B { type T; val xz: T } = null; xx = yy; } + abstract class Test2 { - var yy: A with B { type T; val xz: T } = null; + val yy: A with B { type T; val xz: T } = null; val xx: A with B { type T; val xz: T } = yy } -- cgit v1.2.3 From 70e55d26100199b99502705233786bbdc15c4c6b Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Wed, 28 Jan 2015 19:01:09 +0100 Subject: Fixed problem with ensureSingleton Need to also ensure that the singleton is stable. This makes compound.scala pass. --- src/dotty/tools/dotc/core/Skolemization.scala | 6 +++--- src/dotty/tools/dotc/core/TypeComparer.scala | 2 +- tests/pending/pos/compound.scala | 16 ---------------- tests/pos/compound.scala | 14 ++++++++++++++ 4 files changed, 18 insertions(+), 20 deletions(-) delete mode 100644 tests/pending/pos/compound.scala create mode 100644 tests/pos/compound.scala (limited to 'tests/pending') diff --git a/src/dotty/tools/dotc/core/Skolemization.scala b/src/dotty/tools/dotc/core/Skolemization.scala index 8bc5c815f..2832a3bad 100644 --- a/src/dotty/tools/dotc/core/Skolemization.scala +++ b/src/dotty/tools/dotc/core/Skolemization.scala @@ -20,14 +20,14 @@ trait Skolemization { protected var skolemsOutstanding = false - def ensureSingleton(tp: Type): SingletonType = tp.stripTypeVar match { - case tp: SingletonType => + def ensureStableSingleton(tp: Type): SingletonType = tp.stripTypeVar match { + case tp: SingletonType if tp.isStable => tp case tp: ValueType => skolemsOutstanding = true SkolemType(tp) case tp: TypeProxy => - ensureSingleton(tp.underlying) + ensureStableSingleton(tp.underlying) } /** Approximate a type `tp` with a type that does not contain skolem types. diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala index 1d0ea03c1..9826a23ea 100644 --- a/src/dotty/tools/dotc/core/TypeComparer.scala +++ b/src/dotty/tools/dotc/core/TypeComparer.scala @@ -517,7 +517,7 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling wi val saved = skolemsOutstanding try { val rebindNeeded = tp2.refinementRefersToThis - val base = if (rebindNeeded) ensureSingleton(tp1) else tp1 + val base = if (rebindNeeded) ensureStableSingleton(tp1) else tp1 val rinfo2 = if (rebindNeeded) tp2.refinedInfo.substSkolem(tp2, base) else tp2.refinedInfo def qualifies(m: SingleDenotation) = isSubType(m.info, rinfo2) def memberMatches(mbr: Denotation): Boolean = mbr match { // inlined hasAltWith for performance diff --git a/tests/pending/pos/compound.scala b/tests/pending/pos/compound.scala deleted file mode 100644 index 16dbf9a08..000000000 --- a/tests/pending/pos/compound.scala +++ /dev/null @@ -1,16 +0,0 @@ -// There's still a problem with var's here, presumably because they are not paths. -// Needs some more investigation. -abstract class A { type T } - -abstract class B { val xz: Any } - -abstract class Test { - var yy: A with B { type T; val xz: T } = null; - var xx: A with B { type T; val xz: T } = null; - xx = yy; -} - -abstract class Test2 { - val yy: A with B { type T; val xz: T } = null; - val xx: A with B { type T; val xz: T } = yy -} diff --git a/tests/pos/compound.scala b/tests/pos/compound.scala new file mode 100644 index 000000000..24a936f13 --- /dev/null +++ b/tests/pos/compound.scala @@ -0,0 +1,14 @@ +abstract class A { type T } + +abstract class B { val xz: Any } + +abstract class Test { + var yy: A with B { type T; val xz: T } = null; + var xx: A with B { type T; val xz: T } = null; + xx = yy; +} + +abstract class Test2 { + var yy: A with B { type T; val xz: T } = null; + val xx: A with B { type T; val xz: T } = yy +} -- cgit v1.2.3