Re: [PATCH v2 1/2] xdiff: implement a zealous diff3, or "zdiff3"

[Elijah Newren <newren@gmail.com>]

Hi Phillip,

On Wed, Sep 15, 2021 at 3:25 AM Phillip Wood <phillip.wood123@gmail.com> wrote:
>
> Hi Elijah
>
> On 11/09/2021 18:03, Elijah Newren via GitGitGadget wrote:
> > From: Elijah Newren <newren@gmail.com>
> > [...]
> > diff --git a/t/t6427-diff3-conflict-markers.sh b/t/t6427-diff3-conflict-markers.sh
> > index 25c4b720e72..de9c6190b9c 100755
> > --- a/t/t6427-diff3-conflict-markers.sh
> > +++ b/t/t6427-diff3-conflict-markers.sh
> > @@ -211,4 +211,60 @@ test_expect_success 'rebase --apply describes fake ancestor base' '
> >       )
> >   '
> >
> > +test_setup_zdiff3 () {
> > +     test_create_repo zdiff3 &&
> > +     (
> > +             cd zdiff3 &&
> > +
> > +             test_write_lines 1 2 3 4 5 6 7 8 9 >basic &&
> > +             test_write_lines 1 2 3 AA 4 5 BB 6 7 8 >middle-common &&
> > +             test_write_lines 1 2 3 4 5 6 7 8 9 >interesting &&
> > +
> > +             git add basic middle-common &&
>
> interesting does not get committed

Well, that's embarrassing.  It also explains a lot too; I was
attempting to replicate a weird case I had seen and was surprised I
wasn't able to get it and saw some new really weird behavior instead.
Turns out that new weird behavior was just the fact that zdiff3 wasn't
kicking in because the file wasn't even tracked.  If I had added it,
it would have duplicated the original case I saw...

> > +             git commit -m base &&
>
> adding "base=$(git rev-parse --short HEAD^1)" here ...

Don't you mean to add this below inside the next test_expect block,
where it is used?  But yeah, good idea.

>
> > +
> > +             git branch left &&
> > +             git branch right &&
> > +
> > +             git checkout left &&
> > +             test_write_lines 1 2 3 4 A B C D E 7 8 9 >basic &&
> > +             test_write_lines 1 2 3 CC 4 5 DD 6 7 8 >middle-common &&
> > +             test_write_lines 1 2 3 4 A B C D E F G H I J 7 8 9 >interesting &&
> > +             git add -u &&
> > +             git commit -m letters &&
> > +
> > +             git checkout right &&
> > +             test_write_lines 1 2 3 4 A X C Y E 7 8 9 >basic &&
> > +             test_write_lines 1 2 3 EE 4 5 FF 6 7 8 >middle-common &&
> > +             test_write_lines 1 2 3 4 A B C 5 6 G H I J 7 8 9 >interesting &&
> > +             git add -u &&
> > +             git commit -m permuted
> > +     )
> > +}
> > +
> > +test_expect_failure 'check zdiff3 markers' '
> > +     test_setup_zdiff3 &&
> > +     (
> > +             cd zdiff3 &&
> > +
> > +             git checkout left^0 &&
> > +
> > +             test_must_fail git -c merge.conflictstyle=zdiff3 merge -s recursive right^0 &&
> > +
> > +             test_write_lines 1 2 3 4 A "<<<<<<< HEAD" B C D "||||||| $(git rev-parse --short HEAD^1)" 5 6 ======= X C Y ">>>>>>> right^0" E 7 8 9 >expect &&
>
> ... and then using $base rather than $(git rev-parse ...) would shorten
> these lines. It might be clearer if they were split up something like
> this as well
>
>         test_write_lines \
>                 1 2 3 4 A \
>                 "<<<<<<< HEAD" B C D \
>                 "||||||| $base" 5 6 ======= \
>                 X C Y ">>>>>>> right^0"\
>                  E 7 8 9 >expect &&

Yeah, that looks a lot better.

> > +             test_cmp expect basic &&
> > +
> > +             test_write_lines 1 2 3 "<<<<<<< HEAD" CC "||||||| $(git rev-parse --short HEAD^1)" AA ======= EE ">>>>>>> right^0" 4 5 "<<<<<<< HEAD" DD "||||||| $(git rev-parse --short HEAD^1)" BB ======= FF ">>>>>>> right^0" 6 7 8 >expect &&
> > +             test_cmp expect middle-common &&
> > +
> > +             # Not passing this one yet.  For some reason, after extracting
> > +             # the common lines "A B C" and "G H I J", the remaining part
> > +             # is comparing "5 6" in the base to "5 6" on the left and
> > +             # "D E F" on the right.  And zdiff3 currently picks the side
> > +             # that matches the base as the merge result.  Weird.
> > +             test_write_lines 1 2 3 4 A B C D E F G H I J 7 8 9 >expect &&
>
> I might be about to make a fool of myself but I don't think this is
> right for expect. 5 and 6 are deleted on the left so the two sides
> should conflict. Manually comparing the result of merging with diff3 and
> zdiff3 the zdiff3 result looked correct to me.

You are right.  Had I managed to add and thus track 'interesting', I
would have seen this correct zdiff3 conflict for it, and I hope I
would have figured out why I got the 'expect' file wrong here.  But
either way, thanks for catching and fixing both my bugs in the
testsuite.

> I do wonder (though a brief try failed to trigger it) if there are cases
> where the diff algorithm does something "clever" which means it does not
> treat a common prefix or suffix as unchanged (see d2f82950a9
> ("Re(-re)*fix trim_common_tail()", 2007-12-20) for a related issue). We
> could just trim the common prefix and suffix from the two sides
> ourselves using xdl_recmatch().

You seem to understand the xdl stuff much better than I.  I'm not sure
how xdl_recmatch() would be called or where.  Would you like to take
over the patches?