odem_rs_core/

fsm.rs

//! A module providing infrastructure for building safe and controlled type
//! state machines in ODEM-rs.
//!
//! This module defines a set of traits, types, and macros that facilitate the
//! creation and management of state machines with enforced state transitions.
//! It ensures that state changes are tracked and validated at compile time.
//!
//! # Overview
//!
//! The key components provided by this module are:
//!
//! - **Macros**:
//!     - [`fsm`]: A macro to simplify the generation of state machines,
//!       allowing for concise definitions of states and transitions.
//!
//! - **Types**:
//!     - [`Ephemeral`]: A token type used to enforce one-time usage, ensuring
//!       that the number of token witnesses is always known.
//!     - [`StateMachine`]: A wrapper type for custom state machines generated
//!       through the `fsm!` macro. It maintains the state and controls
//!       transitions.
//!     - [`TransitionError`]: An error type indicating issues that may occur
//!       during state transitions, such as invalidation or borrowing conflicts.
//!
//! - **Traits**:
//!     - [`Stateful`]: Marks a type that supports methods using `Ephemeral`
//!       tokens to track state changes. It provides hooks for tracking the
//!       number of tokens *witnessing* the current state.
//!     - [`Rebrand`]: Defines a generalized associated type (GAT) that
//!       corresponds with a rebranded version of that type.
//!     - [`Brand`]: Extends `Stateful` types with a method to create an
//!       `Ephemeral` token, allowing for state tracking through branding.
//!     - [`Debrand`]: Allows branded instances to temporarily escape state
//!       tracking to execute closures that may rebrand the instance.
//!     - [`Transition`]: Defines safe state transitions between states
//!       `U` and `V`, given a token witness to the current state.
//!
//! # Usage
//!
//! This module is intended for defining state machines where state transitions
//! need to be controlled and validated. By using the provided traits and types,
//! you can enforce that certain methods are only callable in specific states
//! and that transitions between states are valid. This leads to safer and
//! hopefully more maintainable code.
//!
//! The `fsm` macro can be used to generate a custom state machine with defined
//! states and transitions, reducing boilerplate and potential for errors.
//!
//! # Example
//!
//! ```
//! # use odem_rs_core::fsm::*;
//! # use core::clone::Clone;
//! // Define a state machine with three states: `Idle`, `Exec`, and `Done`.
//! fsm! {
//!     pub enum States<C: Clone> {
//!         Idle(C) -> { Exec },
//!         Exec -> { Idle, Done },
//!         Done -> {}
//!     }
//! }
//!
//! fn main() {
//!     use States::*;
//!     let context = "MyContext".to_string();
//!     let machine = StateMachine::new(Idle(context.clone()));
//!
//!     // Transition from Initialized to Running
//!     machine.brand(|sm, once| {
//!         // Assert the idle state
//!         let idle = sm.token(once).into_idle().unwrap();
//!         // Transition into the running state
//!         let exec: token::Exec<'_> = sm.transition(idle, ());
//!         // Do something with the running state
//!         let done: token::Done<'_> = sm.transition(exec, ());
//!     });
//! }
//! ```
//!
//! # Safety
//!
//! The use of [`Ephemeral`] tokens and the `brand` and `debrand` methods enforce at
//! compile time that state transitions are valid and that state changes do not
//! occur while other parts of the program hold a token witness. This helps
//! prevent bugs related to invalid state transitions and ensures that the state
//! machine remains in a valid state throughout its lifecycle.
//!
//! Specifically, it is made impossible to use token reflecting the state of one
//! state machine to affect transitions in another one.
//!
//! For example, this machine attempts to use a token made for another state
//! machine, leading to a compiler error:
//!
//! ```compile_fail,E0521
//! # use odem_rs_core::fsm::*;
//! // Define a state machine with three states: `Idle`, `Exec`, and `Done`.
//! fsm! {
//!     pub enum States {
//!         Idle -> { Exec },
//!         Exec -> { Idle, Done },
//!         Done -> {}
//!     }
//! }
//!
//! # fn main() {
//! let m1 = StateMachine::new(States::Idle);
//! let m2 = StateMachine::new(States::Exec);
//!
//! m1.brand(|_, once| {
//!     // Use the wrong brand of Ephemeral token; should (and does) not compile!
//!     let exec = m2.token(once).into_exec().unwrap();
//!     let _: token::Done<'_> = m1.transition(exec, ());
//! });
//! # }
//! ```
//!
//! # Notes
//!
//! While the module provides mechanisms to prevent multiple tokens from
//! invalidating each other, it is possible to create multiple tokens via
//! repeated calls to `brand`, which would lead to the state being frozen in a
//! read-only mode. Care should be taken to manage tokens appropriately and
//! ensure that branding scopes are correctly entered and exited.

use core::{
	cell::{BorrowMutError, Cell, Ref, RefCell},
	marker::PhantomData,
	ops::Deref,
	pin::Pin,
};

/* *********************************************************** Exposed Traits */

/// Trait implemented by the [`fsm`]-macro.
pub trait FSM {
	/// Type of generically branded token.
	type Token<'b>;

	/// Type of the stateless enumeration of all possible states.
	type Erased;

