Possible merge bug

Possible merge bug

[Michael Schiff]

[Summary]
Issue occurs when two branches reorder lines of the same file and are
then merged back to the base branch. Instead of getting a content
merge conflict, the branches are merged successfully and a line in the
file is duplicated.


[Steps to Reproduce]
1. initialize a new repository and create a file with three lines of content:
```
a
b
c
```
and commit the result

2. branch from this commit and modify the contents of the file to be:
```
b
a
c
```
and commit the results

3. checkout master at commit from step one

4. branch from this commit and modify the contents of the file to be:
```
b
c
a
```
and commit the results

5. checkout master at the commit from step one

6. merge the first branch (results in ff-merge)

7. merge the second branch (results in auto merge_3way)

8. examine file contents:
```
b
a
c
a
```

[Expected Behavior]
I expected to get a content merge conflict when attempting to merge
the second branch.  If the example is changed to be a file starting
```
a
b
c
d
```
with two branches that change it to
```
c
a
b
d
```
and
```
c
d
a
b
```
respectively, and then the same sequence of merges, this is detected
as a merge conflict as I would expect the single line case to be.

[What Happened Instead]
Instead merge succeeds without conflict and results in duplication of
a line in the file


[System Info]
git version:
git version 2.34.0.rc0.377.g6d82a21a3b
cpu: x86_64
built from commit: 6d82a21a3b699caf378cb0f89b6b0e803fc58480
sizeof-long: 8
sizeof-size_t: 8
shell-path: /bin/sh
uname: Darwin 20.6.0 Darwin Kernel Version 20.6.0: Wed Jun 23 00:26:31
PDT 2021; root:xnu-7195.141.2~5/RELEASE_X86_64 x86_64
compiler info: clang: 13.0.0 (clang-1300.0.29.3)
libc info: no libc information available
$SHELL (typically, interactive shell): /bin/zsh


[Enabled Hooks]

[Other Details]
I tried this experiment with a few different merge strategies and got
the same result regardless of which I picked.  I did some rudimentary
debugging and tracked handling of the merge for this file through
merge-ort.c -> merge_3way -> ll_merge -> xdiff/xmerge.c -- It seems
xdiff/xmerge is responsible for attempting the actual merge, deciding
if there are conflicts and dropping the usual markers, or successfully
auto-merging the changes.  Wasn't sure of the testing process for
xdiff and figured I would put this to the mailing list for feedback.

Re: Possible merge bug

[Saksham Mittal]

Hello there,

I wrote a small script as well that automates testing this use case as well, but I don't really know what the policy is on attachments in git, seeing as how it's my first time contributing to git.

I am on git version 2.33.1 on Fedora 35, but I am not seeing the bug while running the script. So, I grabbed the git source code and built it. This version is 2.34.0.rc2.9.g4d53e91c6b, not quite your version but I tried to go back to the commit you mentioned and build it, but I faced some errors and no binary would build.

Anyway, the version I built and tested also did not permit auto merge and required me to manually make changes as well, so the issue seems to have been fixed.

You can take a look at my script as well, I followed your instructions as best I could and built this:

#!/bin/bash

git --version

mkdir sample
cd sample
git init
echo -e "a\nb\nc\n" > test
git add .
git commit -m "abc"

git branch b1
git switch b1

echo -e "b\na\nc" > test
git add .
git commit -m "bac"

git switch main
git branch b2
git switch b2

echo -e "b\nc\na" > test
git add .
git commit -m "bca"

git switch main
git merge b1
git merge b2

git log --graph --oneline --all


Cheers,

Saksham Mittal

Re: Possible merge bug

[Philippe Blain]

Hi Michael,

Le 2021-11-11 à 06:20, Saksham Mittal a écrit :
> Hello there,
> 
> I wrote a small script as well that automates testing this use case as well, but I don't really know what the policy is on attachments in git, seeing as how it's my first time contributing to git.

I used the script from Saksham (slightly modified to not depend on any Git configuration)
and could not reproduce either with Git built from the same commit as you.
Maybe some setting in your ~/.gitconfig is at play ?

For the record, my edited version of the reproducer:

--- 8< ---
#!/bin/sh

export PATH="/path/to/built/git/bin-wrappers:$PATH"
export GIT_AUTHOR_NAME=J
export GIT_AUTHOR_EMAIL=j@l.com
export GIT_COMMITTER_NAME=J
export GIT_COMMITTER_EMAIL=j@l.com
export HOME=

git --version --build-options

rm -rf sample
mkdir sample
cd sample
git init
echo -e "a\nb\nc\n" > test
git add .
git commit -m "abc"

git branch b1
git switch b1

