From: Yee Cheng Chin Date: Thu, 19 Mar 2026 23:30:08 GMT Subject: Re: [PATCH v2] xdiff: re-diff shifted change groups when using histogram algorithm Message-ID: In-Reply-To: <016df393-a36f-4e5e-ab6a-eb661f5c84cc@gmail.com> Great. Sounds good, thanks! On Fri, Mar 13, 2026 at 3:23 AM Phillip Wood wrote: > > On 13/03/2026 07:07, Junio C Hamano wrote: > > "Yee Cheng Chin via GitGitGadget" writes: > > > >> From: Yee Cheng Chin > >> > >> 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 > >> --- > > > > 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'. > > >