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 /src/reflect | |
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 'src/reflect')
-rw-r--r-- | src/reflect/scala/reflect/internal/util/Collections.scala | 38 |
1 files changed, 31 insertions, 7 deletions
diff --git a/src/reflect/scala/reflect/internal/util/Collections.scala b/src/reflect/scala/reflect/internal/util/Collections.scala index f32825252c..59af819dad 100644 --- a/src/reflect/scala/reflect/internal/util/Collections.scala +++ b/src/reflect/scala/reflect/internal/util/Collections.scala @@ -53,17 +53,41 @@ trait Collections { } lb.toList } + /** like map2, but returns list `xs` itself - instead of a copy - if function * `f` maps all elements to themselves. */ - final def map2Conserve[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 + final def map2Conserve[A <: AnyRef, B](xs: List[A], ys: List[B])(f: (A, B) => A): List[A] = { + // Note to developers: there exists a duplication between this function and `List#mapConserve`. + // If any successful optimization attempts or other changes are made, please rehash them there too. + @tailrec + def loop(mapped: ListBuffer[A], unchanged: List[A], pending0: List[A], pending1: List[B]): List[A] = { + if (pending0.isEmpty || pending1.isEmpty) { + if (mapped eq null) unchanged + else mapped.prependToList(unchanged) + } else { + val head00 = pending0.head + val head01 = pending1.head + val head1 = f(head00, head01) + + if ((head1 eq head00.asInstanceOf[AnyRef])) { + loop(mapped, unchanged, pending0.tail, pending1.tail) + } else { + val b = if (mapped eq null) new ListBuffer[A] else mapped + var xc = unchanged + while ((xc ne pending0) && (xc ne pending1)) { + b += xc.head + xc = xc.tail + } + b += head1 + val tail0 = pending0.tail + val tail1 = pending1.tail + loop(b, tail0, tail0, tail1) + } + } } + loop(null, xs, xs, ys) + } final def map3[A, B, C, D](xs1: List[A], xs2: List[B], xs3: List[C])(f: (A, B, C) => D): List[D] = { if (xs1.isEmpty || xs2.isEmpty || xs3.isEmpty) Nil |