Vakyartha documentation

1//! Word-level comparison for a redline that marks only what changed.
2//!
3//! Text is compared as tokens (a word, one whitespace character, or one
4//! other character), so a change never splits a word. The changes are then
5//! cleaned the way a person reads a redline: an unchanged stretch no longer
6//! than the changes on both sides of it is folded into one change, so a
7//! rewritten sentence reads as one change rather than as confetti.
8
9use std::ops::Range;
10
11/// Old characters `delete` give way to new characters `insert` (char
12/// indices into each text). Either may be empty.
13#[derive(Debug, Clone, PartialEq, Eq)]
14pub(crate) struct Change {
15 pub delete: Range<usize>,
16 pub insert: Range<usize>,
17}
18
19/// Above this many token edits the two texts are compared as one change:
20/// past it a word-by-word redline is noise, and the comparison's memory
21/// grows with the square of the edits.
22const MAX_EDITS: usize = 1_000;
23
24/// The changes that turn `old` into `new`, in order and never touching.
25/// `absorbable(range)` says whether an unchanged stretch of `old` may be
26/// folded into the changes around it; a stretch that must stay where it is
27/// (a field's result, a footnote mark between its words) is never folded.
28pub(crate) fn changes(
29 old: &[char],
30 new: &[char],
31 absorbable: impl Fn(Range<usize>) -> bool,
32) -> Vec<Change> {
33 let old_tokens = tokens(old);
34 let new_tokens = tokens(new);
35 let old_keys: Vec<String> = old_tokens.iter().map(|range| key(old, range)).collect();
36 let new_keys: Vec<String> = new_tokens.iter().map(|range| key(new, range)).collect();
37
38 let mut prefix = 0;
39 while prefix < old_keys.len() && prefix < new_keys.len() && old_keys[prefix] == new_keys[prefix]
40 {
41 prefix += 1;
42 }
43 let mut suffix = 0;
44 while suffix < old_keys.len() - prefix
45 && suffix < new_keys.len() - prefix
46 && old_keys[old_keys.len() - 1 - suffix] == new_keys[new_keys.len() - 1 - suffix]
47 {
48 suffix += 1;
49 }
50 let old_middle = &old_keys[prefix..old_keys.len() - suffix];
51 let new_middle = &new_keys[prefix..new_keys.len() - suffix];
52
53 // Token-index regions: (old tokens, new tokens) that differ.
54 let mut regions: Vec<(Range<usize>, Range<usize>)> = Vec::new();
55 match myers(old_middle, new_middle) {
56 Some(steps) => {
57 let (mut a, mut b) = (prefix, prefix);
58 let mut open: Option<(usize, usize)> = None;
59 for step in steps {
60 match step {
61 Step::Equal => {
62 if let Some((a_start, b_start)) = open.take() {
63 regions.push((a_start..a, b_start..b));
64 }
65 a += 1;
66 b += 1;
67 }
68 Step::Delete => {
69 open.get_or_insert((a, b));
70 a += 1;
71 }
72 Step::Insert => {
73 open.get_or_insert((a, b));
74 b += 1;
75 }
76 }
77 }
78 if let Some((a_start, b_start)) = open {
79 regions.push((a_start..a, b_start..b));
80 }
81 }
82 None => regions.push((
83 prefix..old_keys.len() - suffix,
84 prefix..new_keys.len() - suffix,
85 )),
86 }
87
88 let at = |tokens: &[Range<usize>], len: usize, index: usize| {
89 tokens.get(index).map(|token| token.start).unwrap_or(len)
90 };
91 let mut changes: Vec<Change> = regions
92 .into_iter()
93 .filter(|(a, b)| !a.is_empty() || !b.is_empty())
94 .map(|(a, b)| Change {
95 delete: at(&old_tokens, old.len(), a.start)..at(&old_tokens, old.len(), a.end),
96 insert: at(&new_tokens, new.len(), b.start)..at(&new_tokens, new.len(), b.end),
97 })
98 .collect();
99 fold_short_equalities(&mut changes, absorbable);
100 changes
101}
102
103/// Folds an unchanged stretch between two changes into them when it is no
104/// longer than the larger side of each (the semantic clean-up of Myers'
105/// diff as diff-match-patch does it), until nothing more folds.
106fn fold_short_equalities(changes: &mut Vec<Change>, absorbable: impl Fn(Range<usize>) -> bool) {
107 loop {
108 let mut folded = false;
109 for index in 1..changes.len() {
110 let (before, after) = (&changes[index - 1], &changes[index]);
111 let equal = before.delete.end..after.delete.start;
112 let length = equal.len();
113 if length <= before.delete.len().max(before.insert.len())
114 && length <= after.delete.len().max(after.insert.len())
115 && absorbable(equal)
116 {
117 let merged = Change {
118 delete: before.delete.start..after.delete.end,
119 insert: before.insert.start..after.insert.end,
120 };
121 changes[index - 1] = merged;
122 changes.remove(index);
123 folded = true;
124 break;
125 }
126 }
127 if !folded {
128 return;
129 }
130 }
131}
132
133/// Words (letters and digits, joined across `.`, `,`, apostrophes and
134/// hyphens between them), single whitespace characters, and single other
135/// characters. Scripts written without spaces go a character at a time.
136fn tokens(text: &[char]) -> Vec<Range<usize>> {
137 let mut out = Vec::new();
138 let mut index = 0;
139 while index < text.len() {
140 let start = index;
141 if is_word(text[index]) {
142 index += 1;
143 loop {
144 match text.get(index) {
145 Some(next) if is_word(*next) => index += 1,
146 Some(joiner)
147 if is_joiner(*joiner)
148 && text.get(index + 1).is_some_and(|after| is_word(*after)) =>
149 {
150 index += 2;
151 }
152 _ => break,
153 }
154 }
155 } else {
156 index += 1;
157 }
158 out.push(start..index);
159 }
160 out
161}
162
163fn is_word(character: char) -> bool {
164 (character.is_alphanumeric() || character == '_') && !is_unspaced(character)
165}
166
167/// Scripts written without spaces between words.
168fn is_unspaced(character: char) -> bool {
169 matches!(
170 u32::from(character),
171 0x0E00..=0x0EFF // Thai, Lao
172 | 0x1000..=0x109F // Myanmar
173 | 0x1780..=0x17FF // Khmer
174 | 0x3040..=0x30FF // Hiragana, Katakana
175 | 0x3400..=0x4DBF // CJK extension A
176 | 0x4E00..=0x9FFF // CJK unified ideographs
177 | 0xF900..=0xFAFF // CJK compatibility ideographs
178 | 0x20000..=0x2FA1F // CJK extensions B onwards
179 )
180}
181
182fn is_joiner(character: char) -> bool {
183 matches!(character, '.' | ',' | '\'' | '’' | '-' | '‐' | '‑')
184}
185
186fn key(text: &[char], range: &Range<usize>) -> String {
187 text[range.clone()]
188 .iter()
189 .map(|character| fold(*character))
190 .collect()
191}
192
193/// The character compared in place of `character`. A line break the model
194/// writes compares equal to the space the reader shows for one, and
195/// typographic quotes, no-break spaces and hyphens compare equal to their
196/// plain forms, so retyping a curly apostrophe is not a change. The
197/// document keeps its own character wherever the two compare equal.
198pub(crate) fn fold(character: char) -> char {
199 match character {
200 '\n' | '\r' | '\u{a0}' | '\u{2007}' | '\u{202f}' => ' ',
201 '‘' | '’' | '‚' | '‛' | '′' => '\'',
202 '“' | '”' | '„' | '‟' | '″' => '"',
203 '‐' | '‑' => '-',
204 other => other,
205 }
206}
207
208/// `text` with every character [`fold`]ed.
209pub(crate) fn fold_text(text: &str) -> String {
210 text.chars().map(fold).collect()
211}
212
213#[derive(Debug, Clone, Copy, PartialEq, Eq)]
214enum Step {
215 Equal,
216 Delete,
217 Insert,
218}
219
220/// Myers' O((N+M)D) shortest edit script. `None` when more than
221/// [`MAX_EDITS`] edits are needed.
222fn myers(a: &[String], b: &[String]) -> Option<Vec<Step>> {
223 let (n, m) = (a.len(), b.len());
224 let max = n + m;
225 let offset = max + 1;
226 let mut v = vec![0usize; 2 * max + 3];
227 // `trace[d]` is v on diagonals -d-1..=d+1 as step d found it.
228 let mut trace: Vec<Vec<usize>> = Vec::new();
229 for d in 0..=max.min(MAX_EDITS) {
230 trace.push(v[offset - d - 1..=offset + d + 1].to_vec());
231 for step in 0..=d {
232 let slot = offset - d + 2 * step;
233 let k = slot as isize - offset as isize;
234 let mut x = if step == 0 || (step != d && v[slot - 1] < v[slot + 1]) {
235 v[slot + 1]
236 } else {
237 v[slot - 1] + 1
238 };
239 let mut y = usize::try_from(x as isize - k).ok()?;
240 while x < n && y < m && a[x] == b[y] {
241 x += 1;
242 y += 1;
243 }
244 v[slot] = x;
245 if x >= n && y >= m {
246 return backtrack(&trace, n, m, d);
247 }
248 }
249 }
250 None
251}
252
253fn backtrack(trace: &[Vec<usize>], n: usize, m: usize, last: usize) -> Option<Vec<Step>> {
254 let mut steps = Vec::new();
255 let (mut x, mut y) = (n as isize, m as isize);
256 for d in (0..=last).rev() {
257 let window = trace.get(d)?;
258 let d = d as isize;
259 let at = |k: isize| -> Option<isize> {
260 window
261 .get(usize::try_from(k + d + 1).ok()?)
262 .map(|value| *value as isize)
263 };
264 let k = x - y;
265 let previous_k = if k == -d || (k != d && at(k - 1)? < at(k + 1)?) {
266 k + 1
267 } else {
268 k - 1
269 };
270 let previous_x = at(previous_k)?;
271 let previous_y = previous_x - previous_k;
272 while x > previous_x && y > previous_y {
273 steps.push(Step::Equal);
274 x -= 1;
275 y -= 1;
276 }
277 if d > 0 {
278 steps.push(if x == previous_x {
279 Step::Insert
280 } else {
281 Step::Delete
282 });
283 }
284 x = previous_x;
285 y = previous_y;
286 }
287 steps.reverse();
288 Some(steps)
289}
290
291#[cfg(test)]
292#[allow(clippy::unwrap_used, clippy::expect_used)]
293mod tests {
294 use super::*;
295
296 fn chars(text: &str) -> Vec<char> {
297 text.chars().collect()
298 }
299
300 /// The changes as (deleted, inserted) strings.
301 fn diff(old: &str, new: &str) -> Vec<(String, String)> {
302 let (old, new) = (chars(old), chars(new));
303 changes(&old, &new, |_| true)
304 .into_iter()
305 .map(|change| {
306 (
307 old[change.delete].iter().collect(),
308 new[change.insert].iter().collect(),
309 )
310 })
311 .collect()
312 }
313
314 #[test]
315 fn a_changed_word_is_the_only_change() {
316 assert_eq!(
317 diff(
318 "continues for twelve months, see the schedule.",
319 "continues for twenty-four months, see the schedule."
320 ),
321 vec![("twelve".to_string(), "twenty-four".to_string())]
322 );
323 }
324
325 #[test]
326 fn words_are_never_split() {
327 assert_eq!(
328 diff("for twelve months", "for twenty months"),
329 vec![("twelve".to_string(), "twenty".to_string())]
330 );
331 assert_eq!(
332 diff("Fees of 1,250.00 apply", "Fees of 1,300.00 apply"),
333 vec![("1,250.00".to_string(), "1,300.00".to_string())]
334 );
335 // Neighbouring changed words read as one change.
336 assert_eq!(
337 diff("the schedule applies", "the schedules apply"),
338 vec![(
339 "schedule applies".to_string(),
340 "schedules apply".to_string()
341 )]
342 );
343 }
344
345 #[test]
346 fn a_short_unchanged_stretch_between_changes_is_folded_in() {
347 assert_eq!(
348 diff("the Effective Date applies", "the Commencement Day applies"),
349 vec![("Effective Date".to_string(), "Commencement Day".to_string())]
350 );
351 // A long unchanged stretch keeps the changes apart.
352 assert_eq!(
353 diff(
354 "Alpha says the quarterly figures are final. Beta",
355 "Gamma says the quarterly figures are final. Delta"
356 ),
357 vec![
358 ("Alpha".to_string(), "Gamma".to_string()),
359 ("Beta".to_string(), "Delta".to_string())
360 ]
361 );
362 }
363
364 #[test]
365 fn a_stretch_that_must_stay_is_never_folded() {
366 let (old, new) = (
367 chars("the Effective Date applies"),
368 chars("the Commencement Day applies"),
369 );
370 let changes = changes(&old, &new, |_| false);
371 assert_eq!(changes.len(), 2);
372 }
373
374 #[test]
375 fn insertions_and_deletions_alone() {
376 assert_eq!(
377 diff("payable within 30 days", "payable within 30 business days"),
378 vec![(String::new(), "business ".to_string())]
379 );
380 assert_eq!(
381 diff("payable within 30 business days", "payable within 30 days"),
382 vec![("business ".to_string(), String::new())]
383 );
384 assert_eq!(
385 diff("", "New text"),
386 vec![(String::new(), "New text".to_string())]
387 );
388 assert_eq!(
389 diff("Old text", ""),
390 vec![("Old text".to_string(), String::new())]
391 );
392 assert!(diff("Same", "Same").is_empty());
393 assert!(diff("", "").is_empty());
394 }
395
396 #[test]
397 fn typographic_forms_compare_equal() {
398 assert!(diff("the Supplier’s “rights”", "the Supplier's \"rights\"").is_empty());
399 assert!(diff("Section\u{a0}4.2", "Section 4.2").is_empty());
400 assert!(diff("one two", "one\ntwo").is_empty());
401 }
402
403 #[test]
404 fn unspaced_scripts_compare_a_character_at_a_time() {
405 assert_eq!(
406 diff("本契約は東京で締結", "本契約は大阪で締結"),
407 vec![("東京".to_string(), "大阪".to_string())]
408 );
409 }
410
411 #[test]
412 fn a_rewrite_reads_as_one_change() {
413 let changes = diff(
414 "The supplier shall deliver the goods within ten days of the order.",
415 "Delivery is due no later than two weeks after each purchase order is placed.",
416 );
417 assert_eq!(changes.len(), 1, "{changes:?}");
418 }
419
420 #[test]
421 fn beyond_the_edit_bound_the_texts_are_one_change() {
422 let old: String = (0..1_500).map(|index| format!("a{index} ")).collect();
423 let new: String = (0..1_500).map(|index| format!("b{index} ")).collect();
424 let changes = diff(&old, &new);
425 assert_eq!(changes.len(), 1);
426 }
427
428 #[test]
429 fn edits_far_apart_in_a_long_text_stay_small() {
430 let body: String = (0..2_000).map(|index| format!("w{index} ")).collect();
431 let old = format!("First {body}last");
432 let new = format!("Initial {body}final");
433 assert_eq!(
434 diff(&old, &new),
435 vec![
436 ("First".to_string(), "Initial".to_string()),
437 ("last".to_string(), "final".to_string())
438 ]
439 );
440 }
441}
442

