Merge pull request #1169 from rklaehn/SI-6261

Si 6261

3 files changed, 182 insertions, 40 deletions

diff --git a/src/library/scala/collection/immutable/HashMap.scala b/src/library/scala/collection/immutable/HashMap.scala
index 0b297aeb45..b41327ed95 100644
--- a/src/library/scala/collection/immutable/HashMap.scala
+++ b/src/library/scala/collection/immutable/HashMap.scala
@@ -146,6 +146,29 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int {
 
   private object EmptyHashMap extends HashMap[Any, Nothing] { }
 
+  // utility method to create a HashTrieMap from two leaf HashMaps (HashMap1 or HashMapCollision1) with non-colliding hash code)
+  private def makeHashTrieMap[A, B](hash0:Int, elem0:HashMap[A, B], hash1:Int, elem1:HashMap[A, B], level:Int, size:Int) : HashTrieMap[A, B] = {
+    val index0 = (hash0 >>> level) & 0x1f
+    val index1 = (hash1 >>> level) & 0x1f
+    if(index0 != index1) {
+      val bitmap = (1 << index0) | (1 << index1)
+      val elems = new Array[HashMap[A,B]](2)
+      if(index0 < index1) {
+        elems(0) = elem0
+        elems(1) = elem1
+      } else {
+        elems(0) = elem1
+        elems(1) = elem0
+      }
+      new HashTrieMap[A, B](bitmap, elems, size)
+    } else {
+      val elems = new Array[HashMap[A,B]](1)
+      val bitmap = (1 << index0)
+      elems(0) = makeHashTrieMap(hash0, elem0, hash1, elem1, level + 5, size)
+      new HashTrieMap[A, B](bitmap, elems, size)
+    }
+  }
+
   // TODO: add HashMap2, HashMap3, ...
 
   class HashMap1[A,+B](private[collection] val key: A, private[collection] val hash: Int, private[collection] val value: (B @uV), private[collection] var kv: (A,B @uV)) extends HashMap[A,B] {
@@ -183,30 +206,10 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int {
           new HashMap1(nkv._1, hash, nkv._2, nkv)
         }
       } else {
-        var thatindex = (hash >>> level) & 0x1f
-        var thisindex = (this.hash >>> level) & 0x1f
         if (hash != this.hash) {
           // they have different hashes, but may collide at this level - find a level at which they don't
-          var lvl = level
-          var top: HashTrieMap[A, B1] = null
-          var prev: HashTrieMap[A, B1] = null
-          while (thisindex == thatindex) {
-            val newlevel = new HashTrieMap[A, B1](1 << thisindex, new Array[HashMap[A, B1]](1), 2)
-            if (prev ne null) prev.elems(0) = newlevel else top = newlevel
-            prev = newlevel
-            lvl += 5
-            thatindex = (hash >>> lvl) & 0x1f
-            thisindex = (this.hash >>> lvl) & 0x1f
-          }
-          val bottelems = new Array[HashMap[A,B1]](2)
-          val ind = if (thisindex < thatindex) 1 else 0
-          bottelems(1 - ind) = this
-          bottelems(ind) = new HashMap1[A, B1](key, hash, value, kv)
-          val bottom = new HashTrieMap[A,B1]((1 << thisindex) | (1 << thatindex), bottelems, 2)
-          if (prev ne null) {
-            prev.elems(0) = bottom
-            top
-          } else bottom
+          val that = new HashMap1[A, B1](key, hash, value, kv)
+          makeHashTrieMap[A,B1](this.hash, this, hash, that, level, 2)
         } else {
           // 32-bit hash collision (rare, but not impossible)
           new HashMapCollision1(hash, ListMap.empty.updated(this.key,this.value).updated(key,value))
@@ -221,12 +224,13 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int {
     // this method may be called multiple times in a multithreaded environment, but that's ok
     private[HashMap] def ensurePair: (A,B) = if (kv ne null) kv else { kv = (key, value); kv }
     protected override def merge0[B1 >: B](that: HashMap[A, B1], level: Int, merger: Merger[A, B1]): HashMap[A, B1] = {
-      that.updated0(key, hash, level, value, kv, if (merger ne null) merger.invert else null)
+      that.updated0(key, hash, level, value, kv, merger.invert)
     }
   }
 
   private[collection] class HashMapCollision1[A, +B](private[collection] val hash: Int, val kvs: ListMap[A, B @uV])
           extends HashMap[A, B @uV] {
+    // assert(kvs.size > 1)
 
     override def size = kvs.size
 
@@ -238,20 +242,20 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int {
         if ((merger eq null) || !kvs.contains(key)) new HashMapCollision1(hash, kvs.updated(key, value))
         else new HashMapCollision1(hash, kvs + merger((key, kvs(key)), kv))
       } else {
-        var m: HashMap[A,B1] = new HashTrieMap[A,B1](0,new Array[HashMap[A,B1]](0),0)
-        // might be able to save some ops here, but it doesn't seem to be worth it
-        for ((k,v) <- kvs)
-          m = m.updated0(k, this.hash, level, v, null, merger)
-        m.updated0(key, hash, level, value, kv, merger)
+        val that = new HashMap1(key, hash, value, kv)
+        makeHashTrieMap(this.hash, this, hash, that, level, size + 1)
       }
 
     override def removed0(key: A, hash: Int, level: Int): HashMap[A, B] =
       if (hash == this.hash) {
         val kvs1 = kvs - key
-        if (!kvs1.isEmpty)
-          new HashMapCollision1(hash, kvs1)
-        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)
       } else this
 
     override def iterator: Iterator[(A,B)] = kvs.iterator
@@ -275,6 +279,9 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int {
     private[collection] val size0: Int
   ) extends HashMap[A, B @uV] {
 
+    // assert(Integer.bitCount(bitmap) == elems.length)
+    // assert(elems.length > 1 || (elems.length == 1 && elems(0).isInstanceOf[HashTrieMap[_,_]]))
+
 /*
     def this (level: Int, m1: HashMap1[A,B], m2: HashMap1[A,B]) = {
       this(((m1.hash >>> level) & 0x1f) | ((m2.hash >>> level) & 0x1f), {
@@ -347,9 +354,14 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int {
             Array.copy(elems, 0, elemsNew, 0, offset)
             Array.copy(elems, offset + 1, elemsNew, offset, elems.length - offset - 1)
             val sizeNew = size - sub.size
-            new HashTrieMap(bitmapNew, elemsNew, sizeNew)
+            if (elemsNew.length == 1 && !elemsNew(0).isInstanceOf[HashTrieMap[_,_]])
+              elemsNew(0)
+            else
+              new HashTrieMap(bitmapNew, elemsNew, sizeNew)
           } else
             HashMap.empty[A,B]
+        } else if(elems.length == 1 && !subNew.isInstanceOf[HashTrieMap[_,_]]) {
+          subNew
         } else {
           val elemsNew = new Array[HashMap[A,B]](elems.length)
           Array.copy(elems, 0, elemsNew, 0, elems.length)
@@ -480,7 +492,7 @@ time { mNew.iterator.foreach( p => ()) }
         }
 
         new HashTrieMap[A, B1](this.bitmap | that.bitmap, merged, totalelems)
-      case hm: HashMapCollision1[_, _] => that.merge0(this, level, if (merger ne null) merger.invert else null)
+      case hm: HashMapCollision1[_, _] => that.merge0(this, level, merger.invert)
       case hm: HashMap[_, _] => this
       case _ => sys.error("section supposed to be unreachable.")
     }
diff --git a/src/library/scala/collection/immutable/ListMap.scala b/src/library/scala/collection/immutable/ListMap.scala
index 091443f909..c21032603f 100644
--- a/src/library/scala/collection/immutable/ListMap.scala
+++ b/src/library/scala/collection/immutable/ListMap.scala
@@ -121,12 +121,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.next; res }
+        else { val res = (self.key, self.value); self = self.tail; res }
     }.toList.reverseIterator
 
   protected def key: A = throw new NoSuchElementException("empty map")
   protected def value: B = throw new NoSuchElementException("empty map")
-  protected def next: ListMap[A, B] = throw new NoSuchElementException("empty map")
+  override def tail: ListMap[A, B] = throw new NoSuchElementException("empty map")
 
   /** This class represents an entry in the `ListMap`.
    */
@@ -140,7 +140,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.next, acc + 1)
+    @tailrec private def size0(cur: ListMap[A, B1], acc: Int): Int = if (cur.isEmpty) acc else size0(cur.tail, acc + 1)
 
     /** Is this an empty map?
      *
@@ -157,7 +157,7 @@ extends AbstractMap[A, B]
      */
     override def apply(k: A): B1 = apply0(this, k)
 
-    @tailrec private def apply0(cur: ListMap[A, B1], k: A): B1 = if (k == cur.key) cur.value else apply0(cur.next, k)
+    @tailrec private def apply0(cur: ListMap[A, B1], k: A): B1 = if (k == cur.key) cur.value else apply0(cur.tail, k)
 
     /** Checks if this map maps `key` to a value and return the
      *  value if it exists.
@@ -169,7 +169,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.next.nonEmpty) get0(cur.next, k) else None
+      else if (cur.tail.nonEmpty) get0(cur.tail, 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`,
@@ -198,7 +198,7 @@ extends AbstractMap[A, B]
       var lst: List[(A, B1)] = Nil
       while (cur.nonEmpty) {
         if (k != cur.key) lst ::= ((cur.key, cur.value))
-        cur = cur.next
+        cur = cur.tail
       }
       var acc = ListMap[A, B1]()
       while (lst != Nil) {
@@ -211,6 +211,6 @@ extends AbstractMap[A, B]
     }
 
 
-    override protected def next: ListMap[A, B1] = ListMap.this
+    override def tail: ListMap[A, B1] = ListMap.this
   }
 }
diff --git a/test/files/run/t6261.scala b/test/files/run/t6261.scala
new file mode 100644
index 0000000000..b4463256c9
--- /dev/null
+++ b/test/files/run/t6261.scala
@@ -0,0 +1,130 @@
+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)
+    if(x.getClass.getSimpleName != "HashTrieMap")
+      println("A hash map containing two non-colliding values should be a HashTrieMap")
+
+    val y = x - 1
+    if(y.getClass.getSimpleName != "HashMap1")
+      println("A hash map containing one element should always use HashMap1")
+  }
+
+  def test2() {
+    // class that always causes hash collisions
+    case class Collision(value:Int) { override def hashCode = 0 }
+
+    // create a set that should have a collison
+    val x = HashMap.empty + (Collision(0)->0) + (Collision(1) ->0)
+    if(x.getClass.getSimpleName != "HashMapCollision1")
+      println("HashMap of size >1 with collisions should use HashMapCollision")
+
+    // remove the collision again by removing all but one element
+    val y = x - Collision(0)
+    if(y.getClass.getSimpleName != "HashMap1")
+      println("HashMap of size 1 should use HashMap1" + y.getClass)
+  }
+  def test3() {
+    // 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)->0
+    val b = Collision(h0,1)->0
+    val c = Collision(h1,0)->0
+
+    // create a HashSetCollision1
+    val x = HashMap(a) + b
+    if(x.getClass.getSimpleName != "HashMapCollision1")
+      println("x should be a HashMapCollision")
+    StructureTests.validate(x)
+    //StructureTests.printStructure(x)
+    require(x.size==2 && x.contains(a._1) && x.contains(b._1))
+
+    // go from a HashSetCollision1 to a HashTrieSet with maximum depth
+    val y = x + c
+    if(y.getClass.getSimpleName != "HashTrieMap")
+      println("y should be a HashTrieMap")
+    StructureTests.validate(y)
+    // StructureTests.printStructure(y)
+    require(y.size==3 && y.contains(a._1) && y.contains(b._1) && y.contains(c._1))
+
+    // go from a HashSet1 directly to a HashTrieSet with maximum depth
+    val z = HashMap(a) + c
+    if(y.getClass.getSimpleName != "HashTrieMap")
+      println("y should be a HashTrieMap")
+    StructureTests.validate(z)
+    // StructureTests.printStructure(z)
+    require(z.size == 2 && z.contains(a._1) && z.contains(c._1))
+  }
+  test0()
+  test1()
+  test2()
+  test3()
+}
+
+
+package scala.collection.immutable {
+  object StructureTests {
+    def printStructure(x:HashMap[_,_], prefix:String="") {
+      x match {
+        case m:HashMap.HashTrieMap[_,_] =>
+          println(prefix+m.getClass.getSimpleName + " " + m.size)
+          m.elems.foreach(child => printStructure(child, prefix + "  "))
+        case m:HashMap.HashMapCollision1[_,_] =>
+          println(prefix+m.getClass.getSimpleName + " " + m.kvs.size)
+        case m:HashMap.HashMap1[_,_] =>
+          println(prefix+m.getClass.getSimpleName + " " + m.head)
+        case _ =>
+          println(prefix+"empty")
+      }
+    }
+
+    def validate(x:HashMap[_,_]) {
+      x match {
+        case m:HashMap.HashTrieMap[_,_] =>
+          require(m.elems.size>1 || (m.elems.size==1 && m.elems(0).isInstanceOf[HashMap.HashTrieMap[_,_]]))
+          m.elems.foreach(validate _)
+        case m:HashMap.HashMapCollision1[_,_] =>
+          require(m.kvs.size>1)
+        case m:HashMap.HashMap1[_,_] =>
+        case _ =>
+      }
+    }
+  }
+}