Re: [PATCH] xdiff: re-diff shifted change groups when using histogram algorithm
- From
- Phillip Wood <phillip.wood123@gmail.com>
- Date
- Jan 24, 2026, 10:54 UTC
- Message-ID
- <4fa413ae-f2a4-4de2-a2fb-0b1db379750b@gmail.com>
- In-Reply-To
- <xmqqikcusn8p.fsf@gitster.g>
On 21/01/2026 20:51, Junio C Hamano wrote:
Show 35 quoted lines
> "Yee Cheng Chin via GitGitGadget" <gitgitgadget@gmail.com> writes:
>
>> @@ -915,6 +919,45 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
>> }
>> }
>>
>> + /*
>> + * If this has a matching group from the other file, it could
>> + * either be the original match from the diff algorithm, or
>> + * arrived at by shifting and joining groups. When it's the
>> + * latter, it's possible for the two newly joined sides to have
>> + * matching lines. Re-diff the group to mark these matching
>> + * lines as unchanged and remove from the diff output.
>> + *
>> + * Only do this for histogram diff as its LCS algorithm makes
>> + * this scenario possible. In contrast, patience diff finds LCS
>> + * of unique lines that groups cannot be shifted across.
>> + * Myer's diff (standalone or used as fall-back in patience
>> + * diff) already finds minimal edits so it is not possible for
>> + * shifted groups to result in a smaller diff. (Without
>> + * XDF_NEED_MINIMAL, Myer's isn't technically guaranteed to be
>> + * minimal, but it should be so most of the time)
>> + */
>> + if (end_matching_other != -1 &&
>> + XDF_DIFF_ALG(flags) == XDF_HISTOGRAM_DIFF &&
>> + (g.start != g_orig.start ||
>> + g.end != g_orig.end ||
>> + go.start != go_orig.start ||
>> + go.end != go_orig.end)) {
>
> So the idea is to remember the original values in g and go (the
> location of the group in the file and the other file) and if
> shifting up and down changed any one of the four ends from the
> original locations, we always take the fall-back route (if we are
> doing histogram)?I'm a bit confused why we need to check both groups. I think they're supposed to move together (if we move "g" by n context lines we also move "go" by n context lines) so I can't see how we can have
g.start == g_orig.start && g.end == g_orig.end
when
go.start != go.orig.start || go.end != go_orig.end
Show 17 quoted lines
> 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 a good point
Show 8 quoted lines
>> + xpparam_t xpp; >> + xdfenv_t xe; >> + >> + memset(&xpp, 0, sizeof(xpp)); >> + xpp.flags = flags & ~XDF_DIFF_ALGORITHM_MASK; >> + >> + memcpy(&xe.xdf1, xdf, sizeof(xdfile_t)); >> + memcpy(&xe.xdf2, xdfo, sizeof(xdfile_t));
These would be safer as "xe.xdf1 = *xdf" so we don't have to worry about getting the size correct (sizeof(*xdf) would also be safer but there is no need for memcpy() here).
I also wondered if we need to do a diff or if we can just mark the common prefix and suffix as unchanged but I suspect that wont will work for more complicated examples.
Thanks
Phillip
Show 14 quoted lines
>> +
>> + if (xdl_fall_back_diff(&xe, &xpp,
>> + g.start + 1, g.end - g.start,
>> + go.start + 1, go.end - go.start)) {
>> + return -1;
>> + }
>> + }
>> +
>> next:
>> /* Move past the just-processed group: */
>> if (group_next(xdf, &g))
>>
>> base-commit: f0ef5b6d9bcc258e4cbef93839d1b7465d5212b9
>