ocaml-merge-queue
A local Git merge queue with content-bound gate verdicts
Star
Fork
Watch
ocaml-merge-queue doc branches.md
21 kB · 318 lines
Markdown
at main

Branches and worktrees #

After a land: the branch and the worktree #

A landed branch has done its job, and what happens next depends on what it is.

  • A branch the rules name is left alone. mq land staging --onto main moves main and never moves, rewrites or deletes staging.
  • A work branch whose worktree mq handed out is tidied away. Any branch based on it takes its target as upstream, the branch is deleted, and its pool worktree is removed: its path names nothing, and its directory is parked for the next hand-out or check (below). arc land deletes the local branch in the same way, and a forge can delete the branch of a merged request. --keep-branch keeps both, the branch moved to the commit it landed as and the worktree brought along, for a follow-up that starts there.
  • A land completes its branch when the branch holds no commit the land did not take and the land kept it for no follow-up. The landing's settlement says so in the complete member of its settled record (Outcomes), as a forge closes the issue a merged request fixes: a tracker hook closes the issue a branch names on that land alone. A land with newer commits not queued, or under --keep-branch, is one step of the branch's work, so a branch that lands its docs before its code lands them with --keep-branch.
  • A branch with no mq worktree is moved, not deleted. It ends level with its target, with that target as its upstream if it had none, for git branch -d to delete. If a checkout has it out, the checkout comes along as rule 2 says, uncommitted changes included. When a change there would be overwritten, the branch stays on its old commits, and the outcome says so and prints no next:. Once that change is committed or stashed, git rebase staging finds nothing left to apply.

The commits NAME held before the replay stay reachable in refs/mq/keep's reflog for as long as Git keeps its lines, thirty days by default, as a dropped tip does (The state). Without that line they would be reachable from nothing once the branch, its reflog and its worktree are gone, which matters most when a resolver wrote the landing.

All of this is conditional on what was queued. NAME is moved or deleted only while it still stands at the queued tip, and a pool worktree is removed only while it is clean and holds no untracked file but the build directory, as git worktree remove removes it: an ignored path is no untracked one. An untracked file keeps the worktree, and the outcome names it as git status does (scratch/notes is untracked, so /pool/fix-ttl.3 is kept). Whoever committed again during the wait keeps the branch and the worktree, and the outcome says 1 newer commit not queued, with next: mq land NAME.

The branch is deleted at the local landing, whether or not the repository has a remote. A landing that a later mq pull takes back returns under its own name (Several machines).

A landing is undone by landing its revert, which is git revert on a new branch and then mq land. No mq command undoes a landing. staging@{1} names the tip before the last landing, for whoever wants to read it.

Rule 6 sets what removal means. A worktree lives at <pool>/NAME.N, where N is a serial the pool never reuses, so a path kept in a variable after a land names nothing, even when someone starts a new fix-ttl the next day. The line of refs/mq/keep's reflog that keeps a landed or dropped branch's work ends with its hand-out, (worktree NAME.N), so the pool hands that path out to no later work while Git keeps the line.

The directory behind the path is not thrown away. A full checkout of a large tree costs seconds and a cold build minutes, so removal parks the worktree whole in the pool, its HEAD detached and its build directory in place, and the next hand-out or the next land's checks take it: they switch its files to the commit they need, which rewrites only the paths that differ, as git checkout does, and keep its build. A parked worktree holds nothing but its commit's files and its build directory, which Git ignores; one that holds anything else is not mq's to clean, so nobody takes it and it stays.

A working directory is an inode, and a move keeps the inode. A process standing in <pool>/fix-ttl.3/sub would follow the worktree into its next use, and its next git commit would land on the branch the directory was handed to next. So a worktree a process stands in is not parked: removal takes it off Git's list and moves it under the pool's .reap/, where each of the process's Git commands fails, and the reap deletes it. A park waits for the pool's lock another process holds, rather than throwing the warm build away. Either way the journal says what became of the worktree: parked, or set-aside with what refused the park (mq events). Nothing else of it stands under the pool: the directory a slashed name nests its worktree in (<pool>/agent-3/ for agent-3/issue-123) goes once the worktree has left it empty, and so does the one under .idle/ a hand-out takes the parked worktree out of.

