Skip to content
Sign up

flagon-io/g1t

public
00

Where people and agents ship software together. The open-source git platform for the whole job: issues, agents, checks and deploys to the edge.

g1t.sh
gitagentscloudflarerustforgemcp
399 linesCodeBlameRaw
1//! Comparing two commits: which files changed, and how.
2//!
3//! Trees are walked together and identical subtrees are skipped by hash, so
4//! the cost follows the size of the change rather than the repository.
5
6use std::collections::BTreeMap;
7
8use g1t_contracts::repos::{DiffLine, EntryKind, FileDiff, FileStatus, Hunk, LineKind, TreeEntry};
9use futures_util::future::{try_join, try_join_all};
10use similar::{ChangeTag, TextDiff};
11use worker::Result;
12
13use crate::store::GitRepo;
14
15/// Beyond these the comparison is cut short and marked truncated.
16const MAX_FILES: usize = 300;
17const MAX_LINES: usize = 20_000;
18/// Files larger than this are listed without their lines.
19const MAX_FILE_BYTES: usize = 512 * 1024;
20const CONTEXT_LINES: usize = 3;
21
22/// A file that differs between the two trees.
23struct Change {
24 path: String,
25 old: Option<String>,
26 new: Option<String>,
27 old_kind: Option<EntryKind>,
28 new_kind: Option<EntryKind>,
29}
30
31async fn entries<R: GitRepo>(repo: &R, tree: Option<&str>) -> Result<BTreeMap<String, TreeEntry>> {
32 let Some(tree) = tree else {
33 return Ok(BTreeMap::new());
34 };
35 Ok(repo
36 .read_tree(tree)
37 .await?
38 .unwrap_or_default()
39 .into_iter()
40 .map(|entry| (entry.name.clone(), entry))
41 .collect())
42}
43
44/// How many files' contents are read at once.
45const READS_AT_ONCE: usize = 16;
46
47/// Collects the files that differ between two trees. Each level of the
48/// trees is read at once, since every read is a round trip to the store
49/// and the levels' trees do not depend on each other.
50async fn changed_files<R: GitRepo>(
51 repo: &R,
52 old_root: Option<&str>,
53 new_root: &str,
54) -> Result<(Vec<Change>, bool)> {
55 changed_files_up_to(repo, old_root, new_root, MAX_FILES).await
56}
57
58/// [`changed_files`], cut short after `max_files` files.
59async fn changed_files_up_to<R: GitRepo>(
60 repo: &R,
61 old_root: Option<&str>,
62 new_root: &str,
63 max_files: usize,
64) -> Result<(Vec<Change>, bool)> {
65 let mut changes = Vec::new();
66 let mut level = vec![(
67 String::new(),
68 old_root.map(str::to_owned),
69 Some(new_root.to_owned()),
70 )];
71 while !level.is_empty() {
72 let read = try_join_all(level.iter().map(|(_, old_tree, new_tree)| async move {
73 let (old, new) = try_join(
74 entries(repo, old_tree.as_deref()),
75 entries(repo, new_tree.as_deref()),
76 )
77 .await?;
78 Ok::<_, worker::Error>((old, new))
79 }))
80 .await?;
81 let mut next = Vec::new();
82 for ((prefix, _, _), (old, new)) in level.iter().zip(read) {
83 let names: std::collections::BTreeSet<&String> = old.keys().chain(new.keys()).collect();
84 for name in names {
85 let (before, after) = (old.get(name), new.get(name));
86 // A file made executable keeps its hash, and is still a change.
87 if before.map(|e| (&e.hash, e.kind)) == after.map(|e| (&e.hash, e.kind)) {
88 continue;
89 }
90 let path = format!("{prefix}{name}");
91 let subtree = |entry: Option<&TreeEntry>| {
92 entry
93 .filter(|entry| entry.kind == EntryKind::Tree)
94 .map(|entry| entry.hash.clone())
95 };
96 let file = |entry: Option<&TreeEntry>| {
97 entry
98 .filter(|entry| entry.kind != EntryKind::Tree)
99 .map(|entry| entry.hash.clone())
100 };
101 let file_kind = |entry: Option<&TreeEntry>| entry.map(|entry| entry.kind).filter(|kind| *kind != EntryKind::Tree);
102 let (old_dir, new_dir) = (subtree(before), subtree(after));
103 if old_dir.is_some() || new_dir.is_some() {
104 next.push((format!("{path}/"), old_dir, new_dir));
105 }
106 let (old_file, new_file) = (file(before), file(after));
107 if old_file.is_some() || new_file.is_some() {
108 if changes.len() >= max_files {
109 changes.sort_by(|a: &Change, b: &Change| a.path.cmp(&b.path));
110 return Ok((changes, true));
111 }
112 changes.push(Change {
113 path,
114 old: old_file,
115 new: new_file,
116 old_kind: file_kind(before),
117 new_kind: file_kind(after),
118 });
119 }
120 }
121 }
122 level = next;
123 }
124 changes.sort_by(|a, b| a.path.cmp(&b.path));
125 Ok((changes, false))
126}
127
128/// The paths of the files that differ between two trees, without reading
129/// any file: what is needed to see whether two changes touch the same
130/// files. Returns the paths and whether the list was cut short.
131pub async fn changed_paths<R: GitRepo>(
132 repo: &R,
133 old_tree: Option<&str>,
134 new_tree: &str,
135) -> Result<(Vec<String>, bool)> {
136 let (changes, truncated) = changed_files(repo, old_tree, new_tree).await?;
137 Ok((changes.into_iter().map(|change| change.path).collect(), truncated))
138}
139
140/// A file as one tree has it: its kind and blob.
141pub type FileEntry = (EntryKind, String);
142
143/// The files that differ between two trees, each as it was and as it is
144/// (`None` where it is not there), without reading any file. Returns them
145/// by path and whether the list was cut short.
146pub async fn changed_entries<R: GitRepo>(
147 repo: &R,
148 old_tree: Option<&str>,
149 new_tree: &str,
150) -> Result<(Vec<(String, Option<FileEntry>, Option<FileEntry>)>, bool)> {
151 changed_entries_up_to(repo, old_tree, new_tree, MAX_FILES).await
152}
153
154/// [`changed_entries`], listing up to `max_files` files rather than the
155/// comparison's limit: what a merge applies (merge_methods.rs).
156pub async fn changed_entries_up_to<R: GitRepo>(
157 repo: &R,
158 old_tree: Option<&str>,
159 new_tree: &str,
160 max_files: usize,
161) -> Result<(Vec<(String, Option<FileEntry>, Option<FileEntry>)>, bool)> {
162 let (changes, truncated) = changed_files_up_to(repo, old_tree, new_tree, max_files).await?;
163 let entries = changes
164 .into_iter()
165 .map(|change| {
166 let old = change.old_kind.zip(change.old);
167 let new = change.new_kind.zip(change.new);
168 (change.path, old, new)
169 })
170 .collect();
171 Ok((entries, truncated))
172}
173
174/// The text of a blob, or `None` if it is binary, too large or missing.
175async fn text<R: GitRepo>(repo: &R, hash: Option<&str>) -> Result<Option<String>> {
176 let Some(hash) = hash else {
177 return Ok(Some(String::new()));
178 };
179 let Some(bytes) = repo.read_blob(hash).await? else {
180 return Ok(None);
181 };
182 if bytes.len() > MAX_FILE_BYTES || bytes.contains(&0) {
183 return Ok(None);
184 }
185 Ok(String::from_utf8(bytes).ok())
186}
187
188fn line_diff(old: &str, new: &str) -> (Vec<Hunk>, u32, u32) {
189 let diff = TextDiff::from_lines(old, new);
190 let (mut additions, mut deletions) = (0, 0);
191 let hunks = diff
192 .grouped_ops(CONTEXT_LINES)
193 .iter()
194 .map(|group| Hunk {
195 lines: group
196 .iter()
197 .flat_map(|op| diff.iter_changes(op))
198 .map(|change| {
199 let kind = match change.tag() {
200 ChangeTag::Equal => LineKind::Context,
201 ChangeTag::Insert => {
202 additions += 1;
203 LineKind::Add
204 }
205 ChangeTag::Delete => {
206 deletions += 1;
207 LineKind::Delete
208 }
209 };
210 DiffLine {
211 kind,
212 old: change.old_index().map(|index| index as u32 + 1),
213 new: change.new_index().map(|index| index as u32 + 1),
214 text: change.value().trim_end_matches(['\r', '\n']).to_owned(),
215 }
216 })
217 .collect(),
218 })
219 .collect();
220 (hunks, additions, deletions)
221}
222
223/// The files that differ between two trees, with their line changes.
224/// Returns the files and whether the list of files was cut short.
225///
226/// Files are read in order until about `MAX_LINES` lines have been read;
227/// the ones after that are listed without their lines, marked `omitted`,
228/// and are read by asking for them by path (`only`), which reads just them.
229pub async fn compare_trees<R: GitRepo>(
230 repo: &R,
231 old_tree: Option<&str>,
232 new_tree: &str,
233 only: Option<&[String]>,
234) -> Result<(Vec<FileDiff>, bool)> {
235 let (mut changes, truncated) = changed_files(repo, old_tree, new_tree).await?;
236 if let Some(only) = only {
237 changes.retain(|change| only.contains(&change.path));
238 }
239 let mut files = Vec::with_capacity(changes.len());
240 let mut lines = 0;
241 // Contents are read a batch at a time, all of a batch at once.
242 let mut texts_read: Vec<Option<(String, String)>> = Vec::with_capacity(changes.len());
243 for batch in changes.chunks(READS_AT_ONCE) {
244 let read = try_join_all(batch.iter().map(|change| async move {
245 let (old, new) = try_join(
246 text(repo, change.old.as_deref()),
247 text(repo, change.new.as_deref()),
248 )
249 .await?;
250 Ok::<_, worker::Error>(old.zip(new))
251 }))
252 .await?;
253 lines += read
254 .iter()
255 .flatten()
256 .map(|(old, new)| old.lines().count().max(new.lines().count()))
257 .sum::<usize>();
258 texts_read.extend(read);
259 if lines >= MAX_LINES {
260 break;
261 }
262 }
263 let mut texts_read = texts_read.into_iter();
264 lines = 0;
265 for change in changes {
266 let status = match (&change.old, &change.new) {
267 (None, _) => FileStatus::Added,
268 (_, None) => FileStatus::Deleted,
269 _ => FileStatus::Modified,
270 };
271 // Past the limit (not read at all), or read: its two sides, or
272 // nothing when it is binary or too large.
273 let (texts, omitted) = match texts_read.next() {
274 Some(texts) if lines < MAX_LINES => (texts, false),
275 _ => (None, true),
276 };
277 let (hunks, additions, deletions, binary) = match texts {
278 Some((old, new)) => {
279 let (hunks, additions, deletions) = line_diff(&old, &new);
280 (hunks, additions, deletions, false)
281 }
282 None => (Vec::new(), 0, 0, !omitted),
283 };
284 lines += hunks.iter().map(|hunk| hunk.lines.len()).sum::<usize>();
285 files.push(FileDiff {
286 path: change.path,
287 status,
288 additions,
289 deletions,
290 binary,
291 hunks,
292 omitted,
293 });
294 }
295 Ok((files, truncated))
296}
297
298#[cfg(test)]
299mod tests {
300 use std::collections::HashMap;
301 use std::future::Future;
302 use std::pin::pin;
303 use std::task::{Context, Poll, Waker};
304
305 use g1t_contracts::repos::{Branch, Commit, GitAccess};
306
307 use super::*;
308 use crate::store::Scope;
309
310 fn run<F: Future>(future: F) -> F::Output {
311 match pin!(future).as_mut().poll(&mut Context::from_waker(Waker::noop())) {
312 Poll::Ready(output) => output,
313 Poll::Pending => panic!("the fake store never waits"),
314 }
315 }
316
317 #[derive(Default)]
318 struct Fake {
319 trees: HashMap<String, Vec<TreeEntry>>,
320 blobs: HashMap<String, Vec<u8>>,
321 }
322
323 impl GitRepo for Fake {
324 async fn access(&self, _scope: Scope) -> Result<GitAccess> {
325 unimplemented!()
326 }
327 async fn branches(&self) -> Result<Vec<Branch>> {
328 Ok(Vec::new())
329 }
330 async fn log(&self, _git_ref: &str, _limit: u32) -> Result<Vec<Commit>> {
331 Ok(Vec::new())
332 }
333 async fn parents(&self, _commit_hash: &str) -> Result<Option<Vec<String>>> {
334 Ok(None)
335 }
336 async fn read_tree(&self, tree_hash: &str) -> Result<Option<Vec<TreeEntry>>> {
337 Ok(self.trees.get(tree_hash).cloned())
338 }
339 async fn read_blob(&self, blob_hash: &str) -> Result<Option<Vec<u8>>> {
340 Ok(self.blobs.get(blob_hash).cloned())
341 }
342 async fn read_file(&self, _git_ref: &str, _path: &str) -> Result<Option<Vec<u8>>> {
343 Ok(None)
344 }
345 async fn fork(&self, _target_key: &str, _default_branch_only: bool) -> Result<()> {
346 Ok(())
347 }
348 }
349
350 /// A tree that adds `count` files of `lines` lines each, f000 onward,
351 /// then a binary one, `zz.bin`.
352 fn added(count: usize, lines: usize) -> Fake {
353 let mut fake = Fake::default();
354 let mut entries = Vec::new();
355 for n in 0..count {
356 let hash = format!("b{n}");
357 fake.blobs.insert(hash.clone(), "line\n".repeat(lines).into_bytes());
358 entries.push(TreeEntry { name: format!("f{n:03}"), hash, kind: EntryKind::Blob });
359 }
360 fake.blobs.insert("bin".into(), vec![0, 1, 2]);
361 entries.push(TreeEntry { name: "zz.bin".into(), hash: "bin".into(), kind: EntryKind::Blob });
362 fake.trees.insert("root".into(), entries);
363 fake
364 }
365
366 #[test]
367 fn a_small_change_has_every_files_lines() {
368 let fake = added(3, 10);
369 let (files, truncated) = run(compare_trees(&fake, None, "root", None)).unwrap();
370 assert!(!truncated);
371 assert_eq!(files.len(), 4);
372 assert!(files[..3].iter().all(|f| !f.omitted && !f.binary && f.additions == 10));
373 assert!(files[3].binary && !files[3].omitted);
374 }
375
376 #[test]
377 fn files_past_the_line_limit_are_listed_as_omitted_not_binary() {
378 // 40 files of 1,000 lines: about 20 of them fit.
379 let fake = added(40, 1_000);
380 let (files, truncated) = run(compare_trees(&fake, None, "root", None)).unwrap();
381 assert!(!truncated, "every file is listed");
382 assert_eq!(files.len(), 41);
383 let read = files.iter().filter(|f| !f.omitted).count();
384 assert!((MAX_LINES / 1_000..=MAX_LINES / 1_000 + READS_AT_ONCE).contains(&read), "{read} read");
385 let last = files.last().unwrap();
386 assert!(last.omitted && !last.binary && last.hunks.is_empty() && last.additions == 0);
387 }
388
389 #[test]
390 fn an_omitted_file_is_read_when_asked_for_by_path() {
391 let fake = added(40, 1_000);
392 let only = ["f039".to_owned(), "missing".to_owned()];
393 let (files, _) = run(compare_trees(&fake, None, "root", Some(&only))).unwrap();
394 assert_eq!(files.len(), 1);
395 assert_eq!(files[0].path, "f039");
396 assert!(!files[0].omitted);
397 assert_eq!(files[0].additions, 1_000);
398 }
399}