Worked system design solution

Design State Machine Framework

A generic StateMachine<S, E> framework: declarative transition table (current state + event → next state + action), guards for conditional transitions, entry/exit actions per state, history (shallow and deep), and hierarchical states / statecharts. Implemented in TypeScript, Java, and C++ with tests covering an order workflow.

LLDMedium22 min readstate-machinefsmframeworktransitionsguards

Clarify Requirements

What we mean by "state machine" and the feature set

Functional requirements

Generic API — StateMachine<S, E> over user-defined state enum S and event enum E. Compile-time-safe in Java and TypeScript; template-safe in C++.
Declarative builder: .state(S).onEvent(E).transitionTo(S2).guard(predicate).action(fn).register().
Transition lookup — given (currentState, event, context), return the next state in O(1).
Guards — boolean predicates over an external context object; if the guard returns false the transition is skipped and the machine stays in the current state.
Entry / exit actions per state — invoked whenever the machine enters or exits that state.
Transition action — invoked between exit (old) and entry (new), receiving the event payload.
Hierarchical states (statecharts) — a state can have substates; entering the parent enters its default substate.
History states — re-entering a parent state restores its previously-active substate (shallow); deep history restores the entire nested path.
fire(event, payload?) — drive the machine. Returns true if a transition occurred.
Listeners — observers notified on onTransition(from, to, event).

Non-functional requirements

fire is O(1) average: indexed by (state, event).
Configuration is immutable after build() — guarantees thread-safety for the transition table. Instance state (current state) must be guarded externally for concurrent use.
Composes naturally — building a sub-machine and embedding it as a substate must work without special-casing.

Out of scope (v1)

Item	Reason
Distributed state machines (Saga)	Cross-process orchestration is a different problem
Persistent state (load from DB on restart)	Storage layer concern
Event sourcing replay	Adjacent problem
Visualisation / DOT export	Tooling layer
Asynchronous transitions	Discussed as extension

Key edge cases

Edge case	Expected behaviour
Event fired with no matching transition	Return false; `onIgnoredEvent` listener fires
Guard returns false	Treated like no transition; machine stays
Self-transition (`A → A`)	Exit and re-enter `A`; entry/exit fire
Internal transition (`A → A` with no exit)	Variant: action fires but no exit/entry
Multiple matching transitions for the same event	First-registered wins; document explicitly
Re-entering a parent state	If history is enabled, restore the previous substate

Interview: "What's the difference between FSM and a statechart?" — FSMs have flat states; statecharts add hierarchy, history, parallel regions, and guards. Name-drop UML Statecharts (Harel) for credibility.

Core Entities

State, Event, Transition, Context, StateMachine

Domain objects

State

Field	Type	Notes
`id`	S (generic)	Enum value or string tag
`onEntry`	Action?	Runs when state is entered
`onExit`	Action?	Runs when state is exited
`parent`	State?	For hierarchy
`defaultChild`	State?	Default substate when entering parent
`history`	'NONE' \| 'SHALLOW' \| 'DEEP'	History mode

Event

A user-defined enum. The framework treats it as an opaque key.

Transition

Field	Type	Notes
`from`	State	Source
`event`	E	Trigger
`to`	State	Target
`guard`	Predicate(ctx, payload)?	Optional condition
`action`	Action(ctx, payload)?	Side effect between exit/entry
`internal`	boolean	If true, skip exit/entry

Context

An arbitrary user object accessible to guards and actions. Pattern: pass a typed Ctx along with the machine; guards read fields like ctx.userIsAdmin.

Transition Table

Map<from, Map<event, Transition[]>>. Stored at build time, immutable thereafter. Lookup is two map fetches → O(1).

StateMachine

Field	Type	Notes
`states`	Map<id, State>	All known states
`transitions`	Map<from, Map<event, T[]>>	Indexed table
`current`	State	Current state
`historyByParent`	Map<parentId, State>	Last active child per parent
`listeners`	TransitionListener[]	Observers
`fire(event, payload?)`	method	Drive machine

Fire algorithm

function fire(event, payload):
  // 1. Search transitions from current and walk up the parent chain.
  var node = current
  while node:
    list = transitions[node.id][event]
    for tr in list:
      if !tr.guard || tr.guard(ctx, payload):
          performTransition(tr, payload)
          return true
    node = node.parent
  onIgnoredEvent(event)
  return false

