mod build_order¶
- module build_order¶
The order to build a set of easyconfigs in, as a graph problem.
This is deliberately not
crate::select. Choosing which versions a site should carry is a constraint problem with one answer per package name, and that is what a stack is. Sequencing a build is a different question: given what the recipes already pin, in what order can they be built. Mokhov, Mitchell and Peyton Jones separate exactly these two concerns, the task description from the scheduler, in doi:10.1145/3236774, and conflating them is why asking the stack solver for a build order produced conflicts that were policy decisions rather than facts about the recipes.So a node here is a whole module, name and version and toolchain and versionsuffix together, the way a functional deployment model keys a package by its full identity and lets several coexist (doi:10.1017/s0956796810000195). Two versions of binutils on the system toolchain, or Perl at GCCcore and at SYSTEM, are two nodes. The package key in
crate::resolvo_providergives those the same distinct namesstack solveuses, because EasyBuild installs them side by side (doi:10.1145/2522920.2522927). A build-only tool such as CMake is the same kind of node: EasyBuild loads it only while the recipe that names it builds.A runtime dependency does not coexist that way.
stack solvekeeps one version of that name at one toolchain, and it rejects a closure where no candidate satisfies every such requirement. Eigen 3.4.1 required by one recipe and Eigen 5.0.0 required by another is that closure.build_orderrefuses it before an order is written, and the error names each requester and the version it resolved. The order does not repin a recipe. Choosing which pin to keep would be the policy decision this module leaves to the solver, and an exact pin the other recipe does not accept has no version the solver can keep.What remains is a choice function for requirements that admit more than one candidate, and a topological sort. Both are deterministic, so the same tree and the same roots give the same order every time.
The graph is petgraph’s, and the algorithms are its own rather than hand-rolled:
toposortfor the order,tarjan_sccto name every cycle in full when there is one, andgreedy_feedback_arc_setto say which edges would break it. daggy was the other candidate and refuses a cyclic graph at insertion, returningWouldCyclefor the edge that closed it. That is the wrong shape here: an easyconfig tree genuinely contains bootstrap cycles, and the useful answer names the whole cycle rather than the one edge that happened to be added last.Types
- type BuildGraph¶
The build graph: an edge runs from a dependency to what needs it, so a topological order is already the order to build in.
Functions
- fn build_graph(candidates: &[Candidate], roots: &[String], choice: Choice) -> Result<BuildGraph, OrderError>¶
Build the graph the recipes describe, reachable from
roots.Nodes are whole modules and edges run from a dependency to what needs it. The graph is returned even when it has a cycle, because naming the cycle is more useful than refusing to hand it over.
- fn build_graph_against_installed(candidates: &[Candidate], roots: &[String], choice: Choice, is_installed: &dyn Fn(&ModuleKey) -> bool) -> Result<(BuildGraph, BTreeSet<ModuleKey>), OrderError>¶
The build graph of
roots, stopping at modulesis_installednames.The graph is the one
build_graphwould build for everything that still has to be built. An installed module is not a node: the robot does not rebuild it, and it does not rebuild what was installed with it. The set is those modules, in key order.
- fn build_order(candidates: &[Candidate], roots: &[String], choice: Choice) -> Result<Vec<Candidate>, OrderError>¶
What to build, in the order to build it.
Roots are package names, optionally
name==version. Every dependency the reachable recipes state is included, build-time and runtime alike, since both have to exist before the build starts.
- fn build_order_against_installed(candidates: &[Candidate], roots: &[String], choice: Choice, is_installed: &dyn Fn(&ModuleKey) -> bool) -> Result<OrderAgainstInstalled, OrderError>¶
build_orderagainst an installed module list.is_installedis the robot’s view of the machine: a module it names is left out of the order, and so is everything reachable only through it. Resolution is otherwise the same walk, including the synthetic GCC-family hierarchy and the refusal of two runtime versions in one toolchain. A predicate that is never true returns the same order asbuild_orderand an emptyinstalledlist.
- fn closure_against_installed(candidates: &[Candidate], starts: &[ModuleKey], choice: Choice, is_installed: &dyn Fn(&ModuleKey) -> bool) -> InstalledClosure¶
Close
startsover the tree the wayeb --robotdoes against an existing install: an installed module is a leaf, because its own dependencies were installed with it, and everything reachable through modules that are not installed has to be built.Unlike
graph_from_keysa requirement nothing satisfies does not abort the walk. It is recorded and the walk goes on, so one missing recipe in one pull request does not hide the rest of its build set.
- fn cycle_breaking_edges(graph: &BuildGraph) -> Vec<(ModuleKey, ModuleKey, Edge)>¶
Which edges would break the cycles in a graph, if any.
A bootstrap chain is a real cycle in the tree and someone has to decide where to cut it, usually by taking one build from the previous generation. This says where the cut is cheapest rather than leaving it to be guessed.
- fn format_order(order: &[Candidate]) -> String¶
The order as easyconfig paths, one per line, ready for a build list.
- fn graph_from_keys(candidates: &[Candidate], starts: &[ModuleKey], choice: Choice) -> Result<BuildGraph, OrderError>¶
The build graph reachable from modules named by their full identity.
build_graphtakes package names and picks one build of each; this takes the builds themselves, for a caller that already knows which ones it means, as an easystack does when it names easyconfig files. A key with no candidate in the tree is a node with no dependencies.
- fn graph_from_keys_against_installed(candidates: &[Candidate], starts: &[ModuleKey], choice: Choice, is_installed: &dyn Fn(&ModuleKey) -> bool) -> Result<(BuildGraph, BTreeSet<ModuleKey>), OrderError>¶
graph_from_keys, stopping at modulesis_installednames.An installed module is not added, and nothing it depends on is walked. The set is those modules, in key order. A predicate that is never true builds the same graph as
graph_from_keys.
- fn module_name(key: &ModuleKey) -> String¶
The EasyBuild module name of a key:
name/version[-toolchain]versionsuffix, the way it appears undermodules/allandsoftware/in an install tree.
- fn multi_build_names(order: &[Candidate]) -> BTreeMap<String, Vec<String>>¶
How many distinct builds of each name the order contains.
A name with more than one build is the case a stack solve cannot express, so it is worth reporting rather than leaving for someone to notice.
- fn reachable_graph(candidates: &[Candidate], starts: &[ModuleKey], choice: Choice) -> (BuildGraph, Vec<UnresolvedRequirement>)¶
The build graph reachable from
starts, including modules that are already installed.graph_from_keysreturns on the first requirement nothing satisfies. A deployed stack still has a graph when one recipe names a dependency the tree cannot fill: that requirement is recorded and the walk continues. Edge kinds are kept. Nothing here is treated as installed. The caller decides which of these modules are on the machine.
- fn reverse_closure(uses: &BTreeMap<ModuleKey, Vec<ReverseUse>>, starts: &[ModuleKey]) -> Vec<ClosureStep>¶
Modules that depend on
starts, directly or through other dependents.startsthemselves are not returned: they are the modules the caller already has. Each other module is reported once, on the shortest walk, with the edge that reached it.
- fn reverse_index(graph: &BuildGraph, candidates: &[Candidate]) -> BTreeMap<ModuleKey, Vec<ReverseUse>>¶
Who uses each module in
graph.Edges in the graph run from a dependency to the module that needs it, so the reverse of that edge is one entry here. A pair that has both a runtime edge and a build edge is recorded once, as
UseKind::Runtime. A builddependency with no runtime edge isUseKind::BuildOnly.exts_listis not a dependency tuple, so it is not a graph edge. A bundle whose extension name and version match a module in the graph gets anUseKind::Extensionentry from that module to the bundle. The toolchain is the bundle’s: an extension is built as part of the bundle.
- fn reverse_uses(candidates: &[Candidate], choice: Choice) -> BTreeMap<ModuleKey, Vec<ReverseUse>>¶
Who uses each module, resolved the same way
graph_from_keysresolves a dependency.The map’s key is the module being used. A pair that has both a runtime edge and a build edge is recorded once, as
UseKind::Runtime. Anexts_listentry is not a dependency tuple, so a bundle whose extension name and version match a module gets anUseKind::Extensionedge. A requirement nothing satisfies is left out: one missing recipe must not hide the rest of the closure.
- fn runtime_edges(order: &[Candidate]) -> HashMap<String, Vec<String>>¶
Index of runtime edges for callers that want the graph rather than the list.
- fn to_dot(graph: &BuildGraph) -> String¶
The graph in Graphviz DOT, for looking at a generation rather than reading six hundred lines of it.
Enums
- enum Choice¶
Which candidate to take when a requirement admits several.
Sequencing does not decide policy, so this is deliberately small: the question is only which of the admissible builds the order should contain.
- Newest¶
Newest version wins, which matches what a recipe means by >=.
- Oldest¶
Oldest admissible version, for reproducing what an old tree built.
- enum Edge¶
Why one build has to happen before another.
- Runtime¶
The dependent loads it at run time.
- Build¶
The dependent needs it present to build.
- Toolchain¶
The dependent is built with it: its toolchain, which no easyconfig lists among its dependencies because EasyBuild reads it off the
toolchainline instead.
Traits implemented
- enum OrderError¶
Why an order could not be produced.
- UnknownRoot¶
No package of that name is in the tree.
- requested: String¶
What was asked for.
- suggestions: Vec<String>¶
Names close enough to be worth offering.
- NoSuchVersion¶
The package exists; that version of it does not.
- name: String¶
The package name, which was found.
- requirement: String¶
The requirement that matched nothing.
- available: Vec<String>¶
What the tree does carry, newest first.
- Unsatisfied¶
A requirement matches nothing, with the module that stated it.
- requirement: String¶
The dependency as the recipe wrote it.
- available: Vec<String>¶
Versions of that package the tree carries.
- Cycle(Vec<ModuleKey>)¶
The graph has a cycle. Every module in the strongly connected component is named, not just the edge that happened to close it, since a bootstrap chain is broken by choosing where to cut the whole loop.
- RuntimeVersions(Vec<RuntimeConflict>)¶
Runtime requirements of one name at one toolchain disagree, and no candidate satisfies all of them.
stack solverejects that closure. The order does not pick a winner.
Traits implemented
- impl std::fmt::Display for OrderError¶
- impl std::error::Error for OrderError¶
- enum UseKind¶
How one module uses another.
A module listed in both
dependenciesandbuilddependenciesisUseKind::Runtime. The runtime edge is the shared-library link, so “builddependency only” means the runtime list does not name it.UseKind::Toolchainis thetoolchainline. The resolver records it because the build needs the toolchain first. It is not a link to a patched library.- Runtime¶
Listed in
dependencies.
- BuildOnly¶
Listed in
builddependenciesand not independencies.
- Extension¶
This module’s name and version appear in the bundle’s
exts_list.
- Toolchain¶
The dependent is built with this module as its toolchain.
Traits implemented
Structs and Unions
- struct ClosureStep¶
A module the reverse walk reached, and the edge that reached it.
- struct InstalledClosure¶
What a set of starts would make EasyBuild’s robot build on a given stack.
- unresolved: Vec<UnresolvedRequirement>¶
Requirements no easyconfig in the tree satisfies, sorted.
- struct ModuleKey¶
A module’s full identity, which is what makes two builds the same build.
- name: String¶
Package name.
- version: String¶
Version as the easyconfig states it.
- toolchain: String¶
Toolchain, written as EasyBuild names it in a module.
- versionsuffix: String¶
Versionsuffix, empty when the recipe has none.
Implementations
- impl ModuleKey¶
Functions
- fn of(candidate: &Candidate) -> Self¶
The key for one candidate.
Built only from fields on
candidate(no filesystem reads). The version segment is the EasyBuild install stem (versionprefix+ bareversion). Toolchain spelling follows EasyBuild 5.4.2: only the exact namesystemis the system toolchain;dummykeeps dummy-<version> in the key, asdet_full_ec_versiondoes.
Traits implemented
- struct OrderAgainstInstalled¶
What still has to be built once modules already on the machine are leaves.
- struct ReverseUse¶
One module that uses another, and the kind of use.
- struct RuntimeConflict¶
Runtime pins of one name at one toolchain that cannot share a stack.
- name: String¶
Package name.
- toolchain: String¶
Toolchain label,
foss-2026.1orsystem.
- requests: Vec<RuntimePin>¶
Who asked, sorted by requester, then requirement, then resolved version.
Traits implemented
- impl std::fmt::Display for RuntimeConflict¶