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