xsd_schema/document/
namespace.rs

1//! Namespace chain storage for the document buffer.
2//!
3//! [`NamespaceNode`] is a 16-byte linked-list node holding a single namespace
4//! binding (prefix → namespace URI).  Chains are stored in a page-based arena
5//! ([`NamespacePageFactory`]) that mirrors the [`NodePages`](super::page::NodePages)
6//! pattern.
7
8use std::cell::Cell;
9
10use bumpalo::Bump;
11
12use crate::ids::NameId;
13
14// ── NsRef ─────────────────────────────────────────────────────────────
15
16/// Opaque index into a [`NamespacePageFactory`].
17#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
18pub struct NsRef(pub u32);
19
20impl Default for NsRef {
21    /// Default is the NULL sentinel, not slot 0.
22    fn default() -> Self {
23        Self::NULL
24    }
25}
26
27impl NsRef {
28    /// Sentinel value that marks end-of-chain or "no namespace".
29    pub const NULL: NsRef = NsRef(u32::MAX);
30
31    /// Returns `true` if this reference is the NULL sentinel.
32    #[inline]
33    pub fn is_null(self) -> bool {
34        self == Self::NULL
35    }
36}
37
38// ── Page-addressing constants ─────────────────────────────────────────
39
40/// Page size exponent: 2^12 = 4096 namespace nodes per page.
41pub const NS_PAGE_SHIFT: u32 = 12;
42
43/// Namespace nodes per page (4096).
44pub const NS_PAGE_SIZE: u32 = 1 << NS_PAGE_SHIFT;
45
46/// Bitmask for extracting the slot within a page.
47pub const NS_PAGE_MASK: u32 = NS_PAGE_SIZE - 1; // 0xFFF
48
49// ── NamespaceNode ─────────────────────────────────────────────────────
50
51/// A single namespace binding in a linked chain — 12 bytes.
52///
53/// Each element that declares namespace bindings stores an [`NsRef`] head
54/// that points to the first `NamespaceNode` in a chain.  The `next` field
55/// links to the following binding (or [`NsRef::NULL`] for end-of-chain).
56#[derive(Clone, Copy, Debug, PartialEq, Eq)]
57pub struct NamespaceNode {
58    pub prefix: NameId,
59    pub namespace_uri: NameId,
60    pub next: NsRef,
61}
62
63impl Default for NamespaceNode {
64    fn default() -> Self {
65        Self {
66            prefix: NameId(0),
67            namespace_uri: NameId(0),
68            next: NsRef::NULL,
69        }
70    }
71}
72
73impl NamespaceNode {
74    /// Creates a new namespace node.
75    pub fn new(prefix: NameId, namespace_uri: NameId, next: NsRef) -> Self {
76        Self {
77            prefix,
78            namespace_uri,
79            next,
80        }
81    }
82}
83
84// ── NamespacePageFactory ──────────────────────────────────────────────
85
86/// Arena-backed page array of [`Cell<NamespaceNode>`].
87///
88/// Mirrors [`NodePages`](super::page::NodePages) but for namespace bindings.
89pub struct NamespacePageFactory<'a> {
90    arena: &'a Bump,
91    pages: Vec<&'a [Cell<NamespaceNode>]>,
92    len: u32,
93}
94
95/// Returns the page number for a flat namespace index.
96#[inline]
97fn page_of(ns_ref: NsRef) -> u32 {
98    ns_ref.0 >> NS_PAGE_SHIFT
99}
100
101/// Returns the slot (offset within page) for a flat namespace index.
102#[inline]
103fn slot_of(ns_ref: NsRef) -> u32 {
104    ns_ref.0 & NS_PAGE_MASK
105}
106
107impl<'a> NamespacePageFactory<'a> {
108    /// Creates a new factory with the first page pre-allocated.
109    pub fn new(arena: &'a Bump) -> Self {
110        let first_page = Self::make_page(arena);
111        Self {
112            arena,
113            pages: vec![first_page],
114            len: 0,
115        }
116    }
117
118    /// Allocates the next namespace slot and returns its [`NsRef`].
119    ///
120    /// Returns `None` if the index would reach `u32::MAX` (reserved as NULL).
121    pub fn alloc(&mut self) -> Option<NsRef> {
122        let idx = self.len;
123        if idx == u32::MAX {
124            return None;
125        }
126        self.len = idx + 1;
127        if idx > 0 && slot_of(NsRef(idx)) == 0 {
128            self.allocate_page();
129        }
130        Some(NsRef(idx))
131    }
132
133    /// Reads the namespace node at the given reference.
134    #[inline]
135    pub fn get(&self, ns_ref: NsRef) -> NamespaceNode {
136        let page = page_of(ns_ref) as usize;
137        let slot = slot_of(ns_ref) as usize;
138        self.pages[page][slot].get()
139    }
140
141    /// Writes a namespace node at the given reference (interior mutability).
142    #[inline]
143    pub fn set(&self, ns_ref: NsRef, node: NamespaceNode) {
144        let page = page_of(ns_ref) as usize;
145        let slot = slot_of(ns_ref) as usize;
146        self.pages[page][slot].set(node);
147    }
148
149    /// Returns the total number of allocated namespace nodes.
150    #[inline]
151    pub fn len(&self) -> u32 {
152        self.len
153    }
154
155    /// Returns `true` if no namespace nodes have been allocated.
156    #[inline]
157    pub fn is_empty(&self) -> bool {
158        self.len == 0
159    }
160
161    /// Returns an iterator over the chain starting at `head`.
162    ///
163    /// Yields `(prefix, namespace_uri)` pairs.  An [`NsRef::NULL`] head
164    /// produces an empty iterator.
165    pub fn iter_chain(&self, head: NsRef) -> NamespaceChain<'_, 'a> {
166        NamespaceChain {
167            factory: self,
168            cursor: head,
169        }
170    }
171
172    fn allocate_page(&mut self) {
173        let page = Self::make_page(self.arena);
174        self.pages.push(page);
175    }
176
177    fn make_page(arena: &Bump) -> &[Cell<NamespaceNode>] {
178        arena.alloc_slice_fill_with(NS_PAGE_SIZE as usize, |_| {
179            Cell::new(NamespaceNode::default())
180        })
181    }
182}
183
184// ── NamespaceChain iterator ───────────────────────────────────────────
185
186/// Iterator over a linked chain of namespace bindings.
187pub struct NamespaceChain<'f, 'a> {
188    factory: &'f NamespacePageFactory<'a>,
189    cursor: NsRef,
190}
191
192impl Iterator for NamespaceChain<'_, '_> {
193    type Item = (NameId, NameId);
194
195    fn next(&mut self) -> Option<Self::Item> {
196        if self.cursor.is_null() {
197            return None;
198        }
199        let node = self.factory.get(self.cursor);
200        self.cursor = node.next;
201        Some((node.prefix, node.namespace_uri))
202    }
203}
204
205// ── Tests ─────────────────────────────────────────────────────────────
206
207#[cfg(test)]
208mod tests {
209    use super::*;
210    use std::mem;
211
212    #[test]
213    fn nsref_null_is_u32_max() {
214        assert_eq!(NsRef::NULL.0, u32::MAX);
215    }
216
217    #[test]
218    fn nsref_default_is_null() {
219        assert_eq!(NsRef::default(), NsRef::NULL);
220        assert!(NsRef::default().is_null());
221    }
222
223    #[test]
224    fn nsref_is_null() {
225        assert!(NsRef::NULL.is_null());
226        assert!(!NsRef(0).is_null());
227        assert!(!NsRef(42).is_null());
228    }
229
230    #[test]
231    fn end_of_chain_is_null() {
232        let node = NamespaceNode::new(NameId(1), NameId(2), NsRef::NULL);
233        assert!(node.next.is_null());
234    }
235
236    #[test]
237    fn namespace_node_is_12_bytes() {
238        assert_eq!(mem::size_of::<NamespaceNode>(), 12);
239    }
240
241    #[test]
242    fn sequential_alloc() {
243        let arena = Bump::new();
244        let mut factory = NamespacePageFactory::new(&arena);
245        for expected in 0..10u32 {
246            let ns_ref = factory.alloc().unwrap();
247            assert_eq!(ns_ref.0, expected);
248        }
249    }
250
251    #[test]
252    fn set_get_round_trip() {
253        let arena = Bump::new();
254        let mut factory = NamespacePageFactory::new(&arena);
255        let r = factory.alloc().unwrap();
256
257        let node = NamespaceNode::new(NameId(10), NameId(20), NsRef::NULL);
258        factory.set(r, node);
259        assert_eq!(factory.get(r), node);
260    }
261
262    #[test]
263    fn cross_page_allocation() {
264        let arena = Bump::new();
265        let mut factory = NamespacePageFactory::new(&arena);
266
267        let count = NS_PAGE_SIZE + 1;
268        for i in 0..count {
269            let r = factory.alloc().unwrap();
270            assert_eq!(r.0, i);
271            factory.set(
272                r,
273                NamespaceNode::new(NameId(i), NameId(i + 1000), NsRef::NULL),
274            );
275        }
276        assert_eq!(factory.len(), count);
277
278        // Verify last node on first page
279        let last_first = NsRef(NS_PAGE_SIZE - 1);
280        assert_eq!(factory.get(last_first).prefix, NameId(NS_PAGE_SIZE - 1));
281
282        // Verify first node on second page
283        let first_second = NsRef(NS_PAGE_SIZE);
284        assert_eq!(factory.get(first_second).prefix, NameId(NS_PAGE_SIZE));
285    }
286
287    #[test]
288    fn single_node_chain() {
289        let arena = Bump::new();
290        let mut factory = NamespacePageFactory::new(&arena);
291        let r = factory.alloc().unwrap();
292        factory.set(r, NamespaceNode::new(NameId(1), NameId(2), NsRef::NULL));
293
294        let items: Vec<_> = factory.iter_chain(r).collect();
295        assert_eq!(items, vec![(NameId(1), NameId(2))]);
296    }
297
298    #[test]
299    fn two_node_chain() {
300        let arena = Bump::new();
301        let mut factory = NamespacePageFactory::new(&arena);
302
303        let r1 = factory.alloc().unwrap();
304        let r0 = factory.alloc().unwrap();
305
306        // Build chain: r0 -> r1 -> NULL
307        factory.set(r1, NamespaceNode::new(NameId(3), NameId(4), NsRef::NULL));
308        factory.set(r0, NamespaceNode::new(NameId(1), NameId(2), r1));
309
310        let items: Vec<_> = factory.iter_chain(r0).collect();
311        assert_eq!(items, vec![(NameId(1), NameId(2)), (NameId(3), NameId(4))]);
312    }
313
314    #[test]
315    fn multi_node_chain() {
316        let arena = Bump::new();
317        let mut factory = NamespacePageFactory::new(&arena);
318
319        let r2 = factory.alloc().unwrap();
320        let r1 = factory.alloc().unwrap();
321        let r0 = factory.alloc().unwrap();
322
323        factory.set(r2, NamespaceNode::new(NameId(5), NameId(6), NsRef::NULL));
324        factory.set(r1, NamespaceNode::new(NameId(3), NameId(4), r2));
325        factory.set(r0, NamespaceNode::new(NameId(1), NameId(2), r1));
326
327        let items: Vec<_> = factory.iter_chain(r0).collect();
328        assert_eq!(
329            items,
330            vec![
331                (NameId(1), NameId(2)),
332                (NameId(3), NameId(4)),
333                (NameId(5), NameId(6)),
334            ]
335        );
336    }
337
338    #[test]
339    fn null_chain_yields_empty() {
340        let arena = Bump::new();
341        let factory = NamespacePageFactory::new(&arena);
342        let items: Vec<_> = factory.iter_chain(NsRef::NULL).collect();
343        assert!(items.is_empty());
344    }
345
346    #[test]
347    fn len_and_is_empty() {
348        let arena = Bump::new();
349        let mut factory = NamespacePageFactory::new(&arena);
350        assert_eq!(factory.len(), 0);
351        assert!(factory.is_empty());
352
353        factory.alloc().unwrap();
354        assert_eq!(factory.len(), 1);
355        assert!(!factory.is_empty());
356    }
357}
xsd_schema/document/namespace.rs

xsd_schema/document/
namespace.rs
