Fix for view isEmpty.

Views have been inheriting the very inefficient isEmpty
from Traversable, and since isEmpty is not specifically
forwarded to the underlying collections, views miss out on all
the important optimizations in those collections which tend to
be implemented via method override.  Not to mention, they miss
out on correctness, because calling foreach has a habit of
forcing the first element of the view.

8 files changed, 36 insertions, 20 deletions

diff --git a/src/library/scala/collection/IterableLike.scala b/src/library/scala/collection/IterableLike.scala
index 2e9599058f..ac6d754f9e 100644
--- a/src/library/scala/collection/IterableLike.scala
+++ b/src/library/scala/collection/IterableLike.scala
@@ -171,7 +171,7 @@ self =>
    *          fewer elements than size.
    */
   def sliding(size: Int): Iterator[Repr] = sliding(size, 1)
-  
+
   /** Groups elements in fixed size blocks by passing a "sliding window"
    *  over them (as opposed to partitioning them, as is done in grouped.)
    *  @see [[scala.collection.Iterator]], method `sliding`
@@ -293,6 +293,7 @@ self =>
 
   override /*TraversableLike*/ def view = new IterableView[A, Repr] {
     protected lazy val underlying = self.repr
+    override def isEmpty = self.isEmpty
     override def iterator = self.iterator
   }
 
