Merge pull request #1160 from rklaehn/SI-6220

Si 6220

2 files changed, 121 insertions, 10 deletions

diff --git a/src/library/scala/collection/immutable/HashSet.scala b/src/library/scala/collection/immutable/HashSet.scala
index ef0173337c..d9ce7a68f7 100644
--- a/src/library/scala/collection/immutable/HashSet.scala
+++ b/src/library/scala/collection/immutable/HashSet.scala
@@ -102,6 +102,30 @@ object HashSet extends ImmutableSetFactory[HashSet] {
 
   private object EmptyHashSet extends HashSet[Any] { }
 
+  // utility method to create a HashTrieSet from two leaf HashSets (HashSet1 or HashSetCollision1) with non-colliding hash code)
+  private def makeHashTrieSet[A](hash0:Int, elem0:HashSet[A], hash1:Int, elem1:HashSet[A], level:Int) : HashTrieSet[A] = {
+    val index0 = (hash0 >>> level) & 0x1f
+    val index1 = (hash1 >>> level) & 0x1f
+    if(index0 != index1) {
+      val bitmap = (1 << index0) | (1 << index1)
+      val elems = new Array[HashSet[A]](2)
+      if(index0 < index1) {
+        elems(0) = elem0
+        elems(1) = elem1
+      } else {
+        elems(0) = elem1
+        elems(1) = elem0
+      }
+      new HashTrieSet[A](bitmap, elems, elem0.size + elem1.size)
+    } else {
+      val elems = new Array[HashSet[A]](1)
+      val bitmap = (1 << index0)
+      val child = makeHashTrieSet(hash0, elem0, hash1, elem1, level + 5)
+      elems(0) = child
+      new HashTrieSet[A](bitmap, elems, child.size)
+    }
+  }
+
   // TODO: add HashSet2, HashSet3, ...
 
   class HashSet1[A](private[HashSet] val key: A, private[HashSet] val hash: Int) extends HashSet[A] {
@@ -114,9 +138,7 @@ object HashSet extends ImmutableSetFactory[HashSet] {
       if (hash == this.hash && key == this.key) this
       else {
         if (hash != this.hash) {
-          //new HashTrieSet[A](level+5, this, new HashSet1(key, hash))
-          val m = new HashTrieSet[A](0,new Array[HashSet[A]](0),0) // TODO: could save array alloc
-          m.updated0(this.key, this.hash, level).updated0(key, hash, level)
+          makeHashTrieSet(this.hash, this, hash, new HashSet1(key, hash), level)
         } else {
           // 32-bit hash collision (rare, but not impossible)
           new HashSetCollision1(hash, ListSet.empty + this.key + key)
@@ -140,13 +162,7 @@ object HashSet extends ImmutableSetFactory[HashSet] {
 
     override def updated0(key: A, hash: Int, level: Int): HashSet[A] =
       if (hash == this.hash) new HashSetCollision1(hash, ks + key)
-      else {
-        var m: HashSet[A] = new HashTrieSet[A](0,new Array[HashSet[A]](0),0)
-        // might be able to save some ops here, but it doesn't seem to be worth it
-        for (k <- ks)
-          m = m.updated0(k, this.hash, level)
-        m.updated0(key, hash, level)
-      }
+      else makeHashTrieSet(this.hash, this, hash, new HashSet1(key, hash), level)
 
     override def removed0(key: A, hash: Int, level: Int): HashSet[A] =
       if (hash == this.hash) {
@@ -181,6 +197,9 @@ object HashSet extends ImmutableSetFactory[HashSet] {
 
   class HashTrieSet[A](private val bitmap: Int, private[collection] val elems: Array[HashSet[A]], private val size0: Int)
         extends HashSet[A] {
+    assert(Integer.bitCount(bitmap) == elems.length)
+    // assertion has to remain disabled until SI-6197 is solved
+    // assert(elems.length > 1 || (elems.length == 1 && elems(0).isInstanceOf[HashTrieSet[_]]))
 
     override def size = size0
 
diff --git a/test/files/run/t6220.scala b/test/files/run/t6220.scala
new file mode 100644
index 0000000000..834b692f43
--- /dev/null
+++ b/test/files/run/t6220.scala
@@ -0,0 +1,92 @@
+import scala.collection.immutable._
+
+object Test extends App {
+
+  // finds an int x such that improved(x) differs in the first bit to improved(0),
+  // which is the worst case for the HashTrieSet
+  def findWorstCaseInts() {
+    // copy of improve from HashSet
+    def improve(hcode: Int) = {
+      var h: Int = hcode + ~(hcode << 9)
+      h = h ^ (h >>> 14)
+      h = h + (h << 4)
+      h ^ (h >>> 10)
+    }
+
+    // find two hashes which have a large separation
+    val x = 0
+    var y = 1
+    val ix = improve(x)
+    while(y!=0 && improve(y)!=ix+(1<<31))
+      y+=1
+    printf("%s %s %x %x\n",x,y,improve(x), improve(y))
+  }
+  // this is not done every test run since it would slow down ant test.suite too much.
+  // findWorstCaseInts()
+
+  // two numbers that are immediately adiacent when fed through HashSet.improve
+  val h0 = 0
+  val h1 = 1270889724
+
+  // h is the hashcode, i is ignored for the hashcode but relevant for equality
+  case class Collision(h:Int, i:Int) {
+    override def hashCode = h
+  }
+  val a = Collision(h0,0)
+  val b = Collision(h0,1)
+  val c = Collision(h1,0)
+
+  // create a HashSetCollision1
+  val x = HashSet(a) + b
+  if(x.getClass.getSimpleName != "HashSetCollision1")
+    println("x should be a collision")
+  StructureTests.validate(x)
+  // StructureTests.printStructure(x)
+  require(x.size==2 && x.contains(a) && x.contains(b))
+
+  // go from a HashSetCollision1 to a HashTrieSet with maximum depth
+  val y = x + c
+  if(y.getClass.getSimpleName != "HashTrieSet")
+    println("y should be a HashTrieSet")
+  StructureTests.validate(y)
+  // StructureTests.printStructure(y)
+  require(y.size==3 && y.contains(a) && y.contains(b) && y.contains(c))
+
+  // go from a HashSet1 directly to a HashTrieSet with maximum depth
+  val z = HashSet(a) + c
+  if(y.getClass.getSimpleName != "HashTrieSet")
+    println("y should be a HashTrieSet")
+  StructureTests.validate(z)
+  // StructureTests.printStructure(z)
+  require(z.size == 2 && z.contains(a) && z.contains(c))
+}
+
+package scala.collection.immutable {
+  object StructureTests {
+    def printStructure(x:HashSet[_], prefix:String="") {
+      x match {
+        case m:HashSet.HashTrieSet[_] =>
+          println(prefix+m.getClass.getSimpleName + " " + m.size)
+          m.elems.foreach(child => printStructure(child, prefix + "  "))
+        case m:HashSet.HashSetCollision1[_] =>
+          println(prefix+m.getClass.getSimpleName + " " + m.ks.size)
+        case m:HashSet.HashSet1[_] =>
+          println(prefix+m.getClass.getSimpleName + " " + m.head)
+        case _ =>
+          println(prefix+"empty")
+      }
+    }
+
+    def validate(x:HashSet[_]) {
+      x match {
+        case m:HashSet.HashTrieSet[_] =>
+          require(m.elems.size>1 || (m.elems.size==1 && m.elems(0).isInstanceOf[HashSet.HashTrieSet[_]]))
+          m.elems.foreach(validate _)
+        case m:HashSet.HashSetCollision1[_] =>
+          require(m.ks.size>1)
+        case m:HashSet.HashSet1[_] =>
+        case _ =>
+      }
+    }
+  }
+}