crates/nornir-depgraph/src/layout.rs
//! Pure (no-egui) dependency-graph layout + edge classification.
//!
//! This is the data core behind the 🔗 Dep Graph tab's renderer
//! (`super::graph`). Keeping it egui-free makes it:
//!
//! * **inject-and-assert testable** (LAW #1) — feed a known multi-level
//! graph (A→B→C, A→C direct) and assert the transitive closure, the
//! direct-vs-transitive edge classification, and the laid-out node
//! positions, with no display; and
//! * **introspectable** (LAW #6) — [`DepGraphLayout::state_json`] is folded
//! straight into the viz's `NORNIR_VIZ_STATE` dump so a robot test (and the
//! operator) can read the rendered graph structure — nodes, positions,
//! edges, direct/transitive flags — without a screenshot.
//!
//! Two display modes (C5):
//! * **direct** — only the cross-repo edges the snapshot recorded
//! (`snap.edges`), one column per topo rank.
//! * **deep** — the FULL transitive closure: every `from` gets an edge to
//! every repo reachable from it, the transitively-derived ones flagged so
//! the renderer can dim them (C7).
//!
//! Click-to-expand (I3): a node can be **collapsed**, which hides the subtree
//! reachable *only* through it; [`DepGraphLayout::visible`] reports which nodes
//! survive the current collapse set so the renderer and the introspection agree.
use std::collections::{BTreeMap, BTreeSet, VecDeque};
use crate::CrossRepoEdge;
/// How an edge in the laid-out graph relates to the recorded snapshot.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum EdgeClass {
/// A directly-recorded `snap.edges` entry (`from` consumes `to` via a crate).
Direct,
/// A transitive reachability edge synthesised in **deep** mode: `to` is
/// reachable from `from` only through one or more intermediate repos.
Transitive,
}
impl EdgeClass {
pub fn as_str(self) -> &'static str {
match self {
EdgeClass::Direct => "direct",
EdgeClass::Transitive => "transitive",
}
}
}
/// A laid-out edge: endpoints + classification + the via-crate labels (empty for
/// synthesised transitive edges, whose label is the hop count instead).
#[derive(Debug, Clone)]
pub struct LaidEdge {
pub from: String,
pub to: String,
pub class: EdgeClass,
/// Cross-repo crates justifying a direct edge (`from` consumes, `to`
/// produces). Empty for a synthesised transitive edge.
pub via: Vec<String>,
/// Shortest hop distance `from → to` over direct edges (1 for a direct edge,
/// ≥2 for a transitive one). Lets the renderer fade deeper hops.
pub hops: usize,
}
/// A laid-out node: a repo placed on a column/row grid.
#[derive(Debug, Clone)]
pub struct LaidNode {
pub repo: String,
pub col: usize,
pub row: usize,
/// Whether this node is currently collapsed (its exclusive subtree hidden).
pub collapsed: bool,
}
/// The complete laid-out dependency graph for one snapshot, in one display mode.
#[derive(Debug, Clone)]
pub struct DepGraphLayout {
/// `true` when the layout is the full transitive closure (C5 deep mode).
pub deep: bool,
pub nodes: Vec<LaidNode>,
pub edges: Vec<LaidEdge>,
/// Repos collapsed by the user (their exclusive subtree is hidden).
collapsed: BTreeSet<String>,
}
impl DepGraphLayout {
/// Build a layout from the repo set + the recorded snapshot edges.
///
/// * `repos` — every repo to place (the lanes), so isolated repos still show.
/// * `edges` — `snap.edges`: `from` depends on `to`.
/// * `deep` — false → draw only the direct edges; true → also synthesise the
/// transitive-closure edges (flagged [`EdgeClass::Transitive`]).
/// * `collapsed` — repos the user has collapsed (I3); their exclusively-owned
/// subtree is dropped from both nodes and edges.
pub fn build(
repos: &[String],
edges: &[CrossRepoEdge],
deep: bool,
collapsed: &BTreeSet<String>,
) -> Self {
// ── adjacency (direct deps) over the repo set ──────────────────────
let repo_set: BTreeSet<&str> = repos.iter().map(String::as_str).collect();
let mut adj: BTreeMap<&str, Vec<&str>> = BTreeMap::new();
let mut via_of: BTreeMap<(&str, &str), Vec<String>> = BTreeMap::new();
for e in edges {
if !repo_set.contains(e.from.as_str()) || !repo_set.contains(e.to.as_str()) {
continue;
}
adj.entry(e.from.as_str()).or_default().push(e.to.as_str());
via_of.insert(
(e.from.as_str(), e.to.as_str()),
e.via.iter().cloned().collect(),
);
}
// ── which nodes are hidden by a collapse? a node is hidden iff EVERY
// direct-dep path that reaches it passes through a collapsed repo
// (i.e. it is in the *exclusive* subtree of some collapsed node and
// has no surviving path from a non-collapsed root). We compute the
// set of nodes reachable WITHOUT descending past a collapsed repo,
// then hide the rest. Collapsed repos themselves stay visible (so the
// user can re-expand them) — only their hidden-only children vanish.
// A root is a top consumer: a repo with no incoming dep edge *from within
// the repo set* (nothing in-set depends on it). BFS from every root marks
// the reachable set; a node survives iff some path reaches it without
// descending out of a collapsed repo.
let roots: Vec<&str> = repos
.iter()
.map(String::as_str)
.filter(|r| {
!edges
.iter()
.any(|e| e.to == **r && repo_set.contains(e.from.as_str()))
})
.collect();
let mut visible: BTreeSet<&str> = BTreeSet::new();
let mut q: VecDeque<&str> = VecDeque::new();
for r in &roots {
if visible.insert(r) {
q.push_back(r);
}
}
// Roots set can miss repos in a cyclic / fully-connected graph; seed with
// any repo that has no incoming edge, else fall back to all repos so we
// never blank the canvas.
if visible.is_empty() {
for r in repos {
visible.insert(r.as_str());
q.push_back(r.as_str());
}
}
while let Some(cur) = q.pop_front() {
// Do not descend past a collapsed node — its children are hidden
// unless another (open) path reaches them.
if collapsed.contains(cur) {
continue;
}
if let Some(children) = adj.get(cur) {
for &c in children {
if visible.insert(c) {
q.push_back(c);
}
}
}
}
// Always keep the explicitly-collapsed repos themselves on screen.
for c in collapsed {
if repo_set.contains(c.as_str()) {
visible.insert(c.as_str());
}
}
let visible_repos: Vec<String> =
repos.iter().filter(|r| visible.contains(r.as_str())).cloned().collect();
// ── columns by topo rank (deps first → left). Use the longest-path
// rank so a transitive dep sits to the right of its shallowest user.
let rank = longest_path_rank(&visible_repos, &adj);
// Group repos per column, assign rows by stable repo-name order.
let mut by_col: BTreeMap<usize, Vec<String>> = BTreeMap::new();
for r in &visible_repos {
by_col.entry(*rank.get(r.as_str()).unwrap_or(&0)).or_default().push(r.clone());
}
let mut nodes: Vec<LaidNode> = Vec::new();
for (&col, repos_in_col) in &by_col {
for (row, repo) in repos_in_col.iter().enumerate() {
nodes.push(LaidNode {
repo: repo.clone(),
col,
row,
collapsed: collapsed.contains(repo),
});
}
}
nodes.sort_by(|a, b| a.repo.cmp(&b.repo));
// ── edges. Direct edges between two visible repos always drawn. In deep
// mode, additionally synthesise a Transitive edge for every (from,to)
// where `to` is reachable from `from` in ≥2 hops and there is NOT
// already a direct edge.
let vis_set: BTreeSet<&str> = visible_repos.iter().map(String::as_str).collect();
let mut laid: Vec<LaidEdge> = Vec::new();
let mut direct_pairs: BTreeSet<(String, String)> = BTreeSet::new();
for e in edges {
if vis_set.contains(e.from.as_str()) && vis_set.contains(e.to.as_str()) {
// hide a direct edge if it descends out of a collapsed node
if collapsed.contains(e.from.as_str()) {
continue;
}
direct_pairs.insert((e.from.clone(), e.to.clone()));
laid.push(LaidEdge {
from: e.from.clone(),
to: e.to.clone(),
class: EdgeClass::Direct,
via: via_of
.get(&(e.from.as_str(), e.to.as_str()))
.cloned()
.unwrap_or_default(),
hops: 1,
});
}
}
if deep {
for from in &visible_repos {
if collapsed.contains(from) {
continue;
}
for (to, hops) in bfs_distances(from, &adj) {
if hops < 2 || !vis_set.contains(to.as_str()) {
continue;
}
if direct_pairs.contains(&(from.clone(), to.clone())) {
continue;
}
laid.push(LaidEdge {
from: from.clone(),
to: to.clone(),
class: EdgeClass::Transitive,
via: Vec::new(),
hops,
});
}
}
}
Self { deep, nodes, edges: laid, collapsed: collapsed.clone() }
}
/// The transitive dependency closure of `repo` over the *recorded direct
/// edges* (not the laid-out edges) — every repo reachable following
/// `from → to`, excluding `repo` itself. The ground truth the deep-mode
/// synthesis and the tests assert against.
pub fn transitive_closure(repo: &str, edges: &[CrossRepoEdge]) -> BTreeSet<String> {
let mut adj: BTreeMap<&str, Vec<&str>> = BTreeMap::new();
for e in edges {
adj.entry(e.from.as_str()).or_default().push(e.to.as_str());
}
let mut seen: BTreeSet<String> = BTreeSet::new();
let mut q: VecDeque<&str> = VecDeque::new();
q.push_back(repo);
while let Some(cur) = q.pop_front() {
if let Some(children) = adj.get(cur) {
for &c in children {
if seen.insert(c.to_string()) {
q.push_back(c);
}
}
}
}
seen.remove(repo);
seen
}
/// The repos currently visible (after applying the collapse set).
pub fn visible(&self) -> Vec<String> {
self.nodes.iter().map(|n| n.repo.clone()).collect()
}
/// Look up a node's (col, row) by repo name.
pub fn position(&self, repo: &str) -> Option<(usize, usize)> {
self.nodes.iter().find(|n| n.repo == repo).map(|n| (n.col, n.row))
}
pub fn direct_edges(&self) -> usize {
self.edges.iter().filter(|e| e.class == EdgeClass::Direct).count()
}
pub fn transitive_edges(&self) -> usize {
self.edges.iter().filter(|e| e.class == EdgeClass::Transitive).count()
}
/// The introspection blob folded into the viz `state_json` (LAW #6): the
/// rendered graph structure — mode, node positions, classified edges, and
/// the collapse set — so a robot test sees exactly what is painted.
pub fn state_json(&self) -> serde_json::Value {
serde_json::json!({
"deep": self.deep,
"node_count": self.nodes.len(),
"direct_edges": self.direct_edges(),
"transitive_edges": self.transitive_edges(),
"collapsed": self.collapsed.iter().cloned().collect::<Vec<_>>(),
"nodes": self.nodes.iter().map(|n| serde_json::json!({
"repo": n.repo,
"col": n.col,
"row": n.row,
"collapsed": n.collapsed,
})).collect::<Vec<_>>(),
"edges": self.edges.iter().map(|e| serde_json::json!({
"from": e.from,
"to": e.to,
"class": e.class.as_str(),
"hops": e.hops,
"via": e.via,
})).collect::<Vec<_>>(),
})
}
}
/// Longest-path layering: a node's column is 1 + the max column of every repo
/// that depends on it... no — deps go LEFT, consumers RIGHT. We rank so that a
/// dependency always sits at a strictly *smaller* column than its consumer, so
/// arrows flow consumer(right) → dep(left) reads cleanly. Concretely: a repo's
/// column = max over its dependencies' columns + 1; leaves (no deps) get 0... we
/// invert that so deps are at col 0. We compute the longest dependency chain
/// FROM each node and place deeper deps further right.
fn longest_path_rank<'a>(
repos: &'a [String],
adj: &BTreeMap<&'a str, Vec<&'a str>>,
) -> BTreeMap<String, usize> {
// rank[r] = length of the longest path r → … (following from→to dep edges).
// A repo with no deps has rank 0; its consumer has rank ≥1. So deps (deeper
// chains) get LARGER ranks → placed further right.
let mut memo: BTreeMap<String, usize> = BTreeMap::new();
fn depth<'a>(
r: &'a str,
adj: &BTreeMap<&'a str, Vec<&'a str>>,
memo: &mut BTreeMap<String, usize>,
stack: &mut BTreeSet<String>,
) -> usize {
if let Some(&d) = memo.get(r) {
return d;
}
if !stack.insert(r.to_string()) {
return 0; // cycle guard
}
let mut best = 0;
if let Some(children) = adj.get(r) {
for &c in children {
best = best.max(1 + depth(c, adj, memo, stack));
}
}
stack.remove(r);
memo.insert(r.to_string(), best);
best
}
let mut stack = BTreeSet::new();
for r in repos {
let d = depth(r.as_str(), adj, &mut memo, &mut stack);
memo.insert(r.clone(), d);
}
// Now invert: the deepest dep chain should be on the RIGHT. The consumer
// (largest depth) goes LEFT (col 0). So col = max_depth - depth.
let max_depth = memo.values().copied().max().unwrap_or(0);
repos
.iter()
.map(|r| (r.clone(), max_depth - memo.get(r).copied().unwrap_or(0)))
.collect()
}
/// BFS shortest-hop distances from `start` over the direct-dep adjacency.
fn bfs_distances<'a>(
start: &str,
adj: &BTreeMap<&'a str, Vec<&'a str>>,
) -> Vec<(String, usize)> {
let mut dist: BTreeMap<String, usize> = BTreeMap::new();
let mut q: VecDeque<(String, usize)> = VecDeque::new();
q.push_back((start.to_string(), 0));
dist.insert(start.to_string(), 0);
while let Some((cur, d)) = q.pop_front() {
if let Some(children) = adj.get(cur.as_str()) {
for &c in children {
if !dist.contains_key(c) {
dist.insert(c.to_string(), d + 1);
q.push_back((c.to_string(), d + 1));
}
}
}
}
dist.into_iter().filter(|(r, _)| r != start).collect()
}
#[cfg(test)]
mod tests {
use super::*;
use std::collections::BTreeSet;
fn edge(from: &str, to: &str, via: &[&str]) -> CrossRepoEdge {
CrossRepoEdge::normal(from, to, via.iter().map(|s| s.to_string()).collect())
}
/// The C5 spec graph: A → B → C, plus a DIRECT A → C.
fn abc() -> (Vec<String>, Vec<CrossRepoEdge>) {
let repos = vec!["A".to_string(), "B".to_string(), "C".to_string()];
let edges = vec![
edge("A", "B", &["b_crate"]),
edge("B", "C", &["c_crate"]),
edge("A", "C", &["c_direct"]),
];
(repos, edges)
}
#[test]
fn transitive_closure_is_correct() {
let (_, edges) = abc();
// A's transitive set = {B, C}.
assert_eq!(
DepGraphLayout::transitive_closure("A", &edges),
["B", "C"].iter().map(|s| s.to_string()).collect::<BTreeSet<_>>()
);
// B's transitive set = {C}.
assert_eq!(
DepGraphLayout::transitive_closure("B", &edges),
["C"].iter().map(|s| s.to_string()).collect::<BTreeSet<_>>()
);
// C is a leaf.
assert!(DepGraphLayout::transitive_closure("C", &edges).is_empty());
}
#[test]
fn direct_mode_classifies_every_edge_direct() {
let (repos, edges) = abc();
let lay = DepGraphLayout::build(&repos, &edges, false, &BTreeSet::new());
assert_eq!(lay.direct_edges(), 3, "all 3 recorded edges are direct");
assert_eq!(lay.transitive_edges(), 0, "no synthesised edges in direct mode");
// A→B, B→C, A→C are all present and classified Direct.
for (f, t) in [("A", "B"), ("B", "C"), ("A", "C")] {
let e = lay.edges.iter().find(|e| e.from == f && e.to == t).expect("edge");
assert_eq!(e.class, EdgeClass::Direct, "{f}->{t} is direct");
assert_eq!(e.hops, 1);
}
}
#[test]
fn deep_mode_synthesises_only_genuinely_transitive_edges() {
// Drop the direct A→C so A→C becomes a *transitive* (2-hop) edge.
let repos = vec!["A".to_string(), "B".to_string(), "C".to_string()];
let edges = vec![edge("A", "B", &["b_crate"]), edge("B", "C", &["c_crate"])];
let lay = DepGraphLayout::build(&repos, &edges, true, &BTreeSet::new());
// Two direct edges (A→B, B→C) + one synthesised transitive (A→C, 2 hops).
assert_eq!(lay.direct_edges(), 2);
assert_eq!(lay.transitive_edges(), 1);
let t = lay
.edges
.iter()
.find(|e| e.class == EdgeClass::Transitive)
.expect("a transitive edge");
assert_eq!((t.from.as_str(), t.to.as_str()), ("A", "C"));
assert_eq!(t.hops, 2, "A reaches C in 2 hops");
}
#[test]
fn deep_mode_does_not_duplicate_an_existing_direct_edge() {
// With the direct A→C present, deep mode must NOT also add a transitive
// A→C (the direct edge wins; the pair is already covered).
let (repos, edges) = abc();
let lay = DepGraphLayout::build(&repos, &edges, true, &BTreeSet::new());
let ac: Vec<&LaidEdge> =
lay.edges.iter().filter(|e| e.from == "A" && e.to == "C").collect();
assert_eq!(ac.len(), 1, "exactly one A→C edge");
assert_eq!(ac[0].class, EdgeClass::Direct, "the direct A→C wins");
}
#[test]
fn layout_places_deps_right_of_consumers() {
let (repos, edges) = abc();
let lay = DepGraphLayout::build(&repos, &edges, false, &BTreeSet::new());
let col = |r: &str| lay.position(r).unwrap().0;
// A consumes B and C → A is left of both. B consumes C → B left of C.
assert!(col("A") < col("B"), "A (consumer) left of B");
assert!(col("B") < col("C"), "B left of C (its dep)");
assert!(col("A") < col("C"), "A left of C");
}
#[test]
fn state_json_exposes_positions_and_edge_classes() {
let (repos, edges) = abc();
let lay = DepGraphLayout::build(&repos, &edges, true, &BTreeSet::new());
let j = lay.state_json();
assert_eq!(j["deep"], serde_json::Value::Bool(true));
assert_eq!(j["node_count"], 3);
// every node carries a col + row
let nodes = j["nodes"].as_array().unwrap();
assert_eq!(nodes.len(), 3);
assert!(nodes.iter().all(|n| n["col"].is_number() && n["row"].is_number()));
// every edge carries a class in {direct, transitive}
let edges_j = j["edges"].as_array().unwrap();
assert!(edges_j.iter().all(|e| {
matches!(e["class"].as_str(), Some("direct") | Some("transitive"))
}));
// exactly the 3 direct edges (A→C direct present → no transitive dupes)
assert_eq!(j["direct_edges"], 3);
assert_eq!(j["transitive_edges"], 0);
}
#[test]
fn collapsing_a_node_hides_its_exclusive_subtree() {
// A → B → C. Collapse B: C is reachable only through B, so it is hidden;
// A and B remain.
let repos = vec!["A".to_string(), "B".to_string(), "C".to_string()];
let edges = vec![edge("A", "B", &["b"]), edge("B", "C", &["c"])];
let collapsed: BTreeSet<String> = ["B".to_string()].into_iter().collect();
let lay = DepGraphLayout::build(&repos, &edges, false, &collapsed);
let vis = lay.visible();
assert!(vis.contains(&"A".to_string()), "A stays");
assert!(vis.contains(&"B".to_string()), "collapsed B stays (to re-expand)");
assert!(!vis.contains(&"C".to_string()), "C hidden under collapsed B");
// the B→C edge is gone, A→B remains.
assert!(lay.edges.iter().any(|e| e.from == "A" && e.to == "B"));
assert!(!lay.edges.iter().any(|e| e.from == "B" && e.to == "C"));
}
#[test]
fn collapsing_keeps_a_node_with_an_alternate_open_path() {
// Diamond: A→B→D, A→C→D. Collapse B: D still reachable via C, so D stays.
let repos = ["A", "B", "C", "D"].iter().map(|s| s.to_string()).collect::<Vec<_>>();
let edges = vec![
edge("A", "B", &["b"]),
edge("A", "C", &["c"]),
edge("B", "D", &["d"]),
edge("C", "D", &["d"]),
];
let collapsed: BTreeSet<String> = ["B".to_string()].into_iter().collect();
let lay = DepGraphLayout::build(&repos, &edges, false, &collapsed);
assert!(lay.visible().contains(&"D".to_string()), "D survives via C");
// B→D hidden (descends out of collapsed B), C→D survives.
assert!(!lay.edges.iter().any(|e| e.from == "B" && e.to == "D"));
assert!(lay.edges.iter().any(|e| e.from == "C" && e.to == "D"));
}
}