SI-8627 make Stream.filterNot non-eager

The obvious fix, overriding `filterNot` in Stream, is not binary
compatible, see https://github.com/scala/scala/pull/3925

Instead, this makes `filterImpl` in TaversableLike private[scala],
which allows overriding it in Stream. The corresponding mima-failures
can be whitelisted, as the changes are only to private[scala].

In 2.12.x we can remove the override of `filter` in Stream, but in
2.11.x this is not binary compatible.

Eventually we'd also like to make filter / filterNot in
TraversableLike final, but that's not source compatible, so it cannot
be done in 2.12.x.

6 files changed, 139 insertions, 13 deletions

diff --git a/bincompat-backward.whitelist.conf b/bincompat-backward.whitelist.conf
index ffacbf0442..1c48887b63 100644
--- a/bincompat-backward.whitelist.conf
+++ b/bincompat-backward.whitelist.conf
@@ -185,6 +185,15 @@ filter {
     {
         matchName="scala.reflect.runtime.SynchronizedOps.newNestedScope"
         problemName=MissingMethodProblem
+    },
+    // see github.com/scala/scala/pull/3925, SI-8627, SI-6440
+    {
+        matchName="scala.collection.TraversableLike.filterImpl"
+        problemName=MissingMethodProblem
+    },
+    {
+        matchName="scala.collection.immutable.Stream.filteredTail"
+        problemName=MissingMethodProblem
     }
   ]
 }
diff --git a/bincompat-forward.whitelist.conf b/bincompat-forward.whitelist.conf
index 0b90cf4c8b..ec80e7cce9 100644
--- a/bincompat-forward.whitelist.conf
+++ b/bincompat-forward.whitelist.conf
@@ -271,6 +271,103 @@ filter {
     {
         matchName="scala.reflect.api.PredefTypeCreator"
         problemName=MissingClassProblem
+    },
+    // see github.com/scala/scala/pull/3925, SI-8627, SI-6440
+    {
+        matchName="scala.collection.IterableViewLike#AbstractTransformed.filterImpl"
+        problemName=MissingMethodProblem
+    },
+    {
+        matchName="scala.collection.AbstractTraversable.filterImpl"
+        problemName=MissingMethodProblem
+    },
+    {
+        matchName="scala.collection.TraversableViewLike#AbstractTransformed.filterImpl"
+        problemName=MissingMethodProblem
+    },
+    {
+        matchName="scala.collection.TraversableLike.filterImpl"
+        problemName=MissingMethodProblem
+    },
+    {
+        matchName="scala.collection.SeqViewLike#AbstractTransformed.filterImpl"
+        problemName=MissingMethodProblem
+    },
+    {
+        matchName="scala.collection.immutable.TreeSet.filterImpl"
+        problemName=MissingMethodProblem
+    },
+    {
+        matchName="scala.collection.immutable.Stream.filteredTail"
+        problemName=MissingMethodProblem
+    },
+    {
+        matchName="scala.collection.immutable.Stream.filterImpl"
+        problemName=MissingMethodProblem
+    },
+    {
+        matchName="scala.collection.immutable.Stream.filterImpl"
+        problemName=MissingMethodProblem
+    },
+    {
+        matchName="scala.collection.immutable.StringOps.filterImpl"
+        problemName=MissingMethodProblem
+    },
+    {
+        matchName="scala.collection.immutable.TreeMap.filterImpl"
+        problemName=MissingMethodProblem
+    },
+    {
+        matchName="scala.collection.concurrent.TrieMap.filterImpl"
+        problemName=MissingMethodProblem
+    },
+    {
+        matchName="scala.collection.mutable.ArrayOps#ofByte.filterImpl"
+        problemName=MissingMethodProblem
+    },
+    {
+        matchName="scala.collection.mutable.ArrayOps#ofLong.filterImpl"
+        problemName=MissingMethodProblem
+    },
+    {
+        matchName="scala.collection.mutable.ArrayOps#ofUnit.filterImpl"
+        problemName=MissingMethodProblem
+    },
+    {
+        matchName="scala.collection.mutable.ArrayOps#ofInt.filterImpl"
+        problemName=MissingMethodProblem
+    },
+    {
+        matchName="scala.collection.mutable.ArrayOps#ofChar.filterImpl"
+        problemName=MissingMethodProblem
+    },
+    {
+        matchName="scala.collection.mutable.ArrayOps#ofRef.filterImpl"
+        problemName=MissingMethodProblem
+    },
+    {
+        matchName="scala.collection.mutable.ArrayOps#ofDouble.filterImpl"
+        problemName=MissingMethodProblem
+    },
+    {
+        matchName="scala.collection.mutable.ArrayOps#ofFloat.filterImpl"
+        problemName=MissingMethodProblem
+    },
+    {
+        matchName="scala.collection.mutable.ArrayOps#ofBoolean.filterImpl"
+        problemName=MissingMethodProblem
+    },
+    {
+        matchName="scala.collection.mutable.ArrayOps#ofShort.filterImpl"
+        problemName=MissingMethodProblem
+    },
+    {
+        matchName="scala.collection.mutable.TreeSet.filterImpl"
+        problemName=MissingMethodProblem
+    },
+    {
+        matchName="scala.reflect.io.AbstractFile.filterImpl"
+        problemName=MissingMethodProblem
     }
   ]
 }
