Teach diff to honor diff algorithms set through git attributes

From: John Cai <[email protected]>

The diff option parsing for --minimal, --patience, --histgoram can all be consolidated into one function. This is a preparatory step for the subsequent commit which teaches diff to keep track of whether or not a diff algorithm has been set via the command line.

While we're at it, the logic that sets the diff algorithm in diff_opt_diff_algorithm() can be refactored into a helper that will allow multiple callsites to set the diff algorithm.

Signed-off-by John Cai <[email protected]>

---
  diff.c | 87 ++++++++++++++++++++++++++++++++++++----------------------
  1 file changed, 54 insertions(+), 33 deletions(-)

diff.c +21 -6

index 329eebf16a0..a8a31c81fe7 100644
@@ -3437,6 +3437,22 @@ static int diff_filepair_is_phoney(struct diff_filespec *one,
  	return !DIFF_FILE_VALID(one) && !DIFF_FILE_VALID(two);
  }
 
+static int set_diff_algorithm(struct diff_options *opts,
+			      const char *alg)
+{
+	long value = parse_algorithm_value(alg);
+
+	if (value < 0)
+		return 1;
+
+	/* clear out previous settings */
+	DIFF_XDL_CLR(opts, NEED_MINIMAL);
+	opts->xdl_opts &= ~XDF_DIFF_ALGORITHM_MASK;
+	opts->xdl_opts |= value;
+
+	return 0;
+}
+
  static void builtin_diff(const char *name_a,
  			 const char *name_b,
  			 struct diff_filespec *one,

@@ -5107,17 +5123,40 @@ static int diff_opt_diff_algorithm(const struct option *opt,
  				   const char *arg, int unset)
  {
  	struct diff_options *options = opt->value;
-	long value = parse_algorithm_value(arg);
 
  	BUG_ON_OPT_NEG(unset);
-	if (value < 0)
+
+	if (set_diff_algorithm(options, arg))
  		return error(_("option diff-algorithm accepts \"myers\", "
  			       "\"minimal\", \"patience\" and \"histogram\""));
 
-	/* clear out previous settings */
-	DIFF_XDL_CLR(options, NEED_MINIMAL);
-	options->xdl_opts &= ~XDF_DIFF_ALGORITHM_MASK;
-	options->xdl_opts |= value;
+	return 0;
+}
+

diff.c +10 -27

+
  	return 0;
  }
 

@@ -5242,26 +5281,6 @@ static enum parse_opt_result diff_opt_output(struct parse_opt_ctx_t *ctx,
  	return 0;
  }
 
