prologue
What is a state machine?
Let’s just use the definition from wikiPedia:
A finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine, is a mathematical model of computation.
In short: what we commonly call a state machine is short for a finite state machine, a mathematical model of computation.
Finite state machines (also known as finite automata), if there is a classification, it is as follows:
This figure only looks at a general classification. In fact, it has a simple cognition, because the type we want to discuss is mainly DFA(Deterministic Finite Automaton) : Deterministic Finite state Automaton. It is also the simplest state machine model. What we refer to as state machines in the following are deterministic finite state automata.
Note: There are various types of categorization, and the classification is based on whether there is output or not. Wikipedia’s classification method is not consistent with this classification, so you can refer to it.
So what are the characteristics of deterministic finite state automata? Simply speaking, the change of state caused by each input is determined, that is, a state can only have one transformation rule for the same input.
Start with a simple state machine model
Many people swipe their cards to get in and out of the subway every day to get to work. Let’s take the turnstiles as an example.
The gate is initially in a “locked” state, in which it does not allow passengers to spin the barriers through the entrance. When someone swipes a card, the gate becomes “unlocked,” but it doesn’t turn around on its own. It has to wait until someone pushes the revolving fence through the gate, after which the gate becomes “locked” again.
In the above description, you can see that the gate is always in one of two states: Locked or Unlocked. And there are only two trigger conditions for conversion: swiping a card or going through a rotating fence.
Next, we can model the gate system graphically, using rounded rectangles to represent states and arrows to represent transitions between states:
The above system Outlines how the system works, but there are some scenarios that the system cannot clearly define. For example, if you swipe your card and then swipe it again, how does the status change? For example, if someone is going through the rotation bar before swiping the card, how does the status change? In both cases, the state machine we built will remain in its current state.
We also need to add an initial state to the system so that we can continue to refine the model:
Definition of finite state machine
The above model is a simple state machine model. Based on this, we can summarize several key characteristics of the system:
- This system contains a finite number of states
- The system contains a limited number of inputs (or events) that can trigger transitions between states
- The system has a specific initial state
- The behavior of the system at any given moment depends on the current state and the current input
- For every state the system can be in, every input (or event) has the right behavior
• The system must be describable by a finite set of states.
• The system must have a finite set of inputs and/or events that can trigger transitions between states.
• The system has a particular initial state
• The behavior of The system at a given point in time depends upon The current state and The input or event that occurs at that time.
• For each state the system may be in, behavior is defined for each possible input or event.
At this point we have enough definitions, some theories, but not enough. As engineers, we usually need to use a more formal, or more mathematical, way of describing the system. A finite automaton M is usually defined by a quintuple (σ, Q, q0, F, δ) :
- σ is the set of symbols representing input to M
- Q is the set of states of M
- Q0 ∈ Q is the start state of M
- F infq is the set of final states of M
- Q × σ → Q is the transition function
In simple terms, the quintuple is (input, state set, initial state, result state set, transition method). Its parameters are the current state and its inputs and outputs are the resulting states δ(q, x) = p. A finite state machine M is in state Q, receives input from X, and changes to state P after processing the Action in the transition process.
The abstraction of this transformation method will be especially important when we customize the state machine.
In the chapter
The simplest way to implement a state machine is to use enumerated classes and swtich-Case statements, but we will not use that approach today. Instead, we will try to define a state machine in two different ways.
How to Implement State Machine – Object Oriented (OOP)
Basic abstraction
The first way is to use OOP to create a general purpose state machine. The first thing to consider is what classes can be abstracted out? Combined with the quintuple above, the abstraction is as follows:
protocol Event: Hashable { }
class State<E: Event> {
}
class StateMachine<E: Event> {
}
Copy the codeThe first is events: since state transitions need to be triggered by events, the Event set is defined here as an Event protocol, which is then used by whoever defines the corresponding Event enumeration.
The second is state: here, the Transition Function in the quintuple is encapsulated into the state class, and the state class itself directly manages the transformation behavior.
The third is the state machine: this is similar to the view Controller in MVC, which is the center of the state machine and needs to manage the state switch.
The above is the infrastructure of the state machine model DEFINED by me. What is our overall design idea?
The state machine class accepts event firing
2. Pass the event to the current state, which triggers the event
3. After the event is triggered: If you need to jump to another state, the current state leaves while the target state enters
The design is very simple, so let’s look at the implementation.
State class
class State<E: Event> { weak open var stateMachine: StateMachine<E>? open func trigger(event: E) {} open func enter() { stateMachine? .currentState = self } open func exit() { } }Copy the codeHere’s what it looks like:
- State machine properties
When the state machine receives an event, the current state needs to call the state machine to enter the target state after the event judgment.
- The trigger condition
Transition! The current state accepts that every transition of an input event will be registered here.
- The Transition method
Specifically, the exit method of the current state and the entry method of the target state.
A state machine class
class StateMachine<E: Event> {
typealias FSMState = State<E>
open var currentState: FSMState!
private var states: [FSMState] = []
init(initialState: FSMState) {
currentState = initialState
}
open func setupStates(_states: [FSMState]) {
states = _states
states.forEach { $0.stateMachine = self }
}
open func trigger(event: E) {
currentState.trigger(event: event)
}
open func enter(_ stateClass: AnyClass) {
states.forEach {
if type(of: $0) == stateClass {
$0.enter()
}
}
}
}
Copy the codeSo let’s analyze what we need:
- A constructor
For the state machine class, we need to give it an initial state, so that its constructor takes an initial state parameter.
- The state sets
Because a state machine needs to manage transitions between states, it needs to store those states.
- Triggering method
When an external event is triggered, the state machine triggers the event detection method for the current state, because here we have each state internally complete the corresponding transition rules for different inputs.
- Transition state method
When entering a new state, according to the above design, we need to handle the method of entering the new state through the state machine class.
How to use it?
When I go to think what the software may be using a state machine, the first reaction is to the game, because the game in a role in a variety of state, if it is to use the if – else that would be too cumbersome, this time, through the state machine to control the change of state must be the optimal solution, such as idle state, walk, run, Attack state, hurt state, etc.
So let’s just use a simple example, with two buttons to control the state switch between walk and Run.
So you define events first
enum RoleEvent: Event {
case clickRunButton
case clickWalkButton
}
Copy the codeTo define the state, here we define RunState and WalkState:
class RunState: State<RoleEvent> { override func trigger(event: RoleEvent) { super.trigger(event: event) switch event { case .clickRunButton: break case .clickWalkButton: self.exit() stateMachine? .enter(WalkState.self) } } override func enter() { super.enter() NSLog("====run enter=====") } override func exit() { super.exit() NSLog("====run exit=====") } } class WalkState: State<RoleEvent> { override func trigger(event: RoleEvent) { super.trigger(event: event) switch event { case .clickRunButton: self.exit() stateMachine? .enter(RunState.self) case .clickWalkButton: break } } override func enter() { super.enter() NSLog("====walk enter=====") } override func exit() { super.exit() NSLog("====walk exit=====") } }Copy the codeFinally, initialization:
func initialStateMachine() {
let run = RunState.init()
let walk = WalkState.init()
stateMachine = StateMachine.init(initialState: run)
stateMachine.setupStates(_states: [run, walk])
}
Copy the codeStateMachine triggers different events:
stateMachine.trigger(event: .clickRunButton)
// stateMachine.trigger(event: .clickWalkButton)
Copy the codeHow to implement the state machine-functional formula
Stateful was a lightweight framework for implementing a more Swift style state machine.
Transition
Let’s get out of OOP and think back to the mathematical definition of deterministic finite automata, and the key thing is transition function, so let’s abstract the transition into a structure that contains all the elements of a transformation rule.
public typealias ExecutionBlock = (() -> Void) public struct Transition<State, Event> { public let event: Event public let source: State public let destination: State let preAction: ExecutionBlock? let postAction: ExecutionBlock? public init(with event: Event, from: State, to: State, preBlock: ExecutionBlock? , postBlock: ExecutionBlock?) { self.event = event self.source = from self.destination = to self.preAction = preBlock self.postAction = postBlock } func executePreAction() { preAction?() } func executePostAction() { postAction?() } }Copy the codeIf you look at this code, you’ll see that we encapsulate the Transition event, the start state, the end state, and the actions that need to be performed during the Transition.
Now, a simple math problem, given three states and four events, what is the maximum number of Transition instances you need?
State Machine
To keep the thread safe, we will use three queues and, consistent with the above state machine, we will set an initialization state:
class StateMachine<State, Event> {
public var currentState: State {
return {
workingQueue.sync {
return internalCurrentState
}
}()
}
private var internalCurrentState: State
private let lockQueue: DispatchQueue
private let workingQueue: DispatchQueue
private let callbackQueue: DispatchQueue
public init(initialState: State, callbackQueue: DispatchQueue? = nil) {
self.internalCurrentState = initialState
self.lockQueue = DispatchQueue(label: "com.statemachine.queue.lock")
self.workingQueue = DispatchQueue(label: "com.statemachine.queue.working")
self.callbackQueue = callbackQueue ?? .main
}
}
Copy the codeThe transition event is handled in the main queue by default, but you can also define a queue and pass it in at initialization, called the callbackQueue.
The next step is to register the status table. Here we use a dictionary:
private var transitionsByEvent: [Event : [Transition<State, Event>]] = [:]
Copy the codeWhy is there a dictionary here?
This should be easy to understand because the State machine accepts the Event, and then queries whether there is a corresponding Transition based on the current State and Event. If there is a Transition, the relevant processing is performed, and if there is no Transition, it is not executed. Since each Event corresponds to a group of transitions, the dictionary Value should be an array of transitions.
Register the Transition
public func add(transition: Transition<State, Event>) { lockQueue.sync { if let transitions = self.transitionsByEvent[transition.event] { if (transitions.filter { return $0.source == transition.source }.count > 0) { assertionFailure("Transition with event '(transition.event)' and source '(transition.source)' already existing.") } self.transitionsByEvent[transition.event]? .append(transition) } else { self.transitionsByEvent[transition.event] = [transition] } } }Copy the codeVery simple, use a serial queue to implement a read/write lock, keep thread safe.
Accept the Event
After registering the state table, all that remains is to accept the corresponding Event and do the corresponding processing. It is important to note that, like the exit and Enter methods in OOP, transition is initialized with preAction and postAction, so you need to be careful about the order in which you call the methods.
// -parameters: /// -event: an event that is triggered /// -execution: an operation that needs to be executed during a state transition /// -callback: Public func process(event: event, execution: (() -> Void)? = nil, callback: TransitionBlock? = nil) { var transitions: [Transition<State, Event>]? lockQueue.sync { transitions = self.transitionByEvent[event] } workingQueue.async { let performableTransitions = transitions? .filter { $0.source == self.internalCurrentState } ?? [] if performableTransitions.count == 0 { self.callbackQueue.async { callback?(.failure) } return } assert(performableTransitions.count == 1, "Found multiple transitions with event '(event)' and source '(self.internalCurrentState)'.") let transition = performableTransitions.first! self.callbackQueue.async { transition.executePreAction() } self.callbackQueue.async { execution? () } self.internalCurrentState = transition.destination self.callbackQueue.async { transition.executePostAction() } self.callbackQueue.async { callback?(.success) } } }Copy the codeIf the registration fails, the failed callback will be executed. Otherwise, the following order will be executed:
1. Execute preAction in Transition
2. Then there is the execution action Block passed in the Process method
3. Change the current state of the state machine
4. Then execute the postAction in Transition
5. Finally, a successful callback is executed
One important thing to note here is that the callbackQueue defaults to the primary queue. If a custom queue is passed in during initialization, it should be a serial queue. This ensures that preAction, postAction, callBack, and so on are executed in order.
How do you use it?
It’s the same simple example above, but here we’ll just define the enumeration of events and states:
enum EventType {
case clickWalkButton
case clickRunButton
}
enum StateType {
case walk
case run
}
typealias StateMachineDefault = StateMachine<StateType, EventType>
typealias TransitionDefault = Transition<StateType, EventType>
Copy the codeThen it’s time to initialize the state machine:
func initialStateMachine() { stateMachine = StateMachineDefault.init(initialState: .walk) let a = transitionDefault.init (with:.clickWalkButton, from:.run, to:.walk) {NSLog(" ready to walk ")} postBlock: } let b = transitionDefault. init(with:.clickrunbutton, from:.walk, to: .run) {NSLog(" ready to run ")} postBlock: {NSLog(" started running ")} statemachine.add (transition: a) statemachine.add (transition: b)}Copy the codeLast but not least, the incoming event can be triggered directly:
stateMachine.process(event: .clickRunButton)
Copy the codeThe actual case
In actual development, we often encounter various state switching scenarios of the keyboard, which is actually suitable for using the state machine, because once there are more than three states, it is very efficient to use the state machine.
First determine the states to be clicked:
/// Keyboard status enum KeyboardState: State {case prepareToEditText // Preparing to edit Case prepareToRecord // Preparing to record case editingText // editing case showingPannel // Displaying pannel}Copy the codeThen there is the trigger event for the keyboard click:
/// Triggered event enum KeyboardEvent: Event {case clickSwitchButton // Click the toggle button case clickMoreButton // Click the More button case tapTextField // Click the input box case vcDidTapped // Click the blank area of the controller}Copy the codeAt this point, there is an association between the trigger event and the keyboard state that we can UML
| Trigger event \ Initial state | prepareToEdit | prepareToRecord | editingText | showingPannel |
|---|---|---|---|---|
| clickSwitchButton | prepareToRecord | editingText | prepareToRecord | prepareToRecord |
| clickMoreButton | showingPannel | showingPannel | showingPannel | prepareToEdit |
| tapTextField | editingText | ** | \ | editingText |
| vcDidTapped | ** | ** | prepareToEdit | prepareToEdit |
We can then add events that change between different states to the state machine:
stateMachine.listen(.clickSwitchButton,
transform: .prepareToEditText,
toState: .prepareToRecord) { [weak self] (transition) in
}
stateMachine.listen(.clickSwitchButton,
transform: .prepareToRecord,
toState: .editingText) { [weak self] (transition) in
}
......
Copy the codeFinally, the triggering condition can be called when clicking the button and other interactions:
@objc func switchButtonClicked(_ sender: UIButton) { stateMachine.trigger(.clickSwitchButton) } @objc func morefeaturesButtonClicked(_ sender: UIButton) { stateMachine.trigger(.clickMoreButton) }Copy the codeSo a keyboard switch event is done. This way is better than a lot of judging code according to readability, and extensible. If you want to add another state later, it is nothing more than adding several more conditions of state transition to the state machine state, which is not complicated.
The final chapter
All right, that’s it for the state machine. So why write an article about state machines? The main reason is that I find it very efficient in managing multiple STATES of the UI, especially when the number of states is more than three, such as managing various states of the keyboard in the IM module.
If you manage multiple states only through enumerations, you have a lot of current state code that is difficult to maintain. If a new state is to be added, the code that determines the existing state needs a lot of modification and does not meet the open-closed principle (closed for modification, open for extension), etc.
Finally, I hope you can use state machines in appropriate scenarios.
reference
[1] Finite State Machines (PDF)
[2] A More Object-oriented State Machine
[3] wikipedia: Finite-state machine
[4] Maze source code (2) : GamePlayKit’s state machine
[5] Implementing a Finite State Machine Using C# in Unity
[6] Finite State Machine (Finite Automata)