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

fop_core/tree/
arena.rs
