wip on typecomparers

1 files changed, 311 insertions, 36 deletions

diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala
index 3a15a50e1..8762cf637 100644
--- a/src/dotty/tools/dotc/core/TypeComparer.scala
+++ b/src/dotty/tools/dotc/core/TypeComparer.scala
@@ -23,6 +23,8 @@ class TypeComparer(initctx: Context) extends DotClass {
   private var pendingSubTypes: mutable.Set[(Type, Type)] = null
   private var recCount = 0
 
+  final val oldCompare = true // ###
+
   /** If the constraint is frozen we cannot add new bounds to the constraint. */
   protected var frozenConstraint = false
 
@@ -102,34 +104,40 @@ class TypeComparer(initctx: Context) extends DotClass {
    *  @return Whether the augmented constraint is still satisfiable.
    */
   def addConstraint(param: PolyParam, bound: Type, fromBelow: Boolean): Boolean = {
-    param == bound ||
-    !frozenConstraint && {
-      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 =>
-          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 bound: WildcardType =>
+    param == bound || // ###
+    !frozenConstraint && { // ###
+
+    constr.println(s"adding ${param.show} ${if (fromBelow) ">:>" else "<:<"} ${bound.show} (${bound.getClass}) to ${constraint.show}")
+    val res = bound.dealias.stripTypeVar match {
+      case bound: PolyParam if constraint contains bound =>
+        val TypeBounds(lo, hi) = constraint.bounds(bound)
+        if (lo eq hi)
+          addConstraint(param, lo, fromBelow)
+        else if (param == bound)
           true
-        case _ =>
-          addConstraint1(param, bound, fromBelow)
-      }
-      constr.println(s"added ${param.show} ${if (fromBelow) ">:>" else "<:<"} ${bound.show} = ${constraint.show}")
-      res
+        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 bound: WildcardType =>
+        true
+      case bound => // !!! remove to keep the originals
+        addConstraint1(param, bound, fromBelow)
     }
+    constr.println(s"added ${param.show} ${if (fromBelow) ">:>" else "<:<"} ${bound.show} = ${constraint.show}")
+    res
+    } // ###
   }
 
+  def isConstrained(param: PolyParam): Boolean =
+    !frozenConstraint && (constraint contains param)
+
   /** Solve constraint set for given type parameter `param`.
    *  If `fromBelow` is true the parameter is approximated by its lower bound,
    *  otherwise it is approximated by its upper bound. However, any occurrences
@@ -162,6 +170,9 @@ class TypeComparer(initctx: Context) extends DotClass {
     finally frozenConstraint = saved
   }
 
+  def isNonBottomSubType(tp1: Type, tp2: Type): Boolean =
+    !(tp2 isRef NothingClass) && isSubType(tp1, tp2)
+
   def isSubType(tp1: Type, tp2: Type): Boolean =
     if (tp1 == NoType || tp2 == NoType) false
     else if (tp1 eq tp2) true
@@ -177,7 +188,8 @@ class TypeComparer(initctx: Context) extends DotClass {
         }
 */
         val result =
-          if (recCount < LogPendingSubTypesThreshold) firstTry(tp1, tp2)
+          if (recCount < LogPendingSubTypesThreshold)
+            if (oldCompare) firstTry(tp1, tp2) else compare(tp1, tp2)
           else monitoredIsSubType(tp1, tp2)
         recCount -= 1
         if (!result) constraint = saved
@@ -212,14 +224,277 @@ class TypeComparer(initctx: Context) extends DotClass {
     !pendingSubTypes(p) && {
       try {
         pendingSubTypes += p
-        firstTry(tp1, tp2)
+        if (oldCompare) firstTry(tp1, tp2) else compare(tp1, tp2)
       } finally {
         pendingSubTypes -= p
       }
     }
   }
 
-  def firstTry(tp1: Type, tp2: Type): Boolean = ctx.debugTraceIndented(s"$tp1 <:< $tp2") {
+  def compare(tp1: Type, tp2: Type): Boolean = ctx.debugTraceIndented(s"$tp1 <:< $tp2") {
+    tp2 match {
+      case tp2: ProtoType =>
+        isMatchedByProto(tp2, tp1)
+      case tp2: TypeVar =>
+        isSubType(tp1, tp2.underlying)
+      case tp2: WildcardType =>
+        def compareWildcard = tp2.optBounds match {
+          case TypeBounds(_, hi2) => isSubType(tp1, hi2)
+          case NoType => true
+        }
+        compareWildcard
+      case tp2: AnnotatedType =>
+        isSubType(tp1, tp2.tpe) // todo: refine?
+      case ErrorType =>
+        true
+      case AndType(left2, right2) =>
+        isSubType(tp1, left2) && isSubType(tp1, right2)
+      case _ =>
+        compare1(tp1, tp2)
+    }
+  }
+
+  def compare1(tp1: Type, tp2: Type): Boolean = {
+    tp1 match {
+      case tref1: TypeRef =>
+        val sym1 = tref1.symbol
+        tref1.info match {
+          case TypeBounds(lo1, hi1) =>
+            if (lo1 eq hi1) return compare(hi1, tp2)
+            else if (sym1 is GADTFlexType)
+              return isSubType(hi1, tp2) ||
+                trySetType(tref1, TypeBounds(lo1, hi1 & tp2))
+          case _ =>
+            if ((sym1 eq NothingClass) && tp2.isInstanceOf[ValueType]) return true
+            if ((sym1 eq NullClass) && tp2.dealias.typeSymbol.isNullableClass) return true
+        }
+      case param1: PolyParam if isConstrained(param1) =>
+        def comparePoly = (
+             param1 == tp2
+          || isSubTypeWhenFrozen(bounds(param1).hi, tp2)
+          || { if ((tp2 isRef defn.NothingClass) && ctx.typerState.isGlobalCommittable)
+                 ctx.log(s"!!! instantiating to Nothing: $tp1")
+               addConstraint(param1, tp2, fromBelow = false)
+             }
+          )
+        return comparePoly
+      case tp1 @ ThisType(cls) if cls is ModuleClass =>
+        tp2 match {
+          case tp2: TermRef =>
+            return tp2.symbol.moduleClass == cls && cls.owner.thisType <:< tp2.prefix
+          case _ =>
+        }
+      case tp1: TypeVar =>
+        return compare(tp1.underlying, tp2)
+      case tp1: WildcardType =>
+        def compareWildcard = tp1.optBounds match {
+          case TypeBounds(lo1, _) => isSubType(lo1, tp2) // todo: use short-circuiting to current method more often?
+          case NoType => true
+        }
+        return compareWildcard
+      case tp1: AnnotatedType =>
+        return isSubType(tp1.tpe, tp2)
+      case ErrorType =>
+        return true
+      case OrType(left1, right1) =>
+        return isSubType(left1, tp2) && isSubType(right1, tp2)
+      case _ =>
+    }
+    rightIsSuper(tp1, tp2)
+  }
+
+  def rightIsSuper(tp1: Type, tp2: Type): Boolean = tp2 match {
+    case tp2: NamedType =>
+      def compareNamed: Boolean = {
+        val sym2 = tp2.symbol
+        val pre2 = tp2.prefix
+        tp1 match {
+          case tp1: NamedType =>
+            val sym1 = tp1.symbol
+            val pre1 = tp1.prefix
+            if (sym1 == sym2) {
+              if (  ctx.erasedTypes
+                 || sym1.isStaticOwner
+                 || isSubType(pre1, pre2)
+                 || pre1.isInstanceOf[ThisType] && pre2.isInstanceOf[ThisType]) return true
+            } else if (tp1.name == tp2.name && isSubType(pre1, pre2)) return true
+          case _ =>
+        }
+        if (sym2.isClass) {
+          val base = tp1.baseType(sym2)
+          if (base.exists && (base ne tp1)) isSubType(base, tp2)
+          else
+            (sym2 == defn.SingletonClass) && tp1.isStable ||
+            (defn.hkTraits contains sym2) && isSubTypeHK(tp1.widen, tp2) ||
+            leftIsSub2(tp1, tp2)
+        }
+        else tp2.info match {
+          case TypeBounds(lo2, hi2) =>
+            if (lo2 eq hi2)
+              isSubType(tp1.dealias, hi2.dealias)
+            else if (sym2 is GADTFlexType)
+              isSubType(tp1, lo2) || trySetType(tp2, TypeBounds(lo2 | tp1, hi2))
+            else {
+              (frozenConstraint || !isCappable(tp1)) && isSubType(tp1, lo2) ||
+              leftIsSub(tp1, tp2)
+            }
+          case _ =>
+            leftIsSub(tp1, tp2)
+        }
+      }
+      compareNamed
+
+    case tp2 @ RefinedType(parent2, name2) =>
+      def compareRefined: Boolean = tp1.widen match {
+        case tp1 @ RefinedType(parent1, name1) if nameMatches(name1, name2, tp1, tp2) =>
+          // optimized case; all info on tp1.name2 is in refinement tp1.refinedInfo.
+          isSubType(tp1, parent2) && isSubType(tp1.refinedInfo, tp2.refinedInfo)
+        case _ =>
+          def hasMatchingMember(name: Name): Boolean = traceIndented(s"hasMatchingMember($name) ${tp1.member(name)}") (
+               tp1.member(name).hasAltWith(alt => isSubType(alt.info, tp2.refinedInfo))
+            ||
+               { // special case for situations like:
+                 //    foo <: C { type T = foo.T }
+                 tp2.refinedInfo match {
+                   case TypeBounds(lo, hi) if lo eq hi =>
+                     val ref = tp1 select name
+                     isSubType(ref, lo) && isSubType(hi, ref)
+                   case _ => false
+                 }
+               }
+            ||
+               name.isHkParamName && {
+                 val idx = name.hkParamIndex
+                 val tparams = tp1.typeParams
+                 idx < tparams.length && hasMatchingMember(tparams(idx).name)
+               }
+          )
+          isSubType(tp1, parent2) && (
+               name2 == nme.WILDCARD
+            || hasMatchingMember(name2)
+            || leftIsSub2(tp1, tp2))
+      }
+      compareRefined
+
+    case param2: PolyParam =>
+      def comparePoly =
+        param2 == tp1 || {
+          if (isConstrained(param2))
+            isSubTypeWhenFrozen(tp1, bounds(param2).lo) ||
+            addConstraint(param2, tp1.widen, fromBelow = true)
+          else
+            (ctx.mode is Mode.TypevarsMissContext) ||
+            isNonBottomSubType(tp1, bounds(param2).lo) ||
+            leftIsSub(tp1, tp2)
+      }
+      comparePoly
+
+    case ThisType(cls) if (cls is ModuleClass) =>
+      def compareThis: Boolean = {
+        tp1 match {
+          case tp1: TermRef =>
+            if (tp1.symbol.moduleClass == cls)
+              return tp1.prefix <:< cls.owner.thisType
+          case _ =>
+        }
+        leftIsSub(tp1, tp2)
+      }
+      compareThis
+
+    case tp2: BoundType =>
+      tp1 == tp2 || leftIsSub(tp1, tp2)
+    case OrType(tp21, tp22) =>
+      isSubType(tp1, tp21) || isSubType(tp1, tp22)
+
+    case tp2 @ MethodType(_, formals2) =>
+      def compareMethod = tp1 match {
+        case tp1 @ MethodType(_, formals1) =>
+          tp1.signature == tp2.signature &&
+            (if (Config.newMatch) subsumeParams(formals1, formals2, tp1.isJava, tp2.isJava)
+             else matchingParams(formals1, formals2, tp1.isJava, tp2.isJava)) &&
+            tp1.isImplicit == tp2.isImplicit && // needed?
+            isSubType(tp1.resultType, tp2.resultType.subst(tp2, tp1))
+        case _ =>
+          false
+      }
+      compareMethod
+
+    case tp2: PolyType =>
+      def comparePoly = tp1 match {
+        case tp1: PolyType =>
+          (tp1.signature sameParams tp2.signature) &&
+          matchingTypeParams(tp1, tp2) &&
+          isSubType(tp1.resultType, tp2.resultType.subst(tp2, tp1))
+        case _ =>
+          false
+      }
+      comparePoly
+
+    case tp2 @ ExprType(restpe2) =>
+      def compareExpr = tp1 match {
+        // We allow ()T to be a subtype of => T.
+        // We need some subtype relationship between them so that e.g.
+        // def toString   and   def toString()   don't clash when seen
+        // as members of the same type. And it seems most logical to take
+        // ()T <:< => T, since everything one can do with a => T one can
+        // also do with a ()T by automatic () insertion.
+        case tp1 @ MethodType(Nil, _) => isSubType(tp1.resultType, restpe2)
+        case _ => isSubType(tp1.widenExpr, restpe2)
+      }
+      compareExpr
+
+    case tp2 @ TypeBounds(lo2, hi2) =>
+      def compareBounds = tp1 match {
+        case tp1 @ TypeBounds(lo1, hi1) =>
+          val v = tp1.variance + tp2.variance
+          ((v > 0) || (lo2 isRef NothingClass) || isSubType(lo2, lo1)) &&
+          ((v < 0) || (hi2 isRef AnyClass) || isSubType(hi1, hi2))
+        case tp1: ClassInfo =>
+          val tt = tp1.typeRef
+          isSubType(lo2, tt) && isSubType(tt, hi2)
+        case _ =>
+          false
+      }
+      compareBounds
+
+    case ClassInfo(pre2, cls2, _, _, _) =>
+      def compareClassInfo = tp1 match {
+        case ClassInfo(pre1, cls1, _, _, _) =>
+          (cls1 eq cls2) && isSubType(pre2, pre1)
+        case _ =>
+          false
+      }
+      compareClassInfo
+
+    case _ =>
+      leftIsSub(tp1, tp2)
+  }
+
+  def leftIsSub(tp1: Type, tp2: Type): Boolean = tp1 match {
+    case tp1: TypeRef =>
+      tp1.info match {
+        case TypeBounds(lo1, hi1) => isSubType(hi1, tp2)
+        case _ => false
+      }
+    case tp1: SingletonType =>
+      isSubType(tp1.underlying.widenExpr, tp2)
+    case tp1: RefinedType =>
+      isSubType(tp1.parent, tp2)
+    case _ =>
+      leftIsSub2(tp1, tp2)
+  }
+
+  def leftIsSub2(tp1: Type, tp2: Type): Boolean = tp1 match {
+    case param1: PolyParam =>
+      assert(!isConstrained(param1))
+      (ctx.mode is Mode.TypevarsMissContext) || isSubType(bounds(param1).hi, tp2)
+    case AndType(tp11, tp12) =>
+      isSubType(tp11, tp2) || isSubType(tp12, tp2)
+    case _ =>
+      false
+  }
+
+  def firstTry(tp1: Type, tp2: Type): Boolean = {
     tp2 match {
       case tp2: NamedType =>
         tp1 match {
@@ -250,7 +525,7 @@ class TypeComparer(initctx: Context) extends DotClass {
         if (cls is ModuleClass)
           tp1 match {
             case tp1: TermRef =>
-              return tp1.symbol.moduleClass == cls && tp1.prefix <:< cls.owner.thisType // ???
+              if (tp1.symbol.moduleClass == cls) return tp1.prefix <:< cls.owner.thisType
             case _ =>
           }
         secondTry(tp1, tp2)
@@ -263,7 +538,7 @@ class TypeComparer(initctx: Context) extends DotClass {
       case tp2: BoundType =>
         tp2 == tp1 || secondTry(tp1, tp2)
       case tp2: TypeVar =>
-        (tp1 eq tp2) || isSubType(tp1, tp2.underlying)
+        isSubType(tp1, tp2.underlying)
       case tp2: ProtoType =>
         isMatchedByProto(tp2, tp1)
       case tp2: WildcardType =>
@@ -273,6 +548,8 @@ class TypeComparer(initctx: Context) extends DotClass {
         }
       case tp2: AnnotatedType =>
         isSubType(tp1, tp2.tpe) // todo: refine?
+      case AndType(tp21, tp22) =>
+        isSubType(tp1, tp21) && isSubType(tp1, tp22)
       case ErrorType =>
         true
       case _ =>
@@ -285,7 +562,7 @@ class TypeComparer(initctx: Context) extends DotClass {
       if (cls is ModuleClass)
         tp2 match {
           case tp2: TermRef =>
-            return tp2.symbol.moduleClass == cls && cls.owner.thisType <:< tp2.prefix
+            if (tp2.symbol.moduleClass == cls) return cls.owner.thisType <:< tp2.prefix
           case _ =>
         }
       thirdTry(tp1, tp2)
@@ -310,6 +587,8 @@ class TypeComparer(initctx: Context) extends DotClass {
       }
     case tp1: AnnotatedType =>
       isSubType(tp1.tpe, tp2)
+    case OrType(tp11, tp12) =>
+      isSubType(tp11, tp2) && isSubType(tp12, tp2)
     case ErrorType =>
       true
     case _ =>
@@ -362,8 +641,6 @@ class TypeComparer(initctx: Context) extends DotClass {
             || hasMatchingMember(name2)
             || fourthTry(tp1, tp2))
       }
-    case AndType(tp21, tp22) =>
-      isSubType(tp1, tp21) && isSubType(tp1, tp22)
     case OrType(tp21, tp22) =>
       isSubType(tp1, tp21) || isSubType(tp1, tp22) || fourthTry(tp1, tp2)
     case tp2 @ MethodType(_, formals2) =>
@@ -427,8 +704,8 @@ class TypeComparer(initctx: Context) extends DotClass {
           isSubType(hi1, tp2) ||
           (tp1.symbol is GADTFlexType) && trySetType(tp1, TypeBounds(lo1, hi1 & tp2))
         case _ =>
-          (tp1.symbol eq NothingClass) ||
-          (tp1.symbol eq NullClass) && tp2.dealias.typeSymbol.isNonValueClass
+          (tp1.symbol eq NothingClass) && tp2.isInstanceOf[ValueType] ||
+          (tp1.symbol eq NullClass) && tp2.dealias.typeSymbol.isNullableClass
       }
     case tp1: SingletonType =>
       isSubType(tp1.underlying.widenExpr, tp2)
@@ -436,8 +713,6 @@ class TypeComparer(initctx: Context) extends DotClass {
       isSubType(tp1.parent, tp2)
     case AndType(tp11, tp12) =>
       isSubType(tp11, tp2) || isSubType(tp12, tp2)
-    case OrType(tp11, tp12) =>
-      isSubType(tp11, tp2) && isSubType(tp12, tp2)
     case _ =>
       false
   }