作者丨搜狐焦点-向辉
来源丨搜狐技术产品（ID：sohu-tech）
本文字数：4593字
预计阅读时间：14分钟
我们还是直接使用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.
简言之：我们通常称作的状态机是有限状态机的简称，它是一种数学计算模型。
有限状态机（也就是有限自动机）如果进行一个分类的话，分类如下：
这张图只是看一个大概的分类，实际上这个有一个简单的认知就可以了，因为我们要探讨的种类主要就是DFA(Deterministic Finite Automaton)：确定性有限状态自动机。它也是最简单的一种状态机模型，下文中我们简称为状态机的都是确定性有限状态自动机。
❝注：分类本身是有各种分类方式的，这里采取是以是否有输出作为分类的前提，Wikipedia上的分类方式和此种分类不太一致，大家可以参考对比一下。
那么确定性有限状态自动机有哪些特点呢？简单来讲就是每一种输入引起状态的变化是确定的，即一个状态对于同样的输入，只能有一种转换规则。
很多人每天上班都要刷卡进出地铁，我们就以有旋转栅门的地铁站闸机入口作为例子。
这个闸机口在开始的时候有一个“locked”的状态, 在这个状态下它并不会让乘客旋转栅栏通过进站口。当有人刷卡了，那么这个闸机口的状态就会变为“unlocked”，但是它并不会自己转动，必须得等到有人推动旋转栅栏通过闸机口，且在这之后闸机口的状态会再次变为“locked”。
从上面的描述中可以看到这个闸机口总是处于两种状态之一：Locked 或者 Unlocked。同时也只有两种转化的触发条件：刷卡 或者 通过旋转栅栏。
接下来，我们可以通过图形的方式来给这个闸机系统建模，使用圆角矩形代表状态，使用箭头代表状态之间的转换：
上述系统大概描述出了该系统是如何工作的，但是还有一些场景是这个系统无法明确定义的。比如刷了卡之后马上又刷了一次卡，那么状态如何转变呢？比如还没有刷卡之前就有人要通过旋转栏，那么状态是如何转变呢？在上述的两种情况，我们建的状态机模型会保留在它的当前状态。
同时我们还得给这个系统加上一个初始的状态，这样我们就可以继续完善这个模型了：
上述模型就是一个简单的状态机模型，基于此，我们可以从中总结出这个系统几个关键的特征：
❝• 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 occur at that time.
• For each state the system may be in, behavior is defined for each possible input or event.
这个时候我们的定义已经够多了，有些理论，但是还是还不够，作为工程师，我们通常需要使用更加正式的，或者说更数学的方式来描述该系统，一个有限自动机M通常被五元组(Σ, Q, q0, F, δ)所定义:
简单来说，该五元组为（输入，状态集，初始状态，结果状态集，转换方法）, 那么这里的转换方法如何理解呢？它的参数就是当前状态 以及 输入 输出就是 结果状态 即 δ(q, x) = p。一个有限状态机 M 处于状态 q 中，接受到 x 输入，在处理完转换过程中的Action之后，就会变为状态 p 。
而对于这个转化方法的抽象，在我们自定义状态机的时候将尤为重要。
实现状态机最简单的方法是使用枚举类和swtich-case语句来实现，但是我们今天不会使用这种方式，而是会尝试用两种不同的方式来定义一个状态机。
第一种方式是使用OOP的思路来完成一个通用的状态机，那么首当其冲的要考虑可以抽象出哪些类呢？结合上方的五元组，抽象如下：
protocol Event: Hashable { }
class State<E: Event> {
}
class StateMachine<E: Event> {
}
第一是事件：因为状态的转移是需要事件触发的，所以事件集在这里定义为一个Event协议，后面谁使用，谁定义相应的事件枚举即可。
第二是状态：这里把五元组中的Transition Function封装进状态类，直接由状态类本身来管理转换行为。
第三是状态机：这个就类似我们MVC中的view controller，是状态机的中枢，需要由它来管理状态的切换。
以上就是我定义的状态机模型的基建了，那么我们整体的设计思路呢？
1、状态机类接受事件触发
2、将事件传递给当前状态，由当前状态触发事件
3、事件触发后：如果需要跳转到其它状态，当前状态离开，而目标状态进入
设计非常简单，接下来看具体的实现。
class State<E: Event> {
weak open var stateMachine: StateMachine<E>?
open func trigger(event: E) {}
open func enter() {
stateMachine?.currentState = self
}
open func exit() { }
}
这里来分析一下具体有什么：
当状态机传入事件的时候，当前状态在进行事件判断之后，需要调用状态机以进入目标状态。
此处相当于注册transition！当前状态接受每一个输入事件的转移都将注册在此处。
具体来说就是当前状态的离开方法，以及目标状态的进入方法。
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()
}
}
}
}
那么接下来分析一下具体需要些什么：
对于状态机类，我们需要给它一个初始状态，这样的话，它的构造方法就需要一个初始状态的参数。
因为状态机需要管理状态之间的转移，那么它就需要存储这些状态。
外界事件触发的时候，状态机就触发当前状态的事件检测方法，因为这里，我们是让每一个状态内部来针对不同的输入，来完成对应的转换规则的。
当要进入新状态时，依照上述的设计，我们需要通过状态机类来处理进入新状态的方法。
当我去思考哪些软件可能会使用状态机的时候，第一反应就是游戏，因为游戏中一个角色有各种各样的状态，如果是使用if-else的话那未免太过于繁琐，这个时候，通过状态机来控制状态的变化一定是最优解，比如idle状态，walk状态，run状态，attack状态，hurt状态等等等等。
所以这里我们只用一个简单的例子，通过两个按钮来控制角色walk和run的状态切换。
所以使用的时候先定义事件
enum RoleEvent: Event {
case clickRunButton
case clickWalkButton
}
再定义状态，这里我们定义RunState 和 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=====")
}
}
最后就是初始化了：
func initialStateMachine() {
let run = RunState.init()
let walk = WalkState.init()
stateMachine = StateMachine.init(initialState: run)
stateMachine.setupStates(_states: [run, walk])
}
然后实际使用的时候，通过stateMachine触发不同的事件即可：
stateMachine.trigger(event: .clickRunButton)
// stateMachine.trigger(event: .clickWalkButton)
这里我参考了一个很轻量级的Swift状态机框架Stateful来实现一个更swift风格的状态机。
我们先抛开OOP的思路，回想一下确定性有限自动机的数学定义，有一个东西很关键，那就是transition function，所以这里我们先把transition抽象为一个结构体，包含一个转换规则的所有元素。
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?()
}
}
来看这一段代码的话，会发现，我们将触发事件，开始状态，结束状态，以及转换过程中需要执行的Action都封装进了该Transition中。
接下来出个简单的数学题，假设有3个状态，4个事件，最多需要有多少个Transition实例呢？
为了保证线程安全，我们将使用三个队列，同时和上述状态机一致，我们将设定一个初始化状态：
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
}
}
处理transition事件默认是在主队列中，同时也可以自定义一个队列并在初始化时传入，即callbackQueue。
接下来要做的就是注册状态表了，这里我们使用一个字典：
private var transitionsByEvent: [Event : [Transition<State, Event>]] = [:]
为什么这里用一个字典呢？
这里应该很好理解，因为状态机接受Event，然后结合当前State 以及 Event 去查询有没有对应的Transition，如果有就进行相关处理，如果没有就不执行。同时因为每一个Event，对应的都是一组Transition（因为每一个状态都可以接受该Event转换为另一个状态），那么这个字典的Value值很自然的就应该是一个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]
}
}
}
很简单，使用串行队列实现一个读写锁，保证线程安全。
当注册完状态表之后，剩下的就是接受相应Event，然后做出相应的处理了。要注意的一点就是类似前面OOP中调用的exit 方法 以及 enter 方法，初始化transition的时候也有相应的preAction和postAction, 调用方法的时候需要注意顺序。
/// 接受事件，做出相应处理
/// - Parameters:
/// - event: 触发的事件
/// - execution: 状态转移的过程中需要执行的 操作
/// - 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)
}
}
}
这里接受Event触发之后，首先当然是判断该事件对应的Transition是否注册，如果注册失败，那就执行失败的callback，反之按照以下顺序执行：
1、先执行该Transition中的preAction
2、然后是Process方法中传入的执行操作Block
3、接着改变状态机当前状态
4、然后是执行该Transition中的postAction 5、最后是执行成功的回调
当然这里有一个要注意的地方，就是callbackQueue默认为主队列，如果是初始化时传入自定义队列的话，最好是串行队列！因为这样可以确保preAction, postAction, callBack等等可以按照顺序执行。
还是上述那个简单的例子，但是这里我们直接定义事件和状态的枚举即可：
enum EventType {
case clickWalkButton
case clickRunButton
}
enum StateType {
case walk
case run
}
typealias StateMachineDefault = StateMachine<StateType, EventType>
typealias TransitionDefault = Transition<StateType, EventType>
然后就是初始化状态机了：
func initialStateMachine() {
stateMachine = StateMachineDefault.init(initialState: .walk)
let a = TransitionDefault.init(with: .clickWalkButton, from: .run, to: .walk) {
NSLog("准备走")
} postBlock: {
NSLog("开始走了")
}
let b = TransitionDefault.init(with: .clickRunButton, from: .walk, to: .run) {
NSLog("准备跑")
} postBlock: {
NSLog("开始跑了")
}
stateMachine.add(transition: a)
stateMachine.add(transition: b)
}
最后就是直接传入事件触发即可：
stateMachine.process(event: .clickRunButton)
在实际的开发中，我们经常会遇到键盘的各种状态切换的场景，这种场景其实就很适合使用状态机，因为一旦超过三种状态，使用状态机就会非常高效。
首先确定要键盘点击的几个状态：
/// 键盘状态
enum KeyboardState: State {
case prepareToEditText // 准备编辑
case prepareToRecord // 准备录音
case editingText // 正在编辑
case showingPannel // 正在展示pannel
}
然后是键盘点击的触发事件：
/// 触发事件
enum KeyboardEvent: Event {
case clickSwitchButton // 点击切换按钮
case clickMoreButton // 点击more按钮
case tapTextField // 点击输入框
case vcDidTapped // 点击控制器空白区域
}
那么这个时候，在触发事件和键盘状态之间就出现了一个关联关系，我们可以UML化这种关联
| 触发事件\初始状态 | prepareToEdit | prepareToRecord | editingText | showingPannel |
|---|---|---|---|---|
| clickSwitchButton | prepareToRecord | editingText | prepareToRecord | prepareToRecord |
| clickMoreButton | showingPannel | showingPannel | showingPannel | prepareToEdit |
| tapTextField | editingText | / | / | editingText |
| vcDidTapped | / | / | prepareToEdit | prepareToEdit |
接下来就可以将不同状态之间改变的事件添加入状态机中：
stateMachine.listen(.clickSwitchButton,
transform: .prepareToEditText,
toState: .prepareToRecord) { [weak self] (transition) in
}
stateMachine.listen(.clickSwitchButton,
transform: .prepareToRecord,
toState: .editingText) { [weak self] (transition) in
}
......
最后就是触发了，当点击按钮等交互时，即可调用该触发条件：
//MARK: -
//MARK: 点击事件
@objc func switchButtonClicked(_ sender: UIButton) {
stateMachine.trigger(.clickSwitchButton)
}
@objc func morefeaturesButtonClicked(_ sender: UIButton) {
stateMachine.trigger(.clickMoreButton)
}
这样一个键盘的切换事件就搞定了。这种方式比大量的判断代码根据可读性，而且可拓展性也更强，如果后续想要再增加一种状态的话，那无非就是状态机状态多添加几种状态转移的条件而已，这并不复杂。
好了，状态机介绍完了。那为什么要写一篇文章来介绍状态机呢？主要原因是因为我觉得它在管理UI的多种状态时非常高效，特别是当状态数大于三个以上的时候，比如管理IM模块中键盘的各种状态时。
而如果是仅仅通过枚举来管理多种状态，那代码中就会有大量的当前状态判断的代码，很不易维护；如果要添加一个新的状态，那么原有状态判断的代码需要大量的修改，不满足开闭原则（对修改关闭，对拓展开放）等等。
最后希望大家在合适的场景中使用状态机吧。
[1] https://web.archive.org/web/20140327131120/http://www4.ncsu.edu/~drwrigh3/docs/courses/csc216/fsm-notes.pdf
[2] https://www.conradbock.org/statemachine.html
[3] https://en.wikipedia.org/wiki/Finite-state_machine
[4] http://www.ios5.online/ios/ioskf/ioskfajc/201703/50096.html
[5] https://faramira.com/implementing-a-finite-state-machine-using-c-in-unity-part-1
[6] https://www.youtube.com/watch?v=Qa6csfkK7_I
-End-
最近有一些小伙伴，让我帮忙找一些 面试题 资料，于是我翻遍了收藏的 5T 资料后，汇总整理出来，可以说是程序员面试必备！所有资料都整理到网盘了，欢迎下载！
面试题】即可获取文章引用微信公众号"程序员大咖",如有侵权,请联系管理员删除!