From a4ac5e066ee3072a78eec1a4125cc46ba823d41b Mon Sep 17 00:00:00 2001
From: Martin Odersky <odersky@gmail.com>
Date: Fri, 14 Oct 2016 22:45:35 +0200
Subject: Fix-#1500 Include constraining type variables when interpolating

Fixes #1500. Review by @smarter.
---
 src/dotty/tools/dotc/typer/Inferencing.scala | 44 ++++++++++++++++++++++++----
 1 file changed, 39 insertions(+), 5 deletions(-)

(limited to 'src')

diff --git a/src/dotty/tools/dotc/typer/Inferencing.scala b/src/dotty/tools/dotc/typer/Inferencing.scala
index 9a1a42e44..646fe3f3e 100644
--- a/src/dotty/tools/dotc/typer/Inferencing.scala
+++ b/src/dotty/tools/dotc/typer/Inferencing.scala
@@ -261,7 +261,7 @@ object Inferencing {
       else
         for (tvar <- constraint.uninstVars)
           if (!(vs contains tvar) && qualifies(tvar)) {
-            typr.println(s"instantiating non-occurring ${tvar.show} in ${tp.show}")
+            typr.println(s"instantiating non-occurring ${tvar.show} in ${tp.show} / $tp")
             tvar.instantiate(fromBelow = true)
           }
     }
@@ -306,12 +306,16 @@ object Inferencing {
    *  we want to instantiate U to x.type right away. No need to wait further.
    */
   private def variances(tp: Type, include: TypeVar => Boolean)(implicit ctx: Context): VarianceMap = Stats.track("variances") {
-    val accu = new TypeAccumulator[VarianceMap] {
+    val constraint = ctx.typerState.constraint
+
+    object accu extends TypeAccumulator[VarianceMap] {
+      def setVariance(v: Int) = variance = v
       def apply(vmap: VarianceMap, t: Type): VarianceMap = t match {
-        case t: TypeVar if !t.isInstantiated && (ctx.typerState.constraint contains t) && include(t) =>
+        case t: TypeVar
+        if !t.isInstantiated && (ctx.typerState.constraint contains t) && include(t) =>
           val v = vmap(t)
           if (v == null) vmap.updated(t, variance)
-          else if (v == variance) vmap
+          else if (v == variance || v == 0) vmap
           else vmap.updated(t, 0)
         case _ =>
           foldOver(vmap, t)
@@ -319,7 +323,37 @@ object Inferencing {
       override def applyToPrefix(vmap: VarianceMap, t: NamedType) =
         apply(vmap, t.prefix)
     }
-    accu(SimpleMap.Empty, tp)
+
+    /** Include in `vmap` type variables occurring in the constraints of type variables
+     *  already in `vmap`. Specifically:
+     *   - if `tvar` is covariant in `vmap`, include all variables in its lower bound
+     *     (because they influence the minimal solution of `tvar`),
+     *   - if `tvar` is contravariant in `vmap`, include all variables in its upper bound
+     *     at flipped variances (because they influence the maximal solution of `tvar`),
+     *   - if `tvar` is nonvariant in `vmap`, include all variables in its upper and lower
+     *     bounds as non-variant.
+     *  Do this in a fixpoint iteration until `vmap` stabilizes.
+     */
+    def propagate(vmap: VarianceMap): VarianceMap = {
+      var vmap1 = vmap
+      def traverse(tp: Type) = { vmap1 = accu(vmap1, tp) }
+      vmap.foreachBinding { (tvar, v) =>
+        val param = tvar.origin
+        val e = constraint.entry(param)
+        accu.setVariance(v)
+        if (v >= 0) {
+          traverse(e.bounds.lo)
+          constraint.lower(param).foreach(p => traverse(constraint.typeVarOfParam(p)))
+        }
+        if (v <= 0) {
+          traverse(e.bounds.hi)
+          constraint.upper(param).foreach(p => traverse(constraint.typeVarOfParam(p)))
+        }
+      }
+      if (vmap1 eq vmap) vmap else propagate(vmap1)
+    }
+
+    propagate(accu(SimpleMap.Empty, tp))
   }
 }
 
-- 
cgit v1.2.3


From f368dd523fd68bb5edc992676ae35b69bbd90db8 Mon Sep 17 00:00:00 2001
From: Guillaume Martres <smarter@ubuntu.com>
Date: Tue, 25 Oct 2016 17:52:19 +0200
Subject: Remove fixpoint computation of interpolateUndetVars

This is not necessary now that `variances` includes a fixpoint
computation
---
 src/dotty/tools/dotc/typer/Inferencing.scala | 15 +++++----------
 1 file changed, 5 insertions(+), 10 deletions(-)

(limited to 'src')

diff --git a/src/dotty/tools/dotc/typer/Inferencing.scala b/src/dotty/tools/dotc/typer/Inferencing.scala
index 646fe3f3e..aede4974a 100644
--- a/src/dotty/tools/dotc/typer/Inferencing.scala
+++ b/src/dotty/tools/dotc/typer/Inferencing.scala
@@ -223,7 +223,6 @@ object Inferencing {
       constr.println(s"qualifying undet vars: ${constraint.uninstVars filter qualifies map (tvar => s"$tvar / ${tvar.show}")}, constraint: ${constraint.show}")
 
       val vs = variances(tp, qualifies)
-      var changed = false
       val hasUnreportedErrors = ctx.typerState.reporter match {
         case r: StoreReporter if r.hasErrors => true
         case _ => false
@@ -253,17 +252,13 @@ object Inferencing {
           if (v != 0) {
             typr.println(s"interpolate ${if (v == 1) "co" else "contra"}variant ${tvar.show} in ${tp.show}")
             tvar.instantiate(fromBelow = v == 1)
-            changed = true
           }
         }
-      if (changed) // instantiations might have uncovered new typevars to interpolate
-        interpolateUndetVars(tree, ownedBy)
-      else
-        for (tvar <- constraint.uninstVars)
-          if (!(vs contains tvar) && qualifies(tvar)) {
-            typr.println(s"instantiating non-occurring ${tvar.show} in ${tp.show} / $tp")
-            tvar.instantiate(fromBelow = true)
-          }
+      for (tvar <- constraint.uninstVars)
+        if (!(vs contains tvar) && qualifies(tvar)) {
+          typr.println(s"instantiating non-occurring ${tvar.show} in ${tp.show} / $tp")
+          tvar.instantiate(fromBelow = true)
+        }
     }
     if (constraint.uninstVars exists qualifies) interpolate()
   }
-- 
cgit v1.2.3