Sign in

flagon-io/g1t

public

g1t/services/repos/src/last_commits.rs

224 lines9,032 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;
19
20/// Reads trees, remembering those already read: commits share most of them.
21struct Trees<'a, R: GitRepo> {
22 repo: &'a R,
23 read: HashMap<String, Option<Vec<TreeEntry>>>,
24}
25
26impl<'a, R: GitRepo> Trees<'a, R> {
27 async fn get(&mut self, hash: &str) -> Result<Option<Vec<TreeEntry>>> {
28 if let Some(found) = self.read.get(hash) {
29 return Ok(found.clone());
30 }
31 let found = self.repo.read_tree(hash).await?;
32 self.read.insert(hash.to_owned(), found.clone());
33 Ok(found)
34 }
35
36 /// The tree hash of `path` in a commit's root tree; the root for an empty path.
37 async fn dir(&mut self, root: &str, path: &str) -> Result<Option<String>> {
38 let mut hash = root.to_owned();
39 for segment in path.split('/').filter(|segment| !segment.is_empty()) {
40 let Some(entries) = self.get(&hash).await? else {
41 return Ok(None);
42 };
43 match entries.into_iter().find(|entry| entry.name == segment && entry.kind == EntryKind::Tree) {
44 Some(entry) => hash = entry.hash,
45 None => return Ok(None),
46 }
47 }
48 Ok(Some(hash))
49 }
50
51 async fn entries(&mut self, dir: Option<&str>) -> Result<HashMap<String, String>> {
52 let Some(dir) = dir else {
53 return Ok(HashMap::new());
54 };
55 Ok(self.get(dir).await?.unwrap_or_default().into_iter().map(|entry| (entry.name, entry.hash)).collect())
56 }
57}
58
59/// The last commit of each entry of `path` at `git_ref`, and whether every
60/// entry was given one.
61pub async fn last_commits<R: GitRepo>(repo: &R, git_ref: &str, path: &str) -> Result<(Vec<LastCommit>, bool)> {
62 let history = repo.log(git_ref, MAX_COMMITS).await?;
63 let Some(head) = history.first() else {
64 return Ok((Vec::new(), true));
65 };
66 let mut trees = Trees { repo, read: HashMap::new() };
67 let mut dir = trees.dir(&head.tree_hash, path).await?;
68 let mut current = trees.entries(dir.as_deref()).await?;
69 let mut open: Vec<String> = current.keys().cloned().collect();
70 let mut found: Vec<LastCommit> = Vec::new();
71 let give = |found: &mut Vec<LastCommit>, name: String, commit: &Commit| found.push(LastCommit { name, commit: commit.clone() });
72 for (index, commit) in history.iter().enumerate() {
73 if open.is_empty() {
74 break;
75 }
76 let Some(parent) = history.get(index + 1) else {
77 // The oldest commit read. If it is the first commit there is,
78 // what is left was added by it.
79 if commit.parents.is_empty() {
80 for name in open.drain(..) {
81 give(&mut found, name, commit);
82 }
83 }
84 break;
85 };
86 let parent_dir = trees.dir(&parent.tree_hash, path).await?;
87 if parent_dir == dir {
88 continue;
89 }
90 let before = trees.entries(parent_dir.as_deref()).await?;
91 let (changed, still): (Vec<String>, Vec<String>) = open.into_iter().partition(|name| before.get(name) != current.get(name));
92 for name in changed {
93 give(&mut found, name, commit);
94 }
95 open = still;
96 dir = parent_dir;
97 current = before;
98 }
99 let complete = open.is_empty();
100 Ok((found, complete))
101}
102
103#[cfg(test)]
104mod tests {
105 use std::future::Future;
106 use std::pin::pin;
107 use std::task::{Context, Poll, Waker};
108
109 use g1t_contracts::repos::{Branch, GitAccess, Signature};
110
111 use super::*;
112 use crate::store::Scope;
113
114 fn run<F: Future>(future: F) -> F::Output {
115 match pin!(future).as_mut().poll(&mut Context::from_waker(Waker::noop())) {
116 Poll::Ready(output) => output,
117 Poll::Pending => panic!("the fake store never waits"),
118 }
119 }
120
121 #[derive(Default)]
122 struct Fake {
123 trees: HashMap<String, Vec<TreeEntry>>,
124 history: Vec<Commit>,
125 }
126
127 impl GitRepo for Fake {
128 async fn access(&self, _scope: Scope) -> Result<GitAccess> {
129 unimplemented!()
130 }
131 async fn branches(&self) -> Result<Vec<Branch>> {
132 Ok(Vec::new())
133 }
134 async fn log(&self, _git_ref: &str, limit: u32) -> Result<Vec<Commit>> {
135 Ok(self.history.iter().take(limit as usize).cloned().collect())
136 }
137 async fn parents(&self, _commit_hash: &str) -> Result<Option<Vec<String>>> {
138 Ok(None)
139 }
140 async fn read_tree(&self, tree_hash: &str) -> Result<Option<Vec<TreeEntry>>> {
141 Ok(self.trees.get(tree_hash).cloned())
142 }
143 async fn read_blob(&self, _blob_hash: &str) -> Result<Option<Vec<u8>>> {
144 Ok(None)
145 }
146 async fn read_file(&self, _git_ref: &str, _path: &str) -> Result<Option<Vec<u8>>> {
147 Ok(None)
148 }
149 async fn fork(&self, _target_key: &str) -> Result<()> {
150 Ok(())
151 }
152 }
153
154 fn entry(name: &str, hash: &str, kind: EntryKind) -> TreeEntry {
155 TreeEntry { name: name.into(), hash: hash.into(), kind }
156 }
157
158 fn commit(hash: &str, tree: &str, parent: Option<&str>) -> Commit {
159 Commit {
160 hash: hash.into(),
161 tree_hash: tree.into(),
162 message: format!("commit {hash}"),
163 author: Signature { name: "a".into(), email: "a@example.com".into() },
164 parents: parent.map(|p| vec![p.to_owned()]).unwrap_or_default(),
165 authored_at: String::new(),
166 }
167 }
168
169 /// c1 adds README and src/a.rs; c2 changes src/a.rs; c3 changes README.
170 fn repo() -> Fake {
171 let mut fake = Fake::default();
172 fake.trees.insert("src1".into(), vec![entry("a.rs", "a1", EntryKind::Blob)]);
173 fake.trees.insert("src2".into(), vec![entry("a.rs", "a2", EntryKind::Blob)]);
174 fake.trees.insert("root1".into(), vec![entry("README.md", "r1", EntryKind::Blob), entry("src", "src1", EntryKind::Tree)]);
175 fake.trees.insert("root2".into(), vec![entry("README.md", "r1", EntryKind::Blob), entry("src", "src2", EntryKind::Tree)]);
176 fake.trees.insert("root3".into(), vec![entry("README.md", "r2", EntryKind::Blob), entry("src", "src2", EntryKind::Tree)]);
177 fake.history = vec![commit("c3", "root3", Some("c2")), commit("c2", "root2", Some("c1")), commit("c1", "root1", None)];
178 fake
179 }
180
181 fn by_name(found: Vec<LastCommit>) -> HashMap<String, String> {
182 found.into_iter().map(|last| (last.name, last.commit.hash)).collect()
183 }
184
185 #[test]
186 fn each_root_entry_gets_the_newest_commit_that_changed_it() {
187 let (found, complete) = run(last_commits(&repo(), "main", "")).unwrap();
188 assert!(complete);
189 let found = by_name(found);
190 assert_eq!(found["README.md"], "c3");
191 assert_eq!(found["src"], "c2");
192 }
193
194 #[test]
195 fn a_subdirectory_is_walked_by_its_own_tree() {
196 let (found, complete) = run(last_commits(&repo(), "main", "src")).unwrap();
197 assert!(complete);
198 assert_eq!(by_name(found)["a.rs"], "c2");
199 }
200
201 #[test]
202 fn an_entry_unchanged_since_the_first_commit_belongs_to_it() {
203 let mut fake = repo();
204 fake.trees.insert("root2".into(), vec![entry("README.md", "r1", EntryKind::Blob), entry("src", "src1", EntryKind::Tree)]);
205 fake.trees.insert("root3".into(), vec![entry("README.md", "r2", EntryKind::Blob), entry("src", "src1", EntryKind::Tree)]);
206 let (found, complete) = run(last_commits(&fake, "main", "")).unwrap();
207 assert!(complete);
208 assert_eq!(by_name(found)["src"], "c1");
209 }
210
211 #[test]
212 fn a_walk_cut_short_leaves_the_rest_unknown() {
213 let mut fake = repo();
214 // c1 has a parent the walk never reaches.
215 fake.history[2].parents = vec!["c0".into()];
216 fake.trees.insert("root2".into(), vec![entry("README.md", "r1", EntryKind::Blob), entry("src", "src1", EntryKind::Tree)]);
217 fake.trees.insert("root3".into(), vec![entry("README.md", "r2", EntryKind::Blob), entry("src", "src1", EntryKind::Tree)]);
218 let (found, complete) = run(last_commits(&fake, "main", "")).unwrap();
219 assert!(!complete);
220 let found = by_name(found);
221 assert_eq!(found["README.md"], "c3");
222 assert!(!found.contains_key("src"));
223 }
224}