crates/nornir-depgraph/src/lib.rs
//! Cross-repo dependency graph — the shared **depgraph core** for a nordisk
//! suite, lifted out of nornir so nornir AND dwarves render the same dependency
//! view. Pure: no warehouse, no egui.
//!
//! * **Compute** — for every repo, learn what it `produces` (workspace member
//! crate names) and `consumes` (external dep names), via `cargo_metadata`
//! ([`inspect_repo`]) or by parsing the manifests directly
//! ([`WorkspaceGraph::build_from_members`], no subprocess). For each pair
//! `(A, B)` add an edge `A → B` justified by `A.consumes ∩ B.produces`;
//! petgraph then gives the build order.
//! * **Query** — [`WorkspaceGraph`] answers deps/dependents, transitive
//! closures, blast radius, dep paths, and external-dep users.
//! * **Layout** — [`layout::DepGraphLayout`] lays the graph out for the
//! dependency VIEW (columns, transitive closure, collapse), egui-free and
//! `state_json`-introspectable.
//!
//! A [`DepGraphSnapshot`] is the immutable historical artefact a consumer
//! (nornir's suite warehouse) persists; this crate defines the data type, not
//! the warehouse I/O — that stays with whoever owns the warehouse.
use std::collections::{BTreeMap, BTreeSet};
use std::path::{Path, PathBuf};
use anyhow::{anyhow, Context, Result};
use cargo_metadata::MetadataCommand;
use chrono::{DateTime, Utc};
use petgraph::algo::toposort;
use petgraph::graph::{DiGraph, NodeIndex};
use uuid::Uuid;
pub mod funcgraph;
pub mod layout;
pub mod selftest;
/// The dependency table a cross-repo edge was declared in. PUBLISH ORDER is gated
/// by `Normal`+`Build` only — a `cargo publish` needs a crate's normal/build deps
/// on crates.io first, but NOT its dev-deps. `Dev` edges are still recorded (useful
/// for blast-radius / "who tests against whom") but EXCLUDED from topo ordering.
/// Master-of-deps points #1/#2.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq, PartialOrd, Ord, serde::Serialize, serde::Deserialize)]
pub enum DepKind {
#[default]
Normal,
Build,
Dev,
}
impl DepKind {
/// Parse the persisted/string form (`"dev"`/`"build"`/anything→Normal).
pub fn from_str_lenient(s: &str) -> Self {
match s {
"dev" => DepKind::Dev,
"build" => DepKind::Build,
_ => DepKind::Normal,
}
}
/// The persisted/string form.
pub fn as_str(self) -> &'static str {
match self {
DepKind::Normal => "normal",
DepKind::Build => "build",
DepKind::Dev => "dev",
}
}
/// Whether this edge gates publish order (Normal/Build yes, Dev no).
pub fn is_order_gating(self) -> bool {
!matches!(self, DepKind::Dev)
}
}
#[derive(Debug, Clone, Default)]
pub struct RepoFacts {
pub name: String,
pub root: PathBuf,
pub produces: BTreeSet<String>,
/// Every crate name this repo consumes (ALL dep kinds), for external-dep
/// queries / blast radius.
pub consumes: BTreeSet<String>,
/// Crate names this repo consumes ONLY through `[dev-dependencies]` tables (no
/// member declares them as a normal/build dep). These seed `Dev`-kind edges —
/// the repo-level edge is `Normal` if ANY member has a non-dev edge to the
/// producer (master-of-deps point #8).
pub dev_only_consumes: BTreeSet<String>,
}
#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
pub struct CrossRepoEdge {
pub from: String,
pub to: String,
/// Crate names that justify this edge — `from` consumes these,
/// `to` produces them.
pub via: BTreeSet<String>,
/// Which dependency table this edge came from. `Dev` edges are NOT publish-order
/// gating. Defaults to `Normal` for snapshots/wire payloads written before kinds
/// were tracked (`#[serde(default)]`), so old data degrades safely.
#[serde(default)]
pub kind: DepKind,
}
impl CrossRepoEdge {
/// A `Normal`-kind edge (the common case + back-compat for call sites that
/// don't distinguish kinds, e.g. viz layout / synthetic test graphs).
pub fn normal(from: impl Into<String>, to: impl Into<String>, via: BTreeSet<String>) -> Self {
Self { from: from.into(), to: to.into(), via, kind: DepKind::Normal }
}
}
// (serde derives below enable wire transport of dep-graph snapshots for the
// viz `Viz.Timeline` RPC; the iceberg row mapping is hand-written, not serde.)
#[derive(Debug)]
pub struct WorkspaceGraph {
pub facts: BTreeMap<String, RepoFacts>,
pub edges: Vec<CrossRepoEdge>,
inner: DiGraph<String, usize>,
}
impl WorkspaceGraph {
/// Build a **query-only** graph straight from `edges` (and optional `facts`),
/// bypassing `cargo_metadata`. `inner` is left empty, so build-order/topo is
/// unavailable; the dependency-query methods (`deps_transitive`, `dep_path`,
/// `dependents_*`, …), which read `edges`, work. Used by `regression::trace`
/// to rank suspects off a recorded dep-graph snapshot.
pub fn from_query_parts(facts: BTreeMap<String, RepoFacts>, edges: Vec<CrossRepoEdge>) -> Self {
Self { facts, edges, inner: DiGraph::new() }
}
/// Build the cross-repo graph from a member→checkout-path map **without any
/// `cargo metadata` subprocess** — parse each member's `Cargo.toml`(s)
/// directly (the `toml` crate), in PARALLEL (tiny files, one worker per core).
/// Workspace-aware: a member that is itself a cargo workspace contributes
/// every member crate it declares. A member whose manifest is missing or
/// unparseable is **SKIPPED** (logged), never fatal to the whole graph — the
/// fix for one bad manifest (e.g. facett) sinking the entire republish.
///
/// Produces the SAME [`WorkspaceGraph`] structure as [`build`] (same
/// `produces`/`consumes` facts → same name-intersection edges), so
/// `affected_set`, `record_dep_graph`, and the disjoint-name check are
/// unchanged. This is the republish hot path's graph builder.
pub fn build_from_members(resolved: &BTreeMap<String, PathBuf>) -> Result<Self> {
let entries: Vec<(String, PathBuf)> =
resolved.iter().map(|(n, p)| (n.clone(), p.clone())).collect();
let parsed = parallel_map(&entries, |(name, root)| {
match inspect_repo_manifests(name, root) {
Ok(f) => Some(f),
Err(e) => {
eprintln!(
"nornir: dep-graph: skipping member `{name}` — manifest parse failed: {e:#}"
);
None
}
}
});
let mut facts: BTreeMap<String, RepoFacts> = BTreeMap::new();
for f in parsed.into_iter().flatten() {
facts.insert(f.name.clone(), f);
}
Self::from_facts(facts)
}
/// Assemble the petgraph + cross-repo edges from already-gathered `facts` —
/// the half shared by [`build`] (cargo-metadata facts) and
/// [`build_from_members`] (direct-manifest facts). For each pair `(A, B)` an
/// edge `A → B` is added justified by `A.consumes ∩ B.produces`. The
/// disjoint-produced-crate-name invariant is enforced here.
pub fn from_facts(facts: BTreeMap<String, RepoFacts>) -> Result<Self> {
// Inverse index: producing-crate-name → owning repo name. A crate name
// produced by MORE THAN ONE repo is AMBIGUOUS — it cannot unambiguously
// justify a cross-repo edge (which repo is the producer?), so it is dropped
// from the index rather than failing the WHOLE graph. This is the real
// nordisk shape: a convention crate like `xtask` (a build-tool bin present
// in every repo) is produced by 7 repos; hard-erroring on it zeroed out
// EVERY cross-repo edge (deps/dependents/build-order all empty). Each repo
// still keeps such a crate as its own local crate; it just can't source a
// cross-repo dependency edge. (Repos SHOULD also mark these `publish = false`
// so they never reach `produces` at all — but the graph must be robust to it.)
let mut producer: BTreeMap<&str, &str> = BTreeMap::new();
let mut ambiguous: BTreeSet<&str> = BTreeSet::new();
for f in facts.values() {
for c in &f.produces {
match producer.insert(c.as_str(), f.name.as_str()) {
Some(prev) if prev != f.name => {
ambiguous.insert(c.as_str());
}
_ => {}
}
}
}
for c in &ambiguous {
producer.remove(c);
eprintln!(
"nornir: dep-graph: crate `{c}` is produced by multiple repos — ambiguous, \
excluded from cross-repo edge resolution (kept as a local crate per repo)"
);
}
let mut edges: Vec<CrossRepoEdge> = Vec::new();
let mut inner: DiGraph<String, usize> = DiGraph::new();
let mut indices: BTreeMap<String, NodeIndex> = BTreeMap::new();
for name in facts.keys() {
indices.insert(name.clone(), inner.add_node(name.clone()));
}
for from_facts in facts.values() {
let mut grouped: BTreeMap<&str, BTreeSet<String>> = BTreeMap::new();
for consumed in &from_facts.consumes {
if let Some(&owner) = producer.get(consumed.as_str()) {
if owner != from_facts.name {
grouped.entry(owner).or_default().insert(consumed.clone());
}
}
}
for (to_name, via) in grouped {
// Repo-level edge KIND: `Dev` only when EVERY justifying crate is
// consumed solely through a `[dev-dependencies]` table — if ANY via
// crate is a normal/build dep, the edge is order-gating `Normal`
// (master-of-deps point #8: the normal edge wins for ordering).
let kind = if via.iter().all(|c| from_facts.dev_only_consumes.contains(c)) {
DepKind::Dev
} else {
DepKind::Normal
};
// ORDERING graph (`inner`): non-dev edges only, so the dev back-edges
// (xtask/bench → nornir) never create a false cycle / mis-order.
if kind.is_order_gating() {
let weight = via.len();
inner.add_edge(indices[&from_facts.name], indices[to_name], weight);
}
edges.push(CrossRepoEdge {
from: from_facts.name.clone(),
to: to_name.to_string(),
via,
kind,
});
}
}
Ok(Self { facts, edges, inner })
}
/// Topological build order: dependencies first, consumers last.
/// Errors if the cross-repo graph has a cycle.
///
/// When `inner` (the petgraph built by [`build`](Self::build)) is empty —
/// the case for a graph rebuilt from the warehouse's `dep_graph_edges` via
/// [`from_query_parts`](Self::from_query_parts), which never runs
/// `cargo metadata` — fall back to an edge-based topological sort over
/// [`component_names`](Self::component_names). The warehouse snapshot carries
/// the cross-repo edges, so build order is fully recoverable from them; this
/// is what makes `build_order` non-empty for monitored multi-repo workspaces
/// (e.g. `nordisk`) where the descriptor/`cargo metadata` path is unavailable.
pub fn build_order(&self) -> Result<Vec<String>> {
if self.inner.node_count() == 0 {
// Edge-based path: deterministic topo over the known components.
// `topo_order_from_edges` already uses the deps-first convention
// (it inverts the consumer→producer edges internally).
let repos = self.component_names();
return Ok(topo_order_from_edges(&repos, &self.edges));
}
// petgraph's toposort returns sources (in-degree 0) first.
// Our edges point consumer → producer, so the "source" is a
// top-level consumer; reverse to get deps-first.
let order = toposort(&self.inner, None).map_err(|cyc| {
anyhow!(
"cross-repo dependency cycle detected at node `{}`",
self.inner[cyc.node_id()]
)
})?;
Ok(order.into_iter().rev().map(|n| self.inner[n].clone()).collect())
}
/// Every component (repo) the graph knows about — the union of the `facts`
/// keys and the edge endpoints. A graph built via [`from_query_parts`] from
/// a recorded snapshot has empty `facts` but real `edges`, so callers that
/// need the node set (the funnel planner's component list / validation) must
/// use this rather than `facts.keys()`. Sorted, deduped, empty names dropped.
pub fn component_names(&self) -> Vec<String> {
let mut set: BTreeSet<String> = self.facts.keys().cloned().collect();
for e in &self.edges {
if !e.from.is_empty() {
set.insert(e.from.clone());
}
if !e.to.is_empty() {
set.insert(e.to.clone());
}
}
set.into_iter().collect()
}
/// True when `repo` is a known component (in `facts` or as an edge
/// endpoint). See [`component_names`](Self::component_names).
pub fn has_component(&self, repo: &str) -> bool {
self.facts.contains_key(repo)
|| self.edges.iter().any(|e| e.from == repo || e.to == repo)
}
pub fn dependencies_of(&self, repo: &str) -> Vec<&CrossRepoEdge> {
self.edges.iter().filter(|e| e.from == repo).collect()
}
/// Edges where `repo` is the *producer* — i.e. the repos that
/// directly depend on it. Reverse of [`dependencies_of`].
pub fn dependents_of(&self, repo: &str) -> Vec<&CrossRepoEdge> {
self.edges.iter().filter(|e| e.to == repo).collect()
}
/// Forward transitive closure: every repo `repo` (transitively)
/// depends on. Excludes `repo` itself.
pub fn deps_transitive(&self, repo: &str) -> BTreeSet<String> {
self.reachable(repo, Direction::Forward)
}
/// Reverse transitive closure: every repo that (transitively)
/// depends on `repo` — the **blast radius** of a change to `repo`.
/// Excludes `repo` itself.
pub fn dependents_transitive(&self, repo: &str) -> BTreeSet<String> {
self.reachable(repo, Direction::Reverse)
}
/// A directional **adjacency index** over the cross-repo edges, built in ONE
/// pass so a BFS can look up a node's neighbours in O(1)+O(out-degree) instead
/// of re-scanning every edge at every frontier hop. `Forward` maps each
/// consumer `from` → its producers `to`; `Reverse` maps each producer `to` →
/// its consumers `from`. Values borrow `self.edges` (no clone) and preserve edge
/// order, so a BFS over this yields the SAME visit order (and same shortest
/// path) the old inline `for e in &self.edges` scan did — only without the
/// O(V·E) per-traversal rescan.
fn adjacency(&self, dir: Direction) -> std::collections::HashMap<&str, Vec<&str>> {
let mut adj: std::collections::HashMap<&str, Vec<&str>> = std::collections::HashMap::new();
for e in &self.edges {
let (key, val) = match dir {
Direction::Forward => (e.from.as_str(), e.to.as_str()),
Direction::Reverse => (e.to.as_str(), e.from.as_str()),
};
adj.entry(key).or_default().push(val);
}
adj
}
/// BFS over cross-repo edges from `start` in the given direction,
/// returning every reachable repo (excluding `start`). Traverses a built-once
/// [`adjacency`](Self::adjacency) index rather than re-scanning every edge per
/// hop (O(E) build + O(V+E) walk, vs the old O(V·E)); the visited set + result
/// order are unchanged.
fn reachable(&self, start: &str, dir: Direction) -> BTreeSet<String> {
use std::collections::VecDeque;
let adj = self.adjacency(dir);
let mut seen: BTreeSet<String> = BTreeSet::new();
let mut queue: VecDeque<String> = VecDeque::new();
seen.insert(start.to_string());
queue.push_back(start.to_string());
while let Some(cur) = queue.pop_front() {
if let Some(neighbours) = adj.get(cur.as_str()) {
for &next in neighbours {
if seen.insert(next.to_string()) {
queue.push_back(next.to_string());
}
}
}
}
seen.remove(start);
seen
}
/// The invalidation set for a set of changed repos: the changed repos
/// themselves ∪ everything that (transitively) depends on them,
/// returned in build order (dependencies first). This is exactly the
/// set a release/bench pipeline must re-run after `changed` moved.
pub fn affected_by_change(&self, changed: &[String]) -> Vec<String> {
let mut set: BTreeSet<String> = BTreeSet::new();
for c in changed {
set.insert(c.clone());
set.extend(self.dependents_transitive(c));
}
let repos: Vec<String> = set.into_iter().collect();
topo_order_from_edges(&repos, &self.edges)
}
/// Shortest dependency path `from → … → to` (following dependency
/// edges), or `None` if `to` is not a transitive dependency of
/// `from`. The returned vec starts with `from` and ends with `to`.
pub fn dep_path(&self, from: &str, to: &str) -> Option<Vec<String>> {
use std::collections::VecDeque;
if from == to {
return self.facts.contains_key(from).then(|| vec![from.to_string()]);
}
// Walk a built-once forward adjacency (consumer → producers) rather than
// re-scanning every edge at each frontier hop; BFS order is preserved
// (edge order within each node's list), so the shortest path returned — and
// its tie-breaking — is identical to the old inline scan.
let adj = self.adjacency(Direction::Forward);
let mut parent: BTreeMap<String, String> = BTreeMap::new();
let mut seen: BTreeSet<String> = BTreeSet::new();
let mut queue: VecDeque<String> = VecDeque::new();
seen.insert(from.to_string());
queue.push_back(from.to_string());
while let Some(cur) = queue.pop_front() {
let Some(neighbours) = adj.get(cur.as_str()) else { continue };
for &next in neighbours {
if !seen.insert(next.to_string()) {
continue;
}
parent.insert(next.to_string(), cur.clone());
if next == to {
let mut path = vec![to.to_string()];
let mut node = to.to_string();
while let Some(p) = parent.get(&node) {
path.push(p.clone());
node = p.clone();
}
path.reverse();
return Some(path);
}
queue.push_back(next.to_string());
}
}
None
}
/// Crates `repo` consumes that no repo in the workspace produces —
/// i.e. genuinely external dependencies (crates.io etc.).
pub fn external_deps(&self, repo: &str) -> BTreeSet<String> {
let produced: BTreeSet<&str> = self
.facts
.values()
.flat_map(|f| f.produces.iter().map(String::as_str))
.collect();
match self.facts.get(repo) {
Some(f) => f
.consumes
.iter()
.filter(|c| !produced.contains(c.as_str()))
.cloned()
.collect(),
None => BTreeSet::new(),
}
}
/// Workspace repos whose `consumes` set contains `krate` (sorted).
/// Used to answer "who uses external crate X?".
pub fn external_dep_users(&self, krate: &str) -> Vec<String> {
self.facts
.values()
.filter(|f| f.consumes.contains(krate))
.map(|f| f.name.clone())
.collect()
}
}
/// Direction of traversal over the cross-repo dependency edges.
#[derive(Clone, Copy)]
enum Direction {
/// Follow `from → to` (a repo's dependencies).
Forward,
/// Follow `to → from` (a repo's dependents).
Reverse,
}
pub fn inspect_repo(name: &str, root: &Path) -> Result<RepoFacts> {
let meta = MetadataCommand::new()
.current_dir(root)
.no_deps()
.exec()
.with_context(|| format!("cargo_metadata for repo `{name}` at {}", root.display()))?;
let mut produces: BTreeSet<String> = BTreeSet::new();
let mut all_local: BTreeSet<String> = BTreeSet::new();
let mut all_deps: BTreeSet<String> = BTreeSet::new();
// Crate names seen in a NON-dev table anywhere → these are NOT dev-only.
let mut non_dev_deps: BTreeSet<String> = BTreeSet::new();
for p in &meta.packages {
all_local.insert(p.name.to_string());
// `publish == Some([])` means `publish = false` — a strictly
// local crate (typical for `xtask` helpers). Such crates are
// not visible to any other workspace, so they don't count as
// something this repo "produces" for cross-repo wiring.
let is_private = matches!(&p.publish, Some(v) if v.is_empty());
if !is_private {
produces.insert(p.name.to_string());
}
for d in &p.dependencies {
all_deps.insert(d.name.clone());
// cargo_metadata tags each dep with its kind; Development = dev-dep.
if d.kind != cargo_metadata::DependencyKind::Development {
non_dev_deps.insert(d.name.clone());
}
}
}
// Strip *all* in-workspace dep names (published or not) from the
// consumed set — even private crates can be intra-workspace deps,
// they just can't be cross-workspace deps.
let consumes: BTreeSet<String> = all_deps.difference(&all_local).cloned().collect();
// Dev-only = consumed but never via a normal/build table.
let dev_only_consumes: BTreeSet<String> =
consumes.iter().filter(|c| !non_dev_deps.contains(*c)).cloned().collect();
Ok(RepoFacts {
name: name.to_string(),
root: root.to_path_buf(),
produces,
consumes,
dev_only_consumes,
})
}
// ─── direct-manifest facts (no `cargo metadata` subprocess) ───────────────
/// The `cargo metadata`-free twin of [`inspect_repo`]: parse the member's
/// `Cargo.toml`(s) directly to derive the SAME `produces`/`consumes` sets.
///
/// - **produces** = every non-private `[package].name` (a `publish = false` or
/// `publish = []` crate is local-only, exactly as `inspect_repo` treats it).
/// - **consumes** = every dependency name across all the repo's manifests
/// (normal/dev/build + target- and workspace-scoped tables, honoring a
/// `package = "…"` rename) MINUS the repo's own local crate names.
///
/// Errors only when the repo has no parseable root `Cargo.toml` — the caller
/// turns that into a SKIP, never a graph-wide failure.
fn inspect_repo_manifests(name: &str, root: &Path) -> Result<RepoFacts> {
let manifests = collect_repo_manifests(root);
if manifests.is_empty() {
return Err(anyhow!(
"no parseable Cargo.toml for repo `{name}` at {}",
root.display()
));
}
let mut produces: BTreeSet<String> = BTreeSet::new();
let mut all_local: BTreeSet<String> = BTreeSet::new();
let mut all_deps: BTreeSet<String> = BTreeSet::new();
// Names seen in a NON-dev table anywhere → not dev-only.
let mut non_dev_deps: BTreeSet<String> = BTreeSet::new();
for doc in &manifests {
if let Some(pkg) = doc.get("package") {
if let Some(pname) = pkg.get("name").and_then(|v| v.as_str()) {
all_local.insert(pname.to_string());
if !manifest_is_private(pkg) {
produces.insert(pname.to_string());
}
}
}
collect_dep_names(doc, &mut all_deps, &mut non_dev_deps);
}
let consumes: BTreeSet<String> = all_deps.difference(&all_local).cloned().collect();
let dev_only_consumes: BTreeSet<String> =
consumes.iter().filter(|c| !non_dev_deps.contains(*c)).cloned().collect();
Ok(RepoFacts {
name: name.to_string(),
root: root.to_path_buf(),
produces,
consumes,
dev_only_consumes,
})
}
/// Every manifest belonging to a member repo: its root `Cargo.toml` plus — when
/// the root is a cargo workspace — every `[workspace].members` manifest. A
/// missing/unparseable root yields an empty vec (the caller skips the member).
fn collect_repo_manifests(root: &Path) -> Vec<toml::Value> {
let root_manifest = root.join("Cargo.toml");
let Some(root_doc) = read_manifest_toml(&root_manifest) else {
return Vec::new();
};
let mut out: Vec<toml::Value> = Vec::new();
let mut seen: BTreeSet<PathBuf> = BTreeSet::new();
seen.insert(root_manifest.clone());
// The root may be a `[package]`, a virtual `[workspace]`, or both.
if let Some(members) = root_doc
.get("workspace")
.and_then(|w| w.get("members"))
.and_then(|m| m.as_array())
{
for entry in members {
let Some(pat) = entry.as_str() else { continue };
for mpath in resolve_member_glob(root, pat) {
if seen.insert(mpath.clone()) {
if let Some(doc) = read_manifest_toml(&mpath) {
out.push(doc);
}
}
}
}
}
out.push(root_doc);
out
}
/// Expand a `[workspace].members` entry to the manifest path(s) it names. Handles
/// a literal member dir (`crates/foo`) and a single trailing `*` glob (`crates/*`
/// or `*`) — the forms cargo workspaces use in practice. A `**` or mid-path glob
/// is treated literally (best-effort; such a member just won't resolve and is
/// silently skipped, never fatal).
fn resolve_member_glob(root: &Path, pat: &str) -> Vec<PathBuf> {
let prefix = if pat == "*" {
Some("")
} else {
pat.strip_suffix("/*")
};
if let Some(prefix) = prefix {
let dir = root.join(prefix);
let mut out = Vec::new();
if let Ok(rd) = std::fs::read_dir(&dir) {
for e in rd.flatten() {
let p = e.path();
if p.is_dir() {
let mf = p.join("Cargo.toml");
if mf.is_file() {
out.push(mf);
}
}
}
}
out.sort();
out
} else {
vec![root.join(pat).join("Cargo.toml")]
}
}
/// Read + parse a `Cargo.toml`. `None` on any read/parse error (missing file,
/// torn bytes, invalid TOML) — the caller treats that as "skip this manifest".
fn read_manifest_toml(path: &Path) -> Option<toml::Value> {
std::fs::read_to_string(path).ok()?.parse::<toml::Table>().map(toml::Value::Table).ok()
}
/// `publish = false` (bool) or `publish = []` (empty array) ⇒ a strictly local
/// crate — mirrors `inspect_repo`'s `matches!(&p.publish, Some(v) if v.is_empty())`.
fn manifest_is_private(pkg: &toml::Value) -> bool {
match pkg.get("publish") {
Some(toml::Value::Boolean(b)) => !b,
Some(toml::Value::Array(a)) => a.is_empty(),
_ => false,
}
}
/// Collect every dependency name declared anywhere in one manifest: the
/// `[dependencies]` / `[dev-dependencies]` / `[build-dependencies]` tables, their
/// `[target.<cfg>.…]` variants, and `[workspace.dependencies]`. A `package = "…"`
/// rename resolves to the REAL crate name (what `cargo_metadata`'s `Dependency.name`
/// reports), so a renamed path-dep still matches its producer's crate name.
///
/// `out` gets EVERY name (all kinds); `non_dev` gets only names seen in a
/// non-`dev-dependencies` table — the difference (out − non_dev) is the dev-ONLY
/// set, which seeds `Dev`-kind edges (master-of-deps #1/#8). `[workspace.dependencies]`
/// declarations are version-source for inheritance, not a kind, so they count as
/// non-dev (a member that inherits them does so in a real dep table).
fn collect_dep_names(
manifest: &toml::Value,
out: &mut BTreeSet<String>,
non_dev: &mut BTreeSet<String>,
) {
fn from_table(t: &toml::Value, out: &mut BTreeSet<String>, also: Option<&mut BTreeSet<String>>) {
let Some(tbl) = t.as_table() else { return };
let mut sink = also;
for (key, spec) in tbl {
let real = spec
.as_table()
.and_then(|s| s.get("package"))
.and_then(|p| p.as_str())
.unwrap_or(key)
.to_string();
out.insert(real.clone());
if let Some(s) = sink.as_deref_mut() {
s.insert(real);
}
}
}
// (kind name, is_dev)
const KINDS: [(&str, bool); 3] = [
("dependencies", false),
("dev-dependencies", true),
("build-dependencies", false),
];
for (k, is_dev) in KINDS {
if let Some(t) = manifest.get(k) {
from_table(t, out, (!is_dev).then_some(&mut *non_dev));
}
}
// [workspace.dependencies] — inherited-dep declarations (treated as non-dev).
if let Some(t) = manifest.get("workspace").and_then(|w| w.get("dependencies")) {
from_table(t, out, Some(&mut *non_dev));
}
// [target.<cfg>.dependencies] (and dev/build variants) — platform-scoped deps.
if let Some(targets) = manifest.get("target").and_then(|t| t.as_table()) {
for cfg in targets.values() {
for (k, is_dev) in KINDS {
if let Some(t) = cfg.get(k) {
from_table(t, out, (!is_dev).then_some(&mut *non_dev));
}
}
}
}
}
/// Minimal parallel map — results returned in input order, identical to a serial
/// `items.iter().map(f).collect()`. Used to parse every member's (tiny)
/// `Cargo.toml` concurrently here, and by the monitor to fan the per-member SBOM
/// `cargo metadata` resolve. Top-level only — callers must pass a closure that
/// opens no inner pool.
///
/// ROOT-LAW #0: all nordisk parallelism originates in the ONE shared gatling
/// engine (znippy-zoomies), never a hand-rolled `thread::scope` work-stealing
/// pool. This routes straight through
/// [`gatling::gatling_forkjoin::gatling_map_balanced`] — a work-stealing,
/// heaviest-first, batched pool that writes each result into its own output slot
/// so the returned `Vec` is in the original `items` order. Per-member manifests
/// are uniformly tiny, so every unit gets weight `1` and the batch is `1`;
/// `n_workers == 0` lets gatling pick one worker per core (and collapse to a
/// serial loop for a single item).
pub fn parallel_map<T, R, F>(items: &[T], f: F) -> Vec<R>
where
T: Sync,
R: Send,
F: Fn(&T) -> R + Sync,
{
gatling::gatling_forkjoin::gatling_map_balanced(items, 0, 1, |_| 1, |_, t| f(t))
}
#[cfg(test)]
mod parallel_map_tests {
use super::*;
/// RED-WHEN-BROKEN: `parallel_map` must be an order-preserving map — its output
/// must equal a serial `iter().map(f)` element-for-element. This is the invariant
/// the whole `build_from_members` fan-out relies on; if the gatling routing ever
/// scrambled indices or dropped/duplicated an item, this fails. Uses a large,
/// non-trivial input so a scheduling bug can't hide behind a tiny work set.
#[test]
fn parallel_map_equals_serial_map() {
let items: Vec<u64> = (0..5_000).collect();
let f = |x: &u64| x.wrapping_mul(2654435761).wrapping_add(*x);
let par = parallel_map(&items, f);
let ser: Vec<u64> = items.iter().map(f).collect();
assert_eq!(par, ser, "parallel_map must match serial map, in order");
// Empty input is the serial-collapse edge case.
assert!(parallel_map::<u64, u64, _>(&[], f).is_empty());
// Single item likewise round-trips.
assert_eq!(parallel_map(&[7u64], f), vec![f(&7)]);
}
}
// ─── persistence ────────────────────────────────────────────────────────
/// A [`DepGraphSnapshot`] materialised into the flat, fully-normalised form the
/// `dep_graph_edges` warehouse table stores: **one row per
/// `(snapshot, edge, via-crate)`** — an edge justified by three crates becomes
/// three rows, all sharing the snapshot header + `(from, to, kind)` and differing
/// only in `via_crate`. This is the columnar shape an Iceberg/Arrow sink wants (no
/// nested `Vec<String>` column); [`group_snapshots`] folds a stream of these rows
/// back into [`DepGraphSnapshot`]s, and [`DepGraphSnapshot::to_rows`] flattens the
/// other way, so `group_snapshots(snap.to_rows())` round-trips a snapshot exactly.
///
/// An edge with *no* justifying crate (an empty `via`) is represented by a single
/// row whose `via_crate` is empty, so it survives the round trip rather than
/// vanishing.
#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
pub struct DepGraphRow {
pub snapshot_id: Uuid,
pub workspace_name: String,
pub timestamp: DateTime<Utc>,
/// The consuming repo (`edge.from`).
pub from: String,
/// The producing repo (`edge.to`).
pub to: String,
/// ONE crate justifying this `(from → to)` edge, or empty when the edge has
/// no recorded justification. See the type docs for the fan-out.
pub via_crate: String,
/// Which dependency table the edge came from. `#[serde(default)]` so rows
/// written before kinds were tracked read back as [`DepKind::Normal`].
#[serde(default)]
pub kind: DepKind,
}
/// One row materialised from the `dep_graph_edges` table per
/// `(snapshot, edge, crate)`. Use [`group_snapshots`] to fold back into
/// [`DepGraphSnapshot`]s.
#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
pub struct DepGraphSnapshot {
pub snapshot_id: Uuid,
pub workspace_name: String,
pub timestamp: DateTime<Utc>,
pub edges: Vec<CrossRepoEdge>,
}
impl DepGraphSnapshot {
/// Flatten this snapshot into the warehouse's [`DepGraphRow`] rows — one row
/// per `(edge, via-crate)`, sharing the snapshot header. An edge with an empty
/// `via` yields a single row with an empty `via_crate` (so it round-trips).
/// The inverse of [`group_snapshots`].
pub fn to_rows(&self) -> Vec<DepGraphRow> {
let mut rows = Vec::new();
for e in &self.edges {
if e.via.is_empty() {
rows.push(DepGraphRow {
snapshot_id: self.snapshot_id,
workspace_name: self.workspace_name.clone(),
timestamp: self.timestamp,
from: e.from.clone(),
to: e.to.clone(),
via_crate: String::new(),
kind: e.kind,
});
} else {
for c in &e.via {
rows.push(DepGraphRow {
snapshot_id: self.snapshot_id,
workspace_name: self.workspace_name.clone(),
timestamp: self.timestamp,
from: e.from.clone(),
to: e.to.clone(),
via_crate: c.clone(),
kind: e.kind,
});
}
}
}
rows
}
}
/// Fold a flat stream of [`DepGraphRow`]s (as read out of the `dep_graph_edges`
/// warehouse table) back into whole [`DepGraphSnapshot`]s — the primitive the
/// snapshot doc promises, and the exact inverse of [`DepGraphSnapshot::to_rows`].
///
/// Grouping is two levels: rows are grouped by `snapshot_id` (snapshots appear in
/// **first-seen order**, so a query that returns rows newest-first keeps that
/// order), and within a snapshot the rows are grouped by `(from, to, kind)` with
/// their `via_crate`s collected into the edge's `via` set (deduped, sorted — it is
/// a `BTreeSet`). Edges within a snapshot are returned sorted by `(from, to, kind)`
/// so the fold is deterministic regardless of row arrival order. An empty
/// `via_crate` contributes no crate but still materialises its edge.
///
/// The snapshot header (`workspace_name`, `timestamp`) is taken from the FIRST row
/// seen for each `snapshot_id`; well-formed warehouse rows carry a consistent
/// header per snapshot, so this is lossless for data written by [`to_rows`].
pub fn group_snapshots(rows: impl IntoIterator<Item = DepGraphRow>) -> Vec<DepGraphSnapshot> {
// Preserve first-seen snapshot order.
let mut order: Vec<Uuid> = Vec::new();
// snapshot_id → (workspace_name, timestamp, edges-by-(from,to,kind))
#[allow(clippy::type_complexity)]
let mut acc: BTreeMap<
Uuid,
(String, DateTime<Utc>, BTreeMap<(String, String, DepKind), BTreeSet<String>>),
> = BTreeMap::new();
for r in rows {
let entry = acc.entry(r.snapshot_id).or_insert_with(|| {
order.push(r.snapshot_id);
(r.workspace_name.clone(), r.timestamp, BTreeMap::new())
});
let via = entry.2.entry((r.from, r.to, r.kind)).or_default();
if !r.via_crate.is_empty() {
via.insert(r.via_crate);
}
}
order
.into_iter()
.map(|id| {
let (workspace_name, timestamp, edge_map) = acc.remove(&id).expect("id was recorded");
let edges = edge_map
.into_iter()
.map(|((from, to, kind), via)| CrossRepoEdge { from, to, via, kind })
.collect();
DepGraphSnapshot { snapshot_id: id, workspace_name, timestamp, edges }
})
.collect()
}
/// Topological order over `repos` derived from `edges`. Edges with
/// endpoints outside `repos` are ignored. Convention: dependencies
/// first, dependents last — matches [`WorkspaceGraph::build_order`].
/// On cycle / partial graph, returns `repos` in input order so callers
/// always get a deterministic permutation.
///
/// `Dev`-kind edges are SKIPPED — a dev-dep is not part of the published crate's
/// requirements, so it must not gate publish order (this is what excludes the
/// xtask/bench → nornir back-edges that otherwise cycle the graph). Snapshots
/// written before kinds were tracked read every edge as `Normal`, so old data
/// keeps its previous ordering (no regression). Master-of-deps #2.
pub fn topo_order_from_edges(repos: &[String], edges: &[CrossRepoEdge]) -> Vec<String> {
use std::collections::{BTreeMap, BTreeSet, VecDeque};
let set: BTreeSet<&str> = repos.iter().map(|s| s.as_str()).collect();
let mut indeg: BTreeMap<&str, usize> = repos.iter().map(|r| (r.as_str(), 0)).collect();
let mut adj: BTreeMap<&str, Vec<&str>> = BTreeMap::new();
for e in edges {
if !e.kind.is_order_gating() {
continue;
}
let from = e.from.as_str();
let to = e.to.as_str();
if !set.contains(from) || !set.contains(to) {
continue;
}
adj.entry(to).or_default().push(from);
*indeg.entry(from).or_insert(0) += 1;
}
let mut q: VecDeque<&str> =
indeg.iter().filter(|(_, d)| **d == 0).map(|(r, _)| *r).collect();
let mut out: Vec<String> = Vec::with_capacity(repos.len());
while let Some(r) = q.pop_front() {
out.push(r.to_string());
if let Some(children) = adj.get(r) {
for &c in children {
let d = indeg.get_mut(c).unwrap();
*d -= 1;
if *d == 0 {
q.push_back(c);
}
}
}
}
if out.len() == repos.len() {
out
} else {
repos.to_vec()
}
}
#[cfg(test)]
mod manifest_tests {
use super::*;
/// Write a minimal member crate `<root>/<name>/` with the given package name,
/// `publish` flag, and path-dep crate names (each `dep` becomes
/// `dep = { path = "../dep" }`).
fn member(root: &Path, dir: &str, pkg: &str, publish_false: bool, path_deps: &[&str]) {
let crate_dir = root.join(dir);
std::fs::create_dir_all(crate_dir.join("src")).unwrap();
let mut toml = format!(
"[package]\nname = \"{pkg}\"\nversion = \"0.1.0\"\nedition = \"2021\"\n"
);
if publish_false {
toml.push_str("publish = false\n");
}
if !path_deps.is_empty() {
toml.push_str("\n[dependencies]\n");
for d in path_deps {
toml.push_str(&format!("{d} = {{ path = \"../{d}\" }}\n"));
}
}
std::fs::write(crate_dir.join("Cargo.toml"), toml).unwrap();
std::fs::write(crate_dir.join("src/lib.rs"), "// fixture\n").unwrap();
}
fn resolved(root: &Path, members: &[&str]) -> BTreeMap<String, PathBuf> {
members
.iter()
.map(|m| (m.to_string(), root.join(m)))
.collect()
}
fn edge_set(g: &WorkspaceGraph) -> BTreeSet<(String, String, Vec<String>)> {
g.edges
.iter()
.map(|e| {
(
e.from.clone(),
e.to.clone(),
e.via.iter().cloned().collect::<Vec<_>>(),
)
})
.collect()
}
/// Direct-manifest parse reproduces the cross-repo edges + produces facts of a
/// path-dep diamond, with ZERO `cargo metadata` subprocess.
#[test]
fn manifest_facts_capture_diamond_edges() {
let dir = tempfile::tempdir().unwrap();
let root = dir.path();
// app → liba → util ; app → libb → util (consumer → producer edges).
member(root, "app", "app", false, &["liba", "libb"]);
member(root, "liba", "liba", false, &["util"]);
member(root, "libb", "libb", false, &["util"]);
member(root, "util", "util", false, &[]);
let g = WorkspaceGraph::build_from_members(&resolved(
root,
&["app", "liba", "libb", "util"],
))
.expect("manifest graph builds");
// produces: each repo produces exactly its own crate.
for m in ["app", "liba", "libb", "util"] {
let f = g.facts.get(m).unwrap();
assert!(f.produces.contains(m), "{m} must produce its own crate");
}
// Edges follow the path-deps.
let edges = edge_set(&g);
assert!(edges.contains(&("app".into(), "liba".into(), vec!["liba".into()])));
assert!(edges.contains(&("app".into(), "libb".into(), vec!["libb".into()])));
assert!(edges.contains(&("liba".into(), "util".into(), vec!["util".into()])));
assert!(edges.contains(&("libb".into(), "util".into(), vec!["util".into()])));
// Blast radius of a util change is the whole diamond, in build order.
let affected = g.affected_by_change(&["util".to_string()]);
assert_eq!(
affected.iter().cloned().collect::<BTreeSet<_>>(),
["app", "liba", "libb", "util"].iter().map(|s| s.to_string()).collect()
);
}
/// A `publish = false` member is NOT a producer (local-only), so nothing
/// depends on it cross-repo — mirrors `inspect_repo`'s private-crate rule.
#[test]
fn private_member_produces_nothing() {
let dir = tempfile::tempdir().unwrap();
let root = dir.path();
member(root, "app", "app", false, &["xtask"]);
member(root, "xtask", "xtask", true, &[]); // publish = false → private
let g = WorkspaceGraph::build_from_members(&resolved(root, &["app", "xtask"])).unwrap();
assert!(g.facts.get("xtask").unwrap().produces.is_empty(), "private crate produces nothing");
// `app` consumes `xtask` but no repo PRODUCES it → no cross-repo edge.
assert!(g.edges.iter().all(|e| e.to != "xtask"), "no edge to a private producer");
}
/// RED-WHEN-REVERTED: a crate name produced by MORE THAN ONE repo (the real
/// `xtask`-in-every-repo case) is AMBIGUOUS — it is excluded from cross-repo
/// edge resolution but must NOT fail the whole graph. The pre-fix hard-error on
/// the first duplicate produced-name returned `Err`, which `build_member_graph`
/// turned into `None`, zeroing out EVERY edge (deps/dependents/build-order all
/// empty on the live nordisk server). Assert the unrelated edge still builds.
#[test]
fn duplicate_produced_name_is_ambiguous_not_fatal() {
let dir = tempfile::tempdir().unwrap();
let root = dir.path();
// Real cross-repo edge app → core via `corelib`; TWO repos both produce a
// crate literally named `xtask` (non-private) — the collision that used to
// sink the entire graph.
member(root, "app", "app", false, &["corelib", "xtask"]);
member(root, "core", "corelib", false, &["xtask"]);
member(root, "app-tools", "xtask", false, &[]);
member(root, "core-tools", "xtask", false, &[]);
let g = WorkspaceGraph::build_from_members(&resolved(
root,
&["app", "core", "app-tools", "core-tools"],
))
.expect("graph must build despite the duplicate `xtask` producer (was a hard Err)");
let edges = edge_set(&g);
assert!(
edges.contains(&("app".into(), "core".into(), vec!["corelib".into()])),
"the real cross-repo edge must survive the ambiguous `xtask`; got {edges:?}"
);
assert!(
g.edges.iter().all(|e| !e.via.contains(&"xtask".to_string())),
"the ambiguous `xtask` name must not justify any cross-repo edge"
);
}
/// A broken/unparseable manifest in ONE member is SKIPPED (logged), and the
/// rest of the graph still builds — the fix for one bad manifest (facett)
/// sinking the entire republish dep-graph.
#[test]
fn broken_manifest_member_is_skipped_not_fatal() {
let dir = tempfile::tempdir().unwrap();
let root = dir.path();
member(root, "app", "app", false, &["util"]);
member(root, "util", "util", false, &[]);
// A third member with a torn Cargo.toml (invalid TOML).
let bad = root.join("facett");
std::fs::create_dir_all(&bad).unwrap();
std::fs::write(bad.join("Cargo.toml"), "[package\nname = busted = =\n").unwrap();
let g = WorkspaceGraph::build_from_members(&resolved(root, &["app", "util", "facett"]))
.expect("a broken member must not fail the whole graph");
// The good members are present + wired; the broken one is simply absent.
assert!(g.facts.contains_key("app"));
assert!(g.facts.contains_key("util"));
assert!(!g.facts.contains_key("facett"), "broken member skipped from facts");
assert!(g.edges.iter().any(|e| e.from == "app" && e.to == "util"));
}
}
#[cfg(test)]
mod snapshot_row_tests {
use super::*;
fn ts() -> DateTime<Utc> {
DateTime::parse_from_rfc3339("2026-07-14T12:00:00Z").unwrap().with_timezone(&Utc)
}
fn via(cs: &[&str]) -> BTreeSet<String> {
cs.iter().map(|s| s.to_string()).collect()
}
fn snap(id: Uuid, edges: Vec<CrossRepoEdge>) -> DepGraphSnapshot {
DepGraphSnapshot { snapshot_id: id, workspace_name: "nordisk".into(), timestamp: ts(), edges }
}
/// A multi-crate edge fans out to ONE row per via-crate; `group_snapshots`
/// folds them back into exactly the original snapshot (round trip).
#[test]
fn to_rows_group_snapshots_round_trip() {
let id = Uuid::new_v4();
// Edges in (from, to, kind) order — the order `group_snapshots` returns and
// the order `from_facts` already produces real snapshots in.
let original = snap(
id,
vec![
CrossRepoEdge { from: "dwarves".into(), to: "edda".into(), via: via(&["nornir-service"]), kind: DepKind::Dev },
CrossRepoEdge { from: "nornir".into(), to: "edda".into(), via: via(&["jera", "nornir-git", "saga"]), kind: DepKind::Normal },
],
);
let rows = original.to_rows();
// 1 via-crate + 3 via-crates = 4 fully-normalised rows.
assert_eq!(rows.len(), 4, "one row per (edge, via-crate)");
let regrouped = group_snapshots(rows);
assert_eq!(regrouped.len(), 1, "one snapshot id → one snapshot");
// RED-when-broken: the folded snapshot must equal the original exactly
// (edges are BTreeSet-sorted via + (from,to,kind)-sorted, matching to_rows).
assert_eq!(regrouped[0], original, "round trip must reconstruct the snapshot");
}
/// Rows for two snapshots interleaved in a single stream are separated by
/// `snapshot_id`, and the snapshots come back in FIRST-SEEN order.
#[test]
fn group_snapshots_separates_ids_and_preserves_first_seen_order() {
let (a, b) = (Uuid::new_v4(), Uuid::new_v4());
let row = |id: Uuid, from: &str, to: &str, c: &str| DepGraphRow {
snapshot_id: id,
workspace_name: "w".into(),
timestamp: ts(),
from: from.into(),
to: to.into(),
via_crate: c.into(),
kind: DepKind::Normal,
};
// Interleaved: b first, then a, then more b — b must sort before a.
let rows = vec![
row(b, "x", "y", "c1"),
row(a, "p", "q", "c2"),
row(b, "x", "y", "c3"), // second crate for b's x→y edge
];
let out = group_snapshots(rows);
assert_eq!(out.len(), 2);
assert_eq!(out[0].snapshot_id, b, "b was seen first");
assert_eq!(out[1].snapshot_id, a);
// b's single edge accumulated both crates.
assert_eq!(out[0].edges.len(), 1);
assert_eq!(out[0].edges[0].via, via(&["c1", "c3"]));
}
/// An edge with an empty `via` survives the round trip as a single empty-crate
/// row (it must not vanish, and must not gain a phantom crate).
#[test]
fn empty_via_edge_round_trips() {
let id = Uuid::new_v4();
let original = snap(
id,
vec![CrossRepoEdge { from: "a".into(), to: "b".into(), via: BTreeSet::new(), kind: DepKind::Normal }],
);
let rows = original.to_rows();
assert_eq!(rows.len(), 1);
assert_eq!(rows[0].via_crate, "", "empty-via edge → one empty-crate row");
let regrouped = group_snapshots(rows);
assert_eq!(regrouped[0], original);
assert!(regrouped[0].edges[0].via.is_empty(), "no phantom crate materialised");
}
/// Same (from,to) but different `kind` stays as two distinct edges through the
/// fold (a Normal and a Dev edge are not merged).
#[test]
fn distinct_kinds_are_not_merged() {
let id = Uuid::new_v4();
let mk = |c: &str, k: DepKind| DepGraphRow {
snapshot_id: id,
workspace_name: "w".into(),
timestamp: ts(),
from: "a".into(),
to: "b".into(),
via_crate: c.into(),
kind: k,
};
let out = group_snapshots(vec![mk("c1", DepKind::Normal), mk("c2", DepKind::Dev)]);
assert_eq!(out.len(), 1);
assert_eq!(out[0].edges.len(), 2, "Normal and Dev a→b are separate edges");
assert!(out[0].edges.iter().any(|e| e.kind == DepKind::Normal && e.via == via(&["c1"])));
assert!(out[0].edges.iter().any(|e| e.kind == DepKind::Dev && e.via == via(&["c2"])));
}
/// An empty row stream folds to no snapshots (no panic on the empty case).
#[test]
fn empty_rows_yield_no_snapshots() {
assert!(group_snapshots(Vec::new()).is_empty());
}
}
#[cfg(test)]
mod mimir_tests {
use super::*;
/// Build a `WorkspaceGraph` directly from facts + edges, bypassing
/// `cargo_metadata`. `inner` is left empty: the Mímir methods under
/// test work purely off `facts`/`edges`.
fn graph(facts: Vec<RepoFacts>, edges: Vec<CrossRepoEdge>) -> WorkspaceGraph {
let mut fmap = BTreeMap::new();
for f in facts {
fmap.insert(f.name.clone(), f);
}
WorkspaceGraph { facts: fmap, edges, inner: DiGraph::new() }
}
fn facts(name: &str, produces: &[&str], consumes: &[&str]) -> RepoFacts {
RepoFacts {
name: name.to_string(),
root: PathBuf::from("/dev/null"),
produces: produces.iter().map(|s| s.to_string()).collect(),
consumes: consumes.iter().map(|s| s.to_string()).collect(),
..Default::default()
}
}
fn edge(from: &str, to: &str, via: &[&str]) -> CrossRepoEdge {
CrossRepoEdge::normal(from, to, via.iter().map(|s| s.to_string()).collect())
}
/// Diamond: app → liba → util, app → libb → util.
/// `app` also consumes external `serde`; `util` consumes external `libc`.
fn diamond() -> WorkspaceGraph {
graph(
vec![
facts("app", &["app_c"], &["a_c", "b_c", "serde"]),
facts("liba", &["a_c"], &["util_c"]),
facts("libb", &["b_c"], &["util_c"]),
facts("util", &["util_c"], &["libc"]),
],
vec![
edge("app", "liba", &["a_c"]),
edge("app", "libb", &["b_c"]),
edge("liba", "util", &["util_c"]),
edge("libb", "util", &["util_c"]),
],
)
}
fn names(edges: Vec<&CrossRepoEdge>, pick_to: bool) -> BTreeSet<String> {
edges
.into_iter()
.map(|e| if pick_to { e.to.clone() } else { e.from.clone() })
.collect()
}
#[test]
fn dependents_of_is_reverse_of_dependencies() {
let g = diamond();
// who depends directly on util? liba, libb.
assert_eq!(
names(g.dependents_of("util"), false),
["liba", "libb"].iter().map(|s| s.to_string()).collect()
);
// app depends directly on liba, libb.
assert_eq!(
names(g.dependencies_of("app"), true),
["liba", "libb"].iter().map(|s| s.to_string()).collect()
);
assert!(g.dependents_of("app").is_empty());
}
#[test]
fn transitive_closures() {
let g = diamond();
assert_eq!(
g.deps_transitive("app"),
["liba", "libb", "util"].iter().map(|s| s.to_string()).collect()
);
// blast radius of util = everything above it.
assert_eq!(
g.dependents_transitive("util"),
["app", "liba", "libb"].iter().map(|s| s.to_string()).collect()
);
assert!(g.deps_transitive("util").is_empty());
assert!(g.dependents_transitive("app").is_empty());
}
/// **Deep multi-hop chain — guards the adjacency BFS.** A long chain
/// `a → b → c → d → e` plus an `a → e` shortcut exercises the built-once
/// [`adjacency`](WorkspaceGraph::adjacency) traversal across many frontier hops:
/// `reachable` must return the full closure, and `dep_path` must still return the
/// SHORTEST route (the one-hop shortcut), not the long chain. RED if the
/// adjacency walk drops a hop or loses BFS's shortest-path / edge-order tie-break.
#[test]
fn dep_path_and_reachable_walk_a_deep_chain() {
let g = graph(
vec![
facts("a", &["a_c"], &["b_c", "e_c"]),
facts("b", &["b_c"], &["c_c"]),
facts("c", &["c_c"], &["d_c"]),
facts("d", &["d_c"], &["e_c"]),
facts("e", &["e_c"], &[]),
],
vec![
edge("a", "b", &["b_c"]),
edge("b", "c", &["c_c"]),
edge("c", "d", &["d_c"]),
edge("d", "e", &["e_c"]),
edge("a", "e", &["e_c"]), // the shortcut: a depends on e directly too
],
);
// Forward closure from `a` reaches every downstream repo.
assert_eq!(
g.deps_transitive("a"),
["b", "c", "d", "e"].iter().map(|s| s.to_string()).collect()
);
// Reverse closure (blast radius) of `e` is everything above it.
assert_eq!(
g.dependents_transitive("e"),
["a", "b", "c", "d"].iter().map(|s| s.to_string()).collect()
);
// Shortest path a → e is the one-hop shortcut, not a→b→c→d→e.
assert_eq!(g.dep_path("a", "e"), Some(vec!["a".to_string(), "e".to_string()]));
// The long route is still fully walkable: a → b → c → d through the chain.
assert_eq!(
g.dep_path("a", "d"),
Some(vec!["a".to_string(), "b".to_string(), "c".to_string(), "d".to_string()])
);
// No path backwards (edges are directed consumer→producer).
assert_eq!(g.dep_path("e", "a"), None);
}
#[test]
fn affected_by_change_is_blast_radius_in_build_order() {
let g = diamond();
let affected = g.affected_by_change(&["util".to_string()]);
assert_eq!(
affected.iter().cloned().collect::<BTreeSet<_>>(),
["app", "liba", "libb", "util"].iter().map(|s| s.to_string()).collect()
);
// build order: dependencies first. util before liba/libb; both before app.
let pos = |n: &str| affected.iter().position(|x| x == n).unwrap();
assert!(pos("util") < pos("liba"));
assert!(pos("util") < pos("libb"));
assert!(pos("liba") < pos("app"));
assert!(pos("libb") < pos("app"));
}
#[test]
fn dep_path_finds_shortest_route() {
let g = diamond();
let p = g.dep_path("app", "util").expect("path exists");
assert_eq!(p.len(), 3);
assert_eq!(p.first().unwrap(), "app");
assert_eq!(p.last().unwrap(), "util");
assert_eq!(g.dep_path("app", "app"), Some(vec!["app".to_string()]));
// util doesn't depend on app — no forward path.
assert_eq!(g.dep_path("util", "app"), None);
assert_eq!(g.dep_path("app", "ghost"), None);
}
#[test]
fn external_deps_and_users() {
let g = diamond();
assert_eq!(
g.external_deps("app"),
["serde"].iter().map(|s| s.to_string()).collect()
);
assert_eq!(
g.external_deps("util"),
["libc"].iter().map(|s| s.to_string()).collect()
);
// liba's only consumed crate (util_c) is produced internally.
assert!(g.external_deps("liba").is_empty());
assert_eq!(g.external_dep_users("serde"), vec!["app".to_string()]);
assert_eq!(g.external_dep_users("libc"), vec!["util".to_string()]);
// util_c is consumed by both liba and libb (sorted by repo name).
assert_eq!(
g.external_dep_users("util_c"),
vec!["liba".to_string(), "libb".to_string()]
);
}
}