Confusing (maybe wrong?) conflict output with ort

Confusing (maybe wrong?) conflict output with ort

[Alex Xu (Hello71)]

[-- Attachment #1: Type: text/plain, Size: 7177 bytes --]

Hi all,

After upgrading to git 2.34.1, I tried to rebase [0] onto [1], but 
encountered "strange" conflict results.

git rebase -s recursive main produces [[RECURSIVE]]. It is roughly what 
I expected to be output. If I take all the changes from the upper 
section of the conflict, my changes will be effectively undone. If I 
take all the changes from the lower section, then the upstream changes 
will be undone.

On the other hand, running git rebase -s ort main produces [[ORT]]. I am 
unsure if it is wrong, strictly speaking, but it is certainly unexpected 
and difficult for me to resolve. Selecting the upper section of the 
conflict does erase my changes, as before, but selecting the lower 
section results in syntactically incorrect code (foreach is ended by 
endif). The diff3 output makes even less sense to me.

A script is attached to assist in reproducing my results. Running it 
initializes the repository to the desired state. Then, run "git rebase 
-s strategy master" to produce the conflict.

Thanks,
Alex.

[0] https://gitlab.freedesktop.org/alxu/mesa/-/commit/4ad18ab613101e3489ca2d9e7151125f670e1ea5
[1] https://gitlab.freedesktop.org/alxu/mesa/-/commit/c47fd3dc0062101b3e75a414b17d2765735f7424

[[RECURSIVE]]

<<<<<<< HEAD
use_elf_tls = true
pre_args += '-DUSE_ELF_TLS'

if with_platform_android and get_option('platform-sdk-version') >= 29
  # By default the NDK compiler, at least, emits emutls references instead of
  # ELF TLS, even when building targeting newer API levels.  Make it actually do
  # ELF TLS instead.
  c_args += '-fno-emulated-tls'
  cpp_args += '-fno-emulated-tls'
endif

# -mtls-dialect=gnu2 speeds up non-initial-exec TLS significantly but requires
# full toolchain (including libc) support.
have_mtls_dialect = false
foreach c_arg : get_option('c_args')
  if c_arg.startswith('-mtls-dialect=')
    have_mtls_dialect = true
    break
  endif
endforeach
if not have_mtls_dialect
  # need .run to check libc support. meson aborts when calling .run when
  # cross-compiling, but because this is just an optimization we can skip it
  if meson.is_cross_build()
    warning('cannot auto-detect -mtls-dialect when cross-compiling, using compiler default')
  else
    # -fpic to force dynamic tls, otherwise TLS relaxation defeats check
    gnu2_test = cc.run('int __thread x; int main() { return x; }', args: ['-mtls-dialect=gnu2', '-fpic'], name: '-mtls-dialect=gnu2')
    if gnu2_test.returncode() == 0
      c_args += '-mtls-dialect=gnu2'
      cpp_args += '-mtls-dialect=gnu2'
=======
use_elf_tls = false
if not with_platform_windows or not with_shared_glapi
  pre_args += '-DUSE_ELF_TLS'
  use_elf_tls = true

  if with_platform_android and get_option('platform-sdk-version') >= 29
    # By default the NDK compiler, at least, emits emutls references instead of
    # ELF TLS, even when building targeting newer API levels.  Make it actually do
    # ELF TLS instead.
    c_args += '-fno-emulated-tls'
    cpp_args += '-fno-emulated-tls'
  endif

  # -mtls-dialect=gnu2 speeds up non-initial-exec TLS significantly but requires
  # full toolchain (including libc) support.
  have_mtls_dialect = false
  foreach c_arg : get_option('c_args')
    if c_arg.startswith('-mtls-dialect=')
      have_mtls_dialect = true
      break
    endif
  endforeach
  if not have_mtls_dialect
    # need .run to check libc support. meson aborts when calling .run when
    # cross-compiling, but because this is just an optimization we can skip it
    if meson.is_cross_build()
      warning('cannot auto-detect -mtls-dialect when cross-compiling, using compiler default')
    else
      # -fpic to force dynamic tls, otherwise TLS relaxation defeats check
      gnu2_test = cc.run('int __thread x; int main() { return x; }', args: ['-mtls-dialect=gnu2', '-fpic'], name: '-mtls-dialect=gnu2')
      # https://gitlab.freedesktop.org/mesa/mesa/-/issues/5665
      if gnu2_test.returncode() == 0 and (
           host_machine.cpu_family() != 'x86_64' or
           # https://github.com/mesonbuild/meson/issues/6377
           #cc.get_linker_id() != 'ld.lld' or
           cc.links('''int __thread x; int y; int main() { __asm__(
                  "leaq x@TLSDESC(%rip), %rax\n"
                  "movq y@GOTPCREL(%rip), %rdx\n"
                  "call *x@TLSCALL(%rax)\n"); }''', name: 'split TLSDESC')
           )
        c_args += '-mtls-dialect=gnu2'
        cpp_args += '-mtls-dialect=gnu2'
      endif
>>>>>>> 4ad18ab6131 (meson: check for lld split TLSDESC bug (fixes #5665))
    endif
  endif
endif

[[ORT]]

# -mtls-dialect=gnu2 speeds up non-initial-exec TLS significantly but requires
# full toolchain (including libc) support.
have_mtls_dialect = false
foreach c_arg : get_option('c_args')
  if c_arg.startswith('-mtls-dialect=')
    have_mtls_dialect = true
    break
  endif
<<<<<<< HEAD
endforeach
if not have_mtls_dialect
  # need .run to check libc support. meson aborts when calling .run when
  # cross-compiling, but because this is just an optimization we can skip it
  if meson.is_cross_build()
    warning('cannot auto-detect -mtls-dialect when cross-compiling, using compiler default')
  else
    # -fpic to force dynamic tls, otherwise TLS relaxation defeats check
    gnu2_test = cc.run('int __thread x; int main() { return x; }', args: ['-mtls-dialect=gnu2', '-fpic'], name: '-mtls-dialect=gnu2')
    if gnu2_test.returncode() == 0
      c_args += '-mtls-dialect=gnu2'
      cpp_args += '-mtls-dialect=gnu2'
=======

  # -mtls-dialect=gnu2 speeds up non-initial-exec TLS significantly but requires
  # full toolchain (including libc) support.
  have_mtls_dialect = false
  foreach c_arg : get_option('c_args')
    if c_arg.startswith('-mtls-dialect=')
      have_mtls_dialect = true
      break
    endif
  endforeach
  if not have_mtls_dialect
    # need .run to check libc support. meson aborts when calling .run when
    # cross-compiling, but because this is just an optimization we can skip it
    if meson.is_cross_build()
      warning('cannot auto-detect -mtls-dialect when cross-compiling, using compiler default')
    else
      # -fpic to force dynamic tls, otherwise TLS relaxation defeats check
      gnu2_test = cc.run('int __thread x; int main() { return x; }', args: ['-mtls-dialect=gnu2', '-fpic'], name: '-mtls-dialect=gnu2')
      # https://gitlab.freedesktop.org/mesa/mesa/-/issues/5665
      if gnu2_test.returncode() == 0 and (
           host_machine.cpu_family() != 'x86_64' or
           # https://github.com/mesonbuild/meson/issues/6377
           #cc.get_linker_id() != 'ld.lld' or
           cc.links('''int __thread x; int y; int main() { __asm__(
                  "leaq x@TLSDESC(%rip), %rax\n"
                  "movq y@GOTPCREL(%rip), %rdx\n"
                  "call *x@TLSCALL(%rax)\n"); }''', name: 'split TLSDESC')
           )
        c_args += '-mtls-dialect=gnu2'
        cpp_args += '-mtls-dialect=gnu2'
      endif
>>>>>>> 4ad18ab6131 (meson: check for lld split TLSDESC bug (fixes #5665))
    endif
  endif
endif

[-- Attachment #2: reproducer.sh --]
[-- Type: application/x-shellscript, Size: 4039 bytes --]

Re: Confusing (maybe wrong?) conflict output with ort

[Elijah Newren]

Hi,

On Thu, Dec 2, 2021 at 11:08 AM Alex Xu (Hello71) <alex_y_xu@yahoo.ca> wrote:
>
> Hi all,
>
> After upgrading to git 2.34.1, I tried to rebase [0] onto [1], but
> encountered "strange" conflict results.
>
> git rebase -s recursive main produces [[RECURSIVE]]. It is roughly what
> I expected to be output. If I take all the changes from the upper
> section of the conflict, my changes will be effectively undone. If I
> take all the changes from the lower section, then the upstream changes
> will be undone.

In general, this does not work.  The only time it can work is if every
region of the code considered by the three-way content merge ended up
with conflicts.  (If any of those regions had automatically resolvable
changes, then after taking just the upper section(s) or just the lower
section(s) of each conflict would still result in a file that is a
mixture of changes from both sides due to the automatically resolvable
chunks that the merge already handled.)

> On the other hand, running git rebase -s ort main produces [[ORT]]. I am
> unsure if it is wrong, strictly speaking, but it is certainly unexpected
> and difficult for me to resolve. Selecting the upper section of the
> conflict does erase my changes, as before, but selecting the lower
> section results in syntactically incorrect code (foreach is ended by
> endif). The diff3 output makes even less sense to me.

The output from using ort is identical to that obtained by

   git rebase -s recursive -Xdiff-algorithm=histogram ...

on your testcase; i.e. this is due to a difference between the
histogram and myers diff algorithms.
(recursive defaults to using myers diff; ort uses histogram diff.)

> A script is attached to assist in reproducing my results. Running it
> initializes the repository to the desired state. Then, run "git rebase
> -s strategy master" to produce the conflict.

Thanks.  I'll note for others that there's a missing 'git add
meson.build' (without which the script errors out), and folks should
probably run this from an empty directory that they can nuke later.


Let's use a simpler example for demonstration purposes with some made
up pseudocode.  I'll label each line so I can refer to it ('B' for
base, plus a line number), but the lines are everything after the
label:

B01 if condition1:
B02   if condition2:
B03     do_stuff2()
B04   endif
B05   for var in range:
B06     if condition3:
B07       do_stuff3()
B08     endif
B09   endfor
B10 endif

And let's say that locally, you modified line 7 to do something more
complex, so that the local version looks like this: (prefixing the
line numbers with 'L' for local)

L01 if condition1:
L02   if condition2:
L03     do_stuff2()
L04   endif
L05   for var in range:
L06     if condition3:
L07       more_detailed_stuff3()
L08     endif
L09   endfor
L10 endif

Further, let's say that upstream either determined that condition1 was
always true, or just that they wanted to run all the code
unconditionally so they removed the outer if and un-indented
everything.  So they have (prefixing the line numbers with 'U' for
upstream):

U01 if condition2:
U02   do_stuff2()
U03 endif
U04 for var in range:
U05   if condition3:
U06     do_stuff3()
U07   endif
U08 endfor


There's multiple equally valid ways to attempt to merge this.  One
could be just considering the entire region to conflict, so you'd end
up with a conflict region that looks like this:

    <<<<<<
L01 if condition1:
L02   if condition2:
L03     do_stuff2()
L04   endif
L05   for var in range:
L06     if condition 3:
L07       do_stuff3()
L08     endif
L09   endfor
L10 endif
    ||||||
B01 if condition1:
B02   if condition2:
B03     do_stuff2()
B04   endif
B05   for var in range:
B06     if condition3:
B07       do_stuff3()
B08     endif
B09   endfor
B10 endif
    ======
U01 if condition2:
U02   do_stuff2()
U03 endif
U04 for var in range:
U05   if condition3:
U06     do_stuff3()
U07   endif
U08 endfor
    >>>>>>

Of course, you can leave out the middle region if not doing diff3.

Alternatively, if you look closely, there is exactly one line that
matches in all three versions of the code: B04 == L04 == U07 (if you
think there are other lines that match, you're not paying enough
attention to leading whitespace).  That one matching line could be
used to break us into two conflict regions, which we'll take as a
first step towards simplifying this:

    <<<<<<
L01 if condition1:
L02   if condition2:
L03     do_stuff2()
    ||||||
B01 if condition1:
B02   if condition2:
B03     do_stuff2()
    ======
U01 if condition2:
U02   do_stuff2()
U03 endif
U04 for var in range:
U05   if condition3:
U06     do_stuff3()
    >>>>>>
B04   endif
    <<<<<<
L05   for var in range:
L06     if condition 3:
L07       more_detailed_stuff3()
L08     endif
L09   endfor
L10 endif
    ||||||
B05   for var in range:
B06     if condition3:
B07       do_stuff3()
B08     endif
B09   endfor
B10 endif
    ======
U08 endfor
    >>>>>>

Now, if you look at the first conflict region, the local side matches
the base side exactly, so it can be trivially merged -- we should just
take the upstream side.  Doing that gives us the following:

U01 if condition2:
U02   do_stuff2()
U03 endif
U04 for var in range:
U05   if condition3:
U06     do_stuff3()
B04   endif
    <<<<<<
L05   for var in range:
L06     if condition 3:
L07       more_detailed_stuff3()
L08     endif
L09   endfor
L10 endif
    ||||||
B05   for var in range:
B06     if condition3:
B07       do_stuff3()
B08     endif
B09   endfor
B10 endif
    ======
U08 endfor
    >>>>>>

Or, if you don't use the diff3 format, then we can leave out the
middle section of the remaining conflict and get just:

U01 if condition2:
U02   do_stuff2()
U03 endif
U04 for var in range:
U05   if condition3:
U06     do_stuff3()
B04   endif
    <<<<<<
L05   for var in range:
L06     if condition 3:
L07       more_detailed_stuff3()
L08     endif
L09   endfor
L10 endif
    ======
U08 endfor
    >>>>>>

Now, if you try to use just the "left" side of the remaining conflict,
you get code that doesn't even compile because it's mixing upstream
and local code (and in particular ends U04's "for" with L10's "endif",
similar to the example you gave).  The lines U04-B04 roughly
correspond to L05-L08 (though U06 needs updating based on L07), and
your confusion is probably that both are included in the result.  But
the above is why.

Does that help explain things?

Re: Confusing (maybe wrong?) conflict output with ort

[Alex Xu (Hello71)]

Excerpts from Elijah Newren's message of December 2, 2021 6:58 pm:
> Hi,
> 
> On Thu, Dec 2, 2021 at 11:08 AM Alex Xu (Hello71) <alex_y_xu@yahoo.ca> wrote:
>>
>> Hi all,
>>
>> After upgrading to git 2.34.1, I tried to rebase [0] onto [1], but
>> encountered "strange" conflict results.
>>
>> git rebase -s recursive main produces [[RECURSIVE]]. It is roughly what
>> I expected to be output. If I take all the changes from the upper
>> section of the conflict, my changes will be effectively undone. If I
>> take all the changes from the lower section, then the upstream changes
>> will be undone.
> 
> In general, this does not work.  The only time it can work is if every
> region of the code considered by the three-way content merge ended up
> with conflicts.  (If any of those regions had automatically resolvable
> changes, then after taking just the upper section(s) or just the lower
> section(s) of each conflict would still result in a file that is a
> mixture of changes from both sides due to the automatically resolvable
> chunks that the merge already handled.)
> 
>> On the other hand, running git rebase -s ort main produces [[ORT]]. I am
>> unsure if it is wrong, strictly speaking, but it is certainly unexpected
>> and difficult for me to resolve. Selecting the upper section of the
>> conflict does erase my changes, as before, but selecting the lower
>> section results in syntactically incorrect code (foreach is ended by
>> endif). The diff3 output makes even less sense to me.
> 
> The output from using ort is identical to that obtained by
> 
>    git rebase -s recursive -Xdiff-algorithm=histogram ...
> 
> on your testcase; i.e. this is due to a difference between the
> histogram and myers diff algorithms.
> (recursive defaults to using myers diff; ort uses histogram diff.)

[ ... ]

> Does that help explain things?

Hm, I did try both default and patience and it didn't make a difference. 
git rebase -s recursive -Xdiff-algorithm=histogram master does produce 
the same result as ort though. I probably should have tried that first. 
Thanks for the explanation though, that's very helpful!

Cheers,
Alex.