From 898fa00a76286786427b093f0161ea0d3d3bae29 Mon Sep 17 00:00:00 2001
From: Jason Zaugg <jzaugg@gmail.com>
Date: Sun, 19 Feb 2017 14:47:02 +1000
Subject: SI-10187 Support mutation of mutable.HashMap in getOrElseUpdate

Scala 2.12.1 included optimizations to `HashMape.getOrElseUpdate`
to avoid recomputing the index in the hash table when adding an
the element.

However, this index could be stale if the callback added elements
to the map and triggered a resize.

This commit checks that the table is unchanged before reusing
the index, restoring the 2.12.0 behaviour.
---
 src/library/scala/collection/mutable/HashMap.scala | 12 +++++--
 .../scala/collection/mutable/HashMapTest.scala     | 38 ++++++++++++++++++++++
 2 files changed, 48 insertions(+), 2 deletions(-)
 create mode 100644 test/junit/scala/collection/mutable/HashMapTest.scala

diff --git a/src/library/scala/collection/mutable/HashMap.scala b/src/library/scala/collection/mutable/HashMap.scala
index 11ff1f0893..de61ebb796 100644
--- a/src/library/scala/collection/mutable/HashMap.scala
+++ b/src/library/scala/collection/mutable/HashMap.scala
@@ -73,10 +73,18 @@ extends AbstractMap[A, B]
   }
 
   override def getOrElseUpdate(key: A, defaultValue: => B): B = {
-    val i = index(elemHashCode(key))
+    val hash = elemHashCode(key)
+    val i = index(hash)
     val entry = findEntry(key, i)
     if (entry != null) entry.value
-    else addEntry(createNewEntry(key, defaultValue), i)
+    else {
+      val table0 = table
+      val default = defaultValue
+      // Avoid recomputing index if the `defaultValue()` hasn't triggered
+      // a table resize.
+      val newEntryIndex = if (table0 eq table) i else index(hash)
+      addEntry(createNewEntry(key, default), newEntryIndex)
+    }
   }
 
   /* inlined HashTable.findEntry0 to preserve its visibility */
diff --git a/test/junit/scala/collection/mutable/HashMapTest.scala b/test/junit/scala/collection/mutable/HashMapTest.scala
new file mode 100644
index 0000000000..cc1979a920
--- /dev/null
+++ b/test/junit/scala/collection/mutable/HashMapTest.scala
@@ -0,0 +1,38 @@
+package scala.collection
+package mutable
+
+import org.junit.Assert._
+import org.junit.Test
+import org.junit.runner.RunWith
+import org.junit.runners.JUnit4
+
+@RunWith(classOf[JUnit4])
+class HashMapTest {
+
+  @Test
+  def getOrElseUpdate_mutationInCallback() {
+    val hm = new mutable.HashMap[String, String]()
+    // add enough elements to resize the hash table in the callback
+    def add() = 1 to 100000 foreach (i => hm(i.toString) = "callback")
+    hm.getOrElseUpdate("0", {
+      add()
+      ""
+    })
+    assertEquals(Some(""), hm.get("0"))
+  }
+
+  @Test
+  def getOrElseUpdate_evalOnce(): Unit = {
+    var i = 0
+    val hm = new mutable.HashMap[Int, Int]()
+    hm.getOrElseUpdate(0, {i += 1; i})
+    assertEquals(1, hm(0))
+  }
+
+  @Test
+  def getOrElseUpdate_noEval(): Unit = {
+    val hm = new mutable.HashMap[Int, Int]()
+    hm.put(0, 0)
+    hm.getOrElseUpdate(0, throw new AssertionError())
+  }
+}
-- 
cgit v1.2.3