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