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, or Perl at GCCcore and at SYSTEM, are simply two nodes. Nothing has to be reconciled, because EasyBuild installs them side by side as different modules, which is what makes them co-installable in the sense of doi:10.1145/2522920.2522927.

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: toposort for the order, tarjan_scc to name every cycle in full when there is one, and greedy_feedback_arc_set to say which edges would break it. daggy was the other candidate and refuses a cyclic graph at insertion, returning WouldCycle for 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_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 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 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 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 toolchain line instead.

Traits implemented

impl std::fmt::Display for Edge

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.

from: ModuleKey

The module whose dependency could not be met.

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.

Traits implemented

impl std::fmt::Display for OrderError

impl std::error::Error for OrderError

Structs and Unions

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.

Traits implemented

impl std::fmt::Display for ModuleKey