echo -e "b\na\nc" > test
git add .
git commit -m "bac"

git switch master
git branch b2
git switch b2

echo -e "b\nc\na" > test
git add .
git commit -m "bca"

git switch master
echo "----- Merging b1 -----"
git merge b1
cat test
echo "----- Merging b2 -----"
git merge b2
echo "----- Content of test -----"
cat test
--- 8< ---


Running it ends with this output:


----- Merging b1 -----
Updating 5e00de3..02910cf
Fast-forward
  test | 3 +--
  1 file changed, 1 insertion(+), 2 deletions(-)
b
a
c
----- Merging b2 -----
Auto-merging test
CONFLICT (content): Merge conflict in test
Automatic merge failed; fix conflicts and then commit the result.
----- Content of test -----
b
a
c
<<<<<<< HEAD
=======
a
>>>>>>> b2


Cheers,
Philippe.

Re: Possible merge bug

[Michael Schiff]

This script includes an extra new-line, turing the final change into a
2 line diff, which is caught correctly.  Modified to:
--- 8< ---
git --version --build-options

rm -rf sample
mkdir sample
cd sample
git init
echo -e "a\nb\nc" > test
git add .
git commit -m "abc"

git branch b1
git switch b1

echo -e "b\na\nc" > test
git add .
git commit -m "bac"

git switch master
git branch b2
git switch b2

echo -e "b\nc\na" > test
git add .
git commit -m "bca"

git switch master
echo "----- Merging b1 -----"
git merge b1
cat test
echo "----- Merging b2 -----"
git merge b2
echo "----- Content of test -----"
cat test
--- 8< ---

The only meaningful difference being the removal of the trailing \n
from the first echo.  Running it produces the output:

git version 2.34.0.rc0.377.g6d82a21a3b
cpu: x86_64
built from commit: 6d82a21a3b699caf378cb0f89b6b0e803fc58480
sizeof-long: 8
sizeof-size_t: 8
shell-path: /bin/sh
hint: Using 'master' as the name for the initial branch. This default
branch name
hint: is subject to change. To configure the initial branch name to use in all
hint: of your new repositories, which will suppress this warning, call:
hint:
hint: git config --global init.defaultBranch <name>
hint:
hint: Names commonly chosen instead of 'master' are 'main', 'trunk' and
hint: 'development'. The just-created branch can be renamed via this command:
hint:
hint: git branch -m <name>
Initialized empty Git repository in /Users/michaelschiff/Desktop/sample/.git/
[master (root-commit) 8d6bc12] abc
 1 file changed, 3 insertions(+)
 create mode 100644 test
Switched to branch 'b1'
[b1 b5328d8] bac
 1 file changed, 1 insertion(+), 1 deletion(-)
Switched to branch 'master'
Switched to branch 'b2'
[b2 98603f6] bca
 1 file changed, 1 insertion(+), 1 deletion(-)
Switched to branch 'master'
----- Merging b1 -----
Updating 8d6bc12..b5328d8
Fast-forward
 test | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
b
a
c
----- Merging b2 -----
Auto-merging test
Merge made by the 'ort' strategy.
 test | 1 +
 1 file changed, 1 insertion(+)
----- Content of test -----
b
a
c
a



Happy to provide any other info that helps

On Thu, Nov 11, 2021 at 6:28 AM Philippe Blain
<levraiphilippeblain@gmail.com> wrote:
>
> Hi Michael,
>
> Le 2021-11-11 à 06:20, Saksham Mittal a écrit :
> > Hello there,
> >
> > I wrote a small script as well that automates testing this use case as well, but I don't really know what the policy is on attachments in git, seeing as how it's my first time contributing to git.
>
> I used the script from Saksham (slightly modified to not depend on any Git configuration)
> and could not reproduce either with Git built from the same commit as you.
> Maybe some setting in your ~/.gitconfig is at play ?
>
> For the record, my edited version of the reproducer:
>
> --- 8< ---
> #!/bin/sh
>
> export PATH="/path/to/built/git/bin-wrappers:$PATH"
> export GIT_AUTHOR_NAME=J
> export GIT_AUTHOR_EMAIL=j@l.com
> export GIT_COMMITTER_NAME=J
> export GIT_COMMITTER_EMAIL=j@l.com
> export HOME=
>
> git --version --build-options
>
> rm -rf sample
> mkdir sample
> cd sample
> git init
> echo -e "a\nb\nc\n" > test
> git add .
> git commit -m "abc"
>
> git branch b1
> git switch b1
>
> echo -e "b\na\nc" > test
> git add .
> git commit -m "bac"
>
> git switch master
> git branch b2
> git switch b2
>
> echo -e "b\nc\na" > test
> git add .
> git commit -m "bca"
>
> git switch master
> echo "----- Merging b1 -----"
> git merge b1
> cat test
> echo "----- Merging b2 -----"
> git merge b2
> echo "----- Content of test -----"
> cat test
> --- 8< ---
>
>
> Running it ends with this output:
>
>
> ----- Merging b1 -----
> Updating 5e00de3..02910cf
> Fast-forward
>   test | 3 +--
>   1 file changed, 1 insertion(+), 2 deletions(-)
> b
> a
> c
> ----- Merging b2 -----
> Auto-merging test
> CONFLICT (content): Merge conflict in test
> Automatic merge failed; fix conflicts and then commit the result.
> ----- Content of test -----
> b
> a
> c
> <<<<<<< HEAD
> =======
> a
> >>>>>>> b2
>
>
> Cheers,
> Philippe.
>

