git.iko.soy/dodrio
on 649bef1 help sign in
dodrio/src/diff.rs
327 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 debug!(" updating children shared by old and new");
202 let num_children_to_diff = cmp::min(new.len(), old.len());
203 let mut new_children = new.iter();
204 let mut old_children = old.iter();
205 let mut pushed = false;
207 for (i, (new_child, old_child)) in new_children
208 .by_ref()
209 .zip(old_children.by_ref())
210 .take(num_children_to_diff)
211 .enumerate()
212 {
213 if i == 0 {
214 change_list.push_first_child();
215 pushed = true;
216 } else {
217 debug_assert!(pushed);
218 change_list.pop_push_next_sibling();
219 }
221 diff(
222 cached_set,
223 change_list,
224 registry,
225 old_child.clone(),
226 new_child.clone(),
227 cached_roots,
228 );
229 }
231 if old_children.next().is_some() {
232 debug!(" removing extra old children");
233 debug_assert!(new_children.next().is_none());
234 if pushed {
235 change_list.pop_push_next_sibling();
236 } else {
237 change_list.push_first_child();
238 }
239 change_list.remove_self_and_next_siblings();
240 pushed = false;
241 } else {
242 debug!(" creating new children");
243 for (i, new_child) in new_children.enumerate() {
244 if i == 0 && pushed {
245 change_list.pop();
246 pushed = false;
247 }
248 create(
249 cached_set,
250 change_list,
251 registry,
252 new_child.clone(),
253 cached_roots,
254 );
255 change_list.append_child();
256 }
257 }
259 debug!(" done updating children");
260 if pushed {
261 change_list.pop();
262 }
265fn remove_children(
266 change_list: &mut ChangeListBuilder,
267 registry: &mut EventsRegistry,
268 old: &[Node],
269) {
270 for child in old {
271 registry.remove_subtree(child);
272 }
273 // Fast way to remove all children: set the node's textContent to an empty
274 // string.
275 change_list.set_text("");
278fn create(
279 cached_set: &CachedSet,
280 change_list: &mut ChangeListBuilder,
281 registry: &mut EventsRegistry,
282 node: Node,
283 cached_roots: &mut FxHashSet<CacheId>,
284) {
285 match node.kind {
286 NodeKind::Text(TextNode { text }) => {
287 change_list.create_text_node(text);
288 }
289 NodeKind::Element(ElementNode {
290 tag_name,
291 listeners,
292 attributes,
293 children,
294 namespace,
295 }) => {
296 if let Some(namespace) = namespace {
297 change_list.create_element_ns(tag_name, namespace);
298 } else {
299 change_list.create_element(tag_name);
300 }
301 for l in listeners {
302 unsafe {
303 registry.add(l);
304 }
305 change_list.new_event_listener(l);
306 }
307 for attr in attributes {
308 change_list.set_attribute(&attr.name, &attr.value);
309 }
310 for child in children {
311 create(
312 cached_set,
313 change_list,
314 registry,
315 child.clone(),
316 cached_roots,
317 );
318 change_list.append_child();
319 }
320 }
321 NodeKind::Cached(c) => {
322 cached_roots.insert(c.id);
323 let node = cached_set.get(c.id);
324 create(cached_set, change_list, registry, node, cached_roots)
325 }
326 }