Hierarchical state machine

Deep dive

How it works

In: one event and the current leaf state · Out: the new leaf state and the ordered exit/entry actions · State: state table (parent, initial child, handler per state), current leaf, one history slot per composite, event queue (run to completion) · Cost: O(depth) per event: bubbling up plus exits and entries along the path through the LCA

1. Dispatch starts at the current leaf and calls its handler.
2. Super: go to the parent; past the root the event is dropped.
3. Handled: stop (internal transition: no exit, no entry).
4. Transition(t): find the LCA, the nearest proper ancestor of both the handling state and t.
5. Exit from the current leaf up to the LCA (exit actions; record history in the parent).
6. Enter from below the LCA down to t (entry actions, top-down).
7. Drill down: while the state has an initial child, enter it.
8. A history target is a stored id (shallow: the child, then drill below it; deep: the leaf).

Top
 +-- Off
 +-- On [Power->Off, Vol: handled]
      +-- Stopped [Play->history(Active)]
      +-- Active [Stop->Stopped, Reload->Active]   initial: Playing
           +-- Playing [Pause->Paused]
           +-- Paused  [Play->Playing]

A guard is a condition in the handler before it returns Transition; if false, it returns Super or Handled. Orthogonal regions (AND-states) run several machines at once inside one parent: each event goes to every region (not in the code below). The W3C SCXML Recommendation (2015) writes these semantics in XML: <state>, <parallel>, <history type="shallow|deep">, <initial>. UML state machines use the same model.

Code

A media player. Asserts: exact exit/enter order across the hierarchy, parent handling of events a leaf ignores, history, and a self-transition on a composite. Semantics chosen: external (a transition to its own source exits and re-enters it and its substates); local semantics would keep the composite active. The last lines count transitions against a flat equivalent.

#[derive(Clone, Copy, PartialEq, Debug)]
enum Ev { Power, Play, Pause, Stop, Reload, Vol }
const EVENTS: [Ev; 6] = [Ev::Power, Ev::Play, Ev::Pause, Ev::Stop, Ev::Reload, Ev::Vol];
enum Res { Handled, Super, Transition(usize) }
use Res::*;
const TOP: usize = 0; const OFF: usize = 1; const ON: usize = 2; const STOPPED: usize = 3;
const ACTIVE: usize = 4; const PLAYING: usize = 5; const PAUSED: usize = 6;
const NAMES: [&str; 7] = ["Top", "Off", "On", "Stopped", "Active", "Playing", "Paused"];
const PARENT: [Option<usize>; 7] = [None, Some(TOP), Some(TOP), Some(ON), Some(ON), Some(ACTIVE), Some(ACTIVE)];
const INITIAL: [Option<usize>; 7] = [Some(OFF), None, Some(STOPPED), None, Some(PLAYING), None, None];
type Handler = fn(&Hsm, Ev) -> Res;
const HANDLERS: [Handler; 7] = [
    |_, _| Super,
    |_, e| if e == Ev::Power { Transition(ON) } else { Super },
    |_, e| match e { Ev::Power => Transition(OFF), Ev::Vol => Handled, _ => Super }, // Vol: internal
    |h, e| if e == Ev::Play { Transition(h.history[ACTIVE].unwrap_or(ACTIVE)) } else { Super },
    |_, e| match e { Ev::Stop => Transition(STOPPED), Ev::Reload => Transition(ACTIVE), _ => Super },
    |_, e| if e == Ev::Pause { Transition(PAUSED) } else { Super },
    |_, e| if e == Ev::Play { Transition(PLAYING) } else { Super },
];
struct Hsm { cur: usize, history: [Option<usize>; 7], log: Vec<String> }
impl Hsm {
    fn new() -> Self {
        let mut h = Hsm { cur: TOP, history: [None; 7], log: vec![] };
        h.log.push("enter Top".into());
        h.drill();
        h
    }
    fn drill(&mut self) { // initial transitions: enter default substates until a leaf
        while let Some(c) = INITIAL[self.cur] { self.cur = c; self.log.push(format!("enter {}", NAMES[c])); }
    }
    fn dispatch(&mut self, e: Ev) -> Option<usize> { // returns the state that handled it
        let mut s = self.cur;
        loop {
            match HANDLERS[s](self, e) {
                Handled => return Some(s),
                Transition(t) => { self.transition(s, t); return Some(s); }
                Super => s = PARENT[s]?, // bubble up; None past the root = unhandled
            }
        }
    }
    fn transition(&mut self, src: usize, tgt: usize) {
        let proper_anc = |mut x: usize| { let mut v = vec![]; while let Some(p) = PARENT[x] { v.push(p); x = p; } v };
        let sa = proper_anc(src);
        let lca = *proper_anc(tgt).iter().find(|a| sa.contains(a)).unwrap();
        while self.cur != lca { // exit from the active leaf up to (not including) the LCA
            let x = self.cur;
            self.log.push(format!("exit {}", NAMES[x]));
            self.history[PARENT[x].unwrap()] = Some(x); // shallow history: last active child
            self.cur = PARENT[x].unwrap();
        }
        let mut down = vec![]; // entry path LCA -> target, top-down
        let mut x = tgt;
        while x != lca { down.push(x); x = PARENT[x].unwrap(); }
        for &s in down.iter().rev() { self.log.push(format!("enter {}", NAMES[s])); self.cur = s; }
        self.drill();
    }
    fn take_log(&mut self) -> String { self.log.drain(..).collect::<Vec<_>>().join(", ") }
}
fn main() {
    let mut m = Hsm::new();
    assert_eq!(m.take_log(), "enter Top, enter Off");
    m.dispatch(Ev::Power);
    assert_eq!(m.take_log(), "exit Off, enter On, enter Stopped");
    m.dispatch(Ev::Play); // no history yet: default Playing
    assert_eq!(m.take_log(), "exit Stopped, enter Active, enter Playing");
    assert_eq!(m.dispatch(Ev::Vol), Some(ON)); // leaf ignores it; On handles it
    assert!(m.log.is_empty() && m.cur == PLAYING);
    // cross-hierarchy: handled by Active, target Stopped, LCA = On
    assert_eq!(m.dispatch(Ev::Stop), Some(ACTIVE));
    assert_eq!(m.take_log(), "exit Playing, exit Active, enter Stopped");
    m.dispatch(Ev::Play); m.dispatch(Ev::Pause); m.take_log();
    assert_eq!(m.dispatch(Ev::Stop), Some(ACTIVE)); // Paused has no Stop: parent handles it
    assert_eq!(m.take_log(), "exit Paused, exit Active, enter Stopped");
    m.dispatch(Ev::Play); // history restores Paused, not the default Playing
    assert_eq!(m.cur, PAUSED);
    assert_eq!(m.take_log(), "exit Stopped, enter Active, enter Paused");
    // self-transition on a composite: Active is exited and re-entered (external)
    m.dispatch(Ev::Reload);
    assert_eq!(m.take_log(), "exit Paused, exit Active, enter Active, enter Playing");
    m.dispatch(Ev::Power); // inherited from On
    assert_eq!(m.take_log(), "exit Playing, exit Active, exit On, enter Off");
    assert_eq!(m.dispatch(Ev::Vol), None); // nobody handles it in Off
    let probe = Hsm::new();
    let hier = (0..7).map(|s| EVENTS.iter().filter(|&&e| matches!(HANDLERS[s](&probe, e), Transition(_))).count()).sum::<usize>();
    let leaves: Vec<usize> = (0..7).filter(|&s| !(0..7).any(|c| PARENT[c] == Some(s))).collect();
    let flat: usize = leaves.iter().map(|&l| EVENTS.iter().filter(|&&e| {
        let mut s = Some(l);
        while let Some(x) = s { match HANDLERS[x](&probe, e) { Transition(_) => return true, Handled => return false, Super => s = PARENT[x] } }
        false
    }).count()).sum();
    println!("hierarchical transitions: {hier}, flat transitions: {flat}");
}

