SI-9522 release key reference when deleting from OpenHashMap

This sets the key field in the hash table entry to its default value
when an entry is deleted, so as not to unexpectedly retain an object
reference, leading to a memory leak.

Also includes incidental changes to the slot location algorithm that
reduce the number of deleted entries.

6 files changed, 116 insertions, 32 deletions

diff --git a/build.sbt b/build.sbt
index d592b86aff..2eb629f923 100644
--- a/build.sbt
+++ b/build.sbt
@@ -66,6 +66,7 @@ val scalaXmlDep = withoutScalaLang("org.scala-lang.modules" %% "scala-xml" % ver
 val partestDep = withoutScalaLang("org.scala-lang.modules" %% "scala-partest" % versionNumber("partest"))
 val junitDep = "junit" % "junit" % "4.11"
 val junitIntefaceDep = "com.novocode" % "junit-interface" % "0.11" % "test"
+val jolDep = "org.openjdk.jol" % "jol-core" % "0.5"
 val asmDep = "org.scala-lang.modules" % "scala-asm" % versionProps("scala-asm.version")
 val jlineDep = "jline" % "jline" % versionProps("jline.version")
 val antDep = "org.apache.ant" % "ant" % "1.9.4"
@@ -544,7 +545,7 @@ lazy val junit = project.in(file("test") / "junit")
   .settings(disablePublishing: _*)
   .settings(
     fork in Test := true,
-    libraryDependencies ++= Seq(junitDep, junitIntefaceDep),
+    libraryDependencies ++= Seq(junitDep, junitIntefaceDep, jolDep),
     testOptions += Tests.Argument(TestFrameworks.JUnit, "-a", "-v"),
     unmanagedSourceDirectories in Test := List(baseDirectory.value)
   )
diff --git a/build.xml b/build.xml
index 778bcc561b..c1b0b228a1 100644
--- a/build.xml
+++ b/build.xml
@@ -277,6 +277,7 @@ TODO:
       <property name="junit.version" value="4.12"/>
       <artifact:dependencies pathId="junit.classpath" filesetId="junit.fileset">
         <dependency groupId="junit" artifactId="junit" version="${junit.version}"/>
+        <dependency groupId="org.openjdk.jol" artifactId="jol-core" version="0.5"/>
       </artifact:dependencies>
       <copy-deps project="junit"/>
 
diff --git a/src/eclipse/repl/.classpath b/src/eclipse/repl/.classpath
index 682377adc9..141f84e6bb 100644
--- a/src/eclipse/repl/.classpath
+++ b/src/eclipse/repl/.classpath
@@ -2,7 +2,7 @@
 <classpath>
 	<classpathentry kind="src" path="repl"/>
 	<classpathentry kind="var" path="SCALA_BASEDIR/build/deps/asm/scala-asm-5.0.4-scala-3.jar"/>
-	<classpathentry kind="var" path="SCALA_BASEDIR/build/deps/repl/jline-2.12.1.jar"/>
+	<classpathentry kind="var" path="SCALA_BASEDIR/build/deps/repl/jline-2.14.1.jar"/>
 	<classpathentry combineaccessrules="false" kind="src" path="/scala-compiler"/>
 	<classpathentry combineaccessrules="false" kind="src" path="/scala-library"/>
 	<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER"/>
diff --git a/src/eclipse/test-junit/.classpath b/src/eclipse/test-junit/.classpath
index 3635c85112..1e1b510663 100644
--- a/src/eclipse/test-junit/.classpath
+++ b/src/eclipse/test-junit/.classpath
@@ -11,6 +11,7 @@
 	<classpathentry combineaccessrules="false" kind="src" path="/partest-extras"/>
 	<classpathentry combineaccessrules="false" kind="src" path="/scaladoc"/>
 	<classpathentry kind="var" path="SCALA_BASEDIR/build/deps/scaladoc/scala-xml_2.12.0-M4-1.0.5.jar"/>
+	<classpathentry kind="var" path="SCALA_BASEDIR/build/deps/junit/jol-core-0.5.jar"/>
 	<classpathentry kind="con" path="org.eclipse.jdt.junit.JUNIT_CONTAINER/4"/>
 	<classpathentry kind="output" path="build-test-junit"/>
 </classpath>
diff --git a/src/library/scala/collection/mutable/OpenHashMap.scala b/src/library/scala/collection/mutable/OpenHashMap.scala
index 5f8f5b9a0a..5bea1634c4 100644
--- a/src/library/scala/collection/mutable/OpenHashMap.scala
+++ b/src/library/scala/collection/mutable/OpenHashMap.scala
@@ -21,10 +21,16 @@ object OpenHashMap {
   def apply[K, V](elems : (K, V)*) = new OpenHashMap[K, V] ++= elems
   def empty[K, V] = new OpenHashMap[K, V]
 
-  final private class OpenEntry[Key, Value](val key: Key,
-                                            val hash: Int,
+  /** A hash table entry.
+    * 
+    * The entry is occupied if and only if its `value` is a `Some`;
+    * deleted if and only if its `value` is `None`.
+    * If its `key` is not the default value of type `Key`, the entry is occupied.
+    * If the entry is occupied, `hash` contains the hash value of `key`.
+    */
+  final private class OpenEntry[Key, Value](var key: Key,
+                                            var hash: Int,
                                             var value: Option[Value])
-                extends HashEntry[Key, OpenEntry[Key, Value]]
 
   private[mutable] def nextPositivePowerOfTwo(i : Int) = 1 << (32 - Integer.numberOfLeadingZeros(i - 1))
 }
@@ -64,7 +70,14 @@ extends AbstractMap[Key, Value]
   private[this] val actualInitialSize = OpenHashMap.nextPositivePowerOfTwo(initialSize)
 
   private var mask = actualInitialSize - 1
-  private var table : Array[Entry] = new Array[Entry](actualInitialSize)
+
+  /** The hash table.
+    * 
+    * The table's entries are initialized to `null`, indication of an empty slot.
+    * A slot is either deleted or occupied if and only if the entry is non-`null`.
+    */
+  private[this] var table = new Array[Entry](actualInitialSize)
+
   private var _size = 0
   private var deleted = 0
 
@@ -91,42 +104,43 @@ extends AbstractMap[Key, Value]
     table = new Array[Entry](newSize)
     mask = newSize - 1
     oldTable.foreach( entry =>
-      if (entry != null && entry.value != None) addEntry(entry))
+      if (entry != null && entry.value != None)
+        table(findIndex(entry.key, entry.hash)) = entry )
     deleted = 0
   }
 
   /** Return the index of the first slot in the hash table (in probe order)
-    * that either is empty, or is or was last occupied by the given key.
-    */
-  private[this] def findIndex(key: Key) : Int = findIndex(key, hashOf(key))
-
-  /** Return the index of the first slot in the hash table (in probe order)
-    * that either is empty, or is or was last occupied by the given key.
-    * 
-    * This method is an optimization for when the hash value is in hand.
+    * that is, in order of preference, either occupied by the given key, deleted, or empty.
     * 
     * @param hash hash value for `key`
     */
   private[this] def findIndex(key: Key, hash: Int): Int = {
     var j = hash
-
     var index = hash & mask
     var perturb = index
-    while(table(index) != null &&
-          !(table(index).hash == hash &&
-            table(index).key == key)){
+
+    /** Index of the first slot containing a deleted entry, or -1 if none found yet. */
+    var firstDeletedIndex = -1
+
+    var entry = table(index)
+    while (entry != null) {
+      if (entry.hash == hash && entry.key == key && entry.value != None)
+        return index
+
+      if (firstDeletedIndex == -1 && entry.value == None)
+        firstDeletedIndex = index
+
       j = 5 * j + 1 + perturb
       perturb >>= 5
       index = j & mask
+      entry = table(index)
     }
-    index
-  }
 
-  private[this] def addEntry(entry: Entry) =
-    if (entry != null) table(findIndex(entry.key, entry.hash)) = entry
+    if (firstDeletedIndex == -1) index else firstDeletedIndex
+  }
 
   override def update(key: Key, value: Value) {
-    put(key, hashOf(key), value)
+    put(key, value)
   }
 
   @deprecatedOverriding("+= should not be overridden in order to maintain consistency with put.", "2.11.0")
