RFC: implement new zdiff3 conflict style

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

From: Elijah Newren <[email protected]>

"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.

---
 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(-)

index 06a2f90c4875..e695867ee548 100644
@@ -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"),

index b50c5d0ea386..859455929814 100644
@@ -1566,7 +1566,7 @@ _git_checkout ()
 
 	case "$cur" in
 	--conflict=*)
-		__gitcomp "diff3 merge" "" "${cur##--conflict=}"
+		__gitcomp "diff3 merge zdiff3" "" "${cur##--conflict=}"
 		;;
 	--*)
 		__gitcomp_builtin checkout

index 609615db2cd6..9977813a9d37 100644
@@ -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;
 		/*

index 7a046051468f..8629ae287c79 100644
@@ -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;

gitgitgadget

From: Elijah Newren <[email protected]>

---
 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(-)

index cb2ed589075b..7ab289f35c7f 100644
@@ -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

index b1a6fe449973..85c3d3513f74 100644
@@ -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::

index f85603261325..7e9093fab60d 100644
@@ -70,6 +70,9 @@ OPTIONS
 --diff3::
 	Show conflicts in "diff3" style.
 
+--zdiff3::
+	Show conflicts in "zdiff3" style.
+
 --ours::
 --theirs::
 --union::

index 3819fadac1f1..259e1ac2cf0c 100644
@@ -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.

index 55af6fd24e27..a61742c8f98f 100644
@@ -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.

index 55bde91ef9e5..5964810caa41 100644
@@ -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

index 5c438cd50587..5c90f76fbe35 100644
@@ -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::

index af5f9fc24f93..35d454143399 100644
@@ -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

index f4cd7747d35d..45606936c328 100644
@@ -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);

index 859455929814..8489ca394970 100644
@@ -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

"Elijah Newren via GitGitGadget" <[email protected]> writes:

[An example to reduce

    1234<ABCDE|56=AXCYE>789
to
    1234A<BCD|56=XCY>E789

elided]

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.

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

C
D
E
F
<<<<<<< l
I
=======
i

This is simple, and useful.

diff3 will output this:

A
<<<<<<< l

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

b
C
D
E
F
i

Not very friendly.

Your zdiff3:

A

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

Just marginally better.

Uwe's zdiff3:

A

<<<<<<< l
B
||||||| b
=======
b

C
D
E
F
<<<<<<< l
I
||||||| b
=======
i

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

Felipe Contreras

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

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?

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

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

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.)

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.

Am 15.06.21 um 07:16 schrieb Elijah Newren via GitGitGadget:

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/[email protected]/

-- Hannes

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/[email protected]/),
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);

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.

Am 15.06.21 um 23:45 schrieb Elijah Newren:

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

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.

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

index b1dc9df7ea..5f76957169 100644
@@ -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")) {

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

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

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

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.

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

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).

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

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 <[email protected]>
     +    Based-on-patch-by: Uwe Kleine-König <[email protected]>
     +    Helped-by: Phillip Wood <[email protected]>
          Signed-off-by: Elijah Newren <[email protected]>
      
       ## 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

From: Elijah Newren <[email protected]>

"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.

---
 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(-)

index 06a2f90c487..e695867ee54 100644
@@ -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"),

index b50c5d0ea38..8489ca39497 100644
@@ -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=}"

index 609615db2cd..9977813a9d3 100644
@@ -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;
 		/*

index 7a046051468..8629ae287c7 100644
@@ -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;

gitgitgadget

From: Elijah Newren <[email protected]>

---
 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(-)

index cb2ed589075..52d79117ef8 100644
@@ -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

index b1a6fe44997..85c3d3513f7 100644
@@ -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::

index f8560326132..7e9093fab60 100644
@@ -70,6 +70,9 @@ OPTIONS
 --diff3::
 	Show conflicts in "diff3" style.
 
+--zdiff3::
+	Show conflicts in "zdiff3" style.
+
 --ours::
 --theirs::
 --union::

index 3819fadac1f..259e1ac2cf0 100644
@@ -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.

index 55af6fd24e2..a61742c8f98 100644
@@ -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.

index 55bde91ef9e..5964810caa4 100644
@@ -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

index 5c438cd5058..5c90f76fbe3 100644
@@ -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::

index af5f9fc24f9..35d45414339 100644
@@ -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

index f4cd7747d35..45606936c32 100644
@@ -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

Hi Elijah

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

Here is an evil test case that shows this problem (diff on top of your patch)

index de9c6190b9..836843c6b0 100755
@@ -219,8 +219,9 @@ test_setup_zdiff3 () {
                test_write_lines 1 2 3 4 5 6 7 8 9 >basic &&
                test_write_lines 1 2 3 AA 4 5 BB 6 7 8 >middle-common &&
                test_write_lines 1 2 3 4 5 6 7 8 9 >interesting &&
+               test_write_lines 1 2 3 4 5 6 7 8 9 >evil &&
 
-               git add basic middle-common &&
+               git add basic middle-common interesting evil &&
                git commit -m base &&
 
                git branch left &&

@@ -230,19 +231,21 @@ test_setup_zdiff3 () {
                test_write_lines 1 2 3 4 A B C D E 7 8 9 >basic &&
                test_write_lines 1 2 3 CC 4 5 DD 6 7 8 >middle-common &&
                test_write_lines 1 2 3 4 A B C D E F G H I J 7 8 9 >interesting &&
+               test_write_lines 1 2 3 4 X A B C 7 8 9 >evil &&
                git add -u &&
                git commit -m letters &&
 
                git checkout right &&
                test_write_lines 1 2 3 4 A X C Y E 7 8 9 >basic &&
                test_write_lines 1 2 3 EE 4 5 FF 6 7 8 >middle-common &&
                test_write_lines 1 2 3 4 A B C 5 6 G H I J 7 8 9 >interesting &&
+               test_write_lines 1 2 3 4 Y A B C B C 7 8 9 >evil &&
                git add -u &&
                git commit -m permuted
        )
 }
 
-test_expect_failure 'check zdiff3 markers' '
+test_expect_success 'check zdiff3 markers' '
        test_setup_zdiff3 &&
        (
                cd zdiff3 &&

@@ -251,6 +254,14 @@ test_expect_failure 'check zdiff3 markers' '
 
                test_must_fail git -c merge.conflictstyle=zdiff3 merge -s recursive right^0 &&
 
+               test_write_lines \
+                       1 2 3 4 \
+                       "<<<<<<< HEAD" X A \
+                       "||||||| $(git rev-parse --short HEAD^1)" 5 6 ======= \
+                       Y A B C ">>>>>>> right^0" \
+                       B C 7 8 9 >expect &&
+               test_cmp expect evil &&
+
                test_write_lines 1 2 3 4 A "<<<<<<< HEAD" B C D "||||||| $(git rev-parse --short HEAD^1)" 5 6 ======= X C Y ">>>>>>> right^0" E 7 8 9 >expect &&
                test_cmp expect basic &&
 

Hi Phillip,

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

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

Yeah, that looks a lot better.

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.

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?

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 <[email protected]>
     -    Helped-by: Phillip Wood <[email protected]>
     +    Co-authored-by: Phillip Wood <[email protected]>
          Signed-off-by: Elijah Newren <[email protected]>
      
       ## 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

From: Elijah Newren <[email protected]>

"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.

---
 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(-)

index 06a2f90c487..e695867ee54 100644
@@ -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"),

index 8108eda1e86..a7fb14e9a40 100644
@@ -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=}"

index 75b32aef51d..2e3a5a2943e 100644
@@ -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;
 		/*

index b29deca5de8..72e25a9ffa5 100644
@@ -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;

gitgitgadget

From: Elijah Newren <[email protected]>

---
 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(-)

index e27cc639447..99e83dd36e5 100644
@@ -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

index b1a6fe44997..85c3d3513f7 100644
@@ -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::

index f8560326132..7e9093fab60 100644
@@ -70,6 +70,9 @@ OPTIONS
 --diff3::
 	Show conflicts in "diff3" style.
 
+--zdiff3::
+	Show conflicts in "zdiff3" style.
+
 --ours::
 --theirs::
 --union::

index e4f3352eb58..e8cecf5a51d 100644
@@ -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.

index 506345cb0ed..dd9830dc5f8 100644
@@ -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.

index 55bde91ef9e..5964810caa4 100644
@@ -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

index 5c438cd5058..5c90f76fbe3 100644
@@ -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::

index af5f9fc24f9..35d45414339 100644
@@ -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

index 8c69dcdf72a..a0b0fac6a68 100644
@@ -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

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

Hi Elijah

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/[email protected]/

From: Phillip Wood <[email protected]>

"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.

---
 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(-)

index 06a2f90c487..e695867ee54 100644
@@ -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"),

index 8108eda1e86..a7fb14e9a40 100644
@@ -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=}"

index 75b32aef51d..2e3a5a2943e 100644
@@ -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;
 		/*

index b29deca5de8..72e25a9ffa5 100644
@@ -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;

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 <[email protected]>
     +Author: Phillip Wood <[email protected]>
      
       ## 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 <[email protected]>
     -    Co-authored-by: Phillip Wood <[email protected]>
     +    Co-authored-by: Elijah Newren <[email protected]>
     +    Signed-off-by: Phillip Wood <[email protected]>
          Signed-off-by: Elijah Newren <[email protected]>
      
       ## 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

From: Elijah Newren <[email protected]>

---
 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(-)

index e27cc639447..99e83dd36e5 100644
@@ -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

index b1a6fe44997..85c3d3513f7 100644
@@ -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::

index f8560326132..7e9093fab60 100644
@@ -70,6 +70,9 @@ OPTIONS
 --diff3::
 	Show conflicts in "diff3" style.
 
+--zdiff3::
+	Show conflicts in "zdiff3" style.
+
 --ours::
 --theirs::
 --union::

index e4f3352eb58..e8cecf5a51d 100644
@@ -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.

index 506345cb0ed..dd9830dc5f8 100644
@@ -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.

index 55bde91ef9e..5964810caa4 100644
@@ -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

index 5c438cd5058..5c90f76fbe3 100644
@@ -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::

index af5f9fc24f9..35d45414339 100644
@@ -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

index 8c69dcdf72a..a0b0fac6a68 100644
@@ -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

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

From: Phillip Wood <[email protected]>

"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.

---
 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(-)

index 06a2f90c487..e695867ee54 100644
@@ -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"),

index 8108eda1e86..a7fb14e9a40 100644
@@ -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=}"

index 75b32aef51d..2e3a5a2943e 100644
@@ -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;
 		/*

index b29deca5de8..72e25a9ffa5 100644
@@ -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;

gitgitgadget

From: Elijah Newren <[email protected]>

---
 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(-)

index e27cc639447..99e83dd36e5 100644
@@ -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

index b1a6fe44997..85c3d3513f7 100644
@@ -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::

index f8560326132..7e9093fab60 100644
@@ -70,6 +70,9 @@ OPTIONS
 --diff3::
 	Show conflicts in "diff3" style.
 
+--zdiff3::
+	Show conflicts in "zdiff3" style.
+
 --ours::
 --theirs::
 --union::

index e4f3352eb58..e8cecf5a51d 100644
@@ -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.

index 506345cb0ed..dd9830dc5f8 100644
@@ -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.

index 55bde91ef9e..5964810caa4 100644
@@ -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

index 5c438cd5058..5c90f76fbe3 100644
@@ -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::

index af5f9fc24f9..35d45414339 100644
@@ -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

index 8c69dcdf72a..a0b0fac6a68 100644
@@ -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

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.