From 80b3f433e5536d086806fa108ccdfacf10719cc2 Mon Sep 17 00:00:00 2001 From: Paolo Giarrusso Date: Mon, 20 Aug 2012 19:34:43 +0200 Subject: Make Stream.withFilter.{map,flatMap} run in constant stack space The included test currently fails because `map` and `flatMap` do not run in constant stack space on a stream returned by `Stream.withFilter`, as I reported here: https://groups.google.com/d/msg/scala-language/WqJR38REXnk/saaSiDdmyqoJ Fix the problem and add a simple testcase. Note that the stack space consumed when producing an element of this stream is proportional to the number of elements failing the test before the next success. The stack space consumed to produce the stream itself is the space needed to produce the first element, that is, is proportional to the number of failures before the first success. --- test/files/run/stream-stack-overflow-filter-map.check | 2 ++ test/files/run/stream-stack-overflow-filter-map.scala | 14 ++++++++++++++ 2 files changed, 16 insertions(+) create mode 100644 test/files/run/stream-stack-overflow-filter-map.check create mode 100644 test/files/run/stream-stack-overflow-filter-map.scala (limited to 'test') diff --git a/test/files/run/stream-stack-overflow-filter-map.check b/test/files/run/stream-stack-overflow-filter-map.check new file mode 100644 index 0000000000..dbf856668b --- /dev/null +++ b/test/files/run/stream-stack-overflow-filter-map.check @@ -0,0 +1,2 @@ +Stream() +Stream() 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..e2bd47bfca --- /dev/null +++ b/test/files/run/stream-stack-overflow-filter-map.scala @@ -0,0 +1,14 @@ +object Test extends App { + //This runs fine. + val resFMap1 = (1 to 10000).toStream filter (_ => false) flatMap (Seq(_)) + val resMap1 = (1 to 10000).toStream filter (_ => false) map (_ + 1) + assert(resMap1.isEmpty) + assert(resFMap1.isEmpty) + println(resMap1) + println(resFMap1) + //This will cause a stack overflow + val resFMap2 = (1 to 10000).toStream withFilter (_ => false) flatMap (Seq(_)) + val resMap2 = (1 to 10000).toStream withFilter (_ => false) map (_ + 1) + assert(resMap1 == resMap2) + assert(resFMap1 == resFMap2) +} -- cgit v1.2.3 From baca952d6a3953e1c3537bc1f13fa733211ec040 Mon Sep 17 00:00:00 2001 From: Paolo Giarrusso Date: Mon, 20 Aug 2012 22:44:49 +0200 Subject: Cleanup testcase No need to check the output - checking programmatically that the produced streams are empty is enough. --- test/files/run/stream-stack-overflow-filter-map.check | 2 -- test/files/run/stream-stack-overflow-filter-map.scala | 6 ++---- 2 files changed, 2 insertions(+), 6 deletions(-) delete mode 100644 test/files/run/stream-stack-overflow-filter-map.check (limited to 'test') diff --git a/test/files/run/stream-stack-overflow-filter-map.check b/test/files/run/stream-stack-overflow-filter-map.check deleted file mode 100644 index dbf856668b..0000000000 --- a/test/files/run/stream-stack-overflow-filter-map.check +++ /dev/null @@ -1,2 +0,0 @@ -Stream() -Stream() diff --git a/test/files/run/stream-stack-overflow-filter-map.scala b/test/files/run/stream-stack-overflow-filter-map.scala index e2bd47bfca..8210518d95 100644 --- a/test/files/run/stream-stack-overflow-filter-map.scala +++ b/test/files/run/stream-stack-overflow-filter-map.scala @@ -1,12 +1,10 @@ object Test extends App { - //This runs fine. val resFMap1 = (1 to 10000).toStream filter (_ => false) flatMap (Seq(_)) val resMap1 = (1 to 10000).toStream filter (_ => false) map (_ + 1) assert(resMap1.isEmpty) assert(resFMap1.isEmpty) - println(resMap1) - println(resFMap1) - //This will cause a stack overflow + + //This risks causing a stack overflow val resFMap2 = (1 to 10000).toStream withFilter (_ => false) flatMap (Seq(_)) val resMap2 = (1 to 10000).toStream withFilter (_ => false) map (_ + 1) assert(resMap1 == resMap2) -- cgit v1.2.3 From ee40800f63ceaa65e6e241a093d0178e055657da Mon Sep 17 00:00:00 2001 From: Paolo Giarrusso Date: Wed, 22 Aug 2012 16:39:40 +0200 Subject: Improve test for Stream.withFilter.{map,flatMap} Test a wider range of functionality. --- .../run/stream-stack-overflow-filter-map.scala | 50 +++++++++++++++++----- 1 file changed, 40 insertions(+), 10 deletions(-) (limited to 'test') diff --git a/test/files/run/stream-stack-overflow-filter-map.scala b/test/files/run/stream-stack-overflow-filter-map.scala index 8210518d95..c6e8781d0a 100644 --- a/test/files/run/stream-stack-overflow-filter-map.scala +++ b/test/files/run/stream-stack-overflow-filter-map.scala @@ -1,12 +1,42 @@ +import collection.generic.{FilterMonadic, CanBuildFrom} + object Test extends App { - val resFMap1 = (1 to 10000).toStream filter (_ => false) flatMap (Seq(_)) - val resMap1 = (1 to 10000).toStream filter (_ => false) map (_ + 1) - assert(resMap1.isEmpty) - assert(resFMap1.isEmpty) - - //This risks causing a stack overflow - val resFMap2 = (1 to 10000).toStream withFilter (_ => false) flatMap (Seq(_)) - val resMap2 = (1 to 10000).toStream withFilter (_ => false) map (_ + 1) - assert(resMap1 == resMap2) - assert(resFMap1 == resFMap2) + 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) { + testStream((1 to j).toStream) + } } -- cgit v1.2.3 From 8d770a78731fa72ae227fc020195910aee34304a Mon Sep 17 00:00:00 2001 From: Paolo Giarrusso Date: Wed, 22 Aug 2012 16:48:32 +0200 Subject: Also check that Stream.toSeq gives the right result. --- test/files/run/stream-stack-overflow-filter-map.scala | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'test') diff --git a/test/files/run/stream-stack-overflow-filter-map.scala b/test/files/run/stream-stack-overflow-filter-map.scala index c6e8781d0a..f3a9dd49cb 100644 --- a/test/files/run/stream-stack-overflow-filter-map.scala +++ b/test/files/run/stream-stack-overflow-filter-map.scala @@ -37,6 +37,8 @@ object Test extends App { //Complete test case for withFilter + map/flatMap, as requested by @axel22. for (j <- (0 to 3) :+ 10000) { - testStream((1 to j).toStream) + val stream = (1 to j).toStream + assert(stream.toSeq == (1 to j).toSeq) + testStream(stream) } } -- cgit v1.2.3