facett_graph/

depgraph.rs

//! **Dependency-graph** component — a layered DAG. Ported + generalised from
//! nornir's `src/viz/graph.rs` (phase 1: copied here, nornir still owns its
//! copy). Nodes toposorted into columns (deps left → dependents right), drawn as
//! **boxes** with a status-coloured border + optional sub-label; edges as
//! **arrows** with a `via` label; click a node to select → a drill-down panel of
//! its deps/dependents.
//!
//! Generic: the consumer supplies `(nodes, edges)` (indices + colours), not a
//! nornir `Timeline`. nornir keeps the *data*; facett draws the *shape*.
//!
//! ## FC contract (the canonical Elm split, FC-2 / FC-9)
//! - **[`DepGraphState`]** — the complete observable, serializable, round-trippable
//!   interaction state: the drilled-in selection, keyed on the node's stable
//!   **label** (FC-5). The bulk `nodes`+`edges` are *input* held on [`DepGraphView`]
//!   (their `Color32` is not serde-round-trippable and they are not driver-mutated),
//!   so they live OUTSIDE the Model — the derived counts/column depth a driver reads
//!   are published via the form-3 `state_json`.
//! - **[`Msg`] + [`DepGraphView::update`]** — the single mutation path (FC-2): a node
//!   is toggle-selected / cleared by its label (the same gesture the box click drives),
//!   so a headless driver ([`facett_core::harness`]) reaches it too.
//! - **[`DepGraphView::view`]** — a **pure** paint (FC-9): reads `&self`, paints the
//!   boxes/arrows/drill-down and *returns* the [`Msg`]s the clicks produced; the
//!   [`impl_facet_via_elm!`](facett_core::impl_facet_via_elm) bridge applies them.

use std::collections::{BTreeMap, VecDeque};

use egui::{Align2, Color32, FontId, Pos2, Rect, CornerRadius, Sense, Stroke, Ui, Vec2};
use facett_core::{FacetCaps, theme};
use serde::{Deserialize, Serialize};

const NODE_W: f32 = 160.0;
const NODE_H: f32 = 56.0;
const COL_GAP: f32 = 220.0;
const ROW_GAP: f32 = 90.0;
const LEFT_PAD: f32 = 30.0;
const TOP_PAD: f32 = 40.0;

/// One node: a label, an optional sub-label (a sha, a version…), and a border
/// colour (the consumer's status policy).
#[derive(Clone)]
pub struct DepNode {
    pub label: String,
    pub sublabel: Option<String>,
    pub color: Color32,
}

/// A directed edge `from → to`, with the connecting items shown on the arrow.
#[derive(Clone)]
pub struct DepEdge {
    pub from: usize,
    pub to: usize,
    pub via: Vec<String>,
}

/// **The complete observable interaction state (FC-1 / FC-3)** of a
/// [`DepGraphView`]: the drilled-in selection, keyed on the node's stable **label**
/// (FC-5) so a reorder/insert/delete can't silently re-point it the way a list index
/// would. The `nodes`/`edges` are *input* on [`DepGraphView`], kept out of this Model.
#[derive(Clone, Debug, Default, PartialEq, Eq, Serialize, Deserialize)]
pub struct DepGraphState {
    /// Selected node, keyed on its stable **label** (FC-5).
    pub selected: Option<String>,
}

/// A robot-/CLI-addressable control message (FC-2) — the named boundary a headless
/// driver (or a host) drives the graph through, the same effect a node-box click
/// produces. Applied by [`DepGraphView::update`].
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Msg {
    /// Toggle-select a node by its stable **label** (the box click): re-selecting the
    /// open node clears it.
    SelectNode(String),
    /// Clear the drill-in selection.
    ClearSelection,
}

/// Side work as data (FC-8). The dep-graph does no I/O — every [`Msg`] mutates only
/// the in-memory [`DepGraphState`] — so this is uninhabited on purpose.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Effect {}

