concurrent-composition.kt

interface State {
    val subStates: List<State>
}

interface Event

data class Transition(val event: Event, val state: State) {
    override fun toString() = "$event -> $state"
}

// 状態遷移表 `Map<State, Set<Transition>>` をプロセスと捉える
// scratch バッファだと typealias が使えないので……
val Map<State, Set<Transition>>.initialState get() = keys.first()

fun concurrentComposition(
    syncEvents: Set<Event>,
    processes: List<Map<State, Set<Transition>>>
): Map<State, Set<Transition>> {

    data class CompositeState(override val subStates: List<State>) : State {
        override fun toString() = "(${subStates.joinToString("||")})"
    }

    val result = mutableMapOf<State, Set<Transition>>()
    val initialState = processes.map { it.initialState }
    val frontier: MutableSet<State> = mutableSetOf(CompositeState(initialState))

    while (frontier.isNotEmpty()) {
        val newTransitions = mutableSetOf<Transition>()
        val state = frontier.popFirst()
        val transitionSet = state.subStates.zip(processes) { s, p -> p[s] ?: setOf() }

        // 同期イベントによる遷移を展開する
        syncEvents.forEach { event ->
            // event での全遷移の組み合わせを追加
            transitionSet
                .map { transitions -> transitions.filter { it.event == event }.map { it.state } }
                .directProduct()
                .map(::CompositeState)
                .map { Transition(event, it) }
                .let { newTransitions += it }
        }

        // 非同期イベントの遷移を展開する（インターリーブ）
        transitionSet
            // 同期イベント集合に含まれない遷移を対象にする
            .map { it.filterNot { transition -> syncEvents.contains(transition.event) } }
            .mapIndexed { i, asyncTransitions -> asyncTransitions.map { i to it } }
            .flatten()
            .forEach { (i, transition) ->
                state.subStates.altered(i, transition.state)
                    .let(::CompositeState)
                    .let { Transition(transition.event, it) }
                    .let { newTransitions += it }
            }

        result[state] = result.getOrDefault(state, setOf()) + newTransitions
        frontier.addAll(newTransitions.map { it.state } - result.keys)
    }

    return result
}

fun <E> MutableCollection<E>.popFirst() = first().also { remove(it) }

fun <E> List<E>.altered(atIndex: Int, byValue: E) = take(atIndex) + byValue + drop(atIndex + 1)

fun <E> Collection<Collection<E>>.directProduct(): List<List<E>> =
    if (isEmpty()) {
        listOf()
    } else {
        val (head, rest) = first() to drop(1)
        head.map(::listOf).let {
            if (rest.isEmpty())
                it
            else
                rest.directProduct().flatMap { tail -> it.map { h -> h + tail } }
        }
    }

fun Map<State, Set<Transition>>.printDot() = buildDot(initialState, this).let(::println)

fun buildDot(initial: State, graph: Map<State, Set<Transition>>): String {
    val states = graph.keys
    val nodes = states.mapIndexed { index: Int, vars: State ->
        val attr = if (graph.getValue(vars).isEmpty()) "filled" else if (vars == initial) "bold" else "solid"
        "$index [label=\"$vars\" style=$attr]"
    }.joinToString(";\n  ")
    val edges = graph.entries.flatMap {
        val start = states.indexOf(it.key)
        it.value.map { arrow ->
            val (name, state) = arrow
            val end = states.indexOf(state)
            "$start -> $end [label=\"$name\"]"
        }
    }.joinToString(";\n  ")
    return "digraph {\n  $nodes;\n  $edges;\n}"
}