facett-core 0.2.0

//! **navgraph** — one numbered navigation graph over the whole application, down to the
//! fields, drawn in dev mode. Phase 1 of `.nornir/navgraph-design.md`.
//!
//! Owner, 2026-09-28: *"show graph of navigation with unique numbering at dev mode"*.
//!
//! # What it is
//!
//! A tree of nodes, one per addressable thing on screen (`App` → `Surface` → `Pane` →
//! `Group` → `Field`). Each node has a stable dotted id (`facett-demo.deck.tabs.Map`)
//! and a number, the path of 1-based ranks from the root: `1`, `1.2`, `1.2.3`.
//!
//! * **Declared order wins.** A step is a plain number when the parent's child order is
//!   declared: by the host's [`NavOrder`], by a container whose draw order *is* its
//!   declaration (a tab strip, [`declare_draw_order`]), or by a list the container hands
//!   in for this frame ([`declare_children`], e.g. a [`FocusGroup`](crate::focus::FocusGroup)).
//! * **`~n`** — the parent declared nothing, so `n` is the draw order this frame. A guess
//!   is marked on the step that is guessed and can never pass for a declaration.
//! * **`?n`** — the parent declared an order and this child is not in it. `n` is its draw
//!   rank, so two undeclared siblings are still tellable apart. The `?` is a to-do list.
//!
//! # How it is collected
//!
//! A per-frame arena ([`NavGraph`]) kept in the egui `Context` memory. It is allocated
//! once and cleared every frame; nodes are slots in a `Vec` whose capacity and whose
//! `String`s are reused, so a steady-state frame allocates nothing in the arena.
//! Registration points:
//!
//! * [`crate::a11y::node`] — every FC-4 painted atom registers as a `Field`;
//! * [`crate::devid::badge`] — every deck pane registers as a `Pane`;
//! * [`crate::focus::FocusGroup::nav_register`] — a form group and its fields;
//! * [`scope`] / [`begin`]+[`end`] — a parent (app, surface, group) around a closure;
//! * [`field`] — a plain egui widget (`Button`, `TextEdit`) from its `Response`.
//!
//! An egui [`Plugin`](egui::Plugin) ([`install`]) clears the arena at the start of each
//! pass and, at the end of the pass, numbers the nodes, paints the overlay on the top
//! layer (so dev mode never moves layout) and publishes one AccessKit node per shown
//! chip: `nav: 1.2.3 tabs.Map [focused]`. The chips publish AccessKit nodes WITHOUT a
//! hit-test rect, so the overlay can never take a click from the widget under it.
//!
//! # The gate
//!
//! Every entry point returns at once unless dev mode is on — the same gate as the dev-id
//! badge ([`crate::devid::enabled`]: `debug_assertions`, or `FACETT_DEVID=1` in a
//! release build). Inside dev mode nothing is collected while the overlay is
//! [`NavMode::Off`] and no chord is being typed, so an idle dev build pays one atomic
//! load per registration point.
//!
//! # Keys (dev mode)
//!
//! * `Ctrl+Shift+G` cycles the overlay: off → labels → labels + next → labels + all edges.
//! * `Ctrl+G 1 . 2 . 3 Enter` focuses node `1.2.3` (Escape cancels, Backspace edits).
//!   `~` and `?` are not typed: `1.2` matches `~1.~2` too.
//!
//! `FACETT_NAVGRAPH=labels|next|all` sets the starting mode.

use std::fmt::Write as _;
use std::sync::atomic::{AtomicUsize, Ordering};

use egui::{Color32, Context, FontId, Id, IdMap, Key, LayerId, Modifiers, Order, Pos2, Rect, Response, Stroke, Ui, pos2, vec2};
use serde::{Deserialize, Serialize};

use crate::edges::{point_at_frac, spline_points_into};
use crate::look::NavOverlayTokens;
use crate::nav::{Dir4, nearest_in_direction};

/// Ordinary egui: every navigable widget egui laid out, read at the end of the pass.
pub mod harvest;

/// The prefix of every navgraph atom in the AccessKit tree.
pub const NAV_ATOM: &str = "nav:";
/// The suffix a chip's atom carries when its node has focus (or a chord selected it).
pub const FOCUSED_MARK: &str = crate::devid::FOCUSED_MARK;
/// Levels shown without hovering (owner, 2026-09-25: app, surface, pane).
pub const DEFAULT_DEPTH: u8 = 3;
/// In a [`NavOrder`] list, the slot for the one child that is not named — the active
/// pane of a tabbed deck, whose key changes with the tab.
pub const WILDCARD: &str = "*";

const GRAPH_ID: &str = "facett_navgraph";
const CHIP_FONT: f32 = 10.0;
const SPLINE_SAMPLES: usize = 16;

/// How many contexts are collecting right now. A fast path only: zero means every
/// registration point returns before touching the context.
static COLLECTING: AtomicUsize = AtomicUsize::new(0);

/// What kind of thing a node is (design §1).
#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum NavKind {
    App,
    Surface,
    Pane,
    Group,
    Field,
}

impl NavKind {
    pub fn as_str(self) -> &'static str {
        match self {
            Self::App => "app",
            Self::Surface => "surface",
            Self::Pane => "pane",
            Self::Group => "group",
            Self::Field => "field",
        }
    }
}

/// What the overlay draws. `Ctrl+Shift+G` steps through them in this order.
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum NavMode {
    #[default]
    Off,
    Labels,
    LabelsNext,
    All,
}

impl NavMode {
    /// The next mode in the cycle (wraps to `Off`).
    pub fn next(self) -> Self {
        match self {
            Self::Off => Self::Labels,
            Self::Labels => Self::LabelsNext,
            Self::LabelsNext => Self::All,
            Self::All => Self::Off,
        }
    }
    pub fn as_str(self) -> &'static str {
        match self {
            Self::Off => "off",
            Self::Labels => "labels",
            Self::LabelsNext => "next",
            Self::All => "all",
        }
    }
    /// Parse `off|labels|next|all` (also `0..=3`). `None` for anything else.
    pub fn parse(s: &str) -> Option<Self> {
        match s.trim() {
            "off" | "0" => Some(Self::Off),
            "labels" | "on" | "1" => Some(Self::Labels),
            "next" | "labels+next" | "2" => Some(Self::LabelsNext),
            "all" | "3" => Some(Self::All),
            _ => None,
        }
    }
    fn shows_next(self) -> bool {
        matches!(self, Self::LabelsNext | Self::All)
    }
    fn shows_all(self) -> bool {
        self == Self::All
    }
}

/// One step of a number.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Step {
    /// Declared rank `n`, written `n`.
    Declared(u32),
    /// Draw-order rank under an undeclared parent, written `~n`.
    Guessed(u32),
    /// Missing from a declared parent's list; draw rank `n`, written `?n`.
    Undeclared(u32),
}

impl Step {
    pub fn is_declared(self) -> bool {
        matches!(self, Self::Declared(_))
    }
    fn rank(self) -> u32 {
        match self {
            Self::Declared(n) | Self::Guessed(n) | Self::Undeclared(n) => n,
        }
    }
    fn write_to(self, out: &mut String) {
        let _ = match self {
            Self::Declared(n) => write!(out, "{n}"),
            Self::Guessed(n) => write!(out, "~{n}"),
            Self::Undeclared(n) => write!(out, "?{n}"),
        };
    }
    fn as_str(self) -> &'static str {
        match self {
            Self::Declared(_) => "declared",
            Self::Guessed(_) => "guessed",
            Self::Undeclared(_) => "undeclared",
        }
    }
}

/// **The declared navigation order** — parent id → its ordered child keys. Handed in by
/// the host once ([`set_order`]); it is not rebuilt every frame.
///
/// Parent ids are full dotted ids (`facett-demo.deck`); the root level is the empty
/// string. Child entries are the child's own key (the last segment). [`WILDCARD`]
/// declares a slot for the one child that is not named.
///
/// It is `serde`, so it can be the child order of the future layout document (design
/// §5.1, ron).
#[derive(Clone, Debug, Default, PartialEq, Eq, Serialize, Deserialize)]
pub struct NavOrder {
    pub parents: std::collections::BTreeMap<String, Vec<String>>,
}

impl NavOrder {
    pub fn new() -> Self {
        Self::default()
    }
    /// Declare `parent`'s children, in order.
    pub fn children<I, S>(mut self, parent: &str, kids: I) -> Self
    where
        I: IntoIterator<Item = S>,
        S: Into<String>,
    {
        self.parents.insert(parent.to_string(), kids.into_iter().map(Into::into).collect());
        self
    }
    /// Declare the root level (the app nodes), in order.
    pub fn roots<I, S>(self, kids: I) -> Self
    where
        I: IntoIterator<Item = S>,
        S: Into<String>,
    {
        self.children("", kids)
    }
    pub fn get(&self, parent: &str) -> Option<&[String]> {
        self.parents.get(parent).map(Vec::as_slice)
    }
    pub fn is_empty(&self) -> bool {
        self.parents.is_empty()
    }
}

