fsm.go 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432
  1. // Copyright (c) 2013 - Max Persson <max@looplab.se>
  2. //
  3. // Licensed under the Apache License, Version 2.0 (the "License");
  4. // you may not use this file except in compliance with the License.
  5. // You may obtain a copy of the License at
  6. //
  7. // http://www.apache.org/licenses/LICENSE-2.0
  8. //
  9. // Unless required by applicable law or agreed to in writing, software
  10. // distributed under the License is distributed on an "AS IS" BASIS,
  11. // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12. // See the License for the specific language governing permissions and
  13. // limitations under the License.
  14. // Package fsm implements a finite state machine.
  15. //
  16. // It is heavily based on two FSM implementations:
  17. //
  18. // Javascript Finite State Machine
  19. // https://github.com/jakesgordon/javascript-state-machine
  20. //
  21. // Fysom for Python
  22. // https://github.com/oxplot/fysom (forked at https://github.com/mriehl/fysom)
  23. //
  24. package fsm
  25. import (
  26. "strings"
  27. "sync"
  28. )
  29. // transitioner is an interface for the FSM's transition function.
  30. type transitioner interface {
  31. transition(*FSM) error
  32. }
  33. // FSM is the state machine that holds the current state.
  34. //
  35. // It has to be created with NewFSM to function properly.
  36. type FSM struct {
  37. // current is the state that the FSM is currently in.
  38. current string
  39. // transitions maps events and source states to destination states.
  40. transitions map[eKey]string
  41. // callbacks maps events and targers to callback functions.
  42. callbacks map[cKey]Callback
  43. // transition is the internal transition functions used either directly
  44. // or when Transition is called in an asynchronous state transition.
  45. transition func()
  46. // transitionerObj calls the FSM's transition() function.
  47. transitionerObj transitioner
  48. // stateMu guards access to the current state.
  49. stateMu sync.RWMutex
  50. // eventMu guards access to Event() and Transition().
  51. eventMu sync.Mutex
  52. }
  53. // EventDesc represents an event when initializing the FSM.
  54. //
  55. // The event can have one or more source states that is valid for performing
  56. // the transition. If the FSM is in one of the source states it will end up in
  57. // the specified destination state, calling all defined callbacks as it goes.
  58. type EventDesc struct {
  59. // Name is the event name used when calling for a transition.
  60. Name string
  61. // Src is a slice of source states that the FSM must be in to perform a
  62. // state transition.
  63. Src []string
  64. // Dst is the destination state that the FSM will be in if the transition
  65. // succeds.
  66. Dst string
  67. }
  68. // Callback is a function type that callbacks should use. Event is the current
  69. // event info as the callback happens.
  70. type Callback func(*Event)
  71. // Events is a shorthand for defining the transition map in NewFSM.
  72. type Events []EventDesc
  73. // Callbacks is a shorthand for defining the callbacks in NewFSM.a
  74. type Callbacks map[string]Callback
  75. // NewFSM constructs a FSM from events and callbacks.
  76. //
  77. // The events and transitions are specified as a slice of Event structs
  78. // specified as Events. Each Event is mapped to one or more internal
  79. // transitions from Event.Src to Event.Dst.
  80. //
  81. // Callbacks are added as a map specified as Callbacks where the key is parsed
  82. // as the callback event as follows, and called in the same order:
  83. //
  84. // 1. before_<EVENT> - called before event named <EVENT>
  85. //
  86. // 2. before_event - called before all events
  87. //
  88. // 3. leave_<OLD_STATE> - called before leaving <OLD_STATE>
  89. //
  90. // 4. leave_state - called before leaving all states
  91. //
  92. // 5. enter_<NEW_STATE> - called after entering <NEW_STATE>
  93. //
  94. // 6. enter_state - called after entering all states
  95. //
  96. // 7. after_<EVENT> - called after event named <EVENT>
  97. //
  98. // 8. after_event - called after all events
  99. //
  100. // There are also two short form versions for the most commonly used callbacks.
  101. // They are simply the name of the event or state:
  102. //
  103. // 1. <NEW_STATE> - called after entering <NEW_STATE>
  104. //
  105. // 2. <EVENT> - called after event named <EVENT>
  106. //
  107. // If both a shorthand version and a full version is specified it is undefined
  108. // which version of the callback will end up in the internal map. This is due
  109. // to the psuedo random nature of Go maps. No checking for multiple keys is
  110. // currently performed.
  111. func NewFSM(initial string, events []EventDesc, callbacks map[string]Callback) *FSM {
  112. f := &FSM{
  113. transitionerObj: &transitionerStruct{},
  114. current: initial,
  115. transitions: make(map[eKey]string),
  116. callbacks: make(map[cKey]Callback),
  117. }
  118. // Build transition map and store sets of all events and states.
  119. allEvents := make(map[string]bool)
  120. allStates := make(map[string]bool)
  121. for _, e := range events {
  122. for _, src := range e.Src {
  123. f.transitions[eKey{e.Name, src}] = e.Dst
  124. allStates[src] = true
  125. allStates[e.Dst] = true
  126. }
  127. allEvents[e.Name] = true
  128. }
  129. // Map all callbacks to events/states.
  130. for name, fn := range callbacks {
  131. var target string
  132. var callbackType int
  133. switch {
  134. case strings.HasPrefix(name, "before_"):
  135. target = strings.TrimPrefix(name, "before_")
  136. if target == "event" {
  137. target = ""
  138. callbackType = callbackBeforeEvent
  139. } else if _, ok := allEvents[target]; ok {
  140. callbackType = callbackBeforeEvent
  141. }
  142. case strings.HasPrefix(name, "leave_"):
  143. target = strings.TrimPrefix(name, "leave_")
  144. if target == "state" {
  145. target = ""
  146. callbackType = callbackLeaveState
  147. } else if _, ok := allStates[target]; ok {
  148. callbackType = callbackLeaveState
  149. }
  150. case strings.HasPrefix(name, "enter_"):
  151. target = strings.TrimPrefix(name, "enter_")
  152. if target == "state" {
  153. target = ""
  154. callbackType = callbackEnterState
  155. } else if _, ok := allStates[target]; ok {
  156. callbackType = callbackEnterState
  157. }
  158. case strings.HasPrefix(name, "after_"):
  159. target = strings.TrimPrefix(name, "after_")
  160. if target == "event" {
  161. target = ""
  162. callbackType = callbackAfterEvent
  163. } else if _, ok := allEvents[target]; ok {
  164. callbackType = callbackAfterEvent
  165. }
  166. default:
  167. target = name
  168. if _, ok := allStates[target]; ok {
  169. callbackType = callbackEnterState
  170. } else if _, ok := allEvents[target]; ok {
  171. callbackType = callbackAfterEvent
  172. }
  173. }
  174. if callbackType != callbackNone {
  175. f.callbacks[cKey{target, callbackType}] = fn
  176. }
  177. }
  178. return f
  179. }
  180. // Current returns the current state of the FSM.
  181. func (f *FSM) Current() string {
  182. f.stateMu.RLock()
  183. defer f.stateMu.RUnlock()
  184. return f.current
  185. }
  186. // Is returns true if state is the current state.
  187. func (f *FSM) Is(state string) bool {
  188. f.stateMu.RLock()
  189. defer f.stateMu.RUnlock()
  190. return state == f.current
  191. }
  192. // SetState allows the user to move to the given state from current state.
  193. // The call does not trigger any callbacks, if defined.
  194. func (f *FSM) SetState(state string) {
  195. f.stateMu.Lock()
  196. defer f.stateMu.Unlock()
  197. f.current = state
  198. }
  199. // Can returns true if event can occur in the current state.
  200. func (f *FSM) Can(event string) bool {
  201. f.stateMu.RLock()
  202. defer f.stateMu.RUnlock()
  203. _, ok := f.transitions[eKey{event, f.current}]
  204. return ok && (f.transition == nil)
  205. }
  206. // Cannot returns true if event can not occure in the current state.
  207. // It is a convenience method to help code read nicely.
  208. func (f *FSM) Cannot(event string) bool {
  209. return !f.Can(event)
  210. }
  211. // Event initiates a state transition with the named event.
  212. //
  213. // The call takes a variable number of arguments that will be passed to the
  214. // callback, if defined.
  215. //
  216. // It will return nil if the state change is ok or one of these errors:
  217. //
  218. // - event X inappropriate because previous transition did not complete
  219. //
  220. // - event X inappropriate in current state Y
  221. //
  222. // - event X does not exist
  223. //
  224. // - internal error on state transition
  225. //
  226. // The last error should never occur in this situation and is a sign of an
  227. // internal bug.
  228. func (f *FSM) Event(event string, args ...interface{}) error {
  229. f.eventMu.Lock()
  230. defer f.eventMu.Unlock()
  231. f.stateMu.RLock()
  232. defer f.stateMu.RUnlock()
  233. if f.transition != nil {
  234. return InTransitionError{event}
  235. }
  236. dst, ok := f.transitions[eKey{event, f.current}]
  237. if !ok {
  238. for ekey := range f.transitions {
  239. if ekey.event == event {
  240. return InvalidEventError{event, f.current}
  241. }
  242. }
  243. return UnknownEventError{event}
  244. }
  245. e := &Event{f, event, f.current, dst, nil, args, false, false}
  246. err := f.beforeEventCallbacks(e)
  247. if err != nil {
  248. return err
  249. }
  250. if f.current == dst {
  251. f.afterEventCallbacks(e)
  252. return NoTransitionError{e.Err}
  253. }
  254. // Setup the transition, call it later.
  255. f.transition = func() {
  256. f.stateMu.Lock()
  257. f.current = dst
  258. f.stateMu.Unlock()
  259. f.enterStateCallbacks(e)
  260. f.afterEventCallbacks(e)
  261. }
  262. if err = f.leaveStateCallbacks(e); err != nil {
  263. if _, ok := err.(CanceledError); ok {
  264. f.transition = nil
  265. }
  266. return err
  267. }
  268. // Perform the rest of the transition, if not asynchronous.
  269. f.stateMu.RUnlock()
  270. err = f.doTransition()
  271. f.stateMu.RLock()
  272. if err != nil {
  273. return InternalError{}
  274. }
  275. return e.Err
  276. }
  277. // Transition wraps transitioner.transition.
  278. func (f *FSM) Transition() error {
  279. f.eventMu.Lock()
  280. defer f.eventMu.Unlock()
  281. return f.doTransition()
  282. }
  283. // doTransition wraps transitioner.transition.
  284. func (f *FSM) doTransition() error {
  285. return f.transitionerObj.transition(f)
  286. }
  287. // transitionerStruct is the default implementation of the transitioner
  288. // interface. Other implementations can be swapped in for testing.
  289. type transitionerStruct struct{}
  290. // Transition completes an asynchrounous state change.
  291. //
  292. // The callback for leave_<STATE> must prviously have called Async on its
  293. // event to have initiated an asynchronous state transition.
  294. func (t transitionerStruct) transition(f *FSM) error {
  295. if f.transition == nil {
  296. return NotInTransitionError{}
  297. }
  298. f.transition()
  299. f.transition = nil
  300. return nil
  301. }
  302. // beforeEventCallbacks calls the before_ callbacks, first the named then the
  303. // general version.
  304. func (f *FSM) beforeEventCallbacks(e *Event) error {
  305. if fn, ok := f.callbacks[cKey{e.Event, callbackBeforeEvent}]; ok {
  306. fn(e)
  307. if e.canceled {
  308. return CanceledError{e.Err}
  309. }
  310. }
  311. if fn, ok := f.callbacks[cKey{"", callbackBeforeEvent}]; ok {
  312. fn(e)
  313. if e.canceled {
  314. return CanceledError{e.Err}
  315. }
  316. }
  317. return nil
  318. }
  319. // leaveStateCallbacks calls the leave_ callbacks, first the named then the
  320. // general version.
  321. func (f *FSM) leaveStateCallbacks(e *Event) error {
  322. if fn, ok := f.callbacks[cKey{f.current, callbackLeaveState}]; ok {
  323. fn(e)
  324. if e.canceled {
  325. return CanceledError{e.Err}
  326. } else if e.async {
  327. return AsyncError{e.Err}
  328. }
  329. }
  330. if fn, ok := f.callbacks[cKey{"", callbackLeaveState}]; ok {
  331. fn(e)
  332. if e.canceled {
  333. return CanceledError{e.Err}
  334. } else if e.async {
  335. return AsyncError{e.Err}
  336. }
  337. }
  338. return nil
  339. }
  340. // enterStateCallbacks calls the enter_ callbacks, first the named then the
  341. // general version.
  342. func (f *FSM) enterStateCallbacks(e *Event) {
  343. if fn, ok := f.callbacks[cKey{f.current, callbackEnterState}]; ok {
  344. fn(e)
  345. }
  346. if fn, ok := f.callbacks[cKey{"", callbackEnterState}]; ok {
  347. fn(e)
  348. }
  349. }
  350. // afterEventCallbacks calls the after_ callbacks, first the named then the
  351. // general version.
  352. func (f *FSM) afterEventCallbacks(e *Event) {
  353. if fn, ok := f.callbacks[cKey{e.Event, callbackAfterEvent}]; ok {
  354. fn(e)
  355. }
  356. if fn, ok := f.callbacks[cKey{"", callbackAfterEvent}]; ok {
  357. fn(e)
  358. }
  359. }
  360. const (
  361. callbackNone int = iota
  362. callbackBeforeEvent
  363. callbackLeaveState
  364. callbackEnterState
  365. callbackAfterEvent
  366. )
  367. // cKey is a struct key used for keeping the callbacks mapped to a target.
  368. type cKey struct {
  369. // target is either the name of a state or an event depending on which
  370. // callback type the key refers to. It can also be "" for a non-targeted
  371. // callback like before_event.
  372. target string
  373. // callbackType is the situation when the callback will be run.
  374. callbackType int
  375. }
  376. // eKey is a struct key used for storing the transition map.
  377. type eKey struct {
  378. // event is the name of the event that the keys refers to.
  379. event string
  380. // src is the source from where the event can transition.
  381. src string
  382. }