首页 文章详情

如何在Swift中实现状态机?

知识小集 | 398 2021-09-30 16:25 0 0 0
UniSMS (合一短信)


序章

什么是状态机?

我们还是直接使用wikiPedia上的定义:

A finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automatonor 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, δ)所定义:

  • Σ 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 ⊆ Q is the set of final states of M
  • δ : Q × Σ → Q is the transition function

简单来说,该五元组为(输入,状态集,初始状态,结果状态集,转换方法), 那么这里的转换方法如何理解呢?它的参数就是当前状态 以及 输入 输出就是 结果状态 即 δ(q, x) = p。一个有限状态机 M 处于状态 q 中,接受到 x 输入,在处理完转换过程中的Action之后,就会变为状态 p 。

而对于这个转化方法的抽象,在我们自定义状态机的时候将尤为重要。

中章

实现状态机最简单的方法是使用枚举类和swtich-case语句来实现,但是我们今天不会使用这种方式,而是会尝试用两种不同的方式来定义一个状态机。

如何实现状态机 - 面向对象(OOP)

基本抽象

第一种方式是使用OOP的思路来完成一个通用的状态机,那么首当其冲的要考虑可以抽象出哪些类呢?结合上方的五元组,抽象如下:

protocol EventHashable { }

class State<EEvent{

}

class StateMachine<EEvent{
    
}

第一是事件:因为状态的转移是需要事件触发的,所以事件集在这里定义为一个Event协议,后面谁使用,谁定义相应的事件枚举即可。

第二是状态:这里把五元组中的Transition Function封装进状态类,直接由状态类本身来管理转换行为。

第三是状态机:这个就类似我们MVC中的view controller,是状态机的中枢,需要由它来管理状态的切换。

以上就是我定义的状态机模型的基建了,那么我们整体的设计思路呢?

1、状态机类接受事件触发 

2、将事件传递给当前状态,由当前状态触发事件 

3、事件触发后:如果需要跳转到其它状态,当前状态离开,而目标状态进入

设计非常简单,接下来看具体的实现。

状态类

class State<EEvent{

    weak open var stateMachine: StateMachine<E>?

    open func trigger(event: E) {}

    open func enter() {
        stateMachine?.currentState = self
    }

    open func exit() { }
}

这里来分析一下具体有什么:

  • 状态机属性

当状态机传入事件的时候,当前状态在进行事件判断之后,需要调用状态机以进入目标状态。

  • 触发条件

此处相当于注册transition!当前状态接受每一个输入事件的转移都将注册在此处。

  • Transition 方法

具体来说就是当前状态的离开方法,以及目标状态的进入方法。

状态机类

class StateMachine<EEvent{
    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 RoleEventEvent {
    case clickRunButton
    case clickWalkButton
}

再定义状态,这里我们定义RunState 和 WalkState:

class RunStateState<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 WalkStateState<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风格的状态机。

Transition

我们先抛开OOP的思路,回想一下确定性有限自动机的数学定义,有一个东西很关键,那就是transition function,所以这里我们先把transition抽象为一个结构体,包含一个转换规则的所有元素。

public typealias ExecutionBlock = (() -> Void)
public struct Transition<StateEvent{
    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实例呢?

State Machine

为了保证线程安全,我们将使用三个队列,同时和上述状态机一致,我们将设定一个初始化状态:

class StateMachine<StateEvent{
    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<StateEvent>]] = [:]

为什么这里用一个字典呢?

这里应该很好理解,因为状态机接受Event,然后结合当前State 以及 Event 去查询有没有对应的Transition,如果有就进行相关处理,如果没有就不执行。同时因为每一个Event,对应的都是一组Transition(因为每一个状态都可以接受该Event转换为另一个状态),那么这个字典的Value值很自然的就应该是一个Transition数组了。

注册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

当注册完状态表之后,剩下的就是接受相应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<StateEvent>]?
        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<StateTypeEventType>
typealias TransitionDefault = Transition<StateTypeEventType>

然后就是初始化状态机了:

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 KeyboardStateState {
    case prepareToEditText   // 准备编辑
    case prepareToRecord     // 准备录音
    case editingText         // 正在编辑
    case showingPannel       // 正在展示pannel
}

然后是键盘点击的触发事件:

/// 触发事件
enum KeyboardEventEvent {
    case clickSwitchButton    // 点击切换按钮
    case clickMoreButton      // 点击more按钮
    case tapTextField         // 点击输入框
    case vcDidTapped          // 点击控制器空白区域
}

那么这个时候,在触发事件和键盘状态之间就出现了一个关联关系,我们可以UML化这种关联

触发事件\初始状态prepareToEditprepareToRecordeditingTextshowingPannel
clickSwitchButtonprepareToRecordeditingTextprepareToRecordprepareToRecord
clickMoreButtonshowingPannelshowingPannelshowingPannelprepareToEdit
tapTextFieldeditingText//editingText
vcDidTapped//prepareToEditprepareToEdit

接下来就可以将不同状态之间改变的事件添加入状态机中:

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

good-icon 0
favorite-icon 0
收藏
回复数量: 0
    暂无评论~~
    Ctrl+Enter