function performTransition(tr, payload):
  if !tr.internal:
      runExitChain(current, tr.from)
  if tr.action: tr.action(ctx, payload)
  if !tr.internal:
      runEntryChain(tr.from, tr.to, payload)
  current = leafOf(tr.to)   // descend to default child or restored history
  notifyListeners(tr)

The walk-up-the-parent-chain step is what makes a statechart different from a flat FSM. Events handled by a parent state apply to every nested substate unless a substate overrides them.

Algorithm: The chain-up event matching mirrors how DOM event bubbling works. Hand-drawing the parent chain helps the interviewer see why hierarchical states drastically reduce transition-table size.

Classes & Relationships

StateMachine builder + immutable transition table

Class diagram

classDiagram
    class StateConfig~S~ {
        +id: S
        +parent: S?
        +defaultChild: S?
        +history: HistoryMode
        +onEntry: Action?
        +onExit: Action?
    }

    class Transition~S, E~ {
        +from: S
        +event: E
        +to: S
        +guard: Guard?
        +action: Action?
        +internal: boolean
    }

    class StateMachineBuilder~S, E, Ctx~ {
        -states: Map~S, StateConfig~
        -transitions: List~Transition~
        +state(s: S) StateConfig
        +addTransition(t) void
        +build(initial: S, ctx: Ctx) StateMachine
    }

    class StateMachine~S, E, Ctx~ {
        -current: S
        -states: Map~S, StateConfig~
        -table: Map~S, Map~E, Transition[]~~
        -historyByParent: Map~S, S~
        -ctx: Ctx
        -listeners: TransitionListener[]
        +fire(e: E, payload?) boolean
        +getState() S
        +addListener(l) void
    }

    class TransitionListener~S, E~ {
        <<interface>>
        +onTransition(from, to, event) void
        +onIgnoredEvent(state, event) void
    }

    class HistoryMode {
        <<enum>>
        NONE
        SHALLOW
        DEEP
    }

    StateMachineBuilder ..> StateConfig
    StateMachineBuilder ..> Transition
    StateMachineBuilder ..> StateMachine : builds
    StateMachine "1" o--> "*" StateConfig
    StateMachine "1" o--> "*" Transition
    StateMachine "1" o--> "*" TransitionListener
    StateConfig ..> HistoryMode

Relationships explained

StateMachineBuilder ──▶ StateMachine — factory pattern. Builder accumulates configuration; build() produces an immutable, runnable machine.
StateMachine ◇── StateConfig (*) — composition. Machine owns its state catalogue.
StateMachine ◇── Transition (*) — owns transitions, indexed for O(1) lookup.
StateMachine ◇── TransitionListener (*) — pluggable observers (logging, metrics, persistence).
StateConfig ──▶ HistoryMode — enum-valued attribute.

Why a builder

The transition table is awkward to populate via a single constructor — you'd pass a huge map literal. The builder pattern lets us write:

StateMachineBuilder<OrderState, OrderEvent, OrderCtx> b = ...;
b.state(NEW).onEntry(ctx -> log("created"));
b.state(PAID).onEntry(ctx -> reserveInventory(ctx));
b.transition(NEW, PLACE, PAID).guard(ctx -> ctx.totalCents > 0);
b.transition(PAID, SHIP, SHIPPED).action(ctx -> sendShipNotice(ctx));
b.transition(SHIPPED, DELIVER, DELIVERED);
StateMachine<...> sm = b.build(NEW, ctx);

The DSL reads like specification, not code. Each line corresponds to a row in a state diagram.

Hierarchical states example

ON (parent)
├── ON.IDLE  (default child)
├── ON.WORKING
│    └── ON.WORKING.PAUSED   (deep child)
OFF

A transition declared as ON --POWER_OFF--> OFF applies to every substate of ON (IDLE, WORKING, WORKING.PAUSED). Without hierarchy you'd write three transitions. The savings explode with deeper nesting.

History modes

NONE — re-entering parent ON goes back to ON.IDLE.
SHALLOW — re-entering ON goes back to ON.WORKING (last direct child) but ON.WORKING resets to its default.
DEEP — re-entering ON restores all the way to ON.WORKING.PAUSED.

