diff options
author | Grzegorz Kossakowski <grzegorz.kossakowski@gmail.com> | 2013-08-12 13:20:32 -0700 |
---|---|---|
committer | Grzegorz Kossakowski <grzegorz.kossakowski@gmail.com> | 2013-08-12 13:20:32 -0700 |
commit | 651e1988fa1e0f8efeb4eeca9e83d833c1895da3 (patch) | |
tree | 847cf93dea5e9da5b9a48a4d0dea8d7c94f9db6f /src/reflect | |
parent | 8589deb4b4da4664fb79e6e371f33e0b71298f5f (diff) | |
parent | b741e8ada8d8ba716af791868ba1222cd74255e4 (diff) | |
download | scala-651e1988fa1e0f8efeb4eeca9e83d833c1895da3.tar.gz scala-651e1988fa1e0f8efeb4eeca9e83d833c1895da3.tar.bz2 scala-651e1988fa1e0f8efeb4eeca9e83d833c1895da3.zip |
Merge pull request #2764 from folone/master
Making map2Conserve occupy constant stack space in spirit of SI-2411.
Diffstat (limited to 'src/reflect')
-rw-r--r-- | src/reflect/scala/reflect/internal/Types.scala | 15 | ||||
-rw-r--r-- | src/reflect/scala/reflect/internal/util/Collections.scala | 36 |
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) |