First implementation of SubTyper.

3 files changed, 178 insertions, 57 deletions

diff --git a/src/dotty/tools/dotc/core/Contexts.scala b/src/dotty/tools/dotc/core/Contexts.scala
index 9de9aa0d5..bdec812bf 100644
--- a/src/dotty/tools/dotc/core/Contexts.scala
+++ b/src/dotty/tools/dotc/core/Contexts.scala
@@ -6,6 +6,7 @@ import Periods._
 import Names._
 import Phases._
 import Types._
+import SubTypers._
 
 object Contexts {
 
@@ -15,6 +16,7 @@ object Contexts {
     val underlying: Context
     val root: RootContext
     val period: Period
+    def subTyper: SubTyper
     def names: NameTable
     def phase: Phase = ???
     def stableInterval: Interval = ???
@@ -24,6 +26,7 @@ object Contexts {
   abstract class SubContext(val underlying: Context) extends Context {
     val root: RootContext = underlying.root
     val period: Period = underlying.period
+    val subTyper = underlying.subTyper
     def names: NameTable = root.names
   }
 
@@ -43,6 +46,7 @@ object Contexts {
     var lastPhaseId: Int = NoPhaseId
     lazy val definitions = new Definitions()(this)
 
+    val subTyper = new SubTyper(Map())(this)
   }
 
   private final val initialUniquesCapacity = 4096
diff --git a/src/dotty/tools/dotc/core/SubTyper.scala b/src/dotty/tools/dotc/core/SubTyper.scala
index ad9bb7fb4..a97f23224 100644
--- a/src/dotty/tools/dotc/core/SubTyper.scala
+++ b/src/dotty/tools/dotc/core/SubTyper.scala
@@ -1,92 +1,208 @@
 package dotty.tools.dotc.core
 
 import Types._, Contexts._, Symbols._
+import collection.mutable
 
 object SubTypers {
 
   type Constraints = Map[PolyParam, TypeBounds]
 
-  class SubTyper extends DotClass {
+  object SubTyper {
+    private final val LogPendingSubTypesThreshold = 50
+  }
 
-    var constraints: Constraints = _
-    implicit var ctx: Context = _
+  class SubTyper(var constraints: Constraints)(implicit ctx: Context) extends DotClass {
+    import SubTyper._
 
-    def init(constraints: Constraints)(implicit ctx: Context): SubTyper = {
-      this.constraints = constraints
-      this.ctx = ctx
-      this
-    }
+    private var pendingSubTypes: mutable.Set[(Type, Type)] = null
+    private var recCount = 0
 
-    def addConstraint(param: PolyParam, bounds: TypeBounds): Boolean = {
+   def addConstraint(param: PolyParam, bounds: TypeBounds): Boolean = {
       val newbounds = constraints(param) & bounds
       constraints = constraints.updated(param, newbounds)
       newbounds.lo <:< newbounds.hi
     }
 
-    def isSubType(tp1: Type, tp2: Type): Boolean = {
-      if (tp1 == NoType || tp2 == NoType) return false
-      if (tp1 eq tp2) return true
-      val cs = constraints
-      try {
-        val result = firstTry(tp1, tp2)
-        if (!result) constraints = cs
-        result
-      } catch {
-        case ex: Throwable =>
-          constraints = cs
-          throw ex
+    def isSubType(tp1: Type, tp2: Type): Boolean =
+      if (tp1 == NoType || tp2 == NoType) false
+      else if (tp1 eq tp2) true
+      else {
+        val cs = constraints
+        try {
+          recCount += 1
+          val result =
+            if (recCount < LogPendingSubTypesThreshold) firstTry(tp1, tp2)
+            else monitoredIsSubType(tp1, tp2)
+          recCount -= 1
+          if (!result) constraints = cs
+          result
+        } catch {
+          case ex: Throwable =>
+            recCount -= 1
+            constraints = cs
+            throw ex
+        }
+      }
+
+    def monitoredIsSubType(tp1: Type, tp2: Type) = {
+      if (pendingSubTypes == null)
+        pendingSubTypes = new mutable.HashSet[(Type, Type)]
+      val p = (tp1, tp2)
+      !pendingSubTypes(p) && {
+        try {
+          pendingSubTypes += p
+          firstTry(tp1, tp2)
+        } finally {
+          pendingSubTypes -= p
+        }
       }
     }
 
     def firstTry(tp1: Type, tp2: Type): Boolean = tp2 match {
-        case tp2: TypeRef =>
-          tp1 match {
-            case tp1: TypeRef =>
-              val sym1 = tp1.symbol
-              val sym2 = tp2.symbol
-              val pre1 = tp1.prefix
-              val pre2 = tp2.prefix
-              (sym1 == sym2 && (
-                ctx.erasedTypes ||
-                sym1.owner.hasFlag(Flags.Package) ||
-                isSubType(pre1, pre2))
-               ||
-               tp1.name == tp2.name &&
-               isSubType(pre1, pre2) &&
-               (sym2.isAbstractType || isSubType(pre2, pre1))
-               ||
-               (sym2.isClass) && {
-                 val base = tp1.baseType(sym2)
-                 (base ne tp1) && isSubType(base, tp2)
-               }
-               ||
-               thirdTryRef(tp1, tp2))
-             case _ =>
-               secondTry(tp1, tp2)
-          }
-        case tp2: PolyParam if (constraints contains tp2) =>
-          addConstraint(tp2, TypeBounds(tp1, AnyType))
-        case _ =>
-          secondTry(tp1, tp2)
-      }
+      case tp2: TypeRef =>
+        tp1 match {
+          case tp1: TypeRef =>
+            val sym1 = tp1.symbol
+            val sym2 = tp2.symbol
+            val pre1 = tp1.prefix
+            val pre2 = tp2.prefix
+            (sym1 == sym2 && (
+              ctx.erasedTypes ||
+              sym1.owner.hasFlag(Flags.Package) ||
+              isSubType(pre1, pre2))
+              ||
+              tp1.name == tp2.name &&
+              isSubType(pre1, pre2) &&
+              (sym2.isAbstractType || isSubType(pre2, pre1)) // ???
+              ||
+              (sym2.isClass) && {
+                val base = tp1.baseType(sym2)
+                (base ne tp1) && isSubType(base, tp2)
+              }
+              ||
+              thirdTryRef(tp1, tp2))
+          case _ =>
+            secondTry(tp1, tp2)
+        }
+      case WildcardType | ErrorType =>
+        true
+      case tp2: PolyParam if (constraints contains tp2) =>
+        addConstraint(tp2, TypeBounds(tp1, defn.AnyType))
+      case _ =>
+        secondTry(tp1, tp2)
+    }
 
 
     def secondTry(tp1: Type, tp2: Type): Boolean = tp1 match {
       case tp1: PolyParam if (constraints contains tp1) =>
-        addConstraint(tp1, TypeBounds(NothingType, tp2))
+        addConstraint(tp1, TypeBounds(defn.NothingType, tp2))
+      case WildcardType | ErrorType =>
+        true
       case _ =>
         thirdTry(tp1, tp2)
     }
 
     def thirdTryRef(tp1: Type, tp2: TypeRef): Boolean = (
-      (tp2 == SingletonType && tp1.isStable)
+      (tp2 == defn.SingletonType && tp1.isStable)
       ||
       (!tp2.symbol.isClass && isSubType(tp1, tp2.info.bounds.lo))
       ||
       fourthTry(tp1, tp2)
     )
 
-    def thirdTry(tp1: Type, tp2: Type): Boolean = ???
-    def fourthTry(tp1: Type, tp2: Type): Boolean = ???
+    def thirdTry(tp1: Type, tp2: Type): Boolean = tp2 match {
+      case tp2: TypeRef =>
+        thirdTryRef(tp1, tp2)
+      case AppliedType(tycon, targs) =>
+        val clazz2 = tycon.typeSymbol
+        val base = tp1.baseType(clazz2)
+        base.exists && isSubArgs(base.typeArgs, tp2.typeArgs, clazz2.typeParams) ||
+        fourthTry(tp1, tp2)
+      case tp2: RefinedType =>
+        isSubType(tp1, tp2.parent) &&
+        ((tp2.names, tp2.infos).zipped forall ((name, info) =>
+          isSubType(tp1.member(name).info, info)))
+      case AndType(tp21, tp22) =>
+        isSubType(tp1, tp21) && isSubType(tp1, tp22)
+      case OrType(tp21, tp22) =>
+        isSubType(tp1, tp21) || isSubType(tp1, tp22)
+      case tp2 @ MethodType(_, formals1) =>
+        tp1 match {
+          case tp1 @ MethodType(_, formals2) =>
+            sameLength(formals1, formals2) &&
+            matchingParams(formals1, formals2, tp1.isJava, tp2.isJava) &&
+            tp1.isImplicit == tp2.isImplicit &&
+            isSubType(tp1.resultType, tp2.resultType.subst(tp2, tp1))
+          case _ =>
+            false
+        }
+      case tp2 @ ExprType(restpe1) =>
+        tp1 match {
+          case tp1 @ ExprType(restpe2) =>
+            isSubType(restpe1, restpe2)
+          case _ =>
+            false
+        }
+      case TypeBounds(lo2, hi2) =>
+        tp1 match {
+          case TypeBounds(lo1, hi1) =>
+            isSubType(lo2, lo1) && isSubType(hi1, hi2)
+          case tp1: ClassInfo =>
+            val tt = tp1.typeTemplate
+            lo2 <:< tt && tt <:< hi2
+          case _ =>
+            false
+        }
+      case _ =>
+        fourthTry(tp1, tp2)
+    }
+
+    def fourthTry(tp1: Type, tp2: Type): Boolean =  tp1 match {
+      case tp1: TypeRef =>
+        ((tp1 eq defn.NothingType)
+         ||
+         (tp1 eq defn.NullType) && tp2.typeSymbol.containsNull
+         ||
+         (!tp1.symbol.isClass && isSubType(tp1.info.bounds.hi, tp2)))
+      case RefinedType(parent, _) =>
+        isSubType(parent, tp2)
+      case AndType(tp11, tp12) =>
+        isSubType(tp11, tp2) || isSubType(tp12, tp2)
+      case OrType(tp11, tp12) =>
+        isSubType(tp11, tp2) && isSubType(tp12, tp2)
+      case tp1: SingletonType =>
+        isSubType(tp1.underlying, tp2)
+      case _ =>
+        false
+    }
+
+    def isSubArgs(tps1: List[Type], tps2: List[Type], tparams: List[TypeSymbol]): Boolean = tparams match {
+      case tparam :: tparams1 =>
+        val variance = tparam.variance
+        val t1 = tps1.head
+        val t2 = tps2.head
+        (variance > 0 || isSubType(t2, t1)) &&
+        (variance < 0 || isSubType(t1, t2)) &&
+        isSubArgs(tps1.tail, tps2.tail, tparams1)
+      case _ =>
+        assert(tps1.isEmpty && tps2.isEmpty)
+        true
+    }
+
+    /** Are `syms1` and `syms2` parameter lists with pairwise equivalent types? */
+    private def matchingParams(formals1: List[Type], formals2: List[Type], isJava1: Boolean, isJava2: Boolean): Boolean = formals1 match {
+      case Nil =>
+        formals2.isEmpty
+      case formal1 :: rest1 =>
+        formals2 match {
+          case Nil =>
+            false
+          case formal2 :: rest2 =>
+            (formal1 =:= formal2 ||
+              isJava1 && formal2 == defn.ObjectType && formal1 == defn.AnyType ||
+              isJava2 && formal1 == defn.ObjectType && formal2 == defn.AnyType) &&
+              matchingParams(rest1, rest2, isJava1, isJava2)
+        }
+    }
   }
 }
\ No newline at end of file
diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala
index 74b8ef959..a81dfb4c9 100644
--- a/src/dotty/tools/dotc/core/Types.scala
+++ b/src/dotty/tools/dotc/core/Types.scala
@@ -40,8 +40,6 @@ object Types {
 
   abstract class Type extends DotClass {
 
-    def <:< (that: Type): Boolean = ???
-
     def =:= (that: Type): Boolean = ???
 
     def hash = NotCached
@@ -125,6 +123,9 @@ object Types {
     def memberType(sym: Symbol): Type = ???
     def memberInfo(sym: Symbol): Type = ???
 
+    def <:< (that: Type)(implicit ctx: Context): Boolean =
+      ctx.subTyper.isSubType(this, that)
+
     def widen: Type = ???
 
     def deconst: Type = ???