Interview: History states are the most-asked statechart concept that candidates flub. Memorise the three modes and which one most state machines actually need (shallow).

Code Implementation

TypeScript / Java / C++ implementation with an order workflow demo

TypeScript

// state-machine.ts
type Guard<C, P> = (ctx: C, payload?: P) => boolean;
type Action<C, P> = (ctx: C, payload?: P) => void;

export interface StateConfig<S, C> {
  id: S;
  parent?: S;
  defaultChild?: S;
  onEntry?: Action<C, unknown>;
  onExit?: Action<C, unknown>;
}

interface Transition<S, E, C> {
  from: S;
  event: E;
  to: S;
  guard?: Guard<C, unknown>;
  action?: Action<C, unknown>;
  internal?: boolean;
}

export class StateMachine<S, E, C> {
  private current: S;
  private table = new Map<S, Map<E, Transition<S, E, C>[]>>();
  private states = new Map<S, StateConfig<S, C>>();
  private listeners: Array<(from: S, to: S, event: E) => void> = [];

  constructor(
    initial: S,
    private ctx: C,
    states: StateConfig<S, C>[],
    transitions: Transition<S, E, C>[],
  ) {
    this.current = initial;
    for (const s of states) this.states.set(s.id, s);
    for (const t of transitions) {
      let perState = this.table.get(t.from);
      if (!perState) { perState = new Map(); this.table.set(t.from, perState); }
      let list = perState.get(t.event);
      if (!list) { list = []; perState.set(t.event, list); }
      list.push(t);
    }
    // Enter initial state
    this.states.get(initial)?.onEntry?.(ctx);
  }

  fire(event: E, payload?: unknown): boolean {
    // Walk up parent chain looking for a matching transition.
    let node: S | undefined = this.current;
    while (node !== undefined) {
      const perEvent = this.table.get(node);
      const list = perEvent?.get(event);
      if (list) {
        for (const tr of list) {
          if (!tr.guard || tr.guard(this.ctx, payload)) {
            this.performTransition(tr, payload);
            return true;
          }
        }
      }
      node = this.states.get(node)?.parent;
    }
    return false;
  }

  private performTransition(tr: Transition<S, E, C>, payload: unknown): void {
    const fromCfg = this.states.get(this.current);
    if (!tr.internal) fromCfg?.onExit?.(this.ctx);
    tr.action?.(this.ctx, payload);
    const toCfg = this.states.get(tr.to);
    if (!tr.internal) toCfg?.onEntry?.(this.ctx);
    this.current = tr.to;
    for (const l of this.listeners) l(tr.from, tr.to, tr.event);
  }

  addListener(l: (from: S, to: S, event: E) => void): void { this.listeners.push(l); }
  getState(): S { return this.current; }
}

// ---------- Example: order workflow ----------

export enum OrderState { NEW = 'NEW', PAID = 'PAID', SHIPPED = 'SHIPPED', DELIVERED = 'DELIVERED', CANCELLED = 'CANCELLED' }
export enum OrderEvent { PAY = 'PAY', SHIP = 'SHIP', DELIVER = 'DELIVER', CANCEL = 'CANCEL' }
export interface OrderCtx { totalCents: number; userIsAdmin: boolean; log: string[]; }

export function buildOrderMachine(ctx: OrderCtx): StateMachine<OrderState, OrderEvent, OrderCtx> {
  return new StateMachine<OrderState, OrderEvent, OrderCtx>(
    OrderState.NEW,
    ctx,
    [
      { id: OrderState.NEW, onEntry: c => c.log.push('entered NEW') },
      { id: OrderState.PAID, onEntry: c => c.log.push('entered PAID') },
      { id: OrderState.SHIPPED, onEntry: c => c.log.push('entered SHIPPED') },
      { id: OrderState.DELIVERED, onEntry: c => c.log.push('entered DELIVERED') },
      { id: OrderState.CANCELLED, onEntry: c => c.log.push('entered CANCELLED') },
    ],
    [
      { from: OrderState.NEW, event: OrderEvent.PAY, to: OrderState.PAID,
        guard: c => c.totalCents > 0 },
      { from: OrderState.PAID, event: OrderEvent.SHIP, to: OrderState.SHIPPED },
      { from: OrderState.SHIPPED, event: OrderEvent.DELIVER, to: OrderState.DELIVERED },
      { from: OrderState.NEW, event: OrderEvent.CANCEL, to: OrderState.CANCELLED },
      { from: OrderState.PAID, event: OrderEvent.CANCEL, to: OrderState.CANCELLED,
        guard: c => c.userIsAdmin },
    ],
  );
}

