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