1use std::ops::Range;
2
3use sum_tree::{Bias, SumTree};
4use text::{Anchor, BufferSnapshot, OffsetRangeExt, Point, Rope, ToOffset, ToPoint};
5
6pub use git2 as libgit;
7use libgit::{
8 DiffLine as GitDiffLine, DiffLineType as GitDiffLineType, DiffOptions as GitOptions,
9 Patch as GitPatch,
10};
11
12#[derive(Debug, Clone, Copy)]
13pub enum DiffHunkStatus {
14 Added,
15 Modified,
16 Removed,
17}
18
19#[derive(Debug, Clone, PartialEq, Eq)]
20pub struct DiffHunk<T> {
21 pub buffer_range: Range<T>,
22 pub head_byte_range: Range<usize>,
23}
24
25impl DiffHunk<u32> {
26 pub fn status(&self) -> DiffHunkStatus {
27 if self.head_byte_range.is_empty() {
28 DiffHunkStatus::Added
29 } else if self.buffer_range.is_empty() {
30 DiffHunkStatus::Removed
31 } else {
32 DiffHunkStatus::Modified
33 }
34 }
35}
36
37impl sum_tree::Item for DiffHunk<Anchor> {
38 type Summary = DiffHunkSummary;
39
40 fn summary(&self) -> Self::Summary {
41 DiffHunkSummary {
42 buffer_range: self.buffer_range.clone(),
43 head_range: self.head_byte_range.clone(),
44 }
45 }
46}
47
48#[derive(Debug, Default, Clone)]
49pub struct DiffHunkSummary {
50 buffer_range: Range<Anchor>,
51 head_range: Range<usize>,
52}
53
54impl sum_tree::Summary for DiffHunkSummary {
55 type Context = text::BufferSnapshot;
56
57 fn add_summary(&mut self, other: &Self, _: &Self::Context) {
58 self.head_range.start = self.head_range.start.min(other.head_range.start);
59 self.head_range.end = self.head_range.end.max(other.head_range.end);
60 }
61}
62
63#[derive(Debug, Default, Clone, PartialEq, Eq, PartialOrd, Ord)]
64struct HunkHeadEnd(usize);
65
66impl<'a> sum_tree::Dimension<'a, DiffHunkSummary> for HunkHeadEnd {
67 fn add_summary(&mut self, summary: &'a DiffHunkSummary, _: &text::BufferSnapshot) {
68 self.0 = summary.head_range.end;
69 }
70
71 fn from_summary(summary: &'a DiffHunkSummary, _: &text::BufferSnapshot) -> Self {
72 HunkHeadEnd(summary.head_range.end)
73 }
74}
75
76#[derive(Debug, Default, Clone, PartialEq, Eq, PartialOrd, Ord)]
77struct HunkBufferStart(u32);
78
79impl<'a> sum_tree::Dimension<'a, DiffHunkSummary> for HunkBufferStart {
80 fn add_summary(&mut self, summary: &'a DiffHunkSummary, buffer: &text::BufferSnapshot) {
81 self.0 = summary.buffer_range.start.to_point(buffer).row;
82 }
83
84 fn from_summary(summary: &'a DiffHunkSummary, buffer: &text::BufferSnapshot) -> Self {
85 HunkBufferStart(summary.buffer_range.start.to_point(buffer).row)
86 }
87}
88
89#[derive(Debug, Default, Clone, PartialEq, Eq, PartialOrd, Ord)]
90struct HunkBufferEnd(u32);
91
92impl<'a> sum_tree::Dimension<'a, DiffHunkSummary> for HunkBufferEnd {
93 fn add_summary(&mut self, summary: &'a DiffHunkSummary, buffer: &text::BufferSnapshot) {
94 self.0 = summary.buffer_range.end.to_point(buffer).row;
95 }
96
97 fn from_summary(summary: &'a DiffHunkSummary, buffer: &text::BufferSnapshot) -> Self {
98 HunkBufferEnd(summary.buffer_range.end.to_point(buffer).row)
99 }
100}
101
102struct HunkLineIter<'a, 'b> {
103 patch: &'a GitPatch<'b>,
104 hunk_index: usize,
105 line_index: usize,
106}
107
108impl<'a, 'b> HunkLineIter<'a, 'b> {
109 fn new(patch: &'a GitPatch<'b>, hunk_index: usize) -> Self {
110 HunkLineIter {
111 patch,
112 hunk_index,
113 line_index: 0,
114 }
115 }
116}
117
118impl<'a, 'b> std::iter::Iterator for HunkLineIter<'a, 'b> {
119 type Item = GitDiffLine<'b>;
120
121 fn next(&mut self) -> Option<Self::Item> {
122 if self.line_index >= self.patch.num_lines_in_hunk(self.hunk_index).unwrap() {
123 return None;
124 }
125
126 let line_index = self.line_index;
127 self.line_index += 1;
128 Some(
129 self.patch
130 .line_in_hunk(self.hunk_index, line_index)
131 .unwrap(),
132 )
133 }
134}
135
136#[derive(Clone)]
137pub struct BufferDiffSnapshot {
138 tree: SumTree<DiffHunk<Anchor>>,
139}
140
141impl BufferDiffSnapshot {
142 pub fn hunks_in_range<'a>(
143 &'a self,
144 query_row_range: Range<u32>,
145 buffer: &'a BufferSnapshot,
146 ) -> impl 'a + Iterator<Item = DiffHunk<u32>> {
147 self.tree.iter().filter_map(move |hunk| {
148 let range = hunk.buffer_range.to_point(&buffer);
149
150 if range.start.row <= query_row_range.end && query_row_range.start <= range.end.row {
151 let end_row = if range.end.column > 0 {
152 range.end.row + 1
153 } else {
154 range.end.row
155 };
156
157 Some(DiffHunk {
158 buffer_range: range.start.row..end_row,
159 head_byte_range: hunk.head_byte_range.clone(),
160 })
161 } else {
162 None
163 }
164 })
165 }
166
167 #[cfg(test)]
168 fn hunks<'a>(&'a self, text: &'a BufferSnapshot) -> impl 'a + Iterator<Item = DiffHunk<u32>> {
169 self.hunks_in_range(0..u32::MAX, text)
170 }
171}
172
173pub struct BufferDiff {
174 last_update_version: clock::Global,
175 snapshot: BufferDiffSnapshot,
176}
177
178impl BufferDiff {
179 pub fn new(head_text: &Option<String>, buffer: &text::BufferSnapshot) -> BufferDiff {
180 let mut tree = SumTree::new();
181
182 if let Some(head_text) = head_text {
183 let buffer_text = buffer.as_rope().to_string();
184 let patch = Self::diff(&head_text, &buffer_text);
185
186 if let Some(patch) = patch {
187 for hunk_index in 0..patch.num_hunks() {
188 let hunk = Self::process_patch_hunk(&patch, hunk_index, buffer);
189 tree.push(hunk, buffer);
190 }
191 }
192 }
193
194 BufferDiff {
195 last_update_version: buffer.version().clone(),
196 snapshot: BufferDiffSnapshot { tree },
197 }
198 }
199
200 pub fn snapshot(&self) -> BufferDiffSnapshot {
201 self.snapshot.clone()
202 }
203
204 pub fn update(&mut self, head_text: &str, buffer: &text::BufferSnapshot) {
205 // let buffer_string = buffer.as_rope().to_string();
206 // let buffer_bytes = buffer_string.as_bytes();
207
208 // let mut options = GitOptions::default();
209 // options.context_lines(0);
210 // let patch = match GitPatch::from_buffers(
211 // head_text.as_bytes(),
212 // None,
213 // buffer_bytes,
214 // None,
215 // Some(&mut options),
216 // ) {
217 // Ok(patch) => patch,
218 // Err(_) => todo!("This needs to be handled"),
219 // };
220
221 // let mut hunks = SumTree::<DiffHunk<Anchor>>::new();
222 // let mut delta = 0i64;
223 // for hunk_index in 0..patch.num_hunks() {
224 // for line_index in 0..patch.num_lines_in_hunk(hunk_index).unwrap() {
225 // let line = patch.line_in_hunk(hunk_index, line_index).unwrap();
226
227 // let hunk = match line.origin_value() {
228 // GitDiffLineType::Addition => {
229 // let buffer_start = line.content_offset();
230 // let buffer_end = buffer_start as usize + line.content().len();
231 // let head_offset = (buffer_start - delta) as usize;
232 // delta += line.content().len() as i64;
233 // DiffHunk {
234 // buffer_range: buffer.anchor_before(buffer_start as usize)
235 // ..buffer.anchor_after(buffer_end),
236 // head_byte_range: head_offset..head_offset,
237 // }
238 // }
239
240 // GitDiffLineType::Deletion => {
241 // let head_start = line.content_offset();
242 // let head_end = head_start as usize + line.content().len();
243 // let buffer_offset = (head_start + delta) as usize;
244 // delta -= line.content().len() as i64;
245 // DiffHunk {
246 // buffer_range: buffer.anchor_before(buffer_offset)
247 // ..buffer.anchor_after(buffer_offset),
248 // head_byte_range: (head_start as usize)..head_end,
249 // }
250 // }
251
252 // _ => continue,
253 // };
254
255 // let mut combined = false;
256 // hunks.update_last(
257 // |last_hunk| {
258 // if last_hunk.head_byte_range.end == hunk.head_byte_range.start {
259 // last_hunk.head_byte_range.end = hunk.head_byte_range.end;
260 // last_hunk.buffer_range.end = hunk.buffer_range.end;
261 // combined = true;
262 // }
263 // },
264 // buffer,
265 // );
266 // if !combined {
267 // hunks.push(hunk, buffer);
268 // }
269 // }
270 // }
271
272 // println!("=====");
273 // for hunk in hunks.iter() {
274 // let buffer_range = hunk.buffer_range.to_point(&buffer);
275 // println!(
276 // "hunk in buffer range {buffer_range:?}, head slice {:?}",
277 // &head_text[hunk.head_byte_range.clone()]
278 // );
279 // }
280 // println!("=====");
281
282 // self.snapshot.tree = hunks;
283 }
284
285 pub fn actual_update(
286 &mut self,
287 head_text: &str,
288 buffer: &BufferSnapshot,
289 ) -> Option<DiffHunk<Anchor>> {
290 for edit_range in self.group_edit_ranges(buffer) {
291 // let patch = self.diff(head, current)?;
292 }
293
294 None
295 }
296
297 fn diff<'a>(head: &'a str, current: &'a str) -> Option<GitPatch<'a>> {
298 let mut options = GitOptions::default();
299 options.context_lines(0);
300
301 let patch = GitPatch::from_buffers(
302 head.as_bytes(),
303 None,
304 current.as_bytes(),
305 None,
306 Some(&mut options),
307 );
308
309 match patch {
310 Ok(patch) => Some(patch),
311
312 Err(err) => {
313 log::error!("`GitPatch::from_buffers` failed: {}", err);
314 None
315 }
316 }
317 }
318
319 fn group_edit_ranges(&mut self, buffer: &text::BufferSnapshot) -> Vec<Range<u32>> {
320 const EXPAND_BY: u32 = 20;
321 const COMBINE_DISTANCE: u32 = 5;
322
323 // let mut cursor = self.snapshot.tree.cursor::<HunkBufferStart>();
324
325 let mut ranges = Vec::<Range<u32>>::new();
326
327 for edit in buffer.edits_since::<Point>(&self.last_update_version) {
328 let buffer_start = edit.new.start.row.saturating_sub(EXPAND_BY);
329 let buffer_end = (edit.new.end.row + EXPAND_BY).min(buffer.row_count());
330
331 match ranges.last_mut() {
332 Some(last_range) if last_range.end.abs_diff(buffer_end) <= COMBINE_DISTANCE => {
333 last_range.start = last_range.start.min(buffer_start);
334 last_range.end = last_range.end.max(buffer_end);
335 }
336
337 _ => ranges.push(buffer_start..buffer_end),
338 }
339 }
340
341 self.last_update_version = buffer.version().clone();
342 ranges
343 }
344
345 fn process_patch_hunk<'a>(
346 patch: &GitPatch<'a>,
347 hunk_index: usize,
348 buffer: &text::BufferSnapshot,
349 ) -> DiffHunk<Anchor> {
350 let line_item_count = patch.num_lines_in_hunk(hunk_index).unwrap();
351 assert!(line_item_count > 0);
352
353 let mut first_deletion_buffer_row: Option<u32> = None;
354 let mut buffer_byte_range: Option<Range<usize>> = None;
355 let mut head_byte_range: Option<Range<usize>> = None;
356
357 for line_index in 0..line_item_count {
358 let line = patch.line_in_hunk(hunk_index, line_index).unwrap();
359 let kind = line.origin_value();
360 let content_offset = line.content_offset() as isize;
361 let content_len = line.content().len() as isize;
362
363 match (kind, &mut buffer_byte_range, &mut head_byte_range) {
364 (GitDiffLineType::Addition, None, _) => {
365 let end = content_offset + content_len;
366 buffer_byte_range = Some(content_offset as usize..end as usize);
367 }
368
369 (GitDiffLineType::Addition, Some(buffer_byte_range), _) => {
370 let end = content_offset + content_len;
371 buffer_byte_range.end = end as usize;
372 }
373
374 (GitDiffLineType::Deletion, _, None) => {
375 let end = content_offset + content_len;
376 head_byte_range = Some(content_offset as usize..end as usize);
377 }
378
379 (GitDiffLineType::Deletion, _, Some(head_byte_range)) => {
380 let end = content_offset + content_len;
381 head_byte_range.end = end as usize;
382 }
383
384 _ => {}
385 }
386
387 if kind == GitDiffLineType::Deletion && first_deletion_buffer_row.is_none() {
388 //old_lineno is guarenteed to be Some for deletions
389 //libgit gives us line numbers that are 1-indexed but also returns a 0 for some states
390 let row = line.old_lineno().unwrap().saturating_sub(1);
391 first_deletion_buffer_row = Some(row);
392 }
393 }
394
395 //unwrap_or deletion without addition
396 let buffer_byte_range = buffer_byte_range.unwrap_or_else(|| {
397 //we cannot have an addition-less hunk without deletion(s) or else there would be no hunk
398 let row = first_deletion_buffer_row.unwrap();
399 let anchor = buffer.anchor_before(Point::new(row, 0));
400 let offset = anchor.to_offset(buffer);
401 offset..offset
402 });
403
404 //unwrap_or addition without deletion
405 let head_byte_range = head_byte_range.unwrap_or(0..0);
406
407 DiffHunk {
408 buffer_range: buffer.anchor_before(buffer_byte_range.start)
409 ..buffer.anchor_before(buffer_byte_range.end),
410 head_byte_range,
411 }
412 }
413
414 fn name() {
415 // if self.hunk_index >= self.patch.num_hunks() {
416 // return None;
417 // }
418
419 // let mut line_iter = HunkLineIter::new(&self.patch, self.hunk_index);
420 // let line = line_iter.find(|line| {
421 // matches!(
422 // line.origin_value(),
423 // GitDiffLineType::Addition | GitDiffLineType::Deletion
424 // )
425 // })?;
426
427 // //For the first line of a hunk the content offset is equally valid for an addition or deletion
428 // let content_offset = line.content_offset() as usize;
429
430 // let mut buffer_range = content_offset..content_offset;
431 // let mut head_byte_range = match line.origin_value() {
432 // GitDiffLineType::Addition => content_offset..content_offset,
433 // GitDiffLineType::Deletion => content_offset..content_offset + line.content().len(),
434 // _ => unreachable!(),
435 // };
436
437 // for line in line_iter {
438 // match line.origin_value() {
439 // GitDiffLineType::Addition => {
440 // // buffer_range.end =
441 // }
442
443 // GitDiffLineType::Deletion => {}
444
445 // _ => continue,
446 // }
447 // }
448
449 // self.hunk_index += 1;
450 // Some(DiffHunk {
451 // buffer_range: buffer.anchor_before(buffer_range.start)
452 // ..buffer.anchor_before(buffer_range.end),
453 // head_byte_range,
454 // })
455 }
456}
457
458#[cfg(test)]
459mod tests {
460 use super::*;
461 use text::Buffer;
462 use unindent::Unindent as _;
463
464 #[gpui::test]
465 fn test_buffer_diff_simple() {
466 let head_text = "
467 one
468 two
469 three
470 "
471 .unindent();
472
473 let buffer_text = "
474 one
475 hello
476 three
477 "
478 .unindent();
479
480 let mut buffer = Buffer::new(0, 0, buffer_text);
481 let diff = BufferDiff::new(&Some(head_text.clone()), &buffer);
482 assert_hunks(&diff, &buffer, &head_text, &[(1..2, "two\n")]);
483
484 buffer.edit([(0..0, "point five\n")]);
485 assert_hunks(&diff, &buffer, &head_text, &[(2..3, "two\n")]);
486 }
487
488 #[track_caller]
489 fn assert_hunks(
490 diff: &BufferDiff,
491 buffer: &BufferSnapshot,
492 head_text: &str,
493 expected_hunks: &[(Range<u32>, &str)],
494 ) {
495 let hunks = diff.snapshot.hunks(buffer).collect::<Vec<_>>();
496 assert_eq!(
497 hunks.len(),
498 expected_hunks.len(),
499 "actual hunks are {hunks:#?}"
500 );
501
502 let diff_iter = hunks.iter().enumerate();
503 for ((index, hunk), (expected_range, expected_str)) in diff_iter.zip(expected_hunks) {
504 assert_eq!(&hunk.buffer_range, expected_range, "for hunk {index}");
505 assert_eq!(
506 &head_text[hunk.head_byte_range.clone()],
507 *expected_str,
508 "for hunk {index}"
509 );
510 }
511 }
512
513 // use rand::rngs::StdRng;
514 // #[gpui::test(iterations = 100)]
515 // fn test_buffer_diff_random(mut rng: StdRng) {}
516}