	/// Private trait function to convert a branded [`Ephemeral`] into an equally
	/// branded machine-specific token type.
	///
	/// The function argument of type [`Private`] is meant to prevent users from
	/// calling this method directly rather than calling the methods on the
	/// complex state machines, like [`StateMachine`].
	///
	/// Calling the method directly has the potential to invalidate the branding
	/// since `'brand` is chosen by the caller and therefore could be applied
	/// to `Ephemeral` token from other instances.
	fn token<'b>(this: &Self, once: Ephemeral<'b>, _: Private) -> Self::Token<'b>;

	/// Erases the configuration-specific payloads from the enumeration,
	/// returning a type-erased version.
	fn erased(&self) -> Self::Erased;

	/// Returns the name of the current state as a string.
	fn label(&self) -> &'static str;
}

/// Marks a type for supporting extra methods using [`Ephemeral`]-tokens to keep
/// track of state changes.
pub trait Stateful {
	/// Associated marker type for the branding.
	type Brand; // = `&'brand ()`

	/// Method hook used to register the creation of another [`Ephemeral`]-token
	/// for this instance.
	///
	/// # Safety
	/// Calling this method increases the count of `Ephemeral`-token emitted
	/// by the object. Only call this method manually if one of these token
	/// flows into an object that will release it later in order to freeze the
	/// state.
	unsafe fn enter(&self);

	/// Method hook used to register the destruction of a [`Ephemeral`]-token
	/// for this instance.
	///
	/// # Safety
	/// Calling this method reduces the count of `Ephemeral`-token which may
	/// enable transitions to occur. Only call this method manually when
	/// releasing a token from an object in order to unfreeze the state.
	unsafe fn leave(&self);
}

/// Extension trait to keep track of a [`Stateful`] object's current branding.
pub trait Rebrand<'brand>: Stateful<Brand = &'brand ()> {
	/// Meta function that computes the rebranded version of `Self` and forces
	/// the type to correspond with the `Self` type for one of the brandings.
	///
	/// This prevents the trait from being implemented like this:
	/// ```compile_fail,E0271
	/// # use odem_rs_core::fsm::*;
	/// # use core::marker::PhantomData;
	/// struct S<'b>(PhantomData<fn(&'b ()) -> &'b ()>);
	///
	/// impl<'b> Stateful for S<'b> {
	///     type Brand = &'b ();
	///     unsafe fn enter(&self) {}
	///     unsafe fn leave(&self) {}
	/// }
	///
	/// impl<'b> Rebrand<'b> for S<'b> {
	///     type Kind<'a> = S<'a>; // legal, since Kind<'b> == S<'b>
	/// }
	///
	/// struct T<'b>(PhantomData<fn(&'b ()) -> &'b ()>);
	///
	/// impl<'b> Stateful for T<'b> {
	///     type Brand = &'b ();
	///     unsafe fn enter(&self) {}
	///     unsafe fn leave(&self) {}
	/// }
	///
	/// impl<'b> Rebrand<'b> for T<'b> {
	///     type Kind<'a> = S<'a>; // illegal, since ∄'a: Kind<'a> == T<'b>
	/// }
	/// ```
	///
	type Kind<'a>: Rebrand<'a, Kind<'brand> = Self>;

	/// "Converts" a reference to `Self` into a reference of `Self::Kind`, which
	/// is constrained to be a reference to `Self` itself, making this a no-op.
	///
	/// The method is required to support branding.
	fn identity_ref(&self) -> &Self::Kind<'brand> {
		// SAFETY: since Self::Kind<'brand> == Self, this is a no-op
		unsafe { &*(self as *const Self as *const Self::Kind<'brand>) }
	}

	/// "Converts" a mutable reference to `Self` into a mutable reference of
	/// `Self::Kind`, which is constrained to be a mutable reference to `Self`
	/// itself, making this a no-op.
	///
	/// The method is required to support branding.
	fn identity_mut(&mut self) -> &mut Self::Kind<'brand> {
		// SAFETY: since Self::Kind<'brand> == Self, this is a no-op
		unsafe { &mut *(self as *mut Self as *mut Self::Kind<'brand>) }
	}
}

/// Extends [`Stateful`] types by a method to create a [`Ephemeral`]-token that
/// helps to track state changes.
pub trait Brand<F, R> {
	/// Provides an [`Ephemeral`]-token to a closure for [`Stateful`] objects,
	/// unlocking the brand-specific methods.
	fn brand(self, f: F) -> R;
}

/// Extends [`Stateful`] types by a method to temporarily escape the tracking of
/// state changes. This is necessary when state transitions may occur as a
/// side effect of a function call, since those are blocked as long as token
/// witnesses to other states exist.
pub trait Debrand<'b, F, R> {
	/// This method allows branded instances to temporarily escape their
	/// branding in order to execute a caller-supplied closure that may rebrand
	/// the instance.
	///
	/// Not using this method and branding the same instance twice freezes
	/// the state in read-only mode, preventing transitions in order to
	/// ensure that the state both token are witnessing doesn't change.
	fn debrand(self, once: impl Into<Ephemeral<'b>>, f: F) -> (Ephemeral<'b>, R);
}

/// Trait allowing safe state-transitions given a token witness that is
/// testifying to the current state and returning another token after the
/// transition occurred.
///
/// Only potentially correct transitions are implemented, allowing a static
/// compile-time check that all transitions follow a predefined flow-chart.
pub trait Transition<'b, U, V> {
	/// Associated type specifying the payload of the destination state `V`.
	type Data;

