PeristentHashMapBuilder.putAll() with another persistent hash map can produce incorrect results.

[chuckjaz]

Consider the following code:

val p = persistentHashMapOf<Int, Int>(99 to 1)
val e = Array(101) { it }.map { it to it }
val c = persistentHashMapOf(*e.toTypedArray())
val n = p.builder().apply { putAll(c) }.build()
println("n[99] = ${n[99]}")

Expected

n[99] = 99

Received

n[99] = 1

Changing the putAll call above to putAll(e) produces the expected result.

[chuckjaz]

The was originally found in Compose: https://issuetracker.google.com/issues/193433239

[chuckjaz]

The issue appears to me to be centered around this line,

https://github.com/Kotlin/kotlinx.collections.immutable/blob/master/core/commonMain/src/implementations/immutableMap/TrieNode.kt#L607

It inverts the other and this in a way that causes the old values to be given preference to new values. If this code executes it appears to be in danger of producing the wrong value. The fix for this is not obvious to me. I couldn't think of something that wasn't brutally direct .

[chuckjaz]

I created a candidate fix in #115. This seems to work when I test it in the Compose local copy of this code.

[qurbonzoda]

@chuckjaz do you need an immediate release with the fix?

[chuckjaz]

No. We use a renamed copy of this code because it is not stable. A fix that you approve of would be sufficient then I will cherry-pick the change into our sources.

[chuckjaz]

When the #116 lands I will cherry-pick the result into our sources.

[qurbonzoda]

Understood. Thank you for the bug report, by the way.

[chuckjaz]

It was @igordmn's original report. I just narrowed it down a bit further.