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

From: Yee Cheng Chin <ychin.git@gmail.com>
Date: Jan 30, 2026, 01:58 UTC
Message-ID: <CAHTeOx-TLwqbcdGcb2drD4vE6D3M93EPMjcAeTNR+XNTbmTVZg@mail.gmail.com>
In-Reply-To: <xmqqsebo9lv6.fsf@gitster.g>

On Thu, Jan 29, 2026 at 12:58 PM Junio C Hamano <gitster@pobox.com> wrote:

Show 35 quoted lines

>
> Yee Cheng Chin <ychin.git@gmail.com> writes:
> >
> > On Wed, Jan 21, 2026 at 12:51 PM Junio C Hamano <gitster@pobox.com> wrote:
> >> By the way, this appears after the if/else if/ cascade that has:
> >>
> >>         if (g.end == earliest_end) {
> >>                 ... do nothing case (case #1)
> >>         } else if (end_matching_other != -1) {
> >>                 ... do the slide-up thing (case #2)
> >>         } else if (flags & XDF_INDENT_HEIRISTIC) {
> >>                 ... do the indent heuristic thing (case #3)
> >>         }
> >>
> >> Am I reading the code correctly that, even though this new block
> >> appears as if it is a post-clean-up phase that is independent from
> >> which one of the three choices are taken in the previous if/elseif
> >> cascade, it only is relevant to the second case?  I am wondering if
> >> it would make it easier to follow if the new code were made into a
> >> small helper function that is called from the (case #2) arm of the
> >> existing if/else if cascade.
> >
> > That's correct. This condition happens only in the 2nd case. The
> > problematic scenario here only happens when the opposite side is
> > non-empty. If the opposite is empty (case #3, where we run the indent
> > heuristic algorithm), there's simply no need to re-diff anything
> > because diff'ing against an empty hunk is pointless.
>
> OK.  In the version posted, it appeard that it is possible, after
> not doing the slide-up thing but using indent heuristic thing, to
> fall into this compensation codepath because the new code was placed
> after the above if-else-if cascade as if it is an independent
> clean-up phase.  Encapsulating that new code in a helper function
> and calling it at the end of "do the slide-up thing" block will make
> the intent clearer.

Sorry, I actually misspoke. I forgot that re-diff is actually needed in both case #1 and #2. Note that even in #1, it's possible for `end_matching_other != -1` to be true. In case #3, it only cannot happen because `end_matching_other` has to be -1 by then (meaning that this diff hunk only has content on this side and is empty on the other).

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.

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.