[PATCH] xdiff: implement a zealous diff3

From: Uwe Kleine-König <redacted>

"zdiff3" is identical to ordinary diff3, only it allows more aggressive
compaction than diff3. This way the displayed base isn't necessary
technically correct, but still this mode might help resolving merge
conflicts between two near identical additions.

Signed-off-by: Uwe Kleine-König <redacted>
---

I'm re-sending this patch from 2013 because I do think it provides value
and we might want to make it the default.

I hardcoded diff3 to be zdiff3 and all the tests passed, so if our tests
don't care about the simplification level of diff3 perhaps many (or even
most) our users don't either.

FTR: this patch applied cleanly.

 builtin/merge-file.c                   | 2 ++
 contrib/completion/git-completion.bash | 2 +-
 xdiff-interface.c                      | 2 ++
 xdiff/xdiff.h                          | 1 +
 xdiff/xmerge.c                         | 8 +++++++-
 5 files changed, 13 insertions(+), 2 deletions(-)

diff --git a/builtin/merge-file.c b/builtin/merge-file.c
index 06a2f90c48..e695867ee5 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 b50c5d0ea3..8594559298 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

diff --git a/xdiff-interface.c b/xdiff-interface.c
index 609615db2c..9977813a9d 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 7a04605146..8629ae287c 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 1659edb453..95871a0b6e 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;

@@ -482,6 +482,12 @@ static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1,
 	int style = xmp->style;
 	int favor = xmp->favor;
 
