Optimize subtype test between refined types with multiple refinements

We now pair refinedInfos with the same name as deeply as wek can (before only went to depth 1).

2 files changed, 84 insertions, 8 deletions

diff --git a/src/dotty/tools/dotc/Bench.scala b/src/dotty/tools/dotc/Bench.scala
new file mode 100644
index 000000000..1fca7a2bb
--- /dev/null
+++ b/src/dotty/tools/dotc/Bench.scala
@@ -0,0 +1,47 @@
+/* NSC -- new Scala compiler
+ * Copyright 2005-2013 LAMP/EPFL
+ * @author  Martin Odersky
+ */
+package dotty.tools
+package dotc
+
+import core.Contexts.Context
+import reporting.Reporter
+
+/* To do:
+ *   - simplify hk types
+ *   - have a second look at normalization (leave at method types if pt is method type?)
+ *   - Don't open package objects from class files if they are present in source
+ *   - Revise the way classes are inherited - when not followed by [...] or (...),
+ *     assume the unparameterized type and forward type parameters as we do now for the synthetic head class.
+ */
+object Bench extends Driver {
+  def resident(compiler: Compiler): Reporter = unsupported("resident") /*loop { line =>
+    val command = new CompilerCommand(line split "\\s+" toList, new Settings(scalacError))
+    compiler.reporter.reset()
+    new compiler.Run() compile command.files
+  }*/
+
+  lazy val compiler = new Compiler
+
+  override def newCompiler(): Compiler = compiler
+
+  override def doCompile(compiler: Compiler, fileNames: List[String])(implicit ctx: Context): Reporter = {
+    if (new config.Settings.Setting.SettingDecorator[Boolean](ctx.base.settings.resident).value(ctx))
+      resident(compiler)
+    else
+      super.doCompile(compiler, fileNames)
+  }
+
+  val N = 10
+
+  override def main(args: Array[String]): Unit = {
+    for (i <- 0 until N) {
+      val start = System.nanoTime()
+      process(args)
+      println(s"time elapsed: ${(System.nanoTime - start) / 1000000}ms")
+    }
+  }
+}
+
+
diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala
index 9604e1531..15a3d746d 100644
--- a/src/dotty/tools/dotc/core/TypeComparer.scala
+++ b/src/dotty/tools/dotc/core/TypeComparer.scala
@@ -24,8 +24,6 @@ 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
 
@@ -208,8 +206,7 @@ class TypeComparer(initctx: Context) extends DotClass {
         }
 */
         val result =
-          if (recCount < LogPendingSubTypesThreshold)
-            if (oldCompare) firstTry(tp1, tp2) else compare(tp1, tp2)
+          if (recCount < LogPendingSubTypesThreshold) firstTry(tp1, tp2)
           else monitoredIsSubType(tp1, tp2)
         successCount += 1
         totalCount += 1
@@ -260,13 +257,17 @@ class TypeComparer(initctx: Context) extends DotClass {
     !pendingSubTypes(p) && {
       try {
         pendingSubTypes += p
-        if (oldCompare) firstTry(tp1, tp2) else compare(tp1, tp2)
+        firstTry(tp1, tp2)
       } finally {
         pendingSubTypes -= p
       }
     }
   }
 
+/* Alternative implementation of isSubType, currently put on hold. Did not work
+ * out. Keep around for a while longer in case we want to mine it for ideas.
+ */
+
   def compare(tp1: Type, tp2: Type): Boolean = ctx.debugTraceIndented(s"$tp1 <:< $tp2") {
     tp2 match {
       case tp2: ProtoType =>
@@ -381,10 +382,24 @@ class TypeComparer(initctx: Context) extends DotClass {
       compareNamed
 
     case tp2 @ RefinedType(parent2, name2) =>
+      def matchRefinements(tp1: Type, tp2: Type, seen: Set[Name]): Type = tp1 match {
+        case tp1 @ RefinedType(parent1, name1) if !(seen contains name1) =>
+          tp2 match {
+            case tp2 @ RefinedType(parent2, name2) if nameMatches(name1, name2, tp1, tp2) =>
+              if (isSubType(tp1.refinedInfo, tp2.refinedInfo))
+                matchRefinements(parent1, parent2, seen + name1)
+              else NoType
+            case _ => tp2
+          }
+        case _ => tp2
+      }
       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)
+          isSubType(tp1.refinedInfo, tp2.refinedInfo) && {
+            val ancestor2 = matchRefinements(parent1, parent2, Set.empty + name1)
+            ancestor2.exists && isSubType(tp1, ancestor2)
+          }
         case _ =>
           def hasMatchingMember(name: Name): Boolean = traceIndented(s"hasMatchingMember($name) ${tp1.member(name)}") (
                tp1.member(name).hasAltWith(alt => isSubType(alt.info, tp2.refinedInfo))
@@ -681,10 +696,24 @@ class TypeComparer(initctx: Context) extends DotClass {
       }
       compareNamed
     case tp2 @ RefinedType(parent2, name2) =>
-      def compareRefined = tp1.widen match {
+      def matchRefinements(tp1: Type, tp2: Type, seen: Set[Name]): Type = tp1 match {
+        case tp1 @ RefinedType(parent1, name1) if !(seen contains name1) =>
+          tp2 match {
+            case tp2 @ RefinedType(parent2, name2) if nameMatches(name1, name2, tp1, tp2) =>
+              if (isSubType(tp1.refinedInfo, tp2.refinedInfo))
+                matchRefinements(parent1, parent2, seen + name1)
+              else NoType
+            case _ => tp2
+          }
+        case _ => tp2
+      }
+      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)
+          isSubType(tp1.refinedInfo, tp2.refinedInfo) && {
+            val ancestor2 = matchRefinements(parent1, parent2, Set.empty + name1)
+            ancestor2.exists && isSubType(tp1, ancestor2)
+          }
         case _ =>
           def hasMatchingMember(name: Name): Boolean = /*>|>*/ traceIndented(s"hasMatchingMember($name) ${tp1.member(name)}") /*<|<*/ (
                tp1.member(name).hasAltWith(alt => isSubType(alt.info, tp2.refinedInfo))