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