| 1 | /** |
| 2 | * How far a branch has moved from the default branch: commits it has that |
| 3 | * the default branch does not (ahead), and commits the default branch has |
| 4 | * that it does not (behind), the way `git rev-list --left-right --count` |
| 5 | * says it. Worked out from what was read of the two histories, merges |
| 6 | * included; when what was read stops short of where they meet, there is no |
| 7 | * answer rather than a guess. |
| 8 | */ |
| 9 | export type Drift = { ahead: number; behind: number }; |
| 10 | |
| 11 | /** A commit as far as counting needs it. */ |
| 12 | export type Link = { hash: string; parents: string[] }; |
| 13 | |
| 14 | /** |
| 15 | * `commits` is everything read of either history, in any order, repeats |
| 16 | * allowed. Null when either head is missing from it, or when a commit only |
| 17 | * one side reaches has a parent that was not read: that parent's history |
| 18 | * could change either count. |
| 19 | */ |
| 20 | export function drift(branch: string, main: string, commits: Iterable<Link>): Drift | null { |
| 21 | const parents = new Map<string, string[]>(); |
| 22 | for (const commit of commits) parents.set(commit.hash, commit.parents); |
| 23 | if (!parents.has(branch) || !parents.has(main)) return null; |
| 24 | const fromBranch = reach(branch, parents); |
| 25 | const fromMain = reach(main, parents); |
| 26 | let ahead = 0; |
| 27 | let behind = 0; |
| 28 | for (const [hash, above] of parents) { |
| 29 | const onBranch = fromBranch.has(hash); |
| 30 | const onMain = fromMain.has(hash); |
| 31 | if (onBranch === onMain) continue; |
| 32 | if (above.some((parent) => !parents.has(parent))) return null; |
| 33 | if (onBranch) ahead++; |
| 34 | else behind++; |
| 35 | } |
| 36 | return { ahead, behind }; |
| 37 | } |
| 38 | |
| 39 | /** Every commit read that `head` descends from, itself included. */ |
| 40 | function reach(head: string, parents: Map<string, string[]>): Set<string> { |
| 41 | const seen = new Set([head]); |
| 42 | const next = [head]; |
| 43 | for (let hash = next.pop(); hash != null; hash = next.pop()) { |
| 44 | for (const parent of parents.get(hash) ?? []) { |
| 45 | if (parents.has(parent) && !seen.has(parent)) { |
| 46 | seen.add(parent); |
| 47 | next.push(parent); |
| 48 | } |
| 49 | } |
| 50 | } |
| 51 | return seen; |
| 52 | } |
| 53 | |
| 54 | /** `load` over each of `items`, at most `limit` at a time, answers in order. */ |
| 55 | export async function bounded<T, R>(items: readonly T[], limit: number, load: (item: T) => Promise<R>): Promise<R[]> { |
| 56 | const out = new Array<R>(items.length); |
| 57 | let taken = 0; |
| 58 | const worker = async () => { |
| 59 | while (taken < items.length) { |
| 60 | const index = taken++; |
| 61 | out[index] = await load(items[index] as T); |
| 62 | } |
| 63 | }; |
| 64 | await Promise.all(Array.from({ length: Math.min(limit, items.length) }, worker)); |
| 65 | return out; |
| 66 | } |