libraries/stdlib/test/collections/ConcurrentModificationTest.kt

/*
 * Copyright 2010-2023 JetBrains s.r.o. and Kotlin Programming Language contributors.
 * Use of this source code is governed by the Apache 2.0 license that can be found in the license/LICENSE.txt file.
 */

package test.collections

import test.TestPlatform
import test.collections.js.linkedStringMapOf
import test.collections.js.linkedStringSetOf
import test.collections.js.stringMapOf
import test.collections.js.stringSetOf
import test.current
import kotlin.test.Test
import kotlin.test.assertFailsWith
import kotlin.test.assertTrue
import kotlin.test.fail

class ConcurrentModificationTest {

    private fun <C, I : Iterator<*>> testIteratorThrowsCME(
        withCollection: WithCollection<C>,
        createIterator: C.() -> I,
        collectionOp: CollectionOperation<C>,
        iteratorOp: IteratorOperation<I>
    ) {
        var invoked = false
        withCollection { collection ->
            invoked = true

            val iterator = collection.createIterator()

            val _ = iteratorOp.precedingFunction?.invoke(iterator)
            collectionOp.function.invoke(collection)

            val message = "listOp: ${collectionOp.description}, iteratorOp: ${iteratorOp.description}"
            if (collectionOp.throwsCME) {
                assertFailsWith<ConcurrentModificationException>(message) {
                    iteratorOp.function.invoke(iterator)
                }
            } else {
                try {
                    val _ = iteratorOp.function.invoke(iterator)
                } catch (e: Throwable) {
                    fail("$message. Expected no exception, but was $e")
                }
            }
        }

        assertTrue(invoked)
    }

    private fun <C : MutableList<String>> testIteratorThrowsCME(
        withMutableList: WithCollection<C>,
        listOps: List<CollectionOperation<C>>
    ) {
        for (listOp in listOps) {
            for (iteratorOp in iteratorOperations<String>()) {
                testIteratorThrowsCME(withMutableList, { iterator() }, listOp, iteratorOp)
            }
            for (iteratorOp in listIteratorOperations) {
                testIteratorThrowsCME(withMutableList, { listIterator() }, listOp, iteratorOp)
                testIteratorThrowsCME(withMutableList, { listIterator(2) }, listOp, iteratorOp)
            }
        }
    }

    private fun <C : MutableList<String>> testSubListThrowsCME(
        withSubList: WithCollection<C>,
        subListOps: List<CollectionOperation<C>>
    ) {
        var invoked = false
        withSubList { subList ->
            invoked = true

            for (subListOp in subListOps) {
                val message = "subListOp: ${subListOp.description}"
                if (subListOp.throwsCME) {
                    assertFailsWith<ConcurrentModificationException>(message) {
                        subListOp.function.invoke(subList)
                    }
                } else {
                    try {
                        subListOp.function.invoke(subList)
                    } catch (e: Throwable) {
                        fail("$message. Expected no exception, but was $e")
                    }
                }
            }
        }
        assertTrue(invoked)
    }

