crates/nornir-release-core/src/graph_math.rs
//! `nornir release doctor` — the **mathematical foundations**: the graph-theory +
//! optimization core the advisory doctor reasons over, so its answers are *derived*
//! (SCC / topo / MFAS / planning) instead of hand-coded heuristics.
//!
//! Model: the constellation is a directed graph `G=(V,E)` — `V` = crates (cargo
//! publishes CRATES, so that's the granularity), `E` = publish-order-gating edges
//! (`A→B` ⇔ `A` has an in-workspace Normal/Build `path` dep on `B` ⇒ `B` must
//! publish first). The gating graph is already built in [`crate::doctor`]'s
//! `RepoGraph`/`crate_graph`; this module supplies the pure algorithms over it:
//!
//! * [`tarjan_scc`] — strongly-connected components, `O(V+E)`. Every SCC with >1
//! node (or a self-loop) is *exactly* a dependency cycle.
//! * [`condense`] → [`Condensation`] — collapse each SCC to a super-node; the
//! condensation `G/SCC` is always a DAG. [`Condensation::topo_order`] gives the
//! coarse publish order, [`Condensation::waves`] the parallelizable antichains.
//! * [`min_feedback_arc_set`] — per-SCC MFAS: constellation SCCs are tiny (2–5
//! crates) so we EXHAUSTIVELY enumerate edge-subsets and rank the candidate cuts
//! by cost (DEV = 0, OPTIONAL/feature-gated = 1, crate-split = high) — each cut
//! carries a proof (the residual topo order) that removing it yields a DAG.
//! * the invertive [`plan`] planner — a STRIPS-style closure over the outcome-space
//! Ω: remedy operators held in a DATA TABLE ([`remedy_table`]) whose preconditions
//! are matched against the current [`Symptoms`] and applied to a FIXPOINT. This is
//! the anti-`if/else`: adding a remedy = adding a row, never a new branch.
//!
//! Everything here is PURE (no I/O), deterministic (BTree-ordered), and independent
//! of how the graph was extracted — the same code serves a source-derived graph and
//! (item 8) a future binary-derived one.
use std::collections::{BTreeMap, BTreeSet};
/// A directed graph as `node → the set of nodes it points at`. Throughout this
/// module the edge `A→B` reads "**A depends on B**" (B must publish first), matching
/// the doctor's `crate_deps`/`repo_edges` convention.
pub type Adj = BTreeMap<String, BTreeSet<String>>;
// ─────────────────────────── Tarjan SCC ───────────────────────────
/// Tarjan's strongly-connected components over `adj`, `O(V+E)`. Each returned
/// component is a sorted member list; the outer vector is deterministic. Every
/// component with more than one node — or a single node with a self-loop — IS a
/// dependency cycle (the nodes that provably cannot be linearly ordered).
///
/// DELEGATES to [`nornir_graph::tarjan_scc`], which is the constellation's ONE
/// Tarjan (LAW 5: reuse, never twin). The iterative, stack-safe implementation that
/// used to live here MOVED there verbatim when the graph seam was extracted — its
/// `Adj` is a type alias for the exact `BTreeMap<String, BTreeSet<String>>` this
/// module's [`Adj`] is, so there is no conversion. Everything else in this module
/// (condensation, waves, MFAS, the planner) still builds on this one function, so
/// it keeps its name and signature; only the body moved.
pub fn tarjan_scc(adj: &Adj) -> Vec<Vec<String>> {
nornir_graph::tarjan_scc(adj)
}
/// True when a single-node component `[n]` carries a self-loop (`n` depends on
/// itself) — the degenerate one-node cycle Tarjan reports as a size-1 SCC.
pub fn is_self_loop(adj: &Adj, comp: &[String]) -> bool {
comp.len() == 1 && adj.get(&comp[0]).map(|d| d.contains(&comp[0])).unwrap_or(false)
}
/// The dependency CYCLES in `adj`: every SCC with >1 node, plus every self-loop.
/// (A clean DAG returns an empty vector.) Each cycle is the SCC's sorted node set —
/// the crates whose entanglement no linear order can resolve = the "must-break" set.
pub fn cycles(adj: &Adj) -> Vec<Vec<String>> {
tarjan_scc(adj)
.into_iter()
.filter(|c| c.len() > 1 || is_self_loop(adj, c))
.collect()
}
// ─────────────────────────── condensation ───────────────────────────
/// The condensation `G/SCC`: each SCC collapsed to a super-node. Because every
/// cycle lives inside one SCC, the condensation is **always a DAG** — so it always
/// topo-sorts (coarse publish order) and layers into antichains (publish waves).
#[derive(Debug, Clone)]
pub struct Condensation {
/// Component id → its member nodes (sorted). The "must-break" internals.
pub comps: Vec<Vec<String>>,
/// Node → the component it belongs to.
pub comp_of: BTreeMap<String, usize>,
/// Component → the components it depends on (the condensed edge set; acyclic).
pub dag: Vec<BTreeSet<usize>>,
}
/// Build the [`Condensation`] of `adj` via [`tarjan_scc`]. `O(V+E)`.
pub fn condense(adj: &Adj) -> Condensation {
let comps = tarjan_scc(adj);
let n = comps.len();
let mut comp_of: BTreeMap<String, usize> = BTreeMap::new();
for (i, c) in comps.iter().enumerate() {
for node in c {
comp_of.insert(node.clone(), i);
}
}
let mut dag: Vec<BTreeSet<usize>> = vec![BTreeSet::new(); n];
for (from, tos) in adj {
// A node may be absent from comp_of only if it appears purely as an edge
// target with no key of its own — treat such nodes as their own trivial
// component would require adding them; the doctor always keys every node,
// so guard defensively and skip an unkeyed endpoint.
let Some(&cf) = comp_of.get(from) else { continue };
for to in tos {
if let Some(&ct) = comp_of.get(to) {
if cf != ct {
dag[cf].insert(ct);
}
}
}
}
Condensation { comps, comp_of, dag }
}
impl Condensation {
/// The components that ARE dependency cycles (size >1 super-nodes). Their member
/// sets are the crates a cut must break.
pub fn must_break(&self) -> Vec<&[String]> {
self.comps.iter().filter(|c| c.len() > 1).map(|c| c.as_slice()).collect()
}
/// Coarse publish order over the condensation: component ids, **dependencies
/// first**, Kahn's algorithm. Deterministic (ties by the component's smallest
/// member name). Always succeeds — the condensation is a DAG.
pub fn topo_order(&self) -> Vec<usize> {
let n = self.comps.len();
// indeg(c) = #components c depends on; a comp that depends on nothing is
// publishable first.
let mut indeg: Vec<usize> = (0..n).map(|c| self.dag[c].len()).collect();
let mut consumers: Vec<Vec<usize>> = vec![Vec::new(); n];
for (cf, deps) in self.dag.iter().enumerate() {
for &ct in deps {
consumers[ct].push(cf);
}
}
let key = |c: usize| self.comps[c].first().cloned().unwrap_or_default();
let mut ready: BTreeSet<(String, usize)> =
(0..n).filter(|&c| indeg[c] == 0).map(|c| (key(c), c)).collect();
let mut order = Vec::new();
while let Some((k, c)) = ready.iter().next().cloned() {
ready.remove(&(k, c));
order.push(c);
for &con in &consumers[c] {
indeg[con] -= 1;
if indeg[con] == 0 {
ready.insert((key(con), con));
}
}
}
order
}
/// PARALLELIZABLE PUBLISH WAVES: the DAG layered into antichains. Wave 0 = the
/// components that depend on nothing (publishable immediately); each later wave
/// is the components whose every dependency published in an earlier wave. Each
/// component expands to its member crate names — so a wave is the set of crates
/// that can be published **concurrently**. Deps-first, deterministic.
pub fn waves(&self) -> Vec<Vec<String>> {
let n = self.comps.len();
let mut indeg: Vec<usize> = (0..n).map(|c| self.dag[c].len()).collect();
let mut consumers: Vec<Vec<usize>> = vec![Vec::new(); n];
for (cf, deps) in self.dag.iter().enumerate() {
for &ct in deps {
consumers[ct].push(cf);
}
}
let mut frontier: Vec<usize> = (0..n).filter(|&c| indeg[c] == 0).collect();
let mut waves: Vec<Vec<String>> = Vec::new();
while !frontier.is_empty() {
// Expand this antichain's components into crate names (sorted, stable).
let mut wave: Vec<String> =
frontier.iter().flat_map(|&c| self.comps[c].iter().cloned()).collect();
wave.sort();
waves.push(wave);
let mut next: Vec<usize> = Vec::new();
for &c in &frontier {
for &con in &consumers[c] {
indeg[con] -= 1;
if indeg[con] == 0 {
next.push(con);
}
}
}
frontier = next;
}
waves
}
}
// ───────────────────── MFAS (minimum feedback arc set) ─────────────────────
/// How an intra-cycle edge can be cut, and its cost — the MFAS ranking key. Lower is
/// cheaper. A DEV edge is already non-gating (free to reclassify); an OPTIONAL edge
/// is a feature to gate off (cheap); a NORMAL gating edge needs a crate-split (dear).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum EdgeClass {
/// Already a dev-dep — not publish-gating; "cutting" it is free (cost 0).
Dev,
/// Feature-gated / optional path dep — gate the feature off (cost 1).
Optional,
/// Plain Normal/Build path dep — only a crate-split removes it (high cost).
Normal,
}
impl EdgeClass {
/// The cut cost of an edge of this class. `Normal` is the crate-split cost —
/// deliberately high so the MFAS prefers dev/optional cuts, and rises with the
/// number of crates the edge rides on (passed by the caller via `via_len`).
pub fn cost(self, via_len: usize) -> u32 {
match self {
EdgeClass::Dev => 0,
EdgeClass::Optional => 1,
EdgeClass::Normal => 10 + via_len as u32,
}
}
}
/// One directed intra-SCC edge, classified for MFAS: `from` depends on `to`, riding
/// on the `via` crate(s) (what `to` produces that `from` needs), with a cut class.
#[derive(Debug, Clone)]
pub struct ClassifiedEdge {
pub from: String,
pub to: String,
pub via: Vec<String>,
pub class: EdgeClass,
}
impl ClassifiedEdge {
fn cost(&self) -> u32 {
self.class.cost(self.via.len())
}
/// The concrete remedy sentence for cutting this edge.
fn action(&self) -> String {
match self.class {
EdgeClass::Dev => format!(
"cut `{} → {}` — it's a DEV edge (already non-gating); move it out of the order graph",
self.from, self.to
),
EdgeClass::Optional => format!(
"gate the feature off so `{}` no longer requires `{}` (optional dep)",
self.from, self.to
),
EdgeClass::Normal => {
let via = if self.via.is_empty() {
self.to.clone()
} else {
self.via.join(", ")
};
format!(
"split `{}`: extract `{}` into a leaf crate both can depend on, so `{}` no longer path-depends on `{}`",
self.to, via, self.from, self.to
)
}
}
}
}
/// A ranked MFAS candidate: the set of edges to remove, the total cost, the concrete
/// remedy actions, and the PROOF the residual is a DAG (its topo order over the
/// SCC's nodes — non-empty ⇔ acyclic, which we also `assert` on construction).
#[derive(Debug, Clone)]
pub struct CutSolution {
/// Edges to remove, as `(from, to)` pairs.
pub edges: Vec<(String, String)>,
/// Total cut cost (sum of removed-edge costs). Lower is better.
pub cost: u32,
/// One human remedy sentence per removed edge, cheapest-class first.
pub actions: Vec<String>,
/// Proof witness: a topological order of the SCC's nodes over the RESIDUAL edge
/// set. A DAG always has one; its presence certifies acyclicity.
pub proof_order: Vec<String>,
}
/// Kahn topo-sort of `nodes` under `edges` (edge `A→B` = A depends on B, so B
/// precedes A). Returns `Some(order)` iff the graph is acyclic — the DAG proof.
fn topo_of(nodes: &[String], edges: &[(&str, &str)]) -> Option<Vec<String>> {
let set: BTreeSet<&str> = nodes.iter().map(|s| s.as_str()).collect();
let mut indeg: BTreeMap<&str, usize> = nodes.iter().map(|n| (n.as_str(), 0)).collect();
let mut consumers: BTreeMap<&str, Vec<&str>> = BTreeMap::new();
for &(from, to) in edges {
if set.contains(from) && set.contains(to) {
*indeg.get_mut(from).unwrap() += 1; // from depends on to
consumers.entry(to).or_default().push(from);
}
}
let mut ready: BTreeSet<&str> =
indeg.iter().filter(|&(_, &d)| d == 0).map(|(&n, _)| n).collect();
let mut order = Vec::new();
while let Some(&n) = ready.iter().next() {
ready.remove(n);
order.push(n.to_string());
if let Some(cs) = consumers.get(n) {
for &c in cs {
let d = indeg.get_mut(c).unwrap();
*d -= 1;
if *d == 0 {
ready.insert(c);
}
}
}
}
(order.len() == nodes.len()).then_some(order)
}
/// **Minimum Feedback Arc Set** over one SCC: exhaustively enumerate edge-subsets
/// and return the cuts whose removal makes the SCC acyclic, ranked cheapest-first.
/// Constellation SCCs are tiny (2–5 crates), so the `2^m` enumeration is trivial;
/// for a pathologically large SCC (`m > 20` edges) we fall back to subsets of size
/// ≤ 3 (still finds every small cut). Only MINIMAL cuts are kept (no cut that is a
/// strict superset of another feasible cut). Each solution proves acyclicity by
/// carrying a residual topo order.
///
/// Ranking key: `(total cost, #edges, edge names)` — so a cost-0 DEV cut beats a
/// cost-1 OPTIONAL cut beats a crate-split, and ties are deterministic.
pub fn min_feedback_arc_set(nodes: &[String], edges: &[ClassifiedEdge]) -> Vec<CutSolution> {
let m = edges.len();
// The residual edge set for a removal mask, as (from,to) &str pairs.
let residual = |mask: u64| -> Vec<(&str, &str)> {
(0..m)
.filter(|i| mask & (1 << i) == 0)
.map(|i| (edges[i].from.as_str(), edges[i].to.as_str()))
.collect()
};
// Candidate removal masks: full power set when small, else size-≤3 subsets.
let masks: Vec<u64> = if m <= 20 {
(1u64..(1u64 << m)).collect()
} else {
let mut v = Vec::new();
for a in 0..m {
v.push(1u64 << a);
for b in (a + 1)..m {
v.push((1u64 << a) | (1u64 << b));
for c in (b + 1)..m {
v.push((1u64 << a) | (1u64 << b) | (1u64 << c));
}
}
}
v
};
// Feasible cuts: (mask, cost, proof_order).
let mut feasible: Vec<(u64, u32, Vec<String>)> = Vec::new();
for mask in masks {
if let Some(order) = topo_of(nodes, &residual(mask)) {
let cost: u32 = (0..m)
.filter(|i| mask & (1 << i) != 0)
.map(|i| edges[i].cost())
.sum();
feasible.push((mask, cost, order));
}
}
// Drop non-minimal cuts: any mask that is a strict SUPERSET of another feasible
// mask (removing extra edges is never necessary once acyclic).
let minimal: Vec<(u64, u32, Vec<String>)> = feasible
.iter()
.filter(|(mask, _, _)| {
!feasible
.iter()
.any(|(other, _, _)| other != mask && (mask & other) == *other)
})
.cloned()
.collect();
let mut sols: Vec<CutSolution> = minimal
.into_iter()
.map(|(mask, cost, proof_order)| {
// Removed edges, ordered cheapest-class first for readable actions.
let mut removed: Vec<&ClassifiedEdge> =
(0..m).filter(|i| mask & (1 << i) != 0).map(|i| &edges[i]).collect();
removed.sort_by_key(|e| (e.cost(), e.from.clone(), e.to.clone()));
debug_assert_eq!(proof_order.len(), nodes.len(), "proof must cover every node");
CutSolution {
edges: removed.iter().map(|e| (e.from.clone(), e.to.clone())).collect(),
cost,
actions: removed.iter().map(|e| e.action()).collect(),
proof_order,
}
})
.collect();
sols.sort_by(|a, b| {
(a.cost, a.edges.len(), &a.edges).cmp(&(b.cost, b.edges.len(), &b.edges))
});
sols
}
// ───────────────────── invertive planner (utfallsrum Ω) ─────────────────────
/// A finding CLASS in the release outcome-space Ω. The doctor's state `s ∈ Ω` is the
/// multiset of open symptoms; the green target is the empty multiset. A remedy
/// operator's precondition is simply "count of its target class > 0" — so dispatch
/// is generic (match preconditions), never a hand-coded `if` per symptom.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub enum SymptomKind {
/// Path dep of a MEMBER crate missing `version=` — auto-fixable (`--fix`).
VersionGap,
/// Path dep on a NON-member crate — needs a decision (join cascade / publish it).
NonMemberDep,
/// External version skew — a repo behind the semver-join target.
Skew,
/// Dirty working tree (noise) — auto-tidyable.
Dirty,
/// A dependency cycle whose cheapest MFAS cut costs ≤ 1 (dev/optional) — auto.
CheapCycle,
/// A dependency cycle whose cheapest cut is a crate-split — needs a decision.
HardCycle,
/// A crate held from crates.io by a patch-fork — needs an upstream publish.
PromoteBlock,
}
/// The open-symptom multiset — a point in Ω. `total()` is the convergence measure
/// each AUTO operator must strictly reduce.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct Symptoms {
counts: BTreeMap<SymptomKind, usize>,
}
impl Symptoms {
pub fn new() -> Self {
Self::default()
}
/// Set (or clear, with 0) the count of a symptom class.
pub fn set(&mut self, kind: SymptomKind, n: usize) {
if n == 0 {
self.counts.remove(&kind);
} else {
self.counts.insert(kind, n);
}
}
pub fn count(&self, kind: SymptomKind) -> usize {
self.counts.get(&kind).copied().unwrap_or(0)
}
/// Total open symptoms across all classes — the multiset cardinality.
pub fn total(&self) -> usize {
self.counts.values().sum()
}
pub fn is_green(&self) -> bool {
self.counts.is_empty()
}
}
/// AUTO (safe to apply) vs DECISION (surface one crisp ask) — the operator's class.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum RemedyClass {
Auto,
Decision,
}
/// A STRIPS-style remedy operator: `⟨precondition, effect⟩` held as DATA. The
/// precondition is implicit — "target class count > 0"; the effect closes that class
/// (`count ↦ 0`). Adding a remedy = adding a row to [`remedy_table`], never a branch.
#[derive(Debug, Clone)]
pub struct RemedyOp {
/// Stable id the executor dispatches a real action on (e.g. `"fix-versions"`).
pub id: &'static str,
pub class: RemedyClass,
/// The symptom class this operator closes (its precondition + effect target).
pub target: SymptomKind,
/// Human remedy sentence / the flag it corresponds to.
pub action: &'static str,
}
/// The remedy operator TABLE — the doctor's entire remedy knowledge, as data. The
/// planner dispatches generically over it; the ORDER is the AUTO-application
/// priority (cheapest / most-foundational first). `fix-versions` is the first
/// operator (reusing the built `--fix`).
pub fn remedy_table() -> Vec<RemedyOp> {
use RemedyClass::*;
use SymptomKind::*;
vec![
RemedyOp {
id: "fix-versions",
class: Auto,
target: VersionGap,
action: "run --fix: fill `version = \"…\"` on every member path dep",
},
RemedyOp {
id: "tidy-dirty",
class: Auto,
target: Dirty,
action: "--tidy: drop working-tree noise (.claude/, *.arrows) and commit",
},
RemedyOp {
id: "bump-skew-join",
class: Auto,
target: Skew,
action: "bump each behind repo to the semver-join (⊔) target",
},
RemedyOp {
id: "cut-cycle-cheap",
class: Auto,
target: CheapCycle,
action: "MFAS: cut the cost-≤1 edge (drop a dev edge / gate a feature off)",
},
RemedyOp {
id: "add-member",
class: Decision,
target: NonMemberDep,
action: "DECIDE: add the non-member dep to the release cascade, or publish it first",
},
RemedyOp {
id: "split-crate",
class: Decision,
target: HardCycle,
action: "DECIDE: split a crate (extract a leaf) to break the cycle — MFAS crate-split",
},
RemedyOp {
id: "unfork",
class: Decision,
target: PromoteBlock,
action: "DECIDE: publish the forked dep's real version upstream, or wait for it",
},
]
}
/// One applied (or proposed) remedy in the plan trace.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct PlanStep {
pub op_id: &'static str,
pub class: RemedyClass,
pub action: &'static str,
pub closes: SymptomKind,
/// How many findings of that class the step closes.
pub count: usize,
}
/// The invertive remedy PLAN: the ordered AUTO steps applied to a fixpoint, then the
/// minimal set of DECISION asks that remain (surfaced one at a time). `green` ⇔ the
/// autos reach the empty multiset with no decisions left — a self-healed release.
#[derive(Debug, Clone)]
pub struct RemedyPlan {
/// AUTO steps, in application order — each strictly reduces the open multiset.
pub steps: Vec<PlanStep>,
/// DECISION asks that block a full auto-heal, cheapest/most-actionable first.
pub decisions: Vec<PlanStep>,
/// True iff the AUTO closure reaches green with zero decisions.
pub green: bool,
}
/// THE PLANNER — closure of the remedy operators over Ω. Starting from `initial`,
/// repeatedly match an AUTO operator's precondition (its target class is open) and
/// apply its effect (close that class), recording the step; loop to a FIXPOINT (no
/// AUTO operator applies). Then collect the DECISION operators still triggered as the
/// minimal ask set. Model-based / declarative: no `if` per symptom, only table
/// matching.
///
/// **Convergence** is guaranteed: every AUTO application strictly reduces
/// `state.total()` (it closes a non-empty class and no operator re-opens a closed
/// one), so the loop runs at most `initial.total()` times — asserted below.
pub fn plan(initial: &Symptoms, table: &[RemedyOp]) -> RemedyPlan {
let mut state = initial.clone();
let mut steps = Vec::new();
let budget = initial.total() + 1; // strict-decrease ⇒ ≤ total iterations
let mut guard = 0;
loop {
guard += 1;
assert!(guard <= budget + 1, "planner must converge (strict-decrease invariant)");
// Precondition matching: first AUTO op (table order = priority) whose target
// class is open. This is the generic dispatch — the anti-if/else.
let Some(op) = table
.iter()
.find(|o| o.class == RemedyClass::Auto && state.count(o.target) > 0)
else {
break;
};
let before = state.total();
let closed = state.count(op.target);
state.set(op.target, 0); // effect
debug_assert!(state.total() < before, "AUTO op must strictly reduce the multiset");
steps.push(PlanStep {
op_id: op.id,
class: RemedyClass::Auto,
action: op.action,
closes: op.target,
count: closed,
});
}
// Remaining open classes are exactly the DECISION-targeted ones (any class with
// no operator would also remain — surfaced too, so nothing is silently dropped).
let decisions: Vec<PlanStep> = table
.iter()
.filter(|o| o.class == RemedyClass::Decision && state.count(o.target) > 0)
.map(|o| PlanStep {
op_id: o.id,
class: RemedyClass::Decision,
action: o.action,
closes: o.target,
count: state.count(o.target),
})
.collect();
let green = state.is_green();
RemedyPlan { steps, decisions, green }
}
#[cfg(test)]
mod tests {
use super::*;
fn adj(pairs: &[(&str, &[&str])]) -> Adj {
pairs
.iter()
.map(|(n, ds)| (n.to_string(), ds.iter().map(|s| s.to_string()).collect()))
.collect()
}
fn edge(from: &str, to: &str, class: EdgeClass) -> ClassifiedEdge {
ClassifiedEdge { from: from.to_string(), to: to.to_string(), via: vec![to.to_string()], class }
}
/// Tarjan on a known graph: one 3-node cycle (a→b→c→a) + a clean tail (c→d).
#[test]
fn tarjan_finds_the_scc() {
let g = adj(&[("a", &["b"]), ("b", &["c"]), ("c", &["a", "d"]), ("d", &[])]);
let cs = cycles(&g);
assert_eq!(cs.len(), 1, "exactly one cycle");
assert_eq!(cs[0], vec!["a", "b", "c"], "the SCC = the 3-node loop, sorted");
// Two SCCs total: the {a,b,c} loop and the singleton {d}.
assert_eq!(tarjan_scc(&g).len(), 2, "{{a,b,c}} + {{d}}");
nornir_testmatrix::functional_status(
"release-graph-math",
"tarjan_scc",
cs.len() == 1 && cs[0] == vec!["a", "b", "c"],
"3-node cycle a→b→c→a isolated from tail d",
);
}
#[test]
fn dag_has_no_cycle_and_topo_orders() {
let g = adj(&[("app", &["lib"]), ("lib", &["core"]), ("core", &[])]);
assert!(cycles(&g).is_empty(), "a DAG has no cycle");
let cond = condense(&g);
// 3 singleton comps; coarse order is deps-first: core, lib, app.
let order: Vec<String> = cond
.topo_order()
.iter()
.map(|&c| cond.comps[c].join("+"))
.collect();
assert_eq!(order, vec!["core", "lib", "app"]);
nornir_testmatrix::functional_status(
"release-graph-math",
"condensation_topo",
order == vec!["core", "lib", "app"],
"deps-first coarse order over a DAG",
);
}
/// Publish waves = antichains: independent leaves publish together.
#[test]
fn waves_are_antichains() {
// core is a shared leaf; a and b both depend on core; app depends on a+b.
let g = adj(&[
("core", &[]),
("a", &["core"]),
("b", &["core"]),
("app", &["a", "b"]),
]);
let waves = condense(&g).waves();
assert_eq!(waves.len(), 3, "three waves");
assert_eq!(waves[0], vec!["core"], "wave 0 = the shared leaf");
assert_eq!(waves[1], vec!["a", "b"], "wave 1 = the two independents, concurrent");
assert_eq!(waves[2], vec!["app"], "wave 2 = the sink");
nornir_testmatrix::functional_status(
"release-graph-math",
"publish_waves",
waves.len() == 3 && waves[1] == vec!["a", "b"],
"antichain wave 1 = {a,b} publishable concurrently",
);
}
/// MFAS ranking: a 2-node cycle where one edge is OPTIONAL (cost 1) and the other
/// NORMAL (crate-split, cost ≥10) → the cheapest cut is the optional edge.
#[test]
fn mfas_ranks_cheapest_cut_first() {
let nodes = vec!["a".to_string(), "b".to_string()];
let edges = vec![
edge("a", "b", EdgeClass::Normal), // a→b: costly split
edge("b", "a", EdgeClass::Optional), // b→a: cheap gate-off
];
let sols = min_feedback_arc_set(&nodes, &edges);
assert!(!sols.is_empty(), "the cycle is breakable");
let best = &sols[0];
assert_eq!(best.edges, vec![("b".to_string(), "a".to_string())], "cut the optional edge");
assert_eq!(best.cost, 1, "gate-off costs 1");
assert_eq!(best.proof_order.len(), 2, "residual is a DAG (proof covers both nodes)");
// Every solution's proof must actually be acyclic.
for s in &sols {
assert_eq!(s.proof_order.len(), nodes.len(), "each cut proves a DAG");
}
// Cheapest first.
assert!(sols.windows(2).all(|w| w[0].cost <= w[1].cost), "ranked by cost");
nornir_testmatrix::functional_status(
"release-graph-math",
"mfas_ranking",
best.cost == 1 && best.edges == vec![("b".to_string(), "a".to_string())],
"optional-edge cut (cost 1) ranked above crate-split (cost ≥10)",
);
}
/// A DEV edge is a cost-0 cut and wins outright.
#[test]
fn mfas_prefers_free_dev_cut() {
let nodes = vec!["x".to_string(), "y".to_string()];
let edges = vec![
edge("x", "y", EdgeClass::Dev), // free
edge("y", "x", EdgeClass::Normal), // split
];
let sols = min_feedback_arc_set(&nodes, &edges);
assert_eq!(sols[0].cost, 0, "the dev cut is free");
assert_eq!(sols[0].edges, vec![("x".to_string(), "y".to_string())]);
}
/// Invertive planner: version gaps + skew are AUTO → applied to a fixpoint; a
/// non-member dep + a hard cycle remain as DECISION asks. Convergence: the auto
/// steps strictly reduce the multiset to just the decisions.
#[test]
fn planner_converges_autos_then_asks() {
let mut s = Symptoms::new();
s.set(SymptomKind::VersionGap, 37);
s.set(SymptomKind::Skew, 2);
s.set(SymptomKind::NonMemberDep, 4);
s.set(SymptomKind::HardCycle, 1);
let plan = plan(&s, &remedy_table());
// AUTO closure handled the version gaps + skew.
let auto_ids: Vec<&str> = plan.steps.iter().map(|p| p.op_id).collect();
assert!(auto_ids.contains(&"fix-versions"), "version gaps auto-fixed first");
assert!(auto_ids.contains(&"bump-skew-join"), "skew auto-bumped");
assert_eq!(plan.steps.len(), 2, "exactly the two applicable AUTO ops");
// The FIRST operator is the reused --fix.
assert_eq!(plan.steps[0].op_id, "fix-versions", "--fix is the first operator");
// DECISION asks remain, minimal set.
let dec_ids: Vec<&str> = plan.decisions.iter().map(|p| p.op_id).collect();
assert_eq!(dec_ids, vec!["add-member", "split-crate"], "two crisp asks, ordered");
assert!(!plan.green, "not green: decisions block the auto-heal");
nornir_testmatrix::functional_status(
"release-graph-math",
"planner_fixpoint",
plan.steps.len() == 2 && plan.decisions.len() == 2 && !plan.green,
"37 version-gaps + 2 skew auto-closed; non-member + hard-cycle → 2 asks",
);
}
/// A clean state plans to GREEN with no steps and no asks (fixpoint = green).
#[test]
fn planner_green_on_clean_state() {
let plan = plan(&Symptoms::new(), &remedy_table());
assert!(plan.steps.is_empty() && plan.decisions.is_empty() && plan.green);
}
/// A cheap cycle is an AUTO remedy; feeding only a CheapCycle drives the
/// cut-cycle-cheap operator to a green fixpoint.
#[test]
fn planner_auto_cuts_cheap_cycle() {
let mut s = Symptoms::new();
s.set(SymptomKind::CheapCycle, 1);
let plan = plan(&s, &remedy_table());
assert_eq!(plan.steps.len(), 1);
assert_eq!(plan.steps[0].op_id, "cut-cycle-cheap");
assert!(plan.green, "the cheap cut heals it fully");
}
// ═══════════════════ additional edge-case coverage ═══════════════════
// Hand-verifiable small graphs: disconnected components, self-loops, larger
// SCCs, MFAS minimality, and the condensation-is-a-DAG invariant.
/// Given `nodes` and the FULL edge list (`A→B` = "A depends on B"), verify that
/// `order` is a genuine topological order of the graph with `removed` edges cut:
/// it's a permutation of the nodes and every surviving dependency precedes its
/// dependent (pos(B) < pos(A) for a kept edge A→B). This is an INDEPENDENT
/// re-check of a [`CutSolution::proof_order`] — the residual really is acyclic.
fn is_valid_topo(
nodes: &[&str],
all_edges: &[(&str, &str)],
removed: &[(String, String)],
order: &[String],
) -> bool {
// permutation check
let want: BTreeSet<&str> = nodes.iter().copied().collect();
let got: BTreeSet<&str> = order.iter().map(|s| s.as_str()).collect();
if want != got || order.len() != nodes.len() {
return false;
}
let pos = |n: &str| order.iter().position(|x| x == n).unwrap();
let cut: BTreeSet<(String, String)> = removed.iter().cloned().collect();
all_edges.iter().all(|&(from, to)| {
if cut.contains(&(from.to_string(), to.to_string())) {
return true; // this edge was removed
}
// A→B means B must publish first ⇒ B precedes A in the order.
pos(to) < pos(from)
})
}
/// Two disjoint 2-cycles plus an isolated node: `cycles()` finds BOTH cycles
/// (order-independent), the lone node is not a cycle, and the condensation is
/// acyclic with every node collapsed into a single wave (nothing gates anything).
#[test]
fn disconnected_two_cycles_and_isolated_node() {
let g = adj(&[
("a", &["b"]), ("b", &["a"]), // cycle {a,b}
("c", &["d"]), ("d", &["c"]), // cycle {c,d}
("e", &[]), // isolated leaf
]);
let cs = cycles(&g);
assert_eq!(cs.len(), 2, "two independent cycles");
assert!(cs.contains(&vec!["a".to_string(), "b".to_string()]));
assert!(cs.contains(&vec!["c".to_string(), "d".to_string()]));
assert!(!cs.iter().any(|c| c.contains(&"e".to_string())), "e is no cycle");
let cond = condense(&g);
// 3 components: {a,b}, {c,d}, {e}. None depends on another ⇒ acyclic ⇒
// topo covers all, and every node sits in ONE wave.
assert_eq!(cond.comps.len(), 3);
assert_eq!(cond.topo_order().len(), 3, "condensation is a DAG (all ordered)");
let waves = cond.waves();
assert_eq!(waves.len(), 1, "no cross-component edges ⇒ a single wave");
assert_eq!(waves[0], vec!["a", "b", "c", "d", "e"], "all publishable together");
// must_break = the two multi-node SCCs.
assert_eq!(cond.must_break().len(), 2);
nornir_testmatrix::functional_status(
"release-graph-math",
"disconnected_components",
cs.len() == 2 && waves.len() == 1,
"two disjoint 2-cycles + isolated node isolated correctly",
);
}
/// A self-loop `n→n` is the degenerate one-node cycle: `is_self_loop` detects it,
/// `cycles()` reports the singleton, and a plain singleton (`m`, no self-edge) is
/// NOT a cycle even though it is its own SCC.
#[test]
fn self_loop_is_a_one_node_cycle() {
let g = adj(&[("n", &["n"]), ("m", &["n"])]);
assert!(is_self_loop(&g, &["n".to_string()]), "n→n is a self-loop");
assert!(!is_self_loop(&g, &["m".to_string()]), "m has no self-edge");
let cs = cycles(&g);
assert_eq!(cs, vec![vec!["n".to_string()]], "only the self-loop is a cycle");
// Tarjan still finds two SCCs total ({n} and {m}).
assert_eq!(tarjan_scc(&g).len(), 2);
nornir_testmatrix::functional_status(
"release-graph-math",
"self_loop_cycle",
cs == vec![vec!["n".to_string()]],
"self-loop n→n flagged as a size-1 cycle; clean singleton m is not",
);
}
/// Condensation of a 3-cycle with a tail: the loop collapses to ONE super-node,
/// the tail stays singletons, `comp_of` groups the loop together, and the coarse
/// order is strictly dependencies-first over the acyclic condensation.
#[test]
fn condensation_groups_scc_and_stays_acyclic() {
// a→b→c→a is the loop; c→d, d→e is a clean tail hanging off it.
let g = adj(&[
("a", &["b"]), ("b", &["c"]), ("c", &["a", "d"]),
("d", &["e"]), ("e", &[]),
]);
let cond = condense(&g);
// The loop's three nodes share ONE component; d, e are their own.
let ca = cond.comp_of["a"];
assert_eq!(cond.comp_of["b"], ca);
assert_eq!(cond.comp_of["c"], ca);
assert_ne!(cond.comp_of["d"], ca);
assert_ne!(cond.comp_of["e"], cond.comp_of["d"]);
// Exactly one must-break SCC = the loop, sorted.
assert_eq!(cond.must_break(), vec![["a".to_string(), "b".to_string(), "c".to_string()].as_slice()]);
// Acyclic ⇒ topo covers every component; deps-first ⇒ e, then d, then loop.
let order: Vec<String> =
cond.topo_order().iter().map(|&c| cond.comps[c].join("+")).collect();
assert_eq!(order, vec!["e", "d", "a+b+c"], "tail leaf first, cycle super-node last");
// No component depends on itself (the DAG invariant).
assert!(cond.dag.iter().enumerate().all(|(i, deps)| !deps.contains(&i)));
nornir_testmatrix::functional_status(
"release-graph-math",
"condensation_acyclic",
order == vec!["e", "d", "a+b+c"],
"3-cycle collapsed to one super-node; condensation topo-sorts deps-first",
);
}
/// MFAS on a 3-node cycle where every edge is a costly `Normal`: exactly the three
/// single-edge cuts are minimal (any 2-edge cut is a strict superset and dropped),
/// each costs the same, and each proof order is an INDEPENDENTLY-verified DAG.
#[test]
fn mfas_three_cycle_yields_three_minimal_single_cuts() {
let nodes = vec!["a".to_string(), "b".to_string(), "c".to_string()];
let all: [(&str, &str); 3] = [("a", "b"), ("b", "c"), ("c", "a")];
let edges = vec![
edge("a", "b", EdgeClass::Normal),
edge("b", "c", EdgeClass::Normal),
edge("c", "a", EdgeClass::Normal),
];
let sols = min_feedback_arc_set(&nodes, &edges);
assert_eq!(sols.len(), 3, "three minimal single-edge cuts, no supersets");
for s in &sols {
assert_eq!(s.edges.len(), 1, "each minimal cut removes exactly one edge");
assert_eq!(s.cost, 11, "Normal cut = 10 + via_len(1)");
// The carried proof really is a topological order of the residual.
assert!(
is_valid_topo(&["a", "b", "c"], &all, &s.edges, &s.proof_order),
"proof_order must be a valid residual DAG order: {:?}",
s.proof_order
);
}
// The three cuts are exactly the three distinct edges.
let mut cut_edges: Vec<(String, String)> =
sols.iter().map(|s| s.edges[0].clone()).collect();
cut_edges.sort();
assert_eq!(
cut_edges,
vec![
("a".to_string(), "b".to_string()),
("b".to_string(), "c".to_string()),
("c".to_string(), "a".to_string()),
]
);
nornir_testmatrix::functional_status(
"release-graph-math",
"mfas_three_cycle_minimal",
sols.len() == 3 && sols.iter().all(|s| s.edges.len() == 1),
"3-cycle: 3 minimal single-edge cuts, each a proven residual DAG",
);
}
/// MFAS minimality: a feasible cut is dropped when it is a strict SUPERSET of
/// another feasible cut. On a 2-cycle both single-edge cuts work, so the
/// remove-both cut (also feasible) must NOT be returned.
#[test]
fn mfas_drops_non_minimal_superset_cuts() {
let nodes = vec!["a".to_string(), "b".to_string()];
let edges = vec![
edge("a", "b", EdgeClass::Normal),
edge("b", "a", EdgeClass::Optional),
];
let sols = min_feedback_arc_set(&nodes, &edges);
assert_eq!(sols.len(), 2, "both single-edge cuts; the 2-edge superset is dropped");
assert!(sols.iter().all(|s| s.edges.len() == 1), "no non-minimal (2-edge) cut kept");
// Cheapest (optional, cost 1) first.
assert_eq!(sols[0].cost, 1);
assert_eq!(sols[0].edges, vec![("b".to_string(), "a".to_string())]);
}
/// The `EdgeClass` cut-cost schedule: Dev is free, Optional flat 1, and a Normal
/// crate-split rises with the number of crates the edge rides on.
#[test]
fn edge_class_cost_schedule() {
assert_eq!(EdgeClass::Dev.cost(5), 0, "a dev cut is always free");
assert_eq!(EdgeClass::Optional.cost(3), 1, "an optional gate-off is flat 1");
assert_eq!(EdgeClass::Normal.cost(0), 10, "base crate-split cost");
assert_eq!(EdgeClass::Normal.cost(2), 12, "cost grows with via_len");
// So a Normal cut is always dearer than an Optional, which beats Dev.
assert!(EdgeClass::Dev.cost(9) < EdgeClass::Optional.cost(9));
assert!(EdgeClass::Optional.cost(9) < EdgeClass::Normal.cost(0));
}
/// The planner surfaces a DECISION-only symptom with no AUTO reduction: a
/// promote-block yields zero auto steps and one crisp `unfork` ask, not green.
#[test]
fn planner_surfaces_decision_only_symptom() {
let mut s = Symptoms::new();
s.set(SymptomKind::PromoteBlock, 3);
let plan = plan(&s, &remedy_table());
assert!(plan.steps.is_empty(), "nothing auto-heals a promote block");
assert_eq!(plan.decisions.len(), 1);
assert_eq!(plan.decisions[0].op_id, "unfork");
assert_eq!(plan.decisions[0].count, 3, "the ask carries the finding count");
assert!(!plan.green);
}
/// Multiple distinct AUTO symptoms all close to a green fixpoint, and `Symptoms`
/// bookkeeping (`set(_, 0)` clears, `total`, `is_green`) is exact.
#[test]
fn planner_multiple_autos_reach_green() {
let mut s = Symptoms::new();
s.set(SymptomKind::Dirty, 1);
s.set(SymptomKind::CheapCycle, 2);
assert_eq!(s.total(), 3);
s.set(SymptomKind::Dirty, 0); // clearing removes the class entirely
assert_eq!(s.total(), 2);
assert_eq!(s.count(SymptomKind::Dirty), 0);
s.set(SymptomKind::Dirty, 1); // put it back
let plan = plan(&s, &remedy_table());
let ids: BTreeSet<&str> = plan.steps.iter().map(|p| p.op_id).collect();
assert!(ids.contains("tidy-dirty") && ids.contains("cut-cycle-cheap"));
assert_eq!(plan.steps.len(), 2);
assert!(plan.green && plan.decisions.is_empty(), "all AUTO ⇒ self-healed green");
}
}