Skip to content
Sign in

flagon-io/g1t

public
0
356 linesCodeBlameRaw
1//! How far branches have moved from the default branch, for Active branches
2//! on a project's overview and the Branches page (`branch_drift`).
3//!
4//! Each branch head's history and the default branch's are read to a depth,
5//! in turn deeper, until they meet; the default branch's history is read
6//! once per depth for every branch. Histories are read by commit hash, which
7//! the store keeps for good (store.rs), and each answer is kept by the pair
8//! of heads (lib.rs), so only heads that moved cost a walk. Before
9//! 2026-10-08 the site did this itself: up to twenty `log` calls per view,
10//! each with its own access check and store handle.
11
12use std::collections::{HashMap, HashSet};
13
14use g1t_contracts::repos::{Commit, Drift};
15use worker::Result;
16
17use crate::store::GitRepo;
18
19/// How deep each history is read, in turn: (branch, default branch). Most
20/// branches are a few commits ahead of where they left a default branch
21/// that has moved on a little; one left long ago needs the default
22/// branch's history further back; one far from both reads both deeply.
23/// Past the last, there is no answer.
24pub const DEPTHS: [(u32, u32); 4] = [(12, 120), (40, 120), (40, 1000), (1000, 1000)];
25
26/// Branches read at once.
27const AT_ONCE: usize = 8;
28
29/// A branch head's commit and drift, and whether the answer may be kept:
30/// not when a read failed.
31#[derive(Clone, Debug)]
32pub struct Measured {
33 pub commit: Option<Commit>,
34 pub drift: Option<Drift>,
35 pub settled: bool,
36}
37
38/// Commits `branch` has that `main` does not (ahead) and the other way
39/// round (behind), from what was read of the two histories (`commits`, in
40/// any order, repeats allowed). `None` when either head is missing, or when
41/// a commit only one side reaches has a parent that was not read: that
42/// parent's history could change either count.
43pub fn drift<'a>(branch: &str, main: &str, commits: impl IntoIterator<Item = &'a Commit>) -> Option<Drift> {
44 let mut parents: HashMap<&str, &[String]> = HashMap::new();
45 for commit in commits {
46 parents.insert(commit.hash.as_str(), commit.parents.as_slice());
47 }
48 if !parents.contains_key(branch) || !parents.contains_key(main) {
49 return None;
50 }
51 let from_branch = reach(branch, &parents);
52 let from_main = reach(main, &parents);
53 let (mut ahead, mut behind) = (0, 0);
54 for (hash, above) in &parents {
55 let on_branch = from_branch.contains(hash);
56 if on_branch == from_main.contains(hash) {
57 continue;
58 }
59 if above.iter().any(|parent| !parents.contains_key(parent.as_str())) {
60 return None;
61 }
62 if on_branch {
63 ahead += 1;
64 } else {
65 behind += 1;
66 }
67 }
68 Some(Drift { ahead, behind })
69}
70
71/// Every commit read that `head` descends from, itself included.
72fn reach<'a>(head: &'a str, parents: &HashMap<&'a str, &'a [String]>) -> HashSet<&'a str> {
73 let mut seen = HashSet::from([head]);
74 let mut next = vec![head];
75 while let Some(hash) = next.pop() {
76 for parent in parents.get(hash).copied().unwrap_or_default() {
77 if let Some((&known, _)) = parents.get_key_value(parent.as_str())
78 && seen.insert(known)
79 {
80 next.push(known);
81 }
82 }
83 }
84 seen
85}
86
87/// What was read of one branch's history so far.
88struct Reading {
89 commits: Vec<Commit>,
90 depth: u32,
91 answer: Option<Measured>,
92}
93
94/// Each of `heads` measured against `base`, in the order given.
95pub async fn measure<R: GitRepo>(git: &R, base: &str, heads: &[String]) -> Vec<Measured> {
96 let mut readings: Vec<Reading> = heads.iter().map(|_| Reading { commits: Vec::new(), depth: 0, answer: None }).collect();
97 // The default branch's history, read once per depth and not deeper
98 // once a read reached its start.
99 let mut main: Option<(u32, Vec<Commit>)> = None;
100 let mut main_failed = false;
101 for (branch_depth, main_depth) in DEPTHS {
102 if readings.iter().all(|reading| reading.answer.is_some()) {
103 break;
104 }
105 let deeper = match &main {
106 Some((read_to, commits)) => *read_to < main_depth && commits.len() as u32 >= *read_to,
107 None => true,
108 };
109 if deeper && !main_failed {
110 match git.log(base, main_depth).await {
111 Ok(commits) if !commits.is_empty() => main = Some((main_depth, commits)),
112 _ => main_failed = true,
113 }
114 }
115 let Some((_, main_commits)) = &main else {
116 for reading in readings.iter_mut().filter(|reading| reading.answer.is_none()) {
117 reading.answer = Some(Measured { commit: None, drift: None, settled: false });
118 }
119 break;
120 };
121 let open: Vec<usize> = (0..heads.len()).filter(|&index| readings[index].answer.is_none()).collect();
122 for chunk in open.chunks(AT_ONCE) {
123 let reads = futures_util::future::join_all(chunk.iter().map(|&index| {
124 let reading = &readings[index];
125 // Read again only when deeper, and only when the last read
126 // did not already reach the start.
127 let again = reading.depth == 0 || (branch_depth > reading.depth && reading.commits.len() as u32 >= reading.depth);
128 let head = heads[index].as_str();
129 async move { if again { Some(git.log(head, branch_depth).await) } else { None } }
130 }))
131 .await;
132 for (&index, read) in chunk.iter().zip(reads) {
133 let reading = &mut readings[index];
134 match read {
135 Some(Ok(commits)) if !commits.is_empty() => {
136 reading.commits = commits;
137 reading.depth = branch_depth;
138 }
139 Some(_) => {
140 reading.answer = Some(Measured { commit: None, drift: None, settled: false });
141 continue;
142 }
143 None => {}
144 }
145 let head = heads[index].as_str();
146 if let Some(counted) = drift(head, base, main_commits.iter().chain(reading.commits.iter())) {
147 reading.answer = Some(Measured { commit: reading.commits.first().cloned(), drift: Some(counted), settled: true });
148 }
149 }
150 }
151 if main_failed {
152 break;
153 }
154 }
155 readings
156 .into_iter()
157 .map(|reading| {
158 reading.answer.unwrap_or_else(|| Measured {
159 commit: reading.commits.first().cloned(),
160 drift: None,
161 // Read to the last depth without meeting: that is the answer
162 // for this pair, and it will not change.
163 settled: !main_failed && reading.depth > 0,
164 })
165 })
166 .collect()
167}
168
169#[cfg(test)]
170mod tests {
171 use std::cell::RefCell;
172 use std::future::Future;
173 use std::pin::pin;
174 use std::task::{Context, Poll, Waker};
175
176 use g1t_contracts::repos::{Branch, GitAccess, Signature, TreeEntry};
177
178 use super::*;
179 use crate::store::Scope;
180
181 fn run<F: Future>(future: F) -> F::Output {
182 match pin!(future).as_mut().poll(&mut Context::from_waker(Waker::noop())) {
183 Poll::Ready(output) => output,
184 Poll::Pending => panic!("the fake store never waits"),
185 }
186 }
187
188 fn commit(hash: &str, parents: &[&str]) -> Commit {
189 Commit {
190 hash: hash.into(),
191 tree_hash: format!("t{hash}"),
192 message: format!("commit {hash}\n\nbody"),
193 author: Signature { name: "a".into(), email: "a@example.com".into() },
194 parents: parents.iter().map(|&p| p.to_owned()).collect(),
195 authored_at: String::new(),
196 }
197 }
198
199 /// Commits by hash; `log` follows first parents. Counts each read.
200 #[derive(Default)]
201 struct Fake {
202 commits: HashMap<String, Commit>,
203 reads: RefCell<Vec<(String, u32)>>,
204 fail: Option<String>,
205 }
206
207 impl Fake {
208 fn with(commits: Vec<Commit>) -> Fake {
209 Fake { commits: commits.into_iter().map(|c| (c.hash.clone(), c)).collect(), ..Fake::default() }
210 }
211 }
212
213 impl GitRepo for Fake {
214 async fn access(&self, _scope: Scope) -> Result<GitAccess> {
215 unimplemented!()
216 }
217 async fn branches(&self) -> Result<Vec<Branch>> {
218 Ok(Vec::new())
219 }
220 async fn log(&self, git_ref: &str, limit: u32) -> Result<Vec<Commit>> {
221 self.reads.borrow_mut().push((git_ref.to_owned(), limit));
222 if self.fail.as_deref() == Some(git_ref) {
223 return Err(worker::Error::RustError("store busy".into()));
224 }
225 let mut out = Vec::new();
226 let mut at = self.commits.get(git_ref);
227 while let Some(commit) = at {
228 if out.len() as u32 >= limit {
229 break;
230 }
231 out.push(commit.clone());
232 at = commit.parents.first().and_then(|parent| self.commits.get(parent));
233 }
234 Ok(out)
235 }
236 async fn parents(&self, _commit_hash: &str) -> Result<Option<Vec<String>>> {
237 Ok(None)
238 }
239 async fn read_tree(&self, _tree_hash: &str) -> Result<Option<Vec<TreeEntry>>> {
240 Ok(None)
241 }
242 async fn read_blob(&self, _blob_hash: &str) -> Result<Option<Vec<u8>>> {
243 Ok(None)
244 }
245 async fn read_file(&self, _git_ref: &str, _path: &str) -> Result<Option<Vec<u8>>> {
246 Ok(None)
247 }
248 async fn fork(&self, _target_key: &str) -> Result<()> {
249 Ok(())
250 }
251 }
252
253 /// m1 ← m2 ← m3 on main; b1 ← b2 branched from m2.
254 fn forked() -> Vec<Commit> {
255 vec![commit("m1", &[]), commit("m2", &["m1"]), commit("m3", &["m2"]), commit("b1", &["m2"]), commit("b2", &["b1"])]
256 }
257
258 /// A straight line of `n` commits named `{prefix}{i}`, the first on `from`.
259 fn line(prefix: &str, from: Option<&str>, n: usize) -> Vec<Commit> {
260 (1..=n)
261 .map(|i| {
262 let parent = if i == 1 { from.map(str::to_owned) } else { Some(format!("{prefix}{}", i - 1)) };
263 commit(&format!("{prefix}{i}"), &parent.iter().map(String::as_str).collect::<Vec<_>>())
264 })
265 .collect()
266 }
267
268 #[test]
269 fn counts_both_sides_from_where_they_forked() {
270 assert_eq!(drift("b2", "m3", &forked()), Some(Drift { ahead: 2, behind: 1 }));
271 assert_eq!(drift("m3", "m3", &forked()), Some(Drift { ahead: 0, behind: 0 }));
272 }
273
274 #[test]
275 fn a_merge_from_main_is_not_ahead() {
276 // b3 merges m3 into the branch.
277 let mut history = forked();
278 history.push(commit("b3", &["b2", "m3"]));
279 assert_eq!(drift("b3", "m3", &history), Some(Drift { ahead: 3, behind: 0 }));
280 }
281
282 #[test]
283 fn no_answer_when_the_histories_were_not_read_far_enough() {
284 let history = vec![commit("m3", &["m2"]), commit("b2", &["b1"])];
285 assert_eq!(drift("b2", "m3", &history), None);
286 assert_eq!(drift("b9", "m3", &forked()), None);
287 }
288
289 #[test]
290 fn measures_every_head_with_one_read_of_main() {
291 let git = Fake::with(forked());
292 let found = run(measure(&git, "m3", &["b2".to_owned(), "m2".to_owned(), "m3".to_owned()]));
293 assert_eq!(found[0].drift, Some(Drift { ahead: 2, behind: 1 }));
294 assert_eq!(found[0].commit.as_ref().map(|c| c.hash.as_str()), Some("b2"));
295 assert_eq!(found[1].drift, Some(Drift { ahead: 0, behind: 1 }));
296 assert_eq!(found[2].drift, Some(Drift { ahead: 0, behind: 0 }));
297 assert!(found.iter().all(|m| m.settled));
298 let reads = git.reads.borrow();
299 assert_eq!(reads.iter().filter(|(hash, _)| hash == "m3").count(), 2, "main once, plus m3 as a head: {reads:?}");
300 assert!(reads.iter().all(|(_, depth)| *depth == 12 || *depth == 120));
301 }
302
303 #[test]
304 fn reads_deeper_only_for_a_branch_that_needs_it() {
305 // main: 150 commits; "long" is 30 ahead of m100 (50 behind); "short" is 1 ahead of m149.
306 let mut history = line("m", None, 150);
307 history.extend(line("l", Some("m100"), 30));
308 history.push(commit("s1", &["m149"]));
309 let git = Fake::with(history);
310 let found = run(measure(&git, "m150", &["l30".to_owned(), "s1".to_owned()]));
311 assert_eq!(found[0].drift, Some(Drift { ahead: 30, behind: 50 }));
312 assert_eq!(found[1].drift, Some(Drift { ahead: 1, behind: 1 }));
313 let reads = git.reads.borrow();
314 assert_eq!(reads.iter().filter(|(hash, _)| hash == "s1").count(), 1);
315 assert_eq!(*reads.iter().filter(|(hash, _)| hash == "l30").map(|(_, depth)| depth).max().unwrap(), 40);
316 assert!(!reads.iter().any(|(_, depth)| *depth == 1000), "{reads:?}");
317 }
318
319 #[test]
320 fn unrelated_histories_read_to_their_start_count_every_commit() {
321 let mut history = line("m", None, 3);
322 history.extend(line("x", None, 2));
323 let git = Fake::with(history);
324 let found = run(measure(&git, "m3", &["x2".to_owned()]));
325 assert_eq!(found[0].drift, Some(Drift { ahead: 2, behind: 3 }));
326 assert_eq!(found[0].commit.as_ref().map(|c| c.hash.as_str()), Some("x2"));
327 assert!(found[0].settled);
328 // Both reached their start at the first depth: never read again.
329 assert_eq!(git.reads.borrow().len(), 2);
330 }
331
332 #[test]
333 fn past_the_last_depth_the_answer_is_settled_without_a_count() {
334 // The branch is 1,200 commits long: no depth reaches where it left main.
335 let mut history = line("m", None, 3);
336 history.extend(line("x", Some("m1"), 1200));
337 let git = Fake::with(history);
338 let found = run(measure(&git, "m3", &["x1200".to_owned()]));
339 assert_eq!(found[0].drift, None);
340 assert_eq!(found[0].commit.as_ref().map(|c| c.hash.as_str()), Some("x1200"));
341 assert!(found[0].settled);
342 }
343
344 #[test]
345 fn a_failed_read_is_not_kept() {
346 let mut git = Fake::with(forked());
347 git.fail = Some("b2".into());
348 let found = run(measure(&git, "m3", &["b2".to_owned(), "b1".to_owned()]));
349 assert!(!found[0].settled);
350 assert_eq!(found[1].drift, Some(Drift { ahead: 1, behind: 1 }));
351 assert!(found[1].settled);
352 git.fail = Some("m3".into());
353 let found = run(measure(&git, "m3", &["b2".to_owned()]));
354 assert!(!found[0].settled);
355 }
356}