Typestate: Encoding Protocols in Types

Many APIs are not collections of independent methods. They are protocols. A file must be opened before it is read and cannot be read after it is closed. A request builder needs a destination before it can send. A transaction may commit or roll back exactly once. Documentation can describe those rules, and runtime guards can detect violations, but an ordinary object often exposes every method in every state.

Typestate changes the interface as a value moves through its protocol. Instead of one Upload type with append, verify, and publish methods that may throw “wrong state,” there are state-specific forms such as Upload<Receiving> and Upload<Verified>. A transition consumes one form and returns another. Code that tries to publish an unverified upload does not have the required type.

The thesis is precise: typestate makes legal operation sequences part of static API shape. It is most effective when the language also controls ownership and aliases, because changing a type is useful only if stale references cannot keep using the previous state. Runtime state and validation still matter at I/O boundaries, after process restarts, and wherever the compiler cannot see the complete protocol.

Model the Protocol Before Designing Its Types #

Start with a transition system, not generic syntax. Let $S$ be a set of states and $O$ a set of operations. A partial transition function

is defined only for legal state-operation pairs. If publish is valid from Verified but not from Receiving, then $\delta(Verified, publish)$ exists and $\delta(Receiving, publish)$ does not.

For a resumable upload, a useful protocol might be:

Write an invariant beside every state:

The table exposes decisions that code otherwise obscures. Is abort legal after verification? Can verification be repeated? Is publishing idempotent? Are terminal values retained for inspection? Typestate cannot repair an ambiguous protocol; it faithfully encodes whatever transition graph is chosen.

State should represent a meaningful change in available operations or guarantees. Creating ReceivingChunk17 and ReceivingChunk18 types would encode incidental progress and make APIs unusable. The current byte offset belongs in runtime data inside Receiving; the fact that appending is allowed belongs in its type.

Make Each State Expose Only Its Legal Operations #

There are two common representations. One uses separate concrete types such as CreatedUpload and VerifiedUpload. The other uses a generic carrier with a phantom state parameter:

Upload<Created>
Upload<Receiving>
Upload<Verified>
Upload<Published>

The state parameter is called phantom when it exists for static distinction but has no corresponding runtime field. Methods are implemented only for the states where they are legal:

struct Created;
struct Receiving { next_offset: u64 }
struct Verified { digest: Digest }
struct Published;

struct Upload<State> {
    id: UploadId,
    object: TemporaryObject,
    state: State,
}

impl Upload<Created> {
    fn begin(self) -> Result<Upload<Receiving>, BeginError> { /* ... */ }
}

impl Upload<Receiving> {
    fn append(&mut self, chunk: &[u8]) -> Result<(), AppendError> { /* ... */ }
    fn finish(self, expected: Digest) -> Result<Upload<Verified>, VerifyError> { /* ... */ }
    fn abort(self) -> Result<Upload<Aborted>, CleanupError> { /* ... */ }
}

impl Upload<Verified> {
    fn publish(self) -> Result<Upload<Published>, PublishError> { /* ... */ }
}

There is no publish method on Upload<Receiving>, so autocomplete does not offer it and compilation rejects a direct call. finish consumes self, making the receiving handle unavailable after a successful transition. The terminal type has no mutating methods.

State-specific data also becomes precise. Only Receiving needs next_offset; only Verified carries a trusted digest. A single object with nullable nextOffset, nullable digest, and a status enum would permit combinations such as Created plus a digest unless every constructor and mutation defended the invariant.

This is related to, but distinct from, a closed algebraic data type. A sum such as Created | Receiving | Verified is useful when one consumer must inspect any state at runtime. Typestate instead gives a caller one known state and changes the available API at transitions. Systems often use both: a dynamic sum at a storage or message boundary, then a state-specific value after validation.

Work Through a Safe Upload Transition #

Assume a client creates an upload, sends chunks, verifies the complete object, and publishes it. A successful path can be written without status checks:

fn receive_upload(
    created: Upload<Created>,
    chunks: impl Iterator<Item = Vec<u8>>,
    expected: Digest,
) -> Result<Upload<Published>, UploadError> {
    let mut receiving = created.begin()?;

    for chunk in chunks {
        receiving.append(&chunk)?;
    }

    let verified = receiving.finish(expected)?;
    let published = verified.publish()?;
    Ok(published)
}

