Fix base-finding for virtual commits in recursive merge - #4487

Interesting. Thanks for digging into this - this aligns pretty well with what I was seeing as well where the order of parents was reversed in the merge base calculation during recursion... but I havent yet grokked why (or more accurately where) Git is doing this.

Thanks much for the test case and PR. I’m going to 🤔 on this a bit to make sure there are no other edges but i think this is likely the right fix.

I noticed that this still isn't producing the same tree as git. I'm digging in to make sure that we're identical here. One problem is that git now uses longer conflict markers in the recursive merge base. I've opened #4488 to resolve that.

I'm still investigating.

It looks like your files have CR/LF line endings. Git has also changed the behavior when it produces conflict files based on inputs with CR/LF line endings. #4489 should allow us to produce the same results.

After including these two fixes, we're still not producing the same ancestor for version.txt.

Git:

zoidberg:Temp/testrepos/merge-recursive% git merge branchJ-2
Auto-merging version.txt
CONFLICT (content): Merge conflict in version.txt
Automatic merge failed; fix conflicts and then commit the result.
zoidberg:Temp/testrepos/merge-recursive% git ls-files --stage
100644 1bde1883de4977ea3e664b315da951d1f614c3b1 0	targetfile.txt
100644 b7de2b52ba055688061355fad1599a5d214ce8f8 1	version.txt
100644 358efd6f589384fa8baf92234db9c7899a53916e 2	version.txt
100644 a664873b1c0b9a1ed300f8644dde536fdaa3a34f 3	version.txt
zoidberg:Temp/testrepos/merge-recursive% git cat-file blob b7de2b52ba055688061355fad1599a5d214ce8f8
<<<<<<<<< Temporary merge branch 1
<<<<<<<<< Temporary merge branch 1
C 
=========
B 
>>>>>>>>> Temporary merge branch 2
=========
A 
>>>>>>>>> Temporary merge branch 2

With this PR:

stage:

100644 1bde1883de4977ea3e664b315da951d1f614c3b1 0 targetfile.txt 
100644 53381b95506bac4a5c859e540f3d478ad155181e 1 version.txt 
100644 358efd6f589384fa8baf92234db9c7899a53916e 2 version.txt 
100644 a664873b1c0b9a1ed300f8644dde536fdaa3a34f 3 version.txt

53381b95506bac4a5c859e540f3d478ad155181e:

<<<<<<<<< Temporary merge branch 1
<<<<<<<<< Temporary merge branch 1
A 
=========
B 
>>>>>>>>> Temporary merge branch 2
=========
C 
>>>>>>>>> Temporary merge branch 2

Still 👀

So git-merge-recursive does indeed reverse the merge bases. We should have been doing this from the beginning.

We need to do this full reversal, too, to match, instead of just creating the virtual merge base with the parents reversed.

If, for example, there are multiple merge bases, eg:

A B C D

then we need to reverse the merge base list as

D C B A

which would merge D+C, then merge that result with B, and that result with A.

If we only reverse the parents in the virtual merge base, then we would merge A+B, but then treat it as if the parents were B and A. Then merge that with C (and treating it like its parents were C B A...) And finally merging that with D.

So I'm moving the reverse logic to match git. I've cherry-picked your test data and test - modifying it to match the data that git produces. I'll open a PR.

Thanks again for your investigation and the PR.

I'm skeptical that your fixes will fully solve the issue (I think the behavior of merge_base_many wrt. virtual bases requires them to always be the second parameter). I'll see if I can create another repro that still fails with your changes.

Well, they are the second parameter now, no?

I’m very happy to have more testing - If we produce different trees than Git then that would be an issue that we should investigate and fix.

I've tweaked the repro case and this still repros without the one/two switch. I'll close this and create a PR into your changes.