Commit Graph: Log Order, Merge Bases, Merges and Rebase at Scale

Commit Graph: History Engine for the Review Service

You've joined the team that owns commitgraph, the small library behind our code-review service. It models a git-like repository: commits form a graph, branches are movable names, tags are fixed names, and each commit carries a tiny key/value "tree" instead of file contents. The review UI asks it three things all day: *which commits are in this review* (log), *what is the diff base* (merge_base) and *how far apart are these two branches* (ahead_behind). Last week those answers started looking wrong for a few teams, and the roadmap has merges, cherry-pick, rebase and a very large monorepo behind it. The Parts below take you through the incident and then the roadmap.

Codebase

refs.py, names.py, model.py, errors.py and workload.py are known-good; do not change workload.py (recorded load tests depend on its exact behaviour).

How your code is run

run(operations: list[list]) -> list executes the operations in order against a fresh repository and returns one result per operation. Each operation is [name, *args].

A fresh repository contains one commit, the root c1 (author time 0, message "init", empty tree), the branch main pointing at it, and HEAD attached to main.

Conventions

• Commit ids are c2, c3, ... in creation order (Commit.seq is the number). *Any* operation that creates a commit (commit, a merge commit, cherry_pick, revert, each commit a rebase writes) takes the next number. A failed operation never uses up a number, and neither does an operation that creates nothing (up_to_date, ff:). Whenever "later/newer commit" is needed for a tie-break it means the higher seq, compared as a number: "c10" sorts before "c9" as text.
• Author time at is an integer you pass to the operations that create commits. It is *not* guaranteed to increase: author clocks are skewed, so a child may carry an earlier at than its parent, and merges are often dated before the commits they merge.
• Trees and change sets. A tree is a dict of string keys to string values. A change set maps keys to a new value, or to null for "delete this key". A commit's tree is its parent's tree with the change set applied.
• Revisions (rev) are HEAD, a branch name, a tag name or a commit id, optionally followed by ~N (N = 0, 1, 2, ...; go to the first parent N times). Branch and tag names share one namespace, and a name may not look like a commit id (c12), equal HEAD, contain .. or ~, or fall outside [A-Za-z0-9._/-] (first character alphanumeric, no trailing /).
• Failures are returned, not raised, as a dict {"err": "<code>", ...}. No successful result is a dict. When an operation can fail several ways, the codes are checked in the order listed in the table. Every failed operation leaves the repository exactly as it was.
• HEAD is attached to a branch (a new commit advances that branch) or detached on a commit (a new commit advances HEAD only). checkout of a branch name attaches; any other revision detaches.

• at must be an integer (true/false do not count), message a non-empty string, changes a dict whose keys are strings and values are strings or null; otherwise bad_args. A wrong number of arguments, an operation that is not a non-empty list starting with a string, gives bad_args; an unknown operation name gives unknown_op.
• log takes rev = a revision, or "A..B" for "reachable from B but not from A"; null/omitted means HEAD. limit is null/omitted or an integer >= 1, else bad_args. Revisions on either side of .. resolve left to right.
• A new merge commit has parents [HEAD commit, target commit] (in that order), author time at, and message "Merge <rev> into <branch>" (the rev text exactly as given; the branch is the attached branch, or the word HEAD when detached). Until Part 2 its tree is whatever trees.merge_trees returns.
• merge rules, in this order, with T = the target and H = the HEAD commit: if T is H or an ancestor of H, nothing to do: "up_to_date". Else if H is an ancestor of T, fast-forward: HEAD (and its branch) moves to T, result "ff:<T>". Else create a merge commit, result "merge:<id>".

Worked example

[["commit", 10, "add readme", {"README": "v1"}],
 ["branch", "topic"],
 ["commit", 20, "add parser", {"parser.py": "v1"}],
 ["checkout", "topic"],
 ["commit", 30, "fix typo", {"README": "v1b"}],
 ["log"],
 ["log", "main..topic"],
 ["ahead_behind", "main", "topic"],
 ["checkout", "main"],
 ["merge", 40, "topic"],
 ["log"],
 ["show", "HEAD"]]

