Merge pull request #2764 from folone/master

Making map2Conserve occupy constant stack space in spirit of SI-2411.

2 files changed, 38 insertions, 13 deletions

diff --git a/src/reflect/scala/reflect/internal/Types.scala b/src/reflect/scala/reflect/internal/Types.scala
index 11527d88ca..71f46fedb7 100644
--- a/src/reflect/scala/reflect/internal/Types.scala
+++ b/src/reflect/scala/reflect/internal/Types.scala
@@ -80,7 +80,8 @@ trait Types
   with tpe.CommonOwners
   with tpe.GlbLubs
   with tpe.TypeMaps
-  with tpe.TypeConstraints { self: SymbolTable =>
+  with tpe.TypeConstraints
+  with util.Collections { self: SymbolTable =>
 
   import definitions._
   import TypesStats._
@@ -4317,18 +4318,6 @@ trait Types
       }
   }
 
-  /** like map2, but returns list `xs` itself - instead of a copy - if function
-   *  `f` maps all elements to themselves.
-   */
-  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
-    }
-
   /** Do type arguments `targs` conform to formal parameters `tparams`?
    */
   def isWithinBounds(pre: Type, owner: Symbol, tparams: List[Symbol], targs: List[Type]): Boolean = {
diff --git a/src/reflect/scala/reflect/internal/util/Collections.scala b/src/reflect/scala/reflect/internal/util/Collections.scala
index e127d577e1..59af819dad 100644
--- a/src/reflect/scala/reflect/internal/util/Collections.scala
+++ b/src/reflect/scala/reflect/internal/util/Collections.scala
@@ -53,6 +53,42 @@ 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] = {
+    // 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
     else f(xs1.head, xs2.head, xs3.head) :: map3(xs1.tail, xs2.tail, xs3.tail)(f)