The pool is bounded by disk and by nothing else. A worktree in use is never evicted. The parked worktrees are the cache: mq keeps as many as the machine's budget allows and evicts the least recently used. A hand-out ends unavailable only when the volume is under the machine's free-space floor with every parked worktree evicted; the block names the measured free space and the floor. The bound is on disk because a warm tree is large. In one checkout of four repositories it takes 7,695 MiB, so eighteen worktrees at once hold 135 GiB.

A branch based on another branch #

A land's target is never another lane. A lane is a local branch the rules do not name and mq keeps a record of, refs/mq/meta/NAME, which mq new, mq field and a land write. mq new b a makes a the base of b, and mq land b lands b into the branch a lands into: a's own target, read down a's bases to the first branch that is no lane, or the entry branch when none of them is one. A base the rules name is landed into, or, when it takes its commits from another, that other branch is: a branch based on main lands into staging. mq keeps a record of a branch it made, its description, and of a branch it holds queued, its pin: either is a lane. A base mq keeps no record of, such as a branch made with git branch and not queued, is landed into as it stands. A land into another lane's branch would rewrite work its owner did not ask for, so only --onto names a target as typed. A shared feature branch the rules name works as a small staging: several people land into feature-x, each land checked, and mq land feature-x later lands the whole into staging.

A land takes a branch's own commits and no others. They are the commits since its base, whatever the target, as git rebase --onto takes the commits since the upstream. A branch with neither an upstream nor a recorded base, such as one fetched from a peer, has its merge base with the target as its base. A hotfix pushed to staging therefore never rides into release/1.2 under an unrelated branch's name. Two kinds are skipped. The first are commits whose landing still stands on the target: the record of a landing names the commits it consumed. A landing a pull took back no longer stands, so its branch can land the same commits again. The second are commits whose patch the target already holds, as git rebase skips them, or a copy: a commit with the same author line, author date and subject and the same paths changed, whatever lines it changes, as a replay among other commits or a conflict resolved by hand leaves it, or only some of those paths when both commits' trees hold the others alike, as git cherry-pick leaves out a path its target already holds. The count starts past the oldest of these: the commits since the base that the target holds, from the oldest on, each the one parent of the next, are none of the branch's, so its own commits are counted from the newest of them, and the check for a conflict with the target merges only the changes since there. The commits b inherited from a are therefore never landed under b's name, nor met as a conflict with their landed copies, whether a is still there or has landed and been replayed and its lines rewritten since.

