crates/nornir-release-core/src/shadow_solve.rs
//! **`shadow_solve` — a non-destructive cross-check on the shipped publish order.**
//!
//! The release doctor derives the authoritative publish order the SAME way the real
//! `--execute` driver does: SCC condensation of the crate graph
//! ([`graph_math::condense`]) topo-sorted deps-first
//! ([`crate::doctor::global_crate_publish_order`]). That order SHIPS — nothing here
//! changes it.
//!
//! This module runs a SECOND, independent solver over the exact same member graph and
//! DIFFS its answer against the shipped order, so we can *learn where a constructive
//! solver would differ* before ever promoting it to primary. It reuses the two
//! constructive modules that already exist for exactly this reasoning:
//!
//! * [`depgraph_trait`](crate::depgraph_trait) — an INDEPENDENT linearization: a
//! `PetDepGraph` built from the same edges, ordered by its own Kahn `topo()` (a
//! different algorithm/module than the condensation topo the real order uses). Two
//! correct topological orders of the same DAG agree on every *comparable* pair, so
//! on a clean (publishable) graph this cross-check is silent — it only speaks when
//! the shadow solver **cannot linearize** members the shipped SCC-condensation
//! order placed (a real crate cycle), or when the shipped order **violates a
//! dependency edge** the independent solver honours (a would-be ordering bug).
//! * [`version_solve`](crate::version_solve) — the PubGrub-style interval CSP, run as
//! a constraint-satisfaction leg over the same `crate_dep_reqs`. Purely telemetry
//! here: a provably empty requirement intersection is recorded, never blocks.
//!
//! **Contract:** additive and non-fatal. `shadow_solve` NEVER changes the publish
//! order and NEVER fails a currently-green (publishable, DAG) release — agreement is
//! an info note; disagreement is a Warning that NAMES the divergent members and
//! defers to the shipped order. Pure (no I/O), deterministic (BTree/sorted).
//!
//! [`graph_math::condense`]: crate::graph_math::condense
use std::collections::{BTreeMap, BTreeSet};
use serde::Serialize;
use crate::depdag::crate_adjacency;
use crate::depgraph_trait::{DepGraph, DepGraphError, PetDepGraph};
use crate::graph_math::{self, Adj};
use crate::model::RepoGraph;
use crate::version_solve::{check_crate_constraints, constraints_from_graphs};
/// How the shadow (constructive) solver diverges from the shipped order.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize)]
pub enum DivergenceKind {
/// The independent Kahn solver could NOT linearize members the shipped
/// SCC-condensation order placed anyway — a real crate cycle. The shipped order
/// lumps the cycle's members (name-sorted) into one wave; the constructive solver
/// leaves them unplaced. The members are exactly the un-linearizable set.
Unlinearizable,
/// The two orders DISAGREE on a dependency edge: the shipped order sequences a
/// dependency AFTER its dependent (or fails to place one), which the independent
/// solver would not — a genuine ordering conflict on the named members.
OrderViolation,
}
impl DivergenceKind {
fn token(self) -> &'static str {
match self {
DivergenceKind::Unlinearizable => "unlinearizable",
DivergenceKind::OrderViolation => "order_violation",
}
}
}
/// One divergence between the shadow solver and the shipped order.
#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
pub struct Divergence {
pub kind: DivergenceKind,
/// The members the two solvers disagree on (sorted).
pub members: Vec<String>,
/// Human-readable why.
pub detail: String,
}
/// The shadow-solve cross-check report. `divergences` empty ⇒ the constructive solver
/// AGREES with the shipped order (an info note); non-empty ⇒ a non-fatal Warning that
/// names the divergent members. Either way the shipped order is authoritative.
#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize)]
pub struct ShadowSolveReport {
/// Number of publish units (crates) in the member graph.
pub member_count: usize,
/// The authoritative SHIPPED publish order (crate names, deps-first).
pub shipped_order: Vec<String>,
/// The SHADOW (independent Kahn) order; empty when the shadow solver could not
/// linearize the graph (a cycle) — see `shadow_cycle`.
pub shadow_order: Vec<String>,
/// Members the shadow solver could not place (a crate cycle + anything gated
/// behind it). Empty on a clean DAG.
pub shadow_cycle: Vec<String>,
/// The divergences found (empty ⇒ the solvers agree).
pub divergences: Vec<Divergence>,
/// version_solve (PubGrub CSP) leg: `true` when no provably-unsatisfiable
/// requirement intersection was found (telemetry only — never gates).
pub constraint_ok: bool,
/// Dep crate names version_solve flagged as having mutually exclusive
/// requirements (telemetry only).
pub constraint_conflicts: Vec<String>,
}
impl ShadowSolveReport {
/// True when the constructive solver AGREES with the shipped order.
#[must_use]
pub fn agree(&self) -> bool {
self.divergences.is_empty()
}
/// The union of every divergence's members (sorted, de-duplicated) — the payload
/// the Warning names.
#[must_use]
pub fn divergent_members(&self) -> Vec<String> {
let mut s: BTreeSet<String> = BTreeSet::new();
for d in &self.divergences {
for m in &d.members {
s.insert(m.clone());
}
}
s.into_iter().collect()
}
/// The NON-FATAL Warning line, or `None` when the solvers agree. Never blocks —
/// the shipped order stays authoritative.
#[must_use]
pub fn warning(&self) -> Option<String> {
if self.agree() {
return None;
}
Some(format!(
"⚠ SHADOW-SOLVE: the constructive cross-check (depgraph/version_solve) \
disagrees with the shipped publish order on: {} — shipped order kept \
authoritative (non-blocking).",
self.divergent_members().join(", "),
))
}
/// The info note emitted when the solvers agree (telemetry).
#[must_use]
pub fn info(&self) -> String {
format!(
"shadow-solve: constructive cross-check AGREES with the shipped order over \
{} member(s); divergence rate 0.0",
self.member_count,
)
}
/// Robot-observable introspection blob (LAW 6).
#[must_use]
pub fn state_json(&self) -> serde_json::Value {
serde_json::json!({
"member_count": self.member_count,
"agree": self.agree(),
"divergence_count": self.divergences.len(),
"divergent_members": self.divergent_members(),
"shipped_order": self.shipped_order,
"shadow_order": self.shadow_order,
"shadow_cycle": self.shadow_cycle,
"constraint_ok": self.constraint_ok,
"constraint_conflicts": self.constraint_conflicts,
"divergences": self.divergences.iter().map(|d| serde_json::json!({
"kind": d.kind.token(),
"members": d.members,
"detail": d.detail,
})).collect::<Vec<_>>(),
})
}
/// Printable one/two-line summary ("" is never returned — always at least the note).
#[must_use]
pub fn format(&self) -> String {
match self.warning() {
Some(w) => {
let mut s = w;
for d in &self.divergences {
s.push_str(&format!("\n · {}", d.detail));
}
s
}
None => self.info(),
}
}
}
/// The SHIPPED crate-level publish order — computed the SAME way the real
/// `--execute` driver does ([`crate::doctor::global_crate_publish_order`]): condense
/// the crate graph and topo-sort deps-first, expanding each component (a singleton
/// for a DAG; the entangled set for a cycle) into its name-sorted members.
#[must_use]
pub fn shipped_crate_order(graphs: &[RepoGraph]) -> Vec<String> {
let (_owner, adj) = crate_adjacency(graphs);
shipped_order_from_adj(&adj)
}
/// [`shipped_crate_order`] over a pre-built adjacency (the pure core — testable
/// without assembling `RepoGraph`s).
#[must_use]
pub fn shipped_order_from_adj(adj: &Adj) -> Vec<String> {
let cond = graph_math::condense(adj);
cond.topo_order()
.into_iter()
.flat_map(|c| cond.comps[c].clone())
.collect()
}
/// Run the shadow-solve cross-check for the whole constellation: derive the shipped
/// order the way the real driver does, then diff the independent constructive solvers
/// against it. Additive, non-fatal.
#[must_use]
pub fn shadow_solve(graphs: &[RepoGraph]) -> ShadowSolveReport {
let (_owner, adj) = crate_adjacency(graphs);
let shipped = shipped_order_from_adj(&adj);
let mut report = diff_orders(&shipped, &adj);
// version_solve (PubGrub interval CSP) leg — constraint SATISFACTION over the same
// per-consumer requirements. Telemetry only: a provably empty intersection is
// recorded, never a block (the graph_precheck/gate legs own hard refusal).
let constraints = constraints_from_graphs(graphs);
let conflicts = check_crate_constraints(&constraints, &BTreeMap::new());
report.constraint_conflicts = {
let mut v: Vec<String> = conflicts.iter().map(|c| c.dep.clone()).collect();
v.sort();
v.dedup();
v
};
report.constraint_ok = report.constraint_conflicts.is_empty();
report
}
/// The pure diff core: given the shipped order and the member adjacency, run the
/// INDEPENDENT Kahn linearization ([`PetDepGraph::topo`]) and compare. Returns a
/// report with `constraint_*` left at their defaults (filled by [`shadow_solve`]).
///
/// Divergence detection is edge-satisfaction based (robust to tie-breaks — two valid
/// topological orders of the same DAG agree on every comparable pair):
/// * **Unlinearizable** — the shadow solver returns a cycle; the un-placeable members
/// (which the shipped condensation order placed anyway) are the divergence.
/// * **OrderViolation** — for a dependency edge `from → to`, the shipped order and the
/// shadow order disagree on whether `to` precedes `from`. Zero on any pair of valid
/// topological orders; fires only if the shipped order itself violates an edge.
#[must_use]
pub fn diff_orders(shipped_order: &[String], adj: &Adj) -> ShadowSolveReport {
let member_count = adj.len();
// Independent constructive linearization over the SAME edges.
let mut g = PetDepGraph::new();
for n in adj.keys() {
g.add_node(n.clone());
}
for (from, tos) in adj {
for to in tos {
g.add_edge(from.clone(), to.clone());
}
}
let shipped_pos: BTreeMap<&str, usize> =
shipped_order.iter().enumerate().map(|(i, n)| (n.as_str(), i)).collect();
let mut divergences: Vec<Divergence> = Vec::new();
let (shadow_order, shadow_cycle) = match g.topo() {
Ok(order) => {
let shadow_pos: BTreeMap<&str, usize> =
order.iter().enumerate().map(|(i, n)| (n.as_str(), i)).collect();
// Compare edge satisfaction. `sat(order, from, to)` = both placed and the
// dependency `to` precedes its dependent `from`.
let sat = |pos: &BTreeMap<&str, usize>, from: &str, to: &str| -> bool {
match (pos.get(to), pos.get(from)) {
(Some(t), Some(f)) => t < f,
_ => false,
}
};
let mut bad: BTreeSet<String> = BTreeSet::new();
for (from, tos) in adj {
for to in tos {
let ship = sat(&shipped_pos, from, to);
let shadow = sat(&shadow_pos, from, to);
if ship != shadow {
bad.insert(from.clone());
bad.insert(to.clone());
}
}
}
if !bad.is_empty() {
let members: Vec<String> = bad.into_iter().collect();
divergences.push(Divergence {
detail: format!(
"the shipped order and the independent solver disagree on a \
dependency edge among: {}",
members.join(", "),
),
kind: DivergenceKind::OrderViolation,
members,
});
}
(order, Vec::new())
}
Err(DepGraphError::Cycle(stuck)) => {
// The constructive solver cannot linearize a real cycle; the shipped
// SCC-condensation order placed these members anyway (lumped in one wave).
divergences.push(Divergence {
detail: format!(
"the constructive solver could not linearize a dependency cycle the \
shipped condensation order placed: {}",
stuck.join(", "),
),
kind: DivergenceKind::Unlinearizable,
members: stuck.clone(),
});
(Vec::new(), stuck)
}
};
ShadowSolveReport {
member_count,
shipped_order: shipped_order.to_vec(),
shadow_order,
shadow_cycle,
divergences,
constraint_ok: true,
constraint_conflicts: Vec::new(),
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::collections::BTreeSet;
fn adj(pairs: &[(&str, &[&str])]) -> Adj {
pairs
.iter()
.map(|(n, ds)| (n.to_string(), ds.iter().map(|s| s.to_string()).collect::<BTreeSet<_>>()))
.collect()
}
/// AGREE fixture: a clean crate DAG (`app → lib → base`). The independent Kahn
/// solver produces a valid topological order that agrees with the shipped
/// condensation order on every dependency edge ⇒ NO divergence, NO Warning.
#[test]
fn agreeing_dag_yields_no_warning() {
let g = adj(&[("app", &["lib"]), ("lib", &["base"]), ("base", &[])]);
let shipped = shipped_order_from_adj(&g);
assert_eq!(shipped, vec!["base", "lib", "app"], "deps-first shipped order");
let report = diff_orders(&shipped, &g);
assert!(report.agree(), "clean DAG: the solvers agree");
assert!(report.warning().is_none(), "agreement is an info note, not a Warning");
assert!(report.divergent_members().is_empty());
assert_eq!(report.shadow_order, vec!["base", "lib", "app"]);
assert!(report.shadow_cycle.is_empty());
assert_eq!(report.state_json()["agree"], true);
nornir_testmatrix::functional_status(
"release-shadow-solve",
"agree_no_warning",
report.agree() && report.warning().is_none(),
"clean DAG: constructive cross-check agrees with the shipped order → no Warning",
);
}
/// A diamond (`app → {a,b} → base`) has tie-break freedom (a, b are incomparable),
/// yet the two valid topological orders STILL agree on every comparable pair ⇒ no
/// divergence. Guards against a naive sequence-equality diff that would flag the
/// harmless tie-break as a false divergence.
#[test]
fn tie_break_freedom_is_not_a_divergence() {
let g = adj(&[
("app", &["a", "b"]),
("a", &["base"]),
("b", &["base"]),
("base", &[]),
]);
let shipped = shipped_order_from_adj(&g);
let report = diff_orders(&shipped, &g);
assert!(report.agree(), "incomparable a,b tie-break is NOT a divergence");
assert!(report.warning().is_none());
}
/// RED-WHEN-BROKEN — DIVERGE fixture: a genuine crate cycle (`app ⇄ lib`). The
/// shipped condensation order lumps both into one wave and places them; the
/// independent constructive (Kahn) solver CANNOT linearize them ⇒ exactly one
/// divergence Warning that NAMES both members. If the cross-check ever stopped
/// catching a cycle the shipped order glossed over, this fails.
#[test]
fn cycle_fixture_diverges_with_one_warning() {
let g = adj(&[("app", &["lib"]), ("lib", &["app"])]);
let shipped = shipped_order_from_adj(&g);
// The shipped SCC-condensation order still lists both (lumped, name-sorted).
assert_eq!(shipped, vec!["app", "lib"]);
let report = diff_orders(&shipped, &g);
assert!(!report.agree(), "a cycle is a divergence");
assert_eq!(report.divergences.len(), 1, "exactly one divergence");
assert_eq!(report.divergences[0].kind, DivergenceKind::Unlinearizable);
assert_eq!(
report.divergent_members(),
vec!["app".to_string(), "lib".to_string()],
"the Warning names both cycle members",
);
let warn = report.warning().expect("a Warning must be surfaced");
assert!(warn.contains("app") && warn.contains("lib"));
assert!(report.shadow_order.is_empty(), "the shadow solver placed nothing");
assert_eq!(report.shadow_cycle, vec!["app".to_string(), "lib".to_string()]);
nornir_testmatrix::functional_status(
"release-shadow-solve",
"cycle_one_warning",
report.divergences.len() == 1
&& report.divergent_members() == vec!["app".to_string(), "lib".to_string()],
"crate cycle app⇄lib → exactly one divergence Warning naming both members",
);
}
/// RED-WHEN-BROKEN — a shipped order that VIOLATES a dependency edge (dependency
/// sequenced AFTER its dependent) is caught by the independent solver even though
/// the graph is a clean DAG. Guards the "shipped order is wrong" path distinct from
/// the cycle path.
#[test]
fn wrong_shipped_order_is_flagged() {
let g = adj(&[("app", &["lib"]), ("lib", &["base"]), ("base", &[])]);
// A DELIBERATELY WRONG shipped order: app before its dep lib.
let wrong = vec!["app".to_string(), "lib".to_string(), "base".to_string()];
let report = diff_orders(&wrong, &g);
assert!(!report.agree(), "a dependency-violating shipped order diverges");
assert_eq!(report.divergences[0].kind, DivergenceKind::OrderViolation);
assert!(report.divergent_members().contains(&"app".to_string()));
assert!(report.divergent_members().contains(&"lib".to_string()));
// The independent solver itself is correct (deps-first).
assert_eq!(report.shadow_order, vec!["base", "lib", "app"]);
}
/// End-to-end over `RepoGraph`s: a clean cross-repo chain agrees, and the
/// version_solve (PubGrub CSP) leg runs clean (no mutually-exclusive requirements).
#[test]
fn shadow_solve_over_repographs_agrees_and_runs_csp() {
let mut a = RepoGraph { repo: "A".into(), ..Default::default() };
a.crate_deps.entry("app".into()).or_default().insert("lib".into());
let mut b = RepoGraph { repo: "B".into(), ..Default::default() };
b.crate_deps.entry("lib".into()).or_default().insert("base".into());
let mut c = RepoGraph { repo: "C".into(), ..Default::default() };
c.crate_deps.entry("base".into()).or_default();
let report = shadow_solve(&[a, b, c]);
assert_eq!(report.member_count, 3);
assert!(report.agree(), "clean chain agrees");
assert!(report.constraint_ok, "no conflicting requirements");
assert!(report.constraint_conflicts.is_empty());
}
/// The version_solve leg surfaces a mutually-exclusive requirement pair as
/// telemetry WITHOUT ever creating a divergence (constraint conflicts are the CSP
/// leg's business; they never block or flip `agree`).
#[test]
fn constraint_conflict_is_telemetry_not_a_divergence() {
let mut g = RepoGraph { repo: "edda".into(), ..Default::default() };
// Two consumers pin the same dep to disjoint majors → EmptyIntersection.
g.crate_deps.entry("skade".into()).or_default().insert("edda".into());
g.crate_deps.entry("holger".into()).or_default().insert("edda".into());
g.crate_deps.entry("edda".into()).or_default();
let mut r1 = BTreeMap::new();
r1.insert("edda".to_string(), BTreeSet::from(["^1".to_string()]));
g.crate_dep_reqs.insert("skade".to_string(), r1);
let mut r2 = BTreeMap::new();
r2.insert("edda".to_string(), BTreeSet::from(["^2".to_string()]));
g.crate_dep_reqs.insert("holger".to_string(), r2);
let report = shadow_solve(&[g]);
assert!(report.agree(), "a version conflict is NOT an ordering divergence");
assert!(!report.constraint_ok, "the CSP leg flags the conflict");
assert_eq!(report.constraint_conflicts, vec!["edda".to_string()]);
nornir_testmatrix::functional_status(
"release-shadow-solve",
"csp_conflict_telemetry",
report.agree() && report.constraint_conflicts == vec!["edda".to_string()],
"mutually-exclusive requirement pair is CSP telemetry, never an ordering divergence",
);
}
}