| /* |
| * Copyright 2016-2017 JetBrains s.r.o. |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| package kotlinx.coroutines.experimental |
| |
| import com.devexperts.dxlab.lincheck.Actor |
| import com.devexperts.dxlab.lincheck.Result |
| import com.devexperts.dxlab.lincheck.verifier.Verifier |
| import java.lang.reflect.Method |
| import java.util.* |
| import kotlin.coroutines.experimental.Continuation |
| import kotlin.coroutines.experimental.CoroutineContext |
| import kotlin.coroutines.experimental.EmptyCoroutineContext |
| import kotlin.coroutines.experimental.intrinsics.COROUTINE_SUSPENDED |
| import kotlin.coroutines.experimental.intrinsics.startCoroutineUninterceptedOrReturn |
| |
| data class OpResult(val name: String, val value: Any?) { |
| override fun toString(): String = "$name=$value" |
| } |
| |
| private const val CS_STR = "COROUTINE_SUSPENDED" |
| |
| class LinTesting { |
| private val resumed = object : ThreadLocal<ArrayList<OpResult>>() { |
| override fun initialValue() = arrayListOf<OpResult>() |
| } |
| |
| private inline fun wrap(block: () -> Any?): Any? = |
| try { repr(block()) } |
| catch(e: Throwable) { repr(e) } |
| |
| private fun repr(e: Any?): Any? = |
| when { |
| e === COROUTINE_SUSPENDED -> CS_STR |
| e is Throwable -> e.toString() |
| else -> e |
| } |
| |
| fun <T> run(name: String, block: suspend () -> T): List<OpResult> { |
| val list = resumed.get() |
| list.clear() |
| val result = arrayListOf(OpResult(name, wrap { |
| block.startCoroutineUninterceptedOrReturn(completion = object : Continuation<Any?> { |
| override val context: CoroutineContext |
| get() = EmptyCoroutineContext |
| |
| override fun resume(value: Any?) { |
| resumed.get() += OpResult(name, repr(value)) |
| } |
| |
| override fun resumeWithException(exception: Throwable) { |
| resumed.get() += OpResult(name, repr(exception)) |
| } |
| } |
| ) |
| })) |
| result.addAll(list) |
| return result |
| } |
| } |
| |
| class LinVerifier( |
| actorsPerThread: List<List<Actor>>, testInstance: Any, resetMethod: Method? |
| ) : Verifier(actorsPerThread, testInstance, resetMethod) { |
| private val possibleResultsSet: Set<List<List<Result>>> = |
| generateAllLinearizableExecutions(actorsPerThread) |
| .map { linEx: List<Actor> -> |
| val res: List<Result> = executeActors(testInstance, linEx) |
| val actorIds = linEx.withIndex().associateBy({ it.value}, { it.index }) |
| actorsPerThread.map { actors -> actors.map { actor -> res[actorIds[actor]!!] } } |
| }.toSet() |
| |
| override fun verifyResults(results: List<List<Result>>) { |
| if (!valid(results)) { |
| println("\nNon-linearizable execution:") |
| printResults(results) |
| println("\nPossible linearizable executions:") |
| possibleResultsSet.forEach { possibleResults -> |
| printResults(possibleResults) |
| println() |
| } |
| throw AssertionError("Non-linearizable execution detected, see log for details") |
| } |
| } |
| |
| private fun printResults(results: List<List<Result>>) { |
| results.forEachIndexed { index, res -> |
| println("Thread $index: $res") |
| } |
| println("Op map: ${results.toOpMap()}") |
| } |
| |
| private fun valid(results: List<List<Result>>): Boolean = |
| (results in possibleResultsSet) || possibleResultsSet.any { matches(results, it) } |
| |
| private fun matches(results: List<List<Result>>, possible: List<List<Result>>): Boolean = |
| results.toOpMap() == possible.toOpMap() |
| |
| private fun List<List<Result>>.toOpMap(): Map<String, List<Any?>> { |
| val filtered = flatMap { it }.flatMap { it.resultValue }.filter { it.value != CS_STR } |
| return filtered.groupBy({ it.name }, { it.value }) |
| } |
| |
| private fun generateAllLinearizableExecutions(actorsPerThread: List<List<Actor>>): List<List<Actor>> { |
| val executions = ArrayList<List<Actor>>() |
| generateLinearizableExecutions0( |
| executions, actorsPerThread, ArrayList<Actor>(), IntArray(actorsPerThread.size), |
| actorsPerThread.sumBy { it.size }) |
| return executions |
| } |
| |
| @Suppress("UNCHECKED_CAST") |
| private fun generateLinearizableExecutions0(executions: MutableList<List<Actor>>, actorsPerThread: List<List<Actor>>, |
| currentExecution: ArrayList<Actor>, indexes: IntArray, length: Int) { |
| if (currentExecution.size == length) { |
| executions.add(currentExecution.clone() as List<Actor>) |
| return |
| } |
| for (i in indexes.indices) { |
| val actors = actorsPerThread[i] |
| if (indexes[i] == actors.size) |
| continue |
| currentExecution.add(actors[indexes[i]]) |
| indexes[i]++ |
| generateLinearizableExecutions0(executions, actorsPerThread, currentExecution, indexes, length) |
| indexes[i]-- |
| currentExecution.removeAt(currentExecution.size - 1) |
| } |
| } |
| } |
| |
| private val VALUE = Result::class.java.getDeclaredField("value").apply { isAccessible = true } |
| |
| @Suppress("UNCHECKED_CAST") |
| private val Result.resultValue: List<OpResult> |
| get() = VALUE.get(this) as List<OpResult> |