@@ -150,6 +164,8 @@ extends AbstractMap[Key, Value]
     } else {
       val res = entry.value
       if (entry.value == None) {
+        entry.key = key
+        entry.hash = hash
         size += 1
         deleted -= 1
         modCount += 1
@@ -159,13 +175,22 @@ extends AbstractMap[Key, Value]
     }
   }
 
+  /** Delete the hash table slot contained in the given entry. */
+  @inline
+  private[this] def deleteSlot(entry: Entry) = {
+    entry.key = null.asInstanceOf[Key]
+    entry.hash = 0
+    entry.value = None
+
+    size -= 1
+    deleted += 1
+  }
+
   override def remove(key : Key): Option[Value] = {
-    val index = findIndex(key)
-    if (table(index) != null && table(index).value != None){
-      val res = table(index).value
-      table(index).value = None
-      size -= 1
-      deleted += 1
+    val entry = table(findIndex(key, hashOf(key)))
+    if (entry != null && entry.value != None) {
+      val res = entry.value
+      deleteSlot(entry)
       res
     } else None
   }
@@ -249,7 +274,7 @@ extends AbstractMap[Key, Value]
   }
 
   override def retain(f : (Key, Value) => Boolean) = {
-    foreachUndeletedEntry(entry => if (!f(entry.key, entry.value.get)) {entry.value = None; size -= 1; deleted += 1} )
+    foreachUndeletedEntry(entry => if (!f(entry.key, entry.value.get)) deleteSlot(entry))
     this
   }
 
