[PATCH 0/2] RFC: implement new zdiff3 conflict style

[PATCH 0/2] RFC: implement new zdiff3 conflict style

[Elijah Newren via GitGitGadget]

Implement a zealous diff3, or "zdiff3". This new mode is identical to
ordinary diff3 except that it allows compaction of common lines between the
two sides of history, if those common lines occur at the beginning or end of
a conflict hunk.

This is just RFC, because I need to add tests. Also, while I've remerged
every merge, revert, or duly marked cherry-pick from both git.git and
linux.git with this patch using the new zdiff3 mode, that only shows it
doesn't segfault. (Though I also reran 10% of the linux remerges with zdiff3
under valgrind without issues.) I looked through some differences between
--remerge-diff with diff3 and --remerge-diff with zdiff3, but those are
essentially diffs of a diff of a diff, which I found hard to read. I'd like
to look through more examples, and use it for a while before submitting the
patches without the RFC tag.

Elijah Newren (2):
  xdiff: implement a zealous diff3, or "zdiff3"
  update documentation for new zdiff3 conflictStyle

 Documentation/config/merge.txt         |  9 ++++-
 Documentation/git-checkout.txt         |  3 +-
 Documentation/git-merge-file.txt       |  3 ++
 Documentation/git-merge.txt            | 32 +++++++++++++---
 Documentation/git-rebase.txt           |  6 +--
 Documentation/git-restore.txt          |  3 +-
 Documentation/git-switch.txt           |  3 +-
 Documentation/technical/rerere.txt     | 10 ++---
 builtin/checkout.c                     |  2 +-
 builtin/merge-file.c                   |  2 +
 contrib/completion/git-completion.bash |  6 +--
 xdiff-interface.c                      |  2 +
 xdiff/xdiff.h                          |  1 +
 xdiff/xmerge.c                         | 52 ++++++++++++++++++++++++--
 14 files changed, 107 insertions(+), 27 deletions(-)


base-commit: 670b81a890388c60b7032a4f5b879f2ece8c4558
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1036%2Fnewren%2Fzdiff3-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1036/newren/zdiff3-v1
Pull-Request: https://github.com/git/git/pull/1036
-- 
gitgitgadget

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

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

"zdiff3" is identical to ordinary diff3 except that it allows compaction
of common lines on the two sides of history at the beginning or end of
the conflict hunk.  For example, the following diff3 conflict:

    1
    2
    3
    4
    <<<<<<
    A
    B
    C
    D
    E
    ||||||
    5
    6
    ======
    A
    X
    C
    Y
    E
    >>>>>>
    7
    8
    9

has common lines 'A', 'C', and 'E' on the two sides.  With zdiff3, one
would instead get the following conflict:

    1
    2
    3
    4
    A
    <<<<<<
    B
    C
    D
    ||||||
    5
    6
    ======
    X
    C
    Y
    >>>>>>
    E
    7
    8
    9

Note that the common lines, 'A', and 'E' were moved outside the
conflict.  Unlike with the two-way conflicts from the 'merge'
conflictStyle, the zdiff3 conflict is NOT split into multiple conflict
regions to allow the common 'C' lines to be shown outside a conflict,
because zdiff3 shows the base version too and the base version cannot be
reasonably split.

Initial-patch-by: Uwe Kleine-König <u.kleine-koenig@pengutronix.de>
Signed-off-by: Elijah Newren <newren@gmail.com>
---
 builtin/merge-file.c                   |  2 +
 contrib/completion/git-completion.bash |  2 +-
 xdiff-interface.c                      |  2 +
 xdiff/xdiff.h                          |  1 +
 xdiff/xmerge.c                         | 52 ++++++++++++++++++++++++--
 5 files changed, 55 insertions(+), 4 deletions(-)

