vize_l0/id.rs
1//! Node identity: the key every side table and cross-stage reference uses.
2//!
3//! `architecture.md`'s shared-infrastructure contract is "cross-stage
4//! references and analysis results are `NodeId`-keyed tables, not fat nodes
5//! and not raw `*mut` traversal". [`NodeId`] is that key.
6
7use core::fmt;
8use core::num::NonZeroU32;
9
10/// Analysis identities live beside the preserved sets the pass manager
11/// intersects; they are ids all the same.
12pub use crate::pass::preserved::AnalysisId;
13
14/// A stage-local node identity.
15///
16/// # Why `NonZeroU32` rather than a reserved sentinel
17///
18/// Both give `Option<NodeId>` a 4-byte layout, which is the requirement (an
19/// L2 op holding several optional child references pays 4 bytes per slot, not
20/// 8). `NonZeroU32` is chosen because it makes "no such node" **unrepresentable
21/// inside `NodeId` itself**: with a reserved-sentinel `u32` every consumer must
22/// remember that `NodeId(0)` is not a node, and nothing stops one from
23/// constructing it. The niche is also stable-Rust: reserving a range on a plain
24/// `u32` needs `rustc_layout_scalar_valid_range`, which is unstable.
25///
26/// The cost is that the raw value and the index differ by one, so the
27/// conversion is explicit and single-sourced: [`NodeId::from_index`] and
28/// [`NodeId::index`]. Nothing else may do the arithmetic.
29#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
30pub struct NodeId(NonZeroU32);
31
32/// `NodeId` is a key, copied into every side-table lookup; a niche keeps
33/// `Option<NodeId>` the same width as the id.
34///
35/// Deliberately **not** `#[cfg(target_pointer_width = "64")]`-guarded, unlike
36/// the node-size asserts in `vize_relief`. That guard exists because those
37/// figures are 64-bit footprints of pointer-containing structs ("the wasm32
38/// build is 32-bit", `crates/vize_relief/src/relief/elements.rs:31-36`).
39/// `NodeId` holds a `u32` and no pointer, so its footprint is the same on
40/// every target and guarding would only stop the wasm32 lane P2-14 makes
41/// required from checking the niche - which is the property most worth
42/// checking there.
43const _: () = assert!(size_of::<NodeId>() == 4);
44const _: () = assert!(size_of::<Option<NodeId>>() == 4);
45
46impl NodeId {
47 /// The first id a stage mints, equivalent to `from_index(0)`.
48 pub const FIRST: NodeId = NodeId(NonZeroU32::MIN);
49
50 /// The id for a 0-based node index.
51 ///
52 /// Returns `None` only for `u32::MAX`, whose successor does not fit — a
53 /// stage with more than `u32::MAX - 1` nodes in one artifact, which no
54 /// real input reaches. Callers minting ids in sequence should propagate
55 /// the `None` rather than unwrap it: exhaustion is a diagnostic, not a
56 /// panic.
57 #[inline]
58 #[must_use]
59 pub const fn from_index(index: u32) -> Option<NodeId> {
60 match NonZeroU32::new(index.wrapping_add(1)) {
61 Some(raw) => Some(NodeId(raw)),
62 None => None,
63 }
64 }
65
66 /// The 0-based index this id denotes.
67 ///
68 /// This is the dense-side-table subscript, and the only place the
69 /// off-by-one between the niche representation and the index lives.
70 #[inline]
71 #[must_use]
72 pub const fn index(self) -> u32 {
73 self.0.get() - 1
74 }
75
76 /// The 0-based index as a `usize`, for indexing a dense table.
77 #[inline]
78 #[must_use]
79 pub const fn index_usize(self) -> usize {
80 self.index() as usize
81 }
82
83 /// The niche representation, for a folio page that serializes ids.
84 #[inline]
85 #[must_use]
86 pub const fn to_raw(self) -> NonZeroU32 {
87 self.0
88 }
89
90 /// Rebuild an id from its niche representation.
91 #[inline]
92 #[must_use]
93 pub const fn from_raw(raw: NonZeroU32) -> NodeId {
94 NodeId(raw)
95 }
96
97 /// The next id in sequence, or `None` at exhaustion.
98 #[inline]
99 #[must_use]
100 pub const fn next(self) -> Option<NodeId> {
101 match self.0.checked_add(1) {
102 Some(raw) => Some(NodeId(raw)),
103 None => None,
104 }
105 }
106}
107
108/// Prints the **index**, not the niche value, because the index is what folio
109/// pages and diagnostics show: `NodeId(0)` is the first node.
110impl fmt::Debug for NodeId {
111 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
112 write!(f, "NodeId({})", self.index())
113 }
114}
115
116impl fmt::Display for NodeId {
117 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
118 write!(f, "%{}", self.index())
119 }
120}
121
122#[cfg(test)]
123mod tests {
124 use super::NodeId;
125 use vize_l0::cstr;
126
127 #[test]
128 fn index_round_trips_through_the_niche() {
129 for index in [0u32, 1, 2, 41, u32::MAX - 1] {
130 let id = NodeId::from_index(index).expect("index below u32::MAX has an id");
131 assert_eq!(id.index(), index);
132 assert_eq!(id.index_usize(), index as usize);
133 assert_eq!(NodeId::from_raw(id.to_raw()), id);
134 }
135 }
136
137 #[test]
138 fn the_first_id_is_index_zero() {
139 assert_eq!(
140 NodeId::FIRST,
141 NodeId::from_index(0).expect("index 0 has an id")
142 );
143 assert_eq!(NodeId::FIRST.index(), 0);
144 }
145
146 #[test]
147 fn exhaustion_yields_none_rather_than_wrapping() {
148 assert_eq!(NodeId::from_index(u32::MAX), None);
149 let last = NodeId::from_raw(core::num::NonZeroU32::MAX);
150 assert_eq!(last.next(), None);
151 }
152
153 #[test]
154 fn next_walks_the_index_sequence() {
155 let first = NodeId::FIRST;
156 let second = first.next().expect("the second id exists");
157 assert_eq!(second.index(), 1);
158 assert_eq!(second, NodeId::from_index(1).expect("index 1 has an id"));
159 }
160
161 #[test]
162 fn debug_and_display_show_the_index() {
163 let id = NodeId::from_index(7).expect("index 7 has an id");
164 assert_eq!(cstr!("{id:?}").as_str(), "NodeId(7)");
165 assert_eq!(cstr!("{id}").as_str(), "%7");
166 }
167
168 #[test]
169 fn ids_order_by_index() {
170 let a = NodeId::from_index(1).expect("index 1 has an id");
171 let b = NodeId::from_index(2).expect("index 2 has an id");
172 assert!(a < b);
173 }
174}