/// The layered dep-graph viewer. Implements [`Facet`].
pub struct DepGraphView {
    pub title: String,
    pub nodes: Vec<DepNode>,
    pub edges: Vec<DepEdge>,
    /// All observable interaction state (FC-3): the label-keyed selection.
    state: DepGraphState,
}

impl DepGraphView {
    pub fn new(nodes: Vec<DepNode>, edges: Vec<DepEdge>) -> Self {
        Self { title: "deps".into(), nodes, edges, state: DepGraphState::default() }
    }

    /// **FC-3** — read the complete observable interaction state.
    pub fn state(&self) -> &DepGraphState {
        &self.state
    }

    /// The currently-selected node's stable label, if any.
    pub fn selected(&self) -> Option<&str> {
        self.state.selected.as_deref()
    }

    /// Index of the currently-selected node (resolved from its stable label).
    fn selected_idx(&self) -> Option<usize> {
        self.state.selected.as_deref().and_then(|l| self.nodes.iter().position(|n| n.label == l))
    }
    pub fn with_title(mut self, t: impl Into<String>) -> Self {
        self.title = t.into();
        self
    }

    /// Drill into a node by its stable label (or `None` to clear). A thin wrapper
    /// over the FC-2 [`update`](Self::update) mutation path (the sole way the Model
    /// changes): deterministic (a *set*, never a toggle).
    pub fn select(&mut self, node: Option<String>) {
        let _ = self.update(Msg::ClearSelection);
        if let Some(n) = node {
            let _ = self.update(Msg::SelectNode(n));
        }
    }

    /// **FC-2 / FC-8** — the single mutation path. Apply one [`Msg`]; returns the
    /// (always empty) [`Effect`]s the host should run. The canvas node-box click
    /// routes its [`Msg`] here too, so live == headless.
    pub fn update(&mut self, msg: Msg) -> Vec<Effect> {
        match msg {
            // Toggle on the stable label: re-selecting the open node clears it.
            Msg::SelectNode(label) => {
                self.state.selected =
                    if self.state.selected.as_deref() == Some(label.as_str()) { None } else { Some(label) };
            }
            Msg::ClearSelection => self.state.selected = None,
        }
        Vec::new()
    }

    /// Column index per node — toposort, deps first (left). Longest-path layering
    /// so a dependent sits right of all its deps. Cycle → best effort.
    pub fn columns(&self) -> Vec<usize> {
        let n = self.nodes.len();
        let mut indeg = vec![0usize; n];
        let mut adj: Vec<Vec<usize>> = vec![Vec::new(); n];
        for e in &self.edges {
            if e.from < n && e.to < n {
                // `from` consumes `to` → place `to` first.
                adj[e.to].push(e.from);
                indeg[e.from] += 1;
            }
        }
        let mut col = vec![0usize; n];
        let mut q: VecDeque<usize> = (0..n).filter(|&i| indeg[i] == 0).collect();
        while let Some(r) = q.pop_front() {
            for &c in &adj[r] {
                col[c] = col[c].max(col[r] + 1);
                indeg[c] -= 1;
                if indeg[c] == 0 {
                    q.push_back(c);
                }
            }
        }
        col
    }

    /// Paint the graph, returning the [`Msg`]s the clicks produced. A thin wrapper
    /// over the pure [`view`](Self::view) that applies them (kept for direct callers).
    pub fn show(&mut self, ui: &mut Ui) {
        let msgs = self.view(ui);
        for m in msgs {
            let _ = self.update(m);
        }
    }

