Let’s dive into the fascinating world of zero-cost state machines in Rust. I’ve been working with this concept for a while, and I’m excited to share what I’ve learned.

Rust’s type system is a powerful tool that allows us to create state machines with no runtime overhead. This means we can enforce state transitions at compile-time, making our code safer and more efficient.

The idea behind zero-cost state machines is to use Rust’s type system to represent different states and transitions. We can do this using enums, generics, and associated types. By encoding our business logic directly into types, we create self-documenting APIs that catch invalid state transitions before our code even runs.

Let’s start with a simple example. Imagine we’re building a traffic light system. We have three states: Red, Yellow, and Green. We can represent this using an enum:

enum TrafficLight {
    Red,
    Yellow,
    Green,
}

Now, let’s say we want to enforce the correct order of transitions. We can use Rust’s type system to make sure that Red can only transition to Green, Green can only transition to Yellow, and Yellow can only transition to Red.

Here’s how we can implement this:

struct Red;
struct Yellow;
struct Green;

struct TrafficLight<State>(State);

impl TrafficLight<Red> {
    fn new() -> Self {
        TrafficLight(Red)
    }

    fn turn_green(self) -> TrafficLight<Green> {
        TrafficLight(Green)
    }
}

impl TrafficLight<Green> {
    fn turn_yellow(self) -> TrafficLight<Yellow> {
        TrafficLight(Yellow)
    }
}

impl TrafficLight<Yellow> {
    fn turn_red(self) -> TrafficLight<Red> {
        TrafficLight(Red)
    }
}

In this implementation, each state is represented by an empty struct. The TrafficLight struct is generic over the state, which means we can have different types for each state of the traffic light.

Each state has its own implementation block, which defines the valid transitions from that state. For example, TrafficLight can only transition to TrafficLight.

Now, let’s see how we can use this:

fn main() {
    let light = TrafficLight::new(); // Red
    let light = light.turn_green(); // Green
    let light = light.turn_yellow(); // Yellow
    let light = light.turn_red(); // Red
    
    // This would cause a compile-time error:
    // let light = light.turn_green();
}

If we try to make an invalid transition, like turning a yellow light directly to green, we’ll get a compile-time error. This is the power of zero-cost state machines - we get strong guarantees about our program’s behavior without any runtime checks.

But what if we want to add some data to our states? Let’s extend our traffic light example to include a timer for each state:

struct Red(u32);
struct Yellow(u32);
struct Green(u32);

struct TrafficLight<State>(State);

impl TrafficLight<Red> {
    fn new(duration: u32) -> Self {
        TrafficLight(Red(duration))
    }

    fn turn_green(self) -> TrafficLight<Green> {
        TrafficLight(Green(30))
    }
}

impl TrafficLight<Green> {
    fn turn_yellow(self) -> TrafficLight<Yellow> {
        TrafficLight(Yellow(5))
    }
}

impl TrafficLight<Yellow> {
    fn turn_red(self) -> TrafficLight<Red> {
        TrafficLight(Red(20))
    }
}

Now each state carries a duration. We can even add methods to update this duration:

impl TrafficLight<Red> {
    // ... previous methods ...

    fn update_duration(&mut self, new_duration: u32) {
        self.0 .0 = new_duration;
    }
}

This pattern isn’t just useful for simple examples like traffic lights. It’s incredibly powerful for modeling complex systems. For instance, let’s consider a more complex example: a state machine for a vending machine.

A vending machine can be in several states: Ready (waiting for coins), HasCoins (has received some money), Vending (dispensing a product), and OutOfStock. Each state has different possible actions:

struct Coin(u32);
struct Product(String);

struct Ready;
struct HasCoins(u32);
struct Vending(Product);
struct OutOfStock;

struct VendingMachine<State>(State);

impl VendingMachine<Ready> {
    fn new() -> Self {
        VendingMachine(Ready)
    }

    fn insert_coin(self, coin: Coin) -> VendingMachine<HasCoins> {
        VendingMachine(HasCoins(coin.0))
    }
}

impl VendingMachine<HasCoins> {
    fn insert_coin(mut self, coin: Coin) -> Self {
        self.0 .0 += coin.0;
        self
    }

    fn vend(self, product: Product) -> VendingMachine<Vending> {
        VendingMachine(Vending(product))
    }

    fn cancel(self) -> VendingMachine<Ready> {
        println!("Returning {} cents", self.0 .0);
        VendingMachine(Ready)
    }
}

impl VendingMachine<Vending> {
    fn complete(self) -> VendingMachine<Ready> {
        println!("Enjoy your {}!", self.0 .0);
        VendingMachine(Ready)
    }
}

impl VendingMachine<OutOfStock> {
    fn restock(self) -> VendingMachine<Ready> {
        VendingMachine(Ready)
    }
}

This state machine ensures that we can only perform valid actions in each state. For example, we can’t vend a product if no coins have been inserted, and we can’t insert more coins while a product is being vended.

Here’s how we might use this vending machine:

fn main() {
    let machine = VendingMachine::new();
    let machine = machine.insert_coin(Coin(25));
    let machine = machine.insert_coin(Coin(25));
    let machine = machine.vend(Product("Soda".to_string()));
    let machine = machine.complete();
}

Again, any attempt to perform an invalid action (like trying to vend without inserting coins) would result in a compile-time error.

One of the key benefits of this approach is that it’s zero-cost. The state machine is entirely represented in the type system, so there’s no runtime overhead. Once the code compiles, all the state checks have already been performed.

This technique isn’t limited to simple state machines. We can use it to model complex workflows, protocols, or any system where we want to enforce a specific sequence of operations.

For instance, we could model a TCP connection:

