1use crate::{CharClassifier, CharKind, LanguageScope};
2use imara_diff::{
3 diff,
4 intern::{InternedInput, Token},
5 sources::lines_with_terminator,
6 Algorithm, UnifiedDiffBuilder,
7};
8use std::{iter, ops::Range, sync::Arc};
9
10const MAX_WORD_DIFF_LEN: usize = 512;
11const MAX_WORD_DIFF_LINE_COUNT: usize = 8;
12
13/// Computes a diff between two strings, returning a unified diff string.
14pub fn unified_diff(old_text: &str, new_text: &str) -> String {
15 let input = InternedInput::new(old_text, new_text);
16 diff(
17 Algorithm::Histogram,
18 &input,
19 UnifiedDiffBuilder::new(&input),
20 )
21}
22
23/// Computes a diff between two strings, returning a vector of old and new row
24/// ranges.
25pub fn line_diff(old_text: &str, new_text: &str) -> Vec<(Range<u32>, Range<u32>)> {
26 let mut edits = Vec::new();
27 let input = InternedInput::new(
28 lines_with_terminator(old_text),
29 lines_with_terminator(new_text),
30 );
31 diff_internal(&input, |_, _, old_rows, new_rows| {
32 edits.push((old_rows, new_rows));
33 });
34 edits
35}
36
37/// Computes a diff between two strings, returning a vector of edits.
38///
39/// The edits are represented as tuples of byte ranges and replacement strings.
40///
41/// Internally, this function first performs a line-based diff, and then performs a second
42/// word-based diff within hunks that replace small numbers of lines.
43pub fn text_diff(old_text: &str, new_text: &str) -> Vec<(Range<usize>, Arc<str>)> {
44 text_diff_with_options(old_text, new_text, DiffOptions::default())
45}
46
47pub struct DiffOptions {
48 pub language_scope: Option<LanguageScope>,
49 pub max_word_diff_len: usize,
50 pub max_word_diff_line_count: usize,
51}
52
53impl Default for DiffOptions {
54 fn default() -> Self {
55 Self {
56 language_scope: Default::default(),
57 max_word_diff_len: MAX_WORD_DIFF_LEN,
58 max_word_diff_line_count: MAX_WORD_DIFF_LINE_COUNT,
59 }
60 }
61}
62
63/// Computes a diff between two strings, using a specific language scope's
64/// word characters for word-level diffing.
65pub fn text_diff_with_options(
66 old_text: &str,
67 new_text: &str,
68 options: DiffOptions,
69) -> Vec<(Range<usize>, Arc<str>)> {
70 let empty: Arc<str> = Arc::default();
71 let mut edits = Vec::new();
72 let mut hunk_input = InternedInput::default();
73 let input = InternedInput::new(
74 lines_with_terminator(old_text),
75 lines_with_terminator(new_text),
76 );
77 diff_internal(
78 &input,
79 |old_byte_range, new_byte_range, old_rows, new_rows| {
80 if should_perform_word_diff_within_hunk(
81 &old_rows,
82 &old_byte_range,
83 &new_rows,
84 &new_byte_range,
85 &options,
86 ) {
87 let old_offset = old_byte_range.start;
88 let new_offset = new_byte_range.start;
89 hunk_input.clear();
90 hunk_input.update_before(tokenize(
91 &old_text[old_byte_range.clone()],
92 options.language_scope.clone(),
93 ));
94 hunk_input.update_after(tokenize(
95 &new_text[new_byte_range.clone()],
96 options.language_scope.clone(),
97 ));
98 diff_internal(&hunk_input, |old_byte_range, new_byte_range, _, _| {
99 let old_byte_range =
100 old_offset + old_byte_range.start..old_offset + old_byte_range.end;
101 let new_byte_range =
102 new_offset + new_byte_range.start..new_offset + new_byte_range.end;
103 let replacement_text = if new_byte_range.is_empty() {
104 empty.clone()
105 } else {
106 new_text[new_byte_range.clone()].into()
107 };
108 edits.push((old_byte_range, replacement_text));
109 });
110 } else {
111 let replacement_text = if new_byte_range.is_empty() {
112 empty.clone()
113 } else {
114 new_text[new_byte_range.clone()].into()
115 };
116 edits.push((old_byte_range.clone(), replacement_text));
117 }
118 },
119 );
120 edits
121}
122
123fn should_perform_word_diff_within_hunk(
124 old_row_range: &Range<u32>,
125 old_byte_range: &Range<usize>,
126 new_row_range: &Range<u32>,
127 new_byte_range: &Range<usize>,
128 options: &DiffOptions,
129) -> bool {
130 !old_byte_range.is_empty()
131 && !new_byte_range.is_empty()
132 && old_byte_range.len() <= options.max_word_diff_len
133 && new_byte_range.len() <= options.max_word_diff_len
134 && old_row_range.len() <= options.max_word_diff_line_count
135 && new_row_range.len() <= options.max_word_diff_line_count
136}
137
138fn diff_internal(
139 input: &InternedInput<&str>,
140 mut on_change: impl FnMut(Range<usize>, Range<usize>, Range<u32>, Range<u32>),
141) {
142 let mut old_offset = 0;
143 let mut new_offset = 0;
144 let mut old_token_ix = 0;
145 let mut new_token_ix = 0;
146 diff(
147 Algorithm::Histogram,
148 input,
149 |old_tokens: Range<u32>, new_tokens: Range<u32>| {
150 old_offset += token_len(
151 &input,
152 &input.before[old_token_ix as usize..old_tokens.start as usize],
153 );
154 new_offset += token_len(
155 &input,
156 &input.after[new_token_ix as usize..new_tokens.start as usize],
157 );
158 let old_len = token_len(
159 &input,
160 &input.before[old_tokens.start as usize..old_tokens.end as usize],
161 );
162 let new_len = token_len(
163 &input,
164 &input.after[new_tokens.start as usize..new_tokens.end as usize],
165 );
166 let old_byte_range = old_offset..old_offset + old_len;
167 let new_byte_range = new_offset..new_offset + new_len;
168 old_token_ix = old_tokens.end;
169 new_token_ix = new_tokens.end;
170 old_offset = old_byte_range.end;
171 new_offset = new_byte_range.end;
172 on_change(old_byte_range, new_byte_range, old_tokens, new_tokens);
173 },
174 );
175}
176
177fn tokenize(text: &str, language_scope: Option<LanguageScope>) -> impl Iterator<Item = &str> {
178 let classifier = CharClassifier::new(language_scope).for_completion(true);
179 let mut chars = text.char_indices();
180 let mut prev = None;
181 let mut start_ix = 0;
182 iter::from_fn(move || {
183 while let Some((ix, c)) = chars.next() {
184 let mut token = None;
185 let kind = classifier.kind(c);
186 if let Some((prev_char, prev_kind)) = prev {
187 if kind != prev_kind || (kind == CharKind::Punctuation && c != prev_char) {
188 token = Some(&text[start_ix..ix]);
189 start_ix = ix;
190 }
191 }
192 prev = Some((c, kind));
193 if token.is_some() {
194 return token;
195 }
196 }
197 if start_ix < text.len() {
198 let token = &text[start_ix..];
199 start_ix = text.len();
200 return Some(token);
201 }
202 None
203 })
204}
205
206fn token_len(input: &InternedInput<&str>, tokens: &[Token]) -> usize {
207 tokens
208 .iter()
209 .map(|token| input.interner[*token].len())
210 .sum()
211}
212
213#[cfg(test)]
214mod tests {
215 use super::*;
216
217 #[test]
218 fn test_tokenize() {
219 let text = "";
220 assert_eq!(tokenize(text, None).collect::<Vec<_>>(), Vec::<&str>::new());
221
222 let text = " ";
223 assert_eq!(tokenize(text, None).collect::<Vec<_>>(), vec![" "]);
224
225 let text = "one";
226 assert_eq!(tokenize(text, None).collect::<Vec<_>>(), vec!["one"]);
227
228 let text = "one\n";
229 assert_eq!(tokenize(text, None).collect::<Vec<_>>(), vec!["one", "\n"]);
230
231 let text = "one.two(three)";
232 assert_eq!(
233 tokenize(text, None).collect::<Vec<_>>(),
234 vec!["one", ".", "two", "(", "three", ")"]
235 );
236
237 let text = "one two three()";
238 assert_eq!(
239 tokenize(text, None).collect::<Vec<_>>(),
240 vec!["one", " ", "two", " ", "three", "(", ")"]
241 );
242
243 let text = " one\n two three";
244 assert_eq!(
245 tokenize(text, None).collect::<Vec<_>>(),
246 vec![" ", "one", "\n ", "two", " ", "three"]
247 );
248 }
249
250 #[test]
251 fn test_text_diff() {
252 let old_text = "one two three";
253 let new_text = "one TWO three";
254 assert_eq!(text_diff(old_text, new_text), [(4..7, "TWO".into()),]);
255
256 let old_text = "one\ntwo\nthree\n";
257 let new_text = "one\ntwo\nAND\nTHEN\nthree\n";
258 assert_eq!(
259 text_diff(old_text, new_text),
260 [(8..8, "AND\nTHEN\n".into()),]
261 );
262
263 let old_text = "one two\nthree four five\nsix seven eight nine\nten\n";
264 let new_text = "one two\nthree FOUR five\nsix SEVEN eight nine\nten\nELEVEN\n";
265 assert_eq!(
266 text_diff(old_text, new_text),
267 [
268 (14..18, "FOUR".into()),
269 (28..33, "SEVEN".into()),
270 (49..49, "ELEVEN\n".into())
271 ]
272 );
273 }
274}