finite_state_machine.md (6758B)
1 # Finite State Machine 2 3 A **state machine** (or finite state machine, FSM) is a behavioral model where a 4 system can exist in exactly one of a finite number of states at any given time, 5 and transitions between states are triggered by specific events or conditions. 6 Rust is particularly well-suited for state machines because its type system can 7 enforce valid transitions either at runtime (using enums) or at compile time 8 (using the typestate 9 pattern).[^1](https://www.itemis.com/en/products/itemis-create/documentation/user-guide/overview_what_are_state_machines) 10 11 --- 12 13 ## Core Concepts 14 15 Three building blocks define any state 16 machine:[^2](https://www.ni.com/docs/en-US/bundle/patools/page/what-is-a-state-machine.html) 17 18 - **States** – distinct situations a system can be in (e.g., `Created`, `Paid`, 19 `Shipped`) 20 - **Transitions** – rules that move the system from one state to another 21 - **Events** – inputs/triggers that cause a transition (e.g., "payment 22 received") 23 24 A system can only be in **one state at a time**, and transitions that don't 25 exist for the current state are simply 26 invalid.[^3](https://stately.ai/blog/2023-10-02-what-is-a-state-machine) 27 28 --- 29 30 ## Approach 1: Enum-Based State Machine 31 32 The simplest Rust approach uses `enum` variants to represent states and pattern 33 matching to handle transitions. Here's an order-processing 34 example:[^4](https://oneuptime.com/blog/post/2026-02-01-rust-state-machines/view) 35 36 ```rust 37 #[derive(Debug, Clone)] 38 enum OrderState { 39 Created { items: Vec<String>, total: f64 }, 40 Paid { items: Vec<String>, total: f64, payment_id: String }, 41 Shipped { items: Vec<String>, tracking_number: String }, 42 Delivered { delivered_at: String }, 43 Cancelled { reason: String }, 44 } 45 46 #[derive(Debug)] 47 struct Order { 48 id: String, 49 state: OrderState, 50 } 51 52 impl Order { 53 fn new(id: String, items: Vec<String>, total: f64) -> Self { 54 Order { id, state: OrderState::Created { items, total } } 55 } 56 57 // Transition only valid from Created state 58 fn pay(self, payment_id: String) -> Result<Self, &'static str> { 59 match self.state { 60 OrderState::Created { items, total } => Ok(Order { 61 id: self.id, 62 state: OrderState::Paid { items, total, payment_id }, 63 }), 64 _ => Err("Can only pay for orders in Created state"), 65 } 66 } 67 68 fn ship(self, tracking_number: String) -> Result<Self, &'static str> { 69 match self.state { 70 OrderState::Paid { items, .. } => Ok(Order { 71 id: self.id, 72 state: OrderState::Shipped { items, tracking_number }, 73 }), 74 _ => Err("Can only ship paid orders"), 75 } 76 } 77 } 78 79 fn main() { 80 let order = Order::new("ORD-001".to_string(), vec!["Widget".to_string()], 99.99); 81 let order = order.pay("PAY-123".to_string()).unwrap(); 82 let order = order.ship("TRACK-456".to_string()).unwrap(); 83 println!("{:?}", order); 84 } 85 ``` 86 87 This catches invalid transitions **at runtime** via `Result`. It's simple and 88 easy to understand, but bugs only surface when that code path is 89 hit.[^4](https://oneuptime.com/blog/post/2026-02-01-rust-state-machines/view) 90 91 --- 92 93 ## Approach 2: Typestate Pattern (Compile-Time Safety) 94 95 The **typestate pattern** encodes state into the _type itself_ using generics, 96 so the Rust compiler rejects invalid transitions before your code ever 97 runs.[^4](https://oneuptime.com/blog/post/2026-02-01-rust-state-machines/view) 98 99 ```rust 100 use std::marker::PhantomData; 101 102 // Zero-sized marker types — no runtime cost 103 struct Created; 104 struct Paid { payment_id: String } 105 struct Shipped { tracking_number: String } 106 107 struct Order<St> { 108 id: String, 109 items: Vec<String>, 110 total: f64, 111 state_data: St, 112 } 113 114 // Methods only available on Order<Created> 115 impl Order<Created> { 116 fn new(id: String, items: Vec<String>, total: f64) -> Self { 117 Order { id, items, total, state_data: Created } 118 } 119 120 fn pay(self, payment_id: String) -> Order<Paid> { 121 Order { id: self.id, items: self.items, total: self.total, 122 state_data: Paid { payment_id } } 123 } 124 } 125 126 // Methods only available on Order<Paid> 127 impl Order<Paid> { 128 fn ship(self, tracking_number: String) -> Order<Shipped> { 129 Order { id: self.id, items: self.items, total: self.total, 130 state_data: Shipped { tracking_number } } 131 } 132 } 133 134 fn main() { 135 let order = Order::new("ORD-001".to_string(), vec!["Widget".to_string()], 49.99); 136 let paid = order.pay("PAY-123".to_string()); // ✅ Created → Paid 137 let shipped = paid.ship("TRACK-456".to_string()); // ✅ Paid → Shipped 138 139 // ❌ This would FAIL TO COMPILE — ship() doesn't exist on Order<Created> 140 // let bad = order.ship("TRACK-789".to_string()); 141 } 142 ``` 143 144 Because `ship()` is only implemented on `Order<Paid>`, calling it on an unpaid 145 order is a **compile-time error**, not a runtime 146 bug.[^4](https://oneuptime.com/blog/post/2026-02-01-rust-state-machines/view) 147 148 --- 149 150 ## Which Approach to Choose? 151 152 | | Enum-Based | Typestate Pattern | 153 | :-------------------------------- | :------------------------ | :--------------------------------- | 154 | **Error detection** | Runtime | Compile time | 155 | **Complexity** | Low | Medium–High | 156 | **Dynamic state** (e.g., from DB) | ✅ Easy | ❌ Needs wrapper enum | 157 | **IDE autocomplete** | Shows all methods | Shows only valid methods | 158 | **Best for** | Prototyping, simple flows | Financial, safety-critical systems | 159 160 In practice, many production systems use **both**: typestate for core business 161 logic, with an enum wrapper (`AnyOrder`) for serialization and dynamic event 162 handling.[^4](https://oneuptime.com/blog/post/2026-02-01-rust-state-machines/view) 163 164 [^5]: https://www.freecodecamp.org/news/state-machines-basics-of-computer-science-d42855debc66/ 165 166 [^6]: https://www.youtube.com/watch?v=sosnUnI-vco 167 168 [^7]: https://www.reddit.com/r/learnprogramming/comments/1g5yxci/state_machines_for_a_beginner/ 169 170 [^8]: https://github.com/Lifestreams-ai/statemachine 171 172 [^9]: https://uk.mathworks.com/discovery/state-machine.html 173 174 [^10]: https://docs.rs/simple_statemachine 175 176 [^11]: https://www.reddit.com/r/rust/comments/18fugz0/state_machines_implementation/ 177 178 [^12]: https://www.stateworks.com/technology/understanding-state-machines/ 179 180 [^13]: https://en.wikipedia.org/wiki/Finite-state_machine 181 182 [^14]: https://users.rust-lang.org/t/on-state-machines/114910 183 184 [^15]: https://sparxsystems.com/resources/tutorials/uml2/state-diagram.html