git.iko.soy/dodrio
on 102ea64 help sign in
dodrio/src/diff.rs
933 lines 32 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::{FxHashMap, FxHashSet};
8use std::cmp::Ordering;
9use std::u32;
10use wasm_bindgen::UnwrapThrowExt;
12// Diff the `old` node with the `new` node. Emits instructions to modify a
13// physical DOM node that reflects `old` into something that reflects `new`.
14//
15// Upon entry to this function, the physical DOM node must be on the top of the
16// change list stack:
17//
18// [... node]
19//
20// The change list stack is in the same state when this function exits.
21pub(crate) fn diff(
22 cached_set: &CachedSet,
23 change_list: &mut ChangeListBuilder,
24 registry: &mut EventsRegistry,
25 old: &Node,
26 new: &Node,
27 cached_roots: &mut FxHashSet<CacheId>,
28) {
29 match (&new.kind, &old.kind) {
30 (
31 &NodeKind::Text(TextNode { text: new_text }),
32 &NodeKind::Text(TextNode { text: old_text }),
33 ) => {
34 if new_text != old_text {
35 change_list.commit_traversal();
36 change_list.set_text(new_text);
37 }
38 }
40 (&NodeKind::Text(_), &NodeKind::Element(_)) => {
41 change_list.commit_traversal();
42 create(cached_set, change_list, registry, new, cached_roots);
43 registry.remove_subtree(&old);
44 change_list.replace_with();
45 }
47 (&NodeKind::Element(_), &NodeKind::Text(_)) => {
48 change_list.commit_traversal();
49 create(cached_set, change_list, registry, new, cached_roots);
50 // Note: text nodes cannot have event listeners, so we don't need to
51 // remove the old node's listeners from our registry her.
52 change_list.replace_with();
53 }
55 (
56 &NodeKind::Element(ElementNode {
57 key: _,
58 tag_name: new_tag_name,
59 listeners: new_listeners,
60 attributes: new_attributes,
61 children: new_children,
62 namespace: new_namespace,
63 }),
64 &NodeKind::Element(ElementNode {
65 key: _,
66 tag_name: old_tag_name,
67 listeners: old_listeners,
68 attributes: old_attributes,
69 children: old_children,
70 namespace: old_namespace,
71 }),
72 ) => {
73 if new_tag_name != old_tag_name || new_namespace != old_namespace {
74 change_list.commit_traversal();
75 create(cached_set, change_list, registry, new, cached_roots);
76 registry.remove_subtree(&old);
77 change_list.replace_with();
78 return;
79 }
80 diff_listeners(change_list, registry, old_listeners, new_listeners);
81 diff_attributes(change_list, old_attributes, new_attributes);
82 diff_children(
83 cached_set,
84 change_list,
85 registry,
86 old_children,
87 new_children,
88 cached_roots,
89 );
90 }
92 // Both the new and old nodes are cached.
93 (&NodeKind::Cached(ref new), &NodeKind::Cached(ref old)) => {
94 cached_roots.insert(new.id);
96 if new.id == old.id {
97 // This is the same cached node, so nothing has changed!
98 return;
99 }
101 let new = cached_set.get(new.id);
102 let old = cached_set.get(old.id);
103 diff(cached_set, change_list, registry, old, new, cached_roots);
104 }
106 // New cached node when the old node was not cached. In this scenario,
107 // we assume that they are pretty different, and it isn't worth diffing
108 // the subtrees, so we just create the new cached node afresh.
109 (&NodeKind::Cached(ref c), _) => {
110 change_list.commit_traversal();
111 cached_roots.insert(c.id);
112 let new = cached_set.get(c.id);
113 create(cached_set, change_list, registry, new, cached_roots);
114 registry.remove_subtree(&old);
115 change_list.replace_with();
116 }
118 // Old cached node and new non-cached node. Again, assume that they are
119 // probably pretty different and create the new non-cached node afresh.
120 (_, &NodeKind::Cached(_)) => {
121 change_list.commit_traversal();
122 create(cached_set, change_list, registry, new, cached_roots);
123 registry.remove_subtree(&old);
124 change_list.replace_with();
125 }
126 }
129// Diff event listeners between `old` and `new`.
130//
131// The listeners' node must be on top of the change list stack:
132//
133// [... node]
134//
135// The change list stack is left unchanged.
136fn diff_listeners(
137 change_list: &mut ChangeListBuilder,
138 registry: &mut EventsRegistry,
139 old: &[Listener],
140 new: &[Listener],
141) {
142 if !old.is_empty() || !new.is_empty() {
143 change_list.commit_traversal();
144 }
146 'outer1: for new_l in new {
147 unsafe {
148 // Safety relies on removing `new_l` from the registry manually at
149 // the end of its lifetime. This happens below in the `'outer2`
150 // loop, and elsewhere in diffing when removing old dom trees.
151 registry.add(new_l);
152 }
154 for old_l in old {
155 if new_l.event == old_l.event {
156 change_list.update_event_listener(new_l);
157 continue 'outer1;
158 }
159 }
161 change_list.new_event_listener(new_l);
162 }
164 'outer2: for old_l in old {
165 registry.remove(old_l);
167 for new_l in new {
168 if new_l.event == old_l.event {
169 continue 'outer2;
170 }
171 }
172 change_list.remove_event_listener(old_l.event);
173 }
176// Diff a node's attributes.
177//
178// The attributes' node must be on top of the change list stack:
179//
180// [... node]
181//
182// The change list stack is left unchanged.
183fn diff_attributes(change_list: &mut ChangeListBuilder, old: &[Attribute], new: &[Attribute]) {
184 // Do O(n^2) passes to add/update and remove attributes, since
185 // there are almost always very few attributes.
186 'outer: for new_attr in new {
187 if new_attr.is_volatile() {
188 change_list.commit_traversal();
189 change_list.set_attribute(new_attr.name, new_attr.value);
190 } else {
191 for old_attr in old {
192 if old_attr.name == new_attr.name {
193 if old_attr.value != new_attr.value {
194 change_list.commit_traversal();
195 change_list.set_attribute(new_attr.name, new_attr.value);
196 }
197 continue 'outer;
198 }
199 }
201 change_list.commit_traversal();
202 change_list.set_attribute(new_attr.name, new_attr.value);
203 }
204 }
206 'outer2: for old_attr in old {
207 for new_attr in new {
208 if old_attr.name == new_attr.name {
209 continue 'outer2;
210 }
211 }
213 change_list.commit_traversal();
214 change_list.remove_attribute(old_attr.name);
215 }
218// Diff the given set of old and new children.
219//
220// The parent must be on top of the change list stack when this function is
221// entered:
222//
223// [... parent]
224//
225// the change list stack is in the same state when this function returns.
226fn diff_children(
227 cached_set: &CachedSet,
228 change_list: &mut ChangeListBuilder,
229 registry: &mut EventsRegistry,
230 old: &[Node],
231 new: &[Node],
232 cached_roots: &mut FxHashSet<CacheId>,
233) {
234 if new.is_empty() {
235 if !old.is_empty() {
236 change_list.commit_traversal();
237 remove_all_children(change_list, registry, old);
238 }
239 return;
240 }
242 if old.is_empty() {
243 if !new.is_empty() {
244 change_list.commit_traversal();
245 create_and_append_children(cached_set, change_list, registry, new, cached_roots);
246 }
247 return;
248 }
250 let new_is_keyed = new[0].key().is_some();
251 let old_is_keyed = old[0].key().is_some();
253 debug_assert!(
254 new.iter().all(|n| n.key().is_some() == new_is_keyed),
255 "all siblings must be keyed or all siblings must be non-keyed"
256 );
257 debug_assert!(
258 old.iter().all(|o| o.key().is_some() == old_is_keyed),
259 "all siblings must be keyed or all siblings must be non-keyed"
260 );
262 if new_is_keyed && old_is_keyed {
263 let t = change_list.next_temporary();
264 diff_keyed_children(cached_set, change_list, registry, old, new, cached_roots);
265 change_list.set_next_temporary(t);
266 } else {
267 diff_non_keyed_children(cached_set, change_list, registry, old, new, cached_roots);
268 }
271// Diffing "keyed" children.
272//
273// With keyed children, we care about whether we delete, move, or create nodes
274// versus mutate existing nodes in place. Presumably there is some sort of CSS
275// transition animation that makes the virtual DOM diffing algorithm
276// observable. By specifying keys for nodes, we know which virtual DOM nodes
277// must reuse (or not reuse) the same physical DOM nodes.
278//
279// This is loosely based on Inferno's keyed patching implementation. However, we
280// have to modify the algorithm since we are compiling the diff down into change
281// list instructions that will be executed later, rather than applying the
282// changes to the DOM directly as we compare virtual DOMs.
283//
284// https://github.com/infernojs/inferno/blob/36fd96/packages/inferno/src/DOM/patching.ts#L530-L739
285//
286// When entering this function, the parent must be on top of the change list
287// stack:
288//
289// [... parent]
290//
291// Upon exiting, the change list stack is in the same state.
292fn diff_keyed_children(
293 cached_set: &CachedSet,
294 change_list: &mut ChangeListBuilder,
295 registry: &mut EventsRegistry,
296 old: &[Node],
297 new: &[Node],
298 cached_roots: &mut FxHashSet<CacheId>,
299) {
300 if cfg!(debug_assertions) {
301 let mut keys = FxHashSet::default();
302 let mut assert_unique_keys = |children: &[Node]| {
303 keys.clear();
304 for child in children {
305 let key = child.key();
306 debug_assert!(
307 key.is_some(),
308 "if any sibling is keyed, all siblings must be keyed"
309 );
310 keys.insert(key);
311 }
312 debug_assert_eq!(
313 children.len(),
314 keys.len(),
315 "keyed siblings must each have a unique key"
316 );
317 };
318 assert_unique_keys(old);
319 assert_unique_keys(new);
320 }
322 // First up, we diff all the nodes with the same key at the beginning of the
323 // children.
324 //
325 // `shared_prefix_count` is the count of how many nodes at the start of
326 // `new` and `old` share the same keys.
327 let shared_prefix_count =
328 match diff_keyed_prefix(cached_set, change_list, registry, old, new, cached_roots) {
329 KeyedPrefixResult::Finished => return,
330 KeyedPrefixResult::MoreWorkToDo(count) => count,
331 };
333 // Next, we find out how many of the nodes at the end of the children have
334 // the same key. We do _not_ diff them yet, since we want to emit the change
335 // list instructions such that they can be applied in a single pass over the
336 // DOM. Instead, we just save this information for later.
337 //
338 // `shared_suffix_count` is the count of how many nodes at the end of `new`
339 // and `old` share the same keys.
340 let shared_suffix_count = old[shared_prefix_count..]
341 .iter()
342 .rev()
343 .zip(new[shared_prefix_count..].iter().rev())
344 .take_while(|&(old, new)| old.key() == new.key())
345 .count();
347 let old_shared_suffix_start = old.len() - shared_suffix_count;
348 let new_shared_suffix_start = new.len() - shared_suffix_count;
350 // Ok, we now hopefully have a smaller range of children in the middle
351 // within which to re-order nodes with the same keys, remove old nodes with
352 // now-unused keys, and create new nodes with fresh keys.
353 diff_keyed_middle(
354 cached_set,
355 change_list,
356 registry,
357 &old[shared_prefix_count..old_shared_suffix_start],
358 &new[shared_prefix_count..new_shared_suffix_start],
359 cached_roots,
360 shared_prefix_count,
361 shared_suffix_count,
362 old_shared_suffix_start,
363 );
365 // Finally, diff the nodes at the end of `old` and `new` that share keys.
366 let old_suffix = &old[old_shared_suffix_start..];
367 let new_suffix = &new[new_shared_suffix_start..];
368 debug_assert_eq!(old_suffix.len(), new_suffix.len());
369 if !old_suffix.is_empty() {
370 diff_keyed_suffix(
371 cached_set,
372 change_list,
373 registry,
374 old_suffix,
375 new_suffix,
376 cached_roots,
377 new_shared_suffix_start,
378 );
379 }
382enum KeyedPrefixResult {
383 // Fast path: we finished diffing all the children just by looking at the
384 // prefix of shared keys!
385 Finished,
386 // There is more diffing work to do. Here is a count of how many children at
387 // the beginning of `new` and `old` we already processed.
388 MoreWorkToDo(usize),
391// Diff the prefix of children in `new` and `old` that share the same keys in
392// the same order.
393//
394// Upon entry of this function, the change list stack must be:
395//
396// [... parent]
397//
398// Upon exit, the change list stack is the same.
399fn diff_keyed_prefix(
400 cached_set: &CachedSet,
401 change_list: &mut ChangeListBuilder,
402 registry: &mut EventsRegistry,
403 old: &[Node],
404 new: &[Node],
405 cached_roots: &mut FxHashSet<CacheId>,
406) -> KeyedPrefixResult {
407 change_list.go_down();
408 let mut shared_prefix_count = 0;
410 for (i, (old, new)) in old.iter().zip(new.iter()).enumerate() {
411 if old.key() != new.key() {
412 break;
413 }
415 change_list.go_to_sibling(i);
416 diff(cached_set, change_list, registry, old, new, cached_roots);
417 shared_prefix_count += 1;
418 }
420 // If that was all of the old children, then create and append the remaining
421 // new children and we're finished.
422 if shared_prefix_count == old.len() {
423 change_list.go_up();
424 change_list.commit_traversal();
425 create_and_append_children(
426 cached_set,
427 change_list,
428 registry,
429 &new[shared_prefix_count..],
430 cached_roots,
431 );
432 return KeyedPrefixResult::Finished;
433 }
435 // And if that was all of the new children, then remove all of the remaining
436 // old children and we're finished.
437 if shared_prefix_count == new.len() {
438 change_list.go_to_sibling(shared_prefix_count);
439 change_list.commit_traversal();
440 remove_self_and_next_siblings(change_list, registry, &old[shared_prefix_count..]);
441 return KeyedPrefixResult::Finished;
442 }
444 change_list.go_up();
445 KeyedPrefixResult::MoreWorkToDo(shared_prefix_count)
448// The most-general, expensive code path for keyed children diffing.
449//
450// We find the longest subsequence within `old` of children that are relatively
451// ordered the same way in `new` (via finding a longest-increasing-subsequence
452// of the old child's index within `new`). The children that are elements of
453// this subsequence will remain in place, minimizing the number of DOM moves we
454// will have to do.
455//
456// Upon entry to this function, the change list stack must be:
457//
458// [... parent]
459//
460// Upon exit from this function, it will be restored to that same state.
461fn diff_keyed_middle(
462 cached_set: &CachedSet,
463 change_list: &mut ChangeListBuilder,
464 registry: &mut EventsRegistry,
465 old: &[Node],
466 mut new: &[Node],
467 cached_roots: &mut FxHashSet<CacheId>,
468 shared_prefix_count: usize,
469 shared_suffix_count: usize,
470 old_shared_suffix_start: usize,
471) {
472 // Should have already diffed the shared-key prefixes and suffixes.
473 debug_assert_ne!(new.first().map(|n| n.key()), old.first().map(|o| o.key()));
474 debug_assert_ne!(new.last().map(|n| n.key()), old.last().map(|o| o.key()));
476 // The algorithm below relies upon using `u32::MAX` as a sentinel
477 // value, so if we have that many new nodes, it won't work. This
478 // check is a bit academic (hence only enabled in debug), since
479 // wasm32 doesn't have enough address space to hold that many nodes
480 // in memory.
481 debug_assert!(new.len() < u32::MAX as usize);
483 // Map from each `old` node's key to its index within `old`.
484 let mut old_key_to_old_index = FxHashMap::default();
485 old_key_to_old_index.reserve(old.len());
486 old_key_to_old_index.extend(old.iter().enumerate().map(|(i, o)| (o.key(), i)));
488 // The set of shared keys between `new` and `old`.
489 let mut shared_keys = FxHashSet::default();
490 // Map from each index in `new` to the index of the node in `old` that
491 // has the same key.
492 let mut new_index_to_old_index = Vec::with_capacity(new.len());
493 new_index_to_old_index.extend(new.iter().map(|n| {
494 let key = n.key();
495 if let Some(&i) = old_key_to_old_index.get(&key) {
496 shared_keys.insert(key);
497 i
498 } else {
499 u32::MAX as usize
500 }
501 }));
503 // If none of the old keys are reused by the new children, then we
504 // remove all the remaining old children and create the new children
505 // afresh.
506 if shared_suffix_count == 0 && shared_keys.is_empty() {
507 if shared_prefix_count == 0 {
508 change_list.commit_traversal();
509 remove_all_children(change_list, registry, old);
510 } else {
511 change_list.go_down_to_child(shared_prefix_count);
512 change_list.commit_traversal();
513 remove_self_and_next_siblings(change_list, registry, &old[shared_prefix_count..]);
514 }
515 create_and_append_children(cached_set, change_list, registry, new, cached_roots);
516 return;
517 }
519 // Save each of the old children whose keys are reused in the new
520 // children.
521 let mut old_index_to_temp = vec![u32::MAX; old.len()];
522 let mut start = 0;
523 loop {
524 let end = (start..old.len())
525 .find(|&i| {
526 let key = old[i].key();
527 !shared_keys.contains(&key)
528 })
529 .unwrap_or(old.len());
531 if end - start > 0 {
532 change_list.commit_traversal();
533 let mut t = change_list.save_children_to_temporaries(
534 shared_prefix_count + start,
535 shared_prefix_count + end,
536 );
537 for i in start..end {
538 old_index_to_temp[i] = t;
539 t += 1;
540 }
541 }
543 debug_assert!(end <= old.len());
544 if end == old.len() {
545 break;
546 } else {
547 start = end + 1;
548 }
549 }
551 // Remove any old children whose keys were not reused in the new
552 // children. Remove from the end first so that we don't mess up indices.
553 let mut removed_count = 0;
554 for (i, old_child) in old.iter().enumerate().rev() {
555 if !shared_keys.contains(&old_child.key()) {
556 registry.remove_subtree(old_child);
557 change_list.commit_traversal();
558 change_list.remove_child(i + shared_prefix_count);
559 removed_count += 1;
560 }
561 }
563 // If there aren't any more new children, then we are done!
564 if new.is_empty() {
565 return;
566 }
568 // The longest increasing subsequence within `new_index_to_old_index`. This
569 // is the longest sequence on DOM nodes in `old` that are relatively ordered
570 // correctly within `new`. We will leave these nodes in place in the DOM,
571 // and only move nodes that are not part of the LIS. This results in the
572 // maximum number of DOM nodes left in place, AKA the minimum number of DOM
573 // nodes moved.
574 let mut new_index_is_in_lis = FxHashSet::default();
575 new_index_is_in_lis.reserve(new_index_to_old_index.len());
576 let mut predecessors = vec![0; new_index_to_old_index.len()];
577 let mut starts = vec![0; new_index_to_old_index.len()];
578 longest_increasing_subsequence::lis_with(
579 &new_index_to_old_index,
580 &mut new_index_is_in_lis,
581 |a, b| a < b,
582 &mut predecessors,
583 &mut starts,
584 );
586 // Now we will iterate from the end of the new children back to the
587 // beginning, diffing old children we are reusing and if they aren't in the
588 // LIS moving them to their new destination, or creating new children. Note
589 // that iterating in reverse order lets us use `Node.prototype.insertBefore`
590 // to move/insert children.
591 //
592 // But first, we ensure that we have a child on the change list stack that
593 // we can `insertBefore`. We handle this once before looping over `new`
594 // children, so that we don't have to keep checking on every loop iteration.
595 if shared_suffix_count > 0 {
596 // There is a shared suffix after these middle children. We will be
597 // inserting before that shared suffix, so add the first child of that
598 // shared suffix to the change list stack.
599 //
600 // [... parent]
601 change_list.go_down_to_child(old_shared_suffix_start - removed_count);
602 // [... parent first_child_of_shared_suffix]
603 } else {
604 // There is no shared suffix coming after these middle children.
605 // Therefore we have to process the last child in `new` and move it to
606 // the end of the parent's children if it isn't already there.
607 let last_index = new.len() - 1;
608 let last = new.last().unwrap_throw();
609 new = &new[..new.len() - 1];
610 if shared_keys.contains(&last.key()) {
611 let old_index = new_index_to_old_index[last_index];
612 let temp = old_index_to_temp[old_index];
613 // [... parent]
614 change_list.go_down_to_temp_child(temp);
615 // [... parent last]
616 diff(
617 cached_set,
618 change_list,
619 registry,
620 &old[old_index],
621 last,
622 cached_roots,
623 );
624 if new_index_is_in_lis.contains(&last_index) {
625 // Don't move it, since it is already where it needs to be.
626 } else {
627 change_list.commit_traversal();
628 // [... parent last]
629 change_list.append_child();
630 // [... parent]
631 change_list.go_down_to_temp_child(temp);
632 // [... parent last]
633 }
634 } else {
635 change_list.commit_traversal();
636 // [... parent]
637 create(cached_set, change_list, registry, last, cached_roots);
638 // [... parent last]
639 change_list.append_child();
640 // [... parent]
641 change_list.go_down_to_reverse_child(0);
642 // [... parent last]
643 }
644 }
646 for (new_index, new_child) in new.iter().enumerate().rev() {
647 let old_index = new_index_to_old_index[new_index];
648 if old_index == u32::MAX as usize {
649 debug_assert!(!shared_keys.contains(&new_child.key()));
650 change_list.commit_traversal();
651 // [... parent successor]
652 create(cached_set, change_list, registry, new_child, cached_roots);
653 // [... parent successor new_child]
654 change_list.insert_before();
655 // [... parent new_child]
656 } else {
657 debug_assert!(shared_keys.contains(&new_child.key()));
658 let temp = old_index_to_temp[old_index];
659 debug_assert_ne!(temp, u32::MAX);
661 if new_index_is_in_lis.contains(&new_index) {
662 // [... parent successor]
663 change_list.go_to_temp_sibling(temp);
664 // [... parent new_child]
665 } else {
666 change_list.commit_traversal();
667 // [... parent successor]
668 change_list.push_temporary(temp);
669 // [... parent successor new_child]
670 change_list.insert_before();
671 // [... parent new_child]
672 }
674 diff(
675 cached_set,
676 change_list,
677 registry,
678 &old[old_index],
679 new_child,
680 cached_roots,
681 );
682 }
683 }
685 // [... parent child]
686 change_list.go_up();
687 // [... parent]
690// Diff the suffix of keyed children that share the same keys in the same order.
691//
692// The parent must be on the change list stack when we enter this function:
693//
694// [... parent]
695//
696// When this function exits, the change list stack remains the same.
697fn diff_keyed_suffix(
698 cached_set: &CachedSet,
699 change_list: &mut ChangeListBuilder,
700 registry: &mut EventsRegistry,
701 old: &[Node],
702 new: &[Node],
703 cached_roots: &mut FxHashSet<CacheId>,
704 new_shared_suffix_start: usize,
705) {
706 debug_assert_eq!(old.len(), new.len());
707 debug_assert!(!old.is_empty());
709 // [... parent]
710 change_list.go_down();
711 // [... parent new_child]
713 for (i, (old_child, new_child)) in old.iter().zip(new.iter()).enumerate() {
714 change_list.go_to_sibling(new_shared_suffix_start + i);
715 diff(
716 cached_set,
717 change_list,
718 registry,
719 old_child,
720 new_child,
721 cached_roots,
722 );
723 }
725 // [... parent]
726 change_list.go_up();
729// Diff children that are not keyed.
730//
731// The parent must be on the top of the change list stack when entering this
732// function:
733//
734// [... parent]
735//
736// the change list stack is in the same state when this function returns.
737fn diff_non_keyed_children(
738 cached_set: &CachedSet,
739 change_list: &mut ChangeListBuilder,
740 registry: &mut EventsRegistry,
741 old: &[Node],
742 new: &[Node],
743 cached_roots: &mut FxHashSet<CacheId>,
744) {
745 // Handled these cases in `diff_children` before calling this function.
746 debug_assert!(!new.is_empty());
747 debug_assert!(!old.is_empty());
749 // [... parent]
750 change_list.go_down();
751 // [... parent child]
753 for (i, (new_child, old_child)) in new.iter().zip(old.iter()).enumerate() {
754 // [... parent prev_child]
755 change_list.go_to_sibling(i);
756 // [... parent this_child]
757 diff(
758 cached_set,
759 change_list,
760 registry,
761 old_child,
762 new_child,
763 cached_roots,
764 );
765 }
767 match old.len().cmp(&new.len()) {
768 Ordering::Greater => {
769 // [... parent prev_child]
770 change_list.go_to_sibling(new.len());
771 // [... parent first_child_to_remove]
772 change_list.commit_traversal();
773 remove_self_and_next_siblings(change_list, registry, &old[new.len()..]);
774 // [... parent]
775 }
776 Ordering::Less => {
777 // [... parent last_child]
778 change_list.go_up();
779 // [... parent]
780 change_list.commit_traversal();
781 create_and_append_children(
782 cached_set,
783 change_list,
784 registry,
785 &new[old.len()..],
786 cached_roots,
787 );
788 }
789 Ordering::Equal => {
790 // [... parent child]
791 change_list.go_up();
792 // [... parent]
793 }
794 }
797// Create the given children and append them to the parent node.
798//
799// The parent node must currently be on top of the change list stack:
800//
801// [... parent]
802//
803// When this function returns, the change list stack is in the same state.
804fn create_and_append_children(
805 cached_set: &CachedSet,
806 change_list: &mut ChangeListBuilder,
807 registry: &mut EventsRegistry,
808 new: &[Node],
809 cached_roots: &mut FxHashSet<CacheId>,
810) {
811 debug_assert!(change_list.traversal_is_committed());
812 for child in new {
813 create(cached_set, change_list, registry, child, cached_roots);
814 change_list.append_child();
815 }
818// Remove all of a node's children.
819//
820// The change list stack must have this shape upon entry to this function:
821//
822// [... parent]
823//
824// When this function returns, the change list stack is in the same state.
825fn remove_all_children(
826 change_list: &mut ChangeListBuilder,
827 registry: &mut EventsRegistry,
828 old: &[Node],
829) {
830 debug_assert!(change_list.traversal_is_committed());
831 for child in old {
832 registry.remove_subtree(child);
833 }
834 // Fast way to remove all children: set the node's textContent to an empty
835 // string.
836 change_list.set_text("");
839// Remove the current child and all of its following siblings.
840//
841// The change list stack must have this shape upon entry to this function:
842//
843// [... parent child]
844//
845// After the function returns, the child is no longer on the change list stack:
846//
847// [... parent]
848fn remove_self_and_next_siblings(
849 change_list: &mut ChangeListBuilder,
850 registry: &mut EventsRegistry,
851 old: &[Node],
852) {
853 debug_assert!(change_list.traversal_is_committed());
854 for child in old {
855 registry.remove_subtree(child);
856 }
857 change_list.remove_self_and_next_siblings();
860// Emit instructions to create the given virtual node.
861//
862// The change list stack may have any shape upon entering this function:
863//
864// [...]
865//
866// When this function returns, the new node is on top of the change list stack:
867//
868// [... node]
869fn create(
870 cached_set: &CachedSet,
871 change_list: &mut ChangeListBuilder,
872 registry: &mut EventsRegistry,
873 node: &Node,
874 cached_roots: &mut FxHashSet<CacheId>,
875) {
876 debug_assert!(change_list.traversal_is_committed());
877 match node.kind {
878 NodeKind::Text(TextNode { text }) => {
879 change_list.create_text_node(text);
880 }
881 NodeKind::Element(&ElementNode {
882 key: _,
883 tag_name,
884 listeners,
885 attributes,
886 children,
887 namespace,
888 }) => {
889 if let Some(namespace) = namespace {
890 change_list.create_element_ns(tag_name, namespace);
891 } else {
892 change_list.create_element(tag_name);
893 }
895 for l in listeners {
896 unsafe {
897 registry.add(l);
898 }
899 change_list.new_event_listener(l);
900 }
902 for attr in attributes {
903 change_list.set_attribute(&attr.name, &attr.value);
904 }
906 // Fast path: if there is a single text child, it is faster to
907 // create-and-append the text node all at once via setting the
908 // parent's `textContent` in a single change list instruction than
909 // to emit three instructions to (1) create a text node, (2) set its
910 // text content, and finally (3) append the text node to this
911 // parent.
912 if children.len() == 1 {
913 if let Node {
914 kind: NodeKind::Text(TextNode { text }),
915 } = children[0]
916 {
917 change_list.set_text(text);
918 return;
919 }
920 }
922 for child in children {
923 create(cached_set, change_list, registry, child, cached_roots);
924 change_list.append_child();
925 }
926 }
927 NodeKind::Cached(ref c) => {
928 cached_roots.insert(c.id);
929 let node = cached_set.get(c.id);
930 create(cached_set, change_list, registry, node, cached_roots)
931 }
932 }