threads / bug / 53549

[BUG] diff algorithm selection issue

Subject: [BUG] diff algorithm selection issue

## tl;dr

6 messages between May 26, 2020 and May 26, 2020.

replies: 5people: 2as markdown or json

ydirson@free.fr· May 26, 2020, 09:36 UTC · lore
Hi all,

When the config has diff.algorithm=patience set, "git diff --minimal" seems to be ignored, and does not give the same output as "git diff --diff-algorithm=minimal", but really the same as "git diff --diff-algorithm=patience".

See top commit on https://gitlab.com/ydirson/omaha/-/commits/bug/git-diff-minimal where patience diff manages to show a quite braindead diff.

Also, I found it curious that in the manpage the long (--diff-algorithm=minimal) and short (--minimal) forms are described with a copy-paste of the text, and no mention of them being equivalent (or not, for that matter ;).

Junio C Hamano· May 26, 2020, 16:10 UTC · re: ydirson@free.fr · lore

Re: [BUG] diff algorithm selection issue

ydirson@free.fr writes:
> When the config has diff.algorithm=patience set, "git diff --minimal" seems to
> be ignored, and does not give the same output as "git diff --diff-algorithm=minimal",
> but really the same as "git diff --diff-algorithm=patience".

Thanks for reporting. The document on --diff-algorithm does make it sound as if the --diff-algorithm=minimal option must operate as if myers algorithm is used with the minumalization tweak, but that is wrong from the point of view of the intent of the "minimal" option, which was meant to be a secondary option that tweaks the base algorithm (be it myers or patience or any other new algorithm we might introduce in the future) by allowing it to spend more cycles to come up with a smaller diff.

At least, it is what the "--minimal" option (not the value "minimal" given to the "--diff-algorithm=<algo>" option), and the underlying mechanism that supports the option, meant to do.

But the way the option is surfaced to the end-user facing UI (and the documentation) with "--diff-algorithm=minimal", it does look like

	git -c diff.algorithm=patience cmd --diff-algorithm=minimal
	git -c diff.algorithm=patience cmd --diff-algorithm=myers --minimal
ought to be equivalent.
Also, I suspect that
	git -c diff.algorithm=patience cmd --diff-algorithm=myers
does not do what we expect, either.

I have not convinced myself that the attached is the best way to fix the issue, but anyway, somebody seems to be OR'ing in diff_algorithm to xdl_opts field after we see --diff-algorithm=minimal and replaced XDF_DIFF_ALGORITHM_MASK bits in xdl_opts field in this function, so the attached patch may defeat that code---the real bug is probably in that code, but I haven't figured out where it is X-<.

 diff.c | 4 ++++
 1 file changed, 4 insertions(+)
