graph_explorer_style/

interner.rs

//! String ↔ u32 interning for the per-frame path.
//!
//! Node ids and label texts are interned ONCE, at scene-build time (per
//! navigation / arrival — never per frame). Everything downstream — Scene,
//! Frame, hit targets, screen positions, sim sync — is keyed by these dense
//! indices, which is what lets every per-frame structure be a Vec of Copy
//! elements refilled in place.
//!
//! Indices are **append-only and never reused** for the life of the session.
//! The animator correlates `from`/`to` scenes by index; reusing a dead node's
//! slot would alias its mid-flight animation state onto an unrelated new
//! node. The cost is index space growing with nodes-ever-seen rather than
//! currently-alive — accepted in the spec (a few hundred KB of slack at
//! tens-of-thousands scale).
//!
//! `NodeIndex` and `LabelId` are deliberately kept as bare `u32` aliases
//! rather than newtypes: the two index spaces are already separated by
//! receiver type (`Interner` vs `LabelInterner`), so a newtype would add
//! ceremony without adding safety, and consumers keep plain-integer
//! indexing idioms (`Vec` indexing, arithmetic, etc.) for free.

use std::collections::HashMap;

/// Dense index of an interned node id. Stable for the session.
pub type NodeIndex = u32;
/// Dense index of an interned label text. `EMPTY_LABEL` (0) is reserved for
/// the empty string, so "no label" is a plain compare, not an Option.
pub type LabelId = u32;
pub const EMPTY_LABEL: LabelId = 0;

/// What an interned id denotes — classified once, at intern time, replacing
/// the per-hit `starts_with("__")` string tests.
///
/// This preserves TWO distinct pre-existing behaviors that must not
/// collapse into one another:
///  - `graph-explorer-wasm`'s `node_screen_positions` excludes ANY id starting with
///    `"__"` from the projection API (see `crates/graph-explorer-wasm/src/lib.rs`).
///  - `graph-explorer-render`'s hit-test `pick` only special-cases `"__more"`,
///    `"__agg:"`-prefixed ids, and skips exactly `"__loading"` as
///    pick-inert; every other `"__"`-prefixed id is hit-tested as an
///    ordinary node.
///
/// `OtherSynthetic` exists to keep both behaviors intact under one
/// classification: it is synthetic for the screen-positions exclusion, but
/// `graph-explorer-wasm`'s `node_at` maps it to hit-test kind "node" (not skipped) —
/// only `Loading` is pick-inert.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum IdKind {
    Node,
    More,
    Aggregate,
    Loading,
    /// Any `"__"`-prefixed id that is not `"__more"`, `"__loading"`, or
    /// `"__agg:"`-prefixed (e.g. a near-miss like `"__agg"` with no colon,
    /// or an unrecognized `"__x"`). Synthetic for screen-position purposes
    /// (matches the old blanket `starts_with("__")` filter), but hit-testing
    /// treats it as an ordinary hittable node — `graph-explorer-wasm`'s `node_at`
    /// maps it to hit kind `"node"`, honoring this contract.
    OtherSynthetic,
}

impl IdKind {
    pub fn is_synthetic(self) -> bool { !matches!(self, IdKind::Node) }
    fn classify(id: &str) -> Self {
        if id == "__more" { IdKind::More }
        else if id == "__loading" { IdKind::Loading }
        else if id.starts_with("__agg:") { IdKind::Aggregate }
        else if id.starts_with("__") { IdKind::OtherSynthetic }
        else { IdKind::Node }
    }
}

/// Node-id interner. `to_id` is the single place id Strings live.
#[derive(Debug, Default)]
pub struct Interner {
    to_index: HashMap<String, NodeIndex>,
    to_id: Vec<String>,
    kinds: Vec<IdKind>,
}

impl Interner {
    pub fn new() -> Self { Self::default() }

    pub fn intern(&mut self, id: &str) -> NodeIndex {
        if let Some(&ix) = self.to_index.get(id) { return ix; }
        // Scene-build-time only (never per frame), so the check is free
        // where it matters; it turns a theoretical silent index-wrap at
        // u32::MAX ids-ever-seen into a loud panic instead.
        assert!(self.to_id.len() < u32::MAX as usize, "interner full");
        let ix = self.to_id.len() as NodeIndex;
        self.to_index.insert(id.to_string(), ix);
        self.to_id.push(id.to_string());
        self.kinds.push(IdKind::classify(id));
        ix
    }

    pub fn get(&self, id: &str) -> Option<NodeIndex> { self.to_index.get(id).copied() }

    /// Resolve an index back to its id string.
    ///
    /// # Panics
    /// Panics if `ix` did not come from this interner's `intern`/`get`.
    /// Indices are dense and append-only within one `Interner` instance;
    /// they are not portable across instances, and an out-of-range index
    /// panics rather than silently returning a wrong or empty string.
    pub fn resolve(&self, ix: NodeIndex) -> &str { &self.to_id[ix as usize] }

