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.

2 files changed, 33 insertions, 7 deletions

diff --git a/src/library/scala/collection/immutable/List.scala b/src/library/scala/collection/immutable/List.scala
index c01694960c..b11368acdf 100644
--- a/src/library/scala/collection/immutable/List.scala
+++ b/src/library/scala/collection/immutable/List.scala
@@ -161,6 +161,8 @@ sealed abstract class List[+A] extends AbstractSeq[A]
    *    @inheritdoc
    */
   @inline final def mapConserve[B >: A <: AnyRef](f: A => B): List[B] = {
+    // Note to developers: there exists a duplication between this function and `reflect.internal.util.Collections#map2Conserve`.
+    // If any successful optimization attempts or other changes are made, please rehash them there too.
     @tailrec
     def loop(mapped: ListBuffer[B], unchanged: List[A], pending: List[A]): List[B] =
       if (pending.isEmpty) {
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