diff options
author | George Leontiev <folone@gmail.com> | 2013-07-30 11:06:26 +0200 |
---|---|---|
committer | George Leontiev <folone@gmail.com> | 2013-08-08 20:38:24 +0200 |
commit | b741e8ada8d8ba716af791868ba1222cd74255e4 (patch) | |
tree | 06c6af67ecf12a97e730bf926398744f947af9f4 /test | |
parent | b145cb1c5d98cf7b01a145fa38c3e412e59f81b6 (diff) | |
download | scala-b741e8ada8d8ba716af791868ba1222cd74255e4.tar.gz scala-b741e8ada8d8ba716af791868ba1222cd74255e4.tar.bz2 scala-b741e8ada8d8ba716af791868ba1222cd74255e4.zip |
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.
Diffstat (limited to 'test')
-rw-r--r-- | test/files/scalacheck/CheckCollections.scala | 59 |
1 files changed, 59 insertions, 0 deletions
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) + +} |