	/// Performs the transition between `U` and `V` given an `U`-specific token
	/// and returning a `V`-specific token.
	///
	/// The method is not directly callable for the user in order to ensure that
	/// the invariants regarding the number of token witnesses are kept. The
	/// mechanism is enforced by the last [`Private`] argument to the function
	/// that cannot be constructed outside of this module.
	fn transition(this: &mut Self, curr: U, data: Self::Data, _: Private) -> V;
}

/* *************************************************************** Token Type */

/// Type for a one-time-only usable token.
///
/// Token of this type are used as a seed for the [`brand`] method and are meant
/// to ensure that other kinds of Token may only be created once. This is the
/// reason why the type constructor is deliberately kept private. The *only* way
/// to create this token is to call the `brand` method.
///
/// This is important because otherwise it would be possible to create two Token
/// from the same instance and use one of them to invalidate the other one. This
/// type of bug is prevented by the `brand`-method tracking the number of
/// `Ephemeral` tokens released for each object in combination of transitions
/// blocking changes to the state if more than one Token exists.
///
/// [`brand`]: Brand::brand
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Ephemeral<'brand>(PhantomData<fn(&'brand ()) -> &'brand ()>);

/* ****************************************** Marker Type for Private Details */

/// Marker type to enable generating private functions in a public trait
/// interface.
pub struct Private(());

/* ************************************************************ Complex State */

/// Wrapper type for custom state machines generated through the
/// [`fsm`] macro.
pub struct StateMachine<'b, T: ?Sized> {
	/// Invariant lifetime for branding.
	_mark: PhantomData<fn(&'b ()) -> &'b ()>,

	/// The number of open scopes/[`Ephemeral`] token emitted.
	///
	/// Freezes state transitions if larger than 1.
	token: Cell<u32>,

	/// Mutable access to the inner state generated by the macro.
	state: RefCell<T>,
}

impl<T> StateMachine<'static, T> {
	/// Creates a new state machine using the state `T`.
	pub const fn new(inner: T) -> Self {
		Self {
			_mark: PhantomData,
			token: Cell::new(0),
			state: RefCell::new(inner),
		}
	}
}

impl<'b, T: FSM> StateMachine<'b, T> {
	/// Returns an enumeration containing token witnesses for the current state.
	pub fn token(&self, once: Ephemeral<'b>) -> T::Token<'b> {
		T::token(&*self.borrow(), once, Private(()))
	}

	/// Returns a type-erased version of the current state, i.e. an enumeration
	/// of just the states, without additional payload.
	pub fn erased(&self) -> T::Erased {
		T::erased(&*self.borrow())
	}

	/// Returns the name of the current state as a string.
	pub fn label(&self) -> &'static str {
		T::label(&*self.borrow())
	}

	/// Performs a state transition given the current state and the payload of
	/// the follow-up state, returning a token witness for the next state.
	///
	/// This method will panic if the transition would invalidate other token
	/// witnesses. See [`Self::try_transition`] for a non-panicking variant.
	pub fn transition<U, V>(&self, curr: U, data: T::Data) -> V
	where
		T: Transition<'b, U, V>,
	{
		match self.try_transition(curr, data) {
			Ok(v) => v,
			Err(err) => panic!(
				"cannot transition from '{}' to '{}': {err}",
				self.label(),
				core::any::type_name::<V>(),
			),
		}
	}

	/// Attempts to perform a state transition given the current state and the
	/// payload of the follow-up state, returning a token witness for the next
	/// state if successful and the previous token witness on error.
	///
	/// It is not possible to transition if other token witnesses for the same
	/// state machine would be invalidated by the transition. If you simply
	/// want to update the data associated with a state without changing it,
	/// consider using [`Self::update`] which doesn't have this restriction.
	pub fn try_transition<U, V>(&self, curr: U, data: T::Data) -> Result<V, TransitionError<U>>
	where
		T: Transition<'b, U, V>,
	{
		match self.token.get() {
			0 => unreachable!("transitioning without tokens should be impossible"),
			1 => match self.state.try_borrow_mut() {
				Ok(mut state) => Ok(T::transition(&mut *state, curr, data, Private(()))),
				Err(err) => Err(TransitionError::Borrow(curr, err)),
			},
			n => Err(TransitionError::Invalidation(curr, n)),
		}
	}

	/// Updates the internal data of a state without changing it.
	///
	/// This is allowed, even if other token witnesses exist as it cannot
	/// invalidate them and will only panic if the state cannot be modified due
	/// to being borrowed already.
	pub fn update<U>(&self, curr: U, data: T::Data) -> U
	where
		T: Transition<'b, U, U>,
	{
		T::transition(&mut *self.state.borrow_mut(), curr, data, Private(()))
	}

	/// Borrows the inner state.
	#[track_caller]
	pub fn borrow(&self) -> Ref<'_, T> {
		self.state.borrow()
	}
}