    @Test
    fun mutableList() {
        if (TestPlatform.current == TestPlatform.Js) return

        /**
         * Some operations should register a modification by contract, but java ArrayList,
         * whose implementation we can't change, do not register.
         * @param isJavaArrayListBehavior specifies whether to test java ArrayList behavior or the behavior by contract.
         */
        fun operations(isJavaArrayListBehavior: Boolean) = listOf<CollectionOperation<MutableList<String>>>(
            CollectionOperation("set()", throwsCME = false) { set(2, "e") },

            CollectionOperation("add()") { add("e") },
            CollectionOperation("add(index)") { add(2, "e") },

            CollectionOperation("remove(non-existing)", throwsCME = false) { remove("e") },
            CollectionOperation("remove(existing)") { remove("d") },
            CollectionOperation("removeAt()") { removeAt(2) },

            CollectionOperation("addAll()") { addAll(listOf("e", "f")) },
            CollectionOperation("addAll(emptyList())", throwsCME = isJavaArrayListBehavior) { addAll(emptyList()) },
            CollectionOperation("addAll(index)") { addAll(2, listOf("e", "f")) },
            CollectionOperation("addAll(index, emptyList())", throwsCME = isJavaArrayListBehavior) { addAll(2, emptyList()) },

            CollectionOperation("removeAll(non-existing)", throwsCME = false) { removeAll(listOf("e", "f")) },
            CollectionOperation("removeAll(some exist)") { removeAll(listOf("d", "e")) },
            CollectionOperation("removeAll(emptyList())", throwsCME = false) { removeAll(emptyList()) },

            CollectionOperation("retainAll(this.toMutableList())", throwsCME = false) { retainAll(this.toMutableList()) },
            CollectionOperation("retainAll(non-existing)") { retainAll(listOf("e", "f")) },
            CollectionOperation("retainAll(some exist)") { retainAll(listOf("d", "e")) },
            CollectionOperation("retainAll(emptyList())") { retainAll(emptyList()) },

            CollectionOperation("clear()") { clear() },
            CollectionOperation("iterator.remove()") { iterator().apply { val _ = next(); remove() } },
        ).also { ops ->
            // TODO(KT-89006): change .also to .let
            val _ = ops + ops.map {
                CollectionOperation("subList(1, size)." + it.description, it.throwsCME) { it.function.invoke(subList(1, size)) }
            }
        }

        fun testThrowsCME(isJavaArrayListBehavior: Boolean = true, withMutableList: WithCollection<MutableList<String>>) {
            testIteratorThrowsCME(withMutableList, operations(isJavaArrayListBehavior))
        }

        // size == capacity
        testThrowsCME { action ->
            MutableList(4) { ('a' + it).toString() }.also(action)
        }
        testThrowsCME { action ->
            mutableListOf("a", "b", "c", "d").also(action)
        }

        testThrowsCME { action ->
            val _ = buildList(4) {
                addAll(listOf("a", "b", "c", "d"))
                action(this)
            }
        }

        testThrowsCME(isJavaArrayListBehavior = false) { action ->
            ArrayDeque<String>(4).apply {
                addAll(listOf("a", "b", "c", "d"))
                action(this)
            }
        }
        testThrowsCME(isJavaArrayListBehavior = false) { action ->
            ArrayDeque(listOf("a", "b", "c", "d")).also(action)
        }

        // size < capacity
        testThrowsCME { action ->
            ArrayList<String>(10).apply {
                addAll(listOf("a", "b", "c", "d"))
                action(this)
            }
        }

        testThrowsCME { action ->
            val _ = buildList(10) {
                addAll(listOf("a", "b", "c", "d"))
                action(this)
            }
        }

        testThrowsCME(isJavaArrayListBehavior = false) { action ->
            ArrayDeque<String>(10).apply {
                addAll(listOf("a", "b", "c", "d"))
                action(this)
            }
        }
    }

    @Test
    fun arrayList() {
        if (TestPlatform.current == TestPlatform.Js) return

        val operations = listOf<CollectionOperation<ArrayList<String>>>(
            CollectionOperation("trimToSize()") { trimToSize() },
            CollectionOperation("ensureCapacity(minCapacity > capacity)") { ensureCapacity(100) },
        )

        fun testThrowsCME(withArrayList: WithCollection<ArrayList<String>>) {
            testIteratorThrowsCME(withArrayList, operations)
        }

        // size == capacity
        testThrowsCME { action ->
            ArrayList<String>(4).apply {
                addAll(listOf("a", "b", "c", "d"))
                action(this)
            }
        }
        testThrowsCME { action ->
            arrayListOf("a", "b", "c", "d").also(action)
        }

        // size < capacity
        testThrowsCME { action ->
            ArrayList<String>(10).apply {
                addAll(listOf("a", "b", "c", "d"))
                action(this)
            }
        }
    }

    @Test
    fun arrayDeque() {
        if (TestPlatform.current == TestPlatform.Js) return

        val operations = listOf<CollectionOperation<ArrayDeque<String>>>(
            CollectionOperation("addFirst()") { addFirst("e") },
            CollectionOperation("addLast()") { addLast("e") },

            CollectionOperation("removeFirst()") { removeFirst() },
            CollectionOperation("removeLast()") { removeLast() },

            CollectionOperation("removeFirstOrNull()") { removeFirstOrNull() },
            CollectionOperation("removeLastOrNull()") { removeLastOrNull() },
        )

        fun testThrowsCME(withArrayDeque: WithCollection<ArrayDeque<String>>) {
            testIteratorThrowsCME(withArrayDeque, operations)
        }

        // size == capacity
        testThrowsCME { action ->
            ArrayDeque<String>(4).apply {
                addAll(listOf("a", "b", "c", "d"))
                action(this)
            }
        }
        testThrowsCME { action ->
            ArrayDeque(listOf("a", "b", "c", "d")).also(action)
        }

        // size < capacity
        testThrowsCME { action ->
            ArrayDeque<String>(10).apply {
                addAll(listOf("a", "b", "c", "d"))
                action(this)
            }
        }
    }

