1use std::ops::Range;
2
3use sum_tree::SumTree;
4use text::{Anchor, BufferSnapshot, OffsetRangeExt, Point, ToOffset, 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 BufferDiffSnapshot {
101 tree: SumTree<DiffHunk<Anchor>>,
102}
103
104impl BufferDiffSnapshot {
105 pub fn hunks_in_range<'a>(
106 &'a self,
107 query_row_range: Range<u32>,
108 buffer: &'a BufferSnapshot,
109 ) -> impl 'a + Iterator<Item = DiffHunk<u32>> {
110 self.tree.iter().filter_map(move |hunk| {
111 let range = hunk.buffer_range.to_point(&buffer);
112
113 if range.start.row <= query_row_range.end && query_row_range.start <= range.end.row {
114 let end_row = if range.end.column > 0 {
115 range.end.row + 1
116 } else {
117 range.end.row
118 };
119
120 Some(DiffHunk {
121 buffer_range: range.start.row..end_row,
122 head_byte_range: hunk.head_byte_range.clone(),
123 })
124 } else {
125 None
126 }
127 })
128 }
129
130 #[cfg(test)]
131 fn hunks<'a>(&'a self, text: &'a BufferSnapshot) -> impl 'a + Iterator<Item = DiffHunk<u32>> {
132 self.hunks_in_range(0..u32::MAX, text)
133 }
134}
135
136pub struct BufferDiff {
137 snapshot: BufferDiffSnapshot,
138}
139
140impl BufferDiff {
141 pub fn new(head_text: &Option<String>, buffer: &text::BufferSnapshot) -> BufferDiff {
142 let mut instance = BufferDiff {
143 snapshot: BufferDiffSnapshot {
144 tree: SumTree::new(),
145 },
146 };
147
148 if let Some(head_text) = head_text {
149 instance.update(head_text, buffer);
150 }
151
152 instance
153 }
154
155 pub fn snapshot(&self) -> BufferDiffSnapshot {
156 self.snapshot.clone()
157 }
158
159 pub fn update(&mut self, head_text: &str, buffer: &text::BufferSnapshot) {
160 let mut tree = SumTree::new();
161
162 let buffer_text = buffer.as_rope().to_string();
163 let patch = Self::diff(&head_text, &buffer_text);
164
165 if let Some(patch) = patch {
166 for hunk_index in 0..patch.num_hunks() {
167 let hunk = Self::process_patch_hunk(&patch, hunk_index, buffer);
168 tree.push(hunk, buffer);
169 }
170 }
171
172 self.snapshot.tree = tree;
173 }
174
175 fn diff<'a>(head: &'a str, current: &'a str) -> Option<GitPatch<'a>> {
176 let mut options = GitOptions::default();
177 options.context_lines(0);
178
179 let patch = GitPatch::from_buffers(
180 head.as_bytes(),
181 None,
182 current.as_bytes(),
183 None,
184 Some(&mut options),
185 );
186
187 match patch {
188 Ok(patch) => Some(patch),
189
190 Err(err) => {
191 log::error!("`GitPatch::from_buffers` failed: {}", err);
192 None
193 }
194 }
195 }
196
197 fn process_patch_hunk<'a>(
198 patch: &GitPatch<'a>,
199 hunk_index: usize,
200 buffer: &text::BufferSnapshot,
201 ) -> DiffHunk<Anchor> {
202 let line_item_count = patch.num_lines_in_hunk(hunk_index).unwrap();
203 assert!(line_item_count > 0);
204
205 let mut first_deletion_buffer_row: Option<u32> = None;
206 let mut buffer_byte_range: Option<Range<usize>> = None;
207 let mut head_byte_range: Option<Range<usize>> = None;
208
209 for line_index in 0..line_item_count {
210 let line = patch.line_in_hunk(hunk_index, line_index).unwrap();
211 let kind = line.origin_value();
212 let content_offset = line.content_offset() as isize;
213 let content_len = line.content().len() as isize;
214
215 match (kind, &mut buffer_byte_range, &mut head_byte_range) {
216 (GitDiffLineType::Addition, None, _) => {
217 let end = content_offset + content_len;
218 buffer_byte_range = Some(content_offset as usize..end as usize);
219 }
220
221 (GitDiffLineType::Addition, Some(buffer_byte_range), _) => {
222 let end = content_offset + content_len;
223 buffer_byte_range.end = end as usize;
224 }
225
226 (GitDiffLineType::Deletion, _, None) => {
227 let end = content_offset + content_len;
228 head_byte_range = Some(content_offset as usize..end as usize);
229 }
230
231 (GitDiffLineType::Deletion, _, Some(head_byte_range)) => {
232 let end = content_offset + content_len;
233 head_byte_range.end = end as usize;
234 }
235
236 _ => {}
237 }
238
239 if kind == GitDiffLineType::Deletion && first_deletion_buffer_row.is_none() {
240 //old_lineno is guarenteed to be Some for deletions
241 //libgit gives us line numbers that are 1-indexed but also returns a 0 for some states
242 let row = line.old_lineno().unwrap().saturating_sub(1);
243 first_deletion_buffer_row = Some(row);
244 }
245 }
246
247 //unwrap_or deletion without addition
248 let buffer_byte_range = buffer_byte_range.unwrap_or_else(|| {
249 //we cannot have an addition-less hunk without deletion(s) or else there would be no hunk
250 let row = first_deletion_buffer_row.unwrap();
251 let anchor = buffer.anchor_before(Point::new(row, 0));
252 let offset = anchor.to_offset(buffer);
253 offset..offset
254 });
255
256 //unwrap_or addition without deletion
257 let head_byte_range = head_byte_range.unwrap_or(0..0);
258
259 DiffHunk {
260 buffer_range: buffer.anchor_before(buffer_byte_range.start)
261 ..buffer.anchor_before(buffer_byte_range.end),
262 head_byte_range,
263 }
264 }
265}
266
267#[cfg(test)]
268mod tests {
269 use super::*;
270 use text::Buffer;
271 use unindent::Unindent as _;
272
273 #[gpui::test]
274 fn test_buffer_diff_simple() {
275 let head_text = "
276 one
277 two
278 three
279 "
280 .unindent();
281
282 let buffer_text = "
283 one
284 hello
285 three
286 "
287 .unindent();
288
289 let mut buffer = Buffer::new(0, 0, buffer_text);
290 let diff = BufferDiff::new(&Some(head_text.clone()), &buffer);
291 assert_hunks(&diff, &buffer, &head_text, &[(1..2, "two\n")]);
292
293 buffer.edit([(0..0, "point five\n")]);
294 assert_hunks(&diff, &buffer, &head_text, &[(2..3, "two\n")]);
295 }
296
297 #[track_caller]
298 fn assert_hunks(
299 diff: &BufferDiff,
300 buffer: &BufferSnapshot,
301 head_text: &str,
302 expected_hunks: &[(Range<u32>, &str)],
303 ) {
304 let hunks = diff.snapshot.hunks(buffer).collect::<Vec<_>>();
305 assert_eq!(
306 hunks.len(),
307 expected_hunks.len(),
308 "actual hunks are {hunks:#?}"
309 );
310
311 let diff_iter = hunks.iter().enumerate();
312 for ((index, hunk), (expected_range, expected_str)) in diff_iter.zip(expected_hunks) {
313 assert_eq!(&hunk.buffer_range, expected_range, "for hunk {index}");
314 assert_eq!(
315 &head_text[hunk.head_byte_range.clone()],
316 *expected_str,
317 "for hunk {index}"
318 );
319 }
320 }
321
322 // use rand::rngs::StdRng;
323 // #[gpui::test(iterations = 100)]
324 // fn test_buffer_diff_random(mut rng: StdRng) {}
325}