- What are typestates?
- A simple example: the living and the dead
- More than one “living” state
- Typestate in the wild: serde
- Variation: state type parameter
- Variation: state types that contain actual state
The typestate pattern is an API design pattern that encodes information about an object’s run-time state in its compile-time type. In particular, an API using the typestate pattern will have:
Operations on an object (such as methods or functions) that are only available when the object is in certain states,
A way of encoding these states at the type level, such that attempts to use the operations in the wrong state fail to compile,
State transition operations (methods or functions) that change the type-level state of objects in addition to, or instead of, changing run-time dynamic state, such that the operations in the previous state are no longer possible.
This is useful because:
- It moves certain types of errors from run-time to compile-time, giving programmers faster feedback.
- It interacts nicely with IDEs, which can avoid suggesting operations that are illegal in a certain state.
- It can eliminate run-time checks, making code faster/smaller.
This pattern is so easy in Rust that it’s almost obvious, to the point that you may have already written code that uses it, perhaps without realizing it. Interestingly, it’s very difficult to implement in most other programming languages — most of them fail to satisfy items number 2 and/or 3 above.
I haven’t seen a detailed examination of the nuances of this pattern, so here’s my contribution.
What are typestates?
Typestates are a technique for moving properties of state (the dynamic information a program is processing) into the type level (the static world that the compiler can check ahead-of-time).
Typestates are a broader topic than the specific pattern I’ll discuss here, which is why I’m calling it the “typestate pattern.”
The special case of typestates that interests us here is the way they can enforce run-time order of operations at compile-time. Here are some examples of properties that can be enforced by the typestate pattern in Rust (I assert — I don’t have implementations of all of them):
“The buffer can only be translated if you have checked that it’s valid UTF-8.”
“You must not perform any I/O operations on a file handle after it’s been closed.”
“These messages can only be sent to the client after authentication has succeeded, and not after we have ended the session.”
“Once you have done action A, you must perform either B or C (but not both) before you can do D.”
In most other languages, we would have to handle these with runtime checks and errors/exceptions. Or, we might get lazy and not check them at all, instead mentioning them in the documentation and hoping people read it!
With the typestate pattern, we can prevent code that breaks these rules from compiling, helping programmers find mistakes earlier and eliminating the overhead of run-time checks.
A simple example: the living and the dead
There’s a common pattern in Rust libraries that allows an API to have two
states, “living” and “dead.” Or, to put things concretely,
from the standard library has two states: “open” and “closed.” If you have
access to a
File, it’s open: the only way to obtain one1 is from the
// At this point, we do not yet have access to a File. // Open one: let file = open?; // Here, we have access to `file`, and it's open. If opening had // failed, we would have gotten an error.
In every case, when I say something like “the only way to X,” there’s an implicit caveat: “using safe code.” Using unsafe code it is possible to violate any invariant in the language, if you work hard enough at it! All guarantees discussed here are in terms of safe code.
We can close a file by letting it go out of scope, but for the sake of this
discussion, let’s explicitly give up access using
drop; // Trying to use the file after close is a compile error: // file.read_to_string(&mut buffer); <-- DOES NOT COMPILE
This works because of the signature of
drop takes its argument by value, not by reference (
means the argument gets moved into the
drop function, and the caller loses
access to it.
This is an example of the typestate pattern, enforcing the property “you may not
perform other operations on a
File after closing it.”
This might look like RAII to you, and you’re right. In Rust, most cases of the
RAII pattern are also applications of the two-state typestate pattern. For
Box maintains two properties of the pointer it contains:
Boxmay point to a given heap-allocated chunk at any given time.
Once the heap-allocated chunk has been deallocated, no
Boxes may point to it.
But compared to RAII in other languages, particularly C++, there’s a crucial difference: when we change states, the object in the previous state, whether an open file or a smart pointer, can no longer be used. This is because Rust’s notion of “moving” a value causes the previous owner to lose access to the value, while in most other languages, this is not true.
Aside: why this doesn’t work well in other languages
Here’s a simple RAII-as-typestate example in Rust, using
Box. We’ll try to
Box after it’s been moved, which will fail to compile:
Here’s an equivalent example in C++. (I’m picking on C++ because it’s so similar to Rust.) This example does not work, which is to say, it compiles:
static int int
This program compiles without so much as a warning on GCC 7
what it’s doing here is technically legal. Moving a value in C++ does not affect
our ability to access the original. In fact, C++ even defines what
contains after we move it: it’s now
nullptr. So this is a “valid” program that
crashes without printing anything2.
Okay, technically, dereferencing
nullptr is undefined behavior in
C++. But in practice, unless you’re on an ancient version of Unix or a very
obscure embedded system, it crashes the program.
A move in C++ is really a copy, but a special copy that can alter the original. Nothing prevents us from doing stuff with the original after the move; at best, it can throw an exception at runtime when we try. (At worst, it can ignore this problem and do undefined things.)
This difference in move semantics in the two languages is subtle, but this little difference is enough to make it difficult to implement a robust typestate pattern in C++. Few other languages even have move semantics (or mechanisms that can be used to do the same thing, like linear types), making the pattern much, much harder.
More than one “living” state
Going beyond RAII, we might want to have more than one “living” state for our object.
Here’s a motivating example. Let’s design an interface for generating an HTTP protocol response. We don’t need to get into the nitty-gritty of HTTP — for this discussion, all you need to know is that an HTTP response consists of:
- Exactly one status line.
- Zero or more headers.
- An optional body.
We would like an API where this compiles:
And this does not:
(Notice that I’m using method chaining, i.e.
x.foo().bar(). The reason will
be apparent shortly.)
One way to do this is to model each state as a separate type:
status_lineoperation converts an
headerleaves the type unchanged.
Notice that each operation consumes
self and either produces a new object in
a certain state, or (in the case of
body) produces nothing, ending the process.
- We can’t send a header before the status line, because the operation simply isn’t defined.
- We can’t send a status line after the header, because, likewise, it isn’t defined on the type.
- We can’t do anything after sending the body, because the object is taken away from us.
That’s a decent interface. Let’s consider the implementation.
HttpResponseAfterStatus) gets consumed
and recreated at every step, it needs to be cheap, which is to say, fairly
small. An easy technique is to make both types simple wrappers for a smart
pointer to the actual state, which stays the same in all type-states:
This API is okay, but it will be awkward if we want to generate headers in a
loop, because we have to keep replacing the consumed
To make this more pleasant, operations that don’t change the typestate are often
defined as taking
// Let's try this again:
Optionally (not shown above), you can also have the operation return the reference to self, which lets the user choose whether or not to use method chaining.
Typestate in the wild:
There are several examples of the typestate pattern in widespread use in the
Rust ecosystem. The highest-profile one that I’m aware of is
Serializer models a fairly complex state machine using
typestates. For instance,
- Starting with a
serialize_structoperation consumes it and produces an object that implements the
- You can call the
skip_fieldmethods zero or more times.
endmethod consumes the
SerializeStructand produces a result.
You cannot accidentally call
serialize_struct twice, or call both
serialize_i32, or add fields to the struct after
end. You cannot serialize two values where one was expected.
Attempting any of these will produce a compile error.
Serializer is a trait that third-parties will implement to define new data
formats. Because the trait is specified using the typestate pattern, it’s
basically impossible for an implementation to misbehave using safe code, except
for randomly panicking. I suspect this robustness is part of the reason for
Variation: state type parameter
Instead of having a separate struct for each state, we can model state as a type parameter for a single generic struct. This is often less boilerplatey and more powerful than having entirely separate types, but it’s also harder to explain, which is why I didn’t cover it first.
Consider the HTTP response example again. Here’s how we might model it using a state type parameter:
// S is the state parameter. We require it to impl // our ResponseState trait (below) to prevent users // from trying weird types like HttpResponse<u8>. // State type options. // expecting status line // expecting headers or body
I’ll pause there, as there’s a lot going on.
Unlike generic types like
Vec<T> that can be applied to almost any
HttpResponse<S> type to be used with only two values of
HttpResponse<Headers>. (Technically, as written, the
user could implement
ResponseState for a custom type and try using it with
HttpResponse. If that bothers you, you can use the sealed trait pattern to
Headers are types that exist only as types, and not as values;
we’ve used the zero-variant enum pattern to ensure this. Types like this are
broadly referred to as phantom types, which is where
std::marker::PhantomData gets its name from.
Okay, let’s define some operations on
/// Operations that are valid only in Start state. /// Operations that are valid only in Headers state.
So far this is equivalent to the original code, which didn’t use generics. Why is this more powerful, then?
State type parameters enable several interesting things:
It’s easy and concise to add operations that are valid in all states, or a subset of states.
All of these operations on the
HttpResponseshow up on the same generated
HttpResponse, but under separate headings, one per impl block. You can attach doc comments to each impl block, as shown above, to help users follow along. In the previous example with one type per state, the methods are spread across multiple pages, making them harder to follow.
To add an operation that’s valid in any state, we simply leave
/// These operations are available in any state.
We only have two states in this example, but if we had more, we might want to add operations that are valid in more than one state, but not all states. To do this, we can use a trait to identify the states, and a constrained impl block to define the operations:
/// Trait implemented by states that are sending data. // other states could go here /// These operations are only available in states that /// impl SendingState.
Variation: state types that contain actual state
In the original version, when we were modeling each state with a totally separate type, we could easily add some fields to one struct and not the other, to store different information in different states. Now that we’re using a single generic struct in all states, it appears that we’ve lost this ability. But we can fix that.
In the most recent example above, the state types used as state type parameters
were phantom types that couldn’t be instantiated at runtime. This is often
useful, but doesn’t have to be the case. If the state types are concrete, we
can store stuff inside them; by storing an
S inside our common struct, we
inherit its contents.
For example, we might want to track the status code that we sent back to the
client in our HTTP response. We could use an
Option<u8>, which would start out
None and get set to
status_line, but that’s not ideal for
Any function, in any state, could try to access the code, even though it only makes sense to do so once the status line has been sent.
Any access to the code will have to deal with
None, even though we know the field is set after the status line has been sent.
We’ll be allocating space for the code in all states, which is a waste. In this case, the field is small (one byte), but what if it’s large?
These issues go away if we put the state inside the state type used as a parameter:
// Similar to before: // State type options. These now can add fields to HttpResponse. // Start adds no fields. ; // Headers adds a field recording the response code we sent.
Now, when we’re operating on an
HttpResponse<Start>, we can’t try to access
response_code — it simply isn’t there. This also means that in
state, the response is one byte smaller than in
Headers; that’s probably
insigificant here, but can become useful if you need to store more state.
Headers state, though, we’re guaranteed to have
response_code and we
can access it directly.
I use this variant in my m4vga crate, which provides a video driver. The video driver can be in multiple states depending on how much you’ve set up, and it stores different amounts of information in each state.
The typestate pattern is natural to use in Rust, and lets us design APIs that are easy to use correctly and impossible to use incorrectly. I’m sure there are more variations that I haven’t covered — I’d love to hear about them, drop me a line.
Also: I’d be interested in hearing about successful implementations of this pattern in languages other than Rust. At first glance, it seems to require a language with checked move semantics, but I bet you can find a way around that.