Attacking exponential complexity in TypeMaps

  - Don't normalize existentials during the `contain`-s type map;
    `ExistentialType#normalize' calls contains internally and
    an exponential blowup ensues.
  - Ensure that the type map used in variance validation never
    returns modified types in order to avoid needless cloning of
    symbols.

The enclosed test case still gets stuck in Uncurry, thanks to
the way that `TypeMap#mapOver(List[Symbol])` recurses through the
type first to check whether the type map would be an no-op or not.
If not, it repeats the type map with cloned symbols. Doing the work
twice at each level of recursion blows up the complexity.

Removing that "fast path" allows the enclosed test to compile
completely. As at this commit, it gets stuck in uncurry, which
dealiases `s.List` to `s.c.i.List` within the type.

Some more background on the troublesome part of `TypeMap`:

  http://lrytz.github.io/scala-aladdin-bugtracker/displayItem.do%3Fid=1210.html
  https://github.com/scala/scala/commit/f8b2b21050e7a2ca0f537ef70e3e0c8eead43abc

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[_]]]]]]]]]]]]]]]]]]]]]]]]
+          = ??? } }
+