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/// Per-node state that HTML keeps outside the node's attributes.
15///
16/// A form control's *live* state is deliberately distinct from the content
17/// attribute of the same name: `input.checked = false` leaves the `checked`
18/// attribute (which is `defaultChecked`) alone, and `setAttribute("checked")`
19/// does not change the live state. `None` means "never set explicitly", so
20/// readers fall back to the default from the attributes.
21#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
22pub struct FormState {
23    /// The live checkedness of a checkbox or radio, i.e. `input.checked`.
24    pub checked: Option<bool>,
25}
26
27/// A single tree node
28#[derive(Clone)]
29pub struct TreeNode<T> {
30    pub value: T,
31    parent: Option<Weak<RefCell<TreeNode<T>>>>,
32    children: Vec<NodeRef<T>>,
33    /// Live form-control state, kept out of `value` so that attribute
34    /// reflection and DOM cloning stay independent of it.
35    form_state: Cell<FormState>,
36    /// DOM id of the document this node was created by, which is what
37    /// `Node.ownerDocument` reports.
38    ///
39    /// Walking the parent chain is not enough: a freshly created element is
40    /// not in a tree yet, yet it still has an owner document. Recording the
41    /// creator keeps `ownerDocument` correct for detached nodes and for nodes
42    /// that are later adopted into a different document.
43    owner_document: Cell<Option<u64>>,
44}
45
46impl<T> TreeNode<T> {
47    /// Create a new node wrapped in Rc<RefCell<_>>
48    pub fn new(value: T) -> NodeRef<T> {
49        Rc::new(RefCell::new(Self {
50            value,
51            parent: None,
52            children: Vec::new(),
53            form_state: Cell::new(FormState::default()),
54            owner_document: Cell::new(None),
55        }))
56    }
57
58    /// The DOM id of the document that created this node, if known.
59    pub fn owner_document(&self) -> Option<u64> {
60        self.owner_document.get()
61    }
62
63    /// Records the DOM id of the document that owns this node.
64    pub fn set_owner_document(&self, document_dom_id: u64) {
65        self.owner_document.set(Some(document_dom_id));
66    }
67
68    /// The node's live form-control state.
69    pub fn form_state(&self) -> FormState {
70        self.form_state.get()
71    }
72
73    /// Replaces the node's live form-control state.
74    pub fn set_form_state(&self, state: FormState) {
75        self.form_state.set(state);
76    }
77
78    /// The live checkedness, if the script has set one explicitly.
79    pub fn checkedness(&self) -> Option<bool> {
80        self.form_state.get().checked
81    }
82
83    /// Sets the live checkedness, leaving the `checked` attribute alone.
84    pub fn set_checkedness(&self, checked: bool) {
85        self.form_state.set(FormState {
86            checked: Some(checked),
87        });
88    }
89
90    /// Returns the parent node, if any
91    pub fn parent(&self) -> Option<NodeRef<T>> {
92        self.parent.as_ref().and_then(|w| w.upgrade())
93    }
94
95    /// Returns slice of child nodes
96    pub fn children(&self) -> &[NodeRef<T>] {
97        &self.children
98    }
99
100    /// Remove all children of this node
101    pub fn clear_children(&mut self) {
102        for child in &self.children {
103            child.borrow_mut().parent = None;
104        }
105        self.children.clear();
106    }
107
108    /// Add a child node
109    pub fn add_child(parent: &NodeRef<T>, child: NodeRef<T>) {
110        child.borrow_mut().parent = Some(Rc::downgrade(parent));
111        parent.borrow_mut().children.push(child);
112    }
113
114    /// Removes `child` from `parent`, returning the detached node when found.
115    pub fn remove_child(parent: &NodeRef<T>, child: &NodeRef<T>) -> Option<NodeRef<T>> {
116        let position = {
117            let borrowed = parent.borrow();
118            borrowed
119                .children
120                .iter()
121                .position(|candidate| Rc::ptr_eq(candidate, child))
122        }?;
123        let removed = parent.borrow_mut().children.remove(position);
124        removed.borrow_mut().parent = None;
125        Some(removed)
126    }
127
128    /// Detaches a node from its current parent.
129    pub fn detach(node: &NodeRef<T>) -> bool {
130        let Some(parent) = node.borrow().parent() else {
131            return false;
132        };
133        Self::remove_child(&parent, node).is_some()
134    }
135
136    /// Appends `child`, moving it from its current parent when necessary.
137    ///
138    /// Returns `false` when the operation would create a tree cycle.
139    pub fn append_child(parent: &NodeRef<T>, child: NodeRef<T>) -> bool {
140        if Self::is_inclusive_ancestor(&child, parent) {
141            return false;
142        }
143        Self::detach(&child);
144        Self::add_child(parent, child);
145        true
146    }
147
148    /// Inserts `child` immediately before `reference`, moving it from its
149    /// current parent when necessary.
150    pub fn insert_before(parent: &NodeRef<T>, child: NodeRef<T>, reference: &NodeRef<T>) -> bool {
151        if Rc::ptr_eq(&child, reference) {
152            return reference
153                .borrow()
154                .parent()
155                .is_some_and(|candidate| Rc::ptr_eq(&candidate, parent));
156        }
157        if Self::is_inclusive_ancestor(&child, parent) {
158            return false;
159        }
160        if !reference
161            .borrow()
162            .parent()
163            .is_some_and(|candidate| Rc::ptr_eq(&candidate, parent))
164        {
165            return false;
166        }
167
168        Self::detach(&child);
169        let Some(index) = parent
170            .borrow()
171            .children
172            .iter()
173            .position(|candidate| Rc::ptr_eq(candidate, reference))
174        else {
175            return false;
176        };
177        Self::insert_child_at(parent, index, child);
178        true
179    }
180
181    pub fn is_inclusive_ancestor(ancestor: &NodeRef<T>, node: &NodeRef<T>) -> bool {
182        let mut current = Some(Rc::clone(node));
183        while let Some(candidate) = current {
184            if Rc::ptr_eq(ancestor, &candidate) {
185                return true;
186            }
187            current = candidate.borrow().parent();
188        }
189        false
190    }
191
192    /// Insert a child at a given position
193    pub fn insert_child_at(parent: &NodeRef<T>, index: usize, child: NodeRef<T>) {
194        child.borrow_mut().parent = Some(Rc::downgrade(parent));
195        parent.borrow_mut().children.insert(index, child);
196    }
197
198    /// Create a child with value and add it to parent
199    pub fn add_child_value(parent: &NodeRef<T>, value: T) -> NodeRef<T> {
200        let child = Self::new(value);
201        Self::add_child(parent, Rc::clone(&child));
202        child
203    }
204
205    /// Replace child at given index
206    pub fn replace_child(
207        parent: &NodeRef<T>,
208        index: usize,
209        new_child: NodeRef<T>,
210    ) -> Option<NodeRef<T>> {
211        let mut p = parent.borrow_mut();
212        if index < p.children.len() {
213            let old_child = std::mem::replace(&mut p.children[index], new_child);
214            old_child.borrow_mut().parent = None;
215            Some(old_child)
216        } else {
217            None
218        }
219    }
220
221    /// Find direct children matching predicate
222    pub fn find_children_by<F>(&self, predicate: F) -> Vec<NodeRef<T>>
223    where
224        F: Fn(&T) -> bool,
225    {
226        self.children
227            .iter()
228            .filter(|c| predicate(&c.borrow().value))
229            .cloned()
230            .collect()
231    }
232
233    /// Clone node (optionally deep)
234    pub fn clone_node(&self, deep: bool) -> NodeRef<T>
235    where
236        T: Clone,
237    {
238        let new_node = Rc::new(RefCell::new(TreeNode {
239            value: self.value.clone(),
240            children: Vec::new(),
241            parent: None,
242            // The cloning steps for `input` copy the checkedness, and doing so
243            // for every node is harmless because other types ignore it.
244            form_state: Cell::new(self.form_state.get()),
245            // A clone is adopted by the document that imports it, but keeping
246            // the source's owner is the better default until then.
247            owner_document: Cell::new(self.owner_document.get()),
248        }));
249
250        if deep {
251            for child in &self.children {
252                let child_clone = child.borrow().clone_node(true);
253                child_clone.borrow_mut().parent = Some(Rc::downgrade(&new_node));
254                new_node.borrow_mut().children.push(child_clone);
255            }
256        }
257
258        new_node
259    }
260}
261
262/// Represents a tree with a single root node
263#[derive(Clone)]
264pub struct Tree<T> {
265    pub root: NodeRef<T>,
266    /// Monotonic counter bumped by [`Tree::mark_dirty`] on every mutation.
267    ///
268    /// Layout snapshots cache the DOM and are reused while the version is
269    /// unchanged, so any mutation (currently the text-input write-back, later
270    /// JS DOM manipulation) must call [`Tree::mark_dirty`] to invalidate them.
271    version: Cell<u64>,
272}
273
274impl<T: Clone> Tree<T> {
275    /// Create a new tree with root value
276    pub fn new(root_value: T) -> Self {
277        Self {
278            root: TreeNode::new(root_value),
279            version: Cell::new(0),
280        }
281    }
282
283    /// Wrap an already-built root in a fresh tree.
284    ///
285    /// The version counter starts at zero, so the resulting tree is treated as
286    /// a newly parsed document.
287    pub fn from_root(root: NodeRef<T>) -> Self {
288        Self {
289            root,
290            version: Cell::new(0),
291        }
292    }
293
294    /// Records a DOM mutation by bumping the tree's version counter.
295    pub fn mark_dirty(&self) {
296        self.version.set(self.version.get() + 1);
297    }
298
299    /// The current mutation version of the tree.
300    pub fn version(&self) -> u64 {
301        self.version.get()
302    }
303
304    /// Recursively traverse all nodes, applying a function
305    pub fn traverse<F>(&self, mut f: F)
306    where
307        F: FnMut(&NodeRef<T>),
308    {
309        fn visit<T, F>(node: &NodeRef<T>, f: &mut F)
310        where
311            F: FnMut(&NodeRef<T>),
312        {
313            f(node);
314            for child in &node.borrow().children {
315                visit(child, f);
316            }
317        }
318        visit(&self.root, &mut f);
319    }
320
321    /// Map each node value to another type, returning a new Tree
322    pub fn map<U, F>(&self, f: F) -> Tree<U>
323    where
324        F: Fn(&T) -> U,
325        U: Clone,
326    {
327        fn map_node<T, U, F>(node: &NodeRef<T>, f: &F) -> NodeRef<U>
328        where
329            F: Fn(&T) -> U,
330            U: Clone,
331        {
332            let n = node.borrow();
333            let new_node = TreeNode::new(f(&n.value));
334            for child in &n.children {
335                let mapped_child = map_node(child, f);
336                TreeNode::add_child(&new_node, mapped_child);
337            }
338            new_node
339        }
340
341        Tree {
342            root: map_node(&self.root, &f),
343            version: Cell::new(0),
344        }
345    }
346
347    /// Map using the NodeRef itself (for access to parent/children)
348    pub fn map_with_node<U, F>(&self, f: F) -> Tree<U>
349    where
350        F: Fn(&NodeRef<T>) -> U,
351        U: Clone,
352    {
353        fn map_node<T, U, F>(node: &NodeRef<T>, f: &F) -> NodeRef<U>
354        where
355            F: Fn(&NodeRef<T>) -> U,
356            U: Clone,
357        {
358            let new_node = TreeNode::new(f(node));
359            for child in &node.borrow().children {
360                let mapped_child = map_node(child, f);
361                TreeNode::add_child(&new_node, mapped_child);
362            }
363            new_node
364        }
365
366        Tree {
367            root: map_node(&self.root, &f),
368            version: Cell::new(0),
369        }
370    }
371
372    /// Find all nodes in the tree that satisfy a predicate
373    pub fn find_all<F>(&self, predicate: F) -> Vec<NodeRef<T>>
374    where
375        F: Fn(&T) -> bool,
376    {
377        let mut result = Vec::new();
378        self.traverse(|node| {
379            if predicate(&node.borrow().value) {
380                result.push(Rc::clone(node));
381            }
382        });
383        result
384    }
385}
386
387impl<T: Clone + Debug> Display for Tree<T> {
388    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
389        fn fmt_node<T: Clone + Debug>(
390            node: &NodeRef<T>,
391            f: &mut Formatter<'_>,
392            prefix: &str,
393            is_last: bool,
394        ) -> fmt::Result {
395            let n = node.borrow();
396            let connector = if prefix.is_empty() {
397                ""
398            } else if is_last {
399                "└── "
400            } else {
401                "├── "
402            };
403            writeln!(f, "{}{}{:?}", prefix, connector, n.value)?;
404            let child_count = n.children.len();
405            for (i, child) in n.children.iter().enumerate() {
406                let mut new_prefix = prefix.to_string();
407                new_prefix.push_str(if is_last { "    " } else { "│   " });
408                fmt_node(child, f, &new_prefix, i == child_count - 1)?;
409            }
410            Ok(())
411        }
412        fmt_node(&self.root, f, "", true)
413    }
414}
415
416impl<T: Clone + Debug> Debug for Tree<T> {
417    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
418        write!(f, "{}", self)
419    }
420}
421
422#[cfg(test)]
423mod tests {
424    use super::*;
425
426    #[test]
427    fn append_child_reparents_and_prevents_cycles() {
428        let root = TreeNode::new("root");
429        let first = TreeNode::new("first");
430        let second = TreeNode::new("second");
431        TreeNode::add_child(&root, Rc::clone(&first));
432        TreeNode::add_child(&first, Rc::clone(&second));
433
434        assert!(TreeNode::append_child(&root, Rc::clone(&second)));
435        assert!(first.borrow().children().is_empty());
436        assert!(Rc::ptr_eq(&second.borrow().parent().unwrap(), &root));
437        assert!(!TreeNode::append_child(&second, Rc::clone(&root)));
438    }
439
440    #[test]
441    fn owner_document_is_kept_per_node_and_across_clones() {
442        let element = TreeNode::new("element");
443        // A fresh node has no document until a factory records one.
444        assert_eq!(element.borrow().owner_document(), None);
445
446        element.borrow().set_owner_document(7);
447        assert_eq!(element.borrow().owner_document(), Some(7));
448
449        // Re-parenting does not change the owner; adopting into another
450        // document is an explicit step.
451        let other = TreeNode::new("other");
452        TreeNode::add_child(&other, Rc::clone(&element));
453        assert_eq!(element.borrow().owner_document(), Some(7));
454
455        // A clone starts out owned by the same document as its source.
456        let clone = element.borrow().clone_node(true);
457        assert_eq!(clone.borrow().owner_document(), Some(7));
458    }
459
460    #[test]
461    fn detach_and_clear_children_reset_parent_links() {
462        let root = TreeNode::new("root");
463        let first = TreeNode::new("first");
464        let second = TreeNode::new("second");
465        TreeNode::add_child(&root, Rc::clone(&first));
466        TreeNode::add_child(&root, Rc::clone(&second));
467
468        assert!(TreeNode::detach(&first));
469        assert!(first.borrow().parent().is_none());
470        root.borrow_mut().clear_children();
471        assert!(second.borrow().parent().is_none());
472    }
473
474    #[test]
475    fn insert_before_moves_nodes_and_preserves_order() {
476        let root = TreeNode::new("root");
477        let first = TreeNode::new("first");
478        let second = TreeNode::new("second");
479        let moving = TreeNode::new("moving");
480        TreeNode::add_child(&root, Rc::clone(&first));
481        TreeNode::add_child(&root, Rc::clone(&second));
482        TreeNode::add_child(&first, Rc::clone(&moving));
483
484        assert!(TreeNode::insert_before(&root, Rc::clone(&moving), &second));
485        let children = root.borrow().children().to_vec();
486        assert!(Rc::ptr_eq(&children[0], &first));
487        assert!(Rc::ptr_eq(&children[1], &moving));
488        assert!(Rc::ptr_eq(&children[2], &second));
489        assert!(first.borrow().children().is_empty());
490    }
491}
orinium_browser/engine/tree.rs

orinium_browser/engine/
tree.rs
