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.

1 files changed, 19 insertions, 0 deletions

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)})"