Attacking exponential complexity in TypeMaps

retronym · retronym · commit 238b1fba3d50 · 2015-11-13T14:24:35.000+10:00
- 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 scala@f8b2b21
diff --git 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
@@ -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
@@ -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
@@ -0,0 +1 @@
+-Ystop-after:refchecks
diff --git a/test/files/pos/existential-slow-compile1.scala 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[_]]]]]]]]]]]]]]]]]]]]]]]]
+          = ??? } }
+
