nordisk/facett

facett-graphview/tests/unfold_scales.rs

//! **The progressive-unfold set must not be quadratic in the graph.**
//!
//! `DecoratedGraphView::visible_ids` walked the unfold with a `children_of` that
//! FILTERED THE WHOLE EDGE LIST, by string comparison, once per expanded node — so
//! the cost of one frame was `O(V · E)` string compares plus a `String` clone per
//! hit. Under a few hundred nodes that is invisible. At korp's declared ceiling for
//! this engine (100 000 nodes — `korp::graphnav::VIEWER_TABLE`, `engine_2d`) it is
//! ~10^10 compares **per frame**, and the host does not render slowly, it stops:
//!
//! MEASURED on oden, 2026-09-03, korp `d929e38`, thin `korp-ui` on Xvfb :131 — the
//! 🏬 Warehouse ▸ 🕸 explorer opened `korp_demo` (106 250 nodes / 100 000 edges), the
//! derivation picked `engine_2d`, and the main thread sat at 99.9 % CPU for over two
//! minutes with no repaint at all. `gdb -p` on the live process, thread 1:
//!
//! ```text
//! #1  <Vec<String> as SpecFromIterNested<…DecoratedGraphView::children_of::{closure#1}>>::from_iter
//! #2  <facett_core::nav::DrillNav>::visible::<…DecoratedGraphView::visible_ids::{closure#0}, Vec<String>>
//! #3  <facett_graphview::decorated_view::DecoratedGraphView>::visible_ids
//! #4  <facett_graphview::decorated_view::DecoratedGraphView>::view
//! ```
//!
//! `$KORP_STATE` stopped being written, so every robot drive against that scene read
//! a stale file and reported the WRONG engine as selected. The engine chooser was on
//! screen the whole time and could not be clicked, because nothing repainted.
//!
//! The guard is a SCALING budget, not a stopwatch on one size: the linear lane and
//! the quadratic lane are three orders of magnitude apart here, so the threshold sits
//! in a gap no machine load can close.

use facett_graphview::decorated_view::{DecoratedGraphView, Msg};
use facett_graphview::model::{Color, GraphEdge, GraphModel, GraphNode, Pos};

/// A `n`-node forward chain: every node expanded, so the unfold walks the whole
/// graph — the shape a road slice or a `korp_demo` open actually produces.
fn chain(n: usize) -> GraphModel {
    let nodes = (0..n)
        .map(|i| GraphNode {
            id: format!("n{i:06}"),
            label: format!("n{i}"),
            fill: Color::rgb(20, 20, 20),
            stroke: Color::rgb(80, 80, 80),
            pos: Pos { x: i as f32, y: 0.0 },
        })
        .collect();
    let edges = (0..n.saturating_sub(1))
        .map(|i| GraphEdge {
            from: format!("n{i:06}"),
            to: format!("n{:06}", i + 1),
            color: Color::rgb(60, 60, 60),
            dashed: false,
            label: None,
        })
        .collect();
    GraphModel { nodes, edges }
}

/// `with_model` seeds the navigator FULLY UNFOLDED, so this is the default state a
/// host lands in the moment a scene arrives — not a contrived one.
fn unfolded(n: usize) -> DecoratedGraphView {
    DecoratedGraphView::new("scale").with_model(chain(n))
}

#[test]
fn the_unfold_set_of_a_20k_node_graph_is_computed_in_one_pass() {
    let v = unfolded(20_000);
    let t0 = std::time::Instant::now();
    let vis = v.visible_ids();
    let ms = t0.elapsed().as_secs_f64() * 1e3;
    assert_eq!(vis.len(), 20_000, "every node of an all-expanded chain is visible");
    // One indexed pass over 20 000 edges is single-digit milliseconds. The
    // per-node edge filter is 20 000 × 20 000 = 4·10^8 string compares — seconds.
    // 300 ms sits ~60x above the one and ~10x below the other.
    assert!(ms < 300.0, "visible_ids took {ms:.1} ms on 20 000 nodes — that is the per-node edge scan, not an index");
}

#[test]
fn doubling_the_graph_does_not_quadruple_the_unfold() {
    // The shape of the cost, not its absolute value: an indexed pass is linear
    // (ratio ~2), the per-node filter is quadratic (ratio ~4). Measured on the
    // larger sizes so the constant factors are amortised.
    let a = unfolded(10_000);
    let b = unfolded(20_000);
    let t = |v: &DecoratedGraphView| {
        let t0 = std::time::Instant::now();
        let _ = v.visible_ids();
        t0.elapsed().as_secs_f64()
    };
    // Warm both lanes so the first-touch page faults do not land on one side.
    let _ = t(&a);
    let _ = t(&b);
    let ta = t(&a).max(1e-6);
    let tb = t(&b);
    let ratio = tb / ta;
    assert!(ratio < 3.0, "10k → 20k cost ratio {ratio:.2} — a linear index is ~2, the O(V·E) filter is ~4");
}

#[test]
fn the_unfold_still_answers_the_partially_expanded_case() {
    // RED-when-broken for the OPTIMISATION itself: an index that ignores the
    // `expanded` set would return every node here, and the two tests above would
    // still pass. Only the root and its one child are visible.
    let mut v = DecoratedGraphView::new("partial").with_model(chain(50));
    let _ = v.update(Msg::Fold("n000001".into()));
    let vis = v.visible_ids();
    assert_eq!(
        vis.iter().cloned().collect::<Vec<_>>(),
        vec!["n000000".to_string(), "n000001".to_string()],
        "the folded node stays, its subtree does not"
    );
}