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

[Phillip Wood <phillip.wood123@gmail.com>]

On 13/03/2026 07:07, Junio C Hamano wrote:
> "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.

Yes, sorry for the slow response. I agree with Junio that this is 
explained well and looks good

Thanks

Phillip

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