The reliability of software systems has doubtlessly been the topic of conversation at many conference room - and dinner - tables. Since the first computer was ejected from the nest and gracefully flew to the skies, developers have been throwing a variety of test paradigms and linters at the problem. Alas, it has all been to very little effect in my opinion.

Now don’t get me wrong, in recent decades we have indeed gotten quite proficient at testing. That is, testing for the failure modes that we can think of. And that is an major distinction! The unknown unknowns about that failure modes in our system will, by definition, continue to trouble us forevermore.

I’ll make an empirical assertion here without much to back it up, but if you’ll bear with me: I believe that most errors stem from misuse. I won’t stoop to making a quantitative assessment of that, take it as you’d like.

And so, personally, whenever I’m tutoring anybody in the art of software design ¹ I tend to repeat the same simple mantra:

$$\text{“Make misuse inexpressible”}$$

The problem

Any time you’re putting together a new module, always ask yourself: how could the user misuse it?

Let’s look at a simple example.

struct Cat {
    name: String,
    hunger: u8,
    is_alive: bool,
}

The above is a naive representation of data about a cat. This is perhaps how someone would draw it up in one of the more architecturaly-challenged languages during the dark ages before Rust came along.

The problem is evident immediatelly: what on earth is the definition of the hunger field when is_alive=false?

/// Every present and future developer must remember to check
/// for invariants!
impl Cat {
    fn feed(&mut self) {
        assert!(self.is_alive);
        ...
    }
    fn kill(&mut self) {
        assert!(self.is_alive);
        ...
    }
}

The situation you’re placing all maintainers and users of your module in may be visualized like so:

The Cat case might seem simple and benign, but the problem is actually exponential² in nature! Each new field extends the possible states of the system by all its permutations with existing fields. And if I were a betting man, I’d put my money on the set of invalid states growing at a faster rate than the set of valid ones, pretty much every time.

The stopover solution: Algebraic types

Thankfully us Rust developers don’t have to suffer like our predecessors. The Algebraic Data Type system already puts us light years ahead of others when it comes to reliably defining states in our systems.

enum CatState {
    Dead,
    Alive {
        hunger: u8,
    }
}

struct Cat {
    name: String,
    state: CatState,
}

The above is the simplest and most elegant way you can get yourself half-way out of the tar pit³. This is already the first design that would come to the mind of any Rust developer, driving us into a state of ache and discomfort when we are forced to interact with other programming languages.

This already gets you most of the way there: you’ve now made invalid states inexpressible. However, misuse is still somewhat expressible since the user may attempt to feed a dead cat. However by tucking away the hunger field under the Alive state, we have essentially guaranteed that no dead cat can ever be fed! Then it just becomes a matter of error handling.

impl Cat {
    fn feed(&mut self) -> Result<()> {
        let CatState::Alive { hunger: &mut u8 } = &mut self.state
        else
        {
            return Err(TriedToFeedDeadCat);
        };
        *hunger = 0;
        Ok(())
    }
}

We have now transformed the problem into the following:

The Typestate pattern

The above pattern, as you can see, leaves you still with some pesky runtime errors from incorrect use of the module’s API. Depending on the application that might not be a problem though. Error handling in rust is quite versatile and rarely needs to crash the system. It also happens to be mandatory, so the chances of harmful side effects from a Result::Err being returned are near nil.

However what if we wanted to make the module more reliable still? Well if you’re a Rust developer I’m sure you can see where this is going. In the previous chapter we leveraged the compiler to take what would have been invalid cats running around the system (runtime errors) and made them inexpressible (compilation errors). Now we will do something similar to make incorrect uses of the API also compilation errors!

The idea is quite forthright: dead cats shouldn’t have a feed() method at all.

Going back to the example with the kitty:

pub struct Alive { hunger: u8 };
pub struct Dead(()); // private tuple field (optional)
                     // prevents creation out of the module

trait CatState {} // this typically stays private
impl CatState for Dead {}
impl CatState for Alive {}

pub struct Cat<S: CatState> {
    name: String,
    state: S,
}

Then operations may be defined separately for Cat<Alive> and Cat<Dead>:

impl Cat<Alive> {
    /// Cats can only be created alive.
    pub fn new() -> Cat<Alive> { ... }

    /// Only alive cats can be fed!
    pub fn feed(&mut self) { ... }

    /// State transitions consume the object and return a new type!
    pub fn kill(self) -> Cat<Dead> { ... }
}

impl Cat<Dead> {
    /// Only bury the poor kitty if you're sure it's dead!
    pub fn bury(self) { ... }
}

And operations which apply to a cat in any state can of course still be defined.

impl<S: CatState> Cat<S> {
    pub fn name(&self) -> &str { &self.name }
}

The object’s state is now encoded in its type, how cool is that?!

Can we do this in other languages?

The short answer is: with great difficulty, and only a fraction of the reliability.

The key takeaway here is that in order to enforce the typestate pattern we rely on move semantics to control when object transitions from one state to the next. Without a move operator Cat::kill() would have to return a brand new Cat<Dead> while the user gets to keep on to his Cat<Alive> instance. This in my opinion would leave you in a state worse off than not using the typestate pattern at all, since the latent errors left over by defunct objects would far outnumber any usage errors you may need to handle.

Some languages like C++ do have something resembling a move operation now, however the compiler guarantees there basically non-existent⁴.

In summary

• Software systems have data structures with variables, out of which some tend to only be valid in a subset of states. This leads to runtime errors, as objects may exist in invalid states throughout the codebase.
• As new fields are added to an object, its set of invalid states tends to grow at a faster rate than the set of valid ones. This expands the application’s threat surface exponentially as it grows in complexity.
• Invalid states may be prevented at compile-time through proper use of Algebraic Data Types.
• Incorrect uses of an object while using ADTs is generally safe, since proper error handling is difficult to miss when consuming enums.
• Misuse of an object can be made completely inexpressible at compile-time through the Typestate pattern.