Sign in

flagon-io/g1t

public

g1t/services/repos/src/last_commits.rs

268 lines10,992 bytesCodeBlame

Pick any line to see why it is the way it is: the commit, the pull request and issue it came from, and what the agent was thinking.

Branches and Tags pages, each file's last commit, and the branch menu on files1//! 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;
Last commits read trees two dozen commits at a time, and the file list waits at most 3 s for them19/// 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;
Branches and Tags pages, each file's last commit, and the branch menu on files22
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> {
Last commits read trees two dozen commits at a time, and the file list waits at most 3 s for them30 /// 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
Branches and Tags pages, each file's last commit, and the branch menu on files58 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
A last-commits walk answers within 2.5 s with what it has, and keeps only finished answers91/// entry was given one. `out_of_time` is asked between batches; once it
92/// says so the walk stops with what it has, incomplete.
93pub async fn last_commits<R: GitRepo>(
94 repo: &R,
95 git_ref: &str,
96 path: &str,
97 out_of_time: &dyn Fn() -> bool,
98) -> Result<(Vec<LastCommit>, bool)> {
Branches and Tags pages, each file's last commit, and the branch menu on files99 let history = repo.log(git_ref, MAX_COMMITS).await?;
100 let Some(head) = history.first() else {
101 return Ok((Vec::new(), true));
102 };
103 let mut trees = Trees { repo, read: HashMap::new() };
104 let mut dir = trees.dir(&head.tree_hash, path).await?;
105 let mut current = trees.entries(dir.as_deref()).await?;
106 let mut open: Vec<String> = current.keys().cloned().collect();
107 let mut found: Vec<LastCommit> = Vec::new();
108 let give = |found: &mut Vec<LastCommit>, name: String, commit: &Commit| found.push(LastCommit { name, commit: commit.clone() });
109 for (index, commit) in history.iter().enumerate() {
110 if open.is_empty() {
111 break;
112 }
Last commits read trees two dozen commits at a time, and the file list waits at most 3 s for them113 if index % READ_AHEAD == 0 {
A last-commits walk answers within 2.5 s with what it has, and keeps only finished answers114 if index > 0 && out_of_time() {
115 break;
116 }
Last commits read trees two dozen commits at a time, and the file list waits at most 3 s for them117 let ahead = history.iter().skip(index + 1).take(READ_AHEAD).map(|commit| commit.tree_hash.clone()).collect();
118 trees.prefetch_dirs(ahead, path).await?;
119 }
Branches and Tags pages, each file's last commit, and the branch menu on files120 let Some(parent) = history.get(index + 1) else {
121 // The oldest commit read. If it is the first commit there is,
122 // what is left was added by it.
123 if commit.parents.is_empty() {
124 for name in open.drain(..) {
125 give(&mut found, name, commit);
126 }
127 }
128 break;
129 };
130 let parent_dir = trees.dir(&parent.tree_hash, path).await?;
131 if parent_dir == dir {
132 continue;
133 }
134 let before = trees.entries(parent_dir.as_deref()).await?;
135 let (changed, still): (Vec<String>, Vec<String>) = open.into_iter().partition(|name| before.get(name) != current.get(name));
136 for name in changed {
137 give(&mut found, name, commit);
138 }
139 open = still;
140 dir = parent_dir;
141 current = before;
142 }
143 let complete = open.is_empty();
144 Ok((found, complete))
145}
146
147#[cfg(test)]
148mod tests {
149 use std::future::Future;
150 use std::pin::pin;
151 use std::task::{Context, Poll, Waker};
152
153 use g1t_contracts::repos::{Branch, GitAccess, Signature};
154
155 use super::*;
156 use crate::store::Scope;
157
158 fn run<F: Future>(future: F) -> F::Output {
159 match pin!(future).as_mut().poll(&mut Context::from_waker(Waker::noop())) {
160 Poll::Ready(output) => output,
161 Poll::Pending => panic!("the fake store never waits"),
162 }
163 }
164
165 #[derive(Default)]
166 struct Fake {
167 trees: HashMap<String, Vec<TreeEntry>>,
168 history: Vec<Commit>,
169 }
170
171 impl GitRepo for Fake {
172 async fn access(&self, _scope: Scope) -> Result<GitAccess> {
173 unimplemented!()
174 }
175 async fn branches(&self) -> Result<Vec<Branch>> {
176 Ok(Vec::new())
177 }
178 async fn log(&self, _git_ref: &str, limit: u32) -> Result<Vec<Commit>> {
179 Ok(self.history.iter().take(limit as usize).cloned().collect())
180 }
181 async fn parents(&self, _commit_hash: &str) -> Result<Option<Vec<String>>> {
182 Ok(None)
183 }
184 async fn read_tree(&self, tree_hash: &str) -> Result<Option<Vec<TreeEntry>>> {
185 Ok(self.trees.get(tree_hash).cloned())
186 }
187 async fn read_blob(&self, _blob_hash: &str) -> Result<Option<Vec<u8>>> {
188 Ok(None)
189 }
190 async fn read_file(&self, _git_ref: &str, _path: &str) -> Result<Option<Vec<u8>>> {
191 Ok(None)
192 }
193 async fn fork(&self, _target_key: &str) -> Result<()> {
194 Ok(())
195 }
196 }
197
198 fn entry(name: &str, hash: &str, kind: EntryKind) -> TreeEntry {
199 TreeEntry { name: name.into(), hash: hash.into(), kind }
200 }
201
202 fn commit(hash: &str, tree: &str, parent: Option<&str>) -> Commit {
203 Commit {
204 hash: hash.into(),
205 tree_hash: tree.into(),
206 message: format!("commit {hash}"),
207 author: Signature { name: "a".into(), email: "a@example.com".into() },
208 parents: parent.map(|p| vec![p.to_owned()]).unwrap_or_default(),
209 authored_at: String::new(),
210 }
211 }
212
213 /// c1 adds README and src/a.rs; c2 changes src/a.rs; c3 changes README.
214 fn repo() -> Fake {
215 let mut fake = Fake::default();
216 fake.trees.insert("src1".into(), vec![entry("a.rs", "a1", EntryKind::Blob)]);
217 fake.trees.insert("src2".into(), vec![entry("a.rs", "a2", EntryKind::Blob)]);
218 fake.trees.insert("root1".into(), vec![entry("README.md", "r1", EntryKind::Blob), entry("src", "src1", EntryKind::Tree)]);
219 fake.trees.insert("root2".into(), vec![entry("README.md", "r1", EntryKind::Blob), entry("src", "src2", EntryKind::Tree)]);
220 fake.trees.insert("root3".into(), vec![entry("README.md", "r2", EntryKind::Blob), entry("src", "src2", EntryKind::Tree)]);
221 fake.history = vec![commit("c3", "root3", Some("c2")), commit("c2", "root2", Some("c1")), commit("c1", "root1", None)];
222 fake
223 }
224
225 fn by_name(found: Vec<LastCommit>) -> HashMap<String, String> {
226 found.into_iter().map(|last| (last.name, last.commit.hash)).collect()
227 }
228
229 #[test]
230 fn each_root_entry_gets_the_newest_commit_that_changed_it() {
A last-commits walk answers within 2.5 s with what it has, and keeps only finished answers231 let (found, complete) = run(last_commits(&repo(), "main", "", &|| false)).unwrap();
Branches and Tags pages, each file's last commit, and the branch menu on files232 assert!(complete);
233 let found = by_name(found);
234 assert_eq!(found["README.md"], "c3");
235 assert_eq!(found["src"], "c2");
236 }
237
238 #[test]
239 fn a_subdirectory_is_walked_by_its_own_tree() {
A last-commits walk answers within 2.5 s with what it has, and keeps only finished answers240 let (found, complete) = run(last_commits(&repo(), "main", "src", &|| false)).unwrap();
Branches and Tags pages, each file's last commit, and the branch menu on files241 assert!(complete);
242 assert_eq!(by_name(found)["a.rs"], "c2");
243 }
244
245 #[test]
246 fn an_entry_unchanged_since_the_first_commit_belongs_to_it() {
247 let mut fake = repo();
248 fake.trees.insert("root2".into(), vec![entry("README.md", "r1", EntryKind::Blob), entry("src", "src1", EntryKind::Tree)]);
249 fake.trees.insert("root3".into(), vec![entry("README.md", "r2", EntryKind::Blob), entry("src", "src1", EntryKind::Tree)]);
A last-commits walk answers within 2.5 s with what it has, and keeps only finished answers250 let (found, complete) = run(last_commits(&fake, "main", "", &|| false)).unwrap();
Branches and Tags pages, each file's last commit, and the branch menu on files251 assert!(complete);
252 assert_eq!(by_name(found)["src"], "c1");
253 }
254
255 #[test]
256 fn a_walk_cut_short_leaves_the_rest_unknown() {
257 let mut fake = repo();
258 // c1 has a parent the walk never reaches.
259 fake.history[2].parents = vec!["c0".into()];
260 fake.trees.insert("root2".into(), vec![entry("README.md", "r1", EntryKind::Blob), entry("src", "src1", EntryKind::Tree)]);
261 fake.trees.insert("root3".into(), vec![entry("README.md", "r2", EntryKind::Blob), entry("src", "src1", EntryKind::Tree)]);
A last-commits walk answers within 2.5 s with what it has, and keeps only finished answers262 let (found, complete) = run(last_commits(&fake, "main", "", &|| false)).unwrap();
Branches and Tags pages, each file's last commit, and the branch menu on files263 assert!(!complete);
264 let found = by_name(found);
265 assert_eq!(found["README.md"], "c3");
266 assert!(!found.contains_key("src"));
267 }
268}