facett-graphnav/tests/legibility.rs
//! **Legibility at scale for the NAVIGATOR** — the pane whose whole job is reading
//! data, so the pane where "as good and better for viewing data" is measured.
//!
//! Four defects pinned, each with the number that goes RED when it comes back:
//!
//! | defect | oracle |
//! |---|---|
//! | hover scanned the whole dataset on every mouse move | `hover_candidates` |
//! | every label painted, on top of every other | `labels_placed` / `labels_suppressed` + a pixel oracle |
//! | every edge stroked, until the pane was one grey block | `edge_peak_before` / `edge_peak_after` + a pixel oracle |
//! | GPU opt-in without an installed renderer rendered blank | a vertex-for-vertex fallback |
//!
//! The pixel oracles rasterize the *result* (label boxes, edge segments), not the
//! algorithm's own bookkeeping, so a cure that silently stopped working while still
//! reporting plausible counters is still caught.
use egui::{pos2, Rect};
use facett_core::harness::headless_render;
use facett_core::legibility::{edge_ink_profile, max_label_overlap, ScreenGrid};
use facett_graphnav::legible::{plan_nav, HoverIndex, LegibilityOpts, NavFrame};
use facett_graphnav::model::{Edge, Node, PropGraph};
use facett_graphnav::GraphNav;
fn viewport() -> Rect {
Rect::from_min_size(pos2(0.0, 0.0), egui::vec2(900.0, 700.0))
}
/// A deterministic crowded cloud (fixed xorshift — reproducible run to run).
fn cloud(n: usize) -> Vec<egui::Pos2> {
let mut s = 0x2545_F491_4F6C_DD1Du64;
let mut next = move || {
s ^= s << 13;
s ^= s >> 7;
s ^= s << 17;
(s >> 11) as f32 / (1u64 << 53) as f32
};
(0..n).map(|_| pos2(next() * 900.0, next() * 700.0)).collect()
}
fn demo_graph(n: usize) -> PropGraph {
let nodes: Vec<Node> = (0..n).map(|i| Node::new(format!("n{i}"), "Thing")).collect();
let edges: Vec<Edge> = (0..n)
.map(|i| Edge::new(format!("n{i}"), format!("n{}", (i * 7 + 3) % n), "REL"))
.collect();
PropGraph { nodes, edges }
}
// ── 1. HOVER ────────────────────────────────────────────────────────────────
/// **The pointer cost must track the neighbourhood, not the dataset.**
///
/// The navigator used to resolve the hovered node by iterating EVERY node, projecting
/// it and taking a distance — on every mouse move, including nodes far off-screen,
/// while the paint loop right below it was already viewport-culled. So the frame's
/// paint half scaled with the screen and its pointer half scaled with the dataset:
/// exactly the shape `facett-geomap`'s `PointGrid` was caught in, and exactly as
/// invisible, because "it feels fine on the demo graph" is true at 12 nodes.
#[test]
fn hover_costs_a_neighbourhood_not_the_dataset() {
let mut seen = Vec::new();
for n in [1000usize, 20_000, 200_000] {
let pts = cloud(n);
let mut h = HoverIndex::default();
h.ensure(n as u64, pts.iter().copied().enumerate());
assert_eq!(h.len(), n);
// Probe a real node in the middle of the cloud, so the sizes are comparable.
let target = pts[n / 2];
let hit = h.hover(target, 10.0);
assert!(hit.is_some(), "n={n}: probing a node's own position must hit something");
assert!(
h.last_candidates <= 128,
"n={n}: one hover probe distance-tested {} nodes",
h.last_candidates
);
seen.push((n, h.last_candidates));
}
let (n0, c0) = seen[0];
let (n1, c1) = *seen.last().unwrap();
assert!(
c1 <= c0 * 3,
"dataset {n0} -> {n1} (×{}) but hover cost {c0} -> {c1} — that is a dataset scan",
n1 / n0
);
}
/// The indexed hover picks the SAME node the old linear "nearest within 10 px" scan
/// picked, including the tie rule (lowest index wins).
#[test]
fn indexed_hover_matches_the_linear_nearest_scan() {
let pts = cloud(4000);
let mut h = HoverIndex::default();
h.ensure(1, pts.iter().copied().enumerate());
let mut hits = 0usize;
for k in 0..400 {
let p = pos2(((k * 13) % 900) as f32, ((k * 23) % 700) as f32);
let brute = pts
.iter()
.enumerate()
.map(|(i, q)| (i, p.distance(*q)))
.filter(|&(_, d)| d <= 10.0)
.min_by(|a, b| a.1.total_cmp(&b.1).then(a.0.cmp(&b.0)))
.map(|(i, _)| i);
assert_eq!(h.hover(p, 10.0), brute, "probe {p:?}");
hits += usize::from(brute.is_some());
}
assert!(hits > 100, "the sweep must really hover things ({hits})");
}
// ── 2. LABELS ───────────────────────────────────────────────────────────────
/// **The pixel oracle for labels.** No two surviving labels may share a pixel — and the
/// control (every candidate painted at its anchor, the pre-fix behaviour) is measured in
/// the same test, so "the pile is gone" is a comparison rather than a claim.
#[test]
fn label_collision_is_pixel_disjoint_and_the_control_is_a_pile() {
let centres = cloud(3000);
let n = centres.len();
let plan = plan_nav(
&NavFrame {
centres: ¢res,
visible: &vec![true; n],
label_chars: &vec![12usize; n],
label_pinned: &vec![false; n],
label_priority: &(0..n).map(|i| (i % 97) as f32).collect::<Vec<_>>(),
edges: &[],
edge_always: &[],
edge_weight: &[],
viewport: viewport(),
font_px: 10.0,
},
LegibilityOpts::default(),
);
let placed = plan.labels().expect("thinning is on by default");
let rects: Vec<Rect> = placed.placed.iter().map(|p| p.rect).collect();
assert_eq!(
max_label_overlap(&rects, viewport(), 1.0),
1,
"no pixel may carry two labels"
);
assert!(placed.suppressed > 0, "a 3000-label crowd must suppress losers");
assert!(!placed.placed.is_empty(), "and must still draw the winners");
// The control: every label at its anchor, as the pre-fix painter did.
let unthinned: Vec<Rect> = centres
.iter()
.map(|&c| Rect::from_center_size(c, egui::vec2(12.0 * 5.8, 10.0)))
.collect();
let peak = max_label_overlap(&unthinned, viewport(), 1.0);
assert!(peak >= 5, "the control must really overplot, got peak {peak}");
}
/// A **pinned** label (selection / hover / path / search hit) is never dropped — those
/// are the answer to the user's question.
#[test]
fn the_labels_the_user_is_pointing_at_survive_any_crowd() {
let centres = cloud(2000);
let n = centres.len();
let mut pinned = vec![false; n];
for i in (0..n).step_by(250) {
pinned[i] = true;
}
let plan = plan_nav(
&NavFrame {
centres: ¢res,
visible: &vec![true; n],
label_chars: &vec![14usize; n],
label_pinned: &pinned,
label_priority: &vec![0.0; n],
edges: &[],
edge_always: &[],
edge_weight: &[],
viewport: viewport(),
font_px: 10.0,
},
LegibilityOpts::default(),
);
let placed = plan.labels().unwrap();
let drawn: std::collections::BTreeSet<usize> = placed.placed.iter().map(|p| p.index).collect();
for (i, &f) in pinned.iter().enumerate() {
if f {
assert!(drawn.contains(&i), "pinned label {i} was dropped");
}
}
assert!(placed.suppressed > 0, "the crowd around them still thinned");
}
// ── 3. EDGES ────────────────────────────────────────────────────────────────
/// **The pixel oracle for edges.** A hairball saturates the pane; the ink budget
/// collapses the saturated-pixel count while still drawing a graph. Both numbers come
/// from rasterizing the real segments.
#[test]
fn the_edge_ink_budget_makes_a_hairball_readable() {
let centres = cloud(1200);
let n = centres.len();
// A dense random graph: 12 000 edges over 1200 nodes.
let edges: Vec<(u32, u32)> =
(0..12_000u32).map(|i| ((i * 37 % n as u32), (i * 91 + 7) % n as u32)).collect();
let segs: Vec<(egui::Pos2, egui::Pos2)> =
edges.iter().map(|&(a, b)| (centres[a as usize], centres[b as usize])).collect();
let all: Vec<u32> = (0..segs.len() as u32).collect();
let plan = plan_nav(
&NavFrame {
centres: ¢res,
visible: &vec![true; n],
label_chars: &vec![0usize; n],
label_pinned: &[],
label_priority: &[],
edges: &edges,
edge_always: &[],
edge_weight: &[],
viewport: viewport(),
font_px: 10.0,
},
LegibilityOpts::default(),
);
let keep = plan.edges().expect("thinning is on by default");
let (lit_b, peak_b, sat_b) = edge_ink_profile(&segs, &all, viewport(), 4);
let (lit_a, peak_a, sat_a) = edge_ink_profile(&segs, keep, viewport(), 4);
assert!(sat_b > 5_000, "the control hairball must really be saturated: {sat_b}");
assert!(sat_a * 3 < sat_b, "the budget must cut saturated ink hard: {sat_b} -> {sat_a}");
assert!(peak_a < peak_b, "peak pile {peak_b} -> {peak_a}");
assert!(lit_a > 0 && lit_a < lit_b, "still a graph: {lit_b} -> {lit_a}");
assert!(plan.report.edge_peak_after < plan.report.edge_peak_before);
assert_eq!(
plan.report.edges_drawn + plan.report.edges_thinned,
plan.inner.report.edges_considered,
"every considered edge is either drawn or budgeted away"
);
}
/// A **sparse** graph loses nothing. This is what distinguishes a density budget from
/// "draw 1 edge in k" — random subsampling would thin the readable regions too.
#[test]
fn a_sparse_navigator_graph_is_untouched() {
let centres: Vec<egui::Pos2> = (0..12).map(|i| pos2(60.0 + i as f32 * 70.0, 350.0)).collect();
let edges: Vec<(u32, u32)> = (0..11u32).map(|i| (i, i + 1)).collect();
let plan = plan_nav(
&NavFrame {
centres: ¢res,
visible: &[true; 12],
label_chars: &[4usize; 12],
label_pinned: &[],
label_priority: &[],
edges: &edges,
edge_always: &[],
edge_weight: &[],
viewport: viewport(),
font_px: 10.0,
},
LegibilityOpts::default(),
);
assert_eq!(plan.report.edges_thinned, 0, "nothing to thin in a sparse graph");
assert_eq!(plan.report.labels_suppressed, 0, "nor to suppress");
}
/// Turning legibility OFF restores the historical plan exactly: every edge, no label
/// placement. That is what keeps an A/B (and any future golden) honest.
#[test]
fn legibility_off_draws_everything() {
let centres = cloud(500);
let edges: Vec<(u32, u32)> = (0..2000u32).map(|i| (i % 500, (i * 3 + 1) % 500)).collect();
let plan = plan_nav(
&NavFrame {
centres: ¢res,
visible: &vec![true; 500],
label_chars: &vec![8usize; 500],
label_pinned: &[],
label_priority: &[],
edges: &edges,
edge_always: &[],
edge_weight: &[],
viewport: viewport(),
font_px: 10.0,
},
LegibilityOpts::off(),
);
assert!(plan.edges().is_none(), "no edge is dropped");
assert!(plan.labels().is_none(), "no label placement runs");
assert_eq!(plan.report.edges_drawn, edges.len());
}
// ── 4. GPU FALLBACK ─────────────────────────────────────────────────────────
/// GPU opt-in with **no renderer installed** must paint the CPU frame vertex for
/// vertex. This box has none, which is precisely the state that used to render blank.
#[test]
fn gpu_optin_without_a_renderer_falls_back_vertex_for_vertex() {
let g = demo_graph(120);
let mut cpu = GraphNav::new("cpu", g.clone());
let mut gpu = GraphNav::new("gpu", g);
gpu.legibility.gpu_cloud = true;
let c = headless_render(&mut cpu);
let r = headless_render(&mut gpu);
assert!(c.drew(), "the control frame draws");
assert_eq!(
r.vertices, c.vertices,
"no renderer installed ⇒ the CPU frame, vertex for vertex ({} vs {})",
r.vertices, c.vertices
);
assert_eq!(
r.state["legibility"]["frame"]["gpu_cloud"],
serde_json::json!(false),
"and the navigator says the GPU lane did not paint"
);
// Not two blanks agreeing.
let mut empty = GraphNav::new("empty", PropGraph::new());
assert!(r.vertices > headless_render(&mut empty).vertices);
}
/// The navigator publishes its legibility work in `state_json`, so a robot asserts on
/// numbers. A rendered frame must report a real hover index, not a zero.
#[test]
fn state_json_publishes_the_frames_legibility_work() {
let mut nav = GraphNav::new("nav", demo_graph(300));
let r = headless_render(&mut nav);
let lg = &r.state["legibility"];
assert_eq!(lg["opts"]["thin_labels"], serde_json::json!(true), "legibility is on by default");
assert_eq!(lg["opts"]["gpu_cloud"], serde_json::json!(false), "the GPU lane is not");
assert!(
lg["frame"]["hover_indexed"].as_u64().unwrap() > 0,
"the hover index was built for the visible nodes: {lg}"
);
}
/// The lattice sizing lesson, restated where it bites: the index spans the DATA's
/// bounding box, so occupancy stays low at any extent. A world-spanning lattice (the
/// `PointGrid` bug) would pile the whole dataset into a few cells and the hover cost
/// assertions above would only pass by luck.
#[test]
fn the_hover_lattice_spans_the_data_at_any_extent() {
for span in [10.0f32, 900.0, 50_000.0] {
let pts: Vec<egui::Pos2> = (0..20_000)
.map(|i| {
let (r, c) = (i / 142, i % 142);
pos2(c as f32 / 142.0 * span, r as f32 / 142.0 * span)
})
.collect();
let g = ScreenGrid::build(&pts);
assert!(
g.max_occupancy() <= 64,
"span {span}: fullest bin holds {} of 20000",
g.max_occupancy()
);
}
}
// ── the DRAG path (lane M, 2026-10-02) ──────────────────────────────────────
/// **A drag does no hover work.** Lane L saw `hover_candidates: 42` in `lineage`'s state
/// after a 4 s drag at 100k on the RTX 5080 and suspected the hover path under the
/// dragging pointer. It is not there: while the canvas is dragged the navigator neither
/// rebuilds the screen index nor probes it (`hover_builds` / `hover_probes` stand
/// still while the camera moves); `hover_candidates` is the last probe BEFORE the drag
/// (the press frame), a readout, not per-frame work. After the release the first hover
/// frame rebuilds once and probes again.
#[test]
fn a_drag_neither_rebuilds_nor_probes_the_hover_index() {
use facett_core::Facet as _;
use facett_graphnav::layout::LayoutKind;
use facett_graphnav::Msg;
let mut nav = GraphNav::new("drag", demo_graph(6_000));
let _ = nav.update(Msg::SetLayout(LayoutKind::Grid));
let ctx = egui::Context::default();
ctx.set_pixels_per_point(1.0);
let size = egui::vec2(1280.0, 860.0);
let frame = |nav: &mut GraphNav, events: Vec<egui::Event>| {
let input = egui::RawInput {
screen_rect: Some(Rect::from_min_size(egui::Pos2::ZERO, size)),
events,
..Default::default()
};
ctx.run_ui(input, |ui| {
egui::CentralPanel::default().show(ui, |ui| nav.ui(ui));
}).textures_delta.clear();
};
let counts = |nav: &GraphNav| {
let f = nav.legibility_frame_json();
(f["hover_builds"].as_u64().unwrap(), f["hover_probes"].as_u64().unwrap())
};
let button = |pos, pressed| egui::Event::PointerButton {
pos,
button: egui::PointerButton::Primary,
pressed,
modifiers: Default::default(),
};
let mut at = pos2(size.x * 0.4, size.y * 0.6);
frame(&mut nav, vec![egui::Event::PointerMoved(at)]);
frame(&mut nav, vec![egui::Event::PointerMoved(at)]);
let (b0, p0) = counts(&nav);
assert!(b0 >= 1 && p0 >= 1, "hovering the canvas builds and probes the index: {b0} {p0}");
frame(&mut nav, vec![button(at, true)]);
// Past egui's click distance: the canvas is now being dragged.
for _ in 0..4 {
at.x += 4.0;
frame(&mut nav, vec![egui::Event::PointerMoved(at)]);
}
let pan0 = nav.camera().pan;
let (b1, p1) = counts(&nav);
for _ in 0..30 {
at.x += 3.0;
frame(&mut nav, vec![egui::Event::PointerMoved(at)]);
}
assert_ne!(nav.camera().pan, pan0, "the drag pans the camera");
assert_eq!(counts(&nav), (b1, p1), "30 drag frames: no index rebuild, no hover probe");
frame(&mut nav, vec![button(at, false)]);
frame(&mut nav, vec![egui::Event::PointerMoved(at)]);
let (b2, p2) = counts(&nav);
assert!(b2 == b1 + 1 && p2 > p1, "after the release the index is rebuilt ONCE and probed: {b1}->{b2} {p1}->{p2}");
}