git.iko.soy/dodrio
on 03dc316 help sign in
dodrio/src/diff.rs
310 lines 10 kB history raw
1use crate::{
2 cached_set::{CacheId, CachedSet},
3 change_list::ChangeList,
4 events::EventsRegistry,
5 node::{Attribute, ElementNode, Listener, Node, NodeKind, TextNode},
6};
7use std::cmp;
9pub(crate) fn diff(
10 cached_set: &CachedSet,
11 change_list: &mut ChangeList,
12 registry: &mut EventsRegistry,
13 old: Node,
14 new: Node,
15 cached_roots: &mut bumpalo::collections::Vec<CacheId>,
16) {
17 match (&new.kind, &old.kind) {
18 (
19 &NodeKind::Text(TextNode { text: new_text }),
20 &NodeKind::Text(TextNode { text: old_text }),
21 ) => {
22 debug!(" both are text nodes");
23 if new_text != old_text {
24 debug!(" text needs updating");
25 change_list.emit_set_text(new_text);
26 }
27 }
29 (&NodeKind::Text(_), &NodeKind::Element(_)) => {
30 debug!(" replacing a text node with an element");
31 create(cached_set, change_list, registry, new, cached_roots);
32 registry.remove_subtree(&old);
33 change_list.emit_replace_with();
34 }
36 (&NodeKind::Element(_), &NodeKind::Text(_)) => {
37 debug!(" replacing an element with a text node");
38 create(cached_set, change_list, registry, new, cached_roots);
39 // Note: text nodes cannot have event listeners, so we don't need to
40 // remove the old node's listeners from our registry her.
41 change_list.emit_replace_with();
42 }
44 (
45 &NodeKind::Element(ElementNode {
46 tag_name: new_tag_name,
47 listeners: new_listeners,
48 attributes: new_attributes,
49 children: new_children,
50 namespace: new_namespace,
51 }),
52 &NodeKind::Element(ElementNode {
53 tag_name: old_tag_name,
54 listeners: old_listeners,
55 attributes: old_attributes,
56 children: old_children,
57 namespace: old_namespace,
58 }),
59 ) => {
60 debug!(" updating an element");
61 if new_tag_name != old_tag_name || new_namespace != old_namespace {
62 debug!(" different tag names or namespaces; creating new element and replacing old element");
63 create(cached_set, change_list, registry, new, cached_roots);
64 registry.remove_subtree(&old);
65 change_list.emit_replace_with();
66 return;
67 }
68 diff_listeners(change_list, registry, old_listeners, new_listeners);
69 diff_attributes(change_list, old_attributes, new_attributes);
70 diff_children(
71 cached_set,
72 change_list,
73 registry,
74 old_children,
75 new_children,
76 cached_roots,
77 );
78 }
80 // Both the new and old nodes are cached.
81 (&NodeKind::Cached(ref new), &NodeKind::Cached(ref old)) => {
82 cached_roots.push(new.id);
84 if new.id == old.id {
85 // This is the same cached node, so nothing has changed!
86 return;
87 }
89 let new = cached_set.get(new.id);
90 let old = cached_set.get(old.id);
91 diff(cached_set, change_list, registry, old, new, cached_roots);
92 }
94 // New cached node when the old node was not cached. In this scenario,
95 // we assume that they are pretty different, and it isn't worth diffing
96 // the subtrees, so we just create the new cached node afresh.
97 (&NodeKind::Cached(ref c), _) => {
98 cached_roots.push(c.id);
99 let new = cached_set.get(c.id);
100 create(cached_set, change_list, registry, new, cached_roots);
101 registry.remove_subtree(&old);
102 change_list.emit_replace_with();
103 }
105 // Old cached node and new non-cached node. Again, assume that they are
106 // probably pretty different and create the new non-cached node afresh.
107 (_, &NodeKind::Cached(_)) => {
108 create(cached_set, change_list, registry, new, cached_roots);
109 registry.remove_subtree(&old);
110 change_list.emit_replace_with();
111 }
112 }
115fn diff_listeners(
116 change_list: &mut ChangeList,
117 registry: &mut EventsRegistry,
118 old: &[Listener],
119 new: &[Listener],
120) {
121 debug!(" updating event listeners");
123 'outer1: for new_l in new {
124 unsafe {
125 // Safety relies on removing `new_l` from the registry manually at
126 // the end of its lifetime. This happens below in the `'outer2`
127 // loop, and elsewhere in diffing when removing old dom trees.
128 registry.add(new_l);
129 }
131 for old_l in old {
132 if new_l.event == old_l.event {
133 change_list.emit_update_event_listener(new_l);
134 continue 'outer1;
135 }
136 }
138 change_list.emit_new_event_listener(new_l);
139 }
141 'outer2: for old_l in old {
142 registry.remove(old_l);
144 for new_l in new {
145 if new_l.event == old_l.event {
146 continue 'outer2;
147 }
148 }
149 change_list.emit_remove_event_listener(old_l.event);
150 }
153fn diff_attributes(change_list: &mut ChangeList, old: &[Attribute], new: &[Attribute]) {
154 debug!(" updating attributes");
156 // Do O(n^2) passes to add/update and remove attributes, since
157 // there are almost always very few attributes.
158 'outer: for new_attr in new {
159 if new_attr.is_volatile() {
160 change_list.emit_set_attribute(new_attr.name, new_attr.value);
161 } else {
162 for old_attr in old {
163 if old_attr.name == new_attr.name {
164 if old_attr.value != new_attr.value {
165 change_list.emit_set_attribute(new_attr.name, new_attr.value);
166 }
167 continue 'outer;
168 }
169 }
170 change_list.emit_set_attribute(new_attr.name, new_attr.value);
171 }
172 }
174 'outer2: for old_attr in old {
175 for new_attr in new {
176 if old_attr.name == new_attr.name {
177 continue 'outer2;
178 }
179 }
180 change_list.emit_remove_attribute(old_attr.name);
181 }
184fn diff_children(
185 cached_set: &CachedSet,
186 change_list: &mut ChangeList,
187 registry: &mut EventsRegistry,
188 old: &[Node],
189 new: &[Node],
190 cached_roots: &mut bumpalo::collections::Vec<CacheId>,
191) {
192 debug!(" updating children shared by old and new");
194 let num_children_to_diff = cmp::min(new.len(), old.len());
195 let mut new_children = new.iter();
196 let mut old_children = old.iter();
197 let mut pushed = false;
199 for (i, (new_child, old_child)) in new_children
200 .by_ref()
201 .zip(old_children.by_ref())
202 .take(num_children_to_diff)
203 .enumerate()
204 {
205 if i == 0 {
206 change_list.emit_push_first_child();
207 pushed = true;
208 } else {
209 debug_assert!(pushed);
210 change_list.emit_pop_push_next_sibling();
211 }
213 diff(
214 cached_set,
215 change_list,
216 registry,
217 old_child.clone(),
218 new_child.clone(),
219 cached_roots,
220 );
221 }
223 if old_children.next().is_some() {
224 debug!(" removing extra old children");
225 debug_assert!(new_children.next().is_none());
226 if !pushed {
227 change_list.emit_push_first_child();
228 } else {
229 change_list.emit_pop_push_next_sibling();
230 }
231 change_list.emit_remove_self_and_next_siblings();
232 pushed = false;
233 } else {
234 debug!(" creating new children");
235 for (i, new_child) in new_children.enumerate() {
236 if i == 0 && pushed {
237 change_list.emit_pop();
238 pushed = false;
239 }
240 create(
241 cached_set,
242 change_list,
243 registry,
244 new_child.clone(),
245 cached_roots,
246 );
247 change_list.emit_append_child();
248 }
249 }
251 debug!(" done updating children");
252 if pushed {
253 change_list.emit_pop();
254 }
257fn create(
258 cached_set: &CachedSet,
259 change_list: &mut ChangeList,
260 registry: &mut EventsRegistry,
261 node: Node,
262 cached_roots: &mut bumpalo::collections::Vec<CacheId>,
263) {
264 match node.kind {
265 NodeKind::Text(TextNode { text }) => {
266 change_list.emit_create_text_node(text);
267 }
268 NodeKind::Element(ElementNode {
269 tag_name,
270 listeners,
271 attributes,
272 children,
273 namespace,
274 }) => {
275 if let Some(namespace) = namespace {
276 change_list.emit_create_element_ns(tag_name, namespace);
277 } else {
278 change_list.emit_create_element(tag_name);
279 }
280 for l in listeners {
281 unsafe {
282 registry.add(l);
283 }
284 change_list.emit_new_event_listener(l);
285 }
286 for attr in attributes {
287 if namespace.is_none() || attr.name.starts_with("xmlns") {
288 change_list.emit_set_attribute(&attr.name, &attr.value);
289 } else {
290 change_list.emit_set_attribute_ns(&attr.name, &attr.value);
291 }
292 }
293 for child in children {
294 create(
295 cached_set,
296 change_list,
297 registry,
298 child.clone(),
299 cached_roots,
300 );
301 change_list.emit_append_child();
302 }
303 }
304 NodeKind::Cached(c) => {
305 cached_roots.push(c.id);
306 let node = cached_set.get(c.id);
307 create(cached_set, change_list, registry, node, cached_roots)
308 }
309 }