    @Test
    @Suppress("RETURN_VALUE_NOT_USED", "RETURN_VALUE_NOT_USED_COERCION")
    fun subList() {
        if (TestPlatform.current == TestPlatform.Js) return

        val operations = listOf<CollectionOperation<MutableList<String>>>(
            CollectionOperation("isEmpty()") { isEmpty() },
            CollectionOperation("size") { size },

            CollectionOperation("equals()") { equals(listOf("x")) },
            CollectionOperation("hashCode()") { hashCode() },
            CollectionOperation("toString()") { toString() },

            CollectionOperation("indexOf") { indexOf("d") },
            CollectionOperation("lastIndexOf") { lastIndexOf("d") },
            CollectionOperation("contains") { contains("d") },

            CollectionOperation("get()") { get(2) },
            CollectionOperation("set()") { set(2, "e") },

            CollectionOperation("add()") { add("e") },
            CollectionOperation("add(index)") { add(2, "e") },

            CollectionOperation("remove()") { remove("d") },
            CollectionOperation("removeAt()") { removeAt(2) },

            CollectionOperation("addAll()") { addAll(listOf("e", "f")) },
            CollectionOperation("addAll(index)") { addAll(2, listOf("e", "f")) },

            CollectionOperation("removeAll()") { removeAll(listOf("d", "e")) },

            CollectionOperation("retainAll()") { retainAll(listOf("d", "e")) },

            CollectionOperation("clear()") { clear() },
            CollectionOperation("iterator()") { iterator() },
            CollectionOperation("listIterator()") { listIterator() },
        )

        fun testThrowsCME(withMutableList: WithCollection<MutableList<String>>) {
            testSubListThrowsCME(withMutableList, operations)
        }

        testThrowsCME { action ->
            val arrayList = arrayListOf("a", "b", "c", "d")
            val subList = arrayList.subList(0, arrayList.size)
            arrayList.add("e")
            action(subList)
        }
        assertFailsWith<ConcurrentModificationException> {
            val arrayList = arrayListOf("a", "b", "c", "d")
            for (e in arrayList.subList(1, 3)) arrayList.remove(e)
        }

        testThrowsCME { action ->
            val _ = buildList {
                addAll(listOf("a", "b", "c", "d"))
                val subList = subList(0, size)
                add("e")
                action(subList)
            }
        }
        assertFailsWith<ConcurrentModificationException> {
            buildList<String> {
                addAll(listOf("a", "b", "c"))
                for (e in subList(1, 3)) remove(e)
            }
        }

        testThrowsCME { action ->
            val arrayDeque = ArrayDeque(listOf("a", "b", "c", "d"))
            val subList = arrayDeque.subList(0, arrayDeque.size)
            arrayDeque.add("e")
            action(subList)
        }
        assertFailsWith<ConcurrentModificationException> {
            val arrayDeque = ArrayDeque(listOf("a", "b", "c", "d"))
            for (e in arrayDeque.subList(1, 3)) arrayDeque.remove(e)
        }
    }

    @Test
    fun mutableSet() {
        val operations = listOf<CollectionOperation<MutableSet<String>>>(
            CollectionOperation("add(non-existing)") { add("e") },
            CollectionOperation("add(existing)", throwsCME = false) { add("d") },

            CollectionOperation("remove(non-existing)", throwsCME = false) { remove("e") },
            CollectionOperation("remove(existing)") { remove("d") },

            CollectionOperation("addAll(emptyList())", throwsCME = false) { addAll(emptyList()) },
            CollectionOperation("addAll(existing)", throwsCME = false) { addAll(listOf("d", "b")) },
            CollectionOperation("addAll(some exist)") { addAll(listOf("d", "e")) },
            CollectionOperation("addAll(non-existing)") { addAll(listOf("e", "f")) },

            CollectionOperation("removeAll(non-existing)", throwsCME = false) { removeAll(listOf("e", "f")) },
            CollectionOperation("removeAll(some exist") { removeAll(listOf("d", "e")) },
            CollectionOperation("removeAll(emptyList())", throwsCME = false) { removeAll(emptyList()) },

            CollectionOperation("retainAll(this.toMutableSet())", throwsCME = false) { retainAll(this.toMutableSet()) },
            CollectionOperation("retainAll(non-existing)") { retainAll(listOf("e", "f")) },
            CollectionOperation("retainAll(some exist)") { retainAll(listOf("d", "e")) },
            CollectionOperation("retainAll(emptyList())") { retainAll(emptyList()) },

            CollectionOperation("clear()") { clear() },
            CollectionOperation("iterator.remove()") { iterator().apply { val _ = next(); remove() } },
        )

        fun testThrowsCME(withMutableSet: WithCollection<MutableSet<String>>) {
            for (setOp in operations) {
                for (iteratorOp in iteratorOperations<String>()) {
                    testIteratorThrowsCME(withMutableSet, { iterator() }, setOp, iteratorOp)
                }
            }
        }

        // Because platform implementations may have different load factor and rehash strategy,
        // make sure there is enough capacity to avoid rehash.

        val elements = listOf("a", "b", "c", "d")

        testThrowsCME { action ->
            LinkedHashSet<String>(10).apply {
                addAll(elements)
                action(this)
            }
        }
        testThrowsCME { action ->
            HashSet<String>(10).apply {
                addAll(elements)
                action(this)
            }
        }

        testThrowsCME { action ->
            val _ = buildSet(10) {
                addAll(elements)
                action(this)
            }
        }

        if (TestPlatform.current == TestPlatform.Js) {
            testThrowsCME { action ->
                stringSetOf().apply {
                    addAll(elements)
                    action(this)
                }
            }
            testThrowsCME { action ->
                linkedStringSetOf().apply {
                    addAll(elements)
                    action(this)
                }
            }
        }
    }

