Developments10 分钟 读完 (大约 1508 个字)

[Golang] 有限状态机FSM

有限状态机(Finite State Machine)是一个非常有用的模型，理论上只要你考虑的状态足够多，就可以模拟世界上大部分事物。

1.有限状态机

简单描述有限状态机，它有三个特征：

状态总数state是有限的
任一时刻，只处在一种状态之中
某种条件之下，会从一种状态转变到另一种状态

转变(transition)通常都是满足某个条件或是事件触发，执行动作，实现状态的迁移(也可以是保持原状态)。
而“动作”是不稳定的，动作的触发往往是暂时的，使用状态的是为了使事务的边界更清晰，逻辑更加分明，同时保证稳定，在没有外部条件触发的情况下，一个状态会一直持续下去。

2.一个例子

以电梯为例，简单考虑，电梯拥有三种状态：“开启”、“停止/关闭”、“移动”。显然为了安全起见，电梯在移动过程中需要保持电梯门关闭；而电梯门在开启状态下，可以再次开启电梯门以让其他人进入。
电梯三种状态的转换如下图：
fsm for elevator

3.代码

正好用golang来实现下一个简单的fsm。
由状态接口State interface{}统一定义状态，状态管理机Statemanager来管理状态，二者实现了一个简单fsm的大部分功能。

3.1 状态接口state.go

为了统一管理状态，需要使用接口定义状态。状态机从状态接口查询到用户的自定义状态应该具备的属性有：

  • Name(): 对应State接口的名称；
  • EnableSelfTransit(): 是否允许同状态转移；
  • CanTransitTo(): 能否转移到指定状态。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package main

import "reflect"

type State interface {
	Name() string
	EnableSelfTransit() bool
	OnBegin()
	OnEnd()
	CanTransitTo(name string) bool
}

func GetStateName(s State) string {
	if s == nil {
		return "none"
	}
	// Use reflect to get the name of state (not the var name)
	return reflect.TypeOf(s).Elem().Name()
}

需要说明GetStateName()方法，由于State在初始化时，可以理解为OpeningState State，除了缺省的属性外，其他属性都是空值，这其中就包括很关键的name，GetStateName()通过reflect直接获取实例的名称作为name。

3.2 状态信息info.go

定义了结构体StateInfo，目的是为了在状态初始化时，将一些值赋为缺省值，避免在很多状态中重复编写很多代码。(当然，可以通过重写修改缺省的值)

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
type StateInfo struct {
	name string
}

func (s *StateInfo) Name() string {
	return s.name
}

func (s *StateInfo) setName(name string) {
	s.name = name
}

// Default info
func (s *StateInfo) EnableSelfTransit() bool {
	// False by default
	return false
}

func (s *StateInfo) OnBegin() {
}

func (s *StateInfo) OnEnd() {
}

func (s *StateInfo) CanTransitTo(name string) bool {
	// True by default
	return true
}

3.3 状态管理statemgr.go

StateManager为fsm的核心，通过映射stateByName保存所有的状态，定义回调函数OnChange()提供状态转移的通知(也可以是其他功能)。

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
package main

import (
	"errors"
)

type StateManager struct {
	stateByName map[string]State
	// Callback while state gets changed
	OnChange func(from, to State)
	curr State
}

func (sm *StateManager) Get(name string) State {
	// In case get panic when 'name' do not exist
	if v, ok := sm.stateByName[name]; ok {
		return v
	}
	return nil
}

func (sm *StateManager) Add(s State) {
	name := GetStateName(s)
	// State does not have any interface of setName()
	// Though StateInfo gets one
	s.(interface{
		// Actually this method is from StateInfo
		setName(name string)
	}).setName(name)

	// Check name duplication
	if sm.Get(name) != nil {
		panic("Duplicate state:" + name)
	}

	sm.stateByName[name] = s
}

// Init StateManager
func NewStateManager() *StateManager {
	return &StateManager{
		stateByName: make(map[string]State),
	}
}

// Define errors
var ErrStateNotFound = errors.New("state not found")
var ErrForbidSelfStateTransit = errors.New("forbid self transit")
var ErrCannotTransitToState = errors.New("cannot transit to state")

func (sm *StateManager) GetCurrState() State {
	return sm.curr
}

