Модульное тестирование

При разработке новых алгоритмов часто используются существующие структуры данных в качестве строительных блоков. Поскольку эти структуры данных, как правило, нетривиальны, количество возможных переплетений существенно возрастает.

Если вы считаете такие основополагающие структуры данных правильными и рассматриваете их операции как атомарные, вы можете проверить только осмысленные переплетения, тем самым повышая качество тестирования. Lincheck позволяет это сделать с помощью функции модульного тестирования, доступной для стратегии проверки моделей.

Рассмотрим ниже представленное MultiMap реализацию, основанную на современной j.u.c.ConcurrentHashMap.

import java.util.concurrent.*

class MultiMap<K, V> {
    val map = ConcurrentHashMap<K, List<V>>()

    // Adds the value to the list by the given key
    // Contains the race :(
    fun add(key: K, value: V) {
        val list = map[key]
        if (list == null) {
            map[key] = listOf(value)
        } else {
            map[key] = list + value
        }
    }

    fun get(key: K): List<V> = map[key] ?: emptyList()
}

Уже гарантируется, что j.u.c.ConcurrentHashMap является линейно упорядоченной, поэтому её операции можно рассматривать как атомарные. Вы можете указать эту гарантию с помощью опции addGuarantee в ModelCheckingOptions() в вашем тесте.

import java.util.concurrent.*
import org.jetbrains.kotlinx.lincheck.annotations.*
import org.jetbrains.kotlinx.lincheck.check
import org.jetbrains.kotlinx.lincheck.paramgen.*
import org.jetbrains.kotlinx.lincheck.strategy.managed.*
import org.jetbrains.kotlinx.lincheck.strategy.managed.modelchecking.*
import org.junit.*

class MultiMap<K,V> {
    val map = ConcurrentHashMap<K, List<V>>()

    // Adds the value to the list by the given key
    // Contains the race :(
    fun add(key: K, value: V) {
        val list = map[key]
        if (list == null) {
            map[key] = listOf(value)
        } else {
            map[key] = list + value
        }
    }

    fun get(key: K): List<V> = map[key] ?: emptyList()
}

@Param(name = "key", gen = IntGen::class, conf = "1:2")
class MultiMapTest {
    private val map = MultiMap<Int, Int>()

    @Operation
    fun add(@Param(name = "key") key: Int, value: Int) = map.add(key, value)

    @Operation
    fun get(@Param(name = "key") key: Int) = map.get(key)

    @Test
    fun modularTest() = ModelCheckingOptions()
        .addGuarantee(forClasses(ConcurrentHashMap::class).allMethods().treatAsAtomic())
        // Note that with the atomicity guarantees set, Lincheck can examine all possible interleavings,
        // so the test successfully passes when the number of invocations is set to `Int.MAX_VALUE`
        // If you comment the line above, the test takes a lot of time and likely fails with `OutOfMemoryError`.
        .invocationsPerIteration(Int.MAX_VALUE)
        .check(this::class)
}