2 cached_set::{CacheId, CachedSet},
3 change_list::ChangeListBuilder,
4 events::EventsRegistry,
5 node::{Attribute, ElementNode, ElementNodeFlags, Listener, Node, NodeKind, TextNode},
7use fxhash::{FxHashMap, FxHashSet};
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`.
15// Upon entry to this function, the physical DOM node must be on the top of the
20// The stack is in the same state when this function exits.
22 cached_set: &CachedSet,
23 change_list: &mut ChangeListBuilder,
24 registry: &mut EventsRegistry,
27 cached_roots: &mut FxHashSet<CacheId>,
29 match (&new.kind, &old.kind) {
31 &NodeKind::Text(TextNode { text: new_text }),
32 &NodeKind::Text(TextNode { text: old_text }),
34 if new_text != old_text {
35 change_list.set_text(new_text);
39 (&NodeKind::Text(_), &NodeKind::Element(_)) => {
40 create(cached_set, change_list, registry, new, cached_roots);
41 registry.remove_subtree(&old);
42 change_list.replace_with();
45 (&NodeKind::Element(_), &NodeKind::Text(_)) => {
46 create(cached_set, change_list, registry, new, cached_roots);
47 // Note: text nodes cannot have event listeners, so we don't need to
48 // remove the old node's listeners from our registry her.
49 change_list.replace_with();
53 &NodeKind::Element(ElementNode {
55 tag_name: new_tag_name,
56 listeners: new_listeners,
57 attributes: new_attributes,
58 children: new_children,
59 namespace: new_namespace,
61 &NodeKind::Element(ElementNode {
63 tag_name: old_tag_name,
64 listeners: old_listeners,
65 attributes: old_attributes,
66 children: old_children,
67 namespace: old_namespace,
70 if new_tag_name != old_tag_name || new_namespace != old_namespace {
71 create(cached_set, change_list, registry, new, cached_roots);
72 registry.remove_subtree(&old);
73 change_list.replace_with();
76 diff_listeners(change_list, registry, old_listeners, new_listeners);
77 diff_attributes(change_list, old_attributes, new_attributes);
90 // Both the new and old nodes are cached.
91 (&NodeKind::Cached(ref new), &NodeKind::Cached(ref old)) => {
92 cached_roots.insert(new.id);
95 // This is the same cached node, so nothing has changed!
99 let new = cached_set.get(new.id);
100 let old = cached_set.get(old.id);
101 diff(cached_set, change_list, registry, old, new, cached_roots);
104 // New cached node when the old node was not cached. In this scenario,
105 // we assume that they are pretty different, and it isn't worth diffing
106 // the subtrees, so we just create the new cached node afresh.
107 (&NodeKind::Cached(ref c), _) => {
108 cached_roots.insert(c.id);
109 let new = cached_set.get(c.id);
110 create(cached_set, change_list, registry, new, cached_roots);
111 registry.remove_subtree(&old);
112 change_list.replace_with();
115 // Old cached node and new non-cached node. Again, assume that they are
116 // probably pretty different and create the new non-cached node afresh.
117 (_, &NodeKind::Cached(_)) => {
118 create(cached_set, change_list, registry, new, cached_roots);
119 registry.remove_subtree(&old);
120 change_list.replace_with();
125// Diff event listeners between `old` and `new`.
127// The listeners' node must be on top of the stack:
131// The stack is left unchanged.
133 change_list: &mut ChangeListBuilder,
134 registry: &mut EventsRegistry,
138 'outer1: for new_l in new {
140 // Safety relies on removing `new_l` from the registry manually at
141 // the end of its lifetime. This happens below in the `'outer2`
142 // loop, and elsewhere in diffing when removing old dom trees.
147 if new_l.event == old_l.event {
148 change_list.update_event_listener(new_l);
153 change_list.new_event_listener(new_l);
156 'outer2: for old_l in old {
157 registry.remove(old_l);
160 if new_l.event == old_l.event {
164 change_list.remove_event_listener(old_l.event);
168// Diff a node's attributes.
170// The attributes' node must be on top of the stack:
174// The stack is left unchanged.
175fn diff_attributes(change_list: &mut ChangeListBuilder, old: &[Attribute], new: &[Attribute]) {
176 // Do O(n^2) passes to add/update and remove attributes, since
177 // there are almost always very few attributes.
178 'outer: for new_attr in new {
179 if new_attr.is_volatile() {
180 change_list.set_attribute(new_attr.name, new_attr.value);
182 for old_attr in old {
183 if old_attr.name == new_attr.name {
184 if old_attr.value != new_attr.value {
185 change_list.set_attribute(new_attr.name, new_attr.value);
190 change_list.set_attribute(new_attr.name, new_attr.value);
194 'outer2: for old_attr in old {
195 for new_attr in new {
196 if old_attr.name == new_attr.name {
200 change_list.remove_attribute(old_attr.name);
204// Diff the given set of old and new children.
206// The parent must be on top of the stack when this function is entered:
210// The stack is in the same state when this function returns.
212 cached_set: &CachedSet,
213 change_list: &mut ChangeListBuilder,
214 registry: &mut EventsRegistry,
215 new_flags: ElementNodeFlags,
216 old_flags: ElementNodeFlags,
219 cached_roots: &mut FxHashSet<CacheId>,
223 remove_all_children(change_list, registry, old);
229 create_and_append_children(cached_set, change_list, registry, new, cached_roots);
233 if new_flags.has_keyed_children() && old_flags.has_keyed_children() {
234 let t = change_list.next_temporary();
235 diff_keyed_children(cached_set, change_list, registry, old, new, cached_roots);
236 change_list.set_next_temporary(t);
238 diff_non_keyed_children(cached_set, change_list, registry, old, new, cached_roots);
242// Diffing "keyed" children.
244// With keyed children, we care about whether we delete, move, or create nodes
245// versus mutate existing nodes in place. Presumably there is some sort of CSS
246// transition animation that makes the virtual DOM diffing algorithm
247// observable. By specifying keys for nodes, we know which virtual DOM nodes
248// must reuse (or not reuse) the same physical DOM nodes.
250// This is loosely based on Inferno's keyed patching implementation. However, we
251// have to modify the algorithm since we are compiling the diff down into change
252// list instructions that will be executed later, rather than applying the
253// changes to the DOM directly as we compare virtual DOMs.
255// https://github.com/infernojs/inferno/blob/36fd96/packages/inferno/src/DOM/patching.ts#L530-L739
257// When entering this function, the parent must be on top of the stack:
261// Upon exiting, the stack is in the same state.
262fn diff_keyed_children(
263 cached_set: &CachedSet,
264 change_list: &mut ChangeListBuilder,
265 registry: &mut EventsRegistry,
268 cached_roots: &mut FxHashSet<CacheId>,
270 // First up, we diff all the nodes with the same key at the beginning of the
273 // `shared_prefix_count` is the count of how many nodes at the start of
274 // `new` and `old` share the same keys.
275 let shared_prefix_count =
276 match diff_keyed_prefix(cached_set, change_list, registry, old, new, cached_roots) {
277 KeyedPrefixResult::Finished => return,
278 KeyedPrefixResult::MoreWorkToDo(count) => count,
281 // Next, we find out how many of the nodes at the end of the children have
282 // the same key. We do _not_ diff them yet, since we want to emit the change
283 // list instructions such that they can be applied in a single pass over the
284 // DOM. Instead, we just save this information for later.
286 // `shared_suffix_count` is the count of how many nodes at the end of `new`
287 // and `old` share the same keys.
288 let shared_suffix_count = old[shared_prefix_count..]
291 .zip(new[shared_prefix_count..].iter().rev())
292 .take_while(|&(old, new)| old.key() == new.key())
295 let old_shared_suffix_start = old.len() - shared_suffix_count;
296 let new_shared_suffix_start = new.len() - shared_suffix_count;
298 // Ok, we now hopefully have a smaller range of children in the middle
299 // within which to re-order nodes with the same keys, remove old nodes with
300 // now-unused keys, and create new nodes with fresh keys.
305 &old[shared_prefix_count..old_shared_suffix_start],
306 &new[shared_prefix_count..new_shared_suffix_start],
310 old_shared_suffix_start,
313 // Finally, diff the nodes at the end of `old` and `new` that share keys.
314 let old_suffix = &old[old_shared_suffix_start..];
315 let new_suffix = &new[new_shared_suffix_start..];
316 debug_assert_eq!(old_suffix.len(), new_suffix.len());
317 if !old_suffix.is_empty() {
325 new_shared_suffix_start,
330enum KeyedPrefixResult {
331 // Fast path: we finished diffing all the children just by looking at the
332 // prefix of shared keys!
334 // There is more diffing work to do. Here is a count of how many children at
335 // the beginning of `new` and `old` we already processed.
339// Diff the prefix of children in `new` and `old` that share the same keys in
342// Upon entry of this function, the stack must be:
346// Upon exit, the stack is the same.
348 cached_set: &CachedSet,
349 change_list: &mut ChangeListBuilder,
350 registry: &mut EventsRegistry,
353 cached_roots: &mut FxHashSet<CacheId>,
354) -> KeyedPrefixResult {
355 let mut pushed = false;
356 let mut shared_prefix_count = 0;
358 for (old, new) in old.iter().zip(new.iter()) {
359 if old.key() != new.key() {
364 debug_assert!(shared_prefix_count > 0);
365 change_list.pop_push_next_sibling();
367 debug_assert_eq!(shared_prefix_count, 0);
368 change_list.push_first_child();
372 diff(cached_set, change_list, registry, old, new, cached_roots);
373 shared_prefix_count += 1;
375 // At the end of the loop, the stack looks like
377 // [... parent child_we_just_diffed]
378 debug_assert!(pushed);
381 // If that was all of the old children, then create and append the remaining
382 // new children and we're finished.
383 if shared_prefix_count == old.len() {
386 "we handle the case of empty children before calling this method, so
387 `shared_prefix_count` must be greater than zero, and therefore we
388 must have pushed in the above loop"
391 create_and_append_children(
395 &new[shared_prefix_count..],
398 return KeyedPrefixResult::Finished;
401 // And if that was all of the new children, then remove all of the remaining
402 // old children and we're finished.
403 if shared_prefix_count == new.len() {
405 debug_assert!(pushed);
406 change_list.pop_push_next_sibling();
407 change_list.remove_self_and_next_siblings();
408 return KeyedPrefixResult::Finished;
412 debug_assert!(shared_prefix_count > 0);
415 KeyedPrefixResult::MoreWorkToDo(shared_prefix_count)
418// The most-general, expensive code path for keyed children diffing.
420// We find the longest subsequence within `old` of children that are relatively
421// ordered the same way in `new` (via finding a longest-increasing-subsequence
422// of the old child's index within `new`). The children that are elements of
423// this subsequence will remain in place, minimizing the number of DOM moves we
426// Upon entry to this function, the stack must be:
430// Upon exit from this function, it will be restored to that same state.
432 cached_set: &CachedSet,
433 change_list: &mut ChangeListBuilder,
434 registry: &mut EventsRegistry,
437 cached_roots: &mut FxHashSet<CacheId>,
438 shared_prefix_count: usize,
439 shared_suffix_count: usize,
440 old_shared_suffix_start: usize,
442 // Should have already diffed the shared-key prefixes and suffixes.
443 debug_assert_ne!(new.first().map(|n| n.key()), old.first().map(|o| o.key()));
444 debug_assert_ne!(new.last().map(|n| n.key()), old.last().map(|o| o.key()));
446 // The algorithm below relies upon using `u32::MAX` as a sentinel
447 // value, so if we have that many new nodes, it won't work. This
448 // check is a bit academic (hence only enabled in debug), since
449 // wasm32 doesn't have enough address space to hold that many nodes
451 debug_assert!(new.len() < u32::MAX as usize);
453 // Map from each `old` node's key to its index within `old`.
454 let mut old_key_to_old_index = FxHashMap::default();
455 old_key_to_old_index.reserve(old.len());
456 old_key_to_old_index.extend(old.iter().enumerate().map(|(i, o)| (o.key(), i)));
458 // The set of shared keys between `new` and `old`.
459 let mut shared_keys = FxHashSet::default();
460 // Map from each index in `new` to the index of the node in `old` that
462 let mut new_index_to_old_index = Vec::with_capacity(new.len());
463 new_index_to_old_index.extend(new.iter().map(|n| {
465 if let Some(&i) = old_key_to_old_index.get(&key) {
466 shared_keys.insert(key);
473 // If none of the old keys are reused by the new children, then we
474 // remove all the remaining old children and create the new children
476 if shared_suffix_count == 0 && shared_keys.is_empty() {
477 if shared_prefix_count == 0 {
478 remove_all_children(change_list, registry, old);
480 change_list.pop_push_next_sibling();
481 remove_self_and_next_siblings(change_list, registry, &old[shared_prefix_count..]);
483 create_and_append_children(cached_set, change_list, registry, new, cached_roots);
487 // The longest increasing subsequence within `new_index_to_old_index` in
488 // reverse order (since `lis_with` adds the indices in reverse
489 // order). We will leave these nodes in place in the DOM, and only move
490 // nodes that are not part of the LIS. This results in the minimum
491 // number of DOM nodes moved.
492 let mut reverse_lis = Vec::with_capacity(new_index_to_old_index.len());
493 let mut predecessors = vec![0; new_index_to_old_index.len()];
494 let mut starts = vec![0; new_index_to_old_index.len()];
495 longest_increasing_subsequence::lis_with(
496 &new_index_to_old_index,
503 // Save each of the old children whose keys are reused in the new
505 let mut old_index_to_temp = vec![u32::MAX; old.len()];
508 let end = (start..old.len())
510 let key = old[i].key();
511 !shared_keys.contains(&key)
513 .unwrap_or(old.len());
516 let mut t = change_list.save_children_to_temporaries(
517 shared_prefix_count + start,
518 shared_prefix_count + end,
520 for i in start..end {
521 old_index_to_temp[i] = t;
526 debug_assert!(end <= old.len());
527 if end == old.len() {
534 // Remove any old children whose keys were not reused in the new
535 // children. Remove from the end first so that we don't mess up indices.
536 let mut removed_count = 0;
537 for (i, old_child) in old.iter().enumerate().rev() {
538 if !shared_keys.contains(&old_child.key()) {
539 change_list.remove_child(i + shared_prefix_count);
544 // Whether we have pushed a child onto the stack or not.
545 let mut pushed = false;
547 // Now iterate from the end of the new children back to the beginning,
548 // moving old children to their new destination, diffing them, and
549 // creating new children as necessary. Note that iterating in reverse
550 // order lets us use `Node.prototype.insertBefore` to move/insert
552 if shared_suffix_count > 0 {
553 change_list.push_child(old_shared_suffix_start - removed_count);
556 let mut segment_end = new.len();
557 for lis_index in reverse_lis {
558 // Because we use `u32::MAX` as a sentinel value representing "a child
559 // with this key is not a member of `new`", we filter that out here.
560 let old_index = new_index_to_old_index[lis_index];
561 if old_index == u32::MAX as usize {
565 // A segment begins with a member of the LIS, which will remain in
566 // place in the DOM, followed by zero or more new children that are
567 // not members of the LIS. If one of these new children shares a key
568 // with one of the old children, then we will move that old child in
569 // the DOM. Otherwise, we create the new child afresh.
570 debug_assert!(segment_end - lis_index > 0);
572 // Go through each of the non-LIS child and move-and-diff or create
574 diff_and_move_or_create_segment(
581 lis_index + 1..segment_end,
582 &new_index_to_old_index,
587 // Now we push the member of the LIS and diff it with its
588 // correspondingly-keyed new child.
589 let new_child = &new[lis_index];
590 let temp = old_index_to_temp[old_index];
591 debug_assert_ne!(temp, u32::MAX);
595 change_list.push_temporary(temp);
606 segment_end = lis_index;
609 // And now diff-and-move or create each of the non-LIS children that
610 // appear before the first LIS-member.
611 diff_and_move_or_create_segment(
619 &new_index_to_old_index,
629// Diff-and-then-move or create each new node in the given segment. The
630// segment's nodes must _not_ be members of the LIS (those nodes we will diff in
631// place elsewhere, and we should not move them nor create them afresh).
633// On entering this function, the stack has the parent and optionally the next
634// sibling after this segment of children:
636// [... parent next_sibling] if *pushed == true
637// [... parent] otherwise
639// After exiting, if any children were moved or created, then `pushed` is set to
640// true and the stack has the first child in this segment on top. Otherwise the
641// stack is left as it was on entering.
643// [... parent child] if *pushed == true
644// [... parent] otherwise
645fn diff_and_move_or_create_segment(
646 cached_set: &CachedSet,
647 change_list: &mut ChangeListBuilder,
648 registry: &mut EventsRegistry,
651 cached_roots: &mut FxHashSet<CacheId>,
652 segment: Range<usize>,
653 new_index_to_old_index: &[usize],
654 old_index_to_temp: &[u32],
657 for new_index in segment.rev() {
658 let new_child = &new[new_index];
659 let old_index = new_index_to_old_index[new_index];
660 if old_index == u32::MAX as usize {
661 // The key is not reused. Create this new child afresh.
662 create(cached_set, change_list, registry, new_child, cached_roots);
664 // The key is reused. Diff it with the old node and then
665 // move the old node into its final destination.
666 let temp = old_index_to_temp[old_index];
667 debug_assert_ne!(temp, u32::MAX);
668 change_list.push_temporary(temp);
679 // At this point the stack can have one of two shapes.
681 // [... parent next_child new_child]
682 change_list.insert_before();
683 // [... parent new_child]
685 // [... parent new_child]
686 change_list.append_child();
688 change_list.push_last_child();
689 // [... parent new_child]
693 // At the end of each loop iteration, the stack looks like:
695 // [... parent new_child]
696 debug_assert!(*pushed);
700// Diff the suffix of keyed children that share the same keys in the same order.
702// The parent must be on the stack when we enter this function:
706// When this function exits, the stack remains the same.
708 cached_set: &CachedSet,
709 change_list: &mut ChangeListBuilder,
710 registry: &mut EventsRegistry,
713 cached_roots: &mut FxHashSet<CacheId>,
714 new_shared_suffix_start: usize,
716 debug_assert_eq!(old.len(), new.len());
717 debug_assert!(!old.is_empty());
720 change_list.push_child(new_shared_suffix_start);
721 // [... parent new_child]
723 for (old_child, new_child) in old.iter().zip(new.iter()) {
733 // [... parent this_new_child]
734 change_list.pop_push_next_sibling();
735 // [... parent next_new_child]
742// Diff children that are not keyed.
744// The parent must be on the top of the stack when entering this function:
748// The stack is in the same state when this function returns.
749fn diff_non_keyed_children(
750 cached_set: &CachedSet,
751 change_list: &mut ChangeListBuilder,
752 registry: &mut EventsRegistry,
755 cached_roots: &mut FxHashSet<CacheId>,
757 // Handled these cases in `diff_children` before calling this function.
758 debug_assert!(!new.is_empty());
759 debug_assert!(!old.is_empty());
761 for (i, (new_child, old_child)) in new.iter().zip(old.iter()).enumerate() {
763 change_list.push_first_child();
765 change_list.pop_push_next_sibling();
778 match old.len().cmp(&new.len()) {
779 Ordering::Greater => {
780 change_list.pop_push_next_sibling();
781 remove_self_and_next_siblings(change_list, registry, &old[new.len()..]);
785 create_and_append_children(
799// Create the given children and append them to the parent node.
801// The parent node must currently be on top of the stack:
805// When this function returns, the stack is in the same state.
806fn create_and_append_children(
807 cached_set: &CachedSet,
808 change_list: &mut ChangeListBuilder,
809 registry: &mut EventsRegistry,
811 cached_roots: &mut FxHashSet<CacheId>,
814 create(cached_set, change_list, registry, child, cached_roots);
815 change_list.append_child();
819// Remove all of a node's children.
821// The stack must have this shape upon entry to this function:
825// When this function returns, the stack is in the same state.
826fn remove_all_children(
827 change_list: &mut ChangeListBuilder,
828 registry: &mut EventsRegistry,
832 registry.remove_subtree(child);
834 // Fast way to remove all children: set the node's textContent to an empty
836 change_list.set_text("");
839// Remove the current child and all of its following siblings.
841// The stack must have this shape upon entry to this function:
845// After the function returns, the child is no longer on the stack:
848fn remove_self_and_next_siblings(
849 change_list: &mut ChangeListBuilder,
850 registry: &mut EventsRegistry,
854 registry.remove_subtree(child);
856 change_list.remove_self_and_next_siblings();
859// Emit instructions to create the given virtual node.
861// The stack may have any shape upon entering this function:
865// When this function returns, the new node is on top of the stack:
869 cached_set: &CachedSet,
870 change_list: &mut ChangeListBuilder,
871 registry: &mut EventsRegistry,
873 cached_roots: &mut FxHashSet<CacheId>,
876 NodeKind::Text(TextNode { text }) => {
877 change_list.create_text_node(text);
879 NodeKind::Element(ElementNode {
887 if let Some(namespace) = namespace {
888 change_list.create_element_ns(tag_name, namespace);
890 change_list.create_element(tag_name);
896 change_list.new_event_listener(l);
898 for attr in attributes {
899 change_list.set_attribute(&attr.name, &attr.value);
901 for child in children {
902 create(cached_set, change_list, registry, child, cached_roots);
903 change_list.append_child();
906 NodeKind::Cached(ref c) => {
907 cached_roots.insert(c.id);
908 let node = cached_set.get(c.id);
909 create(cached_set, change_list, registry, node, cached_roots)
keysesc to close
- j k
- move down, up
- enter
- open
- esc
- back, or up a level
- 1 2 3 4
- readme, files, commits, refs
- /
- filter
- y
- copy the clone command
- c
- compare the chosen commit with another (or shift-click both)
- ?
- show or hide this list