2 cached_set::{CacheId, CachedSet},
3 change_list::ChangeListBuilder,
4 events::EventsRegistry,
5 node::{Attribute, ElementNode, Listener, Node, NodeKind, TextNode},
7use fxhash::{FxHashMap, FxHashSet};
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`.
15// Upon entry to this function, the physical DOM node must be on the top of the
20// The change list 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);
88 // Both the new and old nodes are cached.
89 (&NodeKind::Cached(ref new), &NodeKind::Cached(ref old)) => {
90 cached_roots.insert(new.id);
93 // This is the same cached node, so nothing has changed!
97 let new = cached_set.get(new.id);
98 let old = cached_set.get(old.id);
99 diff(cached_set, change_list, registry, old, new, cached_roots);
102 // New cached node when the old node was not cached. In this scenario,
103 // we assume that they are pretty different, and it isn't worth diffing
104 // the subtrees, so we just create the new cached node afresh.
105 (&NodeKind::Cached(ref c), _) => {
106 cached_roots.insert(c.id);
107 let new = cached_set.get(c.id);
108 create(cached_set, change_list, registry, new, cached_roots);
109 registry.remove_subtree(&old);
110 change_list.replace_with();
113 // Old cached node and new non-cached node. Again, assume that they are
114 // probably pretty different and create the new non-cached node afresh.
115 (_, &NodeKind::Cached(_)) => {
116 create(cached_set, change_list, registry, new, cached_roots);
117 registry.remove_subtree(&old);
118 change_list.replace_with();
123// Diff event listeners between `old` and `new`.
125// The listeners' node must be on top of the change list stack:
129// The change list stack is left unchanged.
131 change_list: &mut ChangeListBuilder,
132 registry: &mut EventsRegistry,
136 'outer1: for new_l in new {
138 // Safety relies on removing `new_l` from the registry manually at
139 // the end of its lifetime. This happens below in the `'outer2`
140 // loop, and elsewhere in diffing when removing old dom trees.
145 if new_l.event == old_l.event {
146 change_list.update_event_listener(new_l);
151 change_list.new_event_listener(new_l);
154 'outer2: for old_l in old {
155 registry.remove(old_l);
158 if new_l.event == old_l.event {
162 change_list.remove_event_listener(old_l.event);
166// Diff a node's attributes.
168// The attributes' node must be on top of the change list stack:
172// The change list stack is left unchanged.
173fn diff_attributes(change_list: &mut ChangeListBuilder, old: &[Attribute], new: &[Attribute]) {
174 // Do O(n^2) passes to add/update and remove attributes, since
175 // there are almost always very few attributes.
176 'outer: for new_attr in new {
177 if new_attr.is_volatile() {
178 change_list.set_attribute(new_attr.name, new_attr.value);
180 for old_attr in old {
181 if old_attr.name == new_attr.name {
182 if old_attr.value != new_attr.value {
183 change_list.set_attribute(new_attr.name, new_attr.value);
188 change_list.set_attribute(new_attr.name, new_attr.value);
192 'outer2: for old_attr in old {
193 for new_attr in new {
194 if old_attr.name == new_attr.name {
198 change_list.remove_attribute(old_attr.name);
202// Diff the given set of old and new children.
204// The parent must be on top of the change list stack when this function is
209// the change list stack is in the same state when this function returns.
211 cached_set: &CachedSet,
212 change_list: &mut ChangeListBuilder,
213 registry: &mut EventsRegistry,
216 cached_roots: &mut FxHashSet<CacheId>,
220 remove_all_children(change_list, registry, old);
226 create_and_append_children(cached_set, change_list, registry, new, cached_roots);
230 let new_is_keyed = new[0].key().is_some();
231 let old_is_keyed = old[0].key().is_some();
234 new.iter().all(|n| n.key().is_some() == new_is_keyed),
235 "all siblings must be keyed or all siblings must be non-keyed"
238 old.iter().all(|o| o.key().is_some() == old_is_keyed),
239 "all siblings must be keyed or all siblings must be non-keyed"
242 if new_is_keyed && old_is_keyed {
243 let t = change_list.next_temporary();
244 diff_keyed_children(cached_set, change_list, registry, old, new, cached_roots);
245 change_list.set_next_temporary(t);
247 diff_non_keyed_children(cached_set, change_list, registry, old, new, cached_roots);
251// Diffing "keyed" children.
253// With keyed children, we care about whether we delete, move, or create nodes
254// versus mutate existing nodes in place. Presumably there is some sort of CSS
255// transition animation that makes the virtual DOM diffing algorithm
256// observable. By specifying keys for nodes, we know which virtual DOM nodes
257// must reuse (or not reuse) the same physical DOM nodes.
259// This is loosely based on Inferno's keyed patching implementation. However, we
260// have to modify the algorithm since we are compiling the diff down into change
261// list instructions that will be executed later, rather than applying the
262// changes to the DOM directly as we compare virtual DOMs.
264// https://github.com/infernojs/inferno/blob/36fd96/packages/inferno/src/DOM/patching.ts#L530-L739
266// When entering this function, the parent must be on top of the change list
271// Upon exiting, the change list stack is in the same state.
272fn diff_keyed_children(
273 cached_set: &CachedSet,
274 change_list: &mut ChangeListBuilder,
275 registry: &mut EventsRegistry,
278 cached_roots: &mut FxHashSet<CacheId>,
280 if cfg!(debug_assertions) {
281 let mut keys = FxHashSet::default();
282 let mut assert_unique_keys = |children: &[Node]| {
284 for child in children {
285 let key = child.key();
288 "if any sibling is keyed, all siblings must be keyed"
295 "keyed siblings must each have a unique key"
298 assert_unique_keys(old);
299 assert_unique_keys(new);
302 // First up, we diff all the nodes with the same key at the beginning of the
305 // `shared_prefix_count` is the count of how many nodes at the start of
306 // `new` and `old` share the same keys.
307 let shared_prefix_count =
308 match diff_keyed_prefix(cached_set, change_list, registry, old, new, cached_roots) {
309 KeyedPrefixResult::Finished => return,
310 KeyedPrefixResult::MoreWorkToDo(count) => count,
313 // Next, we find out how many of the nodes at the end of the children have
314 // the same key. We do _not_ diff them yet, since we want to emit the change
315 // list instructions such that they can be applied in a single pass over the
316 // DOM. Instead, we just save this information for later.
318 // `shared_suffix_count` is the count of how many nodes at the end of `new`
319 // and `old` share the same keys.
320 let shared_suffix_count = old[shared_prefix_count..]
323 .zip(new[shared_prefix_count..].iter().rev())
324 .take_while(|&(old, new)| old.key() == new.key())
327 let old_shared_suffix_start = old.len() - shared_suffix_count;
328 let new_shared_suffix_start = new.len() - shared_suffix_count;
330 // Ok, we now hopefully have a smaller range of children in the middle
331 // within which to re-order nodes with the same keys, remove old nodes with
332 // now-unused keys, and create new nodes with fresh keys.
337 &old[shared_prefix_count..old_shared_suffix_start],
338 &new[shared_prefix_count..new_shared_suffix_start],
342 old_shared_suffix_start,
345 // Finally, diff the nodes at the end of `old` and `new` that share keys.
346 let old_suffix = &old[old_shared_suffix_start..];
347 let new_suffix = &new[new_shared_suffix_start..];
348 debug_assert_eq!(old_suffix.len(), new_suffix.len());
349 if !old_suffix.is_empty() {
357 new_shared_suffix_start,
362enum KeyedPrefixResult {
363 // Fast path: we finished diffing all the children just by looking at the
364 // prefix of shared keys!
366 // There is more diffing work to do. Here is a count of how many children at
367 // the beginning of `new` and `old` we already processed.
371// Diff the prefix of children in `new` and `old` that share the same keys in
374// Upon entry of this function, the change list stack must be:
378// Upon exit, the change list stack is the same.
380 cached_set: &CachedSet,
381 change_list: &mut ChangeListBuilder,
382 registry: &mut EventsRegistry,
385 cached_roots: &mut FxHashSet<CacheId>,
386) -> KeyedPrefixResult {
387 let mut pushed = false;
388 let mut shared_prefix_count = 0;
390 for (old, new) in old.iter().zip(new.iter()) {
391 if old.key() != new.key() {
396 debug_assert!(shared_prefix_count > 0);
397 change_list.pop_push_next_sibling();
399 debug_assert_eq!(shared_prefix_count, 0);
400 change_list.push_first_child();
404 diff(cached_set, change_list, registry, old, new, cached_roots);
405 shared_prefix_count += 1;
407 // At the end of the loop, the change list stack looks like
409 // [... parent child_we_just_diffed]
410 debug_assert!(pushed);
413 // If that was all of the old children, then create and append the remaining
414 // new children and we're finished.
415 if shared_prefix_count == old.len() {
418 "we handle the case of empty children before calling this method, so
419 `shared_prefix_count` must be greater than zero, and therefore we
420 must have pushed in the above loop"
423 create_and_append_children(
427 &new[shared_prefix_count..],
430 return KeyedPrefixResult::Finished;
433 // And if that was all of the new children, then remove all of the remaining
434 // old children and we're finished.
435 if shared_prefix_count == new.len() {
437 debug_assert!(pushed);
438 change_list.pop_push_next_sibling();
439 change_list.remove_self_and_next_siblings();
440 return KeyedPrefixResult::Finished;
444 debug_assert!(shared_prefix_count > 0);
447 KeyedPrefixResult::MoreWorkToDo(shared_prefix_count)
450// The most-general, expensive code path for keyed children diffing.
452// We find the longest subsequence within `old` of children that are relatively
453// ordered the same way in `new` (via finding a longest-increasing-subsequence
454// of the old child's index within `new`). The children that are elements of
455// this subsequence will remain in place, minimizing the number of DOM moves we
458// Upon entry to this function, the change list stack must be:
462// Upon exit from this function, it will be restored to that same state.
464 cached_set: &CachedSet,
465 change_list: &mut ChangeListBuilder,
466 registry: &mut EventsRegistry,
469 cached_roots: &mut FxHashSet<CacheId>,
470 shared_prefix_count: usize,
471 shared_suffix_count: usize,
472 old_shared_suffix_start: usize,
474 // Should have already diffed the shared-key prefixes and suffixes.
475 debug_assert_ne!(new.first().map(|n| n.key()), old.first().map(|o| o.key()));
476 debug_assert_ne!(new.last().map(|n| n.key()), old.last().map(|o| o.key()));
478 // The algorithm below relies upon using `u32::MAX` as a sentinel
479 // value, so if we have that many new nodes, it won't work. This
480 // check is a bit academic (hence only enabled in debug), since
481 // wasm32 doesn't have enough address space to hold that many nodes
483 debug_assert!(new.len() < u32::MAX as usize);
485 // Map from each `old` node's key to its index within `old`.
486 let mut old_key_to_old_index = FxHashMap::default();
487 old_key_to_old_index.reserve(old.len());
488 old_key_to_old_index.extend(old.iter().enumerate().map(|(i, o)| (o.key(), i)));
490 // The set of shared keys between `new` and `old`.
491 let mut shared_keys = FxHashSet::default();
492 // Map from each index in `new` to the index of the node in `old` that
494 let mut new_index_to_old_index = Vec::with_capacity(new.len());
495 new_index_to_old_index.extend(new.iter().map(|n| {
497 if let Some(&i) = old_key_to_old_index.get(&key) {
498 shared_keys.insert(key);
505 // If none of the old keys are reused by the new children, then we
506 // remove all the remaining old children and create the new children
508 if shared_suffix_count == 0 && shared_keys.is_empty() {
509 if shared_prefix_count == 0 {
510 remove_all_children(change_list, registry, old);
512 change_list.pop_push_next_sibling();
513 remove_self_and_next_siblings(change_list, registry, &old[shared_prefix_count..]);
515 create_and_append_children(cached_set, change_list, registry, new, cached_roots);
519 // Save each of the old children whose keys are reused in the new
521 let mut old_index_to_temp = vec![u32::MAX; old.len()];
524 let end = (start..old.len())
526 let key = old[i].key();
527 !shared_keys.contains(&key)
529 .unwrap_or(old.len());
532 let mut t = change_list.save_children_to_temporaries(
533 shared_prefix_count + start,
534 shared_prefix_count + end,
536 for i in start..end {
537 old_index_to_temp[i] = t;
542 debug_assert!(end <= old.len());
543 if end == old.len() {
550 // Remove any old children whose keys were not reused in the new
551 // children. Remove from the end first so that we don't mess up indices.
552 let mut removed_count = 0;
553 for (i, old_child) in old.iter().enumerate().rev() {
554 if !shared_keys.contains(&old_child.key()) {
555 registry.remove_subtree(old_child);
556 change_list.remove_child(i + shared_prefix_count);
561 // If there aren't any more new children, then we are done!
566 // The longest increasing subsequence within `new_index_to_old_index`. This
567 // is the longest sequence on DOM nodes in `old` that are relatively ordered
568 // correctly within `new`. We will leave these nodes in place in the DOM,
569 // and only move nodes that are not part of the LIS. This results in the
570 // maximum number of DOM nodes left in place, AKA the minimum number of DOM
572 let mut new_index_is_in_lis = FxHashSet::default();
573 new_index_is_in_lis.reserve(new_index_to_old_index.len());
574 let mut predecessors = vec![0; new_index_to_old_index.len()];
575 let mut starts = vec![0; new_index_to_old_index.len()];
576 longest_increasing_subsequence::lis_with(
577 &new_index_to_old_index,
578 &mut new_index_is_in_lis,
584 // Now we will iterate from the end of the new children back to the
585 // beginning, diffing old children we are reusing and if they aren't in the
586 // LIS moving them to their new destination, or creating new children. Note
587 // that iterating in reverse order lets us use `Node.prototype.insertBefore`
588 // to move/insert children.
590 // But first, we ensure that we have a child on the change list stack that
591 // we can `insertBefore`. We handle this once before looping over `new`
592 // children, so that we don't have to keep checking on every loop iteration.
593 if shared_suffix_count > 0 {
594 // There is a shared suffix after these middle children. We will be
595 // inserting before that shared suffix, so add the first child of that
596 // shared suffix to the change list stack.
599 change_list.push_child(old_shared_suffix_start - removed_count);
600 // [... parent first_child_of_shared_suffix]
602 // There is no shared suffix coming after these middle children.
603 // Therefore we have to process the last child in `new` and move it to
604 // the end of the parent's children if it isn't already there.
605 let last_index = new.len() - 1;
606 let last = new.last().unwrap_throw();
607 new = &new[..new.len() - 1];
608 if shared_keys.contains(&last.key()) {
609 let old_index = new_index_to_old_index[last_index];
610 let temp = old_index_to_temp[old_index];
612 change_list.push_temporary(temp);
622 if new_index_is_in_lis.contains(&last_index) {
623 // Don't move it, since it is already where it needs to be.
625 change_list.append_child();
627 change_list.push_temporary(temp);
632 create(cached_set, change_list, registry, last, cached_roots);
634 change_list.append_child();
636 change_list.push_last_child();
641 for (new_index, new_child) in new.iter().enumerate().rev() {
642 let old_index = new_index_to_old_index[new_index];
643 if old_index == u32::MAX as usize {
644 debug_assert!(!shared_keys.contains(&new_child.key()));
645 // [... parent successor]
646 create(cached_set, change_list, registry, new_child, cached_roots);
647 // [... parent successor new_child]
648 change_list.insert_before();
649 // [... parent new_child]
651 debug_assert!(shared_keys.contains(&new_child.key()));
652 let temp = old_index_to_temp[old_index];
653 debug_assert_ne!(temp, u32::MAX);
655 if new_index_is_in_lis.contains(&new_index) {
656 // [... parent successor]
659 change_list.push_temporary(temp);
660 // [... parent new_child]
662 // [... parent successor]
663 change_list.push_temporary(temp);
664 // [... parent successor new_child]
665 change_list.insert_before();
666 // [... parent new_child]
680 // [... parent child]
685// Diff the suffix of keyed children that share the same keys in the same order.
687// The parent must be on the change list stack when we enter this function:
691// When this function exits, the change list stack remains the same.
693 cached_set: &CachedSet,
694 change_list: &mut ChangeListBuilder,
695 registry: &mut EventsRegistry,
698 cached_roots: &mut FxHashSet<CacheId>,
699 new_shared_suffix_start: usize,
701 debug_assert_eq!(old.len(), new.len());
702 debug_assert!(!old.is_empty());
705 change_list.push_child(new_shared_suffix_start);
706 // [... parent new_child]
708 for (old_child, new_child) in old.iter().zip(new.iter()) {
718 // [... parent this_new_child]
719 change_list.pop_push_next_sibling();
720 // [... parent next_new_child]
727// Diff children that are not keyed.
729// The parent must be on the top of the change list stack when entering this
734// the change list stack is in the same state when this function returns.
735fn diff_non_keyed_children(
736 cached_set: &CachedSet,
737 change_list: &mut ChangeListBuilder,
738 registry: &mut EventsRegistry,
741 cached_roots: &mut FxHashSet<CacheId>,
743 // Handled these cases in `diff_children` before calling this function.
744 debug_assert!(!new.is_empty());
745 debug_assert!(!old.is_empty());
747 for (i, (new_child, old_child)) in new.iter().zip(old.iter()).enumerate() {
750 change_list.push_first_child();
751 // [... parent first_child]
753 // [... parent prev_sibling]
754 change_list.pop_push_next_sibling();
755 // [... parent next_sibling]
768 // Note that because `new` and `old` are not empty, the previous loop always
769 // executes at least once, so the change list stack is now:
771 // [... parent child]
773 match old.len().cmp(&new.len()) {
774 Ordering::Greater => {
775 // [... parent last_shared_child]
776 change_list.pop_push_next_sibling();
777 // [... parent first_child_to_remove]
778 remove_self_and_next_siblings(change_list, registry, &old[new.len()..]);
782 // [... parent last_child]
785 create_and_append_children(
794 // [... parent child]
801// Create the given children and append them to the parent node.
803// The parent node must currently be on top of the change list stack:
807// When this function returns, the change list stack is in the same state.
808fn create_and_append_children(
809 cached_set: &CachedSet,
810 change_list: &mut ChangeListBuilder,
811 registry: &mut EventsRegistry,
813 cached_roots: &mut FxHashSet<CacheId>,
816 create(cached_set, change_list, registry, child, cached_roots);
817 change_list.append_child();
821// Remove all of a node's children.
823// The change list stack must have this shape upon entry to this function:
827// When this function returns, the change list stack is in the same state.
828fn remove_all_children(
829 change_list: &mut ChangeListBuilder,
830 registry: &mut EventsRegistry,
834 registry.remove_subtree(child);
836 // Fast way to remove all children: set the node's textContent to an empty
838 change_list.set_text("");
841// Remove the current child and all of its following siblings.
843// The change list stack must have this shape upon entry to this function:
847// After the function returns, the child is no longer on the change list stack:
850fn remove_self_and_next_siblings(
851 change_list: &mut ChangeListBuilder,
852 registry: &mut EventsRegistry,
856 registry.remove_subtree(child);
858 change_list.remove_self_and_next_siblings();
861// Emit instructions to create the given virtual node.
863// The change list stack may have any shape upon entering this function:
867// When this function returns, the new node is on top of the change list stack:
871 cached_set: &CachedSet,
872 change_list: &mut ChangeListBuilder,
873 registry: &mut EventsRegistry,
875 cached_roots: &mut FxHashSet<CacheId>,
878 NodeKind::Text(TextNode { text }) => {
879 change_list.create_text_node(text);
881 NodeKind::Element(&ElementNode {
889 if let Some(namespace) = namespace {
890 change_list.create_element_ns(tag_name, namespace);
892 change_list.create_element(tag_name);
898 change_list.new_event_listener(l);
900 for attr in attributes {
901 change_list.set_attribute(&attr.name, &attr.value);
903 for child in children {
904 create(cached_set, change_list, registry, child, cached_roots);
905 change_list.append_child();
908 NodeKind::Cached(ref c) => {
909 cached_roots.insert(c.id);
910 let node = cached_set.get(c.id);
911 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