patchblame: make diff algorithm configurable

From: Antonin Delpeuch <antonin@delpeuch.eu>

The diff algorithm used in 'git-blame(1)' can be configured using the `--diff-algorithm` option or the `diff.algorithm` config variable. Myers diff remains the default.

Signed-off-by: Antonin Delpeuch <antonin@delpeuch.eu>
---
    blame: make diff algorithm configurable
    
    There has been long-standing interest in changing the default diff
    algorithm to "histogram", and Git 3.0 was floated as a possible occasion
    for that: https://lore.kernel.org/git/xmqqed873vgn.fsf@gitster.g/
    
    As a preparation, it is worth making sure that the diff algorithm is
    configurable where useful. It can have significant impact on the output
    of the git-blame command, so I propose to make it configurable there
    too. I have followed the convention of other commands (such as git-diff)
    to introduce a --diff-algorithm option.
    
    I understand that this command is a user-facing (porcelain) one, so I
    think making it honor the diff.algorithm UI config variable is also
    appropriate. The git-blame command has a machine-readable format that
    can be enabled with --porcelain (which should be called --plumbing if
    you ask me) so I wonder if the diff.algorithm variable should still be
    honored in this case, as there could be the desire to keep it
    independent from UI config variables (similarly to git-merge-file, a
    plumbing command which doesn't honor diff.algorithm).
    
    If the general idea of this patch is judged worthwhile, I would be happy
    to add tests to demonstrate the impact of the diff algorithm on blame
    output.

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

 Documentation/git-blame.adoc | 21 ++++++++++++++++++++
 builtin/blame.c              | 38 +++++++++++++++++++++++++++++++++++-
 2 files changed, 58 insertions(+), 1 deletion(-)

"Antonin Delpeuch via GitGitGadget" <gitgitgadget@gmail.com> writes:

The usual way to compose a log message of this project is to

 - Give an observation on how the current system works in the
   present tense (so no need to say "Currently X is Y", or
   "Previously X was Y" to describe the state before your change;
   just "X is Y" is enough), and discuss what you perceive as a
   problem in it.

 - Propose a solution (optional---often, problem description
   trivially leads to an obvious solution in reader's minds).

 - Give commands to somebody editing the codebase to "make it so",
   instead of saying "This commit does X".

in this order. This hasn't changed since your first commit to this project a few years ago.

And when read with that expectation, I was surprised that "blame" already paid attention to the command line option and configuration variable, as that paragraph was supposed to explain what happens without the patch being proposed. It was a pleasant surprise that turned out to be untrue X-<.

All of the above are good materials to be in the proposed log message, not under the three-dash line, to explain the motivation behind the change.

Good consideration and something we should make sure we do the right thing for our users. Personally, I would not be concerned---the only folks that possibly affected are those who save old blame output and wants a fresh "git blame" run they make today would produce bit-for-bit identical output, but if they use newer versions of Git with improved xdiff implementation, they cannot expect that with or without the configuration knob _anyway_. This is just my personal opinion. Others may differ.

Do not ever say this here.

I've seen from time to time people ask "I am thinking of doing this; will a patch be accepted? If so, I'll work on it." before showing any work, and my response always has been:

 (1) We don't know how useful and interesting your contribution would
     be for our audience, until we see it; and

 (2) If you truly believe in your work (find it useful, find writing
     it fun, etc.), that would be incentive enough for you to work
     on it, whether or not the result will land in my tree.  You
     should instead aim for something so brilliant that we would
     come to you begging for your permission to include it in our
     project.

Is this copied from somewhere else, or did you come up with the above text yourself? If the former, perhaps it is a good idea to reduce the duplicattion. Use of "include::line-range-format.adoc[]" in Documentation/blame-options.adoc (which in turn is included by Documentation/git-blame.adoc) may serve as a good model to include the same text in multiple places (the "line-range" syntax thing is included directly or indirectly and its text appears in a handful of places as the result). Copy the original text out into a new file to be included (say, "diff-algorithm-option.adoc"), replace the original text with "include::diff-algorithm-option.adoc[]", and then add another "include::diff-algorithm-option.adoc[]" here in git-blame documentation instead of duplicating the text like the above hunk does.

OK, this message is copied from git_diff_ui_config(), which is where "git log" and 4 commands in the "git diff" family gets their error message when "git -c diff.algorithm=bogus <cmd>" is run. It is a bit suboptimal, but users would know how to read the documentation (even though in practice they never do), so let's say this is OK, at least for now.

    For future reference (note: this is a #leftoverbits comment that is
    left here for the benefit of those who scan the list archive for
    ideas on what to do when they are absolutely bored without anything
    interesting to do, not meant as a suggestion to do anything of this
    sort before this patch lands), in addition to "git log" and 4
    commands in the "git diff" family,

     - merge-ort.c has the same message.
     - builtin/merge-file.c gives a bit nicer message but that is a bit
       of maintenance burden.
     - curiously "git log" and four commands in the "git diff" family
       give a much nicer message when a --diff-algorithm=bogus is given
       from the command line, but not in the configuration file.

    we may want to consolidate the error message into one place (a
    constant or "extern const char *diff_algorithm_error_message",
    or something else that is i18n friendly) and use it from all these
    places I just identified.

This one relies on git_diff_heuristic_config() to give message when it returns negative, so we do not have to do anything. OK.

    Contination of the above #leftoverbits may be to see if
    parse_algorithm_value() is a good place to consolidate the error
    message, after auditing all its callers (if such a change turns
    out to be a good idea, they need to lose their own messages).

You inherited the same "config error gets a message that requires users to consult the manual, option error gets something a bit more useful but is a maintenance burden" trait from "git diff" and family here. Let's say this is OK, too, at least for now.

We do not do // comments around here, outside borrowed code.

WHY?

OK.

On 20/10/2025 18:05, Junio C Hamano wrote:

I am surprised by your reaction here, both by its substance and form.

My understanding is that gathering feedback on a proposal before carrying out the implementation work in its entirety is widely accepted as a good practice for contributions to open source projects. For instance, the following guide encourages to do so (in GitHub terms, by proposing an improvement as an issue first, and by opening a draft pull request if necessary):

https://opensource.guide/how-to-contribute/

While this is phrased in the context of GitHub, I think the general principle behind it is healthy. In projects I maintain, I feel bad for contributors who submit contributions that clearly required a significant effort, but that I can't accept for certain reasons. I wish they had got in touch ahead of investing all this work, because I care about their time.

In fact, I already did so for an earlier contribution to this very project, and on that occasion you did not seem to take offense at the fact that my proposal was done without an accompanying patch:

https://lore.kernel.org/git/8bb5e41e-4db9-4527-8492-3aca6a0f40bf@delpeuch.eu/

Has your position changed since? Or did I benefit from more of your kindness back then as a new contributor?

Your argument about my work being worthy on its own even if it's not integrated to your tree is an interesting one, but let me expand on my motivation for this patch. This change is not something I personally need, nor something that is particularly fun to write. I am working on this with the hope that it will eventually make it possible to switch the default to the histogram algorithm, for the benefit of many git users. I see no point for this patch if it is not integrated in your tree. It is a gift to you and to the git community: if the gift is to be declined, I'd rather not spend time crafting it.

Concerning the form, I feel obliged to let you know that from my cultural standpoint, your reply reads rather aggressive. Specifically, the sentence "Do not ever say this here." reads menacing to me, and the use of all caps later on in your reply reads aggressive to me. I'm doing my best to assume that it is not be the attitude you wanted to convey and hope that you can receive this feedback gratefully.

In an attempt to conform to the coding style of this project, I ran `make style`, which generated this change. Given that it is on a line I hadn't touched, I pondered on whether to include it in my patch or not. In the past, I had submitted a patch which fixed a formatting issue in the documentation in passing, together with content changes further down, and you had been supportive of this:

https://lore.kernel.org/git/xmqq1qaeqtw7.fsf@gitster.g/

So I decided to include it this time as well. I am happy to remove it if you prefer not to have it.

I thank you for the rest of your comments and will take them into account for a new version of this patch, pending the discussion above.

Best wishes,

Antonin

Antonin Delpeuch <antonin@delpeuch.eu> writes:

Yeah, after sending it out, I realized that the canned response above was not fitting to this exact instance. I overreacted primarily because what I saw everything before that part was indication of a great new contributor, which made my dissapointment to see the dreaded "I will do this if this is accepted" even worse.

Your "this one lacks tests" is a bit different from what we sometimes see on this list that I react with the above canned response, which is "I want to do this great thing. If you promise you will accept this change, I'll work on it" without showing any detailed design or code. It is more like "I know we need test but I have shown the main part of the change. Am I going in the right direction?"

You certainly didn't deserve the above response.  Sorry about that.

Hi Antonin

On 20/10/2025 15:56, Antonin Delpeuch via GitGitGadget wrote:

I think this sounds like a reasonable thing to do, although it is technically a breaking change.

I think this should be

	xdl_opts &= ~(XDF_DIFF_ALGORITHM_MASK | XDF_NEED_MINIMAL);

as you have below for the option parsing.

Style - oneline comments should look like

	/* comment */

"git blame" also has a "--minimal" option which now needs to clear the diff algorithm when it sets the minimal flag.

Thanks

Phillip

From: Antonin Delpeuch <antonin@delpeuch.eu>

The diff algorithm used in 'git-blame(1)' is set to 'myers', without the possibility to change it aside from the `--minimal` option.

There has been long-standing interest in changing the default diff algorithm to "histogram", and Git 3.0 was floated as a possible occasion for taking some steps towards that:

https://lore.kernel.org/git/xmqqed873vgn.fsf@gitster.g/

As a preparation for this move, it is worth making sure that the diff algorithm is configurable where useful.

Make it configurable in the `git-blame(1)` command by introducing the `--diff-algorithm` option and make honor the `diff.algorithm` config variable. Keep Myers diff as the default.

Signed-off-by: Antonin Delpeuch <antonin@delpeuch.eu>
---
    blame: make diff algorithm configurable
    
    Changes since v1:
    
     * add tests
     * ignore --diff-algorithm when it is provided before --minimal
     * improve patch description
     * remove duplication of documentation sections
     * style improvements

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

Range-diff vs v1:

 1:  32b59d0204 ! 1:  107f51620b blame: make diff algorithm configurable
     @@ Metadata
       ## Commit message ##
          blame: make diff algorithm configurable
      
     -    The diff algorithm used in 'git-blame(1)' can be configured using the
     -    `--diff-algorithm` option or the `diff.algorithm` config variable.
     -    Myers diff remains the default.
     +    The diff algorithm used in 'git-blame(1)' is set to 'myers',
     +    without the possibility to change it aside from the `--minimal` option.
     +
     +    There has been long-standing interest in changing the default diff
     +    algorithm to "histogram", and Git 3.0 was floated as a possible occasion
     +    for taking some steps towards that:
     +
     +    https://lore.kernel.org/git/xmqqed873vgn.fsf@gitster.g/
     +
     +    As a preparation for this move, it is worth making sure that the diff
     +    algorithm is configurable where useful.
     +
     +    Make it configurable in the `git-blame(1)` command by introducing the
     +    `--diff-algorithm` option and make honor the `diff.algorithm` config
     +    variable. Keep Myers diff as the default.
      
          Signed-off-by: Antonin Delpeuch <antonin@delpeuch.eu>
      
     - ## Documentation/git-blame.adoc ##
     -@@ Documentation/git-blame.adoc: include::blame-options.adoc[]
     - 	Ignore whitespace when comparing the parent's version and
     - 	the child's to find where the lines came from.
     - 
     + ## Documentation/diff-algorithm-option.adoc (new) ##
     +@@
      +`--diff-algorithm=(patience|minimal|histogram|myers)`::
      +	Choose a diff algorithm. The variants are as follows:
      ++
     @@ Documentation/git-blame.adoc: include::blame-options.adoc[]
      +For instance, if you configured the `diff.algorithm` variable to a
      +non-default value and want to use the default one, then you
      +have to use `--diff-algorithm=default` option.
     +
     + ## Documentation/diff-options.adoc ##
     +@@ Documentation/diff-options.adoc: and starts with _<text>_, this algorithm attempts to prevent it from
     + appearing as a deletion or addition in the output. It uses the "patience
     + diff" algorithm internally.
     + 
     +-`--diff-algorithm=(patience|minimal|histogram|myers)`::
     +-	Choose a diff algorithm. The variants are as follows:
     +-+
     +---
     +-   `default`;;
     +-   `myers`;;
     +-	The basic greedy diff algorithm. Currently, this is the default.
     +-   `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 the `diff.algorithm` variable to a
     +-non-default value and want to use the default one, then you
     +-have to use `--diff-algorithm=default` option.
     ++include::diff-algorithm-option.adoc[]
     + 
     + `--stat[=<width>[,<name-width>[,<count>]]]`::
     + 	Generate a diffstat. By default, as much space as necessary
     +
     + ## Documentation/git-blame.adoc ##
     +@@ Documentation/git-blame.adoc: include::blame-options.adoc[]
     + 	Ignore whitespace when comparing the parent's version and
     + 	the child's to find where the lines came from.
     + 
     ++include::diff-algorithm-option.adoc[]
      +
       --abbrev=<n>::
       	Instead of using the default 7+1 hexadecimal digits as the
     @@ builtin/blame.c: static int blame_move_callback(const struct option *option, con
       	return 0;
       }
       
     ++static int blame_diff_algorithm_minimal(const struct option *option,
     ++					const char *arg, int unset)
     ++{
     ++	int *opt = option->value;
     ++
     ++	BUG_ON_OPT_NEG(unset);
     ++	BUG_ON_OPT_ARG(arg);
     ++
     ++	*opt &= ~XDF_DIFF_ALGORITHM_MASK;
     ++	*opt |= XDF_NEED_MINIMAL;
     ++
     ++	return 0;
     ++}
     ++
      +static int blame_diff_algorithm_callback(const struct option *option,
      +					 const char *arg, int unset)
      +{
     @@ builtin/blame.c: static int blame_move_callback(const struct option *option, con
      +		return error(_("option diff-algorithm accepts \"myers\", "
      +			       "\"minimal\", \"patience\" and \"histogram\""));
      +
     -+	// ignore any previous --minimal setting, following git-diff's behavior
     -+	*opt &= ~XDF_NEED_MINIMAL;
     -+	*opt &= ~XDF_DIFF_ALGORITHM_MASK;
     ++	*opt &= ~(XDF_NEED_MINIMAL | XDF_DIFF_ALGORITHM_MASK);
      +	*opt |= value;
      +
      +	return 0;
     @@ builtin/blame.c: static int blame_move_callback(const struct option *option, con
       {
       	struct object_id oid;
      @@ builtin/blame.c: int cmd_blame(int argc,
     - 		OPT_BIT('f', "show-name", &output_option, N_("show original filename (Default: auto)"), OUTPUT_SHOW_NAME),
     - 		OPT_BIT('n', "show-number", &output_option, N_("show original linenumber (Default: off)"), OUTPUT_SHOW_NUMBER),
     - 		OPT_BIT('p', "porcelain", &output_option, N_("show in a format designed for machine consumption"), OUTPUT_PORCELAIN),
     --		OPT_BIT(0, "line-porcelain", &output_option, N_("show porcelain format with per-line commit information"), OUTPUT_PORCELAIN|OUTPUT_LINE_PORCELAIN),
     -+		OPT_BIT(0, "line-porcelain", &output_option, N_("show porcelain format with per-line commit information"), OUTPUT_PORCELAIN | OUTPUT_LINE_PORCELAIN),
     - 		OPT_BIT('c', NULL, &output_option, N_("use the same output mode as git-annotate (Default: off)"), OUTPUT_ANNOTATE_COMPAT),
     - 		OPT_BIT('t', NULL, &output_option, N_("show raw timestamp (Default: off)"), OUTPUT_RAW_TIMESTAMP),
     - 		OPT_BIT('l', NULL, &output_option, N_("show long commit SHA1 (Default: off)"), OUTPUT_LONG_OBJECT_NAME),
       		OPT_BIT('s', NULL, &output_option, N_("suppress author name and timestamp (Default: off)"), OUTPUT_NO_AUTHOR),
       		OPT_BIT('e', "show-email", &output_option, N_("show author email instead of name (Default: off)"), OUTPUT_SHOW_EMAIL),
       		OPT_BIT('w', NULL, &xdl_opts, N_("ignore whitespace differences"), XDF_IGNORE_WHITESPACE),
     @@ builtin/blame.c: int cmd_blame(int argc,
       		OPT_STRING_LIST(0, "ignore-rev", &ignore_rev_list, N_("rev"), N_("ignore <rev> when blaming")),
       		OPT_STRING_LIST(0, "ignore-revs-file", &ignore_revs_file_list, N_("file"), N_("ignore revisions from <file>")),
       		OPT_BIT(0, "color-lines", &output_option, N_("color redundant metadata from previous line differently"), OUTPUT_COLOR_LINE),
     + 		OPT_BIT(0, "color-by-age", &output_option, N_("color lines by age"), OUTPUT_SHOW_AGE_WITH_COLOR),
     ++		OPT_CALLBACK_F(0, "minimal", &xdl_opts, NULL,
     ++			       N_("spend extra cycles to find better match"),
     ++			       PARSE_OPT_NONEG | PARSE_OPT_NOARG,
     ++			       blame_diff_algorithm_minimal),
     + 		OPT_BIT(0, "minimal", &xdl_opts, N_("spend extra cycles to find better match"), XDF_NEED_MINIMAL),
     + 		OPT_STRING('S', NULL, &revs_file, N_("file"), N_("use revisions from <file> instead of calling git-rev-list")),
     + 		OPT_STRING(0, "contents", &contents_from, N_("file"), N_("use <file>'s contents as the final image")),
     +
     + ## t/meson.build ##
     +@@ t/meson.build: integration_tests = [
     +   't8012-blame-colors.sh',
     +   't8013-blame-ignore-revs.sh',
     +   't8014-blame-ignore-fuzzy.sh',
     ++  't8015-blame-diff-algorithm.sh',
     +   't8020-last-modified.sh',
     +   't9001-send-email.sh',
     +   't9002-column.sh',
     +
     + ## t/t8015-blame-diff-algorithm.sh (new) ##
     +@@
     ++#!/bin/sh
     ++
     ++test_description='git blame with specific diff algorithm'
     ++
     ++. ./test-lib.sh
     ++
     ++test_expect_success setup '
     ++	cat >file.c <<-\EOF &&
     ++	int f(int x, int y)
     ++	{
     ++		if (x == 0)
     ++		{
     ++			return y;
     ++		}
     ++		return x;
     ++	}
     ++
     ++	int g(size_t u)
     ++	{
     ++		while (u < 30)
     ++		{
     ++			u++;
     ++		}
     ++		return u;
     ++	}
     ++	EOF
     ++	test_write_lines x x x x >file.txt &&
     ++	git add file.c file.txt &&
     ++	GIT_AUTHOR_NAME=Initial git commit -m Initial &&
     ++
     ++	cat >file.c <<-\EOF &&
     ++	int g(size_t u)
     ++	{
     ++		while (u < 30)
     ++		{
     ++			u++;
     ++		}
     ++		return u;
     ++	}
     ++
     ++	int h(int x, int y, int z)
     ++	{
     ++		if (z == 0)
     ++		{
     ++			return x;
     ++		}
     ++		return y;
     ++	}
     ++	EOF
     ++	test_write_lines x x x A B C D x E F G >file.txt &&
     ++	git add file.c file.txt &&
     ++	GIT_AUTHOR_NAME=Second git commit -m Second
     ++'
     ++
     ++test_expect_success 'blame uses Myers diff algorithm by default for now' '
     ++	cat >expected <<-\EOF &&
     ++	Second
     ++	Initial
     ++	Second
     ++	Initial
     ++	Second
     ++	Initial
     ++	Second
     ++	Initial
     ++	Initial
     ++	Second
     ++	Initial
     ++	Second
     ++	Initial
     ++	Second
     ++	Initial
     ++	Second
     ++	Initial
     ++	EOF
     ++
     ++	# git blame file.c | grep --only-matching -e Initial -e Second > actual &&
     ++	# test_cmp expected actual
     ++	echo goo
     ++'
     ++
     ++test_expect_success 'blame honors --diff-algorithm option' '
     ++	cat >expected <<-\EOF &&
     ++	Initial
     ++	Initial
     ++	Initial
     ++	Initial
     ++	Initial
     ++	Initial
     ++	Initial
     ++	Initial
     ++	Second
     ++	Second
     ++	Second
     ++	Second
     ++	Second
     ++	Second
     ++	Second
     ++	Second
     ++	Second
     ++	EOF
     ++
     ++	git blame file.c --diff-algorithm=histogram | \
     ++		grep --only-matching -e Initial -e Second > actual &&
     ++	test_cmp expected actual
     ++'
     ++
     ++test_expect_success 'blame honors diff.algorithm config variable' '
     ++	cat >expected <<-\EOF &&
     ++	Initial
     ++	Initial
     ++	Initial
     ++	Initial
     ++	Initial
     ++	Initial
     ++	Initial
     ++	Initial
     ++	Second
     ++	Second
     ++	Second
     ++	Second
     ++	Second
     ++	Second
     ++	Second
     ++	Second
     ++	Second
     ++	EOF
     ++
     ++	git config diff.algorithm histogram &&
     ++	git blame file.c | \
     ++		grep --only-matching -e Initial -e Second > actual &&
     ++	test_cmp expected actual
     ++'
     ++
     ++test_expect_success 'blame honors --minimal option' '
     ++	cat >expected <<-\EOF &&
     ++	Initial
     ++	Initial
     ++	Initial
     ++	Second
     ++	Second
     ++	Second
     ++	Second
     ++	Initial
     ++	Second
     ++	Second
     ++	Second
     ++	EOF
     ++
     ++	git blame file.txt --minimal | \
     ++		grep --only-matching -e Initial -e Second > actual &&
     ++	test_cmp expected actual
     ++'
     ++
     ++test_done

 Documentation/diff-algorithm-option.adoc |  20 +++
 Documentation/diff-options.adoc          |  21 +---
 Documentation/git-blame.adoc             |   2 +
 builtin/blame.c                          |  52 ++++++++
 t/meson.build                            |   1 +
 t/t8015-blame-diff-algorithm.sh          | 154 +++++++++++++++++++++++
 6 files changed, 230 insertions(+), 20 deletions(-)
 create mode 100644 Documentation/diff-algorithm-option.adoc
 create mode 100755 t/t8015-blame-diff-algorithm.sh

"Antonin Delpeuch via GitGitGadget" <gitgitgadget@gmail.com> writes:

Hmph. It is very unfortunate that we had --minimal already. We should have done --diff-algorithm=<which> instead, but that is way too late.

Micronit. I think the reference to 3.0 only about potentially breaking backward compatibility by making the family of diff-* plumbing commands ignore diff.algorithm configuration, and other usability changes like this one are fair game without having to wait for 3.0 boundary (the plumbing commands do ignore the configuration already, so there is nothing we have to wait 3.0 before doing).

Sensible.

I presume the reverse is true, i.e. giving "--minimal" and then "--diff-algorithm=histogram" in this order would make "histogram" survive, in other words, the usual "last one wins" rule is applied?

This and diff.c:diff_opt_diff_algorithm_no_arg(), which I think is the original from which this was copied from, look somewhat different, but this can afford to be simpler, as it does not have to parse "--histogram", "--patience", etc., as independent command line options. OK.

Quite straight-forward and sensible.

This OPT_BIT() can stay here? I thought parse_options_check() was capable of detecting duplicated long-form commands as programming error, but apparently it does not. (#leftoverbits) We should look into teaching parse_options_check() to check duplicated option names.

Do we need to test combination of configuration variables and command line options (to verify that options trump configuration), or two command line options (to verify that the last one wins)?

When xdiff/ part of the system gets improved, the above expected patterns may have to change, these tests may fail. Whoever updates the diff algorithm to cause such a failure has to tell between a genuine _bug_ in their update to diff implementation and the test expecting a suboptimal result based on the behaviour of the diff algorithm before their improvement. And for that, they need to debug these tests. But I suspect that these tests will probably be very difficult to debug, as it is almost impossible to see which line in the original each of these lines correspond to.

I guess that's inevitable, and we'll cross that bridge when it becomes necessary.

Thanks, will queue, but I do find the leftover --minimal bit disturbing.

Hi Junio,

On 28/10/2025 16:22, Junio C Hamano wrote:

Yes, that was already the case in the version 1 of this patch. Philipp noticed that it was only true in one direction, so this fixes it.

Oops, that's an oversight on my part indeed. I'll fix it.

It's easy enough to add such tests, I can add a few more.

I'm happy to make the tests a bit clearer by including the lines in the expected output.

I'll submit a new version with those changes.

Best,

Antonin

From: Antonin Delpeuch <antonin@delpeuch.eu>

The diff algorithm used in 'git-blame(1)' is set to 'myers', without the possibility to change it aside from the `--minimal` option.

There has been long-standing interest in changing the default diff algorithm to "histogram", and Git 3.0 was floated as a possible occasion for taking some steps towards that:

https://lore.kernel.org/git/xmqqed873vgn.fsf@gitster.g/

As a preparation for this move, it is worth making sure that the diff algorithm is configurable where useful.

Make it configurable in the `git-blame(1)` command by introducing the `--diff-algorithm` option and make honor the `diff.algorithm` config variable. Keep Myers diff as the default.

Signed-off-by: Antonin Delpeuch <antonin@delpeuch.eu>
---
    blame: make diff algorithm configurable
    
    Changes since v1:
    
     * add tests
     * ignore --diff-algorithm when it is provided before --minimal
     * improve patch description
     * remove duplication of documentation sections
     * style improvements

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-2075%2Fwetneb%2Fblame_respects_diff_algorithm-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-2075/wetneb/blame_respects_diff_algorithm-v3
Pull-Request: https://github.com/git/git/pull/2075

Range-diff vs v2:

 1:  107f51620b ! 1:  b8bdb03516 blame: make diff algorithm configurable
     @@ builtin/blame.c: int cmd_blame(int argc,
       		OPT_STRING_LIST(0, "ignore-revs-file", &ignore_revs_file_list, N_("file"), N_("ignore revisions from <file>")),
       		OPT_BIT(0, "color-lines", &output_option, N_("color redundant metadata from previous line differently"), OUTPUT_COLOR_LINE),
       		OPT_BIT(0, "color-by-age", &output_option, N_("color lines by age"), OUTPUT_SHOW_AGE_WITH_COLOR),
     +-		OPT_BIT(0, "minimal", &xdl_opts, N_("spend extra cycles to find better match"), XDF_NEED_MINIMAL),
      +		OPT_CALLBACK_F(0, "minimal", &xdl_opts, NULL,
      +			       N_("spend extra cycles to find better match"),
      +			       PARSE_OPT_NONEG | PARSE_OPT_NOARG,
      +			       blame_diff_algorithm_minimal),
     - 		OPT_BIT(0, "minimal", &xdl_opts, N_("spend extra cycles to find better match"), XDF_NEED_MINIMAL),
       		OPT_STRING('S', NULL, &revs_file, N_("file"), N_("use revisions from <file> instead of calling git-rev-list")),
       		OPT_STRING(0, "contents", &contents_from, N_("file"), N_("use <file>'s contents as the final image")),
     + 		OPT_CALLBACK_F('C', NULL, &opt, N_("score"), N_("find line copies within and across files"), PARSE_OPT_OPTARG, blame_copy_callback),
      
       ## t/meson.build ##
      @@ t/meson.build: integration_tests = [
     @@ t/t8015-blame-diff-algorithm.sh (new)
      +	cat >file.c <<-\EOF &&
      +	int f(int x, int y)
      +	{
     -+		if (x == 0)
     -+		{
     -+			return y;
     -+		}
     -+		return x;
     ++	  if (x == 0)
     ++	  {
     ++	    return y;
     ++	  }
     ++	  return x;
      +	}
      +
      +	int g(size_t u)
      +	{
     -+		while (u < 30)
     -+		{
     -+			u++;
     -+		}
     -+		return u;
     ++	  while (u < 30)
     ++	  {
     ++	    u++;
     ++	  }
     ++	  return u;
      +	}
      +	EOF
      +	test_write_lines x x x x >file.txt &&
      +	git add file.c file.txt &&
     -+	GIT_AUTHOR_NAME=Initial git commit -m Initial &&
     ++	GIT_AUTHOR_NAME=Commit_1 git commit -m Commit_1 &&
      +
      +	cat >file.c <<-\EOF &&
      +	int g(size_t u)
      +	{
     -+		while (u < 30)
     -+		{
     -+			u++;
     -+		}
     -+		return u;
     ++	  while (u < 30)
     ++	  {
     ++	    u++;
     ++	  }
     ++	  return u;
      +	}
      +
      +	int h(int x, int y, int z)
      +	{
     -+		if (z == 0)
     -+		{
     -+			return x;
     -+		}
     -+		return y;
     ++	  if (z == 0)
     ++	  {
     ++	    return x;
     ++	  }
     ++	  return y;
      +	}
      +	EOF
      +	test_write_lines x x x A B C D x E F G >file.txt &&
      +	git add file.c file.txt &&
     -+	GIT_AUTHOR_NAME=Second git commit -m Second
     ++	GIT_AUTHOR_NAME=Commit_2 git commit -m Commit_2
      +'
      +
      +test_expect_success 'blame uses Myers diff algorithm by default for now' '
      +	cat >expected <<-\EOF &&
     -+	Second
     -+	Initial
     -+	Second
     -+	Initial
     -+	Second
     -+	Initial
     -+	Second
     -+	Initial
     -+	Initial
     -+	Second
     -+	Initial
     -+	Second
     -+	Initial
     -+	Second
     -+	Initial
     -+	Second
     -+	Initial
     ++	Commit_2 int g(size_t u)
     ++	Commit_1 {
     ++	Commit_2   while (u < 30)
     ++	Commit_1   {
     ++	Commit_2     u++;
     ++	Commit_1   }
     ++	Commit_2   return u;
     ++	Commit_1 }
     ++	Commit_1
     ++	Commit_2 int h(int x, int y, int z)
     ++	Commit_1 {
     ++	Commit_2   if (z == 0)
     ++	Commit_1   {
     ++	Commit_2     return x;
     ++	Commit_1   }
     ++	Commit_2   return y;
     ++	Commit_1 }
      +	EOF
      +
     -+	# git blame file.c | grep --only-matching -e Initial -e Second > actual &&
     -+	# test_cmp expected actual
     -+	echo goo
     ++
     ++	git blame file.c | \
     ++		sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" | \
     ++		sed -e "s/ *$//g" > actual &&
     ++	test_cmp expected actual
      +'
      +
      +test_expect_success 'blame honors --diff-algorithm option' '
      +	cat >expected <<-\EOF &&
     -+	Initial
     -+	Initial
     -+	Initial
     -+	Initial
     -+	Initial
     -+	Initial
     -+	Initial
     -+	Initial
     -+	Second
     -+	Second
     -+	Second
     -+	Second
     -+	Second
     -+	Second
     -+	Second
     -+	Second
     -+	Second
     ++	Commit_1 int g(size_t u)
     ++	Commit_1 {
     ++	Commit_1   while (u < 30)
     ++	Commit_1   {
     ++	Commit_1     u++;
     ++	Commit_1   }
     ++	Commit_1   return u;
     ++	Commit_1 }
     ++	Commit_2
     ++	Commit_2 int h(int x, int y, int z)
     ++	Commit_2 {
     ++	Commit_2   if (z == 0)
     ++	Commit_2   {
     ++	Commit_2     return x;
     ++	Commit_2   }
     ++	Commit_2   return y;
     ++	Commit_2 }
      +	EOF
      +
     -+	git blame file.c --diff-algorithm=histogram | \
     -+		grep --only-matching -e Initial -e Second > actual &&
     ++	git blame file.c --diff-algorithm histogram | \
     ++		sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" | \
     ++		sed -e "s/ *$//g" > actual &&
      +	test_cmp expected actual
      +'
      +
      +test_expect_success 'blame honors diff.algorithm config variable' '
      +	cat >expected <<-\EOF &&
     -+	Initial
     -+	Initial
     -+	Initial
     -+	Initial
     -+	Initial
     -+	Initial
     -+	Initial
     -+	Initial
     -+	Second
     -+	Second
     -+	Second
     -+	Second
     -+	Second
     -+	Second
     -+	Second
     -+	Second
     -+	Second
     ++	Commit_1 int g(size_t u)
     ++	Commit_1 {
     ++	Commit_1   while (u < 30)
     ++	Commit_1   {
     ++	Commit_1     u++;
     ++	Commit_1   }
     ++	Commit_1   return u;
     ++	Commit_1 }
     ++	Commit_2
     ++	Commit_2 int h(int x, int y, int z)
     ++	Commit_2 {
     ++	Commit_2   if (z == 0)
     ++	Commit_2   {
     ++	Commit_2     return x;
     ++	Commit_2   }
     ++	Commit_2   return y;
     ++	Commit_2 }
      +	EOF
      +
      +	git config diff.algorithm histogram &&
      +	git blame file.c | \
     -+		grep --only-matching -e Initial -e Second > actual &&
     ++		sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" | \
     ++		sed -e "s/ *$//g" > actual &&
      +	test_cmp expected actual
      +'
      +
     ++test_expect_success 'blame gives priority to --diff-algorithm over diff.algorithm' '
     ++	cat >expected <<-\EOF &&
     ++	Commit_1 int g(size_t u)
     ++	Commit_1 {
     ++	Commit_1   while (u < 30)
     ++	Commit_1   {
     ++	Commit_1     u++;
     ++	Commit_1   }
     ++	Commit_1   return u;
     ++	Commit_1 }
     ++	Commit_2
     ++	Commit_2 int h(int x, int y, int z)
     ++	Commit_2 {
     ++	Commit_2   if (z == 0)
     ++	Commit_2   {
     ++	Commit_2     return x;
     ++	Commit_2   }
     ++	Commit_2   return y;
     ++	Commit_2 }
     ++	EOF
     ++
     ++	git config diff.algorithm myers &&
     ++	git blame file.c --diff-algorithm histogram | \
     ++		sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" | \
     ++		sed -e "s/ *$//g" > actual &&
     ++	test_cmp expected actual
     ++'
      +test_expect_success 'blame honors --minimal option' '
      +	cat >expected <<-\EOF &&
     -+	Initial
     -+	Initial
     -+	Initial
     -+	Second
     -+	Second
     -+	Second
     -+	Second
     -+	Initial
     -+	Second
     -+	Second
     -+	Second
     ++	Commit_1 x
     ++	Commit_1 x
     ++	Commit_1 x
     ++	Commit_2 A
     ++	Commit_2 B
     ++	Commit_2 C
     ++	Commit_2 D
     ++	Commit_1 x
     ++	Commit_2 E
     ++	Commit_2 F
     ++	Commit_2 G
      +	EOF
      +
      +	git blame file.txt --minimal | \
     -+		grep --only-matching -e Initial -e Second > actual &&
     ++		sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" > actual &&
      +	test_cmp expected actual
      +'
      +
     ++test_expect_success 'blame respects the order of diff options' '
     ++	cat >expected <<-\EOF &&
     ++	Commit_1 x
     ++	Commit_1 x
     ++	Commit_1 x
     ++	Commit_2 A
     ++	Commit_2 B
     ++	Commit_2 C
     ++	Commit_2 D
     ++	Commit_2 x
     ++	Commit_2 E
     ++	Commit_2 F
     ++	Commit_2 G
     ++	EOF
     ++
     ++	git blame file.txt --minimal --diff-algorithm myers | \
     ++		sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" > actual &&
     ++	test_cmp expected actual
     ++'
     ++
     ++
      +test_done

 Documentation/diff-algorithm-option.adoc |  20 +++
 Documentation/diff-options.adoc          |  21 +--
 Documentation/git-blame.adoc             |   2 +
 builtin/blame.c                          |  53 +++++-
 t/meson.build                            |   1 +
 t/t8015-blame-diff-algorithm.sh          | 206 +++++++++++++++++++++++
 6 files changed, 282 insertions(+), 21 deletions(-)
 create mode 100644 Documentation/diff-algorithm-option.adoc
 create mode 100755 t/t8015-blame-diff-algorithm.sh

Hi Antonin

On 28/10/2025 21:14, Antonin Delpeuch via GitGitGadget wrote:

Apart from a problem with clearing XDF_NEED_MINIMAL (which is really the fault of a terrible api) this is looking good.

Unfortunately XDF_DIFF_ALGORITHM_MASK does not include XDF_NEED_MINIMAL 
so if the user has a config file that looks like
	
	[diff]
		algorithm = minimal
		algorithm = myers

We'll parse it as "minimal" rather than "myers"

As we need to reset the diff algorithm in a number of places I think it would be best to define a macro

     	#define CLEAR_DIFF_ALGORITHM(flags) \
		flags &= ~(XDF_DIFF_ALGORITHM_MASK | XDF_NEED_MINIMAL)

and use that where we want to reset the algorithm.

This is a change in behavior as we currently accept "--no-minimal" which clears XDF_NEED_MINIMAL

This is correct becase we're about to set XDF_NEED_MINIMAL so it does not matter that we leave it set here, but would still be clearer if it used the new macro I suggested above.

This is correct

This is just copying the existing text so it is not a new problem but I think it would be better if we said "find a better" rather than "find better". We should prehaps think about hiding this option now that we support --diff-algorithm.

As I said above using PARSE_OPT_NONEG here is a regression

I'm not sure we need to say "for now" here.

There's an extra blank line here

We don't pipe the output git commands as it hides unexpected failures. Instead you should redirect the output of git to a file and then process that file with sed.

This can be a single process by passing -e twice. It does not really matter but neither pattern needs a trailing "g" as they only match once within the line.

You can use test_config() here which will clear the config setting at the end of the test. Alternatively you can save a couple of processes by using "git -c diff.algorithm=myers blame ...". This is setting the config to the default value, I wonder if it would be better to do

	git -c diff.algorithm=histogram blame --diff-algorithm=myers

instead.

The coverage looks good

Thanks

Phillip

Phillip Wood <phillip.wood123@gmail.com> writes:

Ah, I missed this; thanks for a careful reading.

We shouldn't.

Hi Phillip,

On 29/10/2025 11:16, Phillip Wood wrote:

Ouch, good catch! This problem is affecting other places as well.

I'm wondering if we couldn't even add XDF_NEED_MINIMAL to XDF_DIFF_ALGORITHM_MASK. I've reviewed all the places where XDF_DIFF_ALGORITHM_MASK is used, and it seems that in all cases it would either preserve the existing behaviour (potentially allowing us to remove an accompanying "DIFF_XDL_CLR(opts, NEED_MINIMAL);" macro which becomes redundant), or in some other cases it would fix a similar issue (for instance, in merge-file.c).

Is your suggestion to introduce a new macro motivated by stability concerns? I'm aware that xdiff is used in other code bases as a library, so I guess changing XDF_DIFF_ALGORITHM_MASK can indeed be seen as a breaking change.

Antonin

Hi Antonin

On 30/10/2025 09:22, Antonin Delpeuch wrote:

Thanks for taking the time to look at the other uses of XDF_DIFF_ALGORITHM_MASK. I think adding XDF_NEED_MINIMAL to XDF_DIFF_ALGORITHM_MASK is a good idea as I think we always treat "minimal" as another diff algorithm, rather than a variant of "myers" which is how it is implemented in xdiff.

While it is a breaking change, tweaking XDF_DIFF_ALGORITHM_MASK seems like a better idea to me. I wondered about it yesterday but worried it would end up being too much work to review all the existing uses.

Thanks

Phillip

Changes since v3:

 * fix resetting of diff algorithm by adding XDF_NEED_MINIMAL to
   XDF_DIFF_ALGORITHM_MASK
 * restore --no-minimal support
 * fix typo in description of --minimal option
 * remove the 'for now' in test description
 * remove piping in tests
 * pass configuration variables to the blame command directly instead of
   calling 'git config'

Antonin Delpeuch (2):
  xdiff: add 'minimal' to XDF_DIFF_ALGORITHM_MASK
  blame: make diff algorithm configurable

 Documentation/diff-algorithm-option.adoc |  20 +++
 Documentation/diff-options.adoc          |  21 +--
 Documentation/git-blame.adoc             |   2 +
 builtin/blame.c                          |  52 +++++-
 diff.c                                   |   2 -
 merge-ort.c                              |   2 -
 t/meson.build                            |   1 +
 t/t8015-blame-diff-algorithm.sh          | 203 +++++++++++++++++++++++
 xdiff/xdiff.h                            |   2 +-
 9 files changed, 279 insertions(+), 26 deletions(-)
 create mode 100644 Documentation/diff-algorithm-option.adoc
 create mode 100755 t/t8015-blame-diff-algorithm.sh

base-commit: 4253630c6f07a4bdcc9aa62a50e26a4d466219d1
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-2075%2Fwetneb%2Fblame_respects_diff_algorithm-v4
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-2075/wetneb/blame_respects_diff_algorithm-v4
Pull-Request: https://github.com/git/git/pull/2075

Range-diff vs v3:

 -:  ---------- > 1:  e81a5d2bd2 xdiff: add 'minimal' to XDF_DIFF_ALGORITHM_MASK
 1:  b8bdb03516 ! 2:  920a6f3acb blame: make diff algorithm configurable
     @@ builtin/blame.c: static int blame_move_callback(const struct option *option, con
      +{
      +	int *opt = option->value;
      +
     -+	BUG_ON_OPT_NEG(unset);
      +	BUG_ON_OPT_ARG(arg);
      +
      +	*opt &= ~XDF_DIFF_ALGORITHM_MASK;
     -+	*opt |= XDF_NEED_MINIMAL;
     ++	if (!unset)
     ++		*opt |= XDF_NEED_MINIMAL;
      +
      +	return 0;
      +}
     @@ builtin/blame.c: int cmd_blame(int argc,
       		OPT_BIT(0, "color-by-age", &output_option, N_("color lines by age"), OUTPUT_SHOW_AGE_WITH_COLOR),
      -		OPT_BIT(0, "minimal", &xdl_opts, N_("spend extra cycles to find better match"), XDF_NEED_MINIMAL),
      +		OPT_CALLBACK_F(0, "minimal", &xdl_opts, NULL,
     -+			       N_("spend extra cycles to find better match"),
     -+			       PARSE_OPT_NONEG | PARSE_OPT_NOARG,
     -+			       blame_diff_algorithm_minimal),
     ++			       N_("spend extra cycles to find a better match"),
     ++			       PARSE_OPT_NOARG, blame_diff_algorithm_minimal),
       		OPT_STRING('S', NULL, &revs_file, N_("file"), N_("use revisions from <file> instead of calling git-rev-list")),
       		OPT_STRING(0, "contents", &contents_from, N_("file"), N_("use <file>'s contents as the final image")),
       		OPT_CALLBACK_F('C', NULL, &opt, N_("score"), N_("find line copies within and across files"), PARSE_OPT_OPTARG, blame_copy_callback),
     @@ t/t8015-blame-diff-algorithm.sh (new)
      +	GIT_AUTHOR_NAME=Commit_2 git commit -m Commit_2
      +'
      +
     -+test_expect_success 'blame uses Myers diff algorithm by default for now' '
     ++test_expect_success 'blame uses Myers diff algorithm by default' '
      +	cat >expected <<-\EOF &&
      +	Commit_2 int g(size_t u)
      +	Commit_1 {
     @@ t/t8015-blame-diff-algorithm.sh (new)
      +	Commit_1 }
      +	EOF
      +
     -+
     -+	git blame file.c | \
     -+		sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" | \
     -+		sed -e "s/ *$//g" > actual &&
     ++	git blame file.c > output &&
     ++	sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" output > without_varying_parts &&
     ++	sed -e "s/ *$//g" without_varying_parts > actual &&
      +	test_cmp expected actual
      +'
      +
     @@ t/t8015-blame-diff-algorithm.sh (new)
      +	Commit_2 }
      +	EOF
      +
     -+	git blame file.c --diff-algorithm histogram | \
     -+		sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" | \
     -+		sed -e "s/ *$//g" > actual &&
     ++	git blame file.c --diff-algorithm histogram > output &&
     ++	sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" output > without_varying_parts &&
     ++	sed -e "s/ *$//g" without_varying_parts > actual &&
      +	test_cmp expected actual
      +'
      +
     @@ t/t8015-blame-diff-algorithm.sh (new)
      +	Commit_2 }
      +	EOF
      +
     -+	git config diff.algorithm histogram &&
     -+	git blame file.c | \
     -+		sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" | \
     -+		sed -e "s/ *$//g" > actual &&
     ++	git -c diff.algorithm=histogram blame file.c > output &&
     ++	sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" output > without_varying_parts &&
     ++	sed -e "s/ *$//g" without_varying_parts > actual &&
      +	test_cmp expected actual
      +'
      +
     @@ t/t8015-blame-diff-algorithm.sh (new)
      +	Commit_2 }
      +	EOF
      +
     -+	git config diff.algorithm myers &&
     -+	git blame file.c --diff-algorithm histogram | \
     -+		sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" | \
     -+		sed -e "s/ *$//g" > actual &&
     ++	git -c diff.algorithm=myers blame file.c --diff-algorithm histogram &&
     ++	sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" output > without_varying_parts &&
     ++	sed -e "s/ *$//g" without_varying_parts > actual &&
      +	test_cmp expected actual
      +'
     ++
      +test_expect_success 'blame honors --minimal option' '
      +	cat >expected <<-\EOF &&
      +	Commit_1 x
     @@ t/t8015-blame-diff-algorithm.sh (new)
      +	Commit_2 G
      +	EOF
      +
     -+	git blame file.txt --minimal | \
     -+		sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" > actual &&
     ++	git blame file.txt --minimal > output &&
     ++	sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" output > actual &&
      +	test_cmp expected actual
      +'
      +
     @@ t/t8015-blame-diff-algorithm.sh (new)
      +	Commit_2 G
      +	EOF
      +
     -+	git blame file.txt --minimal --diff-algorithm myers | \
     -+		sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" > actual &&
     ++	git blame file.txt --minimal --diff-algorithm myers > output &&
     ++	sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" output > actual &&
      +	test_cmp expected actual
      +'
      +
     -+
      +test_done

From: Antonin Delpeuch <antonin@delpeuch.eu>

The XDF_DIFF_ALGORITHM_MASK bit mask only includes bits for the patience and histogram diffs, not for the minimal one. This means that when reseting the diff algorithm to the default one, one needs to separately clear the bit for the minimal diff. There are places in the code that fail to do that: merge-ort.c and builtin/merge-file.c.

Add the XDF_NEED_MINIMAL bit to the bit mask, and remove the separate clearing of this bit in the places where it hasn't been forgotten.

Signed-off-by: Antonin Delpeuch <antonin@delpeuch.eu>
---
 diff.c        | 2 --
 merge-ort.c   | 2 --
 xdiff/xdiff.h | 2 +-
 3 files changed, 1 insertion(+), 5 deletions(-)

Hi Antonin

On 01/11/2025 21:57, Antonin Delpeuch via GitGitGadget wrote:

Nicely explained. This is a useful improvement that should prevent errors in the future. After this patch there are no users of DIFF_XDL_CLR() so we should probably remove that macro. I'm not sure it makes sense to remove the comments that have been deleted below as we're still clearing the old setting. Apart from that this all looks good.

Thanks

Phillip

From: Antonin Delpeuch <antonin@delpeuch.eu>

The diff algorithm used in 'git-blame(1)' is set to 'myers', without the possibility to change it aside from the `--minimal` option.

There has been long-standing interest in changing the default diff algorithm to "histogram", and Git 3.0 was floated as a possible occasion for taking some steps towards that:

https://lore.kernel.org/git/xmqqed873vgn.fsf@gitster.g/

As a preparation for this move, it is worth making sure that the diff algorithm is configurable where useful.

Make it configurable in the `git-blame(1)` command by introducing the `--diff-algorithm` option and make honor the `diff.algorithm` config variable. Keep Myers diff as the default.

Signed-off-by: Antonin Delpeuch <antonin@delpeuch.eu>
---
 Documentation/diff-algorithm-option.adoc |  20 +++
 Documentation/diff-options.adoc          |  21 +--
 Documentation/git-blame.adoc             |   2 +
 builtin/blame.c                          |  52 +++++-
 t/meson.build                            |   1 +
 t/t8015-blame-diff-algorithm.sh          | 203 +++++++++++++++++++++++
 6 files changed, 278 insertions(+), 21 deletions(-)
 create mode 100644 Documentation/diff-algorithm-option.adoc
 create mode 100755 t/t8015-blame-diff-algorithm.sh

Hi Antonin

Thanks for re-rolling, this is looking pretty sound, I've left a couple of fairly minor comments below.

On 01/11/2025 21:57, Antonin Delpeuch via GitGitGadget wrote:

One thing I'd not thought about before was the interaction between "--no-minimal" and "--diff-algorithm" The code above makes "--no-minimal" behave like "diff-algorithm=myers" which is consistent with the current behavior where the only options for the diff algorithm are "minimal" or "myers". An alternative would be for "--no-minimal" to just clear XDF_NEED_MINIMAL and behave like a no-op if it is given after "--diff-algorithm=patience" or "--diff-algorithm=histogram". I don't really have a strong preference either way.

We can just use XDF_DIFF_ALGORITHM_MASK now that we've added XDF_NEED_MINMAL to it in the last commit.

Given the potential for confusing interactions between "--no-minimal" and "--diff-algorithm" I think it would be worth adding OPT_HIDDEN here.

This would be more efficient if it was written as

	sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" \
	    -e "s/ *$//g" output >actual

Our test suite is really slow on windows so it is worth trying to avoid creating unnecessary processes.

Thanks

Phillip

Phillip Wood <phillip.wood123@gmail.com> writes:

Good observation.

In the longer term, I think we would be better off if we treated "minimal" just like "histogram" and "patience", in that

 (1) If the command takes --diff-algorithm=<name>, giving it as the
     <name> would override the previous setting.

 (2) If the command takes --<name> (i.e. "git diff --histogram"),
     giving "--no-<name>" results in an error.

 (3) If the command takes --<name>, it should take all the variants
     as <name>, not just selected few, or it shouldn't take any.

IOW, we should deprecate "blame --no-minimal" as a past mistake, and in the longer term deprecate "blame --minimal" and tell users to use "--diff-algorithm=minimal" instead.

If Antonin's series wants to teach --histogram and --patience to "git blame", then we can and should keep "blame --minimal" (i.e., (3) above), but in that case, "blame --no-minimal" should still go (i.e., (2) above). Under the new world order where there are more than the "minimal/no-minimal?" binary choice, where you can specify other algorithms from the usual repertoire, the option "no-minimal" no longer makes sense.

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

Just to avoid confusion, the idea above to deprecate and kill "--no-minimal" is totally outside of this topic to teach "git blame" the "--diff-algorithm=<algo>" command line option.

I think in the shorter term I think it is OK for the implementation to do whatever it happens to do when given "--no-minimal", and as you observed, it is fine to behave like "--diff-algorithm=myers". I also like your idea to hide --minimal with the OPT_HIDDEN bit.

Thanks.

Changes since v4:

 * hide --minimal option
 * simplify tests to minimize spun processes
 * remove redundant XDF_NEED_MINIMAL in bit mask

Antonin Delpeuch (2):
  xdiff: add 'minimal' to XDF_DIFF_ALGORITHM_MASK
  blame: make diff algorithm configurable

 Documentation/diff-algorithm-option.adoc |  20 +++
 Documentation/diff-options.adoc          |  21 +--
 Documentation/git-blame.adoc             |   2 +
 builtin/blame.c                          |  52 +++++-
 diff.c                                   |   2 -
 merge-ort.c                              |   2 -
 t/meson.build                            |   1 +
 t/t8015-blame-diff-algorithm.sh          | 203 +++++++++++++++++++++++
 xdiff/xdiff.h                            |   2 +-
 9 files changed, 279 insertions(+), 26 deletions(-)
 create mode 100644 Documentation/diff-algorithm-option.adoc
 create mode 100755 t/t8015-blame-diff-algorithm.sh

base-commit: 4253630c6f07a4bdcc9aa62a50e26a4d466219d1
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-2075%2Fwetneb%2Fblame_respects_diff_algorithm-v5
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-2075/wetneb/blame_respects_diff_algorithm-v5
Pull-Request: https://github.com/git/git/pull/2075

Range-diff vs v4:

 1:  e81a5d2bd2 = 1:  e81a5d2bd2 xdiff: add 'minimal' to XDF_DIFF_ALGORITHM_MASK
 2:  920a6f3acb ! 2:  60015bbada blame: make diff algorithm configurable
     @@ builtin/blame.c: static int blame_move_callback(const struct option *option, con
      +		return error(_("option diff-algorithm accepts \"myers\", "
      +			       "\"minimal\", \"patience\" and \"histogram\""));
      +
     -+	*opt &= ~(XDF_NEED_MINIMAL | XDF_DIFF_ALGORITHM_MASK);
     ++	*opt &= ~XDF_DIFF_ALGORITHM_MASK;
      +	*opt |= value;
      +
      +	return 0;
     @@ builtin/blame.c: int cmd_blame(int argc,
      -		OPT_BIT(0, "minimal", &xdl_opts, N_("spend extra cycles to find better match"), XDF_NEED_MINIMAL),
      +		OPT_CALLBACK_F(0, "minimal", &xdl_opts, NULL,
      +			       N_("spend extra cycles to find a better match"),
     -+			       PARSE_OPT_NOARG, blame_diff_algorithm_minimal),
     ++			       PARSE_OPT_NOARG | PARSE_OPT_HIDDEN, blame_diff_algorithm_minimal),
       		OPT_STRING('S', NULL, &revs_file, N_("file"), N_("use revisions from <file> instead of calling git-rev-list")),
       		OPT_STRING(0, "contents", &contents_from, N_("file"), N_("use <file>'s contents as the final image")),
       		OPT_CALLBACK_F('C', NULL, &opt, N_("score"), N_("find line copies within and across files"), PARSE_OPT_OPTARG, blame_copy_callback),
     @@ t/t8015-blame-diff-algorithm.sh (new)
      +	EOF
      +
      +	git -c diff.algorithm=histogram blame file.c > output &&
     -+	sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" output > without_varying_parts &&
     -+	sed -e "s/ *$//g" without_varying_parts > actual &&
     ++	sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" \
     ++	    -e "s/ *$//g" output > actual &&
      +	test_cmp expected actual
      +'
      +
     @@ t/t8015-blame-diff-algorithm.sh (new)
      +	Commit_2 }
      +	EOF
      +
     -+	git -c diff.algorithm=myers blame file.c --diff-algorithm histogram &&
     -+	sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" output > without_varying_parts &&
     -+	sed -e "s/ *$//g" without_varying_parts > actual &&
     ++	git -c diff.algorithm=myers blame file.c --diff-algorithm histogram > output &&
     ++	sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" \
     ++	    -e "s/ *$//g" output > actual &&
      +	test_cmp expected actual
      +'
      +

From: Antonin Delpeuch <antonin@delpeuch.eu>

The XDF_DIFF_ALGORITHM_MASK bit mask only includes bits for the patience and histogram diffs, not for the minimal one. This means that when reseting the diff algorithm to the default one, one needs to separately clear the bit for the minimal diff. There are places in the code that fail to do that: merge-ort.c and builtin/merge-file.c.

Add the XDF_NEED_MINIMAL bit to the bit mask, and remove the separate clearing of this bit in the places where it hasn't been forgotten.

Signed-off-by: Antonin Delpeuch <antonin@delpeuch.eu>
---
 diff.c        | 2 --
 merge-ort.c   | 2 --
 xdiff/xdiff.h | 2 +-
 3 files changed, 1 insertion(+), 5 deletions(-)

"Antonin Delpeuch via GitGitGadget" <gitgitgadget@gmail.com> writes:

Makes sense. In other words, lack of any algorithm-mask bit means the code uses myers.

The comment still accurately describes what the surviving line does, though. It is borderline if it needs commenting, but the topic of this patch not being "remove overly obvious comments", I'd probably vote for retaining the comment.

Given the definition of XDF_DIFF_ALG(), I wondered how it is used.

    $ git grep -n -e 'XDF_DIFF_ALG(' \*.c
    xdiff/xdiffi.c:324:	if (XDF_DIFF_ALG(xpp->flags) == XDF_PATIENCE_DIFF) {
    xdiff/xdiffi.c:329:	if (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF) {
    xdiff/xprepare.c:170:	if ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) &&
    xdiff/xprepare.c:171:	    (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF)) {
    xdiff/xprepare.c:396:	sample = (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF
    xdiff/xprepare.c:417:	if ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) &&
    xdiff/xprepare.c:418:	    (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) &&

They say "if the specified algorithm is (or is not) patience (or histogram), do this". Now the original code, because the mask did not include the need-minimal bit, would have chosen patience code path even if xpp->flags had XDF_PATIENCE_DIFF and XDF_NEED_MINIMAL bits set at the same time. The code would no longer do so.

What is keeping us safe and not making this change a bug is that among XDF_DIFF_ALGORITHM_MASK bits, we intend to set at most one of them at a time. I wonder if we want the command line option and configuration parser to have an explicit check (and BUG("")) to ensure this constraint.

Also, in the longer term as #leftoverbits clean-up, perhaps these bits can be removed from xpp->flags and diff_options->xdl_opts, xpp structure can gain a separate member that is an enum of the algorithm names instead, and XDF_DIFF_ALGORITHM_MASK can be dropped?

Then set_diff_algorithm() we saw earlier can become

	if (value < 0)
		return -1;
	opts->xdl_algo = value;
	return 0;

And since there is no "clean out prvious settings" required (now we can simply overwrite), we can truly lose that old comment once we do so.

As a part of this topic, I think that a new code to sanity check that there are at most one bit in XDF_DIFF_ALG(xpp->flags) may be a good safety measure to have. Moving the algorithm bits out of the flags is a larger change, and it may be better left outside the topic, but I do not personaly mind seeing such a clean-up included as a preparatory change for this series, either.

Thanks.

From: Antonin Delpeuch <antonin@delpeuch.eu>

The diff algorithm used in 'git-blame(1)' is set to 'myers', without the possibility to change it aside from the `--minimal` option.

There has been long-standing interest in changing the default diff algorithm to "histogram", and Git 3.0 was floated as a possible occasion for taking some steps towards that:

https://lore.kernel.org/git/xmqqed873vgn.fsf@gitster.g/

As a preparation for this move, it is worth making sure that the diff algorithm is configurable where useful.

Make it configurable in the `git-blame(1)` command by introducing the `--diff-algorithm` option and make honor the `diff.algorithm` config variable. Keep Myers diff as the default.

Signed-off-by: Antonin Delpeuch <antonin@delpeuch.eu>
---
 Documentation/diff-algorithm-option.adoc |  20 +++
 Documentation/diff-options.adoc          |  21 +--
 Documentation/git-blame.adoc             |   2 +
 builtin/blame.c                          |  52 +++++-
 t/meson.build                            |   1 +
 t/t8015-blame-diff-algorithm.sh          | 203 +++++++++++++++++++++++
 6 files changed, 278 insertions(+), 21 deletions(-)
 create mode 100644 Documentation/diff-algorithm-option.adoc
 create mode 100755 t/t8015-blame-diff-algorithm.sh

"Antonin Delpeuch via GitGitGadget" <gitgitgadget@gmail.com> writes:

This step does not have anything surprising in it, knowing what the previous iteration contained. Looking good.

Other than that many redirections into a file are written with a space between redirection operator and its target, i.e.

    command > output &&

that should be, according to the coding guidelines, written like

    command >output &&

that is.

Thanks.

Hi Antonin

On 06/11/2025 22:41, Antonin Delpeuch via GitGitGadget wrote:

Excellent, the range-diff below looks good. Thanks for working on this

Phillip

Phillip Wood <phillip.wood123@gmail.com> writes:

OK, we haven't seen any activities since we saw this comment. Are we ready to mark the topic for 'next', or are you waiting for the end of feature freeze to make a (hopefully small and fanal) reroll?

Thanks.

Changes since v5:

 * add back /* clear out previous settings */ comments
 * remove whitespace in bash output redirection

Antonin Delpeuch (2):
  xdiff: add 'minimal' to XDF_DIFF_ALGORITHM_MASK
  blame: make diff algorithm configurable

 Documentation/diff-algorithm-option.adoc |  20 +++
 Documentation/diff-options.adoc          |  21 +--
 Documentation/git-blame.adoc             |   2 +
 builtin/blame.c                          |  52 +++++-
 diff.c                                   |   1 -
 merge-ort.c                              |   1 -
 t/meson.build                            |   1 +
 t/t8015-blame-diff-algorithm.sh          | 203 +++++++++++++++++++++++
 xdiff/xdiff.h                            |   2 +-
 9 files changed, 279 insertions(+), 24 deletions(-)
 create mode 100644 Documentation/diff-algorithm-option.adoc
 create mode 100755 t/t8015-blame-diff-algorithm.sh

base-commit: 4253630c6f07a4bdcc9aa62a50e26a4d466219d1
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-2075%2Fwetneb%2Fblame_respects_diff_algorithm-v6
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-2075/wetneb/blame_respects_diff_algorithm-v6
Pull-Request: https://github.com/git/git/pull/2075

Range-diff vs v5:

 1:  e81a5d2bd2 ! 1:  4846715436 xdiff: add 'minimal' to XDF_DIFF_ALGORITHM_MASK
     @@ Commit message
      
       ## diff.c ##
      @@ diff.c: static int set_diff_algorithm(struct diff_options *opts,
     - 	if (value < 0)
       		return -1;
       
     --	/* clear out previous settings */
     + 	/* clear out previous settings */
      -	DIFF_XDL_CLR(opts, NEED_MINIMAL);
       	opts->xdl_opts &= ~XDF_DIFF_ALGORITHM_MASK;
       	opts->xdl_opts |= value;
     @@ diff.c: static int set_diff_algorithm(struct diff_options *opts,
      
       ## merge-ort.c ##
      @@ merge-ort.c: int parse_merge_opt(struct merge_options *opt, const char *s)
     - 		long value = parse_algorithm_value(arg);
       		if (value < 0)
       			return -1;
     --		/* clear out previous settings */
     + 		/* clear out previous settings */
      -		DIFF_XDL_CLR(opt, NEED_MINIMAL);
       		opt->xdl_opts &= ~XDF_DIFF_ALGORITHM_MASK;
       		opt->xdl_opts |= value;
 2:  60015bbada ! 2:  c477b87cc6 blame: make diff algorithm configurable
     @@ t/t8015-blame-diff-algorithm.sh (new)
      +	Commit_1 }
      +	EOF
      +
     -+	git blame file.c > output &&
     -+	sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" output > without_varying_parts &&
     -+	sed -e "s/ *$//g" without_varying_parts > actual &&
     ++	git blame file.c >output &&
     ++	sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" output >without_varying_parts &&
     ++	sed -e "s/ *$//g" without_varying_parts >actual &&
      +	test_cmp expected actual
      +'
      +
     @@ t/t8015-blame-diff-algorithm.sh (new)
      +	Commit_2 }
      +	EOF
      +
     -+	git blame file.c --diff-algorithm histogram > output &&
     -+	sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" output > without_varying_parts &&
     -+	sed -e "s/ *$//g" without_varying_parts > actual &&
     ++	git blame file.c --diff-algorithm histogram >output &&
     ++	sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" output >without_varying_parts &&
     ++	sed -e "s/ *$//g" without_varying_parts >actual &&
      +	test_cmp expected actual
      +'
      +
     @@ t/t8015-blame-diff-algorithm.sh (new)
      +	Commit_2 }
      +	EOF
      +
     -+	git -c diff.algorithm=histogram blame file.c > output &&
     ++	git -c diff.algorithm=histogram blame file.c >output &&
      +	sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" \
     -+	    -e "s/ *$//g" output > actual &&
     ++	    -e "s/ *$//g" output >actual &&
      +	test_cmp expected actual
      +'
      +
     @@ t/t8015-blame-diff-algorithm.sh (new)
      +	Commit_2 }
      +	EOF
      +
     -+	git -c diff.algorithm=myers blame file.c --diff-algorithm histogram > output &&
     ++	git -c diff.algorithm=myers blame file.c --diff-algorithm histogram >output &&
      +	sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" \
     -+	    -e "s/ *$//g" output > actual &&
     ++	    -e "s/ *$//g" output >actual &&
      +	test_cmp expected actual
      +'
      +
     @@ t/t8015-blame-diff-algorithm.sh (new)
      +	Commit_2 G
      +	EOF
      +
     -+	git blame file.txt --minimal > output &&
     -+	sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" output > actual &&
     ++	git blame file.txt --minimal >output &&
     ++	sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" output >actual &&
      +	test_cmp expected actual
      +'
      +
     @@ t/t8015-blame-diff-algorithm.sh (new)
      +	Commit_2 G
      +	EOF
      +
     -+	git blame file.txt --minimal --diff-algorithm myers > output &&
     -+	sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" output > actual &&
     ++	git blame file.txt --minimal --diff-algorithm myers >output &&
     ++	sed -e "s/^[^ ]* (\([^ ]*\) [^)]*)/\1/g" output >actual &&
      +	test_cmp expected actual
      +'
      +

From: Antonin Delpeuch <antonin@delpeuch.eu>

The XDF_DIFF_ALGORITHM_MASK bit mask only includes bits for the patience and histogram diffs, not for the minimal one. This means that when reseting the diff algorithm to the default one, one needs to separately clear the bit for the minimal diff. There are places in the code that fail to do that: merge-ort.c and builtin/merge-file.c.

Add the XDF_NEED_MINIMAL bit to the bit mask, and remove the separate clearing of this bit in the places where it hasn't been forgotten.

Signed-off-by: Antonin Delpeuch <antonin@delpeuch.eu>
---
 diff.c        | 1 -
 merge-ort.c   | 1 -
 xdiff/xdiff.h | 2 +-
 3 files changed, 1 insertion(+), 3 deletions(-)

From: Antonin Delpeuch <antonin@delpeuch.eu>

The diff algorithm used in 'git-blame(1)' is set to 'myers', without the possibility to change it aside from the `--minimal` option.

There has been long-standing interest in changing the default diff algorithm to "histogram", and Git 3.0 was floated as a possible occasion for taking some steps towards that:

https://lore.kernel.org/git/xmqqed873vgn.fsf@gitster.g/

As a preparation for this move, it is worth making sure that the diff algorithm is configurable where useful.

Make it configurable in the `git-blame(1)` command by introducing the `--diff-algorithm` option and make honor the `diff.algorithm` config variable. Keep Myers diff as the default.

Signed-off-by: Antonin Delpeuch <antonin@delpeuch.eu>
---
 Documentation/diff-algorithm-option.adoc |  20 +++
 Documentation/diff-options.adoc          |  21 +--
 Documentation/git-blame.adoc             |   2 +
 builtin/blame.c                          |  52 +++++-
 t/meson.build                            |   1 +
 t/t8015-blame-diff-algorithm.sh          | 203 +++++++++++++++++++++++
 6 files changed, 278 insertions(+), 21 deletions(-)
 create mode 100644 Documentation/diff-algorithm-option.adoc
 create mode 100755 t/t8015-blame-diff-algorithm.sh

Hi Antonin

On 17/11/2025 08:04, Antonin Delpeuch via GitGitGadget wrote:

Thanks for re-rolling, the range-diff below looks good. Being able to configure the diff algorithm for "git blame" is a nice addition, thanks for working on it.

Phillip

"Antonin Delpeuch via GitGitGadget" <gitgitgadget@gmail.com> writes:

Will queue.  Thanks!