ChampHashMap discards update in collision node where value is ne but == to the value in the existing binding

[retronym]

The legacy hash map's collision node stores hash-sharing entries as a ListMap[A, B]. ChampHashMap instead uses a Vector[(A, B)].

I noticed that this implementation contains an optimization to detect a no-op update and return the current node unchanged: https://github.com/scala/collection-strawman/blob/5b973002e3fff1e7ba65ade82617c21cb37d059f/collections/src/main/scala/strawman/collection/immutable/ChampHashMap.scala#L508-L513

Here's the manifestation of the bug:

scala> val x, y = new java.lang.Integer(42)
x: Integer = 42
y: Integer = 42

scala> x ne y
res0: Boolean = true

scala> val m = scala.collection.immutable.Map[Object, Integer]()
m: scala.collection.immutable.Map[Object,Integer] = ChampHashMap()

scala> case class Collide(x: String) { override def hashCode = 0 }
defined class Collide

scala> val z = (m + (Collide("a"), null) + (Collide("b"), x) + (Collide("b"), y)).apply(Collide("b"))
z: Integer = 42

scala> z eq y
res8: Boolean = false

scala> z eq x
res9: Boolean = true

I have a WIP branch that applied and corrected this no-op update optimization across all the immutable collections: https://github.com/scala/scala/compare/2.13.x...retronym:topic/mapn-setn-key-identity

[julienrf]

@retronym Do you mind opening a PR on scala/scala with the fix?

[SethTisue]

what's the status here?

[retronym]

Ah, I was wondering where this ticket went :)

I've fixed this already over in scala/scala.

scala> val z = (m.updated(Collide("a"), null).updated(Collide("b"), x).updated(Collide("b"), y)).apply(Collide("b"))
z: Integer = 42

scala> z eq y
res5: Boolean = true

scala> z eq x
res6: Boolean = false