woman-standing-beside-flowers-1853424.jpg
一. 狀態(tài)機
狀態(tài)機是古老的計算機理論，在游戲開發(fā)、嵌入式開發(fā)、網(wǎng)絡(luò)協(xié)議等領(lǐng)域，得到廣泛地使用。
狀態(tài)機：它是一個有向圖形，由一組節(jié)點和一組相應(yīng)的轉(zhuǎn)移函數(shù)組成。狀態(tài)機通過響應(yīng)一系列事件而“運行”。每個事件都在屬于“當前” 節(jié)點的轉(zhuǎn)移函數(shù)的控制范圍內(nèi)，其中函數(shù)的范圍是節(jié)點的一個子集。函數(shù)返回“下一個”（也許是同一個）節(jié)點。這些節(jié)點中至少有一個必須是終態(tài)。當?shù)竭_終態(tài)， 狀態(tài)機停止。
二. 常用的狀態(tài)機分類
FSM
有限狀態(tài)機，（英語：Finite-state machine, FSM），又稱有限狀態(tài)自動機，簡稱狀態(tài)機，是表示有限個狀態(tài)以及在這些狀態(tài)之間的轉(zhuǎn)移和動作等行為的數(shù)學(xué)模型。
以下是對狀態(tài)機抽象定義
- State（狀態(tài)）：構(gòu)成狀態(tài)機的基本單位。 狀態(tài)機在任何特定時間都可處于某一狀態(tài)。從生命周期來看有Initial State、End State、Suspend State(掛起狀態(tài))
- Event（事件）：導(dǎo)致轉(zhuǎn)換發(fā)生的事件活動
- Transitions（轉(zhuǎn)換器）：兩個狀態(tài)之間的定向轉(zhuǎn)換關(guān)系，狀態(tài)機對發(fā)生的特定類型事件響應(yīng)后當前狀態(tài)由A轉(zhuǎn)換到B。標準轉(zhuǎn)換、選擇轉(zhuǎn)、子流程轉(zhuǎn)換多種抽象實現(xiàn)
- Actions（轉(zhuǎn)換操作）：在執(zhí)行某個轉(zhuǎn)換時執(zhí)行的具體操作。
- Guards（檢測器）：檢測器出現(xiàn)的原因是為了轉(zhuǎn)換操作執(zhí)行后檢測結(jié)果是否滿足特定條件從一個狀態(tài)切換到某一個狀態(tài)
- Interceptor（攔截器）：對當前狀態(tài)改變前、后進行監(jiān)聽攔截。
狀態(tài)表.jpg
DFA
確定有限狀態(tài)自動機或確定有限自動機（英語：deterministic finite automaton, DFA）是一個能實現(xiàn)狀態(tài)轉(zhuǎn)移的自動機對于一個給定的屬于該自動機的狀態(tài)和一個屬于該自動機字母表的字符，它都能根據(jù)事先給定的轉(zhuǎn)移函數(shù)轉(zhuǎn)移到下一個狀態(tài)（這個狀態(tài)可以是先前那個狀態(tài)）。
DFA 是 FSM 的一種，與 DFA 對應(yīng)的還有 NFA(非確定性有限自動機)。
DFA 的特性：
- 沒有沖突：一個狀態(tài)對于同樣的輸入，不能有多個規(guī)則，即每個輸入只能有一個轉(zhuǎn)移規(guī)則；
- 沒有遺漏：每個狀態(tài)都必須針對每個可能的輸入字符有至少一個規(guī)則
以前我寫過的一篇文章《一個快速分析android app使用了哪些sdk的工具》 曾經(jīng)使用過DFA。
HSM
層次狀態(tài)機(英語：Hierarchical State Machine)是狀態(tài)機理論中的一種層次結(jié)構(gòu)的模型，各個狀態(tài)按照樹狀層次結(jié)構(gòu)組織起來，狀態(tài)圖是層次結(jié)構(gòu)的，也就是說每個狀態(tài)可以擁有子狀態(tài)。
當 FSM 狀態(tài)太多的時候，可以將狀態(tài)分類，并抽離出來。同類型的狀態(tài)做為一個狀態(tài)機，然后再做一個大的狀態(tài)機，來維護這些子狀態(tài)機。
三. Kotlin 開發(fā)的 FSM
github 地址：https://github.com/fengzhizi715/KStateMachine
StateContext
用于保存管理 State 對象實例，表示 State 實例所處的環(huán)境。
interface StateContext {
fun getEvent(): BaseEvent
fun getSource(): BaseState
fun getTarget(): BaseState
fun getException(): Exception?
fun setException(exception: Exception)
fun getTransition(): Transition
}
State
構(gòu)成狀態(tài)機的基本單位，狀態(tài)機在任何特定時間都可處于某一狀態(tài)。
class State(val name: BaseState) {
private val transitions = hashMapOf<BaseEvent, Transition>() // 存儲當前 State 相關(guān)的所有 Transition
private val stateActions = mutableListOf<StateAction>() // 當前 State 相關(guān)的所有 Action
/**
* 當一個 Event 被狀態(tài)機系統(tǒng)分發(fā)的時候，狀態(tài)機用 Action 來進行響應(yīng)
* 狀態(tài)轉(zhuǎn)換可以使用 F(S, E) -> (A, S’) 表示
*
* @param event: 觸發(fā)事件
* @param targetState: 下一個狀態(tài)
* @param guard: 斷言接口，為了轉(zhuǎn)換操作執(zhí)行后檢測結(jié)果是否滿足特定條件從一個狀態(tài)切換到某一個狀態(tài)
* @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 不能對應(yīng)多個 Transition，即 State 只能通過一個 Event 然后 Transition 到另一個 State
throw StateMachineException("Adding multiple transitions for the same event is invalid")
}
transitions[event] = transition
return this
}
/**
* State 執(zhí)行的 Action
*/
fun action(action: StateAction) {
stateActions.add(action)
}
/**
* 進入 State 并執(zhí)行所有的 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
從一個狀態(tài)切換到另一個狀態(tài)。
class Transition(private val event: BaseEvent, private val sourceState: BaseState, private val targetState: BaseState, private var guard:Guard?= null) {
private val actions = mutableListOf<TransitionAction>()
/**
* 是否轉(zhuǎn)換
* @param context
*/
fun transit(context: StateContext): Boolean {
executeTransitionActions(context)
return context.getException() == null
}
/**
* 執(zhí)行 Transition 的 Action
*/
private fun executeTransitionActions(context: StateContext) {
actions.forEach {
try {
it.invoke(this)
} catch (e:Exception) {
context.setException(e)
return
}
}
}
/**
* 添加一個 action，在狀態(tài)轉(zhuǎn)換時執(zhí)行(時間點是在狀態(tài)轉(zhuǎn)換之前)
*/
fun action(action: TransitionAction) {
actions.add(action)
}
/**
* 轉(zhuǎn)換狀態(tài)
*/
fun applyTransition(getNextState: (BaseState) -> State): State = getNextState(targetState)
/**
* 設(shè)置檢測條件，判斷是否滿足狀態(tài)轉(zhuǎn)換的條件，滿足則執(zhí)行狀態(tài)轉(zhuǎn)換
*/
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}"
}
狀態(tài)機的實現(xiàn)
class StateMachine private constructor(private val initialState: BaseState) {
private lateinit var currentState: State // 當前狀態(tài)
private val states = mutableListOf<State>() // 狀態(tài)列表
private val initialized = AtomicBoolean(false) // 是否初始化
private var globalInterceptor: GlobalInterceptor?=null
private val transitionCallbacks: MutableList<TransitionCallback> = mutableListOf()
/**
* 設(shè)置狀態(tài)機全局的攔截器，使用時必須要在 initialize() 之前
* @param event: 狀態(tài)機全局的攔截器
*/
fun interceptor(globalInterceptor: GlobalInterceptor):StateMachine {
this.globalInterceptor = globalInterceptor
return this
}
/**
* 初始化狀態(tài)機，并進入初始化狀態(tài)
*/
fun initialize() {
if(initialized.compareAndSet(false, true)){
currentState = getState(initialState)
globalInterceptor?.stateEntered(currentState)
currentState.enter()
}
}
/**
* 向狀態(tài)機添加 State
*/
fun state(stateName: BaseState, init: State.() -> Unit):StateMachine {
val state = State(stateName)
state.init()
states.add(state)
return this
}
/**
* 通過狀態(tài)名稱獲取狀態(tài)
*/
private fun getState(stateType: BaseState): State = states.firstOrNull { stateType.javaClass == it.name.javaClass } ?: throw NoSuchElementException(stateType.javaClass.canonicalName)
/**
* 向狀態(tài)機發(fā)送 Event，執(zhí)行狀態(tài)轉(zhuǎn)換
*/
@Synchronized
fun sendEvent(e: BaseEvent) {
try {
val transition = currentState.getTransitionForEvent(e)
globalInterceptor?.transitionStarted(transition)
val stateContext: StateContext = DefaultStateContext(e, transition, transition.getSourceState(), transition.getTargetState())
//狀態(tài)轉(zhuǎn)換之前執(zhí)行的 action(Transition 內(nèi)部的 action), action執(zhí)行失敗表示不接受事件，返回false
val accept = transition.transit(stateContext)
if (!accept) {
//狀態(tài)機發(fā)生異常
globalInterceptor?.stateMachineError(this, StateMachineException("狀態(tài)轉(zhuǎn)換失敗,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("狀態(tài)轉(zhuǎn)換時 guard [${guard}], 狀態(tài) [${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
能夠監(jiān)聽 State、Transition、StateContext 以及異常。
interface GlobalInterceptor {
/**
* 進入某個 State
*/
fun stateEntered(state: State)
/**
* 離開某個 State
*/
fun stateExited(state: State)
/**
* State 發(fā)生改變
* @param from: 當前狀態(tài)
* @param to: 下一個狀態(tài)
*/
fun stateChanged(from: State, to: State)
/**
* 觸發(fā) Transition
*/
fun transition(transition: Transition)
/**
* 準備開始 Transition
*/
fun transitionStarted(transition: Transition)
/**
* Transition 結(jié)束
*/
fun transitionEnded(transition: Transition)
/**
* 狀態(tài)機異常的回調(diào)
*/
fun stateMachineError(stateMachine: StateMachine, exception: Exception)
/**
* 監(jiān)聽狀態(tài)機上下文
*/
fun stateContext(stateContext: StateContext)
}
TransitionCallback
只能監(jiān)聽 Transition 發(fā)生的變化，也就是進入 State、離開 State。
interface TransitionCallback {
fun enteringState(
stateMachine: StateMachine,
currentState: BaseState,
transition: Transition,
targetState: BaseState
)
fun enteredState(
stateMachine: StateMachine,
previousState: BaseState,
transition: Transition,
currentState: BaseState
)
}
TypeAliases
定義了狀態(tài)內(nèi)部執(zhí)行的 action、Transition 執(zhí)行的 action、以及是否執(zhí)行 Transition 的斷言。
typealias StateAction = (State) -> Unit
typealias TransitionAction = (Transition) -> Unit
typealias Guard = ()->Boolean
支持 RxJava 2
通過對 StateMachine 增加擴展屬性 enterTransitionObservable、exitTransitionObservable 可以監(jiān)聽到進入 State、離開 State 發(fā)生的變化。
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 }
四. 應(yīng)用
舉一個簡單的例子，用 FSM 來模擬用戶從初始狀態(tài)，到吃飯的狀態(tài)，最后到看電視的狀態(tài)。
demo.png
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())
}
執(zhí)行結(jié)果：
Entered [Initial] State
Action: Wash Vegetables
Action: Cook
Entered [Eat] State
Action: Wash Dishes
Action: Turn on the TV
Entered [WatchTV] State
五. 總結(jié)
之所以開發(fā)一款 FSM 框架，主要是為了重構(gòu)公司的項目。趁疫情期間正好把以前的項目捋一捋。目前打算將這個 FSM 應(yīng)用在我們的移動端和后端的項目上。
參考資料：