/// One node of this frame's graph.
#[derive(Clone, Debug)]
pub struct NavNode {
    /// The full dotted id, e.g. `facett-demo.deck.tabs.Map`.
    pub id: String,
    local: usize,
    /// Human text.
    pub label: String,
    pub kind: NavKind,
    /// This frame's rectangle.
    pub rect: Rect,
    /// Arena index of the parent (`None` for a root).
    pub parent: Option<u32>,
    /// 1 for a root.
    pub depth: u8,
    /// The egui widget this node focuses, when it is one.
    pub widget: Option<Id>,
    /// This node's own step (the last part of [`number`](Self::number)).
    pub step: Step,
    /// The number, e.g. `1.2.~3`.
    pub number: String,
    /// Shown this frame (depth limit, hover, focus).
    pub visible: bool,
    /// The focused widget is this node or under it.
    pub focus_in: bool,
    /// The focused widget is this node.
    pub focused: bool,
    /// Found by the end-of-pass harvest of egui's own widget record (ordinary egui),
    /// not registered by facett.
    pub harvested: bool,
    draw_rank: u32,
    kids: u32,
    wild_used: bool,
    decl_draw: bool,
    decl: String,
    hash: Id,
    chip: Rect,
}

impl NavNode {
    fn empty() -> Self {
        Self {
            id: String::new(),
            local: 0,
            label: String::new(),
            kind: NavKind::Field,
            rect: Rect::NOTHING,
            parent: None,
            depth: 1,
            widget: None,
            step: Step::Guessed(0),
            number: String::new(),
            visible: false,
            focus_in: false,
            focused: false,
            harvested: false,
            draw_rank: 0,
            kids: 0,
            wild_used: false,
            decl_draw: false,
            decl: String::new(),
            hash: Id::NULL,
            chip: Rect::NOTHING,
        }
    }
    /// The node's own key (the last id segment).
    pub fn local(&self) -> &str {
        &self.id[self.local..]
    }
    /// The last two id segments, e.g. `tabs.Map` — the short id a chip shows on hover.
    pub fn short(&self) -> &str {
        let s = self.id.as_str();
        match s.rfind('.') {
            Some(i) => match s[..i].rfind('.') {
                Some(j) => &s[j + 1..],
                None => s,
            },
            None => s,
        }
    }
    /// Does this node's number read `want`, ignoring the `~`/`?` marks?
    pub fn number_is(&self, want: &str) -> bool {
        let mut a = self.number.chars().filter(|c| *c != '~' && *c != '?');
        let mut b = want.chars().filter(|c| !c.is_whitespace());
        loop {
            match (a.next(), b.next()) {
                (None, None) => return true,
                (x, y) if x == y => {}
                _ => return false,
            }
        }
    }
}

