New subtype constraint maintenance algorithm.

Objective: Avoid cycles by detecting all cases where

    A <: B and B <: A

and removing those cases by unifuing A and B.

Cycles need to be avoided because they lead to deep subtype recursions.

8 files changed, 101 insertions, 55 deletions

diff --git a/src/dotty/tools/dotc/CompilationUnit.scala b/src/dotty/tools/dotc/CompilationUnit.scala
index 791e8899d..9c1431459 100644
--- a/src/dotty/tools/dotc/CompilationUnit.scala
+++ b/src/dotty/tools/dotc/CompilationUnit.scala
@@ -13,5 +13,4 @@ class CompilationUnit(val source: SourceFile) {
   var tpdTree: tpd.Tree = tpd.EmptyTree
 
   def isJava = source.file.name.endsWith(".java")
-
 }
\ No newline at end of file
diff --git a/src/dotty/tools/dotc/Main.scala b/src/dotty/tools/dotc/Main.scala
index 8809cd149..217bb3f65 100644
--- a/src/dotty/tools/dotc/Main.scala
+++ b/src/dotty/tools/dotc/Main.scala
@@ -12,7 +12,6 @@ import reporting.Reporter
  *   - simplify hk types
  *   - make use of AndOrType
  *   - review isSubType
- *   - cycle check for implicits
  *   - have a second look at normalization (leave at method types if pt is method type?)
  *   - fix problem with duplicate companion objects for classes with default parameters in constructors
  */
