Sign in

flagon-io/g1t

public

g1t/services/repos/src/last_commits.rs

281 lines11,896 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;
A last-commits walk reads history 48 commits at a time, within its budget22/// Commits of history read at a time.
23const PAGE: u32 = 48;
Branches and Tags pages, each file's last commit, and the branch menu on files24
25/// Reads trees, remembering those already read: commits share most of them.
26struct Trees<'a, R: GitRepo> {
27 repo: &'a R,
28 read: HashMap<String, Option<Vec<TreeEntry>>>,
29}
30
31impl<'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 them32 /// Reads the trees not read yet, all at once.
33 async fn prefetch(&mut self, hashes: impl IntoIterator<Item = String>) -> Result<()> {
34 let mut wanted: Vec<String> = hashes.into_iter().filter(|hash| !self.read.contains_key(hash)).collect();
35 wanted.sort();
36 wanted.dedup();
37 let found = futures_util::future::join_all(wanted.iter().map(|hash| self.repo.read_tree(hash))).await;
38 for (hash, tree) in wanted.into_iter().zip(found) {
39 self.read.insert(hash, tree?);
40 }
41 Ok(())
42 }
43
44 /// Reads, level by level and each level at once, the trees on the way
45 /// to `path` in each of `roots`, and the directory itself.
46 async fn prefetch_dirs(&mut self, roots: Vec<String>, path: &str) -> Result<()> {
47 let mut level = roots;
48 for segment in path.split('/').filter(|segment| !segment.is_empty()) {
49 self.prefetch(level.clone()).await?;
50 level = level
51 .iter()
52 .filter_map(|hash| {
53 self.read.get(hash)?.as_ref()?.iter().find(|entry| entry.name == segment && entry.kind == EntryKind::Tree).map(|entry| entry.hash.clone())
54 })
55 .collect();
56 }
57 self.prefetch(level).await
58 }
59
Branches and Tags pages, each file's last commit, and the branch menu on files60 async fn get(&mut self, hash: &str) -> Result<Option<Vec<TreeEntry>>> {
61 if let Some(found) = self.read.get(hash) {
62 return Ok(found.clone());
63 }
64 let found = self.repo.read_tree(hash).await?;
65 self.read.insert(hash.to_owned(), found.clone());
66 Ok(found)
67 }
68
69 /// The tree hash of `path` in a commit's root tree; the root for an empty path.
70 async fn dir(&mut self, root: &str, path: &str) -> Result<Option<String>> {
71 let mut hash = root.to_owned();
72 for segment in path.split('/').filter(|segment| !segment.is_empty()) {
73 let Some(entries) = self.get(&hash).await? else {
74 return Ok(None);
75 };
76 match entries.into_iter().find(|entry| entry.name == segment && entry.kind == EntryKind::Tree) {
77 Some(entry) => hash = entry.hash,
78 None => return Ok(None),
79 }
80 }
81 Ok(Some(hash))
82 }
83
84 async fn entries(&mut self, dir: Option<&str>) -> Result<HashMap<String, String>> {
85 let Some(dir) = dir else {
86 return Ok(HashMap::new());
87 };
88 Ok(self.get(dir).await?.unwrap_or_default().into_iter().map(|entry| (entry.name, entry.hash)).collect())
89 }
90}
91
92/// 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 answers93/// entry was given one. `out_of_time` is asked between batches; once it
94/// says so the walk stops with what it has, incomplete.
95pub async fn last_commits<R: GitRepo>(
96 repo: &R,
97 git_ref: &str,
98 path: &str,
99 out_of_time: &dyn Fn() -> bool,
100) -> Result<(Vec<LastCommit>, bool)> {
A last-commits walk reads history 48 commits at a time, within its budget101 // History a page at a time, so a walk that is out of time stops
102 // between pages rather than after reading all of it.
103 let mut history = repo.log(git_ref, PAGE).await?;
104 let Some(head) = history.first().cloned() else {
Branches and Tags pages, each file's last commit, and the branch menu on files105 return Ok((Vec::new(), true));
106 };
107 let mut trees = Trees { repo, read: HashMap::new() };
108 let mut dir = trees.dir(&head.tree_hash, path).await?;
109 let mut current = trees.entries(dir.as_deref()).await?;
110 let mut open: Vec<String> = current.keys().cloned().collect();
111 let mut found: Vec<LastCommit> = Vec::new();
112 let give = |found: &mut Vec<LastCommit>, name: String, commit: &Commit| found.push(LastCommit { name, commit: commit.clone() });
A last-commits walk reads history 48 commits at a time, within its budget113 let mut index = 0;
114 while !open.is_empty() && index < history.len() {
115 // Read the next page once the walk reaches the end of this one.
116 if index + 1 >= history.len() && history.len() < MAX_COMMITS as usize && !out_of_time() {
117 if let Some(parent) = history.last().and_then(|commit| commit.parents.first()).cloned() {
118 let more = repo.log(&parent, PAGE).await?;
119 history.extend(more);
120 }
Branches and Tags pages, each file's last commit, and the branch menu on files121 }
Last commits read trees two dozen commits at a time, and the file list waits at most 3 s for them122 if index % READ_AHEAD == 0 {
A last-commits walk answers within 2.5 s with what it has, and keeps only finished answers123 if index > 0 && out_of_time() {
124 break;
125 }
Last commits read trees two dozen commits at a time, and the file list waits at most 3 s for them126 let ahead = history.iter().skip(index + 1).take(READ_AHEAD).map(|commit| commit.tree_hash.clone()).collect();
127 trees.prefetch_dirs(ahead, path).await?;
128 }
A last-commits walk reads history 48 commits at a time, within its budget129 let commit = history[index].clone();
130 let Some(parent) = history.get(index + 1).cloned() else {
Branches and Tags pages, each file's last commit, and the branch menu on files131 // The oldest commit read. If it is the first commit there is,
132 // what is left was added by it.
133 if commit.parents.is_empty() {
134 for name in open.drain(..) {
A last-commits walk reads history 48 commits at a time, within its budget135 give(&mut found, name, &commit);
Branches and Tags pages, each file's last commit, and the branch menu on files136 }
137 }
138 break;
139 };
A last-commits walk reads history 48 commits at a time, within its budget140 index += 1;
Branches and Tags pages, each file's last commit, and the branch menu on files141 let parent_dir = trees.dir(&parent.tree_hash, path).await?;
142 if parent_dir == dir {
143 continue;
144 }
145 let before = trees.entries(parent_dir.as_deref()).await?;
146 let (changed, still): (Vec<String>, Vec<String>) = open.into_iter().partition(|name| before.get(name) != current.get(name));
147 for name in changed {
A last-commits walk reads history 48 commits at a time, within its budget148 give(&mut found, name, &commit);
Branches and Tags pages, each file's last commit, and the branch menu on files149 }
150 open = still;
151 dir = parent_dir;
152 current = before;
153 }
154 let complete = open.is_empty();
155 Ok((found, complete))
156}
157
158#[cfg(test)]
159mod tests {
160 use std::future::Future;
161 use std::pin::pin;
162 use std::task::{Context, Poll, Waker};
163
164 use g1t_contracts::repos::{Branch, GitAccess, Signature};
165
166 use super::*;
167 use crate::store::Scope;
168
169 fn run<F: Future>(future: F) -> F::Output {
170 match pin!(future).as_mut().poll(&mut Context::from_waker(Waker::noop())) {
171 Poll::Ready(output) => output,
172 Poll::Pending => panic!("the fake store never waits"),
173 }
174 }
175
176 #[derive(Default)]
177 struct Fake {
178 trees: HashMap<String, Vec<TreeEntry>>,
179 history: Vec<Commit>,
180 }
181
182 impl GitRepo for Fake {
183 async fn access(&self, _scope: Scope) -> Result<GitAccess> {
184 unimplemented!()
185 }
186 async fn branches(&self) -> Result<Vec<Branch>> {
187 Ok(Vec::new())
188 }
A last-commits walk reads history 48 commits at a time, within its budget189 async fn log(&self, git_ref: &str, limit: u32) -> Result<Vec<Commit>> {
190 // A branch name starts at the head; a hash at that commit; anything else is unknown.
191 let start = if git_ref == "main" { Some(0) } else { self.history.iter().position(|commit| commit.hash == git_ref) };
192 Ok(start.map(|start| self.history.iter().skip(start).take(limit as usize).cloned().collect()).unwrap_or_default())
Branches and Tags pages, each file's last commit, and the branch menu on files193 }
194 async fn parents(&self, _commit_hash: &str) -> Result<Option<Vec<String>>> {
195 Ok(None)
196 }
197 async fn read_tree(&self, tree_hash: &str) -> Result<Option<Vec<TreeEntry>>> {
198 Ok(self.trees.get(tree_hash).cloned())
199 }
200 async fn read_blob(&self, _blob_hash: &str) -> Result<Option<Vec<u8>>> {
201 Ok(None)
202 }
203 async fn read_file(&self, _git_ref: &str, _path: &str) -> Result<Option<Vec<u8>>> {
204 Ok(None)
205 }
206 async fn fork(&self, _target_key: &str) -> Result<()> {
207 Ok(())
208 }
209 }
210
211 fn entry(name: &str, hash: &str, kind: EntryKind) -> TreeEntry {
212 TreeEntry { name: name.into(), hash: hash.into(), kind }
213 }
214
215 fn commit(hash: &str, tree: &str, parent: Option<&str>) -> Commit {
216 Commit {
217 hash: hash.into(),
218 tree_hash: tree.into(),
219 message: format!("commit {hash}"),
220 author: Signature { name: "a".into(), email: "a@example.com".into() },
221 parents: parent.map(|p| vec![p.to_owned()]).unwrap_or_default(),
222 authored_at: String::new(),
223 }
224 }
225
226 /// c1 adds README and src/a.rs; c2 changes src/a.rs; c3 changes README.
227 fn repo() -> Fake {
228 let mut fake = Fake::default();
229 fake.trees.insert("src1".into(), vec![entry("a.rs", "a1", EntryKind::Blob)]);
230 fake.trees.insert("src2".into(), vec![entry("a.rs", "a2", EntryKind::Blob)]);
231 fake.trees.insert("root1".into(), vec![entry("README.md", "r1", EntryKind::Blob), entry("src", "src1", EntryKind::Tree)]);
232 fake.trees.insert("root2".into(), vec![entry("README.md", "r1", EntryKind::Blob), entry("src", "src2", EntryKind::Tree)]);
233 fake.trees.insert("root3".into(), vec![entry("README.md", "r2", EntryKind::Blob), entry("src", "src2", EntryKind::Tree)]);
234 fake.history = vec![commit("c3", "root3", Some("c2")), commit("c2", "root2", Some("c1")), commit("c1", "root1", None)];
235 fake
236 }
237
238 fn by_name(found: Vec<LastCommit>) -> HashMap<String, String> {
239 found.into_iter().map(|last| (last.name, last.commit.hash)).collect()
240 }
241
242 #[test]
243 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 answers244 let (found, complete) = run(last_commits(&repo(), "main", "", &|| false)).unwrap();
Branches and Tags pages, each file's last commit, and the branch menu on files245 assert!(complete);
246 let found = by_name(found);
247 assert_eq!(found["README.md"], "c3");
248 assert_eq!(found["src"], "c2");
249 }
250
251 #[test]
252 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 answers253 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 files254 assert!(complete);
255 assert_eq!(by_name(found)["a.rs"], "c2");
256 }
257
258 #[test]
259 fn an_entry_unchanged_since_the_first_commit_belongs_to_it() {
260 let mut fake = repo();
261 fake.trees.insert("root2".into(), vec![entry("README.md", "r1", EntryKind::Blob), entry("src", "src1", EntryKind::Tree)]);
262 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 answers263 let (found, complete) = run(last_commits(&fake, "main", "", &|| false)).unwrap();
Branches and Tags pages, each file's last commit, and the branch menu on files264 assert!(complete);
265 assert_eq!(by_name(found)["src"], "c1");
266 }
267
268 #[test]
269 fn a_walk_cut_short_leaves_the_rest_unknown() {
270 let mut fake = repo();
271 // c1 has a parent the walk never reaches.
272 fake.history[2].parents = vec!["c0".into()];
273 fake.trees.insert("root2".into(), vec![entry("README.md", "r1", EntryKind::Blob), entry("src", "src1", EntryKind::Tree)]);
274 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 answers275 let (found, complete) = run(last_commits(&fake, "main", "", &|| false)).unwrap();
Branches and Tags pages, each file's last commit, and the branch menu on files276 assert!(!complete);
277 let found = by_name(found);
278 assert_eq!(found["README.md"], "c3");
279 assert!(!found.contains_key("src"));
280 }
281}