diff --git a/test/junit/scala/collection/mutable/OpenHashMapTest.scala b/test/junit/scala/collection/mutable/OpenHashMapTest.scala
index 9b5c20e01a..b6cddf2101 100644
--- a/test/junit/scala/collection/mutable/OpenHashMapTest.scala
+++ b/test/junit/scala/collection/mutable/OpenHashMapTest.scala
@@ -4,6 +4,10 @@ import org.junit.Test
 import org.junit.Assert._
 import org.junit.runner.RunWith
 import org.junit.runners.JUnit4
+import org.openjdk.jol.info.GraphLayout
+import org.openjdk.jol.info.GraphWalker
+import org.openjdk.jol.info.GraphVisitor
+import org.openjdk.jol.info.GraphPathRecord
 
 /** Tests for [[OpenHashMap]]. */
 @RunWith(classOf[JUnit4])
@@ -28,7 +32,13 @@ class OpenHashMapTest {
     val fieldMirror = mirror.reflect(m).reflectField(termSym)
 		*/
     // Use Java reflection instead for now.
-    val field = m.getClass.getDeclaredField("deleted")
+    val field =
+      try {  // Name may or not be mangled, depending on what the compiler authors are doing.
+        m.getClass.getDeclaredField("scala$collection$mutable$OpenHashMap$$deleted")
+      } catch {
+        case _: NoSuchFieldException =>
+          m.getClass.getDeclaredField("deleted")
+      }
     field.setAccessible(true)
 
     m.put(0, 0)
@@ -39,4 +49,50 @@ class OpenHashMapTest {
     // TODO assertEquals(0, fieldMirror.get.asInstanceOf[Int])
     assertEquals(0, field.getInt(m))
   }
+
+  /** Test that an [[OpenHashMap]] frees references to a deleted key (SI-9522). */
+  @Test
+  def freesDeletedKey {
+    import scala.language.reflectiveCalls
+
+    class MyClass {
+      override def hashCode() = 42
+    }
+
+    val counter = new GraphVisitor() {
+      private[this] var instanceCount: Int = _
+
+      def countInstances(obj: AnyRef) = {
+        instanceCount = 0
+        val walker = new GraphWalker(obj)
+        walker.addVisitor(this)
+        walker.walk
+        instanceCount
+      }
+
+      override def visit(record: GraphPathRecord) {
+        if (record.klass() == classOf[MyClass])  instanceCount += 1
+      }
+    }
+
+    val m = OpenHashMap.empty[MyClass, Int]
+    val obj = new MyClass
+    assertEquals("Found a key instance in the map before adding one!?", 0, counter.countInstances(m))
+    m.put(obj, 0)
+    assertEquals("There should be only one key instance in the map.", 1, counter.countInstances(m))
+    m.put(obj, 1)
+    assertEquals("There should still be only one key instance in the map.", 1, counter.countInstances(m))
+    m.remove(obj)
+    assertEquals("There should be no key instance in the map.", 0, counter.countInstances(m))
+
+    val obj2 = new MyClass
+    assertEquals("The hash codes of the test objects need to match.", obj.##, obj2.##)
+    m.put(obj, 0)
+    m.put(obj2, 0)
+    assertEquals("There should be two key instances in the map.", 2, counter.countInstances(m))
+    m.remove(obj)
+    assertEquals("There should be one key instance in the map.", 1, counter.countInstances(m))
+    m.remove(obj2)
+    assertEquals("There should be no key instance in the map.", 0, counter.countInstances(m))
+  }
 }