+	/*
+	 * This is the only change between XDL_MERGE_DIFF3 and
+	 * XDL_MERGE_ZEALOUS_DIFF3. "zdiff3" isn't 100% technically correct (as
+	 * the base might be considerably simplified), but still it might help
+	 * interpreting conflicts between two big and near identical additions.
+	 */
 	if (style == XDL_MERGE_DIFF3) {
 		/*
 		 * "diff3 -m" output does not make sense for anything

-- 
2.32.0

On Sun, Jun 13, 2021 at 09:31:55AM -0500, Felipe Contreras wrote:

From: Uwe Kleine-König <redacted>

"zdiff3" is identical to ordinary diff3, only it allows more aggressive
compaction than diff3. This way the displayed base isn't necessary
technically correct, but still this mode might help resolving merge
conflicts between two near identical additions.

Signed-off-by: Uwe Kleine-König <redacted>
---

I'm re-sending this patch from 2013 because I do think it provides value
and we might want to make it the default.

I take it you didn't investigate the segfault I mentioned.

Try this:

   commit=a5170794372cf1325710a3419473c91ec4af53bf
   for style in merge diff3 zdiff3; do
     git reset --hard
     git checkout $commit^1
     git -c merge.conflictstyle=$style merge $commit^2
   done

The first two are fine; the zdiff3 one segfaults within the xmerge.c
code.

-Peff

Jeff King wrote:

On Sun, Jun 13, 2021 at 09:31:55AM -0500, Felipe Contreras wrote:

quoted

From: Uwe Kleine-König <redacted>

"zdiff3" is identical to ordinary diff3, only it allows more aggressive
compaction than diff3. This way the displayed base isn't necessary
technically correct, but still this mode might help resolving merge
conflicts between two near identical additions.

Signed-off-by: Uwe Kleine-König <redacted>
---

I'm re-sending this patch from 2013 because I do think it provides value
and we might want to make it the default.

I take it you didn't investigate the segfault I mentioned.

I don't know how I was supposed to investigate the few segfaults you
mentioned. All you said is that you never tracked the bug.

Try this:

   commit=a5170794372cf1325710a3419473c91ec4af53bf
   for style in merge diff3 zdiff3; do
     git reset --hard
     git checkout $commit^1
     git -c merge.conflictstyle=$style merge $commit^2
   done

The first two are fine; the zdiff3 one segfaults within the xmerge.c
code.

I can reproduct the segfault, and here is a simpler way to reproduce it:

(I have a hacked version of diff3 until merge-file learns how to use
merge.conflictstyle)

  cat >b <<EOF
  A
  EOF

  cat >l <<EOF
  A

  B
  C
  D
  E
  F
  GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG
  H
  I
  EOF

  cat >r <<EOF
  A

  b
  C
  D
  E
  F
  GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG
  H
  i
  EOF

  $git merge-file --diff3 -p l b r

-- 
Felipe Contreras

Felipe Contreras wrote:

Jeff King wrote:

quoted

Try this:

   commit=a5170794372cf1325710a3419473c91ec4af53bf
   for style in merge diff3 zdiff3; do
     git reset --hard
     git checkout $commit^1
     git -c merge.conflictstyle=$style merge $commit^2
   done

The first two are fine; the zdiff3 one segfaults within the xmerge.c
code.

I can reproduct the segfault, and here is a simpler way to reproduce it:

I found the problem, m->chg0 was not initialized in xdl_refine_conflicts.

I'm not familiar with the area so I don't know if the following makes
sense, but it fixes the crash:

--- a/xdiff/xmerge.c
+++ b/xdiff/xmerge.c

@@ -333,7 +333,7 @@ static int xdl_refine_conflicts(xdfenv_t *xe1, xdfenv_t *xe2, xdmerge_t *m,
                mmfile_t t1, t2;
                xdfenv_t xe;
                xdchange_t *xscr, *x;
-               int i1 = m->i1, i2 = m->i2;
+               int i0 = m->i0, i1 = m->i1, i2 = m->i2;
 
                /* let's handle just the conflicts */
                if (m->mode)

@@ -384,6 +384,8 @@ static int xdl_refine_conflicts(xdfenv_t *xe1, xdfenv_t *xe2, xdmerge_t *m,
                        m->next = m2;
                        m = m2;
                        m->mode = 0;
+                       m->i0 = i0;
+                       m->chg0 = 0;
                        m->i1 = xscr->i1 + i1;
                        m->chg1 = xscr->chg1;
                        m->i2 = xscr->i2 + i2;

-- 
Felipe Contreras

On Sun, Jun 13, 2021 at 01:00:33PM -0500, Felipe Contreras wrote:

quoted

quoted

I'm re-sending this patch from 2013 because I do think it provides value
and we might want to make it the default.

I take it you didn't investigate the segfault I mentioned.

I don't know how I was supposed to investigate the few segfaults you
mentioned. All you said is that you never tracked the bug.

My point is that if you are going to repost a patch that has known
problems, it is worth saying so to give reviewers and the maintainer a
realistic idea of how stable it is.

I also didn't have a reproduction recipe. I found the commit I sent by
just re-running every merge in git.git in a loop.

It sounds like you have a smaller reproduction and maybe a fix, which is
good.

-Peff

Jeff King wrote:

On Sun, Jun 13, 2021 at 01:00:33PM -0500, Felipe Contreras wrote:

quoted

quoted

quoted

I'm re-sending this patch from 2013 because I do think it provides value
and we might want to make it the default.

I take it you didn't investigate the segfault I mentioned.

I don't know how I was supposed to investigate the few segfaults you
mentioned. All you said is that you never tracked the bug.

My point is that if you are going to repost a patch that has known
problems,

It was not known that it had problems.

That fact that person X said patch Y had a problem doesn't necessarily
mean that patch Y has a problem.

  1. The problem in the past might not apply in the present
  2. The problem X person had might be specific to his/her setup
  3. The problem might be due a combination of patches, not the patch
     itself

Plus many others.

A logical person sees evidence for what it is, and the only thing that
person X saying patch Y had a problem means, is that person X said patch
Y had a problem.

-- 
Felipe Contreras

On Mon, Jun 14, 2021 at 11:19:46PM -0500, Felipe Contreras wrote:

quoted

My point is that if you are going to repost a patch that has known
problems,

It was not known that it had problems.

That fact that person X said patch Y had a problem doesn't necessarily
mean that patch Y has a problem.

  1. The problem in the past might not apply in the present
  2. The problem X person had might be specific to his/her setup
  3. The problem might be due a combination of patches, not the patch
     itself

Plus many others.

A logical person sees evidence for what it is, and the only thing that
person X saying patch Y had a problem means, is that person X said patch
Y had a problem.

Wow.

For one thing, you could still relay the _report_ of a problem along
with the patch, which would be valuable information for reviewers.

But much more important, in my opinion: that you would dismiss without
further investigation a report of a bug from the one person who actually
had experience running with the patch implies a level of carelessness
that I'm not comfortable with for the project.

I had already given up on having substantive discussion with you, but I
had hoped I could help the project by pointing out relevant facts in
areas that you were working in. But if a simple statement like "this
segfaulted for me" is not even useful, then I don't see much point in
communicating with you at all.

-Peff

Jeff King wrote:

On Mon, Jun 14, 2021 at 11:19:46PM -0500, Felipe Contreras wrote:

quoted

quoted

My point is that if you are going to repost a patch that has known
problems,

It was not known that it had problems.

That fact that person X said patch Y had a problem doesn't necessarily
mean that patch Y has a problem.

  1. The problem in the past might not apply in the present
  2. The problem X person had might be specific to his/her setup
  3. The problem might be due a combination of patches, not the patch
     itself

Plus many others.

A logical person sees evidence for what it is, and the only thing that
person X saying patch Y had a problem means, is that person X said patch
Y had a problem.

Wow.

For one thing, you could still relay the _report_ of a problem along
with the patch, which would be valuable information for reviewers.

Yes I could have, and knowing what I know now I wouldn't even have even
posted the patch (not without a proposed fix). Woulda, coulda, shoulda.

But that's not the point. The point is that I did not repost a patch with
known problems *today*. Nor did I know what kind of problems, or
how pervasive the issue was.

Presumably you had to try at least 2,500 merges to find *one* issue.

I ran all the tests for diff3 with zdiff3 and they passed without
problems.


Merging this patch would have:

 1. Not broken any tests
 2. Not changed any behavior for any user
 3. Not have caused any problem for the vast majority (> 99%) of
    people trying out zdiff3

So there was no carelessness here.

Moreover, I provied the patch at 9:30, at 10:42 you commented about the
segfault, and 16:24 I had the fix. On a Sunday.

If this is not caring, I don't know what is.

-- 
Felipe Contreras