Skip to contentSkip to conversation

Rework git-diff algorithm selection

PATCH Superseded Michal Privoznik 2 participants 7 messages Jun 15, 2016 Documentation

v1 of 3 Superseded Latest is v3 →

lore
Share & tools
lore
#0 lore raw

cover Rework git-diff algorithm selection

It's been a while I was trying to get this in. Recently, I realized how important this is.

Please keep me CC'ed as I am not subscribed to the list.

Michal Privoznik (3):
git-completion.bash: Autocomplete --minimal and --histogram for
git-diff
config: Introduce diff.algorithm variable
diff: Introduce --diff-algorithm command line option

 Documentation/diff-config.txt          | 17 +++++++++++++++++
 Documentation/diff-options.txt         | 22 ++++++++++++++++++++++
 contrib/completion/git-completion.bash | 14 +++++++++++++-
 diff.c                                 | 33 +++++++++++++++++++++++++++++++++
 diff.h                                 |  2 ++
 merge-recursive.c                      |  6 ++++++
 6 files changed, 93 insertions(+), 1 deletion(-)
Signature · 1 line
1.8.0.2
#1 lore raw

PATCH 1/3 git-completion.bash: Autocomplete --minimal and --histogram for git-diff

Even though --patience was already there, we missed --minimal and --histogram for some reason.

---
 contrib/completion/git-completion.bash | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
contrib/completion/git-completion.bash +1 -1
index a4c48e1..383518c 100644
@@ -1031,7 +1031,7 @@ __git_diff_common_options="--stat --numstat --shortstat --summary
 			--no-ext-diff
 			--no-prefix --src-prefix= --dst-prefix=
 			--inter-hunk-context=
-			--patience
+			--patience --histogram --minimal
 			--raw
 			--dirstat --dirstat= --dirstat-by-file
 			--dirstat-by-file= --cumulative
Signature · 1 line
1.8.0.2
#2 lore raw

PATCH 2/3 config: Introduce diff.algorithm variable

In reply to Michal Privoznik

Some users or projects prefer different algorithms over others, e.g. patience over myers or similar. However, specifying appropriate argument every time diff is to be used is impractical. Moreover, creating an alias doesn't play nicely with other tools based on diff (git-show for instance). Hence, a configuration variable which is able to set specific algorithm is needed. For now, these four values are
accepted: 'myers' (which has the same effect as not setting the config variable at all), 'minimal', 'patience' and 'histogram'.

---
 Documentation/diff-config.txt          | 17 +++++++++++++++++
 contrib/completion/git-completion.bash |  1 +
 diff.c                                 | 23 +++++++++++++++++++++++
 3 files changed, 41 insertions(+)
Documentation/diff-config.txt +17 -0
index 4314ad0..be31276 100644
@@ -155,3 +155,20 @@ diff.tool::
 	"kompare".  Any other value is treated as a custom diff tool,
 	and there must be a corresponding `difftool.<tool>.cmd`
 	option.
+
+diff.algorithm::
+	Choose a diff algorithm.  The variants are as follows:
++
+--
+`myers`;;
+	The basic greedy diff algorithm.
+`minimal`;;
+	Spend extra time to make sure the smallest possible diff is
+	produced.
+`patience`;;
+	Use "patience diff" algorithm when generating patches.
+`histogram`;;
+	This algorithm extends the patience algorithm to "support
+	low-occurrence common elements".
+--
++
contrib/completion/git-completion.bash +1 -0
index 383518c..33e25dc 100644
@@ -1839,6 +1839,7 @@ _git_config ()
 		diff.suppressBlankEmpty
 		diff.tool
 		diff.wordRegex
+		diff.algorithm
 		difftool.
 		difftool.prompt
 		fetch.recurseSubmodules
diff.c +23 -0
index 732d4c2..ddae5c4 100644
@@ -36,6 +36,7 @@ static int diff_no_prefix;
 static int diff_stat_graph_width;
 static int diff_dirstat_permille_default = 30;
 static struct diff_options default_diff_options;
