PR Batching and Conflicts

There is a bit of a problem with git workflows that require PRs to be up-to-date. If t_c is how long your checks take to run, PRs must be up to date, and after changing the content of a PR the checks need to run again, then you can only merge 1 PR each t_c.

If you get your checks to go decently fast that number can work for a fairly large project. You might be in trouble if you want to wait for re-approvals from reviewers though, as the average time it takes for a trivial re-approval will easily be long enough to have you limited to single digit PRs per day.

If you want to go beyond this limit your are going to need some way to relax that up-to-date requirement.

A merge train or queue is a technique for relaxing the up-to-date requirement without giving up too much in terms of correctness. If you can create a set of PRs that you can merge together in a given order without conflicts or failing checks on the result, then you allow them to all merge at once.

With respect to the constraint this has similar properties to allowing PRs to be out of date by a small fixed amount of time, but with more structure.

Back in late 2021 at Hockesytick we were having some issues with PRs being stalled for a long time as described above. We were nowhere near the team size you would usually need to hit the limits I mentioned above, but there were some other things that got us there:

1. We were unfortunately relying on an amount of manual QA. This is in effect equivalent to an extremely long running CI check.
2. We were having a lot of cases where developers had real conflicts with other PRs that required manual resolution.

So I start by building out a system to simply generate a batched PR from the all of the open ones against main.

Take everything open, approved, and passing checks, then iterate in PR number order to attempt to merge them one by one into a branch called ci/development that starts at main. Anything with conflicts is simply skipped at this point.

This first version doesn't do too much besides provide a bit of a heads up to developers when there will be upcoming conflicts with other branches.

To get to something that makes nice batches for QA we then need to add a way for the PRs to be marked as in need of update due to failing QA checks. This was done with a label added to the PRs indicating explicitly that they should be included in the build. Thus the process will now also create a ci/qa branch that uses the same rules as the development branch, but it only considers the labeled PRs.

One interesting issue I discovered in the process is that for the QA branch it was undesirable to kick PRs out of the build unless the label was manually removed or the feature was merged. That means that I ended up making the queue a bit stateful, it would inspect the previous result and abort entirely rather than produce a QA integration branch that was missing things previously included(which you could manually override in a few ways).

I wanted to offer developers the ability to solve conflicts with other PRs as few times as possible. The goal was to enable a number of queued PRs with changes in close proximity to go out at once without the developers needing to put their branches ahead of every conflicting branch.

As for how to actually do that, git has a related feature we can take inspiration from. Git rerere is a tool that saves the resolutions you pick for merge conflicts so that they can be re-applied when the exact same conflict is seen multiple times.

To see how to build this into the queue, lets have a quick look at how rerere works. You turn it on via the rerere.enabled setting in git and then any time you perform an operation that has conflicts it will hook into that to save and replay your resolutions.

So when you start a merge and have conflicts you will see notes that it saved a pre-image of the conflicts. The pre-images are essentially a copy of a file containing the git merge conflict markers, but with the branch info removed.

a
<<<<<<<
=======
c
>>>>>>>
c

Then when you finish resolving all the conflics it will create post-images for each file. The post-images simply contains a copy of the final version of the file you settled on in its entirety.

You can dig around in .git/rr-cache to see what it has saved in a given repository.

The tool will tend to err on the side of caution when determining if it can use a resolution, when it isn't obviously the exact same conflict it is probably better to make the user solve it again themselves.

In our case we wanted something a little different.

• It should create a single file for each conflict resolution rather than each file.
• It should allow for a reasonable amount of flexibility in using the resolutions.

The latter point is because we are describing a resolution that applies only to one merge rather than globally, and it is being applied in a situation where asking the user to give a new resolution is more costly.

The solution that achieves this a tool the developer can run to do the following:

1. Start a merge with specific normalized settings to have git add in all the conflict markers in a consistent format.
2. Remove all of the labels from the markers and save the entire tree at that point as the pre-image.
3. Abort and redo the merge, this time using the user's settings for things like how conflicts are rendered.
4. Allow the user to resolve the merge.
5. Take the tree at the end of the resolution and compute the patch from the pre-image to the result.
6. Save that patch with a generated name in a hidden folder and output the path to the patch to the user.

The user can then add the patch to their PR and the merge queue will consume it when attempting to merge that PR.

That is where the system comes full circle. The simplicity of the queue design means that a user can run any part of the process on their machine. So that is what the tool does.

If you want to create the conflict resolutions for a given PR number, the tool will first run through the process of building up the queue branch locally up to the point where that PR is to be applied. The exact same code is used for this locally and in the tasks to ensure the results are the same.

The patch files get consumed as part of the queue process. When the queue merges a given PR, if there are conflicts, it will attempt to use the saved patches to resolve them. This is done by performing the same steps to get the tree into the pre-image state then attempting to apply the patches found in partial mode (which allows for parts of a patch to not need to be applied). Afterwards if there are no remaining conflict markers the code will also remove all of the patches it can find before finalizing the merge commit. If there are conflicts remaining it will abort applying that PR and move on to the next one.

When squash merges are used the result of removing patches in this way is that the conflict resolution patches will never appear in any commit in the history of the mainline branch.

One obvious problem with this approach is that the patches represent meaningful code changes that are effectively hidden during code review. Looking at a single PR, even if you could read the patch easily, some of the context for what it produces simply isn't in the PR.

The approach we used did involve someone doing a pass through the queue output as a pull request before merging it, but that is a big PR to review in a hurry.

Thus to facilitate reviewing the patch changes separately the process of building the queue is actually a little bit more complicated than what I've described so far.

The first step is still to simply perform the merge as described before. This creates the merged commit below.

Then we can go about creating the following linear commit graph by making use of that saved merged commit.

What we do is we replay the commits of the PR on top of the current queue, but for every commit we use the ours strategy to automatically resolve every conflict in favour of the version in the PR. These rebased commits are shown annotated with the ' symbol.

Then after that we create a merged' commit which is set as having the parent pn' but the file tree from merged. This effectively discards the file tree that was computed by replaying the commits, but still preserves it in the git history.

Now each of p1' to pn' will have nearly the same changed lines as their counterparts and the merged' commit diff will contain only a readable version of the changes that the patches for the PR applied.

This was something that I enjoyed building, and that did enable us to move a lot faster, but it has significant tradeoffs and is by no means simple.

If anything I hope this serves as a bit of a cautionary tale to help you justify a much more significant up front investment in automated testing.

Worth mentioning though is that something people had a decent amount of trouble with is that they were maintaining two versions of their code at once, with the easily visible version not being the final one. So they would have to be aware enough to check that the version of their code with patches applied also works.

The options for improving that are definitely not simple, you would want to provide tools for the user to edit both versions as they are working rather than on demand. Such as by having their their local environment execute the version of the code with patches applied, but show them the version without patches unless they need to be prompted for new resolutions. It might even then not be possible to get that all the way to a great developer experience.