isSubtype: try to dealias TypeRefs before recursively checking the prefixes

As demonstrated by tests/pos/hk-deep-subtype.scala, we can avoid some
deep subtype recursions that result in stack overflows by doing this.

Fix #943.

3 files changed, 23 insertions, 10 deletions

diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala
index 6e2346710..0d46a4b90 100644
--- a/src/dotty/tools/dotc/core/TypeComparer.scala
+++ b/src/dotty/tools/dotc/core/TypeComparer.scala
@@ -144,8 +144,7 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling {
         case info2: TypeAlias => isSubType(tp1, info2.alias)
         case _ => info1 match {
           case info1: TypeAlias => isSubType(info1.alias, tp2)
-          case NoType => secondTry(tp1, tp2)
-          case _ => thirdTryNamed(tp1, tp2)
+          case _ => false
         }
       }
       def compareNamed = {
@@ -153,6 +152,7 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling {
         tp1 match {
           case tp1: NamedType =>
             val sym1 = tp1.symbol
+            compareAlias(tp1.info) ||
             (if ((sym1 ne NoSymbol) && (sym1 eq tp2.symbol))
                ctx.erasedTypes || sym1.isStaticOwner || isSubType(tp1.prefix, tp2.prefix)
             else
@@ -164,10 +164,11 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling {
             ) ||
             compareHK(tp1, tp2, inOrder = true) ||
             compareHK(tp2, tp1, inOrder = false) ||
-            compareAlias(tp1.info)
+            thirdTryNamed(tp1, tp2)
           case _ =>
             compareHK(tp2, tp1, inOrder = false) ||
-            compareAlias(NoType)
+            compareAlias(NoType) ||
+            secondTry(tp1, tp2)
         }
       }
       compareNamed
diff --git a/test/dotc/scala-collections.whitelist b/test/dotc/scala-collections.whitelist
index a758f9a8c..25cd73629 100644
--- a/test/dotc/scala-collections.whitelist
+++ b/test/dotc/scala-collections.whitelist
@@ -263,16 +263,13 @@
 ./scala-scala/src/library/scala/collection/generic/GenericSeqCompanion.scala
 ./scala-scala/src/library/scala/collection/generic/GenericSetTemplate.scala
 
-# deep subtype
-#./scala-scala/src/library/scala/collection/generic/GenericTraversableTemplate.scala
+./scala-scala/src/library/scala/collection/generic/GenericTraversableTemplate.scala
 
 ./scala-scala/src/library/scala/collection/generic/HasNewBuilder.scala
 ./scala-scala/src/library/scala/collection/generic/HasNewCombiner.scala
 
-# https://github.com/lampepfl/dotty/issues/943
-# [error] Test dotc.tests.compileStdLib failed: java.lang.Error: deep subtype, took 6.462 sec
-#./scala-scala/src/library/scala/collection/generic/ImmutableMapFactory.scala
-#./scala-scala/src/library/scala/collection/generic/ImmutableSetFactory.scala
+./scala-scala/src/library/scala/collection/generic/ImmutableMapFactory.scala
+./scala-scala/src/library/scala/collection/generic/ImmutableSetFactory.scala
 
 ./scala-scala/src/library/scala/collection/generic/ImmutableSortedMapFactory.scala
 ./scala-scala/src/library/scala/collection/generic/ImmutableSortedSetFactory.scala
diff --git a/tests/pos/hk-deep-subtype.scala b/tests/pos/hk-deep-subtype.scala
new file mode 100644
index 000000000..202329a79
--- /dev/null
+++ b/tests/pos/hk-deep-subtype.scala
@@ -0,0 +1,15 @@
+// Minimized from scala.collection.generic.GenTraversableFactory plus dependencies
+import scala.annotation.unchecked.uncheckedVariance
+
+trait GT[A] extends GTT[A, GT]
+
+trait HNB[B]
+trait GTT[+C, DD[X] <: GT[X]] extends HNB[DD[C] @uncheckedVariance] // Can be any annotation and still crash
+
+class GTF[EE[X] <: GT[X] with GTT[X, EE]]
+{
+  def foo[F]: EE[F] = ???
+  def bar[G](f: G): EE[G] = ???
+
+  def tabulate: EE[EE[Int]] = bar(foo)
+}