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

From: Phillip Wood <[email-masked]>
Date: Fri, 30 Jan 2026 16:06:10 +0000

On 30/01/2026 01:58, Yee Cheng Chin wrote:
> 
> Case #1 happens when no *remaining* shifting was necessary, but note
> that this happens after the do/while loop above, where previous loops
> could have shifted and compacted the diff blocks already. Case #2 just
> means there's some remaining clean up work to be done.

That's a good point - as well as commenting the new code, it would be 
helpful to update the comment in case #1 to make it clear that we don't 
need to shift back up to align with a matching block, not there there 
was no shift possible. I agree with Junio that it would be useful to add 
the example below as a test

Thanks

Phillip

> Just for a concrete test case that will illustrate this in case
> someone is running the code and want a demonstration:
> 
> File 1:
> AXB*
> 
> File 2:
> CD*XE*
> 
> The first "*" is used as the histogram alignment anchor, which will be
> shifted resulting in a compaction, and therefore needs to trigger a
> re-diff. The correct output is as follows (which will only happen if
> we also run the re-diff in case #1):
> 
> {-A-}[+CD*+]X{-B-}[+E+]*
> 
> Otherwise we will get the wrong output (note how the "X" is
> erroneuously included on both sides):
> 
> {-AXB-}[+CD*XE+]*
> 
> Because of that, I'm leaning on keeping the current code structure,
> because it *is* indeed a cleanup step to be run after the previous
> one. I could still refactor it into a separate function and put it
> into the the case #1/#2 if blocks if you think that's cleaner.
> 
> I will also add the above to the test case in v2.
>