1use std::{iter, ops::Range};
2use sum_tree::SumTree;
3use text::{Anchor, BufferId, BufferSnapshot, OffsetRangeExt, Point};
4
5pub use git2 as libgit;
6use libgit::{DiffLineType as GitDiffLineType, DiffOptions as GitOptions, Patch as GitPatch};
7
8#[derive(Debug, Clone, Copy, PartialEq, Eq)]
9pub enum DiffHunkStatus {
10 Added,
11 Modified,
12 Removed,
13}
14
15/// A diff hunk, representing a range of consequent lines in a singleton buffer, associated with a generic range.
16#[derive(Debug, Clone, PartialEq, Eq)]
17pub struct DiffHunk<T> {
18 /// E.g. a range in multibuffer, that has an excerpt added, singleton buffer for which has this diff hunk.
19 /// Consider a singleton buffer with 10 lines, all of them are modified — so a corresponding diff hunk would have a range 0..10.
20 /// And a multibuffer with the excerpt of lines 2-6 from the singleton buffer.
21 /// If the multibuffer is searched for diff hunks, the associated range would be multibuffer rows, corresponding to rows 2..6 from the singleton buffer.
22 /// But the hunk range would be 0..10, same for any other excerpts from the same singleton buffer.
23 pub associated_range: Range<T>,
24 /// Singleton buffer ID this hunk belongs to.
25 pub buffer_id: BufferId,
26 /// A consequent range of lines in the singleton buffer, that were changed and produced this diff hunk.
27 pub buffer_range: Range<Anchor>,
28 /// Original singleton buffer text before the change, that was instead of the `buffer_range`.
29 pub diff_base_byte_range: Range<usize>,
30}
31
32impl<T> DiffHunk<T> {
33 fn buffer_range_empty(&self) -> bool {
34 if self.buffer_range.start == self.buffer_range.end {
35 return true;
36 }
37
38 // buffer diff hunks are per line, so if we arrive to the same line with different bias, it's the same hunk
39 let Anchor {
40 timestamp: timestamp_start,
41 offset: offset_start,
42 buffer_id: buffer_id_start,
43 bias: _,
44 } = self.buffer_range.start;
45 let Anchor {
46 timestamp: timestamp_end,
47 offset: offset_end,
48 buffer_id: buffer_id_end,
49 bias: _,
50 } = self.buffer_range.end;
51 timestamp_start == timestamp_end
52 && offset_start == offset_end
53 && buffer_id_start == buffer_id_end
54 }
55}
56
57impl DiffHunk<u32> {
58 pub fn status(&self) -> DiffHunkStatus {
59 if self.diff_base_byte_range.is_empty() {
60 DiffHunkStatus::Added
61 } else if self.buffer_range_empty() {
62 DiffHunkStatus::Removed
63 } else {
64 DiffHunkStatus::Modified
65 }
66 }
67}
68
69impl sum_tree::Item for DiffHunk<Anchor> {
70 type Summary = DiffHunkSummary;
71
72 fn summary(&self) -> Self::Summary {
73 DiffHunkSummary {
74 buffer_range: self.associated_range.clone(),
75 }
76 }
77}
78
79#[derive(Debug, Default, Clone)]
80pub struct DiffHunkSummary {
81 buffer_range: Range<Anchor>,
82}
83
84impl sum_tree::Summary for DiffHunkSummary {
85 type Context = text::BufferSnapshot;
86
87 fn add_summary(&mut self, other: &Self, buffer: &Self::Context) {
88 self.buffer_range.start = self
89 .buffer_range
90 .start
91 .min(&other.buffer_range.start, buffer);
92 self.buffer_range.end = self.buffer_range.end.max(&other.buffer_range.end, buffer);
93 }
94}
95
96#[derive(Debug, Clone)]
97pub struct BufferDiff {
98 last_buffer_version: Option<clock::Global>,
99 tree: SumTree<DiffHunk<Anchor>>,
100}
101
102impl BufferDiff {
103 pub fn new() -> BufferDiff {
104 BufferDiff {
105 last_buffer_version: None,
106 tree: SumTree::new(),
107 }
108 }
109
110 pub fn is_empty(&self) -> bool {
111 self.tree.is_empty()
112 }
113
114 pub fn hunks_in_row_range<'a>(
115 &'a self,
116 range: Range<u32>,
117 buffer: &'a BufferSnapshot,
118 ) -> impl 'a + Iterator<Item = DiffHunk<u32>> {
119 let start = buffer.anchor_before(Point::new(range.start, 0));
120 let end = buffer.anchor_after(Point::new(range.end, 0));
121
122 self.hunks_intersecting_range(start..end, buffer)
123 }
124
125 pub fn hunks_intersecting_range<'a>(
126 &'a self,
127 range: Range<Anchor>,
128 buffer: &'a BufferSnapshot,
129 ) -> impl 'a + Iterator<Item = DiffHunk<u32>> {
130 let mut cursor = self.tree.filter::<_, DiffHunkSummary>(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 = std::iter::from_fn(move || {
137 cursor.next(buffer);
138 cursor.item()
139 })
140 .flat_map(move |hunk| {
141 [
142 (
143 &hunk.associated_range.start,
144 hunk.diff_base_byte_range.start,
145 ),
146 (&hunk.associated_range.end, hunk.diff_base_byte_range.end),
147 ]
148 .into_iter()
149 });
150
151 let mut summaries = buffer.summaries_for_anchors_with_payload::<Point, _, _>(anchor_iter);
152 iter::from_fn(move || {
153 let (start_point, start_base) = summaries.next()?;
154 let (mut end_point, end_base) = summaries.next()?;
155
156 if end_point.column > 0 {
157 end_point.row += 1;
158 }
159
160 Some(DiffHunk {
161 associated_range: start_point.row..end_point.row,
162 diff_base_byte_range: start_base..end_base,
163 buffer_range: buffer.anchor_before(start_point)..buffer.anchor_after(end_point),
164 buffer_id: buffer.remote_id(),
165 })
166 })
167 }
168
169 pub fn hunks_intersecting_range_rev<'a>(
170 &'a self,
171 range: Range<Anchor>,
172 buffer: &'a BufferSnapshot,
173 ) -> impl 'a + Iterator<Item = DiffHunk<u32>> {
174 let mut cursor = self.tree.filter::<_, DiffHunkSummary>(move |summary| {
175 let before_start = summary.buffer_range.end.cmp(&range.start, buffer).is_lt();
176 let after_end = summary.buffer_range.start.cmp(&range.end, buffer).is_gt();
177 !before_start && !after_end
178 });
179
180 std::iter::from_fn(move || {
181 cursor.prev(buffer);
182
183 let hunk = cursor.item()?;
184 let range = hunk.associated_range.to_point(buffer);
185 let end_row = if range.end.column > 0 {
186 range.end.row + 1
187 } else {
188 range.end.row
189 };
190
191 Some(DiffHunk {
192 associated_range: range.start.row..end_row,
193 diff_base_byte_range: hunk.diff_base_byte_range.clone(),
194 buffer_range: hunk.buffer_range.clone(),
195 buffer_id: hunk.buffer_id,
196 })
197 })
198 }
199
200 pub fn clear(&mut self, buffer: &text::BufferSnapshot) {
201 self.last_buffer_version = Some(buffer.version().clone());
202 self.tree = SumTree::new();
203 }
204
205 pub async fn update(&mut self, diff_base: &str, buffer: &text::BufferSnapshot) {
206 let mut tree = SumTree::new();
207
208 let buffer_text = buffer.as_rope().to_string();
209 let patch = Self::diff(diff_base, &buffer_text);
210
211 if let Some(patch) = patch {
212 let mut divergence = 0;
213 for hunk_index in 0..patch.num_hunks() {
214 let hunk = Self::process_patch_hunk(&patch, hunk_index, buffer, &mut divergence);
215 tree.push(hunk, buffer);
216 }
217 }
218
219 self.tree = tree;
220 self.last_buffer_version = Some(buffer.version().clone());
221 }
222
223 #[cfg(test)]
224 fn hunks<'a>(&'a self, text: &'a BufferSnapshot) -> impl 'a + Iterator<Item = DiffHunk<u32>> {
225 let start = text.anchor_before(Point::new(0, 0));
226 let end = text.anchor_after(Point::new(u32::MAX, u32::MAX));
227 self.hunks_intersecting_range(start..end, text)
228 }
229
230 fn diff<'a>(head: &'a str, current: &'a str) -> Option<GitPatch<'a>> {
231 let mut options = GitOptions::default();
232 options.context_lines(0);
233
234 let patch = GitPatch::from_buffers(
235 head.as_bytes(),
236 None,
237 current.as_bytes(),
238 None,
239 Some(&mut options),
240 );
241
242 match patch {
243 Ok(patch) => Some(patch),
244
245 Err(err) => {
246 log::error!("`GitPatch::from_buffers` failed: {}", err);
247 None
248 }
249 }
250 }
251
252 fn process_patch_hunk(
253 patch: &GitPatch<'_>,
254 hunk_index: usize,
255 buffer: &text::BufferSnapshot,
256 buffer_row_divergence: &mut i64,
257 ) -> DiffHunk<Anchor> {
258 let line_item_count = patch.num_lines_in_hunk(hunk_index).unwrap();
259 assert!(line_item_count > 0);
260
261 let mut first_deletion_buffer_row: Option<u32> = None;
262 let mut buffer_row_range: Option<Range<u32>> = None;
263 let mut diff_base_byte_range: Option<Range<usize>> = None;
264
265 for line_index in 0..line_item_count {
266 let line = patch.line_in_hunk(hunk_index, line_index).unwrap();
267 let kind = line.origin_value();
268 let content_offset = line.content_offset() as isize;
269 let content_len = line.content().len() as isize;
270
271 if kind == GitDiffLineType::Addition {
272 *buffer_row_divergence += 1;
273 let row = line.new_lineno().unwrap().saturating_sub(1);
274
275 match &mut buffer_row_range {
276 Some(buffer_row_range) => buffer_row_range.end = row + 1,
277 None => buffer_row_range = Some(row..row + 1),
278 }
279 }
280
281 if kind == GitDiffLineType::Deletion {
282 let end = content_offset + content_len;
283
284 match &mut diff_base_byte_range {
285 Some(head_byte_range) => head_byte_range.end = end as usize,
286 None => diff_base_byte_range = Some(content_offset as usize..end as usize),
287 }
288
289 if first_deletion_buffer_row.is_none() {
290 let old_row = line.old_lineno().unwrap().saturating_sub(1);
291 let row = old_row as i64 + *buffer_row_divergence;
292 first_deletion_buffer_row = Some(row as u32);
293 }
294
295 *buffer_row_divergence -= 1;
296 }
297 }
298
299 //unwrap_or deletion without addition
300 let buffer_row_range = buffer_row_range.unwrap_or_else(|| {
301 //we cannot have an addition-less hunk without deletion(s) or else there would be no hunk
302 let row = first_deletion_buffer_row.unwrap();
303 row..row
304 });
305
306 //unwrap_or addition without deletion
307 let diff_base_byte_range = diff_base_byte_range.unwrap_or(0..0);
308
309 let start = Point::new(buffer_row_range.start, 0);
310 let end = Point::new(buffer_row_range.end, 0);
311 let buffer_range = buffer.anchor_before(start)..buffer.anchor_before(end);
312 DiffHunk {
313 associated_range: buffer_range.clone(),
314 buffer_range,
315 diff_base_byte_range,
316 buffer_id: buffer.remote_id(),
317 }
318 }
319}
320
321/// Range (crossing new lines), old, new
322#[cfg(any(test, feature = "test-support"))]
323#[track_caller]
324pub fn assert_hunks<Iter>(
325 diff_hunks: Iter,
326 buffer: &BufferSnapshot,
327 diff_base: &str,
328 expected_hunks: &[(Range<u32>, &str, &str)],
329) where
330 Iter: Iterator<Item = DiffHunk<u32>>,
331{
332 let actual_hunks = diff_hunks
333 .map(|hunk| {
334 (
335 hunk.associated_range.clone(),
336 &diff_base[hunk.diff_base_byte_range],
337 buffer
338 .text_for_range(
339 Point::new(hunk.associated_range.start, 0)
340 ..Point::new(hunk.associated_range.end, 0),
341 )
342 .collect::<String>(),
343 )
344 })
345 .collect::<Vec<_>>();
346
347 let expected_hunks: Vec<_> = expected_hunks
348 .iter()
349 .map(|(r, s, h)| (r.clone(), *s, h.to_string()))
350 .collect();
351
352 assert_eq!(actual_hunks, expected_hunks);
353}
354
355#[cfg(test)]
356mod tests {
357 use std::assert_eq;
358
359 use super::*;
360 use text::{Buffer, BufferId};
361 use unindent::Unindent as _;
362
363 #[test]
364 fn test_buffer_diff_simple() {
365 let diff_base = "
366 one
367 two
368 three
369 "
370 .unindent();
371
372 let buffer_text = "
373 one
374 HELLO
375 three
376 "
377 .unindent();
378
379 let mut buffer = Buffer::new(0, BufferId::new(1).unwrap(), buffer_text);
380 let mut diff = BufferDiff::new();
381 smol::block_on(diff.update(&diff_base, &buffer));
382 assert_hunks(
383 diff.hunks(&buffer),
384 &buffer,
385 &diff_base,
386 &[(1..2, "two\n", "HELLO\n")],
387 );
388
389 buffer.edit([(0..0, "point five\n")]);
390 smol::block_on(diff.update(&diff_base, &buffer));
391 assert_hunks(
392 diff.hunks(&buffer),
393 &buffer,
394 &diff_base,
395 &[(0..1, "", "point five\n"), (2..3, "two\n", "HELLO\n")],
396 );
397
398 diff.clear(&buffer);
399 assert_hunks(diff.hunks(&buffer), &buffer, &diff_base, &[]);
400 }
401
402 #[test]
403 fn test_buffer_diff_range() {
404 let diff_base = "
405 one
406 two
407 three
408 four
409 five
410 six
411 seven
412 eight
413 nine
414 ten
415 "
416 .unindent();
417
418 let buffer_text = "
419 A
420 one
421 B
422 two
423 C
424 three
425 HELLO
426 four
427 five
428 SIXTEEN
429 seven
430 eight
431 WORLD
432 nine
433
434 ten
435
436 "
437 .unindent();
438
439 let buffer = Buffer::new(0, BufferId::new(1).unwrap(), buffer_text);
440 let mut diff = BufferDiff::new();
441 smol::block_on(diff.update(&diff_base, &buffer));
442 assert_eq!(diff.hunks(&buffer).count(), 8);
443
444 assert_hunks(
445 diff.hunks_in_row_range(7..12, &buffer),
446 &buffer,
447 &diff_base,
448 &[
449 (6..7, "", "HELLO\n"),
450 (9..10, "six\n", "SIXTEEN\n"),
451 (12..13, "", "WORLD\n"),
452 ],
453 );
454 }
455}