    /// **FC-9 render** — a **pure** function of `&self`: it paints the boxes/arrows +
    /// the drill-down panel and *returns* the [`Msg`]s the node clicks produced. It
    /// MUST NOT mutate the [`DepGraphState`]; the
    /// [`impl_facet_via_elm!`](facett_core::impl_facet_via_elm) bridge applies the
    /// returned messages through [`update`](Self::update).
    pub fn view(&self, ui: &mut Ui) -> Vec<Msg> {
        let mut msgs: Vec<Msg> = Vec::new();
        if self.nodes.is_empty() {
            ui.label("no nodes");
            return msgs;
        }
        let col = self.columns();
        let mut row_of = vec![0usize; self.nodes.len()];
        let mut per_col: BTreeMap<usize, usize> = BTreeMap::new();
        for (i, &c) in col.iter().enumerate() {
            let r = per_col.entry(c).or_insert(0);
            row_of[i] = *r;
            *r += 1;
        }
        let ncols = col.iter().copied().max().unwrap_or(0) + 1;
        let nrows = per_col.values().copied().max().unwrap_or(1);
        let needed_w = LEFT_PAD + ncols as f32 * COL_GAP + NODE_W;
        let needed_h = TOP_PAD + nrows as f32 * ROW_GAP + NODE_H;
        let avail = ui.available_size();
        let canvas = Vec2::new(avail.x.max(needed_w), avail.y.max(needed_h.max(360.0)));
        let (rect, _resp) = ui.allocate_exact_size(canvas, Sense::hover());
        let th = theme(ui);
        let painter = ui.painter_at(rect);
        painter.rect_filled(rect, CornerRadius::ZERO, th.bg);
        let sel_idx = self.selected_idx();

        let pos_for = |i: usize| {
            Pos2::new(
                rect.left() + LEFT_PAD + col[i] as f32 * COL_GAP,
                rect.top() + TOP_PAD + row_of[i] as f32 * ROW_GAP,
            )
        };

        // edges (under nodes)
        for e in &self.edges {
            if e.from >= self.nodes.len() || e.to >= self.nodes.len() {
                continue;
            }
            let from = pos_for(e.from) + Vec2::new(NODE_W / 2.0, NODE_H / 2.0);
            let to = pos_for(e.to) + Vec2::new(NODE_W / 2.0, NODE_H / 2.0);
            draw_arrow(&painter, from, to, th.edge);
            if !e.via.is_empty() {
                let via = e.via.iter().take(2).cloned().collect::<Vec<_>>().join(", ");
                let label = if e.via.len() > 2 { format!("{via} +{}", e.via.len() - 2) } else { via };
                let mid = Pos2::new((from.x + to.x) / 2.0, (from.y + to.y) / 2.0 - 8.0);
                painter.text(mid, Align2::CENTER_BOTTOM, &label, FontId::monospace(10.0), th.text_dim);
            }
        }

        // nodes — paint the box, then ride a hit-testable, labelled AccessKit node
        // keyed on the stable node **label** (FC-4 + FC-5). Click emits a toggle Msg.
        let base_id = ui.id().with("depgraph-nodes");
        for (i, node) in self.nodes.iter().enumerate() {
            let p = pos_for(i);
            let nrect = Rect::from_min_size(p, Vec2::new(NODE_W, NODE_H));
            let is_sel = sel_idx == Some(i);
            let fill = if is_sel { th.accent.linear_multiply(0.2) } else { th.node_fill };
            painter.rect_filled(nrect, CornerRadius::same(6), fill);
            let (bw, bc) = if is_sel { (3.0, th.accent) } else { (2.0, node.color) };
            painter.rect_stroke(nrect, CornerRadius::same(6), Stroke::new(bw, bc), egui::StrokeKind::Inside);
            painter.text(p + Vec2::new(NODE_W / 2.0, 14.0), Align2::CENTER_TOP, &node.label, FontId::proportional(15.0), th.text);
            if let Some(sub) = &node.sublabel {
                let short: String = sub.chars().take(12).collect();
                painter.text(p + Vec2::new(NODE_W / 2.0, 34.0), Align2::CENTER_TOP, short, FontId::monospace(11.0), th.text_dim);
            }
            let a11y_label = match &node.sublabel {
                Some(s) => format!("{} · {}", node.label, s),
                None => node.label.clone(),
            };
            let sem = facett_core::a11y::Semantics::button(a11y_label).selected(is_sel);
            let resp = facett_core::a11y::node(ui, base_id, &node.label, Sense::click(), nrect, sem);
            if resp.clicked() {
                // FC-9: emit the Msg instead of mutating `self`.
                msgs.push(Msg::SelectNode(node.label.clone()));
            }
        }

        // drill-down panel
        if let Some(sel) = self.selected_idx() {
            let deps: Vec<String> = self
                .edges
                .iter()
                .filter(|e| e.from == sel)
                .filter_map(|e| self.nodes.get(e.to).map(|n| format!("  → {}   [{}]", n.label, e.via.join(", "))))
                .collect();
            let users: Vec<String> = self
                .edges
                .iter()
                .filter(|e| e.to == sel)
                .filter_map(|e| self.nodes.get(e.from).map(|n| format!("  ← {}   [{}]", n.label, e.via.join(", "))))
                .collect();
            let rows = 3 + deps.len() + users.len();
            let panel = Rect::from_min_size(rect.left_top() + Vec2::new(8.0, 8.0), Vec2::new(380.0, rows as f32 * 16.0 + 16.0));
            painter.rect_filled(panel, CornerRadius::same(6), th.panel_bg);
            painter.rect_stroke(panel, CornerRadius::same(6), Stroke::new(1.0, th.panel_stroke), egui::StrokeKind::Inside);
            let mut y = panel.top() + 8.0;
            let mut put = |s: &str, c: Color32| {
                painter.text(Pos2::new(panel.left() + 10.0, y), Align2::LEFT_TOP, s, FontId::proportional(12.0), c);
                y += 16.0;
            };
            put(&format!("◆ {}  (click again to deselect)", self.nodes[sel].label), th.accent);
            put(&format!("depends on ({}):", deps.len()), th.text_dim);
            for d in &deps {
                put(d, th.text);
            }
            put(&format!("used by ({}):", users.len()), th.text_dim);
            for u in &users {
                put(u, th.text);
            }
        }

        // ── render-lane emit: this pure-view paint path RAN ───────────────────
        #[cfg(feature = "testmatrix")]
        facett_core::testmatrix::emit(
            "facett-graph::DepGraphView::view",
            "ui_render",
            !self.nodes.is_empty(),
            &format!("nodes={} edges={}", self.nodes.len(), self.edges.len()),
        );

        msgs
    }
}

