From 0baeb8e22c085a73a129859f7c07d578e1122c0b Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Mon, 27 Feb 2017 11:25:33 +0100 Subject: Don't align aliases in refined types by default We previously tried to force S1 and S2 be the same type when encountering a lub like `T1 { A = S1 } & T2 { A = S2 }`. The comments in this commit explain why this is unsound, so this rewrite is now made subject to a new config option, which is off by default. I verified that the new behavior does not affect the performance of the junit tests. --- .../src/dotty/tools/dotc/core/TypeComparer.scala | 33 +++++++++++++--------- 1 file changed, 19 insertions(+), 14 deletions(-) (limited to 'compiler/src/dotty/tools/dotc/core/TypeComparer.scala') diff --git a/compiler/src/dotty/tools/dotc/core/TypeComparer.scala b/compiler/src/dotty/tools/dotc/core/TypeComparer.scala index fca111702..744112280 100644 --- a/compiler/src/dotty/tools/dotc/core/TypeComparer.scala +++ b/compiler/src/dotty/tools/dotc/core/TypeComparer.scala @@ -1312,23 +1312,28 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { case tp1: RefinedType => tp2 match { case tp2: RefinedType if tp1.refinedName == tp2.refinedName => - // Given two refinements `T1 { X = S1 }` and `T2 { X = S2 }`, if `S1 =:= S2` - // (possibly by instantiating type parameters), rewrite to `T1 & T2 { X = S1 }`. - // Otherwise rewrite to `T1 & T2 { X B }` where `B` is the conjunction of - // the bounds of `X` in `T1` and `T2`. - // The first rule above is contentious because it cuts the constraint set. - // But without it we would replace the two aliases by - // `T { X >: S1 | S2 <: S1 & S2 }`, which looks weird and is probably - // not what's intended. + // Given two refinements `T1 { X = S1 }` and `T2 { X = S2 }` rwrite to + // `T1 & T2 { X B }` where `B` is the conjunction of the bounds of `X` in `T1` and `T2`. + // + // However, if `Config.alignArgsInAnd` is set, and both aliases `X = Si` are + // nonvariant, and `S1 =:= S2` (possibly by instantiating type parameters), + // rewrite instead to `T1 & T2 { X = S1 }`. This rule is contentious because + // it cuts the constraint set. On the other hand, without it we would replace + // the two aliases by `T { X >: S1 | S2 <: S1 & S2 }`, which looks weird + // and is probably not what's intended. val rinfo1 = tp1.refinedInfo val rinfo2 = tp2.refinedInfo val parent = tp1.parent & tp2.parent - val rinfo = - if (rinfo1.isAlias && rinfo2.isAlias && isSameType(rinfo1, rinfo2)) - rinfo1 - else - rinfo1 & rinfo2 - tp1.derivedRefinedType(parent, tp1.refinedName, rinfo) + + def isNonvariantAlias(tp: Type) = tp match { + case tp: TypeAlias => tp.variance == 0 + case _ => false + } + if (Config.alignArgsInAnd && + isNonvariantAlias(rinfo1) && isNonvariantAlias(rinfo2)) + isSameType(rinfo1, rinfo2) + + tp1.derivedRefinedType(parent, tp1.refinedName, rinfo1 & rinfo2) case _ => NoType } -- cgit v1.2.3 From 1d237bb1f0c7aac949b52601e26e96fff0fe4ffd Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Wed, 1 Mar 2017 22:10:17 +0100 Subject: Make alignArgsInAnd safe and turn it on by default Turned out hmaps.scala requires the arg alignment to compile. So we have our first counterexample that we cannot drop this hack. Now it is made safe in the sense that no constraints get lost anymore. --- compiler/src/dotty/tools/dotc/config/Config.scala | 16 +++++---------- .../src/dotty/tools/dotc/core/Constraint.scala | 6 ------ .../dotty/tools/dotc/core/ConstraintHandling.scala | 24 +++++++++++++++++++++- .../dotty/tools/dotc/core/OrderingConstraint.scala | 8 -------- .../src/dotty/tools/dotc/core/TypeComparer.scala | 4 ++-- 5 files changed, 30 insertions(+), 28 deletions(-) (limited to 'compiler/src/dotty/tools/dotc/core/TypeComparer.scala') diff --git a/compiler/src/dotty/tools/dotc/config/Config.scala b/compiler/src/dotty/tools/dotc/config/Config.scala index 900e5669f..dc56ad8b8 100644 --- a/compiler/src/dotty/tools/dotc/config/Config.scala +++ b/compiler/src/dotty/tools/dotc/config/Config.scala @@ -75,20 +75,14 @@ object Config { /** If this flag is set, take the fast path when comparing same-named type-aliases and types */ final val fastPathForRefinedSubtype = true - /** If this flag is set, and we compute `T1 { X = S1 }` & `T2 { X = S2 }`, - * try to align the refinements by computing `S1 =:= S2` (which might instantiate type parameters). - * This rule is contentious because it cuts the constraint set. Also, it is - * currently unsound because `&` gets called in computations on a constraint - * itself. If the `=:=` test generates a new constraint, that constraint is then - * out of sync with with the constraint on which the computation is performed. - * The constraint resulting from `=:=` ends up to be thrown away whereas - * its result is used, which is unsound. So if we want to turn this flag on - * permanently instead of just for debugging, we have to refactor occurrences - * of `&` in `OrderedConstraint` so that they take the `=:=` result into account. + /** If this flag is set, and we compute `T1 { X = S1 }` & `T2 { X = S2 }` as a new + * upper bound of a constrained parameter, try to align the refinements by computing + * `S1 =:= S2` (which might instantiate type parameters). + * This rule is contentious because it cuts the constraint set. * * For more info, see the comment in `TypeComparer#distributeAnd`. */ - final val alignArgsInAnd = false + final val alignArgsInAnd = true /** If this flag is set, higher-kinded applications are checked for validity */ diff --git a/compiler/src/dotty/tools/dotc/core/Constraint.scala b/compiler/src/dotty/tools/dotc/core/Constraint.scala index c99b748b7..50136a26c 100644 --- a/compiler/src/dotty/tools/dotc/core/Constraint.scala +++ b/compiler/src/dotty/tools/dotc/core/Constraint.scala @@ -111,12 +111,6 @@ abstract class Constraint extends Showable { */ def replace(param: PolyParam, tp: Type)(implicit ctx: Context): This - /** Narrow one of the bounds of type parameter `param` - * If `isUpper` is true, ensure that `param <: `bound`, otherwise ensure - * that `param >: bound`. - */ - def narrowBound(param: PolyParam, bound: Type, isUpper: Boolean)(implicit ctx: Context): This - /** Is entry associated with `pt` removable? This is the case if * all type parameters of the entry are associated with type variables * which have their `inst` fields set. diff --git a/compiler/src/dotty/tools/dotc/core/ConstraintHandling.scala b/compiler/src/dotty/tools/dotc/core/ConstraintHandling.scala index 3aa20f15b..89861f6db 100644 --- a/compiler/src/dotty/tools/dotc/core/ConstraintHandling.scala +++ b/compiler/src/dotty/tools/dotc/core/ConstraintHandling.scala @@ -44,6 +44,13 @@ trait ConstraintHandling { try op finally alwaysFluid = saved } + /** If set, align arguments `S1`, `S2`when taking the glb + * `T1 { X = S1 } & T2 { X = S2 }` of a constraint upper bound for some type parameter. + * Aligning means computing `S1 =:= S2` which may change the current constraint. + * See note in TypeComparer#distributeAnd. + */ + protected var homogenizeArgs = false + /** We are currently comparing polytypes. Used as a flag for * optimization: when `false`, no need to do an expensive `pruneLambdaParams` */ @@ -64,7 +71,8 @@ trait ConstraintHandling { } if (Config.checkConstraintsSeparated) assert(!occursIn(bound), s"$param occurs in $bound") - val c1 = constraint.narrowBound(param, bound, isUpper) + val newBound = narrowedBound(param, bound, isUpper) + val c1 = constraint.updateEntry(param, newBound) (c1 eq constraint) || { constraint = c1 val TypeBounds(lo, hi) = constraint.entry(param) @@ -72,6 +80,20 @@ trait ConstraintHandling { } } + /** Narrow one of the bounds of type parameter `param` + * If `isUpper` is true, ensure that `param <: `bound`, otherwise ensure + * that `param >: bound`. + */ + def narrowedBound(param: PolyParam, bound: Type, isUpper: Boolean)(implicit ctx: Context): TypeBounds = { + val oldBounds @ TypeBounds(lo, hi) = constraint.nonParamBounds(param) + val saved = homogenizeArgs + homogenizeArgs = Config.alignArgsInAnd + try + if (isUpper) oldBounds.derivedTypeBounds(lo, hi & bound) + else oldBounds.derivedTypeBounds(lo | bound, hi) + finally homogenizeArgs = saved + } + protected def addUpperBound(param: PolyParam, bound: Type): Boolean = { def description = i"constraint $param <: $bound to\n$constraint" if (bound.isRef(defn.NothingClass) && ctx.typerState.isGlobalCommittable) { diff --git a/compiler/src/dotty/tools/dotc/core/OrderingConstraint.scala b/compiler/src/dotty/tools/dotc/core/OrderingConstraint.scala index 72c7a8e51..61dd5a445 100644 --- a/compiler/src/dotty/tools/dotc/core/OrderingConstraint.scala +++ b/compiler/src/dotty/tools/dotc/core/OrderingConstraint.scala @@ -354,14 +354,6 @@ class OrderingConstraint(private val boundsMap: ParamBounds, updateEntry(p1, p1Bounds).replace(p2, p1) } - def narrowBound(param: PolyParam, bound: Type, isUpper: Boolean)(implicit ctx: Context): This = { - val oldBounds @ TypeBounds(lo, hi) = nonParamBounds(param) - val newBounds = - if (isUpper) oldBounds.derivedTypeBounds(lo, hi & bound) - else oldBounds.derivedTypeBounds(lo | bound, hi) - updateEntry(param, newBounds) - } - // ---------- Removals ------------------------------------------------------------ /** A new constraint which is derived from this constraint by removing diff --git a/compiler/src/dotty/tools/dotc/core/TypeComparer.scala b/compiler/src/dotty/tools/dotc/core/TypeComparer.scala index 744112280..6042cc12c 100644 --- a/compiler/src/dotty/tools/dotc/core/TypeComparer.scala +++ b/compiler/src/dotty/tools/dotc/core/TypeComparer.scala @@ -1315,7 +1315,7 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { // Given two refinements `T1 { X = S1 }` and `T2 { X = S2 }` rwrite to // `T1 & T2 { X B }` where `B` is the conjunction of the bounds of `X` in `T1` and `T2`. // - // However, if `Config.alignArgsInAnd` is set, and both aliases `X = Si` are + // However, if `homogenizeArgs` is set, and both aliases `X = Si` are // nonvariant, and `S1 =:= S2` (possibly by instantiating type parameters), // rewrite instead to `T1 & T2 { X = S1 }`. This rule is contentious because // it cuts the constraint set. On the other hand, without it we would replace @@ -1329,7 +1329,7 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { case tp: TypeAlias => tp.variance == 0 case _ => false } - if (Config.alignArgsInAnd && + if (homogenizeArgs && isNonvariantAlias(rinfo1) && isNonvariantAlias(rinfo2)) isSameType(rinfo1, rinfo2) -- cgit v1.2.3 From 10d868ce335d1ecbb0a6acb8d4bd804d76edcac9 Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Thu, 2 Mar 2017 18:14:24 +0100 Subject: More tests and a typo fixed --- .../src/dotty/tools/dotc/core/TypeComparer.scala | 2 +- tests/pos/t5070.scala | 23 ++++++++++++++++++++++ tests/pos/t5643.scala | 19 ++++++++++++++++++ 3 files changed, 43 insertions(+), 1 deletion(-) create mode 100644 tests/pos/t5643.scala (limited to 'compiler/src/dotty/tools/dotc/core/TypeComparer.scala') diff --git a/compiler/src/dotty/tools/dotc/core/TypeComparer.scala b/compiler/src/dotty/tools/dotc/core/TypeComparer.scala index 6042cc12c..168742257 100644 --- a/compiler/src/dotty/tools/dotc/core/TypeComparer.scala +++ b/compiler/src/dotty/tools/dotc/core/TypeComparer.scala @@ -1312,7 +1312,7 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { case tp1: RefinedType => tp2 match { case tp2: RefinedType if tp1.refinedName == tp2.refinedName => - // Given two refinements `T1 { X = S1 }` and `T2 { X = S2 }` rwrite to + // Given two refinements `T1 { X = S1 }` and `T2 { X = S2 }` rewrite to // `T1 & T2 { X B }` where `B` is the conjunction of the bounds of `X` in `T1` and `T2`. // // However, if `homogenizeArgs` is set, and both aliases `X = Si` are diff --git a/tests/pos/t5070.scala b/tests/pos/t5070.scala index 410afba14..0e5c0ffc0 100644 --- a/tests/pos/t5070.scala +++ b/tests/pos/t5070.scala @@ -13,3 +13,26 @@ class Test { implicitly[a.T](b(a)) // works } + + +class ImplicitVsTypeAliasTezt { + + class Monad[m[_]] { + type For[a] = _For[m, a] + implicit def toFor[a](m: m[a]): For[a] = throw new Error("todo") // lookup fails +// implicit def toFor[a](m: m[a]): _For[m, a] = throw new Error("todo") // fine. + } + + trait _For[m[_], a] { + def map[b](p: a => b): m[b] + } + + def useMonad[m[_], a](m: m[a])(implicit i: Monad[m]) = { + import i._ + + // value map is not a member of type parameter m[a] + for { + x <- m + } yield x.toString + } +} diff --git a/tests/pos/t5643.scala b/tests/pos/t5643.scala new file mode 100644 index 000000000..1ce34ba36 --- /dev/null +++ b/tests/pos/t5643.scala @@ -0,0 +1,19 @@ +object TupledEvidenceTest { + + abstract class TupledEvidence[M[_], T0] { type T = T0 } + + implicit def witnessTuple2[M[_], T1, T2](implicit ev1: M[T1], ev2: M[T2]): + TupledEvidence[M, (T1, T2)] { type T = (T1, T2) } = sys.error("") + + class GetResult[T] + + implicit val getString: GetResult[String] = new GetResult[String] + + implicit def getTuple[T](implicit w: TupledEvidence[GetResult, T]): GetResult[w.T] = sys.error("") + + def f[T : GetResult] = "" + + f[(String,String)](getTuple[(String, String)]) + + f[(String,String)] +} -- cgit v1.2.3 From c7f1f35c36593ac9454c8572a59c649610829b6a Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Fri, 3 Mar 2017 14:04:26 +0100 Subject: Adress reviewers comments --- compiler/src/dotty/tools/dotc/core/TypeComparer.scala | 2 +- tests/pending/pos/depmet_implicit_oopsla_session_2.scala | 8 +++++++- 2 files changed, 8 insertions(+), 2 deletions(-) (limited to 'compiler/src/dotty/tools/dotc/core/TypeComparer.scala') diff --git a/compiler/src/dotty/tools/dotc/core/TypeComparer.scala b/compiler/src/dotty/tools/dotc/core/TypeComparer.scala index 168742257..e423dd686 100644 --- a/compiler/src/dotty/tools/dotc/core/TypeComparer.scala +++ b/compiler/src/dotty/tools/dotc/core/TypeComparer.scala @@ -1331,7 +1331,7 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { } if (homogenizeArgs && isNonvariantAlias(rinfo1) && isNonvariantAlias(rinfo2)) - isSameType(rinfo1, rinfo2) + isSameType(rinfo1, rinfo2) // establish new constraint tp1.derivedRefinedType(parent, tp1.refinedName, rinfo1 & rinfo2) case _ => diff --git a/tests/pending/pos/depmet_implicit_oopsla_session_2.scala b/tests/pending/pos/depmet_implicit_oopsla_session_2.scala index fcf18691a..26fa2a4cc 100644 --- a/tests/pending/pos/depmet_implicit_oopsla_session_2.scala +++ b/tests/pending/pos/depmet_implicit_oopsla_session_2.scala @@ -1,4 +1,10 @@ +// Fails on line 70 with: no implicit argument of type Sessions.Session[ +// | Sessions.In[Int, Sessions.In[Int, Sessions.Out[Int, Sessions.Stop]]]^ +// |]#HasDual[Sessions.Out[Int, Sessions.Out[Int, Sessions.In[Int, Sessions.Stop]]]^ +// | ] found for parameter evidence$1 of method runSession in object Sessions +// This could be related to existential types (the # essentially boils down to one). object Sessions { + def ?[T <: AnyRef](implicit w: T): w.type = w // session states sealed case class Stop() @@ -17,7 +23,7 @@ object Sessions { // friendly interface to the theory def runSession[S, D: Session[S]#HasDual](session: S, dual: D) = - implicitly[Session[S]#HasDual[D]].run(session, dual) + ?[Session[S]#HasDual[D]].run(session, dual) // facts in the theory: -- cgit v1.2.3