/// A registration key: a plain string, or an a11y atom's `Debug` key.
#[derive(Clone, Copy, Debug)]
enum Key0<'a> {
    Str(&'a str),
    Debug(&'a dyn std::fmt::Debug),
}

/// **The per-frame arena** plus the few things that persist across frames (mode, order,
/// chord). Lives in the egui `Context` memory under one id.
#[derive(Clone)]
pub struct NavGraph {
    nodes: Vec<NavNode>,
    len: usize,
    stack: Vec<u32>,
    index: IdMap<u32>,
    root_kids: u32,
    root_wild_used: bool,
    scratch: String,
    // declared order (persistent, compiled once in `set_order`)
    order: NavOrder,
    order_decl: IdMap<()>,
    order_rank: IdMap<u32>,
    order_wild: IdMap<u32>,
    // persistent state
    mode: NavMode,
    depth_limit: u8,
    keep: bool,
    collect: bool,
    counted: bool,
    installed: bool,
    chord_on: bool,
    chord: String,
    selected: String,
    // derived per frame
    edges_contains: Vec<(u32, u32)>,
    edges_next: Vec<(u32, u32)>,
    edges_spatial: Vec<(u32, u32)>,
    sort_buf: Vec<(u32, u32, u32)>,
    rect_buf: Vec<Rect>,
    idx_buf: Vec<u32>,
    pts: Vec<Pos2>,
    text: String,
    guessed: usize,
    undeclared: usize,
    harvest: harvest::HarvestBuf,
}

impl Default for NavGraph {
    fn default() -> Self {
        Self {
            nodes: Vec::new(),
            len: 0,
            stack: Vec::new(),
            index: IdMap::default(),
            root_kids: 0,
            root_wild_used: false,
            scratch: String::new(),
            order: NavOrder::default(),
            order_decl: IdMap::default(),
            order_rank: IdMap::default(),
            order_wild: IdMap::default(),
            mode: NavMode::Off,
            depth_limit: DEFAULT_DEPTH,
            keep: false,
            collect: false,
            counted: false,
            installed: false,
            chord_on: false,
            chord: String::new(),
            selected: String::new(),
            edges_contains: Vec::new(),
            edges_next: Vec::new(),
            edges_spatial: Vec::new(),
            sort_buf: Vec::new(),
            rect_buf: Vec::new(),
            idx_buf: Vec::new(),
            pts: Vec::new(),
            text: String::new(),
            guessed: 0,
            undeclared: 0,
            harvest: harvest::HarvestBuf::default(),
        }
    }
}

fn root_hash() -> Id {
    Id::new("")
}

impl NavGraph {
    /// An empty graph (collection on, so the pure API can be driven without a context).
    pub fn new() -> Self {
        Self { collect: true, ..Self::default() }
    }

    // ── declared order ────────────────────────────────────────────────────────────

    /// Replace the declared order. Compiled once into hash maps keyed by egui `Id`, so
    /// a per-frame lookup hashes and allocates nothing.
    pub fn set_order(&mut self, order: NavOrder) {
        if order == self.order {
            return;
        }
        self.order_decl.clear();
        self.order_rank.clear();
        self.order_wild.clear();
        for (parent, kids) in &order.parents {
            let ph = Id::new(parent.as_str());
            self.order_decl.insert(ph, ());
            for (i, k) in kids.iter().enumerate() {
                let r = i as u32 + 1;
                if k == WILDCARD {
                    self.order_wild.insert(ph, r);
                } else {
                    self.order_rank.insert(ph.with(k.as_str()), r);
                }
            }
        }
        self.order = order;
    }
    pub fn order(&self) -> &NavOrder {
        &self.order
    }

    // ── the arena ─────────────────────────────────────────────────────────────────

    /// Clear this frame's nodes, keeping every capacity.
    pub fn clear(&mut self) {
        self.len = 0;
        self.stack.clear();
        self.index.clear();
        self.root_kids = 0;
        self.root_wild_used = false;
        self.edges_contains.clear();
        self.edges_next.clear();
        self.edges_spatial.clear();
        self.guessed = 0;
        self.undeclared = 0;
    }

    /// This frame's nodes, in registration (draw) order.
    pub fn nodes(&self) -> &[NavNode] {
        &self.nodes[..self.len]
    }
    pub fn len(&self) -> usize {
        self.len
    }
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }
    /// The node whose number reads `number` (marks ignored); first in draw order.
    pub fn find_number(&self, number: &str) -> Option<&NavNode> {
        self.nodes().iter().find(|n| n.number_is(number))
    }
    /// The node with full id `id`.
    pub fn find_id(&self, id: &str) -> Option<&NavNode> {
        self.index.get(&Id::new(id)).map(|&i| &self.nodes[i as usize])
    }
    /// Nodes whose own step is `~` or `?` (after [`finish`](Self::finish)).
    pub fn not_declared(&self) -> impl Iterator<Item = &NavNode> {
        self.nodes().iter().filter(|n| !n.step.is_declared())
    }
    pub fn mode(&self) -> NavMode {
        self.mode
    }
    pub fn depth_limit(&self) -> u8 {
        self.depth_limit
    }
    /// The full id of the node the last chord selected (empty when none).
    pub fn selected(&self) -> &str {
        &self.selected
    }
    pub fn edges_contains(&self) -> &[(u32, u32)] {
        &self.edges_contains
    }
    pub fn edges_next(&self) -> &[(u32, u32)] {
        &self.edges_next
    }
    pub fn edges_spatial(&self) -> &[(u32, u32)] {
        &self.edges_spatial
    }

    /// Register a node under `parent` (or under the scope stack's top when `None`).
    /// A second registration of the same full id in one frame merges into the first
    /// (rects unite, a widget id is kept), so a pane that a scope opened and a badge
    /// later names is one node.
    fn register(
        &mut self,
        key: Key0<'_>,
        label: &str,
        kind: NavKind,
        rect: Rect,
        widget: Option<Id>,
        parent: Option<u32>,
    ) -> Option<u32> {
        if !self.collect {
            return None;
        }
        let parent = parent.or_else(|| self.stack.last().copied());
        self.scratch.clear();
        if let Some(p) = parent {
            self.scratch.push_str(&self.nodes[p as usize].id);
            self.scratch.push('.');
        }
        let local = self.scratch.len();
        match key {
            Key0::Str(s) => push_key(&mut self.scratch, s),
            Key0::Debug(d) => {
                let _ = write!(self.scratch, "{d:?}");
                // `"node-7"` → `node-7`; keep the quotes' content only.
                let raw: &str = &self.scratch[local..];
                if raw.len() >= 2 && raw.starts_with('"') && raw.ends_with('"') {
                    self.scratch.pop();
                    self.scratch.remove(local);
                }
                sanitize_from(&mut self.scratch, local);
            }
        }
        let hash = Id::new(self.scratch.as_str());
        if let Some(&i) = self.index.get(&hash) {
            let n = &mut self.nodes[i as usize];
            n.rect = match (n.rect.is_positive(), rect.is_positive()) {
                (true, true) => n.rect.union(rect),
                (false, true) => rect,
                _ => n.rect,
            };
            if n.widget.is_none() {
                n.widget = widget;
            }
            if n.label.is_empty() {
                n.label.push_str(label);
            }
            return Some(i);
        }
        let idx = self.len;
        if idx == self.nodes.len() {
            self.nodes.push(NavNode::empty());
        }
        self.len += 1;
        let (draw_rank, depth) = match parent {
            Some(p) => {
                let pn = &mut self.nodes[p as usize];
                pn.kids += 1;
                (pn.kids, pn.depth.saturating_add(1))
            }
            None => {
                self.root_kids += 1;
                (self.root_kids, 1)
            }
        };
        let n = &mut self.nodes[idx];
        std::mem::swap(&mut n.id, &mut self.scratch);
        n.local = local;
        n.label.clear();
        n.label.push_str(label);
        n.kind = kind;
        n.rect = rect;
        n.parent = parent;
        n.depth = depth;
        n.widget = widget;
        n.step = Step::Guessed(draw_rank);
        n.number.clear();
        n.visible = false;
        n.focus_in = false;
        n.focused = false;
        n.harvested = false;
        n.draw_rank = draw_rank;
        n.kids = 0;
        n.wild_used = false;
        n.decl_draw = false;
        n.decl.clear();
        n.hash = hash;
        n.chip = Rect::NOTHING;
        self.index.insert(hash, idx as u32);
        Some(idx as u32)
    }

    /// Open a scope: register a node and push it, so later registrations hang under it.
    pub fn open(&mut self, key: &str, kind: NavKind, label: &str, rect: Rect) -> Option<u32> {
        let i = self.register(Key0::Str(key), label, kind, rect, None, None)?;
        self.stack.push(i);
        Some(i)
    }
    /// Close scope `token` (and anything left open above it), setting its final rect.
    pub fn close(&mut self, token: u32, rect: Rect) {
        while let Some(top) = self.stack.pop() {
            if top == token {
                break;
            }
        }
        if let Some(n) = self.nodes.get_mut(token as usize)
            && rect.is_positive()
        {
            n.rect = rect;
        }
    }
    /// Register a leaf (or any node) under the current scope.
    pub fn leaf(&mut self, key: &str, kind: NavKind, label: &str, rect: Rect, widget: Option<Id>) -> Option<u32> {
        self.register(Key0::Str(key), label, kind, rect, widget, None)
    }
    fn leaf_debug(&mut self, key: &dyn std::fmt::Debug, label: &str, rect: Rect, widget: Option<Id>) -> Option<u32> {
        self.register(Key0::Debug(key), label, NavKind::Field, rect, widget, None)
    }
    /// Register a leaf under an explicit parent.
    pub fn leaf_under(&mut self, parent: u32, key: &str, kind: NavKind, label: &str, rect: Rect) -> Option<u32> {
        self.register(Key0::Str(key), label, kind, rect, None, Some(parent))
    }
    /// Declare that `token`'s children are in their declared order when drawn in order
    /// (a tab strip, a toolbar whose code order is its design order).
    pub fn declare_draw_order(&mut self, token: u32) {
        if let Some(n) = self.nodes.get_mut(token as usize) {
            n.decl_draw = true;
        }
    }
    /// Declare the innermost OPEN scope's children in draw order (see
    /// [`super::declare_own_draw_order`]). No open scope: nothing is declared.
    pub fn declare_current_draw_order(&mut self) {
        if let Some(&top) = self.stack.last() {
            self.declare_draw_order(top);
        }
    }
    /// Declare `token`'s children for this frame, by key, in order.
    pub fn declare_children<'a>(&mut self, token: u32, keys: impl IntoIterator<Item = &'a str>) {
        if let Some(n) = self.nodes.get_mut(token as usize) {
            n.decl.clear();
            for k in keys {
                if !n.decl.is_empty() {
                    n.decl.push('\n');
                }
                push_key(&mut n.decl, k);
            }
            if n.decl.is_empty() {
                // An empty list is still a declaration ("no children expected").
                n.decl.push('\n');
            }
        }
    }

    // ── numbering, visibility, edges ──────────────────────────────────────────────

    /// **Number every node** and derive visibility and edges. Pure: a function of the
    /// registrations, the declared order, the focused widget and the pointer.
    pub fn finish(&mut self, focused: Option<Id>, pointer: Option<Pos2>) {
        self.guessed = 0;
        self.undeclared = 0;
        self.edges_contains.clear();
        self.edges_next.clear();
        self.edges_spatial.clear();
        self.root_wild_used = false;
        for n in &mut self.nodes[..self.len] {
            n.wild_used = false;
        }
        let root = root_hash();
        let root_declared = self.order_decl.contains_key(&root);
        for i in 0..self.len {
            let (head, tail) = self.nodes.split_at_mut(i);
            let n = &mut tail[0];
            let local = &n.id[n.local..];
            let step = match n.parent {
                Some(p) => {
                    let pn = &mut head[p as usize];
                    if pn.decl_draw {
                        Step::Declared(n.draw_rank)
                    } else if !pn.decl.is_empty() {
                        match pn.decl.split('\n').position(|k| k == local) {
                            Some(pos) => Step::Declared(pos as u32 + 1),
                            // The wildcard slot of a per-frame declaration (a scene tab set:
                            // `[tabs, *]`) takes the one unnamed child — never a harvested
                            // plain-egui widget, which is chrome, not the slot's occupant.
                            None => match pn.decl.split('\n').position(|k| k == WILDCARD) {
                                Some(pos) if !pn.wild_used && !n.harvested => {
                                    pn.wild_used = true;
                                    Step::Declared(pos as u32 + 1)
                                }
                                _ => Step::Undeclared(n.draw_rank),
                            },
                        }
                    } else if self.order_decl.contains_key(&pn.hash) {
                        lookup(&self.order_rank, &self.order_wild, pn.hash, local, &mut pn.wild_used, n.draw_rank)
                    } else {
                        Step::Guessed(n.draw_rank)
                    }
                }
                None if root_declared => {
                    lookup(&self.order_rank, &self.order_wild, root, local, &mut self.root_wild_used, n.draw_rank)
                }
                None => Step::Guessed(n.draw_rank),
            };
            n.step = step;
            n.number.clear();
            if let Some(p) = n.parent {
                n.number.push_str(&head[p as usize].number);
                n.number.push('.');
            }
            step.write_to(&mut n.number);
            n.focus_in = false;
            n.focused = false;
            match step {
                Step::Declared(_) => {}
                Step::Guessed(_) => self.guessed += 1,
                Step::Undeclared(_) => self.undeclared += 1,
            }
        }
        // Focus: the focused widget's node and every ancestor.
        if let Some(f) = focused {
            for i in 0..self.len {
                if self.nodes[i].widget == Some(f) {
                    self.nodes[i].focused = true;
                    let mut at = Some(i as u32);
                    while let Some(a) = at {
                        let n = &mut self.nodes[a as usize];
                        n.focus_in = true;
                        at = n.parent;
                    }
                }
            }
        }
        // Visibility: the first `depth_limit` levels, and below that the children of a
        // shown node the pointer is in or focus is under.
        for i in 0..self.len {
            let (head, tail) = self.nodes.split_at_mut(i);
            let n = &mut tail[0];
            n.visible = n.rect.is_positive()
                && (n.depth <= self.depth_limit
                    || n.parent.is_some_and(|p| {
                        let pn = &head[p as usize];
                        pn.visible && (pn.focus_in || pointer.is_some_and(|q| pn.rect.contains(q)))
                    }));
        }
        // Contains: parent → child.
        for i in 0..self.len {
            if let Some(p) = self.nodes[i].parent {
                self.edges_contains.push((p, i as u32));
            }
        }
        // Next: siblings in rank order, `?` excluded (it has no place in the order).
        self.sort_buf.clear();
        for (i, n) in self.nodes[..self.len].iter().enumerate() {
            if !matches!(n.step, Step::Undeclared(_)) {
                self.sort_buf.push((n.parent.map_or(0, |p| p + 1), n.step.rank(), i as u32));
            }
        }
        self.sort_buf.sort_unstable();
        for w in self.sort_buf.windows(2) {
            if w[0].0 == w[1].0 {
                self.edges_next.push((w[0].2, w[1].2));
            }
        }
        // Spatial: the arrow-key neighbour (right, down) among shown siblings. Shown
        // nodes only — a pane's thousands of hidden atoms would make this quadratic.
        if self.mode.shows_all() {
            for i in 0..self.len {
                let n = &self.nodes[i];
                if !n.visible {
                    continue;
                }
                self.rect_buf.clear();
                self.idx_buf.clear();
                for (j, m) in self.nodes[..self.len].iter().enumerate() {
                    if j != i && m.visible && m.parent == n.parent {
                        self.rect_buf.push(m.rect);
                        self.idx_buf.push(j as u32);
                    }
                }
                for dir in [Dir4::Right, Dir4::Down] {
                    if let Some(k) = nearest_in_direction(n.rect, &self.rect_buf, dir) {
                        self.edges_spatial.push((i as u32, self.idx_buf[k]));
                    }
                }
            }
        }
    }

    /// Place every shown node's chip (`size_of(node)` gives the chip size). Anchored at
    /// the node's top-left; a chip that collides with an earlier one is pushed down and
    /// right, one pass in draw order, so the layout is deterministic.
    pub fn place_chips(&mut self, mut size_of: impl FnMut(&NavNode) -> egui::Vec2) {
        self.rect_buf.clear();
        for i in 0..self.len {
            let n = &self.nodes[i];
            if !n.visible {
                self.nodes[i].chip = Rect::NOTHING;
                continue;
            }
            let size = size_of(n);
            let mut chip = Rect::from_min_size(n.rect.left_top() + vec2(1.0, 1.0), size);
            for prev in &self.rect_buf {
                if chip.intersects(*prev) {
                    chip = Rect::from_min_size(pos2(chip.left() + 4.0, prev.bottom() + 1.0), size);
                }
            }
            self.rect_buf.push(chip);
            self.nodes[i].chip = chip;
        }
    }

    /// The chip rect placed for node `i` this frame (`Rect::NOTHING` when hidden).
    pub fn chip(&self, i: usize) -> Rect {
        self.nodes.get(i).map_or(Rect::NOTHING, |n| n.chip)
    }

    /// **The whole graph as data** — ids, numbers, kinds, rects, edges. The test
    /// artefact, and what the future editor (design §5) reads.
    pub fn to_json(&self) -> serde_json::Value {
        let r = |r: Rect| {
            let q = |v: f32| (v * 10.0).round() / 10.0;
            serde_json::json!([q(r.min.x), q(r.min.y), q(r.max.x), q(r.max.y)])
        };
        let nodes: Vec<serde_json::Value> = self
            .nodes()
            .iter()
            .map(|n| {
                serde_json::json!({
                    "id": n.id,
                    "number": n.number,
                    "kind": n.kind.as_str(),
                    "label": n.label,
                    "depth": n.depth,
                    "step": n.step.as_str(),
                    "parent": n.parent,
                    "rect": r(n.rect),
                    "visible": n.visible,
                    "focusable": n.widget.is_some(),
                    "focus_in": n.focus_in,
                    "focused": n.focused,
                    "harvested": n.harvested,
                })
            })
            .collect();
        let pairs = |v: &[(u32, u32)]| v.iter().map(|(a, b)| serde_json::json!([a, b])).collect::<Vec<_>>();
        serde_json::json!({
            "mode": self.mode.as_str(),
            "depth_limit": self.depth_limit,
            "declared_order": !self.order.is_empty(),
            "count": self.len,
            "guessed": self.guessed,
            "undeclared": self.undeclared,
            "selected": if self.selected.is_empty() { serde_json::Value::Null } else { self.selected.clone().into() },
            "chord": if self.chord_on { serde_json::Value::from(self.chord.clone()) } else { serde_json::Value::Null },
            "nodes": nodes,
            "edges": {
                "contains": pairs(&self.edges_contains),
                "next": pairs(&self.edges_next),
                "spatial": pairs(&self.edges_spatial),
            },
        })
    }
}

