During the last 18 months I’ve developed software that heavily relied on statemachines to synchronize the behavior of a distributed system with many nodes. When I first designed the system I was very wary of using statemachines, due to the experiences I’ve had with naive implementations during the last twelve years. Especially in embedded your usual programmer will go ahead an program statemachines as a monster of switchcases that could as well be Perl with respect to maintainability. I’ve looked into the abyss and it didn’t like it. So far for my experiences with statemachines. I guess I might have come into contact with the wrong implementations for most parts of my professional life until now, because frankly, statemachines are a greate model to reason about a system’s behavior and even better suited to synchronize different systems with each other. If only the implementations weren’t so horrible.
Enter pytransitions. Yes, not embedded but an interesting design nontheless. As a consumer of the library I don’t have to bother with statemanagement at all and can concentrate on the actual logic contained in the states. While pytransitions has quite a lot of flaws (with it being stringly typed probably being the worst) the core idea was intriguing. So, naturally I wanted to see if I could do something similar using Rust. Now, Rust’s typesystem doesn’t exactly make this easy for us, with no inheritance and the ownership model creating a number of things to consider. But alas – there’s the internet and the Rustbook, which all have their own thoughts on statemachines. Only, that these statemachine designs are IMHO unusable for a lot of usecases. The core problem is, that they usually try to drink Rust’s coolaid and want to somehow validate all transitions at compile time. This is an absolute non starter for a lot of usecases, as it implies knowing the state we are in at each and every point in time by means of having a typed variable to store the current state in:
fn main()
{
let state = State0::new();
let state2 = state.to_state2(); // state2 is of type State2
let state3 = state.to_state3(); // state3 is of type State3
}
See https://blog.yoshuawuyts.com/state-machines/ and https://hoverbear.org/blog/rust-state-machine-pattern/ for more details on what is currently the community’s answer to statemachines. So, why don’t I like this? From a purely academical standpoint this is actually a very interesting solution, however it falls short for common usecases (e.g. parsing a protocol is actually pretty messy with this approach) and it does not lend itself to the same kind of seperation of statelogic from the statemachine logic as libraries such as boost.statechart or pytransitions do. So, I set out to build something that – IMHO – has better real-world usability as common approaches used in Rust.
Design Philosopies
There are two fundamental ways of implementing statemachine libraries with respect to usercode:
- Doing work in the state implementations
- Doing work in during the state transitions
For this work I chose the latter due to Rust making it easier to model for different events this way.
Goals
The goal is to design a state machine library, that:
- … allows us to model the machine’s states
- … allows us to model the machine’s legal transitions
- … allows us to inject usercode
- … doesn’t need the user to dive into the inner workings of the machine.
Getting started
I started off with imagining an ideal interface, that I would like to use, and came up with a rather simple structure. Each machine consists of:
- … An enumeration containing all states
- … A starting state
- … An enumeration containing all events
- … a list of valid transitions linking two states to each other by means of an event.
This is actually pretty close to the canonical definition of a statemachine in theoretical computer science.
States
The states enum needs to be a plain enum with no addional enumdata, i.e.:
enum State
{
Standing,
Walking,
Running
}
Due to the FSM needing to be able to instanciate all states we cannot let the states carry additional data.
Events
Events are an enum as well, but in contrast to the states the typesystem doesn’t keep us from using additional data on enum variants:
enum Event
{
Start,
Stop,
Run(speed: u32)
}
Transitions
Thus, our basic transition is:
struct Transition<StateType, EventType>
{
from: StateType,
to: StateType,
triggered_by: EventType
}
The Machine
The FSM itself is then rather simple
struct FSM<StateType, EventType>
{
current_state: StateType,
transitions: Vec<Transition<StateType, EventType>>
}
Now we only need a single function to step through the statemachine:
let fsm = FSM<State,Event>::new(); /*..*/ fsm.trigger_event(Event::Start);
Obviously there’s some details missing here, that we will look into further down the line. Let’s first adress the elephant in the room: How do we inject usercode here? I’ve left out that part until now, so we make a minor addition to the transition:
struct Transition<StateType, EventType>
{
from: StateType,
to: StateType,
triggered_by: EventType,
trigger_func: Option<Box<dyn FnMut(EventType) ->()>>
}
Okay, the type of the trigger_function looks a bit ghastly, so lets take this apart: The typedefinition tells us, that we can optionally have a functionpointer to a function that takes an instance of the EventType for the transition. Why would we need to pass this instance along – we already know what happened, when the functionpointer is called? The motivation is, to be able to capture data attached to the EventType instance’s enum variant, e.g. the “speed” value in;
enum Event
{
Start,
Stop,
Run(speed: u32)
}
Now, if we pass a matching lambda into the transition we can have our usercode be called, whenever a given transition is triggered. The FSM itself can take care to only ever trigger transitions that are actually defined.
A more complete example
fn main()
{
let on_running = |_arg: Event| {
println!("Now running!")
};
let fsm = FiniteStateMachine::new(State::Stop, // Initial State
vec![
Transition::new(State::Stop, State::Walking, Event::Start),
Transition::new_trig(State::Stop, State::Running, Event::Run(0), Box::new(on_running),
Transition::new(State::Walking, State::Stop, Event::Stop),
Transition::new(State::Running, State::Stop, Event::Stop)
]);
fsm.trigger_event(Event::Running(47));
}
A quick explaination on Event::Run(0): The 0 is a placeholder, since we cannot instanciate an enumvariant without filling all its members. At runtime you can pass any value into run. Note that you will still have to “cast” the enum into the correct variant in the callback e.g. by means of if let Event::Run(speed) = _arg ...
Managing state for your state…
To do something meaningful in your callbacks you’ll probably need to access some kind of external state. The easiest way of doing this is by means of an Rc, e.g.:
/*...*/
let mySharedState: Rc<RefCell<i32>> = Rc::new(RefCell::new(42));
let stateForOnRunning = mySharedState.clone();
let on_running = |_arg: Event| {
println!("Now running!")
/*
do stuff with stateForOnRunning here, variable will
be moved into the closure
*/
};
Getting the code
The code to the crate fsm_rs is available on github: https://github.com/rincewound/fsm_rs and is BSD licensed. It is also available on crates.io
At last: As usual the code is not production ready, but should serve as inspiration. I’ll leave it up to the user to aadjust it for production use cases.