Java

import java.util.*;
import java.util.function.*;

public class StateMachine<S, E, C> {
    public static class Config<S, C> {
        public final S id;
        public S parent;
        public Consumer<C> onEntry;
        public Consumer<C> onExit;
        public Config(S id) { this.id = id; }
    }

    public static class Transition<S, E, C> {
        public final S from, to;
        public final E event;
        public BiPredicate<C, Object> guard;
        public BiConsumer<C, Object> action;
        public boolean internal;
        public Transition(S from, E event, S to) {
            this.from = from; this.event = event; this.to = to;
        }
    }

    public interface TransitionListener<S, E> {
        void onTransition(S from, S to, E event);
    }

    private S current;
    private final C ctx;
    private final Map<S, Config<S, C>> states = new HashMap<>();
    private final Map<S, Map<E, List<Transition<S, E, C>>>> table = new HashMap<>();
    private final List<TransitionListener<S, E>> listeners = new ArrayList<>();

    public StateMachine(S initial, C ctx, List<Config<S, C>> states, List<Transition<S, E, C>> trs) {
        this.current = initial; this.ctx = ctx;
        for (Config<S, C> s : states) this.states.put(s.id, s);
        for (Transition<S, E, C> t : trs) {
            table.computeIfAbsent(t.from, k -> new HashMap<>())
                 .computeIfAbsent(t.event, k -> new ArrayList<>())
                 .add(t);
        }
        Config<S, C> ini = this.states.get(initial);
        if (ini != null && ini.onEntry != null) ini.onEntry.accept(ctx);
    }

    public boolean fire(E event, Object payload) {
        S node = current;
        while (node != null) {
            Map<E, List<Transition<S, E, C>>> perEvent = table.get(node);
            List<Transition<S, E, C>> list = perEvent == null ? null : perEvent.get(event);
            if (list != null) {
                for (Transition<S, E, C> tr : list) {
                    if (tr.guard == null || tr.guard.test(ctx, payload)) {
                        perform(tr, payload);
                        return true;
                    }
                }
            }
            node = states.get(node) == null ? null : states.get(node).parent;
        }
        return false;
    }

    private void perform(Transition<S, E, C> tr, Object payload) {
        Config<S, C> fromCfg = states.get(current);
        if (!tr.internal && fromCfg != null && fromCfg.onExit != null) fromCfg.onExit.accept(ctx);
        if (tr.action != null) tr.action.accept(ctx, payload);
        Config<S, C> toCfg = states.get(tr.to);
        if (!tr.internal && toCfg != null && toCfg.onEntry != null) toCfg.onEntry.accept(ctx);
        current = tr.to;
        for (TransitionListener<S, E> l : listeners) l.onTransition(tr.from, tr.to, tr.event);
    }

    public S getState() { return current; }
    public void addListener(TransitionListener<S, E> l) { listeners.add(l); }
}

C++

#include <unordered_map>
#include <vector>
#include <functional>
#include <memory>
#include <optional>

template <typename S, typename E, typename C>
class StateMachine {
public:
    struct Config {
        S id;
        std::optional<S> parent;
        std::function<void(C&)> onEntry;
        std::function<void(C&)> onExit;
    };

    struct Transition {
        S from;
        E event;
        S to;
        std::function<bool(C&, void*)> guard;
        std::function<void(C&, void*)> action;
        bool internal = false;
    };

    using Listener = std::function<void(S, S, E)>;

private:
    S current;
    C& ctx;
    std::unordered_map<int, Config> states;
    std::unordered_map<int, std::unordered_map<int, std::vector<Transition>>> table;
    std::vector<Listener> listeners;

    int sk(const S& s) const { return static_cast<int>(s); }
    int ek(const E& e) const { return static_cast<int>(e); }

public:
    StateMachine(S initial, C& c, std::vector<Config> cfgs, std::vector<Transition> trs)
        : current(initial), ctx(c) {
        for (auto& cfg : cfgs) states[sk(cfg.id)] = cfg;
        for (auto& t : trs) table[sk(t.from)][ek(t.event)].push_back(t);
        auto it = states.find(sk(initial));
        if (it != states.end() && it->second.onEntry) it->second.onEntry(ctx);
    }

