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