facett-graphview 0.1.12

//! **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,
}

/// 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.
    pub fn build(repos: &[String], edges: &[DepEdge], deep: bool, collapsed: &BTreeSet<String>) -> Self {
        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.clone());
        }

        // A root is a top consumer: nothing in-set depends on it.
        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);
            }
        }
        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() {
            if collapsed.contains(cur) {
                continue;
            }
            if let Some(children) = adj.get(cur) {
                for &c in children {
                    if visible.insert(c) {
                        q.push_back(c);
                    }
                }
            }
        }
        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();

        let rank = longest_path_rank(&visible_repos, &adj);
        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));

        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()) {
                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* — 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<_>>(),
        })
    }
}

/// 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).
fn longest_path_rank<'a>(repos: &'a [String], adj: &BTreeMap<&'a str, Vec<&'a str>>) -> BTreeMap<String, usize> {
    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 {
        // `depth` memoizes `memo[r]` itself, so no extra insert (or clone) is needed.
        depth(r.as_str(), 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()
}

/// 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"));
    }
}