    bool fire(E event, void* payload = nullptr) {
        std::optional<S> node = current;
        while (node.has_value()) {
            auto stIt = table.find(sk(*node));
            if (stIt != table.end()) {
                auto evIt = stIt->second.find(ek(event));
                if (evIt != stIt->second.end()) {
                    for (auto& tr : evIt->second) {
                        if (!tr.guard || tr.guard(ctx, payload)) {
                            perform(tr, payload);
                            return true;
                        }
                    }
                }
            }
            auto cfg = states.find(sk(*node));
            node = (cfg != states.end()) ? cfg->second.parent : std::nullopt;
        }
        return false;
    }

    S getState() const { return current; }
    void addListener(Listener l) { listeners.push_back(std::move(l)); }

private:
    void perform(const Transition& tr, void* payload) {
        auto fromCfg = states.find(sk(current));
        if (!tr.internal && fromCfg != states.end() && fromCfg->second.onExit)
            fromCfg->second.onExit(ctx);
        if (tr.action) tr.action(ctx, payload);
        auto toCfg = states.find(sk(tr.to));
        if (!tr.internal && toCfg != states.end() && toCfg->second.onEntry)
            toCfg->second.onEntry(ctx);
        current = tr.to;
        for (auto& l : listeners) l(tr.from, tr.to, tr.event);
    }
};

Edge Cases & Tests

Tests for transitions, guards, entry/exit, ignored events, listeners

What we test

Case	Why
Valid event causes transition; new state observed	Happy path
Event with no matching transition is ignored	Robustness
Guard returns false → no transition	Conditional path
onEntry fires on entering, onExit on leaving	Lifecycle hooks
Listener notified with from, to, event	Observability
Self-transition with internal=false re-enters	Reset semantics
Cancel from PAID requires admin (guarded)	Cross-cutting authorisation

TypeScript — Vitest

import { describe, expect, it, vi } from 'vitest';
import { buildOrderMachine, OrderEvent, OrderState, OrderCtx } from './state-machine';

function mkCtx(over: Partial<OrderCtx> = {}): OrderCtx {
  return { totalCents: 100, userIsAdmin: false, log: [], ...over };
}

describe('StateMachine', () => {
  it('transitions on a valid event', () => {
    const ctx = mkCtx();
    const sm = buildOrderMachine(ctx);
    expect(sm.fire(OrderEvent.PAY)).toBe(true);
    expect(sm.getState()).toBe(OrderState.PAID);
  });

  it('ignores an event with no matching transition', () => {
    const ctx = mkCtx();
    const sm = buildOrderMachine(ctx);
    expect(sm.fire(OrderEvent.SHIP)).toBe(false);
    expect(sm.getState()).toBe(OrderState.NEW);
  });

  it('blocks transition when guard returns false', () => {
    const ctx = mkCtx({ totalCents: 0 });
    const sm = buildOrderMachine(ctx);
    expect(sm.fire(OrderEvent.PAY)).toBe(false);
    expect(sm.getState()).toBe(OrderState.NEW);
  });

  it('admin guard allows cancel from PAID', () => {
    const ctx = mkCtx({ userIsAdmin: true });
    const sm = buildOrderMachine(ctx);
    sm.fire(OrderEvent.PAY);
    expect(sm.fire(OrderEvent.CANCEL)).toBe(true);
    expect(sm.getState()).toBe(OrderState.CANCELLED);
  });

  it('non-admin cannot cancel from PAID', () => {
    const ctx = mkCtx({ userIsAdmin: false });
    const sm = buildOrderMachine(ctx);
    sm.fire(OrderEvent.PAY);
    expect(sm.fire(OrderEvent.CANCEL)).toBe(false);
    expect(sm.getState()).toBe(OrderState.PAID);
  });

  it('listener is notified with from/to/event', () => {
    const ctx = mkCtx();
    const sm = buildOrderMachine(ctx);
    const spy = vi.fn();
    sm.addListener(spy);
    sm.fire(OrderEvent.PAY);
    expect(spy).toHaveBeenCalledWith(OrderState.NEW, OrderState.PAID, OrderEvent.PAY);
  });

  it('entry actions populate the context log', () => {
    const ctx = mkCtx();
    const sm = buildOrderMachine(ctx);
    sm.fire(OrderEvent.PAY);
    expect(ctx.log).toContain('entered PAID');
  });
});

