---
title: Merge queue
description: magus queue is a speculative, partitioned merge queue; magus supplies its version control, its affected sets and which files are generated.
tags: [merge-queue, queue, magus queue, pull-request, auto-merge, speculation, stacks, github, provider, mergequeue]
---

# Merge queue

`magus queue` is a speculative, partitioned merge queue, compiled into magus the way
`magus buzz` is: one binary holds what it needs. Its code is `internal/queue`, a
package tree of the magus module. The queue takes magus's version control capability
interfaces as they are, narrowed per step, and its `client` package wires magus in: the
version control backend the checkout names (git today; jj, Mercurial and Sapling refuse
by name), and each change's affected set and the workspace's declared outputs through
magus's Go SDK, with the workspace loaded once. Another build tool answers through
`--facts <command>`.

A change joins the queue when its provider reports merge intent on it. With the built-in
GitHub provider that is auto-merge enabled on a pull request, or a label made of the
prefix `describe` reports and a merge method (`merge-queue: squash`) on the pull request,
or on a stack's top. From there the queue:

- builds a candidate per change, main plus every change ahead of it in its partition,
  then gates up to `--depth` of them at once, each running only what its own change adds;
- keeps changes whose affected sets are disjoint in separate partitions, which never wait
  on each other;
- merges a change stacked on another after it, with its own delta measured from that
  change's head;
- settles drift in the candidate itself: a conflict the low-risk classifier resolves is
  resolved, and generated files the merge leaves stale are regenerated there, so a
  change whose branch fell behind main needs nothing from its author;
- rebuilds each green candidate in the job that holds the write credential, from the
  change's head and main's own regeneration or validation's checked one, running none
  of the change's code, and merges it only when the rebuild is the commit validation
  gated;
- merges each green change as its own commit, by its author, with the merge method the
  author picked, as soon as every change beneath it in its partition has merged;
- checks after each merge that main carries exactly the tree it predicted, in the shape
  the merge method gives, and stops if it does not;
- refuses changes from forks, whose branches it cannot push to.

It kicks an author back only for what their own change did: a conflict the classifier
will not resolve, a red gate on a candidate whose every change beneath is validated and
whose base is green on the same projects, a regeneration their code broke, or a stack it
cannot merge. Generated files its merge needs regenerated by code the change touches go
back to the author only when validation left no regenerated candidate apply can check.
A gate killed by a signal, an OOM kill included, is that change's red. Only what the queue can prove is the
machine's (a hook that could not start, the queue's own cancellation) stops a partition
and leaves the change queued.

## Using it

On GitHub, queuing a pull request is enabling auto-merge on it, with the merge method
you want it to land with:

```sh
gh pr merge 482 --auto --squash
```

or "Enable auto-merge" on the pull request's page. Nothing else changes for the author:
push fixes as usual, and a push to a queued pull request has it validated again. Once
the queue's `merge-queue` status is main's required check, auto-merge cannot fire on its
own: GitHub waits for that status, and the queue sets it to `success` only when it is
about to see that pull request merged.

| To                              | Do                                                      |
| ------------------------------- | ------------------------------------------------------- |
| queue a pull request            | `gh pr merge <n> --auto --squash` (or `--rebase`)       |
| queue one GitHub says conflicts | label it `merge-queue: squash`                          |
| queue a stack                   | label its top pull request `merge-queue: squash`        |
| take it out                     | `gh pr merge <n> --disable-auto`, or remove the label   |
| list what is queued             | `magus queue ls --provider github --base main`          |
| see why one is waiting          | its `merge-queue` status, which reads `waiting: <why>`  |
| see why one was kicked back     | the queue's newest comment on it                        |
| land it past the queue          | `gh pr merge <n> --admin`: an admin's bypass, see below |

A pull request carries at most one of the queue's status labels, and the queue sets and
removes them itself:

| Label                             | Means                                            | Removed when                                                     |
| --------------------------------- | ------------------------------------------------ | ---------------------------------------------------------------- |
| `merge-queue: queued`             | the queue holds it                               | it is kicked back or merged, or the next apply run finds it gone |
| `merge-queue: kicked back`        | kicked back; the queue's newest comment says why | it is queued again, or the next apply run finds it closed        |
| `merge-queue: needs regeneration` | its merge needs regeneration its own code runs   | it is queued again, or the next apply run finds it closed        |

Setting one removes the other two. When the queue sees a pull request merge, it removes
every `merge-queue:` label from it, the stack's intent label included; one merged or
closed where the queue did not see it (by hand, or closed unmerged) loses them on the
next apply run, which lists the closed pull requests still carrying any. The intent label
is the prefix followed by a merge method, exactly: `merge-queue: squash`,
`merge-queue: rebase` or `merge-queue: merge`, so no status label ever reads as intent.

GitHub's auto-merge follows GitHub's own mergeability, which says nothing of what the
queue can settle. A pull request GitHub reports as conflicting is queued by the label
instead; the queue merges it onto main, resolves what the low-risk classifier allows and
regenerates what the merge left stale, and kicks it back with `KICK_CONFLICT`, naming
the files, only for a conflict it will not resolve.