impl<T: Default> Default for StateMachine<'static, T> {
	fn default() -> Self {
		Self::new(T::default())
	}
}

impl<'b, T> Stateful for StateMachine<'b, T> {
	type Brand = &'b ();

	#[inline]
	unsafe fn enter(&self) {
		self.token.set(self.token.get() + 1);
	}

	#[inline]
	unsafe fn leave(&self) {
		self.token.set(self.token.get() - 1);
	}
}

impl<'b, T> Rebrand<'b> for StateMachine<'b, T> {
	type Kind<'a> = StateMachine<'a, T>;
}

/// Enumeration of errors that may happen during state transitions.
#[derive(thiserror::Error)]
pub enum TransitionError<T> {
	/// Signals that a transition failed because other token witnesses would
	/// have been invalidated.
	#[error("cannot transition while {1} references exist")]
	Invalidation(T, u32),
	/// Signals that a transition failed because the state was already borrowed
	/// and thus could not be overwritten.
	#[error("cannot transition while state is borrowed")]
	Borrow(T, BorrowMutError),
}

/* ************************************************************************** */

/// Scope-guard that ensures the correct counting of branding scopes even
/// in case of a panic.
struct Guard<T: Stateful, const E: bool = true>(T);

impl<T: Stateful> Guard<T, true> {
	/// Creates a new scope guard, entering the branding scope.
	fn enter(value: T) -> Self {
		unsafe {
			value.enter();
		}
		Self(value)
	}
}

impl<T: Stateful> Guard<T, false> {
	/// Creates a new scope guard, leaving the branding scope.
	fn leave(value: T) -> Self {
		unsafe {
			value.leave();
		}
		Self(value)
	}
}

impl<T: Stateful, const E: bool> Drop for Guard<T, E> {
	/// Drops the scope guard, exiting or entering (depending on `E`) the scope.
	fn drop(&mut self) {
		if E {
			unsafe {
				self.0.leave();
			}
		} else {
			unsafe {
				self.0.enter();
			}
		}
	}
}

/* **************************************************** Trait Implementations */

// implement the Stateful trait for all references to Stateful objects
impl<T: Deref<Target: Stateful>> Stateful for T {
	type Brand = <T::Target as Stateful>::Brand;

	unsafe fn enter(&self) {
		unsafe {
			(**self).enter();
		}
	}

	unsafe fn leave(&self) {
		unsafe {
			(**self).leave();
		}
	}
}

// Implement the Brand method for different kinds of references to Brandable types
impl<'b, T, F, R> Brand<F, R> for &T
where
	T: Rebrand<'b>,
	F: for<'a> FnOnce(&T::Kind<'a>, Ephemeral<'a>) -> R,
{
	fn brand(self, f: F) -> R {
		f(Guard::enter(self.identity_ref()).0, Ephemeral(PhantomData))
	}
}

impl<'b, T, F, R> Brand<F, R> for &mut T
where
	T: Rebrand<'b>,
	F: for<'a> FnOnce(&mut T::Kind<'a>, Ephemeral<'a>) -> R,
{
	fn brand(self, f: F) -> R {
		f(Guard::enter(self.identity_mut()).0, Ephemeral(PhantomData))
	}
}

impl<'b, T, F, R> Brand<F, R> for Pin<&T>
where
	T: Rebrand<'b>,
	F: for<'a> FnOnce(Pin<&T::Kind<'a>>, Ephemeral<'a>) -> R,
{
	fn brand(self, f: F) -> R {
		// SAFETY: T: Brandable<'brand> implies T::Kind<'brand> = Self
		// therefore the cast below is safe
		let this = unsafe { Pin::map_unchecked(self, T::identity_ref) };

		f(Guard::enter(this).0.as_ref(), Ephemeral(PhantomData))
	}
}

impl<'b, T, F, R> Brand<F, R> for Pin<&mut T>
where
	T: Rebrand<'b>,
	F: for<'a> FnOnce(Pin<&mut T::Kind<'a>>, Ephemeral<'a>) -> R,
{
	fn brand(self, f: F) -> R {
		// SAFETY: T: Brandable<'brand> implies T::Kind<'brand> = Self
		// therefore the cast below is safe
		let this = unsafe { Pin::map_unchecked_mut(self, T::identity_mut) };

		f(Guard::enter(this).0.as_mut(), Ephemeral(PhantomData))
	}
}

impl<'b, T, F, R> Brand<F, R> for crate::ptr::Irc<T>
where
	T: crate::ptr::IntrusivelyCounted + Rebrand<'b, Kind<'b>: crate::ptr::IntrusivelyCounted>,
	F: for<'a> FnOnce(&crate::ptr::Irc<T::Kind<'a>>, Ephemeral<'a>) -> R,
{
	fn brand(self, f: F) -> R {
		// SAFETY: T: Brandable<'brand> implies T::Kind<'brand> = Self
		// therefore the cast below is safe
		let this = crate::ptr::Irc::map(self, T::identity_ref);

		f(&Guard::enter(this).0, Ephemeral(PhantomData))
	}
}

