Sign in

pulls/pr_01m47d24b0e6n91zwymwxg0vpx

public

pr_01m47d24b0e6n91zwymwxg0vpx/services/repos/src/diff.rs

239 lines8,685 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 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}
28
29async fn entries<R: GitRepo>(repo: &R, tree: Option<&str>) -> Result<BTreeMap<String, TreeEntry>> {
30 let Some(tree) = tree else {
31 return Ok(BTreeMap::new());
32 };
33 Ok(repo
34 .read_tree(tree)
35 .await?
36 .unwrap_or_default()
37 .into_iter()
38 .map(|entry| (entry.name.clone(), entry))
39 .collect())
40}
41
42/// How many files' contents are read at once.
43const READS_AT_ONCE: usize = 16;
44
45/// Collects the files that differ between two trees. Each level of the
46/// trees is read at once, since every read is a round trip to the store
47/// and the levels' trees do not depend on each other.
48async fn changed_files<R: GitRepo>(
49 repo: &R,
50 old_root: Option<&str>,
51 new_root: &str,
52) -> Result<(Vec<Change>, bool)> {
53 let mut changes = Vec::new();
54 let mut level = vec![(
55 String::new(),
56 old_root.map(str::to_owned),
57 Some(new_root.to_owned()),
58 )];
59 while !level.is_empty() {
60 let read = try_join_all(level.iter().map(|(_, old_tree, new_tree)| async move {
61 let (old, new) = try_join(
62 entries(repo, old_tree.as_deref()),
63 entries(repo, new_tree.as_deref()),
64 )
65 .await?;
66 Ok::<_, worker::Error>((old, new))
67 }))
68 .await?;
69 let mut next = Vec::new();
70 for ((prefix, _, _), (old, new)) in level.iter().zip(read) {
71 let names: std::collections::BTreeSet<&String> = old.keys().chain(new.keys()).collect();
72 for name in names {
73 let (before, after) = (old.get(name), new.get(name));
74 // A file made executable keeps its hash, and is still a change.
75 if before.map(|e| (&e.hash, e.kind)) == after.map(|e| (&e.hash, e.kind)) {
76 continue;
77 }
78 let path = format!("{prefix}{name}");
79 let subtree = |entry: Option<&TreeEntry>| {
80 entry
81 .filter(|entry| entry.kind == EntryKind::Tree)
82 .map(|entry| entry.hash.clone())
83 };
84 let file = |entry: Option<&TreeEntry>| {
85 entry
86 .filter(|entry| entry.kind != EntryKind::Tree)
87 .map(|entry| entry.hash.clone())
88 };
89 let (old_dir, new_dir) = (subtree(before), subtree(after));
90 if old_dir.is_some() || new_dir.is_some() {
91 next.push((format!("{path}/"), old_dir, new_dir));
92 }
93 let (old_file, new_file) = (file(before), file(after));
94 if old_file.is_some() || new_file.is_some() {
95 if changes.len() >= MAX_FILES {
96 changes.sort_by(|a: &Change, b: &Change| a.path.cmp(&b.path));
97 return Ok((changes, true));
98 }
99 changes.push(Change {
100 path,
101 old: old_file,
102 new: new_file,
103 });
104 }
105 }
106 }
107 level = next;
108 }
109 changes.sort_by(|a, b| a.path.cmp(&b.path));
110 Ok((changes, false))
111}
112
113/// The paths of the files that differ between two trees, without reading
114/// any file: what is needed to see whether two changes touch the same
115/// files. Returns the paths and whether the list was cut short.
116pub async fn changed_paths<R: GitRepo>(
117 repo: &R,
118 old_tree: Option<&str>,
119 new_tree: &str,
120) -> Result<(Vec<String>, bool)> {
121 let (changes, truncated) = changed_files(repo, old_tree, new_tree).await?;
122 Ok((changes.into_iter().map(|change| change.path).collect(), truncated))
123}
124
125/// The text of a blob, or `None` if it is binary, too large or missing.
126async fn text<R: GitRepo>(repo: &R, hash: Option<&str>) -> Result<Option<String>> {
127 let Some(hash) = hash else {
128 return Ok(Some(String::new()));
129 };
130 let Some(bytes) = repo.read_blob(hash).await? else {
131 return Ok(None);
132 };
133 if bytes.len() > MAX_FILE_BYTES || bytes.contains(&0) {
134 return Ok(None);
135 }
136 Ok(String::from_utf8(bytes).ok())
137}
138
139fn line_diff(old: &str, new: &str) -> (Vec<Hunk>, u32, u32) {
140 let diff = TextDiff::from_lines(old, new);
141 let (mut additions, mut deletions) = (0, 0);
142 let hunks = diff
143 .grouped_ops(CONTEXT_LINES)
144 .iter()
145 .map(|group| Hunk {
146 lines: group
147 .iter()
148 .flat_map(|op| diff.iter_changes(op))
149 .map(|change| {
150 let kind = match change.tag() {
151 ChangeTag::Equal => LineKind::Context,
152 ChangeTag::Insert => {
153 additions += 1;
154 LineKind::Add
155 }
156 ChangeTag::Delete => {
157 deletions += 1;
158 LineKind::Delete
159 }
160 };
161 DiffLine {
162 kind,
163 old: change.old_index().map(|index| index as u32 + 1),
164 new: change.new_index().map(|index| index as u32 + 1),
165 text: change.value().trim_end_matches(['\r', '\n']).to_owned(),
166 }
167 })
168 .collect(),
169 })
170 .collect();
171 (hunks, additions, deletions)
172}
173
174/// The files that differ between two trees, with their line changes.
175/// Returns the files and whether the result was cut short.
176pub async fn compare_trees<R: GitRepo>(
177 repo: &R,
178 old_tree: Option<&str>,
179 new_tree: &str,
180) -> Result<(Vec<FileDiff>, bool)> {
181 let (changes, mut truncated) = changed_files(repo, old_tree, new_tree).await?;
182 let mut files = Vec::with_capacity(changes.len());
183 let mut lines = 0;
184 // Contents are read a batch at a time, all of a batch at once.
185 let mut texts_read: Vec<Option<(String, String)>> = Vec::with_capacity(changes.len());
186 for batch in changes.chunks(READS_AT_ONCE) {
187 let read = try_join_all(batch.iter().map(|change| async move {
188 let (old, new) = try_join(
189 text(repo, change.old.as_deref()),
190 text(repo, change.new.as_deref()),
191 )
192 .await?;
193 Ok::<_, worker::Error>(old.zip(new))
194 }))
195 .await?;
196 lines += read
197 .iter()
198 .flatten()
199 .map(|(old, new)| old.lines().count().max(new.lines().count()))
200 .sum::<usize>();
201 texts_read.extend(read);
202 if lines >= MAX_LINES {
203 break;
204 }
205 }
206 let mut texts_read = texts_read.into_iter();
207 lines = 0;
208 for change in changes {
209 let status = match (&change.old, &change.new) {
210 (None, _) => FileStatus::Added,
211 (_, None) => FileStatus::Deleted,
212 _ => FileStatus::Modified,
213 };
214 let texts = match texts_read.next() {
215 Some(texts) if lines < MAX_LINES => texts,
216 _ => {
217 truncated = true;
218 None
219 }
220 };
221 let (hunks, additions, deletions, binary) = match texts {
222 Some((old, new)) => {
223 let (hunks, additions, deletions) = line_diff(&old, &new);
224 (hunks, additions, deletions, false)
225 }
226 None => (Vec::new(), 0, 0, true),
227 };
228 lines += hunks.iter().map(|hunk| hunk.lines.len()).sum::<usize>();
229 files.push(FileDiff {
230 path: change.path,
231 status,
232 additions,
233 deletions,
234 binary,
235 hunks,
236 });
237 }
238 Ok((files, truncated))
239}