struct Closed;
struct Listen;
struct SynRcvd;
struct Established;

struct TcpConnection<State>(State);

impl TcpConnection<Closed> {
    fn new() -> Self {
        TcpConnection(Closed)
    }

    fn listen(self) -> TcpConnection<Listen> {
        TcpConnection(Listen)
    }
}

impl TcpConnection<Listen> {
    fn receive_syn(self) -> TcpConnection<SynRcvd> {
        TcpConnection(SynRcvd)
    }
}

impl TcpConnection<SynRcvd> {
    fn receive_ack(self) -> TcpConnection<Established> {
        TcpConnection(Established)
    }
}

impl TcpConnection<Established> {
    fn send_data(&self, data: &[u8]) {
        println!("Sending {} bytes", data.len());
    }

    fn close(self) -> TcpConnection<Closed> {
        TcpConnection(Closed)
    }
}

This ensures that we can only send data on an established connection, and that we follow the correct sequence of steps to establish a connection.

One challenge you might encounter when working with these state machines is how to store them in data structures. Since each state has a different type, you can’t directly store a collection of state machines in different states.

One solution is to use enum to wrap all possible states:

enum VendingMachineState {
    Ready(VendingMachine<Ready>),
    HasCoins(VendingMachine<HasCoins>),
    Vending(VendingMachine<Vending>),
    OutOfStock(VendingMachine<OutOfStock>),
}

This allows you to store multiple vending machines in a collection, regardless of their current state:

let mut machines = vec![
    VendingMachineState::Ready(VendingMachine::new()),
    VendingMachineState::Ready(VendingMachine::new()),
    VendingMachineState::OutOfStock(VendingMachine(OutOfStock)),
];

When you need to interact with a machine, you can use pattern matching to handle each possible state:

for machine in &mut machines {
    match machine {
        VendingMachineState::Ready(m) => {
            *machine = VendingMachineState::HasCoins(m.insert_coin(Coin(25)));
        }
        VendingMachineState::HasCoins(m) => {
            *machine = VendingMachineState::Vending(m.vend(Product("Soda".to_string())));
        }
        VendingMachineState::Vending(m) => {
            *machine = VendingMachineState::Ready(m.complete());
        }
        VendingMachineState::OutOfStock(m) => {
            *machine = VendingMachineState::Ready(m.restock());
        }
    }
}

This pattern allows you to maintain the type safety of your state machines while still being able to work with collections of them.

Another powerful feature of Rust that we can leverage in our state machines is associated types. These allow us to define types that are associated with our state machine, which can vary based on the current state.

Let’s extend our TCP connection example to demonstrate this:

trait ConnectionState {
    type Action;
    fn perform_action(&mut self, action: Self::Action);
}

struct Closed;
struct Listen;
struct Established;

impl ConnectionState for Closed {
    type Action = ();
    fn perform_action(&mut self, _: Self::Action) {
        println!("No action possible in Closed state");
    }
}

impl ConnectionState for Listen {
    type Action = String; // Represent an incoming connection
    fn perform_action(&mut self, ip: Self::Action) {
        println!("Received connection from {}", ip);
    }
}

impl ConnectionState for Established {
    type Action = Vec<u8>; // Represent data to send
    fn perform_action(&mut self, data: Self::Action) {
        println!("Sending {} bytes", data.len());
    }
}

struct TcpConnection<S: ConnectionState>(S);

impl<S: ConnectionState> TcpConnection<S> {
    fn action(&mut self, action: S::Action) {
        self.0.perform_action(action);
    }
}

In this example, each state defines its own Action type. The Closed state has no possible actions, so its Action type is the unit type (). The Listen state can receive incoming connections, so its Action type is String (representing an IP address). The Established state can send data, so its Action type is Vec.

This allows us to have different types of actions for different states, all enforced at compile-time:

let mut conn = TcpConnection(Closed);
conn.action(()); // OK

let mut conn = TcpConnection(Listen);
conn.action("192.168.0.1".to_string()); // OK

let mut conn = TcpConnection(Established);
conn.action(vec![1, 2, 3, 4]); // OK

// These would be compile-time errors:
// conn.action("192.168.0.1".to_string()); // Error: Closed state doesn't accept strings
// conn.action(vec![1, 2, 3, 4]); // Error: Listen state doesn't accept byte vectors

This technique allows us to create even more expressive and type-safe state machines, where not only the allowed transitions but also the allowed actions are encoded in the type system.

As you can see, Rust’s type system provides us with powerful tools to create zero-cost state machines. By encoding our business logic into the type system, we can catch errors at compile-time, create self-documenting APIs, and eliminate the need for runtime checks.

This approach isn’t just about correctness, though. By pushing these checks to compile-time, we’re also improving the performance of our code. There’s no need for runtime checks or branches to handle invalid states because we’ve already proven at compile-time that they can’t occur.

Of course, like any technique, this approach has its trade-offs. The main downside is increased complexity in the type system. As our state machines grow more complex, our types can become more difficult to understand and work with. It’s important to balance the benefits of compile-time guarantees with the need for code that’s easy to read and maintain.

In practice, I’ve found that these state machines are most useful for core parts of a system where correctness is critical. For less critical or more dynamic parts of a system, a more traditional approach might be more appropriate.

As you explore this technique, remember that the goal is to write code that’s not just correct, but also clear and maintainable. Use these zero-cost state machines where they provide real benefits, but don’t be afraid to use simpler approaches where they’re sufficient.

Rust’s type system is a powerful tool, and zero-cost state machines are just one of the many ways we can leverage it to write better, safer code. As you continue to work with Rust, you’ll discover more and more ways to use the type system to express complex ideas and catch errors early. Happy coding!