-static int diff_opt_patience(const struct option *opt,
-			     const char *arg, int unset)
-{
-	struct diff_options *options = opt->value;
-	int i;
-
-	BUG_ON_OPT_NEG(unset);
-	BUG_ON_OPT_ARG(arg);
-	options->xdl_opts = DIFF_WITH_ALG(options, PATIENCE_DIFF);
-	/*
-	 * Both --patience and --anchored use PATIENCE_DIFF
-	 * internally, so remove any anchors previously
-	 * specified.
-	 */
-	for (i = 0; i < options->anchors_nr; i++)
-		free(options->anchors[i]);
-	options->anchors_nr = 0;
-	return 0;
-}
-
  static int diff_opt_ignore_regex(const struct option *opt,
  				 const char *arg, int unset)
  {

@@ -5562,9 +5581,10 @@ struct option *add_diff_options(const struct option *opts,
  			    N_("prevent rename/copy detection if the number of rename/copy targets exceeds given limit")),
 
  		OPT_GROUP(N_("Diff algorithm options")),
-		OPT_BIT(0, "minimal", &options->xdl_opts,
-			N_("produce the smallest possible diff"),
-			XDF_NEED_MINIMAL),
+		OPT_CALLBACK_F(0, "minimal", options, NULL,
+			       N_("produce the smallest possible diff"),
+			       PARSE_OPT_NONEG | PARSE_OPT_NOARG,
+			       diff_opt_diff_algorithm_no_arg),
  		OPT_BIT_F('w', "ignore-all-space", &options->xdl_opts,
  			  N_("ignore whitespace when comparing lines"),
  			  XDF_IGNORE_WHITESPACE, PARSE_OPT_NONEG),

@@ -5589,10 +5609,11 @@ struct option *add_diff_options(const struct option *opts,
  		OPT_CALLBACK_F(0, "patience", options, NULL,
  			       N_("generate diff using the \"patience diff\" algorithm"),
  			       PARSE_OPT_NONEG | PARSE_OPT_NOARG,
-			       diff_opt_patience),
-		OPT_BITOP(0, "histogram", &options->xdl_opts,
-			  N_("generate diff using the \"histogram diff\" algorithm"),
-			  XDF_HISTOGRAM_DIFF, XDF_DIFF_ALGORITHM_MASK),
+			       diff_opt_diff_algorithm_no_arg),
+		OPT_CALLBACK_F(0, "histogram", options, NULL,
+			       N_("generate diff using the \"histogram diff\" algorithm"),
+			       PARSE_OPT_NONEG | PARSE_OPT_NOARG,
+			       diff_opt_diff_algorithm_no_arg),
  		OPT_CALLBACK_F(0, "diff-algorithm", options, N_("<algorithm>"),
  			       N_("choose a diff algorithm"),
  			       PARSE_OPT_NONEG, diff_opt_diff_algorithm),

It can be useful to specify diff algorithms per file type. For example, one may want to use the minimal diff algorithm for .json files, another for .c files, etc.

Teach the diff machinery to check attributes for a diff algorithm. Enforce precedence by favoring the command line option, then looking at attributes, then finally the config.

To enforce precedence order, set the xdl_opts_command_line member during options pasing to indicate the diff algorithm was set via command line args.

Signed-off-by John Cai <[email protected]>

---

Quoted 16 lines · John Cai via GitGitGadget

It can be useful to specify diff algorithms per file type. For example, one may want to use the minimal diff algorithm for .json files, another for .c files, etc.

Teach the diff machinery to check attributes for a diff algorithm. Enforce precedence by favoring the command line option, then looking at attributes, then finally the config.

To enforce precedence order, set the xdl_opts_command_line member during options pasing to indicate the diff algorithm was set via command line args.

Signed-off-by John Cai <[email protected]>

---

diff.c static void builtin_diff(const char *name_a, · line 3653

Quoted 2 lines

diff.c +2 -0

@@ -3652,6 +3652,27 @@ static void builtin_diff(const char *name_a,
+               if (!o->xdl_opts_command_line) {
+                       static struct attr_check *check;

check is declared static...

diff.c static void builtin_diff(const char *name_a, · line 3661

Quoted 4 lines

diff.c +4 -0

+                       const char *one_diff_algo;
+                       const char *two_diff_algo;
+
+                       check = attr_check_alloc();

... is allocated here...

diff.c static void builtin_diff(const char *name_a, · line 3673

Quoted 12 lines

diff.c +12 -0

+                       attr_check_append(check, git_attr("diff-algorithm"));
+
+                       git_check_attr(the_repository->index, NULL, one->path, check);
+                       one_diff_algo = check->items[0].value;
+                       git_check_attr(the_repository->index, NULL, two->path, check);
+                       two_diff_algo = check->items[0].value;
+
+                       if (!ATTR_UNSET(one_diff_algo) && !ATTR_UNSET(two_diff_algo) &&
+                               !strcmp(one_diff_algo, two_diff_algo))
+                               set_diff_algorithm(o, one_diff_algo);
+
+                       attr_check_free(check);

... and freed here...

diff.c static void builtin_diff(const char *name_a, · line 3674

Quoted 1 line

diff.c +1 -0

+               }

... so the reason for the static declaration is not clear. Am I missing something obvious?

From: John Cai <[email protected]>

It can be useful to specify diff algorithms per file type. For example, one may want to use the minimal diff algorithm for .json files, another for .c files, etc.

Teach the diff machinery to check attributes for a diff algorithm. Enforce precedence by favoring the command line option, then looking at attributes, then finally the config.

To enforce precedence order, set the xdl_opts_command_line member during options pasing to indicate the diff algorithm was set via command line args.

t/lib-diff-alternative.sh +10 -1

index 8d1e408bb58..630c98ea65a 100644
@@ -107,8 +107,27 @@ EOF
 
  	STRATEGY=$1
 
+	test_expect_success "$STRATEGY diff from attributes" '
+		echo "file* diff-algorithm=$STRATEGY" >.gitattributes &&
+		test_must_fail git diff --no-index file1 file2 > output &&
+		test_cmp expect output
+	'
+
  	test_expect_success "$STRATEGY diff" '
-		test_must_fail git diff --no-index "--$STRATEGY" file1 file2 > output &&
+		test_must_fail git diff --no-index "--diff-algorithm=$STRATEGY" file1 file2 > output &&
+		test_cmp expect output
+	'
+

t/lib-diff-alternative.sh +1 -0

+	'
  }
 

Quoted 7 lines · John Cai via GitGitGadget

Teach the diff machinery to check attributes for a diff algorithm. Enforce precedence by favoring the command line option, then looking at attributes, then finally the config.

To enforce precedence order, set the xdl_opts_command_line member during options pasing to indicate the diff algorithm was set via command line args.

I've only commented on the tests as it looks like Eric and had a careful look at the code

Hi John

Quoted 5 lines · John Cai via GitGitGadget

From: John Cai <[email protected]>

It can be useful to specify diff algorithms per file type. For example, one may want to use the minimal diff algorithm for .json files, another for .c files, etc.

Have you got any examples of why this is useful? I find myself occasionally changing the algorithm when the default gives a sub-optimal diff but I've not really noticed any pattern with respect to file types.

Quoted 8 lines

Teach the diff machinery to check attributes for a diff algorithm. Enforce precedence by favoring the command line option, then looking at attributes, then finally the config.

To enforce precedence order, set the xdl_opts_command_line member during options pasing to indicate the diff algorithm was set via command line args.

I've only commented on the tests as it looks like Eric and had a careful look at the code

Quoted 22 lines

t/lib-diff-alternative.sh +13 -1

index 8d1e408bb58..630c98ea65a 100644
@@ -107,8 +107,27 @@ EOF
   	STRATEGY=$1
 +	test_expect_success "$STRATEGY diff from attributes" '
+		echo "file* diff-algorithm=$STRATEGY" >.gitattributes &&
+		test_must_fail git diff --no-index file1 file2 > output &&
+		test_cmp expect output
+	'
+
  	test_expect_success "$STRATEGY diff" '
-		test_must_fail git diff --no-index "--$STRATEGY" file1 file2 > output &&
+		test_must_fail git diff --no-index "--diff-algorithm=$STRATEGY" file1 file2 > output &&
+		test_cmp expect output
+	'
+
+	test_expect_success "$STRATEGY diff command line precedence before attributes" '
+		echo "file* diff-algorithm=meyers" >.gitattributes &&
+		test_must_fail git diff --no-index "--diff-algorithm=$STRATEGY" file1 file2 > output &&
+		test_cmp expect output

t/lib-diff-alternative.sh EOF · line 130

Quoted 6 lines

t/lib-diff-alternative.sh +6 -0

+	'
+
+	test_expect_success "$STRATEGY diff attributes precedence before config" '
+		git config diff.algorithm default &&
+		echo "file* diff-algorithm=$STRATEGY" >.gitattributes &&
+		test_must_fail git diff --no-index "--diff-algorithm=$STRATEGY" file1 file2 > output &&

This test passes with or without the code changes in this patch. I think you need to drop --diff-algorithm=$STRATEGY from the diff command.

t/lib-diff-alternative.sh EOF · line 192

Quoted 12 lines

t/lib-diff-alternative.sh +5 -0

  		test_cmp expect output
  	'
 @@ -166,5 +185,11 @@ EOF
  		test_must_fail git diff --no-index "--$STRATEGY" uniq1 uniq2 > output &&
  		test_cmp expect output
  	'
+
+	test_expect_success "$STRATEGY diff from attributes" '
+		echo "file* diff-algorithm=$STRATEGY" >.gitattributes &&
+		test_must_fail git diff --no-index uniq1 uniq2 > output &&
+		test_cmp expect output

This test also passes with or without the code changes in this patch. It is the same as the first test added above but with files that give the same diff irrespective of the algorithm chosen so I don't think it is doing anything useful. Unless I've missed something it should be dropped.

Best Wishes

Phillip

Quoted 3 lines

t/lib-diff-alternative.sh +1 -0

+	'
  }

Hi Phillip,

Quoted 9 lines · Phillip Wood

Hi John

Quoted 5 lines · John Cai via GitGitGadget

From: John Cai <[email protected]>

It can be useful to specify diff algorithms per file type. For example, one may want to use the minimal diff algorithm for .json files, another for .c files, etc.

Quoted 1 line

Have you got any examples of why this is useful? I find myself occasionally changing the algorithm when the default gives a sub-optimal diff but I've not really noticed any pattern with respect to file types.

At $DAYJOB, there has been a discussion and request for a feature like this [1]. One use case that came up was to be able to set a different diff algorithm for .json files.

1. https://gitlab.com/gitlab-org/gitaly/-/issues/2591

[...] I
think "myers" is default for historical reasons and histogram is better not just for special Salesforce xml files, but code files too. The output makes more sense to users. So much so that even though my simple testing suggested it had a 2% performance penalty compared to myers, I forced ort to use it[1] even though I designed everything else in that algorithm around eking out maximum performance. Others who have tested the diff algorithms have also found histogram has very similar performance to myers, and oftentimes even beats it[2][3]. Also, worries about invalidating rerere caches[4] was real, but we already paid that price when we switched to ort.

And if performance
is still a worry, [3] gives me reason to believe we can make our histogram implementation faster. Finally, for the period of time when Palantir was letting me make an internal git distribution (mostly for testing ort), I also carried a patch that changed the default diff algorithm to histogram (not just for ort, but for diff/log/etc. as well). Never had any complaints from the users from it. Perhaps you could do the same in your local version of git used by gitaly?

I also think the user request got converted to a particular solution without looking at the wider problem space: The idea seemed to assume "myers" is default for a good reason, and thus asked for an option to use something else. I'm not sure the assumption is valid;

Hi John,

Quoted 14 lines · John Cai

Hi Phillip,

Quoted 9 lines · Phillip Wood

Hi John

Quoted 5 lines · John Cai via GitGitGadget

From: John Cai <[email protected]>

It can be useful to specify diff algorithms per file type. For example, one may want to use the minimal diff algorithm for .json files, another for .c files, etc.

Quoted 7 lines

Quoted 1 line

Have you got any examples of why this is useful? I find myself occasionally changing the algorithm when the default gives a sub-optimal diff but I've not really noticed any pattern with respect to file types.

At $DAYJOB, there has been a discussion and request for a feature like this [1]. One use case that came up was to be able to set a different diff algorithm for .json files.

1. https://gitlab.com/gitlab-org/gitaly/-/issues/2591

A couple points:

First, there seems to be a misunderstanding in that issue. In particular, the merge algorithm does call into the xdiff library to do the three-way content merge of individual files, and when it does so, it has to specify the diff algorithm (or take the default, currently myers). merge-recursive allows the diff algorithm to be specified by the user (there are -Xdiff-algorithm={histogram,minimal,patience,myers} flags to merge/rebase for it), while merge-ort uses histogram (though it uses the same parser as merge-recursive and thus gets the variables set from the -Xdiff-algorithm flag, it just ignores those values and hardcodes histogram).

Second, I also think the user request got converted to a particular solution without looking at the wider problem space: The idea seemed to assume "myers" is default for a good reason, and thus asked for an option to use something else. I'm not sure the assumption is valid; I think "myers" is default for historical reasons and histogram is better not just for special Salesforce xml files, but code files too. The output makes more sense to users. So much so that even though my simple testing suggested it had a 2% performance penalty compared to myers, I forced ort to use it[1] even though I designed everything else in that algorithm around eking out maximum performance. Others who have tested the diff algorithms have also found histogram has very similar performance to myers, and oftentimes even beats it[2][3]. Also, worries about invalidating rerere caches[4] was real, but we

already paid that price when we switched to ort. And if performance is still a worry, [3] gives me reason to believe we can make our histogram implementation faster. Finally, for the period of time when Palantir was letting me make an internal git distribution (mostly for testing ort), I also carried a patch that changed the default diff algorithm to histogram (not just for ort, but for diff/log/etc. as well). Never had any complaints from the users from it. Perhaps you could do the same in your local version of git used by gitaly?

[1] See c8017176ac ("merge-ort: use histogram diff", 2020-12-13)
[2] From 85551232b5 ("perf: compare diff algorithms", 2012-03-06):
"This does indeed show that histogram diff slightly beats Myers, while patience is much slower than the others."
[3] https://github.com/pascalkuthe/imara-diff
[4] https://lore.kernel.org/git/[email protected]/

From: John Cai <[email protected]>
[...]

diff.c +9 -0

+
+		if (!o->xdl_opts_command_line) {
+			static struct attr_check *check;
+			const char *one_diff_algo;
+			const char *two_diff_algo;
+
+			check = attr_check_alloc();
+			attr_check_append(check, git_attr("diff-algorithm"));
+

diff.h +2 -0

@@ -333,6 +333,8 @@ struct diff_options {
 	int prefix_length;
 	const char *stat_sep;
 	int xdl_opts;
+	/* If xdl_opts has been set via the command line. */
+	int xdl_opts_command_line;
 
 	/* see Documentation/diff-options.txt */
 	char **anchors;

t/lib-diff-alternative.sh +0 -0

index 8d1e408bb58..630c98ea65a 100644
@@ -107,8 +107,27 @@ EOF
 
 	STRATEGY=$1

t/lib-diff-alternative.sh +13 -0

+		test_cmp expect output
+	'
+
+	test_expect_success "$STRATEGY diff command line precedence before attributes" '
+		echo "file* diff-algorithm=meyers" >.gitattributes &&
+		test_must_fail git diff --no-index "--diff-algorithm=$STRATEGY" file1 file2 > output &&
+		test_cmp expect output
+	'
+
+	test_expect_success "$STRATEGY diff attributes precedence before config" '
+		git config diff.algorithm default &&
+		echo "file* diff-algorithm=$STRATEGY" >.gitattributes &&
+		test_must_fail git diff --no-index "--diff-algorithm=$STRATEGY" file1 file2 > output &&
 		test_cmp expect output
 	'
 

Quoted 11 lines · John Cai via GitGitGadget

From: John Cai <[email protected]>
[...]

diff.c +9 -0

+
+		if (!o->xdl_opts_command_line) {
+			static struct attr_check *check;
+			const char *one_diff_algo;
+			const char *two_diff_algo;
+
+			check = attr_check_alloc();
+			attr_check_append(check, git_attr("diff-algorithm"));
+

diff.c static void builtin_diff(const char *name_a, · line 3673

Quoted 10 lines

diff.c +10 -0

+			git_check_attr(the_repository->index, NULL, one->path, check);
+			one_diff_algo = check->items[0].value;
+			git_check_attr(the_repository->index, NULL, two->path, check);
+			two_diff_algo = check->items[0].value;
+
+			if (!ATTR_UNSET(one_diff_algo) && !ATTR_UNSET(two_diff_algo) &&
+				!strcmp(one_diff_algo, two_diff_algo))
+				set_diff_algorithm(o, one_diff_algo);
+
+			attr_check_free(check);

This is a bit nitpicky, but I for one would find this much easier to read with some shorter variables, here just with "a" rather than "one_diff_algo", "b" instead of "two_diff_algo", and splitting "the_repository->index" into "istate" (untested):

	+		if (!o->xdl_opts_command_line) {
	+			static struct attr_check *check;
	+			const char *a;
	+			const char *b;
	+			struct index_state *istate = the_repository->index;
	+
	+			check = attr_check_alloc();
	+			attr_check_append(check, git_attr("diff-algorithm"));
	+
	+			git_check_attr(istate, NULL, one->path, check);
	+			a = check->items[0].value;
	+			git_check_attr(istate, NULL, two->path, check);
	+			b = check->items[0].value;
	+
	+			if (!ATTR_UNSET(a) && !ATTR_UNSET(b) && !strcmp(a, b))
	+				set_diff_algorithm(o, a);
	+
	+			attr_check_free(check);
	+		}

That also nicely keeps the line length shorter.

Quoted 18 lines

diff.h +2 -0

@@ -333,6 +333,8 @@ struct diff_options {
 	int prefix_length;
 	const char *stat_sep;
 	int xdl_opts;
+	/* If xdl_opts has been set via the command line. */
+	int xdl_opts_command_line;
 
 	/* see Documentation/diff-options.txt */
 	char **anchors;

t/lib-diff-alternative.sh +0 -0

index 8d1e408bb58..630c98ea65a 100644
@@ -107,8 +107,27 @@ EOF
 
 	STRATEGY=$1
 

t/lib-diff-alternative.sh EOF · line 117

Quoted 9 lines

t/lib-diff-alternative.sh +7 -1

+	test_expect_success "$STRATEGY diff from attributes" '
+		echo "file* diff-algorithm=$STRATEGY" >.gitattributes &&
+		test_must_fail git diff --no-index file1 file2 > output &&
+		test_cmp expect output
+	'
+
 	test_expect_success "$STRATEGY diff" '
-		test_must_fail git diff --no-index "--$STRATEGY" file1 file2 > output &&
+		test_must_fail git diff --no-index "--diff-algorithm=$STRATEGY" file1 file2 > output &&

Nit: The usual style is ">output", not "> output".

Quoted 18 lines

t/lib-diff-alternative.sh +13 -0

+		test_cmp expect output
+	'
+
+	test_expect_success "$STRATEGY diff command line precedence before attributes" '
+		echo "file* diff-algorithm=meyers" >.gitattributes &&
+		test_must_fail git diff --no-index "--diff-algorithm=$STRATEGY" file1 file2 > output &&
+		test_cmp expect output
+	'
+
+	test_expect_success "$STRATEGY diff attributes precedence before config" '
+		git config diff.algorithm default &&
+		echo "file* diff-algorithm=$STRATEGY" >.gitattributes &&
+		test_must_fail git diff --no-index "--diff-algorithm=$STRATEGY" file1 file2 > output &&
 		test_cmp expect output
 	'
 

t/lib-diff-alternative.sh EOF · line 194

Quoted 10 lines

t/lib-diff-alternative.sh +6 -0

@@ -166,5 +185,11 @@ EOF
 		test_must_fail git diff --no-index "--$STRATEGY" uniq1 uniq2 > output &&
 		test_cmp expect output
 	'
+
+	test_expect_success "$STRATEGY diff from attributes" '
+		echo "file* diff-algorithm=$STRATEGY" >.gitattributes &&
+		test_must_fail git diff --no-index uniq1 uniq2 > output &&
+		test_cmp expect output
+	'
 }

For some non-nitpicking, I do worry about exposing this as a DoS vector, e.g. here's a diff between two distant points in git.git with the various algorithms:

	$ hyperfine -r 1 -L a patience,minimal,histogram,myers 'git diff --diff-algorithm={a} v2.0.0 v2.28.0'
	Benchmark 1: git diff --diff-algorithm=patience v2.0.0 v2.28.0
	  Time (abs ≡):        42.121 s               [User: 41.879 s, System: 0.144 s]

	Benchmark 2: git diff --diff-algorithm=minimal v2.0.0 v2.28.0
	  Time (abs ≡):        35.634 s               [User: 35.473 s, System: 0.160 s]
	
	Benchmark 3: git diff --diff-algorithm=histogram v2.0.0 v2.28.0
	  Time (abs ≡):        46.912 s               [User: 46.657 s, System: 0.228 s]
	
	Benchmark 4: git diff --diff-algorithm=myers v2.0.0 v2.28.0
	  Time (abs ≡):        33.233 s               [User: 33.072 s, System: 0.160 s]
	
	Summary
	  'git diff --diff-algorithm=myers v2.0.0 v2.28.0' ran
	    1.07 times faster than 'git diff --diff-algorithm=minimal v2.0.0 v2.28.0'
	    1.27 times faster than 'git diff --diff-algorithm=patience v2.0.0 v2.28.0'
	    1.41 times faster than 'git diff --diff-algorithm=histogram v2.0.0 v2.28.0'

Now, all of those are very slow overall, but some much more than others. I seem to recall that the non-default ones also had some pathological cases.

Another thing to think about is that we've so far considered the diff algorithm to be purely about presentation, with some notable exceptions such as "patch-id".

I've advocated for us getting to the point of having an in-repo .gitconfig or .gitattributes before with a whitelist of settings like diff.context for certain paths, or a diff.orderFile.

But those seem easy to promise future behavior for, v.s. an entire diff algorithm (which we of course had before, but now we'd have it in repository data).

Maybe that's not a distinction worth worrying about, just putting that out there.

I think if others are concerned about the above something that would neatly side-step those is to have it opt-in via the .git/config somehow, similar to e.g. how you can commit *.gpg content, put this in .gitattributes:

*.gpg diff=gpg

But not have it do anything until this is in the repo's .git/config (or similar):

	[diff "gpg"]
        	textconv = gpg --no-tty --decrypt

For that you could still keep the exact .gitattributes format you have here, i.e.:

file* diff-algorithm=$STRATEGY

But we to pick it up we'd need either:

[diff-algorithm]
histogram = myers

Or:

[diff-algorithm "histogram"]
allow = true

The former form being one that would allow you to map the .gitattributes of the repo (but maybe that would be redundant to .git/info/attributes)...

Quoted 18 lines · Ævar Arnfjörð Bjarmason

On Sun, Feb 05 2023, John Cai via GitGitGadget wrote:
For some non-nitpicking, I do worry about exposing this as a DoS vector, e.g. here's a diff between two distant points in git.git with the various algorithms:

	$ hyperfine -r 1 -L a patience,minimal,histogram,myers 'git diff --diff-algorithm={a} v2.0.0 v2.28.0'
	Benchmark 1: git diff --diff-algorithm=patience v2.0.0 v2.28.0
	  Time (abs ≡):        42.121 s               [User: 41.879 s, System: 0.144 s]

	Benchmark 2: git diff --diff-algorithm=minimal v2.0.0 v2.28.0
	  Time (abs ≡):        35.634 s               [User: 35.473 s, System: 0.160 s]
	
	Benchmark 3: git diff --diff-algorithm=histogram v2.0.0 v2.28.0
	  Time (abs ≡):        46.912 s               [User: 46.657 s, System: 0.228 s]
	
	Benchmark 4: git diff --diff-algorithm=myers v2.0.0 v2.28.0
	  Time (abs ≡):        33.233 s               [User: 33.072 s, System: 0.160 s]

Quoted 5 lines

	Summary
	  'git diff --diff-algorithm=myers v2.0.0 v2.28.0' ran
	    1.07 times faster than 'git diff --diff-algorithm=minimal v2.0.0 v2.28.0'
	    1.27 times faster than 'git diff --diff-algorithm=patience v2.0.0 v2.28.0'
	    1.41 times faster than 'git diff --diff-algorithm=histogram v2.0.0 v2.28.0'

Thanks for this analysis. To clarify, .gitconfig's diff.algorithm setting is already an attack vector right?

I see how this would be adding another one.

That being said, here's a separate issue. I benchmarked the usage of .gitattributes as introduced in this patch series, and indeed it does look like there is additional latency:

$ echo "* diff-algorithm=patience >> .gitattributes
$ hyperfine -r 5 'git-bin-wrapper diff --diff-algorithm=patience v2.0.0 v2.28.0'                      ✭
Benchmark 1: git-bin-wrapper diff --diff-algorithm=patience v2.0.0 v2.28.0
   Time (mean ± σ):     889.4 ms ± 113.8 ms    [User: 715.7 ms, System: 65.3 ms]
   Range (min … max):   764.1 ms … 1029.3 ms    5 runs

$ hyperfine -r 5 'git-bin-wrapper diff v2.0.0 v2.28.0'                                                ✭
Benchmark 1: git-bin-wrapper diff v2.0.0 v2.28.0
   Time (mean ± σ):      2.146 s ±  0.368 s    [User: 0.827 s, System: 0.243 s]
   Range (min … max):    1.883 s …  2.795 s    5 runs

and I imagine the latency scales with the size of .gitattributes. Although I'm not familiar with other parts of the codebase and how it deals with the latency introduced by reading attributes files.

Quoted 39 lines

Now, all of those are very slow overall, but some much more than others. I seem to recall that the non-default ones also had some pathological cases.

Another thing to think about is that we've so far considered the diff algorithm to be purely about presentation, with some notable exceptions such as "patch-id".

I've advocated for us getting to the point of having an in-repo .gitconfig or .gitattributes before with a whitelist of settings like diff.context for certain paths, or a diff.orderFile.

But those seem easy to promise future behavior for, v.s. an entire diff algorithm (which we of course had before, but now we'd have it in repository data).

Maybe that's not a distinction worth worrying about, just putting that out there.

I think if others are concerned about the above something that would neatly side-step those is to have it opt-in via the .git/config somehow, similar to e.g. how you can commit *.gpg content, put this in .gitattributes:

*.gpg diff=gpg

But not have it do anything until this is in the repo's .git/config (or similar):

	[diff "gpg"]
         	textconv = gpg --no-tty --decrypt

For that you could still keep the exact .gitattributes format you have here, i.e.:

file* diff-algorithm=$STRATEGY

But we to pick it up we'd need either:

Quoted 7 lines

[diff-algorithm]
histogram = myers

Or:

[diff-algorithm "histogram"]
allow = true

This would help address slowness from the diff algorithm itself. I'm not opposed to adding this config if this attack vector is concerning to people.

However, it wouldn't help address the additional latency of scanning .gitattributes to find the diff algorithm.

Would a separate config to allow gitattributes be helpful here?

[diff-algorithm]
attributes = true

Quoted 4 lines

The former form being one that would allow you to map the .gitattributes of the repo (but maybe that would be redundant to .git/info/attributes)...

Hi John

Quoted 19 lines · John Cai

Quoted 18 lines · Ævar Arnfjörð Bjarmason

On Sun, Feb 05 2023, John Cai via GitGitGadget wrote:
For some non-nitpicking, I do worry about exposing this as a DoS vector, e.g. here's a diff between two distant points in git.git with the various algorithms:

	$ hyperfine -r 1 -L a patience,minimal,histogram,myers 'git diff --diff-algorithm={a} v2.0.0 v2.28.0'
	Benchmark 1: git diff --diff-algorithm=patience v2.0.0 v2.28.0
	  Time (abs ≡):        42.121 s               [User: 41.879 s, System: 0.144 s]

	Benchmark 2: git diff --diff-algorithm=minimal v2.0.0 v2.28.0
	  Time (abs ≡):        35.634 s               [User: 35.473 s, System: 0.160 s]
	
	Benchmark 3: git diff --diff-algorithm=histogram v2.0.0 v2.28.0
	  Time (abs ≡):        46.912 s               [User: 46.657 s, System: 0.228 s]
	
	Benchmark 4: git diff --diff-algorithm=myers v2.0.0 v2.28.0
	  Time (abs ≡):        33.233 s               [User: 33.072 s, System: 0.160 s]

Quoted 8 lines

Quoted 5 lines

	Summary
	  'git diff --diff-algorithm=myers v2.0.0 v2.28.0' ran
	    1.07 times faster than 'git diff --diff-algorithm=minimal v2.0.0 v2.28.0'
	    1.27 times faster than 'git diff --diff-algorithm=patience v2.0.0 v2.28.0'
	    1.41 times faster than 'git diff --diff-algorithm=histogram v2.0.0 v2.28.0'

Thanks for this analysis. To clarify, .gitconfig's diff.algorithm setting is already an attack vector right?

.gitconfig is under the user's control though whereas .gitattributes is attacker controlled if one clones a malicious repository. Having said the worst results above are for the historgram algorithm that merge-ort uses internally and no one has complained about ort's performance.

Quoted 17 lines

I see how this would be adding another one.

That being said, here's a separate issue. I benchmarked the usage of .gitattributes as introduced in this patch series, and indeed it does look like there is additional latency:

$ echo "* diff-algorithm=patience >> .gitattributes
$ hyperfine -r 5 'git-bin-wrapper diff --diff-algorithm=patience v2.0.0 v2.28.0'                      ✭
Benchmark 1: git-bin-wrapper diff --diff-algorithm=patience v2.0.0 v2.28.0
   Time (mean ± σ):     889.4 ms ± 113.8 ms    [User: 715.7 ms, System: 65.3 ms]
   Range (min … max):   764.1 ms … 1029.3 ms    5 runs

$ hyperfine -r 5 'git-bin-wrapper diff v2.0.0 v2.28.0'                                                ✭
Benchmark 1: git-bin-wrapper diff v2.0.0 v2.28.0
   Time (mean ± σ):      2.146 s ±  0.368 s    [User: 0.827 s, System: 0.243 s]
   Range (min … max):    1.883 s …  2.795 s    5 runs

Quoted 3 lines

and I imagine the latency scales with the size of .gitattributes. Although I'm not familiar with other parts of the codebase and how it deals with the latency introduced by reading attributes files.

Ouch! Thanks for benchmarking that is a suspiciously large slow down. I've a feeling the attributes code parses all the .gitattribute files from scratch for each path that's queried, so there may be scope for making it a bit smarter. I see some slow down but no where near as much

$ hyperfine -r 3 'bin-wrappers/git diff --diff-algorithm=patience --no-color --no-color-moved v2.0.0 v2.28.0'
Benchmark 1: bin-wrappers/git diff --diff-algorithm=patience --no-color --no-color-moved v2.0.0 v2.28.0
  Time (mean ± σ):      1.996 s ±  0.008 s    [User: 1.706 s, System: 0.286 s]
  Range (min … max):    1.989 s …  2.004 s    3 runs

$ hyperfine -r 5 'bin-wrappers/git diff --no-color --no-color-moved v2.0.0 v2.28.0'
Benchmark 1: bin-wrappers/git diff --no-color --no-color-moved v2.0.0 v2.28.0
  Time (mean ± σ):      2.238 s ±  0.037 s    [User: 1.880 s, System: 0.350 s]
  Range (min … max):    2.216 s …  2.303 s    5 runs

Perhaps I'm over simplifying but having read the issue you linked to I couldn't help feeling that the majority of users might be satisfied by just changing gitlab to use the patience algorithm when generating diffs.

The idea to use .gitattributes seems to have come from Patrick rather than a user request.

This is slightly off topic but one thing I'd really like is a way to tell diff use automatically use --diff-words on some files (e.g. Documentation/*)

Best Wishes

Phillip

Quoted 62 lines

Quoted 39 lines

Now, all of those are very slow overall, but some much more than others. I seem to recall that the non-default ones also had some pathological cases.

Another thing to think about is that we've so far considered the diff algorithm to be purely about presentation, with some notable exceptions such as "patch-id".

I've advocated for us getting to the point of having an in-repo .gitconfig or .gitattributes before with a whitelist of settings like diff.context for certain paths, or a diff.orderFile.

But those seem easy to promise future behavior for, v.s. an entire diff algorithm (which we of course had before, but now we'd have it in repository data).

Maybe that's not a distinction worth worrying about, just putting that out there.

I think if others are concerned about the above something that would neatly side-step those is to have it opt-in via the .git/config somehow, similar to e.g. how you can commit *.gpg content, put this in .gitattributes:

*.gpg diff=gpg

But not have it do anything until this is in the repo's .git/config (or similar):

	[diff "gpg"]
         	textconv = gpg --no-tty --decrypt

For that you could still keep the exact .gitattributes format you have here, i.e.:

file* diff-algorithm=$STRATEGY

But we to pick it up we'd need either:

Quoted 7 lines

[diff-algorithm]
histogram = myers

Or:

[diff-algorithm "histogram"]
allow = true

This would help address slowness from the diff algorithm itself. I'm not opposed to adding this config if this attack vector is concerning to people.

However, it wouldn't help address the additional latency of scanning .gitattributes to find the diff algorithm.

Would a separate config to allow gitattributes be helpful here?

[diff-algorithm]
attributes = true

Quoted 4 lines

The former form being one that would allow you to map the .gitattributes of the repo (but maybe that would be redundant to .git/info/attributes)...

Quoted 1 line

Perhaps I'm over simplifying but having read the issue you linked to I couldn't help feeling that the majority of users might be satisfied by just changing gitlab to use the patience algorithm when generating diffs.

Right, I recognize this is a judgment call that may be best left up to the list.

We don't have a way in GitLab to change the diff algorithm currently. Of course that can be implemented outside of Git,

Hi John and Phillip,

Quoted 1 line · John Cai

[...]

Quoted 6 lines

Quoted 1 line

Perhaps I'm over simplifying but having read the issue you linked to I couldn't help feeling that the majority of users might be satisfied by just changing gitlab to use the patience algorithm when generating diffs.

Right, I recognize this is a judgment call that may be best left up to the list.

We don't have a way in GitLab to change the diff algorithm currently. Of course that can be implemented outside of Git,

Well, the below doesn't allow users to make diffs better for *individual* files of interest, but if you agree with me that we should just make diffs better for all users automatically, it's a two-line change in git.git that I'd love to eventually convince the project to take (though obviously doing that would also require some documentation changes and some good messaging in release notes and whatnot). I've used it for a good long while, and had a few dozen users using this patch too, all without complaint:

diff.c +1 -1

index 329eebf16a..77a46d5b7d 100644
@@ -55,7 +55,7 @@ static int diff_relative;
  static int diff_stat_graph_width;
  static int diff_dirstat_permille_default = 30;
  static struct diff_options default_diff_options;
-static long diff_algorithm;
+static long diff_algorithm = XDF_HISTOGRAM_DIFF;
  static unsigned ws_error_highlight_default = WSEH_NEW;
 
  static char diff_colors[][COLOR_MAXLEN] = {

t/t4015-diff-whitespace.sh +0 -0

index b298f220e0..2f663eab72 100755
@@ -1549,7 +1549,7 @@ test_expect_success 'short lines of opposite

sign do not get marked as moved' '
this line should be marked as oldMoved newMoved unchanged 4
EOF

t/t4015-diff-whitespace.sh +1 -2

-       test_expect_code 1 git diff --no-index --color --color-moved=zebra \
+       test_expect_code 1 git diff --diff-algorithm=myers --no-index
--color --color-moved=zebra \
                 old.txt new.txt >output && cat output &&
         grep -v index output | test_decode_color >actual &&
         cat >expect <<-\EOF &&

I used histogram above rather than patience, since (a) it's what git's merge backend uses, (b) it produces roughly similar results to patience from a user perspective, (c) past testing has shown it to be somewhat faster than patience, and (d) we've potentially got some leads in how to speed up our histogram implementation from the README over at https://github.com/pascalkuthe/imara-diff. But, if you really wanted to use patience as the default, it'd also be an easy tweak.

Anyway, just some food for thought.

Hi Elijah

Quoted 12 lines · Elijah Newren

Hi John and Phillip,

Quoted 1 line · John Cai

[...]

Quoted 6 lines

Quoted 1 line

Perhaps I'm over simplifying but having read the issue you linked to I couldn't help feeling that the majority of users might be satisfied by just changing gitlab to use the patience algorithm when generating diffs.

Right, I recognize this is a judgment call that may be best left up to the list.

We don't have a way in GitLab to change the diff algorithm currently. Of course that can be implemented outside of Git,

Quoted 8 lines

Well, the below doesn't allow users to make diffs better for *individual* files of interest, but if you agree with me that we should just make diffs better for all users automatically, it's a two-line change in git.git that I'd love to eventually convince the project to take (though obviously doing that would also require some documentation changes and some good messaging in release notes and whatnot). I've used it for a good long while, and had a few dozen users using this patch too, all without complaint:

I'd support a change to either patience or histogram as the default algorithm. My personal preference would be for the patience algorithm as I think it generally gives nicer diffs in the cases that the two disagree (see below, I've tried changing diff.algorithm to histogram a few times and I always end up changing it back to patience pretty quickly). However I can see there is an advantage in having "diff" and "merge" use the same algorithm as users who diffing either side to the merge base will see the same diff that the merge is using. The histogram algorithm is known to produce sub-optimal diffs in certain cases[1] but I'm not sure how much worse it is in that respect than any of the other algorithms.

[1]
https://lore.kernel.org/git/CAGZ79kZYO6hHiAM8Sfp3J=VX11c=0-7YDSx3_EAKt5-uvvt-Ew@mail.gmail.com/

To see the differences between the output of patience and histogram algorithms I diffed the output of "git log -p --no-merges --diff-algorithm=patience" and "git log -p --no-merges --diff-algorithm=histogram". The first three differences are

- 6c065f72b8 (http: support CURLOPT_PROTOCOLS_STR, 2023-01-16) In get_curl_allowed_protocols() the patience algorithm shows the change in the return statement more clearly

- 47cfc9bd7d (attr: add flag --source to work with tree-ish, 2023-01-14) The histogram algorithm shows read_attr_from_index() being moved whereas the patience algorithm does not making the diff easier to follow.

- b0226007f0 (fsmonitor: eliminate call to deprecated FSEventStream function, 2022-12-14)
In fsm_listen__stop_async() the histogram algorithm shows data->shutdown_style = SHUTDOWN_EVENT;
being moved, which is not as clear as the patience output which shows it as a context line.

I think there is a degree of personal preference when it comes to which out of patience or histogram is best and the user can easily select their preferred algorithm so I'd be happy with either.

Hi Phillip,

Quoted 15 lines · Phillip Wood

Hi Elijah

On 09/02/2023 09:09, Elijah Newren wrote:
I'd support a change to either patience or histogram as the default algorithm. My personal preference would be for the patience algorithm as I think it generally gives nicer diffs in the cases that the two disagree (see below, I've tried changing diff.algorithm to histogram a few times and I always end up changing it back to patience pretty quickly). However I can see there is an advantage in having "diff" and "merge" use the same algorithm as users who diffing either side to the merge base will see the same diff that the merge is using. The histogram algorithm is known to produce sub-optimal diffs in certain cases[1] but I'm not sure how much worse it is in that respect than any of the other algorithms.

[...]

Quoted 2 lines

[1]
https://lore.kernel.org/git/CAGZ79kZYO6hHiAM8Sfp3J=VX11c=0-7YDSx3_EAKt5-uvvt-Ew@mail.gmail.com/

Thanks, I might have a fix, though I'm a bit worried my tweaks might trigger issues elsewhere or cost a bit of performance; I'll need to test. Are there any other good known testcases where histogram produces sub-optimal diffs?

Quoted 14 lines

To see the differences between the output of patience and histogram algorithms I diffed the output of "git log -p --no-merges --diff-algorithm=patience" and "git log -p --no-merges --diff-algorithm=histogram". The first three differences are

- 6c065f72b8 (http: support CURLOPT_PROTOCOLS_STR, 2023-01-16) In get_curl_allowed_protocols() the patience algorithm shows the change in the return statement more clearly

- 47cfc9bd7d (attr: add flag --source to work with tree-ish, 2023-01-14) The histogram algorithm shows read_attr_from_index() being moved whereas the patience algorithm does not making the diff easier to follow.

Quoted 6 lines

- b0226007f0 (fsmonitor: eliminate call to deprecated FSEventStream function, 2022-12-14)
In fsm_listen__stop_async() the histogram algorithm shows data->shutdown_style = SHUTDOWN_EVENT;
being moved, which is not as clear as the patience output which shows it as a context line.

If my current changes are "good", then they also remove the differences between patience and histogram for the second and third commits above. (And the differences between the two algorithms for the first commit look really minor.)

To see the differences between the output of patience and histogram algorithms I diffed the output of "git log -p --no-merges --diff-algorithm=patience" and "git log -p --no-merges --diff-algorithm=histogram". The first three differences are

- 6c065f72b8 (http: support CURLOPT_PROTOCOLS_STR, 2023-01-16) In get_curl_allowed_protocols() the patience algorithm shows the change in the return statement more clearly

- 47cfc9bd7d (attr: add flag --source to work with tree-ish, 2023-01-14) The histogram algorithm shows read_attr_from_index() being moved whereas the patience algorithm does not making the diff easier to follow.

- b0226007f0 (fsmonitor: eliminate call to deprecated FSEventStream function, 2022-12-14)
In fsm_listen__stop_async() the histogram algorithm shows data->shutdown_style = SHUTDOWN_EVENT;
being moved, which is not as clear as the patience output which shows it as a context line.

Quoted 14 lines · Phillip Wood

To see the differences between the output of patience and histogram algorithms I diffed the output of "git log -p --no-merges --diff-algorithm=patience" and "git log -p --no-merges --diff-algorithm=histogram". The first three differences are

- 6c065f72b8 (http: support CURLOPT_PROTOCOLS_STR, 2023-01-16) In get_curl_allowed_protocols() the patience algorithm shows the change in the return statement more clearly

- 47cfc9bd7d (attr: add flag --source to work with tree-ish, 2023-01-14) The histogram algorithm shows read_attr_from_index() being moved whereas the patience algorithm does not making the diff easier to follow.

Quoted 6 lines

- b0226007f0 (fsmonitor: eliminate call to deprecated FSEventStream function, 2022-12-14)
In fsm_listen__stop_async() the histogram algorithm shows data->shutdown_style = SHUTDOWN_EVENT;
being moved, which is not as clear as the patience output which shows it as a context line.

Just a small counter-point, since I happened to be looking at myers vs patience for something elsewhere in the thread, but:

git show 35bd13fcd2caa4185bf3729655ca20b6a5fe9b6f builtin/add.c

looks slightly better to me with myers, even though it is 2 lines longer. The issue is that patience and histogram are very eager to use blank lines as anchor points, so a diff like:

-some words
-
-and some more
+unrelated content
+
+but it happens to also be two paragraphs

in myers becomes:

-some words
+unrelated content

-and some more
+but it happens to also be two paragraphs

in patience (here I'm using single lines, but in practice these may be paragraphs, or stanzas of code). I think that's also the _strength_ of patience in many cases, but it really depends on the content. Replacing a multi-stanza block with another one may be the best explanation for what happened. Or the two stanzas may be independent, and showing the change for each one may be better.

I'm not sure which one happens more often. And you'd probably want to weight it by how good/bad the change is. In the example I showed I don't find patience very much worse, since it's already a pretty ugly diff. But in cases where patience shines, it may be making things significantly more readable.

I don't have a super strong opinion, but I just wanted to chime in that it is not clear to me that patience/histogram is always a win over myers (yes, I know your examples were comparing patience vs histogram, but the larger thread is discussing the other).

Quoted 4 lines

Just a small counter-point, since I happened to be looking at myers vs patience for something elsewhere in the thread, but:

git show 35bd13fcd2caa4185bf3729655ca20b6a5fe9b6f builtin/add.c

"fatal: bad object 35bd13fcd2caa4185bf3729655ca20b6a5fe9b6f"

Is that a local commit of yours?

* They had two people annotating the diffs and independently
scoring them, and then checked for agreement between their answers afterwards. (No, they didn't always agree, but they did have substantial agreement.)

For the (again, non-identical) diffs modifying non-code, they found (see table 11) that:
* 14.9% of the myers diffs are better
* 13.4% of the histogram diffs are better
* 71.6% of the diffs have equal quality

For the (non-identical) diffs modifying code, they found (again, see table 11) that:
* 16.9% of the myers diffs are better
* 62.6% of the histogram diffs are better
* 20.6% of the diffs have equal quality

A ratio of 4 to 1 for histogram being better on code diffs is pretty weighty to me.

Quoted 5 lines

Quoted 1 line

git show 35bd13fcd2caa4185bf3729655ca20b6a5fe9b6f builtin/add.c

"fatal: bad object 35bd13fcd2caa4185bf3729655ca20b6a5fe9b6f"

Is that a local commit of yours?

Oh, sorry. It's not my commit, but it may have been something I picked up off the list. The version from Junio is 20b813d7d3d.

FWIW, I coincidentally hit this case earlier today where patience does a _much_ better job than myers:

https://lore.kernel.org/git/[email protected]/

So don't count me as an objection, but just a curious observer. ;)

Just a small counter-point, since I happened to be looking at myers vs patience for something elsewhere in the thread, but:

   git show 35bd13fcd2caa4185bf3729655ca20b6a5fe9b6f builtin/add.c

looks slightly better to me with myers, even though it is 2 lines longer. The issue is that patience and histogram are very eager to use blank lines as anchor points, so a diff like:

-some words
-
-and some more
+unrelated content
+
+but it happens to also be two paragraphs

in myers becomes:

-some words
+unrelated content

-and some more
+but it happens to also be two paragraphs

in patience (here I'm using single lines, but in practice these may be paragraphs, or stanzas of code). I think that's also the _strength_ of patience in many cases, but it really depends on the content.

Replacing
a multi-stanza block with another one may be the best explanation for what happened. Or the two stanzas may be independent, and showing the change for each one may be better.

I'm not sure which one happens more often. And you'd probably want to weight it by how good/bad the change is. In the example I showed I don't find patience very much worse, since it's already a pretty ugly diff. But in cases where patience shines, it may be making things significantly more readable.

I don't have a super strong opinion, but I just wanted to chime in that it is not clear to me that patience/histogram is always a win over myers (yes, I know your examples were comparing patience vs histogram, but the larger thread is discussing the other).

Indeed. Ironically as there are no unique context lines in that example the blank lines are being matched by patience implementation falling back to the myers algorithm. Normally the myers implementation tries to avoid matching common context lines between two blocks of changed lines but I think because

in this case it is only called on a small part of the file the blank lines are not common enough to trigger that heuristic. I've got a patch[1] that stops the patience implementation falling back to the myers algorithm and just trims any leading and trailing context. On the whole it I think it gives more readable diffs but I've not got any systematic data to back that up. I also suspect there are pathological cases such as each line in the file being duplicated where the falling back to the myers algorithm gives a much better result.

This is slightly off topic but one thing I'd really like is a way to tell diff use automatically use --diff-words on some files (e.g. Documentation/*)

Quoted 3 lines · Phillip Wood

This is slightly off topic but one thing I'd really like is a way to tell diff use automatically use --diff-words on some files (e.g. Documentation/*)

Unlike changing the algorithm, -U options, diff.orderFile etc. doing that would give you a diff that can't be applied with "git apply" or other tools that expect a valid unified diff.

So I can imagine that it would be neat in some contexts, but such a change would have much wider implications than options that tweak how a valid unified diff looks, or is generated.

We'd need some way to mark a diff as "for ad-hoc viewing only".

But as it sounds like you want this for git.git the Documentation/doc-diff script is much better than anything word-diff could spew out, as it diffs the resulting generated docs.

I wonder (but haven't tried) whether you can't "diff" that using the same method that can be used to diff binary files using a custom driver.

Hrm, except that in that case (with includes etc) there isn't really a 1=1 mapping between files within Documentation/ and generated docs (due to includes etc.). But I suppose it could be used only for those files that 1=1 correspond to the generated manpages.

That being said, here's a separate issue. I benchmarked the usage of .gitattributes as introduced in this patch series, and indeed it does look like there is additional latency:

$ echo "* diff-algorithm=patience >> .gitattributes
$ hyperfine -r 5 'git-bin-wrapper diff --diff-algorithm=patience v2.0.0 v2.28.0'                      ✭
Benchmark 1: git-bin-wrapper diff --diff-algorithm=patience v2.0.0 v2.28.0
  Time (mean ± σ):     889.4 ms ± 113.8 ms    [User: 715.7 ms, System: 65.3 ms]
  Range (min … max):   764.1 ms … 1029.3 ms    5 runs

$ hyperfine -r 5 'git-bin-wrapper diff v2.0.0 v2.28.0'                                                ✭
Benchmark 1: git-bin-wrapper diff v2.0.0 v2.28.0
  Time (mean ± σ):      2.146 s ±  0.368 s    [User: 0.827 s, System: 0.243 s]
  Range (min … max):    1.883 s …  2.795 s    5 runs

and I imagine the latency scales with the size of .gitattributes. Although I'm not familiar with other parts of the codebase and how it deals with the latency introduced by reading attributes files.

Hi John,

Quoted 1 line · John Cai

[...]

Quoted 10 lines

That being said, here's a separate issue. I benchmarked the usage of .gitattributes as introduced in this patch series, and indeed it does look like there is additional latency:

$ echo "* diff-algorithm=patience >> .gitattributes
$ hyperfine -r 5 'git-bin-wrapper diff --diff-algorithm=patience v2.0.0 v2.28.0'                      ✭
Benchmark 1: git-bin-wrapper diff --diff-algorithm=patience v2.0.0 v2.28.0
  Time (mean ± σ):     889.4 ms ± 113.8 ms    [User: 715.7 ms, System: 65.3 ms]
  Range (min … max):   764.1 ms … 1029.3 ms    5 runs

Quoted 8 lines

$ hyperfine -r 5 'git-bin-wrapper diff v2.0.0 v2.28.0'                                                ✭
Benchmark 1: git-bin-wrapper diff v2.0.0 v2.28.0
  Time (mean ± σ):      2.146 s ±  0.368 s    [User: 0.827 s, System: 0.243 s]
  Range (min … max):    1.883 s …  2.795 s    5 runs

and I imagine the latency scales with the size of .gitattributes. Although I'm not familiar with other parts of the codebase and how it deals with the latency introduced by reading attributes files.

Yeah, that seems like a large relative performance penalty. I had the feeling that histogram wasn't made the default over myers mostly due to inertia and due to a potential 2% loss in performance (since potentially corrected by Phillip's 663c5ad035 ("diff histogram: intern strings", 2021-11-17)). If we had changed the default diff algorithm to histogram, I suspect folks wouldn't have been asking for per-file knobs to use a better diff algorithm. And the performance penalty for this alternative is clearly much larger than 2%, which makes me think we might want to just revisit the default instead of allowing per-file tweaks.

And on a separate note...

There's another set of considerations we might need to include here as well that I haven't seen anyone else in this thread talk about:

* When trying to diff files, do we read the .gitattributes file from the current checkout to determine the diff algorithm(s)? Or the index? Or the commit we are diffing against?
* If we use the current checkout or index, what about bare clones or diffing between two different commits?
* If diffing between two different commits, and the .gitattributes has changed between those commits, which .gitattributes file wins?
* If diffing between two different commits, and the .gitattributes has NOT changed, BUT a file has been renamed and the old and new names have different rules, which rule wins?

* If per-file diff algorithms are adopted widely enough, will we be forced to change the merge algorithm to also pay attention to them? If it does, more complicated rename cases occur and we need rules for how to handle those.
* If the merge algorithm has to pay attention to .gitattributes for this too, we'll have even more corner cases around what happens if there are merge conflicts in .gitattributes itself (which is already kind of ugly and kludged)

Anyway, I know I'm a bit animated and biased in this area, and I apologize if I'm a bit too much so. Even if I am, hopefully my comments at least provide some useful context.

Quoted 2 lines · Elijah Newren

Quoted 1 line · John Cai

It seems like the performance penalty was because I was adding calls to parse attribute files. Piggy backing off of the attribute parsing in userdiff.h will allow us to not incur this performance penalty:

$ hyperfine -r 5 -L a bin-wrappers/git,git '{a} diff v2.0.0 v2.28.0'
Benchmark 1: git-bin-wrapper diff v2.0.0 v2.28.0
  Time (mean ± σ):      1.072 s ±  0.289 s    [User: 0.626 s, System: 0.081 s]
  Range (min … max):    0.772 s …  1.537 s    5 runs

Benchmark 2: git diff v2.0.0 v2.28.0
Time (mean ± σ): 1.003 s ± 0.065 s [User: 0.684 s, System: 0.067 s]
Range (min … max): 0.914 s … 1.091 s 5 runs

Summary
'git diff v2.0.0 v2.28.0' ran

    1.07 ± 0.30 times faster than 'git-bin-wrapper diff v2.0.0 v2.28.0'

Quoted 4 lines

And on a separate note...

There's another set of considerations we might need to include here as well that I haven't seen anyone else in this thread talk about:

These are some great questions. I'll do my best to answer them.

Quoted 11 lines

* When trying to diff files, do we read the .gitattributes file from the current checkout to determine the diff algorithm(s)? Or the index? Or the commit we are diffing against?
* If we use the current checkout or index, what about bare clones or diffing between two different commits?
* If diffing between two different commits, and the .gitattributes has changed between those commits, which .gitattributes file wins?
* If diffing between two different commits, and the .gitattributes has NOT changed, BUT a file has been renamed and the old and new names have different rules, which rule wins?

In the next version I plan on using Peff's suggestion of utilizing the existing diff driver scheme [1]. I believe these four questions are addressed if we use the existing userdiff.h API, which in turn calls the attr.h API. We check the worktree, then fallback to the index.

By using the userdiff.h API, the behavior will match what users already expect when they for instance set an external driver.

1. https://lore.kernel.org/git/[email protected]/

Quoted 9 lines

* If per-file diff algorithms are adopted widely enough, will we be forced to change the merge algorithm to also pay attention to them? If it does, more complicated rename cases occur and we need rules for how to handle those.
* If the merge algorithm has to pay attention to .gitattributes for this too, we'll have even more corner cases around what happens if there are merge conflicts in .gitattributes itself (which is already kind of ugly and kludged)

I see this feature as a user-experience type convenience feature, so I don't believe there's need for the merge machinery to also pay attention to the diff algorithm set through gitattrbutes. We can clarify this in the documentation.

Quoted 3 lines

Anyway, I know I'm a bit animated and biased in this area, and I apologize if I'm a bit too much so. Even if I am, hopefully my comments at least provide some useful context.

No problem! thanks for raising these issues.

thanks
John

Quoted 11 lines · John Cai via GitGitGadget

From: John Cai <[email protected]>
[...]

diff.c +9 -0

+
+             if (!o->xdl_opts_command_line) {
+                     static struct attr_check *check;
+                     const char *one_diff_algo;
+                     const char *two_diff_algo;
+
+                     check = attr_check_alloc();
+                     attr_check_append(check, git_attr("diff-algorithm"));
+

diff.c static void builtin_diff(const char *name_a, · line 3673

Quoted 10 lines

diff.c +10 -0

+                     git_check_attr(the_repository->index, NULL, one->path, check);
+                     one_diff_algo = check->items[0].value;
+                     git_check_attr(the_repository->index, NULL, two->path, check);
+                     two_diff_algo = check->items[0].value;
+
+                     if (!ATTR_UNSET(one_diff_algo) && !ATTR_UNSET(two_diff_algo) &&
+                             !strcmp(one_diff_algo, two_diff_algo))
+                             set_diff_algorithm(o, one_diff_algo);
+
+                     attr_check_free(check);

This is a bit nitpicky, but I for one would find this much easier to read with some shorter variables, here just with "a" rather than "one_diff_algo", "b" instead of "two_diff_algo", and splitting "the_repository->index" into "istate" (untested):

+ if (!o->xdl_opts_command_line) {
+ static struct attr_check *check;
+ const char *a;
+ const char *b;
+ struct index_state *istate = the_repository->index;
+
+ check = attr_check_alloc();
+ attr_check_append(check, git_attr("diff-algorithm"));
+
+ git_check_attr(istate, NULL, one->path, check);
+ a = check->items[0].value;
+ git_check_attr(istate, NULL, two->path, check);
+ b = check->items[0].value;
+
+ if (!ATTR_UNSET(a) && !ATTR_UNSET(b) && !strcmp(a, b))
+ set_diff_algorithm(o, a);
+
+ attr_check_free(check);
+ }

That also nicely keeps the line length shorter.

Quoted 16 lines

diff.h +2 -0

@@ -333,6 +333,8 @@ struct diff_options {
      int prefix_length;
      const char *stat_sep;
      int xdl_opts;
+     /* If xdl_opts has been set via the command line. */
+     int xdl_opts_command_line;
 
      /* see Documentation/diff-options.txt */
      char **anchors;

t/lib-diff-alternative.sh +0 -0

index 8d1e408bb58..630c98ea65a 100644
@@ -107,8 +107,27 @@ EOF
 
      STRATEGY=$1

t/lib-diff-alternative.sh EOF · line 117

Quoted 10 lines

t/lib-diff-alternative.sh +7 -1

 
+     test_expect_success "$STRATEGY diff from attributes" '
+             echo "file* diff-algorithm=$STRATEGY" >.gitattributes &&
+             test_must_fail git diff --no-index file1 file2 > output &&
+             test_cmp expect output
+     '
+
      test_expect_success "$STRATEGY diff" '
-             test_must_fail git diff --no-index "--$STRATEGY" file1 file2 > output &&
+             test_must_fail git diff --no-index "--diff-algorithm=$STRATEGY" file1 file2 > output &&

Nit: The usual style is ">output", not "> output".

Quoted 17 lines

t/lib-diff-alternative.sh +13 -0

+             test_cmp expect output
+     '
+
+     test_expect_success "$STRATEGY diff command line precedence before attributes" '
+             echo "file* diff-algorithm=meyers" >.gitattributes &&
+             test_must_fail git diff --no-index "--diff-algorithm=$STRATEGY" file1 file2 > output &&
+             test_cmp expect output
+     '
+
+     test_expect_success "$STRATEGY diff attributes precedence before config" '
+             git config diff.algorithm default &&
+             echo "file* diff-algorithm=$STRATEGY" >.gitattributes &&
+             test_must_fail git diff --no-index "--diff-algorithm=$STRATEGY" file1 file2 > output &&
              test_cmp expect output
      '
 

t/lib-diff-alternative.sh EOF · line 194

Quoted 10 lines

t/lib-diff-alternative.sh +6 -0

@@ -166,5 +185,11 @@ EOF
              test_must_fail git diff --no-index "--$STRATEGY" uniq1 uniq2 > output &&
              test_cmp expect output
      '
+
+     test_expect_success "$STRATEGY diff from attributes" '
+             echo "file* diff-algorithm=$STRATEGY" >.gitattributes &&
+             test_must_fail git diff --no-index uniq1 uniq2 > output &&
+             test_cmp expect output
+     '
 }

For some non-nitpicking, I do worry about exposing this as a DoS vector, e.g. here's a diff between two distant points in git.git with the various algorithms:

        $ hyperfine -r 1 -L a patience,minimal,histogram,myers 'git diff --diff-algorithm={a} v2.0.0 v2.28.0'
        Benchmark 1: git diff --diff-algorithm=patience v2.0.0 v2.28.0
          Time (abs ≡):        42.121 s               [User: 41.879 s, System: 0.144 s]

        Benchmark 2: git diff --diff-algorithm=minimal v2.0.0 v2.28.0
          Time (abs ≡):        35.634 s               [User: 35.473 s, System: 0.160 s]

        Benchmark 3: git diff --diff-algorithm=histogram v2.0.0 v2.28.0
          Time (abs ≡):        46.912 s               [User: 46.657 s, System: 0.228 s]

        Benchmark 4: git diff --diff-algorithm=myers v2.0.0 v2.28.0
          Time (abs ≡):        33.233 s               [User: 33.072 s, System: 0.160 s]

        Summary
          'git diff --diff-algorithm=myers v2.0.0 v2.28.0' ran
            1.07 times faster than 'git diff --diff-algorithm=minimal v2.0.0 v2.28.0'
            1.27 times faster than 'git diff --diff-algorithm=patience v2.0.0 v2.28.0'
            1.41 times faster than 'git diff --diff-algorithm=histogram v2.0.0 v2.28.0'

Quoted 123 lines · Ævar Arnfjörð Bjarmason

Quoted 11 lines · John Cai via GitGitGadget

From: John Cai <[email protected]>
[...]

diff.c +9 -0

+
+             if (!o->xdl_opts_command_line) {
+                     static struct attr_check *check;
+                     const char *one_diff_algo;
+                     const char *two_diff_algo;
+
+                     check = attr_check_alloc();
+                     attr_check_append(check, git_attr("diff-algorithm"));
+

diff.c static void builtin_diff(const char *name_a, · line 3673

Quoted 10 lines

diff.c +10 -0

+                     git_check_attr(the_repository->index, NULL, one->path, check);
+                     one_diff_algo = check->items[0].value;
+                     git_check_attr(the_repository->index, NULL, two->path, check);
+                     two_diff_algo = check->items[0].value;
+
+                     if (!ATTR_UNSET(one_diff_algo) && !ATTR_UNSET(two_diff_algo) &&
+                             !strcmp(one_diff_algo, two_diff_algo))
+                             set_diff_algorithm(o, one_diff_algo);
+
+                     attr_check_free(check);

This is a bit nitpicky, but I for one would find this much easier to read with some shorter variables, here just with "a" rather than "one_diff_algo", "b" instead of "two_diff_algo", and splitting "the_repository->index" into "istate" (untested):

+ if (!o->xdl_opts_command_line) {
+ static struct attr_check *check;
+ const char *a;
+ const char *b;
+ struct index_state *istate = the_repository->index;
+
+ check = attr_check_alloc();
+ attr_check_append(check, git_attr("diff-algorithm"));
+
+ git_check_attr(istate, NULL, one->path, check);
+ a = check->items[0].value;
+ git_check_attr(istate, NULL, two->path, check);
+ b = check->items[0].value;
+
+ if (!ATTR_UNSET(a) && !ATTR_UNSET(b) && !strcmp(a, b))
+ set_diff_algorithm(o, a);
+
+ attr_check_free(check);
+ }

That also nicely keeps the line length shorter.

Quoted 16 lines

diff.h +2 -0

@@ -333,6 +333,8 @@ struct diff_options {
      int prefix_length;
      const char *stat_sep;
      int xdl_opts;
+     /* If xdl_opts has been set via the command line. */
+     int xdl_opts_command_line;
 
      /* see Documentation/diff-options.txt */
      char **anchors;

t/lib-diff-alternative.sh +0 -0

index 8d1e408bb58..630c98ea65a 100644
@@ -107,8 +107,27 @@ EOF
 
      STRATEGY=$1

t/lib-diff-alternative.sh EOF · line 117

Quoted 10 lines

t/lib-diff-alternative.sh +7 -1

 
+     test_expect_success "$STRATEGY diff from attributes" '
+             echo "file* diff-algorithm=$STRATEGY" >.gitattributes &&
+             test_must_fail git diff --no-index file1 file2 > output &&
+             test_cmp expect output
+     '
+
      test_expect_success "$STRATEGY diff" '
-             test_must_fail git diff --no-index "--$STRATEGY" file1 file2 > output &&
+             test_must_fail git diff --no-index "--diff-algorithm=$STRATEGY" file1 file2 > output &&

Nit: The usual style is ">output", not "> output".

Quoted 17 lines

t/lib-diff-alternative.sh +13 -0

+             test_cmp expect output
+     '
+
+     test_expect_success "$STRATEGY diff command line precedence before attributes" '
+             echo "file* diff-algorithm=meyers" >.gitattributes &&
+             test_must_fail git diff --no-index "--diff-algorithm=$STRATEGY" file1 file2 > output &&
+             test_cmp expect output
+     '
+
+     test_expect_success "$STRATEGY diff attributes precedence before config" '
+             git config diff.algorithm default &&
+             echo "file* diff-algorithm=$STRATEGY" >.gitattributes &&
+             test_must_fail git diff --no-index "--diff-algorithm=$STRATEGY" file1 file2 > output &&
              test_cmp expect output
      '
 

t/lib-diff-alternative.sh EOF · line 194

Quoted 10 lines

t/lib-diff-alternative.sh +6 -0

@@ -166,5 +185,11 @@ EOF
              test_must_fail git diff --no-index "--$STRATEGY" uniq1 uniq2 > output &&
              test_cmp expect output
      '
+
+     test_expect_success "$STRATEGY diff from attributes" '
+             echo "file* diff-algorithm=$STRATEGY" >.gitattributes &&
+             test_must_fail git diff --no-index uniq1 uniq2 > output &&
+             test_cmp expect output
+     '
 }

For some non-nitpicking, I do worry about exposing this as a DoS vector, e.g. here's a diff between two distant points in git.git with the various algorithms:

        $ hyperfine -r 1 -L a patience,minimal,histogram,myers 'git diff --diff-algorithm={a} v2.0.0 v2.28.0'
        Benchmark 1: git diff --diff-algorithm=patience v2.0.0 v2.28.0
          Time (abs ≡):        42.121 s               [User: 41.879 s, System: 0.144 s]

        Benchmark 2: git diff --diff-algorithm=minimal v2.0.0 v2.28.0
          Time (abs ≡):        35.634 s               [User: 35.473 s, System: 0.160 s]

        Benchmark 3: git diff --diff-algorithm=histogram v2.0.0 v2.28.0
          Time (abs ≡):        46.912 s               [User: 46.657 s, System: 0.228 s]

Quoted 8 lines

        Benchmark 4: git diff --diff-algorithm=myers v2.0.0 v2.28.0
          Time (abs ≡):        33.233 s               [User: 33.072 s, System: 0.160 s]

        Summary
          'git diff --diff-algorithm=myers v2.0.0 v2.28.0' ran
            1.07 times faster than 'git diff --diff-algorithm=minimal v2.0.0 v2.28.0'
            1.27 times faster than 'git diff --diff-algorithm=patience v2.0.0 v2.28.0'
            1.41 times faster than 'git diff --diff-algorithm=histogram v2.0.0 v2.28.0'

If you run with more than 1 run, are your numbers even repeatable?

I'm really surprised by these numbers; they aren't remotely close to what I compute. Am I correct in understanding you ran these in git.git? Was your computer overloaded? Was your git.git in some serious need of repacking? Was it on a network filesystem?

Using git compiled from current main, I see:

$ hyperfine -L a patience,minimal,histogram,myers './git diff
--diff-algorithm={a} v2.0.0 v2.28.0'
Benchmark 1: ./git diff --diff-algorithm=patience v2.0.0 v2.28.0
  Time (mean ± σ):      1.142 s ±  0.033 s    [User: 1.022 s, System: 0.114 s]
  Range (min … max):    1.117 s …  1.212 s    10 runs

Benchmark 2: ./git diff --diff-algorithm=minimal v2.0.0 v2.28.0
Time (mean ± σ): 1.959 s ± 0.011 s [User: 1.830 s, System: 0.120 s]
Range (min … max): 1.947 s … 1.976 s 10 runs

Benchmark 3: ./git diff --diff-algorithm=histogram v2.0.0 v2.28.0
Time (mean ± σ): 1.187 s ± 0.007 s [User: 1.065 s, System: 0.115 s]
Range (min … max): 1.175 s … 1.200 s 10 runs

Benchmark 4: ./git diff --diff-algorithm=myers v2.0.0 v2.28.0
Time (mean ± σ): 1.194 s ± 0.007 s [User: 1.068 s, System: 0.120 s]
Range (min … max): 1.184 s … 1.206 s 10 runs

Summary
'./git diff --diff-algorithm=patience v2.0.0 v2.28.0' ran

    1.04 ± 0.03 times faster than './git diff
--diff-algorithm=histogram v2.0.0 v2.28.0'
    1.05 ± 0.03 times faster than './git diff --diff-algorithm=myers
v2.0.0 v2.28.0'
    1.71 ± 0.05 times faster than './git diff --diff-algorithm=minimal

v2.0.0 v2.28.0'

And this is on a kind-of low-end refurbished laptop from a few years ago (although the repo was recently gc'ed).

I'm biased towards histogram (and making it the default rather than making it configurable per file), but that's probably obvious given that I made ort use it unconditionally. And when I made ort use it, it was actually a minor performance penalty (~1% IIRC)[*], but I thought it was worth it since (a) histogram diffs are more understandable to users in general, (b) the histogram diff data structures provide an idea for possibly solving some ugly corner cases that I don't see a way to solve with the other diffs.

Quoted 1 line

If you run with more than 1 run, are your numbers even repeatable?

Yes, but tl;dr it's diff.colorMoved=true, sorry, see below.

+diff-algorithm
+^^^^^^^^^^^^^^^^

Documentation/gitattributes.txt +11 -0

+
+The attribute `diff-algorithm` affects which algorithm Git uses to generate
+diffs. This allows defining diff algorithms per file extension. Precedence rules
+are as follows, in order from highest to lowest:
+
+*Command line option*
+
+Pass in the `--diff-algorithm` command line option int git-diff(1)
+
+*Git attributes*
+

On Sun, Feb 05, 2023 at 03:46:21AM +0000, John Cai via GitGitGadget wrote:

From the user's perspective, this is weirdly inconsistent with the existing diff attributes, which would be more like:

  # in .gitattributes
  *.json diff=json 

  # in config
  [diff "json"]
  algorithm = histogram

I know why one might choose the scheme you did; it kicks in if the repo sets the algorithm, without users having to set up any extra config. Which is sort of nice, if we assume that malicious actors don't have any incentive to pick the algorithm. In theory they don't, though I saw Ævar mention possible DoS elsewhere in the thread.

Side note: It's also possible that algorithm selection could be required to trigger a separate security bug (say, a buffer overflow in the patience code or something), so restricting that works in a belt-and-suspenders way. But that somehow feels like like the wrong side of the paranoia-vs-feature line.

So I dunno. I recognize that this scheme fulfills your immediate needs better, but I fear that we'll be stuck with a weird split between "diff" and "diff-*" attributes forever. In the long run, having a way for the repo to say "and here is some config I recommend to you" would give you the best of both, but that is a challenging topic that has been discussed and punted on for many years.

Quoted 9 lines

From the user's perspective, this is weirdly inconsistent with the existing diff attributes, which would be more like:

  # in .gitattributes
  *.json diff=json 

  # in config
  [diff "json"]
  algorithm = histogram

That does look more elegant.

Quoted 11 lines · Ævar Arnfjörð Bjarmason

Quoted 9 lines

From the user's perspective, this is weirdly inconsistent with the existing diff attributes, which would be more like:

  # in .gitattributes
  *.json diff=json 

  # in config
  [diff "json"]
  algorithm = histogram

That does look more elegant.

We use attributes to define what it is, while configurations are used to define what to do on different things. The separation of attributes and configuration came not from "elegance" or "security" but from a lot more practical reasons.

For a tracked file, the fact that it contains JSON text as payload does not change per user who cloned the project, or per platform the user used to do so. In-tree .gitattributes that the project controls is a perfect way to define what it is for each file.

On the other hand, the diff program suitable to compare two JSON files may vary per platform (your favorite Windows program may not be available to me) and per user (a platform may support more than one and the choice becomes the matter of personal taste).

The security aspect of giving users tighter control over which exact programs are to be run by not allowing the attributes or so called in-tree configuration mechansim is a small bonus that fell out as a consequence.

To clarify, I'm not suggesting that we ever read arbitrary parts of the "diff.<driver>.<key>" config space, but that we could whitelist one set of "diff.<driver>.<known-key>"="<known-values>".

Quoted 3 lines · Ævar Arnfjörð Bjarmason

To clarify, I'm not suggesting that we ever read arbitrary parts of the "diff.<driver>.<key>" config space, but that we could whitelist one set of "diff.<driver>.<known-key>"="<known-values>".

When the value names the path to an executable or the command line to invoke a program, there is no "portable" value that is useful. Whitelisting macOS only program only because its pathname is one of the known values does not help me running something else.

Quoted 13 lines · John Cai via GitGitGadget

+diff-algorithm
+^^^^^^^^^^^^^^^^

Documentation/gitattributes.txt +11 -0

+
+The attribute `diff-algorithm` affects which algorithm Git uses to generate
+diffs. This allows defining diff algorithms per file extension. Precedence rules
+are as follows, in order from highest to lowest:
+
+*Command line option*
+
+Pass in the `--diff-algorithm` command line option int git-diff(1)
+
+*Git attributes*
+

Documentation/gitattributes.txt String:: · line 761

Quoted 10 lines

Documentation/gitattributes.txt +10 -0

+------------------------
+*.json	diff-algorithm=histogram
+------------------------
+
+*Git config*
+
+----------------------------------------------------------------
+[diff]
+	algorithm = histogram
+----------------------------------------------------------------

From the user's perspective, this is weirdly inconsistent with the existing diff attributes, which would be more like:

  # in .gitattributes
  *.json diff=json 

  # in config
  [diff "json"]
  algorithm = histogram

I know why one might choose the scheme you did; it kicks in if the repo sets the algorithm, without users having to set up any extra config. Which is sort of nice, if we assume that malicious actors don't have any incentive to pick the algorithm. In theory they don't, though I saw Ævar mention possible DoS elsewhere in the thread.

Side note: It's also possible that algorithm selection could be required to trigger a separate security bug (say, a buffer overflow in the patience code or something), so restricting that works in a belt-and-suspenders way. But that somehow feels like like the wrong side of the paranoia-vs-feature line.

So I dunno. I recognize that this scheme fulfills your immediate needs better, but I fear that we'll be stuck with a weird split between "diff" and "diff-*" attributes forever. In the long run, having a way for the repo to say "and here is some config I recommend to you" would give you the best of both, but that is a challenging topic that has been discussed and punted on for many years.

-Peff

Quoted 9 lines

From the user's perspective, this is weirdly inconsistent with the existing diff attributes, which would be more like:

  # in .gitattributes
  *.json diff=json 

  # in config
  [diff "json"]
  algorithm = histogram

Thanks for this suggestion, Peff. What I like about this is that it builds off of the existing diff.<driver> scheme rather than inventing another one. Additionally, we won't get hit with a performance penalty since we already read gitattrbitues to see if a driver has been set or not.

Thinking out loud, if we add "algorithm" as a key for diff.<driver>, it would be mutually exclusive with "command" where "command" takes precedence, correct?

From: John Cai <[email protected]>

The diff option parsing for --minimal, --patience, --histgoram can all be consolidated into one function. This is a preparatory step for the subsequent commit which teaches diff to keep track of whether or not a diff algorithm has been set via the command line.

diff.c +5 -0

index 329eebf16a0..92a0eab942e 100644
@@ -3437,6 +3437,22 @@ static int diff_filepair_is_phoney(struct diff_filespec *one,
 	return !DIFF_FILE_VALID(one) && !DIFF_FILE_VALID(two);
 }
 
+static int set_diff_algorithm(struct diff_options *opts,
+			      const char *alg)
+{
+	long value = parse_algorithm_value(alg);
+

diff.c +1 -2

 static void builtin_diff(const char *name_a,
 			 const char *name_b,
 			 struct diff_filespec *one,

@@ -5107,17 +5123,40 @@ static int diff_opt_diff_algorithm(const struct option *opt,
 				   const char *arg, int unset)
 {
 	struct diff_options *options = opt->value;
-	long value = parse_algorithm_value(arg);
 
 	BUG_ON_OPT_NEG(unset);
-	if (value < 0)
+

diff.c +16 -0

+static int diff_opt_diff_algorithm_no_arg(const struct option *opt,
+				   const char *arg, int unset)
+{
+	struct diff_options *options = opt->value;
+
+	BUG_ON_OPT_NEG(unset);
+	BUG_ON_OPT_ARG(arg);
+
+	if (!strcmp(opt->long_name, "patience")) {
+		size_t i;
+		/*
+		 * Both --patience and --anchored use PATIENCE_DIFF
+		 * internally, so remove any anchors previously
+		 * specified.
+		 */
+		for (i = 0; i < options->anchors_nr; i++)

Quoted 6 lines · John Cai via GitGitGadget

From: John Cai <[email protected]>

The diff option parsing for --minimal, --patience, --histgoram can all be consolidated into one function. This is a preparatory step for the subsequent commit which teaches diff to keep track of whether or not a diff algorithm has been set via the command line.

Everybody other than patience used to be just a bit-op but now everybody is a callback?

Quoted 13 lines

diff.c +5 -0

index 329eebf16a0..92a0eab942e 100644
@@ -3437,6 +3437,22 @@ static int diff_filepair_is_phoney(struct diff_filespec *one,
 	return !DIFF_FILE_VALID(one) && !DIFF_FILE_VALID(two);
 }
 
+static int set_diff_algorithm(struct diff_options *opts,
+			      const char *alg)
+{
+	long value = parse_algorithm_value(alg);
+

diff.c static int diff_filepair_is_phoney(struct diff_filespec *one, · line 3454

Quoted 10 lines

diff.c +10 -0

+	if (value < 0)
+		return 1;
+
+	/* clear out previous settings */
+	DIFF_XDL_CLR(opts, NEED_MINIMAL);
+	opts->xdl_opts &= ~XDF_DIFF_ALGORITHM_MASK;
+	opts->xdl_opts |= value;
+
+	return 0;
+}

The above is a faithful copy of diff_opt_diff_algorithm(), except that it returns 1 (not -1) on failure, which is unexpected in this codebase, and should be corrected if this patch gets rerolled.

Quoted 12 lines

diff.c +1 -2

 static void builtin_diff(const char *name_a,
 			 const char *name_b,
 			 struct diff_filespec *one,

@@ -5107,17 +5123,40 @@ static int diff_opt_diff_algorithm(const struct option *opt,
 				   const char *arg, int unset)
 {
 	struct diff_options *options = opt->value;
-	long value = parse_algorithm_value(arg);
 
 	BUG_ON_OPT_NEG(unset);
-	if (value < 0)
+

diff.c static int diff_opt_diff_algorithm(const struct option *opt, · line 5134

Quoted 10 lines

diff.c +3 -4

+	if (set_diff_algorithm(options, arg))
 		return error(_("option diff-algorithm accepts \"myers\", "
 			       "\"minimal\", \"patience\" and \"histogram\""));
 
-	/* clear out previous settings */
-	DIFF_XDL_CLR(options, NEED_MINIMAL);
-	options->xdl_opts &= ~XDF_DIFF_ALGORITHM_MASK;
-	options->xdl_opts |= value;
+	return 0;
+}

This version of diff_opt_diff_algorithm() behaves identically from the version before this patch, which is excellent.

Quoted 16 lines

diff.c +16 -0

+static int diff_opt_diff_algorithm_no_arg(const struct option *opt,
+				   const char *arg, int unset)
+{
+	struct diff_options *options = opt->value;
+
+	BUG_ON_OPT_NEG(unset);
+	BUG_ON_OPT_ARG(arg);
+
+	if (!strcmp(opt->long_name, "patience")) {
+		size_t i;
+		/*
+		 * Both --patience and --anchored use PATIENCE_DIFF
+		 * internally, so remove any anchors previously
+		 * specified.
+		 */
+		for (i = 0; i < options->anchors_nr; i++)

diff.c static int diff_opt_diff_algorithm(const struct option *opt, · line 5161

Quoted 10 lines

diff.c +8 -0

+			free(options->anchors[i]);
+		options->anchors_nr = 0;
+	}
+
+	if (set_diff_algorithm(options, opt->long_name))
+		BUG("available diff algorithms include \"myers\", "
+			       "\"minimal\", \"patience\" and \"histogram\"");
+
 	return 0;
 }

Calling this instead of diff_opt_patience() would make "--patience" parsed identically as before without this patch, which is excellent.

diff.c struct option *add_diff_options(const struct option *opts, · line 5587

Quoted 11 lines

diff.c +4 -3

@@ -5562,9 +5581,10 @@ struct option *add_diff_options(const struct option *opts,
 			    N_("prevent rename/copy detection if the number of rename/copy targets exceeds given limit")),
 
 		OPT_GROUP(N_("Diff algorithm options")),
-		OPT_BIT(0, "minimal", &options->xdl_opts,
-			N_("produce the smallest possible diff"),
-			XDF_NEED_MINIMAL),
+		OPT_CALLBACK_F(0, "minimal", options, NULL,
+			       N_("produce the smallest possible diff"),
+			       PARSE_OPT_NONEG | PARSE_OPT_NOARG,
+			       diff_opt_diff_algorithm_no_arg),

I offhand cannot say that these two are equivalent, even though they ought to be (otherwise this patch would break things). The callback seems to do much more than just a simple "flip the NEED_MINIMAL bit on".

diff.c struct option *add_diff_options(const struct option *opts, · line 5616

Quoted 8 lines

diff.c +5 -3

-		OPT_BITOP(0, "histogram", &options->xdl_opts,
-			  N_("generate diff using the \"histogram diff\" algorithm"),
-			  XDF_HISTOGRAM_DIFF, XDF_DIFF_ALGORITHM_MASK),
+			       diff_opt_diff_algorithm_no_arg),
+		OPT_CALLBACK_F(0, "histogram", options, NULL,
+			       N_("generate diff using the \"histogram diff\" algorithm"),
+			       PARSE_OPT_NONEG | PARSE_OPT_NOARG,
+			       diff_opt_diff_algorithm_no_arg),

Likewise.

By nature, patience (and anchored) needs to do much more than everybody else, so it almost feels that it is OK (and preferable, even) to leave it a special case to make the distinction stand out. Consolidating everybody else who are much simpler to share the more complex callback does not look like a good change to me, at least at the first glance.

Thanks.

Yeah, it's not great to pull things out from a bit flip to a callback but I needed some way of setting the xdl_opts_command_line member in the next commit

And I think that is a reasonable way to use callback to do "more than just setting a bit". Even in that case, I am not sure if it is a good idea to share the same callback that has conditional code that only is relevant to the "patience" case, though.

I'd have expected it with individual callbacks like:

int handle_patience(...)

  {
	do_patience_specific_stuff();
	do_shared_stuff(PATIENCE_DIFF);

}

int handle_histogram(...)

  {
	do_shared_stuff(HISTOGRAM_DIFF);

}

and so on. That's a bit more verbose, but the call stack reflects the flow we expect.

Quoted 13 lines · Jeff King

I'd have expected it with individual callbacks like:

int handle_patience(...)

  {
	do_patience_specific_stuff();
	do_shared_stuff(PATIENCE_DIFF);

}

int handle_histogram(...)

  {
	do_shared_stuff(HISTOGRAM_DIFF);

}

Quoted 2 lines

and so on. That's a bit more verbose, but the call stack reflects the flow we expect.

Exactly.

Thanks for spelling it out.

From: John Cai <[email protected]>

It can be useful to specify diff algorithms per file type. For example, one may want to use the minimal diff algorithm for .json files, another for .c files, etc.

Teach the diff machinery to check attributes for a diff driver. Also teach the diff driver parser a new type "algorithm" to look for in the config, which will be used if a driver has been specified through the attributes.

Enforce precedence of diff algorithm by favoring the command line option, then looking at the driver attributes & config combination, then finally the diff.algorithm config.

To enforce precedence order, use the xdl_opts_command_line member during options pasing to indicate the diff algorithm was set via command line args.

Signed-off-by John Cai <[email protected]>

---
 Documentation/gitattributes.txt | 41 ++++++++++++++++++++++++++++++++-
 diff.c                          | 25 +++++++++++++-------
 diff.h                          |  2 ++
 t/lib-diff-alternative.sh       | 38 +++++++++++++++++++++++++++++-
 userdiff.c                      |  4 +++-
 userdiff.h                      |  1 +
 6 files changed, 100 insertions(+), 11 deletions(-)

Documentation/gitattributes.txt +0 -0

index c19e64ea0ef..7e69f509d0a 100644

diff.c +1 -6

-
-	if (o->flags.allow_external) {
-		struct userdiff_driver *drv;
-
-		drv = userdiff_find_by_path(o->repo->index, attr_path);
+	if (o->flags.allow_external)
 		if (drv && drv->external)
 			pgm = drv->external;
-	}
 
 	if (msg) {
 		/*

diff.c +2 -1

 		builtin_diff(name, other ? other : name,
 			     one, two, xfrm_msg, must_show_header,
 			     o, complete_rewrite);
-	else
+	} else {
 		fprintf(o->file, "* Unmerged path %s\n", name);
+	}
 }
 
 

Quoted 4 lines

diff.c +0 -0

index 92a0eab942e..24da439e56f 100644

diff.c static void run_diff_cmd(const char *pgm, · line 4459

Quoted 5 lines

diff.c +1 -0

@@ -4456,15 +4456,11 @@ static void run_diff_cmd(const char *pgm,
 	const char *xfrm_msg = NULL;
 	int complete_rewrite = (p->status == DIFF_STATUS_MODIFIED) && p->score;
 	int must_show_header = 0;
+	struct userdiff_driver *drv = userdiff_find_by_path(o->repo->index, attr_path);

Do we run this look-up unconditionally, even when .allow_external bit is not set? Why?

diff.c static void run_diffstat(struct diff_filepair *p, struct diff_options *o, · line 4589

Quoted 7 lines

diff.c +3 -0

@@ -4583,6 +4584,10 @@ static void run_diffstat(struct diff_filepair *p, struct diff_options *o,
 	const char *name;
 	const char *other;
 
+	struct userdiff_driver *drv = userdiff_find_by_path(o->repo->index, p->one->path);
+	if (drv && drv->algorithm)
+		set_diff_algorithm(o, drv->algorithm);

Interesting. Does external diff play a role, like in run_diff_cmd() we saw earlier?

Quoted 4 lines · Junio C Hamano

Quoted 4 lines

diff.c +0 -0

index 92a0eab942e..24da439e56f 100644

Quoted 8 lines

diff.c static void run_diff_cmd(const char *pgm, · line 4459

Quoted 5 lines

diff.c +1 -0

@@ -4456,15 +4456,11 @@ static void run_diff_cmd(const char *pgm,
 	const char *xfrm_msg = NULL;
 	int complete_rewrite = (p->status == DIFF_STATUS_MODIFIED) && p->score;
 	int must_show_header = 0;
+	struct userdiff_driver *drv = userdiff_find_by_path(o->repo->index, attr_path);

Do we run this look-up unconditionally, even when .allow_external bit is not set? Why?

Ah, this is perfectly fine. It used to be that this codepath can tell that there is no need to check the diff driver when it is told never to use any external diff driver. Now, even when it is computing the diff internally, it needs to check the diff driver to find out the favoured algorithm for the path.

Strictly speaking, if we are told NOT to use external diff driver, and if we are told NOT to pay attention to algorithm given by the diff driver, then we know we can skip the overhead of attribute look-up. I.e. we could do this to avoid attribute look-up:

	struct userdiff_driver *drv = NULL;

	if (o->flags.allow_external || !o->ignore_driver_algorithm)
		drv = userdiff_find_by_path(...);

	if (drv && o->flags.allow_external && drv->external)
		pgm = drv->external;
	...
	if (pgm)
		... do the external diff thing ...
	if (one && two) {
		if (drv && !o->ignore_driver_algorithm && drv->algorithm)
			set_diff_algo(...)

I was not sure if it would be worth it before writing the above down, but the resulting flow does not look _too_ bad.

Quoted 11 lines

diff.c static void run_diffstat(struct diff_filepair *p, struct diff_options *o, · line 4589

Quoted 8 lines

diff.c +3 -0

@@ -4583,6 +4584,10 @@ static void run_diffstat(struct diff_filepair *p, struct diff_options *o,
 	const char *name;
 	const char *other;
 
+	struct userdiff_driver *drv = userdiff_find_by_path(o->repo->index, p->one->path);
+	if (drv && drv->algorithm)
+		set_diff_algorithm(o, drv->algorithm);

Interesting. Does external diff play a role, like in run_diff_cmd() we saw earlier?

As whoever wrote "diffstat" did not think of counting output from external diff driver, of course in this codepath external diff would not appear. So what we see is very much expected.

Just move the blank line we see before these new lines one line down, so that the variable decls are grouped together, with a blank line before the first executable statement. I.e.

	const char *name;
	const char *other;

Shouldn't this function refrain from setting algorithm from the driver when the algorithm was given elsewhere? E.g.

	$ git show --histogram --stat

or something? IOW, shouldn't it also pay attention to o->ignore_driver_algorithm bit, just like run_diff_cmd() did?

From: John Cai <[email protected]>

A subsequent commit will need the ability to tell if the diff algorithm was set through the command line through setting a new member of diff_options. While this logic can be added to the diff_opt_diff_algorithm() callback, the --minimal and --histogram options are handled via OPT_BIT without a callback.

Remedy this by consolidating the options parsing logic for --minimal and --histogram into one callback. This way we can modify diff_options in that function.

As an additional refactor, the logic that sets the diff algorithm in diff_opt_diff_algorithm() can be refactored into a helper that will allow multiple callsites to set the diff algorithm.

Signed-off-by John Cai <[email protected]>

---
 diff.c | 57 +++++++++++++++++++++++++++++++++++++++++++--------------
 1 file changed, 43 insertions(+), 14 deletions(-)

From: John Cai <[email protected]>

A subsequent commit will need the ability to tell if the diff algorithm was set through the command line through setting a new member of diff_options. While this logic can be added to the diff_opt_diff_algorithm() callback, the --minimal and --histogram options are handled via OPT_BIT without a callback.

Remedy this by consolidating the options parsing logic for --minimal and --histogram into one callback. This way we can modify diff_options in that function.

As an additional refactor, the logic that sets the diff algorithm in diff_opt_diff_algorithm() can be refactored into a helper that will allow multiple callsites to set the diff algorithm.

Signed-off-by John Cai <[email protected]>

---
 diff.c | 57 +++++++++++++++++++++++++++++++++++++++++++--------------
 1 file changed, 43 insertions(+), 14 deletions(-)

diff.c +43 -15

index 329eebf16a0..5efc22ca06b 100644
@@ -3437,6 +3437,22 @@ static int diff_filepair_is_phoney(struct diff_filespec *one,
        return !DIFF_FILE_VALID(one) && !DIFF_FILE_VALID(two);
 }
 
+static int set_diff_algorithm(struct diff_options *opts,
+                             const char *alg)
+{
+       long value = parse_algorithm_value(alg);
+
+       if (value < 0)
+               return -1;
+
+       /* clear out previous settings */
+       DIFF_XDL_CLR(opts, NEED_MINIMAL);
+       opts->xdl_opts &= ~XDF_DIFF_ALGORITHM_MASK;
+       opts->xdl_opts |= value;
+
+       return 0;
+}
+
 static void builtin_diff(const char *name_a,
                         const char *name_b,
                         struct diff_filespec *one,

@@ -5107,17 +5123,28 @@ static int diff_opt_diff_algorithm(const struct option *opt,
                                   const char *arg, int unset)
 {
        struct diff_options *options = opt->value;
-       long value = parse_algorithm_value(arg);
 
        BUG_ON_OPT_NEG(unset);
-       if (value < 0)
+
+       if (set_diff_algorithm(options, arg))
                return error(_("option diff-algorithm accepts \"myers\", "
                               "\"minimal\", \"patience\" and \"histogram\""));
 
-       /* clear out previous settings */
-       DIFF_XDL_CLR(options, NEED_MINIMAL);
-       options->xdl_opts &= ~XDF_DIFF_ALGORITHM_MASK;
-       options->xdl_opts |= value;
+       return 0;
+}
+
+static int diff_opt_diff_algorithm_no_arg(const struct option *opt,
+                                  const char *arg, int unset)
+{
+       struct diff_options *options = opt->value;
+
+       BUG_ON_OPT_NEG(unset);
+       BUG_ON_OPT_ARG(arg);
+
+       if (set_diff_algorithm(options, opt->long_name))
+               BUG("available diff algorithms include \"myers\", "
+                              "\"minimal\", \"patience\" and \"histogram\"");
+
        return 0;
 }
 

@@ -5250,7 +5277,6 @@ static int diff_opt_patience(const struct option *opt,
 
        BUG_ON_OPT_NEG(unset);
        BUG_ON_OPT_ARG(arg);
-       options->xdl_opts = DIFF_WITH_ALG(options, PATIENCE_DIFF);
        /*
         * Both --patience and --anchored use PATIENCE_DIFF
         * internally, so remove any anchors previously

@@ -5259,7 +5285,8 @@ static int diff_opt_patience(const struct option *opt,
        for (i = 0; i < options->anchors_nr; i++)
                free(options->anchors[i]);
        options->anchors_nr = 0;
-       return 0;
+
+       return set_diff_algorithm(options, "patience");
 }
 
 static int diff_opt_ignore_regex(const struct option *opt,

@@ -5562,9 +5589,10 @@ struct option *add_diff_options(const struct option *opts,
                            N_("prevent rename/copy detection if the number of rename/copy targets exceeds given limit")),
 
                OPT_GROUP(N_("Diff algorithm options")),
-               OPT_BIT(0, "minimal", &options->xdl_opts,
-                       N_("produce the smallest possible diff"),
-                       XDF_NEED_MINIMAL),
+               OPT_CALLBACK_F(0, "minimal", options, NULL,
+                              N_("produce the smallest possible diff"),
+                              PARSE_OPT_NONEG | PARSE_OPT_NOARG,
+                              diff_opt_diff_algorithm_no_arg),
                OPT_BIT_F('w', "ignore-all-space", &options->xdl_opts,
                          N_("ignore whitespace when comparing lines"),
                          XDF_IGNORE_WHITESPACE, PARSE_OPT_NONEG),

@@ -5590,9 +5618,10 @@ struct option *add_diff_options(const struct option *opts,
                               N_("generate diff using the \"patience diff\" algorithm"),
                               PARSE_OPT_NONEG | PARSE_OPT_NOARG,
                               diff_opt_patience),
-               OPT_BITOP(0, "histogram", &options->xdl_opts,
-                         N_("generate diff using the \"histogram diff\" algorithm"),
-                         XDF_HISTOGRAM_DIFF, XDF_DIFF_ALGORITHM_MASK),
+               OPT_CALLBACK_F(0, "histogram", options, NULL,
+                              N_("generate diff using the \"histogram diff\" algorithm"),
+                              PARSE_OPT_NONEG | PARSE_OPT_NOARG,
+                              diff_opt_diff_algorithm_no_arg),
                OPT_CALLBACK_F(0, "diff-algorithm", options, N_("<algorithm>"),
                               N_("choose a diff algorithm"),
                               PARSE_OPT_NONEG, diff_opt_diff_algorithm),
--

gitgitgadget