diff options
| -rw-r--r-- | src/library/scala/collection/immutable/List.scala | 2 | ||||
| -rw-r--r-- | src/reflect/scala/reflect/internal/util/Collections.scala | 38 | ||||
| -rw-r--r-- | test/files/scalacheck/CheckCollections.scala | 59 |
3 files changed, 92 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 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) + +} |