Sign in

flagon-io/g1t

public

Where people and agents ship software together. The open-source git platform for the whole job: issues, agents, checks and deploys to the edge.

gitagentscloudflarerustforgemcp

g1t/services/repos/src/blame.rs

222 lines8,407 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 && let (Some(o), Some(n)) = (change.old_index(), change.new_index())
81 && let Some(slot) = map.get_mut(n) {
82 *slot = Some(o);
83 }
84 }
85 map
86}
87
88/// Who last changed each line of `path` as of `head`. `None` if the file is
89/// missing or not text.
90pub async fn blame<R: GitRepo>(
91 repo: &R,
92 head: &str,
93 path: &str,
94) -> Result<Option<Blame>> {
95 let history = repo.log(head, MAX_COMMITS).await?;
96 let Some(first) = history.first() else {
97 return Ok(None);
98 };
99 let mut reader = Reader {
100 repo,
101 trees: HashMap::new(),
102 texts: HashMap::new(),
103 };
104 let Some(blob) = reader.blob_at(&first.tree_hash, path).await? else {
105 return Ok(None);
106 };
107 let Some(lines) = reader.lines(&blob).await? else {
108 return Ok(None);
109 };
110 let total = lines.len();
111 let by_hash: HashMap<&str, &Commit> =
112 history.iter().map(|commit| (commit.hash.as_str(), commit)).collect();
113
114 // For each commit still to visit: (line in its version, line in the head's).
115 let mut pending: HashMap<String, Vec<(usize, usize)>> = HashMap::new();
116 pending.insert(first.hash.clone(), (0..total).map(|line| (line, line)).collect());
117 let mut owner: Vec<Option<String>> = vec![None; total];
118 let mut partial = false;
119
120 // The log is newest first, so a commit is reached after its children.
121 for commit in &history {
122 let Some(mut lines_here) = pending.remove(&commit.hash) else {
123 continue;
124 };
125 lines_here.sort_unstable();
126 lines_here.dedup_by_key(|(_, final_line)| *final_line);
127 let Some(blob) = reader.blob_at(&commit.tree_hash, path).await? else {
128 continue;
129 };
130 let Some(text) = reader.lines(&blob).await? else {
131 continue;
132 };
133 let mut unexplained = lines_here;
134 for parent_hash in &commit.parents {
135 if unexplained.is_empty() {
136 break;
137 }
138 let Some(parent) = by_hash.get(parent_hash.as_str()) else {
139 // Beyond the history read: these lines are at least this old.
140 partial = true;
141 continue;
142 };
143 let Some(parent_blob) = reader.blob_at(&parent.tree_hash, path).await? else {
144 continue;
145 };
146 let handed: Vec<(usize, usize)> = if parent_blob == blob {
147 std::mem::take(&mut unexplained)
148 } else {
149 let Some(parent_text) = reader.lines(&parent_blob).await? else {
150 continue;
151 };
152 let map = carried(&parent_text, &text);
153 let (moved, kept): (Vec<_>, Vec<_>) = unexplained
154 .into_iter()
155 .partition(|(here, _)| map.get(*here).copied().flatten().is_some());
156 unexplained = kept;
157 moved
158 .into_iter()
159 .map(|(here, final_line)| (map[here].unwrap_or(here), final_line))
160 .collect()
161 };
162 if !handed.is_empty() {
163 pending.entry(parent_hash.clone()).or_default().extend(handed);
164 }
165 }
166 for (_, final_line) in unexplained {
167 owner[final_line] = Some(commit.hash.clone());
168 }
169 }
170 // Lines handed to commits older than the history read.
171 if !pending.is_empty() {
172 partial = true;
173 let oldest = history.last().map(|commit| commit.hash.clone());
174 for line in owner.iter_mut().filter(|line| line.is_none()) {
175 *line = oldest.clone();
176 }
177 }
178
179 let mut ranges: Vec<BlameRange> = Vec::new();
180 for (index, hash) in owner.into_iter().enumerate() {
181 let hash = hash.unwrap_or_else(|| first.hash.clone());
182 let line = index as u32 + 1;
183 match ranges.last_mut() {
184 Some(range) if range.commit == hash => range.end = line,
185 _ => ranges.push(BlameRange { start: line, end: line, commit: hash }),
186 }
187 }
188 let mut commits: Vec<Commit> = Vec::new();
189 for range in &ranges {
190 if !commits.iter().any(|commit| commit.hash == range.commit)
191 && let Some(commit) = by_hash.get(range.commit.as_str()) {
192 commits.push((*commit).clone());
193 }
194 }
195 Ok(Some(Blame {
196 head: first.hash.clone(),
197 ranges,
198 commits,
199 partial,
200 }))
201}
202
203#[cfg(test)]
204mod tests {
205 use super::*;
206
207 fn lines(text: &str) -> Vec<String> {
208 text.lines().map(str::to_owned).collect()
209 }
210
211 #[test]
212 fn unchanged_lines_are_carried_to_the_parent() {
213 let map = carried(&lines("a\nb\nc"), &lines("a\nx\nb\nc"));
214 assert_eq!(map, vec![Some(0), None, Some(1), Some(2)]);
215 }
216
217 #[test]
218 fn a_changed_line_is_not_carried() {
219 let map = carried(&lines("a\nb"), &lines("a\nB"));
220 assert_eq!(map, vec![Some(0), None]);
221 }
222}