fn lookup(rank: &IdMap<u32>, wild: &IdMap<u32>, parent: Id, local: &str, wild_used: &mut bool, draw_rank: u32) -> Step {
    if let Some(&r) = rank.get(&parent.with(local)) {
        return Step::Declared(r);
    }
    if let Some(&r) = wild.get(&parent)
        && !*wild_used
    {
        *wild_used = true;
        return Step::Declared(r);
    }
    Step::Undeclared(draw_rank)
}

/// Append a key with the id separator (`.`) and the list separator (newline) replaced,
/// so a key can never forge an extra path segment.
fn push_key(out: &mut String, key: &str) {
    for c in key.chars() {
        out.push(match c {
            '.' => '_',
            '\n' | '\r' => ' ',
            c => c,
        });
    }
}

fn sanitize_from(s: &mut String, start: usize) {
    if s[start..].contains(['.', '\n', '\r']) {
        // Rare (a Debug key with a dot, e.g. a float); rebuild the tail once.
        let tail: String = s[start..].to_string();
        s.truncate(start);
        push_key(s, &tail);
    }
}

// ── context API ───────────────────────────────────────────────────────────────────

fn gate_open() -> bool {
    crate::devid::enabled()
}

fn fast_off() -> bool {
    COLLECTING.load(Ordering::Relaxed) == 0 || !gate_open()
}

fn with_mut<R>(ctx: &Context, f: impl FnOnce(&mut NavGraph) -> R) -> R {
    ctx.data_mut(|d| f(d.get_temp_mut_or_default::<NavGraph>(Id::new(GRAPH_ID))))
}

/// Read this context's graph (the last finished frame, when called between frames).
pub fn with<R>(ctx: &Context, f: impl FnOnce(&NavGraph) -> R) -> R {
    with_mut(ctx, |g| f(g))
}

/// Is this context collecting right now? A host that has to build a key (a `format!`)
/// asks this first.
pub fn collecting(ctx: &Context) -> bool {
    !fast_off() && with_mut(ctx, |g| g.collect)
}

struct NavPlugin;

impl egui::Plugin for NavPlugin {
    fn debug_name(&self) -> &'static str {
        "facett-navgraph"
    }
    fn on_begin_pass(&mut self, ui: &mut Ui) {
        begin_pass(ui.ctx());
    }
    fn on_end_pass(&mut self, ui: &mut Ui) {
        end_pass(ui.ctx());
    }
}

/// **Install the navgraph on a context** (idempotent). A no-op unless dev mode is on.
/// [`crate::devid::badge`] calls this, so every deck host gets it without a line of
/// code; a host with no deck calls it once. Reads `FACETT_NAVGRAPH` for the start mode.
pub fn install(ctx: &Context) {
    if !gate_open() {
        return;
    }
    let first = with_mut(ctx, |g| {
        let first = !g.installed;
        if first {
            g.installed = true;
            if let Some(m) = std::env::var("FACETT_NAVGRAPH").ok().as_deref().and_then(NavMode::parse) {
                g.mode = m;
            }
        }
        first
    });
    if first {
        ctx.add_plugin(NavPlugin);
        // The plugin runs from the NEXT pass; ask for it.
        ctx.request_repaint();
    }
}

