1use std::ops::Range;
2
3use sum_tree::{Bias, SumTree};
4use text::{Anchor, BufferSnapshot, OffsetRangeExt, Point, Rope, ToPoint};
5
6pub use git2 as libgit;
7use libgit::{DiffOptions as GitOptions, Patch as GitPatch};
8
9#[derive(Debug, Clone, Copy)]
10pub enum DiffHunkStatus {
11 Added,
12 Modified,
13 Removed,
14}
15
16#[derive(Debug, Clone, PartialEq, Eq)]
17pub struct DiffHunk<T> {
18 pub buffer_range: Range<T>,
19 pub head_range: Range<u32>,
20}
21
22impl DiffHunk<u32> {
23 pub fn status(&self) -> DiffHunkStatus {
24 if self.head_range.is_empty() {
25 DiffHunkStatus::Added
26 } else if self.buffer_range.is_empty() {
27 DiffHunkStatus::Removed
28 } else {
29 DiffHunkStatus::Modified
30 }
31 }
32}
33
34impl sum_tree::Item for DiffHunk<Anchor> {
35 type Summary = DiffHunkSummary;
36
37 fn summary(&self) -> Self::Summary {
38 DiffHunkSummary {
39 buffer_range: self.buffer_range.clone(),
40 head_range: self.head_range.clone(),
41 }
42 }
43}
44
45#[derive(Debug, Default, Clone)]
46pub struct DiffHunkSummary {
47 buffer_range: Range<Anchor>,
48 head_range: Range<u32>,
49}
50
51impl sum_tree::Summary for DiffHunkSummary {
52 type Context = text::BufferSnapshot;
53
54 fn add_summary(&mut self, other: &Self, _: &Self::Context) {
55 self.head_range.start = self.head_range.start.min(other.head_range.start);
56 self.head_range.end = self.head_range.end.max(other.head_range.end);
57 }
58}
59
60#[derive(Debug, Default, Clone, PartialEq, Eq, PartialOrd, Ord)]
61struct HunkHeadEnd(u32);
62
63impl<'a> sum_tree::Dimension<'a, DiffHunkSummary> for HunkHeadEnd {
64 fn add_summary(&mut self, summary: &'a DiffHunkSummary, _: &text::BufferSnapshot) {
65 self.0 = summary.head_range.end;
66 }
67
68 fn from_summary(summary: &'a DiffHunkSummary, _: &text::BufferSnapshot) -> Self {
69 HunkHeadEnd(summary.head_range.end)
70 }
71}
72
73#[derive(Debug, Default, Clone, PartialEq, Eq, PartialOrd, Ord)]
74struct HunkBufferEnd(u32);
75
76impl<'a> sum_tree::Dimension<'a, DiffHunkSummary> for HunkBufferEnd {
77 fn add_summary(&mut self, summary: &'a DiffHunkSummary, buffer: &text::BufferSnapshot) {
78 self.0 = summary.buffer_range.end.to_point(buffer).row;
79 }
80
81 fn from_summary(summary: &'a DiffHunkSummary, buffer: &text::BufferSnapshot) -> Self {
82 HunkBufferEnd(summary.buffer_range.end.to_point(buffer).row)
83 }
84}
85
86struct HunkIter<'a> {
87 index: usize,
88 patch: GitPatch<'a>,
89}
90
91impl<'a> HunkIter<'a> {
92 fn diff(head: &'a [u8], current: &'a [u8]) -> Option<Self> {
93 let mut options = GitOptions::default();
94 options.context_lines(0);
95 let patch = match GitPatch::from_buffers(head, None, current, None, Some(&mut options)) {
96 Ok(patch) => patch,
97 Err(_) => return None,
98 };
99
100 Some(HunkIter { index: 0, patch })
101 }
102
103 fn next(&mut self, buffer: &BufferSnapshot) -> Option<DiffHunk<Anchor>> {
104 if self.index >= self.patch.num_hunks() {
105 return None;
106 }
107
108 let (hunk, _) = match self.patch.hunk(self.index) {
109 Ok(it) => it,
110 Err(_) => return None,
111 };
112
113 let new_start = hunk.new_start() - 1;
114 let new_end = new_start + hunk.new_lines();
115 let start_anchor = buffer.anchor_at(Point::new(new_start, 0), Bias::Left);
116 let end_anchor = buffer.anchor_at(Point::new(new_end, 0), Bias::Left);
117 let buffer_range = start_anchor..end_anchor;
118
119 //This is probably wrong? When does this trigger? Should buffer range also do this?
120 let head_range = if hunk.old_start() == 0 {
121 0..0
122 } else {
123 let old_start = hunk.old_start() - 1;
124 let old_end = old_start + hunk.old_lines();
125 old_start..old_end
126 };
127
128 self.index += 1;
129 Some(DiffHunk {
130 buffer_range,
131 head_range,
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 println!("{} hunks overall", self.tree.iter().count());
148
149 self.tree.iter().filter_map(move |hunk| {
150 let range = hunk.buffer_range.to_point(&buffer);
151
152 if range.start.row < query_row_range.end && query_row_range.start < range.end.row {
153 let end_row = if range.end.column > 0 {
154 range.end.row + 1
155 } else {
156 range.end.row
157 };
158
159 Some(DiffHunk {
160 buffer_range: range.start.row..end_row,
161 head_range: hunk.head_range.clone(),
162 })
163 } else {
164 None
165 }
166 })
167 }
168
169 #[cfg(test)]
170 fn hunks<'a>(&'a self, text: &'a BufferSnapshot) -> impl 'a + Iterator<Item = DiffHunk<u32>> {
171 self.hunks_in_range(0..u32::MAX, text)
172 }
173}
174
175pub struct BufferDiff {
176 last_update_version: clock::Global,
177 snapshot: BufferDiffSnapshot,
178}
179
180impl BufferDiff {
181 pub fn new(head_text: &Option<String>, buffer: &text::BufferSnapshot) -> BufferDiff {
182 let hunks = if let Some(head_text) = head_text {
183 let buffer_string = buffer.as_rope().to_string();
184 let buffer_bytes = buffer_string.as_bytes();
185
186 let iter = HunkIter::diff(head_text.as_bytes(), buffer_bytes);
187 if let Some(mut iter) = iter {
188 let mut hunks = SumTree::new();
189 while let Some(hunk) = iter.next(buffer) {
190 hunks.push(hunk, buffer);
191 }
192 hunks
193 } else {
194 SumTree::new()
195 }
196 } else {
197 SumTree::new()
198 };
199
200 BufferDiff {
201 last_update_version: buffer.version().clone(),
202 snapshot: BufferDiffSnapshot { tree: hunks },
203 }
204 }
205
206 pub fn snapshot(&self) -> BufferDiffSnapshot {
207 self.snapshot.clone()
208 }
209
210 pub fn update(&mut self, head: &Rope, buffer: &text::BufferSnapshot) {
211 let expand_by = 20;
212 let combine_distance = 5;
213
214 struct EditRange {
215 head_start: u32,
216 head_end: u32,
217 buffer_start: u32,
218 buffer_end: u32,
219 }
220
221 let mut ranges = Vec::<EditRange>::new();
222
223 for edit in buffer.edits_since::<Point>(&self.last_update_version) {
224 //This bit is extremely wrong, this is not where these row lines should come from
225 let head_start = edit.old.start.row.saturating_sub(expand_by);
226 let head_end = (edit.old.end.row + expand_by).min(head.summary().lines.row + 1);
227
228 let buffer_start = edit.new.start.row.saturating_sub(expand_by);
229 let buffer_end = (edit.new.end.row + expand_by).min(buffer.row_count());
230
231 if let Some(last_range) = ranges.last_mut() {
232 let head_distance = last_range.head_end.abs_diff(head_end);
233 let buffer_distance = last_range.buffer_end.abs_diff(buffer_end);
234
235 if head_distance <= combine_distance || buffer_distance <= combine_distance {
236 last_range.head_start = last_range.head_start.min(head_start);
237 last_range.head_end = last_range.head_end.max(head_end);
238
239 last_range.buffer_start = last_range.buffer_start.min(buffer_start);
240 last_range.buffer_end = last_range.buffer_end.max(buffer_end);
241 } else {
242 ranges.push(EditRange {
243 head_start,
244 head_end,
245 buffer_start,
246 buffer_end,
247 });
248 }
249 } else {
250 ranges.push(EditRange {
251 head_start,
252 head_end,
253 buffer_start,
254 buffer_end,
255 });
256 }
257 }
258
259 self.last_update_version = buffer.version().clone();
260
261 let mut new_hunks = SumTree::new();
262 let mut cursor = self.snapshot.tree.cursor::<HunkHeadEnd>();
263
264 for range in ranges {
265 let head_range = range.head_start..range.head_end;
266 let head_slice = head.slice_rows(head_range.clone());
267 let head_str = head_slice.to_string();
268
269 let buffer_range = range.buffer_start..range.buffer_end;
270 let buffer_slice = buffer.as_rope().slice_rows(buffer_range.clone());
271 let buffer_str = buffer_slice.to_string();
272
273 println!("diffing head {:?}, buffer {:?}", head_range, buffer_range);
274
275 let mut iter = match HunkIter::diff(head_str.as_bytes(), buffer_str.as_bytes()) {
276 Some(iter) => iter,
277 None => continue,
278 };
279
280 while let Some(hunk) = iter.next(buffer) {
281 println!("hunk");
282 let prefix = cursor.slice(&HunkHeadEnd(hunk.head_range.end), Bias::Right, buffer);
283 println!("prefix len: {}", prefix.iter().count());
284 new_hunks.extend(prefix.iter().cloned(), buffer);
285
286 new_hunks.push(hunk.clone(), buffer);
287
288 cursor.seek(&HunkHeadEnd(hunk.head_range.end), Bias::Right, buffer);
289 println!("item: {:?}", cursor.item());
290 if let Some(item) = cursor.item() {
291 if item.head_range.end <= hunk.head_range.end {
292 println!("skipping");
293 cursor.next(buffer);
294 }
295 }
296 }
297 }
298
299 new_hunks.extend(
300 cursor
301 .suffix(buffer)
302 .iter()
303 .map(|i| {
304 println!("extending with {i:?}");
305 i
306 })
307 .cloned(),
308 buffer,
309 );
310 drop(cursor);
311
312 self.snapshot.tree = new_hunks;
313 }
314}
315
316#[derive(Debug, Clone, Copy)]
317pub enum GitDiffEdit {
318 Added(u32),
319 Modified(u32),
320 Removed(u32),
321}
322
323impl GitDiffEdit {
324 pub fn line(self) -> u32 {
325 use GitDiffEdit::*;
326
327 match self {
328 Added(line) | Modified(line) | Removed(line) => line,
329 }
330 }
331}
332
333#[cfg(test)]
334mod tests {
335 use super::*;
336 use text::Buffer;
337 use unindent::Unindent as _;
338
339 #[gpui::test]
340 fn test_buffer_diff_simple() {
341 let head_text = "
342 one
343 two
344 three
345 "
346 .unindent();
347
348 let buffer_text = "
349 one
350 hello
351 three
352 "
353 .unindent();
354
355 let mut buffer = Buffer::new(0, 0, buffer_text);
356 let diff = BufferDiff::new(&Some(head_text.clone()), &buffer);
357 assert_eq!(
358 diff.snapshot.hunks(&buffer).collect::<Vec<_>>(),
359 &[DiffHunk {
360 buffer_range: 1..2,
361 head_range: 1..2
362 }]
363 );
364
365 buffer.edit([(0..0, "point five\n")]);
366 assert_eq!(
367 diff.snapshot.hunks(&buffer).collect::<Vec<_>>(),
368 &[DiffHunk {
369 buffer_range: 2..3,
370 head_range: 1..2
371 }]
372 );
373 }
374
375 // use rand::rngs::StdRng;
376 // #[gpui::test(iterations = 100)]
377 // fn test_buffer_diff_random(mut rng: StdRng) {}
378}