Sign in

flagon-io/g1t

public

g1t/services/repos/src/last_commits.rs

259 lines10,711 bytesCodeBlame
1//! Which commit last changed each entry of a directory, for the file list.
2//!
3//! History is walked newest first along the first-parent chain. Each commit
4//! is compared with its parent only where the directory itself changed (its
5//! tree hash differs), so the walk reads a tree only for the commits that
6//! touched it. An entry is given the newest commit after which its hash is
7//! no longer the same; one that never changes within the walk is given the
8//! oldest commit reached if that is the root, and nothing otherwise.
9
10use std::collections::HashMap;
11
12use g1t_contracts::repos::{Commit, EntryKind, LastCommit, TreeEntry};
13use worker::Result;
14
15use crate::store::GitRepo;
16
17/// How far back the history is walked.
18pub const MAX_COMMITS: u32 = 300;
19/// Commits whose trees are read together, ahead of the walk: each read is a
20/// round trip to the store, so reading them one by one is what is slow.
21const READ_AHEAD: usize = 24;
22
23/// Reads trees, remembering those already read: commits share most of them.
24struct Trees<'a, R: GitRepo> {
25 repo: &'a R,
26 read: HashMap<String, Option<Vec<TreeEntry>>>,
27}
28
29impl<'a, R: GitRepo> Trees<'a, R> {
30 /// Reads the trees not read yet, all at once.
31 async fn prefetch(&mut self, hashes: impl IntoIterator<Item = String>) -> Result<()> {
32 let mut wanted: Vec<String> = hashes.into_iter().filter(|hash| !self.read.contains_key(hash)).collect();
33 wanted.sort();
34 wanted.dedup();
35 let found = futures_util::future::join_all(wanted.iter().map(|hash| self.repo.read_tree(hash))).await;
36 for (hash, tree) in wanted.into_iter().zip(found) {
37 self.read.insert(hash, tree?);
38 }
39 Ok(())
40 }
41
42 /// Reads, level by level and each level at once, the trees on the way
43 /// to `path` in each of `roots`, and the directory itself.
44 async fn prefetch_dirs(&mut self, roots: Vec<String>, path: &str) -> Result<()> {
45 let mut level = roots;
46 for segment in path.split('/').filter(|segment| !segment.is_empty()) {
47 self.prefetch(level.clone()).await?;
48 level = level
49 .iter()
50 .filter_map(|hash| {
51 self.read.get(hash)?.as_ref()?.iter().find(|entry| entry.name == segment && entry.kind == EntryKind::Tree).map(|entry| entry.hash.clone())
52 })
53 .collect();
54 }
55 self.prefetch(level).await
56 }
57
58 async fn get(&mut self, hash: &str) -> Result<Option<Vec<TreeEntry>>> {
59 if let Some(found) = self.read.get(hash) {
60 return Ok(found.clone());
61 }
62 let found = self.repo.read_tree(hash).await?;
63 self.read.insert(hash.to_owned(), found.clone());
64 Ok(found)
65 }
66
67 /// The tree hash of `path` in a commit's root tree; the root for an empty path.
68 async fn dir(&mut self, root: &str, path: &str) -> Result<Option<String>> {
69 let mut hash = root.to_owned();
70 for segment in path.split('/').filter(|segment| !segment.is_empty()) {
71 let Some(entries) = self.get(&hash).await? else {
72 return Ok(None);
73 };
74 match entries.into_iter().find(|entry| entry.name == segment && entry.kind == EntryKind::Tree) {
75 Some(entry) => hash = entry.hash,
76 None => return Ok(None),
77 }
78 }
79 Ok(Some(hash))
80 }
81
82 async fn entries(&mut self, dir: Option<&str>) -> Result<HashMap<String, String>> {
83 let Some(dir) = dir else {
84 return Ok(HashMap::new());
85 };
86 Ok(self.get(dir).await?.unwrap_or_default().into_iter().map(|entry| (entry.name, entry.hash)).collect())
87 }
88}
89
90/// The last commit of each entry of `path` at `git_ref`, and whether every
91/// entry was given one.
92pub async fn last_commits<R: GitRepo>(repo: &R, git_ref: &str, path: &str) -> Result<(Vec<LastCommit>, bool)> {
93 let history = repo.log(git_ref, MAX_COMMITS).await?;
94 let Some(head) = history.first() else {
95 return Ok((Vec::new(), true));
96 };
97 let mut trees = Trees { repo, read: HashMap::new() };
98 let mut dir = trees.dir(&head.tree_hash, path).await?;
99 let mut current = trees.entries(dir.as_deref()).await?;
100 let mut open: Vec<String> = current.keys().cloned().collect();
101 let mut found: Vec<LastCommit> = Vec::new();
102 let give = |found: &mut Vec<LastCommit>, name: String, commit: &Commit| found.push(LastCommit { name, commit: commit.clone() });
103 for (index, commit) in history.iter().enumerate() {
104 if open.is_empty() {
105 break;
106 }
107 if index % READ_AHEAD == 0 {
108 let ahead = history.iter().skip(index + 1).take(READ_AHEAD).map(|commit| commit.tree_hash.clone()).collect();
109 trees.prefetch_dirs(ahead, path).await?;
110 }
111 let Some(parent) = history.get(index + 1) else {
112 // The oldest commit read. If it is the first commit there is,
113 // what is left was added by it.
114 if commit.parents.is_empty() {
115 for name in open.drain(..) {
116 give(&mut found, name, commit);
117 }
118 }
119 break;
120 };
121 let parent_dir = trees.dir(&parent.tree_hash, path).await?;
122 if parent_dir == dir {
123 continue;
124 }
125 let before = trees.entries(parent_dir.as_deref()).await?;
126 let (changed, still): (Vec<String>, Vec<String>) = open.into_iter().partition(|name| before.get(name) != current.get(name));
127 for name in changed {
128 give(&mut found, name, commit);
129 }
130 open = still;
131 dir = parent_dir;
132 current = before;
133 }
134 let complete = open.is_empty();
135 Ok((found, complete))
136}
137
138#[cfg(test)]
139mod tests {
140 use std::future::Future;
141 use std::pin::pin;
142 use std::task::{Context, Poll, Waker};
143
144 use g1t_contracts::repos::{Branch, GitAccess, Signature};
145
146 use super::*;
147 use crate::store::Scope;
148
149 fn run<F: Future>(future: F) -> F::Output {
150 match pin!(future).as_mut().poll(&mut Context::from_waker(Waker::noop())) {
151 Poll::Ready(output) => output,
152 Poll::Pending => panic!("the fake store never waits"),
153 }
154 }
155
156 #[derive(Default)]
157 struct Fake {
158 trees: HashMap<String, Vec<TreeEntry>>,
159 history: Vec<Commit>,
160 }
161
162 impl GitRepo for Fake {
163 async fn access(&self, _scope: Scope) -> Result<GitAccess> {
164 unimplemented!()
165 }
166 async fn branches(&self) -> Result<Vec<Branch>> {
167 Ok(Vec::new())
168 }
169 async fn log(&self, _git_ref: &str, limit: u32) -> Result<Vec<Commit>> {
170 Ok(self.history.iter().take(limit as usize).cloned().collect())
171 }
172 async fn parents(&self, _commit_hash: &str) -> Result<Option<Vec<String>>> {
173 Ok(None)
174 }
175 async fn read_tree(&self, tree_hash: &str) -> Result<Option<Vec<TreeEntry>>> {
176 Ok(self.trees.get(tree_hash).cloned())
177 }
178 async fn read_blob(&self, _blob_hash: &str) -> Result<Option<Vec<u8>>> {
179 Ok(None)
180 }
181 async fn read_file(&self, _git_ref: &str, _path: &str) -> Result<Option<Vec<u8>>> {
182 Ok(None)
183 }
184 async fn fork(&self, _target_key: &str) -> Result<()> {
185 Ok(())
186 }
187 }
188
189 fn entry(name: &str, hash: &str, kind: EntryKind) -> TreeEntry {
190 TreeEntry { name: name.into(), hash: hash.into(), kind }
191 }
192
193 fn commit(hash: &str, tree: &str, parent: Option<&str>) -> Commit {
194 Commit {
195 hash: hash.into(),
196 tree_hash: tree.into(),
197 message: format!("commit {hash}"),
198 author: Signature { name: "a".into(), email: "a@example.com".into() },
199 parents: parent.map(|p| vec![p.to_owned()]).unwrap_or_default(),
200 authored_at: String::new(),
201 }
202 }
203
204 /// c1 adds README and src/a.rs; c2 changes src/a.rs; c3 changes README.
205 fn repo() -> Fake {
206 let mut fake = Fake::default();
207 fake.trees.insert("src1".into(), vec![entry("a.rs", "a1", EntryKind::Blob)]);
208 fake.trees.insert("src2".into(), vec![entry("a.rs", "a2", EntryKind::Blob)]);
209 fake.trees.insert("root1".into(), vec![entry("README.md", "r1", EntryKind::Blob), entry("src", "src1", EntryKind::Tree)]);
210 fake.trees.insert("root2".into(), vec![entry("README.md", "r1", EntryKind::Blob), entry("src", "src2", EntryKind::Tree)]);
211 fake.trees.insert("root3".into(), vec![entry("README.md", "r2", EntryKind::Blob), entry("src", "src2", EntryKind::Tree)]);
212 fake.history = vec![commit("c3", "root3", Some("c2")), commit("c2", "root2", Some("c1")), commit("c1", "root1", None)];
213 fake
214 }
215
216 fn by_name(found: Vec<LastCommit>) -> HashMap<String, String> {
217 found.into_iter().map(|last| (last.name, last.commit.hash)).collect()
218 }
219
220 #[test]
221 fn each_root_entry_gets_the_newest_commit_that_changed_it() {
222 let (found, complete) = run(last_commits(&repo(), "main", "")).unwrap();
223 assert!(complete);
224 let found = by_name(found);
225 assert_eq!(found["README.md"], "c3");
226 assert_eq!(found["src"], "c2");
227 }
228
229 #[test]
230 fn a_subdirectory_is_walked_by_its_own_tree() {
231 let (found, complete) = run(last_commits(&repo(), "main", "src")).unwrap();
232 assert!(complete);
233 assert_eq!(by_name(found)["a.rs"], "c2");
234 }
235
236 #[test]
237 fn an_entry_unchanged_since_the_first_commit_belongs_to_it() {
238 let mut fake = repo();
239 fake.trees.insert("root2".into(), vec![entry("README.md", "r1", EntryKind::Blob), entry("src", "src1", EntryKind::Tree)]);
240 fake.trees.insert("root3".into(), vec![entry("README.md", "r2", EntryKind::Blob), entry("src", "src1", EntryKind::Tree)]);
241 let (found, complete) = run(last_commits(&fake, "main", "")).unwrap();
242 assert!(complete);
243 assert_eq!(by_name(found)["src"], "c1");
244 }
245
246 #[test]
247 fn a_walk_cut_short_leaves_the_rest_unknown() {
248 let mut fake = repo();
249 // c1 has a parent the walk never reaches.
250 fake.history[2].parents = vec!["c0".into()];
251 fake.trees.insert("root2".into(), vec![entry("README.md", "r1", EntryKind::Blob), entry("src", "src1", EntryKind::Tree)]);
252 fake.trees.insert("root3".into(), vec![entry("README.md", "r2", EntryKind::Blob), entry("src", "src1", EntryKind::Tree)]);
253 let (found, complete) = run(last_commits(&fake, "main", "")).unwrap();
254 assert!(!complete);
255 let found = by_name(found);
256 assert_eq!(found["README.md"], "c3");
257 assert!(!found.contains_key("src"));
258 }
259}