| 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 | |
| 6 | use std::collections::BTreeMap; |
| 7 | |
| 8 | use g1t_contracts::repos::{DiffLine, EntryKind, FileDiff, FileStatus, Hunk, LineKind, TreeEntry}; |
| 9 | use futures_util::future::{try_join, try_join_all}; |
| 10 | use similar::{ChangeTag, TextDiff}; |
| 11 | use worker::Result; |
| 12 | |
| 13 | use crate::store::GitRepo; |
| 14 | |
| 15 | /// Beyond these the comparison is cut short and marked truncated. |
| 16 | const MAX_FILES: usize = 300; |
| 17 | const MAX_LINES: usize = 20_000; |
| 18 | /// Files larger than this are listed without their lines. |
| 19 | const MAX_FILE_BYTES: usize = 512 * 1024; |
| 20 | const CONTEXT_LINES: usize = 3; |
| 21 | |
| 22 | /// A file that differs between the two trees. |
| 23 | struct Change { |
| 24 | path: String, |
| 25 | old: Option<String>, |
| 26 | new: Option<String>, |
| 27 | old_kind: Option<EntryKind>, |
| 28 | new_kind: Option<EntryKind>, |
| 29 | } |
| 30 | |
| 31 | async 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. |
| 45 | const 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. |
| 50 | async 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. |
| 121 | pub 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. |
| 131 | pub 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. |
| 136 | pub 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. |
| 154 | async 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 | |
| 167 | fn 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 result was cut short. |
| 204 | pub async fn compare_trees<R: GitRepo>( |
| 205 | repo: &R, |
| 206 | old_tree: Option<&str>, |
| 207 | new_tree: &str, |
| 208 | ) -> Result<(Vec<FileDiff>, bool)> { |
| 209 | let (changes, mut truncated) = changed_files(repo, old_tree, new_tree).await?; |
| 210 | let mut files = Vec::with_capacity(changes.len()); |
| 211 | let mut lines = 0; |
| 212 | // Contents are read a batch at a time, all of a batch at once. |
| 213 | let mut texts_read: Vec<Option<(String, String)>> = Vec::with_capacity(changes.len()); |
| 214 | for batch in changes.chunks(READS_AT_ONCE) { |
| 215 | let read = try_join_all(batch.iter().map(|change| async move { |
| 216 | let (old, new) = try_join( |
| 217 | text(repo, change.old.as_deref()), |
| 218 | text(repo, change.new.as_deref()), |
| 219 | ) |
| 220 | .await?; |
| 221 | Ok::<_, worker::Error>(old.zip(new)) |
| 222 | })) |
| 223 | .await?; |
| 224 | lines += read |
| 225 | .iter() |
| 226 | .flatten() |
| 227 | .map(|(old, new)| old.lines().count().max(new.lines().count())) |
| 228 | .sum::<usize>(); |
| 229 | texts_read.extend(read); |
| 230 | if lines >= MAX_LINES { |
| 231 | break; |
| 232 | } |
| 233 | } |
| 234 | let mut texts_read = texts_read.into_iter(); |
| 235 | lines = 0; |
| 236 | for change in changes { |
| 237 | let status = match (&change.old, &change.new) { |
| 238 | (None, _) => FileStatus::Added, |
| 239 | (_, None) => FileStatus::Deleted, |
| 240 | _ => FileStatus::Modified, |
| 241 | }; |
| 242 | let texts = match texts_read.next() { |
| 243 | Some(texts) if lines < MAX_LINES => texts, |
| 244 | _ => { |
| 245 | truncated = true; |
| 246 | None |
| 247 | } |
| 248 | }; |
| 249 | let (hunks, additions, deletions, binary) = match texts { |
| 250 | Some((old, new)) => { |
| 251 | let (hunks, additions, deletions) = line_diff(&old, &new); |
| 252 | (hunks, additions, deletions, false) |
| 253 | } |
| 254 | None => (Vec::new(), 0, 0, true), |
| 255 | }; |
| 256 | lines += hunks.iter().map(|hunk| hunk.lines.len()).sum::<usize>(); |
| 257 | files.push(FileDiff { |
| 258 | path: change.path, |
| 259 | status, |
| 260 | additions, |
| 261 | deletions, |
| 262 | binary, |
| 263 | hunks, |
| 264 | }); |
| 265 | } |
| 266 | Ok((files, truncated)) |
| 267 | } |