merge-queue #

mq is a merge queue for Git that runs on your own machines and moves main only to a commit whose tree passed your checks.

Each change lands by its branch name. mq land fix replays the branch on its target, runs the target's checks on the replayed tree and fast-forwards the target when they pass. When several changes wait, the queue checks them as one batch, and a red batch is bisected until the change that broke it is named. The rules, the check results and every move of a branch are kept in Git, so git reads what mq reads. Several machines share their results through a Git remote, and several repositories land through their own queues, dependencies first.

mq is in development, before its first release. Its manual, indexed in doc/README.md, specifies the product as it should be. The Gaps section of the design page lists what the binary does not do yet.

Security #

Landing a change runs its code. A check is a command from the rules, run on the change's tree with your rights, as Git runs a hook. On a machine whose scheduler runs the queue, the checks also run outside the sandbox of whoever queued the change. Whoever can write to a remote you pull from can forge a check result, which a land here then reuses.

On macOS, git config mq.confine auto runs each check under Seatbelt, with only the reads, writes and network access its rules grant. No check is confined on Linux yet, and the rules' hook is never confined. doc/trust.md says what mq trusts and where Git's own mechanisms bound that trust.

Background #

CI tests a pull request at its head, and the merge then makes a tree that nobody tested. A merge queue checks the tree that main will hold before main moves. GitHub's merge queue, GitLab's merge trains, bors and Zuul do this on a server, for pull requests, and report on a review page.

mq is that queue on the machine where the work is done. A land needs no server, no forge and no network, and mq land waits and prints the outcome itself, as Phabricator's arc land does. The rules sit on a branch of their own, as in Zuul's config projects and Gerrit's refs/meta/config, so a change cannot edit the rules that judge it.

mq knows nothing of pull requests. A team that reviews on a forge keeps doing so, and its CI calls mq land --dry-run. doc/related-work.md compares mq with each of these tools and cites the pages its claims come from.

Install #

mq installs from opam and needs OCaml 5.2 or later. Its packages are in an opam overlay, which builds them from the main branch of this repository:

$ opam repo add samoht https://tangled.org/gazagnaire.org/opam-overlay.git
$ opam install merge-queue-eio

That installs one executable, mq. No Homebrew bottle is published yet. A queue that serves the repository building mq installs it from its own checked branch, as doc/install.md says.

Usage #

Quick start #

This repository has a pre-commit hook that runs ./test.sh, which fails when ttl.py stops stripping its input. mq init finds the hook and makes it the check of main:

$ mq init
created mq/config: DAG main, check pre-commit
$ W=$(mq new fix-ttl)
$ $EDITOR "$W/ttl.py"
$ git -C "$W" commit -qam "ttl: read hexadecimal"
$ mq land fix-ttl
landed fix-ttl into main: 1 commit, checks pre-commit (0s wall, 0s of runs)
  time: 0s: 0s queued, 0s replaying, 0s checking, 0s moving

mq new creates the branch and prints the path of a fresh worktree for it. mq land checked the replayed tree, moved main and removed the worktree.

A second branch deletes the strip() call, and its author commits with git commit --no-verify, which skips the hook. The queue still checks it:

$ D=$(mq new drop-trim)
$ $EDITOR "$D/ttl.py"
$ git -C "$D" commit --no-verify -qam "ttl: drop the strip"
$ mq land drop-trim                  # exit 1
needs_work drop-trim: check pre-commit failed with exit code 1, last line "ttl: " 30" is no TTL"
  log: /home/alice/app/.git/mq/logs/check-a4119a63c184622bddc926be084f052af8841225-pre-commit-2.log
  worktree: /home/alice/app.worktrees/drop-trim.2
  next: mq land drop-trim

main has not moved. The check failed, so it ran a second time to rule out a flaky test, which is the -2 in the log's name. A new commit on the branch and the same mq land try again, and mq drop drop-trim throws the branch away. doc/sessions.md walks through longer sessions, from a second target to a release.

What to know #

The queue and its checks. A target is a branch the rules name, and the rules list the checks a change must pass to land in it. A check is any command, and mq knows no build system. It runs on the tree the target will hold after the move, never on the branch's own tip. Its result is stored against that tree, so a tree that passed is not checked again. doc/rules.md gives the definitions, and doc/outcomes.md the outcome words and their exit codes.

Lands by name. A change is a Git branch, and its name is the only name you type. mq land NAME waits for the outcome, and mq land NAME --no-wait queues the branch and returns at once. The operating system's scheduler then runs the queue after you leave, once mq schedule start has registered it with launchd, systemd or cron. A busy queue moves fastest with small branches, each queued with --no-wait as soon as it is ready. doc/delivery.md gives that path as commands, with what each check costs, and doc/runs.md says who runs the checks.

The rules branch, mq/config. The rules are one file, mq.toml, on a branch of their own called mq/config. A rule changes by a land into that branch, checked like any other change. The rules also say how branches feed each other, for example new work landing in staging and mq land staging --onto main carrying it on to main. doc/configuration.md lists every key.