diff --git a/builtin/merge-file.c b/builtin/merge-file.c
index 06a2f90c4875..e695867ee548 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 b50c5d0ea386..859455929814 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 609615db2cd6..9977813a9d37 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 7a046051468f..8629ae287c79 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 1659edb45393..b1dc9df7ea0a 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;
@@ -482,6 +518,16 @@ 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.
+	 *
+	 * XDL_MERGE_ZEALOUS_DIFF3 will attempt to refine conflicts
+	 * looking for common areas of sides 1 & 2, despite the base
+	 * not matching and being shown, but will only look for common
+	 * areas at the beginning or ending of the conflict block.
+	 */
 	if (style == XDL_MERGE_DIFF3) {
 		/*
 		 * "diff3 -m" output does not make sense for anything
@@ -604,7 +650,7 @@ 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_refine_conflicts(xe1, xe2, changes, xpp, style) < 0 ||
 	     xdl_simplify_non_conflicts(xe1, changes,
 					XDL_MERGE_ZEALOUS < level) < 0)) {
 		xdl_cleanup_merge(changes);
-- 
gitgitgadget

[PATCH 2/2] update documentation for new zdiff3 conflictStyle

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 Documentation/config/merge.txt         |  9 +++++++-
 Documentation/git-checkout.txt         |  3 +--
 Documentation/git-merge-file.txt       |  3 +++
 Documentation/git-merge.txt            | 32 ++++++++++++++++++++++----
 Documentation/git-rebase.txt           |  6 ++---
 Documentation/git-restore.txt          |  3 +--
 Documentation/git-switch.txt           |  3 +--
 Documentation/technical/rerere.txt     | 10 ++++----
 builtin/checkout.c                     |  2 +-
 contrib/completion/git-completion.bash |  4 ++--
 10 files changed, 52 insertions(+), 23 deletions(-)

diff --git a/Documentation/config/merge.txt b/Documentation/config/merge.txt
index cb2ed589075b..7ab289f35c7f 100644
--- a/Documentation/config/merge.txt
+++ b/Documentation/config/merge.txt
@@ -4,7 +4,14 @@ merge.conflictStyle::
 	shows a `<<<<<<<` conflict marker, changes made by one side,
 	a `=======` marker, changes made by the other side, and then
 	a `>>>>>>>` marker.  An alternate style, "diff3", adds a `|||||||`
-	marker and the original text before the `=======` marker.
+	marker and the original text before the `=======` marker.  The
+	"merge" style tends to produce smaller conflict regions than diff3,
+	both because of the exclusion of the original text, and because
+	when a subset of lines match on the two sides they are just pulled
+	out of the conflict region.  Another alternate style, "zdiff3", is
+	similar to diff3 but removes matching lines on the two sides from
+	the conflict region when those matching lines appear near the
+	beginning or ending of a conflict region.
 
 merge.defaultToUpstream::
 	If merge is called without any commit argument, merge the upstream
diff --git a/Documentation/git-checkout.txt b/Documentation/git-checkout.txt
index b1a6fe449973..85c3d3513f74 100644
--- a/Documentation/git-checkout.txt
+++ b/Documentation/git-checkout.txt
@@ -265,8 +265,7 @@ When switching branches with `--merge`, staged changes may be lost.
 	The same as `--merge` option above, but changes the way the
 	conflicting hunks are presented, overriding the
 	`merge.conflictStyle` configuration variable.  Possible values are
-	"merge" (default) and "diff3" (in addition to what is shown by
-	"merge" style, shows the original contents).
+	"merge" (default), "diff3", and "zdiff3".
 
 -p::
 --patch::
diff --git a/Documentation/git-merge-file.txt b/Documentation/git-merge-file.txt
index f85603261325..7e9093fab60d 100644
--- a/Documentation/git-merge-file.txt
+++ b/Documentation/git-merge-file.txt
@@ -70,6 +70,9 @@ OPTIONS
 --diff3::
 	Show conflicts in "diff3" style.
 
+--zdiff3::
+	Show conflicts in "zdiff3" style.
+
 --ours::
 --theirs::
 --union::
diff --git a/Documentation/git-merge.txt b/Documentation/git-merge.txt
index 3819fadac1f1..259e1ac2cf0c 100644
--- a/Documentation/git-merge.txt
+++ b/Documentation/git-merge.txt
@@ -238,7 +238,8 @@ from the RCS suite to present such a conflicted hunk, like this:
 
 ------------
 Here are lines that are either unchanged from the common
-ancestor, or cleanly resolved because only one side changed.
+ancestor, or cleanly resolved because only one side changed,
+or cleanly resolved because both sides changed the same way.
 <<<<<<< yours:sample.txt
 Conflict resolution is hard;
 let's go shopping.
@@ -259,16 +260,37 @@ side wants to say it is hard and you'd prefer to go shopping, while the
 other side wants to claim it is easy.
 
 An alternative style can be used by setting the "merge.conflictStyle"
-configuration variable to "diff3".  In "diff3" style, the above conflict
-may look like this:
+configuration variable to either "diff3" or "zdiff3".  In "diff3"
+style, the above conflict may look like this:
 
 ------------
 Here are lines that are either unchanged from the common
-ancestor, or cleanly resolved because only one side changed.
+ancestor, or cleanly resolved because only one side changed,
 <<<<<<< yours:sample.txt
+or cleanly resolved because both sides changed the same way.
 Conflict resolution is hard;
 let's go shopping.
-|||||||
+||||||| base:sample.txt
+or cleanly resolved because both sides changed identically.
+Conflict resolution is hard.
+=======
+or cleanly resolved because both sides changed the same way.
+Git makes conflict resolution easy.
+>>>>>>> theirs:sample.txt
+And here is another line that is cleanly resolved or unmodified.
+------------
+
+while in "zdiff3" style, it may look like this:
+
+------------
+Here are lines that are either unchanged from the common
+ancestor, or cleanly resolved because only one side changed,
+or cleanly resolved because both sides changed the same way.
+<<<<<<< yours:sample.txt
+Conflict resolution is hard;
+let's go shopping.
+||||||| base:sample.txt
+or cleanly resolved because both sides changed identically.
 Conflict resolution is hard.
 =======
 Git makes conflict resolution easy.
diff --git a/Documentation/git-rebase.txt b/Documentation/git-rebase.txt
index 55af6fd24e27..a61742c8f98f 100644
--- a/Documentation/git-rebase.txt
+++ b/Documentation/git-rebase.txt
@@ -740,9 +740,9 @@ information about the rebased commits and their parents (and instead
 generates new fake commits based off limited information in the
 generated patches), those commits cannot be identified; instead it has
 to fall back to a commit summary.  Also, when merge.conflictStyle is
-set to diff3, the apply backend will use "constructed merge base" to
-label the content from the merge base, and thus provide no information
-about the merge base commit whatsoever.
+set to diff3 or zdiff3, the apply backend will use "constructed merge
+base" to label the content from the merge base, and thus provide no
+information about the merge base commit whatsoever.
 
 The merge backend works with the full commits on both sides of history
 and thus has no such limitations.
diff --git a/Documentation/git-restore.txt b/Documentation/git-restore.txt
index 55bde91ef9e5..5964810caa41 100644
--- a/Documentation/git-restore.txt
+++ b/Documentation/git-restore.txt
@@ -92,8 +92,7 @@ in linkgit:git-checkout[1] for details.
 	The same as `--merge` option above, but changes the way the
 	conflicting hunks are presented, overriding the
 	`merge.conflictStyle` configuration variable.  Possible values
-	are "merge" (default) and "diff3" (in addition to what is
-	shown by "merge" style, shows the original contents).
+	are "merge" (default), "diff3", and "zdiff3".
 
 --ignore-unmerged::
 	When restoring files on the working tree from the index, do
diff --git a/Documentation/git-switch.txt b/Documentation/git-switch.txt
index 5c438cd50587..5c90f76fbe35 100644
--- a/Documentation/git-switch.txt
+++ b/Documentation/git-switch.txt
@@ -137,8 +137,7 @@ should result in deletion of the path).
 	The same as `--merge` option above, but changes the way the
 	conflicting hunks are presented, overriding the
 	`merge.conflictStyle` configuration variable.  Possible values are
-	"merge" (default) and "diff3" (in addition to what is shown by
-	"merge" style, shows the original contents).
+	"merge" (default), "diff3", and "zdiff3".
 
 -q::
 --quiet::
diff --git a/Documentation/technical/rerere.txt b/Documentation/technical/rerere.txt
index af5f9fc24f93..35d454143399 100644
--- a/Documentation/technical/rerere.txt
+++ b/Documentation/technical/rerere.txt
@@ -14,9 +14,9 @@ conflicts before writing them to the rerere database.
 
 Different conflict styles and branch names are normalized by stripping
 the labels from the conflict markers, and removing the common ancestor
-version from the `diff3` conflict style. Branches that are merged
-in different order are normalized by sorting the conflict hunks.  More
-on each of those steps in the following sections.
+version from the `diff3` or `zdiff3` conflict styles.  Branches that
+are merged in different order are normalized by sorting the conflict
+hunks.  More on each of those steps in the following sections.
 
 Once these two normalization operations are applied, a conflict ID is
 calculated based on the normalized conflict, which is later used by
@@ -42,8 +42,8 @@ get a conflict like the following:
     >>>>>>> AC
 
 Doing the analogous with AC2 (forking a branch ABAC2 off of branch AB
-and then merging branch AC2 into it), using the diff3 conflict style,
-we get a conflict like the following:
+and then merging branch AC2 into it), using the diff3 or zdiff3
+conflict style, we get a conflict like the following:
 
     <<<<<<< HEAD
     B
diff --git a/builtin/checkout.c b/builtin/checkout.c
index f4cd7747d35d..45606936c328 100644
--- a/builtin/checkout.c
+++ b/builtin/checkout.c
@@ -1524,7 +1524,7 @@ static struct option *add_common_options(struct checkout_opts *opts,
 		OPT_BOOL(0, "progress", &opts->show_progress, N_("force progress reporting")),
 		OPT_BOOL('m', "merge", &opts->merge, N_("perform a 3-way merge with the new branch")),
 		OPT_STRING(0, "conflict", &opts->conflict_style, N_("style"),
-			   N_("conflict style (merge or diff3)")),
+			   N_("conflict style (merge, diff3, or zdiff3)")),
 		OPT_END()
 	};
 	struct option *newopts = parse_options_concat(prevopts, options);
diff --git a/contrib/completion/git-completion.bash b/contrib/completion/git-completion.bash
index 859455929814..8489ca394970 100644
--- a/contrib/completion/git-completion.bash
+++ b/contrib/completion/git-completion.bash
@@ -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=}"
-- 
gitgitgadget

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

[Junio C Hamano]

"Elijah Newren via GitGitGadget" <gitgitgadget@gmail.com> writes:

[An example to reduce
    1234<ABCDE|56=AXCYE>789
to
    1234A<BCD|56=XCY>E789
elided]

> Note that the common lines, 'A', and 'E' were moved outside the
> conflict.  Unlike with the two-way conflicts from the 'merge'
> conflictStyle, the zdiff3 conflict is NOT split into multiple conflict
> regions to allow the common 'C' lines to be shown outside a conflict,
> because zdiff3 shows the base version too and the base version cannot be
> reasonably split.

Another thing that was brought up during the original discussion is
that zdiff3 uses different meaning of "base version" from diff3.  In
diff3 output, if you remove everything enclosed in <<< and |||, and
everything enclosed in === and >>>, i.e. 123456789 in the original
example above, you will get "the common ancestor" version, which is
what is shown as the "base".  After zdiff3 munges the lines, that is
not the case, 1234A56E789 never appeared in anybody's version.  It
is a "starting from the common ancestor version, both sides agreed
to make the same uncontroversial changes, which is already included
in this base version" and zdiff3 inserts the conflict markers and
material unique to each side into it.  Being able to recover the
common ancestor version is not always necessary and that is what
makes zdiff3 a plausible solution, but to some workflows and tools
it may matter, so it would be helpful to mention it in the
documentation.

Thanks.

Re: [PATCH 2/2] update documentation for new zdiff3 conflictStyle

[Junio C Hamano]

"Elijah Newren via GitGitGadget" <gitgitgadget@gmail.com> writes:

> +	marker and the original text before the `=======` marker.  The
> +	"merge" style tends to produce smaller conflict regions than diff3,
> +	both because of the exclusion of the original text, and because
> +	when a subset of lines match on the two sides they are just pulled
> +	out of the conflict region.  Another alternate style, "zdiff3", is
> +	similar to diff3 but removes matching lines on the two sides from
> +	the conflict region when those matching lines appear near the
> +	beginning or ending of a conflict region.

I am not a native speaker, but contrast between "beginning" and
"ending" felt funny (I usually see "beginning" vs "end").

> diff --git a/Documentation/git-merge.txt b/Documentation/git-merge.txt
> index 3819fadac1f1..259e1ac2cf0c 100644
> --- a/Documentation/git-merge.txt
> +++ b/Documentation/git-merge.txt
> +while in "zdiff3" style, it may look like this:
> +
> +------------
> +Here are lines that are either unchanged from the common
> +ancestor, or cleanly resolved because only one side changed,
> +or cleanly resolved because both sides changed the same way.
> +<<<<<<< yours:sample.txt
> +Conflict resolution is hard;
> +let's go shopping.
> +||||||| base:sample.txt
> +or cleanly resolved because both sides changed identically.
>  Conflict resolution is hard.
>  =======
>  Git makes conflict resolution easy.

OK, the text in the updated example clearly says what it is ;-)  The
base is not necessarily "unchanged from the common ancestor", but
now includes "both sides changed the same way".

Nicely described.

Will queue.

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

[Felipe Contreras]

Elijah Newren via GitGitGadget wrote:
> From: Elijah Newren <newren@gmail.com>
> 
> "zdiff3" is identical to ordinary diff3 except that it allows compaction
> of common lines on the two sides of history at the beginning or end of
> the conflict hunk.

That was not the main reason behind zdiff3.

The whole point of zdiff3 was to have something closer to the "merge"
style, even if not technically correct.

Your proposal is better than diff3 in that respect, but worse than Uwe's
zdiff3.

If you have this:

  l  b  r
  =  =  =
  A  A  A

  B     b
  C     C
  D     D
  E     E
  F     F
  I     i

merge will output this:

  A

  <<<<<<< l
  B
  =======
  b
  >>>>>>> r
  C
  D
  E
  F
  <<<<<<< l
  I
  =======
  i
  >>>>>>> r

This is simple, and useful.

diff3 will output this:

  A
  <<<<<<< l

  B
  C
  D
  E
  F
  I
  ||||||| b
  =======

  b
  C
  D
  E
  F
  i
  >>>>>>> r

Not very friendly.

Your zdiff3:

  A

  <<<<<<< l
  B
  C
  D
  E
  F
  I
  ||||||| b
  =======
  b
  C
  D
  E
  F
  i
  >>>>>>> r

Just marginally better.

Uwe's zdiff3:

  A

  <<<<<<< l
  B
  ||||||| b
  =======
  b
  >>>>>>> r
  C
  D
  E
  F
  <<<<<<< l
  I
  ||||||| b
  =======
  i
  >>>>>>> r

In my view of all the *diff3's, Uwe's version is the most useful.

-- 
Felipe Contreras

Re: [PATCH 0/2] RFC: implement new zdiff3 conflict style

[Jeff King]

On Tue, Jun 15, 2021 at 05:16:08AM +0000, Elijah Newren via GitGitGadget wrote:

> Implement a zealous diff3, or "zdiff3". This new mode is identical to
> ordinary diff3 except that it allows compaction of common lines between the
> two sides of history, if those common lines occur at the beginning or end of
> a conflict hunk.
> 
> This is just RFC, because I need to add tests. Also, while I've remerged
> every merge, revert, or duly marked cherry-pick from both git.git and
> linux.git with this patch using the new zdiff3 mode, that only shows it
> doesn't segfault. (Though I also reran 10% of the linux remerges with zdiff3
> under valgrind without issues.) I looked through some differences between
> --remerge-diff with diff3 and --remerge-diff with zdiff3, but those are
> essentially diffs of a diff of a diff, which I found hard to read. I'd like
> to look through more examples, and use it for a while before submitting the
> patches without the RFC tag.

I did something similar (but I wasn't smart enough to try your
remerge-diff, and just re-ran a bunch of merges).

Skimming over the results, I didn't see anything that looked incorrect.
Many of them are pretty non-exciting, though. A common case seems to be
ones like 01a2a03c56 (Merge branch 'jc/diff-filter-negation',
2013-09-09), where two sides both add functions in the same place, and
the common lines are just the closing "}" followed by a blank line.

Removing those shared lines actually makes things less readable, IMHO,
but I don't think it's the wrong thing to do. The usual "merge" zealous
minimization likewise produces the same unreadability. If we want to
address that, I think the best way would be by teaching the minimization
some heuristics about which lines are trivial.

Here's another interesting one. In 0c52457b7c (Merge branch
'nd/daemon-informative-errors-typofix', 2014-01-10), the diff3 looks
like:

  <<<<<<< ours
                  if (starts_with(arg, "--informative-errors")) {
  ||||||| base
                  if (!prefixcmp(arg, "--informative-errors")) {
  =======
                  if (!strcmp(arg, "--informative-errors")) {
  >>>>>>> theirs
                          informative_errors = 1;
                          continue;
                  }
  <<<<<<< ours
                  if (starts_with(arg, "--no-informative-errors")) {
  ||||||| base
                  if (!prefixcmp(arg, "--no-informative-errors")) {
  =======
                  if (!strcmp(arg, "--no-informative-errors")) {
  >>>>>>> theirs

A little clunky, but it's easy-ish to see what's going on. With zdiff3,
the context between the two hunks is rolled into a single hunk:

  <<<<<<< ours
                  if (starts_with(arg, "--informative-errors")) {
                          informative_errors = 1;
                          continue;
                  }
                  if (starts_with(arg, "--no-informative-errors")) {
  ||||||| base
                  if (!prefixcmp(arg, "--informative-errors")) {
  =======
                  if (!strcmp(arg, "--informative-errors")) {
                          informative_errors = 1;
                          continue;
                  }
                  if (!strcmp(arg, "--no-informative-errors")) {
  >>>>>>> theirs

which seems worse. I haven't dug/thought carefully enough into your
change yet to know if this is expected, or if there's a bug.

-Peff

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

[Elijah Newren]

On Tue, Jun 15, 2021 at 2:40 AM Felipe Contreras
<felipe.contreras@gmail.com> wrote:
>
> Elijah Newren via GitGitGadget wrote:
> > From: Elijah Newren <newren@gmail.com>
> >
> > "zdiff3" is identical to ordinary diff3 except that it allows compaction
> > of common lines on the two sides of history at the beginning or end of
> > the conflict hunk.
>
> That was not the main reason behind zdiff3.
>
> The whole point of zdiff3 was to have something closer to the "merge"
> style, even if not technically correct.
>
> Your proposal is better than diff3 in that respect, but worse than Uwe's
> zdiff3.
>
> If you have this:
>
>   l  b  r
>   =  =  =
>   A  A  A
>
>   B     b
>   C     C
>   D     D
>   E     E
>   F     F
>   I     i
>
> merge will output this:
>
>   A
>
>   <<<<<<< l
>   B
>   =======
>   b
>   >>>>>>> r
>   C
>   D
>   E
>   F
>   <<<<<<< l
>   I
>   =======
>   i
>   >>>>>>> r
>
> This is simple, and useful.
>
> diff3 will output this:
>
>   A
>   <<<<<<< l
>
>   B
>   C
>   D
>   E
>   F
>   I
>   ||||||| b
>   =======
>
>   b
>   C
>   D
>   E
>   F
>   i
>   >>>>>>> r
>
> Not very friendly.
>
> Your zdiff3:
>
>   A
>
>   <<<<<<< l
>   B
>   C
>   D
>   E
>   F
>   I
>   ||||||| b
>   =======
>   b
>   C
>   D
>   E
>   F
>   i
>   >>>>>>> r
>
> Just marginally better.

Your example here is one where diff3 has no original text in the
conflicted region.  Empty text is trivially easy to split, making it a
somewhat uninteresting testcase for zdiff3.  The interesting question
is what do you do when that region is non-empty?  When it's non-empty,
it's not going to match the two sides (i.e. it won't have "C D E F"
lines for your example) -- we know that because when the original also
matches the two sides, the xdiff code will start with multiple
separate conflicts instead of one big one.  So, in such a case, do you
still decide to split the conflict regions, and if so, how do you
split the non-matching original text?

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

[Sergey Organov]

Elijah Newren <newren@gmail.com> writes:

> On Tue, Jun 15, 2021 at 2:40 AM Felipe Contreras
> <felipe.contreras@gmail.com> wrote:
>>
>> Elijah Newren via GitGitGadget wrote:
>> > From: Elijah Newren <newren@gmail.com>
>> >
>> > "zdiff3" is identical to ordinary diff3 except that it allows compaction
>> > of common lines on the two sides of history at the beginning or end of
>> > the conflict hunk.
>>
>> That was not the main reason behind zdiff3.
>>
>> The whole point of zdiff3 was to have something closer to the "merge"
>> style, even if not technically correct.
>>
>> Your proposal is better than diff3 in that respect, but worse than Uwe's
>> zdiff3.
>>
>> If you have this:
>>
>>   l  b  r
>>   =  =  =
>>   A  A  A
>>
>>   B     b
>>   C     C
>>   D     D
>>   E     E
>>   F     F
>>   I     i
>>
>> merge will output this:
>>
>>   A
>>
>>   <<<<<<< l
>>   B
>>   =======
>>   b
>>   >>>>>>> r
>>   C
>>   D
>>   E
>>   F
>>   <<<<<<< l
>>   I
>>   =======
>>   i
>>   >>>>>>> r
>>
>> This is simple, and useful.
>>
>> diff3 will output this:
>>
>>   A
>>   <<<<<<< l
>>
>>   B
>>   C
>>   D
>>   E
>>   F
>>   I
>>   ||||||| b
>>   =======
>>
>>   b
>>   C
>>   D
>>   E
>>   F
>>   i
>>   >>>>>>> r
>>
>> Not very friendly.

For me it's friendly enough. One key-press in Emacs and I get:

--- upper/xx.txt
+++ lower/xx.txt
@@ -1,7 +1,7 @@
 
-B
+b
 C
 D
 E
 F
-I
+i

In a separate window, that is roughly what you've get in the "merge"
output in the first place, but even more compact.

My point is that once Git provides enough context, a good interactive
tool will do the rest just fine, beneficial to the end-user.

-- Sergey Organov

Re: [PATCH 0/2] RFC: implement new zdiff3 conflict style

[Elijah Newren]

On Tue, Jun 15, 2021 at 2:43 AM Jeff King <peff@peff.net> wrote:
>
> On Tue, Jun 15, 2021 at 05:16:08AM +0000, Elijah Newren via GitGitGadget wrote:
>
> > Implement a zealous diff3, or "zdiff3". This new mode is identical to
> > ordinary diff3 except that it allows compaction of common lines between the
> > two sides of history, if those common lines occur at the beginning or end of
> > a conflict hunk.
> >
> > This is just RFC, because I need to add tests. Also, while I've remerged
> > every merge, revert, or duly marked cherry-pick from both git.git and
> > linux.git with this patch using the new zdiff3 mode, that only shows it
> > doesn't segfault. (Though I also reran 10% of the linux remerges with zdiff3
> > under valgrind without issues.) I looked through some differences between
> > --remerge-diff with diff3 and --remerge-diff with zdiff3, but those are
> > essentially diffs of a diff of a diff, which I found hard to read. I'd like
> > to look through more examples, and use it for a while before submitting the
> > patches without the RFC tag.
>
> I did something similar (but I wasn't smart enough to try your
> remerge-diff, and just re-ran a bunch of merges).

What I did was great for testing if there were funny merges that might
cause segfaults or such with zdiff3, but not so clever for viewing the
direct output from zdiff3.  Using remerge-diff in this way does not
show the [z]diff3 output directly, but a diff of that output against
what was ultimately recorded in the merge, forcing me to attempt to
recreate the original in my head.

(And, of course, I made it even worse by taking the remerge-diff
output with diff3, and the remerge-diff output with zdiff3, and then
diffing those, resulting in yet another layer of diffs that I'd have
to undo in my head to attempt to construct the original.)

> Skimming over the results, I didn't see anything that looked incorrect.
> Many of them are pretty non-exciting, though. A common case seems to be
> ones like 01a2a03c56 (Merge branch 'jc/diff-filter-negation',
> 2013-09-09), where two sides both add functions in the same place, and
> the common lines are just the closing "}" followed by a blank line.
>
> Removing those shared lines actually makes things less readable, IMHO,
> but I don't think it's the wrong thing to do. The usual "merge" zealous
> minimization likewise produces the same unreadability. If we want to
> address that, I think the best way would be by teaching the minimization
> some heuristics about which lines are trivial.
>
> Here's another interesting one. In 0c52457b7c (Merge branch
> 'nd/daemon-informative-errors-typofix', 2014-01-10), the diff3 looks
> like:
>
>   <<<<<<< ours
>                   if (starts_with(arg, "--informative-errors")) {
>   ||||||| base
>                   if (!prefixcmp(arg, "--informative-errors")) {
>   =======
>                   if (!strcmp(arg, "--informative-errors")) {
>   >>>>>>> theirs
>                           informative_errors = 1;
>                           continue;
>                   }
>   <<<<<<< ours
>                   if (starts_with(arg, "--no-informative-errors")) {
>   ||||||| base
>                   if (!prefixcmp(arg, "--no-informative-errors")) {
>   =======
>                   if (!strcmp(arg, "--no-informative-errors")) {
>   >>>>>>> theirs
>
> A little clunky, but it's easy-ish to see what's going on. With zdiff3,
> the context between the two hunks is rolled into a single hunk:
>
>   <<<<<<< ours
>                   if (starts_with(arg, "--informative-errors")) {
>                           informative_errors = 1;
>                           continue;
>                   }
>                   if (starts_with(arg, "--no-informative-errors")) {
>   ||||||| base
>                   if (!prefixcmp(arg, "--informative-errors")) {
>   =======
>                   if (!strcmp(arg, "--informative-errors")) {
>                           informative_errors = 1;
>                           continue;
>                   }
>                   if (!strcmp(arg, "--no-informative-errors")) {
>   >>>>>>> theirs
>
> which seems worse. I haven't dug/thought carefully enough into your
> change yet to know if this is expected, or if there's a bug.

Yeah, I don't know for sure either but that does look buggy to me.
Thanks for digging up these examples.  I'm a bit overdrawn on time for
this, so I'll pick it back up in a week or two and investigate this
case further.

Re: [PATCH 0/2] RFC: implement new zdiff3 conflict style

[Johannes Sixt]

Am 15.06.21 um 07:16 schrieb Elijah Newren via GitGitGadget:
> Implement a zealous diff3, or "zdiff3". This new mode is identical to
> ordinary diff3 except that it allows compaction of common lines between the
> two sides of history, if those common lines occur at the beginning or end of
> a conflict hunk.

As a data point, I tried this series (cf9d93e547 en/zdiff3) on my
criss-cross merge test case that started this adventure, and it produces
the very same output as diff3; cf.
https://lore.kernel.org/git/60883e1b-787f-5ec2-a9af-f2f6757d3c43@kdbg.org/

-- Hannes

Re: [PATCH 0/2] RFC: implement new zdiff3 conflict style

[Elijah Newren]

On Tue, Jun 15, 2021 at 2:36 PM Johannes Sixt <j6t@kdbg.org> wrote:
>
> Am 15.06.21 um 07:16 schrieb Elijah Newren via GitGitGadget:
> > Implement a zealous diff3, or "zdiff3". This new mode is identical to
> > ordinary diff3 except that it allows compaction of common lines between the
> > two sides of history, if those common lines occur at the beginning or end of
> > a conflict hunk.
>
> As a data point, I tried this series (cf9d93e547 en/zdiff3) on my
> criss-cross merge test case that started this adventure, and it produces
> the very same output as diff3; cf.
> https://lore.kernel.org/git/60883e1b-787f-5ec2-a9af-f2f6757d3c43@kdbg.org/

That's good to hear; your two sides had no common text at the
beginning or end of the conflict hunk, so I wouldn't expect zdiff3 to
change that particular example.

The XDL_MERGE_FAVOR_BASE idea (cf.
https://lore.kernel.org/git/20210611190235.1970106-1-newren@gmail.com/),
though would I think simplify the diff3 conflict markers in your
example to

<<<<<<< HEAD
    CClustering ComputeSSLClusters(double threshPercent, const
CDataInfo* scale) const override;
    void ComputeDist(DistFunc distFunc, CDoubleArray& dist,
        double& minDist, double& maxDist) const;
    double EstimateNodeDist2() const override;
    std::vector<double> EstimateNeighborMinDist() const override;
||||||| merged common ancestors
    CClustering ComputeClusters(const double* dist, double threshold,
        const CDataInfo* scale) const override;
    virtual void ComputeDist(DistFunc distFunc, CDoubleArray& dist,
        double& minDist, double& maxDist);
    virtual void ComputeUMatrix();
    virtual void ComputeKNearest(int K, const double*,
        Neighborhood& result) const;
=======
    CClustering ComputeSSLClusters(double threshPercent,
        const CDoubleArray& compWeights, const CDataInfo* scale) const override;
    static void ComputeDist(const CNetNodeHolder& vecs, CDoubleArray& dist,
        double& minDist, double& maxDist);
>>>>>>> no-compweights-in-cnet

That seems like it might be nicer, but I don't do many criss-cross
merges myself so it'd be nice to get opinions of others like you who
do.

Re: [PATCH 0/2] RFC: implement new zdiff3 conflict style

[Johannes Sixt]

Am 15.06.21 um 23:45 schrieb Elijah Newren:
> On Tue, Jun 15, 2021 at 2:36 PM Johannes Sixt <j6t@kdbg.org> wrote:
>>
>> Am 15.06.21 um 07:16 schrieb Elijah Newren via GitGitGadget:
>>> Implement a zealous diff3, or "zdiff3". This new mode is identical to
>>> ordinary diff3 except that it allows compaction of common lines between the
>>> two sides of history, if those common lines occur at the beginning or end of
>>> a conflict hunk.
>>
>> As a data point, I tried this series (cf9d93e547 en/zdiff3) on my
>> criss-cross merge test case that started this adventure, and it produces
>> the very same output as diff3; cf.
>> https://lore.kernel.org/git/60883e1b-787f-5ec2-a9af-f2f6757d3c43@kdbg.org/
> 
> That's good to hear; your two sides had no common text at the
> beginning or end of the conflict hunk, so I wouldn't expect zdiff3 to
> change that particular example.
> 
> The XDL_MERGE_FAVOR_BASE idea (cf.
> https://lore.kernel.org/git/20210611190235.1970106-1-newren@gmail.com/),
> though would I think simplify the diff3 conflict markers in your
> example to
> 
> <<<<<<< HEAD
>     CClustering ComputeSSLClusters(double threshPercent, const
> CDataInfo* scale) const override;
>     void ComputeDist(DistFunc distFunc, CDoubleArray& dist,
>         double& minDist, double& maxDist) const;
>     double EstimateNodeDist2() const override;
>     std::vector<double> EstimateNeighborMinDist() const override;
> ||||||| merged common ancestors
>     CClustering ComputeClusters(const double* dist, double threshold,
>         const CDataInfo* scale) const override;
>     virtual void ComputeDist(DistFunc distFunc, CDoubleArray& dist,
>         double& minDist, double& maxDist);
>     virtual void ComputeUMatrix();
>     virtual void ComputeKNearest(int K, const double*,
>         Neighborhood& result) const;
> =======
>     CClustering ComputeSSLClusters(double threshPercent,
>         const CDoubleArray& compWeights, const CDataInfo* scale) const override;
>     static void ComputeDist(const CNetNodeHolder& vecs, CDoubleArray& dist,
>         double& minDist, double& maxDist);
>>>>>>>> no-compweights-in-cnet
> 
> That seems like it might be nicer, but I don't do many criss-cross
> merges myself so it'd be nice to get opinions of others like you who
> do.

That *is* nicer as it is just the regular conflict with some base
context. Does that mean that the regular recursive merge is a bit sloppy
because it throws away too many conflicts that occur in virtual
ancestors? Even if that is the case, I couldn't tell whether that is a
disadvantage or not, as I've actually never seen nested conflicts in the
past; the diff3 test was the first time I saw one.

With the referenced patch applied (after a small tweak around needs_cr
to make it compile), my testcase does indeed produce the above conflict
under zdiff3 mode. The diff3 mode, OTOH, produces an exceedingly large
non-nested and obviously incorrect conflict (I'm not going to post it
here): our and their side are large and share a lot of text, but the
base part is identical to the above and is far too small.

-- Hannes

Re: [PATCH 0/2] RFC: implement new zdiff3 conflict style

[Elijah Newren]

On Tue, Jun 15, 2021 at 11:16 PM Johannes Sixt <j6t@kdbg.org> wrote:
>
> Am 15.06.21 um 23:45 schrieb Elijah Newren:
> > On Tue, Jun 15, 2021 at 2:36 PM Johannes Sixt <j6t@kdbg.org> wrote:
> >>
> >> Am 15.06.21 um 07:16 schrieb Elijah Newren via GitGitGadget:
> >>> Implement a zealous diff3, or "zdiff3". This new mode is identical to
> >>> ordinary diff3 except that it allows compaction of common lines between the
> >>> two sides of history, if those common lines occur at the beginning or end of
> >>> a conflict hunk.
> >>
> >> As a data point, I tried this series (cf9d93e547 en/zdiff3) on my
> >> criss-cross merge test case that started this adventure, and it produces
> >> the very same output as diff3; cf.
> >> https://lore.kernel.org/git/60883e1b-787f-5ec2-a9af-f2f6757d3c43@kdbg.org/
> >
> > That's good to hear; your two sides had no common text at the
> > beginning or end of the conflict hunk, so I wouldn't expect zdiff3 to
> > change that particular example.
> >
> > The XDL_MERGE_FAVOR_BASE idea (cf.
> > https://lore.kernel.org/git/20210611190235.1970106-1-newren@gmail.com/),
> > though would I think simplify the diff3 conflict markers in your
> > example to
> >
> > <<<<<<< HEAD
> >     CClustering ComputeSSLClusters(double threshPercent, const
> > CDataInfo* scale) const override;
> >     void ComputeDist(DistFunc distFunc, CDoubleArray& dist,
> >         double& minDist, double& maxDist) const;
> >     double EstimateNodeDist2() const override;
> >     std::vector<double> EstimateNeighborMinDist() const override;
> > ||||||| merged common ancestors
> >     CClustering ComputeClusters(const double* dist, double threshold,
> >         const CDataInfo* scale) const override;
> >     virtual void ComputeDist(DistFunc distFunc, CDoubleArray& dist,
> >         double& minDist, double& maxDist);
> >     virtual void ComputeUMatrix();
> >     virtual void ComputeKNearest(int K, const double*,
> >         Neighborhood& result) const;
> > =======
> >     CClustering ComputeSSLClusters(double threshPercent,
> >         const CDoubleArray& compWeights, const CDataInfo* scale) const override;
> >     static void ComputeDist(const CNetNodeHolder& vecs, CDoubleArray& dist,
> >         double& minDist, double& maxDist);
> >>>>>>>> no-compweights-in-cnet
> >
> > That seems like it might be nicer, but I don't do many criss-cross
> > merges myself so it'd be nice to get opinions of others like you who
> > do.
>
> That *is* nicer as it is just the regular conflict with some base
> context. Does that mean that the regular recursive merge is a bit sloppy
> because it throws away too many conflicts that occur in virtual
> ancestors? Even if that is the case, I couldn't tell whether that is a
> disadvantage or not, as I've actually never seen nested conflicts in the
> past; the diff3 test was the first time I saw one.
>
> With the referenced patch applied (after a small tweak around needs_cr
> to make it compile), my testcase does indeed produce the above conflict
> under zdiff3 mode. The diff3 mode, OTOH, produces an exceedingly large
> non-nested and obviously incorrect conflict (I'm not going to post it
> here): our and their side are large and share a lot of text, but the
> base part is identical to the above and is far too small.

The thing about XDL_MERGE_FAVOR_BASE in combination with a recursive
merge, is that if you have two merge-bases, then XDL_MERGE_FAVOR_BASE
will put the text from the merge base of the merge-bases in the
"original text" region.  If your merge bases themselves had multiple
merge-bases, and those merge bases in turn had multiple merge-bases,
etc., so that you end up with a deeply nested recursive merge, then
XDL_MERGE_FAVOR_BASE will cause you to get the "original text" filled
by the text from some ancient ancestor.  The net result is that it
makes it look like you have done a three-way merge between the two
sides you expect with a really ancient merge base.  So, a really small
original text is probably something to be expected from the
XDL_MERGE_FAVOR_BASE patch.

The fact that zdiff3 shrinks it down considerably reflects the fact
that your two sides had long sections of code that matched at the
beginning and end of the conflict hunk.  So it sounds to me like both
pieces were behaving implementationally as designed for your testcase.

Whether using "ancient original text" makes sense in general rather
than using a "more recent original text" (in the form of an attempted
merge of the merge-bases complete with conflict markers), feels like
it's one of those tradeoff things that I figured those who do lots of
criss-cross merges should weigh in on rather than me.

Re: [PATCH 0/2] RFC: implement new zdiff3 conflict style

[Phillip Wood]

On 15/06/2021 20:35, Elijah Newren wrote:
> On Tue, Jun 15, 2021 at 2:43 AM Jeff King <peff@peff.net> wrote:
>>
>> On Tue, Jun 15, 2021 at 05:16:08AM +0000, Elijah Newren via GitGitGadget wrote:
>>
>>> Implement a zealous diff3, or "zdiff3". This new mode is identical to
>>> ordinary diff3 except that it allows compaction of common lines between the
>>> two sides of history, if those common lines occur at the beginning or end of
>>> a conflict hunk.
>>>
>>> This is just RFC, because I need to add tests. Also, while I've remerged
>>> every merge, revert, or duly marked cherry-pick from both git.git and
>>> linux.git with this patch using the new zdiff3 mode, that only shows it
>>> doesn't segfault. (Though I also reran 10% of the linux remerges with zdiff3
>>> under valgrind without issues.) I looked through some differences between
>>> --remerge-diff with diff3 and --remerge-diff with zdiff3, but those are
>>> essentially diffs of a diff of a diff, which I found hard to read. I'd like
>>> to look through more examples, and use it for a while before submitting the
>>> patches without the RFC tag.
>>
>> I did something similar (but I wasn't smart enough to try your
>> remerge-diff, and just re-ran a bunch of merges).
> 
> What I did was great for testing if there were funny merges that might
> cause segfaults or such with zdiff3, but not so clever for viewing the
> direct output from zdiff3.  Using remerge-diff in this way does not
> show the [z]diff3 output directly, but a diff of that output against
> what was ultimately recorded in the merge, forcing me to attempt to
> recreate the original in my head.
> 
> (And, of course, I made it even worse by taking the remerge-diff
> output with diff3, and the remerge-diff output with zdiff3, and then
> diffing those, resulting in yet another layer of diffs that I'd have
> to undo in my head to attempt to construct the original.)
> 
>> Skimming over the results, I didn't see anything that looked incorrect.
>> Many of them are pretty non-exciting, though. A common case seems to be
>> ones like 01a2a03c56 (Merge branch 'jc/diff-filter-negation',
>> 2013-09-09), where two sides both add functions in the same place, and
>> the common lines are just the closing "}" followed by a blank line.
>>
>> Removing those shared lines actually makes things less readable, IMHO,
>> but I don't think it's the wrong thing to do. The usual "merge" zealous
>> minimization likewise produces the same unreadability. If we want to
>> address that, I think the best way would be by teaching the minimization
>> some heuristics about which lines are trivial.
>>
>> Here's another interesting one. In 0c52457b7c (Merge branch
>> 'nd/daemon-informative-errors-typofix', 2014-01-10), the diff3 looks
>> like:
>>
>>    <<<<<<< ours
>>                    if (starts_with(arg, "--informative-errors")) {
>>    ||||||| base
>>                    if (!prefixcmp(arg, "--informative-errors")) {
>>    =======
>>                    if (!strcmp(arg, "--informative-errors")) {
>>    >>>>>>> theirs
>>                            informative_errors = 1;
>>                            continue;
>>                    }
>>    <<<<<<< ours
>>                    if (starts_with(arg, "--no-informative-errors")) {
>>    ||||||| base
>>                    if (!prefixcmp(arg, "--no-informative-errors")) {
>>    =======
>>                    if (!strcmp(arg, "--no-informative-errors")) {
>>    >>>>>>> theirs
>>
>> A little clunky, but it's easy-ish to see what's going on. With zdiff3,
>> the context between the two hunks is rolled into a single hunk:
>>
>>    <<<<<<< ours
>>                    if (starts_with(arg, "--informative-errors")) {
>>                            informative_errors = 1;
>>                            continue;
>>                    }
>>                    if (starts_with(arg, "--no-informative-errors")) {
>>    ||||||| base
>>                    if (!prefixcmp(arg, "--informative-errors")) {
>>    =======
>>                    if (!strcmp(arg, "--informative-errors")) {
>>                            informative_errors = 1;
>>                            continue;
>>                    }
>>                    if (!strcmp(arg, "--no-informative-errors")) {
>>    >>>>>>> theirs
>>
>> which seems worse. I haven't dug/thought carefully enough into your
>> change yet to know if this is expected, or if there's a bug.

XDL_MERGE_ZEALOUS coalesces adjacent conflicts that are separated by 
fewer than four lines. Unfortunately the existing code in 
xdl_merge_two_conflicts() only coalesces 'ours' and 'theirs', not 
'base'. Applying

diff --git a/xdiff/xmerge.c b/xdiff/xmerge.c
index b1dc9df7ea..5f76957169 100644
--- a/xdiff/xmerge.c
+++ b/xdiff/xmerge.c
@@ -455,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;

and running
     git checkout 0c52457b7c^ &&
     bin-wrappers/git -c merge.conflictstyle=zdiff3 merge 0c52457b7c^2
gives

<<<<<<< HEAD
		if (starts_with(arg, "--informative-errors")) {
			informative_errors = 1;
			continue;
		}
		if (starts_with(arg, "--no-informative-errors")) {
||||||| 2f93541d88
		if (!prefixcmp(arg, "--informative-errors")) {
			informative_errors = 1;
			continue;
		}
		if (!prefixcmp(arg, "--no-informative-errors")) {
=======
		if (!strcmp(arg, "--informative-errors")) {
			informative_errors = 1;
			continue;
		}
		if (!strcmp(arg, "--no-informative-errors")) {
 >>>>>>> 0c52457b7c^2

Which I think is correct. Whether combining single line conflicts in 
this way is useful is a different question (and is independent of your 
patch). I can see that with larger conflicts it is worth it but here we 
end up with conflicts where 60% of the lines are from the base version. 
One the other hand there are fewer conflicts to resolve - I'm not sure 
which I prefer.

Best Wishes

Phillip

> Yeah, I don't know for sure either but that does look buggy to me.
> Thanks for digging up these examples.  I'm a bit overdrawn on time for
> this, so I'll pick it back up in a week or two and investigate this
> case further.
> 

Re: [PATCH 0/2] RFC: implement new zdiff3 conflict style

[Jeff King]

On Wed, Jun 16, 2021 at 09:57:49AM +0100, Phillip Wood wrote:

> > > which seems worse. I haven't dug/thought carefully enough into your
> > > change yet to know if this is expected, or if there's a bug.
> 
> XDL_MERGE_ZEALOUS coalesces adjacent conflicts that are separated by fewer
> than four lines. Unfortunately the existing code in
> xdl_merge_two_conflicts() only coalesces 'ours' and 'theirs', not 'base'.
> Applying
> [...]
> gives
> 
> <<<<<<< HEAD
> 		if (starts_with(arg, "--informative-errors")) {
> 			informative_errors = 1;
> 			continue;
> 		}
> 		if (starts_with(arg, "--no-informative-errors")) {
> ||||||| 2f93541d88
> 		if (!prefixcmp(arg, "--informative-errors")) {
> 			informative_errors = 1;
> 			continue;
> 		}
> 		if (!prefixcmp(arg, "--no-informative-errors")) {
> =======
> 		if (!strcmp(arg, "--informative-errors")) {
> 			informative_errors = 1;
> 			continue;
> 		}
> 		if (!strcmp(arg, "--no-informative-errors")) {
> >>>>>>> 0c52457b7c^2
> 
> Which I think is correct. Whether combining single line conflicts in this
> way is useful is a different question (and is independent of your patch). I
> can see that with larger conflicts it is worth it but here we end up with
> conflicts where 60% of the lines are from the base version. One the other
> hand there are fewer conflicts to resolve - I'm not sure which I prefer.

Thanks for figuring that out. I agree that the output after the patch
you showed is correct, in the sense that the common lines show up in the
base now. It does feel like it's working against the point of zdiff3,
though, which is to reduce the number of common lines shown in the
"ours" and "theirs" hunks.

Likewise, I think this coalescing makes things worse even for "merge",
where you get:

  <<<<<<< ours
                  if (starts_with(arg, "--informative-errors")) {
                          informative_errors = 1;
                          continue;
                  }
                  if (starts_with(arg, "--no-informative-errors")) {
  =======
                  if (!strcmp(arg, "--informative-errors")) {
                          informative_errors = 1;
                          continue;
                  }
                  if (!strcmp(arg, "--no-informative-errors")) {
  >>>>>>> theirs

and have to figure out manually that those interior lines are common.
But I imagine there are cases where you have a large number of
uninteresting lines (blank lines, "}", etc) that create a lot of noise
in the output by breaking up the actual changed lines into tiny hunks
that are hard to digest on their own.

-Peff

Re: [PATCH 0/2] RFC: implement new zdiff3 conflict style

[Elijah Newren]

On Wed, Jun 16, 2021 at 1:57 AM Phillip Wood <phillip.wood123@gmail.com> wrote:
>
> On 15/06/2021 20:35, Elijah Newren wrote:
> > On Tue, Jun 15, 2021 at 2:43 AM Jeff King <peff@peff.net> wrote:
> >>
> >> On Tue, Jun 15, 2021 at 05:16:08AM +0000, Elijah Newren via GitGitGadget wrote:
> >>
> >>> Implement a zealous diff3, or "zdiff3". This new mode is identical to
> >>> ordinary diff3 except that it allows compaction of common lines between the
> >>> two sides of history, if those common lines occur at the beginning or end of
> >>> a conflict hunk.
> >>>
> >>> This is just RFC, because I need to add tests. Also, while I've remerged
> >>> every merge, revert, or duly marked cherry-pick from both git.git and
> >>> linux.git with this patch using the new zdiff3 mode, that only shows it
> >>> doesn't segfault. (Though I also reran 10% of the linux remerges with zdiff3
> >>> under valgrind without issues.) I looked through some differences between
> >>> --remerge-diff with diff3 and --remerge-diff with zdiff3, but those are
> >>> essentially diffs of a diff of a diff, which I found hard to read. I'd like
> >>> to look through more examples, and use it for a while before submitting the
> >>> patches without the RFC tag.
> >>
> >> I did something similar (but I wasn't smart enough to try your
> >> remerge-diff, and just re-ran a bunch of merges).
> >
> > What I did was great for testing if there were funny merges that might
> > cause segfaults or such with zdiff3, but not so clever for viewing the
> > direct output from zdiff3.  Using remerge-diff in this way does not
> > show the [z]diff3 output directly, but a diff of that output against
> > what was ultimately recorded in the merge, forcing me to attempt to
> > recreate the original in my head.
> >
> > (And, of course, I made it even worse by taking the remerge-diff
> > output with diff3, and the remerge-diff output with zdiff3, and then
> > diffing those, resulting in yet another layer of diffs that I'd have
> > to undo in my head to attempt to construct the original.)
> >
> >> Skimming over the results, I didn't see anything that looked incorrect.
> >> Many of them are pretty non-exciting, though. A common case seems to be
> >> ones like 01a2a03c56 (Merge branch 'jc/diff-filter-negation',
> >> 2013-09-09), where two sides both add functions in the same place, and
> >> the common lines are just the closing "}" followed by a blank line.
> >>
> >> Removing those shared lines actually makes things less readable, IMHO,
> >> but I don't think it's the wrong thing to do. The usual "merge" zealous
> >> minimization likewise produces the same unreadability. If we want to
> >> address that, I think the best way would be by teaching the minimization
> >> some heuristics about which lines are trivial.
> >>
> >> Here's another interesting one. In 0c52457b7c (Merge branch
> >> 'nd/daemon-informative-errors-typofix', 2014-01-10), the diff3 looks
> >> like:
> >>
> >>    <<<<<<< ours
> >>                    if (starts_with(arg, "--informative-errors")) {
> >>    ||||||| base
> >>                    if (!prefixcmp(arg, "--informative-errors")) {
> >>    =======
> >>                    if (!strcmp(arg, "--informative-errors")) {
> >>    >>>>>>> theirs
> >>                            informative_errors = 1;
> >>                            continue;
> >>                    }
> >>    <<<<<<< ours
> >>                    if (starts_with(arg, "--no-informative-errors")) {
> >>    ||||||| base
> >>                    if (!prefixcmp(arg, "--no-informative-errors")) {
> >>    =======
> >>                    if (!strcmp(arg, "--no-informative-errors")) {
> >>    >>>>>>> theirs
> >>
> >> A little clunky, but it's easy-ish to see what's going on. With zdiff3,
> >> the context between the two hunks is rolled into a single hunk:
> >>
> >>    <<<<<<< ours
> >>                    if (starts_with(arg, "--informative-errors")) {
> >>                            informative_errors = 1;
> >>                            continue;
> >>                    }
> >>                    if (starts_with(arg, "--no-informative-errors")) {
> >>    ||||||| base
> >>                    if (!prefixcmp(arg, "--informative-errors")) {
> >>    =======
> >>                    if (!strcmp(arg, "--informative-errors")) {
> >>                            informative_errors = 1;
> >>                            continue;
> >>                    }
> >>                    if (!strcmp(arg, "--no-informative-errors")) {
> >>    >>>>>>> theirs
> >>
> >> which seems worse. I haven't dug/thought carefully enough into your
> >> change yet to know if this is expected, or if there's a bug.
>
> XDL_MERGE_ZEALOUS coalesces adjacent conflicts that are separated by
> fewer than four lines. Unfortunately the existing code in
> xdl_merge_two_conflicts() only coalesces 'ours' and 'theirs', not
> 'base'. Applying
>
> diff --git a/xdiff/xmerge.c b/xdiff/xmerge.c
> index b1dc9df7ea..5f76957169 100644
> --- a/xdiff/xmerge.c
> +++ b/xdiff/xmerge.c
> @@ -455,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;
>
> and running
>      git checkout 0c52457b7c^ &&
>      bin-wrappers/git -c merge.conflictstyle=zdiff3 merge 0c52457b7c^2
> gives
>
> <<<<<<< HEAD
>                 if (starts_with(arg, "--informative-errors")) {
>                         informative_errors = 1;
>                         continue;
>                 }
>                 if (starts_with(arg, "--no-informative-errors")) {
> ||||||| 2f93541d88
>                 if (!prefixcmp(arg, "--informative-errors")) {
>                         informative_errors = 1;
>                         continue;
>                 }
>                 if (!prefixcmp(arg, "--no-informative-errors")) {
> =======
>                 if (!strcmp(arg, "--informative-errors")) {
>                         informative_errors = 1;
>                         continue;
>                 }
>                 if (!strcmp(arg, "--no-informative-errors")) {
>  >>>>>>> 0c52457b7c^2
>
> Which I think is correct. Whether combining single line conflicts in
> this way is useful is a different question (and is independent of your
> patch). I can see that with larger conflicts it is worth it but here we
> end up with conflicts where 60% of the lines are from the base version.
> One the other hand there are fewer conflicts to resolve - I'm not sure
> which I prefer.

Oh, sweet, thanks for tracking this down!  I'll try to find some time
to play with it some more.

Re: [PATCH 0/2] RFC: implement new zdiff3 conflict style

[Phillip Wood]

On 16/06/2021 11:31, Jeff King wrote:
> On Wed, Jun 16, 2021 at 09:57:49AM +0100, Phillip Wood wrote:
> 
>>>> which seems worse. I haven't dug/thought carefully enough into your
>>>> change yet to know if this is expected, or if there's a bug.
>>
>> XDL_MERGE_ZEALOUS coalesces adjacent conflicts that are separated by fewer
>> than four lines. Unfortunately the existing code in
>> xdl_merge_two_conflicts() only coalesces 'ours' and 'theirs', not 'base'.
>> Applying
>> [...]
>> gives
>>
>> <<<<<<< HEAD
>> 		if (starts_with(arg, "--informative-errors")) {
>> 			informative_errors = 1;
>> 			continue;
>> 		}
>> 		if (starts_with(arg, "--no-informative-errors")) {
>> ||||||| 2f93541d88
>> 		if (!prefixcmp(arg, "--informative-errors")) {
>> 			informative_errors = 1;
>> 			continue;
>> 		}
>> 		if (!prefixcmp(arg, "--no-informative-errors")) {
>> =======
>> 		if (!strcmp(arg, "--informative-errors")) {
>> 			informative_errors = 1;
>> 			continue;
>> 		}
>> 		if (!strcmp(arg, "--no-informative-errors")) {
>>>>>>>>> 0c52457b7c^2
>>
>> Which I think is correct. Whether combining single line conflicts in this
>> way is useful is a different question (and is independent of your patch). I
>> can see that with larger conflicts it is worth it but here we end up with
>> conflicts where 60% of the lines are from the base version. One the other
>> hand there are fewer conflicts to resolve - I'm not sure which I prefer.
> 
> Thanks for figuring that out. I agree that the output after the patch
> you showed is correct, in the sense that the common lines show up in the
> base now. It does feel like it's working against the point of zdiff3,
> though, which is to reduce the number of common lines shown in the
> "ours" and "theirs" hunks.

I agree - the output is longer rather than shorter. As we only want to 
trim the common prefix and suffix from the conflicts I wonder if it 
would be better to special case zdiff3 rather than piggy backing on the 
existing XDL_MERGE_ZEALOUS implementation. We can trim the common lines 
by looping over the begging and end of the hunk comparing the lines 
with xdl_recmatch() without going to the trouble of diffing them as 
XDL_MERGE_ZEALOUS does. I don't think we need to worry about coalescing 
adjacent conflicts for zdiff3. It makes sense to coalesce in the 
XDL_MERGE_ZEALOUS case as it can potentially split a  N line conflict 
hunk into N/2 single line conflict hunks but zdiff3 does not split 
conflict hunks.

> Likewise, I think this coalescing makes things worse even for "merge",
> where you get:
> 
>    <<<<<<< ours
>                    if (starts_with(arg, "--informative-errors")) {
>                            informative_errors = 1;
>                            continue;
>                    }
>                    if (starts_with(arg, "--no-informative-errors")) {
>    =======
>                    if (!strcmp(arg, "--informative-errors")) {
>                            informative_errors = 1;
>                            continue;
>                    }
>                    if (!strcmp(arg, "--no-informative-errors")) {
>    >>>>>>> theirs
> 
> and have to figure out manually that those interior lines are common.
> But I imagine there are cases where you have a large number of
> uninteresting lines (blank lines, "}", etc that create a lot of noise > in the output by breaking up the actual changed lines into tiny hunks
> that are hard to digest on their own.

Yes, I think the heuristic for coalescing conflict hunks could be 
improved. It would be fairly simple to only join two hunks if the 
conflicts are longer that the context between them and the existing 
XDL_MERGE_ZEALOUS_ALNUM logic allows conflicts with more context between 
them to be coalesced if the context lines are uninteresting. I think 
XDL_MERGE_ZEALOUS_ALNUM is only used by `git merge-file` at the moment, 
with everything else going through ll_merge() which uses XDL_MERGE_ZEALOUS

Best Wishes

Phillip

> 
> -Peff
> 

Re: [PATCH 0/2] RFC: implement new zdiff3 conflict style

[Jeff King]

On Wed, Jun 23, 2021 at 10:53:25AM +0100, Phillip Wood wrote:

> > Thanks for figuring that out. I agree that the output after the patch
> > you showed is correct, in the sense that the common lines show up in the
> > base now. It does feel like it's working against the point of zdiff3,
> > though, which is to reduce the number of common lines shown in the
> > "ours" and "theirs" hunks.
> 
> I agree - the output is longer rather than shorter. As we only want to trim
> the common prefix and suffix from the conflicts I wonder if it would be
> better to special case zdiff3 rather than piggy backing on the existing
> XDL_MERGE_ZEALOUS implementation. We can trim the common lines by looping
> over the begging and end of the hunk comparing the lines with xdl_recmatch()
> without going to the trouble of diffing them as XDL_MERGE_ZEALOUS does. I
> don't think we need to worry about coalescing adjacent conflicts for zdiff3.
> It makes sense to coalesce in the XDL_MERGE_ZEALOUS case as it can
> potentially split a  N line conflict hunk into N/2 single line conflict
> hunks but zdiff3 does not split conflict hunks.

That matches my intuition of a reasonable path forward (but I confess to
not being too well-versed in the details of the XDL_MERGE internals).

> Yes, I think the heuristic for coalescing conflict hunks could be improved.
> It would be fairly simple to only join two hunks if the conflicts are longer
> that the context between them and the existing XDL_MERGE_ZEALOUS_ALNUM logic
> allows conflicts with more context between them to be coalesced if the
> context lines are uninteresting. I think XDL_MERGE_ZEALOUS_ALNUM is only
> used by `git merge-file` at the moment, with everything else going through
> ll_merge() which uses XDL_MERGE_ZEALOUS

I don't recall much discussion around using ALNUM versus not, nor could
I find much in the archive. It looks like merge-file was converted to
show off ALNUM when it was added in ee95ec5d58 (xdl_merge(): introduce
XDL_MERGE_ZEALOUS_ALNUM, 2008-02-17), and it never really progressed
from there.

It might be an interesting exercise to re-run a bunch of merges and see
if ALNUM produces better (or worse) results on the whole.

-Peff

[PATCH v2 0/2] RFC: implement new zdiff3 conflict style

[Elijah Newren via GitGitGadget]

Implement a zealous diff3, or "zdiff3". This new mode is identical to
ordinary diff3 except that it allows compaction of common lines between the
two sides of history, if those common lines occur at the beginning or end of
a conflict hunk.

This is still just RFC, because one of the testcases I added fails and
really should be fixed before this series is ready to merge. Also, while
testing I noted one suboptimal merge that I thought I'd be able to easily
reproduce later, but which I wasn't able to reproduce again and for which
I've lost the details. I'd like to keep testing and find it again. Sorry for
the long delay here; been concentrating mostly on merge-ort and sparse-index
and untracked/cwd cleanup things instead.

NOTE: You may want to just eject this topic from seen. It needs more fixes
and while I do plan to eventually get back to it, I'm concentrating more on
other topics.

Changes since v1:

 * Included fixes from Phillip (thanks!)
 * Added some testcases

Elijah Newren (2):
  xdiff: implement a zealous diff3, or "zdiff3"
  update documentation for new zdiff3 conflictStyle

 Documentation/config/merge.txt         |  9 +++-
 Documentation/git-checkout.txt         |  3 +-
 Documentation/git-merge-file.txt       |  3 ++
 Documentation/git-merge.txt            | 32 ++++++++++--
 Documentation/git-rebase.txt           |  6 +--
 Documentation/git-restore.txt          |  3 +-
 Documentation/git-switch.txt           |  3 +-
 Documentation/technical/rerere.txt     | 10 ++--
 builtin/checkout.c                     |  2 +-
 builtin/merge-file.c                   |  2 +
 contrib/completion/git-completion.bash |  6 +--
 t/t6427-diff3-conflict-markers.sh      | 56 +++++++++++++++++++++
 xdiff-interface.c                      |  2 +
 xdiff/xdiff.h                          |  1 +
 xdiff/xmerge.c                         | 68 +++++++++++++++++++++++---
 15 files changed, 176 insertions(+), 30 deletions(-)


base-commit: 670b81a890388c60b7032a4f5b879f2ece8c4558
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1036%2Fnewren%2Fzdiff3-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1036/newren/zdiff3-v2
Pull-Request: https://github.com/git/git/pull/1036

Range-diff vs v1:

 1:  b7561a67c19 ! 1:  06e04c88dea xdiff: implement a zealous diff3, or "zdiff3"
     @@ Commit message
          because zdiff3 shows the base version too and the base version cannot be
          reasonably split.
      
     -    Initial-patch-by: Uwe Kleine-König <u.kleine-koenig@pengutronix.de>
     +    Based-on-patch-by: Uwe Kleine-König <u.kleine-koenig@pengutronix.de>
     +    Helped-by: Phillip Wood <phillip.wood123@gmail.com>
          Signed-off-by: Elijah Newren <newren@gmail.com>
      
       ## builtin/merge-file.c ##
     @@ contrib/completion/git-completion.bash: _git_checkout ()
       		;;
       	--*)
       		__gitcomp_builtin checkout
     +@@ contrib/completion/git-completion.bash: _git_switch ()
     + 
     + 	case "$cur" in
     + 	--conflict=*)
     +-		__gitcomp "diff3 merge" "" "${cur##--conflict=}"
     ++		__gitcomp "diff3 merge zdiff3" "" "${cur##--conflict=}"
     + 		;;
     + 	--*)
     + 		__gitcomp_builtin switch
     +@@ contrib/completion/git-completion.bash: _git_restore ()
     + 
     + 	case "$cur" in
     + 	--conflict=*)
     +-		__gitcomp "diff3 merge" "" "${cur##--conflict=}"
     ++		__gitcomp "diff3 merge zdiff3" "" "${cur##--conflict=}"
     + 		;;
     + 	--source=*)
     + 		__git_complete_refs --cur="${cur##--source=}"
     +
     + ## t/t6427-diff3-conflict-markers.sh ##
     +@@ t/t6427-diff3-conflict-markers.sh: 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
      
       ## xdiff-interface.c ##
      @@ xdiff-interface.c: int git_xmerge_config(const char *var, const char *value, void *cb)
     @@ xdiff/xmerge.c: static int xdl_refine_conflicts(xdfenv_t *xe1, xdfenv_t *xe2, xd
       		m->i1 = xscr->i1 + i1;
       		m->chg1 = xscr->chg1;
       		m->i2 = xscr->i2 + i2;
     +@@ xdiff/xmerge.c: 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;
     +@@ xdiff/xmerge.c: 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;
      @@ xdiff/xmerge.c: static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1,
       	int style = xmp->style;
       	int favor = xmp->favor;
     @@ xdiff/xmerge.c: static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1,
      +	/*
      +	 * 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.
     ++	 * 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.
      +	 *
     -+	 * XDL_MERGE_ZEALOUS_DIFF3 will attempt to refine conflicts
     -+	 * looking for common areas of sides 1 & 2, despite the base
     -+	 * not matching and being shown, but will only look for common
     -+	 * areas at the beginning or ending of the conflict block.
     ++	 * See xdl_refine_conflicts() and xdl_simplify_non_conflicts()
     ++	 * for more details, particularly looking for
     ++	 * XDL_MERGE_ZEALOUS_DIFF3.
      +	 */
       	if (style == XDL_MERGE_DIFF3) {
       		/*
     @@ xdiff/xmerge.c: static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1,
       	/* 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,
     ++	     xdl_simplify_non_conflicts(xe1, changes, style,
       					XDL_MERGE_ZEALOUS < level) < 0)) {
       		xdl_cleanup_merge(changes);
     + 		return -1;
 2:  50e82a7a32c ! 2:  9ce7246c0e9 update documentation for new zdiff3 conflictStyle
     @@ Documentation/config/merge.txt: merge.conflictStyle::
      +	when a subset of lines match on the two sides they are just pulled
      +	out of the conflict region.  Another alternate style, "zdiff3", is
      +	similar to diff3 but removes matching lines on the two sides from
     -+	the conflict region when those matching lines appear near the
     -+	beginning or ending of a conflict region.
     ++	the conflict region when those matching lines appear near either
     ++	the beginning or end of a conflict region.
       
       merge.defaultToUpstream::
       	If merge is called without any commit argument, merge the upstream
     @@ builtin/checkout.c: static struct option *add_common_options(struct checkout_opt
       		OPT_END()
       	};
       	struct option *newopts = parse_options_concat(prevopts, options);
     -
     - ## contrib/completion/git-completion.bash ##
     -@@ contrib/completion/git-completion.bash: _git_switch ()
     - 
     - 	case "$cur" in
     - 	--conflict=*)
     --		__gitcomp "diff3 merge" "" "${cur##--conflict=}"
     -+		__gitcomp "diff3 merge zdiff3" "" "${cur##--conflict=}"
     - 		;;
     - 	--*)
     - 		__gitcomp_builtin switch
     -@@ contrib/completion/git-completion.bash: _git_restore ()
     - 
     - 	case "$cur" in
     - 	--conflict=*)
     --		__gitcomp "diff3 merge" "" "${cur##--conflict=}"
     -+		__gitcomp "diff3 merge zdiff3" "" "${cur##--conflict=}"
     - 		;;
     - 	--source=*)
     - 		__git_complete_refs --cur="${cur##--source=}"

-- 
gitgitgadget

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

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

"zdiff3" is identical to ordinary diff3 except that it allows compaction
of common lines on the two sides of history at the beginning or end of
the conflict hunk.  For example, the following diff3 conflict:

    1
    2
    3
    4
    <<<<<<
    A
    B
    C
    D
    E
    ||||||
    5
    6
    ======
    A
    X
    C
    Y
    E
    >>>>>>
    7
    8
    9

has common lines 'A', 'C', and 'E' on the two sides.  With zdiff3, one
would instead get the following conflict:

    1
    2
    3
    4
    A
    <<<<<<
    B
    C
    D
    ||||||
    5
    6
    ======
    X
    C
    Y
    >>>>>>
    E
    7
    8
    9

Note that the common lines, 'A', and 'E' were moved outside the
conflict.  Unlike with the two-way conflicts from the 'merge'
conflictStyle, the zdiff3 conflict is NOT split into multiple conflict
regions to allow the common 'C' lines to be shown outside a conflict,
because zdiff3 shows the base version too and the base version cannot be
reasonably split.

Based-on-patch-by: Uwe Kleine-König <u.kleine-koenig@pengutronix.de>
Helped-by: Phillip Wood <phillip.wood123@gmail.com>
Signed-off-by: Elijah Newren <newren@gmail.com>
---
 builtin/merge-file.c                   |  2 +
 contrib/completion/git-completion.bash |  6 +--
 t/t6427-diff3-conflict-markers.sh      | 56 +++++++++++++++++++++
 xdiff-interface.c                      |  2 +
 xdiff/xdiff.h                          |  1 +
 xdiff/xmerge.c                         | 68 +++++++++++++++++++++++---
 6 files changed, 126 insertions(+), 9 deletions(-)

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;
-- 
gitgitgadget

[PATCH v2 2/2] update documentation for new zdiff3 conflictStyle

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 Documentation/config/merge.txt     |  9 ++++++++-
 Documentation/git-checkout.txt     |  3 +--
 Documentation/git-merge-file.txt   |  3 +++
 Documentation/git-merge.txt        | 32 +++++++++++++++++++++++++-----
 Documentation/git-rebase.txt       |  6 +++---
 Documentation/git-restore.txt      |  3 +--
 Documentation/git-switch.txt       |  3 +--
 Documentation/technical/rerere.txt | 10 +++++-----
 builtin/checkout.c                 |  2 +-
 9 files changed, 50 insertions(+), 21 deletions(-)

diff --git a/Documentation/config/merge.txt b/Documentation/config/merge.txt
index cb2ed589075..52d79117ef8 100644
--- a/Documentation/config/merge.txt
+++ b/Documentation/config/merge.txt
@@ -4,7 +4,14 @@ merge.conflictStyle::
 	shows a `<<<<<<<` conflict marker, changes made by one side,
 	a `=======` marker, changes made by the other side, and then
 	a `>>>>>>>` marker.  An alternate style, "diff3", adds a `|||||||`
-	marker and the original text before the `=======` marker.
+	marker and the original text before the `=======` marker.  The
+	"merge" style tends to produce smaller conflict regions than diff3,
+	both because of the exclusion of the original text, and because
+	when a subset of lines match on the two sides they are just pulled
+	out of the conflict region.  Another alternate style, "zdiff3", is
+	similar to diff3 but removes matching lines on the two sides from
+	the conflict region when those matching lines appear near either
+	the beginning or end of a conflict region.
 
 merge.defaultToUpstream::
 	If merge is called without any commit argument, merge the upstream
diff --git a/Documentation/git-checkout.txt b/Documentation/git-checkout.txt
index b1a6fe44997..85c3d3513f7 100644
--- a/Documentation/git-checkout.txt
+++ b/Documentation/git-checkout.txt
@@ -265,8 +265,7 @@ When switching branches with `--merge`, staged changes may be lost.
 	The same as `--merge` option above, but changes the way the
 	conflicting hunks are presented, overriding the
 	`merge.conflictStyle` configuration variable.  Possible values are
-	"merge" (default) and "diff3" (in addition to what is shown by
-	"merge" style, shows the original contents).
+	"merge" (default), "diff3", and "zdiff3".
 
 -p::
 --patch::
diff --git a/Documentation/git-merge-file.txt b/Documentation/git-merge-file.txt
index f8560326132..7e9093fab60 100644
--- a/Documentation/git-merge-file.txt
+++ b/Documentation/git-merge-file.txt
@@ -70,6 +70,9 @@ OPTIONS
 --diff3::
 	Show conflicts in "diff3" style.
 
+--zdiff3::
+	Show conflicts in "zdiff3" style.
+
 --ours::
 --theirs::
 --union::
diff --git a/Documentation/git-merge.txt b/Documentation/git-merge.txt
index 3819fadac1f..259e1ac2cf0 100644
--- a/Documentation/git-merge.txt
+++ b/Documentation/git-merge.txt
@@ -238,7 +238,8 @@ from the RCS suite to present such a conflicted hunk, like this:
 
 ------------
 Here are lines that are either unchanged from the common
-ancestor, or cleanly resolved because only one side changed.
+ancestor, or cleanly resolved because only one side changed,
+or cleanly resolved because both sides changed the same way.
 <<<<<<< yours:sample.txt
 Conflict resolution is hard;
 let's go shopping.
@@ -259,16 +260,37 @@ side wants to say it is hard and you'd prefer to go shopping, while the
 other side wants to claim it is easy.
 
 An alternative style can be used by setting the "merge.conflictStyle"
-configuration variable to "diff3".  In "diff3" style, the above conflict
-may look like this:
+configuration variable to either "diff3" or "zdiff3".  In "diff3"
+style, the above conflict may look like this:
 
 ------------
 Here are lines that are either unchanged from the common
-ancestor, or cleanly resolved because only one side changed.
+ancestor, or cleanly resolved because only one side changed,
 <<<<<<< yours:sample.txt
+or cleanly resolved because both sides changed the same way.
 Conflict resolution is hard;
 let's go shopping.
-|||||||
+||||||| base:sample.txt
+or cleanly resolved because both sides changed identically.
+Conflict resolution is hard.
+=======
+or cleanly resolved because both sides changed the same way.
+Git makes conflict resolution easy.
+>>>>>>> theirs:sample.txt
+And here is another line that is cleanly resolved or unmodified.
+------------
+
+while in "zdiff3" style, it may look like this:
+
+------------
+Here are lines that are either unchanged from the common
+ancestor, or cleanly resolved because only one side changed,
+or cleanly resolved because both sides changed the same way.
+<<<<<<< yours:sample.txt
+Conflict resolution is hard;
+let's go shopping.
+||||||| base:sample.txt
+or cleanly resolved because both sides changed identically.
 Conflict resolution is hard.
 =======
 Git makes conflict resolution easy.
diff --git a/Documentation/git-rebase.txt b/Documentation/git-rebase.txt
index 55af6fd24e2..a61742c8f98 100644
--- a/Documentation/git-rebase.txt
+++ b/Documentation/git-rebase.txt
@@ -740,9 +740,9 @@ information about the rebased commits and their parents (and instead
 generates new fake commits based off limited information in the
 generated patches), those commits cannot be identified; instead it has
 to fall back to a commit summary.  Also, when merge.conflictStyle is
-set to diff3, the apply backend will use "constructed merge base" to
-label the content from the merge base, and thus provide no information
-about the merge base commit whatsoever.
+set to diff3 or zdiff3, the apply backend will use "constructed merge
+base" to label the content from the merge base, and thus provide no
+information about the merge base commit whatsoever.
 
 The merge backend works with the full commits on both sides of history
 and thus has no such limitations.
diff --git a/Documentation/git-restore.txt b/Documentation/git-restore.txt
index 55bde91ef9e..5964810caa4 100644
--- a/Documentation/git-restore.txt
+++ b/Documentation/git-restore.txt
@@ -92,8 +92,7 @@ in linkgit:git-checkout[1] for details.
 	The same as `--merge` option above, but changes the way the
 	conflicting hunks are presented, overriding the
 	`merge.conflictStyle` configuration variable.  Possible values
-	are "merge" (default) and "diff3" (in addition to what is
-	shown by "merge" style, shows the original contents).
+	are "merge" (default), "diff3", and "zdiff3".
 
 --ignore-unmerged::
 	When restoring files on the working tree from the index, do
diff --git a/Documentation/git-switch.txt b/Documentation/git-switch.txt
index 5c438cd5058..5c90f76fbe3 100644
--- a/Documentation/git-switch.txt
+++ b/Documentation/git-switch.txt
@@ -137,8 +137,7 @@ should result in deletion of the path).
 	The same as `--merge` option above, but changes the way the
 	conflicting hunks are presented, overriding the
 	`merge.conflictStyle` configuration variable.  Possible values are
-	"merge" (default) and "diff3" (in addition to what is shown by
-	"merge" style, shows the original contents).
+	"merge" (default), "diff3", and "zdiff3".
 
 -q::
 --quiet::
diff --git a/Documentation/technical/rerere.txt b/Documentation/technical/rerere.txt
index af5f9fc24f9..35d45414339 100644
--- a/Documentation/technical/rerere.txt
+++ b/Documentation/technical/rerere.txt
@@ -14,9 +14,9 @@ conflicts before writing them to the rerere database.
 
 Different conflict styles and branch names are normalized by stripping
 the labels from the conflict markers, and removing the common ancestor
-version from the `diff3` conflict style. Branches that are merged
-in different order are normalized by sorting the conflict hunks.  More
-on each of those steps in the following sections.
+version from the `diff3` or `zdiff3` conflict styles.  Branches that
+are merged in different order are normalized by sorting the conflict
+hunks.  More on each of those steps in the following sections.
 
 Once these two normalization operations are applied, a conflict ID is
 calculated based on the normalized conflict, which is later used by
@@ -42,8 +42,8 @@ get a conflict like the following:
     >>>>>>> AC
 
 Doing the analogous with AC2 (forking a branch ABAC2 off of branch AB
-and then merging branch AC2 into it), using the diff3 conflict style,
-we get a conflict like the following:
+and then merging branch AC2 into it), using the diff3 or zdiff3
+conflict style, we get a conflict like the following:
 
     <<<<<<< HEAD
     B
diff --git a/builtin/checkout.c b/builtin/checkout.c
index f4cd7747d35..45606936c32 100644
--- a/builtin/checkout.c
+++ b/builtin/checkout.c
@@ -1524,7 +1524,7 @@ static struct option *add_common_options(struct checkout_opts *opts,
 		OPT_BOOL(0, "progress", &opts->show_progress, N_("force progress reporting")),
 		OPT_BOOL('m', "merge", &opts->merge, N_("perform a 3-way merge with the new branch")),
 		OPT_STRING(0, "conflict", &opts->conflict_style, N_("style"),
-			   N_("conflict style (merge or diff3)")),
+			   N_("conflict style (merge, diff3, or zdiff3)")),
 		OPT_END()
 	};
 	struct option *newopts = parse_options_concat(prevopts, options);
-- 
gitgitgadget

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

[Phillip Wood]

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;
> 

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

[Phillip Wood]

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 &&
  

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

[Elijah Newren]

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?

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

[Elijah Newren]

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?

[PATCH v3 0/2] RFC: implement new zdiff3 conflict style

[Elijah Newren via GitGitGadget]

Implement a zealous diff3, or "zdiff3". This new mode is identical to
ordinary diff3 except that it allows compaction of common lines between the
two sides of history, if those common lines occur at the beginning or end of
a conflict hunk.

This is still just RFC, because a testcase provided by Phillip fails. I
think we should get it working first.

Changes since v2:

 * Included more fixes from Phillip, and a new testcase

Changes since v1:

 * Included fixes from Phillip (thanks!)
 * Added some testcases

Elijah Newren (2):
  xdiff: implement a zealous diff3, or "zdiff3"
  update documentation for new zdiff3 conflictStyle

 Documentation/config/merge.txt         |  9 ++-
 Documentation/git-checkout.txt         |  3 +-
 Documentation/git-merge-file.txt       |  3 +
 Documentation/git-merge.txt            | 32 +++++++--
 Documentation/git-rebase.txt           |  6 +-
 Documentation/git-restore.txt          |  3 +-
 Documentation/git-switch.txt           |  3 +-
 Documentation/technical/rerere.txt     | 10 +--
 builtin/checkout.c                     |  2 +-
 builtin/merge-file.c                   |  2 +
 contrib/completion/git-completion.bash |  6 +-
 t/t6427-diff3-conflict-markers.sh      | 90 ++++++++++++++++++++++++++
 xdiff-interface.c                      |  2 +
 xdiff/xdiff.h                          |  1 +
 xdiff/xmerge.c                         | 68 +++++++++++++++++--
 15 files changed, 210 insertions(+), 30 deletions(-)


base-commit: 4c719308ce59dc70e606f910f40801f2c6051b24
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1036%2Fnewren%2Fzdiff3-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1036/newren/zdiff3-v3
Pull-Request: https://github.com/git/git/pull/1036

Range-diff vs v2:

 1:  06e04c88dea ! 1:  798aefbb40a xdiff: implement a zealous diff3, or "zdiff3"
     @@ Commit message
          because zdiff3 shows the base version too and the base version cannot be
          reasonably split.
      
     +    Note also that the removing of lines common to the two sides might make
     +    the remaining text inside the conflict region match the base text inside
     +    the conflict region (for example, if the diff3 conflict had '5 6 E' on
     +    the right side of the conflict, then the common line 'E' would be moved
     +    outside and both the base and right side's remaining conflict text would
     +    be the lines '5' and '6').  This has the potential to surprise users and
     +    make them think there should not have been a conflict, but there
     +    definitely was a conflict and it should remain.
     +
          Based-on-patch-by: Uwe Kleine-König <u.kleine-koenig@pengutronix.de>
     -    Helped-by: Phillip Wood <phillip.wood123@gmail.com>
     +    Co-authored-by: Phillip Wood <phillip.wood123@gmail.com>
          Signed-off-by: Elijah Newren <newren@gmail.com>
      
       ## builtin/merge-file.c ##
     @@ t/t6427-diff3-conflict-markers.sh: test_expect_success 'rebase --apply describes
      +		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 &&
     @@ t/t6427-diff3-conflict-markers.sh: test_expect_success 'rebase --apply describes
      +		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 &&
      +
     @@ t/t6427-diff3-conflict-markers.sh: test_expect_success 'rebase --apply describes
      +		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
      +	)
     @@ t/t6427-diff3-conflict-markers.sh: test_expect_success 'rebase --apply describes
      +
      +		git checkout left^0 &&
      +
     ++		base=$(git rev-parse --short HEAD^1) &&
      +		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_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_write_lines 1 2 3 \
     ++				 "<<<<<<< HEAD" CC \
     ++				 "||||||| $base" AA \
     ++				 ======= EE \
     ++				 ">>>>>>> right^0" \
     ++				 4 5 \
     ++				 "<<<<<<< HEAD" DD \
     ++				 "||||||| $base" 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_write_lines 1 2 3 4 A B C \
     ++				 "<<<<<<< HEAD" D E F \
     ++				 "||||||| $base" 5 6 \
     ++				 ======= 5 6 \
     ++				 ">>>>>>> right^0" \
     ++				 G H I J 7 8 9 \
     ++				 >expect &&
     ++		test_cmp expect interesting &&
     ++
     ++		# Not passing this one yet; the common "B C" lines is still
     ++		# being left in the conflict blocks on the left and right
     ++		# sides.
     ++		test_write_lines 1 2 3 4 \
     ++				 "<<<<<<< HEAD" X A \
     ++				 "||||||| $base" 5 6 \
     ++				 ======= Y A B C \
     ++				 ">>>>>>> right^0" \
     ++				 B C 7 8 9 \
     ++				 >expect &&
     ++		test_cmp expect evil
      +	)
      +'
      +
 2:  9ce7246c0e9 = 2:  90aee68e14a update documentation for new zdiff3 conflictStyle

-- 
gitgitgadget

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

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

"zdiff3" is identical to ordinary diff3 except that it allows compaction
of common lines on the two sides of history at the beginning or end of
the conflict hunk.  For example, the following diff3 conflict:

    1
    2
    3
    4
    <<<<<<
    A
    B
    C
    D
    E
    ||||||
    5
    6
    ======
    A
    X
    C
    Y
    E
    >>>>>>
    7
    8
    9

has common lines 'A', 'C', and 'E' on the two sides.  With zdiff3, one
would instead get the following conflict:

    1
    2
    3
    4
    A
    <<<<<<
    B
    C
    D
    ||||||
    5
    6
    ======
    X
    C
    Y
    >>>>>>
    E
    7
    8
    9

Note that the common lines, 'A', and 'E' were moved outside the
conflict.  Unlike with the two-way conflicts from the 'merge'
conflictStyle, the zdiff3 conflict is NOT split into multiple conflict
regions to allow the common 'C' lines to be shown outside a conflict,
because zdiff3 shows the base version too and the base version cannot be
reasonably split.

Note also that the removing of lines common to the two sides might make
the remaining text inside the conflict region match the base text inside
the conflict region (for example, if the diff3 conflict had '5 6 E' on
the right side of the conflict, then the common line 'E' would be moved
outside and both the base and right side's remaining conflict text would
be the lines '5' and '6').  This has the potential to surprise users and
make them think there should not have been a conflict, but there
definitely was a conflict and it should remain.

Based-on-patch-by: Uwe Kleine-König <u.kleine-koenig@pengutronix.de>
Co-authored-by: Phillip Wood <phillip.wood123@gmail.com>
Signed-off-by: Elijah Newren <newren@gmail.com>
---
 builtin/merge-file.c                   |  2 +
 contrib/completion/git-completion.bash |  6 +-
 t/t6427-diff3-conflict-markers.sh      | 90 ++++++++++++++++++++++++++
 xdiff-interface.c                      |  2 +
 xdiff/xdiff.h                          |  1 +
 xdiff/xmerge.c                         | 68 +++++++++++++++++--
 6 files changed, 160 insertions(+), 9 deletions(-)

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 8108eda1e86..a7fb14e9a40 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
@@ -2446,7 +2446,7 @@ _git_switch ()
 
 	case "$cur" in
 	--conflict=*)
-		__gitcomp "diff3 merge" "" "${cur##--conflict=}"
+		__gitcomp "diff3 merge zdiff3" "" "${cur##--conflict=}"
 		;;
 	--*)
 		__gitcomp_builtin switch
@@ -2887,7 +2887,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..dc740757187 100755
--- a/t/t6427-diff3-conflict-markers.sh
+++ b/t/t6427-diff3-conflict-markers.sh
@@ -211,4 +211,94 @@ 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 &&
+		test_write_lines 1 2 3 4 5 6 7 8 9 >evil &&
+
+		git add basic middle-common interesting evil &&
+		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 &&
+		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_setup_zdiff3 &&
+	(
+		cd zdiff3 &&
+
+		git checkout left^0 &&
+
+		base=$(git rev-parse --short HEAD^1) &&
+		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 \
+				 "||||||| $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 \
+				 "||||||| $base" AA \
+				 ======= EE \
+				 ">>>>>>> right^0" \
+				 4 5 \
+				 "<<<<<<< HEAD" DD \
+				 "||||||| $base" BB \
+				 ======= FF \
+				 ">>>>>>> right^0" \
+				 6 7 8 \
+				 >expect &&
+		test_cmp expect middle-common &&
+
+		test_write_lines 1 2 3 4 A B C \
+				 "<<<<<<< HEAD" D E F \
+				 "||||||| $base" 5 6 \
+				 ======= 5 6 \
+				 ">>>>>>> right^0" \
+				 G H I J 7 8 9 \
+				 >expect &&
+		test_cmp expect interesting &&
+
+		# Not passing this one yet; the common "B C" lines is still
+		# being left in the conflict blocks on the left and right
+		# sides.
+		test_write_lines 1 2 3 4 \
+				 "<<<<<<< HEAD" X A \
+				 "||||||| $base" 5 6 \
+				 ======= Y A B C \
+				 ">>>>>>> right^0" \
+				 B C 7 8 9 \
+				 >expect &&
+		test_cmp expect evil
+	)
+'
+
 test_done
diff --git a/xdiff-interface.c b/xdiff-interface.c
index 75b32aef51d..2e3a5a2943e 100644
--- a/xdiff-interface.c
+++ b/xdiff-interface.c
@@ -313,6 +313,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 b29deca5de8..72e25a9ffa5 100644
--- a/xdiff/xdiff.h
+++ b/xdiff/xdiff.h
@@ -66,6 +66,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;
-- 
gitgitgadget

[PATCH v3 2/2] update documentation for new zdiff3 conflictStyle

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 Documentation/config/merge.txt     |  9 ++++++++-
 Documentation/git-checkout.txt     |  3 +--
 Documentation/git-merge-file.txt   |  3 +++
 Documentation/git-merge.txt        | 32 +++++++++++++++++++++++++-----
 Documentation/git-rebase.txt       |  6 +++---
 Documentation/git-restore.txt      |  3 +--
 Documentation/git-switch.txt       |  3 +--
 Documentation/technical/rerere.txt | 10 +++++-----
 builtin/checkout.c                 |  2 +-
 9 files changed, 50 insertions(+), 21 deletions(-)

diff --git a/Documentation/config/merge.txt b/Documentation/config/merge.txt
index e27cc639447..99e83dd36e5 100644
--- a/Documentation/config/merge.txt
+++ b/Documentation/config/merge.txt
@@ -4,7 +4,14 @@ merge.conflictStyle::
 	shows a `<<<<<<<` conflict marker, changes made by one side,
 	a `=======` marker, changes made by the other side, and then
 	a `>>>>>>>` marker.  An alternate style, "diff3", adds a `|||||||`
-	marker and the original text before the `=======` marker.
+	marker and the original text before the `=======` marker.  The
+	"merge" style tends to produce smaller conflict regions than diff3,
+	both because of the exclusion of the original text, and because
+	when a subset of lines match on the two sides they are just pulled
+	out of the conflict region.  Another alternate style, "zdiff3", is
+	similar to diff3 but removes matching lines on the two sides from
+	the conflict region when those matching lines appear near either
+	the beginning or end of a conflict region.
 
 merge.defaultToUpstream::
 	If merge is called without any commit argument, merge the upstream
diff --git a/Documentation/git-checkout.txt b/Documentation/git-checkout.txt
index b1a6fe44997..85c3d3513f7 100644
--- a/Documentation/git-checkout.txt
+++ b/Documentation/git-checkout.txt
@@ -265,8 +265,7 @@ When switching branches with `--merge`, staged changes may be lost.
 	The same as `--merge` option above, but changes the way the
 	conflicting hunks are presented, overriding the
 	`merge.conflictStyle` configuration variable.  Possible values are
-	"merge" (default) and "diff3" (in addition to what is shown by
-	"merge" style, shows the original contents).
+	"merge" (default), "diff3", and "zdiff3".
 
 -p::
 --patch::
diff --git a/Documentation/git-merge-file.txt b/Documentation/git-merge-file.txt
index f8560326132..7e9093fab60 100644
--- a/Documentation/git-merge-file.txt
+++ b/Documentation/git-merge-file.txt
@@ -70,6 +70,9 @@ OPTIONS
 --diff3::
 	Show conflicts in "diff3" style.
 
+--zdiff3::
+	Show conflicts in "zdiff3" style.
+
 --ours::
 --theirs::
 --union::
diff --git a/Documentation/git-merge.txt b/Documentation/git-merge.txt
index e4f3352eb58..e8cecf5a51d 100644
--- a/Documentation/git-merge.txt
+++ b/Documentation/git-merge.txt
@@ -240,7 +240,8 @@ from the RCS suite to present such a conflicted hunk, like this:
 
 ------------
 Here are lines that are either unchanged from the common
-ancestor, or cleanly resolved because only one side changed.
+ancestor, or cleanly resolved because only one side changed,
+or cleanly resolved because both sides changed the same way.
 <<<<<<< yours:sample.txt
 Conflict resolution is hard;
 let's go shopping.
@@ -261,16 +262,37 @@ side wants to say it is hard and you'd prefer to go shopping, while the
 other side wants to claim it is easy.
 
 An alternative style can be used by setting the "merge.conflictStyle"
-configuration variable to "diff3".  In "diff3" style, the above conflict
-may look like this:
+configuration variable to either "diff3" or "zdiff3".  In "diff3"
+style, the above conflict may look like this:
 
 ------------
 Here are lines that are either unchanged from the common
-ancestor, or cleanly resolved because only one side changed.
+ancestor, or cleanly resolved because only one side changed,
 <<<<<<< yours:sample.txt
+or cleanly resolved because both sides changed the same way.
 Conflict resolution is hard;
 let's go shopping.
-|||||||
+||||||| base:sample.txt
+or cleanly resolved because both sides changed identically.
+Conflict resolution is hard.
+=======
+or cleanly resolved because both sides changed the same way.
+Git makes conflict resolution easy.
+>>>>>>> theirs:sample.txt
+And here is another line that is cleanly resolved or unmodified.
+------------
+
+while in "zdiff3" style, it may look like this:
+
+------------
+Here are lines that are either unchanged from the common
+ancestor, or cleanly resolved because only one side changed,
+or cleanly resolved because both sides changed the same way.
+<<<<<<< yours:sample.txt
+Conflict resolution is hard;
+let's go shopping.
+||||||| base:sample.txt
+or cleanly resolved because both sides changed identically.
 Conflict resolution is hard.
 =======
 Git makes conflict resolution easy.
diff --git a/Documentation/git-rebase.txt b/Documentation/git-rebase.txt
index 506345cb0ed..dd9830dc5f8 100644
--- a/Documentation/git-rebase.txt
+++ b/Documentation/git-rebase.txt
@@ -741,9 +741,9 @@ information about the rebased commits and their parents (and instead
 generates new fake commits based off limited information in the
 generated patches), those commits cannot be identified; instead it has
 to fall back to a commit summary.  Also, when merge.conflictStyle is
-set to diff3, the apply backend will use "constructed merge base" to
-label the content from the merge base, and thus provide no information
-about the merge base commit whatsoever.
+set to diff3 or zdiff3, the apply backend will use "constructed merge
+base" to label the content from the merge base, and thus provide no
+information about the merge base commit whatsoever.
 
 The merge backend works with the full commits on both sides of history
 and thus has no such limitations.
diff --git a/Documentation/git-restore.txt b/Documentation/git-restore.txt
index 55bde91ef9e..5964810caa4 100644
--- a/Documentation/git-restore.txt
+++ b/Documentation/git-restore.txt
@@ -92,8 +92,7 @@ in linkgit:git-checkout[1] for details.
 	The same as `--merge` option above, but changes the way the
 	conflicting hunks are presented, overriding the
 	`merge.conflictStyle` configuration variable.  Possible values
-	are "merge" (default) and "diff3" (in addition to what is
-	shown by "merge" style, shows the original contents).
+	are "merge" (default), "diff3", and "zdiff3".
 
 --ignore-unmerged::
 	When restoring files on the working tree from the index, do
diff --git a/Documentation/git-switch.txt b/Documentation/git-switch.txt
index 5c438cd5058..5c90f76fbe3 100644
--- a/Documentation/git-switch.txt
+++ b/Documentation/git-switch.txt
@@ -137,8 +137,7 @@ should result in deletion of the path).
 	The same as `--merge` option above, but changes the way the
 	conflicting hunks are presented, overriding the
 	`merge.conflictStyle` configuration variable.  Possible values are
-	"merge" (default) and "diff3" (in addition to what is shown by
-	"merge" style, shows the original contents).
+	"merge" (default), "diff3", and "zdiff3".
 
 -q::
 --quiet::
diff --git a/Documentation/technical/rerere.txt b/Documentation/technical/rerere.txt
index af5f9fc24f9..35d45414339 100644
--- a/Documentation/technical/rerere.txt
+++ b/Documentation/technical/rerere.txt
@@ -14,9 +14,9 @@ conflicts before writing them to the rerere database.
 
 Different conflict styles and branch names are normalized by stripping
 the labels from the conflict markers, and removing the common ancestor
-version from the `diff3` conflict style. Branches that are merged
-in different order are normalized by sorting the conflict hunks.  More
-on each of those steps in the following sections.
+version from the `diff3` or `zdiff3` conflict styles.  Branches that
+are merged in different order are normalized by sorting the conflict
+hunks.  More on each of those steps in the following sections.
 
 Once these two normalization operations are applied, a conflict ID is
 calculated based on the normalized conflict, which is later used by
@@ -42,8 +42,8 @@ get a conflict like the following:
     >>>>>>> AC
 
 Doing the analogous with AC2 (forking a branch ABAC2 off of branch AB
-and then merging branch AC2 into it), using the diff3 conflict style,
-we get a conflict like the following:
+and then merging branch AC2 into it), using the diff3 or zdiff3
+conflict style, we get a conflict like the following:
 
     <<<<<<< HEAD
     B
diff --git a/builtin/checkout.c b/builtin/checkout.c
index 8c69dcdf72a..a0b0fac6a68 100644
--- a/builtin/checkout.c
+++ b/builtin/checkout.c
@@ -1519,7 +1519,7 @@ static struct option *add_common_options(struct checkout_opts *opts,
 		OPT_BOOL(0, "progress", &opts->show_progress, N_("force progress reporting")),
 		OPT_BOOL('m', "merge", &opts->merge, N_("perform a 3-way merge with the new branch")),
 		OPT_STRING(0, "conflict", &opts->conflict_style, N_("style"),
-			   N_("conflict style (merge or diff3)")),
+			   N_("conflict style (merge, diff3, or zdiff3)")),
 		OPT_END()
 	};
 	struct option *newopts = parse_options_concat(prevopts, options);
-- 
gitgitgadget

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

[Phillip Wood]

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?
> 

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

[Phillip Wood]

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/

[PATCH v4 0/2] Implement new zdiff3 conflict style

[Elijah Newren via GitGitGadget]

Implement a zealous diff3, or "zdiff3". This new mode is identical to
ordinary diff3 except that it allows compaction of common lines between the
two sides of history, if those common lines occur at the beginning or end of
a conflict hunk.

Changes since v3:

 * More fixes from Phillip.
 * Marked Phillip as the author of the first commit because he's written
   most the code now; gave myself a co-authored-by trailer on that commit.
 * Removed the RFC label since it's now passing our tests.

Changes since v2:

 * Included more fixes from Phillip, and a new testcase

Changes since v1:

 * Included fixes from Phillip (thanks!)
 * Added some testcases

Elijah Newren (1):
  update documentation for new zdiff3 conflictStyle

Phillip Wood (1):
  xdiff: implement a zealous diff3, or "zdiff3"

 Documentation/config/merge.txt         |  9 ++-
 Documentation/git-checkout.txt         |  3 +-
 Documentation/git-merge-file.txt       |  3 +
 Documentation/git-merge.txt            | 32 +++++++--
 Documentation/git-rebase.txt           |  6 +-
 Documentation/git-restore.txt          |  3 +-
 Documentation/git-switch.txt           |  3 +-
 Documentation/technical/rerere.txt     | 10 +--
 builtin/checkout.c                     |  2 +-
 builtin/merge-file.c                   |  2 +
 contrib/completion/git-completion.bash |  6 +-
 t/t6427-diff3-conflict-markers.sh      | 90 ++++++++++++++++++++++++++
 xdiff-interface.c                      |  2 +
 xdiff/xdiff.h                          |  1 +
 xdiff/xmerge.c                         | 63 ++++++++++++++++--
 15 files changed, 205 insertions(+), 30 deletions(-)


base-commit: 4c719308ce59dc70e606f910f40801f2c6051b24
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1036%2Fnewren%2Fzdiff3-v4
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1036/newren/zdiff3-v4
Pull-Request: https://github.com/git/git/pull/1036

Range-diff vs v3:

 1:  798aefbb40a ! 1:  473fae82da1 xdiff: implement a zealous diff3, or "zdiff3"
     @@
       ## Metadata ##
     -Author: Elijah Newren <newren@gmail.com>
     +Author: Phillip Wood <phillip.wood@dunelm.org.uk>
      
       ## Commit message ##
          xdiff: implement a zealous diff3, or "zdiff3"
     @@ Commit message
          definitely was a conflict and it should remain.
      
          Based-on-patch-by: Uwe Kleine-König <u.kleine-koenig@pengutronix.de>
     -    Co-authored-by: Phillip Wood <phillip.wood123@gmail.com>
     +    Co-authored-by: Elijah Newren <newren@gmail.com>
     +    Signed-off-by: Phillip Wood <phillip.wood123@gmail.com>
          Signed-off-by: Elijah Newren <newren@gmail.com>
      
       ## builtin/merge-file.c ##
     @@ t/t6427-diff3-conflict-markers.sh: test_expect_success 'rebase --apply describes
      +	)
      +}
      +
     -+test_expect_failure 'check zdiff3 markers' '
     ++test_expect_success 'check zdiff3 markers' '
      +	test_setup_zdiff3 &&
      +	(
      +		cd zdiff3 &&
     @@ xdiff/xmerge.c: static int fill_conflict_hunk(xdfenv_t *xe1, const char *name1,
       		if (!dest) {
       			size += marker_size + 1 + needs_cr + marker3_size;
      @@ xdiff/xmerge.c: 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;
     -@@ xdiff/xmerge.c: 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;
     + 	return size;
     + }
     + 
     ++static int recmatch(xrecord_t *rec1, xrecord_t *rec2, unsigned long flags)
     ++{
     ++	return xdl_recmatch(rec1->ptr, rec1->size,
     ++			    rec2->ptr, rec2->size, flags);
     ++}
      +
     -+			/*
     -+			 * 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);
     ++/*
     ++ * Remove any common lines from the beginning and end of the conflicted region.
     ++ */
     ++static void xdl_refine_zdiff3_conflicts(xdfenv_t *xe1, xdfenv_t *xe2, xdmerge_t *m,
     ++		xpparam_t const *xpp)
     ++{
     ++	xrecord_t **rec1 = xe1->xdf2.recs, **rec2 = xe2->xdf2.recs;
     ++	for (; m; m = m->next) {
     ++		/* let's handle just the conflicts */
     ++		if (m->mode)
      +			continue;
     ++
     ++		while(m->chg1 && m->chg2 &&
     ++		      recmatch(rec1[m->i1], rec2[m->i2], xpp->flags)) {
     ++			m->chg1--;
     ++			m->chg2--;
     ++			m->i1++;
     ++			m->i2++;
      +		}
     - 		m->i1 = xscr->i1 + i1;
     - 		m->chg1 = xscr->chg1;
     - 		m->i2 = xscr->i2 + i2;
     -@@ xdiff/xmerge.c: 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;
     -@@ xdiff/xmerge.c: 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;
     ++		while (m->chg1 && m->chg2 &&
     ++		       recmatch(rec1[m->i1 + m->chg1 - 1],
     ++				rec2[m->i2 + m->chg2 - 1], xpp->flags)) {
     ++			m->chg1--;
     ++			m->chg2--;
     ++		}
     ++	}
     ++}
     ++
     + /*
     +  * Sometimes, changes are not quite identical, but differ in only a few
     +  * lines. Try hard to show only these few lines as conflicting.
      @@ xdiff/xmerge.c: static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1,
       	int style = xmp->style;
       	int favor = xmp->favor;
       
     +-	if (style == XDL_MERGE_DIFF3) {
      +	/*
      +	 * XDL_MERGE_DIFF3 does not attempt to refine conflicts by looking
      +	 * at common areas of sides 1 & 2, because the base (side 0) does
     @@ xdiff/xmerge.c: static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1,
      +	 * 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) {
     ++	if (style == XDL_MERGE_DIFF3 || style == XDL_MERGE_ZEALOUS_DIFF3) {
       		/*
       		 * "diff3 -m" output does not make sense for anything
     + 		 * more aggressive than XDL_MERGE_EAGER.
      @@ xdiff/xmerge.c: static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1,
     + 	if (!changes)
       		changes = c;
       	/* refine conflicts */
     - 	if (XDL_MERGE_ZEALOUS <= level &&
     +-	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_MERGE_ZEALOUS < level) < 0)) {
     ++	if (style == XDL_MERGE_ZEALOUS_DIFF3) {
     ++		xdl_refine_zdiff3_conflicts(xe1, xe2, changes, xpp);
     ++	} else if (XDL_MERGE_ZEALOUS <= level &&
     ++		   (xdl_refine_conflicts(xe1, xe2, changes, xpp) < 0 ||
     ++		    xdl_simplify_non_conflicts(xe1, changes,
     ++					       XDL_MERGE_ZEALOUS < level) < 0)) {
       		xdl_cleanup_merge(changes);
       		return -1;
     + 	}
 2:  90aee68e14a = 2:  69f20a702b4 update documentation for new zdiff3 conflictStyle

-- 
gitgitgadget

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

[Phillip Wood via GitGitGadget]

From: Phillip Wood <phillip.wood@dunelm.org.uk>

"zdiff3" is identical to ordinary diff3 except that it allows compaction
of common lines on the two sides of history at the beginning or end of
the conflict hunk.  For example, the following diff3 conflict:

    1
    2
    3
    4
    <<<<<<
    A
    B
    C
    D
    E
    ||||||
    5
    6
    ======
    A
    X
    C
    Y
    E
    >>>>>>
    7
    8
    9

has common lines 'A', 'C', and 'E' on the two sides.  With zdiff3, one
would instead get the following conflict:

    1
    2
    3
    4
    A
    <<<<<<
    B
    C
    D
    ||||||
    5
    6
    ======
    X
    C
    Y
    >>>>>>
    E
    7
    8
    9

Note that the common lines, 'A', and 'E' were moved outside the
conflict.  Unlike with the two-way conflicts from the 'merge'
conflictStyle, the zdiff3 conflict is NOT split into multiple conflict
regions to allow the common 'C' lines to be shown outside a conflict,
because zdiff3 shows the base version too and the base version cannot be
reasonably split.

Note also that the removing of lines common to the two sides might make
the remaining text inside the conflict region match the base text inside
the conflict region (for example, if the diff3 conflict had '5 6 E' on
the right side of the conflict, then the common line 'E' would be moved
outside and both the base and right side's remaining conflict text would
be the lines '5' and '6').  This has the potential to surprise users and
make them think there should not have been a conflict, but there
definitely was a conflict and it should remain.

Based-on-patch-by: Uwe Kleine-König <u.kleine-koenig@pengutronix.de>
Co-authored-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Phillip Wood <phillip.wood123@gmail.com>
Signed-off-by: Elijah Newren <newren@gmail.com>
---
 builtin/merge-file.c                   |  2 +
 contrib/completion/git-completion.bash |  6 +-
 t/t6427-diff3-conflict-markers.sh      | 90 ++++++++++++++++++++++++++
 xdiff-interface.c                      |  2 +
 xdiff/xdiff.h                          |  1 +
 xdiff/xmerge.c                         | 63 ++++++++++++++++--
 6 files changed, 155 insertions(+), 9 deletions(-)

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 8108eda1e86..a7fb14e9a40 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
@@ -2446,7 +2446,7 @@ _git_switch ()
 
 	case "$cur" in
 	--conflict=*)
