Oregami
Repositories/oxedyne/fe2o3

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
10use 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)]
16pub 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.
27pub 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
57fn 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.
91pub 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.
132fn 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)]
168pub 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.
178pub 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}