Ghost element when applying multiples minus operations on a PersistentHashSet

[correacaio]

Hi everyone.

We have been using kotlinx collections immutable for some years and we finally found a bug 😟
I don't know exactly why it happens, but I can simulate it with the following code:

(1..1000).forEach {   // the bug doesn't happen every time, so I put it inside a loop to make it easier to happen 
    val originalList = (1..40000)
        .map {
            listOf(
                UUID.randomUUID().toString(),
                UUID.randomUUID().toString()
            )
        }
    
    val originalPersistentSet = originalList.flatten()
        .toPersistentList()
        .add(UUID.randomUUID().toString())  // this is the only element that shouldn't be removed
        .toPersistentHashSet()
    
    val firstLBatchToRemove = originalList.map { it[0] }.toPersistentHashSet()
    val secondBatchToRemove = originalList.map { it[1] }.toPersistentHashSet()
    
    val result = originalPersistentSet
    //  .minus(firstLBatchToRemove.plus(secondBatchToRemove).toPersistentHashSet())  // if I use this line instead of the next two, it seems that the bug doesn't happen anymore
        .minus(firstLBatchToRemove)
        .minus(secondBatchToRemove)
        .toPersistentHashSet()
    
    result.size shouldBe 1  // always true, as it should be
    shouldNotThrowAny { println(result.first()) }    // This assert fails once in a while throwing `NoSuchElementException`
    
    delay(1.seconds)
}

Basically, after two minus operations in a "large" PersistentHashSet, I get a PersistentSet with size 1 (as expected in this test). Still, when I try to get the element, the following exception is thrown:

Collection is empty.
java.util.NoSuchElementException: Collection is empty.
	at kotlin.collections.CollectionsKt___CollectionsKt.first(_Collections.kt:201)
	at com.collections.PersistentHashSetTest$1$2.invokeSuspend(PersistentHashSetTest.kt:59) // my test class
	at kotlin.coroutines.jvm.internal.BaseContinuationImpl.resumeWith(ContinuationImpl.kt:33)

It long as I can tell, it is a bug exclusively on PersistentHashSet.
I've applied the same tests using PersistentSet, HashSet, and Lists (immutable or not) and it worked just fine.

Hope I have explained it successfully, please tell me if I can help more somehow.

[fzhinkin]

Double checked after #217 and #218 landed the master: the bug is still reproducible.

[fzhinkin]

The reduced reproducer:

import kotlinx.collections.immutable.minus
import kotlinx.collections.immutable.toPersistentHashSet
import kotlin.test.Test
import kotlin.test.assertEquals

public class KCI144 {
    @Test
    fun reproducer() {
        val firstBatch = listOf(4554, 9380, 4260, 6602)
        val secondBatch = listOf(1188, 14794)
        val extraElement = 7450

        val set = firstBatch.plus(secondBatch).plus(extraElement).toPersistentHashSet()
        val result = set.minus(firstBatch.toPersistentHashSet()).minus(secondBatch)
        assertEquals(1, result.size)
        assertEquals(extraElement, result.first())
    }
}

[DmitryNekrasov]

Double checked after #217 and #218 landed the master: the bug is still reproducible.

Fixes in issues #198 and #204 mostly affected fixes inside the TrieNode class from the kotlinx.collections.immutable.implementations.immutableMap package.
The PersistentHashMap class contains this TrieNode as a field, and most operations on the data structure are delegated to it. At the same time, the PersistentOrderedMap and PersistentOrderedSet classes contain the fields val hashMap: PersistentHashMap<K, LinkedValue<V>> and val hashMap: PersistentHashMap<E, Links>, respectively, so their implementations also depend on k.c.i.i.immutableMap.TrieNode. However, the PersistentHashSet class depends on another TrieNode, from the k.c.i.i.immutableSet package, so the above mentioned fixes did not affect the behavior of PersistentHashSet. I have started working on this task now.