1use std::ops::Range;
2
3use sum_tree::SumTree;
4use text::{Anchor, BufferSnapshot, OffsetRangeExt, Point};
5
6pub use git2 as libgit;
7use libgit::{DiffLineType as GitDiffLineType, 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_byte_range: Range<usize>,
20}
21
22impl DiffHunk<u32> {
23 pub fn status(&self) -> DiffHunkStatus {
24 if self.head_byte_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 }
41 }
42}
43
44#[derive(Debug, Default, Clone)]
45pub struct DiffHunkSummary {
46 buffer_range: Range<Anchor>,
47}
48
49impl sum_tree::Summary for DiffHunkSummary {
50 type Context = text::BufferSnapshot;
51
52 fn add_summary(&mut self, other: &Self, buffer: &Self::Context) {
53 self.buffer_range.start = self
54 .buffer_range
55 .start
56 .min(&other.buffer_range.start, buffer);
57 self.buffer_range.end = self.buffer_range.end.max(&other.buffer_range.end, buffer);
58 }
59}
60
61#[derive(Clone)]
62pub struct BufferDiff {
63 last_buffer_version: Option<clock::Global>,
64 tree: SumTree<DiffHunk<Anchor>>,
65}
66
67impl BufferDiff {
68 pub fn new() -> BufferDiff {
69 BufferDiff {
70 last_buffer_version: None,
71 tree: SumTree::new(),
72 }
73 }
74
75 pub fn hunks_in_range<'a>(
76 &'a self,
77 query_row_range: Range<u32>,
78 buffer: &'a BufferSnapshot,
79 ) -> impl 'a + Iterator<Item = DiffHunk<u32>> {
80 let start = buffer.anchor_before(Point::new(query_row_range.start, 0));
81 let end = buffer.anchor_after(Point::new(query_row_range.end, 0));
82
83 let mut cursor = self.tree.filter::<_, DiffHunkSummary>(move |summary| {
84 let before_start = summary.buffer_range.end.cmp(&start, buffer).is_lt();
85 let after_end = summary.buffer_range.start.cmp(&end, buffer).is_gt();
86 !before_start && !after_end
87 });
88
89 std::iter::from_fn(move || {
90 cursor.next(buffer);
91 let hunk = cursor.item()?;
92
93 let range = hunk.buffer_range.to_point(buffer);
94 let end_row = if range.end.column > 0 {
95 range.end.row + 1
96 } else {
97 range.end.row
98 };
99
100 Some(DiffHunk {
101 buffer_range: range.start.row..end_row,
102 head_byte_range: hunk.head_byte_range.clone(),
103 })
104 })
105 }
106
107 pub fn needs_update(&self, buffer: &text::BufferSnapshot) -> bool {
108 match &self.last_buffer_version {
109 Some(last) => buffer.version().changed_since(last),
110 None => true,
111 }
112 }
113
114 pub async fn update(&mut self, head_text: &str, buffer: &text::BufferSnapshot) {
115 let mut tree = SumTree::new();
116
117 let buffer_text = buffer.as_rope().to_string();
118 let patch = Self::diff(&head_text, &buffer_text);
119
120 if let Some(patch) = patch {
121 let mut divergence = 0;
122 for hunk_index in 0..patch.num_hunks() {
123 let hunk = Self::process_patch_hunk(&patch, hunk_index, buffer, &mut divergence);
124 tree.push(hunk, buffer);
125 }
126 }
127
128 self.tree = tree;
129 self.last_buffer_version = Some(buffer.version().clone());
130 }
131
132 #[cfg(test)]
133 fn hunks<'a>(&'a self, text: &'a BufferSnapshot) -> impl 'a + Iterator<Item = DiffHunk<u32>> {
134 self.hunks_in_range(0..u32::MAX, text)
135 }
136
137 fn diff<'a>(head: &'a str, current: &'a str) -> Option<GitPatch<'a>> {
138 let mut options = GitOptions::default();
139 options.context_lines(0);
140
141 let patch = GitPatch::from_buffers(
142 head.as_bytes(),
143 None,
144 current.as_bytes(),
145 None,
146 Some(&mut options),
147 );
148
149 match patch {
150 Ok(patch) => Some(patch),
151
152 Err(err) => {
153 log::error!("`GitPatch::from_buffers` failed: {}", err);
154 None
155 }
156 }
157 }
158
159 fn process_patch_hunk<'a>(
160 patch: &GitPatch<'a>,
161 hunk_index: usize,
162 buffer: &text::BufferSnapshot,
163 buffer_row_divergence: &mut i64,
164 ) -> DiffHunk<Anchor> {
165 let line_item_count = patch.num_lines_in_hunk(hunk_index).unwrap();
166 assert!(line_item_count > 0);
167
168 let mut first_deletion_buffer_row: Option<u32> = None;
169 let mut buffer_row_range: Option<Range<u32>> = None;
170 let mut head_byte_range: Option<Range<usize>> = None;
171
172 for line_index in 0..line_item_count {
173 let line = patch.line_in_hunk(hunk_index, line_index).unwrap();
174 let kind = line.origin_value();
175 let content_offset = line.content_offset() as isize;
176 let content_len = line.content().len() as isize;
177
178 if kind == GitDiffLineType::Addition {
179 *buffer_row_divergence += 1;
180 let row = line.new_lineno().unwrap().saturating_sub(1);
181
182 match &mut buffer_row_range {
183 Some(buffer_row_range) => buffer_row_range.end = row + 1,
184 None => buffer_row_range = Some(row..row + 1),
185 }
186 }
187
188 if kind == GitDiffLineType::Deletion {
189 *buffer_row_divergence -= 1;
190 let end = content_offset + content_len;
191
192 match &mut head_byte_range {
193 Some(head_byte_range) => head_byte_range.end = end as usize,
194 None => head_byte_range = Some(content_offset as usize..end as usize),
195 }
196
197 if first_deletion_buffer_row.is_none() {
198 let old_row = line.old_lineno().unwrap().saturating_sub(1);
199 let row = old_row as i64 + *buffer_row_divergence;
200 first_deletion_buffer_row = Some(row as u32);
201 }
202 }
203 }
204
205 //unwrap_or deletion without addition
206 let buffer_row_range = buffer_row_range.unwrap_or_else(|| {
207 //we cannot have an addition-less hunk without deletion(s) or else there would be no hunk
208 let row = first_deletion_buffer_row.unwrap();
209 row..row
210 });
211
212 //unwrap_or addition without deletion
213 let head_byte_range = head_byte_range.unwrap_or(0..0);
214
215 let start = Point::new(buffer_row_range.start, 0);
216 let end = Point::new(buffer_row_range.end, 0);
217 let buffer_range = buffer.anchor_before(start)..buffer.anchor_before(end);
218 DiffHunk {
219 buffer_range,
220 head_byte_range,
221 }
222 }
223}
224
225/// Range (crossing new lines), old, new
226#[cfg(any(test, feature = "test-support"))]
227#[track_caller]
228pub fn assert_hunks<Iter>(
229 diff_hunks: Iter,
230 buffer: &BufferSnapshot,
231 head_text: &str,
232 expected_hunks: &[(Range<u32>, &str, &str)],
233) where
234 Iter: Iterator<Item = DiffHunk<u32>>,
235{
236 let actual_hunks = diff_hunks
237 .map(|hunk| {
238 (
239 hunk.buffer_range.clone(),
240 &head_text[hunk.head_byte_range],
241 buffer
242 .text_for_range(
243 Point::new(hunk.buffer_range.start, 0)
244 ..Point::new(hunk.buffer_range.end, 0),
245 )
246 .collect::<String>(),
247 )
248 })
249 .collect::<Vec<_>>();
250
251 let expected_hunks: Vec<_> = expected_hunks
252 .iter()
253 .map(|(r, s, h)| (r.clone(), *s, h.to_string()))
254 .collect();
255
256 assert_eq!(actual_hunks, expected_hunks);
257}
258
259#[cfg(test)]
260mod tests {
261 use super::*;
262 use text::Buffer;
263 use unindent::Unindent as _;
264
265 #[test]
266 fn test_buffer_diff_simple() {
267 let head_text = "
268 one
269 two
270 three
271 "
272 .unindent();
273
274 let buffer_text = "
275 one
276 HELLO
277 three
278 "
279 .unindent();
280
281 let mut buffer = Buffer::new(0, 0, buffer_text);
282 let mut diff = BufferDiff::new();
283 smol::block_on(diff.update(&head_text, &buffer));
284 assert_hunks(
285 diff.hunks(&buffer),
286 &buffer,
287 &head_text,
288 &[(1..2, "two\n", "HELLO\n")],
289 );
290
291 buffer.edit([(0..0, "point five\n")]);
292 smol::block_on(diff.update(&head_text, &buffer));
293 assert_hunks(
294 diff.hunks(&buffer),
295 &buffer,
296 &head_text,
297 &[(0..1, "", "point five\n"), (2..3, "two\n", "HELLO\n")],
298 );
299 }
300
301 #[test]
302 fn test_buffer_diff_range() {
303 let head_text = "
304 one
305 two
306 three
307 four
308 five
309 six
310 seven
311 eight
312 nine
313 ten
314 "
315 .unindent();
316
317 let buffer_text = "
318 A
319 one
320 B
321 two
322 C
323 three
324 HELLO
325 four
326 five
327 SIXTEEN
328 seven
329 eight
330 WORLD
331 nine
332
333 ten
334
335 "
336 .unindent();
337
338 let buffer = Buffer::new(0, 0, buffer_text);
339 let mut diff = BufferDiff::new();
340 smol::block_on(diff.update(&head_text, &buffer));
341 assert_eq!(diff.hunks(&buffer).count(), 8);
342
343 assert_hunks(
344 diff.hunks_in_range(7..12, &buffer),
345 &buffer,
346 &head_text,
347 &[
348 (6..7, "", "HELLO\n"),
349 (9..10, "six\n", "SIXTEEN\n"),
350 (12..13, "", "WORLD\n"),
351 ],
352 );
353 }
354}