    @Test
    fun mutableMap() {
        val operations = listOf<CollectionOperation<MutableMap<String, String>>>(
            CollectionOperation("put(non-existing)") { put("e", "e") },
            CollectionOperation("put(existing)", throwsCME = false) { put("d", "d") },
            CollectionOperation("put(update value)", throwsCME = false) { put("d", "D") },

            CollectionOperation("remove(non-existing)", throwsCME = false) { remove("e") },
            CollectionOperation("remove(existing)") { remove("d") },

            CollectionOperation("putAll(emptyList())", throwsCME = false) { putAll(emptyMap()) },
            CollectionOperation("putAll(existing)", throwsCME = false) { putAll(mapOf("d" to "d", "b" to "b")) },
            CollectionOperation("putAll(update values)", throwsCME = false) { putAll(mapOf("d" to "D", "b" to "B")) },
            CollectionOperation("putAll(some exist)") { putAll(mapOf("d" to "d", "e" to "e")) },
            CollectionOperation("putAll(non-existing)") { putAll(mapOf("e" to "e", "f" to "f")) },

            CollectionOperation("clear()") { clear() },
            CollectionOperation("iterator.remove()") { iterator().apply { val _ = next(); remove() } },
        )

        fun testThrowsCME(withMutableMap: WithCollection<MutableMap<String, String>>) {
            for (mapOp in operations) {
                for (iteratorOp in iteratorOperations<String>()) {
                    testIteratorThrowsCME(withMutableMap, { keys.iterator() }, mapOp, iteratorOp)
                    testIteratorThrowsCME(withMutableMap, { values.iterator() }, mapOp, iteratorOp)
                }
                for (iteratorOp in iteratorOperations<MutableMap.MutableEntry<String, String>>()) {
                    testIteratorThrowsCME(withMutableMap, { entries.iterator() }, mapOp, iteratorOp)
                }
            }
        }

        // Because platform implementations may have different load factor and rehash strategy,
        // make sure there is enough capacity to avoid rehash.

        val entries = mapOf("a" to "a", "b" to "b", "c" to "c", "d" to "d")

        testThrowsCME { action ->
            LinkedHashMap<String, String>(10).apply {
                putAll(entries)
                action(this)
            }
        }
        testThrowsCME { action ->
            HashMap<String, String>(10).apply {
                putAll(entries)
                action(this)
            }
        }
        testThrowsCME { action ->
            val _ = buildMap(10) {
                putAll(entries)
                action(this)
            }
        }

        if (TestPlatform.current == TestPlatform.Js) {
            testThrowsCME { action ->
                stringMapOf<String>().apply {
                    putAll(entries)
                    action(this)
                }
            }
            testThrowsCME { action ->
                linkedStringMapOf<String>().apply {
                    putAll(entries)
                    action(this)
                }
            }
        }
    }
}

private typealias WithCollection<C> = (action: (C) -> Unit) -> Unit

private class CollectionOperation<C>(
    val description: String,
    val throwsCME: Boolean = true,
    val function: C.() -> Unit
)

private class IteratorOperation<I>(
    val description: String,
    val precedingFunction: (I.() -> Any?)? = null,
    val function: I.() -> Any?
)

private fun <E> iteratorOperations() = listOf<IteratorOperation<MutableIterator<E>>>(
    IteratorOperation("next()") { val _ = next() },
    IteratorOperation("remove()", { next() }) { remove() }
)

private val listIteratorOperations = listOf<IteratorOperation<MutableListIterator<String>>>(
    IteratorOperation("next()") { next() },
    IteratorOperation("remove()", { next() }) { remove() },
    IteratorOperation("previous()", { next() }) { previous() },
    IteratorOperation("add(\"e\")") { add("e") }
)