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?

I think there is some confusion about Rust's type and generic system going on here. For example:

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> {
        //...        
    }
    //...
}

(I assume you meant some other state struct than Init for the second from.)

This won't work[0] -- you would need to implement the generic version, which the compiler monomorphizes as needed:

impl StateChange for RtspMachine {
    // Just the one method definition
    fn from<T>(self, state: RtspState<T>, event: &Event) -> Result<RtspMachine, EventError> { todo!() }
}

And also:

Because RtspState is generic, either RtspMachine needs to be generic, or a concrete (non-generic) form of RtspState needs to be used:

pub(crate) struct RtspMachine<T> {
    state: RtspState<T>,
}
// OR:
pub(crate) struct RtspMachine { // <-- not generic
    state: RtspState<Init>, // <-- but also not generic
}

And I'm not sure what you mean by this either, unless perhaps it's your multiple-from-methods formulation:

...because types are not something you match over[1]. Rust is statically typed.

You can use enums to make a state machine, and Rust will make sure every match handles every variant at compile time, but they'll still branch at run time. Or you can use types to model your state machine and get a lot of compiler time guarantees, but then yes, every state will be a distinct type (that's the idea). I'm afraid given everything else, I'm not really sure what you're going for.


[0]: Modulo some sort of specialization, which is an experimental and unstable feature (and I don't know that it covers this case either).

[1]: You can downcast trait objects. It's not a common pattern.