From 81b7ed9abb9627d541b795990980f4431b459380 Mon Sep 17 00:00:00 2001 From: Guillaume Martres Date: Wed, 25 Nov 2015 00:07:13 +0100 Subject: 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. --- src/dotty/tools/dotc/core/TypeComparer.scala | 9 +++++---- test/dotc/scala-collections.whitelist | 9 +++------ tests/pos/hk-deep-subtype.scala | 15 +++++++++++++++ 3 files changed, 23 insertions(+), 10 deletions(-) create mode 100644 tests/pos/hk-deep-subtype.scala 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) +} -- cgit v1.2.3 From 3e714af5dbfbd8e61500bd0ede04cc39952f10ee Mon Sep 17 00:00:00 2001 From: Guillaume Martres Date: Wed, 25 Nov 2015 16:08:38 +0100 Subject: Update whitelist with more files that compile Thanks to the previous commit, more files now compile without deep subtyping errors. --- test/dotc/scala-collections.whitelist | 27 +++++++++++++++------------ 1 file changed, 15 insertions(+), 12 deletions(-) diff --git a/test/dotc/scala-collections.whitelist b/test/dotc/scala-collections.whitelist index 25cd73629..a0c9ce588 100644 --- a/test/dotc/scala-collections.whitelist +++ b/test/dotc/scala-collections.whitelist @@ -279,20 +279,23 @@ ./scala-scala/src/library/scala/collection/generic/IsTraversableOnce.scala ./scala-scala/src/library/scala/collection/generic/IterableForwarder.scala -# [error] Test dotc.tests.compileStdLib failed: java.lang.Error: deep subtype -# fails if any of those classes are added: -#./scala-scala/src/library/scala/collection/generic/MapFactory.scala -#./scala-scala/src/library/scala/collection/generic/MutableMapFactory.scala -#./scala-scala/src/library/scala/collection/generic/MutableSetFactory.scala -#./scala-scala/src/library/scala/collection/generic/MutableSortedSetFactory.scala +./scala-scala/src/library/scala/collection/generic/MapFactory.scala +./scala-scala/src/library/scala/collection/generic/MutableMapFactory.scala +./scala-scala/src/library/scala/collection/generic/MutableSetFactory.scala +./scala-scala/src/library/scala/collection/generic/ParMapFactory.scala +./scala-scala/src/library/scala/collection/generic/SeqFactory.scala +./scala-scala/src/library/scala/collection/generic/SortedMapFactory.scala +./scala-scala/src/library/scala/collection/generic/SortedSetFactory.scala +./scala-scala/src/library/scala/collection/generic/SetFactory.scala + +# deep subtype #./scala-scala/src/library/scala/collection/generic/ParFactory.scala -#./scala-scala/src/library/scala/collection/generic/ParMapFactory.scala -#./scala-scala/src/library/scala/collection/generic/ParSetFactory.scala -#./scala-scala/src/library/scala/collection/generic/SeqFactory.scala -#./scala-scala/src/library/scala/collection/generic/SortedMapFactory.scala -#./scala-scala/src/library/scala/collection/generic/SortedSetFactory.scala -#./scala-scala/src/library/scala/collection/generic/SetFactory.scala +# https://github.com/lampepfl/dotty/issues/974 +#./scala-scala/src/library/scala/collection/generic/MutableSortedSetFactory.scala + +# cyclic reference, maybe related to #974 +#./scala-scala/src/library/scala/collection/generic/ParSetFactory.scala ./scala-scala/src/library/scala/collection/generic/OrderedTraversableFactory.scala ./scala-scala/src/library/scala/collection/generic/SeqForwarder.scala -- cgit v1.2.3