Skip to main content

tiny_diff/
lib.rs

1#![no_std]
2
3//! Keyed tree diffing with FIFO matching for repeated sibling keys.
4//!
5//! Paths identify nodes by child index from the root. Movement parents use new-tree
6//! paths, while movement pairs contain old and new child indices. Removals use old
7//! paths, additions and modifications use new paths. Removal order is unspecified.
8//! The caller applies the resulting diff and owns node lifetimes.
9
10extern crate alloc;
11#[cfg(feature = "std")]
12extern crate std;
13
14mod collections;
15
16use core::hash::Hash;
17
18use crate::collections::{
19    Box,
20    HashMap,
21    Vec,
22    VecDeque,
23};
24
25/// A tree node with stable sibling keys and index-based paths.
26/// Children must expose paths extending their parent's path by their child index.
27pub trait DiffNode: Sized {
28    type Key: Eq + Hash;
29    type Modifications;
30
31    /// Appends changes from `previous` to `self` into `diff`.
32    /// Matching roots must have paths of equal depth and corresponding parents.
33    #[cfg_attr(feature = "hotpath", hotpath::measure)]
34    fn diff(&self, previous: Option<&Self>, diff: &mut Diff<Self::Modifications>) {
35        diff_inner(self, previous, diff, false);
36    }
37
38    fn key(&self) -> &Self::Key;
39    fn path(&self) -> &[u32];
40    fn children(&self) -> &[Self];
41
42    /// Whether the entire child trees can be reused without reconciliation.
43    fn same_children(&self, _previous: &Self) -> bool {
44        false
45    }
46
47    /// Whether these nodes have compatible kinds, independently of their keys.
48    fn compatible(&self, previous: &Self) -> bool;
49
50    /// Returns changes for compatible nodes with matching keys, or `None` if unchanged.
51    fn modifications(&self, previous: &Self) -> Option<Self::Modifications>;
52
53    /// Checks application-specific sibling key rules before matching children in debug builds.
54    #[cfg(debug_assertions)]
55    fn validate_children(&self) {}
56}
57
58/// Changes between two trees, without applying them.
59#[derive(Debug)]
60pub struct Diff<Modifications> {
61    pub added: Vec<Box<[u32]>>,
62    pub modified: Vec<(Box<[u32]>, Modifications)>,
63    pub removed: Vec<Box<[u32]>>,
64    pub moved: HashMap<Box<[u32]>, Vec<(u32, u32)>>,
65}
66
67impl<Modifications> Default for Diff<Modifications> {
68    fn default() -> Self {
69        Self {
70            added: Vec::new(),
71            modified: Vec::new(),
72            removed: Vec::new(),
73            moved: HashMap::default(),
74        }
75    }
76}
77
78fn diff_inner<Node: DiffNode>(
79    current: &Node,
80    previous: Option<&Node>,
81    diff: &mut Diff<Node::Modifications>,
82    parent_removed: bool,
83) {
84    // Add new nodes and their descendants in preorder.
85    let Some(previous) = previous else {
86        diff.added.push(current.path().into());
87
88        for child in current.children() {
89            diff_inner(child, None, diff, false);
90        }
91
92        return;
93    };
94
95    // Replace incompatible node kinds without matching their descendants.
96    if !current.compatible(previous) {
97        diff.removed.push(previous.path().into());
98        diff_inner(current, None, diff, false);
99        return;
100    }
101
102    // Propagate replacement to matched descendants when a key or ancestor changes.
103    let removed_here = current.key() != previous.key() || parent_removed;
104    if removed_here {
105        diff.added.push(current.path().into());
106        diff.removed.push(previous.path().into());
107    } else {
108        if let Some(modifications) = current.modifications(previous) {
109            diff.modified.push((current.path().into(), modifications));
110        }
111
112        // Record index changes under the new parent path, independently of modifications.
113        if let (Some((&new_index, parent)), Some(&old_index)) =
114            (current.path().split_last(), previous.path().last())
115            && new_index != old_index
116        {
117            diff.moved
118                .entry(parent.into())
119                .or_default()
120                .push((old_index, new_index));
121        }
122    }
123
124    if !removed_here && current.same_children(previous) {
125        return;
126    }
127
128    #[cfg(debug_assertions)]
129    current.validate_children();
130
131    let current_children = current.children();
132    let previous_children = previous.children();
133
134    // Match the common prefix positionally without building a key map.
135    let mut start = 0;
136    while start < current_children.len() && start < previous_children.len() {
137        if current_children[start].key() != previous_children[start].key() {
138            break;
139        }
140
141        diff_inner(
142            &current_children[start],
143            Some(&previous_children[start]),
144            diff,
145            removed_here,
146        );
147        start += 1;
148    }
149
150    if start < current_children.len() || start < previous_children.len() {
151        // Queue remaining old indices by key to preserve FIFO matching for duplicates.
152        let mut previous_keys = HashMap::<&Node::Key, VecDeque<usize>>::default();
153        for (index, child) in previous_children.iter().enumerate().skip(start) {
154            previous_keys
155                .entry(child.key())
156                .or_default()
157                .push_back(index);
158        }
159
160        // Reuse the earliest unmatched old sibling or add the new node and its descendants.
161        for child in &current_children[start..] {
162            if let Some(old_index) = previous_keys
163                .get_mut(child.key())
164                .and_then(VecDeque::pop_front)
165            {
166                diff_inner(
167                    child,
168                    Some(&previous_children[old_index]),
169                    diff,
170                    removed_here,
171                );
172            } else {
173                diff_inner(child, None, diff, false);
174            }
175        }
176
177        // Remove unmatched branch roots, leaving descendant cleanup to the caller.
178        for indices in previous_keys.values() {
179            for index in indices {
180                diff.removed.push(previous_children[*index].path().into());
181            }
182        }
183    }
184}