fop_core/tree/
arena.rs

1//! Arena allocator for FO tree nodes
2//!
3//! Uses index-based handles instead of Rc<RefCell<>> for better performance
4//! and memory efficiency.
5
6use super::id_registry::IdRegistry;
7use super::node::FoNode;
8use std::fmt;
9
10/// Index-based handle to a node in the arena
11#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
12pub struct NodeId(usize);
13
14impl NodeId {
15    /// Get the raw index value
16    #[inline]
17    pub fn index(self) -> usize {
18        self.0
19    }
20
21    /// Create a NodeId from a raw index (unsafe - use with caution)
22    #[inline]
23    pub const fn from_index(index: usize) -> Self {
24        Self(index)
25    }
26}
27
28impl fmt::Display for NodeId {
29    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
30        write!(f, "Node({})", self.0)
31    }
32}
33
34/// Arena allocator for FO tree nodes
35///
36/// Stores all nodes in a contiguous vector for cache efficiency.
37/// Nodes are accessed by index-based handles (NodeId).
38pub struct FoArena<'a> {
39    nodes: Vec<FoNode<'a>>,
40    id_registry: IdRegistry,
41    /// Document language from xml:lang on fo:root (e.g. "en", "ja")
42    pub document_lang: Option<String>,
43}
44
45impl<'a> FoArena<'a> {
46    /// Create a new empty arena
47    pub fn new() -> Self {
48        Self {
49            nodes: Vec::new(),
50            id_registry: IdRegistry::new(),
51            document_lang: None,
52        }
53    }
54
55    /// Create a new arena with preallocated capacity
56    pub fn with_capacity(capacity: usize) -> Self {
57        Self {
58            nodes: Vec::with_capacity(capacity),
59            id_registry: IdRegistry::new(),
60            document_lang: None,
61        }
62    }
63
64    /// Get a reference to the ID registry
65    pub fn id_registry(&self) -> &IdRegistry {
66        &self.id_registry
67    }
68
69    /// Get a mutable reference to the ID registry
70    pub fn id_registry_mut(&mut self) -> &mut IdRegistry {
71        &mut self.id_registry
72    }
73
74    /// Add a node to the arena and return its ID
75    pub fn add_node(&mut self, node: FoNode<'a>) -> NodeId {
76        let id = NodeId(self.nodes.len());
77        self.nodes.push(node);
78        id
79    }
80
81    /// Get a reference to a node by ID
82    pub fn get(&self, id: NodeId) -> Option<&FoNode<'a>> {
83        self.nodes.get(id.0)
84    }
85
86    /// Get a mutable reference to a node by ID
87    pub fn get_mut(&mut self, id: NodeId) -> Option<&mut FoNode<'a>> {
88        self.nodes.get_mut(id.0)
89    }
90
91    /// Get the number of nodes in the arena
92    #[inline]
93    pub fn len(&self) -> usize {
94        self.nodes.len()
95    }
96
97    /// Check if the arena is empty
98    #[inline]
99    pub fn is_empty(&self) -> bool {
100        self.nodes.is_empty()
101    }
102
103    /// Iterate over all nodes
104    pub fn iter(&self) -> impl Iterator<Item = (NodeId, &FoNode<'a>)> {
105        self.nodes
106            .iter()
107            .enumerate()
108            .map(|(i, node)| (NodeId(i), node))
109    }
110
111    /// Get the root node (first node in arena)
112    pub fn root(&self) -> Option<(NodeId, &FoNode<'a>)> {
113        if self.nodes.is_empty() {
114            None
115        } else {
116            Some((NodeId(0), &self.nodes[0]))
117        }
118    }
119
120    /// Set parent-child relationship
121    pub fn set_parent(&mut self, child: NodeId, parent: NodeId) -> Result<(), String> {
122        if child.0 >= self.nodes.len() {
123            return Err(format!("Child node {} does not exist", child.0));
124        }
125        if parent.0 >= self.nodes.len() {
126            return Err(format!("Parent node {} does not exist", parent.0));
127        }
128
129        // Set parent of child
130        self.nodes[child.0].parent = Some(parent);
131
132        Ok(())
133    }
134
135    /// Append a child to a parent node
136    pub fn append_child(&mut self, parent: NodeId, child: NodeId) -> Result<(), String> {
137        if child.0 >= self.nodes.len() {
138            return Err(format!("Child node {} does not exist", child.0));
139        }
140        if parent.0 >= self.nodes.len() {
141            return Err(format!("Parent node {} does not exist", parent.0));
142        }
143
144        // Set parent of child
145        self.nodes[child.0].parent = Some(parent);
146
147        // Update parent's children list
148        let parent_node = &mut self.nodes[parent.0];
149        if let Some(first_child) = parent_node.first_child {
150            // Find last sibling and append
151            let mut last_sibling = first_child;
152            while let Some(next) = self.nodes[last_sibling.0].next_sibling {
153                last_sibling = next;
154            }
155            self.nodes[last_sibling.0].next_sibling = Some(child);
156        } else {
157            // First child
158            parent_node.first_child = Some(child);
159        }
160
161        Ok(())
162    }
163
164    /// Get all children of a node
165    pub fn children(&self, parent: NodeId) -> Vec<NodeId> {
166        let mut children = Vec::new();
167        if let Some(node) = self.get(parent) {
168            let mut current = node.first_child;
169            while let Some(child_id) = current {
170                children.push(child_id);
171                current = self.get(child_id).and_then(|n| n.next_sibling);
172            }
173        }
174        children
175    }
176
177    /// Get the depth of a node in the tree
178    pub fn depth(&self, mut node: NodeId) -> usize {
179        let mut depth = 0;
180        while let Some(parent) = self.get(node).and_then(|n| n.parent) {
181            depth += 1;
182            node = parent;
183        }
184        depth
185    }
186}
187
188impl<'a> Default for FoArena<'a> {
189    fn default() -> Self {
190        Self::new()
191    }
192}
193
194#[cfg(test)]
195mod tests {
196    use super::*;
197    use crate::tree::node::FoNodeData;
198
199    #[test]
200    fn test_arena_creation() {
201        let arena: FoArena = FoArena::new();
202        assert_eq!(arena.len(), 0);
203        assert!(arena.is_empty());
204    }
205
206    #[test]
207    fn test_add_node() {
208        let mut arena = FoArena::new();
209        let node = FoNode::new(FoNodeData::Root);
210        let id = arena.add_node(node);
211
212        assert_eq!(arena.len(), 1);
213        assert_eq!(id.index(), 0);
214        assert!(arena.get(id).is_some());
215    }
216
217    #[test]
218    fn test_parent_child() {
219        let mut arena = FoArena::new();
220
221        // Create root and child nodes
222        let root = arena.add_node(FoNode::new(FoNodeData::Root));
223        let child = arena.add_node(FoNode::new(FoNodeData::Block {
224            properties: crate::properties::PropertyList::new(),
225        }));
226
227        // Set up relationship
228        arena
229            .append_child(root, child)
230            .expect("test: should succeed");
231
232        // Verify relationship
233        assert_eq!(
234            arena.get(child).expect("test: should succeed").parent,
235            Some(root)
236        );
237        assert_eq!(
238            arena.get(root).expect("test: should succeed").first_child,
239            Some(child)
240        );
241    }
242
243    #[test]
244    fn test_multiple_children() {
245        let mut arena = FoArena::new();
246
247        let root = arena.add_node(FoNode::new(FoNodeData::Root));
248        let child1 = arena.add_node(FoNode::new(FoNodeData::Block {
249            properties: crate::properties::PropertyList::new(),
250        }));
251        let child2 = arena.add_node(FoNode::new(FoNodeData::Block {
252            properties: crate::properties::PropertyList::new(),
253        }));
254        let child3 = arena.add_node(FoNode::new(FoNodeData::Block {
255            properties: crate::properties::PropertyList::new(),
256        }));
257
258        arena
259            .append_child(root, child1)
260            .expect("test: should succeed");
261        arena
262            .append_child(root, child2)
263            .expect("test: should succeed");
264        arena
265            .append_child(root, child3)
266            .expect("test: should succeed");
267
268        let children = arena.children(root);
269        assert_eq!(children.len(), 3);
270        assert_eq!(children[0], child1);
271        assert_eq!(children[1], child2);
272        assert_eq!(children[2], child3);
273    }
274
275    #[test]
276    fn test_depth() {
277        let mut arena = FoArena::new();
278
279        let root = arena.add_node(FoNode::new(FoNodeData::Root));
280        let child = arena.add_node(FoNode::new(FoNodeData::Block {
281            properties: crate::properties::PropertyList::new(),
282        }));
283        let grandchild = arena.add_node(FoNode::new(FoNodeData::Inline {
284            properties: crate::properties::PropertyList::new(),
285        }));
286
287        arena
288            .append_child(root, child)
289            .expect("test: should succeed");
290        arena
291            .append_child(child, grandchild)
292            .expect("test: should succeed");
293
294        assert_eq!(arena.depth(root), 0);
295        assert_eq!(arena.depth(child), 1);
296        assert_eq!(arena.depth(grandchild), 2);
297    }
298
299    #[test]
300    fn test_iteration() {
301        let mut arena = FoArena::new();
302
303        arena.add_node(FoNode::new(FoNodeData::Root));
304        arena.add_node(FoNode::new(FoNodeData::Block {
305            properties: crate::properties::PropertyList::new(),
306        }));
307        arena.add_node(FoNode::new(FoNodeData::Inline {
308            properties: crate::properties::PropertyList::new(),
309        }));
310
311        let count = arena.iter().count();
312        assert_eq!(count, 3);
313    }
314
315    #[test]
316    fn test_node_id_display() {
317        let id = NodeId::from_index(42);
318        assert_eq!(format!("{}", id), "Node(42)");
319    }
320
321    #[test]
322    fn test_node_id_equality() {
323        let id1 = NodeId::from_index(5);
324        let id2 = NodeId::from_index(5);
325        let id3 = NodeId::from_index(6);
326        assert_eq!(id1, id2);
327        assert_ne!(id1, id3);
328    }
329
330    #[test]
331    fn test_node_id_copy() {
332        let id1 = NodeId::from_index(3);
333        let id2 = id1;
334        assert_eq!(id1.index(), id2.index());
335    }
336
337    #[test]
338    fn test_with_capacity() {
339        let arena: FoArena = FoArena::with_capacity(64);
340        assert!(arena.is_empty());
341        assert_eq!(arena.len(), 0);
342    }
343
344    #[test]
345    fn test_default() {
346        let arena: FoArena = FoArena::default();
347        assert!(arena.is_empty());
348    }
349
350    #[test]
351    fn test_root_on_empty_arena() {
352        let arena: FoArena = FoArena::new();
353        assert!(arena.root().is_none());
354    }
355
356    #[test]
357    fn test_root_returns_first_node() {
358        let mut arena = FoArena::new();
359        let root_id = arena.add_node(FoNode::new(FoNodeData::Root));
360        arena.add_node(FoNode::new(FoNodeData::LayoutMasterSet));
361
362        let (id, node) = arena.root().expect("test: should succeed");
363        assert_eq!(id, root_id);
364        assert!(matches!(node.data, FoNodeData::Root));
365    }
366
367    #[test]
368    fn test_get_invalid_id() {
369        let arena: FoArena = FoArena::new();
370        let invalid = NodeId::from_index(999);
371        assert!(arena.get(invalid).is_none());
372    }
373
374    #[test]
375    fn test_get_mut_invalid_id() {
376        let mut arena: FoArena = FoArena::new();
377        let invalid = NodeId::from_index(999);
378        assert!(arena.get_mut(invalid).is_none());
379    }
380
381    #[test]
382    fn test_set_parent_invalid_child() {
383        let mut arena = FoArena::new();
384        let root = arena.add_node(FoNode::new(FoNodeData::Root));
385        let invalid = NodeId::from_index(999);
386        assert!(arena.set_parent(invalid, root).is_err());
387    }
388
389    #[test]
390    fn test_set_parent_invalid_parent() {
391        let mut arena = FoArena::new();
392        let child = arena.add_node(FoNode::new(FoNodeData::Root));
393        let invalid = NodeId::from_index(999);
394        assert!(arena.set_parent(child, invalid).is_err());
395    }
396
397    #[test]
398    fn test_append_child_invalid_child() {
399        let mut arena = FoArena::new();
400        let root = arena.add_node(FoNode::new(FoNodeData::Root));
401        let invalid = NodeId::from_index(999);
402        assert!(arena.append_child(root, invalid).is_err());
403    }
404
405    #[test]
406    fn test_append_child_invalid_parent() {
407        let mut arena = FoArena::new();
408        let child = arena.add_node(FoNode::new(FoNodeData::Root));
409        let invalid = NodeId::from_index(999);
410        assert!(arena.append_child(invalid, child).is_err());
411    }
412
413    #[test]
414    fn test_children_of_leaf() {
415        let mut arena = FoArena::new();
416        let root = arena.add_node(FoNode::new(FoNodeData::Root));
417        let children = arena.children(root);
418        assert!(children.is_empty());
419    }
420
421    #[test]
422    fn test_document_lang() {
423        let mut arena: FoArena = FoArena::new();
424        assert!(arena.document_lang.is_none());
425        arena.document_lang = Some("en".to_string());
426        assert_eq!(arena.document_lang.as_deref(), Some("en"));
427    }
428
429    #[test]
430    fn test_id_registry() {
431        let arena: FoArena = FoArena::new();
432        // id_registry() is accessible and returns a valid reference
433        let _reg = arena.id_registry();
434    }
435
436    #[test]
437    fn test_id_registry_mut() {
438        let mut arena: FoArena = FoArena::new();
439        let _reg = arena.id_registry_mut();
440    }
441
442    #[test]
443    fn test_iter_yields_correct_ids() {
444        let mut arena = FoArena::new();
445        let id0 = arena.add_node(FoNode::new(FoNodeData::Root));
446        let id1 = arena.add_node(FoNode::new(FoNodeData::LayoutMasterSet));
447
448        let items: Vec<_> = arena.iter().collect();
449        assert_eq!(items.len(), 2);
450        assert_eq!(items[0].0, id0);
451        assert_eq!(items[1].0, id1);
452    }
453
454    #[test]
455    fn test_depth_three_levels() {
456        let mut arena = FoArena::new();
457        let root = arena.add_node(FoNode::new(FoNodeData::Root));
458        let child = arena.add_node(FoNode::new(FoNodeData::Block {
459            properties: crate::properties::PropertyList::new(),
460        }));
461        let grandchild = arena.add_node(FoNode::new(FoNodeData::Inline {
462            properties: crate::properties::PropertyList::new(),
463        }));
464        let great_grandchild = arena.add_node(FoNode::new(FoNodeData::Text("hi".to_string())));
465
466        arena
467            .append_child(root, child)
468            .expect("test: should succeed");
469        arena
470            .append_child(child, grandchild)
471            .expect("test: should succeed");
472        arena
473            .append_child(grandchild, great_grandchild)
474            .expect("test: should succeed");
475
476        assert_eq!(arena.depth(root), 0);
477        assert_eq!(arena.depth(child), 1);
478        assert_eq!(arena.depth(grandchild), 2);
479        assert_eq!(arena.depth(great_grandchild), 3);
480    }
481
482    #[test]
483    fn test_sibling_ordering() {
484        let mut arena = FoArena::new();
485        let parent = arena.add_node(FoNode::new(FoNodeData::Root));
486
487        let mut ids = vec![];
488        for _ in 0..5 {
489            let child = arena.add_node(FoNode::new(FoNodeData::Block {
490                properties: crate::properties::PropertyList::new(),
491            }));
492            arena
493                .append_child(parent, child)
494                .expect("test: should succeed");
495            ids.push(child);
496        }
497
498        let children = arena.children(parent);
499        assert_eq!(children, ids);
500    }
501}
fop_core/tree/arena.rs

fop_core/tree/
arena.rs