// Implement the Debrand method for different kinds of references to Brandable types
impl<'b, T, F, R> Debrand<'b, F, R> for &T
where
	T: Rebrand<'b>,
	F: FnOnce(&T) -> R,
{
	fn debrand(self, once: impl Into<Ephemeral<'b>>, f: F) -> (Ephemeral<'b>, R) {
		// can't risk having drop not called, so it's not passed down
		let guard = Guard::leave(self);
		(once.into(), f(guard.0))
	}
}

impl<'b, T, F, R> Debrand<'b, F, R> for Pin<&T>
where
	T: Rebrand<'b>,
	F: FnOnce(Pin<&T>) -> R,
{
	fn debrand(self, once: impl Into<Ephemeral<'b>>, f: F) -> (Ephemeral<'b>, R) {
		// can't risk having drop not called, so it's not passed down
		let guard = Guard::leave(self);
		(once.into(), f(guard.0))
	}
}

impl<'b, T, F, R> Debrand<'b, F, R> for &mut T
where
	T: Rebrand<'b>,
	F: FnOnce(&mut T) -> R,
{
	fn debrand(self, once: impl Into<Ephemeral<'b>>, f: F) -> (Ephemeral<'b>, R) {
		// can't risk having drop not called, so it's not passed down
		let guard = Guard::leave(self);
		(once.into(), f(guard.0))
	}
}

impl<'b, T, F, R> Debrand<'b, F, R> for Pin<&mut T>
where
	T: Rebrand<'b>,
	F: FnOnce(Pin<&mut T>) -> R,
{
	fn debrand(self, once: impl Into<Ephemeral<'b>>, f: F) -> (Ephemeral<'b>, R) {
		// can't risk having drop not called, so it's not passed down
		let mut guard = Guard::leave(self);
		(once.into(), f(guard.0.as_mut()))
	}
}

/* ********************************************************* Continuation Type States */

