Exercise: Finite State Machine
Difficulty - Intermediate
Learning Objectives
- Design and implement finite state machines
- Manage state transitions with validation
- Implement state entry and exit callbacks
- Handle concurrent state access safely
- Build fluent APIs for configuration
- Validate state machine configurations
Problem Statement
Create a flexible finite state machine framework that models systems with discrete states and transitions between them. FSMs are fundamental patterns used in workflow engines, game AI, protocol implementations, UI navigation, and business process automation. Your implementation should support state validation, transition guards, and lifecycle callbacks.
Requirements
1. State Machine Core
Implement a StateMachine type that:
- Tracks the current state
- Maintains a graph of valid transitions
- Validates transitions before executing them
- Returns errors for invalid transitions
- Supports querying the current state
- Is safe for concurrent access
Example Usage:
1sm := NewStateMachine("idle")
2sm.AddTransition("idle", "start", "running")
3sm.AddTransition("running", "stop", "idle")
4sm.Trigger("start") // idle → running
2. Transition Management
Support flexible transition definitions:
- Add transitions:
(from_state, event, to_state) - Allow multiple events from the same state
- Prevent duplicate transitions
- Support wildcard transitions
- Validate that transitions form a valid graph
- Query available events from current state
Example Usage:
1sm.AddTransition("idle", "start", "running")
2sm.AddTransition("idle", "pause", "paused")
3sm.AddTransition("running", "pause", "paused")
4sm.AddTransition("running", "stop", "idle")
5sm.AddTransition("paused", "resume", "running")
6// From idle: can trigger "start" or "pause"
3. State Entry Callbacks
Execute code when entering a state:
- Register callbacks for specific states
- Execute callback after state change completes
- Support multiple callbacks per state
- Callbacks receive previous state as parameter
- Useful for logging, metrics, side effects
Example Usage:
1sm.OnEnter("running", func(from State) {
2 log.Printf("Started: %s → running", from)
3 startTimer()
4})
5sm.OnEnter("idle", func(from State) {
6 log.Printf("Stopped: %s → idle", from)
7 stopTimer()
8})
4. State Exit Callbacks
Execute code when leaving a state:
- Register callbacks for specific states
- Execute callback before state change begins
- Support cleanup operations
- Callbacks receive next state as parameter
- Complement to entry callbacks
Example Usage:
1sm.OnExit("running", func(to State) {
2 saveProgress()
3 log.Printf("Exiting running → %s", to)
4})
5. Transition Guards
Validate transitions with conditional logic:
- Add guard functions to specific transitions
- Guards return bool
- Multiple guards use AND logic
- Guards execute before state change
- Guards receive from, event, to parameters
Example Usage:
1sm.AddGuard("idle", "start", func(from, to State) bool {
2 return hasPermission() && resourcesAvailable()
3})
4sm.Trigger("start") // Only succeeds if guard returns true
6. Transition History
Track state changes over time:
- Record each successful transition
- Include timestamp, from state, event, to state
- Support querying history
- Limit history size
- Useful for debugging and auditing
Example Usage:
1sm.Trigger("start") // idle → running
2sm.Trigger("pause") // running → paused
3sm.Trigger("resume") // paused → running
4
5history := sm.History()
6// Returns: [
7// {Time: t1, From: "idle", Event: "start", To: "running"},
8// {Time: t2, From: "running", Event: "pause", To: "paused"},
9// {Time: t3, From: "paused", Event: "resume", To: "running"}
10// ]
Type Signatures
1package fsm
2
3import "time"
4
5// State represents a state in the machine
6type State string
7
8// Event represents a trigger that causes state transitions
9type Event string
10
11// Transition represents a state change
12type Transition struct {
13 From State
14 Event Event
15 To State
16}
17
18// HistoryEntry records a state transition
19type HistoryEntry struct {
20 Time time.Time
21 From State
22 Event Event
23 To State
24}
25
26// CallbackFunc is executed on state entry/exit
27type CallbackFunc func(otherState State)
28
29// GuardFunc validates whether a transition is allowed
30type GuardFunc func(from, to State) bool
31
32// StateMachine manages states and transitions
33type StateMachine struct {
34 current State
35 transitions map[State]map[Event]State
36 onEnter map[State][]CallbackFunc
37 onExit map[State][]CallbackFunc
38 guards map[Transition][]GuardFunc
39 history []HistoryEntry
40 maxHistory int
41 mu sync.RWMutex
42}
43
44// Core functions
45func NewStateMachine(initial State) *StateMachine
46func AddTransition(from State, event Event, to State) *StateMachine
47func Trigger(event Event) error
48func Current() State
49
50// Callback functions
51func OnEnter(state State, callback CallbackFunc) *StateMachine
52func OnExit(state State, callback CallbackFunc) *StateMachine
53
54// Guard functions
55func AddGuard(from State, event Event, guard GuardFunc) *StateMachine
56
57// History functions
58func History() []HistoryEntry
59func SetMaxHistory(max int)
60
61// Query functions
62func CanTrigger(event Event) bool
63func AvailableEvents() []Event
Example: Order Processing FSM
Here's a realistic state machine for order processing:
1package main
2
3import (
4 "fmt"
5 "log"
6 "your-module/fsm"
7)
8
9func main() {
10 // Create order state machine
11 sm := fsm.NewStateMachine("pending")
12
13 // Define state transitions
14 sm.AddTransition("pending", "pay", "paid").
15 AddTransition("paid", "ship", "shipped").
16 AddTransition("shipped", "deliver", "delivered").
17 AddTransition("pending", "cancel", "cancelled").
18 AddTransition("paid", "cancel", "refunded")
19
20 // Add guard: only ship if payment verified
21 sm.AddGuard("paid", "ship", func(from, to fsm.State) bool {
22 verified := verifyPayment()
23 if !verified {
24 log.Println("Payment not verified, cannot ship")
25 }
26 return verified
27 })
28
29 // Add entry callbacks for logging
30 sm.OnEnter("paid", func(from fsm.State) {
31 log.Printf("Payment received for order")
32 sendConfirmationEmail()
33 })
34
35 sm.OnEnter("shipped", func(from fsm.State) {
36 log.Printf("Order shipped")
37 sendTrackingEmail()
38 })
39
40 sm.OnEnter("delivered", func(from fsm.State) {
41 log.Printf("Order delivered")
42 requestReview()
43 })
44
45 // Add exit callback for cleanup
46 sm.OnExit("pending", func(to fsm.State) {
47 log.Printf("Leaving pending state → %s", to)
48 clearPendingTimer()
49 })
50
51 // Process order
52 fmt.Printf("Current state: %s\n", sm.Current()) // pending
53
54 sm.Trigger("pay") // pending → paid
55 sm.Trigger("ship") // paid → shipped
56 sm.Trigger("deliver") // shipped → delivered
57
58 // View history
59 for _, entry := range sm.History() {
60 fmt.Printf("%s: %s --%s--> %s\n",
61 entry.Time.Format("15:04:05"),
62 entry.From, entry.Event, entry.To)
63 }
64}
65
66func verifyPayment() bool { return true }
67func sendConfirmationEmail() {}
68func sendTrackingEmail() {}
69func requestReview() {}
70func clearPendingTimer() {}
Test Cases
Your implementation should pass these scenarios:
1// Test basic transitions
2func TestBasicTransition() {
3 sm := NewStateMachine("off")
4 sm.AddTransition("off", "turn_on", "on")
5
6 err := sm.Trigger("turn_on")
7 // err should be nil
8 // sm.Current() should be "on"
9}
10
11// Test invalid transition
12func TestInvalidTransition() {
13 sm := NewStateMachine("off")
14 sm.AddTransition("off", "turn_on", "on")
15
16 err := sm.Trigger("invalid_event")
17 // err should not be nil
18 // sm.Current() should still be "off"
19}
20
21// Test entry callback
22func TestEntryCallback() {
23 sm := NewStateMachine("idle")
24 sm.AddTransition("idle", "start", "running")
25
26 var called bool
27 var previousState State
28 sm.OnEnter("running", func(from State) {
29 called = true
30 previousState = from
31 })
32
33 sm.Trigger("start")
34 // called should be true
35 // previousState should be "idle"
36}
37
38// Test exit callback
39func TestExitCallback() {
40 sm := NewStateMachine("running")
41 sm.AddTransition("running", "stop", "idle")
42
43 var called bool
44 var nextState State
45 sm.OnExit("running", func(to State) {
46 called = true
47 nextState = to
48 })
49
50 sm.Trigger("stop")
51 // called should be true
52 // nextState should be "idle"
53}
54
55// Test guard blocks transition
56func TestGuardBlocks() {
57 sm := NewStateMachine("locked")
58 sm.AddTransition("locked", "unlock", "unlocked")
59 sm.AddGuard("locked", "unlock", func(from, to State) bool {
60 return false // Always deny
61 })
62
63 err := sm.Trigger("unlock")
64 // err should indicate guard failed
65 // sm.Current() should still be "locked"
66}
67
68// Test guard allows transition
69func TestGuardAllows() {
70 sm := NewStateMachine("locked")
71 sm.AddTransition("locked", "unlock", "unlocked")
72 sm.AddGuard("locked", "unlock", func(from, to State) bool {
73 return true // Always allow
74 })
75
76 err := sm.Trigger("unlock")
77 // err should be nil
78 // sm.Current() should be "unlocked"
79}
80
81// Test multiple guards
82func TestMultipleGuards() {
83 sm := NewStateMachine("idle")
84 sm.AddTransition("idle", "start", "running")
85 sm.AddGuard("idle", "start", func(from, to State) bool {
86 return true // First guard passes
87 })
88 sm.AddGuard("idle", "start", func(from, to State) bool {
89 return false // Second guard fails
90 })
91
92 err := sm.Trigger("start")
93 // err should indicate guard failed
94 // sm.Current() should still be "idle"
95}
96
97// Test history tracking
98func TestHistory() {
99 sm := NewStateMachine("a")
100 sm.AddTransition("a", "next", "b")
101 sm.AddTransition("b", "next", "c")
102
103 sm.Trigger("next") // a → b
104 sm.Trigger("next") // b → c
105
106 history := sm.History()
107 // len(history) should be 2
108 // history[0].From should be "a"
109 // history[0].To should be "b"
110 // history[1].From should be "b"
111 // history[1].To should be "c"
112}
113
114// Test concurrent access
115func TestConcurrentAccess() {
116 sm := NewStateMachine("idle")
117 sm.AddTransition("idle", "toggle", "active")
118 sm.AddTransition("active", "toggle", "idle")
119
120 var wg sync.WaitGroup
121 for i := 0; i < 100; i++ {
122 wg.Add(1)
123 go func() {
124 defer wg.Done()
125 sm.Trigger("toggle")
126 _ = sm.Current()
127 }()
128 }
129 wg.Wait()
130 // Should not panic
131}
Common Pitfalls
⚠️ Watch out for these common mistakes:
- Race conditions: Multiple goroutines accessing state without proper locking causes data races
- Forgetting to validate events: Always check if transition exists before changing state
- Callback panic handling: Panics in callbacks can crash the state machine - consider defer/recover
- Circular dependencies in guards: Guards that check other state machine states can deadlock
- History memory leak: Unbounded history can consume infinite memory - implement max size
- Guard vs callback confusion: Guards run before transition, callbacks run after
- Not returning errors: Invalid transitions should return descriptive errors, not silently fail
Hints
💡 Hint 1: Nested Map Structure
Use nested maps for efficient transition lookup:
1transitions map[State]map[Event]State
2
3// To find next state:
4if eventMap, ok := sm.transitions[currentState]; ok {
5 if nextState, ok := eventMap[event]; ok {
6 // Valid transition found
7 }
8}
💡 Hint 2: Callback Execution Order
Execute callbacks in this order:
1// 1. Check guards
2for _, guard := range guards {
3 if !guard(from, to) {
4 return errors.New("guard failed")
5 }
6}
7
8// 2. Execute exit callbacks
9for _, callback := range sm.onExit[currentState] {
10 callback(nextState)
11}
12
13// 3. Change state
14sm.current = nextState
15
16// 4. Execute entry callbacks
17for _, callback := range sm.onEnter[nextState] {
18 callback(previousState)
19}
💡 Hint 3: Concurrent Access Pattern
Use RWMutex for better read performance:
1func Current() State {
2 sm.mu.RLock()
3 defer sm.mu.RUnlock()
4 return sm.current
5}
6
7func Trigger(event Event) error {
8 sm.mu.Lock()
9 defer sm.mu.Unlock()
10 // Perform transition
11}
💡 Hint 4: History Circular Buffer
Implement bounded history with a circular buffer or slice trimming:
1// Add to history
2sm.history = append(sm.history, entry)
3
4// Trim if too large
5if len(sm.history) > sm.maxHistory {
6 sm.history = sm.history[1:] // Remove oldest
7}
Solution
Click to see the solution
1package fsm
2
3import (
4 "fmt"
5 "sync"
6 "time"
7)
8
9type State string
10type Event string
11
12type Transition struct {
13 From State
14 Event Event
15 To State
16}
17
18type HistoryEntry struct {
19 Time time.Time
20 From State
21 Event Event
22 To State
23}
24
25type CallbackFunc func(otherState State)
26type GuardFunc func(from, to State) bool
27
28type StateMachine struct {
29 current State
30 transitions map[State]map[Event]State
31 onEnter map[State][]CallbackFunc
32 onExit map[State][]CallbackFunc
33 guards map[Transition][]GuardFunc
34 history []HistoryEntry
35 maxHistory int
36 mu sync.RWMutex
37}
38
39func NewStateMachine(initial State) *StateMachine {
40 return &StateMachine{
41 current: initial,
42 transitions: make(map[State]map[Event]State),
43 onEnter: make(map[State][]CallbackFunc),
44 onExit: make(map[State][]CallbackFunc),
45 guards: make(map[Transition][]GuardFunc),
46 history: make([]HistoryEntry, 0),
47 maxHistory: 100,
48 }
49}
50
51func AddTransition(from State, event Event, to State) *StateMachine {
52 sm.mu.Lock()
53 defer sm.mu.Unlock()
54
55 if sm.transitions[from] == nil {
56 sm.transitions[from] = make(map[Event]State)
57 }
58 sm.transitions[from][event] = to
59
60 return sm
61}
62
63func Trigger(event Event) error {
64 sm.mu.Lock()
65 defer sm.mu.Unlock()
66
67 // Find next state
68 eventMap, ok := sm.transitions[sm.current]
69 if !ok {
70 return fmt.Errorf("no transitions from state %q", sm.current)
71 }
72
73 nextState, ok := eventMap[event]
74 if !ok {
75 return fmt.Errorf("invalid event %q in state %q", event, sm.current)
76 }
77
78 // Check guards
79 transition := Transition{From: sm.current, Event: event, To: nextState}
80 for _, guard := range sm.guards[transition] {
81 if !guard(sm.current, nextState) {
82 return fmt.Errorf("guard prevented transition from %q to %q", sm.current, nextState)
83 }
84 }
85
86 previousState := sm.current
87
88 // Execute exit callbacks
89 for _, callback := range sm.onExit[sm.current] {
90 callback(nextState)
91 }
92
93 // Change state
94 sm.current = nextState
95
96 // Execute entry callbacks
97 for _, callback := range sm.onEnter[sm.current] {
98 callback(previousState)
99 }
100
101 // Record history
102 sm.history = append(sm.history, HistoryEntry{
103 Time: time.Now(),
104 From: previousState,
105 Event: event,
106 To: nextState,
107 })
108
109 // Trim history if needed
110 if len(sm.history) > sm.maxHistory {
111 sm.history = sm.history[1:]
112 }
113
114 return nil
115}
116
117func Current() State {
118 sm.mu.RLock()
119 defer sm.mu.RUnlock()
120 return sm.current
121}
122
123func OnEnter(state State, callback CallbackFunc) *StateMachine {
124 sm.mu.Lock()
125 defer sm.mu.Unlock()
126
127 sm.onEnter[state] = append(sm.onEnter[state], callback)
128 return sm
129}
130
131func OnExit(state State, callback CallbackFunc) *StateMachine {
132 sm.mu.Lock()
133 defer sm.mu.Unlock()
134
135 sm.onExit[state] = append(sm.onExit[state], callback)
136 return sm
137}
138
139func AddGuard(from State, event Event, guard GuardFunc) *StateMachine {
140 sm.mu.Lock()
141 defer sm.mu.Unlock()
142
143 transition := Transition{From: from, Event: event}
144 sm.guards[transition] = append(sm.guards[transition], guard)
145 return sm
146}
147
148func History() []HistoryEntry {
149 sm.mu.RLock()
150 defer sm.mu.RUnlock()
151
152 result := make([]HistoryEntry, len(sm.history))
153 copy(result, sm.history)
154 return result
155}
156
157func SetMaxHistory(max int) {
158 sm.mu.Lock()
159 defer sm.mu.Unlock()
160
161 sm.maxHistory = max
162 if len(sm.history) > max {
163 sm.history = sm.history[len(sm.history)-max:]
164 }
165}
166
167func CanTrigger(event Event) bool {
168 sm.mu.RLock()
169 defer sm.mu.RUnlock()
170
171 eventMap, ok := sm.transitions[sm.current]
172 if !ok {
173 return false
174 }
175 _, ok = eventMap[event]
176 return ok
177}
178
179func AvailableEvents() []Event {
180 sm.mu.RLock()
181 defer sm.mu.RUnlock()
182
183 eventMap, ok := sm.transitions[sm.current]
184 if !ok {
185 return nil
186 }
187
188 events := make([]Event, 0, len(eventMap))
189 for event := range eventMap {
190 events = append(events, event)
191 }
192 return events
193}
Key Takeaways
- FSMs model systems with discrete states and transitions
- Guards validate transitions before they occur
- Callbacks provide hooks for entry/exit logic
- Thread safety is critical for concurrent access
- History tracking aids debugging and auditing
- Fluent APIs improve configuration ergonomics