Revert "Optimised implementation of List.filter/filterNot"

This reverts commit eb5c51383a63c5c3420e53ef021607ff5fd20296.

5 files changed, 5 insertions, 128 deletions

diff --git a/bincompat-forward.whitelist.conf b/bincompat-forward.whitelist.conf
index 1db1e2f408..023e3bddac 100644
--- a/bincompat-forward.whitelist.conf
+++ b/bincompat-forward.whitelist.conf
@@ -924,23 +924,6 @@ filter {
     {
         matchName="scala.collection.mutable.ArrayOps#ofFloat.emptyImpl"
         problemName=DirectMissingMethodProblem
-    },
-    // introduce FilteredTraversableInternal
-    {
-        matchName="scala.collection.immutable.Nil$"
-        problemName=MissingTypesProblem
-    },
-    {
-        matchName="scala.collection.immutable.FilteredTraversableInternal"
-        problemName=MissingClassProblem
-    },
-    {
-        matchName="scala.collection.immutable.List"
-        problemName=MissingTypesProblem
-    },
-    {
-        matchName="scala.collection.immutable.$colon$colon"
-        problemName=MissingTypesProblem
     }
   ]
 }
diff --git a/src/library/scala/collection/immutable/FilteredTraversableInternal.scala b/src/library/scala/collection/immutable/FilteredTraversableInternal.scala
deleted file mode 100644
index 35585b7826..0000000000
--- a/src/library/scala/collection/immutable/FilteredTraversableInternal.scala
+++ /dev/null
@@ -1,104 +0,0 @@
-/*                     __                                               *\
-**     ________ ___   / /  ___     Scala API                            **
-**    / __/ __// _ | / /  / _ |    (c) 2003-2013, LAMP/EPFL             **
-**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
-** /____/\___/_/ |_/____/_/ | |                                         **
-**                          |/                                          **
-\*                                                                      */
-
-package scala
-package collection
-package immutable
-
-import scala.annotation.tailrec
-
-/**
-  * Optimised filter functions for List
-  * n.b. this is an internal class to help maintain compatibility and should not be used directly.
-  */
-private[immutable] trait FilteredTraversableInternal[+A, +Repr <: AnyRef with TraversableLike[A, Repr]] extends TraversableLike[A, Repr] {
-
-  // Optimized for List
-
-  override def filter(p: A => Boolean): Self = filterImpl(p, isFlipped = false)
-
-  override def filterNot(p: A => Boolean): Self = filterImpl(p, isFlipped = true)
-
-  private[this] def filterImpl(p: A => Boolean, isFlipped: Boolean): Self = {
-
-    // everything seen so far so far is not included
-    @tailrec def noneIn(l: Repr): Repr = {
-      if (l.isEmpty)
-        Nil.asInstanceOf[Repr]
-      else {
-        val h = l.head
-        val t = l.tail
-        if (p(h) != isFlipped)
-          allIn(l, t)
-        else
-          noneIn(t)
-      }
-    }
-
-    // everything from 'start' is included, if everything from this point is in we can return the origin
-    // start otherwise if we discover an element that is out we must create a new partial list.
-    @tailrec def allIn(start: Repr, remaining: Repr): Repr = {
-      if (remaining.isEmpty)
-        start
-      else {
-        val x = remaining.head
-        if (p(x) != isFlipped)
-          allIn(start, remaining.tail)
-        else
-          partialFill(start, remaining)
-      }
-    }
-
-    // we have seen elements that should be included then one that should be excluded, start building
-    def partialFill(origStart: Repr, firstMiss: Repr): Repr = {
-      val newHead = new ::(origStart.head, Nil)
-      var toProcess = origStart.tail
-      var currentLast = newHead
-
-      // we know that all elements are :: until at least firstMiss.tail
-      while (!(toProcess eq firstMiss)) {
-        val newElem = new ::(toProcess.head, Nil)
-        currentLast.tl = newElem
-        currentLast = newElem
-        toProcess = toProcess.tail
-      }
-
-      // at this point newHead points to a list which is a duplicate of all the 'in' elements up to the first miss.
-      // currentLast is the last element in that list.
-
-      // now we are going to try and share as much of the tail as we can, only moving elements across when we have to.
-      var next = firstMiss.tail
-      var nextToCopy = next // the next element we would need to copy to our list if we cant share.
-      while (!next.isEmpty) {
-        // generally recommended is next.isNonEmpty but this incurs an extra method call.
-        val head: A = next.head
-        if (p(head) != isFlipped) {
-          next = next.tail
-        } else {
-          // its not a match - do we have outstanding elements?
-          while (!(nextToCopy eq next)) {
-            val newElem = new ::(nextToCopy.head, Nil)
-            currentLast.tl = newElem
-            currentLast = newElem
-            nextToCopy = nextToCopy.tail
-          }
-          nextToCopy = next.tail
-          next = next.tail
-        }
-      }
-
-      // we have remaining elements - they are unchanged attach them to the end
-      if (!nextToCopy.isEmpty)
-        currentLast.tl = nextToCopy.asInstanceOf[List[A]]
-
-      newHead.asInstanceOf[Repr]
-    }
-
-    noneIn(repr)
-  }
-}
\ No newline at end of file
diff --git a/src/library/scala/collection/immutable/List.scala b/src/library/scala/collection/immutable/List.scala
index e878f49c32..8e8bf953f3 100644
--- a/src/library/scala/collection/immutable/List.scala
+++ b/src/library/scala/collection/immutable/List.scala
@@ -86,7 +86,6 @@ sealed abstract class List[+A] extends AbstractSeq[A]
                                   with Product
                                   with GenericTraversableTemplate[A, List]
                                   with LinearSeqOptimized[A, List[A]]
-                                  with FilteredTraversableInternal[A, List[A]]
                                   with Serializable {
   override def companion: GenericCompanion[List] = List
 
@@ -417,7 +416,6 @@ sealed abstract class List[+A] extends AbstractSeq[A]
   // Create a proxy for Java serialization that allows us to avoid mutation
   // during de-serialization.  This is the Serialization Proxy Pattern.
   protected final def writeReplace(): AnyRef = new List.SerializationProxy(this)
-
 }
 
 /** The empty list.
diff --git a/src/reflect/scala/reflect/runtime/JavaUniverseForce.scala b/src/reflect/scala/reflect/runtime/JavaUniverseForce.scala
index f72b027a2e..45dd550e3e 100644
--- a/src/reflect/scala/reflect/runtime/JavaUniverseForce.scala
+++ b/src/reflect/scala/reflect/runtime/JavaUniverseForce.scala
@@ -442,8 +442,8 @@ trait JavaUniverseForce { self: runtime.JavaUniverse  =>
     definitions.DoubleTpe
     definitions.BooleanTpe
     definitions.ScalaNumericValueClasses
-    definitions.ScalaValueClasses
     definitions.ScalaValueClassesNoUnit
+    definitions.ScalaValueClasses
 
     uncurry.VarargsSymbolAttachment
     uncurry.DesugaredParameterType
diff --git a/test/files/run/repl-colon-type.check b/test/files/run/repl-colon-type.check
index ca8bd0648d..21fbe34d96 100644
--- a/test/files/run/repl-colon-type.check
+++ b/test/files/run/repl-colon-type.check
@@ -75,7 +75,7 @@ TypeRef(
     )
     TypeRef(
       TypeSymbol(
-        sealed abstract class List[+A] extends AbstractSeq[A] with LinearSeq[A] with Product with GenericTraversableTemplate[A,List] with LinearSeqOptimized[A,List[A]] with FilteredTraversableInternal[A,List[A]] with Serializable
+        sealed abstract class List[+A] extends AbstractSeq[A] with LinearSeq[A] with Product with GenericTraversableTemplate[A,List] with LinearSeqOptimized[A,List[A]] with Serializable
 
       )
       args = List(
@@ -142,7 +142,7 @@ TypeRef(
       args = List(
         TypeRef(
           TypeSymbol(
-            sealed abstract class List[+A] extends AbstractSeq[A] with LinearSeq[A] with Product with GenericTraversableTemplate[A,List] with LinearSeqOptimized[A,List[A]] with FilteredTraversableInternal[A,List[A]] with Serializable
+            sealed abstract class List[+A] extends AbstractSeq[A] with LinearSeq[A] with Product with GenericTraversableTemplate[A,List] with LinearSeqOptimized[A,List[A]] with Serializable
 
           )
           args = List(
@@ -175,7 +175,7 @@ PolyType(
           args = List(
             TypeRef(
               TypeSymbol(
-                sealed abstract class List[+A] extends AbstractSeq[A] with LinearSeq[A] with Product with GenericTraversableTemplate[A,List] with LinearSeqOptimized[A,List[A]] with FilteredTraversableInternal[A,List[A]] with Serializable
+                sealed abstract class List[+A] extends AbstractSeq[A] with LinearSeq[A] with Product with GenericTraversableTemplate[A,List] with LinearSeqOptimized[A,List[A]] with Serializable
 
               )
               args = List(TypeParamTypeRef(TypeParam(T <: AnyVal)))
@@ -198,7 +198,7 @@ PolyType(
     params = List(TermSymbol(x: T), TermSymbol(y: List[U]))
     resultType = TypeRef(
       TypeSymbol(
-        sealed abstract class List[+A] extends AbstractSeq[A] with LinearSeq[A] with Product with GenericTraversableTemplate[A,List] with LinearSeqOptimized[A,List[A]] with FilteredTraversableInternal[A,List[A]] with Serializable
+        sealed abstract class List[+A] extends AbstractSeq[A] with LinearSeq[A] with Product with GenericTraversableTemplate[A,List] with LinearSeqOptimized[A,List[A]] with Serializable
 
       )
       args = List(TypeParamTypeRef(TypeParam(U >: T)))