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