Merge pull request #4828 from retronym/topic/existential-contains

Attacking exponential complexity in TypeMaps

5 files changed, 44 insertions, 13 deletions

diff --git a/src/reflect/scala/reflect/internal/Variances.scala b/src/reflect/scala/reflect/internal/Variances.scala
index ef22df3f2e..af04f47e0e 100644
--- a/src/reflect/scala/reflect/internal/Variances.scala
+++ b/src/reflect/scala/reflect/internal/Variances.scala
@@ -122,15 +122,21 @@ trait Variances {
        *  same is true of the parameters (ValDefs) unless we are inside a
        *  refinement, in which case they are checked from here.
        */
-      def apply(tp: Type): Type = tp match {
-        case _ if isUncheckedVariance(tp)                    => tp
-        case _ if resultTypeOnly(tp)                         => this(tp.resultType)
-        case TypeRef(_, sym, _) if sym.isAliasType           => this(tp.normalize)
-        case TypeRef(_, sym, _) if !sym.variance.isInvariant => checkVarianceOfSymbol(sym) ; mapOver(tp)
-        case RefinedType(_, _)                               => withinRefinement(mapOver(tp))
-        case ClassInfoType(parents, _, _)                    => parents foreach this ; tp
-        case mt @ MethodType(_, result)                      => flipped(mt.paramTypes foreach this) ; this(result)
-        case _                                               => mapOver(tp)
+      def apply(tp: Type): Type = {
+        tp match {
+          case _ if isUncheckedVariance(tp)                    =>
+          case _ if resultTypeOnly(tp)                         => this(tp.resultType)
+          case TypeRef(_, sym, _) if sym.isAliasType           => this(tp.normalize)
+          case TypeRef(_, sym, _) if !sym.variance.isInvariant => checkVarianceOfSymbol(sym) ; mapOver(tp)
+          case RefinedType(_, _)                               => withinRefinement(mapOver(tp))
+          case ClassInfoType(parents, _, _)                    => parents foreach this
+          case mt @ MethodType(_, result)                      => flipped(mt.paramTypes foreach this) ; this(result)
+          case _                                               => mapOver(tp)
+        }
+        // We're using TypeMap here for type traversal only. To avoid wasteful symbol
+        // cloning during the recursion, it is important to return the input `tp`, rather
+        // than the result of the pattern match above, which normalizes types.
+        tp
       }
       def validateDefinition(base: Symbol) {
         val saved = this.base
diff --git a/src/reflect/scala/reflect/internal/tpe/TypeMaps.scala b/src/reflect/scala/reflect/internal/tpe/TypeMaps.scala
index b8d4050d7d..804360b677 100644
--- a/src/reflect/scala/reflect/internal/tpe/TypeMaps.scala
+++ b/src/reflect/scala/reflect/internal/tpe/TypeMaps.scala
@@ -998,10 +998,20 @@ private[internal] trait TypeMaps {
   class ContainsCollector(sym: Symbol) extends TypeCollector(false) {
     def traverse(tp: Type) {
       if (!result) {
-        tp.normalize match {
-          case TypeRef(_, sym1, _) if (sym == sym1) => result = true
-          case SingleType(_, sym1) if (sym == sym1) => result = true
-          case _ => mapOver(tp)
+        tp match {
+          case _: ExistentialType =>
+            // ExistentialType#normalize internally calls contains, which leads to exponential performance
+            // for types like: `A[_ <: B[_ <: ... ]]`. Example: pos/existential-contains.scala.
+            //
+            // We can just map over the components and wait until we see the underlying type before we call
+            // normalize.
+            mapOver(tp)
+          case _ =>
+            tp.normalize match {
+              case TypeRef(_, sym1, _) if (sym == sym1) => result = true
+              case SingleType(_, sym1) if (sym == sym1) => result = true
+              case _ => mapOver(tp)
+            }
         }
       }
     }
diff --git a/test/files/pos/existental-slow-compile2.scala b/test/files/pos/existental-slow-compile2.scala
new file mode 100644
index 0000000000..907344982c
--- /dev/null
+++ b/test/files/pos/existental-slow-compile2.scala
@@ -0,0 +1,7 @@
+class C {
+  class L[+A]
+  def test = {
+    val foo:
+      L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: _ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: _ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_]]]]]]]]]]]]]]]]]]]]]]]]
+          = ??? } }
+
diff --git a/test/files/pos/existential-slow-compile1.flags b/test/files/pos/existential-slow-compile1.flags
new file mode 100644
index 0000000000..7f7581974d
--- /dev/null
+++ b/test/files/pos/existential-slow-compile1.flags
@@ -0,0 +1 @@
+-Ystop-after:refchecks
diff --git a/test/files/pos/existential-slow-compile1.scala b/test/files/pos/existential-slow-compile1.scala
new file mode 100644
index 0000000000..8602afd9db
--- /dev/null
+++ b/test/files/pos/existential-slow-compile1.scala
@@ -0,0 +1,7 @@
+class C {
+  type L[+A] = scala.collection.immutable.List[A]
+  def test = {
+    val foo:
+      L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: _ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: _ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_ <: L[_]]]]]]]]]]]]]]]]]]]]]]]]
+          = ??? } }
+