crates/nornir-release-core/src/graph_diff.rs
//! Before/after dependency-graph **DIFF** — the release-time delta artifact.
//!
//! # What this is
//!
//! A release changes the constellation's dependency graph: crates get bumped, new
//! members appear, dead ones drop, and edges (`from` depends-on `to`, at a semver
//! `req`) are added / removed / retargeted. This module captures TWO snapshots of
//! that graph — a `before` and an `after` — and computes their [`GraphDiff`]: the
//! added / removed / **bumped** nodes and the added / removed / **changed** edges.
//!
//! Two consumers read the same diff:
//!
//! * a **serde artifact** ([`GraphDiff`] + [`DepGraphSnapshot`]) — the whole delta as
//! one JSON blob a release report / the dwarven UI graph-diff view renders; and
//! * two **warehouse-table POD shapes** — [`SemverDiffRow`] rows for the
//! [`TABLE_SEMVER_DIFFS`] table (one per node add/remove/bump, with the classified
//! [`BumpKind`]) and [`DepGraphEdgeRow`] rows for [`TABLE_DEP_GRAPH_EDGES`] (one per
//! edge add/remove/req-change), so a SQL reader can query "what semver-major bumps
//! did release R ship?" or "which edges changed?" without re-deriving the diff.
//!
//! # Pure, no live warehouse (by design)
//!
//! Everything here is a pure function over the two POD snapshots — no `&dyn
//! Warehouse`, no cargo probe, no network. The POD rows are the SHAPE destined for
//! the two tables (the row structs a writer would build an Arrow batch from), not a
//! writer; wiring them onto the [`nornir_warehouse_trait::Warehouse`] `append_arrow`
//! seam sits ABOVE this module (exactly as [`release_changes`](super::release_changes)
//! writes its own PODs) and is intentionally out of scope, so the diff core is
//! golden-testable on fixtures with zero I/O. Deterministic: every collection is
//! `BTreeMap`/`BTreeSet`-ordered.
//!
//! # Reuse, not a twin (LAW)
//!
//! This is the DELTA between two already-assembled graphs; it does not re-implement
//! the graph assembly ([`depdag`](super::depdag)) or the graph theory
//! ([`graph_math`](crate::graph_math)). It reasons over neutral `(name, version)` /
//! `(from, to, req)` PODs, so either the crate-level [`crate::depdag::ReleaseDepDag`] or a
//! raw `cargo metadata` snapshot can be lowered into a [`DepGraphSnapshot`] and
//! diffed by the same core.
use std::collections::BTreeMap;
use serde::{Deserialize, Serialize};
use crate::graph_math;
/// The `semver_diffs` warehouse table — one row per node add / remove / bump in a
/// release's before→after graph, carrying the classified [`BumpKind`].
pub const TABLE_SEMVER_DIFFS: &str = "semver_diffs";
/// The `dep_graph_edges` warehouse table — one row per edge add / remove / req-change
/// in a release's before→after graph.
pub const TABLE_DEP_GRAPH_EDGES: &str = "dep_graph_edges";
/// One crate node in a captured graph snapshot: a publish unit at a concrete version.
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
pub struct GraphNode {
/// Crate name (the node key).
pub name: String,
/// The crate's version in this snapshot (`Cargo.toml` `version`).
pub version: String,
}
impl GraphNode {
/// Convenience constructor.
pub fn new(name: impl Into<String>, version: impl Into<String>) -> Self {
Self { name: name.into(), version: version.into() }
}
}
/// One directed depends-on edge: `from` depends on `to` at semver requirement `req`.
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
pub struct GraphEdge {
/// The dependent crate.
pub from: String,
/// The depended-on crate.
pub to: String,
/// The semver requirement string justifying the edge (e.g. `"^1.2"`). Empty when
/// the snapshot carries structure only.
#[serde(default)]
pub req: String,
}
impl GraphEdge {
/// Convenience constructor.
pub fn new(from: impl Into<String>, to: impl Into<String>, req: impl Into<String>) -> Self {
Self { from: from.into(), to: to.into(), req: req.into() }
}
/// The `(from, to)` identity of an edge (its key across a diff — the `req` is the
/// mutable attribute, not part of the identity).
fn key(&self) -> (String, String) {
(self.from.clone(), self.to.clone())
}
}
/// A captured before/after snapshot of the release dependency graph — the diff input.
#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize, Deserialize)]
pub struct DepGraphSnapshot {
/// The crate nodes (one per publish unit).
pub nodes: Vec<GraphNode>,
/// The depends-on edges.
pub edges: Vec<GraphEdge>,
}
impl DepGraphSnapshot {
/// name → version index (last write wins on a duplicate name — a snapshot should
/// not carry one, but the index stays total).
fn node_index(&self) -> BTreeMap<String, String> {
self.nodes.iter().map(|n| (n.name.clone(), n.version.clone())).collect()
}
/// `(from, to)` → req index.
fn edge_index(&self) -> BTreeMap<(String, String), String> {
self.edges.iter().map(|e| (e.key(), e.req.clone())).collect()
}
/// Lower this snapshot to the neutral `node → deps` adjacency
/// ([`graph_math::Adj`], where `A→B` reads "A depends on B"). Every node is seeded
/// as a key so an isolated crate (no edges) still participates in the waves.
fn adjacency(&self) -> graph_math::Adj {
let mut adj: graph_math::Adj = BTreeMap::new();
for n in &self.nodes {
adj.entry(n.name.clone()).or_default();
}
for e in &self.edges {
adj.entry(e.from.clone()).or_default().insert(e.to.clone());
adj.entry(e.to.clone()).or_default();
}
adj
}
/// The deps-first PUBLISH WAVES of this snapshot — the parallelizable antichains of
/// the graph's SCC-condensation ([`graph_math::Condensation::waves`]). Wave 0 is the
/// crates that depend on nothing (publishable immediately); each later wave depends
/// only on earlier ones. Deterministic. REUSES `graph_math` — no wave logic twinned
/// here.
pub fn publish_waves(&self) -> Vec<Vec<String>> {
graph_math::condense(&self.adjacency()).waves()
}
/// Build a snapshot from the release [`RepoGraph`](crate::model::RepoGraph)
/// facts + a `name → version` map. Nodes are the PRODUCED crates (every `crate_deps`
/// key across the graphs), versioned from `versions` (a crate absent from the map gets
/// `"0.0.0"` — an explicit UNKNOWN, never silently a real version). Edges are the
/// in-workspace `consumer → dep` order-gating edges among produced crates, with the
/// requirement taken from `crate_dep_reqs` (`*` when the per-consumer requirement is
/// not recorded). Pure — REUSES the same produced-crate / edge granularity as
/// [`datalog::ReleaseFacts`](crate::release_doctor::datalog::ReleaseFacts) and `depdag`,
/// so the graph-diff sees exactly the crates the publish plan orders.
pub fn from_repo_graphs(
graphs: &[crate::model::RepoGraph],
versions: &BTreeMap<String, String>,
) -> Self {
let produced: std::collections::BTreeSet<String> =
graphs.iter().flat_map(|g| g.crate_deps.keys().cloned()).collect();
let mut nodes: Vec<GraphNode> = produced
.iter()
.map(|c| {
GraphNode::new(
c.clone(),
versions.get(c).cloned().unwrap_or_else(|| "0.0.0".to_string()),
)
})
.collect();
nodes.sort_by(|a, b| a.name.cmp(&b.name));
let mut edge_set: BTreeMap<(String, String), String> = BTreeMap::new();
for g in graphs {
for (c, deps) in &g.crate_deps {
for d in deps {
if d == c || !produced.contains(d) {
continue;
}
let req = g
.crate_dep_reqs
.get(c)
.and_then(|m| m.get(d))
.and_then(|s| s.iter().next().cloned())
.unwrap_or_else(|| "*".to_string());
edge_set.entry((c.clone(), d.clone())).or_insert(req);
}
}
}
let edges = edge_set
.into_iter()
.map(|((from, to), req)| GraphEdge::new(from, to, req))
.collect();
Self { nodes, edges }
}
}
/// How big a version jump a node bump is — classified from the parsed
/// `major.minor.patch` cores. `Other` covers a downgrade, a metadata-only change
/// (e.g. `1.0` → `1.0.0`), or an unparseable version on either side (never silently
/// mislabelled as a real bump).
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum BumpKind {
/// Major component increased (a breaking release).
Major,
/// Minor component increased (major equal).
Minor,
/// Patch component increased (major + minor equal).
Patch,
/// Not a forward `major.minor.patch` step (downgrade / metadata / unparseable).
Other,
}
impl BumpKind {
/// Stable lowercase token for the warehouse `bump` column + JSON.
pub fn as_str(self) -> &'static str {
match self {
BumpKind::Major => "major",
BumpKind::Minor => "minor",
BumpKind::Patch => "patch",
BumpKind::Other => "other",
}
}
}
/// A node whose version changed between the two snapshots.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct NodeBump {
/// Crate name.
pub name: String,
/// Version in the `before` snapshot.
pub old_version: String,
/// Version in the `after` snapshot.
pub new_version: String,
/// The classified size of the bump.
pub kind: BumpKind,
}
/// An edge that survived across the diff but whose semver `req` was retargeted.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct EdgeReqChange {
/// The dependent crate.
pub from: String,
/// The depended-on crate.
pub to: String,
/// The requirement in the `before` snapshot.
pub old_req: String,
/// The requirement in the `after` snapshot.
pub new_req: String,
}
/// The before→after dependency-graph DIFF: the whole serde artifact. Every vector is
/// sorted deterministically.
#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize, Deserialize)]
pub struct GraphDiff {
/// Nodes present in `after` but not `before`.
pub added_nodes: Vec<GraphNode>,
/// Nodes present in `before` but not `after`.
pub removed_nodes: Vec<GraphNode>,
/// Nodes present in both with a changed version.
pub bumped_nodes: Vec<NodeBump>,
/// Edges present in `after` but not `before`.
pub added_edges: Vec<GraphEdge>,
/// Edges present in `before` but not `after`.
pub removed_edges: Vec<GraphEdge>,
/// Edges present in both (same `from`/`to`) with a changed `req`.
pub changed_edges: Vec<EdgeReqChange>,
}
impl GraphDiff {
/// Compute the diff `before` → `after`. Nodes are keyed by name, edges by
/// `(from, to)`; the `version` / `req` are the mutable attributes compared within
/// a surviving key.
pub fn between(before: &DepGraphSnapshot, after: &DepGraphSnapshot) -> Self {
let before_nodes = before.node_index();
let after_nodes = after.node_index();
let before_edges = before.edge_index();
let after_edges = after.edge_index();
let mut added_nodes = Vec::new();
let mut bumped_nodes = Vec::new();
for (name, new_version) in &after_nodes {
match before_nodes.get(name) {
None => added_nodes.push(GraphNode::new(name.clone(), new_version.clone())),
Some(old_version) if old_version != new_version => bumped_nodes.push(NodeBump {
name: name.clone(),
old_version: old_version.clone(),
new_version: new_version.clone(),
kind: classify_bump(old_version, new_version),
}),
Some(_) => {}
}
}
let removed_nodes = before_nodes
.iter()
.filter(|(name, _)| !after_nodes.contains_key(*name))
.map(|(name, version)| GraphNode::new(name.clone(), version.clone()))
.collect();
let mut added_edges = Vec::new();
let mut changed_edges = Vec::new();
for ((from, to), new_req) in &after_edges {
match before_edges.get(&(from.clone(), to.clone())) {
None => added_edges.push(GraphEdge::new(from.clone(), to.clone(), new_req.clone())),
Some(old_req) if old_req != new_req => changed_edges.push(EdgeReqChange {
from: from.clone(),
to: to.clone(),
old_req: old_req.clone(),
new_req: new_req.clone(),
}),
Some(_) => {}
}
}
let removed_edges = before_edges
.iter()
.filter(|(key, _)| !after_edges.contains_key(*key))
.map(|((from, to), req)| GraphEdge::new(from.clone(), to.clone(), req.clone()))
.collect();
Self { added_nodes, removed_nodes, bumped_nodes, added_edges, removed_edges, changed_edges }
}
/// True when the two snapshots are graph-equal (no node or edge delta).
pub fn is_empty(&self) -> bool {
self.added_nodes.is_empty()
&& self.removed_nodes.is_empty()
&& self.bumped_nodes.is_empty()
&& self.added_edges.is_empty()
&& self.removed_edges.is_empty()
&& self.changed_edges.is_empty()
}
/// Total node changes (added + removed + bumped).
pub fn node_change_count(&self) -> usize {
self.added_nodes.len() + self.removed_nodes.len() + self.bumped_nodes.len()
}
/// Total edge changes (added + removed + changed).
pub fn edge_change_count(&self) -> usize {
self.added_edges.len() + self.removed_edges.len() + self.changed_edges.len()
}
/// Lower the node deltas into [`SemverDiffRow`]s for the [`TABLE_SEMVER_DIFFS`]
/// table — one row per added / removed / bumped node, grouped under `diff_id`.
pub fn semver_diff_rows(&self, diff_id: &str) -> Vec<SemverDiffRow> {
let mut rows = Vec::new();
for n in &self.added_nodes {
rows.push(SemverDiffRow {
diff_id: diff_id.to_string(),
crate_name: n.name.clone(),
change: "added".into(),
old_version: String::new(),
new_version: n.version.clone(),
bump: String::new(),
});
}
for n in &self.removed_nodes {
rows.push(SemverDiffRow {
diff_id: diff_id.to_string(),
crate_name: n.name.clone(),
change: "removed".into(),
old_version: n.version.clone(),
new_version: String::new(),
bump: String::new(),
});
}
for b in &self.bumped_nodes {
rows.push(SemverDiffRow {
diff_id: diff_id.to_string(),
crate_name: b.name.clone(),
change: "bumped".into(),
old_version: b.old_version.clone(),
new_version: b.new_version.clone(),
bump: b.kind.as_str().to_string(),
});
}
rows.sort();
rows
}
/// Lower the edge deltas into [`DepGraphEdgeRow`]s for the
/// [`TABLE_DEP_GRAPH_EDGES`] table — one row per added / removed / changed edge,
/// grouped under `diff_id`.
pub fn dep_graph_edge_rows(&self, diff_id: &str) -> Vec<DepGraphEdgeRow> {
let mut rows = Vec::new();
for e in &self.added_edges {
rows.push(DepGraphEdgeRow {
diff_id: diff_id.to_string(),
from_crate: e.from.clone(),
to_crate: e.to.clone(),
change: "added".into(),
old_req: String::new(),
new_req: e.req.clone(),
});
}
for e in &self.removed_edges {
rows.push(DepGraphEdgeRow {
diff_id: diff_id.to_string(),
from_crate: e.from.clone(),
to_crate: e.to.clone(),
change: "removed".into(),
old_req: e.req.clone(),
new_req: String::new(),
});
}
for c in &self.changed_edges {
rows.push(DepGraphEdgeRow {
diff_id: diff_id.to_string(),
from_crate: c.from.clone(),
to_crate: c.to.clone(),
change: "changed".into(),
old_req: c.old_req.clone(),
new_req: c.new_req.clone(),
});
}
rows.sort();
rows
}
/// The robot-observable introspection blob (LAW 6): the change tallies + the two
/// POD row sets, so a UI / test can assert the whole diff from one value.
pub fn state_json(&self, diff_id: &str) -> serde_json::Value {
serde_json::json!({
"diff_id": diff_id,
"empty": self.is_empty(),
"node_change_count": self.node_change_count(),
"edge_change_count": self.edge_change_count(),
"added_nodes": self.added_nodes,
"removed_nodes": self.removed_nodes,
"bumped_nodes": self.bumped_nodes,
"added_edges": self.added_edges,
"removed_edges": self.removed_edges,
"changed_edges": self.changed_edges,
"semver_diffs": self.semver_diff_rows(diff_id),
"dep_graph_edges": self.dep_graph_edge_rows(diff_id),
})
}
}
/// One row of the `semver_diffs` warehouse table (the SHAPE, not a writer): a single
/// node add / remove / bump in a release's before→after graph.
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
pub struct SemverDiffRow {
/// Groups all rows of one before/after diff (a release-run / snapshot-pair id).
pub diff_id: String,
/// The crate this row is about.
pub crate_name: String,
/// `"added" | "removed" | "bumped"`.
pub change: String,
/// Version before (`""` for an added crate).
pub old_version: String,
/// Version after (`""` for a removed crate).
pub new_version: String,
/// The [`BumpKind`] token for a `bumped` row (`""` for add / remove).
pub bump: String,
}
/// One row of the `dep_graph_edges` warehouse table (the SHAPE, not a writer): a
/// single edge add / remove / req-change in a release's before→after graph.
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
pub struct DepGraphEdgeRow {
/// Groups all rows of one before/after diff.
pub diff_id: String,
/// The dependent crate.
pub from_crate: String,
/// The depended-on crate.
pub to_crate: String,
/// `"added" | "removed" | "changed"`.
pub change: String,
/// Requirement before (`""` for an added edge).
pub old_req: String,
/// Requirement after (`""` for a removed edge).
pub new_req: String,
}
/// Parse the `major.minor.patch` core of a version (pre-release / build metadata after
/// the first `-` or `+` is dropped). Missing minor/patch default to `0`. Returns
/// `None` when the major (or a present minor/patch) is not a plain integer, so an
/// unparseable version can never be mislabelled as a real bump.
fn parse_core(v: &str) -> Option<(u64, u64, u64)> {
let core = v.trim().split(['-', '+']).next().unwrap_or("").trim();
let mut it = core.split('.');
let major = it.next()?.trim().parse().ok()?;
let minor = match it.next() {
Some(s) => s.trim().parse().ok()?,
None => 0,
};
let patch = match it.next() {
Some(s) => s.trim().parse().ok()?,
None => 0,
};
Some((major, minor, patch))
}
/// Classify a version change as [`BumpKind`]. Only a strictly-forward
/// `major.minor.patch` step is a real bump; everything else (downgrade, equal core,
/// unparseable) is [`BumpKind::Other`].
pub fn classify_bump(old: &str, new: &str) -> BumpKind {
match (parse_core(old), parse_core(new)) {
(Some(o), Some(n)) if n > o => {
if n.0 != o.0 {
BumpKind::Major
} else if n.1 != o.1 {
BumpKind::Minor
} else {
BumpKind::Patch
}
}
_ => BumpKind::Other,
}
}