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

From: Phillip Wood <phillip.wood123@gmail.com>
Date: Jan 30, 2026, 16:06 UTC
Message-ID: <b66b8781-a826-44e0-9a2b-2c3a57547f06@gmail.com>
In-Reply-To: <CAHTeOx-TLwqbcdGcb2drD4vE6D3M93EPMjcAeTNR+XNTbmTVZg@mail.gmail.com>

On 30/01/2026 01:58, Yee Cheng Chin wrote:

Show 5 quoted lines

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

Show 28 quoted lines

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