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