facett-graphview/src/depgraph_layout.rs
//! **Pure (no-egui) dependency-graph layout + edge classification** — a re-home
//! of nornir's `src/viz/depgraph_layout.rs`. Domain-agnostic: instead of
//! nornir's `CrossRepoEdge` it takes a generic [`DepEdge`] (`from`/`to` + a
//! `via` label list), so any host (nornir's dep graph, a package graph, a graph-
//! DB browse) lays out the same way.
//!
//! Egui-free → inject-and-assert testable (feed a known multi-level graph and
//! assert the transitive closure, the direct-vs-transitive edge classification,
//! and the laid-out node positions) + introspectable ([`DepGraphLayout::state_json`]
//! folds straight into a viz `state_json` so a robot reads the rendered structure
//! without a screenshot).
//!
//! Two display modes:
//! * **direct** — only the edges the host recorded, one column per topo rank.
//! * **deep** — the FULL transitive closure: every `from` gets an edge to every
//! node reachable from it, the synthesised ones flagged so a renderer dims them.
//!
//! Click-to-expand: a node can be **collapsed**, hiding the subtree reachable
//! *only* through it; [`DepGraphLayout::visible`] reports which nodes survive.
use std::collections::{BTreeMap, BTreeSet, VecDeque};
/// One recorded dependency edge: `from` depends on `to`, justified by the `via`
/// labels (e.g. the crates the consumer pulls from the producer). The generic
/// stand-in for nornir's `CrossRepoEdge`.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct DepEdge {
pub from: String,
pub to: String,
/// Labels justifying the edge (empty is fine). Carried onto a [`LaidEdge`].
pub via: Vec<String>,
}
impl DepEdge {
/// Build an edge `from → to` with `via` justification labels.
pub fn new(from: impl Into<String>, to: impl Into<String>, via: &[&str]) -> Self {
Self {
from: from.into(),
to: to.into(),
via: via.iter().map(|s| s.to_string()).collect(),
}
}
}
/// How an edge in the laid-out graph relates to the recorded input.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum EdgeClass {
/// A directly-recorded edge (`from` consumes `to`).
Direct,
/// A transitive reachability edge synthesised in **deep** mode: `to` is
/// reachable from `from` only through one or more intermediate nodes.
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 labels (empty for a
/// synthesised transitive edge) + the shortest hop distance.
#[derive(Debug, Clone)]
pub struct LaidEdge {
pub from: String,
pub to: String,
pub class: EdgeClass,
/// Labels justifying a direct edge; empty for a synthesised transitive edge.
pub via: Vec<String>,
/// Shortest hop distance `from → to` over direct edges (1 for direct, ≥2 for
/// transitive). Lets a renderer fade deeper hops.
pub hops: usize,
}
/// A laid-out node: 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,
}
/// **How a [`DepGraphLayout`] places columns and rows** — the layout options of the
/// engine, so a host asks for a shape instead of moving nodes after the fact.
///
/// [`Default`] is the historical layout, unchanged: longest-path columns with the
/// leaves aligned in the last column ([`Align::Sinks`](facett_core::layered::Align)),
/// rows in input order, no pinned column.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct LayoutOpts {
/// Nodes pinned to the **first column** (col 0) — e.g. a workspace's repos, so they
/// line up together on the left. Every other node is laid out from column 1 on by
/// the rank of the graph WITHOUT the pinned nodes, so all edges leaving the pinned
/// column flow right. Empty = no pinned column.
pub first_column: BTreeSet<String>,
/// Which end the longest-path rank aligns: `Sinks` puts every leaf in the last
/// column, `Sources` puts a node right next to its deepest consumer.
pub align: facett_core::layered::Align,
/// Row order inside a column: input order, or barycenter sweeps (fewer crossings).
pub rows: facett_core::layered::RowOrder,
/// The most rows a column holds: a taller rank is STAGGERED over adjacent columns
/// (row `r` of a rank split `k` ways goes to sub-column `r mod k`, row `r div k`), so
/// its order top to bottom is kept and no edge runs inside a rank. A pinned first
/// column is never split. `None` = unbounded (one column per rank).
pub max_rows: Option<usize>,
}
impl Default for LayoutOpts {
fn default() -> Self {
Self {
first_column: BTreeSet::new(),
align: facett_core::layered::Align::Sinks,
rows: facett_core::layered::RowOrder::Input,
max_rows: None,
}
}
}
impl LayoutOpts {
/// `first_column` pinned left, the rest aligned to their consumers
/// ([`Align::Sources`](facett_core::layered::Align)), rows by barycenter — the
/// "roots on the left, what they use flowing right" shape.
pub fn roots_left(first_column: impl IntoIterator<Item = String>) -> Self {
Self {
first_column: first_column.into_iter().collect(),
align: facett_core::layered::Align::Sources,
rows: facett_core::layered::RowOrder::Barycenter { sweeps: 8 },
max_rows: None,
}
}
}
/// The complete laid-out dependency graph in one display mode.
#[derive(Debug, Clone)]
pub struct DepGraphLayout {
/// `true` when the layout is the full transitive closure (deep mode).
pub deep: bool,
pub nodes: Vec<LaidNode>,
pub edges: Vec<LaidEdge>,
collapsed: BTreeSet<String>,
}
impl DepGraphLayout {
/// Build a layout from the node set + the recorded edges.
///
/// * `repos` — every node to place (so isolated nodes still show).
/// * `edges` — `from` depends on `to`.
/// * `deep` — false → only direct edges; true → also synthesise the transitive-
/// closure edges (flagged [`EdgeClass::Transitive`]).
/// * `collapsed` — nodes the user collapsed; their exclusively-owned subtree
/// is dropped from both nodes and edges.
///
/// **O(V + E)** (plus the name sort of the output): every name is interned to a dense
/// id once, and the root test, the unfold walk and the longest-path rank run on
/// those ids. Until 2026-10-02 the root test filtered the whole edge list once per
/// repo — O(V·E), the reason the demo's `World coderoom` stopped at 1 000 crates.
/// The output (columns, rows, edge order, classes, via labels) is unchanged.
pub fn build(
repos: &[String],
edges: &[DepEdge],
deep: bool,
collapsed: &BTreeSet<String>,
) -> Self {
Self::build_with(repos, edges, deep, collapsed, &LayoutOpts::default())
}
/// [`build`](Self::build) with the [`LayoutOpts`] a host asks for (a pinned first
/// column, the rank alignment, the row order). The visible set, the edge classes and
/// the deep closure are the same as `build`'s; only columns and rows follow `opts`.
pub fn build_with(
repos: &[String],
edges: &[DepEdge],
deep: bool,
collapsed: &BTreeSet<String>,
opts: &LayoutOpts,
) -> Self {
use std::collections::{HashMap, HashSet};
// Dense ids: a repeated repo name keeps its first id (the old name sets merged it).
let mut id: HashMap<&str, u32> = HashMap::with_capacity(repos.len());
for r in repos {
let next = id.len() as u32;
id.entry(r.as_str()).or_insert(next);
}
let n = id.len();
// In-set edges as id pairs, in input order (the adjacency keeps that order).
let mut children: Vec<Vec<u32>> = vec![Vec::new(); n];
let mut via_of: HashMap<(u32, u32), usize> = HashMap::with_capacity(edges.len());
let mut depended_on = vec![false; n];
let mut pair: Vec<Option<(u32, u32)>> = Vec::with_capacity(edges.len());
for (ei, e) in edges.iter().enumerate() {
let p = match (id.get(e.from.as_str()), id.get(e.to.as_str())) {
(Some(&a), Some(&b)) => Some((a, b)),
_ => None,
};
pair.push(p);
if let Some((a, b)) = p {
children[a as usize].push(b);
via_of.insert((a, b), ei); // the last recorded edge's labels win, as before
depended_on[b as usize] = true;
}
}
let mut is_collapsed = vec![false; n];
for c in collapsed {
if let Some(&i) = id.get(c.as_str()) {
is_collapsed[i as usize] = true;
}
}
// A root is a top consumer: nothing in-set depends on it.
let mut visible = vec![false; n];
let mut q: VecDeque<u32> = VecDeque::new();
for r in repos {
let i = id[r.as_str()];
if !depended_on[i as usize] && !visible[i as usize] {
visible[i as usize] = true;
q.push_back(i);
}
}
if q.is_empty() {
for r in repos {
let i = id[r.as_str()];
visible[i as usize] = true;
q.push_back(i);
}
}
while let Some(cur) = q.pop_front() {
if is_collapsed[cur as usize] {
continue;
}
for &c in &children[cur as usize] {
if !visible[c as usize] {
visible[c as usize] = true;
q.push_back(c);
}
}
}
for (i, &c) in is_collapsed.iter().enumerate() {
if c {
visible[i] = true;
}
}
let visible_repos: Vec<&String> = repos
.iter()
.filter(|r| visible[id[r.as_str()] as usize])
.collect();
let order: Vec<u32> = visible_repos.iter().map(|r| id[r.as_str()]).collect();
let mut pinned = vec![false; n];
for p in &opts.first_column {
if let Some(&i) = id.get(p.as_str()) {
pinned[i as usize] = visible[i as usize];
}
}
let any_pinned = pinned.iter().any(|&p| p);
let rank: Vec<usize> = if any_pinned {
// The pinned column is 0; the rest is ranked WITHOUT the pinned nodes (their
// edges dropped), from column 1.
let rest: Vec<u32> = order.iter().copied().filter(|&i| !pinned[i as usize]).collect();
let unpinned: Vec<Vec<u32>> = children
.iter()
.enumerate()
.map(|(i, cs)| if pinned[i] { Vec::new() } else { cs.iter().copied().filter(|&c| !pinned[c as usize]).collect() })
.collect();
let r = rank_dense_aligned(&rest, &unpinned, opts.align);
(0..n).map(|i| if pinned[i] { 0 } else { r[i] + 1 }).collect()
} else {
rank_dense_aligned(&order, &children, opts.align)
};
// Rows in input order per column. With a pinned column the columns are compacted
// (no empty column between the pinned one and the rest); without, the rank IS the
// column, as it always was.
let used: BTreeSet<usize> = order.iter().map(|&i| rank[i as usize]).collect();
let compact: BTreeMap<usize, usize> =
used.iter().enumerate().map(|(k, &c)| (c, if any_pinned { k } else { c })).collect();
let mut col_of = vec![0u32; order.len()];
let mut row_of = vec![0u32; order.len()];
let mut fill: BTreeMap<u32, u32> = BTreeMap::new();
for (k, &i) in order.iter().enumerate() {
let c = compact[&rank[i as usize]] as u32;
let r = fill.entry(c).or_insert(0);
(col_of[k], row_of[k]) = (c, *r);
*r += 1;
}
if let facett_core::layered::RowOrder::Barycenter { sweeps } = opts.rows {
let local: std::collections::HashMap<u32, u32> = order.iter().enumerate().map(|(k, &i)| (i, k as u32)).collect();
let local_edges: Vec<(u32, u32)> = order
.iter()
.flat_map(|&i| children[i as usize].iter().map(move |&c| (i, c)))
.filter_map(|(a, b)| Some((*local.get(&a)?, *local.get(&b)?)))
.collect();
let mut lay = facett_core::layered::Layered {
cols: col_of.iter().max().map_or(0, |c| c + 1),
rows_max: fill.values().copied().max().unwrap_or(0),
col: col_of,
row: row_of,
cyclic: false,
};
facett_core::layered::barycenter_rows(&mut lay, &local_edges, sweeps);
(col_of, row_of) = (lay.col, lay.row);
}
if let Some(max) = opts.max_rows.filter(|&m| m > 0) {
(col_of, row_of) = stagger(&col_of, &row_of, max, any_pinned);
}
let mut nodes: Vec<LaidNode> = visible_repos
.iter()
.enumerate()
.map(|(k, repo)| LaidNode {
repo: (*repo).clone(),
col: col_of[k] as usize,
row: row_of[k] as usize,
collapsed: collapsed.contains(*repo),
})
.collect();
nodes.sort_by(|a, b| a.repo.cmp(&b.repo));
let mut laid: Vec<LaidEdge> = Vec::with_capacity(edges.len());
let mut direct_pairs: HashSet<(u32, u32)> = HashSet::new();
for (e, p) in edges.iter().zip(&pair) {
let Some((a, b)) = *p else { continue };
if !visible[a as usize] || !visible[b as usize] || is_collapsed[a as usize] {
continue;
}
if deep {
direct_pairs.insert((a, b));
}
laid.push(LaidEdge {
from: e.from.clone(),
to: e.to.clone(),
class: EdgeClass::Direct,
via: edges[via_of[&(a, b)]].via.clone(),
hops: 1,
});
}
if deep {
let mut adj: BTreeMap<&str, Vec<&str>> = BTreeMap::new();
for (e, p) in edges.iter().zip(&pair) {
if p.is_some() {
adj.entry(e.from.as_str()).or_default().push(e.to.as_str());
}
}
for from in &visible_repos {
let fi = id[from.as_str()];
if is_collapsed[fi as usize] {
continue;
}
for (to, hops) in bfs_distances(from, &adj) {
let ti = id[to.as_str()];
if hops < 2 || !visible[ti as usize] || direct_pairs.contains(&(fi, ti)) {
continue;
}
laid.push(LaidEdge {
from: (*from).clone(),
to,
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* — every node reachable following `from → to`, excluding `repo`.
pub fn transitive_closure(repo: &str, edges: &[DepEdge]) -> 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 nodes 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 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 (LAW 6): 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<_>>(),
})
}
}
/// Split every column taller than `max` rows over `ceil(rows / max)` adjacent columns,
/// interleaved (row `r` → sub-column `r mod k`, row `r div k`); later columns shift
/// right. Column 0 stays whole when `keep_first`.
fn stagger(col: &[u32], row: &[u32], max: usize, keep_first: bool) -> (Vec<u32>, Vec<u32>) {
let cols = col.iter().max().map_or(0, |c| c + 1) as usize;
let mut height = vec![0usize; cols];
for &c in col {
height[c as usize] += 1;
}
let split: Vec<usize> = height
.iter()
.enumerate()
.map(|(c, &h)| if keep_first && c == 0 { 1 } else { h.div_ceil(max).max(1) })
.collect();
let mut start = vec![0u32; cols];
for c in 1..cols {
start[c] = start[c - 1] + split[c - 1] as u32;
}
col.iter()
.zip(row)
.map(|(&c, &r)| {
let k = split[c as usize] as u32;
(start[c as usize] + r % k, r / k)
})
.unzip()
}
/// Longest-path layering: a node's column is `max_depth − depth`, where `depth`
/// is the longest dependency chain from the node, so dependencies sit to the
/// RIGHT of their consumers (arrows flow consumer → dep).
///
/// **O(V + E), iterative.** Every node is expanded once (then memoised) and every edge
/// is looked at once, on dense indices, with an explicit stack — no recursion, so a
/// 100 000-deep chain cannot overflow a thread's (or wasm's) stack. It is the exact
/// depth-first walk the recursive version (until 2026-10-02) made on DAGs.
/// The shared core now ignores back edges entirely, keeping cyclic graphs within
/// n columns instead of counting a phantom node at each cycle boundary.
#[cfg(test)]
fn longest_path_rank<'a>(
repos: &'a [String],
adj: &BTreeMap<&'a str, Vec<&'a str>>,
) -> BTreeMap<String, usize> {
use std::collections::HashMap;
let mut id: HashMap<&str, u32> = HashMap::with_capacity(repos.len());
let intern = |s: &'a str, id: &mut HashMap<&'a str, u32>| -> u32 {
let next = id.len() as u32;
*id.entry(s).or_insert(next)
};
for r in repos {
intern(r.as_str(), &mut id);
}
for (&from, tos) in adj {
intern(from, &mut id);
for &t in tos {
intern(t, &mut id);
}
}
let mut children: Vec<Vec<u32>> = vec![Vec::new(); id.len()];
for (&from, tos) in adj {
children[id[from] as usize] = tos.iter().map(|t| id[t]).collect();
}
let order: Vec<u32> = repos.iter().map(|r| id[r.as_str()]).collect();
let rank = rank_dense(&order, &children);
repos
.iter()
.map(|r| (r.clone(), rank[id[r.as_str()] as usize]))
.collect()
}
/// [`longest_path_rank`] on dense ids: the column of every id the walk from `order`
/// reaches (`children[i]` in edge order). Ids it never reaches get `max_depth`.
#[cfg(test)]
fn rank_dense(order: &[u32], children: &[Vec<u32>]) -> Vec<usize> {
rank_dense_aligned(order, children, facett_core::layered::Align::Sinks)
}
/// [`rank_dense`] with the alignment a [`LayoutOpts`] names.
fn rank_dense_aligned(order: &[u32], children: &[Vec<u32>], align: facett_core::layered::Align) -> Vec<usize> {
// Preserve this view's root order and its reachable-subgraph contract. Dense
// core ranks walks every id, so unreachable vertices become isolated sinks.
let n = children.len();
let mut id = vec![u32::MAX; n];
let mut original = Vec::with_capacity(n);
for &root in order {
if id[root as usize] == u32::MAX {
id[root as usize] = original.len() as u32;
original.push(root as usize);
}
}
for (i, mapped) in id.iter_mut().enumerate() {
if *mapped == u32::MAX {
*mapped = original.len() as u32;
original.push(i);
}
}
let mut reached = vec![false; n];
let mut pending = order.to_vec();
while let Some(node) = pending.pop() {
if std::mem::replace(&mut reached[node as usize], true) {
continue;
}
pending.extend_from_slice(&children[node as usize]);
}
let edges: Vec<_> = original
.iter()
.filter(|&&i| reached[i])
.flat_map(|&i| children[i].iter().map(move |&j| (i, j as usize)))
.map(|(i, j)| (id[i], id[j]))
.collect();
let ranks = facett_core::layered::ranks(n, &edges, align).0;
id.into_iter().map(|i| ranks[i as usize] as usize).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::*;
/// The spec graph: A → B → C, plus a DIRECT A → C.
fn abc() -> (Vec<String>, Vec<DepEdge>) {
let repos = vec!["A".to_string(), "B".to_string(), "C".to_string()];
let edges = vec![
DepEdge::new("A", "B", &["b_crate"]),
DepEdge::new("B", "C", &["c_crate"]),
DepEdge::new("A", "C", &["c_direct"]),
];
(repos, edges)
}
#[test]
fn transitive_closure_is_correct() {
let (_, edges) = abc();
assert_eq!(
DepGraphLayout::transitive_closure("A", &edges),
["B", "C"]
.iter()
.map(|s| s.to_string())
.collect::<BTreeSet<_>>()
);
assert_eq!(
DepGraphLayout::transitive_closure("B", &edges),
["C"].iter().map(|s| s.to_string()).collect::<BTreeSet<_>>()
);
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);
assert_eq!(lay.transitive_edges(), 0);
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);
assert_eq!(e.hops, 1);
}
// the via labels survive onto the laid edge.
let ab = lay
.edges
.iter()
.find(|e| e.from == "A" && e.to == "B")
.unwrap();
assert_eq!(ab.via, vec!["b_crate".to_string()]);
}
#[test]
fn deep_mode_synthesises_only_genuinely_transitive_edges() {
let repos = vec!["A".to_string(), "B".to_string(), "C".to_string()];
let edges = vec![
DepEdge::new("A", "B", &["b"]),
DepEdge::new("B", "C", &["c"]),
];
let lay = DepGraphLayout::build(&repos, &edges, true, &BTreeSet::new());
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);
}
#[test]
fn deep_mode_does_not_duplicate_an_existing_direct_edge() {
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);
assert_eq!(ac[0].class, EdgeClass::Direct);
}
#[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;
assert!(col("A") < col("B"));
assert!(col("B") < col("C"));
assert!(col("A") < col("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);
let nodes = j["nodes"].as_array().unwrap();
assert!(
nodes
.iter()
.all(|n| n["col"].is_number() && n["row"].is_number())
);
let edges_j = j["edges"].as_array().unwrap();
assert!(
edges_j
.iter()
.all(|e| matches!(e["class"].as_str(), Some("direct") | Some("transitive")))
);
assert_eq!(j["direct_edges"], 3);
assert_eq!(j["transitive_edges"], 0);
}
#[test]
fn collapsing_a_node_hides_its_exclusive_subtree() {
let repos = vec!["A".to_string(), "B".to_string(), "C".to_string()];
let edges = vec![
DepEdge::new("A", "B", &["b"]),
DepEdge::new("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()));
assert!(vis.contains(&"B".to_string()));
assert!(!vis.contains(&"C".to_string()));
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() {
let repos = ["A", "B", "C", "D"]
.iter()
.map(|s| s.to_string())
.collect::<Vec<_>>();
let edges = vec![
DepEdge::new("A", "B", &["b"]),
DepEdge::new("A", "C", &["c"]),
DepEdge::new("B", "D", &["d"]),
DepEdge::new("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()));
assert!(!lay.edges.iter().any(|e| e.from == "B" && e.to == "D"));
assert!(lay.edges.iter().any(|e| e.from == "C" && e.to == "D"));
}
/// Independent recursive reference for the shared core contract. DAG ranks
/// are unchanged. For cycles, skip the back edge rather than adding the old
/// extra column for a synthetic zero-depth node.
fn reference_rank(
repos: &[String],
adj: &BTreeMap<&str, Vec<&str>>,
) -> BTreeMap<String, usize> {
fn depth(
r: &str,
adj: &BTreeMap<&str, Vec<&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;
}
let mut best = 0;
if let Some(children) = adj.get(r) {
for &c in children {
if !stack.contains(c) {
best = best.max(1 + depth(c, adj, memo, stack));
}
}
}
stack.remove(r);
memo.insert(r.to_string(), best);
best
}
let mut memo = BTreeMap::new();
let mut stack = BTreeSet::new();
for r in repos {
depth(r, adj, &mut memo, &mut stack);
}
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()
}
/// A seeded random digraph on `n` nodes with `m` edges (cycles, self-loops and
/// duplicate edges all allowed — the generator's graphs have every one of them).
fn random_graph(n: usize, m: usize, seed: u64) -> (Vec<String>, Vec<DepEdge>) {
let mut s = seed.wrapping_mul(0x9E37_79B9_7F4A_7C15) | 1;
let mut next = move || {
s ^= s << 13;
s ^= s >> 7;
s ^= s << 17;
s
};
let repos: Vec<String> = (0..n).map(|i| format!("r{i}")).collect();
let edges = (0..m)
.map(|_| {
let (a, b) = ((next() % n as u64) as usize, (next() % n as u64) as usize);
DepEdge::new(repos[a].clone(), repos[b].clone(), &[])
})
.collect();
(repos, edges)
}
#[test]
fn shared_rank_matches_recursive_reference_with_back_edges_ignored() {
for seed in 1..60u64 {
let n = 2 + (seed as usize * 7) % 40;
let (repos, edges) = random_graph(n, n * (1 + seed as usize % 3), seed);
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());
}
assert_eq!(
longest_path_rank(&repos, &adj),
reference_rank(&repos, &adj),
"seed {seed}"
);
}
}
/// **The layout is O(V + E)** — a 100 000-node, 300 000-edge world (the demo's
/// `World coderoom` ceiling) lays out inside a budget, and a deep chain does not
/// overflow the stack. Release on dwarf: see `facett-benchmarks.md` (lane G).
#[test]
fn a_100k_world_lays_out_in_linear_time() {
let (repos, mut edges) = random_graph(100_000, 300_000, 7);
// A 100 000-deep chain on top: the recursive rank overflowed a thread stack here.
for i in 1..repos.len() {
edges.push(DepEdge::new(repos[i - 1].clone(), repos[i].clone(), &[]));
}
let t0 = std::time::Instant::now();
let lay = DepGraphLayout::build(&repos, &edges, false, &BTreeSet::new());
let dt = t0.elapsed();
assert_eq!(lay.nodes.len(), repos.len());
assert_eq!(lay.direct_edges(), edges.len());
let budget = if cfg!(debug_assertions) { 30.0 } else { 3.0 };
eprintln!(
"DepGraphLayout::build 100k nodes / {} edges: {dt:?} (budget {budget} s)",
edges.len()
);
assert!(
dt.as_secs_f64() < budget,
"100k layout took {dt:?}, budget {budget} s"
);
}
/// **A pinned first column.** Three repos at different depths: the default layout
/// (leaves aligned right) spreads them over three columns; `roots_left` puts all
/// three in column 0, and what they use flows right from column 1 — a crate nothing
/// in the rest depends on (`x`) still starts in column 1, never among the repos.
#[test]
fn roots_left_pins_the_repos_in_the_first_column() {
let repos: Vec<String> = ["r1", "r2", "r3", "a", "b", "c", "x"].iter().map(|s| s.to_string()).collect();
let edges = vec![
DepEdge::new("r1", "a", &[]),
DepEdge::new("a", "b", &[]),
DepEdge::new("b", "c", &[]),
DepEdge::new("r2", "c", &[]),
DepEdge::new("r3", "b", &[]),
DepEdge::new("x", "c", &[]),
];
let def = DepGraphLayout::build(&repos, &edges, false, &BTreeSet::new());
let def_cols: BTreeSet<usize> = ["r1", "r2", "r3"].iter().map(|r| def.position(r).unwrap().0).collect();
assert!(def_cols.len() > 1, "the default spreads the repos: {def_cols:?}");
let opts = LayoutOpts::roots_left(["r1", "r2", "r3"].iter().map(|s| s.to_string()));
let lay = DepGraphLayout::build_with(&repos, &edges, false, &BTreeSet::new(), &opts);
for r in ["r1", "r2", "r3"] {
assert_eq!(lay.position(r).unwrap().0, 0, "{r} in column 0: {}", lay.state_json());
}
let col = |n: &str| lay.position(n).unwrap().0;
assert_eq!((col("a"), col("x")), (1, 1), "the rest starts in column 1");
assert!(col("a") < col("b") && col("b") < col("c"), "deps flow right");
let rows: BTreeSet<usize> = ["r1", "r2", "r3"].iter().map(|r| lay.position(r).unwrap().1).collect();
assert_eq!(rows.len(), 3, "one row each");
assert_eq!(lay.nodes.len(), repos.len(), "nothing dropped");
assert_eq!(lay.direct_edges(), edges.len());
// max_rows staggers a tall rank, keeps the pinned column whole, edges flow right
let mut repos: Vec<String> = (0..5).map(|i| format!("r{i}")).collect();
let mut edges = Vec::new();
for i in 0..9 {
repos.push(format!("c{i}"));
edges.push(DepEdge::new(format!("r{}", i % 5), format!("c{i}"), &[]));
edges.push(DepEdge::new(format!("c{i}"), "leaf", &[]));
}
repos.push("leaf".into());
let mut opts = LayoutOpts::roots_left((0..5).map(|i| format!("r{i}")));
opts.max_rows = Some(4);
let lay = DepGraphLayout::build_with(&repos, &edges, false, &BTreeSet::new(), &opts);
let col = |n: &str| lay.position(n).unwrap().0;
assert!((0..5).all(|i| col(&format!("r{i}")) == 0), "the pinned column stays whole: {}", lay.state_json());
let crate_cols: BTreeSet<usize> = (0..9).map(|i| col(&format!("c{i}"))).collect();
assert_eq!(crate_cols, [1, 2, 3].into_iter().collect(), "9 rows over 3 columns of ≤ 4");
assert!((0..9).all(|i| lay.position(&format!("c{i}")).unwrap().1 < 4));
assert_eq!(col("leaf"), 4, "the next rank moves right of the staggered one");
}
}