Crabrix blog
Implement a deterministic topological planner in Rust, reject missing dependencies, and report a real cycle witness without blaming every blocked package.
· 14 min read
A compiler, a static-site generator and a data pipeline all need to answer a similar question: which work can begin after its prerequisites have completed? A list of names is insufficient once one operation depends on another. You need a graph, a clear edge direction, a readiness rule and an error that distinguishes a missing prerequisite from a cycle. Otherwise a stalled pipeline tends to report whichever task happened to be inspected last.
This tutorial builds a deterministic planner using Rust's standard ordered collections. It returns prerequisites before consumers, rejects references to unknown nodes and reports one actual cycle when no complete order exists. It also reports every node blocked by unresolved cyclic work without claiming that every blocked node is itself part of a cycle. That distinction is useful in package managers, lesson prerequisites, document generation and background jobs whose dependencies need to be explained to a user.
Our input maps each package to the packages it requires. If web contains core in its dependency set, web depends on core and core must appear earlier in the successful order. When the planner constructs its reverse index, it records web as a consumer of core. These are two views of the same relationship, and confusing them reverses the resulting build order while still producing output that may look superficially plausible.
Use a tiny chain as the first fixture: config has no dependencies, core depends on config, and web depends on core. The only valid order is config, core, web. That fixture catches a reversed interpretation immediately. In documentation and diagrams, label arrows with the relationship they express. An arrow meaning depends on points in the opposite direction from one meaning enables, so an unlabeled diagram can undermine an otherwise correct implementation.
A referenced dependency that is absent from the graph is not automatically a leaf. Perhaps the caller forgot to resolve it, filtered it out incorrectly or misspelled its name. Pretending it is ready would produce a plan with a missing prerequisite. The example validates every dependency before scheduling any work and returns both the package and the unknown dependency in its error.
This validation boundary is intentionally separate from downloading or resolving packages. A resolver decides which exact package instance a requirement names; the planner receives an already identified graph. Combining those responsibilities can make a registry failure look like a graph cycle or make a dependency-version conflict disappear into an empty node. Keep the stages separate enough that an error can name the decision that failed and the information needed to reproduce it.
The graph stores dependencies in a BTreeSet, so listing the same dependency twice creates one edge. Readiness counts are computed from that normalized set. This matters because decrementing a prerequisite count once per consumer relationship only works when the count and the reverse index represent the same edges. Counting duplicate declarations while storing unique consumers can leave a node permanently blocked even though every real prerequisite completed.
Normalization is a domain decision, not a universal rule. Two build steps may require distinct outputs from the same package, in which case those output requirements should be modeled explicitly rather than collapsed accidentally. Our nodes represent complete tasks and each dependency relationship means that one complete prerequisite task must finish. Repeated declarations of that exact relationship are redundant, which is why set semantics match the example's contract.
Several tasks may be ready at the same time. Any order among independent ready tasks can be topologically valid, but choosing an order reproducibly makes logs, snapshots and bug reports easier to compare. The planner uses a BTreeSet and removes its first element, so it consistently chooses the lexicographically smallest currently ready name. Input insertion order does not decide which task is selected next.
That tie-break rule does not imply that alphabetical order is the best production scheduler. A real scheduler might prioritize the critical path, user-visible work, memory limits or cache hits. Determinism is the requirement here, and lexical ordering is a small policy that is easy to test. If you later change the policy, keep topological correctness separate from the tie-break rule so a performance change does not accidentally weaken prerequisite enforcement.
Each package begins with a count of unfinished prerequisites. The initial ready set contains packages whose count is zero. Taking a ready package appends it to the output order and decrements the counts of its consumers. A consumer enters the ready set exactly when its count reaches zero. No scan of the entire graph is needed after every completion because the reverse consumer index identifies the affected nodes.
In the runnable fixture, config enables core, then core enables both cli and web. The ordered ready set chooses cli before web. Neither consumer is allowed to run before core, and both remain valid independent choices afterward. This trace is small enough to write on paper, which makes it a useful debugging tool when a larger graph appears to schedule work prematurely or never releases a package that should be ready.
Save this program as main.rs and run it with edition 2021. It needs no downloaded packages. The main function checks a successful branching graph and a graph with a two-node cycle plus a downstream consumer. Compiling the same file as a test harness checks an unknown prerequisite, an empty graph and repeated declarations of the same edge. The code returns structured errors rather than constructing a user-facing sentence inside the algorithm.
The example uses short string names for readability. A real package planner should use an identity that distinguishes versions, sources, targets and other build-unit properties relevant to that system. Two packages with the same display name are not necessarily the same node. Resolving that identity before planning prevents a successful topological order from concealing an incorrectly merged dependency graph.
use std::collections::{BTreeMap, BTreeSet};
type Graph<'a> = BTreeMap<&'a str, BTreeSet<&'a str>>;
#[derive(Debug, PartialEq)]
enum PlanError<'a> {
Unknown { package: &'a str, dependency: &'a str },
Cycle { blocked: Vec<&'a str>, witness: Vec<&'a str> },
}
fn plan<'a>(graph: &Graph<'a>) -> Result<Vec<&'a str>, PlanError<'a>> {
let mut remaining_count = BTreeMap::new();
let mut consumers: BTreeMap<&str, Vec<&str>> = BTreeMap::new();
for (&package, dependencies) in graph {
remaining_count.insert(package, dependencies.len());
for &dependency in dependencies {
if !graph.contains_key(dependency) {
return Err(PlanError::Unknown { package, dependency });
}
consumers.entry(dependency).or_default().push(package);
}
}
let mut ready: BTreeSet<&str> = remaining_count.iter()
.filter_map(|(&name, &count)| (count == 0).then_some(name)).collect();
let mut order = Vec::new();
while let Some(package) = ready.pop_first() {
order.push(package);
for &consumer in consumers.get(package).into_iter().flatten() {
let count = remaining_count.get_mut(consumer).unwrap();
*count -= 1;
if *count == 0 { ready.insert(consumer); }
}
}
if order.len() == graph.len() { return Ok(order); }
let blocked: BTreeSet<&str> = remaining_count.iter()
.filter_map(|(&name, &count)| (count > 0).then_some(name)).collect();
let mut positions = BTreeMap::new();
let mut walk = Vec::new();
let mut current = *blocked.first().unwrap();
let witness = loop {
if let Some(&start) = positions.get(current) {
let mut cycle = walk[start..].to_vec();
cycle.push(current);
break cycle;
}
positions.insert(current, walk.len());
walk.push(current);
current = graph[current].iter().copied()
.find(|name| blocked.contains(*name)).unwrap();
};
Err(PlanError::Cycle { blocked: blocked.into_iter().collect(), witness })
}
fn graph<'a>(rows: &[(&'a str, &[&'a str])]) -> Graph<'a> {
rows.iter().map(|(name, dependencies)|
(*name, dependencies.iter().copied().collect())).collect()
}
fn main() {
let inputs = graph(&[("web", &["core"]), ("cli", &["core"]),
("core", &["config"]), ("config", &[])]);
assert_eq!(plan(&inputs), Ok(vec!["config", "core", "cli", "web"]));
let cyclic = graph(&[("a", &["b"]), ("b", &["a"]), ("c", &["a"])]);
assert_eq!(plan(&cyclic), Err(PlanError::Cycle {
blocked: vec!["a", "b", "c"], witness: vec!["a", "b", "a"] }));
println!("deterministic plan and cycle witness: ok");
}
#[test]
fn unknown_dependency_is_not_treated_as_a_leaf() {
assert_eq!(plan(&graph(&[("app", &["missing"])])),
Err(PlanError::Unknown { package: "app", dependency: "missing" }));
}
#[test]
fn empty_and_duplicate_edge_inputs_have_defined_results() {
assert_eq!(plan(&Graph::new()), Ok(vec![]));
assert_eq!(plan(&graph(&[("app", &["core", "core"]), ("core", &[])])),
Ok(vec!["core", "app"]));
}If the output contains every node, the plan is complete. Otherwise the ready set became empty while some nodes still had unfinished prerequisites. Those remaining nodes are blocked by the unresolved subgraph. At least one cycle exists in that subgraph, but other remaining nodes may merely depend on a cycle. Reporting the entire remaining set as the cycle would therefore accuse nodes that cannot fix the underlying problem.
Our error includes both blocked and witness. The blocked list tells the caller which work could not be scheduled. The witness identifies one closed dependency walk that can explain a real cycle. A user interface can show the witness prominently and list downstream affected packages separately. That gives a developer a smaller relationship to inspect while preserving the broader impact of the failure.
After the ready queue is exhausted, every blocked node has at least one dependency that is also blocked. If it did not, all its prerequisites would already have completed and it would have become ready. The witness search starts at the first blocked node and repeatedly follows one blocked dependency. Because the remaining graph is finite, the walk must eventually revisit a node. The repeated suffix is a closed dependency walk.
The positions map remembers where each visited node first appeared in the walk. When a repeated node is found, slicing from its previous position and appending that node closes the witness. Prefix nodes are excluded: they may lead into a cycle without belonging to it. This iterative approach also avoids consuming the Rust call stack in a deeply nested graph. It finds one witness, not a complete decomposition into all strongly connected components.
A graph can contain several independent cycles or one larger strongly connected region with many possible closed walks. The example reports one deterministic witness, which is enough to establish that a complete topological order is impossible. Fixing that relationship may reveal another cycle on the next run. If your product needs to display every cyclic region at once, use a strongly connected component analysis and distinguish each region from its downstream consumers.
For a package installer, one witness may be sufficient for an actionable first error. For a visual dependency editor, showing all cyclic groups can be more helpful because users may repair several relationships in one interaction. Decide based on the workflow, and name the result accurately. A field called all_cycles would be misleading for this implementation, whereas witness communicates both what the algorithm found and the limit of that evidence.
The returned vector is a valid serial order. It does not create worker threads, enforce resource quotas or decide when a failed task should cancel its consumers. Parallel execution needs to preserve the same readiness invariant while tracking tasks that are queued, running, completed or failed. Decrement a consumer's unfinished count after a prerequisite succeeds, not merely after it starts or enters a worker queue.
Keep scheduling policy and execution state out of the immutable input graph when possible. The graph explains the dependency relationships; an operation-specific state structure records this run's progress. That separation helps when a user cancels a build, retries one package or compares a cached run with a fresh one. Reusing a graph must not accidentally reuse a previous run's half-decremented counters or stale running flags.
A planner can treat a verified cached prerequisite as already satisfied, but only after establishing that the artifact matches the requested build unit. A package name alone is not enough. Source content, selected features, dependency identities, compiler inputs and target configuration can all change what a package produces. Cache reuse therefore needs a separate validity decision before it influences scheduling.
In a learning application, keep the visible labels honest. A package loaded from a valid artifact cache should appear as cached, while a newly compiled package should appear as compiled. A metadata-only check should not be presented as a successful executable run. Those distinctions are useful when investigating a reported boundary: the graph may be correct and the cache entry valid for Check, while linking or execution still exposes a missing backend operation.
A dependency graph gives a useful count of planned work, but package count is not elapsed-time prediction. Ten tiny libraries may compile faster than one large generic library. If a user sees nine of ten packages completed, the final package can still dominate the run. Show the count as completed units alongside the current package and stage, rather than implying that ninety percent of the total time has passed.
The denominator can also change if resolution is still discovering the graph. Avoid reporting a final total before the relevant planning stage has completed. A good event stream can say resolving dependencies first, then publish the known package list, then report acquisition, verification and compilation transitions. This makes a stalled source download distinguishable from a slow compiler invocation without introducing a decorative percentage that obscures the actual operation.
The graph type has unique keys by construction, but that does not mean every input format is already unambiguous. Collecting repeated node declarations into a map can replace an earlier declaration with a later one. If the two declarations disagree about prerequisites, the resulting graph may be valid while no longer representing what the source actually said. Detect that conflict before constructing the planner's normalized input.
The small graph helper in the program constructs test fixtures; its rows are deliberately unique. A parser for a real manifest or job file should return a duplicate-node error with the relevant source locations. Identical repeated declarations may be rejected or merged under a documented rule, but contradictory declarations should not be resolved by whichever entry happened to arrive last.
This is another reason to separate parsing, normalization and planning. A missing field, duplicate identity and structural cycle need different repairs. Once the planner receives a validated map of unique identities and normalized dependency sets, its readiness counts can describe that graph precisely rather than compensating for ambiguities it no longer has enough source information to explain.
Suppose a valid acyclic plan begins executing and core fails to compile. Its consumers cannot proceed, but that runtime state has not introduced a cycle into the dependency graph. If an execution controller simply leaves their unfinished counts nonzero and runs the cycle-reporting branch, it can produce an impossible diagnosis. Structural planning and runtime success tracking must remain distinct.
Give the execution layer explicit states such as waiting, running, succeeded, failed and blocked by failed prerequisite. When core fails, its own diagnostic explains the cause, while downstream tasks can name core as the reason they did not run. Keep those tasks visible if a user wants to understand the impact, but avoid repeating the entire compiler error under every dependent package.
A retry can then reset the affected execution states without changing the graph. After the prerequisite succeeds, consumers become eligible under the original readiness rules. Testing this transition is particularly useful for an interactive compiler, where a user commonly fixes one dependency or project file and expects the same open project to continue through the previously blocked stages.
One package can participate in several distinct build units. Host-side build tools and target-side libraries may need different feature sets or compilation settings, even when they come from the same source version. An alias can also give a dependency a different name in a consumer's source. Neither an alias nor a bare registry name is a complete universal build identity.
For a real compiler integration, resolve those distinctions before feeding nodes to a topological planner. Include the source and exact version, target role and relevant configuration in the unit identity; retain aliases on the edges where consumers use them. Do not unify a build script's dependencies with a target library's dependencies merely to make the graph easier to represent. A deterministic order over incorrectly merged nodes is still an incorrect build.
The tutorial's strings keep the algorithm readable, but the algorithm itself does not require display names as keys. Replacing them with an ordered domain-specific identifier should preserve readiness and cycle semantics while allowing the presentation layer to show a shorter friendly label.
For every successful plan, build a map from node name to output position and assert that every prerequisite appears before its consumer. Also assert that the output contains every graph node exactly once. These properties catch missing nodes and premature scheduling even when a test does not require a particular tie-break policy. A separate test can require the lexical order chosen by this implementation.
For a cycle error, verify every adjacent pair in the witness against the original depends-on relation and verify that the first and last nodes are equal. Check that every witness node appears in blocked, but do not require every blocked node to appear in the witness. A deliberately downstream node such as c in the example makes that distinction observable. Tests should protect the meaning of an error field, not just compare a convenient formatted string.
A real repository can fail before this planner receives a graph. Its workspace may require a selected member, a dependency may come from an unavailable Git revision, or an optional feature may introduce a native toolchain. These are not graph-cycle failures merely because dependency preparation stopped. Preserve the original failure category and enough context to identify the unresolved requirement.
Likewise, a successful plan establishes order, not target compatibility. A library can be correctly ordered and still fail because its code uses a missing operating-system API or exposes a compiler backend defect. A useful build report keeps source acquisition, graph resolution, planning, compilation and execution as distinct stages. That separation makes it possible to improve the missing capability and rerun exactly the stage that failed without rewriting an otherwise correct explanation of the dependency graph.
The planner's main contribution is an explanation that survives changes in input order and execution timing. A successful result says which prerequisites make each step possible. A missing-node error names the incomplete relationship. A cycle result supplies one real closed walk and a separate list of affected work. Those outputs are small enough to log, compare in tests and show in an interface without exposing the entire internal implementation.
When extending the algorithm, keep those meanings intact. Add domain-specific identities before planning, choose a tie-break rule deliberately, validate cached prerequisites separately and model execution progress outside the immutable graph. Whether the application builds Rust libraries, renders a set of web pages or schedules learning exercises, the useful invariant remains concrete: a task becomes ready because every required predecessor has successfully supplied what it needs.