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

[Junio C Hamano <gitster@pobox.com>]

"Yee Cheng Chin via GitGitGadget" <gitgitgadget@gmail.com> writes:

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

And patience gives the same result; as you noted, it uses a unique
line as the anchoring point.

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

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

OK.

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

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


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