MagicStateMachines

MagicStateMachines provides typestate wrappers for compiler-enforced state machines whose contract can live in a separate crate from the runtime implementation.

The library is nightly-only because it uses arbitrary_self_types.

This library in the default configuration does not use unsafe. If you want to use thin-pointers for dynamic dispatch of union state transitions, the feature dynZST can be used which relies on unsafe, but is very small can be easily audited.

All abstractions in this library are zero-cost. The state machines exist only at compile-time and are shown to be well optimizeable by the compiler. Only when using state-machines across boundaries that the compiler can no longer prove: e.g. behind a smart-pointer like Arc or Rc the state incurs storage cost and requires dynamic dispatch. However the dynamic dispatch only happens at boundary at which the state-space gets restricted. Without any restrictions or after a state is proven concrete, all nominally dynamic dispatches are via the compile-time type system back to static dispatch. With other words, calling a dynamically dispatched transition with a concrete state will always be a zero-cost static dispatch, that the compiler can simplify or choose to inline.

The main achievement of this crate is, that it allows using state-machines nearly without any boiler plate, and no penalty to coding ergonomics. A type that that so far did not have a state-machine can be retrofit without changing the overall implementation if it already adhered to the implied state-machine. Async, generics, &mut (SMut), & (&SRef), pin<&mut> (SPinMut), moving (SMove), smart-pointer, and runtime borrow-checking primitives, even traits are all supported. (default fn on traits are NOT supported)

As type-system enforced state-machines change the type, every function that transitions state must always return self. This requires that &mut like borrowing to be facilitated behind a guard which must specialise on the backing storage e.g. Mutex, RwLock or RefCell. For rust std types implementations are provided, for third party they can be implemented without restrictions even for foreign types, as wrappers are mostly defined by a ZST which gets around the foreign type restriction similarily to newtypes.

I generally recomment that state-machines are defined in their own crate, for sake of separation of concerns as well as speeding up compile time (which is fast either way). State machine definitions function analogous to traits, in that they define a contract that implementing types must fulfil. They are however private contracts as they do not provide an interface that could be used by consumers of implementation. Consumers very much can benefit from the compile-time enforcement tho.

In general, this crate can be relied upon for safety proofs. Be aware however as rust does not have linear types, any guard can always be mem::forget()ten.

Contract Crate

Define the stand-in type, state markers, initial states, allowed transitions, and state unions:

use magicstatemachines::{StateMachineDefinition, States};

pub struct ConnectionStandin;

pub mod states {
    use magicstatemachines::States;

    States! {
        Disconnected;
        Connected;
        Authenticated;
    }
}

use states::{Authenticated, Connected, Disconnected};

StateMachineDefinition! {
    for ConnectionStandin;

    Initial: Disconnected;

    transition Disconnected => Connected();
    transition Connected => Authenticated(user: String);
    transition Connected => Disconnected();
    transition Authenticated => Connected | Disconnected();

    union Online: Connected | Authenticated;
}

The contract crate owns the stand-in and states, so downstream crates cannot add extra transitions.

Implementation Crate

Connect a runtime type to the contract and implement methods with state-typed receivers:

use magicstatemachines::{SMut, State, StateMachineImpl, transition};
use contract::{
    ConnectionStandin, InOnline, Online,
    states::{Authenticated, Connected, Disconnected},
};

pub struct Connection {
    user: Option<String>,
}

StateMachineImpl! {
    Connection: ConnectionStandin;

    transition Disconnected => Connected();

    transition Connected => Authenticated(user: String) {
        self.user = Some(user);
    }

    transition Connected | Authenticated => Disconnected() {
        self.user = None;
    }
}

impl Connection {
    pub fn connect<S>(self: State<S, Self, Disconnected>) -> State<S, Self, Connected>
    where
        S: SMut,
    {
        transition!(self)
    }

    pub fn authenticate<S>(
        self: State<S, Self, Connected>,
        user: impl Into<String>,
    ) -> State<S, Self, Authenticated>
    where
        S: SMut,
    {
        transition!(self, user.into())
    }

    pub fn disconnect<S>(self: State<S, Self, impl InOnline>) -> State<S, Self, Disconnected>
    where
        S: SMut,
    {
        transition!(const Online self)
    }
}

transition! is only usable in the module where StateMachineImpl! generated the private transition token. Public callers can only transition through the methods the implementation exposes.

You might have noticed the InOnline trait, that is not explicitly defined in this example. It is generated by the StateMachineDefinition! macro when the union was defined union Online: Connected | Authenticated;

State Storage

State<Storage, T, S> separates the runtime type T, current state marker S, and storage backend Storage.

Common storage aliases include:

• SOwned: directly owned runtime value
• SBox<T, S>: boxed owned runtime value
• SPinBox<T, S>: pinned boxed runtime value
• SRcRefCell<T>: shared Rc<RefCell<_>> state
• SArcMutex<T>: shared Arc<Mutex<_>> state
• SArcRwLock<T>: shared Arc<RwLock<_>> state

Implementation methods usually constrain storage by capability:

• SRef: read-only access to the runtime value
• SMut: mutable access and ordinary transitions
• SPinRef: pinned shared access
• SPinMut: pinned mutable access and pinned transitions
• SMove: storage can be moved by value

This lets one method work across owned values, boxes, shared guards, and custom storage backends.

State Unions

StateUnion! and StateMachineDefinition! { union ... } generate:

• a public union marker, for example Online
• a sealed membership trait, for example InOnline
• a generated enum, for example OnlineEnum<Storage, T>

Use the generated In... trait in method signatures:

fn endpoint<S>(self: &State<S, Self, impl InOnline>) -> &str
where
    S: magicstatemachines::SRef,
{
    &self.endpoint
}

Use EnumExt::into_enum when runtime branching is needed (this incures the runtime cost of stack allocating the enum):

use magicstatemachines::EnumExt;

match Online.into_enum(state) {
    OnlineEnum::Connected(connected) => {
        // connected: State<_, Connection, Connected>
    }
    OnlineEnum::Authenticated(authenticated) => {
        // authenticated: State<_, Connection, Authenticated>
    }
}

Use In::into_discriminated when the return type should remain a DiscriminatedState<_, _, Online>.

Pinned Transitions

Pinned effects receive Pin<&mut T> instead of &mut T:

StateMachineImpl! {
    Connection: ConnectionStandin;

    pinned transition Disconnected => Connected() {
        self.as_mut().mark_connected();
    }
}

Call pinned transitions with:

transition!(pin self)

Pinned union transitions are also supported:

transition!(pin const Online self);
transition!(pin dyn Online self);

pin const requires every union member to share the same pinned body for the target transition. pin dyn discriminates the current concrete state and runs that state's pinned body.

Features

• dynZST: stores dyn Trait over zero-sized types as a thin-pointer via my dynzst crate (uses unsafe and relies to )
• tracing: records transition source, target, and callsite - no longer zero-cost!
• unique-rc-arc: enables UniqueRc and UniqueArc owned storage backends
• the decompose feature is likely not so great, it allows for a state to be temporarily disconnected from the data, which is runtime enforced by equality on a random sentinal. This likely does break garantees by this api, because an attacker could brute force a collision. I should consider instead using an atomic counter that errors on overflow. but for now it is what it is.
  • decompose: enables StateOwned::decompose and StateOwned::recompose
  • decompose-rand: enables the stable rand backend for decomposition IDs
  • nightly-random: uses nightly std::random for decomposition IDs

Layout

StateOwned<T, S> is transparent over T outside of tracing. State markers are zero-sized, and storage wrappers are designed to preserve the backend layout where the state can be inferred from the type or from existing runtime storage.