objects/util/
line_diff.rs

1// SPDX-License-Identifier: Apache-2.0
2//! Shared line-oriented diff primitives used by native and Git-backed blame.
3
4use similar::{Algorithm, DiffOp};
5
6/// Split UTF-8 content into the same logical lines used by blame.
7pub fn split_text_lines(bytes: &[u8]) -> Option<Vec<String>> {
8    let content = std::str::from_utf8(bytes).ok()?;
9    Some(content.lines().map(str::to_string).collect())
10}
11
12/// Return matching `(old, new)` line indexes from a stable, linear-space diff.
13///
14/// This is the single alignment primitive used by native provenance and
15/// Git-overlay blame. Myers keeps memory proportional to the input lengths;
16/// the former full LCS matrix used memory proportional to their product.
17pub fn lcs_line_matches(old_lines: &[String], new_lines: &[String]) -> Vec<(usize, usize)> {
18    let mut matches = Vec::new();
19    for op in similar::capture_diff_slices(Algorithm::Myers, old_lines, new_lines) {
20        if let DiffOp::Equal {
21            old_index,
22            new_index,
23            len,
24        } = op
25        {
26            matches.extend((0..len).map(|offset| (old_index + offset, new_index + offset)));
27        }
28    }
29    matches
30}
31
32#[cfg(test)]
33mod tests {
34    use super::lcs_line_matches;
35
36    #[test]
37    fn line_matches_preserve_simple_alignment() {
38        let old = ["a", "b", "c"].map(str::to_string);
39        let new = ["a", "x", "c"].map(str::to_string);
40        assert_eq!(lcs_line_matches(&old, &new), vec![(0, 0), (2, 2)]);
41    }
42
43    #[test]
44    fn line_matches_are_bounded_for_large_files() {
45        // The former (n + 1) * (m + 1) u32 matrix would require about
46        // 10 GiB for this fixture. The shared Myers implementation stays
47        // linear in the 50k-line inputs and preserves every unchanged line.
48        let old = (0..50_000)
49            .map(|index| format!("line {index}"))
50            .collect::<Vec<_>>();
51        let mut new = old.clone();
52        new[25_000] = "replacement".to_string();
53
54        let matches = lcs_line_matches(&old, &new);
55        assert_eq!(matches.len(), 49_999);
56        assert_eq!(matches.first(), Some(&(0, 0)));
57        assert_eq!(matches.last(), Some(&(49_999, 49_999)));
58        assert!(!matches.contains(&(25_000, 25_000)));
59    }
60}
objects/util/line_diff.rs

objects/util/
line_diff.rs