/// Line + arrowhead from `from` to `to` (head pulled back by half a node width).
pub fn draw_arrow(painter: &egui::Painter, from: Pos2, to: Pos2, color: Color32) {
    painter.line_segment([from, to], Stroke::new(2.0, color));
    let dir = (to - from).normalized();
    let perp = Vec2::new(-dir.y, dir.x);
    let tip = to - dir * (NODE_W / 2.0 + 4.0);
    let base = tip - dir * 10.0;
    painter.add(egui::Shape::convex_polygon(vec![tip, base + perp * 5.0, base - perp * 5.0], color, Stroke::NONE));
}

impl DepGraphView {
    /// The copyable text: the selected node's `label` (+ sublabel) when one is
    /// selected, else every node label, one per line.
    pub fn copy_text(&self) -> Option<String> {
        if self.nodes.is_empty() {
            return None;
        }
        if let Some(i) = self.selected_idx() {
            let n = &self.nodes[i];
            return Some(match &n.sublabel {
                Some(s) => format!("{} — {}", n.label, s),
                None => n.label.clone(),
            });
        }
        Some(self.nodes.iter().map(|n| n.label.clone()).collect::<Vec<_>>().join("\n"))
    }
}

// ── typed copy (§16) — read-only: selected node label or the label list ───────
impl facett_core::clip::CopySource for DepGraphView {
    fn copy_kinds(&self) -> &[facett_core::clip::ClipKind] {
        use facett_core::clip::ClipKind;
        &[ClipKind::Text]
    }

    fn copy_payload(&self) -> Option<facett_core::clip::ClipPayload> {
        self.copy_text().map(facett_core::clip::ClipPayload::Text)
    }
}

// ── FC-2 / FC-3 / FC-8 / FC-9: the canonical Elm split ────────────────────────
impl facett_core::Elm for DepGraphView {
    type Model = DepGraphState;
    type Msg = Msg;
    type Effect = Effect;