A stack is checked at once and lands as one. While a is queued, b is ordered right after it, whatever their queue times and whichever of them is expedited: an expedited b queued before a was queued again still ranks after a, so mq status gives b the position after a's, and the lanes of a stack hold consecutive places, bottom first. Each lane of the stack is a car of the target's train: a's candidate is its own commits replayed onto the target's tip, b's is its own commits replayed onto a's candidate, and every one of their trees is checked in the same step, sharing the build slots as any prediction does, so no slot is idle while a lane of the stack waits (runs.md). The stack lands in one fast-forward of its target, to the highest lane whose tree passed with the tree of every lane below it passed; b therefore never lands before a, since it lands in the move that lands a. A lane whose tree is red ends needs_work, naming its own red, and the lanes above it end needs_work naming it, while the lanes below it land: a commit of b that does not build on a is a defect of b, and never holds a slot or the queue. This is Graphite's stack-aware queue, whose failure evicts the stack above it, and Aviator's parallel mode, which checks each entry on the entries ahead (related-work.md). While a is not queued (never queued, or ended needs_work, removed or dequeued) and the target lacks its commit, nothing will land it, so b ends needs_work, naming a and the ways on (its base a is not queued: land a, or land b alone with mq land b --onto staging). A move the queue made that landed a puts a's commits on the target from that move on, so b rides on the moved tip and never ends for its base before the reading of the moved target tells it. Whether the target holds a's commit is a function of that commit, the target's tip and the commit of the origin notes, which the index keeps (refs.md, "What the index holds"): a reading of the queue asks Git again only once one of them moved, and a run that starts after an install reads what the run before it found. Once the target moved, the reading diffs only the commits new on it: the paths and the patch id of each commit it compared before are kept by their commit. A land of b on a machine with no scheduler has no run to wait for: it ends unavailable with that reason and leaves nothing queued. Two lanes based on a both ride after a, each with its own commits alone, and land in the move that lands a once their trees passed. mq land a lands a into staging, and before a is deleted every branch based on it takes staging as its upstream; a branch whose base a stays, kept with --keep-branch, lands into staging the same way. Each name is typed by whoever gives its ready signal: a land never lands a branch nobody named, so --onto staging lands b's own commits without a's, as git rebase --onto would. It still waits for a while a is queued into staging, the target it names, and is ordered and checked after a as any stacked land is: its own commits are judged on a's candidate, never on a staging that lacks a. While a is not queued into it, --onto waits for nothing and lands b alone. A branch made with Git on top of another, with no upstream to say so, is refused for that reason, naming the branch it contains, with mq field NAME base=OTHER as next:, which records the base. A branch the rules name is no one's unlanded work: a branch with no upstream whose own commits hold the tip of one is based on the newest such branch, as git rebase takes the upstream for the base, and lands into the branch that one takes its commits from, if any. mq drop a is refused while b is based on a, and names b.

A branch the rules name lands differently in one respect. It is never replayed, but along an edge that a commit made with Git has forked (rule 4). mq land main --onto release/1.2 is a fast-forward of the series to main, or is refused, counting the commits the series holds and main lacks and naming the oldest, with next: git log --oneline main..release/1.2, which lists them all. A series that has taken backports of its own takes later fixes as backports too. When such a land ends needs_work, the fix lands into the named branch as any change does, and its next: is a repair branch made at that branch's tip: mq new repair/staging staging. A commit made with Git on the target is normal operation, and the serve absorbs it: the target's commits the source holds, as a copy by patch or one resolved against the source's own changes, are held, and the rest is replayed. Only a true conflict, two different edits of one region neither side has resolved, or a red, ends needs_work along such an edge. The outcome names the side to repair, and that side is repaired through mq like any change, never by a hand edit: when it is the target, the next: is its repair branch, mq new repair/main main.

Waiting for a branch further along the DAG #

mq land NAME --wait-for main lands into NAME's target (staging) as usual, then waits until this machine's main contains the change. This answers "has it passed the longer checks" without a second command, for a caller that closes an issue or reports only once the change is on main. B is a branch of the DAG further along than the target, which the edges up to it carry the change to as each source moves. A remote-tracking copy of one (origin/main) is refused, as is a branch no edge leads to.

It needs the scheduler: the scheduled run lands NAME into staging and serves the edge staging -> main, and the call follows the journal and the tip of main meanwhile, with no run of its own. It ends with the outcome of the branch the change reached last:

  • landed, the landing's own block with ; main holds it after its detail, once main holds the commit NAME landed as, whoever moved it;
  • needs_work, or removed_from_queue where the edge reached a bound, with landed true in the JSON, once the run journals that the edge took nothing of the change. The detail says the change landed into staging, names the edge and says the edge is red and held until its source moves, with the edge's own reason, log and next:. A serve of the edge that ended unavailable is tried again by the next run, and the wait goes on;
  • removed_from_queue, with landed true, when bounds.wait_wall passed from the landing with main still lacking the change.