-		__gitcomp "diff3 merge" "" "${cur##--conflict=}"
+		__gitcomp "diff3 merge zdiff3" "" "${cur##--conflict=}"
 		;;
 	--*)
 		__gitcomp_builtin switch
@@ -2887,7 +2887,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..a9ee4cb207a 100755
--- a/t/t6427-diff3-conflict-markers.sh
+++ b/t/t6427-diff3-conflict-markers.sh
@@ -211,4 +211,94 @@ 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 &&
+		test_write_lines 1 2 3 4 5 6 7 8 9 >evil &&
+
+		git add basic middle-common interesting evil &&
+		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 &&
+		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_success 'check zdiff3 markers' '
+	test_setup_zdiff3 &&
+	(
+		cd zdiff3 &&
+
+		git checkout left^0 &&
+
+		base=$(git rev-parse --short HEAD^1) &&
+		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 \
+				 "||||||| $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 \
+				 "||||||| $base" AA \
+				 ======= EE \
+				 ">>>>>>> right^0" \
+				 4 5 \
+				 "<<<<<<< HEAD" DD \
+				 "||||||| $base" BB \
+				 ======= FF \
+				 ">>>>>>> right^0" \
+				 6 7 8 \
+				 >expect &&
+		test_cmp expect middle-common &&
+
+		test_write_lines 1 2 3 4 A B C \
+				 "<<<<<<< HEAD" D E F \
+				 "||||||| $base" 5 6 \
+				 ======= 5 6 \
+				 ">>>>>>> right^0" \
+				 G H I J 7 8 9 \
+				 >expect &&
+		test_cmp expect interesting &&
+
+		# Not passing this one yet; the common "B C" lines is still
+		# being left in the conflict blocks on the left and right
+		# sides.
+		test_write_lines 1 2 3 4 \
+				 "<<<<<<< HEAD" X A \
+				 "||||||| $base" 5 6 \
+				 ======= Y A B C \
+				 ">>>>>>> right^0" \
+				 B C 7 8 9 \
+				 >expect &&
+		test_cmp expect evil
+	)
+'
+
 test_done
