merge-file: add --diff-algorithm option

Hi all,

Here a few more thoughts about this patch, to explain what brought me to needing that. If this need is misguided, perhaps you could redirect me to a better solution.

I am writing a custom merge driver for Java files. This merge driver internally calls git-merge-file and then solves the merge conflicts which only consist of import statements (there might be cases where it gets it wrong, but I can then use other tools to cleanup those import statements). When testing this, I noticed that the merge driver performed more poorly on other sorts of conflicts, compared to the standard "ort" merge strategy. This is because "ort" uses the "histogram" diff algorithm, which gives better results than the "myers" diff algorithm that merge-file uses.

Intuitively, if "histogram" is the default diff algorithm used by "git merge", then it would also make sense to have the same default for "git merge-file", but I assume that changing this default could be considered a bad breaking change. So I thought that making this diff algorithm configurable would be an acceptable move, hence my patch.

Of course, the diffing could be configured in other ways, for instance with its handling of whitespace or EOL (similarly to what the "git-diff" command offers). I think those options would definitely be worth exposing in merge-file as well. If you think this makes sense, then I would be happy to work on a new version of this patch which would attempt to include all the relevant options. I could also try to add the corresponding tests.

But perhaps my need is misguided? Could it be that I should not be writing a custom merge driver, but instead use another extension point to only process the conflicting hunks after execution of the existing merge driver? I couldn't find such an extension point, but it can well be that I missed it.

Thank you,

Antonin

I cannot comment on this particular use but I think in general calling "git merge-file" from a custom merge driver is perfectly sensible. Have you tested your driver with this patch to see if you get better results with the histogram diff algorithm?

I can see there's an argument for changing the default algorithm of "git merge-file" to match what "ort" uses. I know Elijah found the histogram algorithm gave better results in his testing when he was developing "ort". While it would be a breaking change if on the average the new default gives better conflicts it might be worth it. This patch would mean that someone wanting to use the "myers" algorithm could still do so.

It would be nice to see some tests for this patch, ideally using a test case that gives different conflicts for "myers" and "histogram". We could add the other options later if there is a demand.

Perhaps we could list the available algorithms here so the user does not have to go searching for them in another man page.

I can see there's an argument for changing the default algorithm of "git merge-file" to match what "ort" uses. I know Elijah found the histogram algorithm gave better results in his testing when he was developing "ort". While it would be a breaking change if on the average the new default gives better conflicts it might be worth it. This patch would mean that someone wanting to use the "myers" algorithm could still do so.

From: Antonin Delpeuch <[email protected]>

This makes it possible to use other diff algorithms than the 'myers' default algorithm, when using the 'git merge-file' command.

Signed-off-by Antonin Delpeuch <[email protected]>

---

     merge-file: add --diff-algorithm option

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1606%2Fwetneb%2Fmerge_file_configurable_diff_algorithm-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1606/wetneb/merge_file_configurable_diff_algorithm-v1
Pull-Request: https://github.com/git/git/pull/1606

  Documentation/git-merge-file.txt |  5 +++++
  builtin/merge-file.c             | 28 ++++++++++++++++++++++++++++
  2 files changed, 33 insertions(+)

Documentation/git-merge-file.txt +0 -0

index 6a081eacb72..917535217c1 100644

Documentation/git-merge-file.txt +0 -0

  EXAMPLES
  --------

builtin/merge-file.c +25 -0

index 832c93d8d54..1f987334a31 100644
@@ -1,5 +1,6 @@
  #include "builtin.h"
  #include "abspath.h"
+#include "diff.h"
  #include "hex.h"
  #include "object-name.h"
  #include "object-store.h"

@@ -28,6 +29,30 @@ static int label_cb(const struct option *opt, const char *arg, int unset)
  	return 0;
  }
 
+static int set_diff_algorithm(xpparam_t *xpp,
+			      const char *alg)
+{
+	long diff_algorithm = parse_algorithm_value(alg);
+	if (diff_algorithm < 0)
+		return -1;
+	xpp->flags = (xpp->flags & ~XDF_DIFF_ALGORITHM_MASK) | diff_algorithm;
+	return 0;
+}
+
+static int diff_algorithm_cb(const struct option *opt,
+				const char *arg, int unset)
+{
+	xpparam_t *xpp = opt->value;
+
+	BUG_ON_OPT_NEG(unset);
+
+	if (set_diff_algorithm(xpp, arg))
+		return error(_("option diff-algorithm accepts \"myers\", "
+			       "\"minimal\", \"patience\" and \"histogram\""));
+
+	return 0;
+}
+
  int cmd_merge_file(int argc, const char **argv, const char *prefix)
  {
  	const char *names[3] = { 0 };

base-commit: 98009afd24e2304bf923a64750340423473809ff

From: Antonin Delpeuch <[email protected]>

This makes it possible to use other diff algorithms than the 'myers' default algorithm, when using the 'git merge-file' command. This helps avoid spurious conflicts by selecting a more recent algorithm such as 'histogram', for instance when using 'git merge-file' as part of a custom merge driver.

Signed-off-by Antonin Delpeuch <[email protected]>

Reviewed-by Phillip Wood <[email protected]>

---
merge-file: add --diff-algorithm option

Changes since v1:

* improve commit message to mention the use case of custom merge drivers
* improve documentation to show available options and recommend switching to "histogram"
* add tests

I have left out:

* switching the default to "histogram", because it should only be done in a subsequent release
* adding a configuration variable to control this option, because I was not sure how to call it. Perhaps "merge-file.diffAlgorithm"?

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1606%2Fwetneb%2Fmerge_file_configurable_diff_algorithm-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1606/wetneb/merge_file_configurable_diff_algorithm-v2
Pull-Request: https://github.com/git/git/pull/1606

Range-diff vs v1:

  1:  4aa453e30be ! 1:  842b5abf33c merge-file: add --diff-algorithm option
      @@ Commit message
           merge-file: add --diff-algorithm option

           This makes it possible to use other diff algorithms than the 'myers'
      -    default algorithm, when using the 'git merge-file' command.
      +    default algorithm, when using the 'git merge-file' command. This helps
      +    avoid spurious conflicts by selecting a more recent algorithm such as
      +    'histogram', for instance when using 'git merge-file' as part of a custom
      +    merge driver.
       
           Signed-off-by: Antonin Delpeuch <[email protected]>
      +    Reviewed-by: Phillip Wood <[email protected]>
       
        ## Documentation/git-merge-file.txt ##
       @@ Documentation/git-merge-file.txt: object store and the object ID of its blob is written to standard output.
        	Instead of leaving conflicts in the file, resolve conflicts
        	favouring our (or their or both) side of the lines.
        
      -+--diff-algorithm <algorithm>::
      -+	Use a different diff algorithm while merging, which can help
      ++--diff-algorithm={patience|minimal|histogram|myers}::
      ++	Use a different diff algorithm while merging. The current default is "myers",
      ++	but selecting more recent algorithm such as "histogram" can help
       +	avoid mismerges that occur due to unimportant matching lines
      -+	(such as braces from distinct functions).  See also
      ++	(such as braces from distinct functions). See also
       +	linkgit:git-diff[1] `--diff-algorithm`.
        
        EXAMPLES
      @@ builtin/merge-file.c: int cmd_merge_file(int argc, const char **argv, const char
        		OPT_INTEGER(0, "marker-size", &xmp.marker_size,
        			    N_("for conflicts, use this marker size")),
        		OPT__QUIET(&quiet, N_("do not warn about conflicts")),
      +
      + ## t/t6403-merge-file.sh ##
      +@@ t/t6403-merge-file.sh: test_expect_success 'setup' '
      + 	deduxit me super semitas jusitiae,
      + 	EOF
      +
      +-	printf "propter nomen suum." >>new4.txt
      ++	printf "propter nomen suum." >>new4.txt &&
      ++
      ++	cat >base.c <<-\EOF &&
      ++	int f(int x, int y)
      ++	{
      ++		if (x == 0)
      ++		{
      ++			return y;
      ++		}
      ++		return x;
      ++	}
      ++
      ++	int g(size_t u)
      ++	{
      ++		while (u < 30)
      ++		{
      ++			u++;
      ++		}
      ++		return u;
      ++	}
      ++	EOF
      ++
      ++	cat >ours.c <<-\EOF &&
      ++	int g(size_t u)
      ++	{
      ++		while (u < 30)
      ++		{
      ++			u++;
      ++		}
      ++		return u;
      ++	}
      ++
      ++	int h(int x, int y, int z)
      ++	{
      ++		if (z == 0)
      ++		{
      ++			return x;
      ++		}
      ++		return y;
      ++	}
      ++	EOF
      ++
      ++	cat >theirs.c <<-\EOF
      ++	int f(int x, int y)
      ++	{
      ++		if (x == 0)
      ++		{
      ++			return y;
      ++		}
      ++		return x;
      ++	}
      ++
      ++	int g(size_t u)
      ++	{
      ++		while (u > 34)
      ++		{
      ++			u--;
      ++		}
      ++		return u;
      ++	}
      ++	EOF
      + '
      +
      + test_expect_success 'merge with no changes' '
      +@@ t/t6403-merge-file.sh: test_expect_success '--object-id fails without repository' '
      + 	grep "not a git repository" err
      + '
      +
      ++test_expect_success 'merging C files with "myers" diff algorithm creates some spurious conflicts' '
      ++	cat >expect.c <<-\EOF &&
      ++	int g(size_t u)
      ++	{
      ++		while (u < 30)
      ++		{
      ++			u++;
      ++		}
      ++		return u;
      ++	}
      ++
      ++	int h(int x, int y, int z)
      ++	{
      ++	<<<<<<< ours.c
      ++		if (z == 0)
      ++	||||||| base.c
      ++		while (u < 30)
      ++	=======
      ++		while (u > 34)
      ++	>>>>>>> theirs.c
      ++		{
      ++	<<<<<<< ours.c
      ++			return x;
      ++	||||||| base.c
      ++			u++;
      ++	=======
      ++			u--;
      ++	>>>>>>> theirs.c
      ++		}
      ++		return y;
      ++	}
      ++	EOF
      ++
      ++	test_must_fail git merge-file -p --diff3 --diff-algorithm myers ours.c base.c theirs.c >myers_output.c &&
      ++	test_cmp expect.c myers_output.c
      ++'
      ++
      ++test_expect_success 'merging C files with "histogram" diff algorithm avoids some spurious conflicts' '
      ++	cat >expect.c <<-\EOF &&
      ++	int g(size_t u)
      ++	{
      ++		while (u > 34)
      ++		{
      ++			u--;
      ++		}
      ++		return u;
      ++	}
      ++
      ++	int h(int x, int y, int z)
      ++	{
      ++		if (z == 0)
      ++		{
      ++			return x;
      ++		}
      ++		return y;
      ++	}
      ++	EOF
      ++
      ++	git merge-file -p --diff3 --diff-algorithm histogram ours.c base.c theirs.c >histogram_output.c &&
      ++	test_cmp expect.c histogram_output.c
      ++'
      ++
      + test_done

  Documentation/git-merge-file.txt |   6 ++
  builtin/merge-file.c             |  28 +++++++
  t/t6403-merge-file.sh            | 124 ++++++++++++++++++++++++++++++-
  3 files changed, 157 insertions(+), 1 deletion(-)

Documentation/git-merge-file.txt +6 -0

index 6a081eacb72..71915a00fa4 100644
@@ -92,6 +92,12 @@ object store and the object ID of its blob is written to standard output.
  	Instead of leaving conflicts in the file, resolve conflicts
  	favouring our (or their or both) side of the lines.
 
+--diff-algorithm={patience|minimal|histogram|myers}::
+	Use a different diff algorithm while merging. The current default is "myers",
+	but selecting more recent algorithm such as "histogram" can help
+	avoid mismerges that occur due to unimportant matching lines
+	(such as braces from distinct functions). See also
+	linkgit:git-diff[1] `--diff-algorithm`.
 
  EXAMPLES
  --------

builtin/merge-file.c +28 -0

index 832c93d8d54..1f987334a31 100644
@@ -1,5 +1,6 @@
  #include "builtin.h"
  #include "abspath.h"
+#include "diff.h"
  #include "hex.h"
  #include "object-name.h"
  #include "object-store.h"

@@ -28,6 +29,30 @@ static int label_cb(const struct option *opt, const char *arg, int unset)
  	return 0;
  }
 
+static int set_diff_algorithm(xpparam_t *xpp,
+			      const char *alg)
+{
+	long diff_algorithm = parse_algorithm_value(alg);
+	if (diff_algorithm < 0)
+		return -1;
+	xpp->flags = (xpp->flags & ~XDF_DIFF_ALGORITHM_MASK) | diff_algorithm;
+	return 0;
+}
+
+static int diff_algorithm_cb(const struct option *opt,
+				const char *arg, int unset)
+{
+	xpparam_t *xpp = opt->value;
+
+	BUG_ON_OPT_NEG(unset);
+
+	if (set_diff_algorithm(xpp, arg))
+		return error(_("option diff-algorithm accepts \"myers\", "
+			       "\"minimal\", \"patience\" and \"histogram\""));
+
+	return 0;
+}
+
  int cmd_merge_file(int argc, const char **argv, const char *prefix)
  {
  	const char *names[3] = { 0 };

@@ -48,6 +73,9 @@ int cmd_merge_file(int argc, const char **argv, const char *prefix)
  			    XDL_MERGE_FAVOR_THEIRS),
  		OPT_SET_INT(0, "union", &xmp.favor, N_("for conflicts, use a union version"),
  			    XDL_MERGE_FAVOR_UNION),
+		OPT_CALLBACK_F(0, "diff-algorithm", &xmp.xpp, N_("<algorithm>"),
+			     N_("choose a diff algorithm"),
+			     PARSE_OPT_NONEG, diff_algorithm_cb),
  		OPT_INTEGER(0, "marker-size", &xmp.marker_size,
  			    N_("for conflicts, use this marker size")),
  		OPT__QUIET(&quiet, N_("do not warn about conflicts")),

t/t6403-merge-file.sh +123 -1

index 2c92209ecab..fb872c5a113 100755
@@ -56,7 +56,67 @@ test_expect_success 'setup' '
  	deduxit me super semitas jusitiae,
  	EOF
 
-	printf "propter nomen suum." >>new4.txt
+	printf "propter nomen suum." >>new4.txt &&
+
+	cat >base.c <<-\EOF &&
+	int f(int x, int y)
+	{
+		if (x == 0)
+		{
+			return y;
+		}
+		return x;
+	}
+
+	int g(size_t u)
+	{
+		while (u < 30)
+		{
+			u++;
+		}
+		return u;
+	}
+	EOF
+
+	cat >ours.c <<-\EOF &&
+	int g(size_t u)
+	{
+		while (u < 30)
+		{
+			u++;
+		}
+		return u;
+	}
+
+	int h(int x, int y, int z)
+	{
+		if (z == 0)
+		{
+			return x;
+		}
+		return y;
+	}
+	EOF
+
+	cat >theirs.c <<-\EOF
+	int f(int x, int y)
+	{
+		if (x == 0)
+		{
+			return y;
+		}
+		return x;
+	}
+
+	int g(size_t u)
+	{
+		while (u > 34)
+		{
+			u--;
+		}
+		return u;
+	}
+	EOF
  '
 
  test_expect_success 'merge with no changes' '

@@ -447,4 +507,66 @@ test_expect_success '--object-id fails without repository' '
  	grep "not a git repository" err
  '
 
+test_expect_success 'merging C files with "myers" diff algorithm creates some spurious conflicts' '
+	cat >expect.c <<-\EOF &&
+	int g(size_t u)
+	{
+		while (u < 30)
+		{
+			u++;
+		}
+		return u;
+	}
+
+	int h(int x, int y, int z)
+	{
+	<<<<<<< ours.c
+		if (z == 0)
+	||||||| base.c
+		while (u < 30)
+	=======
+		while (u > 34)
+	>>>>>>> theirs.c
+		{
+	<<<<<<< ours.c
+			return x;
+	||||||| base.c
+			u++;
+	=======
+			u--;
+	>>>>>>> theirs.c
+		}
+		return y;
+	}
+	EOF
+
+	test_must_fail git merge-file -p --diff3 --diff-algorithm myers ours.c base.c theirs.c >myers_output.c &&
+	test_cmp expect.c myers_output.c
+'
+
+test_expect_success 'merging C files with "histogram" diff algorithm avoids some spurious conflicts' '
+	cat >expect.c <<-\EOF &&
+	int g(size_t u)
+	{
+		while (u > 34)
+		{
+			u--;
+		}
+		return u;
+	}
+
+	int h(int x, int y, int z)
+	{
+		if (z == 0)
+		{
+			return x;
+		}
+		return y;
+	}
+	EOF
+
+	git merge-file -p --diff3 --diff-algorithm histogram ours.c base.c theirs.c >histogram_output.c &&
+	test_cmp expect.c histogram_output.c
+'
+
  test_done

base-commit: 98009afd24e2304bf923a64750340423473809ff