Go
by smallnest

一个有特色的有限状态机

gofsm是一个简单、小巧而又特色的有限状态机（FSM）。

github已经有了很多状态机的实现，比如文末列出的一些，还为什么要再发明轮子呢？

原因在于这些状态机有一个特点，就是一个状态机维护一个对象的状态，这样一个状态机就和一个具体的图像实例关联在一起，在有些情况下，这没有什么问题，而且是很好的设计，而且比较符合状态机的定义。但是在有些情况下，当我们需要维护成千上百个对象的时候，需要创建成千上百个状态机对象，这其实是很大的浪费，因为在大部分情况下，对象本身自己会维护/保持自己当前的状态，我们只需把对象当前的状态传递给一个共用的状态机就可以了，也就是gofsm本身是“stateless”，本身它包维护一个或者多个对象的状态，所有需要的输入由调用者输入，它只负责状态的转换的逻辑，所以它的实现非常的简洁实用，这是创建gofsm的一个目的。

第二个原因它提供了Moore和Mealy两种状态机的统一接口，并且提供了UML状态机风格的Action处理，以程序员更熟悉的方式处理状态的改变。

第三个原因，当我们谈论起状态机的时候，我们总会画一个状态转换图，大家可以根据这这张图进行讨论、设计、实现和验证状态的迁移。但是对于代码来说，实现真的和你的设计是一致的吗，你怎么保证？gofsm提供了一个简单的方法，那就是它可以输出图片或者pdf文件，你可以利用输出的状态机图和你的设计进行比较，看看实现和设计是否一致。

gofsm生成的闸门状态图

有限状态机

有限状态机（finite-state machine）常常用于计算机程序和时序逻辑电路的设计数学模型。它被看作是一种抽象的机器，可以有有限个状态。任意时刻这个机器只有唯一的一个状态，这个状态称为当前状态。当有外部的事件或者条件被触发，它可以从一个状态转换到另一个状态，这就是转换（transition）。一个FSM就是由所有的状态、初始状态和每个转换的触发条件所定义。有时候，当这个转换发生的时候，我们可以要执行一些事情，我们称之为动作（Action）。

现实情况中，我们实际上遇到了很多的这种状态机的情况，只不过我们并没有把它们抽象出来，比如路口的红绿灯，总是在红、黄、绿的状态之间转变，比如电梯的状态，包括开、关、上、下等几个状态。

有限状态机可以有效清晰的为一大堆的问题建立模型，大量应用于电子设计、通讯协议、语言解析和其它的工程应用中，比如TCP/IP协议栈。

图像来源 http://www.tcpipguide.com

以一个转门为例，这种专门在一些会展、博物馆、公园的门口很常见，顾客可以投币或者刷卡刷票进入，我们下面以投币(Coin)统称这个触发事件。如果你不投币，闸门是锁着的，你推不动它的转臂，而且投一次币只能进去一个人，过去之后闸门又是锁着的，挺智能的 ：）。

图片来源 wikipedia

如果我们抽象出来它的状态图，可以用下图表示：
图片来源 wikipedia

它有两个状态：Locked、Unlocked。有两个输入（input）会影响它的状态，投币(coin)和推动转臂（push）。

  1. 在Locked状态， push没有作用。不管比push多少次闸门的状态还是lock
  2. 在Locked状态，投币会让闸门开锁，闸门可以让一个人通过
  3. 在Unlocked状态，投币不起作用，闸门还是开着
  4. 在Unlocked状态，如果有人push通过，人通过后闸门会由Unlocked状态转变成Locked状态。

这是一个简单的闸门的状态转换，却是一个很好的理解状态的典型例子。

以表格来表示：

Current StateInputNext StateOutput
LockedcoinUnlockedUnlock turnstile so customer can push through
pushLockedNone
UnlockedcoinUnlockedNone
pushLockedWhen customer has pushed through, lock turnstile

UML也有状态图的改变，它扩展了FSM的概念，提供了层次化的嵌套状态（Hierarchically nested states）和正交区域（orthogonal regions），当然这和本文没有太多的关系，有兴趣的读者可以找UML的资料看看。但是它提供了一个很好的概念，也就是动作（Action）。就像Mealy状态机所需要的一样，动作依赖系统的状态和触发事件，而它的Entry Action和Exit Action，却又像Moore 状态机一样，不依赖输入，只依赖状态。所以UML的动作有三种，一种是事件被处理的时候，状态机会执行特定的动作，比如改变变量、执行I/O、调用方法、触发另一个事件等。而离开一个状态，可以执行Exit action，进入一个状态，则执行Entry action。记住，收到一个事件，对象的状态不会改变，比如上边闸门的例子，在Locked状态下push多少次状态都没改变，这这种情况下，不会执行Exit和Entry action。

gofsm提供了这种扩展的模型，当然如果你不想使用这种扩展，你也可以不去实现Entry和Exit。

可以提到了两种状态机，这两种状态机是这样来区分的：

  • Moore machine
    Moore状态机只使用entry action，输出只依赖状态，不依赖输入。
  • Mealy machine
    Mealy状态机只使用input action，输出依赖输入input和状态state。使用这种状态机通常可以减少状态的数量。