diff --git a/diff.c b/diff.c
index 863da896c0..a6dba45cd6 100644
--- a/diff.c
+++ b/diff.c
@@ -5026,6 +5026,10 @@ static int diff_opt_diff_algorithm(const struct option *opt,
 		return error(_("option diff-algorithm accepts \"myers\", "
 			       "\"minimal\", \"patience\" and \"histogram\""));
 
+	/* we shouldn't have to do this... */
+	if (!(value & XDF_DIFF_ALGORITHM_MASK))
+		diff_algorithm &= ~XDF_DIFF_ALGORITHM_MASK;
+
 	/* clear out previous settings */
 	DIFF_XDL_CLR(options, NEED_MINIMAL);
 	options->xdl_opts &= ~XDF_DIFF_ALGORITHM_MASK;
Junio C Hamano· May 26, 2020, 16:23 UTC · re: Junio C Hamano · lore

Re: [BUG] diff algorithm selection issue

Junio C Hamano <gitster@pobox.com> writes:
> the issue, but anyway, somebody seems to be OR'ing in diff_algorithm
> to xdl_opts field after we see --diff-algorithm=minimal and replaced
> XDF_DIFF_ALGORITHM_MASK bits in xdl_opts field in this function, ...

Well, I am not so sure about that diagnosis, actually. I should probably have taken a bit of caffeine before writing my e-mails.

There is no patch needed. --- I simply had misread your report.
> When the config has diff.algorithm=patience set, "git diff --minimal" seems to
> be ignored, and does not give the same output as "git diff --diff-algorithm=minimal",
> but really the same as "git diff --diff-algorithm=patience".
As I wrote, that is absolutely the intended behaviour.  

When patience and other algorithm learns how to trade cycles off with output size, --minimal may make a difference, but unlike "--diff-algorithm=minimal" that forces Myers algorithm, the "--minimal" option should not change the underlying algorithm.

Thanks.
ydirson@free.fr· May 26, 2020, 16:56 UTC · re: Junio C Hamano · lore

Re: [BUG] diff algorithm selection issue

Hi Junio,
Show 12 quoted lines
> > When the config has diff.algorithm=patience set, "git diff
> > --minimal" seems to
> > be ignored, and does not give the same output as "git diff
> > --diff-algorithm=minimal",
> > but really the same as "git diff --diff-algorithm=patience".
> 
> As I wrote, that is absolutely the intended behaviour.
> 
> When patience and other algorithm learns how to trade cycles off
> with output size, --minimal may make a difference, but unlike
> "--diff-algorithm=minimal" that forces Myers algorithm, the
> "--minimal" option should not change the underlying algorithm.

OK, so then the problem is just in the doc, where --diff-algorithm=minimal should rather be documented as something like:

 The basic greedy "myers" diff algorithm, spending extra time to make
 sure the smallest possible diff is produced (equivalent to
 `--diff-algorithm=myers --minimal`).

Or is it rather intended to be `--diff-algorithm=default --minimal`, whatever the default may be in the future ?

As for the other flags, --patience and --histogram should probably documented as backward-compatibility aliases for --diff-algorithm=, right ?

I'll send a formal patch if all of this sounds good.

And as a last point, there would be the problem shown by patience diff on the commit referenced in my original post - If patience is still considered for promotion to default some day, I guess we wouldn't want it to make such a bad choice.

Best regards,
-- 
Yann
ydirson@free.fr· May 26, 2020, 17:21 UTC · re: ydirson@free.fr · lore

Re: [BUG] diff algorithm selection issue

Show 23 quoted lines
> > > When the config has diff.algorithm=patience set, "git diff
> > > --minimal" seems to
> > > be ignored, and does not give the same output as "git diff
> > > --diff-algorithm=minimal",
> > > but really the same as "git diff --diff-algorithm=patience".
> > 
> > As I wrote, that is absolutely the intended behaviour.
> > 
> > When patience and other algorithm learns how to trade cycles off
> > with output size, --minimal may make a difference, but unlike
> > "--diff-algorithm=minimal" that forces Myers algorithm, the
> > "--minimal" option should not change the underlying algorithm.
> 
> OK, so then the problem is just in the doc, where
> --diff-algorithm=minimal
> should rather be documented as something like:
> 
>  The basic greedy "myers" diff algorithm, spending extra time to make
>  sure the smallest possible diff is produced (equivalent to
>  `--diff-algorithm=myers --minimal`).
> 
> Or is it rather intended to be `--diff-algorithm=default --minimal`,
> whatever the default may be in the future ?

Now that I think about it, do we really want "minimal" as a valid choice for --diff-algorithm, if it's not a choice of algorithm ?

In that case, we may need a separate config option line diff.algorithm.minimal or maybe diff.algorithm.tuning ?

Show 21 quoted lines
> 
> 
> As for the other flags, --patience and --histogram should probably
> documented as backward-compatibility aliases for --diff-algorithm=,
> right ?
> 
> 
> I'll send a formal patch if all of this sounds good.
> 
> 
> And as a last point, there would be the problem shown by patience
> diff
> on the commit referenced in my original post - If patience is still
> considered for promotion to default some day, I guess we wouldn't
> want
> it to make such a bad choice.
> 
> Best regards,
> --
> Yann
> 
Junio C Hamano· May 26, 2020, 18:33 UTC · re: ydirson@free.fr · lore

Re: [BUG] diff algorithm selection issue

ydirson@free.fr writes:
Show 5 quoted lines
>> Or is it rather intended to be `--diff-algorithm=default --minimal`,
>> whatever the default may be in the future ?
>
> Now that I think about it, do we really want "minimal" as a valid choice
> for --diff-algorithm, if it's not a choice of algorithm ?

I asked the same question to myself before writing my first response but it is way too late to ask it now. I do support the spirit of "--minimal", but not "--diff-algorithm=minimal" which may be an ill-thought-out shorthand for "--diff-algorithm=default --minimal".

If you dig the list archive, I would imagine that you would find that not an insignificant part of list participant back then thought it was a good idea ;-)

← back to recent threads