Merge commit 'a170c99' into 2.12.x

29 files changed, 175 insertions, 79 deletions

diff --git a/src/library/scala/AnyVal.scala b/src/library/scala/AnyVal.scala
index fb3d213e19..e861860196 100644
--- a/src/library/scala/AnyVal.scala
+++ b/src/library/scala/AnyVal.scala
@@ -48,9 +48,7 @@ package scala
  *
  * It's important to note that user-defined value classes are limited, and in some circumstances,
  * still must allocate a value class instance at runtime. These limitations and circumstances are
- * explained in greater detail in the [[http://docs.scala-lang.org/overviews/core/value-classes.html Value Classes Guide]]
- * as well as in [[http://docs.scala-lang.org/sips/completed/value-classes.html SIP-15: Value Classes]],
- * the Scala Improvement Proposal.
+ * explained in greater detail in the [[http://docs.scala-lang.org/overviews/core/value-classes.html Value Classes and Universal Traits]].
  */
 abstract class AnyVal extends Any {
   def getClass(): Class[_ <: AnyVal] = null
diff --git a/src/library/scala/collection/IndexedSeqOptimized.scala b/src/library/scala/collection/IndexedSeqOptimized.scala
index a7e06b4d1a..a7e06b4d1a 100755..100644
--- a/src/library/scala/collection/IndexedSeqOptimized.scala
+++ b/src/library/scala/collection/IndexedSeqOptimized.scala
diff --git a/src/library/scala/collection/Iterator.scala b/src/library/scala/collection/Iterator.scala
index e2c271145d..ff10fb44d7 100644
--- a/src/library/scala/collection/Iterator.scala
+++ b/src/library/scala/collection/Iterator.scala
@@ -431,8 +431,16 @@ trait Iterator[+A] extends TraversableOnce[A] {
    */
   def flatMap[B](f: A => GenTraversableOnce[B]): Iterator[B] = new AbstractIterator[B] {
     private var cur: Iterator[B] = empty
-    def hasNext: Boolean =
-      cur.hasNext || self.hasNext && { cur = f(self.next()).toIterator; hasNext }
+    private def nextCur() { cur = f(self.next()).toIterator }
+    def hasNext: Boolean = {
+      // Equivalent to cur.hasNext || self.hasNext && { nextCur(); hasNext }
+      // but slightly shorter bytecode (better JVM inlining!)
+      while (!cur.hasNext) {
+        if (!self.hasNext) return false
+        nextCur()
+      }
+      true
+    }
     def next(): B = (if (hasNext) cur else empty).next()
   }
 
@@ -444,6 +452,7 @@ trait Iterator[+A] extends TraversableOnce[A] {
    *  @note    Reuse: $consumesAndProducesIterator
    */
   def filter(p: A => Boolean): Iterator[A] = new AbstractIterator[A] {
+    // TODO 2.12 - Make a full-fledged FilterImpl that will reverse sense of p
     private var hd: A = _
     private var hdDefined: Boolean = false
 
@@ -509,13 +518,27 @@ trait Iterator[+A] extends TraversableOnce[A] {
   *  @note     Reuse: $consumesAndProducesIterator
   */
   @migration("`collect` has changed. The previous behavior can be reproduced with `toSeq`.", "2.8.0")
-  def collect[B](pf: PartialFunction[A, B]): Iterator[B] = {
-    val self = buffered
-    new AbstractIterator[B] {
-      private def skip() = while (self.hasNext && !pf.isDefinedAt(self.head)) self.next()
-      def hasNext = { skip(); self.hasNext }
-      def next() = { skip(); pf(self.next()) }
+  def collect[B](pf: PartialFunction[A, B]): Iterator[B] = new AbstractIterator[B] {
+    // Manually buffer to avoid extra layer of wrapping with buffered
+    private[this] var hd: A = _
+    
+    // Little state machine to keep track of where we are
+    // Seek = 0; Found = 1; Empty = -1
+    // Not in vals because scalac won't make them static (@inline def only works with -optimize)
+    // BE REALLY CAREFUL TO KEEP COMMENTS AND NUMBERS IN SYNC!
+    private[this] var status = 0/*Seek*/
+    
+    def hasNext = {
+      while (status == 0/*Seek*/) {
+        if (self.hasNext) {
+          hd = self.next()
+          if (pf.isDefinedAt(hd)) status = 1/*Found*/
+        }
+        else status = -1/*Empty*/
+      }
+      status == 1/*Found*/
     }
+    def next() = if (hasNext) { status = 0/*Seek*/; pf(hd) } else Iterator.empty.next()
   }
 
   /** Produces a collection containing cumulative results of applying the
@@ -617,33 +640,105 @@ trait Iterator[+A] extends TraversableOnce[A] {
    *  @note    Reuse: $consumesOneAndProducesTwoIterators
    */
   def span(p: A => Boolean): (Iterator[A], Iterator[A]) = {
-    val self = buffered
-
-    // Must be a named class to avoid structural call to finish from trailing iterator
+    /*
+     * Giving a name to following iterator (as opposed to trailing) because
+     * anonymous class is represented as a structural type that trailing
+     * iterator is referring (the finish() method) and thus triggering
+     * handling of structural calls. It's not what's intended here.
+     */
     class Leading extends AbstractIterator[A] {
-      private val drained  = new mutable.Queue[A]
-      private var finished = false
-      def finish(): Unit = {
-        require(!finished)
-        finished = true
-        while (selfish) drained += self.next
+      var lookahead: mutable.Queue[A] = null
+      var hd: A = _
+      /* Status is kept with magic numbers
+       *   1 means next element is in hd and we're still reading into this iterator
+       *   0 means we're still reading but haven't found a next element
+       *   -1 means we are done reading into the iterator, so we must rely on lookahead
+       *   -2 means we are done but have saved hd for the other iterator to use as its first element
+       */
+      var status = 0
+      private def store(a: A) {
+        if (lookahead == null) lookahead = new mutable.Queue[A]
+        lookahead += a
+      }
+      def hasNext = {
+        if (status < 0) (lookahead ne null) && lookahead.nonEmpty
+        else if (status > 0) true
+        else {
+          if (self.hasNext) {
+            hd = self.next()
+            status = if (p(hd)) 1 else -2
+          }
+          else status = -1
+          status > 0
+        }
       }
-      private def selfish = self.hasNext && p(self.head)
-      def hasNext = if (finished) drained.nonEmpty else selfish
       def next() = {
-        if (finished) drained.dequeue()
-        else if (selfish) self.next()
+        if (hasNext) {
+          if (status == 1) { status = 0; hd }
+          else lookahead.dequeue()
+        }
         else empty.next()
       }
+      def finish(): Boolean = {
+        if (status == -1) false
+        else if (status == -2) {
+          status = -1
+          true
+        }
+        else {
+          if (status == 1) store(hd)
+          while (self.hasNext) {
+            val a = self.next()
+            if (p(a)) store(a)
+            else {
+              hd = a
+              status = -1
+              return true
+            }
+          }
+          false
+        }
+      }
     }
+    
     val leading = new Leading
+    
     val trailing = new AbstractIterator[A] {
-      private lazy val it = {
-        leading.finish()
-        self
+      private[this] var myLeading = leading
+      /* Status flags meanings:
+       *   -1 not yet accesssed
+       *   0 single element waiting in leading
+       *   1 defer to self
+       */
+      private[this] var status = -1
+      def hasNext = {
+        if (status > 0) self.hasNext
+        else {
+          if (status == 0) true
+          else if (myLeading.finish()) {
+            status = 0
+            true
+          }
+          else {
+            status = 1
+            myLeading = null
+            self.hasNext
+          }
+        }
+      }
+      def next() = {
+        if (hasNext) {
+          if (status > 0) self.next()
+          else {
+            status = 1
+            val ans = myLeading.hd
+            myLeading = null
+            ans
+          }
+        }
+        else Iterator.empty.next()
       }
-      def hasNext = it.hasNext
-      def next() = it.next()
+            
       override def toString = "unknown-if-empty iterator"
     }
 
@@ -657,18 +752,35 @@ trait Iterator[+A] extends TraversableOnce[A] {
    *  @return  an iterator consisting of the remaining elements
    *  @note    Reuse: $consumesAndProducesIterator
    */
-  def dropWhile(p: A => Boolean): Iterator[A] = {
-    val self = buffered
-    new AbstractIterator[A] {
-      var dropped = false
-      private def skip() =
-        if (!dropped) {
-          while (self.hasNext && p(self.head)) self.next()
-          dropped = true
+  def dropWhile(p: A => Boolean): Iterator[A] = new AbstractIterator[A] {
+    // Magic value: -1 = hasn't dropped, 0 = found first, 1 = defer to parent iterator
+    private[this] var status = -1
+    // Local buffering to avoid double-wrap with .buffered
+    private[this] var fst: A = _
+    def hasNext: Boolean =
+      if (status == 1) self.hasNext
+      else if (status == 0) true
+      else {
+        while (self.hasNext) {
+          val a = self.next()
+          if (!p(a)) {
+            fst = a
+            status = 0
+            return true
+          }
         }
-      def hasNext = { skip(); self.hasNext }
-      def next() = { skip(); self.next() }
-    }
+        status = 1
+        false
+      }
+    def next() = 
+      if (hasNext) {
+        if (status == 1) self.next()
+        else {
+          status = 1
+          fst
+        }
+      }
+      else Iterator.empty.next()
   }
 
   /** Creates an iterator formed from this iterator and another iterator
@@ -816,7 +928,7 @@ trait Iterator[+A] extends TraversableOnce[A] {
    *               is equal (as determined by `==`) to `elem`, `false` otherwise.
    *  @note        Reuse: $consumesIterator
    */
-  def contains(elem: Any): Boolean = exists(_ == elem)
+  def contains(elem: Any): Boolean = exists(_ == elem)    // Note--this seems faster than manual inlining!
 
   /** Finds the first value produced by the iterator satisfying a
    *  predicate, if any.
@@ -828,12 +940,11 @@ trait Iterator[+A] extends TraversableOnce[A] {
    *  @note    Reuse: $consumesIterator
    */
   def find(p: A => Boolean): Option[A] = {
-    var res: Option[A] = None
-    while (res.isEmpty && hasNext) {
-      val e = next()
-      if (p(e)) res = Some(e)
+    while (hasNext) {
+      val a = next()
+      if (p(a)) return Some(a)
     }
-    res
+    None
   }
 
   /** Returns the index of the first produced value satisfying a predicate, or -1.
@@ -863,15 +974,11 @@ trait Iterator[+A] extends TraversableOnce[A] {
       i += 1
     }
 
-    var found = false
-    while (!found && hasNext) {
-      if (p(next())) {
-        found = true
-      } else {
-        i += 1
-      }
+    while (hasNext) {
+      if (p(next())) return i
+      i += 1
     }
-    if (found) i else -1
+    -1
   }
 
   /** Returns the index of the first occurrence of the specified
@@ -903,15 +1010,11 @@ trait Iterator[+A] extends TraversableOnce[A] {
       i += 1
     }
 
-    var found = false
-    while (!found && hasNext) {
-      if (next() == elem) {
-        found = true
-      } else {
-        i += 1
-      }
+    while (hasNext) {
+      if (next() == elem) return i
+      i += 1
     }
-    if (found) i else -1
+    -1
   }
 
   /** Creates a buffered iterator from this iterator.
diff --git a/src/library/scala/collection/JavaConverters.scala b/src/library/scala/collection/JavaConverters.scala
index 875f6e1c02..875f6e1c02 100755..100644
--- a/src/library/scala/collection/JavaConverters.scala
+++ b/src/library/scala/collection/JavaConverters.scala
diff --git a/src/library/scala/collection/LinearSeqOptimized.scala b/src/library/scala/collection/LinearSeqOptimized.scala
index 571d58a3f3..571d58a3f3 100755..100644
--- a/src/library/scala/collection/LinearSeqOptimized.scala
+++ b/src/library/scala/collection/LinearSeqOptimized.scala
diff --git a/src/library/scala/collection/generic/FilterMonadic.scala b/src/library/scala/collection/generic/FilterMonadic.scala
index 8aefbdb926..8aefbdb926 100755..100644
--- a/src/library/scala/collection/generic/FilterMonadic.scala
+++ b/src/library/scala/collection/generic/FilterMonadic.scala
diff --git a/src/library/scala/collection/generic/HasNewBuilder.scala b/src/library/scala/collection/generic/HasNewBuilder.scala
index aa0ce6698d..aa0ce6698d 100755..100644
--- a/src/library/scala/collection/generic/HasNewBuilder.scala
+++ b/src/library/scala/collection/generic/HasNewBuilder.scala
diff --git a/src/library/scala/collection/immutable/DefaultMap.scala b/src/library/scala/collection/immutable/DefaultMap.scala
index e9b277b9c4..e9b277b9c4 100755..100644
--- a/src/library/scala/collection/immutable/DefaultMap.scala
+++ b/src/library/scala/collection/immutable/DefaultMap.scala
diff --git a/src/library/scala/collection/immutable/IntMap.scala b/src/library/scala/collection/immutable/IntMap.scala
index 8991d0b75a..cb6196e130 100644
--- a/src/library/scala/collection/immutable/IntMap.scala
+++ b/src/library/scala/collection/immutable/IntMap.scala
@@ -146,7 +146,7 @@ private[immutable] class IntMapKeyIterator[V](it: IntMap[V]) extends IntMapItera
 import IntMap._
 
 /** Specialised immutable map structure for integer keys, based on
- *  <a href="http://citeseer.ist.psu.edu/okasaki98fast.html">Fast Mergeable Integer Maps</a>
+ *  [[http://ittc.ku.edu/~andygill/papers/IntMap98.pdf Fast Mergeable Integer Maps]]
  *  by Okasaki and Gill. Essentially a trie based on binary digits of the integers.
  *
  *  '''Note:''' This class is as of 2.8 largely superseded by HashMap.
diff --git a/src/library/scala/collection/immutable/List.scala b/src/library/scala/collection/immutable/List.scala
index eb095dbbc2..66150c1a13 100644
--- a/src/library/scala/collection/immutable/List.scala
+++ b/src/library/scala/collection/immutable/List.scala
@@ -16,7 +16,7 @@ import scala.annotation.tailrec
 import java.io.{ObjectOutputStream, ObjectInputStream}
 
 /** A class for immutable linked lists representing ordered collections
- *  of elements of type.
+ *  of elements of type `A`.
  *
  *  This class comes with two implementing case classes `scala.Nil`
  *  and `scala.::` that implement the abstract members `isEmpty`,
diff --git a/src/library/scala/collection/immutable/RedBlackTree.scala b/src/library/scala/collection/immutable/RedBlackTree.scala
index 0dad106b29..7e8cfcc902 100644
--- a/src/library/scala/collection/immutable/RedBlackTree.scala
+++ b/src/library/scala/collection/immutable/RedBlackTree.scala
@@ -168,7 +168,8 @@ object RedBlackTree {
   }
 
   /* Based on Stefan Kahrs' Haskell version of Okasaki's Red&Black Trees
-   * http://www.cse.unsw.edu.au/~dons/data/RedBlackTree.html */
+   * Constructing Red-Black Trees, Ralf Hinze: http://www.cs.ox.ac.uk/ralf.hinze/publications/WAAAPL99b.ps.gz
+   * Red-Black Trees in a Functional Setting, Chris Okasaki: https://wiki.rice.edu/confluence/download/attachments/2761212/Okasaki-Red-Black.pdf */
   private[this] def del[A, B](tree: Tree[A, B], k: A)(implicit ordering: Ordering[A]): Tree[A, B] = if (tree eq null) null else {
     def balance(x: A, xv: B, tl: Tree[A, B], tr: Tree[A, B]) = if (isRedTree(tl)) {
       if (isRedTree(tr)) {
diff --git a/src/library/scala/collection/immutable/Vector.scala b/src/library/scala/collection/immutable/Vector.scala
index 46d5d0c69c..8bb581d44c 100644
--- a/src/library/scala/collection/immutable/Vector.scala
+++ b/src/library/scala/collection/immutable/Vector.scala
@@ -1156,8 +1156,6 @@ private[immutable] trait VectorPointer[T] {
         if (depth == 3) {
           display3 = new Array(32)
           display3((oldIndex >> 15) & 31) = display2
-          display2 = new Array(32)
-          display1 = new Array(32)
           depth +=1
         }
         display2 = display3((newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]]
@@ -1170,9 +1168,6 @@ private[immutable] trait VectorPointer[T] {
         if (depth == 4) {
           display4 = new Array(32)
           display4((oldIndex >> 20) & 31) = display3
-          display3 = new Array(32)
-          display2 = new Array(32)
-          display1 = new Array(32)
           depth +=1
         }
         display3 = display4((newIndex >> 20) & 31).asInstanceOf[Array[AnyRef]]
@@ -1187,13 +1182,9 @@ private[immutable] trait VectorPointer[T] {
         if (depth == 5) {
           display5 = new Array(32)
           display5((oldIndex >>  25) & 31) = display4
-          display4 = new Array(32)
-          display3 = new Array(32)
-          display2 = new Array(32)
-          display1 = new Array(32)
           depth +=1
         }
-        display4 = display5((newIndex >> 20) & 31).asInstanceOf[Array[AnyRef]]
+        display4 = display5((newIndex >> 25) & 31).asInstanceOf[Array[AnyRef]]
         if (display4 == null) display4 = new Array(32)
         display3 = display4((newIndex >> 20) & 31).asInstanceOf[Array[AnyRef]]
         if (display3 == null) display3 = new Array(32)
diff --git a/src/library/scala/collection/mutable/IndexedSeqOptimized.scala b/src/library/scala/collection/mutable/IndexedSeqOptimized.scala
index 09f0712862..09f0712862 100755..100644
--- a/src/library/scala/collection/mutable/IndexedSeqOptimized.scala
+++ b/src/library/scala/collection/mutable/IndexedSeqOptimized.scala
diff --git a/src/library/scala/collection/mutable/Queue.scala b/src/library/scala/collection/mutable/Queue.scala
index 03d387a535..ad60173b64 100644
--- a/src/library/scala/collection/mutable/Queue.scala
+++ b/src/library/scala/collection/mutable/Queue.scala
@@ -21,7 +21,7 @@ import generic._
  *  @author  Martin Odersky
  *  @version 2.8
  *  @since   1
- *  @see [[http://docs.scala-lang.org/overviews/collections/concrete-mutable-collection-classes.html#mutable_queues "Scala's Collection Library overview"]]
+ *  @see [[http://docs.scala-lang.org/overviews/collections/concrete-mutable-collection-classes.html#queues "Scala's Collection Library overview"]]
  *  section on `Queues` for more information.
  *
  *  @define Coll `mutable.Queue`
diff --git a/src/library/scala/collection/package.scala b/src/library/scala/collection/package.scala
index 6a2b6de75a..13fe7a79c4 100644
--- a/src/library/scala/collection/package.scala
+++ b/src/library/scala/collection/package.scala
@@ -69,6 +69,9 @@ package scala
  * characteristics which are described
  * in [[http://docs.scala-lang.org/overviews/collections/performance-characteristics.html the guide]].
  *
+ * The concrete parallel collections also have specific performance characteristics which are
+ * described in [[http://docs.scala-lang.org/overviews/parallel-collections/concrete-parallel-collections.html#performance-characteristics the parallel collections guide]]
+ *
  * === Converting between Java Collections ===
  *
  * The `JavaConversions` object provides implicit defs that will allow mostly seamless integration
diff --git a/src/library/scala/collection/readme-if-you-want-to-add-something.txt b/src/library/scala/collection/readme-if-you-want-to-add-something.txt
index 6700cb7b68..6700cb7b68 100755..100644
--- a/src/library/scala/collection/readme-if-you-want-to-add-something.txt
+++ b/src/library/scala/collection/readme-if-you-want-to-add-something.txt
diff --git a/src/library/scala/io/Codec.scala b/src/library/scala/io/Codec.scala
index 2a41e25b01..7cb7858b36 100644
--- a/src/library/scala/io/Codec.scala
+++ b/src/library/scala/io/Codec.scala
@@ -21,7 +21,7 @@ import scala.language.implicitConversions
 // XML: optional encoding parameter.
 //   <?xml version="1.0" encoding="ISO8859-1" ?>
 //
-// MacRoman vs. UTF-8: see http://jira.codehaus.org/browse/JRUBY-3576
+// MacRoman vs. UTF-8: see http://osdir.com/ml/lang-jruby-devel/2009-04/msg00071.html
 // -Dfile.encoding: see http://bugs.java.com/bugdatabase/view_bug.do?bug_id=4375816
 
 /** A class for character encoding/decoding preferences.
diff --git a/src/library/scala/reflect/NameTransformer.scala b/src/library/scala/reflect/NameTransformer.scala
index a8430548f5..a8430548f5 100755..100644
--- a/src/library/scala/reflect/NameTransformer.scala
+++ b/src/library/scala/reflect/NameTransformer.scala
diff --git a/src/library/scala/runtime/TraitSetter.java b/src/library/scala/runtime/TraitSetter.java
index d9907c0ac0..d9907c0ac0 100755..100644
--- a/src/library/scala/runtime/TraitSetter.java
+++ b/src/library/scala/runtime/TraitSetter.java
diff --git a/src/library/scala/runtime/VolatileBooleanRef.java b/src/library/scala/runtime/VolatileBooleanRef.java
index ef5b691118..ef5b691118 100755..100644
--- a/src/library/scala/runtime/VolatileBooleanRef.java
+++ b/src/library/scala/runtime/VolatileBooleanRef.java
diff --git a/src/library/scala/runtime/VolatileByteRef.java b/src/library/scala/runtime/VolatileByteRef.java
index d792b0a386..d792b0a386 100755..100644
--- a/src/library/scala/runtime/VolatileByteRef.java
+++ b/src/library/scala/runtime/VolatileByteRef.java
diff --git a/src/library/scala/runtime/VolatileCharRef.java b/src/library/scala/runtime/VolatileCharRef.java
index 555b171283..555b171283 100755..100644
--- a/src/library/scala/runtime/VolatileCharRef.java
+++ b/src/library/scala/runtime/VolatileCharRef.java
diff --git a/src/library/scala/runtime/VolatileDoubleRef.java b/src/library/scala/runtime/VolatileDoubleRef.java
index 1932055c6a..1932055c6a 100755..100644
--- a/src/library/scala/runtime/VolatileDoubleRef.java
+++ b/src/library/scala/runtime/VolatileDoubleRef.java
diff --git a/src/library/scala/runtime/VolatileFloatRef.java b/src/library/scala/runtime/VolatileFloatRef.java
index 3a81be1146..3a81be1146 100755..100644
--- a/src/library/scala/runtime/VolatileFloatRef.java
+++ b/src/library/scala/runtime/VolatileFloatRef.java
diff --git a/src/library/scala/runtime/VolatileIntRef.java b/src/library/scala/runtime/VolatileIntRef.java
index ae015bc8b1..ae015bc8b1 100755..100644
--- a/src/library/scala/runtime/VolatileIntRef.java
+++ b/src/library/scala/runtime/VolatileIntRef.java
diff --git a/src/library/scala/runtime/VolatileLongRef.java b/src/library/scala/runtime/VolatileLongRef.java
index e596f5aa69..e596f5aa69 100755..100644
--- a/src/library/scala/runtime/VolatileLongRef.java
+++ b/src/library/scala/runtime/VolatileLongRef.java
diff --git a/src/library/scala/runtime/VolatileObjectRef.java b/src/library/scala/runtime/VolatileObjectRef.java
index 6063501ffb..6063501ffb 100755..100644
--- a/src/library/scala/runtime/VolatileObjectRef.java
+++ b/src/library/scala/runtime/VolatileObjectRef.java
diff --git a/src/library/scala/runtime/VolatileShortRef.java b/src/library/scala/runtime/VolatileShortRef.java
index 0a2825941f..0a2825941f 100755..100644
--- a/src/library/scala/runtime/VolatileShortRef.java
+++ b/src/library/scala/runtime/VolatileShortRef.java
diff --git a/src/library/scala/sys/process/Process.scala b/src/library/scala/sys/process/Process.scala
index dcd06c89e9..c40838bb06 100644
--- a/src/library/scala/sys/process/Process.scala
+++ b/src/library/scala/sys/process/Process.scala
@@ -155,8 +155,8 @@ trait ProcessCreation {
     * import java.net.URL
     * import java.io.File
     *
-    * val spde = new URL("http://technically.us/spde/About")
-    * val dispatch = new URL("http://databinder.net/dispatch/About")
+    * val spde = new URL("http://technically.us/spde.html")
+    * val dispatch = new URL("http://dispatch.databinder.net/Dispatch.html")
     * val build = new File("project/build.properties")
     * cat(spde, dispatch, build) #| "grep -i scala" !
     * }}}