gofsm提供了一个通用的接口，你可以根据需要确定使用哪个状态机。从软件开发的实践上来看，有时候你并不一定要关注状态机的区分，而是清晰的抽象、设计你所关注的对象的状态、触发条件以及要执行的动作。

gofsm

gofsm参考了 elimisteve/fsm 的实现，实现了一种单一状态机处理多个对象的方法，并且提供了输出状态图的功能。

它除了定义对象的状态外，还定义了触发事件以及处理的Action，这些都是通过字符串来表示的，在使用的时候很容易的和你的对象、方法对应起来。

使用gofsm也很简单，当然第一步将库拉到本地：

1
go get -u github.com/smallnest/gofsm

我们以上面的闸门为例，看看gofsm是如何使用的。

注意下面的单个状态机可以处理并行地的处理多个闸门的状态改变，虽然例子中只生成了一个闸门对象。

首先定义一个闸门对象,它包含一个State，表示它当前的状态：

1
2
3
4
5
6
7
8
type Turnstile struct {
	ID         uint64
	EventCount uint64 //事件统计
	CoinCount  uint64 //投币事件统计
	PassCount  uint64 //顾客通过事件统计
	State      string //当前状态
	States     []string //历史经过的状态
}

状态机的初始化简单直接：

1
2
3
4
5
6
7
8
9
10
11
12
func initFSM() *StateMachine {
	delegate := &DefaultDelegate{p: &TurnstileEventProcessor{}}
	transitions := []Transition{
		Transition{From: "Locked", Event: "Coin", To: "Unlocked", Action: "check"},
		Transition{From: "Locked", Event: "Push", To: "Locked", Action: "invalid-push"},
		Transition{From: "Unlocked", Event: "Push", To: "Locked", Action: "pass"},
		Transition{From: "Unlocked", Event: "Coin", To: "Unlocked", Action: "repeat-check"},
	}
	return NewStateMachine(delegate, transitions...)
}

你定义好转换对应关系transitions,一个Transition代表一个转换，从某个状态到另外一个状态，触发的事件名，要执行的Action。
因为Action是字符串，所以你需要实现delegate将Action和对应的要处理的方法对应起来。

注意from和to的状态可以一样，在这种情况下，状态没有发生改变，只是需要处理Action就可以了。

如果Action为空，也就是不需要处理事件，只是发生状态的改变而已。

处理Action的类型如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
type TurnstileEventProcessor struct{}
func (p *TurnstileEventProcessor) OnExit(fromState string, args []interface{}) {
	……
}
func (p *TurnstileEventProcessor) Action(action string, fromState string, toState string, args []interface{}) {
	……
}
func (p *TurnstileEventProcessor) OnEnter(toState string, args []interface{}) {
    ……
}

然后我们就可以触发一些事件看看闸门的状态机是否正常工作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
ts := &Turnstile{
	ID:     1,
	State:  "Locked",
	States: []string{"Locked"},
}
fsm := initFSM()
//推门
//没刷卡/投币不可进入
err := fsm.Trigger(ts.State, "Push", ts)
if err != nil {
	t.Errorf("trigger err: %v", err)
}
//推门
//没刷卡/投币不可进入
err = fsm.Trigger(ts.State, "Push", ts)
if err != nil {
	t.Errorf("trigger err: %v", err)
}
//刷卡或者投币
//不容易啊，终于解锁了
err = fsm.Trigger(ts.State, "Coin", ts)
if err != nil {
	t.Errorf("trigger err: %v", err)
}
//刷卡或者投币
//这时才解锁
err = fsm.Trigger(ts.State, "Coin", ts)
if err != nil {
	t.Errorf("trigger err: %v", err)
}
//推门
//这时才能进入，进入后闸门被锁
err = fsm.Trigger(ts.State, "Push", ts)
if err != nil {
	t.Errorf("trigger err: %v", err)
}
//推门
//无法进入，闸门已锁
err = fsm.Trigger(ts.State, "Push", ts)
if err != nil {
	t.Errorf("trigger err: %v", err)
}
lastState := Turnstile{
	ID:         1,
	EventCount: 6,
	CoinCount:  2,
	PassCount:  1,
	State:      "Locked",
	States:     []string{"Locked", "Unlocked", "Locked"},
}
if !compareTurnstile(&lastState, ts) {
	t.Errorf("Expected last state: %+v, but got %+v", lastState, ts)
} else {
	t.Logf("最终的状态: %+v", ts)
}

如果想将状态图输出图片，可以调用下面的方法，它实际是调用graphviz生成的，所以请确保你的机器上是否安装了这个软件，你可以执行dot -h检查一下：

1
fsm.Export("state.png")

生成的图片就是文首的闸门的状态机的图片。

如果你想定制graphviz的参数，你可以调用另外一个方法：

1
func (m *StateMachine) ExportWithDetails(outfile string, format string, layout string, scale string, more string) error

其它Go语言实现的FSM

如果你发现gofsm的功能需要改进，或者有一些想法、或者发现了bug，请不用迟疑，在issue中提交你的意见和建议，我会及时的进行反馈。

如果你觉得本项目有用，或者将来可能会使用，请star这个项目 smallnest/gofsm。

如果你想比较其它的Go语言实现的fsm，可以参考下面的列表：

参考资料

  1. https://en.wikipedia.org/wiki/Finite-state_machine