Low-level designCore9 min

State machines

Describe an object's lifecycle as states, events and the transitions between them, and keep the transitions in a table. A table shows the whole policy in one place, changes by a row, and suits many states with simple rules better than a class per state.

Watch it evolve1 / 9

The problem

A hold moves through its states

Each state is a class that accepts some events and names the next state. OnShelf checks the 7-day window.

Start

Stage 1

Stage 2

Final

1 · The situation

A library hold and its lifecycle

A library lets patrons put a hold on a book at another branch. A hold is Requested, then In transit once the branch ships the book, then On shelf when it arrives. The patron has 7 days to pick it up; after that the hold expires. Until it's on the shelf, the patron can cancel.

The first version uses the State pattern from the page before: a HoldState base class that refuses every event, and a class per state that overrides what it accepts. OnShelf checks the 7 days itself, and the three end states share one Closed class with a name. Python writes pick_up() and days_on_shelf().

The first versionJava

abstract class HoldState {
    abstract String name();

    boolean ship(Hold h) {
        return false;
    }

    boolean arrive(Hold h) {
        return false;
    }

    boolean pickUp(Hold h) {
        return false;
    }

    boolean expire(Hold h) {
        return false;
    }

    boolean cancel(Hold h) {
        return false;
    }
}

class Requested extends HoldState {
    String name() {
        return "Requested";
    }

    @Override
    boolean ship(Hold h) {
        h.moveTo(new InTransit());
        return true;
    }

    @Override
    boolean cancel(Hold h) {
        h.moveTo(new Closed("Canceled"));
        return true;
    }
}

class InTransit extends HoldState {
    String name() {
        return "In transit";
    }

    @Override
    boolean arrive(Hold h) {
        h.moveTo(new OnShelf());
        return true;
    }

    @Override
    boolean cancel(Hold h) {
        h.moveTo(new Closed("Canceled"));
        return true;
    }
}

class OnShelf extends HoldState {
    String name() {
        return "On shelf";
    }

    @Override
    boolean pickUp(Hold h) {
        if (h.daysOnShelf() > 7) return false;
        h.moveTo(new Closed("Picked up"));
        return true;
    }

    @Override
    boolean expire(Hold h) {
        if (h.daysOnShelf() <= 7) return false;
        h.moveTo(new Closed("Expired"));
        return true;
    }
}

class Closed extends HoldState {
    private final String name;

    Closed(String name) {
        this.name = name;
    }

    String name() {
        return name;
    }
}

class Hold {
    private final String patron;
    private HoldState state = new Requested();
    private int daysOnShelf;

    Hold(String patron) {
        this.patron = patron;
    }

    void moveTo(HoldState next) {
        state = next;
    }

    void waitDays(int days) {
        daysOnShelf += days;
    }

    int daysOnShelf() {
        return daysOnShelf;
    }

    String patron() {
        return patron;
    }

    String status() {
        return state.name();
    }

    boolean ship() {
        return state.ship(this);
    }

    boolean arrive() {
        return state.arrive(this);
    }

    boolean pickUp() {
        return state.pickUp(this);
    }

    boolean expire() {
        return state.expire(this);
    }

    boolean cancel() {
        return state.cancel(this);
    }
}

public class Main {
    static void report(Hold h, String event, boolean accepted) {
        String result = accepted ? "-> " + h.status() : "refused, still " + h.status();
        System.out.println(h.patron() + ": " + event + " " + result);
    }

    public static void main(String[] args) {
        Hold ana = new Hold("Ana");
        report(ana, "ship", ana.ship());
        report(ana, "arrive", ana.arrive());
        ana.waitDays(3);
        report(ana, "pick up", ana.pickUp());

        Hold ben = new Hold("Ben");
        report(ben, "ship", ben.ship());
        report(ben, "cancel", ben.cancel());

        Hold cai = new Hold("Cai");
        report(cai, "ship", cai.ship());
        report(cai, "arrive", cai.arrive());
        cai.waitDays(9);
        report(cai, "pick up", cai.pickUp());
        report(cai, "expire", cai.expire());
    }
}

The class diagram of this version, drawn from its code: a class per state, each naming the states it leads to.

Three holds: Ana's is picked up, Ben cancels his, and Cai comes too late:

Ana: ship -> In transit
Ana: arrive -> On shelf
Ana: pick up -> Picked up
Ben: ship -> In transit
Ben: cancel -> Canceled
Cai: ship -> In transit
Cai: arrive -> On shelf
Cai: pick up refused, still On shelf
Cai: expire -> Expired

2 · The change

The rules change, and staff want to read them

The circulation staff own the hold policy, and it changes a few times a year. This year they want patrons to be able to cancel while the book waits on the shelf, and they want the help page to list every rule. Neither is easy when the policy is spread through classes:

One state's piece of the policyJava

class OnShelf extends HoldState {
    String name() {
        return "On shelf";
    }

    @Override
    boolean pickUp(Hold h) {
        if (h.daysOnShelf() > 7) return false;
        h.moveTo(new Closed("Picked up"));
        return true;
    }

    @Override
    boolean expire(Hold h) {
        if (h.daysOnShelf() <= 7) return false;
        h.moveTo(new Closed("Expired"));
        return true;
    }
}

Question from staff	Where the answer is today
When can a patron cancel?	In `Requested` and `InTransit`, and implicitly not in the rest
How long is the pickup window?	Twice in `OnShelf`, as `> 7` and `<= 7`
Can we list every rule on the help page?	Only by reading every class
Allow cancel while on the shelf	A new method in `OnShelf`

Each state class here does almost nothing: it checks an event, maybe a condition, and names the next state. The behavior is thin and the rules are what matter, so the rules should be data you can read, print and change in one place.