    /// Look up the kind classified for `ix` at intern time.
    ///
    /// # Panics
    /// Panics if `ix` did not come from this interner's `intern`/`get` —
    /// see [`Interner::resolve`].
    pub fn kind(&self, ix: NodeIndex) -> IdKind { self.kinds[ix as usize] }
    pub fn len(&self) -> usize { self.to_id.len() }
    pub fn is_empty(&self) -> bool { self.to_id.is_empty() }
}

/// Label-text interner. Same shape, separate index space, with slot 0
/// pre-seeded as the empty string.
#[derive(Debug)]
pub struct LabelInterner {
    to_index: HashMap<String, LabelId>,
    to_text: Vec<String>,
}

impl Default for LabelInterner { fn default() -> Self { Self::new() } }

impl LabelInterner {
    pub fn new() -> Self {
        let mut s = Self { to_index: HashMap::new(), to_text: Vec::new() };
        let zero = s.raw_intern("");
        debug_assert_eq!(zero, EMPTY_LABEL);
        s
    }
    fn raw_intern(&mut self, text: &str) -> LabelId {
        if let Some(&ix) = self.to_index.get(text) { return ix; }
        // Scene-build-time only (never per frame); see Interner::intern for
        // why this assert is free where it matters.
        assert!(self.to_text.len() < u32::MAX as usize, "interner full");
        let ix = self.to_text.len() as LabelId;
        self.to_index.insert(text.to_string(), ix);
        self.to_text.push(text.to_string());
        ix
    }
    pub fn intern(&mut self, text: &str) -> LabelId { self.raw_intern(text) }

    /// Resolve an index back to its label text.
    ///
    /// # Panics
    /// Panics if `ix` did not come from this interner's `intern`. Indices
    /// are dense and append-only within one `LabelInterner` instance; they
    /// are not portable across instances, and an out-of-range index panics
    /// rather than silently returning a wrong or empty string.
    pub fn resolve(&self, ix: LabelId) -> &str { &self.to_text[ix as usize] }
}

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

    #[test]
    fn intern_is_idempotent_and_stable() {
        let mut i = Interner::new();
        let a = i.intern("alpha");
        let b = i.intern("beta");
        assert_ne!(a, b);
        assert_eq!(i.intern("alpha"), a, "re-intern returns the same index");
        assert_eq!(i.resolve(a), "alpha");
        assert_eq!(i.resolve(b), "beta");
        assert_eq!(i.len(), 2);
    }

    #[test]
    fn indices_are_append_only_never_reused() {
        let mut i = Interner::new();
        let a = i.intern("a");
        let b = i.intern("b");
        let c = i.intern("c");
        assert_eq!((a, b, c), (0, 1, 2));
        assert_eq!(i.intern("d"), 3);
    }

    #[test]
    fn kind_is_classified_once_at_intern_time() {
        let mut i = Interner::new();
        let n = i.intern("node-1");
        let m = i.intern("__more");
        let g = i.intern("__agg:Sorcery");
        let l = i.intern("__loading");
        assert_eq!(i.kind(n), IdKind::Node);
        assert_eq!(i.kind(m), IdKind::More);
        assert_eq!(i.kind(g), IdKind::Aggregate);
        assert_eq!(i.kind(l), IdKind::Loading);
        assert!(!i.kind(n).is_synthetic());
        assert!(i.kind(m).is_synthetic());
        assert!(i.kind(g).is_synthetic());
        assert!(i.kind(l).is_synthetic());
    }

    #[test]
    fn near_miss_synthetic_ids_fall_back_to_other_synthetic() {
        // These all start with "__" but match none of the three named
        // prefixes. The old `node_screen_positions` filter excluded ANY
        // "__"-prefixed id (see graph-explorer-wasm), so these must stay synthetic
        // even though the old hit-test `kind_of` would have called them
        // ordinary nodes.
        let mut i = Interner::new();
        let no_colon_agg = i.intern("__agg"); // no trailing colon
        let near_more = i.intern("__morex");
        let bare = i.intern("__x");
        assert_eq!(i.kind(no_colon_agg), IdKind::OtherSynthetic);
        assert_eq!(i.kind(near_more), IdKind::OtherSynthetic);
        assert_eq!(i.kind(bare), IdKind::OtherSynthetic);
        assert!(i.kind(no_colon_agg).is_synthetic());
        assert!(i.kind(near_more).is_synthetic());
        assert!(i.kind(bare).is_synthetic());
    }

    #[test]
    fn lookup_without_interning() {
        let mut i = Interner::new();
        let a = i.intern("a");
        assert_eq!(i.get("a"), Some(a));
        assert_eq!(i.get("nope"), None);
    }

    #[test]
    fn label_interner_reserves_zero_for_empty() {
        let mut l = LabelInterner::new();
        assert_eq!(l.intern(""), EMPTY_LABEL);
        let x = l.intern("Sorcery");
        assert_ne!(x, EMPTY_LABEL);
        assert_eq!(l.intern("Sorcery"), x);
        assert_eq!(l.resolve(x), "Sorcery");
        assert_eq!(l.resolve(EMPTY_LABEL), "");
    }
}