Graph runtime: queueing, waves, and nested graphs

At a glance

• Every graph mutation becomes queued work; a single long-lived actor drains that queue one batch at a time.
• Edges run child → parent, so evaluation progresses leaf-to-root in waves.
• A graph's ref decides where its terminal result goes: a Field graph writes an entry value, a Param graph re-triggers its parent graph.
• Every batch carries version snapshots, checked before and after each awaited evaluation, so stale work is discarded rather than committed.

The graph view is the runtime used to author, schedule and evaluate template logic in apps/builder-ui. This page covers the execution semantics: how mutations become queued work, how batches are claimed and drained, how nodes are compiled and evaluated in waves, and how terminal results reach either an entry field or a parent graph. Visual layout is omitted unless it affects runtime behaviour.

Runtime file map

Subsystem	File	Responsibility
Graph model	components/graph-editor/types/graph.ts	Graph type system, DAG helper, evaluation types
Command model	components/graph-editor/lib/commands/types/commands.ts	Command contracts and version bump rules
Tree constraints	components/graph-editor/lib/commands/elementary/add-edge.ts	Single-parent and acyclic edge validation
Command → queue	components/graph-editor/store/command.ts	Applies commands and enqueues dirty subgraphs
Global queue SM	store/graphs/index.ts	Queue, in-flight batch, claim/finish/reset API
Batch contracts	components/graph-editor/lib/batch/contracts.ts	Gateway/compiler/evaluator interfaces
Store adapter	components/graph-editor/lib/batch/gateway.ts	Concrete read/write boundary to Zustand
Scheduler actor	components/graph-editor/lib/batch/runner.ts	Long-lived serialized drain loop
Wave planner	components/graph-editor/lib/batch/graph-batch-pipeline.ts	Affected-set and dependency countdown logic
Batch execution	components/graph-editor/lib/batch/graph-batch-executor.ts	Single-batch state transitions and staleness checks
Node compiler	components/graph-editor/lib/batch/compiler.ts	compileLogicTree integration and rendering
React host hook	components/graph-editor/hooks/use-graph-batch-process.ts	Runner lifecycle hosting
Eval transport	api/templating/query.ts	Request/response mapping for node evaluation

Paths are relative to apps/builder-ui/src/.

Graph semantics and structural constraints

A graph instance consists of id, ref, graphVersion, topologyVersion, nodes and edges. The ref field is not metadata — it controls where terminal output is applied. A Field graph writes directly into entries.setComputed(fieldId, value). A Param graph commits no field value; its terminal result instead triggers reevaluation in its parent graph, at the owning node.

Edge orientation is inverted relative to many DAG engines: from is the child node and to is the parent. Dependency resolution and wave progression therefore run leaf-to-root. The command layer enforces a tree-like structure by rejecting self-loops, parent conflicts (a child may have only one parent), and any edge that would create a cycle. That tree invariant is what the batch planner and skip propagation depend on.

Queue envelope and state machine

Queued work is a GraphBatchQueryItem containing id, entryId, graphId, graphVersion, topologyVersion, and a dirty node-id set. The version fields are snapshot markers captured at enqueue time, compared later against current store versions to detect stale execution.

The global graph slice holds a small state machine of batchQueue, batchInFlight and batchStatus. enqueueGraph appends work, claimBatch moves the queue head into batchInFlight, finishBatch clears it (optionally guarded by batch id), and resetBatchSM returns in-flight work to the queue. The hard invariant: one global in-flight batch at a time.

End-to-end flow

Trigger sources

The normal path is command execution: CommandSlice.applyCommand (and undo/redo) applies a graph mutation, filters dirty nodes against current graph membership, and calls graph.enqueueGraph(dirtyNodes).

Manual triggers exist too — the graph header's run button enqueues all nodes, and each node's run button enqueues only that node id. These are not cosmetic: they are direct entry points into the same queueing system, so anyone debugging unexpected reevaluation should treat them exactly like command-generated batches.

React host versus runtime core

useGraphBatchProcess acts as a host. It initializes the gateway once, keeps compiler and evaluator references current, creates a single runner instance, and starts or stops that runner with the component's mount lifecycle. The drain algorithm is deliberately not encoded in React effect loops: rerenders update dependencies, while the actor owns execution continuity.

Gateway boundary