/// Set the overlay mode (installs the navgraph).
pub fn set_mode(ctx: &Context, mode: NavMode) {
    install(ctx);
    with_mut(ctx, |g| g.mode = mode);
    // A canvas with nothing animating paints only on input, so without this the
    // overlay would wait for the next pointer event (measured: an `osm2d` canvas in the
    // browser had drawn once and never collected).
    ctx.request_repaint();
}
pub fn mode(ctx: &Context) -> NavMode {
    with_mut(ctx, |g| g.mode)
}
/// Hand in the declared order (installs the navgraph). Cheap when unchanged.
pub fn set_order(ctx: &Context, order: NavOrder) {
    install(ctx);
    with_mut(ctx, |g| g.set_order(order));
}
/// Is an order declared? A host that builds its order lazily asks this first.
pub fn has_order(ctx: &Context) -> bool {
    with_mut(ctx, |g| !g.order.is_empty())
}
/// Levels shown without hovering (default [`DEFAULT_DEPTH`]).
pub fn set_depth_limit(ctx: &Context, n: u8) {
    with_mut(ctx, |g| g.depth_limit = n.max(1));
}
/// Keep collecting while the overlay is off — for a host or test that reads
/// [`to_json`] without showing anything.
pub fn keep_collecting(ctx: &Context, on: bool) {
    install(ctx);
    with_mut(ctx, |g| g.keep = on);
}
/// The last finished frame's graph as JSON ([`NavGraph::to_json`]).
pub fn to_json(ctx: &Context) -> serde_json::Value {
    with(ctx, NavGraph::to_json)
}

/// A scope token from [`begin`], closed by [`end`].
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Token(u32);

/// Open a parent node under the current scope. `None` when not collecting.
pub fn begin(ui: &Ui, key: &str, kind: NavKind, label: &str) -> Option<Token> {
    if fast_off() {
        return None;
    }
    let rect = ui.max_rect();
    with_mut(ui.ctx(), |g| g.open(key, kind, label, rect)).map(Token)
}
/// Close a scope from [`begin`] with the rect it finally occupied.
pub fn end(ui: &Ui, token: Option<Token>, rect: Rect) {
    if let Some(Token(t)) = token {
        with_mut(ui.ctx(), |g| g.close(t, rect));
    }
}
/// Declare that the open scope's children, drawn in order, are in declared order.
pub fn declare_draw_order(ui: &Ui, token: Option<Token>) {
    if let Some(Token(t)) = token {
        with_mut(ui.ctx(), |g| g.declare_draw_order(t));
    }
}
/// **A component declares its own atoms** (navgraph-design §9 "Left", phase 3): the
/// children of the scope the component is drawn in — its pane — are in declared order when
/// drawn in order. For a component whose painted atoms follow its DATA order (graph nodes
/// in scene order, heatmap cells row-major, a pipeline's stages), that order is the
/// declaration, and the atoms stop reading `~`. Needs no token and touches no layout, so
/// a component calls it once in its `view` without knowing who hosts it (a `FacetDeck`
/// pane, a scene slot, a wrapped canvas). Outside dev mode it is one atomic load.
pub fn declare_own_draw_order(ui: &Ui) {
    if fast_off() {
        return;
    }
    with_mut(ui.ctx(), |g| g.declare_current_draw_order());
}

/// Declare the open scope's children for this frame, by key, in order.
pub fn declare_children<'a>(ui: &Ui, token: Option<Token>, keys: impl IntoIterator<Item = &'a str>) {
    if let Some(Token(t)) = token {
        with_mut(ui.ctx(), |g| g.declare_children(t, keys));
    }
}

/// **A parent around a closure.** Always wraps `add` in `ui.scope`, in dev mode or not,
/// so turning the overlay on never changes layout.
pub fn scope<R>(ui: &mut Ui, key: &str, kind: NavKind, label: &str, add: impl FnOnce(&mut Ui) -> R) -> R {
    let token = begin(ui, key, kind, label);
    let inner = ui.scope(add);
    end(ui, token, inner.response.rect);
    inner.inner
}

/// [`scope`] whose children's draw order is their declared order (a tab strip).
pub fn scope_ordered<R>(ui: &mut Ui, key: &str, kind: NavKind, label: &str, add: impl FnOnce(&mut Ui) -> R) -> R {
    let token = begin(ui, key, kind, label);
    declare_draw_order(ui, token);
    let inner = ui.scope(add);
    end(ui, token, inner.response.rect);
    inner.inner
}

/// **Register a plain egui widget** (a `Button`, a `TextEdit`) as a `Field` of the
/// current scope. The response's id is what `Ctrl+G <number>` focuses.
pub fn field(ui: &Ui, key: &str, response: &Response) {
    if fast_off() {
        return;
    }
    let (rect, id) = (response.rect, response.id);
    with_mut(ui.ctx(), |g| {
        g.leaf(key, NavKind::Field, key, rect, Some(id));
    });
}

/// The [`crate::a11y::node`] hook: an FC-4 atom becomes a `Field`.
pub(crate) fn atom(ui: &Ui, key: &dyn std::fmt::Debug, label: &str, response: &Response) {
    if fast_off() {
        return;
    }
    let (rect, id) = (response.rect, response.id);
    with_mut(ui.ctx(), |g| {
        g.leaf_debug(key, label, rect, Some(id));
    });
}

/// The [`crate::devid::badge`] hook: a deck pane. Merges into the node a host scope
/// opened under the same key, so the pane's children stay under it.
pub(crate) fn pane(ui: &Ui, key: &str, label: &str, rect: Rect) {
    if fast_off() {
        return;
    }
    with_mut(ui.ctx(), |g| {
        g.leaf(key, NavKind::Pane, label, rect, None);
    });
}

/// Register a [`FocusGroup`](crate::focus::FocusGroup): a `Group` whose declared
/// children are its fields, in order.
pub fn focus_group(ui: &Ui, group: &crate::focus::FocusGroup) {
    if fast_off() {
        return;
    }
    let rect = group.fields.iter().fold(Rect::NOTHING, |a, f| a.union(f.rect));
    with_mut(ui.ctx(), |g| {
        let Some(t) = g.open(&group.id, NavKind::Group, &group.id, rect) else { return };
        g.declare_children(t, group.fields.iter().map(|f| f.id.as_str()));
        for f in &group.fields {
            g.leaf(&f.id, NavKind::Field, &f.id, f.rect, None);
        }
        g.close(t, rect);
    });
}

/// **The browser half** (wasm only). A web host calls [`web::install`] once after the
/// runner starts.
#[cfg(target_arch = "wasm32")]
pub mod web {
    use wasm_bindgen::JsCast as _;
    use wasm_bindgen::closure::Closure;

    /// `?nav=labels|next|all` (or `#…&nav=…`) in the page URL, when present.
    pub fn mode_from_url() -> Option<super::NavMode> {
        let loc = web_sys::window()?.location();
        let s = format!("{}&{}", loc.search().ok()?, loc.hash().ok().unwrap_or_default());
        s.split(['?', '&', '#'])
            .find_map(|kv| kv.strip_prefix("nav="))
            .and_then(super::NavMode::parse)
    }

    /// Stop the browser's own Ctrl+G (Chrome: find next, which opens the find bar and
    /// takes the digits of the chord). eframe's web runner prevents the default only
    /// for Ctrl+O/P/S/comma, so the chord could not be typed in a browser without this.
    /// Capture phase on `window`, so it runs before the page sees the key. Idempotent.
    pub fn prevent_browser_ctrl_g() {
        use std::sync::atomic::{AtomicBool, Ordering};
        static DONE: AtomicBool = AtomicBool::new(false);
        if DONE.swap(true, Ordering::Relaxed) {
            return;
        }
        let Some(w) = web_sys::window() else { return };
        let cb = Closure::<dyn FnMut(web_sys::KeyboardEvent)>::new(|e: web_sys::KeyboardEvent| {
            if (e.ctrl_key() || e.meta_key()) && e.key().eq_ignore_ascii_case("g") {
                e.prevent_default();
            }
        });
        let _ = w.add_event_listener_with_callback_and_bool("keydown", cb.as_ref().unchecked_ref(), true);
        cb.forget();
    }

    /// Both of the above, plus [`super::install`] on `ctx` with the URL's mode.
    pub fn install(ctx: &egui::Context) {
        prevent_browser_ctrl_g();
        super::install(ctx);
        if let Some(m) = mode_from_url() {
            super::set_mode(ctx, m);
        }
    }
}

// ── the pass hooks ────────────────────────────────────────────────────────────────