/// A macro to automate the generation of type state machines.
///
/// The macro takes a definition of states and their possible transitions. It
/// generates:
/// - An enum representing all states.
/// - An equivalent “erased” enum without payloads.
/// - A set of token types for each state (and possibly for groups of states,
///   if groups are defined).
/// - Implementations of [`Transition`] for each defined state transition,
///   ensuring at compile time that only valid transitions are allowed.
///
/// The macro also generates convenience methods to check the current state and
/// to convert between token types. It can only be called from the module scope,
/// not from the function scope, since it creates multiple modules.
///
/// # Example Usage
///
/// Here is a simple invocation of the macro for a finite state machine with
/// three states:
///
/// ```
/// # mod test {
/// # use odem_rs_core::fsm::*;
/// // Define a state machine with three states: `Idle`, `Exec`, and `Done`.
/// fsm! {
///     pub enum States {
///         Idle -> { Exec },
///         Exec -> { Idle, Done },
///         Done -> {}
///     }
/// }
/// # }
/// ```
///
/// The macro also supports a single generic argument with a single trait bound.
///
/// ```
/// # mod test {
/// # use odem_rs_core::fsm::*;
/// # use core::clone::Clone;
/// fsm! {
///     pub enum States<C: Clone> {
///         Idle(C) -> { Exec },
///         Exec -> { Idle, Done },
///         Done -> {}
///     }
/// }
/// # }
/// ```
///
/// There is an implicit trait bound of `?Sized` but it can be overridden by
/// choosing a trait bound that implies `Sized`. For technical reasons, at most
/// one generic argument with one trait bound is supported at the moment.
///
/// The macro also allows defining meta states that are collections of existing
/// states:
///
/// ```
/// # mod test {
/// # use odem_rs_core::fsm::*;
/// fsm! {
///     pub enum States {
///         Idle -> { Exec },
///         Exec -> { Idle, Done },
///         Done -> {}
///     }
///     
///     pub Any = { Idle, Exec, Done };
///     pub Live: Any = { Idle, Exec };
/// }
/// # }
/// ```
///
/// The `Live` meta state is marked as a subset of the `Any` meta state,
/// allowing it to convert into that state.
#[doc(hidden)]
#[macro_export]
macro_rules! __fsm {
	(
		$(#[$DOC:meta])*
		$V:vis enum $E:ident $(<$C:ident: $W:ty>)? {
			$($(#[$SDOC:meta])* $S:ident $(($T:ty))? -> {$($D:ident),* $(,)?}),* $(,)?
		}

		$(
			$(#[$MDOC:meta])*
			$MV:vis $MS:ident $(: $MB:ident)? = {$($MT:ident),* $(,)?};
		)*
	) => {paste::paste! {
		// generate the main enumeration
		#[cfg_attr(doc, aquamarine::aquamarine)]
		$(#[$DOC])*
		#[doc = "```mermaid"]
		#[doc = "---"]
		#[doc = "title: " $E " Transition Diagram"]
		#[doc = "---"]
		#[doc = "flowchart LR"]
		#[doc = $($("\t" $S "{{" $S "}}-->" $D "{{" $D "}}\n")*)*]
		#[doc = "```"]
		$V enum $E $(<$C: ?Sized + $W>)* {
			$(
				$(#[$SDOC])*
				$S $(($T))*
			),*
		}

		impl<$($C: ?Sized + $W)*> $crate::fsm::FSM for $E $(<$C>)* {
			type Token<'brand> = token::$E<'brand>;
			type Erased = erased::$E;

			fn token<'brand>(this: &Self, once: Ephemeral<'brand>, _: Private) -> Self::Token<'brand> {
				match this {$(
					Self::$S {..} => token::$E::$S(token::$S(once))
				),*}
			}

			fn erased(&self) -> Self::Erased {
				match self {$(
					Self::$S {..} => erased::$E::$S
				),*}
			}

			fn label(&self) -> &'static str {
				match self {$(
					Self::$S {..} => stringify!($S)
				),*}
			}
		}

		#[allow(dead_code)]
		impl<$($C: ?Sized + $W)*> $E $(<$C>)* {
			$(
				#[doc = "Returns `true` if the current state is "]
				#[doc = "[`Self::" $S "`] and `false` otherwise."]
				pub const fn [<is_ $S:lower>](&self) -> bool {
					matches!(self, Self::$S {..})
				}
			)*
			$(
				#[doc = "Returns `true` if the current state is "]
				#[doc = $("[`Self::" $MT "`]")" or "* " and `false` otherwise."]
				pub const fn [<is_ $MS:lower>](&self) -> bool {
					$(self.[<is_ $MT:lower>]())|*
				}
			)*
		}

		#[doc = "A module containing a configuration- and payload-erased "]
		#[doc = "version of [`" $E "`]."]
		$V mod erased {
			// import the surrounding scope for the documentation links
			#[allow(unused_imports)]
			use super::*;

			#[cfg_attr(doc, aquamarine::aquamarine)]
			$(#[$DOC])*
			#[doc = "```mermaid"]
			#[doc = "---"]
			#[doc = "title: " $E " Transition Diagram"]
			#[doc = "---"]
			#[doc = "flowchart LR"]
			#[doc = $($("\t" $S "{{" $S "}}-->" $D "{{" $D "}}\n")*)*]
			#[doc = "```"]
			#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash)]
			pub enum $E {$(
				$(#[$SDOC])*
				$S
			),*}

			#[allow(dead_code)]
			impl $E {
				/// Returns the label of the current state as a static string.
				pub const fn label(&self) -> &'static str {
					match self {$(
						Self::$S => stringify!($S)
					),*}
				}

				$(
					#[doc = "Returns `true` if the current state is [`Self::" $S "`] and `false` otherwise."]
					pub const fn [<is_ $S:lower>](&self) -> bool {
						matches!(self, Self::$S)
					}
				)*

				$(
					#[doc = "Returns `true` if the current state is "]
					#[doc = $("[`Self::" $MT "`]")" or "* " and `false` otherwise."]
					pub const fn [<is_ $MS:lower>](&self) -> bool {
						match self {
							$(Self::$MT)|* => true,
							_ => false
						}
					}
				)*
			}
		}

		#[doc = "A module containing weightless, branded 👻 token types that "]
		#[doc = "are used as testimony that equally branded [`" $E "`] are in "]
		#[doc = "the corresponding state (`" $($S)"` or `"* "`)."]
		$V mod token {
			use $crate::fsm::{Ephemeral, Transition};
			use super::*;
			use core::fmt;

			#[doc = "An enumeration of token-witnesses for the states "]
			#[doc = $("[`" $S "`](super::" $E "::" $S ")")", "* " and the meta-states "]
			#[doc = $("[`" $MS "`]")", "* "."]
			#[derive(Debug, Eq, PartialEq, Hash)]
			pub enum $E<'brand> {$(
				#[doc = "[`" $S "`] state containing the token as a witness."]
				#[doc = ""]
				#[doc = "[`" $S "`]: super::" $E "::" $S]
				$S($S<'brand>)
			),*}

			#[allow(dead_code)]
			impl<'brand> $E<'brand> {
				/// Strips the token information from the enumeration, yielding
				/// a type-erased variant of it.
				pub const fn erased(&self) -> erased::$E {
					match self {$(
						Self::$S(_) => erased::$E::$S
					),*}
				}

				$(
					#[doc = "Attempts to convert the token referencing the [`" $E "`] "]
					#[doc = "into a token referencing the more specialized [`" $S "`]."]
					#[doc = ""]
					#[doc = "[`" $E "`]: super::" $E]
					#[doc = "[`" $S "`]: super::" $E "::" $S]
					pub const fn [<as_ $S:lower>](&self) -> Option<&$S<'brand>> {
						match self {
							Self::$S(token) => Some(token),
							_ => None
						}
					}

					#[doc = "Attempts to convert the token for [`" $E "`] "]
					#[doc = "into a token for the more specialized [`" $S "`]."]
					#[doc = ""]
					#[doc = "[`" $E "`]: super::" $E]
					#[doc = "[`" $S "`]: super::" $E "::" $S]
					pub const fn [<into_ $S:lower>](self) -> Result<$S<'brand>, error::[<Not $S>]> {
						match self {
							Self::$S(token) => Ok(token),
							_ => Err(error::[<Not $S>](self.erased()))
						}
					}
				)*

				$(
					#[doc = "Attempts to convert the token referencing the "]
					#[doc = "[`" $E "`] into a token referencing state "]
					#[doc = $($MT)" or "* "."]
					#[doc = ""]
					#[doc = "[`" $E  "`]: super::" $E]
					pub const fn [<as_ $MS:lower>](&self) -> Option<&$MS<'brand>> {
						match self {
							$(Self::$MT(token) => Some(unsafe { &*(token as *const $MT<'brand> as *const $MS<'brand>) }),)*
							_ => None
						}
					}

					#[doc = "Attempts to convert the token for [`" $E "`] "]
					#[doc = "into a token for the more specialized "$($MT)" or "* "."]
					#[doc = ""]
					#[doc = "[`" $E  "`]: super::" $E]
					pub const fn [<into_ $MS:lower>](self) -> Result<$MS<'brand>, error::[<Not $MS>]> {
						match self {
							$(Self::$MT(token) => Ok($MS(token.0)),)*
							_ => Err(error::[<Not $MS>](self.erased()))
						}
					}
				)*
			}

			impl<'brand> From<$E<'brand>> for Ephemeral<'brand> {
				fn from(value: $E<'brand>) -> Self {
					match value {
						$($E::$S(token) => token.0),*
					}
				}
			}

			$(
				#[doc = "Token testifying that the equally branded "]
				#[doc = "[`" $E "`] is [`" $S "`]."]
				#[doc = ""]
				#[doc = "[`" $S "`]: super::" $E "::" $S]
				#[derive(PartialOrd, PartialEq, Ord, Eq, Hash)]
				#[repr(transparent)]
				$V struct $S<'brand>(pub(super) Ephemeral<'brand>);

				impl<'brand> $S<'brand> {
					/// Creates a new token of this type with an invariant lifetime `'brand`.
					///
					/// # Safety
					/// Since tokens of this type are used to provide security guarantees,
					/// creating new ones should only be done if it is absolutely certain that
					/// the property symbolized by the token is actually upheld by the equally
					/// branded object it applies to.
					pub const unsafe fn new(once: Ephemeral<'brand>) -> Self {
						Self(once)
					}
				}

				impl<'brand> From<$S<'brand>> for Ephemeral<'brand> {
					fn from(value: $S<'brand>) -> Self {
						value.0
					}
				}

				impl fmt::Debug for $S<'_> {
					fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
						write!(f, concat!(stringify!($E), "(", stringify!($S), ")"))
					}
				}
			)*

			$crate::fsm::fsm! {
				@gen_transitions ($E) ($($W)*) ($($S $(($T))* => $($D)*),*)
			}

			$(
				$(#[$MDOC])*
				#[repr(transparent)]
				$MV struct $MS<'brand>(Ephemeral<'brand>);

				#[allow(dead_code)]
				impl<'brand> $MS<'brand> {
					/// Creates a new token of this type with an invariant lifetime `'brand`.
					///
					/// # Safety
					/// Since tokens of this type are used to provide security guarantees,
					/// creating new ones should only be done if it is absolutely certain that
					/// the property symbolized by the token is actually upheld by the equally
					/// branded object it applies to.
					pub const unsafe fn new(once: Ephemeral<'brand>) -> Self {
						Self(once)
					}

					$(
						#[doc = "Re-casts a reference to the specialized "]
						#[doc = "[`" $MS "`]-token into a token of the generalized "]
						#[doc = "[`" $MB "`] kind."]
						pub const fn [<as_ $MB:lower>](&self) -> &$MB<'brand> {
							unsafe { &*(self as *const $MS<'brand> as *const $MB<'brand>) }
						}

						#[doc = "Converts the specialized [`" $MS "`]-token into "]
						#[doc = "a token of the generalized [`" $MB "`] kind."]
						pub const fn [<into_ $MB:lower>](self) -> $MB<'brand> {
							$MB(self.0)
						}
					)*
				}

				impl<'brand> From<$MS<'brand>> for Ephemeral<'brand> {
					fn from(value: $MS<'brand>) -> Self {
						value.0
					}
				}

				impl fmt::Debug for $MS<'_> {
					fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
						write!(f, concat!("Token(", stringify!($MS), ")"))
					}
				}

				$(
					#[allow(dead_code)]
					impl<'brand> $MT<'brand> {
						#[doc = "Re-casts a reference to the specialized "]
						#[doc = "[`" $MT "`]-token into a token of the generalized "]
						#[doc = "[`" $MS "`] kind."]
						pub const fn [<as_ $MS:lower>](&self) -> &$MS<'brand> {
							unsafe { &*(self as *const $MT<'brand> as *const $MS<'brand>) }
						}

						#[doc = "Converts the specialized [`" $MT "`]-token into "]
						#[doc = "a token of the generalized [`" $MS "`] kind."]
						pub const fn [<into_ $MS:lower>](self) -> $MS<'brand> {
							$MS(self.0)
						}
					}

					impl<'brand> From<$MT<'brand>> for $MS<'brand> {
						fn from(value: $MT<'brand>) -> Self { value.[<into_ $MS:lower>]() }
					}
				)*
			)*
		}

		/// A module for error types that may occur during conversion.
		$V mod error {
			use core::fmt;

			$(
				#[doc = "Error type indicating that the current [`" $E "`] was not [`" $S "`]."]
				#[doc = ""]
				#[doc = "[`" $S "`]: super::" $E "::" $S]
				#[doc = "[`" $E "`]: super::" $E]
				#[derive(Copy, Clone, Debug)]
				pub struct [<Not $S>](pub super::erased::$E);

				impl fmt::Display for [<Not $S>] {
					fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
						write!(
							f,
							concat!("<", stringify!($S), "> expected but <{}> found instead"),
							self.0.label()
						)
					}
				}

				impl core::error::Error for [<Not $S>] {}
			)*

			$(
				#[doc = "Error type indicating that the current [`" $E "`] was "]
				#[doc = "none of " $("[`" $MT "`](super::" $E "::" $MT ")")" or "* "."]
				#[doc = ""]
				#[doc = "[`" $E "`]: super::" $E]
				#[derive(Copy, Clone, Debug)]
				pub struct [<Not $MS>](pub super::erased::$E);

				impl fmt::Display for [<Not $MS>] {
					fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
						write!(
							f,
							concat!("either " $(, "'", stringify!($MT), "'",)" or "* " expected but state '{}' found instead"),
							self.0.label()
						)
					}
				}

				impl core::error::Error for [<Not $MS>] {}
			)*
		}
	}};

	// transitions with a generic argument
	(@gen_transitions ($E:ident) ($W:ty) ($($S:ident $(($T:ty))? => $($D:ident)*),*)) => {paste::paste! {$(
		impl<'b, C: ?Sized + $W> Transition<'b,$S<'b>, $S<'b>> for super::$E<C> {
			#[allow(unused_parens)]
			type Data = ($($T)*);

			#[doc = "Updates the state of [`" $S "`],"]
			#[doc = "requiring a " $S "-token and returning it."]
			fn transition(this: &mut Self, token: $S<'b>, _data: Self::Data, _: $crate::fsm::Private) -> $S<'b> {
				*this = super::$E::$S $(({
					let _: $T;
					_data
				}))?;
				token
			}
		}

		$(
			impl<'b, C: ?Sized + $W> Transition<'b,$S<'b>, $D<'b>> for super::$E<C> {
				type Data = <Self as Transition<'b,$D<'b>,$D<'b>>>::Data;

				#[doc = "Performs the transition between [`" $S "`] and [`" $D "`],"]
				#[doc = "requiring a " $S "-token and returning the resulting "]
				#[doc = $D "-token."]
				fn transition(this: &mut Self, token: $S<'b>, data: Self::Data, p: $crate::fsm::Private) -> $D<'b> {
					#[cfg(feature = "tracing")]
					::tracing::trace!(from = %stringify!($S), into = %stringify!($D), "transition");
					Self::transition(this, $D(token.0), data, p)
				}
			}
		)*
	)*}};

	// transitions without a generic argument
	(@gen_transitions ($E:ident) () ($($S:ident $(($T:ty))? => $($D:ident)*),*)) => {paste::paste! {$(
		impl<'b> Transition<'b, $S<'b>, $S<'b>> for super::$E {
			#[allow(unused_parens)]
			type Data = ($($T)*);

			#[doc = "Updates the state of [`" $S "`],"]
			#[doc = "requiring a " $S "-token and returning it."]
			fn transition(this: &mut Self, token: $S<'b>, _data: Self::Data, _: $crate::fsm::Private) -> $S<'b> {
				*this = super::$E::$S $(({
					let _: $T;
					_data
				}))?;
				token
			}
		}

		$(
			impl<'b> Transition<'b, $S<'b>, $D<'b>> for super::$E {
				type Data = <Self as Transition<'b,$D<'b>,$D<'b>>>::Data;

				#[doc = "Performs the transition between [`" $S "`] and [`" $D "`],"]
				#[doc = "requiring a " $S "-token and returning the resulting "]
				#[doc = $D "-token."]
				fn transition(this: &mut Self, token: $S<'b>, data: Self::Data, p: $crate::fsm::Private) -> $D<'b> {
					#[cfg(feature = "tracing")]
					::tracing::trace!(from = %stringify!($S), into = %stringify!($D), "transition");
					Self::transition(this, $D(token.0), data, p)
				}
			}
		)*
	)*}};
}

// Export the macro from within this module.
#[doc(inline)]
pub use __fsm as fsm;

#[cfg(test)]
mod tests {
	use super::*;

	// Define a state machine with three states: `Idle`, `Exec`, and `Done`.
	fsm! {
		#[allow(dead_code)]
		pub enum States {
			Idle -> { Busy },
			Busy -> { Idle, Done },
			Done(bool) -> {}
		}
	}

	#[test]
	fn simple_sm() {
		let m1 = StateMachine::new(States::Idle);

		let _ = m1.brand(|sm, once| {
			// Assert the idle state
			let idle = sm.token(once).into_idle().unwrap();
			// Transition into the running state
			let busy: token::Busy<'_> = sm.transition(idle, ());
			// Do something with the running state
			let _: token::Done<'_> = sm.transition(busy, true);

			m1.borrow()
		});
	}
}