`git rerere` and the skeleton lineage: from merge to rebase

narrative.md

git rerere and the skeleton lineage: from merge to rebase

Why we merge (and why we'd rather not)

Every cisagov project descends from a skeleton. skeleton-generic is the root; skeleton-python-library, skeleton-docker, skeleton-ansible-role, skeleton-tf-module, skeleton-packer, and friends layer on top of it; and hundreds of real projects layer on top of those.

When skeleton-generic changes — a pre-commit hook bump, a new GitHub Actions permission block, a dependabot policy tweak — that change has to flow downstream. Today it flows via merge: each descendant periodically merges its parent. skeleton-python-library alone has merged from skeleton-generic 46 times. Its history is a braid: skeleton commits and library commits woven together by merge commits, so that answering "what does this skeleton add on top of generic?" means untangling the braid by hand.

We'd like the answer to that question to be trivially readable from the graph. That means rebase: keep skeleton-python-library as a straight line of library-specific commits sitting on top of the current tip of skeleton-generic. Then git log skeleton-generic/develop..develop is exactly the library-specific delta, always.

We haven't done this because the rebase is brutal. Below is the data showing exactly how brutal — and how git rerere changes the calculus.

October 30, 2024: one upstream change, four fires

Here is a real, concrete instance of the pain.

On 2024-10-30, skeleton-generic merged PR #194 ("ensure pre-commit hooks are sorted"), landing as commit f517db79. Over the next 24 hours, four descendant skeletons each pulled that change and each hit a merge conflict:

Repo	Merge commit	Conflicting files
skeleton-python-library	f1b7b614	.github/dependabot.yml, .pre-commit-config.yaml
skeleton-ansible-role	7cfee800	.github/dependabot.yml
skeleton-tf-module	ef51f4ff	.github/dependabot.yml
skeleton-packer	3c8c0ac4	.github/dependabot.yml, .github/workflows/build.yml

Someone opened each of those files, stared at nearly-identical <<<<<<< blocks, and stitched them back together. Four times. And that's before the change reaches the projects downstream of each skeleton.

This is not a one-off. Replaying every skeleton merge in skeleton-python-library's history (via git merge-tree) shows the same handful of files conflicting again and again: .github/workflows/build.yml in six different merges, .github/dependabot.yml in four, .pre-commit-config.yaml in four. The recurrence is the whole story. It's why merges are tedious — and it's exactly what makes rerere effective.

What rerere does

rerere — reuse recorded resolution — is built into git. When enabled (git config rerere.enabled true), it watches for conflicts. Each time you resolve one, it fingerprints the conflict hunk (the text between <<<<<<< and >>>>>>>, normalized) and stores your resolution under .git/rr-cache/<fingerprint>/. The next time git sees a conflict with the same fingerprint — in a merge, a rebase, a cherry-pick, a revert — it applies your recorded resolution automatically:

CONFLICT (content): Merge conflict in .github/dependabot.yml
Staged '.github/dependabot.yml' using previous resolution.

The conflict is still reported (git wants you to look), but the file in your working tree is already fixed. With rerere.autoUpdate true, it's already staged, too — you just git rebase --continue.

Priming the pump: rerere-train.sh

The obvious objection: "we haven't been running rerere, so our cache is empty." But every one of those 46 skeleton merges is a recorded resolution — the merge commit itself encodes what a human decided. Git ships a script, contrib/rerere-train.sh, that walks history and back-fills the cache from those decisions. On this machine it lives at /usr/share/doc/git/contrib/rerere-train.sh.

Running it in a fresh clone of skeleton-python-library:

$ git config rerere.enabled true
$ git config rerere.autoUpdate true
$ sh /usr/share/doc/git/contrib/rerere-train.sh develop
Learning from fb1a638 Merge remote-tracking branch 'skeleton/develop' ...
Learning from f1b7b61 Merge remote-tracking branch 'skeleton-generic/develop' ...
Learning from 737aaff Merge github.com:cisagov/skeleton-generic ...
... (31 total) ...
$ ls .git/rr-cache | wc -l
43

31 historical merge conflicts harvested, 43 fingerprints cached — from five years of the team's actual decisions, in about a minute.

Now redo the October 2024 merge from scratch:

$ git switch --detach f1b7b614^1
$ git merge f1b7b614^2
Auto-merging .github/dependabot.yml
CONFLICT (content): Merge conflict in .github/dependabot.yml
Auto-merging .pre-commit-config.yaml
CONFLICT (content): Merge conflict in .pre-commit-config.yaml
Staged '.github/dependabot.yml' using previous resolution.
Staged '.pre-commit-config.yaml' using previous resolution.
Automatic merge failed; fix conflicts and then commit the result.

$ git ls-files -u
$                                          # ← nothing unmerged

$ diff <(git show f1b7b614:.github/dependabot.yml) .github/dependabot.yml
$                                          # ← byte-identical to what
                                           #   the team actually shipped

That's the pre-seeding proof: the cache, trained purely from history, reproduces the human resolution exactly.

The real prize: making rebase tractable

Merges are annoying. Rebases are — today — impossible. Here's why.

Take the same point in time: skeleton-python-library at b2b9dd9 (2024-07-30), skeleton-generic at f517db7 (2024-10-30). To rebase python-library onto generic — git rebase --onto f517db7 f517db7 b2b9dd9 — git must replay every python-library-specific commit on top of the new base. There are 190 of them.

We instrumented that rebase (auto-continuing at each stop so we could count). It halts on conflicts 25 times. The distribution:

Conflict stops	File
6	.github/workflows/build.yml
4	.pre-commit-config.yaml
3	.github/dependabot.yml
2 each	requirements.txt, requirements-test.txt, README.md, .travis.yml, codeql-analysis.yml
1 each	test_example.py, CONTRIBUTING.md, .isort.cfg, .gitignore, .bandit.yml

You would open .github/workflows/build.yml, resolve a conflict, continue… and eight commits later, open it again for a nearly identical conflict. Six times. Nobody has the patience for this, which is why we merge.

Now the same rebase, three ways:

Scenario	Stops	Auto-resolved by rerere	Left for a human
rerere on, empty cache	25	1	24
rerere on, cache trained from merge history	24	6	18
rerere on, cache from a previous rebase	25	25	0

Two things to take from this table.

First, the honest caveat: training from merge history only gets you partway on a rebase (24→18 manual). rerere fingerprints the exact conflict text; a merge conflict looks like "our final state vs their final state," while a rebase conflict looks like "our commit-N delta vs their final state." Different text, different fingerprint. About a quarter of the rebase conflicts happen to match a prior merge shape; the rest don't. rerere-train.sh is a running start, not a free pass for the first rebase.

Second, the payoff: once you've done the rebase once, doing it again is free. 25 stops, 25 auto-resolutions, 0 human decisions. This is the operating model:

Do the painful linearizing rebase once, on a throwaway branch. Keep the rr-cache. Every subsequent skeleton sync is a rebase that resolves itself.

And it compounds. Each time a new conflict shape appears, you resolve it once and it joins the cache. The cache is a ratchet.

Sharing the cache across the team (and across repos)

.git/rr-cache/ is just a directory of small text files. It can be shared:

• Within a repo, across people: commit the cache to a dedicated orphan branch (rr-cache), or keep it in a separate small git repo that everyone clones and symlinks into .git/rr-cache. Now the person who does the painful first rebase gifts a zero-effort rebase to everyone else.

• Across repos: point every skeleton clone's .git/rr-cache at a single shared directory. Any conflict whose ours and theirs text is byte-identical across repos will auto-resolve everywhere after being resolved once anywhere.

  Honest caveat, from the 2024-10-30 example: the four dependabot.yml conflicts that day were visually the same but each had a repo-specific trailer line (# Managed by cisagov/skeleton-python-library vs # Managed by cisagov/skeleton-packer). Different text ⇒ different fingerprint ⇒ no cross-repo cache hit for that hunk. Cross-repo sharing helps most where downstreams haven't customized the conflicting region — which, for things like .pre-commit-config.yaml hook lists, is often. It's a bonus, not the foundation. The foundation is the per-repo temporal reuse.

The rebase-instead-of-merge model, concretely

For any repo X with parent skeleton P:

1. One-time linearization (per repo):

   • Enable rerere (enabled + autoUpdate).
   • rerere-train.sh develop to seed from merge history.
   • On a scratch branch, git rebase --onto P/develop P/develop develop. Grind through the ~20 conflicts (rerere will eat some; you'll resolve the rest once each). This produces both a linear branch and a fully-populated rr-cache.
   • Publish the linear branch as the new develop; publish the rr-cache for the team.

2. Ongoing skeleton sync (each time P changes):

   • git fetch P && git rebase P/develop.
   • rerere auto-resolves every conflict shape it's seen. New shapes (rare, because the hotspot files change slowly) get resolved once and cached.

3. Publishing rebased history: for the skeleton→skeleton layer, which cisagov controls end-to-end and where consumers pull rather than fork, force-updating develop after a sync is acceptable and should be documented as normal (runbook §8). For a project repo with external contributors, do the rebase on a lineage/skeleton branch and fast-forward develop only at release points.

The result: git log P/develop..develop in every skeleton is a clean, readable list of exactly what that skeleton contributes. And keeping it that way costs one git rebase --continue loop that mostly drives itself.

---

See runbook.md for the copy-pasteable procedure, and worklog.md for the investigation trail — including the experiments behind every number above.

This document doesn't seem to mention explicitly that the Lineage PRs that are created in the leaf repos (e.g., cisagov/ansible-role-nessus) would also need to be merged in GitHub via rebase (vice merge). We would also need to share rerere directories for all these repos as well.

How do we want to share the rerere dirs? One repo (i.e., cisagov/git-rerere) with a bunch of subdirectories such as skeleton-generic, awssh, etc.? And we just ln -s locally?

How do we want to do the rebase merges in the skeletons and the lineage leafs? I don't think we can merge in the GitHub web UI, so just do the rebase merge locally and force push up to develop?

How do we want to do the rebase merges in the skeletons and the lineage leafs? I don't think we can merge in the GitHub web UI, so just do the rebase merge locally and force push up to develop?

Take a look at the runbook, Step 4c: linearize.sh --final-safe skeleton-python-library

You do it locally. There is some jazz to save the old HEAD in an archival tag.