fn begin_pass(ctx: &Context) {
    if !gate_open() {
        return;
    }
    let (mut chord_on, mut chord) = with_mut(ctx, |g| (g.chord_on, std::mem::take(&mut g.chord)));
    let mut cycle = false;
    let mut enter = false;
    ctx.input_mut(|i| {
        if i.consume_key(Modifiers::CTRL | Modifiers::SHIFT, Key::G) {
            cycle = true;
        } else if i.consume_key(Modifiers::CTRL, Key::G) {
            chord_on = true;
            chord.clear();
        }
        if !chord_on {
            return;
        }
        i.events.retain(|e| match e {
            egui::Event::Key { key, pressed: true, modifiers, .. } if !modifiers.ctrl && !modifiers.command => {
                match key {
                    Key::Enter => enter = true,
                    Key::Escape => {
                        chord_on = false;
                        chord.clear();
                    }
                    Key::Backspace => {
                        chord.pop();
                    }
                    Key::Period => chord.push('.'),
                    k => match digit(*k) {
                        Some(d) => chord.push(d),
                        None => return true,
                    },
                }
                false
            }
            egui::Event::Text(t) => !t.chars().all(|c| c.is_ascii_digit() || c == '.'),
            _ => true,
        });
    });
    let mut focus: Option<Id> = None;
    with_mut(ctx, |g| {
        if cycle {
            g.mode = g.mode.next();
        }
        if enter {
            // Resolve against the graph as it stands: the frame the human looked at.
            g.selected.clear();
            if let Some(i) = g.nodes().iter().position(|n| n.number_is(&chord)) {
                g.selected.push_str(&g.nodes[i].id);
                // A node that is not a widget focuses its first focusable descendant.
                let n = &g.nodes[i];
                focus = n.widget.or_else(|| {
                    let p = n.id.as_str();
                    g.nodes()[i + 1..]
                        .iter()
                        .find(|m| m.widget.is_some() && m.id.len() > p.len() && m.id.starts_with(p) && m.id.as_bytes()[p.len()] == b'.')
                        .and_then(|m| m.widget)
                });
            }
            chord_on = false;
            chord.clear();
        }
        g.chord = chord;
        g.chord_on = chord_on;
        g.clear();
        let want = g.mode != NavMode::Off || g.chord_on || g.keep;
        if want != g.counted {
            if want {
                COLLECTING.fetch_add(1, Ordering::Relaxed);
            } else {
                COLLECTING.fetch_sub(1, Ordering::Relaxed);
            }
            g.counted = want;
        }
        g.collect = want;
    });
    if let Some(id) = focus {
        ctx.memory_mut(|m| m.request_focus(id));
    }
    // The harvest reads labels off the AccessKit nodes egui writes, and a robot reads
    // the chips off the same tree, so dev mode with the overlay on turns AccessKit on
    // (from the next pass; egui decides it at the start of a pass).
    if collect_now(ctx) {
        ctx.enable_accesskit();
    }
}

fn collect_now(ctx: &Context) -> bool {
    with_mut(ctx, |g| g.collect)
}

/// **The navgraph on any egui app — one call.** Installs the overlay (dev mode only):
/// `Ctrl+Shift+G` cycles it, `Ctrl+G <number> Enter` focuses. Every navigable widget is
/// numbered from egui's own per-pass record; facett registrations and a declared
/// [`NavOrder`] refine that tree. Idempotent, so it can sit in the frame loop.
pub fn overlay(ctx: &Context) {
    install(ctx);
}

fn digit(k: Key) -> Option<char> {
    Some(match k {
        Key::Num0 => '0',
        Key::Num1 => '1',
        Key::Num2 => '2',
        Key::Num3 => '3',
        Key::Num4 => '4',
        Key::Num5 => '5',
        Key::Num6 => '6',
        Key::Num7 => '7',
        Key::Num8 => '8',
        Key::Num9 => '9',
        _ => return None,
    })
}

fn end_pass(ctx: &Context) {
    if !gate_open() {
        return;
    }
    // Take the graph out of memory so painting (which locks the context) never runs
    // inside the memory lock; `Default` allocates nothing, and it goes back after.
    let mut g = with_mut(ctx, std::mem::take);
    if g.collect {
        let focused = ctx.memory(|m| m.focused());
        let pointer = ctx.pointer_hover_pos();
        // Ordinary egui: every navigable widget facett did not register, from egui's
        // own per-pass record (`harvest.rs`).
        g.harvest(ctx);
        g.finish(focused, pointer);
        if g.mode != NavMode::Off || g.chord_on {
            paint(ctx, &mut g, pointer);
        }
    }
    with_mut(ctx, |slot| *slot = g);
}

fn paint(ctx: &Context, g: &mut NavGraph, pointer: Option<Pos2>) {
    let tokens = NavOverlayTokens::from_palette(&crate::look::published_palette(ctx));
    let painter = ctx.layer_painter(LayerId::new(Order::Debug, Id::new(GRAPH_ID)));
    let font = FontId::monospace(CHIP_FONT);

    if g.mode != NavMode::Off {
        // Chip sizes from the number's width; monospace, so one glyph advance times the
        // char count measures it without laying out a galley.
        let adv = ctx.fonts_mut(|f| f.glyph_width(&font, '0'));
        let h = ctx.fonts_mut(|f| f.row_height(&font));
        g.place_chips(|n| vec2(adv * n.number.chars().count() as f32 + 6.0, h + 2.0));

        // Edges under the chips. Crisp hairlines in every effects policy (the device
        // rule): no glow in a debug overlay.
        let mode = g.mode;
        if mode.shows_all() {
            for k in 0..g.edges_contains.len() {
                let (a, b) = g.edges_contains[k];
                let (na, nb) = (&g.nodes[a as usize], &g.nodes[b as usize]);
                if na.visible && nb.visible {
                    let c = tokens.contains_at_depth(nb.depth);
                    spline(&painter, &mut g.pts, na.chip.center(), nb.chip.left_center(), 0.15, c, 1.0, false);
                }
            }
        }
        if mode.shows_next() {
            for k in 0..g.edges_next.len() {
                let (a, b) = g.edges_next[k];
                let (na, nb) = (&g.nodes[a as usize], &g.nodes[b as usize]);
                if na.visible && nb.visible {
                    let (p0, p3) = (na.chip.center(), nb.chip.center());
                    spline(&painter, &mut g.pts, p0, p3, 0.25, tokens.edge_next, 1.5, false);
                    arrowhead(&painter, &g.pts, tokens.edge_next);
                }
            }
        }
        if mode.shows_all() {
            for k in 0..g.edges_spatial.len() {
                let (a, b) = g.edges_spatial[k];
                let (na, nb) = (&g.nodes[a as usize], &g.nodes[b as usize]);
                spline(&painter, &mut g.pts, na.chip.center(), nb.chip.center(), 0.0, tokens.edge_spatial, 1.0, true);
            }
        }

        // Chips + one AccessKit node each.
        let mut hovered: Option<usize> = None;
        for i in 0..g.len {
            let n = &g.nodes[i];
            if !n.visible {
                continue;
            }
            let fg = if n.number.contains('?') {
                tokens.chip_undeclared
            } else if n.number.contains('~') {
                tokens.chip_guessed
            } else {
                tokens.chip_declared
            };
            let focused = n.focused || g.selected == n.id;
            painter.rect_filled(n.chip, 2.0, tokens.chip_plate);
            if focused {
                painter.rect_stroke(n.chip, 2.0, Stroke::new(1.0, tokens.chip_focused), egui::StrokeKind::Outside);
            }
            painter.text(n.chip.center(), egui::Align2::CENTER_CENTER, &n.number, font.clone(), fg);
            if pointer.is_some_and(|p| n.chip.contains(p)) {
                hovered = Some(i);
            }
            g.text.clear();
            let _ = write!(g.text, "{NAV_ATOM} {} {}", n.number, n.short());
            // A label that says more than the id (a harvested widget's text) rides along.
            if !n.label.is_empty() && n.label != n.local() {
                let _ = write!(g.text, " · {}", n.label);
            }
            if focused {
                g.text.push(' ');
                g.text.push_str(FOCUSED_MARK);
            }
            let chip = n.chip;
            let label = g.text.as_str();
            ctx.accesskit_node_builder(Id::new(GRAPH_ID).with(n.hash), |node| {
                // AccessKit keeps a `Label`'s text in its VALUE (a consumer reads it from
                // there), so the text goes in both places.
                node.set_role(egui::accesskit::Role::Label);
                node.set_label(label);
                node.set_value(label);
                node.set_bounds(egui::accesskit::Rect {
                    x0: chip.min.x as f64,
                    y0: chip.min.y as f64,
                    x1: chip.max.x as f64,
                    y1: chip.max.y as f64,
                });
            });
        }
        // The hovered chip grows to `number · short id` (design §3).
        if let Some(i) = hovered {
            let n = &g.nodes[i];
            g.text.clear();
            let what = if n.label.is_empty() { n.short() } else { n.label.as_str() };
            let _ = write!(g.text, "{} · {}", n.number, what);
            let w = adv * g.text.chars().count() as f32 + 6.0;
            let r = Rect::from_min_size(n.chip.min, vec2(w, n.chip.height()));
            painter.rect_filled(r, 2.0, tokens.chip_plate);
            painter.rect_stroke(r, 2.0, Stroke::new(1.0, tokens.chip_focused), egui::StrokeKind::Outside);
            painter.text(r.center(), egui::Align2::CENTER_CENTER, &g.text, font.clone(), tokens.chip_declared);
        }
    }

    // The chord being typed, bottom-left, so a human sees what Enter will focus.
    if g.chord_on {
        g.text.clear();
        let _ = write!(g.text, "Ctrl+G {}_", g.chord);
        let screen = ctx.content_rect();
        let galley = painter.layout_no_wrap(g.text.clone(), FontId::monospace(12.0), tokens.chip_declared);
        let pos = screen.left_bottom() + vec2(8.0, -8.0 - galley.size().y);
        let r = Rect::from_min_size(pos, galley.size()).expand(4.0);
        painter.rect_filled(r, 3.0, tokens.chip_plate);
        painter.rect_stroke(r, 3.0, Stroke::new(1.0, tokens.chip_focused), egui::StrokeKind::Outside);
        painter.galley(pos, galley, tokens.chip_declared);
    }
}

