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