returns

["c2", true, "c3", ["topic", "c2"], "c4",
 ["c4", "c2", "c1"], ["c4"], [1, 1],
 ["main", "c3"], "merge:c5",
 ["c5", "c4", "c3", "c2", "c1"],
 ["README=v1b", "parser.py=v1"]]

Part 1: The review page is lying (REV-3318, 3322, 3325, 3330)

Goal: make log, merge_base/merge_bases, ahead_behind and merge follow the definitions below. Reports from teams whose engineers' laptops have drifting clocks:

1. "The commit list of my review shows a commit above the commit it was built on."
2. "The diff base is a commit from three weeks ago, but we forked yesterday."
3. "The *ahead* badge says 2 but I merged a four-commit feature branch into this branch."
4. "I pressed *Update branch* on a branch that already had everything and got an empty merge commit."

Rules

1. Log order. log lists a set of commits (everything reachable from the tip, minus everything reachable from the A of A..B). Repeat until the set is exhausted: among the commits in the set whose children *inside the set* have all been listed already, list the one with the latest at; if two share the same at, the one with the higher seq. So a parent is never listed before a child, whatever the timestamps say. limit keeps the first limit entries of that order.
2. Merge bases. The *common ancestors* of a and b are the commits reachable from both (a commit is reachable from itself). merge_bases returns the maximal ones: common ancestors that are not an ancestor of another common ancestor, sorted by seq descending. After the first commit there is always at least one. merge_base returns the first of that list (the one with the highest seq). Timestamps play no role.
3. Ahead/behind. [ahead, behind] = [number of commits reachable from a but not from b, number reachable from b but not from a], following every parent.
4. Merge. See the merge rules above: merging something already contained is up_to_date and creates nothing.

Example (a late-clock merge; commit times are 100, 900, 950, 300, then the merge at 400)

[["commit", 100, "A", {"a": "1"}], ["branch", "topic"], ["checkout", "topic"],
 ["commit", 900, "T1", {"t": "1"}], ["commit", 950, "T2", {"t": "2"}], ["checkout", "main"],
 ["commit", 300, "M1", {"m": "1"}], ["merge", 400, "topic"], ["log"], ["log", "HEAD", 3], ["log", "c2..main"]]

returns ["c2", true, ["topic", "c2"], "c3", "c4", ["main", "c2"], "c5", "merge:c6", L1, L2, L3] where L1 = ["c6", "c4", "c3", "c5", "c2", "c1"], L2 = ["c6", "c4", "c3"], L3 = ["c6", "c4", "c3", "c5"]. The merge c6 (time 400) comes first although c4 (950) is "newer", because c4 has a child in the set that has not been listed yet while c6 has none.

tests/test_graph.py::test_ordered_never_lists_a_parent_before_its_child currently fails.

Part 2: Real merges, cherry-pick and revert (REV-3351)

Goal: replace the placeholder trees.merge_trees with a three-way merge, and add cherry_pick and revert.

Three-way merge. merge computes the tree of a new merge commit from base, ours (the HEAD commit's tree) and theirs (the target's tree), where base is the tree of merge_base(H, T) (the single best base; Part 3 refines this). For every key present in any of the three trees, with b, o, t the values (absent counts as "no value"):

• o == t -> that value; else t == b (only we changed it) -> o; else o == b (only they changed it) -> t;
• otherwise it is a conflict.

If there is any conflict the merge fails with {"err": "conflict", "keys": [...]} (conflicting keys sorted as strings), creates nothing and moves nothing. A "no value" result means the key is absent in the merged tree.

