Pull / demand-driven resolution

Status: open/planned · Kind: component · Audience: user

Summary

• A pull / demand-driven variant (Buck2 DICE-style): request a target and resolve what is needed to reach it, rather than enumerating the global frontier.
• Complements the push frontier; useful when the caller cares about one goal, not the whole graph.
• Sub-capability of C-D2GO-readiness-scheduling.

Statement

The push frontier answers “everything runnable now.” Pull inverts it: given a target, walk its unfinished ancestors on demand and yield the runnable ones toward it. For a large graph where the caller wants only one deliverable, pull avoids computing the global frontier. It shares the goal’s subgraph with C-551W-goal-directed-frontier but is driven by request rather than recomputed on every state change.

What it provides

• resolve(&Graph, &impl StatusSource, &NodeId, Option<usize>) — the runnable nodes toward the goal, resolved on demand.
• Lazy traversal of ancestors(goal) that stops at satisfied prerequisites.

use graph_scheduler::pull::resolve;

// pull the next runnable work toward the goal
resolve(&g, &state, &"M-0011".into(), Some(4));

Inputs

• A target / goal id; the graph and state.

Outputs

• Runnable nodes toward the goal (resolved lazily).

Underlying implementation

• No code realizes this yet — the capability is planned. It would land with the crate at packages/rust/graph-scheduler/, pull in src/pull.rs behind a default-off pull Cargo feature. Until the crate exists there is no anchor to record here.
• Deferred past cutover, and it may not be built at all. The engine’s dispatcher tick is level-triggered — it recomputes the whole frontier every tick, which is the push model — so nothing in v0.1 has a reason to pull. If goal-direction lands and no consumer asks for lazy resolution, closing this as superseded is the right outcome rather than maintaining a second path to the same answer.

Notes

• Modeled on Buck2’s DICE demand-driven graph (graph-scheduler-research). An opt-in layer, expressed as a Cargo feature rather than a subpath export; the push frontier stays the default. It overlaps goal-directed push (C-551W-goal-directed-frontier), and D-BPD8’s open question — ship one or defer the other — is still open.
• The correctness reference is equality: resolve must return the same id set as the frontier filtered by only_toward(goal). Pull’s only claim is cost, so if it is not measurably cheaper it has no claim at all.

---

← Back to Capabilities