From 6fbb4ac42a3fa00689a6c3bbde2be273b7c36b2d Mon Sep 17 00:00:00 2001
From: Paul Phillips <paulp@improving.org>
Date: Wed, 12 Sep 2012 12:02:07 -0700
Subject: Fix for SI-6367, exponential time in inference.

This pathology is not new - it can be witnessed in 2.9,
where compiling the test case enclosed with this ticket with
-Yinfer-debug will print a line with (pinky to lips) one million
type parameters. 1048576 actually, aka 2^20. But in 2.9 we were
somehow getting away with creating the list, presumably by not
spending much time looking at it. Somewhere between there and M1,
that changed.

I cut it off at the knees - don't create a list of one million
upper bound constraints when 1 will suffice. It would not be too
surprising if this proves to be a boon for performance.
---
 src/reflect/scala/reflect/internal/Types.scala | 30 +++++++++++++----------
 test/files/pos/t6367.scala                     | 34 ++++++++++++++++++++++++++
 2 files changed, 51 insertions(+), 13 deletions(-)
 create mode 100644 test/files/pos/t6367.scala

diff --git a/src/reflect/scala/reflect/internal/Types.scala b/src/reflect/scala/reflect/internal/Types.scala
index df44cf234e..29f7b53154 100644
--- a/src/reflect/scala/reflect/internal/Types.scala
+++ b/src/reflect/scala/reflect/internal/Types.scala
@@ -3935,13 +3935,15 @@ trait Types extends api.Types { self: SymbolTable =>
     def avoidWiden: Boolean = avoidWidening
 
     def addLoBound(tp: Type, isNumericBound: Boolean = false) {
-      if (isNumericBound && isNumericValueType(tp)) {
-        if (numlo == NoType || isNumericSubType(numlo, tp))
-          numlo = tp
-        else if (!isNumericSubType(tp, numlo))
-          numlo = numericLoBound
+      if (!lobounds.contains(tp)) {
+        if (isNumericBound && isNumericValueType(tp)) {
+          if (numlo == NoType || isNumericSubType(numlo, tp))
+            numlo = tp
+          else if (!isNumericSubType(tp, numlo))
+            numlo = numericLoBound
+        }
+        else lobounds ::= tp
       }
-      else lobounds ::= tp
     }
 
     def checkWidening(tp: Type) {
@@ -3953,14 +3955,16 @@ trait Types extends api.Types { self: SymbolTable =>
     }
 
     def addHiBound(tp: Type, isNumericBound: Boolean = false) {
-      checkWidening(tp)
-      if (isNumericBound && isNumericValueType(tp)) {
-        if (numhi == NoType || isNumericSubType(tp, numhi))
-          numhi = tp
-        else if (!isNumericSubType(numhi, tp))
-          numhi = numericHiBound
+      if (!hibounds.contains(tp)) {
+        checkWidening(tp)
+        if (isNumericBound && isNumericValueType(tp)) {
+          if (numhi == NoType || isNumericSubType(tp, numhi))
+            numhi = tp
+          else if (!isNumericSubType(numhi, tp))
+            numhi = numericHiBound
+        }
+        else hibounds ::= tp
       }
-      else hibounds ::= tp
     }
 
     def isWithinBounds(tp: Type): Boolean =
diff --git a/test/files/pos/t6367.scala b/test/files/pos/t6367.scala
new file mode 100644
index 0000000000..1214be7418
--- /dev/null
+++ b/test/files/pos/t6367.scala
@@ -0,0 +1,34 @@
+package play.api.libs.json.util
+
+trait FunctionalCanBuild[M[_]]{
+  def apply[A,B](ma:M[A], mb:M[B]):M[A ~ B]
+}
+
+trait Variant[M[_]]
+
+trait Functor[M[_]] extends Variant[M]{
+  def fmap[A,B](m:M[A], f: A => B): M[B]
+}
+
+case class ~[A,B](_1:A,_2:B)
+
+class FunctionalBuilder[M[_]](canBuild:FunctionalCanBuild[M]){
+  class CanBuild20[A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19, A20](
+    m1:M[A1 ~ A2 ~ A3 ~ A4 ~ A5 ~ A6 ~ A7 ~ A8 ~ A9 ~ A10 ~ A11 ~ A12 ~ A13 ~ A14 ~ A15 ~ A16 ~ A17 ~ A18 ~ A19],
+    m2:M[A20]
+  ) {
+
+    def ~[A21](m3:M[A21]) = new CanBuild21(canBuild(m1,m2),m3)
+
+    def apply[B](f: (A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19, A20) => B)(implicit fu:Functor[M]): M[B] =
+      fu.fmap[A1 ~ A2 ~ A3 ~ A4 ~ A5 ~ A6 ~ A7 ~ A8 ~ A9 ~ A10 ~ A11 ~ A12 ~ A13 ~ A14 ~ A15 ~ A16 ~ A17 ~ A18 ~ A19 ~ A20, B](
+        canBuild(m1, m2),
+        { case a1 ~ a2 ~ a3 ~ a4 ~ a5 ~ a6 ~ a7 ~ a8 ~ a9 ~ a10 ~ a11 ~ a12 ~ a13 ~ a14 ~ a15 ~ a16 ~ a17 ~ a18 ~ a19 ~ a20 =>
+              f(a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15, a16, a17, a18, a19, a20) }
+      )
+  }
+
+  class CanBuild21[A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19, A20, A21](m1:M[A1 ~ A2 ~ A3 ~ A4 ~ A5 ~ A6 ~ A7 ~ A8 ~ A9 ~ A10 ~ A11 ~ A12 ~ A13 ~ A14 ~ A15 ~ A16 ~ A17 ~ A18 ~ A19 ~ A20], m2:M[A21]){
+  }
+
+}
-- 
cgit v1.2.3