SI-7445 ListMap.tail is returning wrong result

Reverted the commit that introduced the bug, and modified HashMap to no
longer assume that tail is O(1).

Review by @Ichoran, @soc

4 files changed, 25 insertions, 24 deletions

diff --git a/src/library/scala/collection/immutable/HashMap.scala b/src/library/scala/collection/immutable/HashMap.scala
index e7d87dd3fe..8a24f721d7 100644
--- a/src/library/scala/collection/immutable/HashMap.scala
+++ b/src/library/scala/collection/immutable/HashMap.scala
@@ -247,15 +247,17 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int {
     override def removed0(key: A, hash: Int, level: Int): HashMap[A, B] =
       if (hash == this.hash) {
         val kvs1 = kvs - key
-        if (kvs1 eq kvs)
-          this
-        else if (kvs1.isEmpty)
-          HashMap.empty[A,B]
-        else if(kvs1.tail.isEmpty) {
-          val kv = kvs1.head
-          new HashMap1[A,B](kv._1,hash,kv._2,kv)
-        } else
-          new HashMapCollision1(hash, kvs1)
+        kvs1.size match {
+          case 0 =>
+            HashMap.empty[A,B]
+          case 1 =>
+            val kv = kvs1.head
+            new HashMap1(kv._1,hash,kv._2,kv)
+          case x if x == kvs.size =>
+            this
+          case _ =>
+            new HashMapCollision1(hash, kvs1)
+        }
       } else this
 
     override protected def filter0(p: ((A, B)) => Boolean, negate: Boolean, level: Int, buffer: Array[HashMap[A, B @uV]], offset0: Int): HashMap[A, B] = {
diff --git a/src/library/scala/collection/immutable/ListMap.scala b/src/library/scala/collection/immutable/ListMap.scala
index b2a1b1ce29..7c40e84280 100644
--- a/src/library/scala/collection/immutable/ListMap.scala
+++ b/src/library/scala/collection/immutable/ListMap.scala
@@ -123,12 +123,12 @@ extends AbstractMap[A, B]
       def hasNext = !self.isEmpty
       def next(): (A,B) =
         if (!hasNext) throw new NoSuchElementException("next on empty iterator")
-        else { val res = (self.key, self.value); self = self.tail; res }
+        else { val res = (self.key, self.value); self = self.next; res }
     }.toList.reverseIterator
 
   protected def key: A = throw new NoSuchElementException("empty map")
   protected def value: B = throw new NoSuchElementException("empty map")
-  override def tail: ListMap[A, B] = throw new NoSuchElementException("empty map")
+  protected def next: ListMap[A, B] = throw new NoSuchElementException("empty map")
 
   /** This class represents an entry in the `ListMap`.
    */
@@ -142,7 +142,7 @@ extends AbstractMap[A, B]
     override def size: Int = size0(this, 0)
 
     // to allow tail recursion and prevent stack overflows
-    @tailrec private def size0(cur: ListMap[A, B1], acc: Int): Int = if (cur.isEmpty) acc else size0(cur.tail, acc + 1)
+    @tailrec private def size0(cur: ListMap[A, B1], acc: Int): Int = if (cur.isEmpty) acc else size0(cur.next, acc + 1)
 
     /** Is this an empty map?
      *
@@ -163,7 +163,7 @@ extends AbstractMap[A, B]
     @tailrec private def apply0(cur: ListMap[A, B1], k: A): B1 =
       if (cur.isEmpty) throw new NoSuchElementException("key not found: "+k)
       else if (k == cur.key) cur.value
-      else apply0(cur.tail, k)
+      else apply0(cur.next, k)
 
     /** Checks if this map maps `key` to a value and return the
      *  value if it exists.
@@ -175,7 +175,7 @@ extends AbstractMap[A, B]
 
     @tailrec private def get0(cur: ListMap[A, B1], k: A): Option[B1] =
       if (k == cur.key) Some(cur.value)
-      else if (cur.tail.nonEmpty) get0(cur.tail, k) else None
+      else if (cur.next.nonEmpty) get0(cur.next, k) else None
 
     /** This method allows one to create a new map with an additional mapping
      *  from `key` to `value`. If the map contains already a mapping for `key`,
@@ -196,12 +196,12 @@ extends AbstractMap[A, B]
       if (cur.isEmpty)
         acc.last
       else if (k == cur.key)
-        (cur.tail /: acc) {
+        (cur.next /: acc) {
           case (t, h) => val tt = t; new tt.Node(h.key, h.value) // SI-7459
         }
       else
-        remove0(k, cur.tail, cur::acc)
+        remove0(k, cur.next, cur::acc)
 
-    override def tail: ListMap[A, B1] = ListMap.this
+    override protected def next: ListMap[A, B1] = ListMap.this
   }
 }
diff --git a/test/files/run/t6261.scala b/test/files/run/t6261.scala
index b4463256c9..bf6d640de3 100644
--- a/test/files/run/t6261.scala
+++ b/test/files/run/t6261.scala
@@ -2,12 +2,6 @@ import scala.collection.immutable._
 
 object Test extends App {
 
-  def test0() {
-    val m=ListMap(1->2,3->4)
-    if(m.tail ne m.tail)
-      println("ListMap.tail uses a builder, so it is not O(1)")
-  }
-
   def test1() {
     // test that a HashTrieMap with one leaf element is not created!
     val x = HashMap.empty + (1->1) + (2->2)
@@ -92,7 +86,6 @@ object Test extends App {
     // StructureTests.printStructure(z)
     require(z.size == 2 && z.contains(a._1) && z.contains(c._1))
   }
-  test0()
   test1()
   test2()
   test3()
diff --git a/test/files/run/t7445.scala b/test/files/run/t7445.scala
new file mode 100644
index 0000000000..e4ffeb8e1a
--- /dev/null
+++ b/test/files/run/t7445.scala
@@ -0,0 +1,6 @@
+import scala.collection.immutable.ListMap
+
+object Test extends App {
+	val a = ListMap(1 -> 1, 2 -> 2, 3 -> 3, 4 -> 4, 5 -> 5);
+	require(a.tail == ListMap(2 -> 2, 3 -> 3, 4 -> 4, 5 -> 5));
+}