diff --git a/src/library/scala/collection/SeqLike.scala b/src/library/scala/collection/SeqLike.scala
index d7418de9c3..f6f08398d3 100644
--- a/src/library/scala/collection/SeqLike.scala
+++ b/src/library/scala/collection/SeqLike.scala
@@ -627,6 +627,7 @@ trait SeqLike[+A, +Repr] extends Any with IterableLike[A, Repr] with GenSeqLike[
 
   override def view = new SeqView[A, Repr] {
     protected lazy val underlying = self.repr
+    override def isEmpty = self.isEmpty
     override def iterator = self.iterator
     override def length = self.length
     override def apply(idx: Int) = self.apply(idx)
diff --git a/src/library/scala/collection/TraversableLike.scala b/src/library/scala/collection/TraversableLike.scala
index 641dd095da..0345f05355 100644
--- a/src/library/scala/collection/TraversableLike.scala
+++ b/src/library/scala/collection/TraversableLike.scala
@@ -86,7 +86,7 @@ trait TraversableLike[+A, +Repr] extends Any
   def repr: Repr = this.asInstanceOf[Repr]
 
   final def isTraversableAgain: Boolean = true
-  
+
   /** The underlying collection seen as an instance of `$Coll`.
    *  By default this is implemented as the current collection object itself,
    *  but this can be overridden.
@@ -174,7 +174,7 @@ trait TraversableLike[+A, +Repr] extends Any
    *
    *  @usecase def ++:[B](that: TraversableOnce[B]): $Coll[B]
    *    @inheritdoc
-   * 
+   *
    *    Example:
    *    {{{
    *      scala> val x = List(1)
@@ -655,6 +655,7 @@ trait TraversableLike[+A, +Repr] extends Any
   def view = new TraversableView[A, Repr] {
     protected lazy val underlying = self.repr
     override def foreach[U](f: A => U) = self foreach f
+    override def isEmpty = self.isEmpty
   }
 
   /** Creates a non-strict view of a slice of this $coll.
diff --git a/src/library/scala/collection/TraversableViewLike.scala b/src/library/scala/collection/TraversableViewLike.scala
index bf4f8205d6..7fbcf1374b 100644
--- a/src/library/scala/collection/TraversableViewLike.scala
+++ b/src/library/scala/collection/TraversableViewLike.scala
@@ -59,7 +59,7 @@ trait ViewMkString[+A] {
  *  $viewInfo
  *
  *  All views for traversable collections are defined by creating a new `foreach` method.
- *  
+ *
  *  @author Martin Odersky
  *  @version 2.8
  *  @since   2.8
@@ -162,7 +162,7 @@ trait TraversableViewLike[+A,
 //     if (b.isInstanceOf[NoBuilder[_]]) newFlatMapped(f).asInstanceOf[That]
 //    else super.flatMap[B, That](f)(bf)
   }
-  override def flatten[B](implicit asTraversable: A => /*<:<!!!*/ GenTraversableOnce[B]) = 
+  override def flatten[B](implicit asTraversable: A => /*<:<!!!*/ GenTraversableOnce[B]) =
     newFlatMapped(asTraversable)
   private[this] implicit def asThis(xs: Transformed[A]): This = xs.asInstanceOf[This]
 
@@ -193,6 +193,15 @@ trait TraversableViewLike[+A,
   override def span(p: A => Boolean): (This, This) = (newTakenWhile(p), newDroppedWhile(p))
   override def splitAt(n: Int): (This, This) = (newTaken(n), newDropped(n))
 
+  // Without this, isEmpty tests go back to the Traversable default, which
+  // involves starting a foreach, which can force the first element of the
+  // view. This is just a backstop - it's overridden at all the "def view"
+  // instantiation points in the collections where the Coll type is known.
+  override def isEmpty = underlying match {
+    case x: GenTraversableOnce[_] => x.isEmpty
+    case _                        => super.isEmpty
+  }
+
   override def scanLeft[B, That](z: B)(op: (B, A) => B)(implicit bf: CanBuildFrom[This, B, That]): That =
     newForced(thisSeq.scanLeft(z)(op)).asInstanceOf[That]
 
diff --git a/src/library/scala/collection/immutable/Stream.scala b/src/library/scala/collection/immutable/Stream.scala
index 9f5f98ddf4..1bf1e20694 100644
--- a/src/library/scala/collection/immutable/Stream.scala
+++ b/src/library/scala/collection/immutable/Stream.scala
@@ -916,6 +916,7 @@ self =>
 
   override def view = new StreamView[A, Stream[A]] {
     protected lazy val underlying = self.repr
+    override def isEmpty = self.isEmpty
     override def iterator = self.iterator
     override def length = self.length
     override def apply(idx: Int) = self.apply(idx)
diff --git a/src/library/scala/collection/mutable/IndexedSeqLike.scala b/src/library/scala/collection/mutable/IndexedSeqLike.scala
index 2ff7ac8272..5d4b4de7b2 100644
--- a/src/library/scala/collection/mutable/IndexedSeqLike.scala
+++ b/src/library/scala/collection/mutable/IndexedSeqLike.scala
@@ -53,6 +53,7 @@ trait IndexedSeqLike[A, +Repr] extends scala.collection.IndexedSeqLike[A, Repr]
    */
   override def view = new IndexedSeqView[A, Repr] {
     protected lazy val underlying = self.repr
+    override def isEmpty = self.isEmpty
     override def iterator = self.iterator
     override def length = self.length
     override def apply(idx: Int) = self.apply(idx)
diff --git a/src/library/scala/collection/parallel/ParIterableLike.scala b/src/library/scala/collection/parallel/ParIterableLike.scala
index 85758b29bc..26877a32b1 100644
--- a/src/library/scala/collection/parallel/ParIterableLike.scala
+++ b/src/library/scala/collection/parallel/ParIterableLike.scala
@@ -171,9 +171,9 @@ self: ParIterableLike[T, Repr, Sequential] =>
 
   /** The task support object which is responsible for scheduling and
    *  load-balancing tasks to processors.
-   *                                                                              
+   *
    *  @see [[scala.collection.parallel.TaskSupport]]
-   */     
+   */
   def tasksupport = {
     val ts = _tasksupport
     if (ts eq null) {
@@ -188,18 +188,18 @@ self: ParIterableLike[T, Repr, Sequential] =>
    *  A task support object can be changed in a parallel collection after it
    *  has been created, but only during a quiescent period, i.e. while there
    *  are no concurrent invocations to parallel collection methods.
-   *                                                                              
-   *  Here is a way to change the task support of a parallel collection:          
-   *                                                                              
-   *  {{{                                                                         
-   *  import scala.collection.parallel._                                          
-   *  val pc = mutable.ParArray(1, 2, 3)                                          
-   *  pc.tasksupport = new ForkJoinTaskSupport(                                   
-   *    new scala.concurrent.forkjoin.ForkJoinPool(2))                            
-   *  }}}                                                                         
+   *
+   *  Here is a way to change the task support of a parallel collection:
+   *
+   *  {{{
+   *  import scala.collection.parallel._
+   *  val pc = mutable.ParArray(1, 2, 3)
+   *  pc.tasksupport = new ForkJoinTaskSupport(
+   *    new scala.concurrent.forkjoin.ForkJoinPool(2))
+   *  }}}
    *
    *  @see [[scala.collection.parallel.TaskSupport]]
-   */     
+   */
   def tasksupport_=(ts: TaskSupport) = _tasksupport = ts
 
   def seq: Sequential
@@ -848,6 +848,7 @@ self: ParIterableLike[T, Repr, Sequential] =>
     override def seq = self.seq.view
     def splitter = self.splitter
     def size = splitter.remaining
+    override def isEmpty = size == 0
   }
 
   override def toArray[U >: T: ClassTag]: Array[U] = {
@@ -877,13 +878,13 @@ self: ParIterableLike[T, Repr, Sequential] =>
   override def toSet[U >: T]: immutable.ParSet[U] = toParCollection[U, immutable.ParSet[U]](() => immutable.ParSet.newCombiner[U])
 
   override def toMap[K, V](implicit ev: T <:< (K, V)): immutable.ParMap[K, V] = toParMap[K, V, immutable.ParMap[K, V]](() => immutable.ParMap.newCombiner[K, V])
-  
+
   override def toVector: Vector[T] = to[Vector]
 
   override def to[Col[_]](implicit cbf: CanBuildFrom[Nothing, T, Col[T @uncheckedVariance]]): Col[T @uncheckedVariance] = if (cbf().isCombiner) {
     toParCollection[T, Col[T]](() => cbf().asCombiner)
   } else seq.to(cbf)
-  
+
   /* tasks */
 
   protected trait StrictSplitterCheckTask[R, Tp] extends Task[R, Tp] {
diff --git a/src/library/scala/collection/parallel/ParSeqLike.scala b/src/library/scala/collection/parallel/ParSeqLike.scala
index be5ab03ba7..27e8eeb174 100644
--- a/src/library/scala/collection/parallel/ParSeqLike.scala
+++ b/src/library/scala/collection/parallel/ParSeqLike.scala
@@ -44,7 +44,7 @@ trait ParSeqLike[+T, +Repr <: ParSeq[T], +Sequential <: Seq[T] with SeqLike[T, S
 extends scala.collection.GenSeqLike[T, Repr]
    with ParIterableLike[T, Repr, Sequential] {
 self =>
-  
+
   type SuperParIterator = IterableSplitter[T]
 
   /** A more refined version of the iterator found in the `ParallelIterable` trait,
@@ -330,6 +330,7 @@ self =>
     def apply(idx: Int) = self(idx)
     override def seq = self.seq.view
     def splitter = self.splitter
+    override def isEmpty = size == 0
   }
 
   /* tasks */