"Assertion failed" for persistentList.removeAt()

[timzam]

I have the following problem in v0.3.2. If I create a list of 33 elements, convert it to PersistentList, and call removeAt for the last element, "assertion failed" will be thrown.

Code:

val list = List(33) { 0 }
val pList = list.toPersistentList()
pList.removeAt(pList.lastIndex)
/*
Assertion failed
        java.lang.AssertionError: Assertion failed
at kotlinx.collections.immutable.internal.CommonFunctionsKt.assert(commonFunctions.kt:8)
at kotlinx.collections.immutable.implementations.immutableList.SmallPersistentVector.<init>(SmallPersistentVector.kt:18)
at kotlinx.collections.immutable.implementations.immutableList.PersistentVector.pullLastBufferFromRoot(PersistentVector.kt:183)
at kotlinx.collections.immutable.implementations.immutableList.PersistentVector.removeFromTailAt(PersistentVector.kt:162)
at kotlinx.collections.immutable.implementations.immutableList.PersistentVector.removeAt(PersistentVector.kt:151)
[...]
*/

I discovered the problem when doing property-based tests for my code that used PersistentList. Here is an example of a property-based test that can find the problem above:

import kotlinx.collections.immutable.toPersistentList
import net.jqwik.api.AfterFailureMode
import net.jqwik.api.Arbitraries
import net.jqwik.api.Arbitrary
import net.jqwik.api.Combinators
import net.jqwik.api.ForAll
import net.jqwik.api.Property
import net.jqwik.api.Provide
import org.junit.Assert.assertEquals

/*

java.lang.AssertionError: Assertion failed

                              |-------------------jqwik-------------------
tries = 37404                 | # of calls to property
checks = 37404                | # of not rejected calls
generation = RANDOMIZED       | parameters are randomly generated
after-failure = RANDOM_SEED   | use a new random seed
edge-cases#mode = MIXIN       | edge cases are mixed in
edge-cases#total = 16         | # of all combined edge cases
edge-cases#tried = 16         | # of edge cases tried in current run
seed = -7880195249629813947   | random seed to reproduce generated values
sample = [RemoveCase(list=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], removeIndex=32)]
original-sample = [RemoveCase(list=[489591, 108, 333, 103363643, 5, 72, 16, 7, 109662, 1191, 74401, 1020547435, 4663656, 5, 2, 89, 17, 23, 17, 1948559812, 179, 1180415318, 141, 10, 69, 26, 44607, 11749, 3072, 46798, 511, 63050, 5201], removeIndex=32)]

Assertion failed
java.lang.AssertionError: Assertion failed
	at kotlinx.collections.immutable.internal.CommonFunctionsKt.assert(commonFunctions.kt:8)
	at kotlinx.collections.immutable.implementations.immutableList.SmallPersistentVector.<init>(SmallPersistentVector.kt:18)
	at kotlinx.collections.immutable.implementations.immutableList.PersistentVector.pullLastBufferFromRoot(PersistentVector.kt:183)
	at kotlinx.collections.immutable.implementations.immutableList.PersistentVector.removeFromTailAt(PersistentVector.kt:162)
	at kotlinx.collections.immutable.implementations.immutableList.PersistentVector.removeAt(PersistentVector.kt:151)
    [...]
    
 */
class PersistentListPropertyBasedTest {

    @Provide
    fun removeCases(): Arbitrary<RemoveCase> {
        val listArbitrary = generateNonNegativeIntegers().list().ofMinSize(1)
        val indexArbitrary = generateNonNegativeIntegers()
        return Combinators.combine(listArbitrary, indexArbitrary).`as` { list, index ->
            RemoveCase(list, index % list.size)
        }
    }

    @Property(tries = 50_000, afterFailure = AfterFailureMode.RANDOM_SEED)
    fun randomRemoves(@ForAll("removeCases") removeCase: RemoveCase) {
        val (list, removeIndex) = removeCase
        val persistentNewList = list.toPersistentList().removeAt(removeIndex)
        val mutableNewList = ArrayList(list).apply { removeAt(removeIndex) }
        assertEquals(mutableNewList, persistentNewList)
    }

    data class RemoveCase(
        val list: List<Int>,
        val removeIndex: Int
    )

    companion object {

        private fun generateNonNegativeIntegers() = Arbitraries.integers().between(0, Int.MAX_VALUE)

    }

}

There is already a PR in progress that should fix the problem (thanks!): #74

[qurbonzoda]

Fixed