A pull request whose merge leaves generated files stale (one conflicts, or main changed
one since the pull request forked) has them regenerated in its candidate, the gate runs
on the result, and apply lands it through an update commit on the branch, with the
bytes validation gated (see [Trust model](#trust-model)). Only when validation left
nothing apply can check, and the build tool cannot prove main's regeneration runs none
of the pull request's own code, does the queue kick it back with `KICK_REGENERATION` and
label it `merge-queue: needs regeneration`. Merge main in, regenerate, push, and queue
it again: the merge then leaves the files as the pull request has them.

A pull request the queue kicks back gets a new comment, and its auto-merge or label is
removed. The comment says what failed on which commits, links the validation run, and
holds, collapsed, the files at issue and a block that runs the same validation on your
machine; its last line is the command that queues it again. One that waits (for a
review, for the change beneath it, for main to settle) stays queued and needs nothing.

An admin merge skips validation and ordering both. The queue notices on its next run
that main moved without it and plans again from the new tip, so nothing breaks, but
nothing checked the combination either. Keep it for when the queue itself is down.

## Trust model

Bytes produced by running a change's code are as untrusted as code its author typed.
Validation runs every change's code, the gate and the regeneration alike, so everything
it writes is a claim, never content: the job holding the write token never takes a
generated file, a candidate tree or a review proof from a verdict.

- **Apply rebuilds.** For each green verdict, apply builds the candidate again from the
  change's head onto what it rebuilt for the change beneath, with the same fixed
  identity and date validation used, and merges only when its rebuild is the commit
  validation gated. The verdict's candidate commit is a hash apply compares against.
- **Generated bytes come from main's regeneration, from validation's checked one, or
  from the author.** Where the candidate holds regenerated files (validation's
  regeneration rewrote something, or a generated file conflicted), apply runs main's
  own regeneration (`apply --regenerate`) in its rebuild, but only after the build tool
  proves the change touches none of the code that regeneration runs: the generating
  targets' definitions, their spell and op sources, toolchain pins and lockfiles, the
  magusfiles, and every input those targets read, whatever its extension (a
  `CMakeLists.txt` is code to CMake). The proof reads main's declarations, so it also
  covers everything a change merged beneath the candidate in the same run changed, and
  a proof failing only there waits for the next run.
- **Where the proof fails, apply checks validation's regeneration instead of running
  one.** Validation's regeneration ran the change's own generators, and when it
  committed anything, validation uploads that commit beside the verdict as
  `candidate.bundle`, a git bundle of the one commit on the merge beneath it. Apply
  loads the bundle and takes the verdict's candidate commit from it only when that
  commit's sole parent is apply's own merge of the pinned head onto what it rebuilt it
  onto (auto-resolved hunks included, settled by apply itself), and it differs from
  that merge only in files main's workspace declares as outputs, the classification
  `magus describe file` reports. The commit is the one the gate ran on, so its tree is
  the gated tree. Every file it changes must be a regular file (`100644`), or `100755`
  only where apply's merge already holds it `100755`. A bundle that does not load, lacks
  that commit, puts it on anything else, touches any other file, or holds a symbolic
  link, a submodule, a mode change or a new executable is `KICK_REFUSED`, naming the
  path. With no bundle, the change leaves
  the queue with the paths (`KICK_REGENERATION`): its author merges main in,
  regenerates and pushes, and it is queued again. Either way the regenerated bytes reach
  the author's branch only in the queue's update commit, pushed under a lease on the
  head. Generated files a change carries and its merge leaves alone are its author's
  bytes, merged as they are once the gate's drift check has held them to what their
  generators make.
- **A hook runs in the base's sandbox.** Every hook (the gate, the regeneration, a
  `--facts` command) runs under the policy magus builds from the base's `sandbox` config,
  never a candidate's: its mode raised to at least `best-effort`, its `sandbox.allow`
  entries and its `sandbox.env.passthrough`, and the declarations of every spell the
  base loaded, rooted at the hook's checkout, with the candidate's scratch directory
  writable and `TMPDIR` inside it. Every spell's, not one project's: a hook is usually a
  nested magus, and a grant the hook lacks is one no target under it can have.
  - Everywhere, the environment is an allowlist. A hook gets only the names magus's
    sandbox gives a sandboxed child (`PATH`, `HOME`, `USER`, the locale, `TERM`, and on
    Linux the XDG directories) and the base's passthrough, then the queue's
    `--scratch-env` variables and its own, and `MAGUS_SANDBOX` naming its mode, so a
    magus the hook runs confines its own targets at least as hard
    ([MGS2010](../reference/codes/sandbox/MGS2010.md) refuses a weaker `--sandbox`).
    `MERGEQUEUE_TOKEN`, `GITHUB_TOKEN`, the Actions runtime token and every other
    variable nothing names never reach it. A credential the passthrough names reaches
    every hook: that is the workspace's choice.
  - Everywhere, the hook's program must be one the policy lets run
    ([MGS2007](../reference/codes/sandbox/MGS2007.md)): on `PATH`, in the system and
    toolchain trees, in the checkout, or under a `sandbox.allow` entry.
  - Where the kernel has landlock (Linux), it holds the hook and every process the hook
    starts to the policy: read, write and run in the checkout, write in the scratch
    directory and in the tool caches the spells declare (`GOCACHE`, `GOMODCACHE`, npm,
    pip, buf and the like), read and run on the system and toolchain trees. Nothing else is
    reachable: not another candidate's checkout, not a credential under the home
    directory, not `/proc/<pid>/environ` of the queue or the runner, not a GitHub
    Actions file command. Landlock also sets no-new-privileges, so `sudo` cannot lift a
    confined hook, and from landlock ABI 6 a hook cannot signal a process outside its
    sandbox.
  - With `--sandbox=required`, or `sandbox.mode: required` on the base, the queue
    refuses ([MGS2012](../reference/codes/sandbox/MGS2012.md)) to run a hook the kernel
    cannot confine, and stops. `tools/gha-queue.buzz` passes it to `validate` and
    `apply`. Without it, on a host without landlock (macOS, Windows, an older Linux), a
    hook runs under the environment allowlist and the program check alone: `magus queue
    validate` runs on a laptop, and confines nothing on its filesystem there.

  What the sandbox does not confine: the network; the tool caches the policy grants,
  which candidates share unless `--scratch-env` points each tool into the scratch
  directory; the filesystem wherever the kernel cannot confine; and a process that leaves
  the hook's process group, which lives until the CI job ends. The queue itself writes
  into a candidate only through its root, and never regenerates in a checkout where the
  change holds a symbolic link at or above a path it changes or regeneration writes. The
  runner and the job's later steps still hold the job's tokens, so where the kernel does
  not confine a hook, one that goes looking can read them from `/proc/<pid>/environ`,
  since a hosted runner grants passwordless `sudo`. With the Actions runtime token it can
  save cache entries in its run's scope, which for a validation started by a push or a
  dispatch on main is main's scope, the one every branch and tag run restores from.
- **No trusted job restores the Actions cache.** A job holding a secret, a write token or
  `id-token` restores no Actions cache: `jdx/mise-action` runs with `cache: false`,
  `setup-magus` restores no run history unless `restore-history` is set, and the Docker
  and MSYS2 setup actions run with their caches off. The queue's plan and validation
  restore nothing either, so an entry an earlier validation planted cannot decide a
  later verdict. magus's
  shared cache is signed with a key only main's CI holds and verified against the trusted
  keys on every read, so a planted entry is refused. The jobs that still restore, the CI
  plan and report, hold only read tokens; a planted run history can make main's own CI
  run gate less, never reach a secret.
- **An update commit is the queue's.** It is authored and committed by the committer,
  never by the identity the change's head claims.
- **Validation reads the signed cache through a read-only proxy.** With
  `validate --remote-cache-read`, the queue reads the runner's cache service URL and
  runtime token itself and serves hooks a loopback proxy in their place, with a random
  stand-in token that authenticates nothing but the proxy. The proxy forwards only
  `GetCacheEntryDownloadURL`, the lookup whose answer is a pre-signed blob URL the hook
  downloads with no credential, and refuses every other method, so no write reaches the
  cache service through it. Hooks get the base's trusted keys, verification on and
  remote writes off, so an entry replays only when main's key signed it. This removes
  the token from a hook's environment and nothing more: the real one is in the
  environment of the validate process that started the hook, and where the kernel does
  not confine the hook, one that goes looking can read it there as it can from the
  runner.
- **Only the kernel confines a hook to its checkout.** The allowlist keeps GitHub
  Actions' file commands (`GITHUB_ENV`, `GITHUB_PATH`, `GITHUB_OUTPUT`, ...) and the
  runner's own paths from a hook, but withholding a path only unnames it. Landlock is
  what puts those paths out of reach, and only on Linux, so the validation job is
  trusted for nothing after its first hook runs.
- **A kick-back shows the author's bytes as text.** Its words are apply's, from facts it
  checked against the plan; what the verdict said is shown in a fence longer than any
  run of backticks in it, capped at 4 KiB, and every file name is a code span, quoted
  when it holds a line break or another character that is not printable. The lines that
  reproduce the run come from apply's own `--reproduce-gate` and
  `--reproduce-regenerate`, never from the verdict.
- **Generated means declared.** A file is generated when some target declares it as its
  output (`magus describe file` says `output`), read from main's declarations. A
  `linguist-generated` attribute alone makes nothing generated: a vendored tree so marked
  is source, and a reviewer has to see it. A file that `generate`, or a target it
  needs, rewrites in place (`magus describe file` says `declared: update`) stays
  source: regeneration may write it, but its conflicts are the author's and a review
  sees it. Another target's in-place update, such as a formatter's, does not count. A file magus maintains itself
  (`maintained`, such as `.gitattributes`) is rewritten by main's magus whenever a hook
  runs it, so the queue puts the change's version back and never commits main's.
- **A resolution is main's computation.** A source conflict
  [auto-resolution](#auto-resolving-source-conflicts) settles is settled by apply's own
  magus from the three versions of the file and main's classification, never taken from
  a verdict, and the result must be the commit validation gated.
- **A review is proven in apply.** Whether a review of an older commit covers a merge of
  main into the change is a version control question apply answers itself, and a merge
  differing only in generated files is covered only when main's regeneration, run on the
  plain merge, gives exactly that merge's tree.
- **Apply follows only the base's own validation.** A pull request's event runs the pull
  request's own copy of the workflow, a fork's included, so that run could upload any
  plan and any verdict. With a run as its source, `apply` reads what started the run
  before it downloads anything, and refuses
  ([MGS3027](../reference/codes/sandbox/MGS3027.md)) any run but the `--workflow`
  definition started by a push or a dispatch on `--base` of the repository itself.
- **Apply pins what it can read itself.** The plan comes from validation's run, so apply
  checks it against its own facts and stops
  ([MGS3028](../reference/codes/sandbox/MGS3028.md)) before merging anything that rests
  on a disagreement: the plan must name apply's own `--base` and remote, its base commit
  must be on the base apply reads, and a stacked change's stack base must be beneath its
  head, off the base, and the head the provider confirmed for the change beneath it (or
  the newest commit it carries of a change the provider lists as merged). A stack base
  is where the delta reviewers approved starts, so a forged one would merge a delta
  nobody reviewed, such as one reverting the base. A stack the provider now declares
  differently only makes the change wait, since it may have changed after planning.
- **Apply writes its own words.** The squash message is apply's, from the change's own
  commits; a verdict carries none.
- **Candidates share nothing.** Each candidate gets a checkout and a scratch directory
  of its own, so no change's hook can plant a cache entry another candidate's gate
  replays; `tools/gha-queue.buzz` points magus's and Go's caches there
  with `--scratch-env`. Every
  process a hook starts is killed when the hook exits, before its verdict is recorded; a
  process that leaves the hook's process group ends with the CI job. magus runs a hook as
  it runs a target's command: the group is killed once the hook's exit is seen and
  before the hook is reaped, since its id can name another hook's group from then on.
  Where that exit cannot be seen unreaped (anything but Linux, macOS and the BSDs), what
  outlives the hook is left running.

How the provider's own credential is scoped is a separate question, answered under
[Providers](#providers).

## Vocabulary

| Term         | Meaning                                                                   |
| ------------ | ------------------------------------------------------------------------- |
| base         | the branch the queue merges into                                          |
| base commit  | the base's tip when the plan was made; every partition starts on it       |
| candidate    | a speculative merge commit: one change merged onto the candidate beneath  |
| onto         | the commit a candidate was built onto: the base commit or the one below   |
| tip          | the base's commit at apply                                                |
| head         | a change's own commit                                                     |
| stack base   | the head of the change a change is stacked on; its own delta starts there |
| merge method | `merge`, `squash` or `rebase`: how the provider merges the change         |
| verdict      | what the queue decided: `merge`, `kick`, `wait`, or `merged` when done    |
| code         | why a change waits or was kicked back, from a closed set                  |

## Commands

Every subcommand writes JSONL events (`mergequeue.event/v1`) on stdout. Hook output and
errors go to stderr. A usage mistake exits 2; a queue that ran and failed exits 1.

| Subcommand | Reads                                          | Writes                                                                 | Rights                       |
| ---------- | ---------------------------------------------- | ---------------------------------------------------------------------- | ---------------------------- |
| `describe` | the provider                                   | setup steps, or a `mergequeue.capabilities/v1` document with `-o json` | read                         |
| `ls`       | the provider                                   | a `mergequeue.changes/v1` document                                     | read                         |
| `plan`     | changes (stdin or `--changes`)                 | a `mergequeue.plan/v1` file                                            | read                         |
| `validate` | the plan (stdin, with `--stdin`)               | the plan and one `mergequeue.verdict/v1` per change                    | read; runs the changes' code |
| `apply`    | a source: the plan, then verdicts as they come | merges through the provider                                            | write; runs no change's code |

```sh
magus queue ls --provider github --base main > changes.json
magus queue plan --changes changes.json --provider github --out plan.json
magus queue validate --stdin --verdicts verdicts \
  --gate 'magus run ci --no-default-charms' \
  --regenerate 'magus run generate:rw' \
  --scratch-env MAGUS_CACHE_DIR=magus --scratch-env GOCACHE=go-build < plan.json
magus queue apply --provider github --base main \
  --regenerate 'magus --sandbox=best-effort run generate:rw' \
  --reproduce-gate 'magus run ci --no-default-charms' \
  --reproduce-regenerate 'magus run generate:rw' \
  --scratch-env MAGUS_CACHE_DIR=magus verdicts
```

`--reproduce-gate` and `--reproduce-regenerate` repeat validation's `--gate` and
`--regenerate` for apply, which never runs them: a kick-back validation decided shows
them as the way to run it again. A verdict records its own, but apply never shows a line
a job running the change's code wrote. Without them a kick-back shows no reproduction.

`--scratch-env NAME=DIR`, on `validate` and `apply` and repeatable, sets `NAME` to `DIR`
inside the checkout's scratch directory in every hook's environment, creating the
directory. It keeps
each candidate's caches its own without the hook line saying so, which leaves the line
one a person can paste and run; each verdict records the lines validation ran.

The checkout the queue works in is the one at magus's global `--root` (`-C`), before the
subcommand as with git, and every relative path resolves against it. magus's other global
flags apply as everywhere; `--dry-run` makes `apply` report what would merge and call
nothing on the provider. `validate` takes no `--provider`: it runs the changes' code, so
it never talks to one. `plan` requires one, since it checks approval. `--remote` names a
remote configured in the checkout (`origin` unless given); a URL is refused. `--vcs`
names the backend (`git` unless given); the queue reads neither `MAGUS_VCS_ENABLED` nor
`MAGUS_VCS_NAME`, which configure magus's own use of version control. `magus queue` never
runs through the server: it acts on the caller's checkout.

`validate` and `apply` build each candidate by merging in a checkout of that one, so it
must be a full clone. A partial clone (`--filter=blob:none`) is refused: git there asks
the remote for any object it lacks, and a merge can ask for a blob it just wrote, which
the remote never had. `plan` builds no candidate and works in either.

`plan` checks each change's approval at the commit a review of its head covers, finds
which changes are stacked on which, drops what conflicts with main on its own (kicked
back with the conflicting files and the commits that touched them), and partitions the
rest. `validate --only <id>` validates one change: the changes beneath it in its
partition are merged under it but not gated, which is how a CI system spreads one plan
over separate jobs; a red there waits rather than kicks back, since it may be a change
beneath it that failed. `--parallel` caps the work done at once, and means the number of
CPUs when zero, for `plan` and `validate` alike.

`apply <source>` reads the plan and the verdicts from one source, which carries both:

| Source      | What it reads                                                       |
| ----------- | ------------------------------------------------------------------- |
| `<dir>`     | the directory `validate --verdicts` writes                          |
| `run:<run>` | the artifacts of a validation run, `<run>` as the provider names it |

The GitHub provider names a run `<owner>/<name>/runs/<id>`. When the text before the
first `:` reads as a URL scheme of two or more characters, the source is a scheme, and a
scheme other than `run` is a usage error. Write `./x:y` for a directory whose name would
read as one; a one-letter scheme is a Windows drive, so `C:\queue` is a directory.

`apply` follows its source until the source is complete: a directory once `.done`
appears in it, a run once it has completed. `--once` applies what the source holds now
and stops, leaving the rest queued; `--interval` sets how often a follow reads the source
and is refused with `--once`. Each update commit the queue pushes is committed by the
committer the provider's `describe` names; `--committer "Name <email>"` overrides it,
for example `--committer "Release Bot <release-bot@example.com>"`. magus has no default:
with neither, a change that needs an update commit waits with `WAIT_NO_COMMITTER` and
apply stops with an error. `--app <slug>` names the app whose token the provider writes
with, and apply checks that the base requires the queue's status from that app. The
GitHub provider requires it: without one it refuses to describe a setup or to merge.

A run source (`run:<owner>/<name>/runs/<id>` on GitHub) needs `--workflow`, the
definition the run must have run. Every listing says what started the run: apply
refuses the run ([MGS3027](../reference/codes/sandbox/MGS3027.md)), downloading nothing,
unless it ran `--workflow` on `--base` of its own repository, started by an event that
runs the base's own copy of it (a push or a dispatch on GitHub). A source directory is
the caller's own, and takes no `--workflow`.

A run source asks the provider's `list_artifacts` for the run's `mergequeue-plan`
artifact, then for each `mergequeue-verdict-<id>` artifact as the run uploads it, and
merges while slower candidates are still validating. The provider reads the run's status
before each listing, so apply stops following only after a listing made once the run had
completed. It downloads over https alone, with the headers the provider returns, drops
them all on a redirect to another host, and refuses a redirect away from https. A
download past 32 MiB, an archive past 64 entries or 64 MiB unpacked, an entry that is
not a regular file inside the artifact, or a verdict that does not read, holds that one
change and nothing else. A provider without `list_artifacts` cannot be followed through
a run, and `apply` says so before reading anything.

## Input: `mergequeue.changes/v1`

```json
{
  "schema": "mergequeue.changes/v1",
  "base": "main",
  "remote_url": "https://github.com/acme/acme",
  "changes": [
    {
      "id": "482",
      "repo": "acme/acme",
      "head": "4b1c...",
      "ref": "refs/pull/482/head",
      "branch": "fix-parser",
      "base": "main",
      "title": "fix: parser",
      "method": "squash",
      "parent": "481",
      "fork": false,
      "affected": ["libs/parser", "apps/web"],
      "unbounded_by": ""
    }
  ],
  "merged": [
    {"id": "479", "head": "9f8e...", "commit": "3f9b...", "method": "squash"}
  ],
  "unqueued": [
    {"id": "490", "repo": "acme/acme", "head": "a1b2...", "mark": "queued"}
  ],
  "closed": [
    {"id": "475", "repo": "acme/acme"}
  ]
}
```

`id`, `head`, `base` and `method` are required, and two changes never share a head. An
id is letters, digits, `.`, `_` and `-`, not starting with `.` or `-`, since it names a
directory; `head` is a full commit id, and `ref`, `branch` and `base` must be names git's
`check-ref-format` accepts. `method` is `merge`, `squash` or `rebase`: a provider's
default the queue cannot see is no method. `parent` is the change the provider says this
one is stacked on, a hint the plan checks against ancestry. Changes are in queue order.
`affected` is the set of units (projects, packages, anything the caller partitions by)
the change can reach. Omitted or `null` means unknown, and `unbounded_by` names why a set
is not a proof; either one puts the change in one partition with everything. An empty
list is a proof that the change reaches nothing.

`merged` lists the merged changes whose head a queued change carries. Planning checks
that main carries each one's `commit` and refuses the whole input when it does not.
`unqueued` lists every other open change: a queued change carrying the head of one waits
with `WAIT_UNQUEUED_BELOW`, since merging it would merge that change's commits unqueued.
So does one built on it before a merge of main went on top: planning fetches each
unqueued head, peels those merges off, and holds a change carrying what is left. A change
built on a fork waits on the fork's kick-back the same way; the fork's head is fetched
for its ancestry only, and only when the listing holds another change. `closed` lists
the closed changes still showing one of the provider's queue labels; planning carries
them into the plan, and apply clears their labels.

## Stacks

A change is stacked on another when it carries that change's head and main does not:
the other is open in the queue, or merged as a squash or a rebase, which leaves its head
off main. A merge of main into the change beneath (GitHub's "Update branch", or an
update commit the queue pushed) does not break the stack. The nearest such change is the
change's stack base, and its own delta is measured from there:

- it merges after the change beneath it, in the same partition whatever their keys;
- its candidate is built from its stack base, so a line it deleted from the change
  beneath stays deleted after that change merges as a squash, where the plain merge from
  its fork point would bring it back;
- when the change beneath is kicked back, or waits, or its candidate cannot be built,
  it waits too and is never blamed: `WAIT_BELOW_KICKED` or `WAIT_BELOW`.

The provider's `parent` must agree with ancestry. A change declaring a parent it is not
built on waits with `WAIT_RESTACK`; one declaring a parent the queue does not list waits
with `WAIT_BELOW`. Refused, with `KICK_REFUSED`:

- a stack mixing merge methods, since a squashed change beneath a merged one appears
  twice in `git log`;
- a stacked change with the rebase method, until predicting a rebase no longer needs git's
  experimental `replay`;
- a change built on two queued changes neither of which is built on the other;
- changes stacked on each other in a cycle, as two changes at one commit are;
- a stack more than 16 unmerged changes deep.

A change stacked on a squashed one usually merges through an update commit whose tree is
the validated one: the tip plus the change's own delta, which is the diff its reviewers
approved. Where the provider needs stacked branches linear, the update commit sits on the
tip alone: it replaces the branch's commits with one holding their delta, made by the
queue (never passed off as the author's), naming the head it replaces, whose commits stay
reachable by id. The queue refuses that replacement while another open change is stacked
on the head it would replace.

An approval carries over a rebase that only moved the change: its whole diff, replayed
onto the new base without a conflict, is exactly the new head. It does not carry over
when the approved commit carries an unqueued change's head, carries commits of a listed
or merged change without that change's current head, or forked from anything but its
stack base, since the approval was given on a diff that excluded what the rebase includes.

Where the provider merges stacks atomically, a validated run of changes stacked on each
other merges in one call through its top, when merging each one's own delta gives each
one's validated tree. The call pins every member to the head it was validated at. The
queue then checks every member's tree and shape, and stops when the provider merged only
part of the run.

## Hooks on each candidate

A hook is a command and its arguments, not a shell line. `--gate`, `--regenerate` and
`--facts` are read once, when the flags are, as sh words: quotes and backslashes group
and escape, and nothing else is shell. A variable, a command substitution, a pipe, `;`,
`&&`, a redirection, a glob, a comment or a leading `NAME=value` is refused with
[MGS3026](../reference/codes/sandbox/MGS3026.md); put such a line in a script and point
the flag at the script. A queue that is cancelled sends each running hook's process
group `SIGTERM` and kills it 30 seconds later. The queue runs the command directly, in a
process group of its own, in the candidate's checkout and
[the base's sandbox](#trust-model), and appends its inputs as arguments, the way `magus
run <target> [project...]` takes projects:

| Hook                    | Arguments                                                         | Stdin                          |
| ----------------------- | ----------------------------------------------------------------- | ------------------------------ |
| `validate --gate`       | the change's affected projects                                    | nothing                        |
| `validate --regenerate` | the change's affected projects                                    | the generated paths to rewrite |
| `apply --regenerate`    | the projects that generate those paths, or every one if unbounded | the generated paths to rewrite |
| `--facts`               | the fact asked for: `affected`, `outputs`, `generation` or `all`  | what that fact takes           |

A change whose affected set is no proof (unknown, or `unbounded_by` set) gets every
project instead, spelled as the build tool spells it: `/` for magus, and what the facts
command answers to `all` for another tool. A change that reaches no project has nothing
to gate and validates green. So `magus run ci --no-default-charms` runs as `magus run ci
--no-default-charms libs/parser apps/web`, a line a person can run as it stands.

No `--` separates the projects from the hook's own words, since `magus run` reads what
follows `--` as the tool's arguments rather than projects. A project path can begin
with `-` (a change can add a directory named `--gate=x`), so planning kicks back a
change whose affected set holds one with `KICK_REFUSED`, and a hook is never run with
one. Paths on stdin are one per line, and git allows a line break (or a carriage
return) in a path, which would read as two: such a path is never written. A
regeneration asked to rewrite one refuses the change, `affected` reads a change
touching one as unbounded, so it gates every project, and `outputs` leaves one
unclassified, which makes it source.

The gate is green on exit 0, and anything else its processes do is red: another exit
status, a death by signal, or exit 75 (`EX_TEMPFAIL`, which magus returns when a lock or
the machine budget is busy) three times running. Its projects are the top change's, so
it runs only what that change adds. When a candidate whose every change beneath is
validated is red, the queue gates the commit it was built onto with the same command
and the same projects, once a run for every change that asks. Red there, the change waits
with `WAIT_BASE_RED`, keeps its place and is told nothing; green, it is kicked back with
`KICK_RED`. The gate's output lines on stderr are tagged with the commit and the change
(`[4b1c0e9a2f31 #482]`), or with `base` for a commit gated as it stands. Each candidate
is a checkout of its own (a git worktree) with a scratch directory of its own; point
every cache there with `--scratch-env`.

A generated-file conflict takes the change's side and `--regenerate` rewrites it, with
the generated paths on stdin; without a hook, a file either side deleted stays deleted.
The regeneration's writes to outputs and to files `generate`'s targets update in place
are committed; a file magus maintains is restored to the candidate's version and left out. A
regeneration that fails, or writes anything nothing declares it writes, kicks that change
back and the run goes on.

## Auto-resolving source conflicts

A conflict in a source file goes back to its author unless two things hold: the merge
settles, and the change is low risk.

The merge is the file's three versions (main's, the change's and their merge base's).
Each side's edits against the merge base are hunks placed by the file's diff driver, the
concurrent-edit model a job's footprint and claims use, and where both sides changed the
same lines their hunks collide at a location, `path#declaration`. Each such region
settles in one of two ways, or not at all:

| Kind | Both sides changed the region by                                     | The queue keeps           |
| ---- | -------------------------------------------------------------------- | ------------------------- |
| 1    | the same change, or one side's lines containing the other's in order | the larger side           |
| 2    | only adding lines where the base had none                            | main's, then the change's |

Any other region, where both sides edited or deleted base lines differently, leaves the
whole file conflicted, as does a side that only deleted lines, a file main's history
does not share with the change, or a symlink. Lines keep their own endings, so a CRLF
file stays CRLF and a missing final newline stays missing.

Low risk is a class from the one change classifier magus has, the one
[gate sizing](ci/risk.md) tiers from, applied to the edit from the merge base to the
merge: generated, prose (`gate_low_risk`, markdown by default) or comment-only. A merge
reads the class alone, not the tier. Code settles only where its project opts it in with `merge_low_risk`,
project-relative globs beside `gate_low_risk`:

```buzz
magus\project({"merge_low_risk": ["testdata/golden/**"]});
```

Nothing is opted in by default. `--facts` answers the same question with an
`auto_resolve` query, given the path, the merge base's content and the merge; a command
that cannot answer it settles nothing. The same files settle the same way in a local
merge, through magus's [merge driver](../guides/integrations/git.md#auto-resolving-source-files).

A settled candidate is gated like any other; the gate's own format check is the only one
it gets, so a resolution that breaks formatting is a red kick-back. Planning, validation
and apply each settle the file themselves from the same three versions, and apply
merges only when its rebuild is the commit validation gated. The provider's own merge
would stop on the conflict, so apply hands it an update commit holding the settled file,
after checking that its own resolution against main's tip is exactly what the rebuild
holds; a change merging by rebase is kicked back instead. Each settled candidate writes
a `resolved` event, and the verdict's reason says the same on a merge, one entry per file:
the classifier's line and each region's location with its kind, as in
`CHANGELOG.md: prose (matches "**/*.md" (built-in default)); CHANGELOG.md### Unreleased: kind 2`.
A red kick-back's report adds that line, and a conflict's report or wait reason names why
each file stayed conflicted: the location that did not settle, or the classifier's line.

## What a review covers

Approval is checked at the commit a review of the head covers: the head itself, or,
walking back through merges of main into the change, the commit beneath each merge that
adds nothing a reviewer did not see. A merge adds nothing when its tree is the plain
merge of its parents, or, for a change stacked on one that has merged, their merge from
its stack base; while the change beneath is open, that second form would drop its
content, so it is not accepted. A merge that differs from the plain merge only in
generated files adds nothing only when main's regeneration, run by apply on the plain
merge, gives exactly the merge's tree, and only after the build tool proves the change
touches none of that regeneration's code; otherwise the change waits with
`WAIT_NOT_APPROVED` for an approval at its head.

The queue enforces the base's own review rule and adds none: where the base requires no
approval, it merges a change nobody approved, and `magus queue describe` says so. The
GitHub provider counts a review only from an account that can push to the repository,
and only at the commit it was given on; an approving `reviewDecision` alone approves
nothing, since GitHub can keep it from a review of an older commit.

## Verdicts: `mergequeue.verdict/v1`

`validate --verdicts <dir>` first writes the plan there as `plan.json`, then one
directory per decided change, named by its id, holding `verdict.json`. Each appears by
rename the moment its change is decided, so a reader never sees a partial one, and each
is checked when written as well as when read. `.done` beside them says the run finished,
and a full run writes it even when it stopped early. Validating a different plan into a
directory that already holds one is an error.

```json
{
  "schema": "mergequeue.verdict/v1",
  "base_commit": "9f2e...",
  "change": {"id": "483", "head": "c0de...", "base": "main", "method": "squash", "fork": false, "title": "feat: lexer"},
  "decision": "merge",
  "after": "482",
  "onto": "5e1a...",
  "candidate_commit": "77aa...",
  "method": "squash",
  "depth": 2,
  "duration_ms": 41230
}
```

`decision` is `merge`, `kick` (with a `report` for the author), `wait` (with a
`reason`), or `merged` for a change whose head is already on the base; every `kick` and
`wait` carries a `code`, and `paths` and `with` name the files at issue and the base
commits that touched them. `after` is the change validated beneath this one and `onto`
its candidate; `method` is the merge method it was validated under. `gate` and
`regenerate` are the hook lines validation ran, which planning's verdicts never carry. `apply` polls the
directory, and merges a change once its own verdict is green and `after` has merged. It
trusts a verdict only as far as the plan vouches for it: a head, an `after`, an `onto`
or a missing change beneath that the plan does not match merges nothing, and a verdict on
a change the plan did not admit is dropped. A kick-back never repeats a verdict's
`report` as its own words: apply writes the report from the code and the commits it
checked, and hands the verdict's `reason` on as a claim, shown only as text.

### Codes

| Code                    | Means                                                                                                                   |
| ----------------------- | ----------------------------------------------------------------------------------------------------------------------- |
| `WAIT_NOT_APPROVED`     | no approval at the commit a review of its head covers                                                                   |
| `WAIT_HEAD_MOVED`       | its head moved since it was listed or validated                                                                         |
| `WAIT_BEHIND`           | a change validated beneath it did not merge, or it was not validated                                                    |
| `WAIT_CONFLICT_AHEAD`   | it conflicts with a change ahead of it, which merges first                                                              |
| `WAIT_REVALIDATE`       | what it was validated on is no longer what it would merge onto                                                          |
| `WAIT_BRANCH_MOVED`     | its branch moved or was deleted before an update commit was pushed                                                      |
| `WAIT_PROVIDER_REFUSED` | the provider refused the merge                                                                                          |
| `WAIT_BELOW`            | the change it is stacked on has not merged                                                                              |
| `WAIT_BELOW_KICKED`     | the change it is stacked on was kicked back                                                                             |
| `WAIT_RESTACK`          | it is not built on the head of the change it says it is stacked on                                                      |
| `WAIT_RETARGET`         | it targets another branch than the queue's base                                                                         |
| `WAIT_METHOD_CHANGED`   | its merge method changed since validation                                                                               |
| `WAIT_WITHDRAWN`        | its merge intent was withdrawn since it was listed                                                                      |
| `WAIT_UNQUEUED_BELOW`   | it carries the commits of an open change nobody queued                                                                  |
| `WAIT_NO_COMMITTER`     | it needs an update commit, and nothing names who commits it                                                             |
| `WAIT_BASE_RED`         | the gate was red on its candidate and on what that was built onto                                                       |
| `WAIT_CHECKS`           | main's required checks are running on its head, or run again on main                                                    |
| `KICK_CONFLICT`         | a real conflict with the base in files that are not generated                                                           |
| `KICK_RED`              | the gate was red on its candidate, green on what it was built onto, or a required check was red on a head carrying main |
| `KICK_REFUSED`          | something the author has to fix that is neither                                                                         |
| `KICK_REGENERATION`     | its merge needs regeneration its own code runs, and validation left no bundle apply can check                           |

## Applying as each candidate goes green

Validation runs the changes' code with a read-only token; apply holds the write token
and runs none of it. In this repository they are two GitHub Actions workflows, and
verdicts pass between them one change at a time:

1. `queue.yaml` (read-only), run on main by a push or a dispatch, plans, then fans the
   plan out as a job matrix, one `validate --only <id>` job per change up to the depth of
   each partition. Each job uploads its verdict as an artifact the moment it finishes.
2. `queue-apply.yaml` starts when validation is requested (`workflow_run: requested`), from
   main's definition with the queue app's token, and downloads each verdict
   artifact as it appears, while validation is still running: `apply` with the run as its
   source merges each change whose predecessors have merged, and stops once the
   validation run completes. A first job waits only to see whether validation's plan job
   runs at all; on a run cancelled before it started it is skipped, and so is apply.
3. A pull request event (merge intent enabled, a queue label, a push, a review) runs the
   pull request's own copy of `queue.yaml`, so apply never follows it. That run's one job
   says whether the event carries merge intent, and `queue-apply.yaml`'s dispatch job,
   holding only an app token scoped to `actions: write`, answers it by dispatching
   `queue.yaml` on main, which validates the whole queue. A forged intent job starts one
   more run on main and nothing else.

The apply job runs in the `magus-queue` environment, which holds the app's key, so every
apply run is listed under the repository's Deployments as a
deployment to `magus-queue`. That list is the queue's run history, not a release.

Both jobs that need a token use the queue's own GitHub App's (see
[Setting it up on GitHub](#setting-it-up-on-github)), and neither runs without it: a run
the job's Actions token dispatches starts no `workflow_run`, and a merge it makes starts
no workflow, so on that token the queue would validate every change and merge none. Most
merges are made by GitHub's auto-merge on behalf of whoever enabled it; when GitHub has
not merged a change in time, the queue merges it itself, as the app. Either merge starts
main's CI, CD and the queue's next run, so nothing is dispatched. `apply` marks each
`merged` event GitHub made with `by_provider`.

Before each merge, apply re-reads the change's approval, merge intent, base and merge
method from the provider, rebuilds its candidate, and predicts the tree main will carry:
the rebuilt candidate's changes since what it was built onto, merged onto main. A change
whose intent was withdrawn, or that was pointed at another branch after planning, is
skipped; one stacked on a change that just merged, and still targeting that change's
branch, is retargeted at main, since the provider merges a change into its own base. A
changed merge method waits for the next run. A file that both the candidate and something
merged since it was built changed, such as a root index two disjoint partitions both
regenerate, is a combination nobody validated: the change waits and is validated again on
the next run. Right before asking for the merge, apply reads intent, base and head once
more. A kick-back is carried out only on the head it was decided for; a head pushed since
waits for a decision of its own.

Main may require checks besides the queue's own (on GitHub, the pull request's CI), and
the provider refuses a merge until they pass, so apply reads their state at the head
(`required_checks`) before it rebuilds anything. Running checks wait with `WAIT_CHECKS`.
Red checks on a head that already carries main's tip ran on what the change would merge
onto, and it is kicked back with `KICK_RED` naming them. Red checks on a head that does
not carry it may have run on an older main, broken since and fixed: apply pushes an
update commit merging main in, which runs them again, and the change waits with
`WAIT_CHECKS`. That head carries the tip, so a head is updated at most once per main
commit. A change the queue cannot push to (a fork's branch, a branch another change
shares, or one merged by rebase, which takes main only by rewriting its commits) is
kicked back saying so. The GitHub provider reads each check from the head's workflow
jobs and commit statuses, through the app's `actions` and `statuses` permissions. In
this repository, `queue-apply.yaml` also answers CI finishing on a same-repository pull
request: when the run's head is still the head of a pull request carrying merge intent,
it starts `queue.yaml` on main, so a change waiting on its checks is picked up the
moment they report.

The queue's status, `merge-queue`, is main's only required check. It reads `pending`
while a change waits and `success` only on the commit apply is about to see merged: right
before it goes green, apply reads main again and confirms it is still the tip the merge
was predicted onto, and a change whose main moved waits for the next run instead. Then the
provider merges it (on GitHub, auto-merge does, as soon as the required check passes), or,
if the provider does not merge it on its own in time, apply asks it to. No credential
bypasses the status. A success apply cannot follow through, because the provider refused
the merge or applying stopped, goes back to `pending` before apply returns, and every run
starts by setting back to `pending` any success an earlier run left on an open change.

The queue validates the merge result, not the branch, so GitHub's "Require branches to
be up to date before merging" stays off: it would force every head onto main's tip, which
the queue's candidates already account for, and the queue cannot push an update to a
fork's branch. What that leaves is a push to main from outside the queue (an admin's
bypass) between apply's read of main and the merge. The merge then lands on a main nobody
validated; apply's check after the merge finds main does not carry the predicted tree and
stops, and the next run plans from the new tip.

Why not have validation post a `merge-queue` status per candidate and trigger apply on
the status event? Posting a status needs `statuses: write` in the job that runs
pull-request code, and branch protection requires exactly that status, so a pull
request could mark itself green. Statuses posted with the Actions token do not start
workflows either. A `workflow_run: completed` trigger fires once per run, so apply
would wait for the slowest candidate. Artifacts are readable through the API as soon as
they are uploaded, which is what lets the write side follow the read side change by
change without either one holding the other's rights.

When the provider's own merge of a head would not give the rebuilt tree, apply pushes an
update commit onto the change's branch with a lease on the validated head, so a branch
that moved or was deleted is left alone, and a branch that refuses the push kicks that
change back without stopping the run. Every update commit is authored and committed by
the committer. The author named on the change's head is never copied onto it: that
field is whatever the change's author typed, the update commit holds the base and its
regeneration rather than their work, and the provider already credits the change to the
account that opened it. It may differ from the provider's merge only in generated
files main's regeneration wrote, or, for a change stacked on a squashed one, in exactly
what that change merged. Anything else is kicked back, and so is an update commit for a
branch another open change also merges from. After the merge, apply checks that
main carries the predicted tree in the shape the merge method gives (one new commit for a
squash, a merge commit whose second parent is what it handed over, a line of commits for
a rebase), and stops otherwise.

## Setting it up on GitHub

The queue writes only as its own GitHub App, for the reason
[above](#applying-as-each-candidate-goes-green): on the job's Actions token it would
validate changes and merge none. `queue-apply.yaml` fails both jobs that need a token
until the app is configured, naming the variable and the secret it needs.

`magus queue describe` reads how the repository is wired and prints the rest as `gh`
commands, each under a comment saying what it does. magus never runs them, and never
changes a setting itself. It reads over the network with your token, so pass one:

```sh
GITHUB_TOKEN=$(gh auth token) magus queue describe --provider github --base main --app <slug>
```

Without `--app` it stops with an error carrying the app's registration link and the
command to run next, since a setup without the app is not one the queue can run on.
`-o json` prints the same as the `setup` of a `mergequeue.capabilities/v1` document: the
status the queue posts and who its credential posts it as, every check the base requires
and the integration each is pinned to, the repository settings the queue needs, the app,
and the steps.

The app has two identifiers, both under About on its settings page
(`https://github.com/settings/apps/<slug>`, or
`https://github.com/organizations/<org>/settings/apps/<slug>` for an organization's app).
Neither is secret, and they do not swap: the client id (it starts with `Iv`) is what
`setup-magus` mints the token with, and the App ID (a number) is the only value a
ruleset's `integration_id` accepts. GitHub answers `GET /apps/<slug>` for a private app
with 404 to every token but the app's own installation's, the owner's `gh auth token`
included, so `describe` reads the App ID another way where GitHub offers one: on an
organization's repository, once the app is installed there, it finds the app among the
[organization's installations](https://docs.github.com/en/rest/orgs/orgs#list-app-installations-for-an-organization),
which only an owner's token may list. Where it cannot (a user's repository, or a token
that is not an owner's), it stops, naming the settings page, and prints the same command
with `--app <slug>:<id>`: give it the App ID after the slug. An id that is not a positive
integer without a leading zero, or that disagrees with the app GitHub shows, is an error,
and so is a slug GitHub has no `<slug>[bot]` user for, which names no app at all.

1. Commit `.github/workflows/queue.yaml` and `.github/workflows/queue-apply.yaml` (this
   repository's are the reference).
2. Run `describe` without `--app`, open the registration link it prints, and click
   "Create GitHub App". It is pre-filled: private, no webhook, and contents, pull
   requests, commit statuses, actions and workflows write.
3. Run `describe` again with `--app <slug>` (or `--app <slug>:<id>` when it asks), and
   run the commands it prints in order: allow auto-merge, install the app on this
   repository alone, create the `magus-queue` environment with its secrets released to
   the default branch only, set the `MAGUS_QUEUE_APP_CLIENT_ID` variable to the app's
   client id (when GitHub hides it, `gh` asks for it), generate a private key on the
   app's page, and store it as the environment's `MAGUS_QUEUE_APP_PRIVATE_KEY` secret.
   That last command deletes every key of the app it finds in `~/Downloads` even when
   storing fails, and with none there it stores nothing, so running it again is safe.
   On a phone, the first is Settings > General > Pull Requests > "Allow auto-merge", the
   client id goes into Settings > Secrets and variables > Actions > Variables, and the
   key into Settings > Environments > magus-queue > Add secret.
4. Apply the ruleset change it prints last, which requires `merge-queue` from the app's
   id with "Require branches to be up to date before merging" off: a ruleset of its own
   when nothing requires it yet, a `gh api` rewrite of that ruleset, or a link for any
   other. Your other rulesets stay as they are. GitHub refuses the pin with 422 "Invalid
   integration ids" until the app is installed, which step 3 did first. The pin is what
   makes the status unforgeable: anyone with write access can post a status from GitHub
   Actions, and only the app posts as the app.

Require `merge-queue` only once the queue is on the default branch. Before that, nothing
posts it, and every merge waits on it.

The next `queue-apply` run finds the variable and the secret. `setup-magus` mints a token
for this repository alone that expires when the job ends, and the queue merges, pushes,
commits and posts its status as the app's bot. The app's pushes start a pull request's
workflows like anyone's, so required checks that run on `pull_request` report on its
update commits, and it can merge a pull request that touches `.github/workflows`. The key
lives in the environment, and a pull request's run is evaluated against its merge ref, so
no pull request's workflow can read it.

`apply` refuses to start, with [MGS3019](../reference/codes/sandbox/MGS3019.md), when the
ruleset pins `merge-queue` to another integration than the app: GitHub would count none
of the statuses it posts. That happens when step 4 is skipped after the ruleset pinned
the context elsewhere, or when the app was replaced.

## Providers

A provider is a Buzz script run on an embedded gopherbuzz VM. It exports these
functions, each taking one record:

| Function          | Receives                                                                                           | Returns                                                                                       |
| ----------------- | -------------------------------------------------------------------------------------------------- | --------------------------------------------------------------------------------------------- |
| `describe`        | `{base, remote_url, status_context, app, setup_steps}`                                             | `{stack_merge, linear_stacks, methods, required_approvals, queue_label?, committer?, setup?}` |
| `list_changes`    | `{base, remote_url}`                                                                               | `{changes, merged, unqueued, closed?}`                                                        |
| `approval_at`     | the change plus `{commit}`                                                                         | `{approved, head, base, method, queued, shared_with, reason?, approved_commit?}`              |
| `list_green`      | `{base, remote_url, context}`                                                                      | `{changes: [{id, repo, head}]}`                                                               |
| `post_status`     | the change plus `{commit, context, state, description}`                                            | `true` when recorded                                                                          |
| `retarget`        | the change plus `{base}`                                                                           | `true` once the change targets `base`                                                         |
| `merge_change`    | the change plus `{commit, message, app, through}`                                                  | `{merged, by_provider?, reason?}`                                                             |
| `kick_back`       | the change plus `{commit, code, report, claim, paths, with, candidate_commit, source, reproduce?}` | `true` when both the comment and the removal happened                                         |
| `mark`            | the change plus `{mark}`: `queued`, `kicked_back`, `needs_regeneration`, or empty for none         | `true` once the change shows that mark and no other                                           |
| `list_artifacts`  | `{source}`                                                                                         | `{run, complete, artifacts: [{name, url}], headers?}`                                         |
| `required_checks` | the change plus `{commit}`                                                                         | `{checks: [{name, state}]}`, `state` one of `pending`, `success`, `failure`                   |

All but `list_artifacts` and `required_checks` are required, and a script missing one
is refused when it opens; `list_artifacts` is required of a provider `apply` follows
through a run, and without `required_checks` apply reads no required check. Every
returned key without a `?` is required: a missing one is an error, never a zero value,
since a missing `fork` or `queued` read as false would admit what the provider meant to
refuse. `stack_merge` is `sequential` or `atomic`, `methods` the merge methods the
repository allows, and a change with any other method is refused. `required_approvals`
is how many approvals the base requires, which `magus queue describe` prints, zero
included. `queue_label` is the
prefix of the label that queues a change, followed by its method, for a provider whose
merge intent is a label; `magus queue describe` prints it for tools such as the pull
request advisor. `committer` is `{name, email}`, the identity the provider's automation
pushes as, which commits every update commit unless `--committer` overrides it.
`setup` is asked for with a `status_context`: `{status_context, credential: {id, name?},
required_checks: [{context, integration?, events?}], settings: [{name, value, want}],
app?, steps: [{title, command? or url?}]}`. `credential` is the integration the write
credential posts statuses as (the `app` named; GitHub's provider requires one),
`required_checks` what the base requires and the integration each is pinned to, and
`steps` only when `setup_steps` is true, since they cost reads a job's token may not be
allowed. A provider that returns no `setup` skips apply's credential check. The `app`
that `describe` and `merge_change` receive is `--app` exactly as a person gave it, in
the provider's own notation, which the queue never reads (GitHub's: the app's slug,
with `:<App ID>` where GitHub hides the app). A `describe` that cannot describe a setup
for that app returns `{refused: {reason, url, app}}` instead of the capabilities: what
is missing, where the provider shows it, and the `--app` to ask again with,
placeholders included (`<slug>`, `q:<id>`). All three are required and non-empty.
`magus queue describe` prints it with the command that runs it again, that `app` in
place of the `--app` it was given, and `apply` stops on it.
`list_artifacts`' `run` is `{repo, head_repo, head_branch, event, branch_event,
definition}`: the repository the run belongs to and the one whose commit it ran, the
branch it ran on, what started it, whether that event runs the branch's own copy of the
definition (`branch_event`; on GitHub only `push` and `workflow_dispatch` do), and the
definition it ran. `approval_at` must
name the change's current head, base and merge method, whether it still carries merge
intent (`queued`), and the other open changes whose head branch is its branch
(`shared_with`); `approved_commit` names an older commit its approvals stand at, which
the queue carries over only across a rebase that changed nothing. `list_green` names
every open change, whatever it targets, whose head carries the status `context` at
success. `through` lists the changes beneath a stack's top that merge in the same call,
lowest first, each with the commit it must still be at. `app` is apply's `--app`, the
app the merge is made as. `merge_change` sets
`by_provider` when the provider merged the change on its own rather than on this call;
left out, it reads as the call's merge. `kick_back`'s `report` is Markdown in the
queue's own words, every file name in it a code span. `claim` is what the verdict said
went wrong, at most 4 KiB, and `paths` and `with` may come from a verdict too, whose
writer ran the change's code: a provider shows these as text only, never as markup.
`source` is the validation run apply followed, empty for a directory, and `reproduce`,
`{gate, regenerate}`, is there only when validation decided the kick and apply was given
`--reproduce-gate`: the hook lines that validate the change again.
`list_changes`' `unqueued` records carry `repo?` and `mark?`, the mark the change shows
now, and its `closed` records `{id, repo?}`. Apply marks `queued` every change the plan
admitted when it starts, clears that mark from an unqueued change still showing it,
marks `needs_regeneration` after a `KICK_REGENERATION` kick-back and `kicked_back` after
any other, and marks none after a merge and on every closed change. Marking none clears
the label that queued the change too, since only a change that left the queue is marked
none. A failed `mark` is a notice and applying goes on: the status and the comment are
the record.

Planning admits a change whatever generated files its merge leaves stale: validation
regenerates them in the candidate and gates the result. Apply kicks it back, with
`KICK_REGENERATION`, only when the build tool cannot prove main's regeneration runs none
of the change's code (`--facts generation`) and validation left no `candidate.bundle`
beside the verdict.

Scripts see Buzz's standard library and a `mergequeue` module whose
`request(method, url: .., body: .., headers: ..)` returns `{status, body}`; a response
over 32 MiB is an error, never a shorter answer. Its `codeSpan(text)` and
`codeBlock(text)` return Markdown showing `text` as it is: a code span, Go-quoted when
`text` holds a character that is not printable, and a fenced block whose fence is longer
than any run of backticks in `text`. The records a script receives hold
strings, bools, lists of strings, records and lists of records. `--provider github` is built in;
`--provider path/to/provider.buzz` loads any other. The GitHub provider reads
`GITHUB_TOKEN` or `MERGEQUEUE_TOKEN` for its reads and only `MERGEQUEUE_TOKEN` for its
writes, so the read-only job cannot write by accident. Its listings page to completion or
fail: a cut listing would read as fewer pull requests, fewer merged changes, or a stale
labeler.

Merge intent is GitHub's native auto-merge, or a `merge-queue: <method>` label applied by
someone who holds write access, on a pull request outside any stack or on a stack's top
pull request; only a method the provider knows, spelled exactly, is intent. Auto-merge
wins over the label on the same pull request. The provider never reads GitHub's
`mergeable`: GitHub will not enable auto-merge on a pull request it says conflicts, and
the label queues it anyway, since whether the conflict stops a merge is the queue's to
decide. The labeler is read from the pull request's timeline; a timeline too long to
read, or a labeler whose permission cannot be looked up, leaves that pull request or
stack unqueued and nothing else. Kicking a
change back posts a new comment, never an edit of an old one: the report, the claim in a
fence, for `KICK_REGENERATION` the label it now carries and that the base is to be
merged in and the files regenerated, a link to the validation run, collapsed blocks for
reproducing it (`gh run download` of the plan, then `magus queue validate --only` with
apply's reproduce lines) and for the files and commits (the first 50 of each, as code
spans), the `gh pr merge <n> --auto --<method>` that queues it again (for a stack, the
label on its top), and last a line holding an HTML comment with one JSON object of its
code and files, in which every `-`, `<`, `>`, `!`, `&` and `@` is a JSON escape so no
file name can end the comment early. It then removes the intent where it lives: its own
auto-merge, its own label, and the label on its stack's top. Last it minimizes as
outdated its own earlier kick-back comments on the pull request, a comment its
credential wrote whose last line is that marker; a failure there is printed to the apply
job's log and does not fail the kick-back. `mark` shows the state as one label at most,
created with a description the first time a repository needs it: `merge-queue: queued`,
`merge-queue: kicked back` or `merge-queue: needs regeneration`, removing the other two;
none removes every one and the `merge-queue: <method>` label. `list_changes` finds the
closed pull requests still showing any of these labels in one search (`is:pr is:closed`
with every label as alternatives), paged to its end. A label GitHub refuses to create for
any reason but that the repository already has it is an error naming GitHub's reason.
Its `describe` reports the label prefix `"merge-queue: "` and, with a setup, the
committer `<slug>[bot] <<id>+<slug>[bot]@users.noreply.github.com>`, the app's bot, read
from GitHub; `queue-apply.yaml` passes the same as `--committer`. Its setup refuses to go on
without `--app`, printing the app's registration link instead, and reads the base's
rulesets and classic branch protection, the app, and for the steps the checks and
workflow runs on the
head of the most recently updated pull request from the repository, which is how it
tells which required checks run on `pull_request`. A read refused with 403 or 404 names
the permission it needs.

On GitHub, `merge_change` for a pull request with auto-merge on waits up to a minute for
GitHub to merge it once the queue's status went green, then merges it itself through the
API, pinned to the head, as the app. A merge GitHub made in the meantime reads as
GitHub's unless the app's bot made it. A stack, queued by label, has no auto-merge, so the queue always
merges it itself. No merge needs a bypass actor. Its `describe` narrows `methods` to what
the repository settings and every active ruleset rule targeting the base branch both
allow, dropping `merge` when one of those rules requires a linear history, and errors
when nothing is left in common.

## The packages

The queue's packages are internal to magus: the command line and its documents are the
interface, and no Go API outside the module is promised. Its contract lives in
`internal/queue/types`, a near-leaf package importing only the
standard library and magus's `types`: the documents (`Changes`, `Plan`, `Verdict`), the
codes, `Provider`, `ArtifactLister`, `Gate`, `BuildFacts`, `VerdictSource`, and the
version control each step gets. Its generated testify mocks are in
`internal/queue/types/gen/mocks`; magus's `types/gen/mocks.MockVCSDriver` stands in for
the version control. The root package, `queue`, holds the three steps (`Planner`,
`Validator`, `Applier`, each built with its required dependencies by its constructor and
run with `Run`), the pure decisions they share (stack detection, partitioning, approval
carry-over), the document codecs, the verdict directory, the artifact follower and the
command hooks.

| Interface        | What it answers                                                         | magus's implementation      |
| ---------------- | ----------------------------------------------------------------------- | --------------------------- |
| `ReadVCS`        | revisions, trees, ranges, ancestry, tree merges; fetching (planning)    | magus's `types.VCSDriver`   |
| `BuildVCS`       | `ReadVCS` plus checkouts, merges in them and local commits (validation) | magus's `types.VCSDriver`   |
| `PushVCS`        | `BuildVCS` plus a leased push (applying)                                | magus's `types.VCSDriver`   |
| `BuildFacts`     | affected sets, all units, how paths are written, what regenerating runs | `client.Workspace`          |
| `Provider`       | list, describe, approve, set statuses, retarget, merge, kick back, mark | the `provider` Buzz scripts |
| `ArtifactLister` | the artifacts a validation run uploaded                                 | the `provider` Buzz scripts |

Every merge, check and push is composed in the queue from the capabilities' facts, so
which merge base a prediction takes, which conflicts are the author's and which
differences a review need not see are decided once, whatever the version control.
`CommandFacts` is the `BuildFacts` behind `--facts`, which gets the fact it is asked for
as its one argument. Asked for `all`, it prints `{"units": [unit]}`, how the build tool
names every unit. Asked for `outputs`, with the paths on stdin, the command prints `{"outputs": [path], "updated": [path], "maintained":
[path]}`: the paths a target writes whole, the ones a target rewrites in place, and the
ones the build tool rewrites itself on every run. A missing key names none, so a command
that prints only `outputs` declares no update and maintains nothing.

Where Go ends and Buzz begins is a rule, not a taste. Go holds what the invariants are
proven over and what needs the machine: admission, partitioning, candidate order, the
merge checks, version control, processes, files and concurrency. Buzz holds what talks
to a system outside the repository, the provider and the CI system, as a pure function of
that system's answers and the record it was handed: it supplies facts and performs
writes, and decides nothing. A fact the queue acts on is re-checked in Go before it is
trusted: a change record passes `Change.Check`, an approval must name a head, a base and
a merge method, a declared stack parent must match ancestry, a stale head is unproven. A
knob is a fact, not a script: what the schedule computes over comes from the build tool
and the provider; how it computes is fixed in Go.