Sign in

pulls/pr_01m47d15m3e54sn21z27rpy5n9

public

pr_01m47d15m3e54sn21z27rpy5n9/services/repos/src/blame.rs

225 lines8,447 bytesCodeBlame
1//! Which commit last changed each line of a file.
2//!
3//! History is walked newest first, as `git blame` does: a line still present,
4//! unchanged, in one of a commit's parents is handed to that parent; a line in
5//! none of them was written by the commit. Following every parent, not just
6//! the first, matters here: catch-up merges bring the default branch into a
7//! pull request, and their lines belong to whoever wrote them on that branch.
8
9use std::collections::HashMap;
10
11use g1t_contracts::repos::{Blame, BlameRange, Commit, EntryKind, TreeEntry};
12use similar::{ChangeTag, TextDiff};
13use worker::Result;
14
15use crate::store::GitRepo;
16
17/// How far back the history is searched. Lines older than this are given to
18/// the oldest commit reached, and the answer is marked partial.
19const MAX_COMMITS: u32 = 400;
20/// Files larger than this are not blamed.
21const MAX_FILE_BYTES: usize = 512 * 1024;
22
23/// Reads files out of commits, remembering trees and texts already read:
24/// most commits share most of their trees.
25struct Reader<'a, R: GitRepo> {
26 repo: &'a R,
27 trees: HashMap<String, Vec<TreeEntry>>,
28 texts: HashMap<String, Option<String>>,
29}
30
31impl<'a, R: GitRepo> Reader<'a, R> {
32 /// The blob hash of `path` in the tree `root`, if it is a file there.
33 async fn blob_at(&mut self, root: &str, path: &str) -> Result<Option<String>> {
34 let mut tree = root.to_owned();
35 let parts: Vec<&str> = path.split('/').filter(|part| !part.is_empty()).collect();
36 for (index, part) in parts.iter().enumerate() {
37 if !self.trees.contains_key(&tree) {
38 let entries = self.repo.read_tree(&tree).await?.unwrap_or_default();
39 self.trees.insert(tree.clone(), entries);
40 }
41 let Some(entry) = self.trees[&tree].iter().find(|entry| entry.name == *part) else {
42 return Ok(None);
43 };
44 let last = index == parts.len() - 1;
45 match (last, entry.kind == EntryKind::Tree) {
46 (true, false) => return Ok(Some(entry.hash.clone())),
47 (false, true) => tree = entry.hash.clone(),
48 _ => return Ok(None),
49 }
50 }
51 Ok(None)
52 }
53
54 /// The lines of a blob, or `None` if it is binary or too large.
55 async fn lines(&mut self, blob: &str) -> Result<Option<Vec<String>>> {
56 if !self.texts.contains_key(blob) {
57 let text = self
58 .repo
59 .read_blob(blob)
60 .await?
61 .filter(|bytes| bytes.len() <= MAX_FILE_BYTES && !bytes.contains(&0))
62 .and_then(|bytes| String::from_utf8(bytes).ok());
63 self.texts.insert(blob.to_owned(), text);
64 }
65 Ok(self.texts[blob]
66 .as_ref()
67 .map(|text| text.lines().map(str::to_owned).collect()))
68 }
69}
70
71/// For each line of `new`, the index of the same, unchanged line in `old`.
72fn carried(old: &[String], new: &[String]) -> Vec<Option<usize>> {
73 // Every line ends in a newline, so a last line matches the same line elsewhere.
74 let text = |lines: &[String]| lines.iter().map(|line| format!("{line}\n")).collect::<String>();
75 let (before, after) = (text(old), text(new));
76 let diff = TextDiff::from_lines(&before, &after);
77 let mut map = vec![None; new.len()];
78 for change in diff.iter_all_changes() {
79 if change.tag() == ChangeTag::Equal {
80 if let (Some(o), Some(n)) = (change.old_index(), change.new_index()) {
81 if let Some(slot) = map.get_mut(n) {
82 *slot = Some(o);
83 }
84 }
85 }
86 }
87 map
88}
89
90/// Who last changed each line of `path` as of `head`. `None` if the file is
91/// missing or not text.
92pub async fn blame<R: GitRepo>(
93 repo: &R,
94 head: &str,
95 path: &str,
96) -> Result<Option<Blame>> {
97 let history = repo.log(head, MAX_COMMITS).await?;
98 let Some(first) = history.first() else {
99 return Ok(None);
100 };
101 let mut reader = Reader {
102 repo,
103 trees: HashMap::new(),
104 texts: HashMap::new(),
105 };
106 let Some(blob) = reader.blob_at(&first.tree_hash, path).await? else {
107 return Ok(None);
108 };
109 let Some(lines) = reader.lines(&blob).await? else {
110 return Ok(None);
111 };
112 let total = lines.len();
113 let by_hash: HashMap<&str, &Commit> =
114 history.iter().map(|commit| (commit.hash.as_str(), commit)).collect();
115
116 // For each commit still to visit: (line in its version, line in the head's).
117 let mut pending: HashMap<String, Vec<(usize, usize)>> = HashMap::new();
118 pending.insert(first.hash.clone(), (0..total).map(|line| (line, line)).collect());
119 let mut owner: Vec<Option<String>> = vec![None; total];
120 let mut partial = false;
121
122 // The log is newest first, so a commit is reached after its children.
123 for commit in &history {
124 let Some(mut lines_here) = pending.remove(&commit.hash) else {
125 continue;
126 };
127 lines_here.sort_unstable();
128 lines_here.dedup_by_key(|(_, final_line)| *final_line);
129 let Some(blob) = reader.blob_at(&commit.tree_hash, path).await? else {
130 continue;
131 };
132 let Some(text) = reader.lines(&blob).await? else {
133 continue;
134 };
135 let mut unexplained = lines_here;
136 for parent_hash in &commit.parents {
137 if unexplained.is_empty() {
138 break;
139 }
140 let Some(parent) = by_hash.get(parent_hash.as_str()) else {
141 // Beyond the history read: these lines are at least this old.
142 partial = true;
143 continue;
144 };
145 let Some(parent_blob) = reader.blob_at(&parent.tree_hash, path).await? else {
146 continue;
147 };
148 let handed: Vec<(usize, usize)> = if parent_blob == blob {
149 std::mem::take(&mut unexplained)
150 } else {
151 let Some(parent_text) = reader.lines(&parent_blob).await? else {
152 continue;
153 };
154 let map = carried(&parent_text, &text);
155 let (moved, kept): (Vec<_>, Vec<_>) = unexplained
156 .into_iter()
157 .partition(|(here, _)| map.get(*here).copied().flatten().is_some());
158 unexplained = kept;
159 moved
160 .into_iter()
161 .map(|(here, final_line)| (map[here].unwrap_or(here), final_line))
162 .collect()
163 };
164 if !handed.is_empty() {
165 pending.entry(parent_hash.clone()).or_default().extend(handed);
166 }
167 }
168 for (_, final_line) in unexplained {
169 owner[final_line] = Some(commit.hash.clone());
170 }
171 }
172 // Lines handed to commits older than the history read.
173 if !pending.is_empty() {
174 partial = true;
175 let oldest = history.last().map(|commit| commit.hash.clone());
176 for line in owner.iter_mut().filter(|line| line.is_none()) {
177 *line = oldest.clone();
178 }
179 }
180
181 let mut ranges: Vec<BlameRange> = Vec::new();
182 for (index, hash) in owner.into_iter().enumerate() {
183 let hash = hash.unwrap_or_else(|| first.hash.clone());
184 let line = index as u32 + 1;
185 match ranges.last_mut() {
186 Some(range) if range.commit == hash => range.end = line,
187 _ => ranges.push(BlameRange { start: line, end: line, commit: hash }),
188 }
189 }
190 let mut commits: Vec<Commit> = Vec::new();
191 for range in &ranges {
192 if !commits.iter().any(|commit| commit.hash == range.commit) {
193 if let Some(commit) = by_hash.get(range.commit.as_str()) {
194 commits.push((*commit).clone());
195 }
196 }
197 }
198 Ok(Some(Blame {
199 head: first.hash.clone(),
200 ranges,
201 commits,
202 partial,
203 }))
204}
205
206#[cfg(test)]
207mod tests {
208 use super::*;
209
210 fn lines(text: &str) -> Vec<String> {
211 text.lines().map(str::to_owned).collect()
212 }
213
214 #[test]
215 fn unchanged_lines_are_carried_to_the_parent() {
216 let map = carried(&lines("a\nb\nc"), &lines("a\nx\nb\nc"));
217 assert_eq!(map, vec![Some(0), None, Some(1), Some(2)]);
218 }
219
220 #[test]
221 fn a_changed_line_is_not_carried() {
222 let map = carried(&lines("a\nb"), &lines("a\nB"));
223 assert_eq!(map, vec![Some(0), None]);
224 }
225}