From b741e8ada8d8ba716af791868ba1222cd74255e4 Mon Sep 17 00:00:00 2001
From: George Leontiev <folone@gmail.com>
Date: Tue, 30 Jul 2013 11:06:26 +0200
Subject: Make map2Conserve occupy constant stack space in spirit of SI-2411

I recently discovered a StackOverflowError, caused by this function:
https://gist.github.com/folone/7b2f2e2a16314ab28109
The circumstances are pretty extreme, still having a tail-recursive
function seems to be a good idea.
The function behaves the same way old function did (supported by tests),
which is not really how map2 behaves. I did not change this behavior to
not introduce any regression. I actually tried to make it behave like map2,
and it does introduce regression.
---
 test/files/scalacheck/CheckCollections.scala | 59 ++++++++++++++++++++++++++++
 1 file changed, 59 insertions(+)
 create mode 100644 test/files/scalacheck/CheckCollections.scala

(limited to 'test/files/scalacheck')

diff --git a/test/files/scalacheck/CheckCollections.scala b/test/files/scalacheck/CheckCollections.scala
new file mode 100644
index 0000000000..108040b900
--- /dev/null
+++ b/test/files/scalacheck/CheckCollections.scala
@@ -0,0 +1,59 @@
+import org.scalacheck.{ ConsoleReporter, Properties }
+import org.scalacheck.Prop._
+
+import scala.reflect.internal.util.Collections._
+
+object Test extends Properties("reflect.internal.util.Collections") {
+  def map2ConserveOld[A <: AnyRef, B](xs: List[A], ys: List[B])(f: (A, B) => A): List[A] =
+    if (xs.isEmpty || ys.isEmpty) xs
+    else {
+      val x1 = f(xs.head, ys.head)
+      val xs1 = map2Conserve(xs.tail, ys.tail)(f)
+      if ((x1 eq xs.head) && (xs1 eq xs.tail)) xs
+      else x1 :: xs1
+    }
+
+  val testfun: (String, Int) => String = { case(x, y) =>
+    x.toLowerCase + y.toString
+  }
+  val testid: (String, Int) => String = { case (x, y) => x }
+
+  val prop1_map2Conserve = forAll { (xs: List[String], ys: List[Int]) =>
+    val res = map2Conserve(xs, ys)(testid)
+    res eq xs
+  }
+
+  val prop2_map2Conserve = forAll { (xs: List[String], ys: List[Int]) =>
+    map2Conserve(xs, ys)(testid)  == map2ConserveOld(xs, ys)(testid) &&
+    map2Conserve(xs, ys)(testfun) == map2ConserveOld(xs, ys)(testfun)
+  }
+
+  def checkStackOverflow() {
+    var xs: List[String] = Nil
+    var ys: List[Int]    = Nil
+    for (i <- 0 until 250000) {
+        xs = "X" :: xs
+        ys = 1   :: ys
+    }
+    map2Conserve(xs, ys){ case(x, y) => x.toLowerCase + y.toString }
+  }
+
+
+  val tests = List(
+    ("map2Conserve(identity)",   prop1_map2Conserve),
+    ("map2Conserve == old impl", prop2_map2Conserve)
+  )
+
+  checkStackOverflow()
+
+  for {
+    (label, prop) <- tests
+  } property(label) = prop
+
+  import org.scalacheck.{ Test => STest }
+
+  def runTests() =
+    STest.checkProperties(
+      STest.Params(testCallback = ConsoleReporter(0)), this)
+
+}
-- 
cgit v1.2.3