| 1 | //! Work done once for many askers. |
| 2 | //! |
| 3 | //! When a repository's default branch moves, work asks again whether each |
| 4 | //! of its open pull requests (up to 100) still merges cleanly |
| 5 | //! (`divergence`). Every one of those questions starts with the same |
| 6 | //! answer about the target: its history from the new head, and what it |
| 7 | //! changed since a pull request's merge base. That half is worked out once |
| 8 | //! per target head and kept here, in the isolate, for the burst of |
| 9 | //! questions that follows ([`Memo`]); the history itself is kept by commit |
| 10 | //! hash in the object cache (store.rs), so other isolates read it without |
| 11 | //! asking the store. Only each pull request's own side is read per pull |
| 12 | //! request. |
| 13 | |
| 14 | use std::collections::{HashMap, HashSet}; |
| 15 | use std::hash::Hash; |
| 16 | use std::rc::Rc; |
| 17 | |
| 18 | use g1t_contracts::repos::Commit; |
| 19 | |
| 20 | /// Answers kept for a short while, at most `cap` of them. |
| 21 | pub struct Memo<K, V> { |
| 22 | entries: HashMap<K, (V, u64)>, |
| 23 | ttl_ms: u64, |
| 24 | cap: usize, |
| 25 | } |
| 26 | |
| 27 | impl<K: Eq + Hash + Clone, V: Clone> Memo<K, V> { |
| 28 | pub fn new(ttl_ms: u64, cap: usize) -> Self { |
| 29 | Memo { entries: HashMap::new(), ttl_ms, cap } |
| 30 | } |
| 31 | |
| 32 | pub fn get(&self, key: &K, now: u64) -> Option<V> { |
| 33 | self.entries |
| 34 | .get(key) |
| 35 | .filter(|(_, at)| now.saturating_sub(*at) < self.ttl_ms) |
| 36 | .map(|(value, _)| value.clone()) |
| 37 | } |
| 38 | |
| 39 | pub fn put(&mut self, key: K, value: V, now: u64) { |
| 40 | let ttl = self.ttl_ms; |
| 41 | self.entries.retain(|_, (_, at)| now.saturating_sub(*at) < ttl); |
| 42 | while self.entries.len() >= self.cap { |
| 43 | let Some(oldest) = self.entries.iter().min_by_key(|(_, (_, at))| *at).map(|(key, _)| key.clone()) else { |
| 44 | break; |
| 45 | }; |
| 46 | self.entries.remove(&oldest); |
| 47 | } |
| 48 | self.entries.insert(key, (value, now)); |
| 49 | } |
| 50 | |
| 51 | #[cfg(test)] |
| 52 | pub fn len(&self) -> usize { |
| 53 | self.entries.len() |
| 54 | } |
| 55 | } |
| 56 | |
| 57 | /// A target branch's side of the question: its history from its head |
| 58 | /// (first parent, newest first), and the same as a set. |
| 59 | pub struct TargetSide { |
| 60 | pub history: Vec<Commit>, |
| 61 | pub shared: HashSet<String>, |
| 62 | } |
| 63 | |
| 64 | impl TargetSide { |
| 65 | pub fn new(history: Vec<Commit>) -> Rc<Self> { |
| 66 | let shared = history.iter().map(|commit| commit.hash.clone()).collect(); |
| 67 | Rc::new(TargetSide { history, shared }) |
| 68 | } |
| 69 | } |
| 70 | |
| 71 | /// Where a target's side is kept: the repository, its default branch, and |
| 72 | /// the version of its refs, which moves with the branch. Kept only while |
| 73 | /// the version can be trusted (registry.rs, refs_cache.rs `usable`). |
| 74 | pub type TargetKey = (String, String, u64); |
| 75 | /// What the target changed between two trees: the repository and the trees. |
| 76 | pub type TheirsKey = (String, String, String); |
| 77 | |
| 78 | /// How long a target's side is kept: long enough for one burst of |
| 79 | /// questions after a push. |
| 80 | pub const TARGET_TTL_MS: u64 = 60_000; |
| 81 | /// What a target changed between two trees never changes; kept a while. |
| 82 | pub const THEIRS_TTL_MS: u64 = 10 * 60_000; |
| 83 | |
| 84 | #[cfg(test)] |
| 85 | mod tests { |
| 86 | use super::*; |
| 87 | |
| 88 | #[test] |
| 89 | fn an_answer_is_kept_for_a_while_and_the_oldest_goes_first() { |
| 90 | let mut memo: Memo<&str, u32> = Memo::new(1_000, 2); |
| 91 | memo.put("a", 1, 0); |
| 92 | assert_eq!(memo.get(&"a", 999), Some(1)); |
| 93 | assert_eq!(memo.get(&"a", 1_000), None); |
| 94 | memo.put("b", 2, 10); |
| 95 | memo.put("c", 3, 20); |
| 96 | // Full: "a" was oldest. |
| 97 | assert_eq!(memo.get(&"a", 20), None); |
| 98 | assert_eq!(memo.get(&"b", 20), Some(2)); |
| 99 | assert_eq!(memo.len(), 2); |
| 100 | // Expired ones go before anything is pushed out. |
| 101 | memo.put("d", 4, 1_015); |
| 102 | assert_eq!(memo.get(&"c", 1_015), Some(3)); |
| 103 | assert_eq!(memo.get(&"d", 1_015), Some(4)); |
| 104 | } |
| 105 | |
| 106 | #[test] |
| 107 | fn a_target_side_is_keyed_by_its_refs_version() { |
| 108 | let commit = |hash: &str| Commit { |
| 109 | hash: hash.into(), |
| 110 | tree_hash: String::new(), |
| 111 | message: String::new(), |
| 112 | author: g1t_contracts::repos::Signature { name: String::new(), email: String::new() }, |
| 113 | parents: Vec::new(), |
| 114 | authored_at: String::new(), |
| 115 | }; |
| 116 | let side = TargetSide::new(vec![commit("b"), commit("a")]); |
| 117 | assert!(side.shared.contains("a") && side.shared.contains("b")); |
| 118 | let mut memo: Memo<TargetKey, Rc<TargetSide>> = Memo::new(TARGET_TTL_MS, 32); |
| 119 | let key = ("rep_1".to_owned(), "main".to_owned(), 7); |
| 120 | memo.put(key.clone(), side, 0); |
| 121 | assert!(memo.get(&key, 10).is_some()); |
| 122 | // The branch moved: the version did too, and the old side is not used. |
| 123 | assert!(memo.get(&("rep_1".to_owned(), "main".to_owned(), 8), 10).is_none()); |
| 124 | } |
| 125 | } |