facett_graphview/
depgraph_layout.rs

1//! **Pure (no-egui) dependency-graph layout + edge classification** — a re-home
2//! of nornir's `src/viz/depgraph_layout.rs`. Domain-agnostic: instead of
3//! nornir's `CrossRepoEdge` it takes a generic [`DepEdge`] (`from`/`to` + a
4//! `via` label list), so any host (nornir's dep graph, a package graph, a graph-
5//! DB browse) lays out the same way.
6//!
7//! Egui-free → inject-and-assert testable (feed a known multi-level graph and
8//! assert the transitive closure, the direct-vs-transitive edge classification,
9//! and the laid-out node positions) + introspectable ([`DepGraphLayout::state_json`]
10//! folds straight into a viz `state_json` so a robot reads the rendered structure
11//! without a screenshot).
12//!
13//! Two display modes:
14//!   * **direct** — only the edges the host recorded, one column per topo rank.
15//!   * **deep** — the FULL transitive closure: every `from` gets an edge to every
16//!     node reachable from it, the synthesised ones flagged so a renderer dims them.
17//!
18//! Click-to-expand: a node can be **collapsed**, hiding the subtree reachable
19//! *only* through it; [`DepGraphLayout::visible`] reports which nodes survive.
20
21use std::collections::{BTreeMap, BTreeSet, VecDeque};
22
23/// One recorded dependency edge: `from` depends on `to`, justified by the `via`
24/// labels (e.g. the crates the consumer pulls from the producer). The generic
25/// stand-in for nornir's `CrossRepoEdge`.
26#[derive(Debug, Clone, PartialEq, Eq)]
27pub struct DepEdge {
28    pub from: String,
29    pub to: String,
30    /// Labels justifying the edge (empty is fine). Carried onto a [`LaidEdge`].
31    pub via: Vec<String>,
32}
33
34impl DepEdge {
35    /// Build an edge `from → to` with `via` justification labels.
36    pub fn new(from: impl Into<String>, to: impl Into<String>, via: &[&str]) -> Self {
37        Self { from: from.into(), to: to.into(), via: via.iter().map(|s| s.to_string()).collect() }
38    }
39}
40
41/// How an edge in the laid-out graph relates to the recorded input.
42#[derive(Debug, Clone, Copy, PartialEq, Eq)]
43pub enum EdgeClass {
44    /// A directly-recorded edge (`from` consumes `to`).
45    Direct,
46    /// A transitive reachability edge synthesised in **deep** mode: `to` is
47    /// reachable from `from` only through one or more intermediate nodes.
48    Transitive,
49}
50
51impl EdgeClass {
52    pub fn as_str(self) -> &'static str {
53        match self {
54            EdgeClass::Direct => "direct",
55            EdgeClass::Transitive => "transitive",
56        }
57    }
58}
59
60/// A laid-out edge: endpoints + classification + the via labels (empty for a
61/// synthesised transitive edge) + the shortest hop distance.
62#[derive(Debug, Clone)]
63pub struct LaidEdge {
64    pub from: String,
65    pub to: String,
66    pub class: EdgeClass,
67    /// Labels justifying a direct edge; empty for a synthesised transitive edge.
68    pub via: Vec<String>,
69    /// Shortest hop distance `from → to` over direct edges (1 for direct, ≥2 for
70    /// transitive). Lets a renderer fade deeper hops.
71    pub hops: usize,
72}
73
74/// A laid-out node: placed on a column/row grid.
75#[derive(Debug, Clone)]
76pub struct LaidNode {
77    pub repo: String,
78    pub col: usize,
79    pub row: usize,
80    /// Whether this node is currently collapsed (its exclusive subtree hidden).
81    pub collapsed: bool,
82}
83
84/// The complete laid-out dependency graph in one display mode.
85#[derive(Debug, Clone)]
86pub struct DepGraphLayout {
87    /// `true` when the layout is the full transitive closure (deep mode).
88    pub deep: bool,
89    pub nodes: Vec<LaidNode>,
90    pub edges: Vec<LaidEdge>,
91    collapsed: BTreeSet<String>,
92}
93
94impl DepGraphLayout {
95    /// Build a layout from the node set + the recorded edges.
96    ///
97    /// * `repos` — every node to place (so isolated nodes still show).
98    /// * `edges` — `from` depends on `to`.
99    /// * `deep` — false → only direct edges; true → also synthesise the transitive-
100    ///   closure edges (flagged [`EdgeClass::Transitive`]).
101    /// * `collapsed` — nodes the user collapsed; their exclusively-owned subtree
102    ///   is dropped from both nodes and edges.
103    pub fn build(repos: &[String], edges: &[DepEdge], deep: bool, collapsed: &BTreeSet<String>) -> Self {
104        let repo_set: BTreeSet<&str> = repos.iter().map(String::as_str).collect();
105        let mut adj: BTreeMap<&str, Vec<&str>> = BTreeMap::new();
106        let mut via_of: BTreeMap<(&str, &str), Vec<String>> = BTreeMap::new();
107        for e in edges {
108            if !repo_set.contains(e.from.as_str()) || !repo_set.contains(e.to.as_str()) {
109                continue;
110            }
111            adj.entry(e.from.as_str()).or_default().push(e.to.as_str());
112            via_of.insert((e.from.as_str(), e.to.as_str()), e.via.clone());
113        }
114
115        // A root is a top consumer: nothing in-set depends on it.
116        let roots: Vec<&str> = repos
117            .iter()
118            .map(String::as_str)
119            .filter(|r| !edges.iter().any(|e| e.to == **r && repo_set.contains(e.from.as_str())))
120            .collect();
121        let mut visible: BTreeSet<&str> = BTreeSet::new();
122        let mut q: VecDeque<&str> = VecDeque::new();
123        for r in &roots {
124            if visible.insert(r) {
125                q.push_back(r);
126            }
127        }
128        if visible.is_empty() {
129            for r in repos {
130                visible.insert(r.as_str());
131                q.push_back(r.as_str());
132            }
133        }
134        while let Some(cur) = q.pop_front() {
135            if collapsed.contains(cur) {
136                continue;
137            }
138            if let Some(children) = adj.get(cur) {
139                for &c in children {
140                    if visible.insert(c) {
141                        q.push_back(c);
142                    }
143                }
144            }
145        }
146        for c in collapsed {
147            if repo_set.contains(c.as_str()) {
148                visible.insert(c.as_str());
149            }
150        }
151
152        let visible_repos: Vec<String> =
153            repos.iter().filter(|r| visible.contains(r.as_str())).cloned().collect();
154
155        let rank = longest_path_rank(&visible_repos, &adj);
156        let mut by_col: BTreeMap<usize, Vec<String>> = BTreeMap::new();
157        for r in &visible_repos {
158            by_col.entry(*rank.get(r.as_str()).unwrap_or(&0)).or_default().push(r.clone());
159        }
160        let mut nodes: Vec<LaidNode> = Vec::new();
161        for (&col, repos_in_col) in &by_col {
162            for (row, repo) in repos_in_col.iter().enumerate() {
163                nodes.push(LaidNode { repo: repo.clone(), col, row, collapsed: collapsed.contains(repo) });
164            }
165        }
166        nodes.sort_by(|a, b| a.repo.cmp(&b.repo));
167
168        let vis_set: BTreeSet<&str> = visible_repos.iter().map(String::as_str).collect();
169        let mut laid: Vec<LaidEdge> = Vec::new();
170        let mut direct_pairs: BTreeSet<(String, String)> = BTreeSet::new();
171        for e in edges {
172            if vis_set.contains(e.from.as_str()) && vis_set.contains(e.to.as_str()) {
173                if collapsed.contains(e.from.as_str()) {
174                    continue;
175                }
176                direct_pairs.insert((e.from.clone(), e.to.clone()));
177                laid.push(LaidEdge {
178                    from: e.from.clone(),
179                    to: e.to.clone(),
180                    class: EdgeClass::Direct,
181                    via: via_of.get(&(e.from.as_str(), e.to.as_str())).cloned().unwrap_or_default(),
182                    hops: 1,
183                });
184            }
185        }
186        if deep {
187            for from in &visible_repos {
188                if collapsed.contains(from) {
189                    continue;
190                }
191                for (to, hops) in bfs_distances(from, &adj) {
192                    if hops < 2 || !vis_set.contains(to.as_str()) {
193                        continue;
194                    }
195                    if direct_pairs.contains(&(from.clone(), to.clone())) {
196                        continue;
197                    }
198                    laid.push(LaidEdge {
199                        from: from.clone(),
200                        to: to.clone(),
201                        class: EdgeClass::Transitive,
202                        via: Vec::new(),
203                        hops,
204                    });
205                }
206            }
207        }
208
209        Self { deep, nodes, edges: laid, collapsed: collapsed.clone() }
210    }
211
212    /// The transitive dependency closure of `repo` over the *recorded direct
213    /// edges* — every node reachable following `from → to`, excluding `repo`.
214    pub fn transitive_closure(repo: &str, edges: &[DepEdge]) -> BTreeSet<String> {
215        let mut adj: BTreeMap<&str, Vec<&str>> = BTreeMap::new();
216        for e in edges {
217            adj.entry(e.from.as_str()).or_default().push(e.to.as_str());
218        }
219        let mut seen: BTreeSet<String> = BTreeSet::new();
220        let mut q: VecDeque<&str> = VecDeque::new();
221        q.push_back(repo);
222        while let Some(cur) = q.pop_front() {
223            if let Some(children) = adj.get(cur) {
224                for &c in children {
225                    if seen.insert(c.to_string()) {
226                        q.push_back(c);
227                    }
228                }
229            }
230        }
231        seen.remove(repo);
232        seen
233    }
234
235    /// The nodes currently visible (after applying the collapse set).
236    pub fn visible(&self) -> Vec<String> {
237        self.nodes.iter().map(|n| n.repo.clone()).collect()
238    }
239
240    /// Look up a node's (col, row) by name.
241    pub fn position(&self, repo: &str) -> Option<(usize, usize)> {
242        self.nodes.iter().find(|n| n.repo == repo).map(|n| (n.col, n.row))
243    }
244
245    pub fn direct_edges(&self) -> usize {
246        self.edges.iter().filter(|e| e.class == EdgeClass::Direct).count()
247    }
248
249    pub fn transitive_edges(&self) -> usize {
250        self.edges.iter().filter(|e| e.class == EdgeClass::Transitive).count()
251    }
252
253    /// The introspection blob (LAW 6): mode, node positions, classified edges,
254    /// and the collapse set — so a robot test sees exactly what is painted.
255    pub fn state_json(&self) -> serde_json::Value {
256        serde_json::json!({
257            "deep": self.deep,
258            "node_count": self.nodes.len(),
259            "direct_edges": self.direct_edges(),
260            "transitive_edges": self.transitive_edges(),
261            "collapsed": self.collapsed.iter().cloned().collect::<Vec<_>>(),
262            "nodes": self.nodes.iter().map(|n| serde_json::json!({
263                "repo": n.repo, "col": n.col, "row": n.row, "collapsed": n.collapsed,
264            })).collect::<Vec<_>>(),
265            "edges": self.edges.iter().map(|e| serde_json::json!({
266                "from": e.from, "to": e.to, "class": e.class.as_str(), "hops": e.hops, "via": e.via,
267            })).collect::<Vec<_>>(),
268        })
269    }
270}
271
272/// Longest-path layering: a node's column is `max_depth − depth`, where `depth`
273/// is the longest dependency chain from the node, so dependencies sit to the
274/// RIGHT of their consumers (arrows flow consumer → dep).
275fn longest_path_rank<'a>(repos: &'a [String], adj: &BTreeMap<&'a str, Vec<&'a str>>) -> BTreeMap<String, usize> {
276    let mut memo: BTreeMap<String, usize> = BTreeMap::new();
277    fn depth<'a>(
278        r: &'a str,
279        adj: &BTreeMap<&'a str, Vec<&'a str>>,
280        memo: &mut BTreeMap<String, usize>,
281        stack: &mut BTreeSet<String>,
282    ) -> usize {
283        if let Some(&d) = memo.get(r) {
284            return d;
285        }
286        if !stack.insert(r.to_string()) {
287            return 0; // cycle guard
288        }
289        let mut best = 0;
290        if let Some(children) = adj.get(r) {
291            for &c in children {
292                best = best.max(1 + depth(c, adj, memo, stack));
293            }
294        }
295        stack.remove(r);
296        memo.insert(r.to_string(), best);
297        best
298    }
299    let mut stack = BTreeSet::new();
300    for r in repos {
301        // `depth` memoizes `memo[r]` itself, so no extra insert (or clone) is needed.
302        depth(r.as_str(), adj, &mut memo, &mut stack);
303    }
304    let max_depth = memo.values().copied().max().unwrap_or(0);
305    repos.iter().map(|r| (r.clone(), max_depth - memo.get(r).copied().unwrap_or(0))).collect()
306}
307
308/// BFS shortest-hop distances from `start` over the direct-dep adjacency.
309fn bfs_distances<'a>(start: &str, adj: &BTreeMap<&'a str, Vec<&'a str>>) -> Vec<(String, usize)> {
310    let mut dist: BTreeMap<String, usize> = BTreeMap::new();
311    let mut q: VecDeque<(String, usize)> = VecDeque::new();
312    q.push_back((start.to_string(), 0));
313    dist.insert(start.to_string(), 0);
314    while let Some((cur, d)) = q.pop_front() {
315        if let Some(children) = adj.get(cur.as_str()) {
316            for &c in children {
317                if !dist.contains_key(c) {
318                    dist.insert(c.to_string(), d + 1);
319                    q.push_back((c.to_string(), d + 1));
320                }
321            }
322        }
323    }
324    dist.into_iter().filter(|(r, _)| r != start).collect()
325}
326
327#[cfg(test)]
328mod tests {
329    use super::*;
330
331    /// The spec graph: A → B → C, plus a DIRECT A → C.
332    fn abc() -> (Vec<String>, Vec<DepEdge>) {
333        let repos = vec!["A".to_string(), "B".to_string(), "C".to_string()];
334        let edges =
335            vec![DepEdge::new("A", "B", &["b_crate"]), DepEdge::new("B", "C", &["c_crate"]), DepEdge::new("A", "C", &["c_direct"])];
336        (repos, edges)
337    }
338
339    #[test]
340    fn transitive_closure_is_correct() {
341        let (_, edges) = abc();
342        assert_eq!(
343            DepGraphLayout::transitive_closure("A", &edges),
344            ["B", "C"].iter().map(|s| s.to_string()).collect::<BTreeSet<_>>()
345        );
346        assert_eq!(
347            DepGraphLayout::transitive_closure("B", &edges),
348            ["C"].iter().map(|s| s.to_string()).collect::<BTreeSet<_>>()
349        );
350        assert!(DepGraphLayout::transitive_closure("C", &edges).is_empty());
351    }
352
353    #[test]
354    fn direct_mode_classifies_every_edge_direct() {
355        let (repos, edges) = abc();
356        let lay = DepGraphLayout::build(&repos, &edges, false, &BTreeSet::new());
357        assert_eq!(lay.direct_edges(), 3);
358        assert_eq!(lay.transitive_edges(), 0);
359        for (f, t) in [("A", "B"), ("B", "C"), ("A", "C")] {
360            let e = lay.edges.iter().find(|e| e.from == f && e.to == t).expect("edge");
361            assert_eq!(e.class, EdgeClass::Direct);
362            assert_eq!(e.hops, 1);
363        }
364        // the via labels survive onto the laid edge.
365        let ab = lay.edges.iter().find(|e| e.from == "A" && e.to == "B").unwrap();
366        assert_eq!(ab.via, vec!["b_crate".to_string()]);
367    }
368
369    #[test]
370    fn deep_mode_synthesises_only_genuinely_transitive_edges() {
371        let repos = vec!["A".to_string(), "B".to_string(), "C".to_string()];
372        let edges = vec![DepEdge::new("A", "B", &["b"]), DepEdge::new("B", "C", &["c"])];
373        let lay = DepGraphLayout::build(&repos, &edges, true, &BTreeSet::new());
374        assert_eq!(lay.direct_edges(), 2);
375        assert_eq!(lay.transitive_edges(), 1);
376        let t = lay.edges.iter().find(|e| e.class == EdgeClass::Transitive).expect("a transitive edge");
377        assert_eq!((t.from.as_str(), t.to.as_str()), ("A", "C"));
378        assert_eq!(t.hops, 2);
379    }
380
381    #[test]
382    fn deep_mode_does_not_duplicate_an_existing_direct_edge() {
383        let (repos, edges) = abc();
384        let lay = DepGraphLayout::build(&repos, &edges, true, &BTreeSet::new());
385        let ac: Vec<&LaidEdge> = lay.edges.iter().filter(|e| e.from == "A" && e.to == "C").collect();
386        assert_eq!(ac.len(), 1);
387        assert_eq!(ac[0].class, EdgeClass::Direct);
388    }
389
390    #[test]
391    fn layout_places_deps_right_of_consumers() {
392        let (repos, edges) = abc();
393        let lay = DepGraphLayout::build(&repos, &edges, false, &BTreeSet::new());
394        let col = |r: &str| lay.position(r).unwrap().0;
395        assert!(col("A") < col("B"));
396        assert!(col("B") < col("C"));
397        assert!(col("A") < col("C"));
398    }
399
400    #[test]
401    fn state_json_exposes_positions_and_edge_classes() {
402        let (repos, edges) = abc();
403        let lay = DepGraphLayout::build(&repos, &edges, true, &BTreeSet::new());
404        let j = lay.state_json();
405        assert_eq!(j["deep"], serde_json::Value::Bool(true));
406        assert_eq!(j["node_count"], 3);
407        let nodes = j["nodes"].as_array().unwrap();
408        assert!(nodes.iter().all(|n| n["col"].is_number() && n["row"].is_number()));
409        let edges_j = j["edges"].as_array().unwrap();
410        assert!(edges_j.iter().all(|e| matches!(e["class"].as_str(), Some("direct") | Some("transitive"))));
411        assert_eq!(j["direct_edges"], 3);
412        assert_eq!(j["transitive_edges"], 0);
413    }
414
415    #[test]
416    fn collapsing_a_node_hides_its_exclusive_subtree() {
417        let repos = vec!["A".to_string(), "B".to_string(), "C".to_string()];
418        let edges = vec![DepEdge::new("A", "B", &["b"]), DepEdge::new("B", "C", &["c"])];
419        let collapsed: BTreeSet<String> = ["B".to_string()].into_iter().collect();
420        let lay = DepGraphLayout::build(&repos, &edges, false, &collapsed);
421        let vis = lay.visible();
422        assert!(vis.contains(&"A".to_string()));
423        assert!(vis.contains(&"B".to_string()));
424        assert!(!vis.contains(&"C".to_string()));
425        assert!(lay.edges.iter().any(|e| e.from == "A" && e.to == "B"));
426        assert!(!lay.edges.iter().any(|e| e.from == "B" && e.to == "C"));
427    }
428
429    #[test]
430    fn collapsing_keeps_a_node_with_an_alternate_open_path() {
431        let repos = ["A", "B", "C", "D"].iter().map(|s| s.to_string()).collect::<Vec<_>>();
432        let edges = vec![
433            DepEdge::new("A", "B", &["b"]),
434            DepEdge::new("A", "C", &["c"]),
435            DepEdge::new("B", "D", &["d"]),
436            DepEdge::new("C", "D", &["d"]),
437        ];
438        let collapsed: BTreeSet<String> = ["B".to_string()].into_iter().collect();
439        let lay = DepGraphLayout::build(&repos, &edges, false, &collapsed);
440        assert!(lay.visible().contains(&"D".to_string()));
441        assert!(!lay.edges.iter().any(|e| e.from == "B" && e.to == "D"));
442        assert!(lay.edges.iter().any(|e| e.from == "C" && e.to == "D"));
443    }
444}
facett_graphview/depgraph_layout.rs

facett_graphview/
depgraph_layout.rs