Replaying a change. cherry_pick and revert (and, in Part 3, rebase) re-apply the change a commit made on top of whatever HEAD has. The change of a commit C with parent P is the set of keys whose value differs between P's tree and C's tree (the root c1 has the empty tree as its "parent"; a deleted key means value "no value"). To replay a change before -> after onto a current tree, for each key in the change: if current already has the after value, do nothing; otherwise if current has the before value, set it to after; otherwise that key is a conflict. Keys not in the change are untouched. The base here is the commit's own parent, not a merge base, and keys outside the change are never looked at.

Both advance the attached branch (or detached HEAD) and return the new commit id. Errors, in this order: bad_args (at not an integer), unknown_rev, merge_commit (the revision is a commit with two parents), conflict ({"err": "conflict", "keys": [...sorted...]}), empty_commit (the replay leaves HEAD's tree unchanged).

Example

[["commit", 10, "base", {"a": "1", "b": "1", "c": "1"}], ["branch", "topic"], ["branch", "hotfix"],
 ["commit", 20, "main: a=2", {"a": "2"}],
 ["checkout", "topic"], ["commit", 30, "topic: b=2", {"b": "2"}], ["commit", 40, "topic: drop c, add d", {"c": null, "d": "1"}],
 ["checkout", "hotfix"], ["commit", 45, "hotfix: e", {"e": "1"}], ["checkout", "main"],
 ["merge", 50, "topic"], ["show", "HEAD"],
 ["cherry_pick", 60, "c4"], ["cherry_pick", 61, "hotfix"], ["revert", 70, "c3"], ["revert", 80, "c4"],
 ["show", "HEAD"], ["log", "HEAD", 3]]

returns ["c2", true, true, "c3", ["topic", "c2"], "c4", "c5", ["hotfix", "c2"], "c6", ["main", "c3"], "merge:c7", ["a=2", "b=2", "d=1"], {"err": "empty_commit"}, "c8", "c9", "c10", ["a=1", "b=1", "d=1", "e=1"], ["c10", "c9", "c8"]]. (The merge keeps main's a=2, takes topic's b=2, deletion of c and new d. Picking c4 finds b=2 already there, so nothing is left to commit. Reverting c3 and c4 restores a=1 and b=1.)

Part 3: Criss-cross history and rebase (REV-3377, REV-3380)

Goal: (a) fix merges in "criss-cross" history, where two branches have merged each other's older states and merge_bases returns several commits, and (b) add rebase.

(a) Merge base for the tree. This changes Part 2: merge no longer uses only merge_base. When merge_bases(H, T) has more than one entry [b0, b1, ...] (highest seq first), the base tree is a virtual base built like this: start with the tree of b0; for each further bi, take the base tree for the pair (b0, bi) (computed by this same rule, recursively) and three-way merge bi's tree into the accumulated tree (ours = accumulated tree, theirs = bi's tree) where a conflicting key silently keeps the accumulated (ours) value instead of failing. With a single base nothing changes. The final merge of ours/theirs against that virtual base then follows the Part 2 rules (conflicts fail as before). merge_base still returns just the one commit with the highest seq, and the ff/up_to_date rules are unaffected.

(b) Rebase. ["rebase", onto] re-creates the current branch's own commits on top of onto.

1. HEAD must be attached to a branch, else detached_head (checked first); then unknown_rev.
2. Let B be the branch tip and O the commit onto names. If O is B or an ancestor of B: result "up_to_date". Else if B is an ancestor of O: the branch simply moves to O, result "ff:<O>".
3. Otherwise the commits to replay are those reachable from B but not from O, in reverse log order (the Part 1 rule applied to that set, then reversed: oldest first). Merge commits are skipped (their side-branch commits are in the set and are replayed like any other). Each remaining commit's change (against its first parent) is replayed (Part 2 "replaying a change") on top of the previous result, starting from the tree of O.
4. A replayed commit whose replay leaves the tree unchanged (already applied) is dropped; otherwise it becomes a new commit with a single parent (the previously created commit, or O for the first), the original message and original author time, and the next commit id.
5. If any commit conflicts, the result is {"err": "conflict", "keys": [...], "commit": "<id of the original commit>"}, and nothing is created or moved (no ids are used). Otherwise the branch moves to the last new commit (or to O if everything was dropped) and the result is "rebased:<new tip id>:<number of new commits>". The old commits stay in the graph (tags and other branches may still reach them).