Re: Possible merge bug

[Johannes Sixt]

Am 13.11.21 um 04:49 schrieb Michael Schiff:
> This script includes an extra new-line, turing the final change into a
> 2 line diff, which is caught correctly.  Modified to:
> --- 8< ---
> git --version --build-options
> 
> rm -rf sample
> mkdir sample
> cd sample
> git init
> echo -e "a\nb\nc" > test
> git add .
> git commit -m "abc"
> 
> git branch b1
> git switch b1
> 
> echo -e "b\na\nc" > test
> git add .
> git commit -m "bac"
> 
> git switch master
> git branch b2
> git switch b2
> 
> echo -e "b\nc\na" > test
> git add .
> git commit -m "bca"
> 
> git switch master
> echo "----- Merging b1 -----"
> git merge b1
> cat test
> echo "----- Merging b2 -----"
> git merge b2
> echo "----- Content of test -----"
> cat test
> --- 8< ---
> 
> The only meaningful difference being the removal of the trailing \n
> from the first echo.  Running it produces the output:
> 
> git version 2.34.0.rc0.377.g6d82a21a3b
> cpu: x86_64
> built from commit: 6d82a21a3b699caf378cb0f89b6b0e803fc58480
> sizeof-long: 8
> sizeof-size_t: 8
> shell-path: /bin/sh
> hint: Using 'master' as the name for the initial branch. This default
> branch name
> hint: is subject to change. To configure the initial branch name to use in all
> hint: of your new repositories, which will suppress this warning, call:
> hint:
> hint: git config --global init.defaultBranch <name>
> hint:
> hint: Names commonly chosen instead of 'master' are 'main', 'trunk' and
> hint: 'development'. The just-created branch can be renamed via this command:
> hint:
> hint: git branch -m <name>
> Initialized empty Git repository in /Users/michaelschiff/Desktop/sample/.git/
> [master (root-commit) 8d6bc12] abc
>  1 file changed, 3 insertions(+)
>  create mode 100644 test
> Switched to branch 'b1'
> [b1 b5328d8] bac
>  1 file changed, 1 insertion(+), 1 deletion(-)
> Switched to branch 'master'
> Switched to branch 'b2'
> [b2 98603f6] bca
>  1 file changed, 1 insertion(+), 1 deletion(-)
> Switched to branch 'master'
> ----- Merging b1 -----
> Updating 8d6bc12..b5328d8
> Fast-forward
>  test | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> b
> a
> c
> ----- Merging b2 -----
> Auto-merging test
> Merge made by the 'ort' strategy.
>  test | 1 +
>  1 file changed, 1 insertion(+)
> ----- Content of test -----
> b
> a
> c
> a

There is no bug.

Before the merge, the diff on our side is

@@ -1,3 +1,3 @@
-a
 b
+a
 c

and the diff on their side is

@@ -1,3 +1,3 @@
-a
 b
 c
+a

Notice how both sides remove the first line, '-a'. The diff algorithm
treats this identical change on both sides not as a conflict, but simply
as "both sides did the same thing, so let's take it". This leaves two
changes: our side added 'a' in the middle and their side added 'a' at
the end. Both changes are separated by a common context, 'c', which does
not produce a conflict as desired. Hence, no conflict in total.

There is one thing to notice, though. Our side turns 'abc' into 'bac',
i.e., swaps the first two lines. There is no unique "true" patch text
that represents a change that swaps two regions of code. It could be

@@ -1,3 +1,3 @@
-a
 b
+a
 c

or

@@ -1,3 +1,3 @@
+b
 a
-b
 c

Git's diff algrithm (and henceforth merge algorithm) happens to pick the
first one in this case. Had it picked the second option, there would
have been a conflict, I think ('-a' vs. '+b').

-- Hannes