orinium_browser/engine/
tree.rs

1//! Generic tree structure for DOM, render tree, or other hierarchical data.
2//!
3//! # Overview
4//! - `TreeNode<T>` stores a node value, parent, and children.
5//! - `Tree<T>` stores a root node and provides traversal, mapping, and searching utilities.
6
7use std::cell::{Cell, RefCell};
8use std::fmt::{self, Debug, Display, Formatter};
9use std::rc::{Rc, Weak};
10
11/// Alias for a reference-counted tree node
12pub type NodeRef<T> = Rc<RefCell<TreeNode<T>>>;
13
14/// A single tree node
15#[derive(Clone)]
16pub struct TreeNode<T> {
17    pub value: T,
18    parent: Option<Weak<RefCell<TreeNode<T>>>>,
19    children: Vec<NodeRef<T>>,
20}
21
22impl<T> TreeNode<T> {
23    /// Create a new node wrapped in Rc<RefCell<_>>
24    pub fn new(value: T) -> NodeRef<T> {
25        Rc::new(RefCell::new(Self {
26            value,
27            parent: None,
28            children: Vec::new(),
29        }))
30    }
31
32    /// Returns the parent node, if any
33    pub fn parent(&self) -> Option<NodeRef<T>> {
34        self.parent.as_ref().and_then(|w| w.upgrade())
35    }
36
37    /// Returns slice of child nodes
38    pub fn children(&self) -> &[NodeRef<T>] {
39        &self.children
40    }
41
42    /// Remove all children of this node
43    pub fn clear_children(&mut self) {
44        for child in &self.children {
45            child.borrow_mut().parent = None;
46        }
47        self.children.clear();
48    }
49
50    /// Add a child node
51    pub fn add_child(parent: &NodeRef<T>, child: NodeRef<T>) {
52        child.borrow_mut().parent = Some(Rc::downgrade(parent));
53        parent.borrow_mut().children.push(child);
54    }
55
56    /// Removes `child` from `parent`, returning the detached node when found.
57    pub fn remove_child(parent: &NodeRef<T>, child: &NodeRef<T>) -> Option<NodeRef<T>> {
58        let position = {
59            let borrowed = parent.borrow();
60            borrowed
61                .children
62                .iter()
63                .position(|candidate| Rc::ptr_eq(candidate, child))
64        }?;
65        let removed = parent.borrow_mut().children.remove(position);
66        removed.borrow_mut().parent = None;
67        Some(removed)
68    }
69
70    /// Detaches a node from its current parent.
71    pub fn detach(node: &NodeRef<T>) -> bool {
72        let Some(parent) = node.borrow().parent() else {
73            return false;
74        };
75        Self::remove_child(&parent, node).is_some()
76    }
77
78    /// Appends `child`, moving it from its current parent when necessary.
79    ///
80    /// Returns `false` when the operation would create a tree cycle.
81    pub fn append_child(parent: &NodeRef<T>, child: NodeRef<T>) -> bool {
82        if Self::is_inclusive_ancestor(&child, parent) {
83            return false;
84        }
85        Self::detach(&child);
86        Self::add_child(parent, child);
87        true
88    }
89
90    /// Inserts `child` immediately before `reference`, moving it from its
91    /// current parent when necessary.
92    pub fn insert_before(parent: &NodeRef<T>, child: NodeRef<T>, reference: &NodeRef<T>) -> bool {
93        if Rc::ptr_eq(&child, reference) {
94            return reference
95                .borrow()
96                .parent()
97                .is_some_and(|candidate| Rc::ptr_eq(&candidate, parent));
98        }
99        if Self::is_inclusive_ancestor(&child, parent) {
100            return false;
101        }
102        if !reference
103            .borrow()
104            .parent()
105            .is_some_and(|candidate| Rc::ptr_eq(&candidate, parent))
106        {
107            return false;
108        }
109
110        Self::detach(&child);
111        let Some(index) = parent
112            .borrow()
113            .children
114            .iter()
115            .position(|candidate| Rc::ptr_eq(candidate, reference))
116        else {
117            return false;
118        };
119        Self::insert_child_at(parent, index, child);
120        true
121    }
122
123    pub fn is_inclusive_ancestor(ancestor: &NodeRef<T>, node: &NodeRef<T>) -> bool {
124        let mut current = Some(Rc::clone(node));
125        while let Some(candidate) = current {
126            if Rc::ptr_eq(ancestor, &candidate) {
127                return true;
128            }
129            current = candidate.borrow().parent();
130        }
131        false
132    }
133
134    /// Insert a child at a given position
135    pub fn insert_child_at(parent: &NodeRef<T>, index: usize, child: NodeRef<T>) {
136        child.borrow_mut().parent = Some(Rc::downgrade(parent));
137        parent.borrow_mut().children.insert(index, child);
138    }
139
140    /// Create a child with value and add it to parent
141    pub fn add_child_value(parent: &NodeRef<T>, value: T) -> NodeRef<T> {
142        let child = Self::new(value);
143        Self::add_child(parent, Rc::clone(&child));
144        child
145    }
146
147    /// Replace child at given index
148    pub fn replace_child(
149        parent: &NodeRef<T>,
150        index: usize,
151        new_child: NodeRef<T>,
152    ) -> Option<NodeRef<T>> {
153        let mut p = parent.borrow_mut();
154        if index < p.children.len() {
155            let old_child = std::mem::replace(&mut p.children[index], new_child);
156            old_child.borrow_mut().parent = None;
157            Some(old_child)
158        } else {
159            None
160        }
161    }
162
163    /// Find direct children matching predicate
164    pub fn find_children_by<F>(&self, predicate: F) -> Vec<NodeRef<T>>
165    where
166        F: Fn(&T) -> bool,
167    {
168        self.children
169            .iter()
170            .filter(|c| predicate(&c.borrow().value))
171            .cloned()
172            .collect()
173    }
174
175    /// Clone node (optionally deep)
176    pub fn clone_node(&self, deep: bool) -> NodeRef<T>
177    where
178        T: Clone,
179    {
180        let new_node = Rc::new(RefCell::new(TreeNode {
181            value: self.value.clone(),
182            children: Vec::new(),
183            parent: None,
184        }));
185
186        if deep {
187            for child in &self.children {
188                let child_clone = child.borrow().clone_node(true);
189                child_clone.borrow_mut().parent = Some(Rc::downgrade(&new_node));
190                new_node.borrow_mut().children.push(child_clone);
191            }
192        }
193
194        new_node
195    }
196}
197
198/// Represents a tree with a single root node
199#[derive(Clone)]
200pub struct Tree<T> {
201    pub root: NodeRef<T>,
202    /// Monotonic counter bumped by [`Tree::mark_dirty`] on every mutation.
203    ///
204    /// Layout snapshots cache the DOM and are reused while the version is
205    /// unchanged, so any mutation (currently the text-input write-back, later
206    /// JS DOM manipulation) must call [`Tree::mark_dirty`] to invalidate them.
207    version: Cell<u64>,
208}
209
210impl<T: Clone> Tree<T> {
211    /// Create a new tree with root value
212    pub fn new(root_value: T) -> Self {
213        Self {
214            root: TreeNode::new(root_value),
215            version: Cell::new(0),
216        }
217    }
218
219    /// Wrap an already-built root in a fresh tree.
220    ///
221    /// The version counter starts at zero, so the resulting tree is treated as
222    /// a newly parsed document.
223    pub fn from_root(root: NodeRef<T>) -> Self {
224        Self {
225            root,
226            version: Cell::new(0),
227        }
228    }
229
230    /// Records a DOM mutation by bumping the tree's version counter.
231    pub fn mark_dirty(&self) {
232        self.version.set(self.version.get() + 1);
233    }
234
235    /// The current mutation version of the tree.
236    pub fn version(&self) -> u64 {
237        self.version.get()
238    }
239
240    /// Recursively traverse all nodes, applying a function
241    pub fn traverse<F>(&self, mut f: F)
242    where
243        F: FnMut(&NodeRef<T>),
244    {
245        fn visit<T, F>(node: &NodeRef<T>, f: &mut F)
246        where
247            F: FnMut(&NodeRef<T>),
248        {
249            f(node);
250            for child in &node.borrow().children {
251                visit(child, f);
252            }
253        }
254        visit(&self.root, &mut f);
255    }
256
257    /// Map each node value to another type, returning a new Tree
258    pub fn map<U, F>(&self, f: F) -> Tree<U>
259    where
260        F: Fn(&T) -> U,
261        U: Clone,
262    {
263        fn map_node<T, U, F>(node: &NodeRef<T>, f: &F) -> NodeRef<U>
264        where
265            F: Fn(&T) -> U,
266            U: Clone,
267        {
268            let n = node.borrow();
269            let new_node = TreeNode::new(f(&n.value));
270            for child in &n.children {
271                let mapped_child = map_node(child, f);
272                TreeNode::add_child(&new_node, mapped_child);
273            }
274            new_node
275        }
276
277        Tree {
278            root: map_node(&self.root, &f),
279            version: Cell::new(0),
280        }
281    }
282
283    /// Map using the NodeRef itself (for access to parent/children)
284    pub fn map_with_node<U, F>(&self, f: F) -> Tree<U>
285    where
286        F: Fn(&NodeRef<T>) -> U,
287        U: Clone,
288    {
289        fn map_node<T, U, F>(node: &NodeRef<T>, f: &F) -> NodeRef<U>
290        where
291            F: Fn(&NodeRef<T>) -> U,
292            U: Clone,
293        {
294            let new_node = TreeNode::new(f(node));
295            for child in &node.borrow().children {
296                let mapped_child = map_node(child, f);
297                TreeNode::add_child(&new_node, mapped_child);
298            }
299            new_node
300        }
301
302        Tree {
303            root: map_node(&self.root, &f),
304            version: Cell::new(0),
305        }
306    }
307
308    /// Find all nodes in the tree that satisfy a predicate
309    pub fn find_all<F>(&self, predicate: F) -> Vec<NodeRef<T>>
310    where
311        F: Fn(&T) -> bool,
312    {
313        let mut result = Vec::new();
314        self.traverse(|node| {
315            if predicate(&node.borrow().value) {
316                result.push(Rc::clone(node));
317            }
318        });
319        result
320    }
321}
322
323impl<T: Clone + Debug> Display for Tree<T> {
324    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
325        fn fmt_node<T: Clone + Debug>(
326            node: &NodeRef<T>,
327            f: &mut Formatter<'_>,
328            prefix: &str,
329            is_last: bool,
330        ) -> fmt::Result {
331            let n = node.borrow();
332            let connector = if prefix.is_empty() {
333                ""
334            } else if is_last {
335                "└── "
336            } else {
337                "├── "
338            };
339            writeln!(f, "{}{}{:?}", prefix, connector, n.value)?;
340            let child_count = n.children.len();
341            for (i, child) in n.children.iter().enumerate() {
342                let mut new_prefix = prefix.to_string();
343                new_prefix.push_str(if is_last { "    " } else { "│   " });
344                fmt_node(child, f, &new_prefix, i == child_count - 1)?;
345            }
346            Ok(())
347        }
348        fmt_node(&self.root, f, "", true)
349    }
350}
351
352impl<T: Clone + Debug> Debug for Tree<T> {
353    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
354        write!(f, "{}", self)
355    }
356}
357
358#[cfg(test)]
359mod tests {
360    use super::*;
361
362    #[test]
363    fn append_child_reparents_and_prevents_cycles() {
364        let root = TreeNode::new("root");
365        let first = TreeNode::new("first");
366        let second = TreeNode::new("second");
367        TreeNode::add_child(&root, Rc::clone(&first));
368        TreeNode::add_child(&first, Rc::clone(&second));
369
370        assert!(TreeNode::append_child(&root, Rc::clone(&second)));
371        assert!(first.borrow().children().is_empty());
372        assert!(Rc::ptr_eq(&second.borrow().parent().unwrap(), &root));
373        assert!(!TreeNode::append_child(&second, Rc::clone(&root)));
374    }
375
376    #[test]
377    fn detach_and_clear_children_reset_parent_links() {
378        let root = TreeNode::new("root");
379        let first = TreeNode::new("first");
380        let second = TreeNode::new("second");
381        TreeNode::add_child(&root, Rc::clone(&first));
382        TreeNode::add_child(&root, Rc::clone(&second));
383
384        assert!(TreeNode::detach(&first));
385        assert!(first.borrow().parent().is_none());
386        root.borrow_mut().clear_children();
387        assert!(second.borrow().parent().is_none());
388    }
389
390    #[test]
391    fn insert_before_moves_nodes_and_preserves_order() {
392        let root = TreeNode::new("root");
393        let first = TreeNode::new("first");
394        let second = TreeNode::new("second");
395        let moving = TreeNode::new("moving");
396        TreeNode::add_child(&root, Rc::clone(&first));
397        TreeNode::add_child(&root, Rc::clone(&second));
398        TreeNode::add_child(&first, Rc::clone(&moving));
399
400        assert!(TreeNode::insert_before(&root, Rc::clone(&moving), &second));
401        let children = root.borrow().children().to_vec();
402        assert!(Rc::ptr_eq(&children[0], &first));
403        assert!(Rc::ptr_eq(&children[1], &moving));
404        assert!(Rc::ptr_eq(&children[2], &second));
405        assert!(first.borrow().children().is_empty());
406    }
407}
orinium_browser/engine/tree.rs

orinium_browser/engine/
tree.rs