The gateway is the single store adapter used by the runner and executor. It claims and finishes batches, builds graph + dag + versions snapshots, reads node evaluations and templates, writes runtime states, and applies terminal side effects — computed entry values for field graphs, parent reevaluation at ownerNodeId for parameter graphs.

It also maintains a lease map keyed by batch id. A completion only finishes a claim while lease and batch id still match, which stops stale or duplicate completions from corrupting in-flight state.

Runner actor semantics

GraphBatchRunner is a serialized actor guarded by running, draining and wakeRequested. start() resets queue state, subscribes to queue and in-flight signals, and wakes the drain loop. wake() either schedules a drain or records another wake request if a drain is already active. drain() repeatedly claims a batch, executes it and finishes the claim, re-entering if signalled or if work remains claimable.

That design prevents reentrant drains and gives deterministic single-threaded processing without locking primitives.

Executor semantics

GraphBatchExecutor owns one claimed batch. It loads a snapshot and pipeline instance, then checks staleness (snapshot.graphVersion against batch.graphVersion). Each wave partitions nodes into runnable and blocked, marks statuses, compiles the runnable ones, evaluates them, applies results, and re-checks cancellation and staleness after every awaited evaluation.

Compilation calls compileLogicTree(..., rootNodeId=nodeId) to produce a node-local template fragment. Both rawTemplate and the rendered template are carried: the rendered one goes to evaluation, the raw one is persisted for introspection and debugging. The evaluator receives { entryId, reqs: [{ nodeId, template }] } and returns node results, merged back into store evaluation state.

Wave planner mechanics

The planner starts from dirty seeds and computes affectedSet = dirty + all ancestors. For each affected node it computes remainingDeps, the number of affected children still unresolved. The initial ready wave is any dirty node with zero remaining dependencies.

A successful node decrements its parent's dependency count; when that reaches zero and the parent is still runnable, the parent joins a later wave. A failed node is marked error and causes ancestor skipping, and a skipped node is never requeued. Separately, the executor's canRunNode blocks a node when any direct child already sits in Error status in the store.

Worked example: successful partial reevaluation

Consider this graph, child → parent:

A node-level run enqueues dirty seed {n1}. The planner derives affectedSet = {n1, n3, terminal} and initializes counters so n1 is ready first. Wave 0 evaluates n1 and unblocks n3; wave 1 evaluates n3 and unblocks terminal; wave 2 evaluates terminal and projects the result through the graph reference path, writing the computed value to the entry for a Field graph.

Note that n2 is untouched. It's outside this batch's affected set, so its previous stable value is reused transitively by parent logic.

Worked example: failure and skip propagation

Same graph, same dirty seed {n1}. If wave evaluation returns error for n1, the executor marks n1 as error and propagates a skip to ancestors n3 and terminal, producing no further runnable waves from that batch. The effect is short-circuiting upward through the tree, avoiding nodes whose required child path already failed.

Nested parameter graph propagation

Parameter graphs attach to a parent graph through GraphRefType.Param metadata (ownerNodeId, paramKey). When such a child graph reaches terminal output, the gateway resolves the parent graph id with getGraphParents(childGraphId) and enqueues that parent with dirty seed [ownerNodeId]. Parent reevaluation then runs through the same pipeline.

Correctness invariants

1. Every node has at most one parent within a graph.
2. Graph edges are acyclic.
3. Global batch execution has at most one in-flight claim.
4. Claim completion must match the active lease and batch id.
5. Staleness is checked both before and after awaited evaluation.
6. Dependency counters never go below zero.
7. Skipped nodes are never requeued.
8. Initialized graphs always contain a terminal node.
9. Graph edits bump graphVersion; topology edits bump both graphVersion and topologyVersion.

Debugging order

When behaviour diverges from expectation, work through it in this order:

1. Queue state — batchQueue, batchInFlight.
2. The claimed batch envelope — dirty, and the version fields.
3. DAG orientation and node statuses in evaluations[graphId].nodes.
4. Stored node templates and the graph reference type.

For nested parameter flows, verify the graphParents mapping and ownerNodeId wiring before touching pipeline logic.

Most regressions here come from violating one of three boundaries: command-layer tree constraints, gateway-only store access, or the placement of the executor's stale checks.

If you change this runtime

Keep queue draining out of React lifecycle code — the runner actor semantics are what make execution deterministic. Keep store operations centralized in the gateway, for testability and separation of concerns. If the evaluator's response shape or semantics change, update the batch contracts and the executor guards in the same change set, or silent partial failures become likely.