Diffinery

codician/diffinerypublic

Open-source, agent-first GitHub and GitHub Actions alternative that runs on your own Cloudflare account: git hosting, pull requests, code review and drop-in GitHub Actions YAML on Workers, Durable Objects, R2 and Containers.

414 lines · 20.2 KBRaw History
1import { ZERO_OID, mergeBase, mergeTrees, readCommit, serializeCommit } from "@diffinery/git-core";
2import { squashSig } from "./collab.js";
3import { ARCHIVED_REASON, automaticLandingRefusal } from "./auto-merge.js";
4import { requiredCheck } from "./required.js";
5import type { Actor } from "@diffinery/shared";
6import { HttpError, now } from "../lib/util.js";
7import type { RepoDO } from "./RepoDO.js";
8import type { Caller, MergeQueueSettings } from "./types.js";
9
10type QueueRow = {
11 number: number;
12 base_ref: string;
13 seq: number;
14 head_sha: string;
15 method: "merge" | "squash" | "rebase";
16 delete_branch: number;
17 enqueued_by: string;
18 enqueued_at: string;
19 parent_sha: string | null;
20 group_sha: string | null;
21 group_ref: string | null;
22 built_at: string | null;
23};
24
25export type QueueEntry = {
26 number: number;
27 title: string;
28 base: string;
29 position: number;
30 headSha: string;
31 method: QueueRow["method"];
32 deleteBranch: boolean;
33 enqueuedBy: Actor;
34 enqueuedAt: string;
35 /** queued: waiting for its merge group to be built; checking: its merge group is running checks. */
36 state: "queued" | "checking";
37 groupRef: string | null;
38 groupSha: string | null;
39 parentSha: string | null;
40 builtAt: string | null;
41 checks: Array<{ name: string; state: string }>;
42};
43
44export type EnqueueResult = { state: "queued" | "merged" | "removed"; entry: QueueEntry | null; mergeCommit?: string | null; reason?: string };
45
46/** Prefix of merge group branches, the same as GitHub's so existing `branches-ignore` filters keep working. */
47export const QUEUE_BRANCH_PREFIX = "gh-readonly-queue/";
48
49export const QUEUE_BOT: Caller = { id: "system:merge-queue", login: "diffinery-merge-queue[bot]", kind: "system", role: "admin" };
50
51const DEFAULT_CONCURRENCY = 5;
52const DEFAULT_TIMEOUT_MINUTES = 60;
53const OK = new Set(["success", "skipped", "neutral"]);
54
55/** Validates merge queue settings from the API or the settings page. */
56export function normalizeMergeQueue(q: MergeQueueSettings | boolean): MergeQueueSettings {
57 const o: MergeQueueSettings = typeof q === "object" && q ? q : {};
58 const int = (v: unknown, min: number, max: number) => (Number.isFinite(Number(v)) ? Math.max(min, Math.min(max, Math.floor(Number(v)))) : undefined);
59 const out: MergeQueueSettings = { method: o.method === "squash" || o.method === "rebase" ? o.method : "merge" };
60 const concurrency = int(o.buildConcurrency, 1, 20);
61 const timeout = int(o.checkTimeoutMinutes, 1, 360);
62 if (concurrency !== undefined) out.buildConcurrency = concurrency;
63 if (timeout !== undefined) out.checkTimeoutMinutes = timeout;
64 return out;
65}
66
67/**
68 * A merge queue per protected base branch, like GitHub's. Each queued pull request
69 * gets a merge group: a commit on `gh-readonly-queue/<base>/pr-<n>-<head>` that holds
70 * the base branch, every pull request ahead of it, and its own changes. `merge_group`
71 * (and `push`) workflows run on that commit; once the required checks pass and every
72 * entry ahead has merged, the base branch fast-forwards to exactly the tested commit.
73 * A pull request whose group fails, conflicts or times out leaves the queue, and the
74 * groups behind it are rebuilt without it.
75 */
76export class MergeQueue {
77 private lock: Promise<unknown> = Promise.resolve();
78 /** Why each pull request last left a queue (kept in memory for the enqueue response). */
79 private removals = new Map<number, string>();
80
81 constructor(private repo: RepoDO) {}
82
83 private get sql() {
84 return this.repo.sql;
85 }
86
87 settings(base: string): MergeQueueSettings | null {
88 return this.repo.protectionFor(base)?.mergeQueue ?? null;
89 }
90
91 private rows(base?: string): QueueRow[] {
92 return base
93 ? this.sql.exec<QueueRow>("SELECT * FROM merge_queue WHERE base_ref = ? ORDER BY seq", base).toArray()
94 : this.sql.exec<QueueRow>("SELECT * FROM merge_queue ORDER BY base_ref, seq").toArray();
95 }
96
97 private row(number: number): QueueRow | null {
98 return this.sql.exec<QueueRow>("SELECT * FROM merge_queue WHERE number = ?", number).toArray()[0] ?? null;
99 }
100
101 isQueued(number: number): boolean {
102 return this.row(number) !== null;
103 }
104
105 /** The base branch whose queue holds the merge group on `sha`, if any. */
106 baseForGroup(sha: string): string | null {
107 return this.sql.exec<{ base_ref: string }>("SELECT base_ref FROM merge_queue WHERE group_sha = ?", sha).toArray()[0]?.base_ref ?? null;
108 }
109
110 hasEntries(base: string): boolean {
111 return this.sql.exec<{ n: number }>("SELECT count(*) AS n FROM merge_queue WHERE base_ref = ?", base).one().n > 0;
112 }
113
114 list(base?: string): QueueEntry[] {
115 const out: QueueEntry[] = [];
116 const position = new Map<string, number>();
117 for (const r of this.rows(base)) {
118 const pos = (position.get(r.base_ref) ?? 0) + 1;
119 position.set(r.base_ref, pos);
120 const title = this.sql.exec<{ title: string }>("SELECT title FROM issues WHERE number = ?", r.number).toArray()[0]?.title ?? "";
121 const rules = this.repo.protectionFor(r.base_ref);
122 const required = rules?.requiredChecks ?? [];
123 const checks = r.group_sha ? this.repo.checksAndStatuses(r.group_sha) : [];
124 out.push({
125 number: r.number,
126 title,
127 base: r.base_ref,
128 position: pos,
129 headSha: r.head_sha,
130 method: r.method,
131 deleteBranch: !!r.delete_branch,
132 enqueuedBy: JSON.parse(r.enqueued_by) as Actor,
133 enqueuedAt: r.enqueued_at,
134 state: r.group_sha ? "checking" : "queued",
135 groupRef: r.group_ref,
136 groupSha: r.group_sha,
137 parentSha: r.parent_sha,
138 builtAt: r.built_at,
139 checks: (required.length ? required : [...new Set(checks.map((c) => c.name))]).map((name) => {
140 const c = requiredCheck(name, checks, rules?.requiredCheckSources?.[name]);
141 return { name, state: c.state === "missing" ? "expected" : c.state === "pending" ? (c.status ?? "queued") : (c.conclusion ?? "neutral") };
142 }),
143 });
144 }
145 return out;
146 }
147
148 entry(number: number): QueueEntry | null {
149 const r = this.row(number);
150 return r ? (this.list(r.base_ref).find((e) => e.number === number) ?? null) : null;
151 }
152
153 /** Add a pull request to its base branch's queue ("Merge when ready"). */
154 async enqueue(number: number, input: { method?: QueueRow["method"]; deleteBranch?: boolean }, caller: Caller): Promise<EnqueueResult> {
155 const { issue } = this.repo.collab.get(number);
156 const pull = issue.pull;
157 if (!pull) throw new HttpError(422, `#${number} is not a pull request`);
158 if (await this.repo.isArchived()) throw new HttpError(403, "repository is archived (read-only)");
159 const settings = this.settings(pull.base);
160 if (!settings) throw new HttpError(422, `${pull.base} does not use a merge queue; merge the pull request directly`);
161 if (this.row(number)) return this.result(number);
162 // The queue lands the pull request for whoever enqueued it: agents and workflow tokens only where the branch allows it.
163 const refusal = automaticLandingRefusal(caller, this.repo.protectionFor(pull.base), pull.base === this.repo.meta.defaultBranch, pull.base);
164 if (refusal) throw new HttpError(refusal.status, refusal.message);
165 const m = await this.repo.collab.mergeability(number, caller, { automatic: true });
166 if (!m.mergeable) throw new HttpError(405, `pull request cannot be added to the merge queue: ${m.blockers.join("; ")}`, { blockers: m.blockers });
167 const method = input.method ?? settings.method ?? "merge";
168 if (method === "merge" && this.repo.protectionFor(pull.base)?.requireLinearHistory) throw new HttpError(422, `${pull.base} requires linear history; use squash or rebase`);
169 this.sql.exec("INSERT INTO counters (name, value) VALUES ('queue', 1) ON CONFLICT(name) DO UPDATE SET value = value + 1");
170 const seq = this.sql.exec<{ value: number }>("SELECT value FROM counters WHERE name = 'queue'").one().value;
171 this.sql.exec(
172 "INSERT INTO merge_queue (number, base_ref, seq, head_sha, method, delete_branch, enqueued_by, enqueued_at) VALUES (?, ?, ?, ?, ?, ?, ?, ?)",
173 number,
174 pull.base,
175 seq,
176 pull.headSha,
177 method,
178 input.deleteBranch ? 1 : 0,
179 JSON.stringify({ id: caller.id, login: caller.login, kind: caller.kind, onBehalfOf: caller.onBehalfOf }),
180 now(),
181 );
182 this.emit(number, "enqueued", caller);
183 await this.process(pull.base);
184 return this.result(number);
185 }
186
187 /** Where a pull request stands after a queue pass: still queued, merged, or removed (and why). */
188 private result(number: number): EnqueueResult {
189 const entry = this.entry(number);
190 if (entry) return { state: "queued", entry };
191 const merged = this.sql.exec<{ merge_commit: string | null; merged: number }>("SELECT merged, merge_commit FROM pulls WHERE number = ?", number).toArray()[0];
192 if (merged?.merged) return { state: "merged", entry: null, mergeCommit: merged.merge_commit };
193 return { state: "removed", entry: null, reason: this.removals.get(number) };
194 }
195
196 /** Remove a pull request from the queue at a person's request. */
197 async dequeue(number: number, caller: Caller): Promise<void> {
198 const r = this.row(number);
199 if (!r) throw new HttpError(404, `#${number} is not in the merge queue`);
200 await this.exclusive(async () => {
201 const row = this.row(number);
202 if (row) await this.remove(row, `${caller.login} removed it from the queue`, caller, false);
203 });
204 await this.process(r.base_ref);
205 }
206
207 /** The repository was archived: nothing merges any more, so every queue is emptied, saying why on each pull request. */
208 repositoryArchived(): Promise<void> {
209 return this.exclusive(async () => {
210 for (const r of this.rows()) await this.remove(r, ARCHIVED_REASON);
211 this.armAlarm();
212 });
213 }
214
215 /** Re-evaluate in the background (after checks, pushes and pull request changes). */
216 schedule(base?: string): void {
217 this.repo.background(this.process(base));
218 }
219
220 /** Advance one queue, or every queue: merge, drop failures, rebuild and build merge groups. */
221 process(base?: string): Promise<void> {
222 return this.exclusive(async () => {
223 const bases = base ? [base] : [...new Set(this.rows().map((r) => r.base_ref))];
224 for (const b of bases) {
225 try {
226 await this.step(b);
227 } catch (e) {
228 console.error(`merge queue for ${b} failed`, e);
229 }
230 }
231 this.armAlarm();
232 });
233 }
234
235 private exclusive<T>(fn: () => Promise<T>): Promise<T> {
236 const run = this.lock.then(fn, fn);
237 this.lock = run.catch(() => undefined);
238 return run;
239 }
240
241 private async step(base: string): Promise<void> {
242 const settings = this.settings(base);
243 const baseRef = `refs/heads/${base}`;
244 // An archived repository is read-only: a merge group's check that finishes after the archive merges nothing.
245 const archived = await this.repo.isArchived();
246 for (const r of this.rows(base)) {
247 if (archived) await this.remove(r, ARCHIVED_REASON);
248 else if (!settings) await this.remove(r, `${base} no longer uses a merge queue`);
249 else if (!this.repo.getRef(baseRef)) await this.remove(r, `the base branch ${base} no longer exists`);
250 else {
251 const p = this.sql.exec<{ head_sha: string; merged: number; state: string }>("SELECT p.head_sha, p.merged, i.state FROM pulls p JOIN issues i ON i.number = p.number WHERE p.number = ?", r.number).toArray()[0];
252 if (!p || p.merged || p.state !== "open") await this.remove(r, "the pull request was closed", undefined, false);
253 else if (p.head_sha !== r.head_sha) await this.remove(r, "new commits were pushed to its branch");
254 }
255 }
256 if (!settings || archived) return;
257
258 // Merge from the front: the front group is built on the current base and its checks passed.
259 for (;;) {
260 const front = this.rows(base)[0];
261 const baseSha = this.repo.getRef(baseRef);
262 if (!front?.group_sha || !baseSha || front.parent_sha !== baseSha) break;
263 const verdict = this.verdict(front, base, settings);
264 if (verdict === "pending") break;
265 if (verdict !== "pass") {
266 await this.remove(front, verdict);
267 continue;
268 }
269 if (!this.repo.casRef(baseRef, baseSha, front.group_sha)) break;
270 this.sql.exec("DELETE FROM merge_queue WHERE number = ?", front.number);
271 // The group's commit is now the base branch; its runs (on the deleted branch) may finish.
272 await this.dropGroup(front, { cancel: false });
273 const by = JSON.parse(front.enqueued_by) as Actor;
274 await this.repo.collab.completeMerge(front.number, front.group_sha, baseSha, { ...by, role: "admin" }, !!front.delete_branch);
275 }
276
277 // Each group must sit on the one ahead of it (the first on the base branch). Groups whose
278 // checks failed leave the queue; anything built on a group that changed is rebuilt.
279 let expected = this.repo.getRef(baseRef)!;
280 let built = 0;
281 let blocked = false;
282 const limit = Math.max(1, Math.min(20, settings.buildConcurrency ?? DEFAULT_CONCURRENCY));
283 for (const r of this.rows(base)) {
284 if (!blocked && r.group_sha && r.parent_sha === expected) {
285 const verdict = this.verdict(r, base, settings);
286 if (verdict !== "pass" && verdict !== "pending") {
287 await this.remove(r, verdict);
288 continue;
289 }
290 expected = r.group_sha;
291 built++;
292 continue;
293 }
294 if (r.group_sha) await this.dropGroup(r, { reset: true });
295 if (blocked || built >= limit) {
296 blocked = true;
297 continue;
298 }
299 const group = await this.build(r, expected);
300 if ("error" in group) {
301 await this.remove(r, group.error);
302 continue;
303 }
304 expected = group.sha;
305 built++;
306 }
307 }
308
309 /** "pass", "pending", or why the group failed. */
310 private verdict(r: QueueRow, base: string, settings: MergeQueueSettings): string {
311 const rules = this.repo.protectionFor(base);
312 const required = rules?.requiredChecks ?? [];
313 const checks = this.repo.checksAndStatuses(r.group_sha!);
314 for (const name of required) {
315 const c = requiredCheck(name, checks, rules?.requiredCheckSources?.[name]);
316 if (c.state === "failure") {
317 const what = c.conclusion === "timed_out" ? "timed out" : c.conclusion === "cancelled" ? "was cancelled" : c.conclusion === "action_required" ? "needs action" : "failed";
318 return `the required check '${name}' ${what} on its merge group`;
319 }
320 }
321 const pending = required.filter((name) => requiredCheck(name, checks, rules?.requiredCheckSources?.[name]).state !== "success");
322 if (!pending.length) return "pass";
323 const timeout = (settings.checkTimeoutMinutes ?? DEFAULT_TIMEOUT_MINUTES) * 60_000;
324 if (r.built_at && Date.parse(r.built_at) + timeout <= Date.now()) {
325 return `required checks did not finish within ${settings.checkTimeoutMinutes ?? DEFAULT_TIMEOUT_MINUTES} minutes (${pending.map((n) => `'${n}'`).join(", ")})`;
326 }
327 return "pending";
328 }
329
330 /** Build the merge group of `r` on `parent`, create its branch and start its workflows. */
331 private async build(r: QueueRow, parent: string): Promise<{ sha: string } | { error: string }> {
332 const store = this.repo.store;
333 const { issue } = this.repo.collab.get(r.number);
334 const pull = issue.pull!;
335 const by = JSON.parse(r.enqueued_by) as Actor;
336 const ts = Math.floor(Date.now() / 1000);
337 const committer = { name: by.login, email: `${by.login}@users.noreply.diffinery.com`, timestamp: ts, timezone: "+0000" };
338 let sha: string;
339 if (r.method === "rebase") {
340 let cur = parent;
341 for (const c of await this.repo.collab.pullCommits(r.number)) {
342 if (c.parents.length !== 1) return { error: "rebase merges cannot include merge commits; use a merge commit or squash" };
343 const [p, mine, theirs] = await Promise.all([readCommit(store, c.parents[0]!), readCommit(store, cur), readCommit(store, c.sha)]);
344 const merged = await mergeTrees(store, p.tree, mine.tree, theirs.tree);
345 if (merged.conflicts.length || !merged.tree) return { error: `it conflicts with ${pull.base} and the pull requests ahead of it (${merged.conflicts.slice(0, 5).join(", ")})` };
346 cur = await store.write("commit", serializeCommit({ tree: merged.tree, parents: [cur], author: theirs.author, committer, message: theirs.message, extraHeaders: theirs.extraHeaders }));
347 }
348 sha = cur;
349 } else {
350 const mb = await mergeBase(store, parent, r.head_sha);
351 const [pt, ht, bt] = await Promise.all([readCommit(store, parent), readCommit(store, r.head_sha), mb ? readCommit(store, mb) : null]);
352 const merged = await mergeTrees(store, bt?.tree ?? null, pt.tree, ht.tree);
353 if (merged.conflicts.length || !merged.tree) return { error: `it conflicts with ${pull.base} and the pull requests ahead of it (${merged.conflicts.slice(0, 5).join(", ")})` };
354 const message =
355 r.method === "squash"
356 ? `${issue.title} (#${r.number})\n\n${(await this.repo.collab.pullCommits(r.number)).map((c) => `* ${c.message.split("\n")[0]}`).join("\n")}\n`
357 : `Merge pull request #${r.number} from ${pull.head}\n\n${issue.title}\n`;
358 const author = r.method === "squash" ? squashSig(issue.author, committer) : committer;
359 sha = await store.write("commit", serializeCommit({ tree: merged.tree, parents: r.method === "squash" ? [parent] : [parent, r.head_sha], author, committer, message }));
360 }
361 const ref = `refs/heads/${QUEUE_BRANCH_PREFIX}${pull.base}/pr-${r.number}-${r.head_sha}`;
362 const old = this.repo.getRef(ref);
363 this.repo.casRef(ref, old, sha);
364 this.sql.exec("UPDATE merge_queue SET parent_sha = ?, group_sha = ?, group_ref = ?, built_at = ? WHERE number = ?", parent, sha, ref, now(), r.number);
365 // GitHub runs push workflows on merge group branches too, then merge_group workflows.
366 await this.repo.afterRefUpdate(ref, old ?? ZERO_OID, sha, QUEUE_BOT);
367 await this.repo.actions.onMergeGroup({ number: r.number, base: pull.base, ref, sha, parent, title: issue.title, sender: by });
368 this.repo.broadcast(`pr:${r.number}`, { action: "queue" });
369 return { sha };
370 }
371
372 /** Delete a group's branch and (unless it merged) cancel its runs; `reset` keeps the entry queued for a rebuild. */
373 private async dropGroup(r: QueueRow, o: { reset?: boolean; cancel?: boolean } = {}): Promise<void> {
374 if (r.group_ref) {
375 if (o.cancel !== false) await this.repo.actions.cancelRunsOnRef(r.group_ref, "Cancelled because its merge group was rebuilt or left the queue.");
376 const sha = this.repo.getRef(r.group_ref);
377 if (sha && this.repo.casRef(r.group_ref, sha, null)) await this.repo.afterRefUpdate(r.group_ref, sha, ZERO_OID, QUEUE_BOT);
378 }
379 if (o.reset) this.sql.exec("UPDATE merge_queue SET parent_sha = NULL, group_sha = NULL, group_ref = NULL, built_at = NULL WHERE number = ?", r.number);
380 }
381
382 private async remove(r: QueueRow, reason: string, by: Caller = QUEUE_BOT, comment = true): Promise<void> {
383 this.sql.exec("DELETE FROM merge_queue WHERE number = ?", r.number);
384 await this.dropGroup(r);
385 this.removals.set(r.number, reason);
386 this.emit(r.number, "dequeued", by);
387 if (comment) {
388 try {
389 this.repo.collab.addComment(r.number, `This pull request was removed from the merge queue: ${reason}.`, QUEUE_BOT);
390 } catch (e) {
391 console.warn("merge queue comment failed", e);
392 }
393 }
394 this.repo.broadcast(`pr:${r.number}`, { action: "queue" });
395 }
396
397 private emit(number: number, action: "enqueued" | "dequeued", by: Caller | Actor): void {
398 const p = this.sql.exec<{ head_ref: string; head_sha: string; base_ref: string }>("SELECT head_ref, head_sha, base_ref FROM pulls WHERE number = ?", number).toArray()[0];
399 if (!p) return;
400 const m = this.repo.meta;
401 this.repo.emit({ type: "pull_request", action, repoId: m.repoId, owner: m.owner, repo: m.name, number, headRef: p.head_ref, headSha: p.head_sha, baseRef: p.base_ref, actor: { id: by.id, login: by.login, kind: by.kind, onBehalfOf: by.onBehalfOf }, at: now() });
402 }
403
404 /** Wake up when the earliest check timeout of a building group runs out. */
405 private armAlarm(): void {
406 let next = Infinity;
407 for (const r of this.rows()) {
408 if (!r.built_at) continue;
409 const minutes = this.settings(r.base_ref)?.checkTimeoutMinutes ?? DEFAULT_TIMEOUT_MINUTES;
410 next = Math.min(next, Date.parse(r.built_at) + minutes * 60_000 + 1000);
411 }
412 this.repo.armAlarm(Number.isFinite(next) ? next : null);
413 }
414}