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
359 match (kind, &mut buffer_byte_range, &mut head_byte_range) {
360 (GitDiffLineType::Addition, None, _) => {
361 let end = content_offset + line.content().len() as isize;
362 buffer_byte_range = Some(content_offset as usize..end as usize);
363 }
364
365 (GitDiffLineType::Addition, Some(buffer_byte_range), _) => {
366 let end = content_offset + line.content().len() as isize;
367 buffer_byte_range.end = end as usize;
368 }
369
370 (GitDiffLineType::Deletion, _, None) => {
371 let end = content_offset + line.content().len() as isize;
372 head_byte_range = Some(content_offset as usize..end as usize);
373 }
374
375 (GitDiffLineType::Deletion, _, Some(head_byte_range)) => {
376 let end = content_offset + line.content().len() as isize;
377 head_byte_range.end = end as usize;
378 }
379
380 _ => {}
381 }
382 }
383
384 //unwrap_or deletion without addition
385 let buffer_byte_range = buffer_byte_range.unwrap_or(0..0);
386 //unwrap_or addition without deletion
387 let head_byte_range = head_byte_range.unwrap_or(0..0);
388
389 DiffHunk {
390 buffer_range: buffer.anchor_before(buffer_byte_range.start)
391 ..buffer.anchor_before(buffer_byte_range.end),
392 head_byte_range,
393 }
394 }
395
396 fn name() {
397 // if self.hunk_index >= self.patch.num_hunks() {
398 // return None;
399 // }
400
401 // let mut line_iter = HunkLineIter::new(&self.patch, self.hunk_index);
402 // let line = line_iter.find(|line| {
403 // matches!(
404 // line.origin_value(),
405 // GitDiffLineType::Addition | GitDiffLineType::Deletion
406 // )
407 // })?;
408
409 // //For the first line of a hunk the content offset is equally valid for an addition or deletion
410 // let content_offset = line.content_offset() as usize;
411
412 // let mut buffer_range = content_offset..content_offset;
413 // let mut head_byte_range = match line.origin_value() {
414 // GitDiffLineType::Addition => content_offset..content_offset,
415 // GitDiffLineType::Deletion => content_offset..content_offset + line.content().len(),
416 // _ => unreachable!(),
417 // };
418
419 // for line in line_iter {
420 // match line.origin_value() {
421 // GitDiffLineType::Addition => {
422 // // buffer_range.end =
423 // }
424
425 // GitDiffLineType::Deletion => {}
426
427 // _ => continue,
428 // }
429 // }
430
431 // self.hunk_index += 1;
432 // Some(DiffHunk {
433 // buffer_range: buffer.anchor_before(buffer_range.start)
434 // ..buffer.anchor_before(buffer_range.end),
435 // head_byte_range,
436 // })
437 }
438}
439
440#[cfg(test)]
441mod tests {
442 use super::*;
443 use text::Buffer;
444 use unindent::Unindent as _;
445
446 #[gpui::test]
447 fn test_buffer_diff_simple() {
448 let head_text = "
449 one
450 two
451 three
452 "
453 .unindent();
454
455 let buffer_text = "
456 one
457 hello
458 three
459 "
460 .unindent();
461
462 let mut buffer = Buffer::new(0, 0, buffer_text);
463 let diff = BufferDiff::new(&Some(head_text.clone()), &buffer);
464 assert_hunks(&diff, &buffer, &head_text, &[(1..2, "two\n")]);
465
466 buffer.edit([(0..0, "point five\n")]);
467 assert_hunks(&diff, &buffer, &head_text, &[(2..3, "two\n")]);
468 }
469
470 #[track_caller]
471 fn assert_hunks(
472 diff: &BufferDiff,
473 buffer: &BufferSnapshot,
474 head_text: &str,
475 expected_hunks: &[(Range<u32>, &str)],
476 ) {
477 let hunks = diff.snapshot.hunks(buffer).collect::<Vec<_>>();
478 assert_eq!(
479 hunks.len(),
480 expected_hunks.len(),
481 "actual hunks are {hunks:#?}"
482 );
483
484 let diff_iter = hunks.iter().enumerate();
485 for ((index, hunk), (expected_range, expected_str)) in diff_iter.zip(expected_hunks) {
486 assert_eq!(&hunk.buffer_range, expected_range, "for hunk {index}");
487 assert_eq!(
488 &head_text[hunk.head_byte_range.clone()],
489 *expected_str,
490 "for hunk {index}"
491 );
492 }
493 }
494
495 // use rand::rngs::StdRng;
496 // #[gpui::test(iterations = 100)]
497 // fn test_buffer_diff_random(mut rng: StdRng) {}
498}