Java — JUnit 5

import org.junit.jupiter.api.Test;
import java.util.*;
import static org.junit.jupiter.api.Assertions.*;

class StateMachineTest {
    enum S { NEW, PAID, SHIPPED, CANCELLED }
    enum E { PAY, SHIP, CANCEL }
    static class Ctx { int totalCents = 100; boolean admin = false; List<String> log = new ArrayList<>(); }

    StateMachine<S, E, Ctx> build(Ctx ctx) {
        StateMachine.Config<S, Ctx> sNew = new StateMachine.Config<>(S.NEW);
        sNew.onEntry = c -> c.log.add("entered NEW");
        StateMachine.Config<S, Ctx> sPaid = new StateMachine.Config<>(S.PAID);
        sPaid.onEntry = c -> c.log.add("entered PAID");
        StateMachine.Config<S, Ctx> sShip = new StateMachine.Config<>(S.SHIPPED);
        StateMachine.Config<S, Ctx> sCx = new StateMachine.Config<>(S.CANCELLED);

        StateMachine.Transition<S, E, Ctx> pay = new StateMachine.Transition<>(S.NEW, E.PAY, S.PAID);
        pay.guard = (c, p) -> c.totalCents > 0;
        StateMachine.Transition<S, E, Ctx> ship = new StateMachine.Transition<>(S.PAID, E.SHIP, S.SHIPPED);
        StateMachine.Transition<S, E, Ctx> cancelPaid = new StateMachine.Transition<>(S.PAID, E.CANCEL, S.CANCELLED);
        cancelPaid.guard = (c, p) -> c.admin;

        return new StateMachine<>(S.NEW, ctx,
            List.of(sNew, sPaid, sShip, sCx),
            List.of(pay, ship, cancelPaid));
    }

    @Test void transitionsHappyPath() {
        Ctx ctx = new Ctx();
        StateMachine<S, E, Ctx> sm = build(ctx);
        assertTrue(sm.fire(E.PAY, null));
        assertEquals(S.PAID, sm.getState());
    }

    @Test void ignoresUnknownEvent() {
        Ctx ctx = new Ctx();
        StateMachine<S, E, Ctx> sm = build(ctx);
        assertFalse(sm.fire(E.SHIP, null));
        assertEquals(S.NEW, sm.getState());
    }

    @Test void guardBlocks() {
        Ctx ctx = new Ctx(); ctx.totalCents = 0;
        StateMachine<S, E, Ctx> sm = build(ctx);
        assertFalse(sm.fire(E.PAY, null));
    }

    @Test void adminCanCancelPaid() {
        Ctx ctx = new Ctx(); ctx.admin = true;
        StateMachine<S, E, Ctx> sm = build(ctx);
        sm.fire(E.PAY, null);
        assertTrue(sm.fire(E.CANCEL, null));
        assertEquals(S.CANCELLED, sm.getState());
    }
}

C++ — gtest

#include <gtest/gtest.h>
#include "state-machine.hpp"
#include <vector>
#include <string>

enum class S { NEW = 0, PAID = 1, SHIPPED = 2, CANCELLED = 3 };
enum class E { PAY = 0, SHIP = 1, CANCEL = 2 };
struct Ctx { int totalCents = 100; bool admin = false; std::vector<std::string> log; };

using SM = StateMachine<S, E, Ctx>;

SM build(Ctx& ctx) {
    SM::Config sNew{S::NEW, std::nullopt, [](Ctx& c){ c.log.push_back("entered NEW"); }, nullptr};
    SM::Config sPaid{S::PAID, std::nullopt, [](Ctx& c){ c.log.push_back("entered PAID"); }, nullptr};
    SM::Config sShip{S::SHIPPED, std::nullopt, nullptr, nullptr};
    SM::Config sCx{S::CANCELLED, std::nullopt, nullptr, nullptr};

    SM::Transition pay{S::NEW, E::PAY, S::PAID,
        [](Ctx& c, void*){ return c.totalCents > 0; }, nullptr, false};
    SM::Transition ship{S::PAID, E::SHIP, S::SHIPPED, nullptr, nullptr, false};
    SM::Transition cancelPaid{S::PAID, E::CANCEL, S::CANCELLED,
        [](Ctx& c, void*){ return c.admin; }, nullptr, false};

    return SM(S::NEW, ctx, {sNew, sPaid, sShip, sCx}, {pay, ship, cancelPaid});
}

