src/orchestrate.rs
//! AIRGAP8 — dependency-ordered install + start.
//!
//! Design (`.nornir/airgap-install.md` §2 Phase 3): products may point at each
//! other, so bring-up is a **topo-sorted** walk of the `depends_on` graph.
//! nornir owns dep-graph machinery (`src/warehouse/dep_graph.rs` / `mimir.rs`)
//! but it lives behind nornir's heavy deps; this lean crate re-implements the
//! same **Kahn topological sort** (sources first) self-contained — the algorithm
//! is small and the seam is just `&[Product]`.
//!
//! [`start_order`](crate::orchestrate::start_order) returns a flat dependency-respecting order; [`start_waves`](crate::orchestrate::start_waves)
//! returns the parallelizable **waves** (each wave = all products whose deps are
//! already started — the `install-system.md` Phase 4 model). Cycles are a hard
//! error (an install that can never converge).
use std::collections::{BTreeMap, BTreeSet, VecDeque};
use anyhow::{Result, anyhow};
use crate::product::Product;
/// Flat dependency-ordered start order (Kahn topo sort, sources first). Errors
/// on a cycle, naming the products still entangled.
pub fn start_order(products: &[Product]) -> Result<Vec<String>> {
Ok(start_waves(products)?.into_iter().flatten().collect())
}
/// Dependency-respecting **teardown** order — the reverse of [`start_order`], so a
/// dependent is stopped/removed **before** the thing it depends on (the Go
/// bundler's `destroy`, AIRGAP-TEARDOWN). A caller walks this order calling
/// `Installer::remove` per component. Same cycle error as [`start_order`].
pub fn teardown_order(products: &[Product]) -> Result<Vec<String>> {
let mut order = start_order(products)?;
order.reverse();
Ok(order)
}
/// Dependency-ordered **waves**: wave `i` holds every product all of whose
/// `depends_on` appear in waves `< i`. Within a wave, products are independent
/// and can be started concurrently (LAW: no rayon — a caller uses
/// `std::thread::scope`/gatling over a wave). Order within a wave is stable
/// (sorted) for deterministic tests.
pub fn start_waves(products: &[Product]) -> Result<Vec<Vec<String>>> {
let names: BTreeSet<&str> = products.iter().map(|p| p.name.as_str()).collect();
// Build in-degree + adjacency over only the known products (ignore deps that
// point outside this set — e.g. `network.target` — they're not our nodes).
let mut indeg: BTreeMap<String, usize> = BTreeMap::new();
let mut dependents: BTreeMap<String, Vec<String>> = BTreeMap::new();
for p in products {
indeg.entry(p.name.clone()).or_insert(0);
for dep in &p.depends_on {
if names.contains(dep.as_str()) {
*indeg.entry(p.name.clone()).or_insert(0) += 1;
dependents
.entry(dep.clone())
.or_default()
.push(p.name.clone());
}
}
}
// Kahn: repeatedly take all in-degree-0 nodes as a wave.
let mut waves: Vec<Vec<String>> = Vec::new();
let mut ready: VecDeque<String> = indeg
.iter()
.filter(|&(_, &d)| d == 0)
.map(|(n, _)| n.clone())
.collect();
let mut done = 0usize;
while !ready.is_empty() {
let mut wave: Vec<String> = ready.drain(..).collect();
wave.sort();
let mut next: BTreeSet<String> = BTreeSet::new();
for n in &wave {
done += 1;
if let Some(deps) = dependents.get(n) {
for d in deps {
let e = indeg.get_mut(d).expect("dependent tracked");
*e -= 1;
if *e == 0 {
next.insert(d.clone());
}
}
}
}
waves.push(wave);
ready.extend(next);
}
if done != indeg.len() {
let stuck: Vec<String> = indeg
.iter()
.filter(|&(_, &d)| d != 0)
.map(|(n, _)| n.clone())
.collect();
// SURFACE: start — a dependency cycle is an install that never converges;
// emit RED naming the entangled products so the matrix sees the broken graph.
crate::surface_status!(
"skidbladnir/start",
"start_waves_ordered",
false,
"dependency cycle among {} products: {}",
products.len(),
stuck.join(", ")
);
return Err(anyhow!(
"dependency cycle among products: {} (cannot order an install that never converges)",
stuck.join(", ")
));
}
// SURFACE: start — green: the ordered bring-up waves for a cycle-free graph.
crate::surface_status!(
"skidbladnir/start",
"start_waves_ordered",
true,
"{} products ordered into {} dependency waves",
products.len(),
waves.len()
);
Ok(waves)
}
#[cfg(test)]
mod tests {
use super::*;
fn p(name: &str, after: &[&str]) -> Product {
Product {
name: name.into(),
user: format!("_{name}"),
depends_on: after.iter().map(|s| s.to_string()).collect(),
ports: vec![],
}
}
/// LAW 1 (inject-assert): feed a real 5-node dep graph, assert the topo
/// WAVES match the expected dependency-ordered bring-up
/// (holger → nornir-server → {mail,tunnr}), and the flat order respects deps.
#[test]
fn topo_waves_from_fixture_dep_graph() {
let products = vec![
p("tunnr", &["nornir-server"]),
p("nornir-server", &["holger"]),
p("mail-server", &["nornir-server"]),
p("holger", &[]),
p("pki", &[]), // independent root → joins wave 1
];
let waves = start_waves(&products).unwrap();
// Wave 1: the two roots (sorted).
assert_eq!(waves[0], vec!["holger", "pki"]);
// Wave 2: nornir-server (after holger).
assert_eq!(waves[1], vec!["nornir-server"]);
// Wave 3: mail-server + tunnr (both after nornir-server, sorted).
assert_eq!(waves[2], vec!["mail-server", "tunnr"]);
// Flat order respects every edge: a dep precedes its dependent.
let order = start_order(&products).unwrap();
let pos = |n: &str| order.iter().position(|x| x == n).unwrap();
assert!(pos("holger") < pos("nornir-server"));
assert!(pos("nornir-server") < pos("mail-server"));
assert!(pos("nornir-server") < pos("tunnr"));
assert_eq!(order.len(), 5);
}
/// Deps that point outside the product set (e.g. `network.target`) are
/// ignored, not treated as missing nodes.
#[test]
fn external_deps_are_ignored() {
let products = vec![p("holger", &["network.target"])];
assert_eq!(start_order(&products).unwrap(), vec!["holger"]);
}
/// Teardown is the exact reverse of start — a dependent is removed before the
/// thing it depends on (holger dies last).
#[test]
fn teardown_is_reverse_of_start() {
let products = vec![
p("tunnr", &["nornir-server"]),
p("nornir-server", &["holger"]),
p("holger", &[]),
];
let mut expected = start_order(&products).unwrap();
expected.reverse();
let td = teardown_order(&products).unwrap();
assert_eq!(td, expected);
let pos = |n: &str| td.iter().position(|x| x == n).unwrap();
assert!(pos("tunnr") < pos("nornir-server"));
assert!(pos("nornir-server") < pos("holger"));
}
/// A cycle is a hard error naming the entangled products.
#[test]
fn cycle_is_rejected() {
let products = vec![p("a", &["b"]), p("b", &["a"])];
let err = start_waves(&products).unwrap_err().to_string();
assert!(err.contains("cycle"), "got: {err}");
assert!(err.contains('a') && err.contains('b'));
}
}