    fn title(&self) -> &str {
        &self.title
    }
    fn state(&self) -> &DepGraphState {
        &self.state
    }
    fn update(&mut self, msg: Msg) -> Vec<Effect> {
        DepGraphView::update(self, msg)
    }
    fn view(&self, ui: &mut Ui) -> Vec<Msg> {
        DepGraphView::view(self, ui)
    }
}

// The bridge macro writes `impl Facet for DepGraphView` from the `Elm` impl: `title`,
// the FC-9 `ui` loop (`for m in view(ui) { update(m) }`), plus the overrides below.
// **Form 3** (`custom_state_json`) because the view publishes a RICHER `state_json`
// than a plain `serde(state())`: the `nodes`/`edges`/`columns` counts facett-demo's
// mega_matrix reads are *derived* from the input `nodes`+`edges`, not the selection
// Model — so the default is suppressed and these EXACT pre-migration keys supplied.
facett_core::impl_facet_via_elm!(DepGraphView, custom_state_json, {
    fn state_json(&self) -> serde_json::Value {
        serde_json::json!({
            "nodes": self.nodes.len(),
            "edges": self.edges.len(),
            "columns": self.columns().iter().copied().max().map(|m| m + 1).unwrap_or(0),
            "selected": self.state.selected.clone(),
        })
    }
    fn copy(&mut self) -> Option<String> {
        use facett_core::clip::CopySource as _;
        self.copy_payload().map(|p| p.as_text())
    }
    /// Boxes/arrows/labels are painted from the active [`Theme`]; a node can be
    /// click-selected (drives the drill-down panel); the layered canvas takes the
    /// host's `available_size`.
    fn caps(&self) -> FacetCaps {
        FacetCaps::NONE.themeable().selectable().resizable().copyable()
    }
    fn selection_json(&self) -> serde_json::Value {
        match self.selected_idx() {
            Some(i) => serde_json::json!({ "node": self.nodes[i].label }),
            None => serde_json::Value::Null,
        }
    }
});

#[cfg(test)]
mod tests {
    use super::*;
    use facett_core::Facet;

    fn node(l: &str) -> DepNode {
        DepNode { label: l.into(), sublabel: None, color: Color32::GRAY }
    }

    #[test]
    fn toposort_columns_and_state() {
        // a → b → c  (a depends on b depends on c): c leftmost, a rightmost.
        let nodes = vec![node("a"), node("b"), node("c")];
        let edges = vec![
            DepEdge { from: 0, to: 1, via: vec!["x".into()] },
            DepEdge { from: 1, to: 2, via: vec![] },
        ];
        let view = DepGraphView::new(nodes, edges);
        let cols = view.columns();
        assert!(cols[2] < cols[1] && cols[1] < cols[0], "deps to the left: {cols:?}");
        let j = Facet::state_json(&view);
        assert_eq!(j["nodes"], 3);
        assert_eq!(j["edges"], 2);
        assert_eq!(j["columns"], 3);
        assert!(j["selected"].is_null());
    }

    #[test]
    fn typed_copy_is_selected_label_or_the_label_list() {
        use facett_core::clip::{ClipKind, CopySource};
        let mut view = DepGraphView::new(vec![node("a"), node("b")], vec![]);
        // No selection -> every label, one per line.
        let p = view.copy_payload().expect("populated graph copies");
        assert_eq!(p.kind(), ClipKind::Text);
        assert_eq!(p.as_text(), "a\nb");
        // Selecting narrows the copy to that node's label.
        view.select(Some("b".into()));
        assert_eq!(view.copy_payload().unwrap().as_text(), "b");
    }

