Statecharts

Deep dive

How it works

In: a chart (states, transitions, entry/exit actions, regions, history) and a stream of events · Out: the new set of active states plus the actions run · State: the configuration (active states) and each XOR state's recorded child · Cost: O(leaves x depth) per event with a scan; O(depth) per leaf with a table

Configuration = set of active states: root, plus for each active XOR state exactly one child, plus for each active AND state all children.

1. send(e) queues e. If a step is running, return: run-to-completion.
2. Pop the next event (internal queue first). For each active leaf walk up the ancestors; the first state with a transition on e fires. Inner states override outer ones, so a parent can define "stop" once for all its children.
3. For a transition src -> dst, find the lowest strict common ancestor L of both (external semantics: src is exited even if it is dst's ancestor).
4. Exit the child of L containing src: active descendants first, deepest first. Each XOR state records its active child (history).
5. Run the transition action (here: raise an event onto the internal queue).
6. Enter from the child of L containing dst down to dst, parents first. At an AND state enter every region (the path region continues down, the others start by default). Below dst: initial child, or the recorded child if the state has history.
7. Loop until both queues are empty.

Player (AND)
├─ Playback (XOR): Stopped ──play──► Running[H] ─┬─ Playing ⇄ pause
│                  Stopped ◄─stop/eof─ Running   └─ Paused
└─ Volume   (XOR): Unmuted ⇄ mute ⇄ Muted
play, pause, stop, play  =>  Paused again (history)      reset => both regions move

Transitions across regions are not allowed (the code asserts); use an event instead.

Code

use std::collections::VecDeque;

#[derive(Clone, Copy, PartialEq)]
pub enum Kind { Xor, And } // Xor: exactly one child active; And: all children (orthogonal regions)

pub struct State {
    name: &'static str, parent: Option<usize>, kind: Kind,
    kids: Vec<usize>, initial: usize, history: bool, last: Option<usize>,
}
pub struct Trans { src: usize, ev: &'static str, dst: usize, raise: Option<&'static str> }

#[derive(Default)]
pub struct Chart {
    s: Vec<State>, t: Vec<Trans>, active: Vec<bool>,
    internal: VecDeque<&'static str>, external: VecDeque<&'static str>,
    busy: bool, pub log: Vec<String>,
}

impl Chart {
    pub fn add(&mut self, name: &'static str, parent: Option<usize>, kind: Kind, history: bool) -> usize {
        let id = self.s.len();
        self.s.push(State { name, parent, kind, kids: vec![], initial: 0, history, last: None });
        self.active.push(false);
        if let Some(p) = parent {
            if self.s[p].kids.is_empty() { self.s[p].initial = id; } // first child = default
            self.s[p].kids.push(id);
        }
        id
    }
    pub fn on(&mut self, src: usize, ev: &'static str, dst: usize, raise: Option<&'static str>) {
        self.t.push(Trans { src, ev, dst, raise });
    }
    pub fn is(&self, name: &str) -> bool { (0..self.s.len()).any(|i| self.active[i] && self.s[i].name == name) }
    fn path(&self, mut n: usize) -> Vec<usize> { // root .. n
        let mut p = vec![n];
        while let Some(q) = self.s[n].parent { p.push(q); n = q; }
        p.reverse(); p
    }
    pub fn start(&mut self) { self.enter(0, &[]); }

    /// Queue an event; the loop runs to completion before the next event is looked at.
    pub fn send(&mut self, ev: &'static str) {
        self.external.push_back(ev);
        if self.busy { return; } // re-entrant call: just queue
        self.busy = true;
        while let Some(e) = self.internal.pop_front().or_else(|| self.external.pop_front()) { self.step(e); }
        self.busy = false;
    }
    fn step(&mut self, ev: &'static str) {
        let mut fire = vec![];
        for n in 0..self.s.len() {
            if !self.active[n] || !self.s[n].kids.is_empty() { continue; } // each active leaf
            let mut c = Some(n); // innermost enabled transition wins
            while let Some(x) = c {
                if let Some(i) = self.t.iter().position(|t| t.src == x && t.ev == ev) {
                    if !fire.contains(&i) { fire.push(i); }
                    break;
                }
                c = self.s[x].parent;
            }
        }
        for i in fire { // one per region; regions are disjoint so order is irrelevant
            let (src, dst, raise) = (self.t[i].src, self.t[i].dst, self.t[i].raise);
            if !self.active[src] { continue; }
            let (ps, pd) = (self.path(src), self.path(dst));
            let mut k = 1; // external transition: lowest strict common ancestor stays active
            while k + 1 < ps.len() && k + 1 < pd.len() && ps[k] == pd[k] { k += 1; }
            assert!(self.s[ps[k - 1]].kind == Kind::Xor, "no transitions across regions");
            self.exit(ps[k]);
            self.enter(pd[k], &pd[k + 1..]);
            if let Some(r) = raise { self.internal.push_back(r); } // handled after this step
        }
    }
    fn exit(&mut self, n: usize) { // children first
        for c in self.s[n].kids.clone() {
            if self.active[c] { if self.s[n].kind == Kind::Xor { self.s[n].last = Some(c); } self.exit(c); }
        }
        self.active[n] = false;
        self.log.push(format!("-{}", self.s[n].name));
    }
    fn enter(&mut self, n: usize, rest: &[usize]) { // parents first; rest = explicit path below n
        self.active[n] = true;
        self.log.push(format!("+{}", self.s[n].name));
        let kids = self.s[n].kids.clone();
        match self.s[n].kind {
            Kind::And => for c in kids {
                if rest.first() == Some(&c) { self.enter(c, &rest[1..]) } else { self.enter(c, &[]) }
            },
            Kind::Xor if !kids.is_empty() => match rest.first() {
                Some(&c) => self.enter(c, &rest[1..]),
                None => {
                    let st = &self.s[n];
                    let c = if st.history { st.last.unwrap_or(st.initial) } else { st.initial };
                    self.enter(c, &[]); // shallow history: child restored, its children default
                }
            },
            _ => {}
        }
    }
}

Usage (the model above, checked with asserts):

let mut c = Chart::default();
let root = c.add("Player", None, Kind::And, false);
let pb = c.add("Playback", Some(root), Kind::Xor, false);
let stopped = c.add("Stopped", Some(pb), Kind::Xor, false);
let run = c.add("Running", Some(pb), Kind::Xor, true); // history
let playing = c.add("Playing", Some(run), Kind::Xor, false);
let paused = c.add("Paused", Some(run), Kind::Xor, false);
let vol = c.add("Volume", Some(root), Kind::Xor, false);
let unm = c.add("Unmuted", Some(vol), Kind::Xor, false);
let muted = c.add("Muted", Some(vol), Kind::Xor, false);
c.on(stopped, "play", run, None);
c.on(run, "stop", stopped, None);              // one transition covers Playing and Paused
c.on(run, "eof", stopped, Some("ended"));      // raised: Volume reacts after this step
c.on(playing, "pause", paused, None);
c.on(paused, "pause", playing, None);
c.on(unm, "mute", muted, None);
c.on(muted, "ended", unm, None);
c.start();
c.send("play"); c.send("pause"); c.send("stop"); c.send("play");
assert!(c.is("Paused"));                       // history, not initial Playing
c.send("mute"); c.log.clear(); c.send("eof");
assert_eq!(c.log, ["-Paused", "-Running", "+Stopped", "-Muted", "+Unmuted"]);

Complexity and constants

• Per event: O(leaves x depth) with the linear transition scan above; O(depth) per leaf with a dense [state][event] table.
• Memory: one bool per state, one Option<usize> per XOR state for history; compile the chart to flat arrays, no per-state allocation.
• Exit/entry lists depend only on the transition (plus history and AND defaults): precompute them.
• Measured here (Apple M4 Pro, release build, the 9-state chart above): about 215 ns per pause event, including two format! allocations for the log; without logging it is lower.

Efficiency

Cost: one event on a UI-sized chart is order of 100 ns (measured above, 215 ns with log strings) and no allocation once logging is off. The bound is what actions do (layout, repaint, network), not dispatch.

Levers:

• Event-indexed transition table instead of scanning all transitions — O(depth) instead of O(transitions) (own reasoning, not measured) — charts beyond ~50 transitions.
• Precomputed exit/entry lists per transition — removes path walks per event (not measured) — hot charts such as gesture recognizers.
• Actions only mark dirty or start timers; the frame loop does the work — N events in a frame cost one repaint (damage tracking) — UI.
• Entry starts and exit stops timers/animations — idle states consume no ticks (design property) — battery-sensitive apps.
• Reused VecDeque queues — no per-event allocation — always.

Naive → standard → state of the art:

• Boolean flags per mode, checked every frame · state is the cross product, bugs in invalid combinations, polling cost every frame
• Flat enum + match, or a hierarchical state machine · O(1) dispatch, no parallel regions or history
• Compiled statechart: dense tables, precomputed entry/exit lists, bitset configuration · order of tens of ns per event (estimate, not measured)

Implementation notes

• Represent active as a bitset indexed by state id; AND/XOR are structural, not stored.
• Entry actions start things (timers, animations, subscriptions); exit actions must stop exactly what entry started. Own resources in entry/exit, not transitions, so every path into a state initialises alike.
• Timers are events: entry starts a one-shot timer, exit cancels it; the timer posts after_300ms onto the external queue (animation frames work the same way).
• Guards must be pure: no side effects, so region order cannot matter.
• send from an action is queued, never immediate (run-to-completion). Hit-testing and gestures produce the external events.

Pitfalls

• Giving the same event handlers in two regions silently fires both; that is the feature, but order between regions is unspecified, so actions must not depend on it.
• Exit parent-before-child leaks timers; entry child-before-parent breaks invariants children assume.
• Transitions "across" regions: ill-defined; model as an event instead.
• Unbounded raised-event chains loop forever; cap them in debug builds.
• History of a never-entered state must fall back to its initial child.
• State explosion returns if data (counters, flags) is encoded in states: keep it in a context and guard on it.

Variants and alternatives

In production

• Standard: W3C SCXML defines the semantics (internal-before-external queue, shallow and deep history) (spec).
• Web and app UIs: XState implements statecharts for JavaScript (docs).
• Embedded firmware: the QP framework (Samek) runs state machines and active objects on ARM Cortex-M and other microcontrollers (site).
• Application toolkits: the Qt SCXML module creates state machines from SCXML files, dynamically or as generated C++ (docs).
• Libraries: Boost.Statechart and Sismic implement orthogonal regions and history in C++ and Python.

Implementations

Sources

• David Harel, Statecharts: A Visual Formalism for Complex Systems, Science of Computer Programming 8(3), 1987. paper
• W3C, State Chart XML (SCXML): State Machine Notation for Control Abstraction, Recommendation 2015. spec (interpretation algorithm in Appendix D)
• Miro Samek, Practical UML Statecharts in C/C++, 2nd ed., CRC Press 2008. code