The variable names are not the guarantee. The types after each line are. Swapping the last two operations fails because Upload<Receiving> has no publish. Calling append after finish fails because finish moved receiving. Calling publish twice fails because the first call consumes verified.

Failures need careful transition semantics. If finish returns only Result<Upload<Verified>, VerifyError> and consumes the receiver, a caller cannot abort or retry after verification fails. That may be intentional if a failed digest permanently poisons the upload. If retry is legal, return ownership on failure:

enum FinishFailure {
    Retryable { upload: Upload<Receiving>, cause: IoError },
    Rejected { upload: Upload<Aborted>, cause: PolicyError },
}

fn finish(
    self,
    expected: Digest,
) -> Result<Upload<Verified>, FinishFailure> { /* ... */ }

Now each error branch states what resource remains and what can legally happen next. This is more informative than an exception that leaves callers guessing whether the receiver is still usable.

The static protocol still surrounds runtime work. finish must compute the actual digest, compare sizes, and atomically record the verified state. publish must tolerate a network failure after storage accepted the operation. A durable idempotency key or compare-and-set transition can make replay safe. Typestate prevents a local source program from issuing an obviously invalid sequence; persistence and distributed failure require their own controls.

Ownership and Lifetimes Protect the State Claim #

Typestate examples often hide the hardest question: what happens to aliases? Consider a language where two variables can reference the same mutable upload:

const first = receiving;
const alias = receiving;
const verified = first.finish();
alias.append(chunk); // Can this stale reference still mutate the object?

A generic state parameter alone does not invalidate alias. If finish mutates a shared object and merely returns it under a new static type, the old view can violate the invariant. Private constructors and disciplined code reduce the risk, but they are not ownership.

Affine or linear typing provides the cleanest foundation. An affine value may be used at most once; a linear value must be used exactly once. A consuming transition moves the resource, so no usable handle remains under the old state. Borrowing allows temporary access without transferring ownership: append(&mut self, ...) obtains one exclusive mutable borrow, while an immutable inspection can use a shared borrow if that cannot invalidate the state.

Lifetimes matter when state values expose dependent resources. A database Transaction<Open> might lend a row cursor that cannot outlive the transaction. Committing while the cursor is borrowed must be rejected, otherwise the cursor could read through a closed transaction. The type relationship is not merely Open -> Committed; it also constrains references tied to Open.

Garbage-collected languages can approximate consuming APIs with closures, encapsulation, unique tokens, or lint rules, but the guarantees are weaker when aliases and casts remain possible. A practical TypeScript API might return fresh immutable wrappers and keep mutable state in a private implementation. It should still retain runtime guards because structural assignment, any, and stale closures can bypass the intended sequence.

Concurrency adds another boundary. Sending Upload<Receiving> to another task should transfer ownership or synchronize access. If two tasks can append through independent handles, the state type says nothing about ordering or offsets. Pair typestate with the language’s sendability, borrowing, or synchronization rules rather than treating the state marker as a lock.

Use Staged Builders for Construction Protocols #

A builder is a small protocol: certain fields are required before build becomes legal. Typestate can replace one builder whose build() throws at runtime with stages that expose only valid next operations.

type Headers = Readonly<Record<string, string>>;

interface NeedsUrl {
  url(value: URL): NeedsMethod;
}

interface NeedsMethod {
  method(value: 'GET' | 'POST'): ReadyRequest;
}

interface ReadyRequest {
  header(name: string, value: string): ReadyRequest;
  body(value: Uint8Array): ReadyRequest;
  build(): Readonly<{
    url: URL;
    method: 'GET' | 'POST';
    headers: Headers;
    body?: Uint8Array;
  }>;
}

request().build() does not compile because NeedsUrl lacks build. After url, the caller must choose a method; after that, optional fields can be added in any order. Separate interfaces keep the surface readable and work in a language without linear ownership because each stage can be an immutable closure over accumulated values.

This design has limits. If five required fields may be supplied in any order, encoding every subset creates up to $2^5$ static states. For large configuration objects, a runtime schema and one validation result are often clearer. Typestate is best when the protocol is sequential or has a small number of meaningful phases, not when it turns arbitrary field presence into a combinatorial API.

Builders also show an ergonomics principle: use types to guide the next action. Meaningful method availability and editor completion are often more valuable than an elaborate compile-time error. State names should use domain vocabulary, and transitions should return errors that preserve resources when recovery is expected.

Cross Dynamic Boundaries Deliberately #