    // ── FC-2 → FC-3 as a *headless* property via the core harness ─────────────
    #[test]
    fn harness_drives_select_toggle_and_clear() {
        use facett_core::harness;
        let mut view = DepGraphView::new(vec![node("a"), node("b"), node("c")], vec![]);
        // Selecting an existing node is observable in the snapshot.
        let snap = harness::snapshot(&mut view, [Msg::SelectNode("b".into())]);
        assert_eq!(snap.selected.as_deref(), Some("b"), "selection is observable headlessly");
        assert_eq!(&snap, view.state(), "the snapshot is a clone of the live state");
        // Re-selecting the open node toggles it off (the existing click behaviour).
        let snap = harness::snapshot(&mut view, [Msg::SelectNode("b".into())]);
        assert_eq!(snap.selected, None, "re-selecting toggles the selection off");
        // ClearSelection wipes it.
        let snap = harness::snapshot(&mut view, [Msg::SelectNode("a".into()), Msg::ClearSelection]);
        assert_eq!(snap.selected, None, "ClearSelection empties the selection");
    }

    #[test]
    fn drive_reports_no_effects_and_state_round_trips() {
        use facett_core::harness;
        let mut view = DepGraphView::new(vec![node("a"), node("b")], vec![]);
        // FC-8: the dep-graph does no I/O, so the effect stream is always empty.
        let effects = harness::drive(&mut view, [Msg::SelectNode("a".into())]);
        assert!(effects.is_empty(), "FC-8: dep-graph emits no Effects");
        // FC-3: the observable Model round-trips through serde.
        let json = serde_json::to_value(view.state()).unwrap();
        assert_eq!(json["selected"], "a");
        let back: DepGraphState = serde_json::from_value(json).unwrap();
        assert_eq!(&back, view.state(), "serde(state) -> state round-trips");
    }

    // ── FC-5: selection is keyed on the STABLE label, not a volatile index, so a
    //    re-layout (reordered nodes → different columns/indices) keeps the same node
    //    selected. ──────────────────────────────────────────────────────────────
    #[test]
    fn selection_survives_a_relayout() {
        use facett_core::harness;
        // a → b → c: c leftmost, a rightmost. Select "b".
        let mut view = DepGraphView::new(
            vec![node("a"), node("b"), node("c")],
            vec![DepEdge { from: 0, to: 1, via: vec![] }, DepEdge { from: 1, to: 2, via: vec![] }],
        );
        harness::drive(&mut view, [Msg::SelectNode("b".into())]);
        let cols_before = view.columns();
        let b_idx_before = view.nodes.iter().position(|n| n.label == "b").unwrap();
        assert_eq!(Facet::selection_json(&view)["node"], "b");

        // Re-layout: reorder the nodes to [c, a, b] and re-point the edges to the same
        // a→b→c shape. The *indices* and the toposort *columns* both change; the graph
        // shape does not.
        view.nodes = vec![node("c"), node("a"), node("b")];
        view.edges = vec![DepEdge { from: 1, to: 2, via: vec![] }, DepEdge { from: 2, to: 0, via: vec![] }];
        let b_idx_after = view.nodes.iter().position(|n| n.label == "b").unwrap();
        let cols_after = view.columns();
        assert_ne!(b_idx_before, b_idx_after, "b sits at a different index after the re-layout");
        assert_ne!(cols_before, cols_after, "the toposort columns changed (a real re-layout)");

        // FC-5: the label-keyed selection still resolves to the SAME node "b".
        assert_eq!(view.state().selected.as_deref(), Some("b"), "selection label is index-independent");
        assert_eq!(Facet::selection_json(&view)["node"], "b", "selection still resolves to node 'b'");
        assert_eq!(Facet::state_json(&view)["selected"], "b");
    }

    #[test]
    fn headless_render_draws_and_reports_state() {
        use facett_core::harness;
        let mut view = DepGraphView::new(
            vec![node("a"), node("b"), node("c")],
            vec![DepEdge { from: 0, to: 1, via: vec!["x".into()] }, DepEdge { from: 1, to: 2, via: vec![] }],
        )
        .with_title("deps");
        let r = harness::headless_render(&mut view);
        assert_eq!(r.title, "deps");
        assert_eq!(r.state["nodes"], 3);
        assert_eq!(r.state["columns"], 3);
        assert!(r.drew(), "a 3-node dep-graph tessellates to vertices");
    }
}