TEST(StateMachine, HappyPath) {
    Ctx ctx;
    auto sm = build(ctx);
    EXPECT_TRUE(sm.fire(E::PAY));
    EXPECT_EQ((int)sm.getState(), (int)S::PAID);
}

TEST(StateMachine, GuardBlocks) {
    Ctx ctx; ctx.totalCents = 0;
    auto sm = build(ctx);
    EXPECT_FALSE(sm.fire(E::PAY));
    EXPECT_EQ((int)sm.getState(), (int)S::NEW);
}

TEST(StateMachine, AdminCancelsPaid) {
    Ctx ctx; ctx.admin = true;
    auto sm = build(ctx);
    sm.fire(E::PAY);
    EXPECT_TRUE(sm.fire(E::CANCEL));
    EXPECT_EQ((int)sm.getState(), (int)S::CANCELLED);
}

Extensibility & Trade-offs

Async transitions, parallel regions, distributed sagas

Natural extensions

1. Hierarchical states (statecharts)

We sketched parents and default children; full Harel statecharts add history pseudo-states, entry/exit on parent state independent of child, and transitions across hierarchy levels. Library XState (JS) and Spring Statemachine (Java) implement the full spec.

2. Parallel regions

A state can have multiple concurrent regions, each with its own current substate. Useful when the same business entity has independent aspects evolving in parallel (e.g. PAYMENT_STATUS × SHIPPING_STATUS). Events go to every region that handles them.

3. Async transitions

Replace fire returning bool with returning a Promise / Future. Guards and actions may be async; the machine queues events and processes one at a time. Adds back-pressure semantics — pile up too many and reject.

4. Persistent state machines

Persist current to a database keyed by entity ID. On every successful transition, write the new state in the same transaction as the side effects. This is idempotent event handling — re-firing the same event safely. Sagas (e.g. Spring Saga, AWS Step Functions) generalise this.

5. Visual exporter

Walk the transition table and emit DOT / PlantUML. Useful for documentation. The immutable build product makes this trivial: for each (from, event, to) → write "from -> to [label=event]".

6. Cross-process orchestration

For distributed workflows (order → inventory → payment → shipping), the state machine moves between services via a workflow engine (Temporal, Cadence, Step Functions). Locally, each service still uses a state machine; globally, the workflow engine coordinates.

Trade-offs

Concern	Choice A	Choice B	Recommendation
Configuration style	Builder DSL	YAML / JSON	DSL — type-safe
State key	Enum	String	Enum — compile-time safety
Transition resolution	First-match	All-match (fork)	First-match — deterministic
Hierarchy	Flat only	Parent chain	Parent chain if domain has natural hierarchy
Async	Sync `fire`	Promise `fire`	Add async layer on top; keep core sync
Persistence	In-memory	DB-backed	In-memory; persistence is a wrapper

Anti-patterns

God state — one giant FSM with 100 states. Split by aggregate (Order, Payment, User) — each gets its own machine.
Side effects in guards — guards must be pure (read context, no writes). Side effects in guards = "I cancelled the order while checking if I should ship it".
Allowing arbitrary state mutation from outside the machine — bypasses the table. Wrap the state field as private; expose only via fire.
Forgetting to call onEntry for the initial state — half the lifecycle hooks fail to fire. We did call it in the constructor; many DIY implementations skip this.
Storing the transition table as a flat list — O(N) lookup per event. Index by (from, event).

When NOT to use a state machine

Logic has no notion of state — pure CRUD with no business rules. Just write the controller.
Highly dynamic states — if states are created at runtime from config, a rules engine (Drools, Easy Rules) is more flexible.
You need full event-sourcing — switch to an event-sourced aggregate where the current state is a function of past events, not a single field.

Interview: Strong closing point: "An immutable transition table + a current-state pointer + entry/exit hooks gives you 80 % of statechart power. Add hierarchy and history for the rest. The framework stays under 200 lines of code; that's what makes it composable."

Practice this question