rdom_core/
node_id.rs

1//! `NodeId` — stable handle into the arena.
2//!
3//! A `NodeId` is an arena slot index plus a **generation**. Freed slots
4//! are recycled (LIFO, cache-friendly), and every recycle bumps the
5//! slot's generation, so a handle to a dropped node can never resolve
6//! to the node that later reuses its slot: `Dom::contains` says `false`,
7//! `node_or_err` returns `InvalidNode`, and every mutation path refuses
8//! it. This is the "never hand out a stale `NodeId` as a live one"
9//! invariant; before generations existed a cached id silently aliased
10//! the new occupant.
11//!
12//! The generation is `NonZeroU32` so `Option<NodeId>` packs into 8 bytes.
13//! The `NodeId` itself is plain `Copy`; mixing ids across different
14//! `Dom`s is a bug (same as mixing `slab::Key`s).
15
16use std::num::NonZeroU32;
17
18#[derive(Clone, Copy, PartialEq, Eq, Hash, Ord, PartialOrd)]
19pub struct NodeId {
20    index: u32,
21    generation: NonZeroU32,
22}
23
24impl NodeId {
25    /// Internal arena index.
26    #[inline]
27    pub(crate) fn index(self) -> usize {
28        self.index as usize
29    }
30
31    /// Construct from an arena index + slot generation. Panics on index
32    /// overflow (should be impossible in practice — 4 billion nodes
33    /// would OOM the process long before the counter rolls).
34    #[inline]
35    pub(crate) fn from_parts(index: usize, generation: NonZeroU32) -> Self {
36        let index = u32::try_from(index).expect("arena overflow: more than u32::MAX nodes");
37        NodeId { index, generation }
38    }
39
40    /// Generation as stored (for the arena's liveness check).
41    #[inline]
42    pub(crate) fn generation_raw(self) -> NonZeroU32 {
43        self.generation
44    }
45
46    /// The slot's generation when this id was issued. Starts at 1 and
47    /// increments each time the slot is freed and reused.
48    #[inline]
49    pub fn generation(self) -> u32 {
50        self.generation.get()
51    }
52
53    /// Raw slot number (`index + 1`) for debugging / Display. Two ids
54    /// with the same `as_u32()` but different `generation()` refer to
55    /// different nodes that occupied the same slot at different times.
56    pub fn as_u32(self) -> u32 {
57        self.index + 1
58    }
59}
60
61/// Compact form, `NodeId(42)` — with `@gen` appended after a recycle —
62/// rather than the derived struct dump, so debug output and paint
63/// snapshots that print ids stay readable.
64impl std::fmt::Debug for NodeId {
65    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
66        write!(f, "NodeId({}", self.index + 1)?;
67        if self.generation.get() > 1 {
68            write!(f, "@{}", self.generation.get())?;
69        }
70        write!(f, ")")
71    }
72}
73
74impl std::fmt::Display for NodeId {
75    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
76        write!(f, "#{}", self.index + 1)?;
77        if self.generation.get() > 1 {
78            write!(f, "@{}", self.generation.get())?;
79        }
80        Ok(())
81    }
82}
83
84#[cfg(test)]
85mod tests {
86    use super::*;
87
88    const G1: NonZeroU32 = NonZeroU32::MIN;
89
90    #[test]
91    fn index_round_trip() {
92        for i in [0, 1, 2, 7, 99, 1000, 1_000_000] {
93            let id = NodeId::from_parts(i, G1);
94            assert_eq!(id.index(), i);
95            assert_eq!(id.generation(), 1);
96        }
97    }
98
99    /// Index + generation: 8 bytes, and `Option<NodeId>` still packs
100    /// into the same 8 via the `NonZeroU32` niche.
101    #[test]
102    fn option_node_id_is_eight_bytes() {
103        assert_eq!(std::mem::size_of::<NodeId>(), 8);
104        assert_eq!(std::mem::size_of::<Option<NodeId>>(), 8);
105    }
106
107    #[test]
108    fn same_slot_different_generation_is_a_different_id() {
109        let a = NodeId::from_parts(5, G1);
110        let b = NodeId::from_parts(5, NonZeroU32::new(2).unwrap());
111        assert_ne!(a, b);
112        assert_eq!(a.index(), b.index());
113    }
114
115    /// First-generation ids print as before (`#slot`); a recycled slot
116    /// shows its generation so debug output can tell the two apart.
117    #[test]
118    fn debug_is_compact() {
119        assert_eq!(format!("{:?}", NodeId::from_parts(8, G1)), "NodeId(9)");
120        assert_eq!(
121            format!("{:?}", NodeId::from_parts(8, NonZeroU32::new(2).unwrap())),
122            "NodeId(9@2)"
123        );
124    }
125
126    #[test]
127    fn display_shows_slot_and_generation_after_reuse() {
128        assert_eq!(format!("{}", NodeId::from_parts(41, G1)), "#42");
129        assert_eq!(
130            format!("{}", NodeId::from_parts(41, NonZeroU32::new(3).unwrap())),
131            "#42@3"
132        );
133    }
134}
rdom_core/node_id.rs

rdom_core/
node_id.rs
