crates/nornir-release-core/src/depgraph_trait.rs
//! **`DepGraph` — the backend-agnostic release dependency-graph SEAM.**
//!
//! The release doctor reasons over ONE shape: a directed graph of publish units
//! (crates) whose edge `A→B` reads "**A depends on B**" (⇒ `B` must publish first).
//! The questions — *what are the cycles?*, *what is the publish order?*, *what is
//! the release closure of this root?* — are whole-graph questions.
//!
//! # This module is now a RE-EXPORT
//!
//! The trait, the pure SCC/topo/closure math and every backend moved to the
//! [`nornir_graph`] leaf, which is the constellation's ONE graph seam. They are
//! re-exported here unchanged so every existing `crate::depgraph_trait::…` call
//! site keeps working:
//!
//! * [`DepGraph`] is `nornir_graph::BulkGraph` — the BULK shape, `nodes()` +
//! `edges()` with the pure deterministic `scc` / `cycles` / `topo` /
//! `release_closure` defaults. Same algorithms, same outputs, one home.
//! * [`PetDepGraph`] is `nornir_graph::PetGraph` — the in-memory `petgraph`-backed
//! impl that overrides `scc` with petgraph's own Tarjan.
//! * [`Edge`] is `nornir_graph::Edge<()>` — a `{ from, to, label }` struct rather
//! than the old bare `(String, String)` tuple, because the shared seam has to
//! carry a consumer-owned edge label for the consumers that have one. Release
//! edges are unlabelled, so the label is `()` and costs nothing; build one with
//! `Edge::new(from, to)`.
//!
//! # What was DELETED
//!
//! This module used to carry `cozo_stub` and `falkordb_stub` behind `cozo = []` /
//! `falkordb = []` features that pulled NO dependency: config-holder structs whose
//! `nodes()` / `edges()` bodies were `// TODO` comments over `Vec::new()`. They
//! could never report red — a graph with no nodes has no cycles, linearizes
//! trivially and has an empty closure, so every default method "passed" — and the
//! comment claiming cozo "fought the build" was wrong: it was cozo's `default`
//! feature (`compact` → `minimal`) dragging the bundled SQLite C stack, and
//! `default-features = false` fixes it.
//!
//! Both stubs are gone. [`nornir_graph`] has a REAL, tested CozoDB backend behind
//! its own off-by-default feature, checked against the in-memory one for identical
//! answers. There is no FalkorDB backend, deliberately: it needs a live
//! Redis-module server, and an absent backend is honest where a stub is not.
pub use nornir_graph::{BulkGraph as DepGraph, DepGraphError, PetGraph as PetDepGraph};
/// A directed publish-order edge, read as "`from` depends on `to`" ⇒ `to` publishes
/// first. Matches the `crate_deps` / `repo_edges` convention used across the doctor.
/// Release edges carry no label, hence `Edge<()>`.
pub type Edge = nornir_graph::Edge<()>;
#[cfg(test)]
mod tests {
use super::*;
use std::collections::BTreeSet;
/// A minimal `DepGraph` that implements ONLY the required pair, to prove the
/// default algorithms stand on `nodes`/`edges` alone (so any backend inherits
/// them for free).
struct RawGraph {
nodes: Vec<String>,
edges: Vec<Edge>,
}
impl DepGraph for RawGraph {
type Label = ();
fn nodes(&self) -> Vec<String> {
self.nodes.clone()
}
fn edges(&self) -> Vec<Edge> {
self.edges.clone()
}
}
fn s(x: &str) -> String {
x.to_string()
}
/// SCC over petgraph: a→b→c→a is one 3-cycle; d stands alone.
#[test]
fn scc_finds_the_cycle() {
let g = PetDepGraph::from_edges([("a", "b"), ("b", "c"), ("c", "a"), ("a", "d")]);
let scc = g.scc();
assert!(scc.contains(&vec![s("a"), s("b"), s("c")]), "cycle abc missing: {scc:?}");
assert!(scc.contains(&vec![s("d")]), "singleton d missing: {scc:?}");
assert_eq!(g.cycles(), vec![vec![s("a"), s("b"), s("c")]]);
}
/// Topo = deps first. DAG: a⇒{b,c}, b⇒d, c⇒d ⇒ d before b,c before a.
#[test]
fn topo_orders_deps_first() {
let g = PetDepGraph::from_edges([("a", "b"), ("a", "c"), ("b", "d"), ("c", "d")]);
let order = g.topo().expect("dag must linearize");
assert_eq!(order.len(), 4);
let pos = |n: &str| order.iter().position(|x| x == n).unwrap();
assert!(pos("d") < pos("b"), "d must precede b: {order:?}");
assert!(pos("d") < pos("c"), "d must precede c: {order:?}");
assert!(pos("b") < pos("a"), "b must precede a: {order:?}");
assert!(pos("c") < pos("a"), "c must precede a: {order:?}");
// Determinism: b before c (name tie-break on the ready frontier).
assert_eq!(order, vec![s("d"), s("b"), s("c"), s("a")]);
}
/// A cyclic graph has NO total order → the cycle surfaces as an error payload.
#[test]
fn topo_rejects_a_cycle() {
let g = PetDepGraph::from_edges([("a", "b"), ("b", "a"), ("c", "a")]);
match g.topo() {
Err(DepGraphError::Cycle(stuck)) => {
// a and b are on the cycle; c is gated behind it — none can emit.
assert!(stuck.contains(&s("a")) && stuck.contains(&s("b")), "stuck={stuck:?}");
}
other => panic!("expected a cycle error, got {other:?}"),
}
}
/// Bounded release closure: depth caps how far the dependency wavefront reaches.
#[test]
fn release_closure_is_depth_bounded() {
// a⇒{b,c}, b⇒d, c⇒d, d⇒e.
let g = PetDepGraph::from_edges([
("a", "b"),
("a", "c"),
("b", "d"),
("c", "d"),
("d", "e"),
]);
let set = |v: &[&str]| -> BTreeSet<String> { v.iter().map(|x| s(x)).collect() };
assert_eq!(g.release_closure(&[s("a")], Some(0)), set(&["a"]));
assert_eq!(g.release_closure(&[s("a")], Some(1)), set(&["a", "b", "c"]));
assert_eq!(g.release_closure(&[s("a")], Some(2)), set(&["a", "b", "c", "d"]));
assert_eq!(g.release_closure(&[s("a")], None), set(&["a", "b", "c", "d", "e"]));
// An unknown root contributes nothing.
assert!(g.release_closure(&[s("zzz")], None).is_empty());
}
/// The default methods must give identical answers whether the backend is
/// petgraph or a raw nodes/edges pair — proving the algorithms live ONCE.
#[test]
fn defaults_match_petgraph_backend() {
let edges = [("a", "b"), ("a", "c"), ("b", "d"), ("c", "d")];
let pet = PetDepGraph::from_edges(edges);
let raw = RawGraph {
nodes: vec![s("a"), s("b"), s("c"), s("d")],
edges: edges.iter().map(|(x, y)| Edge::new(*x, *y)).collect(),
};
assert_eq!(pet.scc(), raw.scc());
assert_eq!(pet.topo(), raw.topo());
assert_eq!(pet.release_closure(&[s("a")], None), raw.release_closure(&[s("a")], None));
// Applied output, so "they agree" is not "they are both empty".
assert_eq!(pet.topo().unwrap(), vec![s("d"), s("b"), s("c"), s("a")]);
}
}