ashlar_diff/
words.rs

1//! Word-level changes between a removed line and the added line it pairs with.
2
3use std::ops::Range;
4
5use crate::myers::{Op, diff_ops};
6
7/// Lines longer than this (bytes) get no word-level emphasis.
8pub const MAX_WORD_DIFF_LINE: usize = 4096;
9
10/// Cost cap for one word diff.
11const WORD_COST: usize = 256;
12
13/// Splits a line into words (letters, digits, `_`), runs of whitespace, and single other chars.
14fn tokens(s: &str) -> Vec<Range<usize>> {
15    #[derive(PartialEq, Clone, Copy)]
16    enum Class {
17        Word,
18        Space,
19        Other,
20    }
21    let class = |c: char| {
22        if c.is_alphanumeric() || c == '_' {
23            Class::Word
24        } else if c.is_whitespace() {
25            Class::Space
26        } else {
27            Class::Other
28        }
29    };
30    let mut out: Vec<Range<usize>> = Vec::new();
31    let mut last: Option<Class> = None;
32    for (i, c) in s.char_indices() {
33        let cl = class(c);
34        let end = i + c.len_utf8();
35        match out.last_mut() {
36            Some(r) if last == Some(cl) && cl != Class::Other => r.end = end,
37            _ => out.push(i..end),
38        }
39        last = Some(cl);
40    }
41    out
42}
43
44/// The byte ranges that changed between `old` and `new`, word by word: `(in old, in new)`.
45/// Adjacent changed tokens merge into one range. `None` when either line is too long, the
46/// lines are equal, or they share no word (emphasis would then cover everything and say
47/// nothing).
48///
49/// ```
50/// let (old, new) = ashlar_diff::word_diff("let x = 1;", "let y = 1;").unwrap();
51/// assert_eq!(old, vec![4..5]);
52/// assert_eq!(new, vec![4..5]);
53/// ```
54pub fn word_diff(old: &str, new: &str) -> Option<(Vec<Range<usize>>, Vec<Range<usize>>)> {
55    if old.len() > MAX_WORD_DIFF_LINE || new.len() > MAX_WORD_DIFF_LINE || old == new {
56        return None;
57    }
58    let (ta, tb) = (tokens(old), tokens(new));
59    let wa: Vec<&str> = ta.iter().map(|r| old.get(r.clone()).unwrap_or("")).collect();
60    let wb: Vec<&str> = tb.iter().map(|r| new.get(r.clone()).unwrap_or("")).collect();
61    let edit = diff_ops(&wa, &wb, WORD_COST);
62    let shares_word = edit.ops.iter().any(|op| match op {
63        Op::Equal { old: o, len, .. } => wa.iter().skip(*o).take(*len).any(|w| !w.trim().is_empty()),
64        _ => false,
65    });
66    if edit.coarse || !shares_word {
67        return None;
68    }
69    let mut ra = Vec::new();
70    let mut rb = Vec::new();
71    let span = |toks: &[Range<usize>], at: usize, len: usize| -> Option<Range<usize>> {
72        let first = toks.get(at)?;
73        let last = toks.get(at + len.checked_sub(1)?)?;
74        Some(first.start..last.end)
75    };
76    for op in &edit.ops {
77        match *op {
78            Op::Equal { .. } => {}
79            Op::Delete { old: o, len } => ra.extend(span(&ta, o, len)),
80            Op::Insert { new: n, len } => rb.extend(span(&tb, n, len)),
81        }
82    }
83    Some((merge(ra), merge(rb)))
84}
85
86fn merge(mut v: Vec<Range<usize>>) -> Vec<Range<usize>> {
87    v.sort_by_key(|r| r.start);
88    let mut out: Vec<Range<usize>> = Vec::with_capacity(v.len());
89    for r in v {
90        match out.last_mut() {
91            Some(l) if r.start <= l.end => l.end = l.end.max(r.end),
92            _ => out.push(r),
93        }
94    }
95    out
96}
97
98#[cfg(test)]
99mod tests {
100    use super::*;
101
102    #[test]
103    fn tokens_split_words_spaces_and_punctuation() {
104        let s = "foo_bar(x,  y)";
105        let words: Vec<&str> = tokens(s).into_iter().map(|r| &s[r]).collect();
106        assert_eq!(words, ["foo_bar", "(", "x", ",", "  ", "y", ")"]);
107    }
108
109    #[test]
110    fn emphasis_marks_changed_words() {
111        let (a, b) = word_diff("fn add(a: i32) -> i32", "fn add(a: i64) -> i64").unwrap();
112        assert_eq!(a, vec![10..13, 18..21]);
113        assert_eq!(b, vec![10..13, 18..21]);
114        assert!(word_diff("abc", "xyz").is_none());
115        assert!(word_diff("same", "same").is_none());
116        let (a, b) = word_diff("é x", "é y").unwrap();
117        assert_eq!((a.first().cloned(), b.first().cloned()), (Some(3..4), Some(3..4)));
118    }
119}
ashlar_diff/words.rs

ashlar_diff/
words.rs
