Leverage The Rust Type System

#Intro

Rust is an interesting language that got inspiration from many other languages. Its type system for example is designed more like functional languages (e.g.: Haskell) rather than imperative languages (e.g.: C++). The biggest benefit of this approach is that it can turn many programming problems into "static typing" problems, and can be evaluated at compile times¹.

One of these programming problems are state machines, which are a useful ways to represent a system and its states with the possible transitions between those states. Using Rust we can ensure that invalid states are unrepresentable².

Let's look at our example problem that we will to solve with this approach...

#The Problem

Let's take the following state machine of a car as an example:

So our car has 3 states:

• Still when it is standing still.
• Moving when we are driving it.
• Crashed when we hit a tree.

For our car, the API will be different depending on the state, and it is shown in the following table.

It is a simple and stupid example, but introduces to us to the problem of the changing behaviour in different states. For example, when the car is moving then we can stop driving, push horn, or drive into tree. However, when the car is crashed then we can still push horn but now our other option is only to exit the car.

#First Approach

In the video of No Boilerplate², it is shown how to represent states with the rust enum. Rust enums are different than the enums of most other languages. They are proper algebraic Sum types, sometimes called Tagged Unions. For example the following code represents a cat:

enum RealCat {
    Alive { hungry: bool },
    Dead,
}

It's more natural thing to model this with Rust's fat enums. There are only two valid states and only the alive variant has the extra hungry attribute. Also, the compiler of Rust knows what you are talking about, and it will keep you in the safe. It will let you know if you forgot to handle one of the two states.

$ cargo build
non-exhaustive patterns: `RealCat::Dead` not covered
  --> src/main.rs:32:7
   |