func (sm *StateManager) CanCurrTransitTo(name string) bool {
	if sm.curr == nil {
		return true
	}
	if sm.curr.Name() == name && !sm.curr.EnableSelfTransit() {
		return false
	}
	return sm.curr.CanTransitTo(name)
}

func (sm *StateManager) Transit(name string) error {
	next := sm.stateByName[name]
	pre :=sm.curr
	if next == nil {
		return ErrStateNotFound
	}
	if pre != nil {
		// Maybe it's more secure to compare with string
		if GetStateName(pre) == name && pre.EnableSelfTransit() {
			goto transitHere
		}
		if !pre.CanTransitTo(name) {
			return ErrCannotTransitToState
		}
		pre.OnEnd()
	}

transitHere:
	sm.curr = next
	sm.curr.OnBegin()
	if sm.OnChange != nil {
		sm.OnChange(pre, sm.curr)
	}
	return nil
}

在方法Add()中有个很有趣的操作：

1
2
3
s.(interface{
   setName(name string)
}).setName(name)

由于在实例化各个状态的过程中，使用了StateInfo作为内嵌结构体，而在传到Add(s State)中时，结构体StateInfo包含了State接口中并未定义的方法setName()，因此需要通过一个类型转换，来调用setName()方法。很骚，学会了

3.4 主方法main.go

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
package main

import "fmt"

type OpeningState struct {
	StateInfo
}

func (os *OpeningState) OnBegin() {
	fmt.Println("Elevator is opening")
}

func (os *OpeningState) OnEnd() {
	fmt.Println("Elevator is closing")
}

// Overwrite EnableSelfTransit()
func (os *OpeningState) EnableSelfTransit() bool {
	return true
}

// Compete state transiting road-map
func (os *OpeningState) CanTransitTo(name string) bool {
	return name == "StoppingState"
}

type StoppingState struct {
	StateInfo
}

func (ss *StoppingState) OnBegin() {
	fmt.Println("Elevator is stopped")
}

func (ss *StoppingState) OnEnd() {
	fmt.Println("Watch out, elevator is going to move")
}

func (ss *StoppingState) CanTransitTo(name string) bool {
	return name != "StoppingState"
}

type RunningState struct {
	StateInfo
}

func (rs *RunningState) OnBegin() {
	fmt.Println("Elevator is moving")
}

func (rs *RunningState) OnEnd() {
	fmt.Println("Elevator reaches target floor")
}

func (rs *RunningState) CanTransitTo(name string) bool {
	return name == "StoppingState"
}

func transitAndReport(sm *StateManager, target string) {
	if err := sm.Transit(target); err != nil {
		fmt.Printf("FAILED transit from %s to %s\nError: %s\n", GetStateName(sm.curr), target, err.Error())
	}
}

func main() {
	sm := NewStateManager()
	sm.OnChange = func(from, to State) {
		fmt.Printf("%s -----> %s\n", GetStateName(from), GetStateName(to))
	}

	// Instantiate states and Add them to statemgr
	sm.Add(new(OpeningState))
	sm.Add(new(StoppingState))
	sm.Add(new(RunningState))

	transitAndReport(sm, "OpeningState")
	transitAndReport(sm, "OpeningState")
	transitAndReport(sm, "StoppingState")
	transitAndReport(sm, "RunningState")
	transitAndReport(sm, "StoppingState")
	transitAndReport(sm, "OpeningState")
}

main.go中定义了三种不同的状态，将StateInfo内嵌以实现属性的默认值设置，对于需要修改的属性，重写了相应的方法。

输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Elevator is opening
none -----> OpeningState
Elevator is opening
OpeningState -----> OpeningState
Elevator is closing
Elevator is stopped
OpeningState -----> StoppingState
Watch out, elevator is going to move
Elevator is moving
StoppingState -----> RunningState
Elevator reaches target floor
Elevator is stopped
RunningState -----> StoppingState
Watch out, elevator is going to move
Elevator is opening
StoppingState -----> OpeningState

当然，一些错误转换主方法中没有测试，你也可以试试。

4 参考

https://new-tonywang.github.io/2020/02/12/FSM/

http://www.ruanyifeng.com/blog/2013/09/finite-state_machine_for_javascript.html

https://www.zhihu.com/question/31845498

#

最新文章

×