fhp_tree/
node.rs

1//! Cache-line aligned node layout and supporting types.
2//!
3//! Each [`Node`](crate::node::Node) occupies exactly 64 bytes (one cache line), split into a hot
4//! first half (tree links, tag, depth) and a cold second half (attribute
5//! metadata, padding).
6
7use fhp_core::tag::Tag;
8
9/// Index into the arena's node vector.
10///
11/// Uses `u32` internally — supports up to ~4 billion nodes.
12/// [`NodeId::NULL`] represents the absence of a node (like `None`).
13#[derive(Clone, Copy, PartialEq, Eq, Hash)]
14pub struct NodeId(pub u32);
15
16impl NodeId {
17    /// Sentinel value representing "no node".
18    pub const NULL: NodeId = NodeId(u32::MAX);
19
20    /// Returns `true` if this is the null sentinel.
21    #[inline(always)]
22    pub const fn is_null(self) -> bool {
23        self.0 == u32::MAX
24    }
25
26    /// Returns the index as `usize` for array indexing.
27    #[inline(always)]
28    pub const fn index(self) -> usize {
29        self.0 as usize
30    }
31}
32
33impl core::fmt::Debug for NodeId {
34    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
35        if self.is_null() {
36            write!(f, "NodeId(NULL)")
37        } else {
38            write!(f, "NodeId({})", self.0)
39        }
40    }
41}
42
43/// Bitflags for node properties.
44///
45/// Packed into a single `u8` for minimal space inside the [`Node`] struct.
46#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
47pub struct NodeFlags(u8);
48
49impl NodeFlags {
50    /// The element is a void element (no children allowed).
51    pub const IS_VOID: u8 = 1 << 0;
52    /// The element has at least one child.
53    pub const HAS_CHILDREN: u8 = 1 << 1;
54    /// The element has at least one attribute.
55    pub const HAS_ATTRS: u8 = 1 << 2;
56    /// The element was self-closing in source (`<br/>`).
57    pub const IS_SELF_CLOSING: u8 = 1 << 3;
58    /// This node is a text node (not an element).
59    pub const IS_TEXT: u8 = 1 << 4;
60    /// This node is a comment node.
61    pub const IS_COMMENT: u8 = 1 << 5;
62    /// This node is a doctype node.
63    pub const IS_DOCTYPE: u8 = 1 << 6;
64    /// This node is a CDATA section.
65    pub const IS_CDATA: u8 = 1 << 7;
66
67    /// Text node reads from `Arena::source` instead of `text_slab`.
68    ///
69    /// Reuses the [`IS_VOID`](Self::IS_VOID) bit (bit 0), which is unused for
70    /// text nodes. Only meaningful when [`IS_TEXT`](Self::IS_TEXT) is also set.
71    pub const IS_TEXT_FROM_SOURCE: u8 = 1 << 0;
72
73    /// Create empty flags.
74    #[inline(always)]
75    pub const fn empty() -> Self {
76        Self(0)
77    }
78
79    /// Set a flag bit.
80    #[inline(always)]
81    pub fn set(&mut self, flag: u8) {
82        self.0 |= flag;
83    }
84
85    /// Check if a flag bit is set.
86    #[inline(always)]
87    pub const fn has(self, flag: u8) -> bool {
88        self.0 & flag != 0
89    }
90}
91
92/// A single DOM node in the arena, exactly 64 bytes (one cache line).
93///
94/// The first 32 bytes contain frequently accessed fields (tree links, tag,
95/// depth). The second 32 bytes contain less-frequently accessed data
96/// (attribute metadata).
97///
98/// # Layout
99///
100/// | Offset | Bytes | Field |
101/// |--------|-------|-------|
102/// | 0      | 1     | `tag` |
103/// | 1      | 1     | `flags` |
104/// | 2      | 2     | `depth` |
105/// | 4      | 4     | `parent` |
106/// | 8      | 4     | `first_child` |
107/// | 12     | 4     | `next_sibling` |
108/// | 16     | 4     | `last_child` |
109/// | 20     | 4     | `prev_sibling` |
110/// | 24     | 4     | `text_offset` |
111/// | 28     | 4     | `text_len` |
112/// | 32     | 4     | `attr_offset` |
113/// | 36     | 4     | `attr_raw_offset` |
114/// | 40     | 8     | `class_hash` |
115/// | 48     | 4     | `id_hash` |
116/// | 52     | 2     | `attr_raw_len` |
117/// | 54     | 2     | `element_index` |
118/// | 56     | 2     | `attr_count` |
119/// | 58     | 6     | `_padding` |
120#[repr(C, align(64))]
121pub struct Node {
122    // === Hot (first 32 bytes) ===
123    /// Interned tag type.
124    pub tag: Tag,
125    /// Bitflags for node properties.
126    pub flags: NodeFlags,
127    /// Nesting depth from root (root = 0).
128    pub depth: u16,
129    /// Parent node, or `NodeId::NULL` for root.
130    pub parent: NodeId,
131    /// First child, or `NodeId::NULL` if no children.
132    pub first_child: NodeId,
133    /// Next sibling, or `NodeId::NULL` if last.
134    pub next_sibling: NodeId,
135    /// Last child, or `NodeId::NULL` if no children.
136    pub last_child: NodeId,
137    /// Previous sibling, or `NodeId::NULL` if first.
138    pub prev_sibling: NodeId,
139    /// Byte offset into the text slab.
140    pub text_offset: u32,
141    /// Length in bytes of the text content in the slab.
142    pub text_len: u32,
143
144    // === Cold (second 32 bytes) ===
145    // Fields ordered to avoid implicit padding with repr(C):
146    // u32s first, then u16s, then byte-array padding.
147    /// Byte offset into the attribute slab.
148    pub attr_offset: u32,
149    /// Reserved (formerly the raw attribute region offset for lazy parsing,
150    /// which was removed). Kept to preserve the 64-byte layout.
151    pub attr_raw_offset: u32,
152    /// 64-bit bloom filter of class attribute tokens.
153    ///
154    /// Each class token is hashed via FNV-1a and a single bit is set at
155    /// `hash % 64`. Zero means no class attribute. Used by the selector
156    /// matcher for fast rejection. 64 bits reduces false positive rate
157    /// from ~15% (5 classes) to ~8% compared to 32-bit.
158    pub class_hash: u64,
159    /// FNV-1a hash of the `id` attribute value.
160    ///
161    /// Zero means no id attribute. Used by the selector matcher for fast
162    /// rejection before scanning attributes.
163    pub id_hash: u32,
164    /// Reserved (formerly the raw attribute region length for lazy parsing,
165    /// which was removed). Kept to preserve the 64-byte layout.
166    pub attr_raw_len: u16,
167    /// 1-based index among element siblings (0 = not computed or text node).
168    pub element_index: u16,
169    /// Number of attributes.
170    pub attr_count: u16,
171    /// Padding to fill the cache line.
172    pub _padding: [u8; 6],
173}
174
175impl Node {
176    /// Create a new element node with all links set to NULL.
177    pub fn new_element(tag: Tag, depth: u16) -> Self {
178        let mut flags = NodeFlags::empty();
179        if tag.is_void() {
180            flags.set(NodeFlags::IS_VOID);
181        }
182        Self {
183            tag,
184            flags,
185            depth,
186            parent: NodeId::NULL,
187            first_child: NodeId::NULL,
188            next_sibling: NodeId::NULL,
189            last_child: NodeId::NULL,
190            prev_sibling: NodeId::NULL,
191            text_offset: 0,
192            text_len: 0,
193            attr_offset: 0,
194            attr_count: 0,
195            attr_raw_offset: 0,
196            attr_raw_len: 0,
197            class_hash: 0,
198            id_hash: 0,
199            element_index: 0,
200            _padding: [0; 6],
201        }
202    }
203
204    /// Create a new text node.
205    pub fn new_text(depth: u16, text_offset: u32, text_len: u32) -> Self {
206        let mut flags = NodeFlags::empty();
207        flags.set(NodeFlags::IS_TEXT);
208        Self {
209            tag: Tag::Unknown,
210            flags,
211            depth,
212            parent: NodeId::NULL,
213            first_child: NodeId::NULL,
214            next_sibling: NodeId::NULL,
215            last_child: NodeId::NULL,
216            prev_sibling: NodeId::NULL,
217            text_offset,
218            text_len,
219            attr_offset: 0,
220            attr_count: 0,
221            attr_raw_offset: 0,
222            attr_raw_len: 0,
223            class_hash: 0,
224            id_hash: 0,
225            element_index: 0,
226            _padding: [0; 6],
227        }
228    }
229
230    /// Create a new comment node.
231    pub fn new_comment(depth: u16, text_offset: u32, text_len: u32) -> Self {
232        let mut flags = NodeFlags::empty();
233        flags.set(NodeFlags::IS_COMMENT);
234        Self {
235            tag: Tag::Unknown,
236            flags,
237            depth,
238            parent: NodeId::NULL,
239            first_child: NodeId::NULL,
240            next_sibling: NodeId::NULL,
241            last_child: NodeId::NULL,
242            prev_sibling: NodeId::NULL,
243            text_offset,
244            text_len,
245            attr_offset: 0,
246            attr_count: 0,
247            attr_raw_offset: 0,
248            attr_raw_len: 0,
249            class_hash: 0,
250            id_hash: 0,
251            element_index: 0,
252            _padding: [0; 6],
253        }
254    }
255
256    /// Create a new doctype node.
257    pub fn new_doctype(depth: u16, text_offset: u32, text_len: u32) -> Self {
258        let mut flags = NodeFlags::empty();
259        flags.set(NodeFlags::IS_DOCTYPE);
260        Self {
261            tag: Tag::Unknown,
262            flags,
263            depth,
264            parent: NodeId::NULL,
265            first_child: NodeId::NULL,
266            next_sibling: NodeId::NULL,
267            last_child: NodeId::NULL,
268            prev_sibling: NodeId::NULL,
269            text_offset,
270            text_len,
271            attr_offset: 0,
272            attr_count: 0,
273            attr_raw_offset: 0,
274            attr_raw_len: 0,
275            class_hash: 0,
276            id_hash: 0,
277            element_index: 0,
278            _padding: [0; 6],
279        }
280    }
281}
282
283impl core::fmt::Debug for Node {
284    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
285        f.debug_struct("Node")
286            .field("tag", &self.tag)
287            .field("flags", &self.flags)
288            .field("depth", &self.depth)
289            .field("parent", &self.parent)
290            .field("first_child", &self.first_child)
291            .field("next_sibling", &self.next_sibling)
292            .finish()
293    }
294}
295
296#[cfg(test)]
297mod tests {
298    use super::*;
299
300    #[test]
301    fn node_is_64_bytes() {
302        assert_eq!(
303            std::mem::size_of::<Node>(),
304            64,
305            "Node must be exactly 64 bytes (one cache line)"
306        );
307    }
308
309    #[test]
310    fn node_alignment_is_64() {
311        assert_eq!(
312            std::mem::align_of::<Node>(),
313            64,
314            "Node must be 64-byte aligned"
315        );
316    }
317
318    #[test]
319    fn node_id_null() {
320        assert!(NodeId::NULL.is_null());
321        assert!(!NodeId(0).is_null());
322        assert!(!NodeId(42).is_null());
323    }
324
325    #[test]
326    fn node_id_debug() {
327        assert_eq!(format!("{:?}", NodeId::NULL), "NodeId(NULL)");
328        assert_eq!(format!("{:?}", NodeId(5)), "NodeId(5)");
329    }
330
331    #[test]
332    fn node_flags() {
333        let mut flags = NodeFlags::empty();
334        assert!(!flags.has(NodeFlags::IS_VOID));
335        assert!(!flags.has(NodeFlags::HAS_CHILDREN));
336
337        flags.set(NodeFlags::IS_VOID);
338        assert!(flags.has(NodeFlags::IS_VOID));
339        assert!(!flags.has(NodeFlags::HAS_CHILDREN));
340
341        flags.set(NodeFlags::HAS_CHILDREN);
342        assert!(flags.has(NodeFlags::IS_VOID));
343        assert!(flags.has(NodeFlags::HAS_CHILDREN));
344    }
345
346    #[test]
347    fn new_element_sets_void_flag() {
348        let br = Node::new_element(Tag::Br, 0);
349        assert!(br.flags.has(NodeFlags::IS_VOID));
350
351        let div = Node::new_element(Tag::Div, 0);
352        assert!(!div.flags.has(NodeFlags::IS_VOID));
353    }
354
355    #[test]
356    fn new_text_sets_text_flag() {
357        let text = Node::new_text(1, 0, 5);
358        assert!(text.flags.has(NodeFlags::IS_TEXT));
359        assert_eq!(text.text_offset, 0);
360        assert_eq!(text.text_len, 5);
361    }
362}
fhp_tree/node.rs

fhp_tree/
node.rs