Batches, bisection and the Fix line. When more changes wait for a target than the machine can check one at a time, the queue replays them onto each other and checks the last tree once. A batch that passes lands every change in one move. A red batch is bisected: the changes before the culprit land, and the culprit ends needs_work. A later commit that repairs a landed change names it on a line Fix <full commit SHA>, and mq stats reads those lines for the change fail rate. doc/delivery.md gives the cost of a red batch.

Daily commands #

Command	What it does
`mq new NAME [BASE]`	creates the branch NAME at the tip of BASE and prints the path of a fresh worktree for it
`mq land [NAME]`	checks NAME replayed on its target and fast-forwards the target when the checks pass; `--no-wait` queues it and returns
`mq status [NAME]`	each branch with something to land, with its state, its failed check, its log and the next command
`mq drop NAME`	withdraws NAME, hands its worktree back and deletes the branch, printing the command that restores it
`mq events [NAME]`	the queue's history on this machine, oldest first; `--checks` adds each check run with its log
`mq stats`	the last day's delivery: a row per queue with its changes, the median and 95th percentile from queued to landed, the share refused and what it waited on; `--all` puts every queue of this machine in one table

A land prints its outcome on standard output, and the outcome's first word sets the exit code. --json prints the same outcome as JSON. mq --help --all lists the other commands, and doc/commands.md specifies each one.

Stacks #

A branch can be based on a lane: a branch that mq new handed out and that has not landed yet. Here the rules land work into staging, a adds a maximum to the TTL, and b, based on a, adds a minimum. b is queued alone, with mq schedule start registered so that the scheduler's runs land what is queued:

$ A=$(mq new a staging)
$ echo "let max = 86400" >> "$A/lib/ttl.ml"
$ git -C "$A" commit -qam "ttl: a maximum"
$ B=$(mq new b a)
$ echo "let min = 1" >> "$B/lib/ttl.ml"
$ git -C "$B" commit -qam "ttl: a minimum"
$ mq land b --no-wait
queued b: position 1 of 1 for staging, no run yet
  next: mq land b

b is queued for staging, the branch a lands into, and never for a: a land never moves another lane's branch. A stack lands from the bottom, and while a is not queued nothing will land it, so the next run ends b needing work, naming a and the ways on:

$ mq status b
b  needs_work  staging  its base a is not queued: land a, or land b alone with mq land b --onto staging
  ended: 10:12:04, 9s ago
  worktree: /home/alice/app.worktrees/b.2

A branch made with Git on top of a lane carries no base, and its land is refused, naming the lane it contains. mq field NAME base=BASE records the base as mq new would have. The same command moves a base to another lane. Here c is made with Git on top of b:

$ git worktree add -q -b c ../c b
$ echo "let zero = 0" >> ../c/lib/ttl.ml
$ git -C ../c commit -qam "ttl: a zero"
$ mq land c --no-wait                 # exit 2
refused c: c contains b, which has not landed, and no upstream says c is based on it
  next: mq field c base=b
$ mq field c base=b
set c: base=b

Queued from the bottom, a, then b, then c, each lands in the run that lands the one below it, b after a and c after b. Each lands its own commits alone, the commits since its base: b's one commit, never a's again under b's name.

$ mq land a --no-wait
queued a: position 1 of 1 for staging, last run 17s ago
  next: mq land a
$ mq land b --no-wait
queued b: position 2 of 2 for staging, behind a, last run 17s ago
  next: mq land b
$ mq land c --no-wait
queued c: position 3 of 3 for staging, behind b, last run 17s ago
  next: mq land c

After that run, staging holds the commits of a, b and c, in order:

$ git log --format=%s staging
ttl: a zero
ttl: a minimum
ttl: a maximum
ttl: read a TTL

This section is the transcript of test/cram/readme-stack.t, which fails when the two differ. doc/branches.md specifies how the target and the own commits of a stacked branch are found.

Several machines and repositories #

mq land never touches the network. mq push and mq pull exchange the branches, the rules and the check results with a plain Git remote, so a tree one machine checked is not checked again on another (doc/machines.md). mq sync is the one then the other, and a [sync] section in the rules has the scheduled run start it as each landing lands (doc/configuration.md).

A repository names the ones it builds with in a lock file, .mqmodule. A change across several is one item of one dependency graph that every repository's queue reads, and each target moves by its own compare-and-swap once every part's tree passed, so the parts do not land atomically (doc/commands.md, doc/design.md). The code still schedules each repository apart, the dependency first (doc/design.md).

API #

The library merge-queue holds the decisions as state machines that read no clock, file or process, as lib/rules.mli and lib/outcome.mli show. The library merge-queue-eio, in lib/eio/, runs them against Git and processes and builds mq. Neither interface is stable before the first release.

Contributing #

Run the quick start in a scratch directory, and open an issue at https://tangled.org/gazagnaire.org/ocaml-merge-queue/issues if anything breaks or surprises you.