Debian Codegraph @

src/blob/builtin_driver/text/utils.rs

raw
1 use std::{iter::Peekable, ops::Range};
2
3 use bstr::{BStr, ByteSlice, ByteVec};
4
5 use crate::blob::builtin_driver::text::ConflictStyle;
6
7 /// Used only when `diff3` is the conflict style as `zdiff3` automatically reduces hunks into nothing.
8 /// Here we check if all hunks are the same.
9 pub fn hunks_differ_in_diff3(
10 style: ConflictStyle,
11 a: &[Hunk],
12 b: &[Hunk],
13 input: &imara_diff::InternedInput<&[u8]>,
14 current_tokens: &[imara_diff::Token],
15 ) -> bool {
16 if style != ConflictStyle::Diff3 {
17 return true;
18 }
19
20 let tokens_for_hunk = |hunk: &Hunk| -> &[imara_diff::Token] {
21 &tokens_for_side(hunk.side, input, current_tokens)[hunk.after.start as usize..hunk.after.end as usize]
22 };
23
24 a.iter()
25 .flat_map(tokens_for_hunk)
26 .ne(b.iter().flat_map(tokens_for_hunk))
27 }
28
29 pub fn contains_lines(hunks: &[Hunk]) -> bool {
30 hunks.iter().any(|h| !h.after.is_empty())
31 }
32
33 /// ## Deviation
34 ///
35 /// This implementation definitely isn't the same as in Git, primarily because it seemed impossible
36 /// to understand what's going on there without investing more time than it seemed worth.
37 pub fn detect_line_ending(
38 hunks: &[Hunk],
39 input: &imara_diff::InternedInput<&[u8]>,
40 current_tokens: &[imara_diff::Token],
41 ) -> Option<&'static BStr> {
42 fn is_eol_crlf(
43 hunks: &[Hunk],
44 input: &imara_diff::InternedInput<&[u8]>,
45 current_tokens: &[imara_diff::Token],
46 ) -> Option<bool> {
47 let (range, side) = hunks.iter().rev().find_map(|h| {
48 (!h.after.is_empty())
49 .then_some((&h.after, h.side))
50 .or((!h.before.is_empty()).then_some((&h.before, Side::Ancestor)))
51 })?;
52
53 let tokens = tokens_for_side(side, input, current_tokens);
54 {
55 let last_line = tokens
56 .get(range.end as usize - 1)
57 .map(|token| &input.interner[*token])?;
58 if last_line.last() == Some(&b'\n') {
59 return last_line.get(last_line.len().checked_sub(2)?).map(|c| *c == b'\r');
60 }
61 }
62 let second_to_last_line = tokens
63 .get(range.end.checked_sub(2)? as usize)
64 .map(|token| &input.interner[*token])?;
65 second_to_last_line
66 .get(second_to_last_line.len().checked_sub(2)?)
67 .map(|c| *c == b'\r')
68 }
69 is_eol_crlf(hunks, input, current_tokens).map(|is_crlf| if is_crlf { b"\r\n".into() } else { b"\n".into() })
70 }
71
72 pub fn detect_line_ending_or_nl(
73 hunks: &[Hunk],
74 input: &imara_diff::InternedInput<&[u8]>,
75 current_tokens: &[imara_diff::Token],
76 ) -> &'static BStr {
77 detect_line_ending(hunks, input, current_tokens).unwrap_or(b"\n".into())
78 }
79
80 fn tokens_for_side<'a>(
81 side: Side,
82 input: &'a imara_diff::InternedInput<&[u8]>,
83 current_tokens: &'a [imara_diff::Token],
84 ) -> &'a [imara_diff::Token] {
85 match side {
86 Side::Current => current_tokens,
87 Side::Other => &input.after,
88 Side::Ancestor => &input.before,
89 }
90 }
91
92 pub fn assure_ends_with_nl(out: &mut Vec<u8>, nl: &BStr) {
93 if !out.is_empty() && !out.ends_with(b"\n") {
94 out.push_str(nl);
95 }
96 }
97
98 pub fn write_conflict_marker(out: &mut Vec<u8>, marker: u8, label: Option<&BStr>, marker_size: u8, nl: &BStr) {
99 assure_ends_with_nl(out, nl);
100 out.extend(std::iter::repeat_n(marker, marker_size as usize));
101 if let Some(label) = label {
102 out.push(b' ');
103 out.extend_from_slice(label);
104 }
105 out.push_str(nl);
106 }
107
108 pub fn write_ancestor(input: &imara_diff::InternedInput<&[u8]>, from: u32, to: usize, out: &mut Vec<u8>) {
109 if to < from as usize {
110 return;
111 }
112 if let Some(tokens) = input.before.get(from as usize..to) {
113 write_tokens(&input.interner, tokens, out);
114 }
115 }
116
117 /// Look at all hunks in `in_out` and fill in the ancestor in the range of `ancestor_range`.
118 /// This is all based on knowing the ranges are sequences of tokens.
119 pub fn fill_ancestor(Range { start, end }: &Range<u32>, in_out: &mut Vec<Hunk>) {
120 fn is_nonzero(num: &u32) -> bool {
121 *num > 0
122 }
123 if in_out.is_empty() {
124 return;
125 }
126 let first = &in_out[0];
127 let mut first_idx = 0;
128 if let Some(lines_to_add) = first.before.start.checked_sub(*start).filter(is_nonzero) {
129 in_out.insert(0, ancestor_hunk(*start, lines_to_add));
130 first_idx += 1;
131 }
132
133 let mut added_hunks = false;
134 for (idx, next_idx) in (first_idx..in_out.len()).map(|idx| (idx, idx + 1)) {
135 let Some(next_hunk) = in_out.get(next_idx) else { break };
136 let hunk = &in_out[idx];
137 if let Some(lines_to_add) = next_hunk.before.start.checked_sub(hunk.before.end).filter(is_nonzero) {
138 in_out.push(ancestor_hunk(hunk.before.end, lines_to_add));
139 added_hunks = true;
140 }
141 }
142 let in_out_len = in_out.len();
143 if added_hunks {
144 in_out[first_idx..in_out_len].sort_by_key(|hunk| hunk.before.start);
145 }
146
147 let last = &in_out[in_out_len - 1];
148 if let Some(lines_to_add) = end.checked_sub(last.before.end).filter(is_nonzero) {
149 in_out.push(ancestor_hunk(last.before.end, lines_to_add));
150 }
151 }
152
153 fn ancestor_hunk(start: u32, num_lines: u32) -> Hunk {
154 let range = start..start + num_lines;
155 Hunk {
156 before: range.clone(),
157 after: range,
158 side: Side::Ancestor,
159 }
160 }
161
162 /// Reduce the area of `a_hunks` and the hunks in `b_hunks` so that only those lines that are
163 /// actually different remain. Note that we have to compare the resolved values, not only the tokens,
164 /// so `current_tokens` is expected to be known to the `input` (and its `interner`).
165 /// Hunks from all input arrays maybe removed in the process from the front and back, in case they
166 /// are entirely equal to each other.
167 /// Note also that `a_hunks` and `b_hunks` are treated to be consecutive, so [`fill_ancestor()`] must
168 /// have been called beforehand, and are assumed to cover the same space in the ancestor buffer.
169 ///
170 /// Return a new vector of all the hunks that were removed from front and back, with partial hunks inserted,
171 /// along with the amount of hunks that go front, with the remaining going towards the back.
172 #[must_use]
173 pub fn zealously_contract_hunks(
174 a_hunks: &mut Vec<Hunk>,
175 b_hunks: &mut Vec<Hunk>,
176 input: &imara_diff::InternedInput<&[u8]>,
177 current_tokens: &[imara_diff::Token],
178 ) -> (Vec<Hunk>, usize) {
179 let line_content = |token_idx: u32, side: Side| {
180 let tokens = match side {
181 Side::Current => current_tokens,
182 Side::Other => &input.after,
183 Side::Ancestor => &input.before,
184 };
185 &input.interner[tokens[token_idx as usize]]
186 };
187 let (mut last_a_hunk_idx, mut last_b_hunk_idx) = (0, 0);
188 let (mut out, hunks_in_front) = {
189 let (mut remove_leading_a_hunks_from, mut remove_leading_b_hunks_from) = (None, None);
190 let (mut a_hunk_token_equal_till, mut b_hunk_token_equal_till) = (None, None);
191 for ((a_token_idx, a_hunk_idx, a_hunk_side), (b_token_idx, b_hunk_idx, b_hunk_side)) in
192 iterate_hunks(a_hunks).zip(iterate_hunks(b_hunks))
193 {
194 let a_line = line_content(a_token_idx, a_hunk_side).as_bstr();
195 let b_line = line_content(b_token_idx, b_hunk_side).as_bstr();
196
197 if last_a_hunk_idx != a_hunk_idx {
198 a_hunk_token_equal_till = None;
199 last_a_hunk_idx = a_hunk_idx;
200 }
201 if last_b_hunk_idx != b_hunk_idx {
202 b_hunk_token_equal_till = None;
203 last_b_hunk_idx = b_hunk_idx;
204 }
205 if a_line == b_line {
206 (remove_leading_a_hunks_from, remove_leading_b_hunks_from) = (Some(a_hunk_idx), Some(b_hunk_idx));
207 (a_hunk_token_equal_till, b_hunk_token_equal_till) = (Some(a_token_idx), Some(b_token_idx));
208 } else {
209 break;
210 }
211 }
212
213 let mut out = Vec::with_capacity(remove_leading_a_hunks_from.unwrap_or_else(|| {
214 if a_hunk_token_equal_till.is_some() {
215 1
216 } else {
217 0
218 }
219 }));
220 truncate_hunks_from_from_front(
221 a_hunks,
222 remove_leading_a_hunks_from,
223 a_hunk_token_equal_till,
224 Some(&mut out),
225 );
226 truncate_hunks_from_from_front(b_hunks, remove_leading_b_hunks_from, b_hunk_token_equal_till, None);
227 let hunks_in_front = out.len();
228 (out, hunks_in_front)
229 };
230
231 (last_a_hunk_idx, last_b_hunk_idx) = (0, 0);
232 {
233 let (mut remove_trailing_a_hunks_from, mut remove_trailing_b_hunks_from) = (None, None);
234 let (mut a_hunk_token_equal_from, mut b_hunk_token_equal_from) = (None, None);
235 for ((a_token_idx, a_hunk_idx, a_hunk_side), (b_token_idx, b_hunk_idx, b_hunk_side)) in
236 iterate_hunks_rev(a_hunks).zip(iterate_hunks_rev(b_hunks))
237 {
238 let a_line = line_content(a_token_idx, a_hunk_side).as_bstr();
239 let b_line = line_content(b_token_idx, b_hunk_side).as_bstr();
240
241 if last_a_hunk_idx != a_hunk_idx {
242 a_hunk_token_equal_from = None;
243 last_a_hunk_idx = a_hunk_idx;
244 }
245 if last_b_hunk_idx != b_hunk_idx {
246 b_hunk_token_equal_from = None;
247 last_b_hunk_idx = b_hunk_idx;
248 }
249
250 if a_line == b_line {
251 (remove_trailing_a_hunks_from, remove_trailing_b_hunks_from) = (Some(a_hunk_idx), Some(b_hunk_idx));
252 (a_hunk_token_equal_from, b_hunk_token_equal_from) = (Some(a_token_idx), Some(b_token_idx));
253 } else {
254 break;
255 }
256 }
257
258 truncate_hunks_from_from_back(
259 a_hunks,
260 remove_trailing_a_hunks_from,
261 a_hunk_token_equal_from,
262 Some(&mut out),
263 );
264 truncate_hunks_from_from_back(b_hunks, remove_trailing_b_hunks_from, b_hunk_token_equal_from, None);
265 }
266
267 (out, hunks_in_front)
268 }
269
270 fn range_by_side(hunk: &mut Hunk) -> &mut Range<u32> {
271 match hunk.side {
272 Side::Current | Side::Other => &mut hunk.after,
273 Side::Ancestor => &mut hunk.before,
274 }
275 }
276 fn truncate_hunks_from_from_front(
277 hunks: &mut Vec<Hunk>,
278 hunks_to_remove_until_idx: Option<usize>,
279 hunk_token_equal_till: Option<u32>,
280 mut out_hunks: Option<&mut Vec<Hunk>>,
281 ) {
282 let Some(hunks_to_remove_until_idx) = hunks_to_remove_until_idx else {
283 assert!(hunk_token_equal_till.is_none());
284 return;
285 };
286 let mut last_index_to_remove = Some(hunks_to_remove_until_idx);
287 let hunk = &mut hunks[hunks_to_remove_until_idx];
288 let range = range_by_side(hunk);
289 if let Some(hunk_token_equal_till) = hunk_token_equal_till {
290 let orig_start = range.start;
291 let new_start = hunk_token_equal_till + 1;
292 range.start = new_start;
293 if Range::<u32>::is_empty(range) {
294 range.start = orig_start;
295 } else if let Some(out) = out_hunks.as_deref_mut() {
296 last_index_to_remove = hunks_to_remove_until_idx.checked_sub(1);
297 let mut removed_hunk = hunk.clone();
298 let new_range = range_by_side(&mut removed_hunk);
299
300 new_range.start = orig_start;
301 new_range.end = new_start;
302
303 out.push(removed_hunk);
304 } else {
305 last_index_to_remove = hunks_to_remove_until_idx.checked_sub(1);
306 }
307 }
308 if let Some(last_index_to_remove) = last_index_to_remove {
309 let mut current_idx = 0;
310 hunks.retain(|hunk| {
311 if current_idx > last_index_to_remove {
312 true
313 } else {
314 current_idx += 1;
315 if let Some(out) = out_hunks.as_deref_mut() {
316 out.push(hunk.clone());
317 }
318 false
319 }
320 });
321 }
322 }
323
324 fn truncate_hunks_from_from_back(
325 hunks: &mut Vec<Hunk>,
326 remove_trailing_hunks_from_idx: Option<usize>,
327 hunk_token_equal_from: Option<u32>,
328 mut out_hunks: Option<&mut Vec<Hunk>>,
329 ) {
330 let Some(mut remove_trailing_hunks_from_idx) = remove_trailing_hunks_from_idx else {
331 assert!(hunk_token_equal_from.is_none());
332 return;
333 };
334
335 let hunk = &mut hunks[remove_trailing_hunks_from_idx];
336 let range = range_by_side(hunk);
337 if let Some(hunk_token_equal_from) = hunk_token_equal_from {
338 let orig_end = range.end;
339 let new_end = hunk_token_equal_from;
340 range.end = new_end;
341 if Range::<u32>::is_empty(range) {
342 range.end = orig_end;
343 } else if let Some(out) = out_hunks.as_deref_mut() {
344 remove_trailing_hunks_from_idx += 1;
345 let mut removed_hunk = hunk.clone();
346 let new_range = range_by_side(&mut removed_hunk);
347
348 new_range.start = new_end;
349 new_range.end = orig_end;
350
351 out.push(removed_hunk);
352 } else {
353 remove_trailing_hunks_from_idx += 1;
354 }
355 }
356 if let Some(out) = out_hunks {
357 out.extend_from_slice(&hunks[remove_trailing_hunks_from_idx..]);
358 }
359 hunks.truncate(remove_trailing_hunks_from_idx);
360 }
361
362 /// Return an iterator over `(token_idx, hunk_idx, hunk_side)` from `hunks`.
363 fn iterate_hunks(hunks: &[Hunk]) -> impl Iterator<Item = (u32, usize, Side)> + '_ {
364 hunks.iter().enumerate().flat_map(|(hunk_idx, hunk)| {
365 match hunk.side {
366 Side::Current | Side::Other => &hunk.after,
367 Side::Ancestor => &hunk.before,
368 }
369 .clone()
370 .map(move |idx| (idx, hunk_idx, hunk.side))
371 })
372 }
373
374 /// Return a reverse iterator over `(token_idx, hunk_idx, hunk_side)` from `hunks`.
375 fn iterate_hunks_rev(hunks: &[Hunk]) -> impl Iterator<Item = (u32, usize, Side)> + '_ {
376 hunks.iter().enumerate().rev().flat_map(|(hunk_idx, hunk)| {
377 match hunk.side {
378 Side::Current | Side::Other => &hunk.after,
379 Side::Ancestor => &hunk.before,
380 }
381 .clone()
382 .rev()
383 .map(move |idx| (idx, hunk_idx, hunk.side))
384 })
385 }
386
387 pub fn write_hunks(
388 hunks: &[Hunk],
389 input: &imara_diff::InternedInput<&[u8]>,
390 current_tokens: &[imara_diff::Token],
391 out: &mut Vec<u8>,
392 ) {
393 for hunk in hunks {
394 let (tokens, range) = match hunk.side {
395 Side::Current => (current_tokens, &hunk.after),
396 Side::Other => (input.after.as_slice(), &hunk.after),
397 Side::Ancestor => (input.before.as_slice(), &hunk.before),
398 };
399 write_tokens(&input.interner, &tokens[usize_range(range)], out);
400 }
401 }
402
403 fn usize_range(range: &Range<u32>) -> Range<usize> {
404 range.start as usize..range.end as usize
405 }
406
407 fn write_tokens(interner: &imara_diff::Interner<&[u8]>, tokens: &[imara_diff::Token], out: &mut Vec<u8>) {
408 for token in tokens {
409 out.extend_from_slice(interner[*token]);
410 }
411 }
412
413 /// Find all hunks in `iter` which aren't from the same side as `hunk` and intersect with it.
414 /// Also put `hunk` into `input` so it's the first item, and possibly put more hunks of the side of `hunk` so
415 /// `iter` doesn't have any overlapping hunks left.
416 /// Return `Some` if `intersecting` is non-empty after the operation, indicating overlapping hunks were found.
417 pub fn take_intersecting(
418 iter: &mut Peekable<impl Iterator<Item = Hunk>>,
419 input: &mut Vec<Hunk>,
420 intersecting: &mut Vec<Hunk>,
421 ) -> Option<()> {
422 input.clear();
423 input.push(iter.next()?);
424 intersecting.clear();
425
426 fn left_overlaps_right(left: &Hunk, right: &Hunk) -> bool {
427 left.side != right.side
428 && (right.before.contains(&left.before.start)
429 || (right.before.is_empty() && right.before.start == left.before.start))
430 }
431
432 loop {
433 let hunk = input.last().expect("just pushed");
434 while iter.peek().filter(|b_hunk| left_overlaps_right(b_hunk, hunk)).is_some() {
435 intersecting.extend(iter.next());
436 }
437 // The hunks that overlap might themselves overlap with a following hunk of the other side.
438 // If so, split it so it doesn't overlap anymore.
439 let mut found_more_intersections = false;
440 while intersecting
441 .last_mut()
442 .zip(iter.peek_mut())
443 .filter(|(last_intersecting, candidate)| left_overlaps_right(candidate, last_intersecting))
444 .is_some()
445 {
446 input.extend(iter.next());
447 found_more_intersections = true;
448 }
449 if !found_more_intersections {
450 break;
451 }
452 }
453 Some(())
454 }
455
456 pub fn tokens(input: &[u8]) -> imara_diff::sources::ByteLines<'_> {
457 imara_diff::sources::byte_lines(input)
458 }
459
460 #[derive(Debug, Copy, Clone, Eq, PartialEq)]
461 pub enum Side {
462 Current,
463 Other,
464 /// A special marker that is just used to be able to mix-in hunks that only point to the ancestor.
465 /// Only `before` matters then.
466 Ancestor,
467 }
468
469 #[derive(Debug, Clone)]
470 pub struct Hunk {
471 pub before: Range<u32>,
472 pub after: Range<u32>,
473 pub side: Side,
474 }
475
476 pub fn collect_hunks(
477 algorithm: imara_diff::Algorithm,
478 input: &imara_diff::InternedInput<&[u8]>,
479 side: Side,
480 mut hunks: Vec<Hunk>,
481 ) -> Vec<Hunk> {
482 let mut diff = imara_diff::Diff::compute(algorithm, input);
483 diff.postprocess_lines(input);
484 hunks.extend(diff.hunks().map(|hunk| Hunk {
485 before: hunk.before,
486 after: hunk.after,
487 side,
488 }));
489 hunks
490 }