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