Lines
61.38 %
Functions
51.53 %
Branches
100 %
//! Node tree data structures and hierarchy management.
//!
//! This module provides the core data structures for managing DOM-like tree hierarchies:
//! - `NodeId`: Type-safe node identifiers with Option<NodeId> optimization
//! - `NodeHierarchy`: Parent-child relationships between nodes
//! - `NodeDataContainer`: Generic storage for node data with efficient indexing
//! # Memory Layout
//! `NodeId` stores a plain `usize` index internally. For FFI structs that need
//! `Option<NodeId>`, a manual 1-based encoding is used (0 = None, n > 0 = Some(n-1)).
//! # Performance
//! - Node lookups are O(1) via direct array indexing
//! - Parent/child traversal is O(1) via pre-computed indices
//! - No heap allocations after initial tree construction
use alloc::vec::Vec;
use core::{
ops::{Index, IndexMut},
slice::Iter,
};
pub use self::node_id::NodeId;
use crate::styled_dom::NodeHierarchyItem;
/// Type alias for depth-first traversal results: (depth, node_id) pairs
pub type NodeDepths = Vec<(usize, NodeId)>;
// Simple FFI-safe NodeId - just a wrapper around usize
pub mod node_id {
fmt,
ops::{Add, AddAssign},
/// A type-safe identifier for a node within a DOM tree.
///
/// `NodeId` is FFI-safe (`#[repr(C)]`) and stores a **zero-based** index internally.
/// Use `NodeId::index()` to get the array index for direct node access.
/// # Zero-based indexing
/// - `NodeId::new(0)` → first node (index 0)
/// - `NodeId::new(5)` → sixth node (index 5)
/// - Use `node_id.index()` to get the array index
/// # FFI Encoding (for `Option<NodeId>`)
/// When storing `Option<NodeId>` in FFI structs (like `NodeHierarchyItem`),
/// we use a **1-based encoding** to represent None:
/// - `0` means `None` (no node)
/// - `n > 0` means `Some(NodeId(n - 1))`
/// Use [`NodeId::from_usize`] to decode and [`NodeId::into_raw`] to encode.
/// See also: [`crate::styled_dom::NodeHierarchyItemId`] for the FFI wrapper type.
/// # Warning
/// **Never manually construct raw usize values for node hierarchy fields!**
/// Always use the provided `from_usize`/`into_raw` functions to avoid
/// off-by-one errors that can cause index-out-of-bounds panics.
#[repr(C)]
#[derive(Copy, Clone, PartialOrd, Ord, PartialEq, Eq, Hash)]
pub struct NodeId {
// Private field to prevent direct manipulation.
// Use NodeId::new() to create, NodeId::index() to read.
inner: usize,
}
impl NodeId {
/// The zero/first node ID (index 0).
pub const ZERO: NodeId = NodeId { inner: 0 };
/// Creates a new `NodeId` from a zero-based index.
#[inline(always)]
pub const fn new(value: usize) -> Self {
NodeId { inner: value }
/// Decodes a raw `usize` to `Option<NodeId>` using 1-based encoding.
/// This is the inverse of [`NodeId::into_usize`].
/// - `0` → `None` (no node)
/// - `n > 0` → `Some(NodeId(n - 1))`
/// This function is for decoding values stored in FFI structs like
/// `NodeHierarchyItem`. Do not use raw usize values directly - always
/// decode them first!
#[inline]
pub const fn from_usize(value: usize) -> Option<Self> {
match value {
0 => None,
i => Some(NodeId { inner: i - 1 }),
/// Encodes `Option<NodeId>` to a raw `usize` for storage in FFI structs.
/// - `None` → `0`
/// - `Some(NodeId(n))` → `n + 1`
/// The returned value uses **1-based encoding**! A value of `0` means "no node",
/// NOT "node at index 0". Use [`NodeId::from_usize`] to decode.
pub const fn into_raw(val: &Option<Self>) -> usize {
match val {
None => 0,
Some(s) => s.inner + 1,
/// Returns the **zero-based** index of this node.
/// This is the actual array index where the node data is stored.
pub const fn index(&self) -> usize {
self.inner
impl From<usize> for NodeId {
fn from(val: usize) -> Self {
NodeId::new(val)
impl From<NodeId> for usize {
fn from(val: NodeId) -> Self {
val.inner
impl Add<usize> for NodeId {
type Output = NodeId;
fn add(self, other: usize) -> NodeId {
NodeId::new(self.inner + other)
impl AddAssign<usize> for NodeId {
fn add_assign(&mut self, other: usize) {
*self = *self + other;
impl fmt::Display for NodeId {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "{}", self.inner)
impl fmt::Debug for NodeId {
write!(f, "NodeId({})", self.inner)
/// Hierarchical information about a node (stores the indices of the parent / child nodes).
#[derive(Debug, Default, Copy, Clone, PartialOrd, Ord, PartialEq, Eq, Hash)]
pub struct Node {
pub parent: Option<NodeId>,
pub previous_sibling: Option<NodeId>,
pub next_sibling: Option<NodeId>,
pub last_child: Option<NodeId>,
// NOTE: first_child can be calculated on the fly:
//
// - if last_child is None, first_child is None
// - if last_child is Some, first_child is parent_index + 1
// This makes the "Node" struct take up 4 registers instead of 5
// pub first_child: Option<NodeId>,
impl Node {
pub const ROOT: Node = Node {
parent: None,
previous_sibling: None,
next_sibling: None,
last_child: None,
pub const fn has_parent(&self) -> bool {
self.parent.is_some()
pub const fn has_previous_sibling(&self) -> bool {
self.previous_sibling.is_some()
pub const fn has_next_sibling(&self) -> bool {
self.next_sibling.is_some()
pub const fn has_first_child(&self) -> bool {
self.last_child.is_some() /* last_child and first_child are always set together */
pub const fn has_last_child(&self) -> bool {
self.last_child.is_some()
pub fn get_first_child(&self, current_node_id: NodeId) -> Option<NodeId> {
// last_child and first_child are always set together
self.last_child.map(|_| current_node_id + 1)
/// The hierarchy of nodes is stored separately from the actual node content in order
/// to save on memory, since the hierarchy can be re-used across several DOM trees even
/// if the content changes.
#[derive(Debug, Default, Clone, PartialEq, Hash, Eq, PartialOrd, Ord)]
pub struct NodeHierarchy {
pub internal: Vec<Node>,
impl NodeHierarchy {
pub const fn new(data: Vec<Node>) -> Self {
Self { internal: data }
pub fn as_ref(&self) -> NodeHierarchyRef<'_> {
NodeHierarchyRef {
internal: &self.internal[..],
#[derive(Debug, PartialEq, Hash, Eq)]
pub struct NodeHierarchyRef<'a> {
pub internal: &'a [Node],
impl<'a> NodeHierarchyRef<'a> {
pub fn from_slice(data: &'a [Node]) -> NodeHierarchyRef<'a> {
NodeHierarchyRef { internal: data }
pub fn len(&self) -> usize {
self.internal.len()
pub fn get(&self, id: NodeId) -> Option<&Node> {
self.internal.get(id.index())
pub fn linear_iter(&self) -> LinearIterator {
LinearIterator {
arena_len: self.len(),
position: 0,
/// Returns the `(depth, NodeId)` of all parent nodes (i.e. nodes that have a
/// `first_child`), in depth sorted order, (i.e. `NodeId(0)` with a depth of 0) is
/// the first element.
/// Runtime: O(n) max
pub fn get_parents_sorted_by_depth(&self) -> NodeDepths {
let mut non_leaf_nodes = Vec::new();
let mut current_children = vec![(0, NodeId::new(0))];
let mut next_children = Vec::new();
let mut depth = 1_usize;
loop {
for id in ¤t_children {
for child_id in id.1.children(self).filter(|id| self[*id].has_first_child()) {
next_children.push((depth, child_id));
non_leaf_nodes.extend(&mut current_children.drain(..));
if next_children.is_empty() {
break;
} else {
current_children.extend(&mut next_children.drain(..));
depth += 1;
non_leaf_nodes
#[derive(Debug, Clone, PartialEq, Hash, Eq, PartialOrd, Ord)]
pub struct NodeDataContainer<T> {
pub internal: Vec<T>,
impl<T> From<Vec<T>> for NodeDataContainer<T> {
fn from(v: Vec<T>) -> NodeDataContainer<T> {
NodeDataContainer { internal: v }
#[derive(Debug, PartialEq, Hash, Eq, PartialOrd, Ord)]
pub struct NodeDataContainerRef<'a, T> {
pub internal: &'a [T],
pub struct NodeDataContainerRefMut<'a, T> {
pub internal: &'a mut [T],
impl<T> Default for NodeDataContainer<T> {
fn default() -> Self {
Self {
internal: Vec::new(),
impl<'a> Index<NodeId> for NodeHierarchyRef<'a> {
type Output = Node;
fn index(&self, node_id: NodeId) -> &Node {
&self.internal[node_id.index()]
impl<T> NodeDataContainer<T> {
pub const fn new(data: Vec<T>) -> Self {
pub fn is_empty(&self) -> bool {
self.internal.is_empty()
pub fn as_ref(&self) -> NodeDataContainerRef<'_, T> {
NodeDataContainerRef {
pub fn as_ref_mut(&mut self) -> NodeDataContainerRefMut<'_, T> {
NodeDataContainerRefMut {
internal: &mut self.internal[..],
impl<'a, T: 'a> NodeDataContainerRefMut<'a, T> {
pub fn from_slice(data: &'a mut [T]) -> NodeDataContainerRefMut<'a, T> {
NodeDataContainerRefMut { internal: data }
pub fn get_mut(&mut self, id: NodeId) -> Option<&mut T> {
self.internal.get_mut(id.index())
impl<'a, T: Send + 'a> NodeDataContainerRef<'a, T> {
pub fn transform_nodeid_optional<U: Send, F: Send + Sync>(
&self,
closure: F,
) -> NodeDataContainer<U>
where
F: Fn(NodeId) -> Option<U>,
{
let len = self.len();
NodeDataContainer {
internal: (0..len)
.filter_map(|node_id| closure(NodeId::new(node_id)))
.collect::<Vec<U>>(),
impl<'a, T: 'a> NodeDataContainerRef<'a, T> {
pub fn from_slice(data: &'a [T]) -> NodeDataContainerRef<'a, T> {
NodeDataContainerRef { internal: data }
pub fn get(&self, id: NodeId) -> Option<&T> {
pub fn iter(&self) -> Iter<T> {
self.internal.iter()
impl<'a, T> Index<NodeId> for NodeDataContainerRef<'a, T> {
type Output = T;
fn index(&self, node_id: NodeId) -> &T {
impl<'a, T> Index<NodeId> for NodeDataContainerRefMut<'a, T> {
impl<'a, T> IndexMut<NodeId> for NodeDataContainerRefMut<'a, T> {
fn index_mut(&mut self, node_id: NodeId) -> &mut T {
&mut self.internal[node_id.index()]
/// Return an iterator of references to this node and the siblings before it.
/// Call `.next().unwrap()` once on the iterator to skip the node itself.
pub const fn preceding_siblings<'a>(
self,
node_hierarchy: &'a NodeHierarchyRef<'a>,
) -> PrecedingSiblings<'a> {
PrecedingSiblings {
node_hierarchy,
node: Some(self),
/// Return an iterator of references to this node's children.
pub fn children<'a>(self, node_hierarchy: &'a NodeHierarchyRef<'a>) -> Children<'a> {
Children {
node: node_hierarchy[self].get_first_child(self),
macro_rules! impl_node_iterator {
($name:ident, $next:expr) => {
impl<'a> Iterator for $name<'a> {
type Item = NodeId;
fn next(&mut self) -> Option<NodeId> {
match self.node.take() {
Some(node) => {
self.node = $next(&self.node_hierarchy[node]);
Some(node)
None => None,
/// An linear iterator, does not respect the DOM in any way,
/// it just iterates over the nodes like a Vec
#[derive(Debug, Copy, Clone)]
pub struct LinearIterator {
arena_len: usize,
position: usize,
impl Iterator for LinearIterator {
if self.arena_len < 1 || self.position > (self.arena_len - 1) {
None
let new_id = Some(NodeId::new(self.position));
self.position += 1;
new_id
/// An iterator of references to the siblings before a given node.
pub struct PrecedingSiblings<'a> {
node: Option<NodeId>,
impl_node_iterator!(PrecedingSiblings, |node: &Node| node.previous_sibling);
/// Special iterator for using NodeDataContainerRef<AzNode> instead of NodeHierarchy
pub struct AzChildren<'a> {
node_hierarchy: &'a NodeDataContainerRef<'a, NodeHierarchyItem>,
impl<'a> Iterator for AzChildren<'a> {
self.node = self.node_hierarchy[node].next_sibling_id();
pub struct AzReverseChildren<'a> {
impl<'a> Iterator for AzReverseChildren<'a> {
self.node = self.node_hierarchy[node].previous_sibling_id();
/// Traverse up through the hierarchy until a node matching the predicate is found.
/// Necessary to resolve the last positioned (= relative)
/// element of an absolute node.
pub fn get_nearest_matching_parent<'a, F>(
predicate: F,
) -> Option<NodeId>
F: Fn(NodeId) -> bool,
let mut current_node = node_hierarchy[self].parent_id()?;
match predicate(current_node) {
true => {
return Some(current_node);
false => {
current_node = node_hierarchy[current_node].parent_id()?;
/// Return the children of this node (necessary for parallel iteration over children)
pub fn az_children_collect<'a>(
) -> Vec<NodeId> {
self.az_children(node_hierarchy).collect()
pub fn az_children<'a>(
) -> AzChildren<'a> {
AzChildren {
node: node_hierarchy[self].first_child_id(self),
pub fn az_reverse_children<'a>(
) -> AzReverseChildren<'a> {
AzReverseChildren {
node: node_hierarchy[self].last_child_id(),
/// An iterator of references to the children of a given node.
pub struct Children<'a> {
impl_node_iterator!(Children, |node: &Node| node.next_sibling);