unify mutable and immutable stacks behavior (#957)

7 files changed, 126 insertions, 35 deletions

diff --git a/src/compiler/scala/tools/nsc/backend/WorklistAlgorithm.scala b/src/compiler/scala/tools/nsc/backend/WorklistAlgorithm.scala
index 1b30e513eb..4405e7d665 100644
--- a/src/compiler/scala/tools/nsc/backend/WorklistAlgorithm.scala
+++ b/src/compiler/scala/tools/nsc/backend/WorklistAlgorithm.scala
@@ -8,7 +8,7 @@
 package scala.tools.nsc.backend
 
 import scala.tools.nsc.ast._
-import scala.collection.mutable.MutableList
+import scala.collection.mutable.Stack
 
 /**
  * Simple implementation of a worklist algorithm. A processing
@@ -26,7 +26,7 @@ import scala.collection.mutable.MutableList
  */
 trait WorklistAlgorithm {
   type Elem
-  type WList <: MutableList[Elem]
+  type WList = Stack[Elem]
 
   val worklist: WList
 
diff --git a/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala b/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala
index 5a5b3ba36f..b619ff949e 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala
@@ -27,7 +27,6 @@ trait Linearizers { self: ICodes =>
    */
   class NormalLinearizer extends Linearizer with WorklistAlgorithm {
     type Elem = BasicBlock;
-    type WList = Stack[Elem];
 
     val worklist: WList = new Stack();
 
diff --git a/src/library/scala/collection/immutable/Stack.scala b/src/library/scala/collection/immutable/Stack.scala
index dfcb3823df..1c2d2f8236 100644
--- a/src/library/scala/collection/immutable/Stack.scala
+++ b/src/library/scala/collection/immutable/Stack.scala
@@ -57,6 +57,14 @@ class Stack[+A] extends Seq[A] {
    */
   def push[B >: A](elem: B): Stack[B] = new Node(elem)
 
+  /** Push a sequence of elements onto the stack. The last element
+   *  of the sequence will be on top of the new stack.
+   *
+   *  @param   elems      the element sequence.
+   *  @return the stack with the new elements on top.
+   */
+  def push[B >: A](elems: B*): Stack[B] = this + elems
+
   /** Push all elements provided by the given iterable object onto
    *  the stack. The last element returned by the iterable object
    *  will be on top of the new stack.
@@ -77,15 +85,28 @@ class Stack[+A] extends Seq[A] {
    *  @return the stack with the new elements on top.
    */
   def push[B >: A](elems: Iterable[B]): Stack[B] =
+    this ++ elems
+
+  /** Push all elements provided by the given iterator object onto
+   *  the stack. The last element returned by the iterable object
+   *  will be on top of the new stack.
+   *
+   *  @param   elems      the iterator object.
+   *  @return the stack with the new elements on top.
+   *  @deprecated
+   */
+  def ++[B >: A](elems: Iterator[B]): Stack[B] =
     elems.foldLeft(this: Stack[B]){ (stack, elem) => stack + elem }
 
-  /** Push a sequence of elements onto the stack. The last element
-   *  of the sequence will be on top of the new stack.
+  /** Push all elements provided by the given iterable object onto
+   *  the stack. The last element returned by the iterable object
+   *  will be on top of the new stack.
    *
-   *  @param   elems      the element sequence.
+   *  @param   elems      the iterable object.
    *  @return the stack with the new elements on top.
    */
-  def push[B >: A](elems: B*): Stack[B] = this + elems
+  override def ++[B >: A](elems: Iterable[B]): Stack[B] =
+    this ++ elems.elements
 
   /** Returns the top element of the stack. An error is signaled if
    *  there is no element on the stack.
@@ -100,13 +121,17 @@ class Stack[+A] extends Seq[A] {
    */
   def pop: Stack[A] = throw new NoSuchElementException("no element on stack")
 
-  /** Returns the n-th element of this stack. The top element has index
-   *  0, elements below are indexed with increasing numbers.
+  /** Returns the n-th element of this stack. The bottom element has index
+   *  0, elements above are indexed with increasing numbers.
    *
    *  @param   n      the index number.
    *  @return the n-th element on the stack.
    */
-  def apply(n: Int): A = throw new NoSuchElementException("no element on stack")
+  def apply(n: Int): A = reverse.reverseApply(n)
+
+  private def reverseApply(n: Int): A =
+    if (n > 0) pop.reverseApply(n - 1)
+    else top
 
   /** Returns an iterator over all elements on the stack. The iterator
    *  issues elements in the reversed order they were inserted into the
@@ -114,7 +139,9 @@ class Stack[+A] extends Seq[A] {
    *
    *  @return an iterator over all stack elements.
    */
-  override def elements: Iterator[A] = new Iterator[A] {
+  override def elements: Iterator[A] = reverse.reverseElements
+
+  private def reverseElements: Iterator[A] = new Iterator[A] {
     var that: Stack[A] = Stack.this;
     def hasNext = !that.isEmpty;
     def next =
@@ -122,6 +149,19 @@ class Stack[+A] extends Seq[A] {
       else { val res = that.top; that = that.pop; res }
   }
 
+  /** A stack consisting of all elements of this stack in reverse order.
+   */
+  override def reverse: Stack[A] = {
+    // copy-paste from List.reverse
+    var result: Stack[A] = Stack.Empty
+    var these = this
+    while (!these.isEmpty) {
+      result = result push List(these.top) // see #978
+      these = these.pop
+    }
+    result
+  }
+
   /** Compares this stack with the given object.
    *
    *  @return true, iff the two stacks are equal; i.e. they contain the
@@ -150,7 +190,6 @@ class Stack[+A] extends Seq[A] {
     override def length: Int = Stack.this.length + 1
     override def top: B = elem
     override def pop: Stack[B] = Stack.this
-    override def apply(n: Int): B = if (n > 0) Stack.this(n - 1) else elem
     override def hashCode(): Int = elem.hashCode() + Stack.this.hashCode()
   }
 
diff --git a/src/library/scala/collection/mutable/Stack.scala b/src/library/scala/collection/mutable/Stack.scala
index 8aa2f27115..b61a3659f8 100644
--- a/src/library/scala/collection/mutable/Stack.scala
+++ b/src/library/scala/collection/mutable/Stack.scala
@@ -19,19 +19,26 @@ package scala.collection.mutable
  *  @version 1.1, 03/05/2004
  */
 @serializable @cloneable
-class Stack[A] extends MutableList[A] with CloneableCollection {
+class Stack[A] extends Seq[A] with CloneableCollection {
+  private var stack: immutable.Stack[A] = immutable.Stack.Empty
 
   /** Checks if the stack is empty.
    *
    *  @return true, iff there is no element on the stack
    */
-  override def isEmpty: Boolean = (first0 eq null)
+  override def isEmpty: Boolean = stack.isEmpty
+
+  override def length = stack.length
+
+  override def apply(index: Int) = stack(index)
 
   /** Pushes a single element on top of the stack.
    *
    *  @param  elem        the element to push onto the stack
    */
-  def +=(elem: A): Unit = prependElem(elem)
+  def +=(elem: A) {
+    this push elem
+  }
 
   /** Pushes all elements provided by an <code>Iterable</code> object
    *  on top of the stack. The elements are pushed in the order they
@@ -39,7 +46,7 @@ class Stack[A] extends MutableList[A] with CloneableCollection {
    *
    *  @param  iter        an iterable object
    */
-  def ++=(iter: Iterable[A]): Unit = this ++= iter.elements
+  def ++=(iter: Iterable[A]): Unit = stack = stack ++ iter
 
   /** Pushes all elements provided by an iterator
    *  on top of the stack. The elements are pushed in the order they
@@ -47,7 +54,7 @@ class Stack[A] extends MutableList[A] with CloneableCollection {
    *
    *  @param  iter        an iterator
    */
-  def ++=(it: Iterator[A]): Unit = it foreach { e => prependElem(e) }
+  def ++=(it: Iterator[A]): Unit = stack = stack ++ it
 
   /** Pushes a sequence of elements on top of the stack. The first element
    *  is pushed first, etc.
@@ -64,28 +71,24 @@ class Stack[A] extends MutableList[A] with CloneableCollection {
    *  @return the top element
    */
   def top: A =
-    if (first0 eq null) throw new NoSuchElementException("stack empty")
-    else first0.elem
+    stack.top
 
   /** Removes the top element from the stack.
    *
    *  @throws Predef.NoSuchElementException
    *  @return the top element
    */
-  def pop(): A =
-    if (first0 ne null) {
-      val res = first0.elem
-      first0 = first0.next
-      len = len - 1;
-      res
-    } else
-      throw new NoSuchElementException("stack empty")
+  def pop(): A = {
+    val res = stack.top
+    stack = stack.pop
+    res
+  }
 
   /**
    * Removes all elements from the stack. After this operation completed,
    * the stack will be empty.
    */
-  def clear(): Unit = reset
+  def clear(): Unit = stack = immutable.Stack.Empty
 
   /** Returns an iterator over all elements on the stack. This iterator
    *  is stable with respect to state changes in the stack object; i.e.
@@ -95,13 +98,13 @@ class Stack[A] extends MutableList[A] with CloneableCollection {
    *
    *  @return an iterator over all stack elements.
    */
-  override def elements: Iterator[A] = toList.elements
+  override def elements: Iterator[A] = stack.elements
 
   /** Creates a list of all stack elements in FIFO order.
    *
    *  @return the created list.
    */
-  override def toList: List[A] = super[MutableList].toList.reverse
+  override def toList: List[A] = stack.toList
 
   /** Checks if two stacks are structurally identical.
    *
@@ -109,9 +112,7 @@ class Stack[A] extends MutableList[A] with CloneableCollection {
    */
   override def equals(obj: Any): Boolean = obj match {
     case that: Stack[_] =>
-      (this.elements zip that.elements) forall {
-        case (thiselem, thatelem) => thiselem == thatelem
-      }
+      this.stack == that.stack
     case _ =>
       false
   }
diff --git a/test/files/jvm/serialization.check b/test/files/jvm/serialization.check
index 490be43d8a..f001f54c70 100755
--- a/test/files/jvm/serialization.check
+++ b/test/files/jvm/serialization.check
@@ -44,8 +44,8 @@ x = Queue(a,b,c)
 y = Queue(a,b,c)
 x equals y: true - y equals x: true
 
-x = Stack(c, b, a)
-y = Stack(c, b, a)
+x = Stack(a, b, c)
+y = Stack(a, b, c)
 x equals y: true - y equals x: true
 
 x = Map(42 -> FortyTwo)
diff --git a/test/files/run/collection-stacks.check b/test/files/run/collection-stacks.check
new file mode 100644
index 0000000000..fcb39c460c
--- /dev/null
+++ b/test/files/run/collection-stacks.check
@@ -0,0 +1,14 @@
+1-2-3: true
+1-2-3: true
+apply
+1: true
+1: true
+3: true
+3: true
+top
+3: true
+3: true
+pop
+1-2: true
+3: true
+1-2: true
diff --git a/test/files/run/collection-stacks.scala b/test/files/run/collection-stacks.scala
new file mode 100644
index 0000000000..ec557cb91d
--- /dev/null
+++ b/test/files/run/collection-stacks.scala
@@ -0,0 +1,38 @@
+import scala.collection._
+
+object Test extends Application {
+  def mutableStack[T](xs: T*): mutable.Stack[T] = {
+    val s = new mutable.Stack[T]
+    s.push(xs: _*)
+    s
+  }
+
+  def immutableStack[T](xs: T*): immutable.Stack[T] = {
+    immutable.Stack.Empty push xs
+  }
+
+  def check[T](expected: T, got: T) {
+    println(got + ": " + (expected == got))
+  }
+
+  // check #957
+  check("1-2-3", immutableStack(1, 2, 3).elements.mkString("-"))
+  check("1-2-3", mutableStack(1, 2, 3).elements.mkString("-"))
+
+  println("apply")
+  check(1, immutableStack(1, 2, 3).apply(0))
+  check(1, mutableStack(1, 2, 3).apply(0))
+  check(3, immutableStack(1, 2, 3).apply(2))
+  check(3, mutableStack(1, 2, 3).apply(2))
+
+  println("top")
+  check(3, immutableStack(1, 2, 3).top)
+  check(3, mutableStack(1, 2, 3).top)
+
+  println("pop")
+  check("1-2", immutableStack(1, 2, 3).pop.mkString("-"))
+  check(3, mutableStack(1, 2, 3).pop())
+  check("1-2", { val s = mutableStack(1, 2, 3); s.pop(); s.toList.mkString("-") })
+}
+
+// vim: set ts=2 sw=2 et: