Sign in

flagon-io/g1t

public

g1t/services/repos/src/diff.rs

186 lines6,561 bytesCodeBlame
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 similar::{ChangeTag, TextDiff};
10use worker::Result;
11
12use crate::store::GitRepo;
13
14/// Beyond these the comparison is cut short and marked truncated.
15const MAX_FILES: usize = 300;
16const MAX_LINES: usize = 20_000;
17/// Files larger than this are listed without their lines.
18const MAX_FILE_BYTES: usize = 512 * 1024;
19const CONTEXT_LINES: usize = 3;
20
21/// A file that differs between the two trees.
22struct Change {
23 path: String,
24 old: Option<String>,
25 new: Option<String>,
26}
27
28async fn entries<R: GitRepo>(repo: &R, tree: Option<&str>) -> Result<BTreeMap<String, TreeEntry>> {
29 let Some(tree) = tree else {
30 return Ok(BTreeMap::new());
31 };
32 Ok(repo
33 .read_tree(tree)
34 .await?
35 .unwrap_or_default()
36 .into_iter()
37 .map(|entry| (entry.name.clone(), entry))
38 .collect())
39}
40
41/// Collects changed files under `prefix`, depth first. Trees are compared
42/// with an explicit stack, since async functions cannot recurse directly.
43async fn changed_files<R: GitRepo>(
44 repo: &R,
45 old_root: Option<&str>,
46 new_root: &str,
47) -> Result<(Vec<Change>, bool)> {
48 let mut changes = Vec::new();
49 let mut stack = vec![(
50 String::new(),
51 old_root.map(str::to_owned),
52 Some(new_root.to_owned()),
53 )];
54 while let Some((prefix, old_tree, new_tree)) = stack.pop() {
55 let old = entries(repo, old_tree.as_deref()).await?;
56 let new = entries(repo, new_tree.as_deref()).await?;
57 let names: std::collections::BTreeSet<&String> = old.keys().chain(new.keys()).collect();
58 for name in names {
59 let (before, after) = (old.get(name), new.get(name));
60 if before.map(|e| &e.hash) == after.map(|e| &e.hash) {
61 continue;
62 }
63 let path = format!("{prefix}{name}");
64 let subtree = |entry: Option<&TreeEntry>| {
65 entry
66 .filter(|entry| entry.kind == EntryKind::Tree)
67 .map(|entry| entry.hash.clone())
68 };
69 let file = |entry: Option<&TreeEntry>| {
70 entry
71 .filter(|entry| entry.kind != EntryKind::Tree)
72 .map(|entry| entry.hash.clone())
73 };
74 let (old_dir, new_dir) = (subtree(before), subtree(after));
75 if old_dir.is_some() || new_dir.is_some() {
76 stack.push((format!("{path}/"), old_dir, new_dir));
77 }
78 let (old_file, new_file) = (file(before), file(after));
79 if old_file.is_some() || new_file.is_some() {
80 if changes.len() >= MAX_FILES {
81 return Ok((changes, true));
82 }
83 changes.push(Change {
84 path,
85 old: old_file,
86 new: new_file,
87 });
88 }
89 }
90 }
91 changes.sort_by(|a, b| a.path.cmp(&b.path));
92 Ok((changes, false))
93}
94
95/// The text of a blob, or `None` if it is binary, too large or missing.
96async fn text<R: GitRepo>(repo: &R, hash: Option<&str>) -> Result<Option<String>> {
97 let Some(hash) = hash else {
98 return Ok(Some(String::new()));
99 };
100 let Some(bytes) = repo.read_blob(hash).await? else {
101 return Ok(None);
102 };
103 if bytes.len() > MAX_FILE_BYTES || bytes.contains(&0) {
104 return Ok(None);
105 }
106 Ok(String::from_utf8(bytes).ok())
107}
108
109fn line_diff(old: &str, new: &str) -> (Vec<Hunk>, u32, u32) {
110 let diff = TextDiff::from_lines(old, new);
111 let (mut additions, mut deletions) = (0, 0);
112 let hunks = diff
113 .grouped_ops(CONTEXT_LINES)
114 .iter()
115 .map(|group| Hunk {
116 lines: group
117 .iter()
118 .flat_map(|op| diff.iter_changes(op))
119 .map(|change| {
120 let kind = match change.tag() {
121 ChangeTag::Equal => LineKind::Context,
122 ChangeTag::Insert => {
123 additions += 1;
124 LineKind::Add
125 }
126 ChangeTag::Delete => {
127 deletions += 1;
128 LineKind::Delete
129 }
130 };
131 DiffLine {
132 kind,
133 old: change.old_index().map(|index| index as u32 + 1),
134 new: change.new_index().map(|index| index as u32 + 1),
135 text: change.value().trim_end_matches(['\r', '\n']).to_owned(),
136 }
137 })
138 .collect(),
139 })
140 .collect();
141 (hunks, additions, deletions)
142}
143
144/// The files that differ between two trees, with their line changes.
145/// Returns the files and whether the result was cut short.
146pub async fn compare_trees<R: GitRepo>(
147 repo: &R,
148 old_tree: Option<&str>,
149 new_tree: &str,
150) -> Result<(Vec<FileDiff>, bool)> {
151 let (changes, mut truncated) = changed_files(repo, old_tree, new_tree).await?;
152 let mut files = Vec::with_capacity(changes.len());
153 let mut lines = 0;
154 for change in changes {
155 let status = match (&change.old, &change.new) {
156 (None, _) => FileStatus::Added,
157 (_, None) => FileStatus::Deleted,
158 _ => FileStatus::Modified,
159 };
160 let texts = if lines >= MAX_LINES {
161 truncated = true;
162 None
163 } else {
164 let old = text(repo, change.old.as_deref()).await?;
165 let new = text(repo, change.new.as_deref()).await?;
166 old.zip(new)
167 };
168 let (hunks, additions, deletions, binary) = match texts {
169 Some((old, new)) => {
170 let (hunks, additions, deletions) = line_diff(&old, &new);
171 (hunks, additions, deletions, false)
172 }
173 None => (Vec::new(), 0, 0, true),
174 };
175 lines += hunks.iter().map(|hunk| hunk.lines.len()).sum::<usize>();
176 files.push(FileDiff {
177 path: change.path,
178 status,
179 additions,
180 deletions,
181 binary,
182 hunks,
183 });
184 }
185 Ok((files, truncated))
186}