git.iko.soy/dodrio
on 3906f80 help sign in
dodrio/src/diff.rs
338 lines 10 kB history raw
1use crate::{
2 cached_set::{CacheId, CachedSet},
3 change_list::ChangeListBuilder,
4 events::EventsRegistry,
5 node::{Attribute, ElementNode, Listener, Node, NodeKind, TextNode},
6};
7use fxhash::FxHashSet;
8use std::cmp;
10pub(crate) fn diff(
11 cached_set: &CachedSet,
12 change_list: &mut ChangeListBuilder,
13 registry: &mut EventsRegistry,
14 old: &Node,
15 new: &Node,
16 cached_roots: &mut FxHashSet<CacheId>,
17) {
18 match (&new.kind, &old.kind) {
19 (
20 &NodeKind::Text(TextNode { text: new_text }),
21 &NodeKind::Text(TextNode { text: old_text }),
22 ) => {
23 debug!(" both are text nodes");
24 if new_text != old_text {
25 debug!(" text needs updating");
26 change_list.set_text(new_text);
27 }
28 }
30 (&NodeKind::Text(_), &NodeKind::Element(_)) => {
31 debug!(" replacing a text node with an element");
32 create(cached_set, change_list, registry, new, cached_roots);
33 registry.remove_subtree(&old);
34 change_list.replace_with();
35 }
37 (&NodeKind::Element(_), &NodeKind::Text(_)) => {
38 debug!(" replacing an element with a text node");
39 create(cached_set, change_list, registry, new, cached_roots);
40 // Note: text nodes cannot have event listeners, so we don't need to
41 // remove the old node's listeners from our registry her.
42 change_list.replace_with();
43 }
45 (
46 &NodeKind::Element(ElementNode {
47 tag_name: new_tag_name,
48 listeners: new_listeners,
49 attributes: new_attributes,
50 children: new_children,
51 namespace: new_namespace,
52 }),
53 &NodeKind::Element(ElementNode {
54 tag_name: old_tag_name,
55 listeners: old_listeners,
56 attributes: old_attributes,
57 children: old_children,
58 namespace: old_namespace,
59 }),
60 ) => {
61 debug!(" updating an element");
62 if new_tag_name != old_tag_name || new_namespace != old_namespace {
63 debug!(" different tag names or namespaces; creating new element and replacing old element");
64 create(cached_set, change_list, registry, new, cached_roots);
65 registry.remove_subtree(&old);
66 change_list.replace_with();
67 return;
68 }
69 diff_listeners(change_list, registry, old_listeners, new_listeners);
70 diff_attributes(change_list, old_attributes, new_attributes);
71 diff_children(
72 cached_set,
73 change_list,
74 registry,
75 old_children,
76 new_children,
77 cached_roots,
78 );
79 }
81 // Both the new and old nodes are cached.
82 (&NodeKind::Cached(ref new), &NodeKind::Cached(ref old)) => {
83 cached_roots.insert(new.id);
85 if new.id == old.id {
86 // This is the same cached node, so nothing has changed!
87 return;
88 }
90 let new = cached_set.get(new.id);
91 let old = cached_set.get(old.id);
92 diff(cached_set, change_list, registry, old, new, cached_roots);
93 }
95 // New cached node when the old node was not cached. In this scenario,
96 // we assume that they are pretty different, and it isn't worth diffing
97 // the subtrees, so we just create the new cached node afresh.
98 (&NodeKind::Cached(ref c), _) => {
99 cached_roots.insert(c.id);
100 let new = cached_set.get(c.id);
101 create(cached_set, change_list, registry, new, cached_roots);
102 registry.remove_subtree(&old);
103 change_list.replace_with();
104 }
106 // Old cached node and new non-cached node. Again, assume that they are
107 // probably pretty different and create the new non-cached node afresh.
108 (_, &NodeKind::Cached(_)) => {
109 create(cached_set, change_list, registry, new, cached_roots);
110 registry.remove_subtree(&old);
111 change_list.replace_with();
112 }
113 }
116fn diff_listeners(
117 change_list: &mut ChangeListBuilder,
118 registry: &mut EventsRegistry,
119 old: &[Listener],
120 new: &[Listener],
121) {
122 debug!(" updating event listeners");
124 'outer1: for new_l in new {
125 unsafe {
126 // Safety relies on removing `new_l` from the registry manually at
127 // the end of its lifetime. This happens below in the `'outer2`
128 // loop, and elsewhere in diffing when removing old dom trees.
129 registry.add(new_l);
130 }
132 for old_l in old {
133 if new_l.event == old_l.event {
134 change_list.update_event_listener(new_l);
135 continue 'outer1;
136 }
137 }
139 change_list.new_event_listener(new_l);
140 }
142 'outer2: for old_l in old {
143 registry.remove(old_l);
145 for new_l in new {
146 if new_l.event == old_l.event {
147 continue 'outer2;
148 }
149 }
150 change_list.remove_event_listener(old_l.event);
151 }
154fn diff_attributes(change_list: &mut ChangeListBuilder, old: &[Attribute], new: &[Attribute]) {
155 debug!(" updating attributes");
157 // Do O(n^2) passes to add/update and remove attributes, since
158 // there are almost always very few attributes.
159 'outer: for new_attr in new {
160 if new_attr.is_volatile() {
161 change_list.set_attribute(new_attr.name, new_attr.value);
162 } else {
163 for old_attr in old {
164 if old_attr.name == new_attr.name {
165 if old_attr.value != new_attr.value {
166 change_list.set_attribute(new_attr.name, new_attr.value);
167 }
168 continue 'outer;
169 }
170 }
171 change_list.set_attribute(new_attr.name, new_attr.value);
172 }
173 }
175 'outer2: for old_attr in old {
176 for new_attr in new {
177 if old_attr.name == new_attr.name {
178 continue 'outer2;
179 }
180 }
181 change_list.remove_attribute(old_attr.name);
182 }
185fn diff_children(
186 cached_set: &CachedSet,
187 change_list: &mut ChangeListBuilder,
188 registry: &mut EventsRegistry,
189 old: &[Node],
190 new: &[Node],
191 cached_roots: &mut FxHashSet<CacheId>,
192) {
193 if new.is_empty() {
194 if !old.is_empty() {
195 remove_children(change_list, registry, old);
196 }
197 return;
198 }
200 if old.is_empty() {
201 create_children(cached_set, change_list, registry, new, cached_roots);
202 return;
203 }
205 debug!(" updating children shared by old and new");
207 let num_children_to_diff = cmp::min(new.len(), old.len());
208 let mut new_children = new.iter();
209 let mut old_children = old.iter();
210 let mut pushed = false;
212 for (i, (new_child, old_child)) in new_children
213 .by_ref()
214 .zip(old_children.by_ref())
215 .take(num_children_to_diff)
216 .enumerate()
217 {
218 if i == 0 {
219 change_list.push_first_child();
220 pushed = true;
221 } else {
222 debug_assert!(pushed);
223 change_list.pop_push_next_sibling();
224 }
226 diff(
227 cached_set,
228 change_list,
229 registry,
230 old_child,
231 new_child,
232 cached_roots,
233 );
234 }
236 if old_children.next().is_some() {
237 debug!(" removing extra old children");
238 debug_assert!(new_children.next().is_none());
239 if pushed {
240 change_list.pop_push_next_sibling();
241 } else {
242 change_list.push_first_child();
243 }
244 change_list.remove_self_and_next_siblings();
245 pushed = false;
246 } else {
247 debug!(" creating new children");
248 if pushed {
249 change_list.pop();
250 pushed = false;
251 }
252 create_children(
253 cached_set,
254 change_list,
255 registry,
256 new_children,
257 cached_roots,
258 );
259 }
261 debug!(" done updating children");
262 if pushed {
263 change_list.pop();
264 }
267fn create_children<'a, I>(
268 cached_set: &CachedSet,
269 change_list: &mut ChangeListBuilder,
270 registry: &mut EventsRegistry,
271 new: I,
272 cached_roots: &mut FxHashSet<CacheId>,
273) where
274 I: IntoIterator<Item = &'a Node<'a>>,
276 for child in new {
277 create(cached_set, change_list, registry, child, cached_roots);
278 change_list.append_child();
279 }
282fn remove_children(
283 change_list: &mut ChangeListBuilder,
284 registry: &mut EventsRegistry,
285 old: &[Node],
286) {
287 for child in old {
288 registry.remove_subtree(child);
289 }
290 // Fast way to remove all children: set the node's textContent to an empty
291 // string.
292 change_list.set_text("");
295fn create(
296 cached_set: &CachedSet,
297 change_list: &mut ChangeListBuilder,
298 registry: &mut EventsRegistry,
299 node: &Node,
300 cached_roots: &mut FxHashSet<CacheId>,
301) {
302 match node.kind {
303 NodeKind::Text(TextNode { text }) => {
304 change_list.create_text_node(text);
305 }
306 NodeKind::Element(ElementNode {
307 tag_name,
308 listeners,
309 attributes,
310 children,
311 namespace,
312 }) => {
313 if let Some(namespace) = namespace {
314 change_list.create_element_ns(tag_name, namespace);
315 } else {
316 change_list.create_element(tag_name);
317 }
318 for l in listeners {
319 unsafe {
320 registry.add(l);
321 }
322 change_list.new_event_listener(l);
323 }
324 for attr in attributes {
325 change_list.set_attribute(&attr.name, &attr.value);
326 }
327 for child in children {
328 create(cached_set, change_list, registry, child, cached_roots);
329 change_list.append_child();
330 }
331 }
332 NodeKind::Cached(ref c) => {
333 cached_roots.insert(c.id);
334 let node = cached_set.get(c.id);
335 create(cached_set, change_list, registry, node, cached_roots)
336 }
337 }