Crucible State Machine — Path Planning

[joshua-temple]

See the Kernel Core discussion for the kernel this extends. Path planning adds Machine.PlanPath(from, to, entity, ...PlanOption) ([]E, error).

PlanPath answers a simple question: what is the shortest sequence of events that moves an entity from one state to another? It walks the transition graph with breadth-first search and returns the event sequence.

Signature & contract

// PlanPath returns the shortest event sequence that transitions the entity
// from `from` to `to`, evaluating each event's guards against the entity's
// shape at the point that event would fire. Returns nil, *ErrNoPath when no
// route exists; the error carries the failure point and reason. The
// ...PlanOption tail follows the kernel's functional-options convention.
func (m *Machine[S, E, C]) PlanPath(from S, to S, entity C, opts ...PlanOption) ([]E, error)

Determinism:

• BFS by edge count — shortest by number of events; no edge weights in v1.
• Ties broken lexicographically by event name.
• Self-loops (From == To) are skipped during expansion.
• Visited-set keyed by destination state (standard BFS).

Purity:

• The entity is not mutated. The planner clones it and simulates transitions on the clone via an internal pure dryRun primitive.
• No effect factories run, no middleware runs, no policies run during planning.
• The returned slice is freshly allocated.

Edge cases:

• from == to returns ([]E{}, nil) — a zero-step path is legal.
• An undeclared from or to returns *ErrUndeclaredState.
• A target that is reachable structurally but blocked by guards on every path returns *ErrNoPath with the first guard-blocked event and the furthest state reached along the frontier.

How it works

The BFS frontier tracks (state, entity-clone, path) tuples. For each outbound transition, the planner calls dryRun, which clones the entity, evaluates the transition's guards on the clone, and — on success — returns the destination state plus the post-transition clone so the next step's guards see any mutations the path accumulated.

flowchart TD
    Start[from state, entity clone] --> Q{frontier non-empty?}
    Q -->|dequeue| Cur[current node]
    Cur --> Hit{state == to?}
    Hit -->|yes| Done[return path - shortest by edge count]
    Hit -->|no| Exp[expand outbound transitions<br/>sorted by event name]
    Exp --> Dry[dryRun each: clone + eval guards]
    Dry -->|guard passes| Enq[enqueue dest + cloned entity]
    Dry -->|guard fails| Block[record blocked edge in diagnostics]
    Enq --> Q
    Block --> Q
    Q -->|empty| NoPath[return ErrNoPath with closest + blocked-at]

Loading

Cloning

The entity is cloned before each simulated transition so the caller's entity is never touched. Because most context types are pointers, the builder author supplies a cheap, domain-specific clone function:

// Clone supplies the function PlanPath uses to copy the entity before
// simulating each transition. Required if any caller invokes PlanPath.
func (b *MachineBuilder[S, E, C]) Clone(fn func(C) C) *MachineBuilder[S, E, C]

A reflection-based deep copy was rejected (slow, brittle on cyclic graphs and unexported fields); requiring a Cloner interface on every entity was rejected (too invasive). The builder-supplied function keeps reflection out of the hot path, lets the author write the cheapest copy, and fails loudly at .Quench() if a PlanPath-using machine forgot to declare it.

Why visited-by-state, not visited-by-(state, entity)

Guards in v1 are pure predicates on the entity, and entity shape evolves monotonically along a path (the planner only ever adds setter outputs). So the first time BFS reaches a state via the shortest path, the entity is as filled-in as it can be for that path. Keying the visited-set by state alone keeps the search space small and the result deterministic. The monotonicity assumption is documented and covered by a property test.

ErrNoPath diagnostics

type ErrNoPath[S, E comparable] struct {
    From      S
    To        S
    Closest   S                          // furthest state reached on the frontier
    BlockedAt *blockedTransition[S, E]   // nil if To is structurally unreachable
    Reason    string
}

The error distinguishes "structurally unreachable" (no edge exists) from "blocked by a guard" (an edge exists but its guard failed), and names the closest state reached — turning a planning failure into an actionable diagnostic instead of a bare nil.

Use cases

• Ergonomic test seeding. Instead of hand-listing the events to reach a precondition state, ask the machine to plan them: events, _ := Machine.PlanPath(Draft, Published, doc) then fire each in turn.
• "Can I get there from here?" checks. A nil error means a route exists under the current entity shape; ErrNoPath tells you exactly where it broke.
• Scenario authoring. A future visual scenario builder proposes an initial event sequence by calling PlanPath, which a user then edits (see the Phase 2 Visualizer discussion).

On HSM

PlanPath walks a graph the builder has already expanded — superstate-level (cross-cutting) transitions are exploded into per-substate edges at build time. The BFS itself stays HSM-unaware, so path planning and the HSM layer compose without either needing to know about the other.

---

Crucible State Machine series: Overview & Roadmap · Kernel Core · HSM · Path Planning · JSON / Mermaid / DOT · Evolution Guide · Conformance · Phase 2