Stored rows, HTTP payloads, queue messages, and user input do not arrive as trusted Upload<Verified> values. They arrive as bytes plus claims. Deserialization must first produce a dynamic representation, validate both the status and its state-specific fields, then construct the corresponding typestate value through controlled constructors.

decodeUpload(row) -> Result<AnyUpload, CorruptRecord>

AnyUpload =
  | CreatedUpload(Upload<Created>)
  | ReceivingUpload(Upload<Receiving>)
  | VerifiedUpload(Upload<Verified>)
  | PublishedUpload(Upload<Published>)
  | AbortedUpload(Upload<Aborted>)

A worker that accepts only verified jobs pattern-matches the dynamic wrapper and passes Upload<Verified> into its static core. It must reject or route other states. Never cast a status string into a phantom parameter; that converts untrusted metadata directly into false proof.

Long-running protocols often span deployments, so old binaries may encounter newly introduced states. Include a schema or protocol version, define unknown-state behavior, and evolve transitions compatibly. Removing a transition may strand durable records that were legal under the previous version. Adding a state can break exhaustive dynamic consumers even if state-specific functions remain valid.

Escape hatches should be explicit. Administrative recovery may need to force an upload from Receiving to Aborted. Model that as a privileged operation with an audit reason and runtime checks, not a public constructor for arbitrary states. The escape is then searchable and reviewable.

Balance Safety Against API Size and Change #

Typestate can eliminate invalid local sequences, improve completion, remove repeated status checks, and attach state-specific data without nullable fields. It is especially valuable for resource lifecycles, cryptographic handshakes, transactions, parsers, workflow stages, and builders with ordered requirements.

The costs are real. Every public state and transition expands the API. Generic error messages can become difficult to read. Returning different types complicates storage in homogeneous collections. Branches that converge may need an enum wrapper or a shared interface. Protocol evolution can force callers to handle a new state or transition result.

Common failure modes include:

• Encoding labels without restricting methods, which creates decorative phantom types.
• Mutating one aliased object and casting it to a new state, leaving stale handles alive.
• Assuming a static transition also made an external side effect atomic or durable.
• Creating a type for every runtime counter, producing state explosion.
• Hiding recovery ownership in exceptions, so callers cannot know whether retry is legal.
• Offering unchecked constructors that let any caller manufacture trusted terminal states.
• Omitting runtime validation at serialization, FFI, reflection, or database boundaries.

Sometimes a runtime state machine is the better design: workflows loaded from configuration, protocols whose states change frequently, systems dominated by cross-process messages, or user interfaces that must display arbitrary persisted states. A validated enum plus a central transition function can be simpler and more observable. Typestate can still protect a small stable inner resource protocol while the outer workflow remains dynamic.

Verify the Transition Graph and Operational Invariants #

Compile-fail tests are first-class typestate tests. Keep small examples that must be rejected: append before begin, publish before verify, use after finish, double publish, and a borrowed cursor outliving its transaction. Positive compile tests cover every legal path and recovery branch. These tests protect API shape when refactoring changes method placement or generic bounds.

Runtime tests verify what types cannot. For the upload example:

1. Generate chunk sequences and assert recorded offsets are contiguous.
2. Corrupt size or digest and confirm finish never constructs Verified.
3. Inject storage failure before and after publication, then verify retry is idempotent.
4. Reload every durable state and validate all state-specific required fields.
5. Race duplicate workers and prove the persistence transition admits only one publisher.
6. Exercise privileged recovery and require an audit record with the prior state and reason.

Model-based testing can use the original transition table as an oracle. Generate operation sequences, run them against a dynamic test adapter, and assert that defined transitions succeed while undefined transitions are rejected without corrupting state. The static API makes many illegal sequences impossible to express normally, but model tests remain useful for wire endpoints, reflection, and persistence code that accepts dynamic operations.

Operationally, record transition attempts with protocol version, source state, target state, outcome, and stable resource ID. Alert on records stuck beyond expected age, repeated failed transitions, and impossible state-field combinations discovered by audits. Reconciliation should operate through explicit recovery transitions instead of rewriting status fields directly.

Typestate is therefore not a replacement for a state machine. It is a way to project a stable state machine into the type checker so ordinary code can express only its legal paths. When ownership preserves that projection and runtime boundaries reconstruct it honestly, the protocol becomes easier to use correctly and harder to violate accidentally.