Fix: known stack overflow bug in Stream#bind

ms-tg · ms-tg · commit c32ee8f15a82 · 2012-12-19T14:38:19.000-05:00
This fixes a known[1][2] bug which often manifests in stack overflow errors in production usage of the FJ library's Stream class. [1] http://code.google.com/p/functionaljava/issues/detail?id=16 [2] http://stackoverflow.com/questions/10915279/functionaljava-app-throws-stackoverflowerror-with-stream-in-stack-trace
diff --git a/core/src/main/java/fj/data/Stream.java b/core/src/main/java/fj/data/Stream.java
@@ -401,7 +401,16 @@ public final <B, C> F<B, Stream<C>> mapM(final F<A, F<B, C>> f) {
    * @return A new stream after performing the map, then final join.
    */
   public final <B> Stream<B> bind(final F<A, Stream<B>> f) {
-    return join(map(f));
+    return map(f).foldLeft(new F2<Stream<B>, Stream<B>, Stream<B>>() {
+        @Override
+        public Stream<B> f(Stream<B> accumulator, Stream<B> element) {
+            Stream<B> result = accumulator;
+            for (B single : element) {
+                result = result.cons(single);
+            }
+            return result;
+        }
+    }, Stream.<B>nil()).reverse();
   }
 
   /**
diff --git a/core/src/test/fj/data/CheckStream.scala b/core/src/test/fj/data/CheckStream.scala
@@ -10,7 +10,8 @@ import Equal.{streamEqual, stringEqual}
 import Unit.unit
 import Stream.{nil, single, join, iterableStream}
 import Ord.stringOrd
-import org.scalacheck.Properties
+import org.scalacheck.{Gen, Properties}
+import collection.JavaConversions
 
 object CheckStream extends Properties("Stream") {
   property("isEmpty") = forAll((a: Stream[Int]) =>
@@ -47,6 +48,18 @@ object CheckStream extends Properties("Stream") {
     def g(s: String) = s.toUpperCase
     streamEqual(stringEqual).eq(a.map((x: String) => f(g(x))), a.map((x: String) => g(x)).map((x: String) => f(x)))})
 
+  val length = Gen.choose(0, 3000)
+
+  property("bindStackOverflow") = forAll(length)(size => {
+    val stream = iterableStream(JavaConversions.asJavaIterable((1 to size)))
+    val bound: Stream[Int] = stream.bind(new F[Int, Stream[Int]] {
+      def f(a: Int) = single(a)
+    })
+    stream.zip(bound).forall(new F[P2[Int, Int], java.lang.Boolean] {
+      def f(a: P2[Int, Int]) = a._1() == a._2()
+    })
+  })
+
   property("foreach") = forAll((a: Stream[Int]) => {
     var i = 0
     a.foreach({