+static long diff_algorithm = 0;
 
 static char diff_colors[][COLOR_MAXLEN] = {
 	GIT_COLOR_RESET,
@@ -143,6 +144,20 @@ static int git_config_rename(const char *var, const char *value)
 	return git_config_bool(var,value) ? DIFF_DETECT_RENAME : 0;
 }
 
+static long parse_algorithm_value(const char *value)
+{
+	if (!value || !strcasecmp(value, "myers"))
+		return 0;
+	else if (!strcasecmp(value, "minimal"))
+		return XDF_NEED_MINIMAL;
+	else if (!strcasecmp(value, "patience"))
+		return XDF_PATIENCE_DIFF;
+	else if (!strcasecmp(value, "histogram"))
+		return XDF_HISTOGRAM_DIFF;
+	else
+		return -1;
+}
+
 /*
  * These are to give UI layer defaults.
  * The core-level commands such as git-diff-files should
@@ -196,6 +211,13 @@ int git_diff_ui_config(const char *var, const char *value, void *cb)
 		return 0;
 	}
 
+	if (!strcmp(var, "diff.algorithm")) {
+		diff_algorithm = parse_algorithm_value(value);
+		if (diff_algorithm < 0)
+			return -1;
+		return 0;
+	}
+
 	if (git_color_config(var, value, cb) < 0)
 		return -1;
 
@@ -3213,6 +3235,7 @@ void diff_setup(struct diff_options *options)
 	options->add_remove = diff_addremove;
 	options->use_color = diff_use_color_default;
 	options->detect_rename = diff_detect_rename_default;
+	options->xdl_opts |= diff_algorithm;
 
 	if (diff_no_prefix) {
 		options->a_prefix = options->b_prefix = "";
Signature · 1 line
1.8.0.2
#3 lore raw

Re: [PATCH 2/3] config: Introduce diff.algorithm variable

Quoted 31 lines · Michal Privoznik

Some users or projects prefer different algorithms over others, e.g. patience over myers or similar. However, specifying appropriate argument every time diff is to be used is impractical. Moreover, creating an alias doesn't play nicely with other tools based on diff (git-show for instance). Hence, a configuration variable which is able to set specific algorithm is needed. For now, these four values are
accepted: 'myers' (which has the same effect as not setting the config variable at all), 'minimal', 'patience' and 'histogram'.

---
 Documentation/diff-config.txt          | 17 +++++++++++++++++
 contrib/completion/git-completion.bash |  1 +
 diff.c                                 | 23 +++++++++++++++++++++++
 3 files changed, 41 insertions(+)
Documentation/diff-config.txt +7 -0
index 4314ad0..be31276 100644
@@ -155,3 +155,20 @@ diff.tool::
 	"kompare".  Any other value is treated as a custom diff tool,
 	and there must be a corresponding `difftool.<tool>.cmd`
 	option.
+
+diff.algorithm::
+	Choose a diff algorithm.  The variants are as follows:
++
+--
+`myers`;;
+	The basic greedy diff algorithm.

Documentation/diff-config.txt diff.tool:: · line 174

Quoted 10 lines
Documentation/diff-config.txt +10 -0
+`minimal`;;
+	Spend extra time to make sure the smallest possible diff is
+	produced.
+`patience`;;
+	Use "patience diff" algorithm when generating patches.
+`histogram`;;
+	This algorithm extends the patience algorithm to "support
+	low-occurrence common elements".
+--
++

Sounds sensible.

Quoted 17 lines
contrib/completion/git-completion.bash +1 -0
index 383518c..33e25dc 100644
@@ -1839,6 +1839,7 @@ _git_config ()
 		diff.suppressBlankEmpty
 		diff.tool
 		diff.wordRegex
+		diff.algorithm
 		difftool.
 		difftool.prompt
 		fetch.recurseSubmodules
diff.c +0 -0
index 732d4c2..ddae5c4 100644

diff.c static int diff_no_prefix; · line 39

Quoted 4 lines
diff.c +1 -0
@@ -36,6 +36,7 @@ static int diff_no_prefix;
 static int diff_stat_graph_width;
 static int diff_dirstat_permille_default = 30;
 static struct diff_options default_diff_options;
+static long diff_algorithm = 0;

Please do not initialize a static explicitly to a zero and instead let BSS do its thing.

Quoted 45 lines
diff.c +22 -0
 static char diff_colors[][COLOR_MAXLEN] = {
 	GIT_COLOR_RESET,
@@ -143,6 +144,20 @@ static int git_config_rename(const char *var, const char *value)
 	return git_config_bool(var,value) ? DIFF_DETECT_RENAME : 0;
 }
 
+static long parse_algorithm_value(const char *value)
+{
+	if (!value || !strcasecmp(value, "myers"))
+		return 0;
+	else if (!strcasecmp(value, "minimal"))
+		return XDF_NEED_MINIMAL;
+	else if (!strcasecmp(value, "patience"))
+		return XDF_PATIENCE_DIFF;
+	else if (!strcasecmp(value, "histogram"))
+		return XDF_HISTOGRAM_DIFF;
+	else
+		return -1;
+}
+
 /*
  * These are to give UI layer defaults.
  * The core-level commands such as git-diff-files should
@@ -196,6 +211,13 @@ int git_diff_ui_config(const char *var, const char *value, void *cb)
 		return 0;
 	}
 
+	if (!strcmp(var, "diff.algorithm")) {
+		diff_algorithm = parse_algorithm_value(value);
+		if (diff_algorithm < 0)
+			return -1;
+		return 0;
+	}
+
 	if (git_color_config(var, value, cb) < 0)
 		return -1;
 
@@ -3213,6 +3235,7 @@ void diff_setup(struct diff_options *options)
 	options->add_remove = diff_addremove;
 	options->use_color = diff_use_color_default;
 	options->detect_rename = diff_detect_rename_default;
+	options->xdl_opts |= diff_algorithm;
 
 	if (diff_no_prefix) {
 		options->a_prefix = options->b_prefix = "";
#4 lore raw

PATCH 3/3 diff: Introduce --diff-algorithm command line option

In reply to Michal Privoznik

Since command line options have higher priority than config file variables and taking previous commit into account, we need a way how to specify myers algorithm on command line. However, inventing --myers is not the right answer. We need far more general option, and that is --diff-algorithm. The older options (--minimal, --patience and --histogram) are kept for backward compatibility.

---
 Documentation/diff-options.txt         | 22 ++++++++++++++++++++++
 contrib/completion/git-completion.bash | 11 +++++++++++
 diff.c                                 | 12 +++++++++++-
 diff.h                                 |  2 ++
 merge-recursive.c                      |  6 ++++++
 5 files changed, 52 insertions(+), 1 deletion(-)
Documentation/diff-options.txt +22 -0
index 39f2c50..4091f52 100644
@@ -45,6 +45,9 @@ ifndef::git-format-patch[]
 	Synonym for `-p --raw`.
 endif::git-format-patch[]
 
+The next three options are kept for compatibility reason. You should use the
+`--diff-algorithm` option instead.
+
 --minimal::
 	Spend extra time to make sure the smallest possible
 	diff is produced.
@@ -55,6 +58,25 @@ endif::git-format-patch[]
 --histogram::
 	Generate a diff using the "histogram diff" algorithm.
 
+--diff-algorithm={patience|minimal|histogram|myers}::
+	Choose a diff algorithm. The variants are as follows:
++
+--
+`myers`;;
+	The basic greedy diff algorithm.
+`minimal`;;
+	Spend extra time to make sure the smallest possible diff is
+	produced.
+`patience`;;
+	Use "patience diff" algorithm when generating patches.
+`histogram`;;
+	This algorithm extends the patience algorithm to "support
+	low-occurrence common elements".
+--
++
+You should prefer this option over the `--minimal`, `--patience` and
+`--histogram` which are kept just for backwards compatibility.
+
 --stat[=<width>[,<name-width>[,<count>]]]::
 	Generate a diffstat. By default, as much space as necessary
 	will be used for the filename part, and the rest for the graph
contrib/completion/git-completion.bash +11 -0
index 33e25dc..d592cf9 100644
@@ -1021,6 +1021,8 @@ _git_describe ()
 	__gitcomp_nl "$(__git_refs)"
 }
 
+__git_diff_algorithms="myers minimal patience histogram"
+
 __git_diff_common_options="--stat --numstat --shortstat --summary
 			--patch-with-stat --name-only --name-status --color
 			--no-color --color-words --no-renames --check
@@ -1035,6 +1037,7 @@ __git_diff_common_options="--stat --numstat --shortstat --summary
 			--raw
 			--dirstat --dirstat= --dirstat-by-file
 			--dirstat-by-file= --cumulative
+			--diff-algorithm=
 "
 
 _git_diff ()
@@ -1042,6 +1045,10 @@ _git_diff ()
 	__git_has_doubledash && return
 
 	case "$cur" in
+	--diff-algorithm=*)
+		__gitcomp "$__git_diff_algorithms" "" "${cur##--diff-algorithm=}"
+		return
+		;;
 	--*)
 		__gitcomp "--cached --staged --pickaxe-all --pickaxe-regex
 			--base --ours --theirs --no-index
@@ -2114,6 +2121,10 @@ _git_show ()
 			" "" "${cur#*=}"
 		return
 		;;
+	--diff-algorithm=*)
+		__gitcomp "$__git_diff_algorithms" "" "${cur##--diff-algorithm=}"
+		return
+		;;
 	--*)
 		__gitcomp "--pretty= --format= --abbrev-commit --oneline
 			$__git_diff_common_options
diff.c +11 -1
index ddae5c4..6418076 100644
@@ -144,7 +144,7 @@ static int git_config_rename(const char *var, const char *value)
 	return git_config_bool(var,value) ? DIFF_DETECT_RENAME : 0;
 }
 
-static long parse_algorithm_value(const char *value)
+long parse_algorithm_value(const char *value)
 {
 	if (!value || !strcasecmp(value, "myers"))
 		return 0;
@@ -3633,6 +3633,16 @@ int diff_opt_parse(struct diff_options *options, const char **av, int ac)
 		options->xdl_opts = DIFF_WITH_ALG(options, PATIENCE_DIFF);
 	else if (!strcmp(arg, "--histogram"))
 		options->xdl_opts = DIFF_WITH_ALG(options, HISTOGRAM_DIFF);
+	else if (!prefixcmp(arg, "--diff-algorithm=")) {
+		long value = parse_algorithm_value(arg+17);
+		if (value < 0)
+			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;
+	}
 
 	/* flags options */
 	else if (!strcmp(arg, "--binary")) {
diff.h +2 -0
index a47bae4..54c2590 100644
@@ -333,6 +333,8 @@ extern struct userdiff_driver *get_textconv(struct diff_filespec *one);
 
 extern int parse_rename_score(const char **cp_p);
 
+extern long parse_algorithm_value(const char *value);
+
 extern int print_stat_summary(FILE *fp, int files,
 			      int insertions, int deletions);
 extern void setup_diff_pager(struct diff_options *);
merge-recursive.c +6 -0
index d882060..53d8feb 100644
@@ -2068,6 +2068,12 @@ int parse_merge_opt(struct merge_options *o, const char *s)
 		o->xdl_opts = DIFF_WITH_ALG(o, PATIENCE_DIFF);
 	else if (!strcmp(s, "histogram"))
 		o->xdl_opts = DIFF_WITH_ALG(o, HISTOGRAM_DIFF);
+	else if (!strcmp(s, "diff-algorithm=")) {
+		long value = parse_algorithm_value(s+15);
+		if (value < 0)
+			return -1;
+		o->xdl_opts |= value;
+	}
 	else if (!strcmp(s, "ignore-space-change"))
 		o->xdl_opts |= XDF_IGNORE_WHITESPACE_CHANGE;
 	else if (!strcmp(s, "ignore-all-space"))
Signature · 1 line
1.8.0.2
#5 lore raw

Re: [PATCH 3/3] diff: Introduce --diff-algorithm command line option

Quoted 3 lines · Michal Privoznik

Since command line options have higher priority than config file variables and taking previous commit into account, we need a way how to specify myers algorithm on command line.

Yes. We cannot stop at [2/3] without this patch.

Quoted 3 lines

However,
inventing --myers is not the right answer. We need far more general option, and that is --diff-algorithm.

Yes, --diff-algorithm=default would let people defeat a configured algo without knowing how exactly to spell myers.

Quoted 3 lines

The older options
(--minimal, --patience and --histogram) are kept for backward compatibility.

That is phrasing it too strongly to be acceptable.

People who do not care any configuration can keep using --histogram without having to retrain their fingers to type a much longer form you introduced (i.e. --diff-algorithm=histogram). It is and will always be just as valid a way to ask for --histogram as the new longhand is.

Quoted 14 lines
---
 Documentation/diff-options.txt         | 22 ++++++++++++++++++++++
 contrib/completion/git-completion.bash | 11 +++++++++++
 diff.c                                 | 12 +++++++++++-
 diff.h                                 |  2 ++
 merge-recursive.c                      |  6 ++++++
 5 files changed, 52 insertions(+), 1 deletion(-)
Documentation/diff-options.txt +0 -0
index 39f2c50..4091f52 100644

Documentation/diff-options.txt ifndef::git-format-patch[] · line 50

Quoted 6 lines
Documentation/diff-options.txt +3 -0
@@ -45,6 +45,9 @@ ifndef::git-format-patch[]
 	Synonym for `-p --raw`.
 endif::git-format-patch[]
 
+The next three options are kept for compatibility reason. You should use the
+`--diff-algorithm` option instead.
+

Drop this.

Quoted 12 lines
Documentation/diff-options.txt +8 -0
@@ -55,6 +58,25 @@ endif::git-format-patch[]
 --histogram::
 	Generate a diff using the "histogram diff" algorithm.
 
+--diff-algorithm={patience|minimal|histogram|myers}::
+	Choose a diff algorithm. The variants are as follows:
++
+--
+`myers`;;
+	The basic greedy diff algorithm.
+`minimal`;;
+	Spend extra time to make sure the smallest possible diff is

Documentation/diff-options.txt endif::git-format-patch[] · line 78

Quoted 10 lines
Documentation/diff-options.txt +10 -0
+	produced.
+`patience`;;
+	Use "patience diff" algorithm when generating patches.
+`histogram`;;
+	This algorithm extends the patience algorithm to "support
+	low-occurrence common elements".
+--
++
+You should prefer this option over the `--minimal`, `--patience` and
+`--histogram` which are kept just for backwards compatibility.

Drop the last one, and replace it with something like:

If you configured diff.algorithm to a non-default value and want to use the default one, you have to use this form and choose myers, i.e. --diff-algorithm=myers, as we do not have a short-and-sweet --myers option.

(but the above is a bit too verbose, so please shorten it appropriately).

Quoted 91 lines
contrib/completion/git-completion.bash +11 -0
index 33e25dc..d592cf9 100644
@@ -1021,6 +1021,8 @@ _git_describe ()
 	__gitcomp_nl "$(__git_refs)"
 }
 
