orinium_browser/engine/layouter/
dom_snapshot.rs

1//! Owned, thread-safe snapshot of the DOM.
2//!
3//! The live DOM tree is built with `Rc<RefCell<TreeNode>>`, which is not
4//! [`Send`]. To build layout off the UI thread, we clone the tree into an
5//! arena of owned nodes. Pre-order (document-order) node ids index the arena,
6//! so the snapshot can be moved to a background thread and the builder walks it
7//! exactly as it walked the `Rc` tree.
8
9use std::cell::RefCell;
10use std::collections::HashMap;
11use std::rc::{Rc, Weak};
12
13use crate::engine::html::HtmlNodeType;
14use crate::engine::html::parser::DomTree;
15use crate::engine::tree::{NodeRef, TreeNode};
16
17/// Pre-order (document-order) id of a node in the snapshot arena.
18pub type NodeId = u32;
19
20/// A single owned snapshot node.
21#[derive(Debug, Clone)]
22pub struct SnapNode {
23    pub kind: HtmlNodeType,
24    pub children: Vec<NodeId>,
25    /// Stable id the JS runtime attaches to a node when it is first exposed to
26    /// scripts. Zero means the node has never been exposed. Layout only builds
27    /// snapshots from the real tree and leaves this zero.
28    pub dom_id: u64,
29    /// The live checkedness of a checkbox or radio, resolved when the snapshot
30    /// was taken: the explicit state if the script set one, otherwise the
31    /// `checked` content attribute (i.e. `defaultChecked`).
32    pub checked: bool,
33    /// The live value of an input/textarea element, resolved when the snapshot
34    /// was taken: the `value` content attribute or the live property value if
35    /// the user/script mutated it.
36    pub value: Option<String>,
37}
38
39/// An owned snapshot of a DOM subtree.
40///
41/// Nodes are stored in pre-order so `id == index`. `roots` lists the ids of
42/// top-level nodes (a snapshot has exactly one root in practice).
43#[derive(Debug, Default)]
44pub struct DomSnapshot {
45    nodes: Vec<SnapNode>,
46    roots: Vec<NodeId>,
47}
48
49impl DomSnapshot {
50    /// Builds a snapshot of `root` and the matching live-node references.
51    ///
52    /// `dom_refs[i]` is the live DOM node for snapshot node id `i`. The refs
53    /// are kept separate (and are **not** `Send`) so the UI thread can apply
54    /// attribute write-backs after the background thread finished building.
55    pub fn from_tree(
56        root: &NodeRef<HtmlNodeType>,
57    ) -> (Self, Vec<Weak<RefCell<TreeNode<HtmlNodeType>>>>) {
58        let mut snapshot = DomSnapshot::default();
59        let mut dom_refs: Vec<Weak<RefCell<TreeNode<HtmlNodeType>>>> = Vec::new();
60        let id = snapshot.walk(root, &mut dom_refs);
61        snapshot.roots.push(id);
62        (snapshot, dom_refs)
63    }
64
65    /// Builds a snapshot of a JS thread's mirror tree.
66    ///
67    /// `dom_ids` maps `Rc::as_ptr` addresses of mirror nodes to the stable id
68    /// assigned by the JS runtime, so node identities survive the snapshot
69    /// round trip. Mirrored nodes that were never exposed to scripts carry
70    /// [`SnapNode::dom_id`] zero.
71    pub fn from_mirror(root: &NodeRef<HtmlNodeType>, dom_ids: &HashMap<usize, u64>) -> Self {
72        fn walk(
73            snapshot: &mut DomSnapshot,
74            node: &NodeRef<HtmlNodeType>,
75            dom_ids: &HashMap<usize, u64>,
76        ) -> NodeId {
77            let id = snapshot.nodes.len() as NodeId;
78            let node_borrow = node.borrow();
79            let value = node_borrow.value.get_attr("value").map(|s| s.to_string());
80            snapshot.nodes.push(SnapNode {
81                kind: node_borrow.value.clone(),
82                children: Vec::new(),
83                dom_id: dom_ids
84                    .get(&(Rc::as_ptr(node) as usize))
85                    .copied()
86                    .unwrap_or(0),
87                checked: crate::engine::html::parser::checkedness(node),
88                value,
89            });
90            let children: Vec<NodeId> = node
91                .borrow()
92                .children()
93                .iter()
94                .map(|child| walk(snapshot, child, dom_ids))
95                .collect();
96            snapshot.nodes[id as usize].children = children;
97            id
98        }
99        let mut snapshot = DomSnapshot::default();
100        let id = walk(&mut snapshot, root, dom_ids);
101        snapshot.roots.push(id);
102        snapshot
103    }
104
105    /// Rebuilds a live DOM tree from the snapshot.
106    ///
107    /// The returned map keyed by `Rc::as_ptr` address pairs every non-zero
108    /// [`SnapNode::dom_id`] with the freshly built node, so the caller can
109    /// re-register the JS runtime's node references after committing.
110    pub fn into_tree(&self) -> (DomTree, HashMap<usize, u64>) {
111        fn build(id: NodeId, snapshot: &DomSnapshot) -> NodeRef<HtmlNodeType> {
112            let node = TreeNode::new(snapshot.nodes[id as usize].kind.clone());
113            for &child in &snapshot.nodes[id as usize].children {
114                let child_node = build(child, snapshot);
115                TreeNode::add_child(&node, child_node);
116            }
117            node
118        }
119
120        let root = build(self.roots[0], self);
121        let tree = DomTree::from_root(root);
122        let mut dom_ids = HashMap::new();
123        let mut index = 0usize;
124        tree.traverse(|node| {
125            let dom_id = self.nodes[index].dom_id;
126            if dom_id != 0 {
127                dom_ids.insert(Rc::as_ptr(node) as usize, dom_id);
128            }
129            index += 1;
130        });
131        (tree, dom_ids)
132    }
133
134    fn walk(
135        &mut self,
136        node: &NodeRef<HtmlNodeType>,
137        dom_refs: &mut Vec<Weak<RefCell<TreeNode<HtmlNodeType>>>>,
138    ) -> NodeId {
139        let id = self.nodes.len() as NodeId;
140        let node_borrow = node.borrow();
141        let value = node_borrow.value.get_attr("value").map(|s| s.to_string());
142        self.nodes.push(SnapNode {
143            kind: node_borrow.value.clone(),
144            children: Vec::new(),
145            dom_id: 0,
146            checked: crate::engine::html::parser::checkedness(node),
147            value,
148        });
149        dom_refs.push(Rc::downgrade(node));
150        let children: Vec<NodeId> = node
151            .borrow()
152            .children()
153            .iter()
154            .map(|child| self.walk(child, dom_refs))
155            .collect();
156        self.nodes[id as usize].children = children;
157        id
158    }
159
160    /// Root node ids (always a single root in practice).
161    pub fn roots(&self) -> &[NodeId] {
162        &self.roots
163    }
164
165    /// All snapshot nodes in pre-order (`id == index`).
166    pub fn nodes(&self) -> &[SnapNode] {
167        &self.nodes
168    }
169
170    /// The node with the given id.
171    pub fn node(&self, id: NodeId) -> &SnapNode {
172        &self.nodes[id as usize]
173    }
174
175    /// Child ids of the node with the given id.
176    pub fn children(&self, id: NodeId) -> &[NodeId] {
177        &self.nodes[id as usize].children
178    }
179
180    /// Concatenated text content of a node, including descendants.
181    pub fn inner_text(&self, id: NodeId) -> String {
182        let node = &self.nodes[id as usize];
183        match &node.kind {
184            HtmlNodeType::Text(content) => content.clone(),
185            HtmlNodeType::Element { .. } | HtmlNodeType::Document => node
186                .children
187                .iter()
188                .map(|&child| self.inner_text(child))
189                .collect(),
190            _ => String::new(),
191        }
192    }
193}
194
195#[cfg(test)]
196mod tests {
197    use super::*;
198    use crate::engine::html::parser::DomTree;
199    use crate::engine::html::parser::Parser as HtmlParser;
200
201    fn tree(html: &str) -> DomTree {
202        HtmlParser::new(html).parse()
203    }
204
205    #[test]
206    fn snapshot_is_built_in_preorder_and_is_send() {
207        let dom = tree("<html><body><div><p>hi</p></div><button>ok</button></body></html>");
208        let (snapshot, _dom_refs) = DomSnapshot::from_tree(&dom.root);
209        let root = snapshot.roots()[0];
210
211        // The parser wraps the tree in a Document node.
212        let doc = snapshot.node(root);
213        assert_eq!(doc.kind.tag_name(), None);
214
215        // root html has the auto-inserted head and body as element children
216        let html = doc.children[0];
217        let html_node = snapshot.node(html);
218        assert_eq!(html_node.kind.tag_name(), Some("html"));
219        assert_eq!(html_node.children.len(), 2);
220
221        // Pre-order: head comes first, then body.
222        assert_eq!(
223            snapshot.node(html_node.children[0]).kind.tag_name(),
224            Some("head")
225        );
226        let body = html_node.children[1];
227        assert_eq!(snapshot.node(body).kind.tag_name(), Some("body"));
228
229        // A snapshot must be movable to another thread.
230        std::thread::spawn(move || {
231            let _ = snapshot.inner_text(root);
232        })
233        .join()
234        .unwrap();
235    }
236
237    #[test]
238    fn inner_text_concatenates_descendants() {
239        let dom = tree("<div><p>hello</p><p>world</p></div>");
240        let (snapshot, _) = DomSnapshot::from_tree(&dom.root);
241        let root = snapshot.roots()[0];
242        assert_eq!(snapshot.inner_text(root), "helloworld");
243    }
244
245    #[test]
246    fn dom_refs_map_node_id_to_live_node() {
247        let dom = tree("<input value='a'>");
248        let (snapshot, dom_refs) = DomSnapshot::from_tree(&dom.root);
249        let root = snapshot.roots()[0];
250
251        // Find the input's snapshot id anywhere below the Document root.
252        fn find(snapshot: &DomSnapshot, id: NodeId, tag: &str) -> Option<NodeId> {
253            if snapshot.node(id).kind.tag_name() == Some(tag) {
254                return Some(id);
255            }
256            snapshot
257                .children(id)
258                .iter()
259                .find_map(|&c| find(snapshot, c, tag))
260        }
261        let input_id = find(&snapshot, root, "input").unwrap();
262
263        let live = dom_refs[input_id as usize].upgrade().unwrap();
264        assert_eq!(live.borrow().value.tag_name(), Some("input"));
265    }
266
267    #[test]
268    fn from_tree_roundtrip_preserves_structure() {
269        let dom = tree("<html><body><div><p>hi</p></div><button>ok</button></body></html>");
270        let (snapshot, _) = DomSnapshot::from_tree(&dom.root);
271        let (rebuilt, dom_ids) = snapshot.into_tree();
272
273        assert_eq!(rebuilt.root.borrow().value.tag_name(), None);
274        assert!(dom_ids.is_empty());
275        assert_eq!(
276            rebuilt.root.borrow().children()[0]
277                .borrow()
278                .value
279                .tag_name(),
280            Some("html")
281        );
282        assert_eq!(
283            rebuilt.root.borrow().children()[0].borrow().children()[0]
284                .borrow()
285                .value
286                .tag_name(),
287            Some("head")
288        );
289        assert_eq!(
290            rebuilt.root.borrow().children()[0].borrow().children()[1]
291                .borrow()
292                .value
293                .tag_name(),
294            Some("body")
295        );
296        assert_eq!(rebuilt.version(), 0);
297    }
298
299    #[test]
300    fn from_mirror_and_into_tree_preserve_dom_ids() {
301        let dom = tree("<div><p>hi</p><p>yo</p></div>");
302
303        // Simulate the JS runtime: expose every node except the first <p>.
304        let mut dom_ids = HashMap::new();
305        let mut next = 1u64;
306        let mut counter = 0usize;
307        dom.traverse(|node| {
308            if counter.is_multiple_of(2) {
309                dom_ids.insert(Rc::as_ptr(node) as usize, next);
310                next += 1;
311            }
312            counter += 1;
313        });
314
315        let snapshot = DomSnapshot::from_mirror(&dom.root, &dom_ids);
316        let (rebuilt, rebuilt_ids) = snapshot.into_tree();
317
318        assert_eq!(rebuilt_ids.len(), dom_ids.len());
319        // Same addresses only by coincidence; verify the ids line up pre-order.
320        let mut rebuilt_preorder: Vec<u64> = Vec::new();
321        rebuilt.traverse(|node| {
322            rebuilt_preorder.push(
323                rebuilt_ids
324                    .get(&(Rc::as_ptr(node) as usize))
325                    .copied()
326                    .unwrap_or(0),
327            );
328        });
329        let mut expected: Vec<u64> = Vec::new();
330        dom.traverse(|node| {
331            expected.push(
332                dom_ids
333                    .get(&(Rc::as_ptr(node) as usize))
334                    .copied()
335                    .unwrap_or(0),
336            );
337        });
338        assert_eq!(rebuilt_preorder, expected);
339    }
340}
orinium_browser/engine/layouter/dom_snapshot.rs

orinium_browser/engine/layouter/
dom_snapshot.rs
