oxedyne/fe2o3/fe2o3_data/src/diff.rs
5.9 KiB, 2 runs
created by r1870400018:70653, which is this file's identity for as long as the history lasts, whatever it is later renamed to
download · who wrote it · its history
| 1 | //! Myers' shortest edit script over any two slices of comparable elements. |
| 2 | //! |
| 3 | //! Moved here from `fe2o3_ore::diff`, which runs it over line and byte pieces, |
| 4 | //! so that any caller wanting a structural diff (a page history, a list of |
| 5 | //! sections) shares the one implementation. |
| 6 | //! |
| 7 | //! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\ |
| 8 | //! Anthropic Claude |
| 9 | |
| 10 | use std::ops::Range; |
| 11 | |
| 12 | |
| 13 | /// A run of `a` that has become a run of `b`. At least one of the two is |
| 14 | /// non-empty. |
| 15 | #[derive(Clone, Debug, Eq, PartialEq)] |
| 16 | pub struct Change { |
| 17 | pub a: Range<usize>, // what the run was, in the old sequence |
| 18 | pub b: Range<usize>, // what it has become, in the new sequence |
| 19 | } |
| 20 | |
| 21 | |
| 22 | /// Returns the changed runs turning `a` into `b`, or `None` where the edit |
| 23 | /// script would exceed `budget`. |
| 24 | /// |
| 25 | /// The shared head and tail are taken off first, since neither costs anything |
| 26 | /// to find and both shrink what Myers is asked to do. |
| 27 | pub fn changed_runs<T: PartialEq>(a: &[T], b: &[T], budget: usize) |
| 28 | -> Option<Vec<Change>> |
| 29 | { |
| 30 | let limit = a.len().min(b.len()); |
| 31 | let mut head = 0; |
| 32 | while head < limit && a[head] == b[head] { |
| 33 | head += 1; |
| 34 | } |
| 35 | let mut tail = 0; |
| 36 | while tail < limit - head |
| 37 | && a[a.len() - 1 - tail] == b[b.len() - 1 - tail] |
| 38 | { |
| 39 | tail += 1; |
| 40 | } |
| 41 | let (an, bn) = (a.len() - tail, b.len() - tail); |
| 42 | if head == an && head == bn { |
| 43 | return Some(Vec::new()); |
| 44 | } |
| 45 | // Where one side has nothing left, every remaining element of the other is |
| 46 | // the whole of the change and Myers has nothing to decide. |
| 47 | if head == an || head == bn { |
| 48 | return Some(vec![Change { a: head..an, b: head..bn }]); |
| 49 | } |
| 50 | let matched = match matches(&a[head..an], &b[head..bn], budget) { |
| 51 | Some(m) => m, |
| 52 | None => return None, |
| 53 | }; |
| 54 | Some(runs_between(&matched, an - head, bn - head, head)) |
| 55 | } |
| 56 | |
| 57 | fn runs_between(matched: &[(usize, usize)], n: usize, m: usize, off: usize) |
| 58 | -> Vec<Change> |
| 59 | { |
| 60 | let mut out: Vec<Change> = Vec::new(); |
| 61 | let (mut i, mut j) = (0usize, 0usize); |
| 62 | for (mi, mj) in matched { |
| 63 | if *mi > i || *mj > j { |
| 64 | out.push(Change { |
| 65 | a: off + i..off + mi, |
| 66 | b: off + j..off + mj, |
| 67 | }); |
| 68 | } |
| 69 | i = mi + 1; |
| 70 | j = mj + 1; |
| 71 | } |
| 72 | if i < n || j < m { |
| 73 | out.push(Change { |
| 74 | a: off + i..off + n, |
| 75 | b: off + j..off + m, |
| 76 | }); |
| 77 | } |
| 78 | out |
| 79 | } |
| 80 | |
| 81 | /// Returns the pairs of positions a shortest edit script leaves matched, |
| 82 | /// ascending, or `None` where that script would be longer than `budget`. |
| 83 | /// |
| 84 | /// This is Myers' greedy algorithm: for each script length `d` in turn, the |
| 85 | /// furthest point reachable on each diagonal is extended along whatever run of |
| 86 | /// equal elements follows it, and the first `d` that reaches the far corner is |
| 87 | /// the length of a shortest script. Keeping the furthest points of every `d` |
| 88 | /// makes the path itself recoverable by walking back through them, which is |
| 89 | /// where the matched pairs come from, and is also what costs O(D²) memory and |
| 90 | /// so what the budget is bounding. |
| 91 | pub fn matches<T: PartialEq>(a: &[T], b: &[T], budget: usize) |
| 92 | -> Option<Vec<(usize, usize)>> |
| 93 | { |
| 94 | let (n, m) = (a.len() as isize, b.len() as isize); |
| 95 | let max = (a.len() + b.len()) as isize; |
| 96 | let cap = budget.min(a.len() + b.len()); |
| 97 | // Furthest x reached on each diagonal k, shifted so that k = 0 sits at max. |
| 98 | // The step at d = 0 reads diagonal k = 1, so one slot beyond 2 * max is |
| 99 | // needed for two empty sides, where max is zero. |
| 100 | let mut v: Vec<isize> = vec![0; (2 * max + 2) as usize]; |
| 101 | let mut trace: Vec<Vec<isize>> = Vec::with_capacity(cap + 1); |
| 102 | for d in 0..=cap { |
| 103 | let dd = d as isize; |
| 104 | // The state before this step, which is what the walk back reads. |
| 105 | trace.push(v[(max - dd) as usize..=(max + dd) as usize].to_vec()); |
| 106 | let mut k = -dd; |
| 107 | while k <= dd { |
| 108 | let mut x = if k == -dd |
| 109 | || (k != dd && v[(max + k - 1) as usize] < v[(max + k + 1) as usize]) |
| 110 | { |
| 111 | v[(max + k + 1) as usize] |
| 112 | } else { |
| 113 | v[(max + k - 1) as usize] + 1 |
| 114 | }; |
| 115 | let mut y = x - k; |
| 116 | while x < n && y < m && a[x as usize] == b[y as usize] { |
| 117 | x += 1; |
| 118 | y += 1; |
| 119 | } |
| 120 | v[(max + k) as usize] = x; |
| 121 | if x >= n && y >= m { |
| 122 | return Some(walk_back(&trace, n, m, d)); |
| 123 | } |
| 124 | k += 2; |
| 125 | } |
| 126 | } |
| 127 | None |
| 128 | } |
| 129 | |
| 130 | /// Walks the furthest points back from the far corner, collecting the pairs |
| 131 | /// matched on the way. |
| 132 | fn walk_back(trace: &[Vec<isize>], n: isize, m: isize, found: usize) |
| 133 | -> Vec<(usize, usize)> |
| 134 | { |
| 135 | let mut matched: Vec<(usize, usize)> = Vec::new(); |
| 136 | let (mut x, mut y) = (n, m); |
| 137 | for d in (0..=found).rev() { |
| 138 | let (prev_x, prev_y) = if d == 0 { |
| 139 | (0, 0) |
| 140 | } else { |
| 141 | let dd = d as isize; |
| 142 | let w = &trace[d]; |
| 143 | let at = |k: isize| w[(k + dd) as usize]; |
| 144 | let k = x - y; |
| 145 | let prev_k = if k == -dd || (k != dd && at(k - 1) < at(k + 1)) { |
| 146 | k + 1 |
| 147 | } else { |
| 148 | k - 1 |
| 149 | }; |
| 150 | let px = at(prev_k); |
| 151 | (px, px - prev_k) |
| 152 | }; |
| 153 | while x > prev_x && y > prev_y { |
| 154 | x -= 1; |
| 155 | y -= 1; |
| 156 | matched.push((x as usize, y as usize)); |
| 157 | } |
| 158 | x = prev_x; |
| 159 | y = prev_y; |
| 160 | } |
| 161 | matched.reverse(); |
| 162 | matched |
| 163 | } |
| 164 | |
| 165 | |
| 166 | /// A stretch shown together: changed runs with the equal elements around them. |
| 167 | #[derive(Clone, Debug, Eq, PartialEq)] |
| 168 | pub struct Hunk { |
| 169 | pub a: Range<usize>, // its span in the old sequence, context included |
| 170 | pub b: Range<usize>, // and in the new |
| 171 | pub runs: Vec<Change>, // the changed runs within it, ascending |
| 172 | } |
| 173 | |
| 174 | /// Groups `runs`, ascending as [`changed_runs`] gives them, of an old sequence |
| 175 | /// `n` long and a new one `m` long into hunks, each run with up to `context` |
| 176 | /// equal elements on either side, so that two runs closer than twice that |
| 177 | /// share one hunk. |
| 178 | pub fn hunks(runs: &[Change], n: usize, m: usize, context: usize) -> Vec<Hunk> { |
| 179 | let mut out: Vec<Hunk> = Vec::new(); |
| 180 | for r in runs { |
| 181 | // The equal stretches before and after a run are as long in both sequences. |
| 182 | let (a0, b0) = (r.a.start.saturating_sub(context), r.b.start.saturating_sub(context)); |
| 183 | let (a1, b1) = ((r.a.end + context).min(n), (r.b.end + context).min(m)); |
| 184 | match out.last_mut() { |
| 185 | Some(h) if a0 <= h.a.end => { |
| 186 | (h.a.end, h.b.end) = (a1, b1); |
| 187 | h.runs.push(r.clone()); |
| 188 | }, |
| 189 | _ => out.push(Hunk { a: a0..a1, b: b0..b1, runs: vec![r.clone()] }), |
| 190 | } |
| 191 | } |
| 192 | out |
| 193 | } |