Finite State Machine

A model of computation where there is exactly one state at a time of a fixed number states. The current state can be changed by transitioning to another. Using state machines has the benefit of 1) being easy to reason about what the program does e.g. security audit and 2) making obvious what a valid state is so the programmer doesn’t accidentally put into a ‘bad’ state i.e. reduce bugs.

Example applications:

  • Modeling authentication flows using a deterministic state machine to prove it can not be exploited
  • Modeling a user interface that has several modes to prevent bugs where a user gets stuck in an unrecoverable state

The following example uses rustlang’s type system to model a finite state machine where transitions can be passed additional typed arguments:

pub struct StateMachine<T> {
    pub state: T
}

pub struct StateMachineWithArgs<T> {
    pub state: T,
}

pub trait TransitionFrom<T, R> {
    fn transition_from(state: T, args: R) -> Self;
}

pub trait State {
    type Args;
    fn new(args: Self::Args) -> Self;
}

impl<T> StateMachineWithArgs<T> where T: State {
    pub fn new(state: T) -> Self {
        StateMachineWithArgs { state }
    }
}

struct StateOne;
impl State for StateOne {
    type Args = ();

    fn new(args: Self::Args) -> Self {
        Self {}
    }
}

struct StateTwo;
impl State for StateTwo {
    type Args = ();

    fn new(args: Self::Args) -> Self {
        Self {}
    }
}

struct StateThree;
impl State for StateThree {
    type Args = ();

    fn new(args: Self::Args) -> Self {
        Self {}
    }
}

// Implement state transitions by implementing the TransitionFrom trait.
// Doing this enforces only known transitions at compile time i.e.
// you get a compile time error that two states can't be transitioned to

impl TransitionFrom<StateMachineWithArgs<StateOne>, ()> for StateMachineWithArgs<StateTwo> {
    fn transition_from(state: StateMachineWithArgs<StateOne>, args: ()) -> StateMachineWithArgs<StateTwo> {
        StateMachineWithArgs::new(StateTwo::new(args))
    }
}

impl TransitionFrom<StateMachineWithArgs<StateTwo>, ()> for StateMachineWithArgs<StateThree> {
    fn transition_from(state: StateMachineWithArgs<StateTwo>, args: ()) -> StateMachineWithArgs<StateThree> {
        StateMachineWithArgs::new(StateThree::new(args))
    }
}

mod test_state_machine {
    use super::*;

    #[test]
    fn it_works() {
        // Initialize the state machine starting with the first state
        let state_one = StateMachineWithArgs::new(StateOne::new(()));

        // Transition to the next state
        let state_two = StateMachineWithArgs::<StateTwo>::transition_from(state_one, ());

        // This won't compile because it's not a valid transition!
        StateMachineWithArgs::<StateThree>::transition_from(state_one, ());
    }
}