git.iko.soy/dodrio
on 13db0a6 help sign in
dodrio/src/diff.rs
1125 lines 37 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, new_template) = cached_set.get(new.id);
102 let (old, old_template) = cached_set.get(old.id);
103 if new_template == old_template {
104 // If they are both using the same template, then just diff the
105 // subtrees.
106 diff(cached_set, change_list, registry, old, new, cached_roots);
107 } else {
108 // Otherwise, they are probably different enough that
109 // re-constructing the subtree from scratch should be faster.
110 // This doubly holds true if we have a new template.
111 change_list.commit_traversal();
112 create_and_replace(
113 cached_set,
114 change_list,
115 registry,
116 new_template,
117 old,
118 new,
119 cached_roots,
120 );
121 }
122 }
124 // New cached node when the old node was not cached. In this scenario,
125 // we assume that they are pretty different, and it isn't worth diffing
126 // the subtrees, so we just create the new cached node afresh.
127 (&NodeKind::Cached(ref c), _) => {
128 change_list.commit_traversal();
129 cached_roots.insert(c.id);
130 let (new, new_template) = cached_set.get(c.id);
131 create_and_replace(
132 cached_set,
133 change_list,
134 registry,
135 new_template,
136 old,
137 new,
138 cached_roots,
139 );
140 }
142 // Old cached node and new non-cached node. Again, assume that they are
143 // probably pretty different and create the new non-cached node afresh.
144 (_, &NodeKind::Cached(_)) => {
145 change_list.commit_traversal();
146 create(cached_set, change_list, registry, new, cached_roots);
147 registry.remove_subtree(&old);
148 change_list.replace_with();
149 }
150 }
153// Diff event listeners between `old` and `new`.
154//
155// The listeners' node must be on top of the change list stack:
156//
157// [... node]
158//
159// The change list stack is left unchanged.
160fn diff_listeners(
161 change_list: &mut ChangeListBuilder,
162 registry: &mut EventsRegistry,
163 old: &[Listener],
164 new: &[Listener],
165) {
166 if !old.is_empty() || !new.is_empty() {
167 change_list.commit_traversal();
168 }
170 'outer1: for new_l in new {
171 unsafe {
172 // Safety relies on removing `new_l` from the registry manually at
173 // the end of its lifetime. This happens below in the `'outer2`
174 // loop, and elsewhere in diffing when removing old dom trees.
175 registry.add(new_l);
176 }
178 for old_l in old {
179 if new_l.event == old_l.event {
180 change_list.update_event_listener(new_l);
181 continue 'outer1;
182 }
183 }
185 change_list.new_event_listener(new_l);
186 }
188 'outer2: for old_l in old {
189 registry.remove(old_l);
191 for new_l in new {
192 if new_l.event == old_l.event {
193 continue 'outer2;
194 }
195 }
196 change_list.remove_event_listener(old_l.event);
197 }
200// Diff a node's attributes.
201//
202// The attributes' node must be on top of the change list stack:
203//
204// [... node]
205//
206// The change list stack is left unchanged.
207fn diff_attributes(change_list: &mut ChangeListBuilder, old: &[Attribute], new: &[Attribute]) {
208 // Do O(n^2) passes to add/update and remove attributes, since
209 // there are almost always very few attributes.
210 'outer: for new_attr in new {
211 if new_attr.is_volatile() {
212 change_list.commit_traversal();
213 change_list.set_attribute(new_attr.name, new_attr.value);
214 } else {
215 for old_attr in old {
216 if old_attr.name == new_attr.name {
217 if old_attr.value != new_attr.value {
218 change_list.commit_traversal();
219 change_list.set_attribute(new_attr.name, new_attr.value);
220 }
221 continue 'outer;
222 }
223 }
225 change_list.commit_traversal();
226 change_list.set_attribute(new_attr.name, new_attr.value);
227 }
228 }
230 'outer2: for old_attr in old {
231 for new_attr in new {
232 if old_attr.name == new_attr.name {
233 continue 'outer2;
234 }
235 }
237 change_list.commit_traversal();
238 change_list.remove_attribute(old_attr.name);
239 }
242// Diff the given set of old and new children.
243//
244// The parent must be on top of the change list stack when this function is
245// entered:
246//
247// [... parent]
248//
249// the change list stack is in the same state when this function returns.
250fn diff_children(
251 cached_set: &CachedSet,
252 change_list: &mut ChangeListBuilder,
253 registry: &mut EventsRegistry,
254 old: &[Node],
255 new: &[Node],
256 cached_roots: &mut FxHashSet<CacheId>,
257) {
258 if new.is_empty() {
259 if !old.is_empty() {
260 change_list.commit_traversal();
261 remove_all_children(change_list, registry, old);
262 }
263 return;
264 }
266 if new.len() == 1 {
267 match (old.first(), &new[0]) {
268 (
269 Some(&Node {
270 kind: NodeKind::Text(TextNode { text: old_text }),
271 }),
272 &Node {
273 kind: NodeKind::Text(TextNode { text: new_text }),
274 },
275 ) if old_text == new_text => {
276 // Don't take this fast path...
277 }
278 (
279 _,
280 &Node {
281 kind: NodeKind::Text(TextNode { text }),
282 },
283 ) => {
284 change_list.commit_traversal();
285 change_list.set_text(text);
286 for o in old {
287 registry.remove_subtree(o);
288 }
289 return;
290 }
291 (_, _) => {}
292 }
293 }
295 if old.is_empty() {
296 if !new.is_empty() {
297 change_list.commit_traversal();
298 create_and_append_children(cached_set, change_list, registry, new, cached_roots);
299 }
300 return;
301 }
303 let new_is_keyed = new[0].key().is_some();
304 let old_is_keyed = old[0].key().is_some();
306 debug_assert!(
307 new.iter().all(|n| n.key().is_some() == new_is_keyed),
308 "all siblings must be keyed or all siblings must be non-keyed"
309 );
310 debug_assert!(
311 old.iter().all(|o| o.key().is_some() == old_is_keyed),
312 "all siblings must be keyed or all siblings must be non-keyed"
313 );
315 if new_is_keyed && old_is_keyed {
316 let t = change_list.next_temporary();
317 diff_keyed_children(cached_set, change_list, registry, old, new, cached_roots);
318 change_list.set_next_temporary(t);
319 } else {
320 diff_non_keyed_children(cached_set, change_list, registry, old, new, cached_roots);
321 }
324// Diffing "keyed" children.
325//
326// With keyed children, we care about whether we delete, move, or create nodes
327// versus mutate existing nodes in place. Presumably there is some sort of CSS
328// transition animation that makes the virtual DOM diffing algorithm
329// observable. By specifying keys for nodes, we know which virtual DOM nodes
330// must reuse (or not reuse) the same physical DOM nodes.
331//
332// This is loosely based on Inferno's keyed patching implementation. However, we
333// have to modify the algorithm since we are compiling the diff down into change
334// list instructions that will be executed later, rather than applying the
335// changes to the DOM directly as we compare virtual DOMs.
336//
337// https://github.com/infernojs/inferno/blob/36fd96/packages/inferno/src/DOM/patching.ts#L530-L739
338//
339// When entering this function, the parent must be on top of the change list
340// stack:
341//
342// [... parent]
343//
344// Upon exiting, the change list stack is in the same state.
345fn diff_keyed_children(
346 cached_set: &CachedSet,
347 change_list: &mut ChangeListBuilder,
348 registry: &mut EventsRegistry,
349 old: &[Node],
350 new: &[Node],
351 cached_roots: &mut FxHashSet<CacheId>,
352) {
353 if cfg!(debug_assertions) {
354 let mut keys = FxHashSet::default();
355 let mut assert_unique_keys = |children: &[Node]| {
356 keys.clear();
357 for child in children {
358 let key = child.key();
359 debug_assert!(
360 key.is_some(),
361 "if any sibling is keyed, all siblings must be keyed"
362 );
363 keys.insert(key);
364 }
365 debug_assert_eq!(
366 children.len(),
367 keys.len(),
368 "keyed siblings must each have a unique key"
369 );
370 };
371 assert_unique_keys(old);
372 assert_unique_keys(new);
373 }
375 // First up, we diff all the nodes with the same key at the beginning of the
376 // children.
377 //
378 // `shared_prefix_count` is the count of how many nodes at the start of
379 // `new` and `old` share the same keys.
380 let shared_prefix_count =
381 match diff_keyed_prefix(cached_set, change_list, registry, old, new, cached_roots) {
382 KeyedPrefixResult::Finished => return,
383 KeyedPrefixResult::MoreWorkToDo(count) => count,
384 };
386 // Next, we find out how many of the nodes at the end of the children have
387 // the same key. We do _not_ diff them yet, since we want to emit the change
388 // list instructions such that they can be applied in a single pass over the
389 // DOM. Instead, we just save this information for later.
390 //
391 // `shared_suffix_count` is the count of how many nodes at the end of `new`
392 // and `old` share the same keys.
393 let shared_suffix_count = old[shared_prefix_count..]
394 .iter()
395 .rev()
396 .zip(new[shared_prefix_count..].iter().rev())
397 .take_while(|&(old, new)| old.key() == new.key())
398 .count();
400 let old_shared_suffix_start = old.len() - shared_suffix_count;
401 let new_shared_suffix_start = new.len() - shared_suffix_count;
403 // Ok, we now hopefully have a smaller range of children in the middle
404 // within which to re-order nodes with the same keys, remove old nodes with
405 // now-unused keys, and create new nodes with fresh keys.
406 diff_keyed_middle(
407 cached_set,
408 change_list,
409 registry,
410 &old[shared_prefix_count..old_shared_suffix_start],
411 &new[shared_prefix_count..new_shared_suffix_start],
412 cached_roots,
413 shared_prefix_count,
414 shared_suffix_count,
415 old_shared_suffix_start,
416 );
418 // Finally, diff the nodes at the end of `old` and `new` that share keys.
419 let old_suffix = &old[old_shared_suffix_start..];
420 let new_suffix = &new[new_shared_suffix_start..];
421 debug_assert_eq!(old_suffix.len(), new_suffix.len());
422 if !old_suffix.is_empty() {
423 diff_keyed_suffix(
424 cached_set,
425 change_list,
426 registry,
427 old_suffix,
428 new_suffix,
429 cached_roots,
430 new_shared_suffix_start,
431 );
432 }
435enum KeyedPrefixResult {
436 // Fast path: we finished diffing all the children just by looking at the
437 // prefix of shared keys!
438 Finished,
439 // There is more diffing work to do. Here is a count of how many children at
440 // the beginning of `new` and `old` we already processed.
441 MoreWorkToDo(usize),
444// Diff the prefix of children in `new` and `old` that share the same keys in
445// the same order.
446//
447// Upon entry of this function, the change list stack must be:
448//
449// [... parent]
450//
451// Upon exit, the change list stack is the same.
452fn diff_keyed_prefix(
453 cached_set: &CachedSet,
454 change_list: &mut ChangeListBuilder,
455 registry: &mut EventsRegistry,
456 old: &[Node],
457 new: &[Node],
458 cached_roots: &mut FxHashSet<CacheId>,
459) -> KeyedPrefixResult {
460 change_list.go_down();
461 let mut shared_prefix_count = 0;
463 for (i, (old, new)) in old.iter().zip(new.iter()).enumerate() {
464 if old.key() != new.key() {
465 break;
466 }
468 change_list.go_to_sibling(i);
469 diff(cached_set, change_list, registry, old, new, cached_roots);
470 shared_prefix_count += 1;
471 }
473 // If that was all of the old children, then create and append the remaining
474 // new children and we're finished.
475 if shared_prefix_count == old.len() {
476 change_list.go_up();
477 change_list.commit_traversal();
478 create_and_append_children(
479 cached_set,
480 change_list,
481 registry,
482 &new[shared_prefix_count..],
483 cached_roots,
484 );
485 return KeyedPrefixResult::Finished;
486 }
488 // And if that was all of the new children, then remove all of the remaining
489 // old children and we're finished.
490 if shared_prefix_count == new.len() {
491 change_list.go_to_sibling(shared_prefix_count);
492 change_list.commit_traversal();
493 remove_self_and_next_siblings(change_list, registry, &old[shared_prefix_count..]);
494 return KeyedPrefixResult::Finished;
495 }
497 change_list.go_up();
498 KeyedPrefixResult::MoreWorkToDo(shared_prefix_count)
501// The most-general, expensive code path for keyed children diffing.
502//
503// We find the longest subsequence within `old` of children that are relatively
504// ordered the same way in `new` (via finding a longest-increasing-subsequence
505// of the old child's index within `new`). The children that are elements of
506// this subsequence will remain in place, minimizing the number of DOM moves we
507// will have to do.
508//
509// Upon entry to this function, the change list stack must be:
510//
511// [... parent]
512//
513// Upon exit from this function, it will be restored to that same state.
514fn diff_keyed_middle(
515 cached_set: &CachedSet,
516 change_list: &mut ChangeListBuilder,
517 registry: &mut EventsRegistry,
518 old: &[Node],
519 mut new: &[Node],
520 cached_roots: &mut FxHashSet<CacheId>,
521 shared_prefix_count: usize,
522 shared_suffix_count: usize,
523 old_shared_suffix_start: usize,
524) {
525 // Should have already diffed the shared-key prefixes and suffixes.
526 debug_assert_ne!(new.first().map(|n| n.key()), old.first().map(|o| o.key()));
527 debug_assert_ne!(new.last().map(|n| n.key()), old.last().map(|o| o.key()));
529 // The algorithm below relies upon using `u32::MAX` as a sentinel
530 // value, so if we have that many new nodes, it won't work. This
531 // check is a bit academic (hence only enabled in debug), since
532 // wasm32 doesn't have enough address space to hold that many nodes
533 // in memory.
534 debug_assert!(new.len() < u32::MAX as usize);
536 // Map from each `old` node's key to its index within `old`.
537 let mut old_key_to_old_index = FxHashMap::default();
538 old_key_to_old_index.reserve(old.len());
539 old_key_to_old_index.extend(old.iter().enumerate().map(|(i, o)| (o.key(), i)));
541 // The set of shared keys between `new` and `old`.
542 let mut shared_keys = FxHashSet::default();
543 // Map from each index in `new` to the index of the node in `old` that
544 // has the same key.
545 let mut new_index_to_old_index = Vec::with_capacity(new.len());
546 new_index_to_old_index.extend(new.iter().map(|n| {
547 let key = n.key();
548 if let Some(&i) = old_key_to_old_index.get(&key) {
549 shared_keys.insert(key);
550 i
551 } else {
552 u32::MAX as usize
553 }
554 }));
556 // If none of the old keys are reused by the new children, then we
557 // remove all the remaining old children and create the new children
558 // afresh.
559 if shared_suffix_count == 0 && shared_keys.is_empty() {
560 if shared_prefix_count == 0 {
561 change_list.commit_traversal();
562 remove_all_children(change_list, registry, old);
563 } else {
564 change_list.go_down_to_child(shared_prefix_count);
565 change_list.commit_traversal();
566 remove_self_and_next_siblings(change_list, registry, &old[shared_prefix_count..]);
567 }
568 create_and_append_children(cached_set, change_list, registry, new, cached_roots);
569 return;
570 }
572 // Save each of the old children whose keys are reused in the new
573 // children.
574 let mut old_index_to_temp = vec![u32::MAX; old.len()];
575 let mut start = 0;
576 loop {
577 let end = (start..old.len())
578 .find(|&i| {
579 let key = old[i].key();
580 !shared_keys.contains(&key)
581 })
582 .unwrap_or(old.len());
584 if end - start > 0 {
585 change_list.commit_traversal();
586 let mut t = change_list.save_children_to_temporaries(
587 shared_prefix_count + start,
588 shared_prefix_count + end,
589 );
590 for i in start..end {
591 old_index_to_temp[i] = t;
592 t += 1;
593 }
594 }
596 debug_assert!(end <= old.len());
597 if end == old.len() {
598 break;
599 } else {
600 start = end + 1;
601 }
602 }
604 // Remove any old children whose keys were not reused in the new
605 // children. Remove from the end first so that we don't mess up indices.
606 let mut removed_count = 0;
607 for (i, old_child) in old.iter().enumerate().rev() {
608 if !shared_keys.contains(&old_child.key()) {
609 registry.remove_subtree(old_child);
610 change_list.commit_traversal();
611 change_list.remove_child(i + shared_prefix_count);
612 removed_count += 1;
613 }
614 }
616 // If there aren't any more new children, then we are done!
617 if new.is_empty() {
618 return;
619 }
621 // The longest increasing subsequence within `new_index_to_old_index`. This
622 // is the longest sequence on DOM nodes in `old` that are relatively ordered
623 // correctly within `new`. We will leave these nodes in place in the DOM,
624 // and only move nodes that are not part of the LIS. This results in the
625 // maximum number of DOM nodes left in place, AKA the minimum number of DOM
626 // nodes moved.
627 let mut new_index_is_in_lis = FxHashSet::default();
628 new_index_is_in_lis.reserve(new_index_to_old_index.len());
629 let mut predecessors = vec![0; new_index_to_old_index.len()];
630 let mut starts = vec![0; new_index_to_old_index.len()];
631 longest_increasing_subsequence::lis_with(
632 &new_index_to_old_index,
633 &mut new_index_is_in_lis,
634 |a, b| a < b,
635 &mut predecessors,
636 &mut starts,
637 );
639 // Now we will iterate from the end of the new children back to the
640 // beginning, diffing old children we are reusing and if they aren't in the
641 // LIS moving them to their new destination, or creating new children. Note
642 // that iterating in reverse order lets us use `Node.prototype.insertBefore`
643 // to move/insert children.
644 //
645 // But first, we ensure that we have a child on the change list stack that
646 // we can `insertBefore`. We handle this once before looping over `new`
647 // children, so that we don't have to keep checking on every loop iteration.
648 if shared_suffix_count > 0 {
649 // There is a shared suffix after these middle children. We will be
650 // inserting before that shared suffix, so add the first child of that
651 // shared suffix to the change list stack.
652 //
653 // [... parent]
654 change_list.go_down_to_child(old_shared_suffix_start - removed_count);
655 // [... parent first_child_of_shared_suffix]
656 } else {
657 // There is no shared suffix coming after these middle children.
658 // Therefore we have to process the last child in `new` and move it to
659 // the end of the parent's children if it isn't already there.
660 let last_index = new.len() - 1;
661 let last = new.last().unwrap_throw();
662 new = &new[..new.len() - 1];
663 if shared_keys.contains(&last.key()) {
664 let old_index = new_index_to_old_index[last_index];
665 let temp = old_index_to_temp[old_index];
666 // [... parent]
667 change_list.go_down_to_temp_child(temp);
668 // [... parent last]
669 diff(
670 cached_set,
671 change_list,
672 registry,
673 &old[old_index],
674 last,
675 cached_roots,
676 );
677 if new_index_is_in_lis.contains(&last_index) {
678 // Don't move it, since it is already where it needs to be.
679 } else {
680 change_list.commit_traversal();
681 // [... parent last]
682 change_list.append_child();
683 // [... parent]
684 change_list.go_down_to_temp_child(temp);
685 // [... parent last]
686 }
687 } else {
688 change_list.commit_traversal();
689 // [... parent]
690 create(cached_set, change_list, registry, last, cached_roots);
691 // [... parent last]
692 change_list.append_child();
693 // [... parent]
694 change_list.go_down_to_reverse_child(0);
695 // [... parent last]
696 }
697 }
699 for (new_index, new_child) in new.iter().enumerate().rev() {
700 let old_index = new_index_to_old_index[new_index];
701 if old_index == u32::MAX as usize {
702 debug_assert!(!shared_keys.contains(&new_child.key()));
703 change_list.commit_traversal();
704 // [... parent successor]
705 create(cached_set, change_list, registry, new_child, cached_roots);
706 // [... parent successor new_child]
707 change_list.insert_before();
708 // [... parent new_child]
709 } else {
710 debug_assert!(shared_keys.contains(&new_child.key()));
711 let temp = old_index_to_temp[old_index];
712 debug_assert_ne!(temp, u32::MAX);
714 if new_index_is_in_lis.contains(&new_index) {
715 // [... parent successor]
716 change_list.go_to_temp_sibling(temp);
717 // [... parent new_child]
718 } else {
719 change_list.commit_traversal();
720 // [... parent successor]
721 change_list.push_temporary(temp);
722 // [... parent successor new_child]
723 change_list.insert_before();
724 // [... parent new_child]
725 }
727 diff(
728 cached_set,
729 change_list,
730 registry,
731 &old[old_index],
732 new_child,
733 cached_roots,
734 );
735 }
736 }
738 // [... parent child]
739 change_list.go_up();
740 // [... parent]
743// Diff the suffix of keyed children that share the same keys in the same order.
744//
745// The parent must be on the change list stack when we enter this function:
746//
747// [... parent]
748//
749// When this function exits, the change list stack remains the same.
750fn diff_keyed_suffix(
751 cached_set: &CachedSet,
752 change_list: &mut ChangeListBuilder,
753 registry: &mut EventsRegistry,
754 old: &[Node],
755 new: &[Node],
756 cached_roots: &mut FxHashSet<CacheId>,
757 new_shared_suffix_start: usize,
758) {
759 debug_assert_eq!(old.len(), new.len());
760 debug_assert!(!old.is_empty());
762 // [... parent]
763 change_list.go_down();
764 // [... parent new_child]
766 for (i, (old_child, new_child)) in old.iter().zip(new.iter()).enumerate() {
767 change_list.go_to_sibling(new_shared_suffix_start + i);
768 diff(
769 cached_set,
770 change_list,
771 registry,
772 old_child,
773 new_child,
774 cached_roots,
775 );
776 }
778 // [... parent]
779 change_list.go_up();
782// Diff children that are not keyed.
783//
784// The parent must be on the top of the change list stack when entering this
785// function:
786//
787// [... parent]
788//
789// the change list stack is in the same state when this function returns.
790fn diff_non_keyed_children(
791 cached_set: &CachedSet,
792 change_list: &mut ChangeListBuilder,
793 registry: &mut EventsRegistry,
794 old: &[Node],
795 new: &[Node],
796 cached_roots: &mut FxHashSet<CacheId>,
797) {
798 // Handled these cases in `diff_children` before calling this function.
799 debug_assert!(!new.is_empty());
800 debug_assert!(!old.is_empty());
802 // [... parent]
803 change_list.go_down();
804 // [... parent child]
806 for (i, (new_child, old_child)) in new.iter().zip(old.iter()).enumerate() {
807 // [... parent prev_child]
808 change_list.go_to_sibling(i);
809 // [... parent this_child]
810 diff(
811 cached_set,
812 change_list,
813 registry,
814 old_child,
815 new_child,
816 cached_roots,
817 );
818 }
820 match old.len().cmp(&new.len()) {
821 Ordering::Greater => {
822 // [... parent prev_child]
823 change_list.go_to_sibling(new.len());
824 // [... parent first_child_to_remove]
825 change_list.commit_traversal();
826 remove_self_and_next_siblings(change_list, registry, &old[new.len()..]);
827 // [... parent]
828 }
829 Ordering::Less => {
830 // [... parent last_child]
831 change_list.go_up();
832 // [... parent]
833 change_list.commit_traversal();
834 create_and_append_children(
835 cached_set,
836 change_list,
837 registry,
838 &new[old.len()..],
839 cached_roots,
840 );
841 }
842 Ordering::Equal => {
843 // [... parent child]
844 change_list.go_up();
845 // [... parent]
846 }
847 }
850// Create the given children and append them to the parent node.
851//
852// The parent node must currently be on top of the change list stack:
853//
854// [... parent]
855//
856// When this function returns, the change list stack is in the same state.
857fn create_and_append_children(
858 cached_set: &CachedSet,
859 change_list: &mut ChangeListBuilder,
860 registry: &mut EventsRegistry,
861 new: &[Node],
862 cached_roots: &mut FxHashSet<CacheId>,
863) {
864 debug_assert!(change_list.traversal_is_committed());
865 for child in new {
866 create(cached_set, change_list, registry, child, cached_roots);
867 change_list.append_child();
868 }
871// Remove all of a node's children.
872//
873// The change list stack must have this shape upon entry to this function:
874//
875// [... parent]
876//
877// When this function returns, the change list stack is in the same state.
878fn remove_all_children(
879 change_list: &mut ChangeListBuilder,
880 registry: &mut EventsRegistry,
881 old: &[Node],
882) {
883 debug_assert!(change_list.traversal_is_committed());
884 for child in old {
885 registry.remove_subtree(child);
886 }
887 // Fast way to remove all children: set the node's textContent to an empty
888 // string.
889 change_list.set_text("");
892// Remove the current child and all of its following siblings.
893//
894// The change list stack must have this shape upon entry to this function:
895//
896// [... parent child]
897//
898// After the function returns, the child is no longer on the change list stack:
899//
900// [... parent]
901fn remove_self_and_next_siblings(
902 change_list: &mut ChangeListBuilder,
903 registry: &mut EventsRegistry,
904 old: &[Node],
905) {
906 debug_assert!(change_list.traversal_is_committed());
907 for child in old {
908 registry.remove_subtree(child);
909 }
910 change_list.remove_self_and_next_siblings();
913// Emit instructions to create the given virtual node.
914//
915// The change list stack may have any shape upon entering this function:
916//
917// [...]
918//
919// When this function returns, the new node is on top of the change list stack:
920//
921// [... node]
922fn create(
923 cached_set: &CachedSet,
924 change_list: &mut ChangeListBuilder,
925 registry: &mut EventsRegistry,
926 node: &Node,
927 cached_roots: &mut FxHashSet<CacheId>,
928) {
929 debug_assert!(change_list.traversal_is_committed());
930 match node.kind {
931 NodeKind::Text(TextNode { text }) => {
932 change_list.create_text_node(text);
933 }
934 NodeKind::Element(&ElementNode {
935 key: _,
936 tag_name,
937 listeners,
938 attributes,
939 children,
940 namespace,
941 }) => {
942 if let Some(namespace) = namespace {
943 change_list.create_element_ns(tag_name, namespace);
944 } else {
945 change_list.create_element(tag_name);
946 }
948 for l in listeners {
949 unsafe {
950 registry.add(l);
951 }
952 change_list.new_event_listener(l);
953 }
955 for attr in attributes {
956 change_list.set_attribute(&attr.name, &attr.value);
957 }
959 // Fast path: if there is a single text child, it is faster to
960 // create-and-append the text node all at once via setting the
961 // parent's `textContent` in a single change list instruction than
962 // to emit three instructions to (1) create a text node, (2) set its
963 // text content, and finally (3) append the text node to this
964 // parent.
965 if children.len() == 1 {
966 if let Node {
967 kind: NodeKind::Text(TextNode { text }),
968 } = children[0]
969 {
970 change_list.set_text(text);
971 return;
972 }
973 }
975 for child in children {
976 create(cached_set, change_list, registry, child, cached_roots);
977 change_list.append_child();
978 }
979 }
980 NodeKind::Cached(ref c) => {
981 cached_roots.insert(c.id);
982 let (node, template) = cached_set.get(c.id);
983 if let Some(template) = template {
984 create_with_template(
985 cached_set,
986 change_list,
987 registry,
988 template,
989 node,
990 cached_roots,
991 );
992 } else {
993 create(cached_set, change_list, registry, node, cached_roots);
994 }
995 }
996 }
999// Get or create the template.
1001// Upon entering this function the change list stack may be in any shape:
1003// [...]
1005// When this function returns, it leaves a freshly cloned copy of the template
1006// on the top of the change list stack:
1008// [... template]
1009#[inline]
1010fn get_or_create_template<'a>(
1011 cached_set: &'a CachedSet,
1012 change_list: &mut ChangeListBuilder,
1013 registry: &mut EventsRegistry,
1014 cached_roots: &mut FxHashSet<CacheId>,
1015 template_id: CacheId,
1016) -> (&'a Node<'a>, bool) {
1017 let (template, template_template) = cached_set.get(template_id);
1018 debug_assert!(
1019 template_template.is_none(),
1020 "templates should not be templated themselves"
1021 );
1023 // If we haven't already created and saved the physical DOM subtree for this
1024 // template, do that now.
1025 if change_list.has_template(template_id) {
1026 // Clone the template and push it onto the stack.
1027 //
1028 // [...]
1029 change_list.push_template(template_id);
1030 // [... template]
1032 (template, true)
1033 } else {
1034 // [...]
1035 create(cached_set, change_list, registry, template, cached_roots);
1036 // [... template]
1037 change_list.save_template(template_id);
1038 // [... template]
1040 (template, false)
1044fn create_and_replace(
1045 cached_set: &CachedSet,
1046 change_list: &mut ChangeListBuilder,
1047 registry: &mut EventsRegistry,
1048 new_template: Option<CacheId>,
1049 old: &Node,
1050 new: &Node,
1051 cached_roots: &mut FxHashSet<CacheId>,
1052) {
1053 debug_assert!(change_list.traversal_is_committed());
1055 if let Some(template_id) = new_template {
1056 let (template, needs_listeners) =
1057 get_or_create_template(cached_set, change_list, registry, cached_roots, template_id);
1058 change_list.replace_with();
1060 let mut old_forcing = None;
1061 if needs_listeners {
1062 old_forcing = Some(change_list.push_force_new_listeners());
1065 diff(
1066 cached_set,
1067 change_list,
1068 registry,
1069 template,
1070 new,
1071 cached_roots,
1072 );
1074 if let Some(old) = old_forcing {
1075 change_list.pop_force_new_listeners(old);
1078 change_list.commit_traversal();
1079 } else {
1080 create(cached_set, change_list, registry, new, cached_roots);
1081 change_list.replace_with();
1083 registry.remove_subtree(old);
1086fn create_with_template(
1087 cached_set: &CachedSet,
1088 change_list: &mut ChangeListBuilder,
1089 registry: &mut EventsRegistry,
1090 template_id: CacheId,
1091 node: &Node,
1092 cached_roots: &mut FxHashSet<CacheId>,
1093) {
1094 debug_assert!(change_list.traversal_is_committed());
1096 // [...]
1097 let (template, needs_listeners) =
1098 get_or_create_template(cached_set, change_list, registry, cached_roots, template_id);
1099 // [... template]
1101 // Now diff the node with its template.
1102 //
1103 // We must force adding new listeners instead of updating existing ones,
1104 // since listeners don't get cloned in `cloneNode`.
1105 let mut old_forcing = None;
1106 if needs_listeners {
1107 old_forcing = Some(change_list.push_force_new_listeners());
1110 diff(
1111 cached_set,
1112 change_list,
1113 registry,
1114 template,
1115 node,
1116 cached_roots,
1117 );
1119 if let Some(old) = old_forcing {
1120 change_list.pop_force_new_listeners(old);
1123 // Make sure that we come back up to the level we were at originally.
1124 change_list.commit_traversal();