vs_protocol/delta/
diff.rs

1//! Compute a [`DeltaOp`] sequence that transforms one [`Tree`] into
2//! another.
3
4use crate::tree::{Node, Ref, Tree};
5
6use super::DeltaOp;
7
8/// Compute a delta that transforms `a` into `b`. `apply(a, diff(a, b))`
9/// equals `b` (modulo position resolution; see the property tests).
10///
11/// The diff is structurally faithful but not optimized: it never emits
12/// [`DeltaOp::Replace`] for whole-subtree collapse. The 40%-edit-
13/// distance threshold lives at the daemon level (M4) where ref churn
14/// is observable across many snapshots.
15#[must_use]
16pub fn diff(a: &Tree, b: &Tree) -> Vec<DeltaOp> {
17    let mut ops = Vec::new();
18    diff_children(&a.roots, &b.roots, Ref::ROOT, &mut ops);
19    ops
20}
21
22fn diff_children(a: &[Node], b: &[Node], parent: Ref, ops: &mut Vec<DeltaOp>) {
23    use std::collections::HashSet;
24    let a_refs: HashSet<Ref> = a.iter().map(|n| n.r).collect();
25    let b_refs: HashSet<Ref> = b.iter().map(|n| n.r).collect();
26
27    for node in a {
28        if !b_refs.contains(&node.r) {
29            ops.push(DeltaOp::Remove { r: node.r });
30        }
31    }
32
33    for (i, node) in b.iter().enumerate() {
34        if !a_refs.contains(&node.r) {
35            ops.push(DeltaOp::Add {
36                r: node.r,
37                parent,
38                pos: Some(u32::try_from(i).unwrap_or(u32::MAX)),
39                role: node.role,
40                label: node.label.clone(),
41                ops: node.ops.clone(),
42                attrs: node.attrs.clone(),
43            });
44            diff_children(&[], &node.children, node.r, ops);
45        }
46    }
47
48    for b_node in b {
49        if let Some(a_node) = a.iter().find(|n| n.r == b_node.r) {
50            diff_node(a_node, b_node, ops);
51        }
52    }
53
54    for (i, b_node) in b.iter().enumerate() {
55        if a_refs.contains(&b_node.r) {
56            let a_kept_pos = a
57                .iter()
58                .filter(|n| b_refs.contains(&n.r))
59                .position(|n| n.r == b_node.r)
60                .expect("kept ref present in a");
61            let b_kept_pos = b
62                .iter()
63                .filter(|n| a_refs.contains(&n.r))
64                .position(|n| n.r == b_node.r)
65                .expect("kept ref present in b");
66            if a_kept_pos != b_kept_pos {
67                ops.push(DeltaOp::Move {
68                    r: b_node.r,
69                    parent,
70                    pos: Some(u32::try_from(i).unwrap_or(u32::MAX)),
71                });
72            }
73        }
74    }
75}
76
77fn diff_node(a: &Node, b: &Node, ops: &mut Vec<DeltaOp>) {
78    if a.role != b.role || a.label != b.label || a.ops != b.ops {
79        ops.push(DeltaOp::Replace {
80            r: a.r,
81            subtree: vec![b.clone()],
82        });
83        return;
84    }
85    if a.attrs != b.attrs {
86        ops.push(DeltaOp::Update {
87            r: a.r,
88            attrs: b.attrs.clone(),
89        });
90    }
91    diff_children(&a.children, &b.children, a.r, ops);
92}
vs_protocol/delta/diff.rs

vs_protocol/delta/
diff.rs