diff --git a/xdiff-interface.c b/xdiff-interface.c
index 75b32aef51d..2e3a5a2943e 100644
--- a/xdiff-interface.c
+++ b/xdiff-interface.c
@@ -313,6 +313,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 b29deca5de8..72e25a9ffa5 100644
--- a/xdiff/xdiff.h
+++ b/xdiff/xdiff.h
@@ -66,6 +66,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..fff0b594f9a 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;
@@ -322,6 +322,40 @@ static int xdl_fill_merge_buffer(xdfenv_t *xe1, const char *name1,
 	return size;
 }
 
+static int recmatch(xrecord_t *rec1, xrecord_t *rec2, unsigned long flags)
+{
+	return xdl_recmatch(rec1->ptr, rec1->size,
+			    rec2->ptr, rec2->size, flags);
+}
+
+/*
+ * Remove any common lines from the beginning and end of the conflicted region.
+ */
+static void xdl_refine_zdiff3_conflicts(xdfenv_t *xe1, xdfenv_t *xe2, xdmerge_t *m,
+		xpparam_t const *xpp)
+{
+	xrecord_t **rec1 = xe1->xdf2.recs, **rec2 = xe2->xdf2.recs;
+	for (; m; m = m->next) {
+		/* let's handle just the conflicts */
+		if (m->mode)
+			continue;
+
+		while(m->chg1 && m->chg2 &&
+		      recmatch(rec1[m->i1], rec2[m->i2], xpp->flags)) {
+			m->chg1--;
+			m->chg2--;
+			m->i1++;
+			m->i2++;
+		}
+		while (m->chg1 && m->chg2 &&
+		       recmatch(rec1[m->i1 + m->chg1 - 1],
+				rec2[m->i2 + m->chg2 - 1], xpp->flags)) {
+			m->chg1--;
+			m->chg2--;
+		}
+	}
+}
+
 /*
  * Sometimes, changes are not quite identical, but differ in only a few
  * lines. Try hard to show only these few lines as conflicting.
@@ -482,7 +516,22 @@ static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1,
 	int style = xmp->style;
 	int favor = xmp->favor;
 
-	if (style == XDL_MERGE_DIFF3) {
+	/*
+	 * 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.
+	 */
+	if (style == XDL_MERGE_DIFF3 || style == XDL_MERGE_ZEALOUS_DIFF3) {
 		/*
 		 * "diff3 -m" output does not make sense for anything
 		 * more aggressive than XDL_MERGE_EAGER.
@@ -603,10 +652,12 @@ static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1,
 	if (!changes)
 		changes = c;
 	/* refine conflicts */
-	if (XDL_MERGE_ZEALOUS <= level &&
-	    (xdl_refine_conflicts(xe1, xe2, changes, xpp) < 0 ||
-	     xdl_simplify_non_conflicts(xe1, changes,
-					XDL_MERGE_ZEALOUS < level) < 0)) {
+	if (style == XDL_MERGE_ZEALOUS_DIFF3) {
+		xdl_refine_zdiff3_conflicts(xe1, xe2, changes, xpp);
+	} else if (XDL_MERGE_ZEALOUS <= level &&
+		   (xdl_refine_conflicts(xe1, xe2, changes, xpp) < 0 ||
+		    xdl_simplify_non_conflicts(xe1, changes,
+					       XDL_MERGE_ZEALOUS < level) < 0)) {
 		xdl_cleanup_merge(changes);
 		return -1;
 	}
-- 
gitgitgadget

[PATCH v4 2/2] update documentation for new zdiff3 conflictStyle

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 Documentation/config/merge.txt     |  9 ++++++++-
 Documentation/git-checkout.txt     |  3 +--
 Documentation/git-merge-file.txt   |  3 +++
 Documentation/git-merge.txt        | 32 +++++++++++++++++++++++++-----
 Documentation/git-rebase.txt       |  6 +++---
 Documentation/git-restore.txt      |  3 +--
 Documentation/git-switch.txt       |  3 +--
 Documentation/technical/rerere.txt | 10 +++++-----
 builtin/checkout.c                 |  2 +-
 9 files changed, 50 insertions(+), 21 deletions(-)

diff --git a/Documentation/config/merge.txt b/Documentation/config/merge.txt
index e27cc639447..99e83dd36e5 100644
--- a/Documentation/config/merge.txt
+++ b/Documentation/config/merge.txt
@@ -4,7 +4,14 @@ merge.conflictStyle::
 	shows a `<<<<<<<` conflict marker, changes made by one side,
 	a `=======` marker, changes made by the other side, and then
 	a `>>>>>>>` marker.  An alternate style, "diff3", adds a `|||||||`
-	marker and the original text before the `=======` marker.
+	marker and the original text before the `=======` marker.  The
+	"merge" style tends to produce smaller conflict regions than diff3,
+	both because of the exclusion of the original text, and because
+	when a subset of lines match on the two sides they are just pulled
+	out of the conflict region.  Another alternate style, "zdiff3", is
+	similar to diff3 but removes matching lines on the two sides from
+	the conflict region when those matching lines appear near either
+	the beginning or end of a conflict region.
 
 merge.defaultToUpstream::
 	If merge is called without any commit argument, merge the upstream
diff --git a/Documentation/git-checkout.txt b/Documentation/git-checkout.txt
index b1a6fe44997..85c3d3513f7 100644
--- a/Documentation/git-checkout.txt
+++ b/Documentation/git-checkout.txt
@@ -265,8 +265,7 @@ When switching branches with `--merge`, staged changes may be lost.
 	The same as `--merge` option above, but changes the way the
 	conflicting hunks are presented, overriding the
 	`merge.conflictStyle` configuration variable.  Possible values are
-	"merge" (default) and "diff3" (in addition to what is shown by
-	"merge" style, shows the original contents).
+	"merge" (default), "diff3", and "zdiff3".
 
 -p::
 --patch::
diff --git a/Documentation/git-merge-file.txt b/Documentation/git-merge-file.txt
index f8560326132..7e9093fab60 100644
--- a/Documentation/git-merge-file.txt
+++ b/Documentation/git-merge-file.txt
@@ -70,6 +70,9 @@ OPTIONS
 --diff3::
 	Show conflicts in "diff3" style.
 
+--zdiff3::
+	Show conflicts in "zdiff3" style.
+
 --ours::
 --theirs::
 --union::
diff --git a/Documentation/git-merge.txt b/Documentation/git-merge.txt
index e4f3352eb58..e8cecf5a51d 100644
--- a/Documentation/git-merge.txt
+++ b/Documentation/git-merge.txt
@@ -240,7 +240,8 @@ from the RCS suite to present such a conflicted hunk, like this:
 
 ------------
 Here are lines that are either unchanged from the common
-ancestor, or cleanly resolved because only one side changed.
+ancestor, or cleanly resolved because only one side changed,
+or cleanly resolved because both sides changed the same way.
 <<<<<<< yours:sample.txt
 Conflict resolution is hard;
 let's go shopping.
@@ -261,16 +262,37 @@ side wants to say it is hard and you'd prefer to go shopping, while the
 other side wants to claim it is easy.
 
 An alternative style can be used by setting the "merge.conflictStyle"
-configuration variable to "diff3".  In "diff3" style, the above conflict
-may look like this:
+configuration variable to either "diff3" or "zdiff3".  In "diff3"
+style, the above conflict may look like this:
 
 ------------
 Here are lines that are either unchanged from the common
-ancestor, or cleanly resolved because only one side changed.
+ancestor, or cleanly resolved because only one side changed,
 <<<<<<< yours:sample.txt
+or cleanly resolved because both sides changed the same way.
 Conflict resolution is hard;
 let's go shopping.
-|||||||
+||||||| base:sample.txt
+or cleanly resolved because both sides changed identically.
+Conflict resolution is hard.
+=======
+or cleanly resolved because both sides changed the same way.
+Git makes conflict resolution easy.
+>>>>>>> theirs:sample.txt
+And here is another line that is cleanly resolved or unmodified.
+------------
+
+while in "zdiff3" style, it may look like this:
+
+------------
+Here are lines that are either unchanged from the common
+ancestor, or cleanly resolved because only one side changed,
+or cleanly resolved because both sides changed the same way.
+<<<<<<< yours:sample.txt
+Conflict resolution is hard;
+let's go shopping.
+||||||| base:sample.txt
+or cleanly resolved because both sides changed identically.
 Conflict resolution is hard.
 =======
 Git makes conflict resolution easy.
diff --git a/Documentation/git-rebase.txt b/Documentation/git-rebase.txt
index 506345cb0ed..dd9830dc5f8 100644
--- a/Documentation/git-rebase.txt
+++ b/Documentation/git-rebase.txt
@@ -741,9 +741,9 @@ information about the rebased commits and their parents (and instead
 generates new fake commits based off limited information in the
 generated patches), those commits cannot be identified; instead it has
 to fall back to a commit summary.  Also, when merge.conflictStyle is
-set to diff3, the apply backend will use "constructed merge base" to
-label the content from the merge base, and thus provide no information
-about the merge base commit whatsoever.
+set to diff3 or zdiff3, the apply backend will use "constructed merge
+base" to label the content from the merge base, and thus provide no
+information about the merge base commit whatsoever.
 
 The merge backend works with the full commits on both sides of history
 and thus has no such limitations.
diff --git a/Documentation/git-restore.txt b/Documentation/git-restore.txt
index 55bde91ef9e..5964810caa4 100644
--- a/Documentation/git-restore.txt
+++ b/Documentation/git-restore.txt
@@ -92,8 +92,7 @@ in linkgit:git-checkout[1] for details.
 	The same as `--merge` option above, but changes the way the
 	conflicting hunks are presented, overriding the
 	`merge.conflictStyle` configuration variable.  Possible values
-	are "merge" (default) and "diff3" (in addition to what is
-	shown by "merge" style, shows the original contents).
+	are "merge" (default), "diff3", and "zdiff3".
 
 --ignore-unmerged::
 	When restoring files on the working tree from the index, do
diff --git a/Documentation/git-switch.txt b/Documentation/git-switch.txt
index 5c438cd5058..5c90f76fbe3 100644
--- a/Documentation/git-switch.txt
+++ b/Documentation/git-switch.txt
@@ -137,8 +137,7 @@ should result in deletion of the path).
 	The same as `--merge` option above, but changes the way the
 	conflicting hunks are presented, overriding the
 	`merge.conflictStyle` configuration variable.  Possible values are
-	"merge" (default) and "diff3" (in addition to what is shown by
-	"merge" style, shows the original contents).
+	"merge" (default), "diff3", and "zdiff3".
 
 -q::
 --quiet::
diff --git a/Documentation/technical/rerere.txt b/Documentation/technical/rerere.txt
index af5f9fc24f9..35d45414339 100644
--- a/Documentation/technical/rerere.txt
+++ b/Documentation/technical/rerere.txt
@@ -14,9 +14,9 @@ conflicts before writing them to the rerere database.
 
 Different conflict styles and branch names are normalized by stripping
 the labels from the conflict markers, and removing the common ancestor
-version from the `diff3` conflict style. Branches that are merged
-in different order are normalized by sorting the conflict hunks.  More
-on each of those steps in the following sections.
+version from the `diff3` or `zdiff3` conflict styles.  Branches that
+are merged in different order are normalized by sorting the conflict
+hunks.  More on each of those steps in the following sections.
 
 Once these two normalization operations are applied, a conflict ID is
 calculated based on the normalized conflict, which is later used by
@@ -42,8 +42,8 @@ get a conflict like the following:
     >>>>>>> AC
 
 Doing the analogous with AC2 (forking a branch ABAC2 off of branch AB
-and then merging branch AC2 into it), using the diff3 conflict style,
-we get a conflict like the following:
+and then merging branch AC2 into it), using the diff3 or zdiff3
+conflict style, we get a conflict like the following:
 
     <<<<<<< HEAD
     B
