| 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 | |
| 10 | use std::collections::HashMap; |
| 11 | |
| 12 | use g1t_contracts::repos::{Commit, EntryKind, LastCommit, TreeEntry}; |
| 13 | use worker::Result; |
| 14 | |
| 15 | use crate::store::GitRepo; |
| 16 | |
| 17 | /// How far back the history is walked. |
| 18 | pub 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. |
| 21 | const READ_AHEAD: usize = 24; |
| 22 | /// Commits of history read at a time. |
| 23 | const PAGE: u32 = 48; |
| 24 | |
| 25 | /// Reads trees, remembering those already read: commits share most of them. |
| 26 | struct Trees<'a, R: GitRepo> { |
| 27 | repo: &'a R, |
| 28 | read: HashMap<String, Option<Vec<TreeEntry>>>, |
| 29 | } |
| 30 | |
| 31 | impl<'a, R: GitRepo> Trees<'a, R> { |
| 32 | /// 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 | |
| 60 | 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 |
| 93 | /// entry was given one. `out_of_time` is asked between batches; once it |
| 94 | /// says so the walk stops with what it has, incomplete. |
| 95 | pub 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)> { |
| 101 | // 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 { |
| 105 | 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() }); |
| 113 | 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 | } |
| 121 | } |
| 122 | if index % READ_AHEAD == 0 { |
| 123 | if index > 0 && out_of_time() { |
| 124 | break; |
| 125 | } |
| 126 | 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 | } |
| 129 | let commit = history[index].clone(); |
| 130 | let Some(parent) = history.get(index + 1).cloned() else { |
| 131 | // 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(..) { |
| 135 | give(&mut found, name, &commit); |
| 136 | } |
| 137 | } |
| 138 | break; |
| 139 | }; |
| 140 | index += 1; |
| 141 | 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 { |
| 148 | give(&mut found, name, &commit); |
| 149 | } |
| 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)] |
| 159 | mod 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 | } |
| 189 | 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()) |
| 193 | } |
| 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() { |
| 244 | let (found, complete) = run(last_commits(&repo(), "main", "", &|| false)).unwrap(); |
| 245 | 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() { |
| 253 | let (found, complete) = run(last_commits(&repo(), "main", "src", &|| false)).unwrap(); |
| 254 | 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)]); |
| 263 | let (found, complete) = run(last_commits(&fake, "main", "", &|| false)).unwrap(); |
| 264 | 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)]); |
| 275 | let (found, complete) = run(last_commits(&fake, "main", "", &|| false)).unwrap(); |
| 276 | assert!(!complete); |
| 277 | let found = by_name(found); |
| 278 | assert_eq!(found["README.md"], "c3"); |
| 279 | assert!(!found.contains_key("src")); |
| 280 | } |
| 281 | } |