+__git_diff_algorithms="myers minimal patience histogram"
+
 __git_diff_common_options="--stat --numstat --shortstat --summary
 			--patch-with-stat --name-only --name-status --color
 			--no-color --color-words --no-renames --check
@@ -1035,6 +1037,7 @@ __git_diff_common_options="--stat --numstat --shortstat --summary
 			--raw
 			--dirstat --dirstat= --dirstat-by-file
 			--dirstat-by-file= --cumulative
+			--diff-algorithm=
 "
 
 _git_diff ()
@@ -1042,6 +1045,10 @@ _git_diff ()
 	__git_has_doubledash && return
 
 	case "$cur" in
+	--diff-algorithm=*)
+		__gitcomp "$__git_diff_algorithms" "" "${cur##--diff-algorithm=}"
+		return
+		;;
 	--*)
 		__gitcomp "--cached --staged --pickaxe-all --pickaxe-regex
 			--base --ours --theirs --no-index
@@ -2114,6 +2121,10 @@ _git_show ()
 			" "" "${cur#*=}"
 		return
 		;;
+	--diff-algorithm=*)
+		__gitcomp "$__git_diff_algorithms" "" "${cur##--diff-algorithm=}"
+		return
+		;;
 	--*)
 		__gitcomp "--pretty= --format= --abbrev-commit --oneline
 			$__git_diff_common_options