#[allow(clippy::too_many_arguments)]
fn spline(painter: &egui::Painter, pts: &mut Vec<Pos2>, p0: Pos2, p3: Pos2, curvature: f32, color: Color32, width: f32, dashed: bool) {
    if (p3 - p0).length_sq() < 1.0 {
        pts.clear();
        return;
    }
    spline_points_into(pts, p0, p3, curvature, SPLINE_SAMPLES);
    let stroke = Stroke::new(width, color);
    for (k, w) in pts.windows(2).enumerate() {
        if dashed && k % 2 == 1 {
            continue;
        }
        painter.line_segment([w[0], w[1]], stroke);
    }
}

fn arrowhead(painter: &egui::Painter, pts: &[Pos2], color: Color32) {
    if pts.len() < 2 {
        return;
    }
    let tip = point_at_frac(pts, 0.9);
    let back = point_at_frac(pts, 0.84);
    let d = tip - back;
    if d.length_sq() < 1e-6 {
        return;
    }
    let d = d.normalized();
    let perp = vec2(-d.y, d.x);
    let stroke = Stroke::new(1.5, color);
    painter.line_segment([tip, tip - d * 6.0 + perp * 3.5], stroke);
    painter.line_segment([tip, tip - d * 6.0 - perp * 3.5], stroke);
}

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

    fn r(x: f32, y: f32, w: f32, h: f32) -> Rect {
        Rect::from_min_size(pos2(x, y), vec2(w, h))
    }

    /// App → two surfaces → fields.
    fn build(g: &mut NavGraph) {
        g.clear();
        let app = g.open("korp", NavKind::App, "korp", r(0.0, 0.0, 800.0, 600.0)).unwrap();
        let a = g.open("explore", NavKind::Surface, "Explore", r(0.0, 0.0, 400.0, 600.0)).unwrap();
        g.leaf("name", NavKind::Field, "name", r(10.0, 10.0, 100.0, 20.0), Some(Id::new("w-name")));
        g.leaf("date", NavKind::Field, "date", r(10.0, 40.0, 100.0, 20.0), Some(Id::new("w-date")));
        g.close(a, Rect::NOTHING);
        let b = g.open("build", NavKind::Surface, "Build", r(400.0, 0.0, 400.0, 600.0)).unwrap();
        g.leaf("run", NavKind::Field, "run", r(410.0, 10.0, 60.0, 20.0), Some(Id::new("w-run")));
        g.close(b, Rect::NOTHING);
        g.close(app, Rect::NOTHING);
    }

    fn numbers(g: &NavGraph) -> Vec<(String, String)> {
        g.nodes().iter().map(|n| (n.id.clone(), n.number.clone())).collect()
    }

    #[test]
    fn with_nothing_declared_every_step_is_a_marked_guess() {
        let mut g = NavGraph::new();
        build(&mut g);
        g.finish(None, None);
        assert_eq!(
            numbers(&g),
            [
                ("korp", "~1"),
                ("korp.explore", "~1.~1"),
                ("korp.explore.name", "~1.~1.~1"),
                ("korp.explore.date", "~1.~1.~2"),
                ("korp.build", "~1.~2"),
                ("korp.build.run", "~1.~2.~1"),
            ]
            .map(|(a, b)| (a.to_string(), b.to_string()))
        );
        assert_eq!(g.not_declared().count(), 6);
    }

    #[test]
    fn declared_order_wins_and_a_missing_child_is_a_question_mark() {
        let mut g = NavGraph::new();
        g.set_order(
            NavOrder::new()
                .roots(["korp"])
                // Declared BACKWARDS relative to the draw order: the declaration wins.
                .children("korp", ["build", "explore"])
                // `date` is not listed: it gets `?` plus its draw rank.
                .children("korp.explore", ["name"])
                .children("korp.build", ["run"]),
        );
        build(&mut g);
        g.finish(None, None);
        let n = |id: &str| g.find_id(id).unwrap().number.clone();
        assert_eq!(n("korp"), "1");
        assert_eq!(n("korp.build"), "1.1");
        assert_eq!(n("korp.explore"), "1.2");
        assert_eq!(n("korp.explore.name"), "1.2.1");
        assert_eq!(n("korp.explore.date"), "1.2.?2");
        assert_eq!(n("korp.build.run"), "1.1.1");
        let bad: Vec<&str> = g.not_declared().map(|n| n.id.as_str()).collect();
        assert_eq!(bad, ["korp.explore.date"], "only the unlisted child is not declared");
        // The chord matches with the marks ignored.
        assert_eq!(g.find_number("1.2.2").unwrap().id, "korp.explore.date");
        assert_eq!(g.find_number("1.1").unwrap().id, "korp.build");
    }

    #[test]
    fn the_wildcard_slot_takes_one_unnamed_child_and_draw_order_scopes_declare() {
        let mut g = NavGraph::new();
        g.set_order(NavOrder::new().roots(["app"]).children("app", ["tabs", "*"]));
        for _ in 0..2 {
            g.clear();
            let app = g.open("app", NavKind::App, "", r(0.0, 0.0, 10.0, 10.0)).unwrap();
            let tabs = g.open("tabs", NavKind::Group, "", r(0.0, 0.0, 10.0, 10.0)).unwrap();
            g.declare_draw_order(tabs);
            for t in ["Map", "Graph", "Grid"] {
                g.leaf(t, NavKind::Field, t, r(0.0, 0.0, 1.0, 1.0), None);
            }
            g.close(tabs, Rect::NOTHING);
            g.leaf("map/2-D map", NavKind::Pane, "", r(0.0, 0.0, 5.0, 5.0), None);
            g.leaf("extra", NavKind::Pane, "", r(0.0, 0.0, 5.0, 5.0), None);
            g.close(app, Rect::NOTHING);
            g.finish(None, None);
            let n = |id: &str| g.find_id(id).unwrap().number.clone();
            assert_eq!(n("app.tabs.Graph"), "1.1.2");
            assert_eq!(n("app.map/2-D map"), "1.2", "the wildcard slot (every frame, not only the first)");
            assert_eq!(n("app.extra"), "1.?3", "only ONE child takes the wildcard");
        }
    }

    /// A component declares its own atoms without a token: the innermost open scope (its
    /// pane) takes draw order as the declaration.
    #[test]
    fn a_component_declares_its_own_atoms_in_draw_order() {
        let mut g = NavGraph::new();
        g.clear();
        let pane = g.open("pane", NavKind::Pane, "", r(0.0, 0.0, 10.0, 10.0)).unwrap();
        g.declare_current_draw_order();
        for k in ["b", "a", "c"] {
            g.leaf(k, NavKind::Field, k, r(0.0, 0.0, 1.0, 1.0), None);
        }
        g.close(pane, Rect::NOTHING);
        g.declare_current_draw_order(); // nothing open: a no-op, never a panic
        g.finish(None, None);
        assert_eq!(g.find_id("pane.a").unwrap().number, "~1.2", "declared in draw order, not guessed");
        assert!(g.find_id("pane.c").unwrap().step.is_declared());
    }

    /// The per-frame declaration (`declare_children`, what `facett_app::scene` hands in
    /// for a tab set) honours the wildcard too, and a harvested widget never takes it.
    #[test]
    fn a_per_frame_declaration_has_a_wildcard_slot_that_skips_harvested_widgets() {
        let mut g = NavGraph::new();
        for _ in 0..2 {
            g.clear();
            let set = g.open("work", NavKind::Group, "", r(0.0, 0.0, 10.0, 10.0)).unwrap();
            g.declare_children(set, ["tabs", WILDCARD]);
            let chrome = g.leaf("w1", NavKind::Field, "min", r(0.0, 0.0, 1.0, 1.0), None).unwrap();
            g.nodes[chrome as usize].harvested = true;
            g.leaf("tabs", NavKind::Group, "", r(0.0, 0.0, 10.0, 1.0), None);
            g.leaf("cases", NavKind::Pane, "", r(0.0, 1.0, 10.0, 10.0), None);
            g.leaf("stray", NavKind::Pane, "", r(0.0, 1.0, 10.0, 10.0), None);
            g.close(set, Rect::NOTHING);
            g.finish(None, None);
            let n = |id: &str| g.find_id(id).unwrap().number.clone();
            assert_eq!(n("work.tabs"), "~1.1");
            assert_eq!(n("work.cases"), "~1.2", "the active tab takes the wildcard, not the chrome button");
            assert!(n("work.w1").contains('?'), "the harvested chrome is undeclared: {}", n("work.w1"));
            assert!(n("work.stray").contains('?'), "one child only: {}", n("work.stray"));
        }
    }

    #[test]
    fn a_second_registration_merges_and_keys_cannot_forge_segments() {
        let mut g = NavGraph::new();
        g.clear();
        let p = g.open("deck", NavKind::Surface, "", r(0.0, 0.0, 10.0, 10.0)).unwrap();
        let a = g.open("pane", NavKind::Pane, "", r(0.0, 0.0, 5.0, 5.0)).unwrap();
        g.leaf("x", NavKind::Field, "", r(0.0, 0.0, 1.0, 1.0), None);
        g.close(a, r(0.0, 0.0, 5.0, 5.0));
        // The badge names the same pane after it drew.
        let again = g.leaf("pane", NavKind::Pane, "Pane", r(0.0, 0.0, 6.0, 6.0), None).unwrap();
        assert_eq!(again, a, "same full id, same node");
        g.leaf("v0.1", NavKind::Field, "", r(0.0, 0.0, 1.0, 1.0), None);
        assert_eq!(g.len(), 4);
        assert!(g.find_id("deck.v0_1").is_some(), "a dot in a key is not a path separator");
        // A Debug key (the a11y hook) loses its quotes.
        g.leaf_debug(&"node-7", "n7", r(0.0, 0.0, 1.0, 1.0), None);
        assert!(g.find_id("deck.node-7").is_some());
        g.leaf_debug(&1.5_f32, "f", r(0.0, 0.0, 1.0, 1.0), None);
        assert!(g.find_id("deck.1_5").is_some(), "a Debug key with a dot is sanitised");
        g.close(p, Rect::NOTHING);
    }

    #[test]
    fn the_arena_reuses_its_capacity_frame_after_frame() {
        let mut g = NavGraph::new();
        build(&mut g);
        g.finish(None, None);
        let cap = g.nodes.capacity();
        for _ in 0..10 {
            build(&mut g);
            g.finish(None, None);
        }
        assert_eq!(g.nodes.capacity(), cap, "the node vec did not grow");
        assert_eq!(g.nodes.len(), 6, "slots are reused, not appended");
    }

    #[test]
    fn depth_limit_hides_deep_levels_until_hover_or_focus() {
        let mut g = NavGraph::new();
        g.depth_limit = 2;
        build(&mut g);
        g.finish(None, None);
        let vis = |g: &NavGraph, id: &str| g.find_id(id).unwrap().visible;
        assert!(vis(&g, "korp.explore"));
        assert!(!vis(&g, "korp.explore.name"), "level 3 is below the limit");
        // Pointer in the Explore surface → its fields show; Build's do not.
        build(&mut g);
        g.finish(None, Some(pos2(50.0, 50.0)));
        assert!(vis(&g, "korp.explore.name"));
        assert!(!vis(&g, "korp.build.run"));
        // Focus inside Build → its fields show, and the chain is marked.
        build(&mut g);
        g.finish(Some(Id::new("w-run")), None);
        assert!(vis(&g, "korp.build.run"));
        assert!(g.find_id("korp.build.run").unwrap().focused);
        assert!(g.find_id("korp.build").unwrap().focus_in);
        assert!(!g.find_id("korp.build").unwrap().focused, "focused is the exact node only");
        assert!(!g.find_id("korp.explore").unwrap().focus_in);
    }

    #[test]
    fn next_edges_follow_rank_and_skip_the_undeclared() {
        let mut g = NavGraph::new();
        g.set_order(NavOrder::new().roots(["korp"]).children("korp", ["build", "explore"]).children("korp.explore", ["name"]));
        build(&mut g);
        g.finish(None, None);
        let id = |i: u32| g.nodes()[i as usize].id.as_str();
        let next: Vec<(&str, &str)> = g.edges_next().iter().map(|&(a, b)| (id(a), id(b))).collect();
        assert!(next.contains(&("korp.build", "korp.explore")), "declared order, not draw order: {next:?}");
        assert!(!next.iter().any(|(a, b)| *a == "korp.explore.date" || *b == "korp.explore.date"), "? has no place in the order");
        assert_eq!(g.edges_contains().len(), 5, "one contains edge per non-root");
    }

    #[test]
    fn colliding_chips_are_pushed_down_and_right_deterministically() {
        let mut g = NavGraph::new();
        g.clear();
        let p = g.open("a", NavKind::App, "", r(0.0, 0.0, 100.0, 100.0)).unwrap();
        // Same top-left as the parent: its chip would sit exactly on the parent's.
        g.leaf("b", NavKind::Surface, "", r(0.0, 0.0, 50.0, 50.0), None);
        g.close(p, Rect::NOTHING);
        g.finish(None, None);
        g.place_chips(|_| vec2(20.0, 12.0));
        let (a, b) = (g.chip(0), g.chip(1));
        assert!(!a.intersects(b), "{a:?} vs {b:?}");
        assert!(b.top() >= a.bottom() && b.left() > a.left(), "pushed down and right");
        let first = (a, b);
        g.place_chips(|_| vec2(20.0, 12.0));
        assert_eq!((g.chip(0), g.chip(1)), first, "same input, same layout");
    }

    #[test]
    fn spline_paths_between_chips_are_pure_and_end_on_the_anchors() {
        let (p0, p3) = (pos2(10.0, 10.0), pos2(200.0, 120.0));
        let mut a = Vec::new();
        let mut b = Vec::new();
        spline_points_into(&mut a, p0, p3, 0.25, SPLINE_SAMPLES);
        spline_points_into(&mut b, p0, p3, 0.25, SPLINE_SAMPLES);
        assert_eq!(a, b, "same rects, same path");
        assert_eq!(a, crate::edges::spline_points(p0, p3, 0.25, SPLINE_SAMPLES), "the buffered twin is the same path");
        assert!((a[0] - p0).length() < 1e-3 && (*a.last().unwrap() - p3).length() < 1e-3);
        let cap = a.capacity();
        spline_points_into(&mut a, p3, p0, 0.1, SPLINE_SAMPLES);
        assert_eq!(a.capacity(), cap, "the buffer is reused");
        // The next-edge arrowhead sits at 0.9 of the path, on the curve.
        let tip = point_at_frac(&a, 0.9);
        assert!(a.iter().any(|q| (*q - tip).length() < 20.0));
    }

    #[test]
    fn json_carries_numbers_kinds_rects_and_edges() {
        let mut g = NavGraph::new();
        g.set_order(NavOrder::new().roots(["korp"]).children("korp", ["explore", "build"]));
        build(&mut g);
        g.finish(None, None);
        let j = g.to_json();
        assert_eq!(j["count"], 6);
        assert_eq!(j["nodes"][1]["id"], "korp.explore");
        assert_eq!(j["nodes"][1]["number"], "1.1");
        assert_eq!(j["nodes"][1]["kind"], "surface");
        assert_eq!(j["nodes"][2]["step"], "guessed");
        assert_eq!(j["nodes"][2]["rect"], serde_json::json!([10.0, 10.0, 110.0, 30.0]));
        assert_eq!(j["edges"]["contains"].as_array().unwrap().len(), 5);
        assert!(j["declared_order"].as_bool().unwrap());
    }

    #[test]
    fn modes_cycle_and_parse() {
        let mut m = NavMode::Off;
        let seen: Vec<NavMode> = (0..4)
            .map(|_| {
                m = m.next();
                m
            })
            .collect();
        assert_eq!(seen, [NavMode::Labels, NavMode::LabelsNext, NavMode::All, NavMode::Off]);
        assert_eq!(NavMode::parse("next"), Some(NavMode::LabelsNext));
        assert_eq!(NavMode::parse("banana"), None);
        assert_eq!(NavOrder::new().roots(["a"]).get(""), Some(&["a".to_string()][..]));
    }
}