| 1 | //! Line diffs (Myers' O(ND) algorithm) and unified output. |
| 2 | |
| 3 | #[derive(Debug, Clone, Copy, PartialEq, Eq)] |
| 4 | pub enum Op { |
| 5 | Same, |
| 6 | Del, |
| 7 | Add, |
| 8 | } |
| 9 | |
| 10 | /// The shortest edit script from `a` to `b`, as (op, line) pairs in order. |
| 11 | pub fn diff<'a>(a: &[&'a str], b: &[&'a str]) -> Vec<(Op, &'a str)> { |
| 12 | // Trim the common prefix and suffix first; most diffs are small edits in large files. |
| 13 | let pre = a.iter().zip(b).take_while(|(x, y)| x == y).count(); |
| 14 | let suf = a[pre..].iter().rev().zip(b[pre..].iter().rev()).take_while(|(x, y)| x == y).count(); |
| 15 | let (am, bm) = (&a[pre..a.len() - suf], &b[pre..b.len() - suf]); |
| 16 | |
| 17 | let mut out: Vec<(Op, &str)> = a[..pre].iter().map(|l| (Op::Same, *l)).collect(); |
| 18 | out.extend(myers(am, bm)); |
| 19 | out.extend(a[a.len() - suf..].iter().map(|l| (Op::Same, *l))); |
| 20 | out |
| 21 | } |
| 22 | |
| 23 | fn myers<'a>(a: &[&'a str], b: &[&'a str]) -> Vec<(Op, &'a str)> { |
| 24 | let (n, m) = (a.len() as isize, b.len() as isize); |
| 25 | if n == 0 { |
| 26 | return b.iter().map(|l| (Op::Add, *l)).collect(); |
| 27 | } |
| 28 | if m == 0 { |
| 29 | return a.iter().map(|l| (Op::Del, *l)).collect(); |
| 30 | } |
| 31 | let max = (n + m) as usize; |
| 32 | let offset = max as isize; |
| 33 | let mut v = vec![0isize; 2 * max + 2]; |
| 34 | let mut trace: Vec<Vec<isize>> = Vec::new(); |
| 35 | 'outer: for d in 0..=max as isize { |
| 36 | trace.push(v.clone()); |
| 37 | let mut k = -d; |
| 38 | while k <= d { |
| 39 | let idx = (k + offset) as usize; |
| 40 | let mut x = if k == -d || (k != d && v[idx - 1] < v[idx + 1]) { v[idx + 1] } else { v[idx - 1] + 1 }; |
| 41 | let mut y = x - k; |
| 42 | while x < n && y < m && a[x as usize] == b[y as usize] { |
| 43 | x += 1; |
| 44 | y += 1; |
| 45 | } |
| 46 | v[idx] = x; |
| 47 | if x >= n && y >= m { |
| 48 | break 'outer; |
| 49 | } |
| 50 | k += 2; |
| 51 | } |
| 52 | } |
| 53 | // Walk back through the saved frontiers to recover the path. |
| 54 | let mut out = Vec::new(); |
| 55 | let (mut x, mut y) = (n, m); |
| 56 | for d in (0..trace.len() as isize).rev() { |
| 57 | let v = &trace[d as usize]; |
| 58 | let k = x - y; |
| 59 | let idx = (k + offset) as usize; |
| 60 | let prev_k = if k == -d || (k != d && v[idx - 1] < v[idx + 1]) { k + 1 } else { k - 1 }; |
| 61 | let prev_x = v[(prev_k + offset) as usize]; |
| 62 | let prev_y = prev_x - prev_k; |
| 63 | while x > prev_x && y > prev_y { |
| 64 | out.push((Op::Same, a[(x - 1) as usize])); |
| 65 | x -= 1; |
| 66 | y -= 1; |
| 67 | } |
| 68 | if d > 0 { |
| 69 | if x == prev_x { |
| 70 | out.push((Op::Add, b[(y - 1) as usize])); |
| 71 | } else { |
| 72 | out.push((Op::Del, a[(x - 1) as usize])); |
| 73 | } |
| 74 | } |
| 75 | x = prev_x; |
| 76 | y = prev_y; |
| 77 | } |
| 78 | out.reverse(); |
| 79 | out |
| 80 | } |
| 81 | |
| 82 | /// Split text into lines, keeping track of whether the last one ended with a newline. |
| 83 | pub fn lines(text: &str) -> Vec<&str> { |
| 84 | if text.is_empty() { |
| 85 | return Vec::new(); |
| 86 | } |
| 87 | text.strip_suffix('\n').unwrap_or(text).split('\n').collect() |
| 88 | } |
| 89 | |
| 90 | /// Unified diff hunks with `context` lines around each change. Empty if equal. |
| 91 | pub fn unified(a: &str, b: &str, context: usize) -> String { |
| 92 | let (al, bl) = (lines(a), lines(b)); |
| 93 | let ops = diff(&al, &bl); |
| 94 | if ops.iter().all(|(op, _)| *op == Op::Same) { |
| 95 | return String::new(); |
| 96 | } |
| 97 | // Line numbers before each op. |
| 98 | let mut pos = Vec::with_capacity(ops.len()); |
| 99 | let (mut i, mut j) = (1usize, 1usize); |
| 100 | for (op, _) in &ops { |
| 101 | pos.push((i, j)); |
| 102 | match op { |
| 103 | Op::Same => { |
| 104 | i += 1; |
| 105 | j += 1; |
| 106 | } |
| 107 | Op::Del => i += 1, |
| 108 | Op::Add => j += 1, |
| 109 | } |
| 110 | } |
| 111 | let changed: Vec<usize> = ops.iter().enumerate().filter(|(_, (op, _))| *op != Op::Same).map(|(k, _)| k).collect(); |
| 112 | let mut out = String::new(); |
| 113 | let mut k = 0; |
| 114 | while k < changed.len() { |
| 115 | let start = changed[k].saturating_sub(context); |
| 116 | let mut end = changed[k]; |
| 117 | while k + 1 < changed.len() && changed[k + 1] <= end + 2 * context + 1 { |
| 118 | k += 1; |
| 119 | end = changed[k]; |
| 120 | } |
| 121 | let end = (end + context + 1).min(ops.len()); |
| 122 | let (a0, b0) = pos[start]; |
| 123 | let a_len = ops[start..end].iter().filter(|(op, _)| *op != Op::Add).count(); |
| 124 | let b_len = ops[start..end].iter().filter(|(op, _)| *op != Op::Del).count(); |
| 125 | out.push_str(&format!("@@ -{},{} +{},{} @@\n", if a_len == 0 { a0 - 1 } else { a0 }, a_len, if b_len == 0 { b0 - 1 } else { b0 }, b_len)); |
| 126 | for (op, line) in &ops[start..end] { |
| 127 | out.push(match op { |
| 128 | Op::Same => ' ', |
| 129 | Op::Del => '-', |
| 130 | Op::Add => '+', |
| 131 | }); |
| 132 | out.push_str(line); |
| 133 | out.push('\n'); |
| 134 | } |
| 135 | k += 1; |
| 136 | } |
| 137 | out |
| 138 | } |
| 139 | |
| 140 | #[cfg(test)] |
| 141 | mod tests { |
| 142 | use super::*; |
| 143 | |
| 144 | fn apply(a: &[&str], ops: &[(Op, &str)]) -> (Vec<String>, Vec<String>) { |
| 145 | let from: Vec<String> = ops.iter().filter(|(o, _)| *o != Op::Add).map(|(_, l)| l.to_string()).collect(); |
| 146 | let to: Vec<String> = ops.iter().filter(|(o, _)| *o != Op::Del).map(|(_, l)| l.to_string()).collect(); |
| 147 | let _ = a; |
| 148 | (from, to) |
| 149 | } |
| 150 | |
| 151 | #[test] |
| 152 | fn edit_scripts_reproduce_both_sides() { |
| 153 | let cases: &[(&str, &str)] = &[ |
| 154 | ("", ""), |
| 155 | ("a\nb\nc\n", "a\nb\nc\n"), |
| 156 | ("", "a\nb\n"), |
| 157 | ("a\nb\n", ""), |
| 158 | ("a\nb\nc\nd\n", "a\nx\nc\nd\ne\n"), |
| 159 | ("a\nb\nc\na\nb\nb\na\n", "c\nb\na\nb\na\nc\n"), |
| 160 | ]; |
| 161 | for (a, b) in cases { |
| 162 | let (al, bl) = (lines(a), lines(b)); |
| 163 | let ops = diff(&al, &bl); |
| 164 | let (from, to) = apply(&al, &ops); |
| 165 | assert_eq!(from, al, "{a:?} -> {b:?}"); |
| 166 | assert_eq!(to, bl, "{a:?} -> {b:?}"); |
| 167 | } |
| 168 | // The classic example has a shortest edit script of length 5. |
| 169 | let (al, bl) = (lines("a\nb\nc\na\nb\nb\na\n"), lines("c\nb\na\nb\na\nc\n")); |
| 170 | assert_eq!(diff(&al, &bl).iter().filter(|(o, _)| *o != Op::Same).count(), 5); |
| 171 | } |
| 172 | |
| 173 | #[test] |
| 174 | fn unified_output() { |
| 175 | let a = "1\n2\n3\n4\n5\n6\n7\n8\n9\n"; |
| 176 | let b = "1\n2\n3\nfour\n5\n6\n7\n8\n9\n"; |
| 177 | assert_eq!(unified(a, b, 1), "@@ -3,3 +3,3 @@\n 3\n-4\n+four\n 5\n"); |
| 178 | assert_eq!(unified(a, a, 3), ""); |
| 179 | assert_eq!(unified("", "new\n", 3), "@@ -0,0 +1,1 @@\n+new\n"); |
| 180 | } |
| 181 | } |