facett-graphview/src/world.rs
//! **The WORLD GRAPH** — a levels-of-detail (repos → crates → functions) graph
//! surface, plus a **scale-aware layout** that feeds the instanced GPU cloud past the
//! O(n²) 100 000-node wall.
//!
//! # The wall this breaks
//! [`crate::gpu_layout::step_cpu`] and its WGSL twin `cs_layout` both do **all-pairs**
//! O(n²) repulsion (every node loops over every other). That is fine to ~30k, hurts at
//! 100k (one CPU step ≈ 24 s; the GPU hides the constant but the O(n²) is intact — its
//! per-iteration cost still grows quadratically, so it walls around ~1M and cannot reach
//! 10M). The *render* was never the wall: the instanced cloud
//! ([`facett_core::render::gpu::graphcloud`]) draws the whole node/edge cloud in **two
//! draw calls**, so it scales to millions of instances. The wall is the LAYOUT.
//!
//! # The two-lane scale-aware layout ([`layout_world`])
//! * **Barnes–Hut O(n log n), parallel** — [`facett_core::barnes_hut::fr_step`], the
//! same core `facett-graphnav` uses. A *real* force layout, comfortable to ~1M nodes
//! (measured — see `examples/scale_probe`). Seeded from the hierarchical placement
//! below so it converges structured + fast.
//! * **Hierarchical space-filling placement, O(n), no force pass** — above the force
//! budget the graph is placed by its LOD hierarchy (repos on a coarse grid, each
//! repo's crates+functions packed into its cell). No n-body pass at all, so it is
//! linear and reaches **10M** trivially; the GPU cloud renders the structured result
//! directly. This is the "grid / space-filling initial placement the GPU cloud renders
//! without a full force pass" lane.
//!
//! # The function-level data seam
//! [`WorldGraph::from_specs`] takes [`RepoSpec`]/[`CrateSpec`] — the repo→crate→function
//! hierarchy. Real function data (nornir's `graph/extract` symbol/call rows) drops in
//! here unchanged; [`WorldGraph::synthetic`] fabricates a **faithful** hierarchy at any
//! target size (clearly flagged [`WorldGraph::synthetic_flag`]) so the scale path is real
//! and testable without a live warehouse.
use facett_core::barnes_hut;
use crate::model::Color;
// ── the world graph's categorical COLOUR map ─────────────────────────────────
//
// The grey-blob fix: every node is coloured by its TIER and its owning REPO/CRATE, so
// the 100k world reads as a structured, coloured map — never an undifferentiated grey
// grid. The 8 base hues are the **validated dataviz reference** categorical set (the
// SAME palette `nornir_warehouse_nav::palette` validated for colour-blind separability
// — worst adjacent CVD ΔE clear of the floor); kept here, not eyeballed, so the world
// graph colours itself without a cross-crate dependency. Repos get distinct hues; a
// crate is a shade of its repo; a function a lighter shade of its crate — so the tree
// is legible as colour families, and size/opacity fall away by tier.
/// The 8 base categorical hues, dark-surface steps (dataviz reference).
const HUES_DARK: [(u8, u8, u8); 8] = [
(0x39, 0x87, 0xe5), // blue
(0x19, 0x9e, 0x70), // aqua
(0xc9, 0x85, 0x00), // yellow
(0x00, 0x83, 0x00), // green
(0x90, 0x85, 0xe9), // violet
(0xe6, 0x67, 0x67), // red
(0xd5, 0x51, 0x81), // magenta
(0xd9, 0x59, 0x26), // orange
];
/// The 8 base categorical hues, light-surface steps (dataviz reference).
const HUES_LIGHT: [(u8, u8, u8); 8] = [
(0x2a, 0x78, 0xd6),
(0x1b, 0xaf, 0x7a),
(0xed, 0xa1, 0x00),
(0x00, 0x83, 0x00),
(0x4a, 0x3a, 0xa7),
(0xe3, 0x49, 0x48),
(0xe8, 0x7b, 0xa4),
(0xeb, 0x68, 0x34),
];
/// Mix a channel a fraction `k` toward `target` (0..255), clamped.
fn mix1(c: u8, target: f32, k: f32) -> u8 {
let c = c as f32;
(c + (target - c) * k).round().clamp(0.0, 255.0) as u8
}
/// Lighten/darken all three channels toward the surface (light: toward white; dark:
/// toward the dark surface) by fraction `k`.
fn shade((r, g, b): (u8, u8, u8), k: f32, dark: bool) -> (u8, u8, u8) {
let target = if dark { 235.0 } else { 20.0 };
(mix1(r, target, k), mix1(g, target, k), mix1(b, target, k))
}
/// **The categorical hue for repo slot `i`** on the given surface. Slots wrap the 8
/// validated hues; every wrap lightens one tier (secondary-encoded by position + the
/// repo cluster in space), so identity follows the entity deterministically.
#[must_use]
pub fn repo_hue(slot: usize, dark: bool) -> Color {
let base = if dark { &HUES_DARK } else { &HUES_LIGHT };
let (r, g, b) = base[slot % 8];
// Tier wrap past 8 repos: lighten toward the surface a fixed step.
let tier = slot / 8;
let (r, g, b) = if tier == 0 { (r, g, b) } else { shade((r, g, b), (tier as f32 * 0.22).min(0.62), dark) };
Color::rgb(r, g, b)
}
/// **The fill for one world node**, by tier + owning repo/crate. A repo wears its hue; a
/// crate a slightly surface-nudged shade of the repo (alternating per ordinal so sibling
/// crates separate); a function a distinctly lighter shade of its crate — so a function
/// reads as "of this crate, two levels down" and the 100k world is a coloured map, not
/// grey. Opacity falls by tier so the hierarchy reads at a glance.
#[must_use]
pub fn node_color(level: NodeLevel, repo_slot: usize, crate_ordinal: usize, dark: bool) -> Color {
let (r, g, b) = {
let c = repo_hue(repo_slot, dark);
(c.r, c.g, c.b)
};
match level {
NodeLevel::Repo => Color::rgba(r, g, b, 255),
NodeLevel::Crate => {
// A per-ordinal tick keeps sibling crate hulls separable within the repo hue.
let k = 0.14 + if crate_ordinal.is_multiple_of(2) { 0.0 } else { 0.10 };
let (r, g, b) = shade((r, g, b), k, dark);
Color::rgba(r, g, b, 240)
}
NodeLevel::Function => {
// A function is a clearly lighter shade of its crate hue (never grey), with a
// small per-crate wobble so adjacent crates' function discs stay distinct.
let k = 0.34 + (crate_ordinal % 3) as f32 * 0.05;
let (r, g, b) = shade((r, g, b), k, dark);
Color::rgba(r, g, b, 220)
}
}
}
/// Marker-radius multiplier by tier (repo largest, function smallest) — the size channel
/// of the hierarchy, so a still/cloud render reads repo ≫ crate ≫ function at a glance.
#[must_use]
pub fn tier_scale(level: NodeLevel) -> f32 {
match level {
NodeLevel::Repo => 3.2,
NodeLevel::Crate => 1.7,
NodeLevel::Function => 0.85,
}
}
/// The per-node owning-crate ordinal (0-based within its repo), for colouring. A single
/// linear pass over the repo-grouped node order (repo, then per crate: crate node then
/// its functions) — the same order `from_specs`/`hier_placement` use. Repo nodes report
/// their repo's crate count as a harmless sentinel (unused by `node_color` for repos).
#[must_use]
pub fn crate_ordinals(w: &WorldGraph) -> Vec<u32> {
let mut out = vec![0u32; w.n];
let mut i = 0usize;
while i < w.n {
let r = w.repo_of[i];
// current crate ordinal within this repo; -1 until the first crate node
let mut cur: i64 = -1;
while i < w.n && w.repo_of[i] == r {
match w.level[i] {
NodeLevel::Repo => out[i] = 0,
NodeLevel::Crate => {
cur += 1;
out[i] = cur as u32;
}
NodeLevel::Function => out[i] = if cur < 0 { 0 } else { cur as u32 },
}
i += 1;
}
}
out
}
/// Which zoom level of the world the caller wants materialised.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Lod {
/// Repos only (+ aggregated cross-repo edges) — the constellation.
Repos,
/// Repos + their crates (+ containment + crate-dep edges).
Crates,
/// The full world: repos + crates + **functions** (+ call edges). The 10M target.
Functions,
}
impl Lod {
/// The stable lowercase key (state_json / robot control).
#[must_use]
pub fn key(self) -> &'static str {
match self {
Lod::Repos => "repos",
Lod::Crates => "crates",
Lod::Functions => "functions",
}
}
/// Parse from a key.
#[must_use]
pub fn from_key(k: &str) -> Option<Lod> {
match k {
"repos" => Some(Lod::Repos),
"crates" => Some(Lod::Crates),
"functions" => Some(Lod::Functions),
_ => None,
}
}
}
/// A node's kind (its LOD level) — drives colour + radius in the cloud.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[repr(u8)]
pub enum NodeLevel {
Repo = 0,
Crate = 1,
Function = 2,
}
/// One crate in a repo spec: its name + how many functions it holds. Real extraction
/// fills `functions` from nornir's symbol rows; the synthetic builder fabricates them.
#[derive(Clone, Debug)]
pub struct CrateSpec {
pub name: String,
pub functions: u32,
}
/// One repo in the world spec: its name + produced crates. The function-level data seam.
#[derive(Clone, Debug)]
pub struct RepoSpec {
pub name: String,
pub crates: Vec<CrateSpec>,
}
/// The materialised world graph at one LOD: an index-space node/edge graph plus the
/// per-node LOD level and owning-repo index (for colour-by-repo + the hierarchical
/// placement). Node ordering is **grouped by repo** (each repo's nodes are one
/// contiguous run: the repo node, then its crate nodes, then its function nodes), which
/// is what makes the O(n) hierarchical placement a single linear pass.
pub struct WorldGraph {
pub lod: Lod,
pub n: usize,
/// Directed call/containment edges by node index. May be empty when built with
/// `with_edges = false` (the massive placement-only path, to bound memory at 10M).
pub edges: Vec<(u32, u32)>,
/// Per-node LOD level.
pub level: Vec<NodeLevel>,
/// Per-node owning repo index (`repo_count` is `repos.len()`).
pub repo_of: Vec<u32>,
/// Repo names in index order (`repo_of[i]` indexes this).
pub repos: Vec<String>,
/// True when the hierarchy is fabricated (not live warehouse data).
synthetic: bool,
}
impl WorldGraph {
/// Was this hierarchy fabricated (vs. built from live warehouse/extract data)?
#[must_use]
pub fn synthetic_flag(&self) -> bool {
self.synthetic
}
/// Number of distinct repos.
#[must_use]
pub fn repo_count(&self) -> usize {
self.repos.len()
}
/// Build the world at `lod` from explicit repo→crate→function specs (the real-data
/// front door). `with_edges` materialises the call/containment edge list (skip it at
/// massive scale when only placement is wanted). `synthetic` flags fabricated data.
#[must_use]
pub fn from_specs(specs: &[RepoSpec], lod: Lod, with_edges: bool, synthetic: bool) -> Self {
let mut level = Vec::new();
let mut repo_of = Vec::new();
let mut repos = Vec::with_capacity(specs.len());
// Per-repo: the index of that repo's node, and (for edge wiring) the index range
// of its function nodes so we can build a sparse call graph.
let mut repo_node_idx = Vec::with_capacity(specs.len());
// fn_ranges[r] = (start, end) over the flat node index space for repo r's fns.
let mut fn_ranges: Vec<(u32, u32)> = Vec::with_capacity(specs.len());
// crate node indices per repo (for containment + crate-dep edges).
let mut crate_idx: Vec<Vec<u32>> = Vec::with_capacity(specs.len());
for (r, spec) in specs.iter().enumerate() {
repos.push(spec.name.clone());
let repo_idx = level.len() as u32;
repo_node_idx.push(repo_idx);
level.push(NodeLevel::Repo);
repo_of.push(r as u32);
let mut this_crates = Vec::new();
if lod == Lod::Crates || lod == Lod::Functions {
for c in &spec.crates {
let ci = level.len() as u32;
this_crates.push(ci);
level.push(NodeLevel::Crate);
repo_of.push(r as u32);
// functions immediately after their crate node (Functions LOD only)
if lod == Lod::Functions {
for _ in 0..c.functions {
level.push(NodeLevel::Function);
repo_of.push(r as u32);
}
}
}
}
let fn_end = level.len() as u32;
fn_ranges.push((repo_idx + 1, fn_end));
crate_idx.push(this_crates);
}
let n = level.len();
let mut edges = Vec::new();
if with_edges {
// Containment: repo → its crates, crate → its functions (structures the layout).
// Plus a sparse CALL graph: intra-crate chains + a few cross-repo calls that
// follow a synthetic repo-dependency ring. ~2–3 edges / node, the realistic
// sparse degree of a crate/symbol dependency graph.
for r in 0..specs.len() {
let repo_idx = repo_node_idx[r];
// repo → crates
for &ci in &crate_idx[r] {
edges.push((repo_idx, ci));
}
if lod == Lod::Functions {
// Walk this repo's function run and wire a call chain + crate containment.
let (fs, fe) = fn_ranges[r];
// crate → first function of each crate is approximated by the chain;
// give every function a "call next" + occasional "call +7" branch.
let mut i = fs;
// skip crate nodes interleaved: identify function nodes by level.
while i < fe {
if level[i as usize] == NodeLevel::Function {
if i + 1 < fe && level[(i + 1) as usize] == NodeLevel::Function {
edges.push((i, i + 1));
}
if i + 7 < fe && level[(i + 7) as usize] == NodeLevel::Function {
edges.push((i, i + 7));
}
}
i += 1;
}
}
}
// Cross-repo call edges: repo r's first node → repo (r+1)%R first node, plus
// a couple of long-range calls, so the graph is one connected component with
// real cross-cluster tension for the force lane.
let rc = specs.len();
if rc > 1 {
for r in 0..rc {
let a = repo_node_idx[r];
let b = repo_node_idx[(r + 1) % rc];
edges.push((a, b));
let c = repo_node_idx[(r * 7 + 3) % rc];
edges.push((a, c));
}
}
}
Self { lod, n, edges, level, repo_of, repos, synthetic }
}
/// Fabricate a **faithful** world graph of roughly `target` nodes at `lod`: a
/// repo→crate→function hierarchy with the fan-out of a real workspace (a few
/// thousand repos at most, 8 crates each, functions filling the rest), plus the
/// sparse call graph. `with_edges = false` skips edge materialisation (memory bound
/// at 10M, where the placement lane needs no edges). Always flagged synthetic.
#[must_use]
pub fn synthetic(target: usize, lod: Lod, with_edges: bool) -> Self {
let target = target.max(1);
// Choose a repo count that keeps repos in the low thousands even at 10M, so the
// per-repo cell holds a believable crate/function population.
let crates_per_repo = 8usize;
let repos = match lod {
Lod::Repos => target.max(1),
Lod::Crates => (target / (1 + crates_per_repo)).max(1),
Lod::Functions => {
// nodes_per_repo = 1 + C + C*Fn. Pick repos ≈ sqrt(target)/… bounded.
let r = ((target as f64).sqrt() as usize / 4).clamp(8, 6000);
r.min(target)
}
};
let mut specs = Vec::with_capacity(repos);
match lod {
Lod::Repos => {
for r in 0..repos {
specs.push(RepoSpec { name: format!("repo{r}"), crates: Vec::new() });
}
}
Lod::Crates => {
for r in 0..repos {
let crates = (0..crates_per_repo)
.map(|c| CrateSpec { name: format!("r{r}c{c}"), functions: 0 })
.collect();
specs.push(RepoSpec { name: format!("repo{r}"), crates });
}
}
Lod::Functions => {
// Distribute the remaining budget as functions across repos×crates.
let overhead = repos * (1 + crates_per_repo);
let fns_total = target.saturating_sub(overhead);
let fns_per_crate = (fns_total / (repos * crates_per_repo)).max(1);
for r in 0..repos {
let crates = (0..crates_per_repo)
.map(|c| CrateSpec { name: format!("r{r}c{c}"), functions: fns_per_crate as u32 })
.collect();
specs.push(RepoSpec { name: format!("repo{r}"), crates });
}
}
}
Self::from_specs(&specs, lod, with_edges, true)
}
}
/// Which layout lane [`layout_world`] ran — reported so the caller (and the probe) can
/// print the honest algorithm used at a given scale.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum LayoutLane {
/// Barnes–Hut O(n log n) parallel force layout (a real n-body converge).
BarnesHut,
/// Hierarchical space-filling placement, O(n), no force pass (the massive lane).
HierGrid,
}
impl LayoutLane {
#[must_use]
pub fn key(self) -> &'static str {
match self {
LayoutLane::BarnesHut => "barnes_hut",
LayoutLane::HierGrid => "hier_grid",
}
}
}
/// The scale-aware layout budget: above `bh_max` nodes the force pass is skipped for the
/// O(n) hierarchical placement; `iters` is the Barnes–Hut converge budget below it.
#[derive(Clone, Copy, Debug)]
pub struct LayoutBudget {
pub bh_max: usize,
pub iters: usize,
}
impl Default for LayoutBudget {
fn default() -> Self {
// 1M is comfortably inside the Barnes–Hut lane's measured envelope; past it the
// per-converge cost stops being interactive, so we place hierarchically instead.
Self { bh_max: 1_000_000, iters: 80 }
}
}
/// **The scale-aware world-graph layout.** Returns a position per node in the
/// `[-1, 1]²` box, plus which lane produced it.
///
/// * `w.n ≤ budget.bh_max` → **Barnes–Hut** O(n log n) parallel force layout, seeded
/// from the hierarchical placement (so it converges structured and fast). Needs
/// `w.edges` (build the world `with_edges = true`).
/// * otherwise → **hierarchical space-filling placement**, O(n), no force pass — reaches
/// 10M. Needs no edges.
///
/// Deterministic: no RNG anywhere (the placement is a pure function of the hierarchy;
/// the Barnes–Hut lane is byte-deterministic for any worker count — see
/// [`facett_core::barnes_hut`]).
#[must_use]
pub fn layout_world(w: &WorldGraph, budget: &LayoutBudget) -> (Vec<[f32; 2]>, LayoutLane) {
let base = hier_placement(w);
if w.n <= budget.bh_max && !w.edges.is_empty() {
let edges: Vec<(usize, usize)> =
w.edges.iter().map(|&(a, b)| (a as usize, b as usize)).collect();
let adj = barnes_hut::adjacency(w.n, &edges);
// **Separation-preserving polish.** The world graph is containment-dominated
// (repo→crate→function is a forest of stars): a full Fruchterman–Reingold
// converge on it *collapses* — every star's leaves pile onto their parent, the
// "grå bajskorvar" stacking. So the force lane is a LIGHT, LOCAL polish of the
// already-spread galaxy seed, not a from-scratch converge:
// * a large ideal length `k` (√(64/n), 16× the classic √(4/n)) keeps the
// repulsion floor high so nodes stay separated;
// * a small, quickly-cooling temperature cap lets call edges tighten a little
// without letting containment stars implode;
// * a bounded iteration count (≤ 24) — enough to relieve edge tension, far short
// of a full converge.
// Net: edges still contract vs. random pairs (springs do pull), but the galaxy's
// clusters-of-clusters spread is preserved (verified by `diag`/`spread` tests).
let k = (64.0 / w.n as f32).sqrt();
let theta = barnes_hut::BH_THETA;
let iters = budget.iters.min(24);
let mut pos = base;
for it in 0..iters {
let temp = 0.012 * (1.0 - it as f32 / iters.max(1) as f32);
pos = barnes_hut::fr_step::<2>(&pos, &adj, k, theta, temp);
}
barnes_hut::normalize_box(&mut pos);
(pos, LayoutLane::BarnesHut)
} else {
(base, LayoutLane::HierGrid)
}
}
/// The golden angle (radians) — the phyllotaxis "sunflower" step that packs a disc of
/// points with no two on the same ray and near-uniform density (so a crate's functions
/// fan out evenly instead of landing on a grid line or on top of one another).
pub(crate) const GOLDEN_ANGLE: f32 = 2.399_963_2; // π(3 − √5)
/// **Hierarchical *galaxy* placement** (O(n), no force pass) — the spread layout the
/// world graph renders directly. A three-level nest that puts the repo→crate→function
/// hierarchy *into space* so it reads at a glance and nodes do **not** stack:
///
/// * **Repos** sit on a near-square coarse grid — one well-guttered cell each, so repo
/// clusters never touch.
/// * **Crates** fan on a ring around their repo's centre (the repo node sits at the
/// centre), so each repo is a little solar system.
/// * **Functions** fan around *their* crate on a phyllotaxis (sunflower) disc whose
/// radius is bounded by the gap to the neighbouring crate — even density, minimal
/// overlap, and the containment hierarchy is legible as concentric structure.
///
/// Deterministic (a pure function of the hierarchy, a per-repo phase the only "rng").
/// Positions land in the `[-1, 1]²` box. This is both the massive-lane output AND the
/// seed the (separation-preserving) force lane polishes below the budget.
#[must_use]
pub fn hier_placement(w: &WorldGraph) -> Vec<[f32; 2]> {
let n = w.n;
let mut pos = vec![[0.0f32; 2]; n];
if n == 0 {
return pos;
}
let repo_count = w.repo_count().max(1);
let rc_cols = (repo_count as f64).sqrt().ceil() as usize;
let rc_rows = repo_count.div_ceil(rc_cols);
// Repo cell pitch in world units; `half` is the usable radius inside a cell (a gutter
// keeps neighbouring repo systems clearly apart).
let cell = 2.0f32 / rc_cols.max(rc_rows) as f32;
let half = cell * 0.5 * 0.82;
// Contiguous run per repo: scan repo_of once (nodes are grouped by repo). Within a
// run the order is repo node, then per crate: the crate node followed by its function
// nodes (exactly what `from_specs` emits) — so a single linear pass recovers the tree.
let mut i = 0usize;
while i < n {
let r = w.repo_of[i] as usize;
let start = i;
while i < n && w.repo_of[i] as usize == r {
i += 1;
}
let end = i;
// Repo cell centre in [-1, 1].
let cr = r / rc_cols;
let cc = r % rc_cols;
let ccx = -1.0 + (cc as f32 + 0.5) * cell;
let ccy = -1.0 + (cr as f32 + 0.5) * cell;
// Recover this repo's crate groups (crate node + its function run).
let mut repo_node: Option<usize> = None;
// (crate node index, [function node indices])
let mut crates: Vec<(usize, Vec<usize>)> = Vec::new();
for k in start..end {
match w.level[k] {
NodeLevel::Repo => repo_node = Some(k),
NodeLevel::Crate => crates.push((k, Vec::new())),
NodeLevel::Function => {
if let Some(last) = crates.last_mut() {
last.1.push(k);
} else {
// A function with no preceding crate (degenerate): treat the repo
// as its cluster centre so it still gets a real position.
crates.push((start, vec![k]));
}
}
}
}
if let Some(rn) = repo_node {
pos[rn] = [ccx, ccy];
}
let c = crates.len().max(1);
// Crate ring radius; a lone crate sits near the repo centre so its functions get
// the whole cell.
let crate_ring = if c == 1 { 0.0 } else { half * 0.55 };
// Gap between adjacent crate centres on the ring — bounds the function disc so
// sibling crates' functions don't inter-penetrate.
let gap = if c > 1 {
2.0 * crate_ring * (std::f32::consts::PI / c as f32).sin()
} else {
half
};
let fdisc = (gap * 0.46).min(half * 0.92).max(1e-4);
// A deterministic per-repo phase so systems aren't all clocked identically.
let phase = r as f32 * 0.7;
for (ci, (cidx, fns)) in crates.iter().enumerate() {
let ang = GOLDEN_ANGLE * ci as f32 + phase;
let cx = ccx + crate_ring * ang.cos();
let cy = ccy + crate_ring * ang.sin();
if *cidx != start {
pos[*cidx] = [cx, cy];
}
let m = fns.len();
for (j, &f) in fns.iter().enumerate() {
// Sunflower disc: radius ∝ √((j+½)/m) for uniform areal density, angle by
// the golden step. Even fan, no two functions coincident.
let t = if m > 0 { (((j as f32) + 0.5) / m as f32).sqrt() } else { 0.0 };
let rr = fdisc * t;
let th = j as f32 * GOLDEN_ANGLE + phase;
pos[f] = [cx + rr * th.cos(), cy + rr * th.sin()];
}
}
}
pos
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn lod_roundtrips() {
for l in [Lod::Repos, Lod::Crates, Lod::Functions] {
assert_eq!(Lod::from_key(l.key()), Some(l));
}
assert_eq!(Lod::from_key("nope"), None);
}
#[test]
fn synthetic_functions_expands_to_target_and_is_grouped() {
let w = WorldGraph::synthetic(50_000, Lod::Functions, true);
// Within a small factor of the target.
assert!(w.n >= 40_000 && w.n <= 60_000, "n={} near target", w.n);
// Node ordering is grouped by repo (repo_of is non-decreasing within runs):
// every repo forms one contiguous run.
let mut seen = std::collections::BTreeSet::new();
let mut prev = None;
for &r in &w.repo_of {
if Some(r) != prev {
assert!(seen.insert(r), "repo {r} run is contiguous (not revisited)");
prev = Some(r);
}
}
// Repo/crate/function levels all present.
assert!(w.level.contains(&NodeLevel::Repo));
assert!(w.level.contains(&NodeLevel::Crate));
assert!(w.level.contains(&NodeLevel::Function));
// Sparse: ~2–3 edges per node.
assert!(w.edges.len() >= w.n && w.edges.len() <= 5 * w.n, "sparse degree: {} edges / {} nodes", w.edges.len(), w.n);
}
#[test]
fn hier_placement_is_in_box_and_deterministic() {
let w = WorldGraph::synthetic(20_000, Lod::Functions, false);
let a = hier_placement(&w);
let b = hier_placement(&w);
assert_eq!(a.len(), w.n);
assert_eq!(a, b, "placement is a pure function of the hierarchy");
for p in &a {
assert!(p[0].abs() <= 1.01 && p[1].abs() <= 1.01, "in box: {p:?}");
assert!(p[0].is_finite() && p[1].is_finite());
}
}
#[test]
fn small_world_takes_the_barnes_hut_lane_and_contracts_edges() {
let w = WorldGraph::synthetic(8_000, Lod::Functions, true);
let (pos, lane) = layout_world(&w, &LayoutBudget { bh_max: 1_000_000, iters: 60 });
assert_eq!(lane, LayoutLane::BarnesHut);
for p in &pos {
assert!(p[0].abs() <= 1.01 && p[1].abs() <= 1.01);
assert!(p[0].is_finite() && p[1].is_finite());
}
// Edges contracted vs. a random baseline (springs actually pulled).
let dist = |i: usize, j: usize| ((pos[i][0] - pos[j][0]).powi(2) + (pos[i][1] - pos[j][1]).powi(2)).sqrt();
let mean_edge: f32 = w.edges.iter().map(|&(a, b)| dist(a as usize, b as usize)).sum::<f32>() / w.edges.len() as f32;
let m = 4000usize;
let mut s = 0.0f32;
for t in 0..m {
s += dist((t * 7) % w.n, (t * 4099 + 1) % w.n);
}
let mean_pair = s / m as f32;
assert!(mean_edge < mean_pair, "edges shorter than random pairs: {mean_edge} vs {mean_pair}");
}
#[test]
fn massive_world_takes_the_hier_grid_lane() {
// No edges materialised — the placement-only massive path.
let w = WorldGraph::synthetic(2_000_000, Lod::Functions, false);
let (pos, lane) = layout_world(&w, &LayoutBudget { bh_max: 1_000_000, iters: 80 });
assert_eq!(lane, LayoutLane::HierGrid, "past the force budget → O(n) placement");
assert_eq!(pos.len(), w.n);
}
/// `(bbox_span, crowded_fraction)` over a `g × g` occupancy grid — `crowded` is the
/// fraction of nodes sharing a cell with another (the stacking proxy).
fn spread_stats(pos: &[[f32; 2]], g: usize) -> (f32, f32) {
let (mut x0, mut y0, mut x1, mut y1) = (f32::MAX, f32::MAX, f32::MIN, f32::MIN);
for p in pos {
x0 = x0.min(p[0]); y0 = y0.min(p[1]); x1 = x1.max(p[0]); y1 = y1.max(p[1]);
}
let span = (x1 - x0).max(y1 - y0).max(1e-6);
let cell = |p: &[f32; 2]| {
(((p[0] - x0) / span * g as f32) as i32, ((p[1] - y0) / span * g as f32) as i32)
};
let mut buckets = std::collections::HashMap::<(i32, i32), u32>::new();
for p in pos {
*buckets.entry(cell(p)).or_default() += 1;
}
let crowded = pos.iter().filter(|p| buckets[&cell(p)] > 1).count();
(span, crowded as f32 / pos.len().max(1) as f32)
}
/// **RED-when-broken: the world graph SPREADS — nodes do not stack.** The old force
/// lane collapsed the well-spread hierarchical seed (every containment star imploded
/// onto its parent: ~51 % of nodes stacked at 4k, the "grå bajskorvar"). This pins the
/// fix: after the full layout, the bbox fills the box AND almost no node shares a coarse
/// grid cell with another. A regression to the collapsing force lane trips this hard.
#[test]
fn layout_spreads_nodes_and_does_not_stack() {
let w = WorldGraph::synthetic(4_000, Lod::Functions, true);
let (pos, lane) = layout_world(&w, &LayoutBudget::default());
assert_eq!(lane, LayoutLane::BarnesHut);
// Distinct positions (no two nodes at the exact same point).
let mut seen = std::collections::HashSet::new();
for p in &pos {
assert!(seen.insert((p[0].to_bits(), p[1].to_bits())), "positions are distinct");
}
// Fills the box, and on a 200×200 grid (10× the node count of cells) barely any node
// stacks — the collapse bug put this over 0.5.
let (span, crowded) = spread_stats(&pos, 200);
assert!(span > 1.2, "layout fills space (span {span:.3})");
assert!(crowded < 0.08, "nodes do not stack (crowded fraction {crowded:.3} must stay tiny)");
}
/// The galaxy seed itself is a clean, near-zero-overlap spread at moderate scale (the
/// property the force polish must preserve, not destroy).
#[test]
fn hier_seed_is_well_distributed() {
let w = WorldGraph::synthetic(4_000, Lod::Functions, false);
let base = hier_placement(&w);
let (span, crowded) = spread_stats(&base, 200);
assert!(span > 1.2, "seed fills space (span {span:.3})");
assert!(crowded < 0.15, "seed is well-distributed (crowded {crowded:.3})");
}
/// Colour: adjacent repos get DISTINCT hues and a function is a (non-grey) shade of its
/// crate's repo hue — the grey-blob red-when-broken at the data level.
#[test]
fn nodes_are_coloured_by_repo_not_grey() {
// The 8 base slots are all different (categorical separability).
let mut hues = std::collections::HashSet::new();
for s in 0..8 {
let c = repo_hue(s, true);
assert!(hues.insert((c.r, c.g, c.b)), "repo slot {s} has a distinct hue");
}
// A function carries its repo's hue family (not grey): its channels track the repo.
for s in 0..8 {
let rc = repo_hue(s, true);
let fc = node_color(NodeLevel::Function, s, 0, true);
let grey = fc.r.abs_diff(fc.g) < 6 && fc.g.abs_diff(fc.b) < 6;
assert!(!grey || (rc.r.abs_diff(rc.g) < 6 && rc.g.abs_diff(rc.b) < 6),
"function of repo {s} is hued like its repo, not grey (fn=#{:02x}{:02x}{:02x})", fc.r, fc.g, fc.b);
}
}
}