[PATCH v3 0/3] Rework git-diff algorithm selection

[PATCH v3 0/3] Rework git-diff algorithm selection

[Michal Privoznik]

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.

diff to v1:
-Junio's suggestions worked in

diff to v2:
-yet more Junio's suggestions included

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          | 18 ++++++++++++++++++
 Documentation/diff-options.txt         | 21 +++++++++++++++++++++
 contrib/completion/git-completion.bash | 14 +++++++++++++-
 diff.c                                 | 34 ++++++++++++++++++++++++++++++++++
 diff.h                                 |  2 ++
 merge-recursive.c                      |  9 +++++++++
 6 files changed, 97 insertions(+), 1 deletion(-)

-- 
1.8.0.2

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

[Michal Privoznik]

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

Signed-off-by: Michal Privoznik <mprivozn@redhat.com>
---
 contrib/completion/git-completion.bash | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/contrib/completion/git-completion.bash b/contrib/completion/git-completion.bash
index a4c48e1..383518c 100644
--- a/contrib/completion/git-completion.bash
+++ b/contrib/completion/git-completion.bash
@@ -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
-- 
1.8.0.2

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

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

Signed-off-by: Michal Privoznik <mprivozn@redhat.com>
---
 Documentation/diff-config.txt          | 18 ++++++++++++++++++
 contrib/completion/git-completion.bash |  1 +
 diff.c                                 | 24 ++++++++++++++++++++++++
 3 files changed, 43 insertions(+)

diff --git a/Documentation/diff-config.txt b/Documentation/diff-config.txt
index 4314ad0..3a62ace 100644
--- a/Documentation/diff-config.txt
+++ b/Documentation/diff-config.txt
@@ -155,3 +155,21 @@ 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:
++
+--
+`default`, `myers`;;
+	The basic greedy diff algorithm. Currently, this happens to be
+	the default algorithm as well.
+`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".
+--
++
diff --git a/contrib/completion/git-completion.bash b/contrib/completion/git-completion.bash
index 383518c..33e25dc 100644
--- a/contrib/completion/git-completion.bash
+++ b/contrib/completion/git-completion.bash
@@ -1839,6 +1839,7 @@ _git_config ()
 		diff.suppressBlankEmpty
 		diff.tool
 		diff.wordRegex
+		diff.algorithm
 		difftool.
 		difftool.prompt
 		fetch.recurseSubmodules
diff --git a/diff.c b/diff.c
index 348f71b..7d6cc4c 100644
--- a/diff.c
+++ b/diff.c
@@ -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;
 
 static char diff_colors[][COLOR_MAXLEN] = {
 	GIT_COLOR_RESET,
@@ -143,6 +144,21 @@ 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)
+		return -1;
+	else if (!strcasecmp(value, "myers") || !strcasecmp(value, "default"))
+		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;
+	return -1;
+}
+
 /*
  * These are to give UI layer defaults.
  * The core-level commands such as git-diff-files should
@@ -196,6 +212,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 +3236,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 = "";
-- 
1.8.0.2

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

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

Signed-off-by: Michal Privoznik <mprivozn@redhat.com>
---
 Documentation/diff-options.txt         | 21 +++++++++++++++++++++
 contrib/completion/git-completion.bash | 11 +++++++++++
 diff.c                                 | 12 +++++++++++-
 diff.h                                 |  2 ++
 merge-recursive.c                      |  9 +++++++++
 5 files changed, 54 insertions(+), 1 deletion(-)

diff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt
index 39f2c50..6f11c34 100644
--- a/Documentation/diff-options.txt
+++ b/Documentation/diff-options.txt
@@ -55,6 +55,27 @@ 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:
++
+--
+`default`, `myers`;;
+	The basic greedy diff algorithm. Currently, this happens to be
+	the default algorithm as well.
+`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".
+--
++
+For instance, if you configured diff.algorithm variable to a
+non-default value and want to use the default one, then you
+have to use `--diff-algorithm=default` option.
+
 --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
diff --git a/contrib/completion/git-completion.bash b/contrib/completion/git-completion.bash
index 33e25dc..d592cf9 100644
--- a/contrib/completion/git-completion.bash
+++ b/contrib/completion/git-completion.bash
@@ -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 --git a/diff.c b/diff.c
index 7d6cc4c..5fa40e9 100644
--- a/diff.c
+++ b/diff.c
@@ -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)
 		return -1;
@@ -3634,6 +3634,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 --git a/diff.h b/diff.h
index a47bae4..54c2590 100644
--- a/diff.h
+++ b/diff.h
@@ -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 *);
diff --git a/merge-recursive.c b/merge-recursive.c
index 33ba5dc..ea9dbd3 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -2068,6 +2068,15 @@ 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;
+		/* clear out previous settings */
+		DIFF_XDL_CLR(o, NEED_MINIMAL);
+		o->xdl_opts &= ~XDF_DIFF_ALGORITHM_MASK;
+		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"))
-- 
1.8.0.2

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

[Junio C Hamano]

Will replace the one in 'pu' with this round.  Looking good.

Thanks.

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

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> Will replace the one in 'pu' with this round.  Looking good.
>
> Thanks.

By the way, wouldn't we want some tests to protect this feature from
future breakages?