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

orinium_browser/engine/layouter/
dom_snapshot.rs
