From b6cbee9d81320524aa2e8a3d80dbf2062dd43fd2 Mon Sep 17 00:00:00 2001
From: Jason Zaugg <jzaugg@gmail.com>
Date: Wed, 18 Feb 2015 14:02:08 +1000
Subject: SI-9157 Avoid exponential blowup with chained type projections

Calling `findMember` in the enclosed test was calling into
`NonClassTypeRef#relativeInfo` an exponentially-increasing number
of times, with respect to the length of the chained type projections.

The numbers of calls increased as: 26, 326, 3336, 33446, 334556.
Can any pattern spotters in the crowd that can identify the sequence?
(I can't.)

Tracing the calls saw we were computing the same `memberType`
repeatedly. This part of the method was not guarded by the cache.

I have changed the method to use the standard idiom of using the
current period for cache invalidation. The enclosed test now compiles
promptly, rather than in geological time.
---
 src/compiler/scala/tools/nsc/typechecker/TreeCheckers.scala |  1 -
 src/reflect/scala/reflect/internal/Types.scala              | 10 +++++-----
 test/files/pos/t9157.scala                                  | 13 +++++++++++++
 3 files changed, 18 insertions(+), 6 deletions(-)
 create mode 100644 test/files/pos/t9157.scala

diff --git a/src/compiler/scala/tools/nsc/typechecker/TreeCheckers.scala b/src/compiler/scala/tools/nsc/typechecker/TreeCheckers.scala
index 743bbe53bd..02356580cc 100644
--- a/src/compiler/scala/tools/nsc/typechecker/TreeCheckers.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/TreeCheckers.scala
@@ -266,7 +266,6 @@ abstract class TreeCheckers extends Analyzer {
 
       if (tree ne typed)
         treesDiffer(tree, typed)
-
       tree
     }
 
diff --git a/src/reflect/scala/reflect/internal/Types.scala b/src/reflect/scala/reflect/internal/Types.scala
index ce36f7efa3..8f114caac0 100644
--- a/src/reflect/scala/reflect/internal/Types.scala
+++ b/src/reflect/scala/reflect/internal/Types.scala
@@ -1976,13 +1976,13 @@ trait Types
      * usage scenario.
      */
     private var relativeInfoCache: Type = _
-    private var memberInfoCache: Type = _
+    private var relativeInfoPeriod: Period = NoPeriod
 
-    private[Types] def relativeInfo = {
-      val memberInfo = pre.memberInfo(sym)
-      if (relativeInfoCache == null || (memberInfo ne memberInfoCache)) {
-        memberInfoCache = memberInfo
+    private[Types] def relativeInfo = /*trace(s"relativeInfo(${safeToString}})")*/{
+      if (relativeInfoPeriod != currentPeriod) {
+        val memberInfo = pre.memberInfo(sym)
         relativeInfoCache = transformInfo(memberInfo)
+        relativeInfoPeriod = currentPeriod
       }
       relativeInfoCache
     }
diff --git a/test/files/pos/t9157.scala b/test/files/pos/t9157.scala
new file mode 100644
index 0000000000..e178b5d84d
--- /dev/null
+++ b/test/files/pos/t9157.scala
@@ -0,0 +1,13 @@
+trait Flow[-In, +Out] {
+  type Repr[+O] <: Flow[In, O]
+  def map: Repr[String]
+}
+
+class Test {
+  // typechecking was exponentially slow wrt the number of projections here.
+  def slowFlow(
+    f: Flow[String,String]#Repr[String]#Repr[String]#Repr[String]#Repr[String]#Repr[String]#Repr[String]#Repr[String]#Repr[String]#Repr[String]#Repr[String]#Repr[String]
+  ) = {
+    f.map
+  }
+}
-- 
cgit v1.2.3