Re: Replaying merges

Now HTML-free

On Sat, May 18, 2024 at 9:33 AM Martin von Zweigbergk
[off-list ref] wrote:

On Fri, May 17, 2024, 18:45 Elijah Newren [off-list ref] wrote:

quoted

Hi Johannes!

On Fri, May 17, 2024 at 5:35 PM Johannes Schindelin
[off-list ref] wrote:

quoted

Hi Elijah,

I took the suggestion to heart that you explained a couple of times to me:
To replay merge commits (including their merge conflict resolutions) by
using the _remerged_ commit as merge base, the original merge commit as
merge head, and the newly-created merge (with conflicts and all) as HEAD.

I noodled on this idea a bit until I got it into a usable shape that I
applied to great effect when working on the recent embargoed releases.

Here it is, the script [*1*] that I used (basically replacing all the
`merge -C` instances in the rebase script with `replay-merge.sh`):

<snip>

quoted

For the most part, this worked beautifully.

Cool to see someone try it out.

quoted

However. The devil lies in the detail.

Yup, but details rather than detail.  ;-)

<snip>

quoted

The biggest complication being the scenario... when a merge
conflict had been addressed in the original merge commit, but in the
replayed merge there is no conflict. In such a scenario, this script _will
create not one, but two merge conflicts, nested ones_!

Only if merge.conflictStyle="diff3"; if merge.conflictStyle="merge",
then there will be no nested conflict (since the nested conflict comes
from the fact that the base version had a conflict itself).

This is one of the issues I noted in my write up a couple years ago:
https://github.com/newren/git/blob/replay/replay-design-notes.txt#L315-L316

Further, it can get worse, since in the current code the inner
conflict from the base merge could be an already arbitrarily nested
merge conflict with N levels (due to recursive merging allowing
arbitrary nested of merge conflicts), giving us an overall nesting of
N+1 merge conflicts rather than just the 2 you assumed.  That's ugly
enough, but we also need to worry about ensuring the conflict markers
from different merges get different conflict marker lengths, which
presents an extra challenge since the outer merge here is not part of
the original recursive merge.

In addition to these challenges, there's some other ones:
  * What about when the remerged commit and the newly-created merge
have the "same" conflict.  Does it actually look the "same" to the
diff machinery so that it can resolve the conflict away to how the
original merge resolved?  (Answer: not with a naive merge of these
three commits; we need to do some extra tweaking.  I'm actually
suprised you said this basic idea worked given this particular
problem.)
  * What about conflicts with binary files?  Or non-textual conflicts
of other types like modify/delete or rename/rename?

quoted

I still do think that your idea has merit, but I fear that it won't ever
be as easy as performing multiple three-way merges in succession.

I totally agree we need to do more than the simple merge of those
three "commits"; I have ideas for this that address some of the
challenges over at
https://github.com/newren/git/blob/replay/replay-design-notes.txt#L264-L341

Another approach is to not eagerly evaluate the auto-merged parent tree and instead do some algebra on the trees. For example, if the parents of the merge commit is calculated by merging tree B and tree C with tree A as base, then you can consider the result as tree B+C-A. If the merge commit itself has tree D and you're rebasing it onto tree E, then the result is E+(D-(B+C-A)). You can then evaluate that by recursively merging the trees as usual. This is effectively what jj does and it works very well.

I don't think Git has support for merging more than 3 trees (or tree entries, etc.) at once yet, but that's not very hard. Here's how jj does it: https://github.com/martinvonz/jj/blob/main/lib%2Fsrc%2Fmerge.rs. I think the tests at the end there are quite easy to read and they explain well how it works.