A call that reads NAME's landing back from its record waits for that landing's commit the same way. mq land NAME typed again after the scheduled run landed it is one.

mq land NAME --onto main is refused while main takes staging: it would put on main a commit staging lacks, and the edge could never be a fast-forward again (rule 1). The refusal's next: is mq land NAME --onto staging, which runs on every machine. A caller adds --wait-for main where a scheduler's runs carry staging there.

The wait is bounded by bounds.wait_wall, counted from the landing, since staging lands into main once the serve of the edge staging -> main that the landing starts ends, or the one after it when a serve was under way.

A land of staging into main whose checks are a confirmed red bisects the red range. Its suspects are the landings of the commits staging holds and main does not, down staging's first parents, oldest first: only a landing's tip was checked when it landed, so a probe never ends inside a landing, and a commit that adds a red test before its fix is never named. A commit a landing landed as is that landing, found by its landing record, the note on the landed commit, or by the line its move left in staging's reflog; a move that landed a batch cuts each land of it; where an adoption rebased staging, the copy of that commit (same author line, author date, subject and paths, or some of the paths with the others held alike) stands for it. The commits a landing landed before its own are no suspect of their own, and each commit no landing took, one replayed by hand, is its own suspect. The search (Search) is over the prefixes of that range, the whole range known to fail, on the build slots the run leaves free, as a batch's is: each round cuts the suspects left into as many parts as settle them soonest on those slots and probes the end of every part but the last at once (Hwang's generalised binary splitting), and each verdict narrows the range, stops the probes it made useless and starts the next on the slot it freed. Each probe runs main's checks on the tree of the commit staging took for a prefix's last suspect, and a result stored for that tree is reused unless mq forget set it aside. A flake (red, then green on its rerun) passes. A prefix fails only on a check red on the whole range, and those checks come first, so a red stored for one of them decides the probe; a prefix red only on checks the range passes holds a red a later suspect repaired, and its probe cannot settle. On one free slot a range of N suspects takes at most ceil(log2 N) probes, one at a time: 3 for 8, 7 for 128; on six, a round probes six prefixes at once, and 128 suspects take three rounds. Each probe is journalled as it starts and as it ends (probe-started, probe), with its prefix, the commit and tree it checks, then its result and seconds; mq events prints both, the land's progress says them, and mq status names the probes under way on main's row, then lists each probe of the last serve in the view of main; a probe a verdict made useless ends with no result. main then fast-forwards to the longest prefix that passed short of the first culprit, a commit of staging, and a culprit event for each culprit, journalled after that landing, names it, its commit and subject, the check red on its prefix with its log, and the commit main took: the first failing suspect, then each one the rest of the range holds without the culprits before it, all named by the one serve (Runs, "A check left to the edge"). mq status shows it on main's row until a later landing into main (The commands). When every prefix fails, main's own tip is probed before the first suspect is named, and a tip that fails as the range does names no suspect. That probe's checks run on main's tree with MQ_SCOPE_TIP naming the range's head, so a check scoped by its change builds the range's paths there, never the empty change of a tree with itself (Configuration). A probe whose check fails only as main's own tip does, that tip built on the scopes the prefix puts in play (exit 79, inherited), ends the search: the red is main's under today's environment, no suspect is named, and the outcome names the check, its first failure and that probe's log, with the repair of main as its next command. When a probe cannot settle (stuck, unavailable, or red only on other checks), main takes nothing and the outcome says which prefix. The land ends needs_work either way. The suspects after the culprit stay on staging, which main can only fast-forward along: once main took a prefix the edge is no longer held, and its next serve takes them with the repairs that land into staging after the culprits. A serve of the same tip ends needs_work at once on its stored red; one whose tip is a new red tree bisects the suspects main still lacks, and the trees an earlier search probed answer from their stored results.

A caller killed during the wait runs the same command again. The name still answers after the landing (The commands), so the second call waits for main from where the first one stopped.