diff --git a/src/library/scala/collection/TraversableLike.scala b/src/library/scala/collection/TraversableLike.scala
index d3a7db6968..a8731a51b1 100644
--- a/src/library/scala/collection/TraversableLike.scala
+++ b/src/library/scala/collection/TraversableLike.scala
@@ -253,7 +253,7 @@ trait TraversableLike[+A, +Repr] extends Any
     b.result
   }
 
-  private def filterImpl(p: A => Boolean, isFlipped: Boolean): Repr = {
+  private[scala] def filterImpl(p: A => Boolean, isFlipped: Boolean): Repr = {
     val b = newBuilder
     for (x <- this)
       if (p(x) != isFlipped) b += x
diff --git a/src/library/scala/collection/immutable/Stream.scala b/src/library/scala/collection/immutable/Stream.scala
index d3ff5e8abf..f43f864e86 100644
--- a/src/library/scala/collection/immutable/Stream.scala
+++ b/src/library/scala/collection/immutable/Stream.scala
@@ -468,6 +468,16 @@ self =>
     )
     else super.flatMap(f)(bf)
 
+  override private[scala] def filterImpl(p: A => Boolean, isFlipped: Boolean): Stream[A] = {
+    // optimization: drop leading prefix of elems for which f returns false
+    // var rest = this dropWhile (!p(_)) - forget DRY principle - GC can't collect otherwise
+    var rest = this
+    while (!rest.isEmpty && p(rest.head) == isFlipped) 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, isFlipped)
+    else Stream.Empty
+  }
+
   /** Returns all the elements of this `Stream` that satisfy the predicate `p`
    * in a new `Stream` - i.e. it is still a lazy data structure. The order of
    * the elements is preserved
@@ -481,15 +491,7 @@ self =>
    * // produces
    * }}}
    */
-  override def filter(p: A => Boolean): Stream[A] = {
-    // optimization: drop leading prefix of elems for which f returns false
-    // 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 def filter(p: A => Boolean): Stream[A] = filterImpl(p, isFlipped = false) // This override is only left in 2.11 because of binary compatibility, see PR #3925
 
   override final def withFilter(p: A => Boolean): StreamWithFilter = new StreamWithFilter(p)
 
@@ -1187,8 +1189,8 @@ object Stream extends SeqFactory[Stream] {
     else cons(start, range(start + step, end, step))
   }
 
-  private[immutable] def filteredTail[A](stream: Stream[A], p: A => Boolean) = {
-    cons(stream.head, stream.tail filter p)
+  private[immutable] def filteredTail[A](stream: Stream[A], p: A => Boolean, isFlipped: Boolean) = {
+    cons(stream.head, stream.tail.filterImpl(p, isFlipped))
   }
 
   private[immutable] def collectedTail[A, B, That](head: B, stream: Stream[A], pf: PartialFunction[A, B], bf: CanBuildFrom[Stream[A], B, That]) = {
diff --git a/test/files/run/t4332.scala b/test/files/run/t4332.scala
index 5a67922911..1c7e7d73de 100644
--- a/test/files/run/t4332.scala
+++ b/test/files/run/t4332.scala
@@ -12,7 +12,7 @@ object Test extends DirectTest {
   }
 
   def isExempt(sym: Symbol) = {
-    val exempt = Set("view", "repr", "sliceWithKnownDelta", "sliceWithKnownBound", "transform")
+    val exempt = Set("view", "repr", "sliceWithKnownDelta", "sliceWithKnownBound", "transform", "filterImpl")
     (exempt contains sym.name.decoded)
   }
 
diff --git a/test/junit/scala/collection/StreamTest.scala b/test/junit/scala/collection/StreamTest.scala
new file mode 100644
index 0000000000..6dc1c79a48
--- /dev/null
+++ b/test/junit/scala/collection/StreamTest.scala
@@ -0,0 +1,18 @@
+package scala.collection.immutable
+
+import org.junit.runner.RunWith
+import org.junit.runners.JUnit4
+import org.junit.Test
+import org.junit.Assert._
+
+@RunWith(classOf[JUnit4])
+class StreamTest {
+
+  @Test
+  def t6727_and_t6440(): Unit = {
+    assertTrue(Stream.continually(()).filter(_ => true).take(2) == Seq((), ()))
+    assertTrue(Stream.continually(()).filterNot(_ => false).take(2) == Seq((), ()))
+    assertTrue(Stream(1,2,3,4,5).filter(_ < 4) == Seq(1,2,3))
+    assertTrue(Stream(1,2,3,4,5).filterNot(_ > 4) == Seq(1,2,3,4))
+  }
+}