| 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 similar::{ChangeTag, TextDiff}; |
| 10 | use worker::Result; |
| 11 | |
| 12 | use crate::store::GitRepo; |
| 13 | |
| 14 | /// Beyond these the comparison is cut short and marked truncated. |
| 15 | const MAX_FILES: usize = 300; |
| 16 | const MAX_LINES: usize = 20_000; |
| 17 | /// Files larger than this are listed without their lines. |
| 18 | const MAX_FILE_BYTES: usize = 512 * 1024; |
| 19 | const CONTEXT_LINES: usize = 3; |
| 20 | |
| 21 | /// A file that differs between the two trees. |
| 22 | struct Change { |
| 23 | path: String, |
| 24 | old: Option<String>, |
| 25 | new: Option<String>, |
| 26 | } |
| 27 | |
| 28 | async 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. |
| 43 | async 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. |
| 96 | async 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 | |
| 109 | fn 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. |
| 146 | pub 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 | } |