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