Bug in PersistentMap equals implementation

[iquadrat]

PersistentMap.equals sometimes returns false even though all map entries are equal!

This is quite serious as comparing PersistentMap is a basic functionality.

We have seen this in the wild. Below is a fully self-contained test to reproduce it. The problem seems to be related with the node structure and the 'minus' / remove method.

Affected versions: at least 0.3.5 and 0.3.8

import kotlinx.collections.immutable.minus
import kotlinx.collections.immutable.persistentMapOf
import net.oddpoet.expect.extension.equal
import net.oddpoet.expect.should
import kotlin.test.Test

class PersistentMapEqualsBugTest {
    private class ChosenHashCode(
        private val hashCode: Int,
        private val name: String,
    ) {
        override fun equals(other: Any?): Boolean {
            return other is ChosenHashCode && (other.name == name)
        }

        override fun hashCode(): Int {
            return hashCode
        }

        override fun toString(): String {
            return name
        }
    }

    @Test
    fun `debug PersistentMap equals`() {
        val a = ChosenHashCode(123, "A")
        val b = ChosenHashCode(123, "B")
        val c = ChosenHashCode(123, "C")

        val abc = persistentMapOf(
            a to "x",
            b to "y",
            c to "z",
        )

        val minusAb = abc.minus(arrayOf(a, b))
        val cOnly = persistentMapOf(c to "z")

        minusAb.entries.should.equal(cOnly.entries) // passes
        minusAb.should.equal(cOnly) // fails
    }
}