| Message ID | 06e04c88dea3e15a90f0a11795b7a8eea3533bc8.1631379829.git.gitgitgadget@gmail.com (mailing list archive) |
|---|---|
| State | Superseded |
| Headers | show |
| Series | RFC: implement new zdiff3 conflict style | expand |
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 > + git commit -m base && adding "base=$(git rev-parse --short HEAD^1)" here ... > + > + 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 && > + 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. 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(). Best Wishes Phillip > + test_cmp expect interesting > + ) > +' > + > test_done > diff --git a/xdiff-interface.c b/xdiff-interface.c > index 609615db2cd..9977813a9d3 100644 > --- a/xdiff-interface.c > +++ b/xdiff-interface.c > @@ -308,6 +308,8 @@ int git_xmerge_config(const char *var, const char *value, void *cb) > die("'%s' is not a boolean", var); > if (!strcmp(value, "diff3")) > git_xmerge_style = XDL_MERGE_DIFF3; > + else if (!strcmp(value, "zdiff3")) > + git_xmerge_style = XDL_MERGE_ZEALOUS_DIFF3; > else if (!strcmp(value, "merge")) > git_xmerge_style = 0; > /* > diff --git a/xdiff/xdiff.h b/xdiff/xdiff.h > index 7a046051468..8629ae287c7 100644 > --- a/xdiff/xdiff.h > +++ b/xdiff/xdiff.h > @@ -65,6 +65,7 @@ extern "C" { > > /* merge output styles */ > #define XDL_MERGE_DIFF3 1 > +#define XDL_MERGE_ZEALOUS_DIFF3 2 > > typedef struct s_mmfile { > char *ptr; > diff --git a/xdiff/xmerge.c b/xdiff/xmerge.c > index 1659edb4539..df0c6041778 100644 > --- a/xdiff/xmerge.c > +++ b/xdiff/xmerge.c > @@ -230,7 +230,7 @@ static int fill_conflict_hunk(xdfenv_t *xe1, const char *name1, > size += xdl_recs_copy(xe1, m->i1, m->chg1, needs_cr, 1, > dest ? dest + size : NULL); > > - if (style == XDL_MERGE_DIFF3) { > + if (style == XDL_MERGE_DIFF3 || style == XDL_MERGE_ZEALOUS_DIFF3) { > /* Shared preimage */ > if (!dest) { > size += marker_size + 1 + needs_cr + marker3_size; > @@ -327,7 +327,7 @@ static int xdl_fill_merge_buffer(xdfenv_t *xe1, const char *name1, > * lines. Try hard to show only these few lines as conflicting. > */ > static int xdl_refine_conflicts(xdfenv_t *xe1, xdfenv_t *xe2, xdmerge_t *m, > - xpparam_t const *xpp) > + xpparam_t const *xpp, int style) > { > for (; m; m = m->next) { > mmfile_t t1, t2; > @@ -368,6 +368,42 @@ static int xdl_refine_conflicts(xdfenv_t *xe1, xdfenv_t *xe2, xdmerge_t *m, > continue; > } > x = xscr; > + if (style == XDL_MERGE_ZEALOUS_DIFF3) { > + int advance1 = xscr->i1, advance2 = xscr->i2; > + > + /* > + * Advance m->i1 and m->i2 so that conflict for sides > + * 1 and 2 start after common region. Decrement > + * m->chg[12] since there are now fewer conflict lines > + * for those sides. > + */ > + m->i1 += advance1; > + m->i2 += advance2; > + m->chg1 -= advance1; > + m->chg2 -= advance2; > + > + /* > + * Splitting conflicts due to internal common regions > + * on the two sides would be inappropriate since we > + * are also showing the merge base and have no > + * reasonable way to split the merge base text. > + */ > + while (xscr->next) > + xscr = xscr->next; > + > + /* > + * Lower the number of conflict lines to not include > + * the final common lines, if any. Do this by setting > + * number of conflict lines to > + * (line offset for start of conflict in xscr) + > + * (number of lines in the conflict in xscr) > + */ > + m->chg1 = (xscr->i1 - advance1) + (xscr->chg1); > + m->chg2 = (xscr->i2 - advance2) + (xscr->chg2); > + xdl_free_env(&xe); > + xdl_free_script(x); > + continue; > + } > m->i1 = xscr->i1 + i1; > m->chg1 = xscr->chg1; > m->i2 = xscr->i2 + i2; > @@ -419,6 +455,7 @@ static int lines_contain_alnum(xdfenv_t *xe, int i, int chg) > static void xdl_merge_two_conflicts(xdmerge_t *m) > { > xdmerge_t *next_m = m->next; > + m->chg0 = next_m->i0 + next_m->chg0 - m->i0; > m->chg1 = next_m->i1 + next_m->chg1 - m->i1; > m->chg2 = next_m->i2 + next_m->chg2 - m->i2; > m->next = next_m->next; > @@ -430,12 +467,12 @@ static void xdl_merge_two_conflicts(xdmerge_t *m) > * it appears simpler -- because it takes up less (or as many) lines -- > * if the lines are moved into the conflicts. > */ > -static int xdl_simplify_non_conflicts(xdfenv_t *xe1, xdmerge_t *m, > +static int xdl_simplify_non_conflicts(xdfenv_t *xe1, xdmerge_t *m, int style, > int simplify_if_no_alnum) > { > int result = 0; > > - if (!m) > + if (!m || style == XDL_MERGE_ZEALOUS_DIFF3) > return result; > for (;;) { > xdmerge_t *next_m = m->next; > @@ -482,6 +519,25 @@ static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1, > int style = xmp->style; > int favor = xmp->favor; > > + /* > + * XDL_MERGE_DIFF3 does not attempt to refine conflicts by looking > + * at common areas of sides 1 & 2, because the base (side 0) does > + * not match and is being shown. Similarly, simplification of > + * non-conflicts is also skipped due to the skipping of conflict > + * refinement. > + * > + * XDL_MERGE_ZEALOUS_DIFF3, on the other hand, will attempt to > + * refine conflicts looking for common areas of sides 1 & 2. > + * However, since the base is being shown and does not match, > + * it will only look for common areas at the beginning or end > + * of the conflict block. Since XDL_MERGE_ZEALOUS_DIFF3's > + * conflict refinement is much more limited in this fashion, the > + * conflict simplification will be skipped. > + * > + * See xdl_refine_conflicts() and xdl_simplify_non_conflicts() > + * for more details, particularly looking for > + * XDL_MERGE_ZEALOUS_DIFF3. > + */ > if (style == XDL_MERGE_DIFF3) { > /* > * "diff3 -m" output does not make sense for anything > @@ -604,8 +660,8 @@ static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1, > changes = c; > /* refine conflicts */ > if (XDL_MERGE_ZEALOUS <= level && > - (xdl_refine_conflicts(xe1, xe2, changes, xpp) < 0 || > - xdl_simplify_non_conflicts(xe1, changes, > + (xdl_refine_conflicts(xe1, xe2, changes, xpp, style) < 0 || > + xdl_simplify_non_conflicts(xe1, changes, style, > XDL_MERGE_ZEALOUS < level) < 0)) { > xdl_cleanup_merge(changes); > return -1; >
On 15/09/2021 11:25, Phillip Wood wrote: > 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(). Here is an evil test case that shows this problem (diff on top of your patch) diff --git a/t/t6427-diff3-conflict-markers.sh b/t/t6427-diff3-conflict-markers.sh index de9c6190b9..836843c6b0 100755 --- a/t/t6427-diff3-conflict-markers.sh +++ b/t/t6427-diff3-conflict-markers.sh @@ -219,8 +219,9 @@ test_setup_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 && + test_write_lines 1 2 3 4 5 6 7 8 9 >evil && - git add basic middle-common && + git add basic middle-common interesting evil && git commit -m base && git branch left && @@ -230,19 +231,21 @@ test_setup_zdiff3 () { 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 && + test_write_lines 1 2 3 4 X A B C 7 8 9 >evil && 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 && + test_write_lines 1 2 3 4 Y A B C B C 7 8 9 >evil && git add -u && git commit -m permuted ) } -test_expect_failure 'check zdiff3 markers' ' +test_expect_success 'check zdiff3 markers' ' test_setup_zdiff3 && ( cd zdiff3 && @@ -251,6 +254,14 @@ test_expect_failure 'check zdiff3 markers' ' test_must_fail git -c merge.conflictstyle=zdiff3 merge -s recursive right^0 && + test_write_lines \ + 1 2 3 4 \ + "<<<<<<< HEAD" X A \ + "||||||| $(git rev-parse --short HEAD^1)" 5 6 ======= \ + Y A B C ">>>>>>> right^0" \ + B C 7 8 9 >expect && + test_cmp expect evil && + 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 && test_cmp expect basic &&
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?
On Wed, Sep 15, 2021 at 4:22 AM Phillip Wood <phillip.wood123@gmail.com> wrote: > > On 15/09/2021 11:25, Phillip Wood wrote: > > 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(). > > Here is an evil test case that shows this problem (diff on top of your patch) > > > diff --git a/t/t6427-diff3-conflict-markers.sh b/t/t6427-diff3-conflict-markers.sh > index de9c6190b9..836843c6b0 100755 > --- a/t/t6427-diff3-conflict-markers.sh > +++ b/t/t6427-diff3-conflict-markers.sh > @@ -219,8 +219,9 @@ test_setup_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 && > + test_write_lines 1 2 3 4 5 6 7 8 9 >evil && > > - git add basic middle-common && > + git add basic middle-common interesting evil && > git commit -m base && > > git branch left && > @@ -230,19 +231,21 @@ test_setup_zdiff3 () { > 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 && > + test_write_lines 1 2 3 4 X A B C 7 8 9 >evil && > 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 && > + test_write_lines 1 2 3 4 Y A B C B C 7 8 9 >evil && > git add -u && > git commit -m permuted > ) > } > > -test_expect_failure 'check zdiff3 markers' ' > +test_expect_success 'check zdiff3 markers' ' ...except your new testcase makes it fail. > test_setup_zdiff3 && > ( > cd zdiff3 && > @@ -251,6 +254,14 @@ test_expect_failure 'check zdiff3 markers' ' > > test_must_fail git -c merge.conflictstyle=zdiff3 merge -s recursive right^0 && > > + test_write_lines \ > + 1 2 3 4 \ > + "<<<<<<< HEAD" X A \ > + "||||||| $(git rev-parse --short HEAD^1)" 5 6 ======= \ > + Y A B C ">>>>>>> right^0" \ > + B C 7 8 9 >expect && > + test_cmp expect evil && > + Yeah, this is an interesting testcase, and I agree with the 'expect' choice you wrote, but the current code doesn't produce it. I'll update the patches and send out another round, and then do you want to try your xdl_recmatch() magic to fix this testcase?
On 18/09/2021 23:06, Elijah Newren wrote: > On Wed, Sep 15, 2021 at 4:22 AM Phillip Wood <phillip.wood123@gmail.com> wrote: >> >> On 15/09/2021 11:25, Phillip Wood wrote: >>> 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(). >> >> Here is an evil test case that shows this problem (diff on top of your patch) >> >> >> diff --git a/t/t6427-diff3-conflict-markers.sh b/t/t6427-diff3-conflict-markers.sh >> index de9c6190b9..836843c6b0 100755 >> --- a/t/t6427-diff3-conflict-markers.sh >> +++ b/t/t6427-diff3-conflict-markers.sh >> @@ -219,8 +219,9 @@ test_setup_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 && >> + test_write_lines 1 2 3 4 5 6 7 8 9 >evil && >> >> - git add basic middle-common && >> + git add basic middle-common interesting evil && >> git commit -m base && >> >> git branch left && >> @@ -230,19 +231,21 @@ test_setup_zdiff3 () { >> 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 && >> + test_write_lines 1 2 3 4 X A B C 7 8 9 >evil && >> 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 && >> + test_write_lines 1 2 3 4 Y A B C B C 7 8 9 >evil && >> git add -u && >> git commit -m permuted >> ) >> } >> >> -test_expect_failure 'check zdiff3 markers' ' >> +test_expect_success 'check zdiff3 markers' ' > > ...except your new testcase makes it fail. Sorry I meant to remove that, I'd changed it to test_expect_success so I could poke about in the test repo when it failed. Best Wishes Phillip > >> test_setup_zdiff3 && >> ( >> cd zdiff3 && >> @@ -251,6 +254,14 @@ test_expect_failure 'check zdiff3 markers' ' >> >> test_must_fail git -c merge.conflictstyle=zdiff3 merge -s recursive right^0 && >> >> + test_write_lines \ >> + 1 2 3 4 \ >> + "<<<<<<< HEAD" X A \ >> + "||||||| $(git rev-parse --short HEAD^1)" 5 6 ======= \ >> + Y A B C ">>>>>>> right^0" \ >> + B C 7 8 9 >expect && >> + test_cmp expect evil && >> + > > Yeah, this is an interesting testcase, and I agree with the 'expect' > choice you wrote, but the current code doesn't produce it. I'll > update the patches and send out another round, and then do you want to > try your xdl_recmatch() magic to fix this testcase? >
Hi Elijah On 18/09/2021 23:04, Elijah Newren wrote: > Hi Phillip, > [...] >> 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? I could do if you really want but I wont have time to do anything for at least a couple of weeks (I really need to get on top of my current series before starting anything new). I outlined the rough idea in [1]. tldr; instead of diffing the two sides of the conflict just walk the start and the end of the two sides until we find a line that does not match. Best Wishes Phillip [1] https://lore.kernel.org/git/f76c79d6-f280-3011-d88d-6de146977626@gmail.com/
diff --git a/builtin/merge-file.c b/builtin/merge-file.c index 06a2f90c487..e695867ee54 100644 --- a/builtin/merge-file.c +++ b/builtin/merge-file.c @@ -34,6 +34,8 @@ int cmd_merge_file(int argc, const char **argv, const char *prefix) struct option options[] = { OPT_BOOL('p', "stdout", &to_stdout, N_("send results to standard output")), OPT_SET_INT(0, "diff3", &xmp.style, N_("use a diff3 based merge"), XDL_MERGE_DIFF3), + OPT_SET_INT(0, "zdiff3", &xmp.style, N_("use a zealous diff3 based merge"), + XDL_MERGE_ZEALOUS_DIFF3), OPT_SET_INT(0, "ours", &xmp.favor, N_("for conflicts, use our version"), XDL_MERGE_FAVOR_OURS), OPT_SET_INT(0, "theirs", &xmp.favor, N_("for conflicts, use their version"), diff --git a/contrib/completion/git-completion.bash b/contrib/completion/git-completion.bash index b50c5d0ea38..8489ca39497 100644 --- a/contrib/completion/git-completion.bash +++ b/contrib/completion/git-completion.bash @@ -1566,7 +1566,7 @@ _git_checkout () case "$cur" in --conflict=*) - __gitcomp "diff3 merge" "" "${cur##--conflict=}" + __gitcomp "diff3 merge zdiff3" "" "${cur##--conflict=}" ;; --*) __gitcomp_builtin checkout @@ -2445,7 +2445,7 @@ _git_switch () case "$cur" in --conflict=*) - __gitcomp "diff3 merge" "" "${cur##--conflict=}" + __gitcomp "diff3 merge zdiff3" "" "${cur##--conflict=}" ;; --*) __gitcomp_builtin switch @@ -2886,7 +2886,7 @@ _git_restore () case "$cur" in --conflict=*) - __gitcomp "diff3 merge" "" "${cur##--conflict=}" + __gitcomp "diff3 merge zdiff3" "" "${cur##--conflict=}" ;; --source=*) __git_complete_refs --cur="${cur##--source=}" 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 && + git commit -m base && + + 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 && + 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 && + test_cmp expect interesting + ) +' + test_done diff --git a/xdiff-interface.c b/xdiff-interface.c index 609615db2cd..9977813a9d3 100644 --- a/xdiff-interface.c +++ b/xdiff-interface.c @@ -308,6 +308,8 @@ int git_xmerge_config(const char *var, const char *value, void *cb) die("'%s' is not a boolean", var); if (!strcmp(value, "diff3")) git_xmerge_style = XDL_MERGE_DIFF3; + else if (!strcmp(value, "zdiff3")) + git_xmerge_style = XDL_MERGE_ZEALOUS_DIFF3; else if (!strcmp(value, "merge")) git_xmerge_style = 0; /* diff --git a/xdiff/xdiff.h b/xdiff/xdiff.h index 7a046051468..8629ae287c7 100644 --- a/xdiff/xdiff.h +++ b/xdiff/xdiff.h @@ -65,6 +65,7 @@ extern "C" { /* merge output styles */ #define XDL_MERGE_DIFF3 1 +#define XDL_MERGE_ZEALOUS_DIFF3 2 typedef struct s_mmfile { char *ptr; diff --git a/xdiff/xmerge.c b/xdiff/xmerge.c index 1659edb4539..df0c6041778 100644 --- a/xdiff/xmerge.c +++ b/xdiff/xmerge.c @@ -230,7 +230,7 @@ static int fill_conflict_hunk(xdfenv_t *xe1, const char *name1, size += xdl_recs_copy(xe1, m->i1, m->chg1, needs_cr, 1, dest ? dest + size : NULL); - if (style == XDL_MERGE_DIFF3) { + if (style == XDL_MERGE_DIFF3 || style == XDL_MERGE_ZEALOUS_DIFF3) { /* Shared preimage */ if (!dest) { size += marker_size + 1 + needs_cr + marker3_size; @@ -327,7 +327,7 @@ static int xdl_fill_merge_buffer(xdfenv_t *xe1, const char *name1, * lines. Try hard to show only these few lines as conflicting. */ static int xdl_refine_conflicts(xdfenv_t *xe1, xdfenv_t *xe2, xdmerge_t *m, - xpparam_t const *xpp) + xpparam_t const *xpp, int style) { for (; m; m = m->next) { mmfile_t t1, t2; @@ -368,6 +368,42 @@ static int xdl_refine_conflicts(xdfenv_t *xe1, xdfenv_t *xe2, xdmerge_t *m, continue; } x = xscr; + if (style == XDL_MERGE_ZEALOUS_DIFF3) { + int advance1 = xscr->i1, advance2 = xscr->i2; + + /* + * Advance m->i1 and m->i2 so that conflict for sides + * 1 and 2 start after common region. Decrement + * m->chg[12] since there are now fewer conflict lines + * for those sides. + */ + m->i1 += advance1; + m->i2 += advance2; + m->chg1 -= advance1; + m->chg2 -= advance2; + + /* + * Splitting conflicts due to internal common regions + * on the two sides would be inappropriate since we + * are also showing the merge base and have no + * reasonable way to split the merge base text. + */ + while (xscr->next) + xscr = xscr->next; + + /* + * Lower the number of conflict lines to not include + * the final common lines, if any. Do this by setting + * number of conflict lines to + * (line offset for start of conflict in xscr) + + * (number of lines in the conflict in xscr) + */ + m->chg1 = (xscr->i1 - advance1) + (xscr->chg1); + m->chg2 = (xscr->i2 - advance2) + (xscr->chg2); + xdl_free_env(&xe); + xdl_free_script(x); + continue; + } m->i1 = xscr->i1 + i1; m->chg1 = xscr->chg1; m->i2 = xscr->i2 + i2; @@ -419,6 +455,7 @@ static int lines_contain_alnum(xdfenv_t *xe, int i, int chg) static void xdl_merge_two_conflicts(xdmerge_t *m) { xdmerge_t *next_m = m->next; + m->chg0 = next_m->i0 + next_m->chg0 - m->i0; m->chg1 = next_m->i1 + next_m->chg1 - m->i1; m->chg2 = next_m->i2 + next_m->chg2 - m->i2; m->next = next_m->next; @@ -430,12 +467,12 @@ static void xdl_merge_two_conflicts(xdmerge_t *m) * it appears simpler -- because it takes up less (or as many) lines -- * if the lines are moved into the conflicts. */ -static int xdl_simplify_non_conflicts(xdfenv_t *xe1, xdmerge_t *m, +static int xdl_simplify_non_conflicts(xdfenv_t *xe1, xdmerge_t *m, int style, int simplify_if_no_alnum) { int result = 0; - if (!m) + if (!m || style == XDL_MERGE_ZEALOUS_DIFF3) return result; for (;;) { xdmerge_t *next_m = m->next; @@ -482,6 +519,25 @@ static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1, int style = xmp->style; int favor = xmp->favor; + /* + * XDL_MERGE_DIFF3 does not attempt to refine conflicts by looking + * at common areas of sides 1 & 2, because the base (side 0) does + * not match and is being shown. Similarly, simplification of + * non-conflicts is also skipped due to the skipping of conflict + * refinement. + * + * XDL_MERGE_ZEALOUS_DIFF3, on the other hand, will attempt to + * refine conflicts looking for common areas of sides 1 & 2. + * However, since the base is being shown and does not match, + * it will only look for common areas at the beginning or end + * of the conflict block. Since XDL_MERGE_ZEALOUS_DIFF3's + * conflict refinement is much more limited in this fashion, the + * conflict simplification will be skipped. + * + * See xdl_refine_conflicts() and xdl_simplify_non_conflicts() + * for more details, particularly looking for + * XDL_MERGE_ZEALOUS_DIFF3. + */ if (style == XDL_MERGE_DIFF3) { /* * "diff3 -m" output does not make sense for anything @@ -604,8 +660,8 @@ static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1, changes = c; /* refine conflicts */ if (XDL_MERGE_ZEALOUS <= level && - (xdl_refine_conflicts(xe1, xe2, changes, xpp) < 0 || - xdl_simplify_non_conflicts(xe1, changes, + (xdl_refine_conflicts(xe1, xe2, changes, xpp, style) < 0 || + xdl_simplify_non_conflicts(xe1, changes, style, XDL_MERGE_ZEALOUS < level) < 0)) { xdl_cleanup_merge(changes); return -1;