Skip to content
Sign up

flagon-io/g1t

public
0

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