1. Государственный автомат
Конечный автомат — это древняя компьютерная теория, которая широко используется в разработке игр, встраиваемых систем, сетевых протоколов и других областях.
State Machine: это ориентированный граф, состоящий из набора узлов и набора соответствующих функций перехода. Конечный автомат «запускается» в ответ на серию событий. Каждое событие находится в пределах области управления функции перехода, принадлежащей «текущему» узлу, где областью действия функции является подмножество узла. Функция возвращает «следующий» (возможно, тот же) узел. По крайней мере один из этих узлов должен быть в конечном состоянии. При достижении конечного состояния конечный автомат останавливается.
2. Обычно используемая классификация конечных автоматов
FSM
Конечный автомат (английский: Finite-state machine, FSM), также известный как конечный автомат или, для краткости, конечный автомат, представляет собой математическую модель, которая представляет конечное число состояний и поведений, таких как переходы и действия между этими состояниями. состояния.
Ниже приводится абстрактное определение конечного автомата.
- Состояние: основная единица, составляющая конечный автомат. Конечный автомат может находиться в состоянии в любой момент времени. С точки зрения жизненного цикла есть начальное состояние, конечное состояние, состояние приостановки (состояние приостановки).
- Событие: действие события, вызвавшее переход.
- Переходы: отношения направленного перехода между двумя состояниями.Текущее состояние переходит из A в B после того, как конечный автомат реагирует на событие определенного типа. Различные абстрактные реализации стандартного преобразования, преобразования выбора и преобразования подпроцесса.
- Действия: определенные действия, которые необходимо выполнить при выполнении определенного перехода.
- Охранники (детектор): причиной появления детектора является переход из состояния в определенное состояние после выполнения операции перехода, чтобы определить, соответствует ли результат определенным условиям.
- Перехватчик: Отслеживайте и перехватывайте текущее состояние до и после изменения.
DFA
Детерминированный конечный автомат или детерминированный конечный автомат (DFA) — это автомат, который может осуществлять переходы между состояниями для заданного состояния, принадлежащего автомату, и символа, принадлежащего автоматному алфавиту. Он может переходить в следующее состояние (это состояние может быть предыдущее состояние) в соответствии с заранее заданной функцией перехода.
DFA — это разновидность FSM, а NFA (недетерминированный конечный автомат) соответствует DFA.
Особенности ДФА:
- Отсутствие конфликта: состояние не может иметь несколько правил для одного и того же входа, то есть каждый вход может иметь только одно правило перехода;
- Никаких упущений: каждое состояние должно иметь хотя бы одно правило для каждого возможного входного символа.
Статья, которую я написал раньше«Инструмент для быстрого анализа того, какие SDK используются приложениями для Android»Раньше использовали DFA.
HSM
Hierarchical State Machine (англ. Hierarchical State Machine) — модель иерархической структуры в теории конечных автоматов. Каждое состояние организовано в соответствии с древовидной иерархией. Диаграмма состояний иерархична, то есть каждое состояние может иметь подсистемы. государства.
Когда состояний FSM слишком много, состояния можно классифицировать и извлечь. Тот же тип состояния используется в качестве конечного автомата, а затем создается большой конечный автомат для поддержки этих подмашин.
3. FSM, разработанный Kotlin
адрес гитхаба:GitHub.com/Zonda71…
StateContext
Используется для сохранения и управления экземплярами объекта State, представляющего среду, в которой находится экземпляр State.
interface StateContext {
fun getEvent(): BaseEvent
fun getSource(): BaseState
fun getTarget(): BaseState
fun getException(): Exception?
fun setException(exception: Exception)
fun getTransition(): Transition
}
State
Базовая единица, составляющая конечный автомат, который может находиться в определенном состоянии в любой момент времени.
class State(val name: BaseState) {
private val transitions = hashMapOf<BaseEvent, Transition>() // 存储当前 State 相关的所有 Transition
private val stateActions = mutableListOf<StateAction>() // 当前 State 相关的所有 Action
/**
* 当一个 Event 被状态机系统分发的时候，状态机用 Action 来进行响应
* 状态转换可以使用 F(S, E) -> (A, S’) 表示
*
* @param event: 触发事件
* @param targetState: 下一个状态
* @param guard: 断言接口，为了转换操作执行后检测结果是否满足特定条件从一个状态切换到某一个状态
* @param init
*/
fun transition(event: BaseEvent, targetState: BaseState, guard: Guard?=null, init: Transition.() -> Unit):State {
val transition = Transition(event, this.name, targetState, guard)
transition.init()
if (transitions.containsKey(event)) { // 同一个 Event 不能对应多个 Transition，即 State 只能通过一个 Event 然后 Transition 到另一个 State
throw StateMachineException("Adding multiple transitions for the same event is invalid")
}
transitions[event] = transition
return this
}
/**
* State 执行的 Action
*/
fun action(action: StateAction) {
stateActions.add(action)
}
/**
* 进入 State 并执行所有的 Action
*/
fun enter() {
stateActions.forEach {
it.invoke(this)
}
}
/**
* 通过 Event 获取 Transition
*/
fun getTransitionForEvent(event: BaseEvent): Transition = transitions[event]?:throw IllegalStateException("Event $event isn't registered with state ${this.name}")
override fun toString(): String = name.javaClass.simpleName
}
Transition
Переключение из одного состояния в другое.
class Transition(private val event: BaseEvent, private val sourceState: BaseState, private val targetState: BaseState, private var guard:Guard?= null) {
private val actions = mutableListOf<TransitionAction>()
/**
* 是否转换
* @param context
*/
fun transit(context: StateContext): Boolean {
executeTransitionActions(context)
return context.getException() == null
}
/**
* 执行 Transition 的 Action
*/
private fun executeTransitionActions(context: StateContext) {
actions.forEach {
try {
it.invoke(this)
} catch (e:Exception) {
context.setException(e)
return
}
}
}
/**
* 添加一个 action，在状态转换时执行(时间点是在状态转换之前)
*/
fun action(action: TransitionAction) {
actions.add(action)
}
/**
* 转换状态
*/
fun applyTransition(getNextState: (BaseState) -> State): State = getNextState(targetState)
/**
* 设置检测条件，判断是否满足状态转换的条件，满足则执行状态转换
*/
fun guard(guard: Guard) {
this.guard = guard
}
fun getGuard():Guard? = guard
fun getSourceState(): BaseState = sourceState
fun getTargetState(): BaseState = targetState
override fun toString(): String = "${sourceState.javaClass.simpleName} transition to ${targetState.javaClass.simpleName} on ${event.javaClass.simpleName}"
}
Реализация конечного автомата
class StateMachine private constructor(private val initialState: BaseState) {
private lateinit var currentState: State // 当前状态
private val states = mutableListOf<State>() // 状态列表
private val initialized = AtomicBoolean(false) // 是否初始化
private var globalInterceptor: GlobalInterceptor?=null
private val transitionCallbacks: MutableList<TransitionCallback> = mutableListOf()
/**
* 设置状态机全局的拦截器，使用时必须要在 initialize() 之前
* @param event: 状态机全局的拦截器
*/
fun interceptor(globalInterceptor: GlobalInterceptor):StateMachine {
this.globalInterceptor = globalInterceptor
return this
}
/**
* 初始化状态机，并进入初始化状态
*/
fun initialize() {
if(initialized.compareAndSet(false, true)){
currentState = getState(initialState)
globalInterceptor?.stateEntered(currentState)
currentState.enter()
}
}
/**
* 向状态机添加 State
*/
fun state(stateName: BaseState, init: State.() -> Unit):StateMachine {
val state = State(stateName)
state.init()
states.add(state)
return this
}
/**
* 通过状态名称获取状态
*/
private fun getState(stateType: BaseState): State = states.firstOrNull { stateType.javaClass == it.name.javaClass } ?: throw NoSuchElementException(stateType.javaClass.canonicalName)
/**
* 向状态机发送 Event，执行状态转换
*/
@Synchronized
fun sendEvent(e: BaseEvent) {
try {
val transition = currentState.getTransitionForEvent(e)
globalInterceptor?.transitionStarted(transition)
val stateContext: StateContext = DefaultStateContext(e, transition, transition.getSourceState(), transition.getTargetState())
//状态转换之前执行的 action(Transition 内部的 action), action执行失败表示不接受事件，返回false
val accept = transition.transit(stateContext)
if (!accept) {
//状态机发生异常
globalInterceptor?.stateMachineError(this, StateMachineException("状态转换失败,source ${currentState.name} -> target ${transition.getTargetState()} Event ${e}"))
return
}
val guard = transition.getGuard()?.invoke()?:true
if (guard) {
val state = transition.applyTransition { getState(stateContext.getTarget()) }
val callbacks = transitionCallbacks.toList()
globalInterceptor?.apply {
stateContext(stateContext)
transition(transition)
stateExited(currentState)
}
callbacks.forEach { callback ->
callback.enteringState(this, stateContext.getSource(), transition, stateContext.getTarget())
}
state.enter()
callbacks.forEach { callback ->
callback.enteredState(this, stateContext.getSource(), transition, stateContext.getTarget())
}
globalInterceptor?.apply {
stateEntered(state)
stateChanged(currentState,state)
transitionEnded(transition)
}
currentState = state
} else {
println("$transition 失败")
globalInterceptor?.stateMachineError(this, StateMachineException("状态转换时 guard [${guard}], 状态 [${currentState.name}]，事件 [${e.javaClass.simpleName}]"))
}
} catch (exception:Exception) {
globalInterceptor?.stateMachineError(this, StateMachineException("This state [${this.currentState.name}] doesn't support transition on ${e.javaClass.simpleName}"))
}
}
@Synchronized
fun getCurrentState(): BaseState = this.currentState.name
/**
* 注册 TransitionCallback
*/
fun registerCallback(transitionCallback: TransitionCallback) = transitionCallbacks.add(transitionCallback)
/**
* 取消 TransitionCallback
*/
fun unregisterCallback(transitionCallback: TransitionCallback) = transitionCallbacks.remove(transitionCallback)
companion object {
fun buildStateMachine(initialStateName: BaseState, init: StateMachine.() -> Unit): StateMachine {
val stateMachine = StateMachine(initialStateName)
stateMachine.init()
return stateMachine
}
}
}
В StateMachine содержит глобальный GlobalInterceptor и список TransitionCallback.
GlobalInterceptor
Возможность прослушивания State, Transition, StateContext и исключений.
interface GlobalInterceptor {
/**
* 进入某个 State
*/
fun stateEntered(state: State)
/**
* 离开某个 State
*/
fun stateExited(state: State)
/**
* State 发生改变
* @param from: 当前状态
* @param to: 下一个状态
*/
fun stateChanged(from: State, to: State)
/**
* 触发 Transition
*/
fun transition(transition: Transition)
/**
* 准备开始 Transition
*/
fun transitionStarted(transition: Transition)
/**
* Transition 结束
*/
fun transitionEnded(transition: Transition)
/**
* 状态机异常的回调
*/
fun stateMachineError(stateMachine: StateMachine, exception: Exception)
/**
* 监听状态机上下文
*/
fun stateContext(stateContext: StateContext)
}
TransitionCallback
Вы можете только следить за изменениями в Transition, то есть входить и выходить из State.
interface TransitionCallback {
fun enteringState(
stateMachine: StateMachine,
currentState: BaseState,
transition: Transition,
targetState: BaseState
)
fun enteredState(
stateMachine: StateMachine,
previousState: BaseState,
transition: Transition,
currentState: BaseState
)
}
TypeAliases
Определяет действия, выполняемые внутри состояния, действия, выполняемые переходом, и утверждение о том, следует ли выполнять переход.
typealias StateAction = (State) -> Unit
typealias TransitionAction = (Transition) -> Unit
typealias Guard = ()->Boolean
Поддержка RxJava 2
Добавляя расширенные атрибуты enterTransitionObservable и exitTransitionObservable в StateMachine, вы можете отслеживать изменения, происходящие при входе и выходе из состояния.
val StateMachine.stateObservable: Observable<TransitionEvent>
get() = Observable.create { emitter ->
val rxCallback = RxStateCallback(emitter)
registerCallback(rxCallback)
emitter.setCancellable {
unregisterCallback(rxCallback)
}
}
val StateMachine.enterTransitionObservable: Observable<TransitionEvent.EnterTransition>
get() = stateObservable
.filter { event -> event is TransitionEvent.EnterTransition }
.map { event -> event as TransitionEvent.EnterTransition }
val StateMachine.exitTransitionObservable: Observable<TransitionEvent.ExitTransition>
get() = stateObservable
.filter { event -> event is TransitionEvent.ExitTransition }
.map { event -> event as TransitionEvent.ExitTransition }
4. Применение
Чтобы привести простой пример, используйте FSM для имитации пользователя от начального состояния до состояния еды и, наконец, до состояния просмотра телевизора.
fun main() {
val sm = StateMachine.buildStateMachine(Initial()) {
state(Initial()) {
action {
println("Entered [$it] State")
}
transition(Cook(), Eat()) {
action {
println("Action: Wash Vegetables")
}
action {
println("Action: Cook")
}
}
}
state(Eat()) {
action {
println("Entered [$it] State")
}
transition(WashDishes(), WatchTV()) {
action {
println("Action: Wash Dishes")
}
action {
println("Action: Turn on the TV")
}
}
}
state(WatchTV()) {
action {
println("Entered [$it] State")
}
}
}
sm.initialize()
sm.sendEvent(Cook())
sm.sendEvent(WashDishes())
}
Результаты:
Entered [Initial] State
Action: Wash Vegetables
Action: Cook
Entered [Eat] State
Action: Wash Dishes
Action: Turn on the TV
Entered [WatchTV] State
V. Резюме
Основной причиной разработки FSM-фреймворка является реструктуризация проектов компании. Воспользуйтесь эпидемией, чтобы воспользоваться предыдущими проектами. В настоящее время мы планируем применить этот FSM к нашим мобильным и серверным проектам.
Использованная литература: