Re: [PATCH v2] xdiff: re-diff shifted change groups when using histogram algorithm

[Junio C Hamano <gitster@pobox.com>]

"Yee Cheng Chin via GitGitGadget" <gitgitgadget@gmail.com> writes:

> From: Yee Cheng Chin <ychin.git@gmail.com>
>
> After a diff algorithm has been run, the compaction phase
> (xdl_change_compact()) shifts and merges change groups to produce a
> cleaner output. However, this shifting could create a new matched group
> where both sides now have matching lines. This results in a
> wrong-looking diff output which contains redundant lines that are the
> same on both files.
>
> Fix this by detecting this situation, and re-diff the texts on each side
> to find similar lines, using the fall-back Myer's diff. Only do this for
> histogram diff as it's the only algorithm where this is relevant. Below
> contains an example, and more details.
> ...
> This issue is rare in a normal repository. Below is a table of
> repositories (`git log --no-merges -p --histogram -1000`), showing how
> many times a re-diff was done and how many times it resulted in finding
> matching lines (therefore addressing this issue) with the fix. In
> general it is fewer than 1% of diff's that exhibit this offending
> behavior:
>
> | Repo (1k commits)  | Re-diff | Found matching lines |
> |--------------------|---------|----------------------|
> | llvm-project       |  45     | 11                   |
> | vim                | 110     |  9                   |
> | git                |  18     |  2                   |
> | WebKit             | 168     |  1                   |
> | ripgrep            |  22     |  1                   |
> | cpython            |  32     |  0                   |
> | vscode             |  13     |  0                   |
>
> Signed-off-by: Yee Cheng Chin <ychin.git@gmail.com>
> ---

Thanks for the updated patch, and sorry for nobody responding to the
patch for over a week.

The detailed explanation of the issue and the inclusion of the
repository analysis results are very helpful; they clearly show that
while this is a rare edge case, it significantly improves the
quality of histogram diffs when it does occur.

 - The removal of go_orig is correct since g and go are kept in sync 
   throughout the slide loops.

 - Clearing the algorithm mask while preserving other flags ensures that 
   user-provided options like --ignore-all-space are correctly applied 
   during the re-diff.

 - While ignore_regex and anchors are not passed to the sub-diff, they 
   aren't currently available to xdl_change_compact anyway. Given that 
   compaction happens before regex filtering in the main pipeline, this
   is OK, I guess.

Let me mark the topic for 'next'.