diff.c +11 -1
index ddae5c4..6418076 100644
@@ -144,7 +144,7 @@ static int git_config_rename(const char *var, const char *value)
 	return git_config_bool(var,value) ? DIFF_DETECT_RENAME : 0;
 }
 
-static long parse_algorithm_value(const char *value)
+long parse_algorithm_value(const char *value)
 {
 	if (!value || !strcasecmp(value, "myers"))
 		return 0;
@@ -3633,6 +3633,16 @@ int diff_opt_parse(struct diff_options *options, const char **av, int ac)
 		options->xdl_opts = DIFF_WITH_ALG(options, PATIENCE_DIFF);
 	else if (!strcmp(arg, "--histogram"))
 		options->xdl_opts = DIFF_WITH_ALG(options, HISTOGRAM_DIFF);
+	else if (!prefixcmp(arg, "--diff-algorithm=")) {
+		long value = parse_algorithm_value(arg+17);
+		if (value < 0)
+			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;
+	}
 
 	/* flags options */
 	else if (!strcmp(arg, "--binary")) {
diff.h +2 -0
index a47bae4..54c2590 100644
@@ -333,6 +333,8 @@ extern struct userdiff_driver *get_textconv(struct diff_filespec *one);
 
 extern int parse_rename_score(const char **cp_p);
 
+extern long parse_algorithm_value(const char *value);
+
 extern int print_stat_summary(FILE *fp, int files,
 			      int insertions, int deletions);
 extern void setup_diff_pager(struct diff_options *);
merge-recursive.c +0 -0
index d882060..53d8feb 100644

merge-recursive.c int parse_merge_opt(struct merge_options *o, const char *s) · line 2075

Quoted 8 lines
merge-recursive.c +5 -0
@@ -2068,6 +2068,12 @@ int parse_merge_opt(struct merge_options *o, const char *s)
 		o->xdl_opts = DIFF_WITH_ALG(o, PATIENCE_DIFF);
 	else if (!strcmp(s, "histogram"))
 		o->xdl_opts = DIFF_WITH_ALG(o, HISTOGRAM_DIFF);
+	else if (!strcmp(s, "diff-algorithm=")) {
+		long value = parse_algorithm_value(s+15);
+		if (value < 0)
+			return -1;
+		o->xdl_opts |= value;

Isn't this new hunk wrong? DIFF_WITH_ALG() removes the previously chosen algorithm choice before OR'ing the new one in, so that

	diff --histogram --patience

would not end up with a value PATIENCE|HISTOGRAM OR'ed together in the algo field.

#6 lore raw

Re: [PATCH 3/3] diff: Introduce --diff-algorithm command line option

Quoted 19 lines · Junio C Hamano

Michal Privoznik <[email protected]> writes:
...

merge-recursive.c int parse_merge_opt(struct merge_options *o, const char *s) · line 2075

Quoted 13 lines
merge-recursive.c +5 -0
index d882060..53d8feb 100644
@@ -2068,6 +2068,12 @@ int parse_merge_opt(struct merge_options *o, const char *s)
 		o->xdl_opts = DIFF_WITH_ALG(o, PATIENCE_DIFF);
 	else if (!strcmp(s, "histogram"))
 		o->xdl_opts = DIFF_WITH_ALG(o, HISTOGRAM_DIFF);
+	else if (!strcmp(s, "diff-algorithm=")) {
+		long value = parse_algorithm_value(s+15);
+		if (value < 0)
+			return -1;
+		o->xdl_opts |= value;

Isn't this new hunk wrong? DIFF_WITH_ALG() removes the previously chosen algorithm choice before OR'ing the new one in, so that

Quoted 4 lines
	diff --histogram --patience

would not end up with a value PATIENCE|HISTOGRAM OR'ed together in the algo field.

I misspoke; this is not "diff", but "merge-recursive". The issue may be the same here, though.