1use std::{ops::Range, sync::Arc};
2
3use sum_tree::SumTree;
4use text::{Anchor, BufferSnapshot, OffsetRangeExt, Point, ToPoint};
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 head_range: self.head_byte_range.clone(),
41 }
42 }
43}
44
45#[derive(Debug, Default, Clone)]
46pub struct DiffHunkSummary {
47 buffer_range: Range<Anchor>,
48 head_range: Range<usize>,
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(usize);
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 HunkBufferStart(u32);
75
76impl<'a> sum_tree::Dimension<'a, DiffHunkSummary> for HunkBufferStart {
77 fn add_summary(&mut self, summary: &'a DiffHunkSummary, buffer: &text::BufferSnapshot) {
78 self.0 = summary.buffer_range.start.to_point(buffer).row;
79 }
80
81 fn from_summary(summary: &'a DiffHunkSummary, buffer: &text::BufferSnapshot) -> Self {
82 HunkBufferStart(summary.buffer_range.start.to_point(buffer).row)
83 }
84}
85
86#[derive(Debug, Default, Clone, PartialEq, Eq, PartialOrd, Ord)]
87struct HunkBufferEnd(u32);
88
89impl<'a> sum_tree::Dimension<'a, DiffHunkSummary> for HunkBufferEnd {
90 fn add_summary(&mut self, summary: &'a DiffHunkSummary, buffer: &text::BufferSnapshot) {
91 self.0 = summary.buffer_range.end.to_point(buffer).row;
92 }
93
94 fn from_summary(summary: &'a DiffHunkSummary, buffer: &text::BufferSnapshot) -> Self {
95 HunkBufferEnd(summary.buffer_range.end.to_point(buffer).row)
96 }
97}
98
99#[derive(Clone)]
100pub struct BufferDiff {
101 last_buffer_version: clock::Global,
102 tree: SumTree<DiffHunk<Anchor>>,
103}
104
105impl BufferDiff {
106 pub async fn new(head_text: Option<Arc<String>>, buffer: &text::BufferSnapshot) -> BufferDiff {
107 let mut instance = BufferDiff {
108 last_buffer_version: buffer.version().clone(),
109 tree: SumTree::new(),
110 };
111
112 if let Some(head_text) = head_text {
113 instance.update(&*head_text, buffer);
114 }
115
116 instance
117 }
118
119 pub fn hunks_in_range<'a>(
120 &'a self,
121 query_row_range: Range<u32>,
122 buffer: &'a BufferSnapshot,
123 ) -> impl 'a + Iterator<Item = DiffHunk<u32>> {
124 self.tree.iter().filter_map(move |hunk| {
125 let range = hunk.buffer_range.to_point(&buffer);
126
127 if range.start.row <= query_row_range.end && query_row_range.start <= range.end.row {
128 let end_row = if range.end.column > 0 {
129 range.end.row + 1
130 } else {
131 range.end.row
132 };
133
134 Some(DiffHunk {
135 buffer_range: range.start.row..end_row,
136 head_byte_range: hunk.head_byte_range.clone(),
137 })
138 } else {
139 None
140 }
141 })
142 }
143
144 pub fn needs_update(&self, buffer: &text::BufferSnapshot) -> bool {
145 buffer.version().changed_since(&self.last_buffer_version)
146 }
147
148 fn update(&mut self, head_text: &str, buffer: &text::BufferSnapshot) {
149 let mut tree = SumTree::new();
150
151 let buffer_text = buffer.as_rope().to_string();
152 let patch = Self::diff(&head_text, &buffer_text);
153
154 if let Some(patch) = patch {
155 let mut divergence = 0;
156 for hunk_index in 0..patch.num_hunks() {
157 let hunk = Self::process_patch_hunk(&patch, hunk_index, buffer, &mut divergence);
158 tree.push(hunk, buffer);
159 }
160 }
161
162 self.tree = tree;
163 self.last_buffer_version = buffer.version().clone();
164 }
165
166 #[cfg(test)]
167 fn hunks<'a>(&'a self, text: &'a BufferSnapshot) -> impl 'a + Iterator<Item = DiffHunk<u32>> {
168 self.hunks_in_range(0..u32::MAX, text)
169 }
170
171 fn diff<'a>(head: &'a str, current: &'a str) -> Option<GitPatch<'a>> {
172 let mut options = GitOptions::default();
173 options.context_lines(0);
174
175 let patch = GitPatch::from_buffers(
176 head.as_bytes(),
177 None,
178 current.as_bytes(),
179 None,
180 Some(&mut options),
181 );
182
183 match patch {
184 Ok(patch) => Some(patch),
185
186 Err(err) => {
187 log::error!("`GitPatch::from_buffers` failed: {}", err);
188 None
189 }
190 }
191 }
192
193 fn process_patch_hunk<'a>(
194 patch: &GitPatch<'a>,
195 hunk_index: usize,
196 buffer: &text::BufferSnapshot,
197 buffer_row_divergence: &mut i64,
198 ) -> DiffHunk<Anchor> {
199 let line_item_count = patch.num_lines_in_hunk(hunk_index).unwrap();
200 assert!(line_item_count > 0);
201
202 let mut first_deletion_buffer_row: Option<u32> = None;
203 let mut buffer_row_range: Option<Range<u32>> = None;
204 let mut head_byte_range: Option<Range<usize>> = None;
205
206 for line_index in 0..line_item_count {
207 let line = patch.line_in_hunk(hunk_index, line_index).unwrap();
208 let kind = line.origin_value();
209 let content_offset = line.content_offset() as isize;
210 let content_len = line.content().len() as isize;
211
212 if kind == GitDiffLineType::Addition {
213 *buffer_row_divergence += 1;
214 let row = line.new_lineno().unwrap().saturating_sub(1);
215
216 match &mut buffer_row_range {
217 Some(buffer_row_range) => buffer_row_range.end = row + 1,
218 None => buffer_row_range = Some(row..row + 1),
219 }
220 }
221
222 if kind == GitDiffLineType::Deletion {
223 *buffer_row_divergence -= 1;
224 let end = content_offset + content_len;
225
226 match &mut head_byte_range {
227 Some(head_byte_range) => head_byte_range.end = end as usize,
228 None => head_byte_range = Some(content_offset as usize..end as usize),
229 }
230
231 if first_deletion_buffer_row.is_none() {
232 let old_row = line.old_lineno().unwrap().saturating_sub(1);
233 let row = old_row as i64 + *buffer_row_divergence;
234 first_deletion_buffer_row = Some(row as u32);
235 }
236 }
237 }
238
239 //unwrap_or deletion without addition
240 let buffer_row_range = buffer_row_range.unwrap_or_else(|| {
241 //we cannot have an addition-less hunk without deletion(s) or else there would be no hunk
242 let row = first_deletion_buffer_row.unwrap();
243 row..row
244 });
245
246 //unwrap_or addition without deletion
247 let head_byte_range = head_byte_range.unwrap_or(0..0);
248
249 let start = Point::new(buffer_row_range.start, 0);
250 let end = Point::new(buffer_row_range.end, 0);
251 let buffer_range = buffer.anchor_before(start)..buffer.anchor_before(end);
252 DiffHunk {
253 buffer_range,
254 head_byte_range,
255 }
256 }
257}
258
259#[cfg(test)]
260mod tests {
261 use super::*;
262 use text::Buffer;
263 use unindent::Unindent as _;
264
265 #[gpui::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 diff = smol::block_on(BufferDiff::new(Some(Arc::new(head_text.clone())), &buffer));
283 assert_hunks(&diff, &buffer, &head_text, &[(1..2, "two\n")]);
284
285 buffer.edit([(0..0, "point five\n")]);
286 assert_hunks(&diff, &buffer, &head_text, &[(2..3, "two\n")]);
287 }
288
289 #[track_caller]
290 fn assert_hunks(
291 diff: &BufferDiff,
292 buffer: &BufferSnapshot,
293 head_text: &str,
294 expected_hunks: &[(Range<u32>, &str)],
295 ) {
296 let hunks = diff.hunks(buffer).collect::<Vec<_>>();
297 assert_eq!(
298 hunks.len(),
299 expected_hunks.len(),
300 "actual hunks are {hunks:#?}"
301 );
302
303 let diff_iter = hunks.iter().enumerate();
304 for ((index, hunk), (expected_range, expected_str)) in diff_iter.zip(expected_hunks) {
305 assert_eq!(&hunk.buffer_range, expected_range, "for hunk {index}");
306 assert_eq!(
307 &head_text[hunk.head_byte_range.clone()],
308 *expected_str,
309 "for hunk {index}"
310 );
311 }
312 }
313
314 // use rand::rngs::StdRng;
315 // #[gpui::test(iterations = 100)]
316 // fn test_buffer_diff_random(mut rng: StdRng) {}
317}