diff options
-rw-r--r-- | src/library/scala/collection/immutable/Stream.scala | 42 | ||||
-rw-r--r-- | test/files/run/stream-stack-overflow-filter-map.scala | 44 |
2 files changed, 74 insertions, 12 deletions
diff --git a/src/library/scala/collection/immutable/Stream.scala b/src/library/scala/collection/immutable/Stream.scala index 1bf1e20694..97707d4f7c 100644 --- a/src/library/scala/collection/immutable/Stream.scala +++ b/src/library/scala/collection/immutable/Stream.scala @@ -479,22 +479,40 @@ self => final class StreamWithFilter(p: A => Boolean) extends WithFilter(p) { override def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Stream[A], B, That]): That = { - def tailMap = asStream[B](tail withFilter p map f) - if (isStreamBuilder(bf)) asThat( - if (isEmpty) Stream.Empty - else if (p(head)) cons(f(head), tailMap) - else tailMap - ) + def tailMap(coll: Stream[A]): Stream[B] = { + var head: A = null.asInstanceOf[A] + var tail: Stream[A] = coll + while (true) { + if (tail.isEmpty) + return Stream.Empty + head = tail.head + tail = tail.tail + if (p(head)) + return cons(f(head), tailMap(tail)) + } + throw new RuntimeException() + } + + if (isStreamBuilder(bf)) asThat(tailMap(Stream.this)) else super.map(f)(bf) } override def flatMap[B, That](f: A => GenTraversableOnce[B])(implicit bf: CanBuildFrom[Stream[A], B, That]): That = { - def tailFlatMap = asStream[B](tail withFilter p flatMap f) - if (isStreamBuilder(bf)) asThat( - if (isEmpty) Stream.Empty - else if (p(head)) f(head).toStream append tailFlatMap - else tailFlatMap - ) + def tailFlatMap(coll: Stream[A]): Stream[B] = { + var head: A = null.asInstanceOf[A] + var tail: Stream[A] = coll + while (true) { + if (tail.isEmpty) + return Stream.Empty + head = tail.head + tail = tail.tail + if (p(head)) + return f(head).toStream append tailFlatMap(tail) + } + throw new RuntimeException() + } + + if (isStreamBuilder(bf)) asThat(tailFlatMap(Stream.this)) else super.flatMap(f)(bf) } diff --git a/test/files/run/stream-stack-overflow-filter-map.scala b/test/files/run/stream-stack-overflow-filter-map.scala new file mode 100644 index 0000000000..f3a9dd49cb --- /dev/null +++ b/test/files/run/stream-stack-overflow-filter-map.scala @@ -0,0 +1,44 @@ +import collection.generic.{FilterMonadic, CanBuildFrom} + +object Test extends App { + def mapSucc[Repr, That](s: FilterMonadic[Int, Repr])(implicit cbf: CanBuildFrom[Repr, Int, That]) = s map (_ + 1) + def flatMapId[T, Repr, That](s: FilterMonadic[T, Repr])(implicit cbf: CanBuildFrom[Repr, T, That]) = s flatMap (Seq(_)) + + def testStreamPred(s: Stream[Int])(p: Int => Boolean) { + val res1 = s withFilter p + val res2 = s filter p + + val expected = s.toSeq filter p + + val fMapped1 = flatMapId(res1) + val fMapped2 = flatMapId(res2) + assert(fMapped1 == fMapped2) + assert(fMapped1.toSeq == expected) + + val mapped1 = mapSucc(res1) + val mapped2 = mapSucc(res2) + assert(mapped1 == mapped2) + assert(mapped1.toSeq == (expected map (_ + 1))) + + assert((res1 map identity).toSeq == res2.toSeq) + } + + def testStream(s: Stream[Int]) { + testStreamPred(s)(_ => false) + testStreamPred(s)(_ => true) + testStreamPred(s)(_ % 2 == 0) + testStreamPred(s)(_ % 3 == 0) + } + + //Reduced version of the test case - either invocation used to cause a stack + //overflow before commit 80b3f433e5536d086806fa108ccdfacf10719cc2. + val resFMap = (1 to 10000).toStream withFilter (_ => false) flatMap (Seq(_)) + val resMap = (1 to 10000).toStream withFilter (_ => false) map (_ + 1) + + //Complete test case for withFilter + map/flatMap, as requested by @axel22. + for (j <- (0 to 3) :+ 10000) { + val stream = (1 to j).toStream + assert(stream.toSeq == (1 to j).toSeq) + testStream(stream) + } +} |