Example (a criss-cross merge; the show after merging y into x)

[["branch", "s1"], ["branch", "s2"], ["checkout", "s1"], ["commit", 10, "B1", {"p": "1"}],
 ["checkout", "s2"], ["commit", 20, "B2", {"q": "1"}], ["branch", "x", "s1"], ["branch", "y", "s2"],
 ["checkout", "x"], ["merge", 30, "s2"], ["commit", 40, "x edits p", {"p": "2"}],
 ["checkout", "y"], ["merge", 50, "s1"], ["commit", 60, "y adds r", {"r": "1"}],
 ["merge_bases", "x", "y"], ["merge_base", "x", "y"], ["checkout", "x"], ["merge", 70, "y"], ["show", "HEAD"]]

ends with ..., ["c3", "c2"], "c3", ["x", "c5"], "merge:c8", ["p=2", "q=1", "r=1"]. The bases are c3 (tree q=1) and c2 (tree p=1); the virtual base is p=1, q=1. Against it x's p=2 is a clean change. With c3 alone as base, p would be a conflict.

Example (rebase; times 10, 100, 500, 20, then the rebase)

[["commit", 10, "base", {"a": "1"}], ["branch", "topic"], ["commit", 100, "main: b", {"b": "1"}], ["tag", "tip"],
 ["checkout", "topic"], ["commit", 500, "topic: c", {"c": "1"}], ["commit", 20, "topic: a=2", {"a": "2"}],
 ["rebase", "main"], ["log"], ["info", "HEAD"], ["info", "HEAD~1"], ["show", "HEAD"], ["ahead_behind", "topic", "main"],
 ["log", "tip..topic"], ["rebase", "main"], ["rebase", "tip"], ["count"]]

returns ["c2", true, "c3", true, ["topic", "c2"], "c4", "c5", "rebased:c7:2", ["c7", "c6", "c3", "c2", "c1"], ["c7", ["c6"], 20, "topic: a=2"], ["c6", ["c3"], 500, "topic: c"], ["a=2", "b=1", "c=1"], [2, 0], ["c7", "c6"], "up_to_date", "up_to_date", 7]. The replayed commits c6, c7 keep their old author times, so log shows the skew exactly as Part 1 specifies; c4 and c5 still exist (count is 7).

Part 4: A very long history (REV-3402)

Goal: the monorepo has hundreds of thousands of commits; merge_base, merge_bases, ahead_behind, is_ancestor and merge must stay fast when the two commits being compared are close to each other in a very long history, with results identical to the rules above. Hidden tests run a few hundred queries over histories of several thousand commits within one run (the whole suite has a few seconds). Enumerating every ancestor of both commits per question is too slow, and so is anything that recurses once per commit in a history thousands of commits deep.

Two operations exist to drive load (their code is in workload.py; read it, do not change it):

• ["generate", seed, steps] simulates a team for steps steps (0 <= steps <= 100000, seed >= 0; else bad_args) on the current repository using the public Repo methods, and returns the commit count. It forks and lands short-lived topic branches off main, syncs main into topics (so criss-cross merges happen), and skews timestamps.
• ["survey", seed, pairs] asks pairs merge-base / ahead-behind / ancestry questions about pairs of recent commits and returns [pairs, sum of merge-base seq numbers, total ahead, total behind, ancestor hits].

generate calls merge, so the merge path has to scale as well. Everything from Parts 1-3 must still behave exactly as specified.

Notes

• You may use the AI assistant freely; you are expected to verify what it produces.
• Later parts must not break earlier ones; hidden tests re-check earlier behaviour after later Parts.
• tests/ shows how the library is exercised; extend it as you go.