I've found typestates (in the informal sense) to be indispensable for designing robust and easy-to-use APIs in Rust. It's also the first pattern I've run across that may be uniquely enabled by Rust language features. To raise awareness and document some useful variations, I wrote an article on it.
Hope y'all find that useful.
Great write-up!
I love this write-up, it encapsulates pretty much everything great about type-state in an easy to understand way!
Very nice write-up. It might be more appropriate to categorize this thread as "tutorial" instead of "announcement" ? We can later consolidate all the blogs, books into a wiki page. Btw, I heard typestate feature was experimented in Rust during pre 1.0 releases.
Nice write-up! This reminds me of the Pretty State Machine Patterns in Rust blog post from 2016.
I've also seen it in use a lot with embedded code, where you'll often need to initialize peripherals and the standard method is to use the typestate pattern to represent partially initialized peripherals, or when one peripheral is initialized and another isn't.
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.
Since you got me interested, I think you can sort of do this in Python with static typing. Here's a rough example (it should probably be read from the bottom up):
import typing
class ActualResponseState: pass
class HttpResponseFinished: pass
class HttpResponseAfterStatus:
def header(self, key, value):
return self
def body(self, text) -> HttpResponseFinished:
self._actual = None # drop the data
# Switch to a class with no methods
self.__class__ = HttpResponseFinished
return typing.cast(HttpResponseFinished, self)
class HttpResponse:
def __init__(self):
self._actual = ActualResponseState()
def status_line(self, code, message) -> HttpResponseAfterStatus:
# Magically switch class
self.__class__ = HttpResponseAfterStatus
return typing.cast(HttpResponseAfterStatus, self)
def a_simple_response(r: HttpResponse):
r.status_line(200, "OK") \
.header("X-Unexpected", "Spanish-Inquisition") \
.header("Content-Length", "6") \
.body("Hello!")
# These show errors
def broken_response_1(r: HttpResponse):
r.header("X-Unexpected", "Spanish-Inquisition")
def broken_response_2(r: HttpResponse):
r.status_line(200, "OK") \
.body("Hello!") \
.header("X-Unexpected", "Spanish-Inquisition")
Static checkers (like PyCharm and MyPy) will show the errors in the broken_response functions.
One limitation is I'm not sure how to automatically change the type hint for an instance other than by using a function to cast. E.g. this confused the static type checking:
r = HttpResponse()
r.status_line(200, "ok")
# Shows "unresolved attribute" for .header
# because the checker doesn't know the type has changed.
r.header("X-Unexpected", "Spanish-Inquisition")
However I'm not particularly familiar with the type checker so this could simply be a limitation with my understanding.
Also it should be noted that Python is very dynamic so static type checking can only get you so far.
Nice to see such a detailed article about this pattern 
PhantomData<VoidFoo> vs UnitFoo
One interesting point that could be expanded, since I don't think there is a clear answer to it, is whether to use void types wrapped in a PhantomData or to directly use custom (usually unit) types. The former clearly expresses the intent of working at the type level, whereas the latter allows adding data associated with the new / different states.
When I try to implement complex typestate-based APIs, one issue which I often face is combinatorial explosion.
For example, imagine a Builder that allows setting 6 parameters A, B, C, D, E, F such that...
Encoding this kind of complex logic in a true typestate API to guarantees that all usage errors are caught at compile time is hard, because of the large amount of states which such a system can be in. If we encode each state using a different type, the code can become very painful to write and maintain; and compile times can suffer. Rustdocs will also become unreadable real fast.
One cheap trick is to enforce that parameters are set in a certain order, which ensures that the library only needs to track O(N) states instead of O(2^N) ones. But that's bad for ergonomics, which is the reason we're using typestates to begin with. And it may not work in even more complex cases where the state being tracked is more complex than a bitfield. Imagine encoding a loop in the type system, for example.
Personally, I usually fall back to run-time checks when I end up in those kind of situations. But maybe people who are more used to the typestate pattern know of ways to make it scale better to complex cases?
Another cool technique you can do with state types is to make constructing the state type require applying the change, e.g. the only way to construct a Floating state here is by passing in some pin config and letting it write the correct configuration to it:
Then applying a state transition can be generic over the destination state (in this case the source state doesn't matter, but you could encode that into the transition as well)
Now, obviously you could pass in some unrelated pin config, or overwrite the configuration written by it after constructing it (inside this module, these are private traits that aren't exposed to users), but I still like this structure as a way to encode the state transitions directly with the state types.
Thanks for the feedback, y'all!
That's what inspired this, actually. The m4vga crate I call out in the last paragraph is definitely embedded.
@chrisd, that's interesting. I've seen similar tricks implemented in Objective-C, where it's pretty easy to change the class of an object at runtime. I don't think it counts, however.
The issue I see with this approach is that someone could retain a reference to one of the objects after any of the state transition methods, because (unless I've missed a recent feature) Python has no way to indicate that an object should become unavailable after an operation is performed. In this situation, the runtime would discover that you've changed the __class__ and complain that e.g. status_line is not a valid method -- but that's a dynamic check.
For example:
def sneaky_response(r: HttpResponse):
r.status_line(200, "OK") # note: return value ignored
r.status_line(200, "OK") # probably passes the type checker, as r: HttpResponse
r = r.status_line(200, "OK")
r.body("Hello!")
r.body("Hello!") # again, probably passes the type checker
Hm, that was the goal of the final Variation section. Is there anything I didn't cover that you think I should expand on? Happy to make edits!
I've spent the past ~2 years working at a Haskell shop, where I have developed an allergy to investing too much effort in expressing something at the type level. In a situation as complex as what you describe, I would probably resort to run-time checks -- or change my approach. (For instance, I don't find myself implementing builders as often as in other languages because of struct literals; I find that providing a parameter object containing the things my library needs to build a thing, and having the user write one as a struct literal, is often simpler and benefits from static checking.)
Indeed! That's essentially what I've done here in my display driver. It's really useful in embedded contexts.
Hm. I think of a "tutorial" as leading one through a single worked example, resulting in a working artifact -- this isn't that. But if people feel strongly I'm happy to move it (or let the mods do it).
My bad, I thought I had read all your article but as it turns out I didn't 
The second Variation part tackles this question with great detail, good job
If you want to see more complex examples of typestate,you can look at the readme for type_level as well as the type_level_examples crate.
As a highlight of type_level_examples I made a channel type which encodes a state machine on the type level
Good write-up! I want to call out two specific points you made that, while both fairly simple and "obviously true" in hindsight, were not necessarily "obvious", in that I'd never quite thought of them directly until you phrased it so clearly.
The first is right at the beginning: that basic ownership and drop semantics actually qualifies as a two-state instance of this pattern. We're doing it all the time, and the rest is not an additional pattern, but rather just ways of adding additional states. Just a small perceptual shift, but useful perspective. You tie it very nicely to the conclusion that these basic semantics are at the root of it all in comparison to other languages.
The second is in this comment with regard to serde:
Serializeris 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 forserde's success.
Having implemented this trait several times while essentially having no clue what I am doing, I can attest to this directly.
The example I would have naturally thought of was the design of the embedded_hal traits. A lot of work went into getting those right, so that they'd be ergonomic for end-users as well as nicely implementable for HAL implementors on various different hardware.
But the serde example is much better. In the HAL case, the implementors of specific hardware crates are working at a lower level again, and are easily thought of as wizards and experts in the domain. It's very easy, as an end-user, to think of them all of a piece, as parts of a coherent ecosystem - which is of course the intent.
What the serde example really points out is that the trait pattern can be used to constrain (provide safety) for external end-user implementations as well. A library author can provide an enforceable type-state pattern of traits for an end-user consumer of the library to implement, safely.
And, of course, to the compiler there's not much difference between these cases, once the realisation has hit.
Finally, a wish:
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.
I wish you had shown that example, because I vastly prefer using libraries that way. Ever so often I trip over one that didn't provide this, and it always feels a little cumbersome, like .. just a missed opportunity. Since I suspect people will be referring to this post for a while to come, it would be nice to show "best practice", though I know you left it out because it wasn't really an important part of your point.
Ahhhh...you have found the author's bias on this one. 
I am personally not a fan of returning things that the caller already has, unless necessary (i.e. if they have given me ownership, so I must give it back). It makes the API harder to explain: "this method returns a &mut T that we promise is the same object as self, because we want to support this one coding pattern that some people use."
It can also be confusing to the user in cases like this:
trait Builder {
fn name(&mut self, name: &str) -> &mut Self;
fn age(&mut self, age: usize) -> &mut Self;
}
fn apply_settings(b: &mut impl Builder) {
// This code does not compile. Do you see why?
b.name("Bob").age(32)
}
(Though as of fairly recently, rustc suggests the correct fix.)
That being said, this isn't the part I feel strongly about, so write your code either way -- it's aesthetics.
Tried it in the playground, and after adding either the semicolon or the return type it compiled successfully. What do you mean here? The problem doesn't look like something connected to the particular Builder pattern...
Another use of type states is to encode scientific units, like in the uom crate. This way you can catch unit errors as type errors!
Great post! I made StateTypes in Rust my field of hobby research.
It seems most people started really getting into the topic after the Hooverbear post. I still remember being amazed by its contents and eventually read it multiple times. Another post that influenced my interests was about embedded_hal, written around december 2017, but i can't remember which post it was exactly 
. I found it on the Hacker News board, probably Japaric's 'Brave new I/O' but reading it now it doesn't seem really familiar.
Thanks for introducing Serde as a State Type library. I wasn't aware mister dtolnay was knees deep into the topic, although i vaguely remember him being part of the labelledgeneric implementation of Frunk. I could be wrong.
So far i have attempted building a state machine for card games, where each card effect implementation simply couldn't give unexpected results. It was never finished, but had an interesting discovery regarding pushdown/pullup transitions -> a compile time stack concept fits really well into Rust and can act as constraint to perform the correct pullup transition (reverse of pushdown).
The last thing i thought about was a single allocation session object for a protobuffer API. Through type-magic it should compose filters and constraints (eg only X (async) handlers can be active for a specific route at a given time) without imposing runtime allocation costs. The code would ideally compile down to a massive (optimised?) switch statement, while conceptually all operations are verified by the rust compiler. Somewhere in there should also be a reactor that keeps polling non fulfilled requests... Basically something similar to Warp's request->response pipeline, but too big in scope! 
I'd be interested in checking out the code even if it's incomplete.
It was... and it was different. It was about tagging variables with boolean predicates. I gave an explanation on Stackoverflow a long time ago (2012!).