Level 4 · Expert· Lesson 8 of 9 · 35 min
Type-level programming
Typestate, phantom types, const generics, type-level computation with traits, and making invalid programs fail to compile.
Rust’s type system can check far more than “this is an integer”. With phantom parameters, traits and const generics you can move whole classes of runtime errors — wrong order of calls, mismatched units, mis-sized buffers — to compile time, at zero runtime cost.
Typestate
A protocol has states, and each state permits different operations. Encode the state as a type parameter:
use std::marker::PhantomData;
// States: zero-sized marker types.
struct Disconnected;
struct Connected;
struct Authenticated;
struct Session<State> {
host: String,
log: Vec<String>,
_state: PhantomData<State>,
}
impl Session<Disconnected> {
fn new(host: &str) -> Self {
Session { host: host.into(), log: vec![], _state: PhantomData }
}
fn connect(mut self) -> Session<Connected> {
self.log.push(format!("connected to {}", self.host));
self.transition()
}
}
impl Session<Connected> {
fn login(mut self, user: &str, password: &str) -> Result<Session<Authenticated>, Session<Connected>> {
if password == "hunter2" {
self.log.push(format!("{user} logged in"));
Ok(self.transition())
} else {
self.log.push("bad password".into());
Err(self) // stay in the Connected state; the caller may retry
}
}
}
impl Session<Authenticated> {
fn query(&mut self, sql: &str) -> usize {
self.log.push(format!("ran `{sql}`"));
sql.len()
}
}
// Available in every state.
impl<S> Session<S> {
fn transition<T>(self) -> Session<T> {
Session { host: self.host, log: self.log, _state: PhantomData }
}
fn log(&self) -> &[String] {
&self.log
}
}
fn main() {
let session = Session::new("db.example.com").connect();
// session.query("SELECT 1"); // ❌ would not compile: no method `query` on Session<Connected>
let session = match session.login("ada", "wrong") {
Ok(s) => s,
Err(s) => s.login("ada", "hunter2").ok().expect("second attempt"),
};
let mut session = session;
session.query("SELECT 1");
println!("{:#?}", session.log());
}
Transitions take self by value, so the old state is consumed: you cannot keep using a Session<Connected> after logging in. Ownership and typestate reinforce each other — in a language without move semantics the stale handle would remain usable.
When to use it: protocols with a small, linear set of states where misuse is costly (builders with required fields, connection handshakes, hardware pins, transaction lifecycles). When states are numerous or chosen at runtime, an enum is the better tool.
Phantom types for units and brands
use std::marker::PhantomData;
use std::ops::{Add, Div};
#[derive(Debug, Clone, Copy, PartialEq)]
struct Quantity<Unit> {
value: f64,
_unit: PhantomData<Unit>,
}
#[derive(Debug, Clone, Copy, PartialEq)] struct Metres;
#[derive(Debug, Clone, Copy, PartialEq)] struct Seconds;
#[derive(Debug, Clone, Copy, PartialEq)] struct MetresPerSecond;
impl<U> Quantity<U> {
const fn new(value: f64) -> Self {
Quantity { value, _unit: PhantomData }
}
}
// Same units add.
impl<U> Add for Quantity<U> {
type Output = Quantity<U>;
fn add(self, o: Self) -> Self { Quantity::new(self.value + o.value) }
}
// Distance / time = speed. No other division is defined.
impl Div<Quantity<Seconds>> for Quantity<Metres> {
type Output = Quantity<MetresPerSecond>;
fn div(self, t: Quantity<Seconds>) -> Self::Output { Quantity::new(self.value / t.value) }
}
fn main() {
let d = Quantity::<Metres>::new(100.0) + Quantity::new(100.0);
let t = Quantity::<Seconds>::new(19.19);
let v: Quantity<MetresPerSecond> = d / t;
println!("{:.2} m/s", v.value);
// let nonsense = d + t; // ❌ would not compile: mismatched types
// let also = t / d; // ❌ would not compile: no impl of Div
}
Quantity<Metres> and Quantity<Seconds> are both a bare f64 at runtime. The Mars Climate Orbiter was lost to a units error that this turns into a compile error. The uom crate develops the idea fully.
Const generics as type-level values
#[derive(Debug, Clone, Copy)]
struct Matrix<const R: usize, const C: usize>([[i64; C]; R]);
impl<const R: usize, const C: usize> Matrix<R, C> {
// The inner dimensions must agree — checked by the type system.
fn mul<const K: usize>(&self, rhs: &Matrix<C, K>) -> Matrix<R, K> {
let mut out = [[0; K]; R];
for r in 0..R {
for k in 0..K {
for c in 0..C {
out[r][k] += self.0[r][c] * rhs.0[c][k];
}
}
}
Matrix(out)
}
}
/// A buffer whose capacity must be a power of two — verified at compile time.
struct Ring<const N: usize> {
data: [u8; N],
head: usize,
}
impl<const N: usize> Ring<N> {
const CHECK: () = assert!(N.is_power_of_two(), "Ring capacity must be a power of two");
fn new() -> Self {
let () = Self::CHECK; // forces evaluation for this N
Ring { data: [0; N], head: 0 }
}
fn push(&mut self, byte: u8) {
self.data[self.head & (N - 1)] = byte; // cheap wrap-around, valid only for powers of two
self.head += 1;
}
}
fn main() {
let a = Matrix([[1, 2, 3], [4, 5, 6]]); // 2×3
let b = Matrix([[1, 0], [0, 1], [1, 1]]); // 3×2
println!("{:?}", a.mul(&b)); // 2×2
// a.mul(&a); // ❌ would not compile: expected Matrix<3, _>, found Matrix<2, 3>
let mut ring = Ring::<8>::new();
for b in 0..10 { ring.push(b); }
println!("{:?}", ring.data);
// Ring::<6>::new(); // ❌ fails to compile: "Ring capacity must be a power of two"
}
An associated const containing an assert! is a post-monomorphization check: it is evaluated per instantiation, turning a property of a const parameter into a compile error. Stable const generics accept integers, bool and char; arithmetic in types ([T; N + 1]) remains unstable (generic_const_exprs).
Computing with traits
A trait impl is a logical rule; the solver searching for an impl is a proof search. With associated types the search returns an answer. Peano arithmetic, entirely at compile time:
use std::marker::PhantomData;
struct Zero;
struct Succ<N>(PhantomData<N>);
trait Nat { const VALUE: usize; }
impl Nat for Zero { const VALUE: usize = 0; }
impl<N: Nat> Nat for Succ<N> { const VALUE: usize = N::VALUE + 1; }
// Addition: 0 + B = B S(A) + B = S(A + B)
trait Add<B> { type Sum; }
impl<B> Add<B> for Zero { type Sum = B; }
impl<A: Add<B>, B> Add<B> for Succ<A> { type Sum = Succ<A::Sum>; }
type One = Succ<Zero>;
type Two = Succ<One>;
type Three = Succ<Two>;
type Five = <Two as Add<Three>>::Sum;
/// A vector whose length is tracked in its type.
struct Vect<T, N> { items: Vec<T>, _len: PhantomData<N> }
impl<T> Vect<T, Zero> {
fn new() -> Self { Vect { items: Vec::new(), _len: PhantomData } }
}
impl<T, N> Vect<T, N> {
fn push(mut self, item: T) -> Vect<T, Succ<N>> {
self.items.push(item);
Vect { items: self.items, _len: PhantomData }
}
}
impl<T, N> Vect<T, Succ<N>> {
/// `first` exists only for non-empty vectors, so it needs no Option.
fn first(&self) -> &T { &self.items[0] }
}
fn main() {
println!("2 + 3 = {}", <Five as Nat>::VALUE);
let v = Vect::new().push("a").push("b");
println!("{}", v.first());
// Vect::<u8, Zero>::new().first(); // ❌ would not compile: no method `first` on Vect<u8, Zero>
}
The typenum crate is this idea made practical (binary rather than unary), and it powered fixed-size arrays in the ecosystem before const generics. The same machinery implements heterogeneous lists (frunk), compile-time dimensional analysis, and type-level state machines.
The trait system is Turing-complete, which is why the compiler has a recursion limit. That is a warning as much as a boast.
Other techniques, briefly
- Sealed traits and marker traits to define closed sets of types (
trait State: sealed::Sealed), so users cannot invent a state. - Witness types and tokens: a value whose existence proves something happened — a
MutexGuardproves the lock is held; a zero-sizedInitializedtoken returned byinit()and required by other functions proves ordering. - Branded lifetimes: an invariant lifetime created by a
for<'id>closure is unique, so indices branded with it can be proven in bounds for one specific collection (GhostCell, theindexingcrate). - Higher-kinded patterns via GATs: abstracting over
Option<_>,Vec<_>as type constructors. const fnand const evaluation: compute lookup tables and validate configuration at compile time.
Judgement
Type-level programming is a trade. It buys guarantees; it costs error-message quality, compile time, and the number of people who can maintain the code. Guidelines:
- Encode invariants whose violation is expensive and plausible. A newtype is nearly free. A typestate builder is cheap. A type-level interpreter is rarely worth it.
- Prefer the simplest mechanism: newtype → enum → typestate → const generics → trait-level computation.
- Check what users see when they get it wrong.
#[diagnostic::on_unimplemented]lets you supply a human-readable message for a missing impl.
Exercises
- Write a typestate builder for
HttpRequestwhereurlandmethodare required andbuild()exists only when both have been set. Use two type parameters withMissing/Presentmarkers. - Extend
QuantitywithMulso thatMetresPerSecond × Seconds = Metres. - Add type-level multiplication to the Peano numbers and check
2 × 3 = 6. - Write
fn concat<T, const A: usize, const B: usize>(a: [T; A], b: [T; B]) -> Vec<T>, and explain why returning[T; A + B]is not possible on stable Rust. - Implement a file handle with states
Closed,Open<ReadOnly>, andOpen<ReadWrite>, wherewriteexists only forReadWrite.
Check your understanding
Pick an answer to see the explanation.
1.What is the typestate pattern?
2.What runtime cost does a
PhantomData<State>marker add?3.Why does Rust's trait system amount to a logic programming language?