1use rope::Rope;
2use std::{cmp, iter, ops::Range};
3use sum_tree::SumTree;
4use text::{Anchor, BufferSnapshot, OffsetRangeExt, Point};
5
6pub use git2 as libgit;
7use libgit::{DiffLineType as GitDiffLineType, DiffOptions as GitOptions, Patch as GitPatch};
8
9#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
10pub enum DiffHunkStatus {
11 Added,
12 Modified,
13 Removed,
14}
15
16/// A diff hunk resolved to rows in the buffer.
17#[derive(Debug, Clone, PartialEq, Eq)]
18pub struct DiffHunk {
19 /// The buffer range, expressed in terms of rows.
20 pub row_range: Range<u32>,
21 /// The range in the buffer to which this hunk corresponds.
22 pub buffer_range: Range<Anchor>,
23 /// The range in the buffer's diff base text to which this hunk corresponds.
24 pub diff_base_byte_range: Range<usize>,
25}
26
27/// We store [`InternalDiffHunk`]s internally so we don't need to store the additional row range.
28#[derive(Debug, Clone, PartialEq, Eq)]
29struct InternalDiffHunk {
30 buffer_range: Range<Anchor>,
31 diff_base_byte_range: Range<usize>,
32}
33
34impl sum_tree::Item for InternalDiffHunk {
35 type Summary = DiffHunkSummary;
36
37 fn summary(&self, _cx: &text::BufferSnapshot) -> Self::Summary {
38 DiffHunkSummary {
39 buffer_range: self.buffer_range.clone(),
40 }
41 }
42}
43
44#[derive(Debug, Default, Clone)]
45pub struct DiffHunkSummary {
46 buffer_range: Range<Anchor>,
47}
48
49impl sum_tree::Summary for DiffHunkSummary {
50 type Context = text::BufferSnapshot;
51
52 fn zero(_cx: &Self::Context) -> Self {
53 Default::default()
54 }
55
56 fn add_summary(&mut self, other: &Self, buffer: &Self::Context) {
57 self.buffer_range.start = self
58 .buffer_range
59 .start
60 .min(&other.buffer_range.start, buffer);
61 self.buffer_range.end = self.buffer_range.end.max(&other.buffer_range.end, buffer);
62 }
63}
64
65#[derive(Debug, Clone)]
66pub struct BufferDiff {
67 tree: SumTree<InternalDiffHunk>,
68}
69
70impl BufferDiff {
71 pub fn new(buffer: &BufferSnapshot) -> BufferDiff {
72 BufferDiff {
73 tree: SumTree::new(buffer),
74 }
75 }
76
77 pub fn build(diff_base: &str, buffer: &text::BufferSnapshot) -> Self {
78 let mut tree = SumTree::new(buffer);
79
80 let buffer_text = buffer.as_rope().to_string();
81 let patch = Self::diff(diff_base, &buffer_text);
82
83 if let Some(patch) = patch {
84 let mut divergence = 0;
85 for hunk_index in 0..patch.num_hunks() {
86 let hunk = Self::process_patch_hunk(&patch, hunk_index, buffer, &mut divergence);
87 tree.push(hunk, buffer);
88 }
89 }
90
91 Self { tree }
92 }
93
94 pub fn is_empty(&self) -> bool {
95 self.tree.is_empty()
96 }
97
98 pub fn hunks_in_row_range<'a>(
99 &'a self,
100 range: Range<u32>,
101 buffer: &'a BufferSnapshot,
102 ) -> impl 'a + Iterator<Item = DiffHunk> {
103 let start = buffer.anchor_before(Point::new(range.start, 0));
104 let end = buffer.anchor_after(Point::new(range.end, 0));
105
106 self.hunks_intersecting_range(start..end, buffer)
107 }
108
109 pub fn hunks_intersecting_range<'a>(
110 &'a self,
111 range: Range<Anchor>,
112 buffer: &'a BufferSnapshot,
113 ) -> impl 'a + Iterator<Item = DiffHunk> {
114 let mut cursor = self
115 .tree
116 .filter::<_, DiffHunkSummary>(buffer, move |summary| {
117 let before_start = summary.buffer_range.end.cmp(&range.start, buffer).is_lt();
118 let after_end = summary.buffer_range.start.cmp(&range.end, buffer).is_gt();
119 !before_start && !after_end
120 });
121
122 let anchor_iter = iter::from_fn(move || {
123 cursor.next(buffer);
124 cursor.item()
125 })
126 .flat_map(move |hunk| {
127 [
128 (
129 &hunk.buffer_range.start,
130 (hunk.buffer_range.start, hunk.diff_base_byte_range.start),
131 ),
132 (
133 &hunk.buffer_range.end,
134 (hunk.buffer_range.end, hunk.diff_base_byte_range.end),
135 ),
136 ]
137 });
138
139 let mut summaries = buffer.summaries_for_anchors_with_payload::<Point, _, _>(anchor_iter);
140 iter::from_fn(move || {
141 let (start_point, (start_anchor, start_base)) = summaries.next()?;
142 let (mut end_point, (mut end_anchor, end_base)) = summaries.next()?;
143
144 if end_point.column > 0 {
145 end_point.row += 1;
146 end_point.column = 0;
147 end_anchor = buffer.anchor_before(end_point);
148 }
149
150 Some(DiffHunk {
151 row_range: start_point.row..end_point.row,
152 diff_base_byte_range: start_base..end_base,
153 buffer_range: start_anchor..end_anchor,
154 })
155 })
156 }
157
158 pub fn hunks_intersecting_range_rev<'a>(
159 &'a self,
160 range: Range<Anchor>,
161 buffer: &'a BufferSnapshot,
162 ) -> impl 'a + Iterator<Item = DiffHunk> {
163 let mut cursor = self
164 .tree
165 .filter::<_, DiffHunkSummary>(buffer, move |summary| {
166 let before_start = summary.buffer_range.end.cmp(&range.start, buffer).is_lt();
167 let after_end = summary.buffer_range.start.cmp(&range.end, buffer).is_gt();
168 !before_start && !after_end
169 });
170
171 iter::from_fn(move || {
172 cursor.prev(buffer);
173
174 let hunk = cursor.item()?;
175 let range = hunk.buffer_range.to_point(buffer);
176 let end_row = if range.end.column > 0 {
177 range.end.row + 1
178 } else {
179 range.end.row
180 };
181
182 Some(DiffHunk {
183 row_range: range.start.row..end_row,
184 diff_base_byte_range: hunk.diff_base_byte_range.clone(),
185 buffer_range: hunk.buffer_range.clone(),
186 })
187 })
188 }
189
190 pub fn compare(&self, old: &Self, new_snapshot: &BufferSnapshot) -> Option<Range<Anchor>> {
191 let mut new_cursor = self.tree.cursor::<()>(new_snapshot);
192 let mut old_cursor = old.tree.cursor::<()>(new_snapshot);
193 old_cursor.next(new_snapshot);
194 new_cursor.next(new_snapshot);
195 let mut start = None;
196 let mut end = None;
197
198 loop {
199 match (new_cursor.item(), old_cursor.item()) {
200 (Some(new_hunk), Some(old_hunk)) => {
201 match new_hunk
202 .buffer_range
203 .start
204 .cmp(&old_hunk.buffer_range.start, new_snapshot)
205 {
206 cmp::Ordering::Less => {
207 start.get_or_insert(new_hunk.buffer_range.start);
208 end.replace(new_hunk.buffer_range.end);
209 new_cursor.next(new_snapshot);
210 }
211 cmp::Ordering::Equal => {
212 if new_hunk != old_hunk {
213 start.get_or_insert(new_hunk.buffer_range.start);
214 if old_hunk
215 .buffer_range
216 .end
217 .cmp(&new_hunk.buffer_range.end, new_snapshot)
218 .is_ge()
219 {
220 end.replace(old_hunk.buffer_range.end);
221 } else {
222 end.replace(new_hunk.buffer_range.end);
223 }
224 }
225
226 new_cursor.next(new_snapshot);
227 old_cursor.next(new_snapshot);
228 }
229 cmp::Ordering::Greater => {
230 start.get_or_insert(old_hunk.buffer_range.start);
231 end.replace(old_hunk.buffer_range.end);
232 old_cursor.next(new_snapshot);
233 }
234 }
235 }
236 (Some(new_hunk), None) => {
237 start.get_or_insert(new_hunk.buffer_range.start);
238 end.replace(new_hunk.buffer_range.end);
239 new_cursor.next(new_snapshot);
240 }
241 (None, Some(old_hunk)) => {
242 start.get_or_insert(old_hunk.buffer_range.start);
243 end.replace(old_hunk.buffer_range.end);
244 old_cursor.next(new_snapshot);
245 }
246 (None, None) => break,
247 }
248 }
249
250 start.zip(end).map(|(start, end)| start..end)
251 }
252
253 #[cfg(test)]
254 fn clear(&mut self, buffer: &text::BufferSnapshot) {
255 self.tree = SumTree::new(buffer);
256 }
257
258 pub fn update(&mut self, diff_base: &Rope, buffer: &text::BufferSnapshot) {
259 *self = Self::build(&diff_base.to_string(), buffer);
260 }
261
262 #[cfg(test)]
263 fn hunks<'a>(&'a self, text: &'a BufferSnapshot) -> impl 'a + Iterator<Item = DiffHunk> {
264 let start = text.anchor_before(Point::new(0, 0));
265 let end = text.anchor_after(Point::new(u32::MAX, u32::MAX));
266 self.hunks_intersecting_range(start..end, text)
267 }
268
269 fn diff<'a>(head: &'a str, current: &'a str) -> Option<GitPatch<'a>> {
270 let mut options = GitOptions::default();
271 options.context_lines(0);
272
273 let patch = GitPatch::from_buffers(
274 head.as_bytes(),
275 None,
276 current.as_bytes(),
277 None,
278 Some(&mut options),
279 );
280
281 match patch {
282 Ok(patch) => Some(patch),
283
284 Err(err) => {
285 log::error!("`GitPatch::from_buffers` failed: {}", err);
286 None
287 }
288 }
289 }
290
291 fn process_patch_hunk(
292 patch: &GitPatch<'_>,
293 hunk_index: usize,
294 buffer: &text::BufferSnapshot,
295 buffer_row_divergence: &mut i64,
296 ) -> InternalDiffHunk {
297 let line_item_count = patch.num_lines_in_hunk(hunk_index).unwrap();
298 assert!(line_item_count > 0);
299
300 let mut first_deletion_buffer_row: Option<u32> = None;
301 let mut buffer_row_range: Option<Range<u32>> = None;
302 let mut diff_base_byte_range: Option<Range<usize>> = None;
303
304 for line_index in 0..line_item_count {
305 let line = patch.line_in_hunk(hunk_index, line_index).unwrap();
306 let kind = line.origin_value();
307 let content_offset = line.content_offset() as isize;
308 let content_len = line.content().len() as isize;
309
310 if kind == GitDiffLineType::Addition {
311 *buffer_row_divergence += 1;
312 let row = line.new_lineno().unwrap().saturating_sub(1);
313
314 match &mut buffer_row_range {
315 Some(buffer_row_range) => buffer_row_range.end = row + 1,
316 None => buffer_row_range = Some(row..row + 1),
317 }
318 }
319
320 if kind == GitDiffLineType::Deletion {
321 let end = content_offset + content_len;
322
323 match &mut diff_base_byte_range {
324 Some(head_byte_range) => head_byte_range.end = end as usize,
325 None => diff_base_byte_range = Some(content_offset as usize..end as usize),
326 }
327
328 if first_deletion_buffer_row.is_none() {
329 let old_row = line.old_lineno().unwrap().saturating_sub(1);
330 let row = old_row as i64 + *buffer_row_divergence;
331 first_deletion_buffer_row = Some(row as u32);
332 }
333
334 *buffer_row_divergence -= 1;
335 }
336 }
337
338 //unwrap_or deletion without addition
339 let buffer_row_range = buffer_row_range.unwrap_or_else(|| {
340 //we cannot have an addition-less hunk without deletion(s) or else there would be no hunk
341 let row = first_deletion_buffer_row.unwrap();
342 row..row
343 });
344
345 //unwrap_or addition without deletion
346 let diff_base_byte_range = diff_base_byte_range.unwrap_or(0..0);
347
348 let start = Point::new(buffer_row_range.start, 0);
349 let end = Point::new(buffer_row_range.end, 0);
350 let buffer_range = buffer.anchor_before(start)..buffer.anchor_before(end);
351 InternalDiffHunk {
352 buffer_range,
353 diff_base_byte_range,
354 }
355 }
356}
357
358/// Range (crossing new lines), old, new
359#[cfg(any(test, feature = "test-support"))]
360#[track_caller]
361pub fn assert_hunks<Iter>(
362 diff_hunks: Iter,
363 buffer: &BufferSnapshot,
364 diff_base: &str,
365 expected_hunks: &[(Range<u32>, &str, &str)],
366) where
367 Iter: Iterator<Item = DiffHunk>,
368{
369 let actual_hunks = diff_hunks
370 .map(|hunk| {
371 (
372 hunk.row_range.clone(),
373 &diff_base[hunk.diff_base_byte_range],
374 buffer
375 .text_for_range(
376 Point::new(hunk.row_range.start, 0)..Point::new(hunk.row_range.end, 0),
377 )
378 .collect::<String>(),
379 )
380 })
381 .collect::<Vec<_>>();
382
383 let expected_hunks: Vec<_> = expected_hunks
384 .iter()
385 .map(|(r, s, h)| (r.clone(), *s, h.to_string()))
386 .collect();
387
388 assert_eq!(actual_hunks, expected_hunks);
389}
390
391#[cfg(test)]
392mod tests {
393 use std::assert_eq;
394
395 use super::*;
396 use text::{Buffer, BufferId};
397 use unindent::Unindent as _;
398
399 #[test]
400 fn test_buffer_diff_simple() {
401 let diff_base = "
402 one
403 two
404 three
405 "
406 .unindent();
407 let diff_base_rope = Rope::from(diff_base.clone());
408
409 let buffer_text = "
410 one
411 HELLO
412 three
413 "
414 .unindent();
415
416 let mut buffer = Buffer::new(0, BufferId::new(1).unwrap(), buffer_text);
417 let mut diff = BufferDiff::new(&buffer);
418 diff.update(&diff_base_rope, &buffer);
419 assert_hunks(
420 diff.hunks(&buffer),
421 &buffer,
422 &diff_base,
423 &[(1..2, "two\n", "HELLO\n")],
424 );
425
426 buffer.edit([(0..0, "point five\n")]);
427 diff.update(&diff_base_rope, &buffer);
428 assert_hunks(
429 diff.hunks(&buffer),
430 &buffer,
431 &diff_base,
432 &[(0..1, "", "point five\n"), (2..3, "two\n", "HELLO\n")],
433 );
434
435 diff.clear(&buffer);
436 assert_hunks(diff.hunks(&buffer), &buffer, &diff_base, &[]);
437 }
438
439 #[test]
440 fn test_buffer_diff_range() {
441 let diff_base = "
442 one
443 two
444 three
445 four
446 five
447 six
448 seven
449 eight
450 nine
451 ten
452 "
453 .unindent();
454 let diff_base_rope = Rope::from(diff_base.clone());
455
456 let buffer_text = "
457 A
458 one
459 B
460 two
461 C
462 three
463 HELLO
464 four
465 five
466 SIXTEEN
467 seven
468 eight
469 WORLD
470 nine
471
472 ten
473
474 "
475 .unindent();
476
477 let buffer = Buffer::new(0, BufferId::new(1).unwrap(), buffer_text);
478 let mut diff = BufferDiff::new(&buffer);
479 diff.update(&diff_base_rope, &buffer);
480 assert_eq!(diff.hunks(&buffer).count(), 8);
481
482 assert_hunks(
483 diff.hunks_in_row_range(7..12, &buffer),
484 &buffer,
485 &diff_base,
486 &[
487 (6..7, "", "HELLO\n"),
488 (9..10, "six\n", "SIXTEEN\n"),
489 (12..13, "", "WORLD\n"),
490 ],
491 );
492 }
493
494 #[test]
495 fn test_buffer_diff_compare() {
496 let base_text = "
497 zero
498 one
499 two
500 three
501 four
502 five
503 six
504 seven
505 eight
506 nine
507 "
508 .unindent();
509
510 let buffer_text_1 = "
511 one
512 three
513 four
514 five
515 SIX
516 seven
517 eight
518 NINE
519 "
520 .unindent();
521
522 let mut buffer = Buffer::new(0, BufferId::new(1).unwrap(), buffer_text_1);
523
524 let empty_diff = BufferDiff::new(&buffer);
525 let diff_1 = BufferDiff::build(&base_text, &buffer);
526 let range = diff_1.compare(&empty_diff, &buffer).unwrap();
527 assert_eq!(range.to_point(&buffer), Point::new(0, 0)..Point::new(8, 0));
528
529 // Edit does not affect the diff.
530 buffer.edit_via_marked_text(
531 &"
532 one
533 three
534 four
535 five
536 «SIX.5»
537 seven
538 eight
539 NINE
540 "
541 .unindent(),
542 );
543 let diff_2 = BufferDiff::build(&base_text, &buffer);
544 assert_eq!(None, diff_2.compare(&diff_1, &buffer));
545
546 // Edit turns a deletion hunk into a modification.
547 buffer.edit_via_marked_text(
548 &"
549 one
550 «THREE»
551 four
552 five
553 SIX.5
554 seven
555 eight
556 NINE
557 "
558 .unindent(),
559 );
560 let diff_3 = BufferDiff::build(&base_text, &buffer);
561 let range = diff_3.compare(&diff_2, &buffer).unwrap();
562 assert_eq!(range.to_point(&buffer), Point::new(1, 0)..Point::new(2, 0));
563
564 // Edit turns a modification hunk into a deletion.
565 buffer.edit_via_marked_text(
566 &"
567 one
568 THREE
569 four
570 five«»
571 seven
572 eight
573 NINE
574 "
575 .unindent(),
576 );
577 let diff_4 = BufferDiff::build(&base_text, &buffer);
578 let range = diff_4.compare(&diff_3, &buffer).unwrap();
579 assert_eq!(range.to_point(&buffer), Point::new(3, 4)..Point::new(4, 0));
580
581 // Edit introduces a new insertion hunk.
582 buffer.edit_via_marked_text(
583 &"
584 one
585 THREE
586 four«
587 FOUR.5
588 »five
589 seven
590 eight
591 NINE
592 "
593 .unindent(),
594 );
595 let diff_5 = BufferDiff::build(&base_text, &buffer);
596 let range = diff_5.compare(&diff_4, &buffer).unwrap();
597 assert_eq!(range.to_point(&buffer), Point::new(3, 0)..Point::new(4, 0));
598
599 // Edit removes a hunk.
600 buffer.edit_via_marked_text(
601 &"
602 one
603 THREE
604 four
605 FOUR.5
606 five
607 seven
608 eight
609 «nine»
610 "
611 .unindent(),
612 );
613 let diff_6 = BufferDiff::build(&base_text, &buffer);
614 let range = diff_6.compare(&diff_5, &buffer).unwrap();
615 assert_eq!(range.to_point(&buffer), Point::new(7, 0)..Point::new(8, 0));
616 }
617}