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 for hunk_index in 0..patch.num_hunks() {
189 let patch = Self::process_patch_hunk(&patch, hunk_index, buffer);
190 tree.push(patch, buffer);
191 }
192 }
193 }
194
195 BufferDiff {
196 last_update_version: buffer.version().clone(),
197 snapshot: BufferDiffSnapshot { tree },
198 }
199 }
200
201 pub fn snapshot(&self) -> BufferDiffSnapshot {
202 self.snapshot.clone()
203 }
204
205 pub fn update(&mut self, head_text: &str, buffer: &text::BufferSnapshot) {
206 // let buffer_string = buffer.as_rope().to_string();
207 // let buffer_bytes = buffer_string.as_bytes();
208
209 // let mut options = GitOptions::default();
210 // options.context_lines(0);
211 // let patch = match GitPatch::from_buffers(
212 // head_text.as_bytes(),
213 // None,
214 // buffer_bytes,
215 // None,
216 // Some(&mut options),
217 // ) {
218 // Ok(patch) => patch,
219 // Err(_) => todo!("This needs to be handled"),
220 // };
221
222 // let mut hunks = SumTree::<DiffHunk<Anchor>>::new();
223 // let mut delta = 0i64;
224 // for hunk_index in 0..patch.num_hunks() {
225 // for line_index in 0..patch.num_lines_in_hunk(hunk_index).unwrap() {
226 // let line = patch.line_in_hunk(hunk_index, line_index).unwrap();
227
228 // let hunk = match line.origin_value() {
229 // GitDiffLineType::Addition => {
230 // let buffer_start = line.content_offset();
231 // let buffer_end = buffer_start as usize + line.content().len();
232 // let head_offset = (buffer_start - delta) as usize;
233 // delta += line.content().len() as i64;
234 // DiffHunk {
235 // buffer_range: buffer.anchor_before(buffer_start as usize)
236 // ..buffer.anchor_after(buffer_end),
237 // head_byte_range: head_offset..head_offset,
238 // }
239 // }
240
241 // GitDiffLineType::Deletion => {
242 // let head_start = line.content_offset();
243 // let head_end = head_start as usize + line.content().len();
244 // let buffer_offset = (head_start + delta) as usize;
245 // delta -= line.content().len() as i64;
246 // DiffHunk {
247 // buffer_range: buffer.anchor_before(buffer_offset)
248 // ..buffer.anchor_after(buffer_offset),
249 // head_byte_range: (head_start as usize)..head_end,
250 // }
251 // }
252
253 // _ => continue,
254 // };
255
256 // let mut combined = false;
257 // hunks.update_last(
258 // |last_hunk| {
259 // if last_hunk.head_byte_range.end == hunk.head_byte_range.start {
260 // last_hunk.head_byte_range.end = hunk.head_byte_range.end;
261 // last_hunk.buffer_range.end = hunk.buffer_range.end;
262 // combined = true;
263 // }
264 // },
265 // buffer,
266 // );
267 // if !combined {
268 // hunks.push(hunk, buffer);
269 // }
270 // }
271 // }
272
273 // println!("=====");
274 // for hunk in hunks.iter() {
275 // let buffer_range = hunk.buffer_range.to_point(&buffer);
276 // println!(
277 // "hunk in buffer range {buffer_range:?}, head slice {:?}",
278 // &head_text[hunk.head_byte_range.clone()]
279 // );
280 // }
281 // println!("=====");
282
283 // self.snapshot.tree = hunks;
284 }
285
286 pub fn actual_update(
287 &mut self,
288 head_text: &str,
289 buffer: &BufferSnapshot,
290 ) -> Option<DiffHunk<Anchor>> {
291 for edit_range in self.group_edit_ranges(buffer) {
292 // let patch = self.diff(head, current)?;
293 }
294
295 None
296 }
297
298 fn diff<'a>(head: &'a str, current: &'a str) -> Option<GitPatch<'a>> {
299 let mut options = GitOptions::default();
300 options.context_lines(0);
301
302 let patch = GitPatch::from_buffers(
303 head.as_bytes(),
304 None,
305 current.as_bytes(),
306 None,
307 Some(&mut options),
308 );
309
310 match patch {
311 Ok(patch) => Some(patch),
312
313 Err(err) => {
314 log::error!("`GitPatch::from_buffers` failed: {}", err);
315 None
316 }
317 }
318 }
319
320 fn group_edit_ranges(&mut self, buffer: &text::BufferSnapshot) -> Vec<Range<u32>> {
321 const EXPAND_BY: u32 = 20;
322 const COMBINE_DISTANCE: u32 = 5;
323
324 // let mut cursor = self.snapshot.tree.cursor::<HunkBufferStart>();
325
326 let mut ranges = Vec::<Range<u32>>::new();
327
328 for edit in buffer.edits_since::<Point>(&self.last_update_version) {
329 let buffer_start = edit.new.start.row.saturating_sub(EXPAND_BY);
330 let buffer_end = (edit.new.end.row + EXPAND_BY).min(buffer.row_count());
331
332 match ranges.last_mut() {
333 Some(last_range) if last_range.end.abs_diff(buffer_end) <= COMBINE_DISTANCE => {
334 last_range.start = last_range.start.min(buffer_start);
335 last_range.end = last_range.end.max(buffer_end);
336 }
337
338 _ => ranges.push(buffer_start..buffer_end),
339 }
340 }
341
342 self.last_update_version = buffer.version().clone();
343 ranges
344 }
345
346 fn process_patch_hunk<'a>(
347 patch: &GitPatch<'a>,
348 hunk_index: usize,
349 buffer: &text::BufferSnapshot,
350 ) -> DiffHunk<Anchor> {
351 let mut buffer_byte_range: Option<Range<usize>> = None;
352 let mut head_byte_range: Option<Range<usize>> = None;
353
354 for line_index in 0..patch.num_lines_in_hunk(hunk_index).unwrap() {
355 let line = patch.line_in_hunk(hunk_index, line_index).unwrap();
356 let kind = line.origin_value();
357 let content_offset = line.content_offset() as isize;
358 let content_len = line.content().len() as isize;
359
360 match (kind, &mut buffer_byte_range, &mut head_byte_range) {
361 (GitDiffLineType::Addition, None, _) => {
362 let end = content_offset + content_len;
363 buffer_byte_range = Some(content_offset as usize..end as usize);
364 }
365
366 (GitDiffLineType::Addition, Some(buffer_byte_range), _) => {
367 let end = content_offset + content_len;
368 buffer_byte_range.end = end as usize;
369 }
370
371 (GitDiffLineType::Deletion, _, None) => {
372 let end = content_offset + content_len;
373 head_byte_range = Some(content_offset as usize..end as usize);
374 }
375
376 (GitDiffLineType::Deletion, _, Some(head_byte_range)) => {
377 let end = content_offset + content_len;
378 head_byte_range.end = end as usize;
379 }
380
381 _ => {}
382 }
383 }
384
385 //unwrap_or deletion without addition
386 let buffer_byte_range = buffer_byte_range.unwrap_or(0..0);
387 //unwrap_or addition without deletion
388 let head_byte_range = head_byte_range.unwrap_or(0..0);
389
390 DiffHunk {
391 buffer_range: buffer.anchor_before(buffer_byte_range.start)
392 ..buffer.anchor_before(buffer_byte_range.end),
393 head_byte_range,
394 }
395 }
396
397 fn name() {
398 // if self.hunk_index >= self.patch.num_hunks() {
399 // return None;
400 // }
401
402 // let mut line_iter = HunkLineIter::new(&self.patch, self.hunk_index);
403 // let line = line_iter.find(|line| {
404 // matches!(
405 // line.origin_value(),
406 // GitDiffLineType::Addition | GitDiffLineType::Deletion
407 // )
408 // })?;
409
410 // //For the first line of a hunk the content offset is equally valid for an addition or deletion
411 // let content_offset = line.content_offset() as usize;
412
413 // let mut buffer_range = content_offset..content_offset;
414 // let mut head_byte_range = match line.origin_value() {
415 // GitDiffLineType::Addition => content_offset..content_offset,
416 // GitDiffLineType::Deletion => content_offset..content_offset + line.content().len(),
417 // _ => unreachable!(),
418 // };
419
420 // for line in line_iter {
421 // match line.origin_value() {
422 // GitDiffLineType::Addition => {
423 // // buffer_range.end =
424 // }
425
426 // GitDiffLineType::Deletion => {}
427
428 // _ => continue,
429 // }
430 // }
431
432 // self.hunk_index += 1;
433 // Some(DiffHunk {
434 // buffer_range: buffer.anchor_before(buffer_range.start)
435 // ..buffer.anchor_before(buffer_range.end),
436 // head_byte_range,
437 // })
438 }
439}
440
441#[cfg(test)]
442mod tests {
443 use super::*;
444 use text::Buffer;
445 use unindent::Unindent as _;
446
447 #[gpui::test]
448 fn test_buffer_diff_simple() {
449 let head_text = "
450 one
451 two
452 three
453 "
454 .unindent();
455
456 let buffer_text = "
457 one
458 hello
459 three
460 "
461 .unindent();
462
463 let mut buffer = Buffer::new(0, 0, buffer_text);
464 let diff = BufferDiff::new(&Some(head_text.clone()), &buffer);
465 assert_hunks(&diff, &buffer, &head_text, &[(1..2, "two\n")]);
466
467 buffer.edit([(0..0, "point five\n")]);
468 assert_hunks(&diff, &buffer, &head_text, &[(2..3, "two\n")]);
469 }
470
471 #[track_caller]
472 fn assert_hunks(
473 diff: &BufferDiff,
474 buffer: &BufferSnapshot,
475 head_text: &str,
476 expected_hunks: &[(Range<u32>, &str)],
477 ) {
478 let hunks = diff.snapshot.hunks(buffer).collect::<Vec<_>>();
479 assert_eq!(
480 hunks.len(),
481 expected_hunks.len(),
482 "actual hunks are {hunks:#?}"
483 );
484
485 let diff_iter = hunks.iter().enumerate();
486 for ((index, hunk), (expected_range, expected_str)) in diff_iter.zip(expected_hunks) {
487 assert_eq!(&hunk.buffer_range, expected_range, "for hunk {index}");
488 assert_eq!(
489 &head_text[hunk.head_byte_range.clone()],
490 *expected_str,
491 "for hunk {index}"
492 );
493 }
494 }
495
496 // use rand::rngs::StdRng;
497 // #[gpui::test(iterations = 100)]
498 // fn test_buffer_diff_random(mut rng: StdRng) {}
499}