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