Implementing a simple state machine with no dynamic allocation and compile time assertion

I'm thinking about a state machine that forces me to implement all state transitions at compile time, so no dynamic allocation is used. I'd like to do

let machine = RtspMachine::begin();
machine.event(...);
machine.event(...);

and event would change the internal state of the machine.

Here's my sketch:

struct Init {}

struct Ready{}

struct Playing{}

struct Recording{}

struct _RtspState<T> {
    t: T
}

type RtspState<T> = _RtspState<T>;

trait StateChange where Self: Sized {
    fn from<T>(self, state: &RtspState<T>, event: &Event) -> std::result::Result<RtspMachine, EventError>;
}

impl StateChange for RtspMachine {
    fn from(self, state: RtspState<Init>, event: &Event) -> std::result::Result<RtspMachine, EventError> {
        //...        
    }
    fn from(self, state: RtspState<Init>, event: &Event) -> std::result::Result<RtspMachine, EventError> {
        //...        
    }
    //...
}

pub(crate) struct RtspMachine {
    state: RtspState
}

The problem is that in order to ensure in compile time that I implemented all transitions, the RtspState must be generic, so I can match over its types. But then, the RtspMachine would have to be generic, thus I'd not be able to simply do machine.event to modify its internal state because its type would change on a state transition.

I thought of doing

enum RtspState {
    Init,
    Ready,
    Playing,
    Recording,
}

but then I cannot match over the state, because RtspState::Init is not a type, but a variant.

One solution would be to make a enum RtspMachineWrapper:

enum RtspMachineWrapper {
    RtspMachine<Init>,
    RtspMachine<Ready>,
    RtspMachine<Playing>,
    RtspMachine<Recording>
}

but then I'd have to reimplement every RtspMachine call to RtspMachineWrapper by doing a large match over all states.

What should I do?

Solution

It looks to me like you're confusing two slightly different patterns that are often used with state machines.

The first is to ensure that every transition is handled nicely by encapsulating the FSM in an enum.

enum RtspState {
  Init,
  Ready,
  Playing,
  Recording,
}

impl RtspState {
  pub fn on_event(&self, event: &Event) -> std::result::Result<Self, EventError> {
    match self {
      Init => Ok(Ready),
      Ready => if event.foo { Ok(Playing) } else { Err(EventError::new("bang")) },
      ...
      // The compiler will complain if we miss any.
    }
  }
}

pub fn main() -> EventError {
  let state = RtspState::Init;
  let state = state.on_event(an_event());
  let state = state.on_event(foo_event());
  ...
}

The other pattern is to create a FSM where invalid events are impossible at compile time. This doesn't use an enum, but uses separate structs as you have in your example. The difference is that only limited events are supported by each struct type.

struct Init {}
struct Ready {}
struct Playing {}
struct Recording {}

struct AnEvent {}
struct FooEvent {}

impl Init {
  pub fn on_an_event(self, e: &AnEvent) -> Ready {
    Ready
  }
}

impl Ready {
  pub fn on_foo_event(self, e: &FooEvent) -> Playing {
     Playing
  }
}

pub fn main() {
  let state = Init;
  let state = state.on_an_event(an_event());
  let state = state.on_foo_event(foo_event());
  // The compiler will complain if we try to do an invalid event.
}

This second form can also be done using traits (as asked by @anon2328).

Here you have (at least) two different ways of doing things, the first and easiest is to use boxed traits.

pub trait Init {
 fn on_an_event(self, e: &AnEvent) -> Box<dyn Ready>;
}

pub trait Ready {
 fn on_foo_event(self, e: &FooEvent) -> Box<dyn Playing>;
}

pub trait Playing {}

// You could put all the traits on one object, 
// or you could create separate types for them.
struct AllAtOnce {}

impl Init for AllAtOnce {
  fn on_an_event(self, e: &AnEvent) -> Box<dyn Ready> {
     Box::new(self)
  }
}

impl Ready for AllAtOnce {
  fn on_foo_event(self, e: &FooEvent) -> Box<dyn Playing> {
         Box::new(self)
  }
}

impl Playing for AllAtOnce {}

fn doit(Box<Init> state) {
  let state: Box<Ready> = state.on_an_event(an_event());
  let state: Box<Playing> = state.on_foo_event(foo_event());
}

fn main() {
  doit(Box::new(AllAtOnce));
}

The second way is to use associated types:

pub struct AnEvent;
pub struct FooEvent;

pub trait Init {
    type Ready: Ready;
    fn on_an_event(self, e: &AnEvent) -> Self::Ready;
}

pub trait Ready {
    type Playing: Playing;
    fn on_foo_event(self, e: &FooEvent) -> Self::Playing;
}

pub trait Playing {}

struct InitImpl;
impl Init for InitImpl {
    type Ready = ReadyImpl;
    fn on_an_event(self, e: &AnEvent) -> Self::Ready {
        ReadyImpl
    }
}

struct ReadyImpl;
impl Ready for ReadyImpl {
    type Playing = PlayingImpl;
    fn on_foo_event(self, e: &FooEvent) -> Self::Playing {
        PlayingImpl
    }
}

struct PlayingImpl;
impl Playing for PlayingImpl {}

pub fn doit<T: Init>(state: T) {
    let state = state.on_an_event(&AnEvent);
    let state = state.on_foo_event(&FooEvent);

    // Gives the error:
    //   no method named `something` found for associated type
    //  `<<T as Init>::Ready as Ready>::Playing` in the current scope
    // state.something();
}

fn main() {
    let state = InitImpl;
    doit(state);
}