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