diff --git a/builtin/checkout.c b/builtin/checkout.c
index 8c69dcdf72a..a0b0fac6a68 100644
--- a/builtin/checkout.c
+++ b/builtin/checkout.c
@@ -1519,7 +1519,7 @@ static struct option *add_common_options(struct checkout_opts *opts,
 		OPT_BOOL(0, "progress", &opts->show_progress, N_("force progress reporting")),
 		OPT_BOOL('m', "merge", &opts->merge, N_("perform a 3-way merge with the new branch")),
 		OPT_STRING(0, "conflict", &opts->conflict_style, N_("style"),
-			   N_("conflict style (merge or diff3)")),
+			   N_("conflict style (merge, diff3, or zdiff3)")),
 		OPT_END()
 	};
 	struct option *newopts = parse_options_concat(prevopts, options);
-- 
gitgitgadget

[PATCH v5 0/2] Implement new zdiff3 conflict style

[Elijah Newren via GitGitGadget]

Implement a zealous diff3, or "zdiff3". This new mode is identical to
ordinary diff3 except that it allows compaction of common lines between the
two sides of history, if those common lines occur at the beginning or end of
a conflict hunk.

Change since v4:

 * None; just resending because v3 wasn't picked up.

Changes since v3:

 * More fixes from Phillip.
 * Marked Phillip as the author of the first commit because he's written
   most the code now; gave myself a co-authored-by trailer on that commit.
 * Removed the RFC label since it's now passing our tests.

Changes since v2:

 * Included more fixes from Phillip, and a new testcase

Changes since v1:

 * Included fixes from Phillip (thanks!)
 * Added some testcases

Elijah Newren (1):
  update documentation for new zdiff3 conflictStyle

Phillip Wood (1):
  xdiff: implement a zealous diff3, or "zdiff3"

 Documentation/config/merge.txt         |  9 ++-
 Documentation/git-checkout.txt         |  3 +-
 Documentation/git-merge-file.txt       |  3 +
 Documentation/git-merge.txt            | 32 +++++++--
 Documentation/git-rebase.txt           |  6 +-
 Documentation/git-restore.txt          |  3 +-
 Documentation/git-switch.txt           |  3 +-
 Documentation/technical/rerere.txt     | 10 +--
 builtin/checkout.c                     |  2 +-
 builtin/merge-file.c                   |  2 +
 contrib/completion/git-completion.bash |  6 +-
 t/t6427-diff3-conflict-markers.sh      | 90 ++++++++++++++++++++++++++
 xdiff-interface.c                      |  2 +
 xdiff/xdiff.h                          |  1 +
 xdiff/xmerge.c                         | 63 ++++++++++++++++--
 15 files changed, 205 insertions(+), 30 deletions(-)


base-commit: 4c719308ce59dc70e606f910f40801f2c6051b24
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1036%2Fnewren%2Fzdiff3-v5
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1036/newren/zdiff3-v5
Pull-Request: https://github.com/git/git/pull/1036

Range-diff vs v4:

 1:  473fae82da1 = 1:  473fae82da1 xdiff: implement a zealous diff3, or "zdiff3"
 2:  69f20a702b4 = 2:  409ae2bbd85 update documentation for new zdiff3 conflictStyle

-- 
gitgitgadget

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

[Phillip Wood via GitGitGadget]

From: Phillip Wood <phillip.wood@dunelm.org.uk>

"zdiff3" is identical to ordinary diff3 except that it allows compaction
of common lines on the two sides of history at the beginning or end of
the conflict hunk.  For example, the following diff3 conflict:

    1
    2
    3
    4
    <<<<<<
    A
    B
    C
    D
    E
    ||||||
    5
    6
    ======
    A
    X
    C
    Y
    E
    >>>>>>
    7
    8
    9

has common lines 'A', 'C', and 'E' on the two sides.  With zdiff3, one
would instead get the following conflict:

    1
    2
    3
    4
    A
    <<<<<<
    B
    C
    D
    ||||||
    5
    6
    ======
    X
    C
    Y
    >>>>>>
    E
    7
    8
    9

Note that the common lines, 'A', and 'E' were moved outside the
conflict.  Unlike with the two-way conflicts from the 'merge'
conflictStyle, the zdiff3 conflict is NOT split into multiple conflict
regions to allow the common 'C' lines to be shown outside a conflict,
because zdiff3 shows the base version too and the base version cannot be
reasonably split.

