git.iko.soy/dodrio
on 97d6f40 help sign in
dodrio/src/diff.rs
307 lines 9.7 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 debug!(" updating children shared by old and new");
195 let num_children_to_diff = cmp::min(new.len(), old.len());
196 let mut new_children = new.iter();
197 let mut old_children = old.iter();
198 let mut pushed = false;
200 for (i, (new_child, old_child)) in new_children
201 .by_ref()
202 .zip(old_children.by_ref())
203 .take(num_children_to_diff)
204 .enumerate()
205 {
206 if i == 0 {
207 change_list.push_first_child();
208 pushed = true;
209 } else {
210 debug_assert!(pushed);
211 change_list.pop_push_next_sibling();
212 }
214 diff(
215 cached_set,
216 change_list,
217 registry,
218 old_child.clone(),
219 new_child.clone(),
220 cached_roots,
221 );
222 }
224 if old_children.next().is_some() {
225 debug!(" removing extra old children");
226 debug_assert!(new_children.next().is_none());
227 if pushed {
228 change_list.pop_push_next_sibling();
229 } else {
230 change_list.push_first_child();
231 }
232 change_list.remove_self_and_next_siblings();
233 pushed = false;
234 } else {
235 debug!(" creating new children");
236 for (i, new_child) in new_children.enumerate() {
237 if i == 0 && pushed {
238 change_list.pop();
239 pushed = false;
240 }
241 create(
242 cached_set,
243 change_list,
244 registry,
245 new_child.clone(),
246 cached_roots,
247 );
248 change_list.append_child();
249 }
250 }
252 debug!(" done updating children");
253 if pushed {
254 change_list.pop();
255 }
258fn create(
259 cached_set: &CachedSet,
260 change_list: &mut ChangeListBuilder,
261 registry: &mut EventsRegistry,
262 node: Node,
263 cached_roots: &mut FxHashSet<CacheId>,
264) {
265 match node.kind {
266 NodeKind::Text(TextNode { text }) => {
267 change_list.create_text_node(text);
268 }
269 NodeKind::Element(ElementNode {
270 tag_name,
271 listeners,
272 attributes,
273 children,
274 namespace,
275 }) => {
276 if let Some(namespace) = namespace {
277 change_list.create_element_ns(tag_name, namespace);
278 } else {
279 change_list.create_element(tag_name);
280 }
281 for l in listeners {
282 unsafe {
283 registry.add(l);
284 }
285 change_list.new_event_listener(l);
286 }
287 for attr in attributes {
288 change_list.set_attribute(&attr.name, &attr.value);
289 }
290 for child in children {
291 create(
292 cached_set,
293 change_list,
294 registry,
295 child.clone(),
296 cached_roots,
297 );
298 change_list.append_child();
299 }
300 }
301 NodeKind::Cached(c) => {
302 cached_roots.insert(c.id);
303 let node = cached_set.get(c.id);
304 create(cached_set, change_list, registry, node, cached_roots)
305 }
306 }