SI-7502 removing non-existent element from ListMap returns same map.

Current imperative version constructs a new ListMap regardless of
the fact the map doesn't contain the element. Replace it with the
tail-recursive variant that conserves. Also replace some usages with
the invariant now held.

1 files changed, 12 insertions, 27 deletions

diff --git a/src/library/scala/collection/immutable/ListMap.scala b/src/library/scala/collection/immutable/ListMap.scala
index 47593a07ab..49295d92dd 100644
--- a/src/library/scala/collection/immutable/ListMap.scala
+++ b/src/library/scala/collection/immutable/ListMap.scala
@@ -181,7 +181,7 @@ extends AbstractMap[A, B]
      *  it will be overridden by this function.
      */
     override def updated [B2 >: B1](k: A, v: B2): ListMap[A, B2] = {
-      val m = if (contains(k)) this - k else this
+      val m = this - k
       new m.Node[B2](k, v)
     }
 
@@ -189,32 +189,17 @@ extends AbstractMap[A, B]
      *  If the map does not contain a mapping for the given key, the
      *  method returns the same map.
      */
-    override def - (k: A): ListMap[A, B1] = {
-      // This definition used to result in stack overflows
-      // if (k == key)
-      //   next
-      // else {
-      //   val tail = next - k
-      //   if (tail eq next) this
-      //   else new tail.Node(key, value)
-      // }
-      // we use an imperative one instead (and use an auxiliary list to preserve order!):
-      var cur: ListMap[A, B1] = this
-      var lst: List[(A, B1)] = Nil
-      while (cur.nonEmpty) {
-        if (k != cur.key) lst ::= ((cur.key, cur.value))
-        cur = cur.tail
-      }
-      var acc = ListMap[A, B1]()
-      while (lst != Nil) {
-        val elem = lst.head
-        val stbl = acc
-        acc = new stbl.Node(elem._1, elem._2)
-        lst = lst.tail
-      }
-      acc
-    }
-
+    override def - (k: A): ListMap[A, B1] = remove0(k, this, Nil)
+
+    @tailrec private def remove0(k: A, cur: ListMap[A, B1], acc: List[ListMap[A, B1]]): ListMap[A, B1] =
+      if (cur.isEmpty)
+        acc.last
+      else if (k == cur.key)
+        (cur.tail /: acc) {
+          case (t, h) => val tt = t; new tt.Node(h.key, h.value) // SI-7459
+        }
+      else
+        remove0(k, cur.tail, cur::acc)
 
     override def tail: ListMap[A, B1] = ListMap.this
   }