vault_core/
textdiff.rs

1//! A small line diff for rendered config files (Phase 35).
2//!
3//! Exists once, in Rust: the CLI, the server and the app all ask for a diff
4//! instead of each carrying one, so the three cannot disagree about what changed.
5//!
6//! Strategy: strip the common head and tail, then a longest-common-subsequence
7//! table over what is left. Rendered configs are tens to a few thousand lines
8//! and differ in a few places, so the middle is small. When it is not
9//! (`MAX_CELLS`), the middle is reported as one deletion and one insertion
10//! rather than spending quadratic memory; the output stays correct, only less
11//! minimal. // ponytail: LCS table, switch to Myers O(ND) if a real config ever
12//! hits the cell ceiling.
13
14/// Largest `n * m` the LCS table may reach (16 MB of `u32`).
15pub const MAX_CELLS: usize = 4_000_000;
16
17#[derive(Debug, Clone, PartialEq, Eq)]
18pub enum Op<'a> {
19    Equal(&'a str),
20    Delete(&'a str),
21    Insert(&'a str),
22}
23
24/// The edit script turning `a` into `b`, line by line.
25pub fn diff_ops<'a>(a: &'a str, b: &'a str) -> Vec<Op<'a>> {
26    let av: Vec<&str> = a.lines().collect();
27    let bv: Vec<&str> = b.lines().collect();
28    let head = av.iter().zip(&bv).take_while(|(x, y)| x == y).count();
29    let tail = av[head..]
30        .iter()
31        .rev()
32        .zip(bv[head..].iter().rev())
33        .take_while(|(x, y)| x == y)
34        .count();
35    let am = &av[head..av.len() - tail];
36    let bm = &bv[head..bv.len() - tail];
37
38    let mut ops: Vec<Op> = av[..head].iter().map(|l| Op::Equal(l)).collect();
39    if am.len().saturating_mul(bm.len()) > MAX_CELLS {
40        ops.extend(am.iter().map(|l| Op::Delete(l)));
41        ops.extend(bm.iter().map(|l| Op::Insert(l)));
42    } else {
43        let (n, m) = (am.len(), bm.len());
44        // lcs[i][j] = length of the LCS of am[i..] and bm[j..]
45        let mut lcs = vec![0u32; (n + 1) * (m + 1)];
46        let at = |i: usize, j: usize| i * (m + 1) + j;
47        for i in (0..n).rev() {
48            for j in (0..m).rev() {
49                lcs[at(i, j)] = if am[i] == bm[j] {
50                    lcs[at(i + 1, j + 1)] + 1
51                } else {
52                    lcs[at(i + 1, j)].max(lcs[at(i, j + 1)])
53                };
54            }
55        }
56        let (mut i, mut j) = (0, 0);
57        while i < n && j < m {
58            if am[i] == bm[j] {
59                ops.push(Op::Equal(am[i]));
60                i += 1;
61                j += 1;
62            } else if lcs[at(i + 1, j)] >= lcs[at(i, j + 1)] {
63                ops.push(Op::Delete(am[i]));
64                i += 1;
65            } else {
66                ops.push(Op::Insert(bm[j]));
67                j += 1;
68            }
69        }
70        ops.extend(am[i..].iter().map(|l| Op::Delete(l)));
71        ops.extend(bm[j..].iter().map(|l| Op::Insert(l)));
72    }
73    ops.extend(av[av.len() - tail..].iter().map(|l| Op::Equal(l)));
74    ops
75}
76
77/// Counts of changed lines: `(added, removed)`.
78pub fn stat(ops: &[Op]) -> (usize, usize) {
79    ops.iter().fold((0, 0), |(a, r), o| match o {
80        Op::Insert(_) => (a + 1, r),
81        Op::Delete(_) => (a, r + 1),
82        Op::Equal(_) => (a, r),
83    })
84}
85
86/// A unified diff with `context` lines around each change. Empty string when
87/// the two sides are identical.
88pub fn unified(a_label: &str, b_label: &str, a: &str, b: &str, context: usize) -> String {
89    let ops = diff_ops(a, b);
90    if stat(&ops) == (0, 0) {
91        return String::new();
92    }
93    // Index of each op's line in a and b (1-based), to head the hunks.
94    let mut pos = Vec::with_capacity(ops.len());
95    let (mut la, mut lb) = (1usize, 1usize);
96    for o in &ops {
97        pos.push((la, lb));
98        match o {
99            Op::Equal(_) => {
100                la += 1;
101                lb += 1;
102            }
103            Op::Delete(_) => la += 1,
104            Op::Insert(_) => lb += 1,
105        }
106    }
107    let changed: Vec<usize> = ops
108        .iter()
109        .enumerate()
110        .filter(|(_, o)| !matches!(o, Op::Equal(_)))
111        .map(|(i, _)| i)
112        .collect();
113
114    // Merge changes whose context windows touch into one hunk.
115    let mut hunks: Vec<(usize, usize)> = Vec::new();
116    for &c in &changed {
117        let lo = c.saturating_sub(context);
118        let hi = (c + context + 1).min(ops.len());
119        match hunks.last_mut() {
120            Some(last) if lo <= last.1 => last.1 = last.1.max(hi),
121            _ => hunks.push((lo, hi)),
122        }
123    }
124
125    let mut out = format!("--- {a_label}\n+++ {b_label}\n");
126    for (lo, hi) in hunks {
127        let slice = &ops[lo..hi];
128        let a_len = slice.iter().filter(|o| !matches!(o, Op::Insert(_))).count();
129        let b_len = slice.iter().filter(|o| !matches!(o, Op::Delete(_))).count();
130        let (sa, sb) = pos[lo];
131        out.push_str(&format!(
132            "@@ -{},{} +{},{} @@\n",
133            if a_len == 0 { sa - 1 } else { sa },
134            a_len,
135            if b_len == 0 { sb - 1 } else { sb },
136            b_len
137        ));
138        for o in slice {
139            let (p, l) = match o {
140                Op::Equal(l) => (' ', l),
141                Op::Delete(l) => ('-', l),
142                Op::Insert(l) => ('+', l),
143            };
144            out.push(p);
145            out.push_str(l);
146            out.push('\n');
147        }
148    }
149    out
150}
151
152#[cfg(test)]
153mod tests {
154    use super::*;
155
156    fn rebuild(ops: &[Op], side_a: bool) -> String {
157        let mut v = Vec::new();
158        for o in ops {
159            match (o, side_a) {
160                (Op::Equal(l), _) | (Op::Delete(l), true) | (Op::Insert(l), false) => v.push(*l),
161                _ => {}
162            }
163        }
164        v.join("\n")
165    }
166
167    #[test]
168    fn identical_text_has_no_diff() {
169        assert_eq!(unified("a", "b", "x\ny\n", "x\ny\n", 3), "");
170    }
171
172    #[test]
173    fn a_changed_line_shows_as_a_delete_and_an_insert_with_context() {
174        let d = unified("old", "new", "a\nb\nc\nd\ne\n", "a\nb\nX\nd\ne\n", 1);
175        assert_eq!(d, "--- old\n+++ new\n@@ -2,3 +2,3 @@\n b\n-c\n+X\n d\n");
176    }
177
178    #[test]
179    fn distant_changes_make_separate_hunks_and_near_ones_merge() {
180        let a: String = (1..=20).map(|i| format!("l{i}\n")).collect();
181        let far = a.replace("l2\n", "L2\n").replace("l19\n", "L19\n");
182        assert_eq!(unified("a", "b", &a, &far, 1).matches("@@ -").count(), 2);
183        let near = a.replace("l5\n", "L5\n").replace("l7\n", "L7\n");
184        assert_eq!(unified("a", "b", &a, &near, 1).matches("@@ -").count(), 1);
185    }
186
187    #[test]
188    fn pure_additions_and_removals_head_their_hunks_correctly() {
189        assert_eq!(
190            unified("a", "b", "", "x\ny\n", 3),
191            "--- a\n+++ b\n@@ -0,0 +1,2 @@\n+x\n+y\n"
192        );
193        assert_eq!(
194            unified("a", "b", "x\ny\n", "", 3),
195            "--- a\n+++ b\n@@ -1,2 +0,0 @@\n-x\n-y\n"
196        );
197    }
198
199    #[test]
200    fn the_script_always_reproduces_both_sides() {
201        let cases = [
202            ("a\nb\nc", "a\nc"),
203            ("", "a"),
204            ("a", ""),
205            ("a\nb\nc\nd", "d\nc\nb\na"),
206            ("x\nx\nx", "x\nx"),
207            ("1\n2\n3\n4\n5\n6", "1\n3\n2\n4\n6\n5\n7"),
208        ];
209        for (a, b) in cases {
210            let ops = diff_ops(a, b);
211            assert_eq!(rebuild(&ops, true), a, "side a of {a:?} -> {b:?}");
212            assert_eq!(rebuild(&ops, false), b, "side b of {a:?} -> {b:?}");
213        }
214    }
215
216    #[test]
217    fn the_diff_is_minimal_for_a_single_insertion() {
218        let ops = diff_ops("a\nb\nc", "a\nb\nNEW\nc");
219        assert_eq!(stat(&ops), (1, 0));
220    }
221
222    #[test]
223    fn past_the_cell_ceiling_the_middle_is_replaced_whole_but_still_correct() {
224        let a: String = (0..2100).map(|i| format!("a{i}\n")).collect();
225        let b: String = (0..2100).map(|i| format!("b{i}\n")).collect();
226        let ops = diff_ops(&a, &b);
227        assert_eq!(stat(&ops), (2100, 2100));
228        assert_eq!(rebuild(&ops, true), a.trim_end());
229    }
230}
vault_core/textdiff.rs

vault_core/
textdiff.rs
