I. State machine
State machine is an ancient computer theory, which is widely used in game development, embedded development, network protocol and other fields.
State machine: It is a directed graph consisting of a set of nodes and a corresponding set of transition functions. A state machine “runs” by responding to a series of events. Each event is within the control of the transition function belonging to the “current” node, where the scope of the function is a subset of the nodes. The function returns the “next” (perhaps the same) node. At least one of these nodes must be in the final state. When the final state is reached, the state machine stops.
Common classification of state machines
FSM
Finite-state machine (FSM), also known as finite-state automata, or state machine for short, is a mathematical model that expresses Finite states and the transfer and action between these states.
The following is an abstract definition of a state machine
- State: The basic unit of a State machine. A state machine can be in a state at any given time. From a lifecycle perspective there is Initial State, End State, Suspend State
- Event: The Event activity that causes the transformation to occur
- Transitions: A directed transition relationship between two states, where the state machine Transitions from A to B after A specific type of event occurs. Standard conversion, selection, sub – process conversion of a variety of abstract implementation
- Actions: Specific Actions that are performed when a transformation is performed.
- Guards (detector) : The reason for the detector is to switch from one state to a certain state after the execution of the operation to whether the detection result meets certain conditions
- Interceptor: intercepts listeners before and after the current status changes.
DFA
To determine finite state automata or to determine finite automata Deterministic Finite Automaton (DFA) is an automaton that can realize state transition. For a given state belonging to the automaton and a character belonging to the alphabet of the automaton, it can transfer to the next state (this state can be the previous state) according to the given transfer function.
DFA is a kind of FSM, and its counterpart is NFA(non-deterministic finite automaton).
DFA features:
- No conflict: A state cannot have more than one rule for the same input, that is, only one transition rule for each input.
- No omissions: Each state must have at least one rule for every possible input character
I used DFA in my previous article, “A Quick Tool to Analyze what SDKS Android Apps Use.”
HSM
Hierarchical State Machine (English: Hierarchical State Machine) is a Hierarchical model in State Machine theory. Each State is organized in a tree hierarchy. The State graph is Hierarchical, that is to say, each State can have sub-states.
When there are too many FSM states, they can be classified and extracted. The same type of state as a state machine, and then a large state machine, to maintain these sub-state machines.
3. FSM developed by Kotlin
Github address: github.com/fengzhizi71…
StateContext
Used to hold an instance of a managed State object, representing the environment in which the State instance resides.
interface StateContext {
fun getEvent(a): BaseEvent
fun getSource(a): BaseState
fun getTarget(a): BaseState
fun getException(a): Exception?
fun setException(exception: Exception)
fun getTransition(a): Transition
}
Copy the codeState
The basic unit of a state machine that can be in a certain state at any given time.
class State(val name: BaseState) {
private val transitions = hashMapOf<BaseEvent, Transition>() // Store all transitions related to the current State
private val stateActions = mutableListOf<StateAction>() // All actions related to the current State
/** * When an Event is distributed by the state machine system, the state machine responds with Action ** State transitions can be represented by F(S, E) -> (A, S ')@paramEvent: triggers the event *@paramTargetState: next state *@paramGuard: Asserts the interface to switch from a state to a state * in order to detect whether the result meets a specific condition after the transition operation is performed@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)) { // One Event cannot correspond to more than one Transition, i.e. State can only be passed from one Event to another State
throw StateMachineException("Adding multiple transitions for the same event is invalid")
}
transitions[event] = transition
return this
}
/** * State Specifies the Action */ to execute
fun action(action: StateAction) {
stateActions.add(action)
}
/** * enter State and execute all actions */
fun enter(a) {
stateActions.forEach {
it.invoke(this)}}/** * Get Transition */ from Event
fun getTransitionForEvent(event: BaseEvent): Transition = transitions[event]? :throw IllegalStateException("Event $event isn't registered with state ${this.name}")
override fun toString(a): String = name.javaClass.simpleName
}
Copy the codeTransition
Switching from one state to another.
class Transition(private val event: BaseEvent, private val sourceState: BaseState, private val targetState: BaseState, private varguard:Guard? =null) {
private val actions = mutableListOf<TransitionAction>()
/** * Whether to convert *@param context
*/
fun transit(context: StateContext): Boolean {
executeTransitionActions(context)
return context.getException() == null
}
/** * Execute Transition Action */
private fun executeTransitionActions(context: StateContext) {
actions.forEach {
try {
it.invoke(this)}catch (e:Exception) {
context.setException(e)
return}}}/** * Add an action to be executed during the state transition (the point in time is before the state transition) */
fun action(action: TransitionAction) {
actions.add(action)
}
/** * Switch state */
fun applyTransition(getNextState: (BaseState) -> State): State = getNextState(targetState)
/** * Set the detection condition to determine whether the condition of state transition is met. If so, perform the state transition */
fun guard(guard: Guard) {
this.guard = guard
}
fun getGuard(a):Guard? = guard
fun getSourceState(a): BaseState = sourceState
fun getTargetState(a): BaseState = targetState
override fun toString(a): String = "${sourceState.javaClass.simpleName} transition to ${targetState.javaClass.simpleName} on ${event.javaClass.simpleName}"
}
Copy the codeImplementation of state machines
class StateMachine private constructor(private val initialState: BaseState) {
private lateinit var currentState: State // Current status
private val states = mutableListOf<State>() // Status list
private val initialized = AtomicBoolean(false) // Whether to initialize
private varglobalInterceptor: GlobalInterceptor? =null
private val transitionCallbacks: MutableList<TransitionCallback> = mutableListOf()
/** * Set the state machine global interceptor, must be used before initialize() *@paramEvent: state machine global interceptor */
fun interceptor(globalInterceptor: GlobalInterceptor):StateMachine {
this.globalInterceptor = globalInterceptor
return this
}
/** * Initializes the state machine and enters the initialization state */
fun initialize(a) {
if(initialized.compareAndSet(false.true)){ currentState = getState(initialState) globalInterceptor? .stateEntered(currentState) currentState.enter() } }/** * Add State */ to the State machine
fun state(stateName: BaseState, init: State. () -> Unit):StateMachine {
val state = State(stateName)
state.init()
states.add(state)
return this
}
/** * Get the status */ from the status name
private fun getState(stateType: BaseState): State = states.firstOrNull { stateType.javaClass == it.name.javaClass } ?: throw NoSuchElementException(stateType.javaClass.canonicalName)
/** * Send Event to state machine to perform state transition */
@Synchronized
fun sendEvent(e: BaseEvent) {
try {
valtransition = currentState.getTransitionForEvent(e) globalInterceptor? .transitionStarted(transition)val stateContext: StateContext = DefaultStateContext(e, transition, transition.getSourceState(), transition.getTargetState())
If the action fails, the event will not be accepted and false will be returned
val accept = transition.transit(stateContext)
if(! accept) {// The state machine is abnormalglobalInterceptor? .stateMachineError(this, StateMachineException("State transition failed,source${currentState.name} -> target ${transition.getTargetState()} Event ${e}"))
return
}
valguard = transition.getGuard()? .invoke()? :true
if (guard) {
val state = transition.applyTransition { getState(stateContext.getTarget()) }
valcallbacks = 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("$transitionFailure") globalInterceptor? .stateMachineError(this, StateMachineException("Guard [${guard}State], [${currentState.name}], events [${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(a): BaseState = this.currentState.name
/** * Register TransitionCallback */
fun registerCallback(transitionCallback: TransitionCallback) = transitionCallbacks.add(transitionCallback)
/** * Cancel 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
}
}
}
Copy the codeStateMachine contains a global GlobalInterceptor and a list of transitionCallbacks.
GlobalInterceptor
Can listen for State, Transition, StateContext, and exceptions.
interface GlobalInterceptor {
/** * enter a State */
fun stateEntered(state: State)
/** * leave a State */
fun stateExited(state: State)
/** * State changed *@paramFrom: Current status *@paramTo: Next state */
fun stateChanged(from: State, to: State)
/** * triggers Transition */
fun transition(transition: Transition)
/**
* 准备开始 Transition
*/
fun transitionStarted(transition: Transition)
/** * Transition end */
fun transitionEnded(transition: Transition)
/** * State machine exception callback */
fun stateMachineError(stateMachine: StateMachine, exception: Exception)
/** * listen to the following text on the status machine */
fun stateContext(stateContext: StateContext)
}
Copy the codeTransitionCallback
You can only listen for changes in the Transition, going into State and leaving State.
interface TransitionCallback {
fun enteringState(
stateMachine: StateMachine,
currentState: BaseState,
transition: Transition,
targetState: BaseState
)
fun enteredState(
stateMachine: StateMachine,
previousState: BaseState,
transition: Transition,
currentState: BaseState
)
}
Copy the codeTypeAliases
Defines actions performed within the state, actions performed by Transition, and assertions about whether Transition is performed.
typealias StateAction = (State) -> Unit
typealias TransitionAction = (Transition) -> Unit
typealias Guard = ()->Boolean
Copy the codeSupport RxJava 2
Through the increase the StateMachine extended attributes enterTransitionObservable, exitTransitionObservable can listen to enter the State, leaving the State changes.
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 }
Copy the code4. The application
As a simple example, use FSM to simulate the user’s initial state, eating state, and finally watching TV state.
fun main(a) {
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())
}
Copy the codeExecution Result:
Entered [Initial] State
Action: Wash Vegetables
Action: Cook
Entered [Eat] State
Action: Wash Dishes
Action: Turn on the TV
Entered [WatchTV] State
Copy the codeIn live.
The main reason for developing an FSM framework was to restructure the company’s projects. Take advantage of the pandemic to take stock of previous projects. Currently we plan to use this FSM for our mobile and back-end projects.
References:
- State machine thinking
- Codereview.stackexchange.com/questions/1…
- Computing in computers I – finite automata