nornir 0.4.22

//! 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::warehouse::dep_graph::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 {
            from: from.to_string(),
            to: to.to_string(),
            via: 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"));
    }
}