Lines
100 %
Functions
72.01 %
Branches
//! 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: Self = Self { inner: 0 };
/// Creates a new `NodeId` from a zero-based index.
#[inline]
#[must_use] pub const fn new(value: usize) -> Self {
Self { 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!
#[must_use] pub const fn from_usize(value: usize) -> Option<Self> {
match value {
0 => None,
i => Some(Self { 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.
#[must_use] 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.
#[must_use] pub const fn index(&self) -> usize {
self.inner
impl From<usize> for NodeId {
fn from(val: usize) -> Self {
Self::new(val)
impl From<NodeId> for usize {
fn from(val: NodeId) -> Self {
val.inner
impl Add<usize> for NodeId {
type Output = Self;
/// AUDIT: saturating add. A raw `self.inner + other` could overflow
/// (debug panic / release wrap to a bogus small index that then aliases
/// a real node). `NodeId` indices are bounded by the arena length, so a
/// saturation to `usize::MAX` is an obviously-invalid index that fails
/// loudly at the next bounds-checked access rather than silently aliasing.
fn add(self, other: usize) -> Self {
Self::new(self.inner.saturating_add(other))
impl AddAssign<usize> for NodeId {
/// AUDIT: saturating add — see [`Add`] impl above.
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: Self = Self {
parent: None,
previous_sibling: None,
next_sibling: None,
last_child: None,
#[must_use] pub const fn has_parent(&self) -> bool {
self.parent.is_some()
#[must_use] pub const fn has_previous_sibling(&self) -> bool {
self.previous_sibling.is_some()
#[must_use] pub const fn has_next_sibling(&self) -> bool {
self.next_sibling.is_some()
#[must_use] pub const fn has_first_child(&self) -> bool {
self.last_child.is_some() /* last_child and first_child are always set together */
#[must_use] pub const fn has_last_child(&self) -> bool {
self.last_child.is_some()
#[must_use] 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 {
#[must_use] pub const fn new(data: Vec<Node>) -> Self {
Self { internal: data }
#[must_use] 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> {
#[must_use] pub const fn from_slice(data: &'a [Node]) -> Self {
NodeHierarchyRef { internal: data }
#[must_use] pub const fn len(&self) -> usize {
self.internal.len()
#[must_use] pub const fn is_empty(&self) -> bool {
self.internal.is_empty()
#[must_use] pub fn get(&self, id: NodeId) -> Option<&Node> {
self.internal.get(id.index())
#[must_use] pub const 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
// the `.drain(..)` calls intentionally empty current/next_children to REUSE
// their allocations across the BFS levels; `into_iter()` would move them.
#[allow(clippy::iter_with_drain)]
#[must_use] pub fn get_parents_sorted_by_depth(&self) -> NodeDepths {
// AUDIT: an empty hierarchy has no root node — indexing `internal[0]`
// (via `self[root]` below) would panic. Bail out early.
if self.is_empty() {
return Vec::new();
let root = NodeId::new(0);
let mut non_leaf_nodes = Vec::new();
// AUDIT: a childless root (e.g. a single-node DOM) is a LEAF, not a
// parent. The old code seeded `current_children` with the root and
// unconditionally pushed it into `non_leaf_nodes`, mislabeling it as a
// parent. Only descend (and only emit the root) when it actually has a
// first child.
if !self[root].has_first_child() {
return non_leaf_nodes;
let mut current_children = vec![(0, root)];
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;
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>) -> Self {
Self { 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 Index<NodeId> for NodeHierarchyRef<'_> {
type Output = Node;
fn index(&self, node_id: NodeId) -> &Node {
&self.internal[node_id.index()]
impl<T> NodeDataContainer<T> {
#[must_use] pub const fn new(data: Vec<T>) -> Self {
#[must_use] 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 const fn from_slice(data: &'a mut [T]) -> Self {
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>(
&self,
closure: F,
) -> NodeDataContainer<U>
where
F: Send + Sync + 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> IntoIterator for &NodeDataContainerRef<'a, T> {
type Item = &'a T;
type IntoIter = Iter<'a, T>;
fn into_iter(self) -> Self::IntoIter {
self.internal.iter()
impl<'a, T: 'a> NodeDataContainerRef<'a, T> {
pub const fn from_slice(data: &'a [T]) -> Self {
NodeDataContainerRef { internal: data }
#[must_use] pub fn get(&self, id: NodeId) -> Option<&T> {
pub fn iter(&self) -> Iter<'_, T> {
impl<T> Index<NodeId> for NodeDataContainerRef<'_, T> {
type Output = T;
fn index(&self, node_id: NodeId) -> &T {
impl<T> Index<NodeId> for NodeDataContainerRefMut<'_, T> {
impl<T> IndexMut<NodeId> for NodeDataContainerRefMut<'_, 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.
#[must_use] 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.
#[must_use] 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 Iterator for $name<'_> {
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, 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
} else {
let new_id = Some(NodeId::new(self.position));
self.position += 1;
new_id
/// An iterator of references to the siblings before a given node.
#[derive(Debug)]
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 Iterator for AzChildren<'_> {
self.node = self.node_hierarchy[node].next_sibling_id();
pub struct AzReverseChildren<'a> {
impl Iterator for AzReverseChildren<'_> {
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<Self>
F: Fn(Self) -> bool,
// AUDIT: guard against (a) an out-of-bounds `self` and (b) a cycle in a
// corrupt hierarchy (a `parent_id` that points back down into a
// descendant). Use checked `get` and cap the walk at the node count —
// a valid parent chain can never be longer than the number of nodes.
let node_count = node_hierarchy.internal.len();
let mut current_node = node_hierarchy.internal.get(self.index())?.parent_id()?;
for _ in 0..node_count {
if predicate(current_node) {
return Some(current_node);
current_node = node_hierarchy.internal.get(current_node.index())?.parent_id()?;
/// Return the children of this node (necessary for parallel iteration over children)
#[must_use] pub fn az_children_collect<'a>(
) -> Vec<Self> {
self.az_children(node_hierarchy).collect()
#[must_use] pub fn az_children<'a>(
) -> AzChildren<'a> {
AzChildren {
node: node_hierarchy[self].first_child_id(self),
#[must_use] 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);
#[cfg(test)]
mod audit_tests {
use super::*;
#[test]
fn parents_by_depth_empty_hierarchy() {
let h = NodeHierarchy::new(Vec::new());
assert!(h.as_ref().get_parents_sorted_by_depth().is_empty());
fn parents_by_depth_single_childless_root() {
// A single-node DOM: the root is a LEAF, not a parent.
let h = NodeHierarchy::new(vec![Node::ROOT]);
fn parents_by_depth_root_with_child() {
let root = Node {
last_child: Some(NodeId::new(1)),
let child = Node {
parent: Some(NodeId::new(0)),
..Node::ROOT
let h = NodeHierarchy::new(vec![root, child]);
let parents = h.as_ref().get_parents_sorted_by_depth();
assert_eq!(parents, vec![(0, NodeId::new(0))]);
fn item(parent: Option<usize>) -> NodeHierarchyItem {
NodeHierarchyItem {
parent: parent.map_or(0, |p| p + 1),
previous_sibling: 0,
next_sibling: 0,
last_child: 0,
fn nearest_matching_parent_cycle_terminates() {
// node1.parent = 2, node2.parent = 1 — cyclic, must not hang.
let items = vec![item(None), item(Some(2)), item(Some(1))];
let cont = NodeDataContainerRef { internal: &items };
let r = NodeId::new(1).get_nearest_matching_parent(&cont, |_| false);
assert_eq!(r, None);
fn nearest_matching_parent_finds_match() {
// 0 <- 1 <- 2 ; from 2, find the root (index 0).
let items = vec![item(None), item(Some(0)), item(Some(1))];
let r = NodeId::new(2).get_nearest_matching_parent(&cont, |n| n == NodeId::new(0));
assert_eq!(r, Some(NodeId::new(0)));
fn node_id_add_saturates() {
assert_eq!(NodeId::new(5) + 3, NodeId::new(8));
assert_eq!(NodeId::new(usize::MAX) + 1, NodeId::new(usize::MAX));
let mut n = NodeId::new(usize::MAX);
n += 10;
assert_eq!(n, NodeId::new(usize::MAX));
#[allow(clippy::pedantic, clippy::nursery)]
mod autotest_generated {
use core::sync::atomic::{AtomicUsize, Ordering};
// ---------------------------------------------------------------------
// helpers
/// A well-formed 5-node tree (children are always contiguous after the
/// parent, as the `first_child = parent + 1` design requires):
/// ```text
/// 0 ── 1 ── 2
/// │ └── 3
/// └── 4
/// ```
fn tree_5() -> Vec<Node> {
vec![
Node {
last_child: Some(NodeId::new(4)),
},
next_sibling: Some(NodeId::new(4)),
last_child: Some(NodeId::new(3)),
parent: Some(NodeId::new(1)),
next_sibling: Some(NodeId::new(3)),
previous_sibling: Some(NodeId::new(2)),
previous_sibling: Some(NodeId::new(1)),
]
fn items(nodes: &[Node]) -> Vec<NodeHierarchyItem> {
nodes.iter().copied().map(NodeHierarchyItem::from).collect()
// NodeId::new / index / ZERO (constructor + getter)
fn node_id_new_roundtrips_index_at_boundaries() {
for v in [0_usize, 1, 2, 42, usize::MAX - 1, usize::MAX] {
assert_eq!(NodeId::new(v).index(), v, "index() must echo new()");
fn node_id_zero_matches_new_zero() {
assert_eq!(NodeId::ZERO, NodeId::new(0));
assert_eq!(NodeId::ZERO.index(), 0);
fn node_id_usize_conversions_are_lossless() {
for v in [0_usize, 7, usize::MAX] {
let id: NodeId = v.into();
let back: usize = id.into();
assert_eq!(back, v);
fn node_id_ordering_follows_index() {
assert!(NodeId::new(0) < NodeId::new(1));
assert!(NodeId::new(1) < NodeId::new(usize::MAX));
assert_eq!(NodeId::new(3), NodeId::new(3));
// NodeId::from_usize / into_raw (1-based FFI encoding round-trip)
fn from_usize_zero_is_none_and_shifts_by_one() {
assert_eq!(NodeId::from_usize(0), None);
assert_eq!(NodeId::from_usize(1), Some(NodeId::new(0)));
assert_eq!(NodeId::from_usize(2), Some(NodeId::new(1)));
// usize::MAX must NOT overflow the `i - 1` decode.
assert_eq!(
NodeId::from_usize(usize::MAX),
Some(NodeId::new(usize::MAX - 1))
);
fn into_raw_encodes_none_as_zero() {
assert_eq!(NodeId::into_raw(&None), 0);
assert_eq!(NodeId::into_raw(&Some(NodeId::new(0))), 1);
assert_eq!(NodeId::into_raw(&Some(NodeId::new(41))), 42);
// Largest index that survives the +1 encode without overflowing.
assert_eq!(NodeId::into_raw(&Some(NodeId::new(usize::MAX - 1))), usize::MAX);
fn encode_decode_roundtrip_is_identity() {
// decode(encode(x)) == x
for x in [
None,
Some(NodeId::new(0)),
Some(NodeId::new(1)),
Some(NodeId::new(9_999)),
Some(NodeId::new(usize::MAX - 1)),
] {
assert_eq!(NodeId::from_usize(NodeId::into_raw(&x)), x, "decode(encode({x:?}))");
// encode(decode(n)) == n
for n in [0_usize, 1, 2, 12_345, usize::MAX] {
assert_eq!(NodeId::into_raw(&NodeId::from_usize(n)), n, "encode(decode({n}))");
/// BOUNDARY: `NodeId::new(usize::MAX)` is the one index that cannot be
/// encoded — `into_raw` computes `inner + 1`, which overflows. Unlike the
/// `Add`/`AddAssign` impls (which were deliberately made saturating), this
/// add is unchecked: debug builds panic, release builds wrap to `0`, i.e.
/// the `None` encoding. Either way the node is lost; assert that it never
/// silently produces some *other* valid-looking node id.
#[cfg(feature = "std")]
fn into_raw_at_usize_max_never_yields_a_bogus_node() {
let encoded = std::panic::catch_unwind(|| NodeId::into_raw(&Some(NodeId::new(usize::MAX))));
match encoded {
// debug: overflow check fires — loud failure, acceptable.
Err(_) => {}
// release: wraps to 0 == the "no node" encoding.
Ok(raw) => {
assert_eq!(raw, 0, "wrapped encode must not alias a real node id");
assert_eq!(NodeId::from_usize(raw), None);
// NodeId Display / Debug (serializer)
fn node_id_display_and_debug_are_well_formed() {
assert_eq!(alloc::format!("{}", NodeId::new(0)), "0");
assert_eq!(alloc::format!("{}", NodeId::new(7)), "7");
assert_eq!(alloc::format!("{:?}", NodeId::new(7)), "NodeId(7)");
// Extreme values must render without panicking and stay non-empty.
let max = alloc::format!("{}", NodeId::new(usize::MAX));
assert_eq!(max, alloc::format!("{}", usize::MAX));
assert!(!max.is_empty());
alloc::format!("{:?}", NodeId::new(usize::MAX)),
alloc::format!("NodeId({})", usize::MAX)
// Node predicates + get_first_child
fn node_root_and_default_have_no_relations() {
for n in [Node::ROOT, Node::default()] {
assert!(!n.has_parent());
assert!(!n.has_previous_sibling());
assert!(!n.has_next_sibling());
assert!(!n.has_first_child());
assert!(!n.has_last_child());
assert_eq!(n.get_first_child(NodeId::new(0)), None);
assert_eq!(Node::default(), Node::ROOT);
fn node_predicates_report_each_populated_field() {
let full = Node {
assert!(full.has_parent());
assert!(full.has_previous_sibling());
assert!(full.has_next_sibling());
assert!(full.has_first_child());
assert!(full.has_last_child());
/// INVARIANT: `has_first_child()` and `has_last_child()` read the same
/// field, so they can never disagree — child-presence is all-or-nothing.
fn has_first_child_always_agrees_with_has_last_child() {
for last_child in [None, Some(NodeId::new(0)), Some(NodeId::new(usize::MAX))] {
let n = Node {
last_child,
assert_eq!(n.has_first_child(), n.has_last_child());
assert_eq!(n.has_first_child(), last_child.is_some());
fn get_first_child_is_self_plus_one_and_saturates() {
let parent = Node {
last_child: Some(NodeId::new(9)),
assert_eq!(parent.get_first_child(NodeId::new(0)), Some(NodeId::new(1)));
assert_eq!(parent.get_first_child(NodeId::new(5)), Some(NodeId::new(6)));
// Extreme id: the `+ 1` is saturating, so this must not panic/wrap. It
// yields an obviously-invalid id that fails loudly at the next lookup.
parent.get_first_child(NodeId::new(usize::MAX)),
Some(NodeId::new(usize::MAX))
// A leaf has no first child regardless of how extreme the id is.
assert_eq!(Node::ROOT.get_first_child(NodeId::new(usize::MAX)), None);
// NodeHierarchy / NodeHierarchyRef
fn hierarchy_new_preserves_len_and_contents() {
let h = NodeHierarchy::new(tree_5());
assert_eq!(h.as_ref().len(), 5);
assert!(!h.as_ref().is_empty());
assert_eq!(h.as_ref().get(NodeId::new(0)), Some(&tree_5()[0]));
assert_eq!(h.as_ref().internal, &tree_5()[..]);
fn empty_hierarchy_is_empty_everywhere() {
let r = h.as_ref();
assert_eq!(r.len(), 0);
assert!(r.is_empty());
assert_eq!(r.get(NodeId::new(0)), None);
assert_eq!(r.linear_iter().count(), 0);
assert!(r.get_parents_sorted_by_depth().is_empty());
let default = NodeHierarchy::default();
assert!(default.as_ref().is_empty());
fn hierarchy_ref_from_slice_matches_len_and_emptiness() {
let empty: [Node; 0] = [];
assert_eq!(NodeHierarchyRef::from_slice(&empty).len(), 0);
assert!(NodeHierarchyRef::from_slice(&empty).is_empty());
let nodes = tree_5();
let r = NodeHierarchyRef::from_slice(&nodes);
assert_eq!(r.len(), 5);
assert!(!r.is_empty());
/// `get()` is the bounds-checked accessor: an out-of-range id must return
/// `None`, never panic and never read out of bounds.
fn hierarchy_ref_get_out_of_bounds_returns_none() {
assert!(r.get(NodeId::new(4)).is_some());
assert_eq!(r.get(NodeId::new(5)), None);
assert_eq!(r.get(NodeId::new(usize::MAX)), None);
/// `Index` (unlike `get`) is unchecked-by-contract: it must fail loudly
/// rather than silently hand back an unrelated node.
#[should_panic]
fn hierarchy_ref_index_out_of_bounds_panics() {
let _ = &r[NodeId::new(5)];
fn hierarchy_linear_iter_walks_every_index_in_order() {
let ids: Vec<NodeId> = r.linear_iter().collect();
ids,
(0..5).map(NodeId::new).collect::<Vec<_>>(),
"linear_iter must yield 0..len exactly once, in order"
/// The `arena_len < 1` guard exists because `arena_len - 1` would underflow
/// on an empty arena; check the 0- and 1-element boundaries explicitly.
fn linear_iter_len_zero_and_one_boundaries() {
NodeHierarchyRef::from_slice(&empty).linear_iter().next(),
let one = [Node::ROOT];
let mut it = NodeHierarchyRef::from_slice(&one).linear_iter();
assert_eq!(it.next(), Some(NodeId::new(0)));
assert_eq!(it.next(), None);
// Exhausted iterators stay exhausted.
fn get_parents_sorted_by_depth_is_depth_ordered_and_leaf_free() {
// Only 0 and 1 have children; 2/3/4 are leaves and must not appear.
assert_eq!(parents, vec![(0, NodeId::new(0)), (1, NodeId::new(1))]);
// Depths must be non-decreasing.
assert!(parents.windows(2).all(|w| w[0].0 <= w[1].0));
// NodeId::children / preceding_siblings (NodeHierarchyRef iterators)
fn children_yields_direct_children_only() {
NodeId::new(0).children(&r).collect::<Vec<_>>(),
vec![NodeId::new(1), NodeId::new(4)]
NodeId::new(1).children(&r).collect::<Vec<_>>(),
vec![NodeId::new(2), NodeId::new(3)]
// Leaves have no children.
assert_eq!(NodeId::new(2).children(&r).count(), 0);
assert_eq!(NodeId::new(4).children(&r).count(), 0);
fn children_of_out_of_bounds_node_panics_loudly() {
// `children()` indexes the hierarchy directly — an id past the end must
// abort rather than fabricate a child list.
let _ = NodeId::new(99).children(&r);
fn preceding_siblings_starts_with_self_then_walks_backwards() {
NodeId::new(3).preceding_siblings(&r).collect::<Vec<_>>(),
vec![NodeId::new(3), NodeId::new(2)],
"the iterator includes the node itself first"
// A first-born has only itself.
NodeId::new(2).preceding_siblings(&r).collect::<Vec<_>>(),
vec![NodeId::new(2)]
/// ADVERSARIAL: a corrupt hierarchy whose `previous_sibling` points at the
/// node itself makes the iterator cycle forever. It must not panic — but a
/// caller that `collect()`s it would hang, so only ever take a bounded
/// prefix from an untrusted hierarchy.
fn preceding_siblings_on_self_cycle_repeats_without_panicking() {
let nodes = vec![
Node::ROOT,
previous_sibling: Some(NodeId::new(1)), // points at itself
];
let first_4: Vec<NodeId> = NodeId::new(1).preceding_siblings(&r).take(4).collect();
assert_eq!(first_4, vec![NodeId::new(1); 4]);
// NodeDataContainer / Ref / RefMut
fn data_container_new_and_len_track_the_vec() {
let c = NodeDataContainer::new(vec![10_u32, 20, 30]);
assert_eq!(c.len(), 3);
assert!(!c.is_empty());
assert_eq!(c.as_ref().len(), 3);
assert_eq!(c.as_ref().get(NodeId::new(2)), Some(&30));
let empty: NodeDataContainer<u32> = NodeDataContainer::new(Vec::new());
assert_eq!(empty.len(), 0);
assert!(empty.is_empty());
assert!(empty.as_ref().is_empty());
assert_eq!(empty.as_ref().get(NodeId::new(0)), None);
// Default and From<Vec<T>> agree with the explicit constructor.
assert!(NodeDataContainer::<u32>::default().is_empty());
assert_eq!(NodeDataContainer::from(vec![1_u32, 2]).len(), 2);
fn data_container_ref_get_out_of_bounds_returns_none() {
let data = [1_u8, 2, 3];
let r = NodeDataContainerRef::from_slice(&data);
assert_eq!(r.get(NodeId::new(0)), Some(&1));
assert_eq!(r.get(NodeId::new(3)), None);
fn data_container_ref_index_out_of_bounds_panics() {
let _ = &r[NodeId::new(3)];
fn data_container_ref_iterators_cover_all_elements() {
assert_eq!(r.iter().copied().collect::<Vec<_>>(), vec![1, 2, 3]);
assert_eq!((&r).into_iter().copied().collect::<Vec<_>>(), vec![1, 2, 3]);
assert_eq!(r.linear_iter().count(), 3);
let empty: [u8; 0] = [];
let e = NodeDataContainerRef::from_slice(&empty);
assert_eq!(e.len(), 0);
assert!(e.is_empty());
assert_eq!(e.iter().count(), 0);
assert_eq!(e.linear_iter().next(), None);
fn data_container_ref_mut_get_mut_is_bounds_checked() {
let mut c = NodeDataContainer::new(vec![1_u32, 2, 3]);
let mut m = c.as_ref_mut();
assert_eq!(m.get_mut(NodeId::new(3)), None);
assert_eq!(m.get_mut(NodeId::new(usize::MAX)), None);
*m.get_mut(NodeId::new(1)).unwrap() = 99;
m[NodeId::new(2)] = 7;
assert_eq!(m[NodeId::new(2)], 7);
assert_eq!(c.internal, vec![1, 99, 7]);
fn data_container_ref_mut_from_slice_on_empty_slice() {
let mut empty: [u32; 0] = [];
let mut m = NodeDataContainerRefMut::from_slice(&mut empty);
assert_eq!(m.get_mut(NodeId::new(0)), None);
assert!(m.internal.is_empty());
fn data_container_ref_mut_index_out_of_bounds_panics() {
let mut data = [1_u8, 2];
let m = NodeDataContainerRefMut::from_slice(&mut data);
let _ = &m[NodeId::new(2)];
// transform_nodeid_optional
fn transform_nodeid_optional_maps_every_index() {
let data = [0_u32; 4];
let out = r.transform_nodeid_optional(|id| Some(id.index() as u32 * 10));
assert_eq!(out.internal, vec![0, 10, 20, 30]);
assert_eq!(out.len(), r.len());
fn transform_nodeid_optional_empty_input_never_calls_the_closure() {
let empty: [u32; 0] = [];
let r = NodeDataContainerRef::from_slice(&empty);
let calls = AtomicUsize::new(0);
let out = r.transform_nodeid_optional(|_| {
calls.fetch_add(1, Ordering::SeqCst);
Some(1_u32)
});
assert_eq!(calls.load(Ordering::SeqCst), 0);
assert!(out.is_empty());
/// CONTRACT TRAP: `None` results are *filtered out*, so the output is
/// COMPACTED — it is shorter than the input and its positions no longer
/// line up with the `NodeId`s that produced them. Indexing the result by a
/// `NodeId` therefore reads the wrong element (or goes out of bounds).
/// Pinned here so the aliasing behaviour can't change silently.
fn transform_nodeid_optional_compacts_and_breaks_nodeid_alignment() {
let data = [0_u32; 5];
// Keep only even node ids: 0, 2, 4.
let out = r.transform_nodeid_optional(|id| {
if id.index() % 2 == 0 {
Some(id.index() as u32)
assert_eq!(out.len(), 3, "output is compacted, NOT padded to the input len");
assert_eq!(out.internal, vec![0, 2, 4]);
// Position 1 holds node 2's value — the result is not index-aligned.
assert_eq!(out.as_ref().get(NodeId::new(1)), Some(&2));
assert_eq!(out.as_ref().get(NodeId::new(4)), None);
// All-None closure yields an empty container rather than panicking.
let none_out = r.transform_nodeid_optional(|_| -> Option<u32> { None });
assert!(none_out.is_empty());
// NodeId::az_children / az_reverse_children / az_children_collect
fn az_children_walks_forwards_and_reverse_walks_backwards() {
let it = items(&nodes);
let h = NodeDataContainerRef::from_slice(&it);
NodeId::new(0).az_children_collect(&h),
NodeId::new(1).az_children(&h).collect::<Vec<_>>(),
NodeId::new(1).az_reverse_children(&h).collect::<Vec<_>>(),
"reverse iteration starts at last_child and walks previous_sibling"
// Leaves yield nothing in either direction.
assert_eq!(NodeId::new(2).az_children(&h).count(), 0);
assert_eq!(NodeId::new(2).az_reverse_children(&h).count(), 0);
assert!(NodeId::new(3).az_children_collect(&h).is_empty());
fn az_children_of_out_of_bounds_node_panics_loudly() {
let _ = NodeId::new(5).az_children(&h);
/// ADVERSARIAL: a `next_sibling` that points back at the node itself makes
/// `az_children` an infinite iterator. It must not panic, but
/// `az_children_collect` on such a hierarchy would allocate until OOM —
/// so only a bounded prefix is taken here.
fn az_children_on_sibling_cycle_repeats_without_panicking() {
next_sibling: Some(NodeId::new(1)), // points at itself
let prefix: Vec<NodeId> = NodeId::new(0).az_children(&h).take(5).collect();
assert_eq!(prefix, vec![NodeId::new(1); 5]);
// NodeId::get_nearest_matching_parent
fn nearest_matching_parent_skips_non_matching_ancestors() {
// From node 2, the first ancestor is 1, then the root 0.
NodeId::new(2).get_nearest_matching_parent(&h, |_| true),
Some(NodeId::new(1))
NodeId::new(2).get_nearest_matching_parent(&h, |n| n == NodeId::new(0)),
Some(NodeId::new(0))
// The root has no parent at all.
NodeId::new(0).get_nearest_matching_parent(&h, |_| true),
// Nothing matches -> None, and the walk terminates.
NodeId::new(3).get_nearest_matching_parent(&h, |_| false),
fn nearest_matching_parent_out_of_bounds_self_returns_none() {
NodeId::new(5).get_nearest_matching_parent(&h, |_| true),
NodeId::new(usize::MAX).get_nearest_matching_parent(&h, |_| true),
fn nearest_matching_parent_self_parent_cycle_terminates() {
// node 1 is its own parent — the node-count cap must break the loop.
NodeId::new(1).get_nearest_matching_parent(&h, |_| false),
/// ADVERSARIAL: a corrupt `parent` index that points past the end of the
/// arena. The lookup must not panic. Note the predicate is still called
/// with that out-of-bounds id, so a permissive predicate hands the caller
/// back an id that will panic when used to index the arena — callers must
/// bounds-check the returned id, not assume it is valid.
fn nearest_matching_parent_out_of_bounds_ancestor_does_not_panic() {
parent: Some(NodeId::new(99)), // dangling
// Rejecting predicate: the dangling id fails the `get()` and yields None.
// Accepting predicate: the dangling id is returned as-is.
NodeId::new(1).get_nearest_matching_parent(&h, |_| true),
Some(NodeId::new(99))
assert!(h.get(NodeId::new(99)).is_none(), "and it is NOT a valid index");