Fixes to constraint handling.

In particular, need to unify polyparams before replacing one with the other, if the result wiould lead to a cyclic constraint.

Also: Avoid setting `inst` field of a type variable if a subtype operation is in progress, because the constraint might be retracted, and the instantiation should be retracted with it.

Third, tighter checks of cyclic constraint, and deep subtype recursions can now be demanded to cause an abort.

3 files changed, 70 insertions, 23 deletions

diff --git a/src/dotty/tools/dotc/core/Constraint.scala b/src/dotty/tools/dotc/core/Constraint.scala
index b47cc921c..1df3c6ac5 100644
--- a/src/dotty/tools/dotc/core/Constraint.scala
+++ b/src/dotty/tools/dotc/core/Constraint.scala
@@ -71,7 +71,7 @@ class Constraint(val myMap: SimpleMap[PolyType, Array[Type]]) extends AnyVal wit
   /** A new constraint which is derived from this constraint by adding or replacing
    *  the entries corresponding to `pt` with `entries`.
    */
-  private def updateEntries(pt: PolyType, entries: Array[Type]): Constraint = {
+  private def updateEntries(pt: PolyType, entries: Array[Type])(implicit ctx: Context) : Constraint = {
     import Constraint._
     val res = new Constraint(myMap.updated(pt, entries))
     if (Config.checkConstraintsNonCyclic) checkNonCyclic(pt, entries)
@@ -82,23 +82,28 @@ class Constraint(val myMap: SimpleMap[PolyType, Array[Type]]) extends AnyVal wit
     res
   }
 
-  /** Check that no constrained parameter contains itself as a bound */
-  def checkNonCyclic(pt: PolyType, entries: Array[Type]) =
+  /** Check that no constrained parameter in `pt` contains itself as a bound */
+  def checkNonCyclic(pt: PolyType, entries: Array[Type])(implicit ctx: Context): Unit =
     for ((entry, i) <- entries.zipWithIndex) {
       val param = PolyParam(pt, i)
       entry match {
         case TypeBounds(lo, hi) =>
-          assert(!param.occursIn(lo, fromBelow = false), s"$param occurs above $lo")
-          assert(!param.occursIn(hi, fromBelow = true), s"$param occurs below $hi")
+          assert(!param.occursIn(lo, fromBelow = true), s"$param occurs below $lo")
+          assert(!param.occursIn(hi, fromBelow = false), s"$param occurs above $hi")
         case _ =>
       }
     }
 
+  /** Check that no constrained parameter contains itself as a bound */
+  def checkNonCyclic()(implicit ctx: Context): Unit = {
+    for (pt <- domainPolys) checkNonCyclic(pt, myMap(pt))
+  }
+
   /** A new constraint which is derived from this constraint by updating
    *  the entry for parameter `param` to `tpe`.
    *  @pre  `this contains param`.
    */
-  def updated(param: PolyParam, tpe: Type): Constraint = {
+  def updated(param: PolyParam, tpe: Type)(implicit ctx: Context): Constraint = {
     val newEntries = myMap(param.binder).clone
     newEntries(param.paramNum) = tpe
     updateEntries(param.binder, newEntries)
@@ -108,7 +113,7 @@ class Constraint(val myMap: SimpleMap[PolyType, Array[Type]]) extends AnyVal wit
    *  `op` over all entries of type `poly`.
    *  @pre  `this contains poly`.
    */
-  def transformed(poly: PolyType, op: Type => Type): Constraint =
+  def transformed(poly: PolyType, op: Type => Type)(implicit ctx: Context) : Constraint =
     updateEntries(poly, myMap(poly) map op)
 
   /** A new constraint with all entries coming from `pt` removed. */
@@ -161,7 +166,7 @@ class Constraint(val myMap: SimpleMap[PolyType, Array[Type]]) extends AnyVal wit
    *  the type parameter `param` from the domain and replacing all occurrences
    *  of the parameter elsewhere in the constraint by type `tp`.
    */
-  def replace(param: PolyParam, tp: Type)(implicit ctx: Context): Constraint = {
+  private def uncheckedReplace(param: PolyParam, tp: Type)(implicit ctx: Context): Constraint = {
 
     def subst(poly: PolyType, entries: Array[Type]) = {
       var result = entries
@@ -183,13 +188,46 @@ class Constraint(val myMap: SimpleMap[PolyType, Array[Type]]) extends AnyVal wit
 
     val pt = param.binder
     val constr1 = if (isRemovable(pt, param.paramNum)) remove(pt) else updated(param, tp)
-    new Constraint(constr1.myMap mapValues subst)
+    val result = new Constraint(constr1.myMap mapValues subst)
+    if (Config.checkConstraintsNonCyclic) result.checkNonCyclic()
+    result
+  }
+
+  /** A new constraint which is derived from this constraint by removing
+   *  the type parameter `param` from the domain and replacing all occurrences
+   *  of the parameter elsewhere in the constraint by type `tp`.
+   *  `tp` is another polyparam, applies the necessary unifications to avoud a cyclic
+   *  constraint.
+   */
+  def replace(param: PolyParam, tp: Type)(implicit ctx: Context): Constraint =
+    tp.dealias.stripTypeVar match {
+      case tp: PolyParam if this contains tp =>
+        val bs = bounds(tp)
+        if (tp == param)
+          this
+        else if (param.occursIn(bs.lo, fromBelow = true) ||
+                 param.occursIn(bs.hi, fromBelow = false))
+          unify(tp, param).uncheckedReplace(param, tp)
+        else
+          uncheckedReplace(param, tp)
+      case _ =>
+        uncheckedReplace(param, tp)
+    }
+
+  /** A constraint resulting by adding p2 = p1 to this constraint, and at the same
+   *  time transferring all bounds of p2 to p1
+   */
+  def unify(p1: PolyParam, p2: PolyParam)(implicit ctx: Context): Constraint = {
+    val p1Bounds =
+      dropParamIn(bounds(p1), p2.binder, p2.paramNum) &
+      dropParamIn(bounds(p2), p1.binder, p1.paramNum)
+    this.updated(p1, p1Bounds).updated(p2, TypeAlias(p1))
   }
 
   /** A new constraint which is derived from this constraint by adding
    *  entries for all type parameters of `poly`.
    */
-  def add(poly: PolyType, tvars: List[TypeVar] = Nil): Constraint = {
+  def add(poly: PolyType, tvars: List[TypeVar] = Nil)(implicit ctx: Context) : Constraint = {
     val nparams = poly.paramNames.length
     val entries = new Array[Type](nparams * 2)
     poly.paramBounds.copyToArray(entries, 0)
diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala
index 221b20e51..0834c310f 100644
--- a/src/dotty/tools/dotc/core/TypeComparer.scala
+++ b/src/dotty/tools/dotc/core/TypeComparer.scala
@@ -34,6 +34,13 @@ class TypeComparer(initctx: Context) extends DotClass {
    */
   protected var ignoreConstraint = false
 
+  /** Is a subtype check in course? In that case we may not
+   *  permanently instantiate type variables, because the corresponding
+   *  constraint might still be retracted and the instantiation should
+   *  then be reversed.
+   */
+  def subtypeCheckInProgress: Boolean = recCount >= 0
+
   private var myAnyClass: ClassSymbol = null
   private var myNothingClass: ClassSymbol = null
   private var myNullClass: ClassSymbol = null
@@ -86,11 +93,9 @@ class TypeComparer(initctx: Context) extends DotClass {
   /** Make p2 = p1, transfer all bounds of p2 to p1 */
   private def unify(p1: PolyParam, p2: PolyParam): Boolean = {
     constr.println(s"unifying $p1 $p2")
-    val p1Bounds =
-      constraint.dropParamIn(constraint.bounds(p1), p2.binder, p2.paramNum) &
-      constraint.dropParamIn(constraint.bounds(p2), p1.binder, p1.paramNum)
-    updateConstraint(p1, p1Bounds) &&
-    updateConstraint(p2, TypeAlias(p1))
+    val constraint1 = constraint.unify(p1, p2)
+    val bounds = constraint1.bounds(p1)
+    isSubType(bounds.lo, bounds.hi) && { constraint = constraint1; true }
   }
 
   /** If current constraint set is not frozen, add the constraint
@@ -216,8 +221,9 @@ class TypeComparer(initctx: Context) extends DotClass {
     if (pendingSubTypes == null) {
       pendingSubTypes = new mutable.HashSet[(Type, Type)]
       ctx.log(s"!!! deep subtype recursion involving ${tp1.show} <:< ${tp2.show}, constraint = ${ctx.typerState.constraint.show}")
-      assert(!Config.flagDeepRecursions)
-      if (Config.traceDeepSubTypes && !this.isInstanceOf[ExplainingTypeComparer])
+      ctx.log(s"!!! constraint = ${constraint.show}")
+      assert(!Config.flagDeepSubTypeRecursions)
+      if (Config.traceDeepSubTypeRecursions && !this.isInstanceOf[ExplainingTypeComparer])
         ctx.log(TypeComparer.explained(implicit ctx => ctx.typeComparer.isSubType(tp1, tp2)))
     }
     val p = (tp1, tp2)
diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala
index bfe4ae5be..6c9bc4f10 100644
--- a/src/dotty/tools/dotc/core/Types.scala
+++ b/src/dotty/tools/dotc/core/Types.scala
@@ -1696,12 +1696,12 @@ object Types {
      *     - fromBelow and param <:< bound
      *     - !fromBelow and param >:> bound
      */
-    def occursIn(bound: Type, fromBelow: Boolean): Boolean = bound match {
+    def occursIn(bound: Type, fromBelow: Boolean)(implicit ctx: Context): Boolean = bound.stripTypeVar match {
       case bound: PolyParam => bound == this
       case bound: AndOrType =>
         def occ1 = occursIn(bound.tp1, fromBelow)
         def occ2 = occursIn(bound.tp2, fromBelow)
-        if (fromBelow == bound.isAnd) occ1 & occ2 else occ1 || occ2
+        if (fromBelow == bound.isAnd) occ1 && occ2 else occ1 || occ2
       case _ => false
     }
 
@@ -1761,10 +1761,11 @@ object Types {
 
     /** Instantiate variable with given type */
     private def instantiateWith(tp: Type)(implicit ctx: Context): Type = {
-      assert(tp ne this)
+      assert(tp ne this, s"self instantiation of ${tp.show}, constraint = ${ctx.typerState.constraint.show}")
       typr.println(s"instantiating ${this.show} with ${tp.show}")
       assert(ctx.typerState.constraint contains this) // !!! DEBUG
-      if (ctx.typerState eq owningState) inst = tp
+      if ((ctx.typerState eq owningState) && !ctx.typeComparer.subtypeCheckInProgress)
+        inst = tp
       ctx.typerState.constraint = ctx.typerState.constraint.replace(origin, tp)
       tp
     }
@@ -1807,8 +1808,10 @@ object Types {
     override def hashCode: Int = System.identityHashCode(this)
     override def equals(that: Any) = this eq that.asInstanceOf[AnyRef]
 
-    override def toString =
-      if (inst.exists) inst.toString else s"TypeVar($origin)"
+    override def toString = {
+      def instStr = if (inst.exists) s" -> $inst" else ""
+      s"TypeVar($origin$instStr)"
+    }
   }
 
   // ------ ClassInfo, Type Bounds ------------------------------------------------------------