3 · The refactor

Turn the classes into a table

Start from the first version. Replace the state classes with two enums and a list of transitions, each one row of the policy:

Status and Event are enums with display labels. A Transition is a row: from a status, on an event, to a status, with an optional guard, a condition on the days on the shelf, and its description. The guard takes only the days, not the whole hold: Hold already depends on the table, and a guard typed on Hold would make the two depend on each other. HoldRules.TABLE lists the six rules.

Java

record Transition(Status from, Event event, Status to, String when, IntPredicate guard) {
    boolean matches(Status current, Event e, int daysOnShelf) {
        return from == current && event == e && guard.test(daysOnShelf);
    }
}

The table version prints the same lines as the classes. The last version also prints the policy, and lets Dee cancel a book that's waiting for her:

Rules:
  Requested + ship -> In transit
  Requested + cancel -> Canceled
  In transit + arrive -> On shelf
  In transit + cancel -> Canceled
  On shelf + cancel -> Canceled
  On shelf + pick up -> Picked up (within 7 days)
  On shelf + expire -> Expired (after 7 days)
Ana: ship -> In transit
Ana: arrive -> On shelf
Ana: pick up -> Picked up
Ben: ship -> In transit
Ben: cancel -> Canceled
Cai: ship -> In transit
Cai: arrive -> On shelf
Cai: pick up refused, still On shelf
Cai: expire -> Expired
Dee: ship -> In transit
Dee: arrive -> On shelf
Dee: cancel -> Canceled

A class per state: 5
One table: 1

Places to read to see the whole hold policy: four state classes and the base class, or one table.

4 · The technique

States, events, transitions and guards

A state machine describes an object as being in exactly one of a set of states. Events arrive, and a transition says: in this state, on this event, move to that state. A guard is a condition that must hold for the transition to fire, such as "within 7 days". A transition table lists the transitions as data, and the object looks up its next state in it.

The hold policy as a state diagram. Every arrow is one row of the table.

The table in the code and the diagram say the same thing. The code's table is one-dimensional, a list of rows. Another common form is a grid with the states down the side, the events across the top, and the next state in each cell; it shows at a glance which events a state ignores.

The end states, Picked up, Expired and Canceled, have no rows: every event there is refused. Deciding what an unlisted event means, refuse it quietly or report an error, is part of the design.

5 · What it costs

When classes beat a table

A table holds rules, not behavior. If entering a state means sending an email, charging a fine and updating a catalog, that work needs a home. A table can name an action per row, but rich per-state behavior is easier to read in a State class.
The compiler checks less. Two rows can match the same state and event, or a state can become unreachable, and nothing complains. Tests and a small validation at startup have to catch it.
Guards hide logic in small functions. Many complex guards make a table as hard to read as the classes it replaced.

Situation	Better fit
Many states and events, little behavior per transition	A transition table
A few states, each with rich behavior of its own	The State pattern
The rules change often, or must be shown to or edited by non-programmers	A table, possibly loaded from configuration
Dozens of states sharing transitions, such as cancel from anywhere	Hierarchical states, from a state machine library or UML

6 · Getting it right

Treat the table as the policy

Validate the table. At startup, check that no two rows can fire for the same state and event together, and that every state can be reached.
Test by row. Each row is a rule: one test per row, plus the refusals, covers the policy.
Funnel every change through fire(). One method changes the status, so it's the place to log transitions or record their history.

Keep guards about the object's data. Here guards read the days on the shelf. Guards that call out to services make the machine hard to test and hard to reason about.
Watch for state explosion. If every state needs the same cancel row, a parent state that all of them inherit from removes the repetition; that's what hierarchical state machines add.

Language	The usual table
Java	Enums for states and events, a record per row, `IntPredicate` or `Predicate` guards
C++	`enum class` states and events, a struct per row with a `std::function` guard
JavaScript	Frozen objects for states and events, an array of row objects with function guards
Python	`Enum` classes, a frozen dataclass per row, lambdas as guards

7 · Look-alikes

Four ways to write the same machine

A switch on an enum, the State pattern and a table all implement a state machine. What differs is where the rules live:

Approach	Where the rules live	Good when
Switch on an enum	In every method that handles an event	Two or three states that rarely change
State pattern	In a class per state	Each state has real behavior of its own
Transition table	In one list of rows	Many states, simple rules, rules that change or must be shown
Workflow engine	In a definition file, run by a library	Long-running processes with people and timeouts in them

The approaches mix: a table can name an action per row, and a State class can look up its transitions in a table. Choose by where you'd rather read the rules.

8 · In practice

Machines in the practice problems

The vending-machine practice problem is a small state machine: two states, idle and has money, and three events, a coin, a pick and a cancel. With two states and three events, either form works. Its reference design uses State classes, so that an out-of-service state is one new class; the states stay thin and the machine keeps the money. A table would also work, with one row per accepted event.

The practice checks recognize the State pattern, as in this page's first version, but have no notion of a transition table; the table versions read as plain, clean classes. Fix the vending machine, and decide which form its rules should take.

Check yourself

4 questions

1. The library adds a "Lost" status: a hold in transit can be marked lost. What changes in the table version?

2. Two rows match the same status and event, with guards that are both true. What happens?

3. Entering On shelf must now email the patron, update the catalog and start a fine timer. Which approach suits that best?

4. Why did the table version pass the guard the days on the shelf rather than the whole hold?

Takeaways

Remember this

A state machine is a set of states, the events that move between them, and guards on those moves.
A transition table lists the moves as rows: from, event, to, guard.
A table shows the whole policy in one place, and a new rule is a new row.
Use a table for many states with simple rules, and State classes when each state has real behavior.
Validate the table: overlapping rows and unreachable states are easy to miss.