1//! Word-level comparison for a redline that marks only what changed.
2//!
3//! Text is compared as tokens (a word, one whitespace character, or one
4//! other character), so a change never splits a word. The changes are then
5//! cleaned the way a person reads a redline: an unchanged stretch no longer
6//! than the changes on both sides of it is folded into one change, so a
7//! rewritten sentence reads as one change rather than as confetti.
8
9use std::ops::Range;
10
11/// Old characters `delete` give way to new characters `insert` (char
12/// indices into each text). Either may be empty.
13#[derive(Debug, Clone, PartialEq, Eq)]
14pub(crate) struct Change {
15 pub delete: Range<usize>,
16 pub insert: Range<usize>,
17}
18
19/// Above this many token edits the two texts are compared as one change:
20/// past it a word-by-word redline is noise, and the comparison's memory
21/// grows with the square of the edits.
22const MAX_EDITS: usize = 1_000;
23
24/// The changes that turn `old` into `new`, in order and never touching.
25/// `absorbable(range)` says whether an unchanged stretch of `old` may be
26/// folded into the changes around it; a stretch that must stay where it is
27/// (a field's result, a footnote mark between its words) is never folded.
28pub(crate) fn changes(
29 old: &[char],
30 new: &[char],
31 absorbable: impl Fn(Range<usize>) -> bool,
32) -> Vec<Change> {
33 let old_tokens = tokens(old);
34 let new_tokens = tokens(new);
35 let old_keys: Vec<String> = old_tokens.iter().map(|range| key(old, range)).collect();
36 let new_keys: Vec<String> = new_tokens.iter().map(|range| key(new, range)).collect();
37
38 let mut prefix = 0;
39 while prefix < old_keys.len() && prefix < new_keys.len() && old_keys[prefix] == new_keys[prefix]
40 {
41 prefix += 1;
42 }
43 let mut suffix = 0;
44 while suffix < old_keys.len() - prefix
45 && suffix < new_keys.len() - prefix
46 && old_keys[old_keys.len() - 1 - suffix] == new_keys[new_keys.len() - 1 - suffix]
47 {
48 suffix += 1;
49 }
50 let old_middle = &old_keys[prefix..old_keys.len() - suffix];
51 let new_middle = &new_keys[prefix..new_keys.len() - suffix];
52
53 // Token-index regions: (old tokens, new tokens) that differ.
54 let mut regions: Vec<(Range<usize>, Range<usize>)> = Vec::new();
55 match myers(old_middle, new_middle) {
56 Some(steps) => {
57 let (mut a, mut b) = (prefix, prefix);
58 let mut open: Option<(usize, usize)> = None;
59 for step in steps {
60 match step {
61 Step::Equal => {
62 if let Some((a_start, b_start)) = open.take() {
63 regions.push((a_start..a, b_start..b));
64 }
65 a += 1;
66 b += 1;
67 }
68 Step::Delete => {
69 open.get_or_insert((a, b));
70 a += 1;
71 }
72 Step::Insert => {
73 open.get_or_insert((a, b));
74 b += 1;
75 }
76 }
77 }
78 if let Some((a_start, b_start)) = open {
79 regions.push((a_start..a, b_start..b));
80 }
81 }
82 None => regions.push((
83 prefix..old_keys.len() - suffix,
84 prefix..new_keys.len() - suffix,
85 )),
86 }
87
88 let at = |tokens: &[Range<usize>], len: usize, index: usize| {
89 tokens.get(index).map(|token| token.start).unwrap_or(len)
90 };
91 let mut changes: Vec<Change> = regions
92 .into_iter()
93 .filter(|(a, b)| !a.is_empty() || !b.is_empty())
94 .map(|(a, b)| Change {
95 delete: at(&old_tokens, old.len(), a.start)..at(&old_tokens, old.len(), a.end),
96 insert: at(&new_tokens, new.len(), b.start)..at(&new_tokens, new.len(), b.end),
97 })
98 .collect();
99 fold_short_equalities(&mut changes, absorbable);
100 changes
101}
102
103/// Folds an unchanged stretch between two changes into them when it is no
104/// longer than the larger side of each (the semantic clean-up of Myers'
105/// diff as diff-match-patch does it), until nothing more folds.
106fn fold_short_equalities(changes: &mut Vec<Change>, absorbable: impl Fn(Range<usize>) -> bool) {
107 loop {
108 let mut folded = false;
109 for index in 1..changes.len() {
110 let (before, after) = (&changes[index - 1], &changes[index]);
111 let equal = before.delete.end..after.delete.start;
112 let length = equal.len();
113 if length <= before.delete.len().max(before.insert.len())
114 && length <= after.delete.len().max(after.insert.len())
115 && absorbable(equal)
116 {
117 let merged = Change {
118 delete: before.delete.start..after.delete.end,
119 insert: before.insert.start..after.insert.end,
120 };
121 changes[index - 1] = merged;
122 changes.remove(index);
123 folded = true;
124 break;
125 }
126 }
127 if !folded {
128 return;
129 }
130 }
131}
132
133/// Words (letters and digits, joined across `.`, `,`, apostrophes and
134/// hyphens between them), single whitespace characters, and single other
135/// characters. Scripts written without spaces go a character at a time.
136fn tokens(text: &[char]) -> Vec<Range<usize>> {
137 let mut out = Vec::new();
138 let mut index = 0;
139 while index < text.len() {
140 let start = index;
141 if is_word(text[index]) {
142 index += 1;
143 loop {
144 match text.get(index) {
145 Some(next) if is_word(*next) => index += 1,
146 Some(joiner)
147 if is_joiner(*joiner)
148 && text.get(index + 1).is_some_and(|after| is_word(*after)) =>
149 {
150 index += 2;
151 }
152 _ => break,
153 }
154 }
155 } else {
156 index += 1;
157 }
158 out.push(start..index);
159 }
160 out
161}
162
163fn is_word(character: char) -> bool {
164 (character.is_alphanumeric() || character == '_') && !is_unspaced(character)
165}
166
167/// Scripts written without spaces between words.
168fn is_unspaced(character: char) -> bool {
169 matches!(
170 u32::from(character),
171 0x0E00..=0x0EFF // Thai, Lao
172 | 0x1000..=0x109F // Myanmar
173 | 0x1780..=0x17FF // Khmer
174 | 0x3040..=0x30FF // Hiragana, Katakana
175 | 0x3400..=0x4DBF // CJK extension A
176 | 0x4E00..=0x9FFF // CJK unified ideographs
177 | 0xF900..=0xFAFF // CJK compatibility ideographs
178 | 0x20000..=0x2FA1F // CJK extensions B onwards
179 )
180}
181
182fn is_joiner(character: char) -> bool {
183 matches!(character, '.' | ',' | '\'' | '’' | '-' | '‐' | '‑')
184}
185
186fn key(text: &[char], range: &Range<usize>) -> String {
187 text[range.clone()]
188 .iter()
189 .map(|character| fold(*character))
190 .collect()
191}
192
193/// The character compared in place of `character`. A line break the model
194/// writes compares equal to the space the reader shows for one, and
195/// typographic quotes, no-break spaces and hyphens compare equal to their
196/// plain forms, so retyping a curly apostrophe is not a change. The
197/// document keeps its own character wherever the two compare equal.
198pub(crate) fn fold(character: char) -> char {
199 match character {
200 '\n' | '\r' | '\u{a0}' | '\u{2007}' | '\u{202f}' => ' ',
201 '‘' | '’' | '‚' | '‛' | '′' => '\'',
202 '“' | '”' | '„' | '‟' | '″' => '"',
203 '‐' | '‑' => '-',
204 other => other,
205 }
206}
207
208/// `text` with every character [`fold`]ed.
209pub(crate) fn fold_text(text: &str) -> String {
210 text.chars().map(fold).collect()
211}
212
213#[derive(Debug, Clone, Copy, PartialEq, Eq)]
214enum Step {
215 Equal,
216 Delete,
217 Insert,
218}
219
220/// Myers' O((N+M)D) shortest edit script. `None` when more than
221/// [`MAX_EDITS`] edits are needed.
222fn myers(a: &[String], b: &[String]) -> Option<Vec<Step>> {
223 let (n, m) = (a.len(), b.len());
224 let max = n + m;
225 let offset = max + 1;
226 let mut v = vec![0usize; 2 * max + 3];
227 // `trace[d]` is v on diagonals -d-1..=d+1 as step d found it.
228 let mut trace: Vec<Vec<usize>> = Vec::new();
229 for d in 0..=max.min(MAX_EDITS) {
230 trace.push(v[offset - d - 1..=offset + d + 1].to_vec());
231 for step in 0..=d {
232 let slot = offset - d + 2 * step;
233 let k = slot as isize - offset as isize;
234 let mut x = if step == 0 || (step != d && v[slot - 1] < v[slot + 1]) {
235 v[slot + 1]
236 } else {
237 v[slot - 1] + 1
238 };
239 let mut y = usize::try_from(x as isize - k).ok()?;
240 while x < n && y < m && a[x] == b[y] {
241 x += 1;
242 y += 1;
243 }
244 v[slot] = x;
245 if x >= n && y >= m {
246 return backtrack(&trace, n, m, d);
247 }
248 }
249 }
250 None
251}
252
253fn backtrack(trace: &[Vec<usize>], n: usize, m: usize, last: usize) -> Option<Vec<Step>> {
254 let mut steps = Vec::new();
255 let (mut x, mut y) = (n as isize, m as isize);
256 for d in (0..=last).rev() {
257 let window = trace.get(d)?;
258 let d = d as isize;
259 let at = |k: isize| -> Option<isize> {
260 window
261 .get(usize::try_from(k + d + 1).ok()?)
262 .map(|value| *value as isize)
263 };
264 let k = x - y;
265 let previous_k = if k == -d || (k != d && at(k - 1)? < at(k + 1)?) {
266 k + 1
267 } else {
268 k - 1
269 };
270 let previous_x = at(previous_k)?;
271 let previous_y = previous_x - previous_k;
272 while x > previous_x && y > previous_y {
273 steps.push(Step::Equal);
274 x -= 1;
275 y -= 1;
276 }
277 if d > 0 {
278 steps.push(if x == previous_x {
279 Step::Insert
280 } else {
281 Step::Delete
282 });
283 }
284 x = previous_x;
285 y = previous_y;
286 }
287 steps.reverse();
288 Some(steps)
289}
290
291#[cfg(test)]
292#[allow(clippy::unwrap_used, clippy::expect_used)]
293mod tests {
294 use super::*;
295
296 fn chars(text: &str) -> Vec<char> {
297 text.chars().collect()
298 }
299
300 /// The changes as (deleted, inserted) strings.
301 fn diff(old: &str, new: &str) -> Vec<(String, String)> {
302 let (old, new) = (chars(old), chars(new));
303 changes(&old, &new, |_| true)
304 .into_iter()
305 .map(|change| {
306 (
307 old[change.delete].iter().collect(),
308 new[change.insert].iter().collect(),
309 )
310 })
311 .collect()
312 }
313
314 #[test]
315 fn a_changed_word_is_the_only_change() {
316 assert_eq!(
317 diff(
318 "continues for twelve months, see the schedule.",
319 "continues for twenty-four months, see the schedule."
320 ),
321 vec![("twelve".to_string(), "twenty-four".to_string())]
322 );
323 }
324
325 #[test]
326 fn words_are_never_split() {
327 assert_eq!(
328 diff("for twelve months", "for twenty months"),
329 vec![("twelve".to_string(), "twenty".to_string())]
330 );
331 assert_eq!(
332 diff("Fees of 1,250.00 apply", "Fees of 1,300.00 apply"),
333 vec![("1,250.00".to_string(), "1,300.00".to_string())]
334 );
335 // Neighbouring changed words read as one change.
336 assert_eq!(
337 diff("the schedule applies", "the schedules apply"),
338 vec![(
339 "schedule applies".to_string(),
340 "schedules apply".to_string()
341 )]
342 );
343 }
344
345 #[test]
346 fn a_short_unchanged_stretch_between_changes_is_folded_in() {
347 assert_eq!(
348 diff("the Effective Date applies", "the Commencement Day applies"),
349 vec![("Effective Date".to_string(), "Commencement Day".to_string())]
350 );
351 // A long unchanged stretch keeps the changes apart.
352 assert_eq!(
353 diff(
354 "Alpha says the quarterly figures are final. Beta",
355 "Gamma says the quarterly figures are final. Delta"
356 ),
357 vec![
358 ("Alpha".to_string(), "Gamma".to_string()),
359 ("Beta".to_string(), "Delta".to_string())
360 ]
361 );
362 }
363
364 #[test]
365 fn a_stretch_that_must_stay_is_never_folded() {
366 let (old, new) = (
367 chars("the Effective Date applies"),
368 chars("the Commencement Day applies"),
369 );
370 let changes = changes(&old, &new, |_| false);
371 assert_eq!(changes.len(), 2);
372 }
373
374 #[test]
375 fn insertions_and_deletions_alone() {
376 assert_eq!(
377 diff("payable within 30 days", "payable within 30 business days"),
378 vec![(String::new(), "business ".to_string())]
379 );
380 assert_eq!(
381 diff("payable within 30 business days", "payable within 30 days"),
382 vec![("business ".to_string(), String::new())]
383 );
384 assert_eq!(
385 diff("", "New text"),
386 vec![(String::new(), "New text".to_string())]
387 );
388 assert_eq!(
389 diff("Old text", ""),
390 vec![("Old text".to_string(), String::new())]
391 );
392 assert!(diff("Same", "Same").is_empty());
393 assert!(diff("", "").is_empty());
394 }
395
396 #[test]
397 fn typographic_forms_compare_equal() {
398 assert!(diff("the Supplier’s “rights”", "the Supplier's \"rights\"").is_empty());
399 assert!(diff("Section\u{a0}4.2", "Section 4.2").is_empty());
400 assert!(diff("one two", "one\ntwo").is_empty());
401 }
402
403 #[test]
404 fn unspaced_scripts_compare_a_character_at_a_time() {
405 assert_eq!(
406 diff("本契約は東京で締結", "本契約は大阪で締結"),
407 vec![("東京".to_string(), "大阪".to_string())]
408 );
409 }
410
411 #[test]
412 fn a_rewrite_reads_as_one_change() {
413 let changes = diff(
414 "The supplier shall deliver the goods within ten days of the order.",
415 "Delivery is due no later than two weeks after each purchase order is placed.",
416 );
417 assert_eq!(changes.len(), 1, "{changes:?}");
418 }
419
420 #[test]
421 fn beyond_the_edit_bound_the_texts_are_one_change() {
422 let old: String = (0..1_500).map(|index| format!("a{index} ")).collect();
423 let new: String = (0..1_500).map(|index| format!("b{index} ")).collect();
424 let changes = diff(&old, &new);
425 assert_eq!(changes.len(), 1);
426 }
427
428 #[test]
429 fn edits_far_apart_in_a_long_text_stay_small() {
430 let body: String = (0..2_000).map(|index| format!("w{index} ")).collect();
431 let old = format!("First {body}last");
432 let new = format!("Initial {body}final");
433 assert_eq!(
434 diff(&old, &new),
435 vec![
436 ("First".to_string(), "Initial".to_string()),
437 ("last".to_string(), "final".to_string())
438 ]
439 );
440 }
441}
442

Textdiff

Indexing the workspace…

Textdiff