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