Note also that the removing of lines common to the two sides might make
the remaining text inside the conflict region match the base text inside
the conflict region (for example, if the diff3 conflict had '5 6 E' on
the right side of the conflict, then the common line 'E' would be moved
outside and both the base and right side's remaining conflict text would
be the lines '5' and '6').  This has the potential to surprise users and
make them think there should not have been a conflict, but there
definitely was a conflict and it should remain.

Based-on-patch-by: Uwe Kleine-König <u.kleine-koenig@pengutronix.de>
Co-authored-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Phillip Wood <phillip.wood123@gmail.com>
Signed-off-by: Elijah Newren <newren@gmail.com>
---
 builtin/merge-file.c                   |  2 +
 contrib/completion/git-completion.bash |  6 +-
 t/t6427-diff3-conflict-markers.sh      | 90 ++++++++++++++++++++++++++
 xdiff-interface.c                      |  2 +
 xdiff/xdiff.h                          |  1 +
 xdiff/xmerge.c                         | 63 ++++++++++++++++--
 6 files changed, 155 insertions(+), 9 deletions(-)

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 8108eda1e86..a7fb14e9a40 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
@@ -2446,7 +2446,7 @@ _git_switch ()
 
 	case "$cur" in
 	--conflict=*)
-		__gitcomp "diff3 merge" "" "${cur##--conflict=}"
+		__gitcomp "diff3 merge zdiff3" "" "${cur##--conflict=}"
 		;;
 	--*)
 		__gitcomp_builtin switch
@@ -2887,7 +2887,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..a9ee4cb207a 100755
--- a/t/t6427-diff3-conflict-markers.sh
+++ b/t/t6427-diff3-conflict-markers.sh
@@ -211,4 +211,94 @@ 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 &&
+		test_write_lines 1 2 3 4 5 6 7 8 9 >evil &&
+
+		git add basic middle-common interesting evil &&
+		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 &&
+		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_success 'check zdiff3 markers' '
+	test_setup_zdiff3 &&
+	(
+		cd zdiff3 &&
+
+		git checkout left^0 &&
+
+		base=$(git rev-parse --short HEAD^1) &&
+		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 \
+				 "||||||| $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 \
+				 "||||||| $base" AA \
+				 ======= EE \
+				 ">>>>>>> right^0" \
+				 4 5 \
+				 "<<<<<<< HEAD" DD \
+				 "||||||| $base" BB \
+				 ======= FF \
+				 ">>>>>>> right^0" \
+				 6 7 8 \
+				 >expect &&
+		test_cmp expect middle-common &&
+
+		test_write_lines 1 2 3 4 A B C \
+				 "<<<<<<< HEAD" D E F \
+				 "||||||| $base" 5 6 \
+				 ======= 5 6 \
+				 ">>>>>>> right^0" \
+				 G H I J 7 8 9 \
+				 >expect &&
+		test_cmp expect interesting &&
+
+		# Not passing this one yet; the common "B C" lines is still
+		# being left in the conflict blocks on the left and right
+		# sides.
+		test_write_lines 1 2 3 4 \
+				 "<<<<<<< HEAD" X A \
+				 "||||||| $base" 5 6 \
+				 ======= Y A B C \
+				 ">>>>>>> right^0" \
+				 B C 7 8 9 \
+				 >expect &&
+		test_cmp expect evil
+	)
+'
+
 test_done
diff --git a/xdiff-interface.c b/xdiff-interface.c
index 75b32aef51d..2e3a5a2943e 100644
--- a/xdiff-interface.c
+++ b/xdiff-interface.c
@@ -313,6 +313,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 b29deca5de8..72e25a9ffa5 100644
--- a/xdiff/xdiff.h
+++ b/xdiff/xdiff.h
@@ -66,6 +66,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..fff0b594f9a 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;
@@ -322,6 +322,40 @@ static int xdl_fill_merge_buffer(xdfenv_t *xe1, const char *name1,
 	return size;
 }
 
+static int recmatch(xrecord_t *rec1, xrecord_t *rec2, unsigned long flags)
+{
+	return xdl_recmatch(rec1->ptr, rec1->size,
+			    rec2->ptr, rec2->size, flags);
+}
+
+/*
+ * Remove any common lines from the beginning and end of the conflicted region.
+ */
+static void xdl_refine_zdiff3_conflicts(xdfenv_t *xe1, xdfenv_t *xe2, xdmerge_t *m,
+		xpparam_t const *xpp)
+{
+	xrecord_t **rec1 = xe1->xdf2.recs, **rec2 = xe2->xdf2.recs;
+	for (; m; m = m->next) {
+		/* let's handle just the conflicts */
+		if (m->mode)
+			continue;
+
+		while(m->chg1 && m->chg2 &&
+		      recmatch(rec1[m->i1], rec2[m->i2], xpp->flags)) {
+			m->chg1--;
+			m->chg2--;
+			m->i1++;
+			m->i2++;
+		}
+		while (m->chg1 && m->chg2 &&
+		       recmatch(rec1[m->i1 + m->chg1 - 1],
+				rec2[m->i2 + m->chg2 - 1], xpp->flags)) {
+			m->chg1--;
+			m->chg2--;
+		}
+	}
+}
+
 /*
  * Sometimes, changes are not quite identical, but differ in only a few
  * lines. Try hard to show only these few lines as conflicting.
@@ -482,7 +516,22 @@ static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1,
 	int style = xmp->style;
 	int favor = xmp->favor;
 
-	if (style == XDL_MERGE_DIFF3) {
+	/*
+	 * 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.
+	 */
+	if (style == XDL_MERGE_DIFF3 || style == XDL_MERGE_ZEALOUS_DIFF3) {
 		/*
 		 * "diff3 -m" output does not make sense for anything
 		 * more aggressive than XDL_MERGE_EAGER.
@@ -603,10 +652,12 @@ static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1,
 	if (!changes)
 		changes = c;
 	/* refine conflicts */
-	if (XDL_MERGE_ZEALOUS <= level &&
-	    (xdl_refine_conflicts(xe1, xe2, changes, xpp) < 0 ||
-	     xdl_simplify_non_conflicts(xe1, changes,
-					XDL_MERGE_ZEALOUS < level) < 0)) {
+	if (style == XDL_MERGE_ZEALOUS_DIFF3) {
+		xdl_refine_zdiff3_conflicts(xe1, xe2, changes, xpp);
+	} else if (XDL_MERGE_ZEALOUS <= level &&
+		   (xdl_refine_conflicts(xe1, xe2, changes, xpp) < 0 ||
+		    xdl_simplify_non_conflicts(xe1, changes,
+					       XDL_MERGE_ZEALOUS < level) < 0)) {
 		xdl_cleanup_merge(changes);
 		return -1;
 	}
-- 
gitgitgadget

[PATCH v5 2/2] update documentation for new zdiff3 conflictStyle

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 Documentation/config/merge.txt     |  9 ++++++++-
 Documentation/git-checkout.txt     |  3 +--
 Documentation/git-merge-file.txt   |  3 +++
 Documentation/git-merge.txt        | 32 +++++++++++++++++++++++++-----
 Documentation/git-rebase.txt       |  6 +++---
 Documentation/git-restore.txt      |  3 +--
 Documentation/git-switch.txt       |  3 +--
 Documentation/technical/rerere.txt | 10 +++++-----
 builtin/checkout.c                 |  2 +-
 9 files changed, 50 insertions(+), 21 deletions(-)

diff --git a/Documentation/config/merge.txt b/Documentation/config/merge.txt
index e27cc639447..99e83dd36e5 100644
--- a/Documentation/config/merge.txt
+++ b/Documentation/config/merge.txt
@@ -4,7 +4,14 @@ merge.conflictStyle::
 	shows a `<<<<<<<` conflict marker, changes made by one side,
 	a `=======` marker, changes made by the other side, and then
 	a `>>>>>>>` marker.  An alternate style, "diff3", adds a `|||||||`
-	marker and the original text before the `=======` marker.
+	marker and the original text before the `=======` marker.  The
+	"merge" style tends to produce smaller conflict regions than diff3,
+	both because of the exclusion of the original text, and because
+	when a subset of lines match on the two sides they are just pulled
+	out of the conflict region.  Another alternate style, "zdiff3", is
+	similar to diff3 but removes matching lines on the two sides from
+	the conflict region when those matching lines appear near either
+	the beginning or end of a conflict region.
 
 merge.defaultToUpstream::
 	If merge is called without any commit argument, merge the upstream
diff --git a/Documentation/git-checkout.txt b/Documentation/git-checkout.txt
index b1a6fe44997..85c3d3513f7 100644
--- a/Documentation/git-checkout.txt
+++ b/Documentation/git-checkout.txt
@@ -265,8 +265,7 @@ When switching branches with `--merge`, staged changes may be lost.
 	The same as `--merge` option above, but changes the way the
 	conflicting hunks are presented, overriding the
 	`merge.conflictStyle` configuration variable.  Possible values are
-	"merge" (default) and "diff3" (in addition to what is shown by
-	"merge" style, shows the original contents).
+	"merge" (default), "diff3", and "zdiff3".
 
 -p::
 --patch::
diff --git a/Documentation/git-merge-file.txt b/Documentation/git-merge-file.txt
index f8560326132..7e9093fab60 100644
--- a/Documentation/git-merge-file.txt
+++ b/Documentation/git-merge-file.txt
@@ -70,6 +70,9 @@ OPTIONS
 --diff3::
 	Show conflicts in "diff3" style.
 
+--zdiff3::
+	Show conflicts in "zdiff3" style.
+
 --ours::
 --theirs::
 --union::
diff --git a/Documentation/git-merge.txt b/Documentation/git-merge.txt
index e4f3352eb58..e8cecf5a51d 100644
--- a/Documentation/git-merge.txt
+++ b/Documentation/git-merge.txt
@@ -240,7 +240,8 @@ from the RCS suite to present such a conflicted hunk, like this:
 
 ------------
 Here are lines that are either unchanged from the common
-ancestor, or cleanly resolved because only one side changed.
+ancestor, or cleanly resolved because only one side changed,
+or cleanly resolved because both sides changed the same way.
 <<<<<<< yours:sample.txt
 Conflict resolution is hard;
 let's go shopping.
@@ -261,16 +262,37 @@ side wants to say it is hard and you'd prefer to go shopping, while the
 other side wants to claim it is easy.
 
 An alternative style can be used by setting the "merge.conflictStyle"
-configuration variable to "diff3".  In "diff3" style, the above conflict
-may look like this:
+configuration variable to either "diff3" or "zdiff3".  In "diff3"
+style, the above conflict may look like this:
 
 ------------
 Here are lines that are either unchanged from the common
-ancestor, or cleanly resolved because only one side changed.
+ancestor, or cleanly resolved because only one side changed,
 <<<<<<< yours:sample.txt
+or cleanly resolved because both sides changed the same way.
 Conflict resolution is hard;
 let's go shopping.
-|||||||
+||||||| base:sample.txt
+or cleanly resolved because both sides changed identically.
+Conflict resolution is hard.
+=======
+or cleanly resolved because both sides changed the same way.
+Git makes conflict resolution easy.
+>>>>>>> theirs:sample.txt
+And here is another line that is cleanly resolved or unmodified.
+------------
+
+while in "zdiff3" style, it may look like this:
+
+------------
+Here are lines that are either unchanged from the common
+ancestor, or cleanly resolved because only one side changed,
+or cleanly resolved because both sides changed the same way.
+<<<<<<< yours:sample.txt
+Conflict resolution is hard;
+let's go shopping.
+||||||| base:sample.txt
+or cleanly resolved because both sides changed identically.
 Conflict resolution is hard.
 =======
 Git makes conflict resolution easy.
diff --git a/Documentation/git-rebase.txt b/Documentation/git-rebase.txt
index 506345cb0ed..dd9830dc5f8 100644
--- a/Documentation/git-rebase.txt
+++ b/Documentation/git-rebase.txt
@@ -741,9 +741,9 @@ information about the rebased commits and their parents (and instead
 generates new fake commits based off limited information in the
 generated patches), those commits cannot be identified; instead it has
 to fall back to a commit summary.  Also, when merge.conflictStyle is
-set to diff3, the apply backend will use "constructed merge base" to
-label the content from the merge base, and thus provide no information
-about the merge base commit whatsoever.
+set to diff3 or zdiff3, the apply backend will use "constructed merge
+base" to label the content from the merge base, and thus provide no
+information about the merge base commit whatsoever.
 
 The merge backend works with the full commits on both sides of history
 and thus has no such limitations.
diff --git a/Documentation/git-restore.txt b/Documentation/git-restore.txt
index 55bde91ef9e..5964810caa4 100644
--- a/Documentation/git-restore.txt
+++ b/Documentation/git-restore.txt
@@ -92,8 +92,7 @@ in linkgit:git-checkout[1] for details.
 	The same as `--merge` option above, but changes the way the
 	conflicting hunks are presented, overriding the
 	`merge.conflictStyle` configuration variable.  Possible values
-	are "merge" (default) and "diff3" (in addition to what is
-	shown by "merge" style, shows the original contents).
+	are "merge" (default), "diff3", and "zdiff3".
 
 --ignore-unmerged::
 	When restoring files on the working tree from the index, do
diff --git a/Documentation/git-switch.txt b/Documentation/git-switch.txt
index 5c438cd5058..5c90f76fbe3 100644
--- a/Documentation/git-switch.txt
+++ b/Documentation/git-switch.txt
@@ -137,8 +137,7 @@ should result in deletion of the path).
 	The same as `--merge` option above, but changes the way the
 	conflicting hunks are presented, overriding the
 	`merge.conflictStyle` configuration variable.  Possible values are
-	"merge" (default) and "diff3" (in addition to what is shown by
-	"merge" style, shows the original contents).
+	"merge" (default), "diff3", and "zdiff3".
 
 -q::
 --quiet::
diff --git a/Documentation/technical/rerere.txt b/Documentation/technical/rerere.txt
index af5f9fc24f9..35d45414339 100644
--- a/Documentation/technical/rerere.txt
+++ b/Documentation/technical/rerere.txt
@@ -14,9 +14,9 @@ conflicts before writing them to the rerere database.
 
 Different conflict styles and branch names are normalized by stripping
 the labels from the conflict markers, and removing the common ancestor
-version from the `diff3` conflict style. Branches that are merged
-in different order are normalized by sorting the conflict hunks.  More
-on each of those steps in the following sections.
+version from the `diff3` or `zdiff3` conflict styles.  Branches that
+are merged in different order are normalized by sorting the conflict
+hunks.  More on each of those steps in the following sections.
 
 Once these two normalization operations are applied, a conflict ID is
 calculated based on the normalized conflict, which is later used by
@@ -42,8 +42,8 @@ get a conflict like the following:
     >>>>>>> AC
 
 Doing the analogous with AC2 (forking a branch ABAC2 off of branch AB
-and then merging branch AC2 into it), using the diff3 conflict style,
-we get a conflict like the following:
+and then merging branch AC2 into it), using the diff3 or zdiff3
+conflict style, we get a conflict like the following:
 
     <<<<<<< HEAD
     B
diff --git a/builtin/checkout.c b/builtin/checkout.c
index 8c69dcdf72a..a0b0fac6a68 100644
--- a/builtin/checkout.c
+++ b/builtin/checkout.c
@@ -1519,7 +1519,7 @@ static struct option *add_common_options(struct checkout_opts *opts,
 		OPT_BOOL(0, "progress", &opts->show_progress, N_("force progress reporting")),
 		OPT_BOOL('m', "merge", &opts->merge, N_("perform a 3-way merge with the new branch")),
 		OPT_STRING(0, "conflict", &opts->conflict_style, N_("style"),
-			   N_("conflict style (merge or diff3)")),
+			   N_("conflict style (merge, diff3, or zdiff3)")),
 		OPT_END()
 	};
 	struct option *newopts = parse_options_concat(prevopts, options);
-- 
gitgitgadget

Re: [PATCH v5 2/2] update documentation for new zdiff3 conflictStyle

[Bagas Sanjaya]

On 01/12/21 07.05, Elijah Newren via GitGitGadget wrote:
>   	The same as `--merge` option above, but changes the way the
>   	conflicting hunks are presented, overriding the
>   	`merge.conflictStyle` configuration variable.  Possible values are
> -	"merge" (default) and "diff3" (in addition to what is shown by
> -	"merge" style, shows the original contents).
> +	"merge" (default), "diff3", and "zdiff3".
>   

Missing '... (the latter both also shows the original contents)'.

-- 
An old man doll... just what I always wanted! - Clara

Re: [PATCH v5 2/2] update documentation for new zdiff3 conflictStyle

[Eric Sunshine]

On Thu, Dec 2, 2021 at 3:42 AM Bagas Sanjaya <bagasdotme@gmail.com> wrote:
> On 01/12/21 07.05, Elijah Newren via GitGitGadget wrote:
> >       The same as `--merge` option above, but changes the way the
> >       conflicting hunks are presented, overriding the
> >       `merge.conflictStyle` configuration variable.  Possible values are
> > -     "merge" (default) and "diff3" (in addition to what is shown by
> > -     "merge" style, shows the original contents).
> > +     "merge" (default), "diff3", and "zdiff3".
>
> Missing '... (the latter both also shows the original contents)'.

The omission is clearly intentional. The additional text added to the
hunk just above this one (which you snipped), does a better job of
explaining the differences between the styles than this little blurb
did. Moreover, there is insufficient context at this location in the
documentation for a reader to fully understand the difference between
"merge" and "diff3", and the problem of lack of context becomes worse
with the addition of "zdiff3". So, Elijah's choice to drop this blurb
-- leaving just an enumeration of choices -- and elsewhere provide
comprehensive detail about the differences is quite sensible. The
revised text is improved by the loss of the blurb.