Re: [PATCH] xdiff: re-diff shifted change groups when using histogram algorithm
- From
Junio C Hamano <gitster@pobox.com>
- Date
- Jan 21, 2026, 20:51 UTC
- Message-ID
- <xmqqikcusn8p.fsf@gitster.g>
- In-Reply-To
- <pull.2120.git.git.1765054287938.gitgitgadget@gmail.com>
"Yee Cheng Chin via GitGitGadget" <gitgitgadget@gmail.com> writes:
Show 5 quoted lines
> When using Myer's diff, the algorithm finds that only the "x" has been
> changed, and produces a final diff result (these are line diffs, but
> using word-diff syntax for ease of presentation):
>
> A A[-A-]{+x+}A AAAAnd patience gives the same result; as you noted, it uses a unique line as the anchoring point.
Show 14 quoted lines
> When using histogram diff, the algorithm first discovers the LCS "A
> AAA", which it uses as anchor, then produces an intermediate diff:
>
> {+A Ax+}A AAA[- AAA-].
>
> This is a longer diff than Myer's, but it's still self-consistent.
> However, the compaction phase attempts to shift the first file's diff
> group upwards (note that this shift crosses the anchor that histogram
> had used), leading to the final results for histogram diff:
>
> [-A AA-]{+A Ax+}A AAA
>
> This is a technically correct patch but looks clearly redundant to a
> human as the first 3 lines should not be in the diff.So true.
Show 6 quoted lines
> The fix would detect that a shift has caused matching to a new group,
> and re-diff the "A AA" and "A Ax" parts, which results in "A A"
> correctly re-marked as unchanged. This creates the now correct histogram
> diff:
>
> A A[-A-]{+x+}A AAAOK.
Show 6 quoted lines
> This issue is rare in a normal repository. Below is a table of > repositories (`git log --no-merges -p --histogram -1000`), showing how > many times a re-diff was done and how many times it resulted in finding > matching lines (therefore addressing this issue) with the fix. In > general it is fewer than 1% of diff's that exhibit this offending > behavior:
In other words, without the fix, we'd see 1% or so commits with suboptimal (or "funny looking") diff that will trigger bug reports, which sounds like an unacceptably high failure rate.
Show 27 quoted lines
> @@ -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)?
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.
Thanks.
Show 21 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));
> +
> + 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