32 | match realcat {
   |       ^^^^^^^ pattern `RealCat::Dead` not covered
   |
   = note, the matched value is of type `RealCat`
help: ensure that all possible cases are being handled by
adding a match arm with a wildcard pattern or an
explicit pattern as shown
   |
33 ~     RealCat::Alive{..} => println!("good good"),
34 ~     RealCat::Dead => todo!()

   $ _

Let's use this approach to represent our car... 🤔

enum Car {
    Still,
    Moving,
    Crashed,
}

Then we can start to implement the methods. First we enter the car that returns a standing still car.

impl Car {
    pub fn enter() -> Self {
        println!("Enter the car");
        Car::Still
    }
}

Let's do the exit method next. This one we can only do from the still and crashed states, and it should "consume" the object, meaning the car should be deleted. However, during moving we cannot exit and the car should not be deleted... Which is a tricky situation, so I'll do a finicky hack around it 😬

impl Car {
    pub fn exit(self) -> Result<(), Self> {
        println!("Exit the car");
        match self {
            Car::Still => Ok(()),
            Car::Moving => Err(self),
            Car::Crashed => Ok(())
        }
    }
}

So we can patch this issue if we, for example, wrap the operation into a result and return that for the user to figure out if we managed to exit the car or not.

fn main() {
    let car = Car::enter();
    match car.exit() {
        Ok(_) => println!("We left the car"),
        Err(_) => println!("We are still in the car")
    }
}

Yeaaaaah...🫤 not the solution we are looking for. This approach would work if the API of our object would stay the same regardless of the state. In this case, it doesn't provide a good abstraction for the user, and it even can be confusing because we can still call the exit method when the car is moving.

This is mostly due to the fact that an enum still count as one type in Rust and its variants doesn't. So let's change the approach!

#Generics As Type Classes

The Rust design pattern we are going to leverage for this problem is called "generics as type classes"¹. This approach basically leverage the Rust type system for representing the state.

A key part of this idea is the way how generic types work in Rust. In Rust, generic type parameter creates what is know in functional languages as a "type class constraint", and each different parameter filled in actually changes the type. So while vector<int> and vector<char> in C++ are just two different copies of the same boilerplate code for a vector type (aka templates), in Rust, Vec<isize> and Vec<char> are two different types.

In object-oriented languages, classes inherit behaviour from their parents. However, this allows the attachment of not only additional behavior to particular members of a type class, but extra as well³.

The problem with object-oriented languages is they’ve got all this implicit environment that they carry around with them. You wanted a banana but what you got was a gorilla holding the banana and the entire jungle.

—Joe Armstrong, creator of Erlang 🧐

The nearest equivalent for this Rust behaviour is the runtime polymorphism in Javascript and Python, where new members can be added to objects willy-nilly by any constructor. However, unlike those languages, all of Rust's additional methods can be type checked when they are used. That makes them more usable while remaining safe.

Let's see how would that look like for our car.

#Second Approach

#Represent states with types

So first of all, let's represent our car states with types as follows.

pub mod states {
    pub struct Still;
    pub struct Moving;
    pub struct Crashed;
}

Then we crate our Car structure using generics.

pub struct Car<S>;

We can even use trait bounds to restrict the generic type to only car states.

use crate::car_with_type::states::CarState;

pub mod states {
    pub struct Still;
    impl CarState for Still {}

    pub struct Moving;
    impl CarState for Moving {}

    pub struct Crashed;
    impl CarState for Crashed {}

    pub trait CarState {}
}

pub struct Car<S>
where
    S: CarState;

However, this code will create the following error when we want to compile it.

$ cargo build
error[E0392]: type parameter `S` is never used
  --> src/car_with_type.rs:16:16
   |
16 | pub struct Car<S> where S: CarState;
   |                ^ unused type parameter
   |
   = help: consider removing `S`, referring to it in a field, or using a marker such as `PhantomData`

   $ _

Luckily, the compiler is for our help, and it already shows the solution to us. We have to use the type parameter. We could just create a field in our Car object and assign the type parameter to it, however, we have an even better option: the PhantomData marker. 👻

pub struct Car<State>
where
    State: CarState
{
    state: std::marker::PhantomData<State>
}

What is this PhantomData marker you ask? It is a zero-sized type used to mark things that "act like" they own a type. They are used during compile time to tell the compiler what State parameter is used, however, because of their zero-sized nature they are left out from the compiled structure. This is again a nice showcase of Rust's zero cost abstraction approach, we can use a marker like PhantomData but it won't use any bytes at run time from the system⁴.

We know that the initial state will be always Still so we can even specify that like this. Then we define our associated function that will create our Car object.

pub struct Car<State = Still>
where
    State: CarState,
{
    state: std::marker::PhantomData<State>,
}

impl Car {
    pub fn enter() -> Car<Still> {
        println!("Enter the car");
        Car {
            state: std::marker::PhantomData::default(),
        }
    }
}

🖊️ Note that we implemented this method for the Car structure that doesn't use type a type parameter. This is because we know the initial state of our car and a type parameter won't have any effect on the output.

So the user simple can create a car like this.

fn main() {
    let car: Car<Still> = Car::enter();
}

From the type annotation, you can see that we have now a standing still car. 🚗

#Creating behaviours

As a next step, let's try to implement the exit behaviour. This is where we failed with the first approach, see if we can get further. Again, this behaviour is only possible if the car is Still or Crashed, and we had to implement it for the generic type last time because of our approach, but this time we can be specific via the use of type parameters. As a start, we focus on the Still state, and we will add the Crashed state later. Let's create an implement block for the Car<Still> type.

impl Car<Still> {
    pub fn exit(self) {
        println!("Exit the car");
    }
}

fn main() {
    let car: Car<Still> = Car::enter();
    car.exit();
}

🖊️ Note that this method takes the ownership of self and it will return nothing. This basically indicates to the compiler to free the memory of self and our object is deleted. If you want to exit the car again, the compiler will notify you that the car object is not valid anymore and the code won't compile.

$ cargo build
error[E0382]: use of moved value: `car`
  --> src/main.rs:10:5
   |
8  |     let car: Car<Still> = Car::enter();
   |         --- move occurs because `car` has type `car_with_type::Car`, which does not implement the `Copy` trait
9  |     car.exit();
   |         ------ `car` moved due to this method call
10 |     car.exit();
   |     ^^^ value used here after move
   |
note: `car_with_type::Car::exit` takes ownership of the receiver `self`, which moves `car`
  --> src/car_with_type.rs:32:17
   |
32 |     pub fn exit(self) {}
   |

   $ _

Now we will add the method to start driving the car, and we can get to the Moving state. This method is only for the Still state, so we can just extend the implementation block we just created.

impl Car<Still> {
    pub fn exit(self) {}

    pub fn start_driving(self) -> Car<Moving> {
        println!("Start driving");
        Car {
            state: std::marker::PhantomData::<Moving>,
        }
    }
}

This method will return a Car<Moving> type of object to us. We will consume our Car<Still> object via taking the ownership of it, and it will be deleted after this operation. This is the desired behaviour for us, because or car is moving now and not standing still anymore.

fn main() {
    let standing_car: Car<Still> = Car::enter();
    let moving_car: Car<Moving> = standing_car.start_driving();
}

So after the start_driving operation, the standing_car variable will be invalid and the use of it will trigger the use of moved value error.

We can use the "shadowing" technique to assign the new Car<Moving> object to our car variable.

fn main() {
    let car: Car<Still> = Car::enter();
    let car: Car<Moving> = standing_car.start_driving();
}

And now let's see if we can exit the car while it is moving... 🤔

$ cargo build
error[E0599]: no method named `exit` found for struct `car_with_type::Car<Moving>` in the current scope
  --> src/main.rs:10:9
   |
10 |     car.exit()
   |         ^^^^ method not found in `Car<Moving>`
   |
  ::: src/car_with_type.rs:16:1
   |
16 | pub struct Car<State = Still>
   | ----------------------------- method `exit` not found for this struct
   |
note: there's an earlier shadowed binding `car` of type `car_with_type::Car` that has method `exit` available
  --> src/main.rs:8:9
   |
8  |     let car: Car<Still> = Car::enter();
   |         ^^^ `car` of type `car_with_type::Car` that has method `exit` defined earlier here
9  |     let car: Car<Moving> = car.start_driving();
   |         --- earlier `car` shadowed here with type `car_with_type::Car<Moving>`
   = note: the method was found for
           - `car_with_type::Car`

   $ _

Aaaand we can't! Nice! 😄 The compiler even let us know that the shadowed Car<Still> variable had this method. Really nice of it. All hail the Compiler! 🫡

Next method is to stop driving the car. This will allow us go back to the Still state, and from there we can exit our vehicle again. We will add this method to the Car<Moving> implementation block.

impl Car<Moving> {
    pub fn stop_driving(self) -> Car<Still> {
        println!("Stop driving");
        Car {
            state: std::marker::PhantomData::<Still>,
        }
    }
}

Pretty much the same as the start_driving method.

fn main() {
    let car: Car<Still> = Car::enter();
    let car: Car<Moving> = car.start_driving();
    let car: Car<Still> = car.stop_driving();
    car.exit()
}

And voila! We can drive and enjoy our car, the "happy path" is covered. Let's crash it now! 😈

impl Car<Moving> {
    pub fn stop_driving(self) -> Car<Still> {
        println!("Stop driving");
        Car {
            state: std::marker::PhantomData::<Still>,
        }
    }

    pub fn drive_into_tree(self) -> Car<Crashed> {
        println!("Drive into a tree");
        Car {
            state: std::marker::PhantomData::<Crashed>,
        }
    }
}

And with this we have a way to enter the Crashed state. Here we can exit the vehicle again.

impl Car<Crashed> {
    pub fn exit(self) {
        println!("Exit the car");
    }
}

The last method is the push_horn method. This is applicable for all three states, so we could extend the implementation block of all of them but that would be a lot of code duplication. Instead of that, we should create an implementation block which implements it for all states.

impl<State> Car<State>
where
    State: CarState
{
    pub fn push_horn(&self) {
        println!("📣 HOOOOOOONK! 🚚📢")
    }
}

Now we are using the trait boundaries for our advantage. We basically, say that for all type parameters that are CarStates we implement a function called push_horn. This reduces the code duplications in our code, and assures that when we change the implementation it will be updated for all states.

🖊️ Note that this is valid only if the implementation is the same for all states. But if that is not the case then we don't really have code duplications 🤷

fn main() {
    let car: Car<Still> = Car::enter();
    car.push_horn();
    let car: Car<Moving> = car.start_driving();
    car.push_horn();
    let car: Car<Crashed> = car.drive_into_tree();
    car.push_horn();
    car.exit()
}

This will create the following output on the console:

$ cargo run
Enter the car
📣 HOOOOOOONK! 🚚📢
Start driving
📣 HOOOOOOONK! 🚚📢
Drive into a tree
📣 HOOOOOOONK! 🚚📢
Exit the car

Process finished with exit code 0

   $ _

Now we have a functioning car! 🚗☁️

We finished! Our car's state machine is implemented in such a way that the invalid scenarios are unrepresentable, and they are caught at compile time. Thank you for tagging along for this topic! 😊

Ooooooor... what if...

#How To Overengineer A Car

One thing we have still in our implementation is a code duplication of the exit behaviour. We could do the same approach as we did for the push_horn method, but what would be the trait boundary? One boundary could be CarState, but that also includes the Moving state. So we have to find another way to filter the states.

#Extend our car

Let's make our car a bit more complicated, so that we can fully appreciate our abstraction.

Also, the car will have an attribute for the gear. This will be represented by the following enum:

#[derive(Debug)]
pub enum Gear {
    First,
    Second,
    Third,
    Fourth,
    Reverse,
}

So the new Car structure looks like the following:

pub struct Car<State = Still>
where
    State: CarState,
{
    state: std::marker::PhantomData<State>,
    gear: Gear,
}

And the gear will be in first when we enter the car:

impl Car {
    pub fn enter() -> Car<Still> {
        println!("Enter the car");
        Car {
            state: std::marker::PhantomData::default(),
            gear: Gear::First,
        }
    }
}

#Using traits as markers

We can leverage the trait boundary mechanism of the language to create markers for our states and filter them. To do that we have to divide our methods into groups. We have methods that are shared between states, and we have some that are only for a given state.

Groups of shared behaviours:

• Exit
  • exit
• Horn
  • push_horn
• Shift
  • shift_up
  • shift_down

Groups of state behaviours

• Still behaviour
  • start_driving
  • Exit
  • Horn
  • Shift
• Moving behaviour
  • stop_driving
  • drive_into_tree
  • Horn
  • Shift
• Crashed behaviour
  • Exit
  • Horn

Then we can start to recreate this structure using traits and trait boundaries as follows:

// Groups of shared behaviours
pub trait SupportsExit {}
pub trait SupportsHorn {}
pub trait SupportsShift {}

// Groups of state behaviours
pub trait StillBehaviour: SupportsExit + SupportsHorn + SupportsShift {}
pub trait MovingBehaviour: SupportsHorn + SupportsShift {}
pub trait CrashedBehaviour: SupportsExit + SupportsHorn {}

For the state behaviours, you can see we use the trait boundaries to define what shared behaviour has to be supported. Now we can use these traits to mark our state structures.

pub struct Still;
impl CarState for Still {}
impl SupportsExit for Still {}
impl SupportsHorn for Still {}
impl SupportsShift for Still {}
impl SupportsStillBehaviour for Still {}

pub struct Moving;
impl CarState for Moving {}
impl SupportsHorn for Moving {}
impl SupportsShift for Moving {}
impl SupportsMovingBehaviour for Moving {}

pub struct Crashed;
impl CarState for Crashed {}
impl SupportsExit for Crashed {}
impl SupportsHorn for Crashed {}
impl SupportsCrashedBehaviour for Crashed {}

pub trait CarState {}

🖊️ Note that when the implementation of a state behaviour is defined for a state (like SupportsStillBehaviour), then you will have a compiler error if one of the trait boundaries are missing (e.g.: SupportsExit). This can assure that nothing is missing. However, it can't assure if more is defined for a state! For example: impl SupportsShift for Crashed {} would not lead to error!

#Implementing behaviours with markers

Now let's utilise the markers we created solve our code duplications. We can now use the SupportsExit trait as a boundary when we create the implementation block for the exit function. It would be something like this...

impl<State> Car<State>
where
    State: CarState + SupportsExit,
{
    pub fn exit(self) {
        println!("Exit the car");
    }
}

This will apply the implementation for Car<Still> and Car<Crashed>, because Still and Crashed are both CarStates and they both SupportsExit.

The same way we can add the new shifting behaviour.

impl<State> Car<State>
where
    State: CarState + SupportsShift,
{
    pub fn shift_up(&mut self) {
        let new_gear = match self.gear {
            Gear::First => Gear::Second,
            Gear::Second => Gear::Third,
            Gear::Third => Gear::Fourth,
            Gear::Fourth => Gear::Fourth,
            Gear::Reverse => Gear::First,
        };
        println!("Shifted up to {:?}", new_gear);
        self.gear = new_gear;
    }

    pub fn shift_down(&mut self) {
        let new_gear = match self.gear {
            Gear::First => Gear::Reverse,
            Gear::Second => Gear::First,
            Gear::Third => Gear::Second,
            Gear::Fourth => Gear::Third,
            Gear::Reverse => Gear::Reverse,
        };
        println!("Shifted down to {:?}", new_gear);
        self.gear = new_gear;
    }
}

#Final Result

With the updates from the methods shown above, our Car Rust module will look as follows:

#[derive(Debug)]
pub enum Gear {
    First,
    Second,
    Third,
    Fourth,
    Reverse,
}

pub struct Car<State = Still>
where
    State: CarState,
{
    state: std::marker::PhantomData<State>,
    gear: Gear,
}

impl Car {
    pub fn enter() -> Car<Still> {
        println!("Enter the car");
        Car {
            state: std::marker::PhantomData::default(),
            gear: Gear::First,
        }
    }
}

impl<State> Car<State>
where
    State: CarState + SupportsExit,
{
    pub fn exit(self) {
        println!("Exit the car");
    }
}

impl<State> Car<State>
where
    State: CarState + SupportsHorn,
{
    pub fn push_horn(&self) {
        println!("📣 HOOOOOOONK! 🚚📢")
    }
}

impl<State> Car<State>
where
    State: CarState + SupportsShift,
{
    pub fn shift_up(&mut self) {
        let new_gear = match self.gear {
            Gear::First => Gear::Second,
            Gear::Second => Gear::Third,
            Gear::Third => Gear::Fourth,
            Gear::Fourth => Gear::Fourth,
            Gear::Reverse => Gear::First,
        };
        println!("Shifted up to {:?}", new_gear);
        self.gear = new_gear;
    }

    pub fn shift_down(&mut self) {
        let new_gear = match self.gear {
            Gear::First => Gear::Reverse,
            Gear::Second => Gear::First,
            Gear::Third => Gear::Second,
            Gear::Fourth => Gear::Third,
            Gear::Reverse => Gear::Reverse,
        };
        println!("Shifted down to {:?}", new_gear);
        self.gear = new_gear;
    }
}

impl<State> Car<State>
where
    State: CarState + SupportsStillBehaviour,
{
    pub fn start_driving(self) -> Car<Moving> {
        println!("Start driving");
        Car {
            state: std::marker::PhantomData::<Moving>,
            gear: self.gear,
        }
    }
}

impl<State> Car<State>
where
    State: CarState + SupportsMovingBehaviour,
{
    pub fn stop_driving(self) -> Car<Still> {
        println!("Stop driving");
        Car {
            state: std::marker::PhantomData::<Still>,
            gear: self.gear,
        }
    }

    pub fn drive_into_tree(self) -> Car<Crashed> {
        println!("Drive into a tree");
        Car {
            state: std::marker::PhantomData::<Crashed>,
            gear: self.gear,
        }
    }
}

impl<State> Car<State> where State: CarState + SupportsCrashedBehaviour {}

Then we can now update our main function to use the new features of our car.

fn main() {
    let car: Car<Still> = Car::enter();
    car.push_horn();
    let mut car: Car<Moving> = car.start_driving();
    car.push_horn();
    car.shift_up();
    car.shift_up();
    car.shift_down();
    let car: Car<Crashed> = car.drive_into_tree();
    car.push_horn();
    car.exit();
}

Which will create the following output on the console:

$ cargo run
Enter the car
📣 HOOOOOOONK! 🚚📢
Start driving
📣 HOOOOOOONK! 🚚📢
Shifted up to Second
Shifted up to Third
Shifted down to Second
Drive into a tree
📣 HOOOOOOONK! 🚚📢
Exit the car

Process finished with exit code 0

   $ _

#Closing Thoughts

With this method we can easily define finite state machines and create their API so that they can change and stay valid for the different states.

#Advantages

First, it allows fields that are common to multiple states to be de-duplicated. By making the non-shared fields generic, they are implemented once.

Second, it makes the impl blocks easier to read, because they are broken down by state. Methods common to all states are typed once in one block, and methods unique to one state are in a separate block.

Both of these mean there are fewer lines of code, and they are better organized.

Besides that adding or removing a given behaviour from a state can be as easy as adding or removing the impl SupportsSomeBehaviour for SomeState line.

#Disadvantages

This currently increases the size of the binary, due to the way monomorphization is implemented in the compiler¹.

#Alternatives

• If a type seems to need a “split API” due to construction or partial initialization, consider the Builder Pattern instead.

• If the API between types does not change – only the behavior does – then the Enum Pattern² is better used instead.

#See also

This pattern is used throughout the standard library, and also the embedded-hal ecosystem used for embedded devices makes extensive use of this pattern. For example, it allows statically verifying the configuration of device registers used to control embedded pins. When a pin is put into a mode, it returns a Pin<MODE> struct, whose generic determines the functions usable in that mode, which are not on the Pin itself⁵.

#Sources