Re: [PATCH v2] xdiff: re-diff shifted change groups when using histogram algorithm
- From
Junio C Hamano <gitster@pobox.com>
- Date
- Mar 13, 2026, 07:07 UTC
- Message-ID
- <xmqqikb08ax3.fsf@gitster.g>
- In-Reply-To
- <pull.2120.v2.git.git.1772463265865.gitgitgadget@gmail.com>
"Yee Cheng Chin via GitGitGadget" <gitgitgadget@gmail.com> writes:
Show 33 quoted lines
> 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'.