diff --git a/src/dotty/tools/dotc/config/Config.scala b/src/dotty/tools/dotc/config/Config.scala
index 714b8633e..b47233bd8 100644
--- a/src/dotty/tools/dotc/config/Config.scala
+++ b/src/dotty/tools/dotc/config/Config.scala
@@ -12,6 +12,8 @@ object Config {
 
   final val checkConstraintsNonCyclic = true
 
+  final val traceDeepSubTypes = false
+
   final val verboseExplainSubtype = true
 
   /** When set, use new signature-based matching.
diff --git a/src/dotty/tools/dotc/core/Constraint.scala b/src/dotty/tools/dotc/core/Constraint.scala
index a9fa8f0c6..8704a35d8 100644
--- a/src/dotty/tools/dotc/core/Constraint.scala
+++ b/src/dotty/tools/dotc/core/Constraint.scala
@@ -79,8 +79,8 @@ class Constraint(val myMap: SimpleMap[PolyType, Array[Type]]) extends AnyVal wit
       val param = PolyParam(pt, i)
       entry match {
         case TypeBounds(lo, hi) =>
-          assert(lo != param, param)
-          assert(hi != param, param)
+          assert(!param.occursIn(lo, fromBelow = false), s"$param occurs above $lo")
+          assert(!param.occursIn(hi, fromBelow = true), s"$param occurs below $hi")
         case _ =>
       }
     }
@@ -126,47 +126,44 @@ class Constraint(val myMap: SimpleMap[PolyType, Array[Type]]) extends AnyVal wit
     noneLeft
   }
 
+  /** Drop parameter `PolyParam(poly, n)` from `bounds`,
+   *  replacing with Nothing in the lower bound and by `Any` in the upper bound.
+   */
+  def dropParamIn(bounds: TypeBounds, poly: PolyType, n: Int)(implicit ctx: Context): TypeBounds = {
+    def drop(tp: Type): Type = tp match {
+      case tp: AndOrType =>
+        val tp1 = drop(tp.tp1)
+        val tp2 = drop(tp.tp2)
+        if (!tp1.exists) tp2
+        else if (!tp2.exists) tp1
+        else tp
+      case PolyParam(`poly`, `n`) => NoType
+      case _ => tp
+    }
+    def approx(tp: Type, limit: Type): Type = {
+      val tp1 = drop(tp)
+      if (tp1.exists || !tp.exists) tp1 else limit
+    }
+    bounds.derivedTypeBounds(
+        approx(bounds.lo, defn.NothingType), approx(bounds.hi, defn.AnyType))
+  }
+
   /** 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`.
    */
   def replace(param: PolyParam, tp: Type)(implicit ctx: Context): Constraint = {
 
-    /** Drop parameter `PolyParam(poly, n)` from bounds in type `tp` */
-    def dropParamIn(tp: Type, poly: PolyType, n: Int, fromBelow: Boolean = false): Type = {
-      def drop(tp: Type): Type = tp match {
-        case tp: AndOrType =>
-          val tp1 = drop(tp.tp1)
-          val tp2 = drop(tp.tp2)
-          if (!tp1.exists) tp2
-          else if (!tp2.exists) tp1
-          else tp
-        case PolyParam(`poly`, `n`) => NoType
-        case _ => tp
-      }
-      tp match {
-        case tp: TypeBounds =>
-          tp.derivedTypeBounds(
-              dropParamIn(tp.lo, poly, n, !fromBelow),
-              dropParamIn(tp.hi, poly, n, fromBelow))
-        case _ =>
-          val tp1 = drop(tp)
-          if (tp1.exists || !tp.exists) tp1
-          else if (fromBelow) defn.NothingType
-          else defn.AnyType
-      }
-    }
-
     def subst(poly: PolyType, entries: Array[Type]) = {
       var result = entries
       var i = 0
       while (i < paramCount(entries)) {
         entries(i) match {
           case oldBounds: TypeBounds =>
-            val newBounds = oldBounds.substParam(param, tp)
+            val newBounds = oldBounds.substParam(param, tp).asInstanceOf[TypeBounds]
             if (oldBounds ne newBounds) {
               if (result eq entries) result = entries.clone
-              result(i) = dropParamIn(newBounds, poly, i, fromBelow = false)
+              result(i) = dropParamIn(newBounds, poly, i)
             }
           case _ =>
         }
diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala
index cdef1ab2c..0969f814f 100644
--- a/src/dotty/tools/dotc/core/TypeComparer.scala
+++ b/src/dotty/tools/dotc/core/TypeComparer.scala
@@ -53,6 +53,16 @@ class TypeComparer(initctx: Context) extends DotClass {
     myObjectClass
   }
 
+  /** 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)
+    isSubType(bounds.lo, bounds.hi) ||
+    { constraint = saved; false } // don't leave the constraint in unsatisfiable state
+  }
+
   private def addConstraint1(param: PolyParam, bound: Type, fromBelow: Boolean): Boolean = {
     val oldBounds = constraint.bounds(param)
     assert(!bound.isInstanceOf[TypeVar])
@@ -64,18 +74,22 @@ class TypeComparer(initctx: Context) extends DotClass {
         else oldBounds.derivedTypeBounds(oldBounds.lo, oldBounds.hi & bound)
       finally ignoreConstraint = saved
     val res =
-      (param == bound) ||
-        (oldBounds eq newBounds) || {
-          val saved = constraint
-          constraint = constraint.updated(param, newBounds)
-          isSubType(newBounds.lo, newBounds.hi) ||
-            { constraint = saved; false } // don't leave the constraint in unsatisfiable state
-        }
+      (param == bound) || (oldBounds eq newBounds) || updateConstraint(param, newBounds)
     constr.println(s"add 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")
+    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))
+  }
+
   /** If current constraint set is not frozen, add the constraint
    *
    *      param >: bound   if fromBelow is true
@@ -89,14 +103,27 @@ class TypeComparer(initctx: Context) extends DotClass {
   def addConstraint(param: PolyParam, bound: Type, fromBelow: Boolean): Boolean = {
     param == bound ||
     !frozenConstraint && {
-      constr.println(s"adding ${param.show} ${if (fromBelow) ">:>" else "<:<"} ${bound.show} to ${constraint.show}")
-      bound match {
+      constr.println(s"adding ${param.show} ${if (fromBelow) ">:>" else "<:<"} ${bound.show} (${bound.getClass}) to ${constraint.show}")
+      val res = bound match {
         case bound: PolyParam if constraint contains bound =>
-          addConstraint1(param, bound, fromBelow) &&
-          addConstraint1(bound, param, !fromBelow)
+          val TypeBounds(lo, hi) = constraint.bounds(bound)
+          if (lo eq hi)
+            addConstraint(param, lo, fromBelow)
+          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 _ =>
           addConstraint1(param, bound, fromBelow)
       }
+      constr.println(s"added ${param.show} ${if (fromBelow) ">:>" else "<:<"} ${bound.show} = ${constraint.show}")
+      res
     }
   }
 
@@ -174,9 +201,9 @@ class TypeComparer(initctx: Context) extends DotClass {
   def monitoredIsSubType(tp1: Type, tp2: Type) = {
     if (pendingSubTypes == null) {
       pendingSubTypes = new mutable.HashSet[(Type, Type)]
-      ctx.log(s"!!! deep subtype recursion involving $tp1 <:< $tp2")
-      if (!this.isInstanceOf[ExplainingTypeComparer])
-        ctx.log(TypeComparer.explained(implicit ctx => tp1 <:< tp2))
+      ctx.log(s"!!! deep subtype recursion involving ${tp1.show} <:< ${tp2.show}, constraint = ${ctx.typerState.constraint.show}")
+      if (Config.traceDeepSubTypes && !this.isInstanceOf[ExplainingTypeComparer])
+        ctx.log(TypeComparer.explained(implicit ctx => ctx.typeComparer.isSubType(tp1, tp2)))
     }
     val p = (tp1, tp2)
     !pendingSubTypes(p) && {
@@ -190,13 +217,6 @@ class TypeComparer(initctx: Context) extends DotClass {
   }
 
   def firstTry(tp1: Type, tp2: Type): Boolean = ctx.debugTraceIndented(s"$tp1 <:< $tp2") {
-    if (false && (tp2 isRef defn.NothingClass) && !frozenConstraint) {
-      tp1 match {
-        case tp1 @ TypeRef(_, name) =>
-          assert(name.toString != "CONS$$U", tp1.info + "/" + tp1.symbol.isAliasType)
-        case _ =>
-      }
-    }
     tp2 match {
       case tp2: NamedType =>
         tp1 match {
diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala
index 930922b5b..f9119d060 100644
--- a/src/dotty/tools/dotc/core/Types.scala
+++ b/src/dotty/tools/dotc/core/Types.scala
@@ -1383,10 +1383,13 @@ object Types {
   trait AndOrType extends ValueType { // todo: check where we can simplify using AndOrType
     def tp1: Type
     def tp2: Type
+    def isAnd: Boolean
   }
 
   abstract case class AndType(tp1: Type, tp2: Type) extends CachedGroundType with AndOrType {
 
+    def isAnd = true
+
     def derivedAndType(tp1: Type, tp2: Type)(implicit ctx: Context) =
       if ((tp1 eq this.tp1) && (tp2 eq this.tp2)) this
       else AndType(tp1, tp2)
@@ -1409,6 +1412,8 @@ object Types {
   abstract case class OrType(tp1: Type, tp2: Type) extends CachedGroundType with AndOrType {
     assert(tp1.isInstanceOf[ValueType] && tp2.isInstanceOf[ValueType], s"$tp1 | $tp2")
 
+    def isAnd = false
+
     def derivedOrType(tp1: Type, tp2: Type)(implicit ctx: Context) =
       if ((tp1 eq this.tp1) && (tp2 eq this.tp2)) this
       else OrType(tp1, tp2)
@@ -1660,6 +1665,20 @@ object Types {
   case class PolyParam(binder: PolyType, paramNum: Int) extends ParamType {
     type BT = PolyType
     def copy(bt: BT) = PolyParam(bt, paramNum)
+
+    /** Looking only at the structure of `bound`, is one of the following true?
+     *     - fromBelow and param <:< bound
+     *     - !fromBelow and param >:> bound
+     */
+    def occursIn(bound: Type, fromBelow: Boolean): Boolean = bound 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
+      case _ => false
+    }
+
     override def underlying(implicit ctx: Context): Type = binder.paramBounds(paramNum)
     // no customized hashCode/equals needed because cycle is broken in PolyType
     override def toString = s"PolyParam(${binder.paramNames(paramNum)})"
diff --git a/src/dotty/tools/dotc/typer/FrontEnd.scala b/src/dotty/tools/dotc/typer/FrontEnd.scala
index 25c9de717..1cea9fe7c 100644
--- a/src/dotty/tools/dotc/typer/FrontEnd.scala
+++ b/src/dotty/tools/dotc/typer/FrontEnd.scala
@@ -11,19 +11,27 @@ class FrontEnd extends Phase {
 
   def name = "frontend"
 
-  def parse(implicit ctx: Context) = {
+  def monitor(doing: String)(body: => Unit)(implicit ctx: Context) =
+    try body
+    catch {
+      case ex: Throwable =>
+        println(s"exception occured while $doing ${ctx.compilationUnit}")
+        throw ex
+    }
+
+  def parse(implicit ctx: Context) = monitor("parsing") {
     val unit = ctx.compilationUnit
     unit.untpdTree = new Parser(unit.source).parse()
     typr.println("parsed:\n"+unit.untpdTree.show)
   }
 
-  def enterSyms(implicit ctx: Context) = {
+  def enterSyms(implicit ctx: Context) = monitor("indexing") {
     val unit = ctx.compilationUnit
     ctx.typer.index(unit.untpdTree)
     typr.println("entered: "+unit.source)
   }
 
-  def typeCheck(implicit ctx: Context) = {
+  def typeCheck(implicit ctx: Context) = monitor("typechecking") {
     val unit = ctx.compilationUnit
     unit.tpdTree = ctx.typer.typedExpr(unit.untpdTree)
     typr.println("typed: "+unit.source)
diff --git a/src/dotty/tools/dotc/util/SourceFile.scala b/src/dotty/tools/dotc/util/SourceFile.scala
index 5691ddcb8..4e1eb224a 100644
--- a/src/dotty/tools/dotc/util/SourceFile.scala
+++ b/src/dotty/tools/dotc/util/SourceFile.scala
@@ -125,6 +125,8 @@ case class SourceFile(file: AbstractFile, content: Array[Char]) {
     }
     col + 1
   }
+
+  override def toString = file.toString
 }
 
 object NoSource extends SourceFile("<no source>", Nil) {