Output of this exact block (release build): hierarchical transitions: 7, flat transitions: 11, no assert fails. The flat count resolves each leaf and event through the parents and ignores history (extra states in a flat machine).

Complexity and constants

• Dispatch: one indirect call per level searched, O(depth); the LCA search is O(depth), precomputable per (source, target).
• A transition runs one exit per level left and one entry per level entered; these actions usually dominate the table walk.
• Memory: parent, initial child and a function pointer per state. I did not time the example.

Efficiency

• Cost: a few table lookups and indirect calls per event, no allocation (the example's log is for the asserts); bound is the entry/exit actions.
• Levers:
  • Enum-indexed arrays of function pointers — no allocation, short predictable chain — firmware, hot loops.
  • Precompute the exit/entry path per (source, target) — no parent walk — fixed machines.
  • Compile-time machines (Boost.SML) — dispatch resolved by the compiler — hot paths.
• Naive → standard → state of the art:
  • Flat match (state, event) with copied arrows · rows grow with leaves times events (11 against 7 here).
  • Parent table with bubbling · one row per shared reaction, O(depth) per event.
  • Compile-time generated machine · same semantics, no run-time table.

Implementation notes

• Run to completion: queue events raised by actions; never dispatch from inside an entry or exit action.
• Keep entry and exit actions short and non-failing.
• Store history as ids so it serialises.

Pitfalls

• External and local self-transitions differ in whether substates reset; pick one and document it.
• Side effects in a handler before it returns Super run in every state passed; act only when handling.
• Deep nesting hides which state handled an event; log the handling state.

Variants and alternatives

In production

• UI flows and workflows: XState (statecharts and actors, inspired by SCXML).
• Embedded firmware: QP/C, active objects with a hierarchical state machine, described in Samek's book.
• Desktop and embedded UIs: Qt QStateMachine (nested, parallel, history).
• C++ systems: Boost.MSM and Boost.SML.
• Telecom connection states, game animation, medical device modes: typical uses, no named deployment verified.

Implementations

Sources

• David Harel, Statecharts: a visual formalism for complex systems, Science of Computer Programming 8(3), 231-274, 1987. paper
• W3C, State Chart XML (SCXML): State Machine Notation for Control Abstraction, Recommendation, 1 September 2015. spec
• Miro Samek, Practical UML Statecharts in C/C++, 2nd ed., 2008. book · code
• Qt documentation, QStateMachine and QHistoryState. docs