Partially solves the problem for #3502.

This commit reimplements filter for Streams, but does not reimplement
map in StreamWithFilter.

The problem is that GC can't collect instances of Streams residing on the stack if there are multiple references to the Stream (more than a single one on the stack on which a Stream method is invoked). In the case of a StreamWithFilter, being an inner class, there is always an `$outer` reference to the outer object, so there is little GC can do. Possible solution - change the return type of WithFilter to something else (in TraversableLike) to allow it to return objects that don't have to subclass TraversableLike.WithFilter, and reimplement the withFilter method in Stream to simply call `filter` method - in the case of Streams, `withFilter` has little sense in either case...

2 files changed, 38 insertions, 4 deletions

diff --git a/src/library/scala/collection/immutable/Stream.scala b/src/library/scala/collection/immutable/Stream.scala
index 9ad7a49e2a..9610afb8cd 100644
--- a/src/library/scala/collection/immutable/Stream.scala
+++ b/src/library/scala/collection/immutable/Stream.scala
@@ -15,6 +15,8 @@ import generic._
 import mutable.{Builder, StringBuilder, LazyBuilder, ListBuffer}
 import scala.annotation.tailrec
 
+
+
 /** The class `Stream` implements lazy lists where elements
  *  are only evaluated when they are needed. Here is an example:
  *
@@ -201,11 +203,14 @@ self =>
    *  @param p the predicate used to filter the stream.
    *  @return the elements of this stream satisfying <code>p</code>.
    */
-  override final def filter(p: A => Boolean): Stream[A] = {
+  override def filter(p: A => Boolean): Stream[A] = {
     // optimization: drop leading prefix of elems for which f returns false
-    var rest = this dropWhile (!p(_))
-    if (rest.isEmpty) Stream.Empty
-    else new Stream.Cons(rest.head, rest.tail filter p)
+    // var rest = this dropWhile (!p(_)) - forget DRY principle - GC can't collect otherwise
+    var rest = this
+    while (!rest.isEmpty && !p(rest.head)) rest = rest.tail
+    // private utility func to avoid `this` on stack (would be needed for the lazy arg)
+    if (rest.nonEmpty) Stream.filteredTail(rest, p)
+    else Stream.Empty
   }
 
   override final def withFilter(p: A => Boolean): StreamWithFilter = new StreamWithFilter(p)
@@ -213,6 +218,7 @@ self =>
   /** A lazier implementation of WithFilter than TraversableLike's.
    */
   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)
       asThat[That](
@@ -612,6 +618,10 @@ object Stream extends SeqFactory[Stream] {
     if (if (step < 0) start <= end else end <= start) Empty
     else new Cons(start, range(start + step, end, step))
 
+  private[immutable] def filteredTail[A](stream: Stream[A], p: A => Boolean) = {
+    new Stream.Cons(stream.head, stream.tail filter p)
+  }
+
   /** A stream containing all elements of a given iterator, in the order they are produced.
    *  @param it   The iterator producing the stream's elements
    */
diff --git a/test/files/run/t3502.scala b/test/files/run/t3502.scala
new file mode 100644
index 0000000000..cc78e54c86
--- /dev/null
+++ b/test/files/run/t3502.scala
@@ -0,0 +1,24 @@
+
+
+
+
+
+// ticket #3502
+object Test {
+
+  object GeneratePrimeFactorsLazy extends (Int => List[Int]) {
+    override def apply(n:Int) = {
+      val s = Stream.range(2, n / 2).filter(n % _ == 0)
+      //val s = for (i <- Stream.range(2, n / 2); if n % i == 0) yield i
+      s.headOption.map(x => x :: apply(n / x)).getOrElse(List(n))
+    }
+  }
+
+  def main(args:Array[String]) {
+    // a prime number
+    //val num = 623456789
+    val num = 2796203
+    assert(GeneratePrimeFactorsLazy(num) == List(num))
+  }
+
+}