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

[Phillip Wood <phillip.wood123@gmail.com>]

On 21/01/2026 20:51, Junio C Hamano wrote:
> "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

> 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

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

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