dogfood
Jump to…
snowcorepublic2 bookmarks
snowfix: 500 error because of database is patchedyuzpxzopsouq1mo
mainroot / crates / df-store / src / git / diff.rsBlameRaw
1//! Diff computation.
2//!
3//! Spec §8: Myers diff, 3 lines of context, and hard limits — "refuse to render
4//! diffs over 5000 files or 100k lines and offer the patch download instead. A
5//! pathological diff should degrade, not take the process down."
6//!
7//! Line-level diffing uses `similar` rather than `gix`'s blob differ so that
8//! hunk construction and the intra-line word diff share one implementation.
9
10use similar::{ChangeTag, TextDiff};
11
12use crate::git::convert;
13use crate::{
14 ChangeKind, Diff, DiffLine, DiffLineKind, DiffOpts, FileDiff, Hunk, Result, RevId, StoreError,
15};
16
17/// Compute a diff between two revisions.
18pub fn compute(
19 repo: &gix::Repository,
20 from: &RevId,
21 to: &RevId,
22 opts: DiffOpts,
23) -> Result<Diff> {
24 let from_commit = convert::find_commit(repo, from)?;
25 let from_tree = from_commit
26 .tree()
27 .map_err(|e| StoreError::Other(anyhow::anyhow!("reading tree: {e}")))?;
28
29 compute_from_tree(repo, from_tree, to, opts)
30}
31
32/// Diff a revision against its first parent, or an empty tree if it is a root.
33pub fn compute_from_parent(
34 repo: &gix::Repository,
35 rev: &RevId,
36 opts: DiffOpts,
37) -> Result<Diff> {
38 let commit = convert::find_commit(repo, rev)?;
39
40 let base_tree = match commit.parent_ids().next() {
41 Some(parent) => repo
42 .find_object(parent.detach())
43 .map_err(|e| StoreError::Other(anyhow::anyhow!("finding parent: {e}")))?
44 .try_into_commit()
45 .map_err(|_| StoreError::NoSuchRevision)?
46 .tree()
47 .map_err(|e| StoreError::Other(anyhow::anyhow!("reading parent tree: {e}")))?,
48 // A root commit: everything in it is an addition.
49 None => repo.empty_tree(),
50 };
51
52 compute_from_tree(repo, base_tree, rev, opts)
53}
54
55fn compute_from_tree(
56 repo: &gix::Repository,
57 from_tree: gix::Tree<'_>,
58 to: &RevId,
59 opts: DiffOpts,
60) -> Result<Diff> {
61 let to_commit = convert::find_commit(repo, to)?;
62 let to_tree = to_commit
63 .tree()
64 .map_err(|e| StoreError::Other(anyhow::anyhow!("reading tree: {e}")))?;
65
66 // Collect the changed paths first, so the file-count limit is applied
67 // before any content is read.
68 let mut changes: Vec<PathChange> = Vec::new();
69 let mut truncated = false;
70
71 from_tree
72 .changes()
73 .map_err(|e| StoreError::Other(anyhow::anyhow!("diffing trees: {e}")))?
74 .for_each_to_obtain_tree(&to_tree, |change| {
75 if changes.len() >= opts.max_files {
76 truncated = true;
77 return Ok::<_, std::convert::Infallible>(
78 gix::object::tree::diff::Action::Cancel,
79 );
80 }
81
82 let path = change.location().to_string();
83
84 // jj conflict artefacts are storage detail, never user-facing.
85 if path.starts_with(".jjconflict-") || path == "JJ-CONFLICT-README" {
86 return Ok(gix::object::tree::diff::Action::Continue);
87 }
88
89 use gix::object::tree::diff::Change;
90
91 // Blobs only. The walk reports the directories on the way down as
92 // well as the files inside them, and a tree entry has no content to
93 // diff — it used to reach the renderer as a "binary file" with no
94 // hunks, so a change touching four crates listed eleven phantom
95 // files nobody edited. `is_blob` also excludes symlinks and
96 // submodule gitlinks, which is what the old check was reaching for.
97 let pc = match change {
98 Change::Addition { entry_mode, id, .. } => {
99 entry_mode.is_blob().then(|| PathChange {
100 path: path.clone(),
101 old_path: None,
102 kind: ChangeKind::Added,
103 old_id: None,
104 new_id: Some(id.detach()),
105 })
106 }
107 Change::Deletion { entry_mode, id, .. } => {
108 entry_mode.is_blob().then(|| PathChange {
109 path: path.clone(),
110 old_path: None,
111 kind: ChangeKind::Deleted,
112 old_id: Some(id.detach()),
113 new_id: None,
114 })
115 }
116 Change::Modification {
117 entry_mode,
118 previous_id,
119 id,
120 ..
121 } => entry_mode.is_blob().then(|| PathChange {
122 path: path.clone(),
123 old_path: None,
124 kind: ChangeKind::Modified,
125 old_id: Some(previous_id.detach()),
126 new_id: Some(id.detach()),
127 }),
128 Change::Rewrite {
129 entry_mode,
130 source_location,
131 source_id,
132 id,
133 ..
134 } => entry_mode.is_blob().then(|| PathChange {
135 path: path.clone(),
136 old_path: Some(source_location.to_string()),
137 kind: ChangeKind::Renamed,
138 old_id: Some(source_id.detach()),
139 new_id: Some(id.detach()),
140 }),
141 };
142
143 if let Some(pc) = pc {
144 changes.push(pc);
145 }
146 Ok(gix::object::tree::diff::Action::Continue)
147 })
148 .map_err(|e| StoreError::Other(anyhow::anyhow!("walking tree diff: {e}")))?;
149
150 let mut out = Diff {
151 files: Vec::with_capacity(changes.len()),
152 truncated,
153 total_additions: 0,
154 total_deletions: 0,
155 };
156
157 let mut budget = opts.max_lines;
158
159 for c in changes {
160 let old = read_blob(repo, c.old_id);
161 let new = read_blob(repo, c.new_id);
162
163 let binary = old.as_deref().is_some_and(is_binary)
164 || new.as_deref().is_some_and(is_binary);
165
166 let mut fd = FileDiff {
167 path: c.path,
168 old_path: c.old_path,
169 kind: c.kind,
170 binary,
171 additions: 0,
172 deletions: 0,
173 hunks: Vec::new(),
174 };
175
176 if !binary {
177 let old_text = old.as_deref().map(String::from_utf8_lossy).unwrap_or_default();
178 let new_text = new.as_deref().map(String::from_utf8_lossy).unwrap_or_default();
179
180 let (hunks, adds, dels, used) =
181 build_hunks(&old_text, &new_text, opts.context_lines, budget);
182
183 fd.hunks = hunks;
184 fd.additions = adds;
185 fd.deletions = dels;
186
187 budget = budget.saturating_sub(used);
188 if budget == 0 {
189 out.truncated = true;
190 }
191 }
192
193 out.total_additions += fd.additions;
194 out.total_deletions += fd.deletions;
195 out.files.push(fd);
196
197 if budget == 0 {
198 break;
199 }
200 }
201
202 Ok(out)
203}
204
205struct PathChange {
206 path: String,
207 old_path: Option<String>,
208 kind: ChangeKind,
209 old_id: Option<gix::ObjectId>,
210 new_id: Option<gix::ObjectId>,
211}
212
213fn read_blob(repo: &gix::Repository, id: Option<gix::ObjectId>) -> Option<Vec<u8>> {
214 let id = id?;
215 repo.find_object(id).ok().map(|o| o.data.clone())
216}
217
218fn is_binary(data: &[u8]) -> bool {
219 data.iter().take(8000).any(|&b| b == 0)
220}
221
222/// Build hunks with the requested context, stopping once `budget` lines are
223/// emitted.
224///
225/// Returns (hunks, additions, deletions, lines_used).
226fn build_hunks(
227 old: &str,
228 new: &str,
229 context: u32,
230 budget: usize,
231) -> (Vec<Hunk>, usize, usize, usize) {
232 let diff = TextDiff::from_lines(old, new);
233
234 let mut hunks = Vec::new();
235 let mut additions = 0usize;
236 let mut deletions = 0usize;
237 let mut used = 0usize;
238
239 for group in diff.grouped_ops(context as usize).iter() {
240 if used >= budget {
241 break;
242 }
243
244 let mut lines = Vec::new();
245 let (mut old_start, mut new_start) = (0u32, 0u32);
246 let (mut old_len, mut new_len) = (0u32, 0u32);
247 let mut first = true;
248
249 for op in group {
250 for change in diff.iter_inline_changes(op) {
251 let kind = match change.tag() {
252 ChangeTag::Equal => DiffLineKind::Context,
253 ChangeTag::Insert => DiffLineKind::Added,
254 ChangeTag::Delete => DiffLineKind::Deleted,
255 };
256
257 let old_lineno = change.old_index().map(|i| i as u32 + 1);
258 let new_lineno = change.new_index().map(|i| i as u32 + 1);
259
260 if first {
261 // Hunk headers are 1-based; an empty side reports 0.
262 old_start = old_lineno.unwrap_or(0);
263 new_start = new_lineno.unwrap_or(0);
264 first = false;
265 }
266
267 match kind {
268 DiffLineKind::Added => {
269 additions += 1;
270 new_len += 1;
271 }
272 DiffLineKind::Deleted => {
273 deletions += 1;
274 old_len += 1;
275 }
276 DiffLineKind::Context => {
277 old_len += 1;
278 new_len += 1;
279 }
280 }
281
282 // `iter_strings_lossy` yields the line already segmented into
283 // runs, flagged with whether each run is part of the intra-line
284 // change. Capturing it here is free — the inline diff has
285 // already been computed to produce the line at all.
286 let mut spans: Vec<crate::DiffSpan> = change
287 .iter_strings_lossy()
288 .map(|(emphasis, value)| crate::DiffSpan {
289 text: value.trim_end_matches('\n').to_string(),
290 emphasis,
291 })
292 .filter(|s| !s.text.is_empty())
293 .collect();
294
295 let content = change.to_string().trim_end_matches('\n').to_string();
296
297 // A context line has nothing emphasised, and an unchanged line
298 // that came back as many runs is just noise for the renderer.
299 if spans.iter().all(|s| !s.emphasis) {
300 spans = if content.is_empty() {
301 Vec::new()
302 } else {
303 vec![crate::DiffSpan { text: content.clone(), emphasis: false }]
304 };
305 }
306
307 lines.push(DiffLine {
308 kind,
309 old_lineno,
310 new_lineno,
311 // Trailing newline is structural, not content.
312 content,
313 spans,
314 });
315
316 used += 1;
317 if used >= budget {
318 break;
319 }
320 }
321 if used >= budget {
322 break;
323 }
324 }
325
326 if !lines.is_empty() {
327 hunks.push(Hunk {
328 old_start,
329 old_lines: old_len,
330 new_start,
331 new_lines: new_len,
332 lines,
333 });
334 }
335 }
336
337 (hunks, additions, deletions, used)
338}
339
340#[cfg(test)]
341mod tests {
342 use super::*;
343
344 #[test]
345 fn counts_additions_and_deletions() {
346 let (hunks, adds, dels, _) = build_hunks("a\nb\nc\n", "a\nB\nc\n", 3, 10_000);
347 assert_eq!(adds, 1);
348 assert_eq!(dels, 1);
349 assert_eq!(hunks.len(), 1);
350 }
351
352 #[test]
353 fn an_unchanged_file_produces_no_hunks() {
354 let (hunks, adds, dels, _) = build_hunks("same\n", "same\n", 3, 10_000);
355 assert!(hunks.is_empty());
356 assert_eq!((adds, dels), (0, 0));
357 }
358
359 #[test]
360 fn collapses_unchanged_regions_to_the_context_window() {
361 // 100 identical lines with one change in the middle must not emit 100
362 // lines — that is the whole point of grouping.
363 let old: String = (0..100).map(|i| format!("line {i}\n")).collect();
364 let new = old.replace("line 50\n", "line FIFTY\n");
365
366 let (hunks, adds, dels, used) = build_hunks(&old, &new, 3, 10_000);
367 assert_eq!((adds, dels), (1, 1));
368 assert_eq!(hunks.len(), 1);
369 // 3 context either side + the changed pair.
370 assert!(used <= 10, "expected a small hunk, emitted {used} lines");
371 }
372
373 #[test]
374 fn respects_the_line_budget() {
375 // A pathological diff must degrade, not run away (spec §8).
376 let old: String = (0..5000).map(|i| format!("old {i}\n")).collect();
377 let new: String = (0..5000).map(|i| format!("new {i}\n")).collect();
378
379 let (_, _, _, used) = build_hunks(&old, &new, 3, 100);
380 assert!(used <= 100, "budget exceeded: {used}");
381 }
382
383 #[test]
384 fn hunk_line_numbers_are_one_based() {
385 let (hunks, _, _, _) = build_hunks("a\nb\n", "a\nc\n", 3, 10_000);
386 let h = &hunks[0];
387 assert_eq!(h.old_start, 1);
388 assert_eq!(h.new_start, 1);
389 let first = &h.lines[0];
390 assert_eq!(first.old_lineno, Some(1));
391 assert_eq!(first.new_lineno, Some(1));
392 }
393
394 #[test]
395 fn added_lines_have_no_old_number_and_vice_versa() {
396 let (hunks, _, _, _) = build_hunks("", "brand new\n", 3, 10_000);
397 let added = hunks[0]
398 .lines
399 .iter()
400 .find(|l| l.kind == DiffLineKind::Added)
401 .expect("an added line");
402 assert_eq!(added.old_lineno, None);
403 assert!(added.new_lineno.is_some());
404 }
405
406 #[test]
407 fn binary_detection_matches_the_blob_heuristic() {
408 assert!(is_binary(b"\0"));
409 assert!(!is_binary(b"text"));
410 }
411
412 #[test]
413 fn content_excludes_the_trailing_newline() {
414 let (hunks, _, _, _) = build_hunks("a\n", "b\n", 3, 10_000);
415 for l in &hunks[0].lines {
416 assert!(!l.content.ends_with('\n'), "content kept its newline: {l:?}");
417 }
418 }
419}

419 lines · Rust