euv_core/vdom/
fn.rs

1use super::*;
2
3/// Returns `true` if every node in the slice has a key.
4///
5/// Returns `false` if the slice is empty (an empty list
6/// trivially has no keys; treating it as keyed would
7/// cause a fallback when both sides are empty).
8///
9/// # Arguments
10///
11/// - `&[VirtualNode]` - Shared reference to a `[VirtualNode]`.
12///
13/// # Returns
14///
15/// - `bool` - A boolean.
16pub fn all_have_keys(children: &[VirtualNode]) -> bool {
17    !children.is_empty() && children.iter().all(VirtualNode::has_key)
18}
19
20/// Computes the diff between two virtual-DOM child lists.
21///
22/// Dispatches to `diff_keyed` when both lists have keys
23/// on every node, otherwise falls back to `diff_positional`.
24///
25/// # Arguments
26///
27/// - `&[VirtualNode]` - Shared reference to a `[VirtualNode]`.
28/// - `&[VirtualNode]` - Shared reference to a `[VirtualNode]`.
29///
30/// # Returns
31///
32/// - `Vec<DiffOp>` - A `Vec<DiffOp>` value.
33pub fn diff_children(old: &[VirtualNode], new: &[VirtualNode]) -> Vec<DiffOp> {
34    if all_have_keys(old) && all_have_keys(new) {
35        diff_keyed(old, new)
36    } else {
37        diff_positional(old, new)
38    }
39}
40
41/// Keyed diff. Both slices must have keys on every node;
42/// nodes without keys are skipped (they are not eligible
43/// for keyed diffing).
44///
45/// # Arguments
46///
47/// - `&[VirtualNode]` - Shared reference to a `[VirtualNode]`.
48/// - `&[VirtualNode]` - Shared reference to a `[VirtualNode]`.
49///
50/// # Returns
51///
52/// - `Vec<DiffOp>` - A `Vec<DiffOp>` value.
53pub fn diff_keyed(old: &[VirtualNode], new: &[VirtualNode]) -> Vec<DiffOp> {
54    let mut ops: Vec<DiffOp> = Vec::new();
55    // Build a set of new keys for fast removal check.
56    let mut new_key_set: HashSet<&str> = HashSet::with_capacity(new.len());
57    for new_child in new.iter() {
58        if let Some(key) = new_child.key() {
59            new_key_set.insert(key);
60        }
61    }
62    // Walk new children. For each new child:
63    // - If its key existed in old, emit Update at its
64    //   new-list index.
65    // - Otherwise, emit Insert at its new-list index.
66    // We do NOT emit Move: a correct move-aware keyed
67    // diff would need to track shifting indices when
68    // earlier inserts/removals change later keys'
69    // positions. The renderer applies ops in order, so
70    // `Update { index }` always refers to the target
71    // position in the new list. The renderer can decide
72    // whether that means "patch in place" or "move DOM
73    // node" based on its own bookkeeping. This keeps
74    // the diff algorithm pure and trivially testable.
75    for (new_index, new_child) in new.iter().enumerate() {
76        let Some(key) = new_child.key() else {
77            continue;
78        };
79        let existed_in_old: bool = old.iter().any(|old_child| old_child.key() == Some(key));
80        if existed_in_old {
81            ops.push(DiffOp::Update { index: new_index });
82        } else {
83            ops.push(DiffOp::Insert {
84                index: new_index,
85                node: new_child.clone(),
86            });
87        }
88    }
89    // Now emit Remove ops for any old keys not in new.
90    // Iterate in reverse order so removals don't shift
91    // earlier indices.
92    for (old_index, old_child) in old.iter().enumerate().rev() {
93        let Some(key) = old_child.key() else {
94            continue;
95        };
96        if !new_key_set.contains(key) {
97            ops.push(DiffOp::Remove { index: old_index });
98        }
99    }
100    ops
101}
102
103/// Positional diff. Patches in place by index, then
104/// inserts/removes at the tail.
105///
106/// # Arguments
107///
108/// - `&[VirtualNode]` - Shared reference to a `[VirtualNode]`.
109/// - `&[VirtualNode]` - Shared reference to a `[VirtualNode]`.
110///
111/// # Returns
112///
113/// - `Vec<DiffOp>` - A `Vec<DiffOp>` value.
114pub fn diff_positional(old: &[VirtualNode], new: &[VirtualNode]) -> Vec<DiffOp> {
115    let mut ops: Vec<DiffOp> = Vec::new();
116    let common_len: usize = old.len().min(new.len());
117    for index in 0..common_len {
118        ops.push(DiffOp::Update { index });
119    }
120    if new.len() > old.len() {
121        for (offset, new_child) in new.iter().skip(common_len).enumerate() {
122            ops.push(DiffOp::Insert {
123                index: common_len + offset,
124                node: new_child.clone(),
125            });
126        }
127    } else if old.len() > new.len() {
128        for index in (common_len..old.len()).rev() {
129            ops.push(DiffOp::Remove { index });
130        }
131    }
132    ops
133}
euv_core/vdom/fn.rs

euv_core/vdom/
fn.rs
