| 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 | //! first commit there is, once the walk reaches it. |
| 9 | //! |
| 10 | //! A walk is never thrown away. What it found is remembered as |
| 11 | //! [`Progress`] per repository, ref and path ([`Memo`]), with the head it |
| 12 | //! started from and, when it had to stop, the commit to go on from: |
| 13 | //! |
| 14 | //! - The same head again goes on from where the last walk stopped, so a |
| 15 | //! long history is walked to its first commit over as many calls as it |
| 16 | //! takes, each within the Worker's limits ([`MAX_READS`]). |
| 17 | //! - A new head walks only back to the remembered one, when that is on its |
| 18 | //! first-parent chain: an entry whose hash did not change in between keeps |
| 19 | //! the commit remembered for it. A push then costs only its own commits. |
| 20 | //! When the remembered head never comes up (a force-push), the walk is a |
| 21 | //! full one. |
| 22 | |
| 23 | use std::collections::{HashMap, HashSet}; |
| 24 | |
| 25 | use g1t_contracts::repos::{Commit, EntryKind, LastCommit, TreeEntry}; |
| 26 | use serde::{Deserialize, Serialize}; |
| 27 | use worker::Result; |
| 28 | |
| 29 | use crate::shared::Shared; |
| 30 | use crate::store::GitRepo; |
| 31 | |
| 32 | /// Reads of the store one call makes at most. Each costs up to three |
| 33 | /// subrequests (a Cache API look, the store, a Cache API put), so this |
| 34 | /// keeps a call well inside the 10,000 a Worker invocation may make, with |
| 35 | /// room for the rest of the request. A repository's root takes about one |
| 36 | /// read per commit, so a call walks some 2,000 commits, and the next call |
| 37 | /// goes on from there. |
| 38 | pub const MAX_READS: u32 = 2_500; |
| 39 | /// Commits whose trees are read together, ahead of the walk: each read is a |
| 40 | /// round trip to the store, so reading them one by one is what is slow. |
| 41 | const READ_AHEAD: usize = 24; |
| 42 | /// Commits of history read at a time. |
| 43 | const PAGE: u32 = 48; |
| 44 | |
| 45 | /// What walks found for a directory, from `head`: kept between walks. |
| 46 | #[derive(Clone, Debug, Serialize, Deserialize)] |
| 47 | pub struct Progress { |
| 48 | /// The commit the walks started from. |
| 49 | pub head: String, |
| 50 | /// The entries given their commit. |
| 51 | pub found: Vec<LastCommit>, |
| 52 | /// The entries not given one yet. |
| 53 | pub open: Vec<String>, |
| 54 | /// The commit to go on from while some are open: the newest not yet |
| 55 | /// compared with its parent. `None` once no walk can find more. |
| 56 | pub at: Option<String>, |
| 57 | } |
| 58 | |
| 59 | impl Progress { |
| 60 | pub fn complete(&self) -> bool { |
| 61 | self.open.is_empty() |
| 62 | } |
| 63 | |
| 64 | /// Whether no walk could find more. |
| 65 | pub fn settled(&self) -> bool { |
| 66 | self.open.is_empty() || self.at.is_none() |
| 67 | } |
| 68 | } |
| 69 | |
| 70 | /// One call's walk: where it got to, and how many reads of the store it made. |
| 71 | pub struct Walk { |
| 72 | pub progress: Progress, |
| 73 | pub reads: u32, |
| 74 | } |
| 75 | |
| 76 | /// Reads trees, remembering those already read: commits share most of them. |
| 77 | struct Trees<'a, R: GitRepo> { |
| 78 | repo: &'a R, |
| 79 | read: HashMap<String, Option<Vec<TreeEntry>>>, |
| 80 | /// Reads of the store so far, trees and history. |
| 81 | reads: u32, |
| 82 | } |
| 83 | |
| 84 | impl<'a, R: GitRepo> Trees<'a, R> { |
| 85 | async fn log(&mut self, from: &str) -> Result<Vec<Commit>> { |
| 86 | self.reads += 1; |
| 87 | self.repo.log(from, PAGE).await |
| 88 | } |
| 89 | |
| 90 | /// Reads the trees not read yet, all at once. |
| 91 | async fn prefetch(&mut self, hashes: impl IntoIterator<Item = String>) -> Result<()> { |
| 92 | let mut wanted: Vec<String> = hashes.into_iter().filter(|hash| !self.read.contains_key(hash)).collect(); |
| 93 | wanted.sort(); |
| 94 | wanted.dedup(); |
| 95 | self.reads += wanted.len() as u32; |
| 96 | let found = futures_util::future::join_all(wanted.iter().map(|hash| self.repo.read_tree(hash))).await; |
| 97 | for (hash, tree) in wanted.into_iter().zip(found) { |
| 98 | self.read.insert(hash, tree?); |
| 99 | } |
| 100 | Ok(()) |
| 101 | } |
| 102 | |
| 103 | /// Reads, level by level and each level at once, the trees on the way |
| 104 | /// to `path` in each of `roots`, and the directory itself. |
| 105 | async fn prefetch_dirs(&mut self, roots: Vec<String>, path: &str) -> Result<()> { |
| 106 | let mut level = roots; |
| 107 | for segment in path.split('/').filter(|segment| !segment.is_empty()) { |
| 108 | self.prefetch(level.clone()).await?; |
| 109 | level = level |
| 110 | .iter() |
| 111 | .filter_map(|hash| { |
| 112 | self.read.get(hash)?.as_ref()?.iter().find(|entry| entry.name == segment && entry.kind == EntryKind::Tree).map(|entry| entry.hash.clone()) |
| 113 | }) |
| 114 | .collect(); |
| 115 | } |
| 116 | self.prefetch(level).await |
| 117 | } |
| 118 | |
| 119 | async fn get(&mut self, hash: &str) -> Result<Option<Vec<TreeEntry>>> { |
| 120 | if let Some(found) = self.read.get(hash) { |
| 121 | return Ok(found.clone()); |
| 122 | } |
| 123 | self.reads += 1; |
| 124 | let found = self.repo.read_tree(hash).await?; |
| 125 | self.read.insert(hash.to_owned(), found.clone()); |
| 126 | Ok(found) |
| 127 | } |
| 128 | |
| 129 | /// The tree hash of `path` in a commit's root tree; the root for an empty path. |
| 130 | async fn dir(&mut self, root: &str, path: &str) -> Result<Option<String>> { |
| 131 | let mut hash = root.to_owned(); |
| 132 | for segment in path.split('/').filter(|segment| !segment.is_empty()) { |
| 133 | let Some(entries) = self.get(&hash).await? else { |
| 134 | return Ok(None); |
| 135 | }; |
| 136 | match entries.into_iter().find(|entry| entry.name == segment && entry.kind == EntryKind::Tree) { |
| 137 | Some(entry) => hash = entry.hash, |
| 138 | None => return Ok(None), |
| 139 | } |
| 140 | } |
| 141 | Ok(Some(hash)) |
| 142 | } |
| 143 | |
| 144 | async fn entries(&mut self, dir: Option<&str>) -> Result<HashMap<String, String>> { |
| 145 | let Some(dir) = dir else { |
| 146 | return Ok(HashMap::new()); |
| 147 | }; |
| 148 | Ok(self.get(dir).await?.unwrap_or_default().into_iter().map(|entry| (entry.name, entry.hash)).collect()) |
| 149 | } |
| 150 | } |
| 151 | |
| 152 | /// Where a walk stands: the history ahead from the commit it is at, and |
| 153 | /// that commit's directory and entries. |
| 154 | struct Cursor { |
| 155 | history: Vec<Commit>, |
| 156 | index: usize, |
| 157 | /// The trees of history before this index have been read ahead. |
| 158 | read_ahead_to: usize, |
| 159 | dir: Option<String>, |
| 160 | current: HashMap<String, String>, |
| 161 | } |
| 162 | |
| 163 | impl Cursor { |
| 164 | /// At the commit `from`, or `None` when there is no such commit. |
| 165 | async fn at<R: GitRepo>(trees: &mut Trees<'_, R>, from: &str, path: &str) -> Result<Option<Cursor>> { |
| 166 | let history = trees.log(from).await?; |
| 167 | let Some(first) = history.first() else { |
| 168 | return Ok(None); |
| 169 | }; |
| 170 | let dir = trees.dir(&first.tree_hash.clone(), path).await?; |
| 171 | let current = trees.entries(dir.as_deref()).await?; |
| 172 | Ok(Some(Cursor { history, index: 0, read_ahead_to: 0, dir, current })) |
| 173 | } |
| 174 | |
| 175 | fn commit(&self) -> &Commit { |
| 176 | &self.history[self.index] |
| 177 | } |
| 178 | } |
| 179 | |
| 180 | /// The last commit of each entry of `path` at the commit `head`, going on |
| 181 | /// from `kept` (what earlier walks of the same ref and path found). The |
| 182 | /// walk stops, for the next call to go on from, once `out_of_time` says so |
| 183 | /// (asked between batches, after some progress) or before it would make |
| 184 | /// more than `max_reads` reads of the store. |
| 185 | pub async fn last_commits<R: GitRepo>( |
| 186 | repo: &R, |
| 187 | head: &str, |
| 188 | path: &str, |
| 189 | kept: Option<Progress>, |
| 190 | out_of_time: &dyn Fn() -> bool, |
| 191 | max_reads: u32, |
| 192 | ) -> Result<Walk> { |
| 193 | let mut trees = Trees { repo, read: HashMap::new(), reads: 0 }; |
| 194 | let segments = path.split('/').filter(|segment| !segment.is_empty()).count(); |
| 195 | // The most a batch read ahead reads, and a page of history. |
| 196 | let batch = (READ_AHEAD * (segments + 1)) as u32 + 1; |
| 197 | let mut found: Vec<LastCommit> = Vec::new(); |
| 198 | let mut open: Vec<String> = Vec::new(); |
| 199 | // An earlier walk from another head, to stop at if it comes up. |
| 200 | let mut stop_at: Option<Progress> = None; |
| 201 | let fresh; |
| 202 | let start = match kept { |
| 203 | Some(kept) if kept.head == head => { |
| 204 | let Some(at) = kept.at.clone().filter(|_| !kept.open.is_empty()) else { |
| 205 | return Ok(Walk { progress: kept, reads: 0 }); |
| 206 | }; |
| 207 | found = kept.found; |
| 208 | open = kept.open; |
| 209 | fresh = false; |
| 210 | at |
| 211 | } |
| 212 | other => { |
| 213 | stop_at = other; |
| 214 | fresh = true; |
| 215 | head.to_owned() |
| 216 | } |
| 217 | }; |
| 218 | let Some(mut cursor) = Cursor::at(&mut trees, &start, path).await? else { |
| 219 | // An unknown head has nothing. A commit to go on from that cannot |
| 220 | // be read any more leaves what is open unknown. |
| 221 | return Ok(Walk { progress: Progress { head: head.to_owned(), found, open, at: None }, reads: trees.reads }); |
| 222 | }; |
| 223 | if fresh { |
| 224 | open = cursor.current.keys().cloned().collect(); |
| 225 | } |
| 226 | let give = |found: &mut Vec<LastCommit>, name: String, commit: &Commit| found.push(LastCommit { name, commit: commit.clone() }); |
| 227 | let mut walked = 0u32; |
| 228 | // Whether the walk had to stop with more to find. |
| 229 | let mut stopped = false; |
| 230 | while !open.is_empty() { |
| 231 | // The head an earlier walk started from: what has not changed |
| 232 | // since keeps what that walk found for it. |
| 233 | if stop_at.as_ref().is_some_and(|kept| kept.head == cursor.commit().hash) { |
| 234 | let Some(kept) = stop_at.take() else { break }; |
| 235 | let given: HashMap<&str, &LastCommit> = kept.found.iter().map(|last| (last.name.as_str(), last)).collect(); |
| 236 | let kept_open: HashSet<&str> = kept.open.iter().map(String::as_str).collect(); |
| 237 | let mut rest = Vec::new(); |
| 238 | for name in open.drain(..) { |
| 239 | match given.get(name.as_str()) { |
| 240 | Some(last) => found.push((*last).clone()), |
| 241 | None => rest.push(name), |
| 242 | } |
| 243 | } |
| 244 | open = rest; |
| 245 | // The rest were still open for that walk too: go on from where |
| 246 | // it stopped rather than walk the same history again. Otherwise |
| 247 | // (it did not know them) the walk goes on from here. |
| 248 | if !open.is_empty() && open.iter().all(|name| kept_open.contains(name.as_str())) { |
| 249 | let next = match &kept.at { |
| 250 | Some(at) => Cursor::at(&mut trees, at, path).await?, |
| 251 | None => None, |
| 252 | }; |
| 253 | // None: that walk found all there was to find. |
| 254 | let Some(next) = next else { break }; |
| 255 | cursor = next; |
| 256 | } |
| 257 | continue; |
| 258 | } |
| 259 | let needs_page = cursor.index + 1 >= cursor.history.len() && !cursor.commit().parents.is_empty(); |
| 260 | let needs_read_ahead = cursor.index >= cursor.read_ahead_to; |
| 261 | if (needs_page || needs_read_ahead) && walked > 0 && (out_of_time() || trees.reads + batch > max_reads) { |
| 262 | stopped = true; |
| 263 | break; |
| 264 | } |
| 265 | // The next page once the walk reaches the end of this one. |
| 266 | if needs_page { |
| 267 | let parent = cursor.commit().parents[0].clone(); |
| 268 | let more = trees.log(&parent).await?; |
| 269 | // What is behind the walk is not needed again. |
| 270 | cursor.history.drain(..cursor.index); |
| 271 | cursor.read_ahead_to = cursor.read_ahead_to.saturating_sub(cursor.index); |
| 272 | cursor.index = 0; |
| 273 | cursor.history.extend(more); |
| 274 | } |
| 275 | if cursor.index >= cursor.read_ahead_to { |
| 276 | // Nor are the trees already compared. |
| 277 | trees.read.clear(); |
| 278 | let ahead = cursor.history.iter().skip(cursor.index + 1).take(READ_AHEAD).map(|commit| commit.tree_hash.clone()).collect(); |
| 279 | trees.prefetch_dirs(ahead, path).await?; |
| 280 | cursor.read_ahead_to = cursor.index + READ_AHEAD; |
| 281 | } |
| 282 | let commit = cursor.commit().clone(); |
| 283 | let Some(parent) = cursor.history.get(cursor.index + 1).cloned() else { |
| 284 | // The oldest commit there is. If it is the first commit, what |
| 285 | // is left was added by it; if its parent could not be read, |
| 286 | // what is left is not known. |
| 287 | if commit.parents.is_empty() { |
| 288 | for name in open.drain(..) { |
| 289 | give(&mut found, name, &commit); |
| 290 | } |
| 291 | } |
| 292 | break; |
| 293 | }; |
| 294 | cursor.index += 1; |
| 295 | walked += 1; |
| 296 | let parent_dir = trees.dir(&parent.tree_hash, path).await?; |
| 297 | if parent_dir == cursor.dir { |
| 298 | continue; |
| 299 | } |
| 300 | let before = trees.entries(parent_dir.as_deref()).await?; |
| 301 | let (changed, still): (Vec<String>, Vec<String>) = open.into_iter().partition(|name| before.get(name) != cursor.current.get(name)); |
| 302 | for name in changed { |
| 303 | give(&mut found, name, &commit); |
| 304 | } |
| 305 | open = still; |
| 306 | cursor.dir = parent_dir; |
| 307 | cursor.current = before; |
| 308 | } |
| 309 | let at = (stopped && !open.is_empty()).then(|| cursor.commit().hash.clone()); |
| 310 | Ok(Walk { progress: Progress { head: head.to_owned(), found, open, at }, reads: trees.reads }) |
| 311 | } |
| 312 | |
| 313 | /// The commits on the first-parent chain from `head` that changed `path` |
| 314 | /// (a file or a directory; empty for the whole tree), newest first: at most |
| 315 | /// `limit`, within `max_reads` reads of the store and before `out_of_time` |
| 316 | /// says so. A commit changed the path when its hash there differs from its |
| 317 | /// parent's, appearing and going away included. `complete` is true when the |
| 318 | /// walk reached the first commit or found `limit`. |
| 319 | pub async fn path_log<R: GitRepo>( |
| 320 | repo: &R, |
| 321 | head: &str, |
| 322 | path: &str, |
| 323 | limit: usize, |
| 324 | out_of_time: &dyn Fn() -> bool, |
| 325 | max_reads: u32, |
| 326 | ) -> Result<(Vec<Commit>, bool)> { |
| 327 | let mut trees = Trees { repo, read: HashMap::new(), reads: 0 }; |
| 328 | let path = path.trim_matches('/'); |
| 329 | let (dir, name) = match path.rsplit_once('/') { |
| 330 | Some((dir, name)) => (dir.to_owned(), name.to_owned()), |
| 331 | None => (String::new(), path.to_owned()), |
| 332 | }; |
| 333 | let segments = dir.split('/').filter(|segment| !segment.is_empty()).count(); |
| 334 | let batch = (READ_AHEAD * (segments + 1)) as u32 + 1; |
| 335 | let mut history = trees.log(head).await?; |
| 336 | let mut changed = Vec::new(); |
| 337 | let mut index = 0usize; |
| 338 | let mut read_ahead_to = 0usize; |
| 339 | // The hash of the path in a commit's tree: the root's own for an empty path. |
| 340 | async fn hash_at<R: GitRepo>(trees: &mut Trees<'_, R>, root: &str, dir: &str, name: &str) -> Result<Option<String>> { |
| 341 | if name.is_empty() { |
| 342 | return Ok(Some(root.to_owned())); |
| 343 | } |
| 344 | let Some(parent) = trees.dir(root, dir).await? else { return Ok(None) }; |
| 345 | Ok(trees.entries(Some(&parent)).await?.remove(name)) |
| 346 | } |
| 347 | let Some(first) = history.first().cloned() else { return Ok((changed, true)) }; |
| 348 | let mut current = hash_at(&mut trees, &first.tree_hash, &dir, &name).await?; |
| 349 | loop { |
| 350 | if changed.len() >= limit { |
| 351 | return Ok((changed, true)); |
| 352 | } |
| 353 | let Some(commit) = history.get(index).cloned() else { return Ok((changed, true)) }; |
| 354 | let needs_page = index + 1 >= history.len() && !commit.parents.is_empty(); |
| 355 | if (needs_page || index >= read_ahead_to) && index > 0 && (out_of_time() || trees.reads + batch > max_reads) { |
| 356 | return Ok((changed, false)); |
| 357 | } |
| 358 | if needs_page { |
| 359 | let more = trees.log(&commit.parents[0]).await?; |
| 360 | history.drain(..index); |
| 361 | read_ahead_to = read_ahead_to.saturating_sub(index); |
| 362 | index = 0; |
| 363 | history.extend(more); |
| 364 | } |
| 365 | if index >= read_ahead_to { |
| 366 | trees.read.clear(); |
| 367 | let ahead = history.iter().skip(index + 1).take(READ_AHEAD).map(|commit| commit.tree_hash.clone()).collect(); |
| 368 | trees.prefetch_dirs(ahead, &dir).await?; |
| 369 | read_ahead_to = index + READ_AHEAD; |
| 370 | } |
| 371 | let Some(parent) = history.get(index + 1).cloned() else { |
| 372 | // The oldest commit read: the first commit added what it has. |
| 373 | let first = commit.parents.is_empty(); |
| 374 | if first && current.is_some() { |
| 375 | changed.push(commit); |
| 376 | } |
| 377 | return Ok((changed, first)); |
| 378 | }; |
| 379 | let before = hash_at(&mut trees, &parent.tree_hash, &dir, &name).await?; |
| 380 | if before != current { |
| 381 | changed.push(commit); |
| 382 | } |
| 383 | current = before; |
| 384 | index += 1; |
| 385 | } |
| 386 | } |
| 387 | |
| 388 | /// Where the progress for a ref and path of a repository is kept: in this |
| 389 | /// colo's cache, and shared between colos when the service has `GIT_CACHE` |
| 390 | /// (shared.rs). |
| 391 | pub struct Memo { |
| 392 | colo_url: String, |
| 393 | shared_key: String, |
| 394 | } |
| 395 | |
| 396 | /// How long progress is kept after its last walk. |
| 397 | const MEMO_TTL_SECONDS: u64 = 30 * 24 * 60 * 60; |
| 398 | |
| 399 | impl Memo { |
| 400 | pub fn new(repo_id: &str, git_ref: &str, path: &str) -> Memo { |
| 401 | let what = g1t_secrets::sha256_hex(&format!("{git_ref}\n{path}")); |
| 402 | Memo { |
| 403 | colo_url: format!("https://last-commits.g1t.internal/progress/v1/{repo_id}/{what}"), |
| 404 | shared_key: format!("last-commits:{repo_id}:{what}"), |
| 405 | } |
| 406 | } |
| 407 | |
| 408 | /// The progress kept, this colo's first. A failure to read is none. |
| 409 | pub async fn get(&self, shared: Option<&Shared>) -> Option<Progress> { |
| 410 | if let Ok(Some(mut response)) = worker::Cache::default().get(self.colo_url.as_str(), false).await |
| 411 | && let Ok(progress) = response.json::<Progress>().await |
| 412 | { |
| 413 | return Some(progress); |
| 414 | } |
| 415 | let bytes = shared?.get(&self.shared_key).await?; |
| 416 | serde_json::from_slice(&bytes).ok() |
| 417 | } |
| 418 | |
| 419 | /// Keeps `progress` here and in the shared store. A failure only costs |
| 420 | /// a longer walk later. |
| 421 | pub async fn keep(&self, shared: Option<&Shared>, progress: &Progress) { |
| 422 | let Ok(bytes) = serde_json::to_vec(progress) else { |
| 423 | return; |
| 424 | }; |
| 425 | let colo = async { |
| 426 | if let Ok(mut response) = worker::Response::from_bytes(bytes.clone()) { |
| 427 | let _ = response.headers_mut().set("cache-control", &format!("max-age={MEMO_TTL_SECONDS}")); |
| 428 | let _ = worker::Cache::default().put(self.colo_url.as_str(), response).await; |
| 429 | } |
| 430 | }; |
| 431 | let shared_put = async { |
| 432 | if let Some(shared) = shared { |
| 433 | shared.put(&self.shared_key, &bytes, MEMO_TTL_SECONDS).await; |
| 434 | } |
| 435 | }; |
| 436 | futures_util::future::join(colo, shared_put).await; |
| 437 | } |
| 438 | } |
| 439 | |
| 440 | #[cfg(test)] |
| 441 | mod tests { |
| 442 | use std::cell::RefCell; |
| 443 | use std::future::Future; |
| 444 | use std::pin::pin; |
| 445 | use std::task::{Context, Poll, Waker}; |
| 446 | |
| 447 | use g1t_contracts::repos::{Branch, GitAccess, Signature}; |
| 448 | |
| 449 | use super::*; |
| 450 | use crate::store::Scope; |
| 451 | |
| 452 | fn run<F: Future>(future: F) -> F::Output { |
| 453 | match pin!(future).as_mut().poll(&mut Context::from_waker(Waker::noop())) { |
| 454 | Poll::Ready(output) => output, |
| 455 | Poll::Pending => panic!("the fake store never waits"), |
| 456 | } |
| 457 | } |
| 458 | |
| 459 | #[derive(Default)] |
| 460 | struct Fake { |
| 461 | trees: HashMap<String, Vec<TreeEntry>>, |
| 462 | history: Vec<Commit>, |
| 463 | /// Every tree read, in order. |
| 464 | trees_read: RefCell<Vec<String>>, |
| 465 | /// Where each history read started. |
| 466 | logs_read: RefCell<Vec<String>>, |
| 467 | } |
| 468 | |
| 469 | impl GitRepo for Fake { |
| 470 | async fn access(&self, _scope: Scope) -> Result<GitAccess> { |
| 471 | unimplemented!() |
| 472 | } |
| 473 | async fn branches(&self) -> Result<Vec<Branch>> { |
| 474 | Ok(Vec::new()) |
| 475 | } |
| 476 | async fn log(&self, git_ref: &str, limit: u32) -> Result<Vec<Commit>> { |
| 477 | self.logs_read.borrow_mut().push(git_ref.to_owned()); |
| 478 | // A branch name starts at the head; a hash at that commit; anything else is unknown. |
| 479 | let start = if git_ref == "main" { Some(0) } else { self.history.iter().position(|commit| commit.hash == git_ref) }; |
| 480 | Ok(start.map(|start| self.history.iter().skip(start).take(limit as usize).cloned().collect()).unwrap_or_default()) |
| 481 | } |
| 482 | async fn parents(&self, _commit_hash: &str) -> Result<Option<Vec<String>>> { |
| 483 | Ok(None) |
| 484 | } |
| 485 | async fn read_tree(&self, tree_hash: &str) -> Result<Option<Vec<TreeEntry>>> { |
| 486 | self.trees_read.borrow_mut().push(tree_hash.to_owned()); |
| 487 | Ok(self.trees.get(tree_hash).cloned()) |
| 488 | } |
| 489 | async fn read_blob(&self, _blob_hash: &str) -> Result<Option<Vec<u8>>> { |
| 490 | Ok(None) |
| 491 | } |
| 492 | async fn read_file(&self, _git_ref: &str, _path: &str) -> Result<Option<Vec<u8>>> { |
| 493 | Ok(None) |
| 494 | } |
| 495 | async fn fork(&self, _target_key: &str) -> Result<()> { |
| 496 | Ok(()) |
| 497 | } |
| 498 | } |
| 499 | |
| 500 | fn entry(name: &str, hash: &str, kind: EntryKind) -> TreeEntry { |
| 501 | TreeEntry { name: name.into(), hash: hash.into(), kind } |
| 502 | } |
| 503 | |
| 504 | fn commit(hash: &str, tree: &str, parent: Option<&str>) -> Commit { |
| 505 | Commit { |
| 506 | hash: hash.into(), |
| 507 | tree_hash: tree.into(), |
| 508 | message: format!("commit {hash}"), |
| 509 | author: Signature { name: "a".into(), email: "a@example.com".into() }, |
| 510 | parents: parent.map(|p| vec![p.to_owned()]).unwrap_or_default(), |
| 511 | authored_at: String::new(), |
| 512 | } |
| 513 | } |
| 514 | |
| 515 | /// c1 adds README and src/a.rs; c2 changes src/a.rs; c3 changes README. |
| 516 | fn repo() -> Fake { |
| 517 | let mut fake = Fake::default(); |
| 518 | fake.trees.insert("src1".into(), vec![entry("a.rs", "a1", EntryKind::Blob)]); |
| 519 | fake.trees.insert("src2".into(), vec![entry("a.rs", "a2", EntryKind::Blob)]); |
| 520 | fake.trees.insert("root1".into(), vec![entry("README.md", "r1", EntryKind::Blob), entry("src", "src1", EntryKind::Tree)]); |
| 521 | fake.trees.insert("root2".into(), vec![entry("README.md", "r1", EntryKind::Blob), entry("src", "src2", EntryKind::Tree)]); |
| 522 | fake.trees.insert("root3".into(), vec![entry("README.md", "r2", EntryKind::Blob), entry("src", "src2", EntryKind::Tree)]); |
| 523 | fake.history = vec![commit("c3", "root3", Some("c2")), commit("c2", "root2", Some("c1")), commit("c1", "root1", None)]; |
| 524 | fake |
| 525 | } |
| 526 | |
| 527 | #[test] |
| 528 | fn a_files_history_is_the_commits_that_changed_it() { |
| 529 | let fake = repo(); |
| 530 | let never = || false; |
| 531 | let names = |found: Vec<Commit>| found.into_iter().map(|commit| commit.hash).collect::<Vec<_>>(); |
| 532 | let (found, complete) = run(path_log(&fake, "main", "src/a.rs", 10, &never, MAX_READS)).unwrap(); |
| 533 | assert_eq!((names(found), complete), (vec!["c2".to_owned(), "c1".to_owned()], true)); |
| 534 | let (found, _) = run(path_log(&fake, "main", "README.md", 10, &never, MAX_READS)).unwrap(); |
| 535 | assert_eq!(names(found), vec!["c3", "c1"]); |
| 536 | // A directory changes with what is in it. |
| 537 | let (found, _) = run(path_log(&fake, "main", "src", 10, &never, MAX_READS)).unwrap(); |
| 538 | assert_eq!(names(found), vec!["c2", "c1"]); |
| 539 | let (found, complete) = run(path_log(&fake, "main", "src/a.rs", 1, &never, MAX_READS)).unwrap(); |
| 540 | assert_eq!((names(found), complete), (vec!["c2".to_owned()], true)); |
| 541 | let (found, _) = run(path_log(&fake, "main", "nope.txt", 10, &never, MAX_READS)).unwrap(); |
| 542 | assert!(found.is_empty()); |
| 543 | } |
| 544 | |
| 545 | #[test] |
| 546 | fn a_long_history_is_walked_across_pages_within_its_reads() { |
| 547 | let fake = long(130); |
| 548 | let never = || false; |
| 549 | let (found, complete) = run(path_log(&fake, "main", ".dockerignore", 10, &never, MAX_READS)).unwrap(); |
| 550 | assert_eq!((found.len(), found[0].hash.as_str(), complete), (1, "c0", true)); |
| 551 | let (found, complete) = run(path_log(&fake, "main", ".dockerignore", 10, &never, 40)).unwrap(); |
| 552 | assert!(found.is_empty() && !complete, "out of reads before the first commit"); |
| 553 | } |
| 554 | |
| 555 | /// A long history, newest first: `.dockerignore` is added by the first |
| 556 | /// commit and never changed; `README.md` changes in every commit after |
| 557 | /// it, under a tree of its own (`t<n>`). |
| 558 | fn long(commits: usize) -> Fake { |
| 559 | let mut fake = Fake::default(); |
| 560 | for n in 0..commits { |
| 561 | let tree = vec![entry(".dockerignore", "ignore", EntryKind::Blob), entry("README.md", &format!("r{n}"), EntryKind::Blob)]; |
| 562 | fake.trees.insert(format!("t{n}"), tree); |
| 563 | let parent = (n > 0).then(|| format!("c{}", n - 1)); |
| 564 | fake.history.insert(0, commit(&format!("c{n}"), &format!("t{n}"), parent.as_deref())); |
| 565 | } |
| 566 | fake |
| 567 | } |
| 568 | |
| 569 | /// Adds commits on top: each changes README.md; `touch_new` also adds `NEW`. |
| 570 | fn push(fake: &mut Fake, commits: usize, touch_new: bool) { |
| 571 | let first = fake.history.len(); |
| 572 | for n in first..first + commits { |
| 573 | let mut tree = vec![entry(".dockerignore", "ignore", EntryKind::Blob), entry("README.md", &format!("r{n}"), EntryKind::Blob)]; |
| 574 | if touch_new { |
| 575 | tree.push(entry("NEW", "new", EntryKind::Blob)); |
| 576 | } |
| 577 | fake.trees.insert(format!("t{n}"), tree); |
| 578 | fake.history.insert(0, commit(&format!("c{n}"), &format!("t{n}"), Some(&format!("c{}", n - 1)))); |
| 579 | } |
| 580 | } |
| 581 | |
| 582 | fn walk(fake: &Fake, head: &str, path: &str, kept: Option<Progress>) -> Progress { |
| 583 | run(last_commits(fake, head, path, kept, &|| false, MAX_READS)).unwrap().progress |
| 584 | } |
| 585 | |
| 586 | fn by_name(found: &[LastCommit]) -> HashMap<String, String> { |
| 587 | found.iter().map(|last| (last.name.clone(), last.commit.hash.clone())).collect() |
| 588 | } |
| 589 | |
| 590 | #[test] |
| 591 | fn each_root_entry_gets_the_newest_commit_that_changed_it() { |
| 592 | let found = walk(&repo(), "c3", "", None); |
| 593 | assert!(found.complete()); |
| 594 | let found = by_name(&found.found); |
| 595 | assert_eq!(found["README.md"], "c3"); |
| 596 | assert_eq!(found["src"], "c2"); |
| 597 | } |
| 598 | |
| 599 | #[test] |
| 600 | fn a_subdirectory_is_walked_by_its_own_tree() { |
| 601 | let found = walk(&repo(), "c3", "src", None); |
| 602 | assert!(found.complete()); |
| 603 | assert_eq!(by_name(&found.found)["a.rs"], "c2"); |
| 604 | } |
| 605 | |
| 606 | #[test] |
| 607 | fn an_entry_unchanged_since_the_first_commit_belongs_to_it() { |
| 608 | let mut fake = repo(); |
| 609 | fake.trees.insert("root2".into(), vec![entry("README.md", "r1", EntryKind::Blob), entry("src", "src1", EntryKind::Tree)]); |
| 610 | fake.trees.insert("root3".into(), vec![entry("README.md", "r2", EntryKind::Blob), entry("src", "src1", EntryKind::Tree)]); |
| 611 | let found = walk(&fake, "c3", "", None); |
| 612 | assert!(found.complete()); |
| 613 | assert_eq!(by_name(&found.found)["src"], "c1"); |
| 614 | } |
| 615 | |
| 616 | #[test] |
| 617 | fn history_that_cannot_be_read_leaves_the_rest_unknown_for_good() { |
| 618 | let mut fake = repo(); |
| 619 | // c1 has a parent the walk never reaches. |
| 620 | fake.history[2].parents = vec!["c0".into()]; |
| 621 | fake.trees.insert("root2".into(), vec![entry("README.md", "r1", EntryKind::Blob), entry("src", "src1", EntryKind::Tree)]); |
| 622 | fake.trees.insert("root3".into(), vec![entry("README.md", "r2", EntryKind::Blob), entry("src", "src1", EntryKind::Tree)]); |
| 623 | let found = walk(&fake, "c3", "", None); |
| 624 | assert!(!found.complete()); |
| 625 | assert!(found.settled(), "no later walk can find more"); |
| 626 | let names = by_name(&found.found); |
| 627 | assert_eq!(names["README.md"], "c3"); |
| 628 | assert!(!names.contains_key("src")); |
| 629 | } |
| 630 | |
| 631 | #[test] |
| 632 | fn an_entry_older_than_a_thousand_commits_resolves() { |
| 633 | let fake = long(1_200); |
| 634 | let found = walk(&fake, "c1199", "", None); |
| 635 | assert!(found.complete()); |
| 636 | let names = by_name(&found.found); |
| 637 | assert_eq!(names[".dockerignore"], "c0"); |
| 638 | assert_eq!(names["README.md"], "c1199"); |
| 639 | } |
| 640 | |
| 641 | #[test] |
| 642 | fn a_walk_out_of_reads_stops_and_the_next_goes_on_from_there() { |
| 643 | let fake = long(1_000); |
| 644 | let first = run(last_commits(&fake, "c999", "", None, &|| false, 300)).unwrap(); |
| 645 | assert!(first.reads <= 300, "{} reads", first.reads); |
| 646 | assert!(!first.progress.settled()); |
| 647 | let at = first.progress.at.clone().unwrap(); |
| 648 | assert_ne!(at, "c999"); |
| 649 | let mut progress = first.progress; |
| 650 | let mut calls = 1; |
| 651 | while !progress.settled() { |
| 652 | fake.trees_read.borrow_mut().clear(); |
| 653 | let next = run(last_commits(&fake, "c999", "", Some(progress), &|| false, 300)).unwrap(); |
| 654 | assert!(next.reads <= 300); |
| 655 | // The next call starts where the last one stopped. |
| 656 | assert!(!fake.trees_read.borrow().contains(&"t999".to_owned())); |
| 657 | progress = next.progress; |
| 658 | calls += 1; |
| 659 | } |
| 660 | assert!(calls >= 3); |
| 661 | assert!(progress.complete()); |
| 662 | assert_eq!(by_name(&progress.found)[".dockerignore"], "c0"); |
| 663 | } |
| 664 | |
| 665 | #[test] |
| 666 | fn three_thousand_commits_take_two_calls_within_the_read_limit() { |
| 667 | let fake = long(3_000); |
| 668 | let first = run(last_commits(&fake, "c2999", "", None, &|| false, MAX_READS)).unwrap(); |
| 669 | assert!(first.reads <= MAX_READS); |
| 670 | assert!(!first.progress.settled()); |
| 671 | let second = run(last_commits(&fake, "c2999", "", Some(first.progress), &|| false, MAX_READS)).unwrap(); |
| 672 | assert!(second.reads <= MAX_READS); |
| 673 | assert!(second.progress.complete()); |
| 674 | assert_eq!(by_name(&second.progress.found)[".dockerignore"], "c0"); |
| 675 | } |
| 676 | |
| 677 | #[test] |
| 678 | fn out_of_time_stops_after_some_progress() { |
| 679 | let fake = long(500); |
| 680 | let found = run(last_commits(&fake, "c499", "", None, &|| true, MAX_READS)).unwrap().progress; |
| 681 | assert!(!found.settled()); |
| 682 | assert_eq!(by_name(&found.found)["README.md"], "c499"); |
| 683 | } |
| 684 | |
| 685 | #[test] |
| 686 | fn a_new_head_reads_only_the_commits_since_the_remembered_one() { |
| 687 | let mut fake = long(600); |
| 688 | let before = walk(&fake, "c599", "", None); |
| 689 | assert!(before.complete()); |
| 690 | push(&mut fake, 3, true); |
| 691 | fake.trees_read.borrow_mut().clear(); |
| 692 | fake.logs_read.borrow_mut().clear(); |
| 693 | let after = walk(&fake, "c602", "", Some(before)); |
| 694 | assert!(after.complete()); |
| 695 | let names = by_name(&after.found); |
| 696 | assert_eq!(names[".dockerignore"], "c0", "kept from the earlier walk"); |
| 697 | assert_eq!(names["README.md"], "c602"); |
| 698 | assert_eq!(names["NEW"], "c600"); |
| 699 | // One page of history and one batch of trees read ahead, not 600. |
| 700 | let read = fake.trees_read.borrow(); |
| 701 | assert!(read.len() <= READ_AHEAD + 1, "{read:?}"); |
| 702 | assert!(!read.contains(&"t500".to_owned())); |
| 703 | assert_eq!(fake.logs_read.borrow().len(), 1); |
| 704 | } |
| 705 | |
| 706 | #[test] |
| 707 | fn a_new_head_goes_on_from_where_an_unfinished_walk_stopped() { |
| 708 | let mut fake = long(1_000); |
| 709 | let first = run(last_commits(&fake, "c999", "", None, &|| false, 300)).unwrap().progress; |
| 710 | assert!(!first.settled()); |
| 711 | let stopped_at = first.at.clone().unwrap(); |
| 712 | push(&mut fake, 2, false); |
| 713 | fake.logs_read.borrow_mut().clear(); |
| 714 | let next = run(last_commits(&fake, "c1001", "", Some(first), &|| false, MAX_READS)).unwrap().progress; |
| 715 | assert!(next.complete()); |
| 716 | assert_eq!(by_name(&next.found)[".dockerignore"], "c0"); |
| 717 | assert_eq!(by_name(&next.found)["README.md"], "c1001"); |
| 718 | // From the new head, then straight to where the first walk stopped. |
| 719 | assert_eq!(fake.logs_read.borrow()[..2], ["c1001".to_owned(), stopped_at]); |
| 720 | } |
| 721 | |
| 722 | #[test] |
| 723 | fn a_force_push_walks_the_whole_history_again() { |
| 724 | let mut fake = long(400); |
| 725 | let before = walk(&fake, "c399", "", None); |
| 726 | assert!(before.complete()); |
| 727 | // A new history: .dockerignore is different in its first commit, and |
| 728 | // the remembered head is not on it. |
| 729 | let mut rewritten = long(450); |
| 730 | for commit in &mut rewritten.history { |
| 731 | commit.hash = format!("x{}", commit.hash); |
| 732 | commit.parents = commit.parents.iter().map(|parent| format!("x{parent}")).collect(); |
| 733 | } |
| 734 | rewritten.trees.get_mut("t0").unwrap()[0].hash = "old-ignore".into(); |
| 735 | for tree in (1..450).map(|n| format!("t{n}")) { |
| 736 | rewritten.trees.get_mut(&tree).unwrap()[0].hash = "new-ignore".into(); |
| 737 | } |
| 738 | fake = rewritten; |
| 739 | let after = walk(&fake, "xc449", "", Some(before)); |
| 740 | assert!(after.complete()); |
| 741 | let names = by_name(&after.found); |
| 742 | assert_eq!(names[".dockerignore"], "xc1", "found by walking, not kept from the old history"); |
| 743 | assert_eq!(names["README.md"], "xc449"); |
| 744 | assert!(fake.trees_read.borrow().contains(&"t1".to_owned())); |
| 745 | } |
| 746 | |
| 747 | #[test] |
| 748 | fn the_same_head_again_reads_nothing() { |
| 749 | let fake = repo(); |
| 750 | let before = walk(&fake, "c3", "", None); |
| 751 | fake.trees_read.borrow_mut().clear(); |
| 752 | let again = run(last_commits(&fake, "c3", "", Some(before), &|| false, MAX_READS)).unwrap(); |
| 753 | assert_eq!(again.reads, 0); |
| 754 | assert!(again.progress.complete()); |
| 755 | } |
| 756 | } |