[RFH] shifting xdiff hunks?

[RFH] shifting xdiff hunks?

[Junio C Hamano]

I was looking at one diff produced from my work-in-progress,
which looked like this...

    diff --git a/Documentation/git.txt b/Documentation/git.txt
    index 06b2e53..f72abfc 100644
    --- a/Documentation/git.txt
    +++ b/Documentation/git.txt
    @@ -265,6 +265,9 @@ gitlink:git-checkout[1]::
     gitlink:git-cherry-pick[1]::
            Cherry-pick the effect of an existing commit.

    +gitlink:git-clean[1]::
    +       Remove untracked files from the working tree.
    +
     gitlink:git-clone[1]::
            Clones a repository into a new directory.

    @@ -318,6 +321,9 @@ gitlink:git-resolve[1]::

     gitlink:git-revert[1]::
            Revert an existing commit.
    +
    +gitlink:git-rm[1]::
    +       Remove files from the working tree and from the index.

     gitlink:git-shortlog[1]::
            Summarizes 'git log' output.

The first hunk begins by an addition of a couple of non-blank
line followed by an addition of a blank line.  The second hunk,
while it does the same thing, is shown differently.

Now, from correctness point of view, this is not a problem at
all, but I am wondering if xdiff can help to always shift the
hunk down or up to consistently produce one way or another
(personally I feel the former is easier to read).

Here is a rough sketch of what I think I want.  When we have
additions, as long as the first line added happens to match the
first line that is common between the versions that comes after
the added hunk (that is, in the case of the second hunk above,
the empty line before "gitlink:git-rm[1]" happens to match the
empty line after the added three lines), roll the hunk down by
one, until you cannot roll it down anymore.

Just in case I get misinterpreted, I am not talking about
treating empty lines in any special way.  It is more about
"starting the hunk with actually changed line".  The first hunk
above clearly begins with something added, while the second one
does not.

Is this something easy to do with the xdiff code?

Re: [RFH] shifting xdiff hunks?

[Davide Libenzi]

On Wed, 12 Apr 2006, Junio C Hamano wrote:

> The first hunk begins by an addition of a couple of non-blank
> line followed by an addition of a blank line.  The second hunk,
> while it does the same thing, is shown differently.
>
> Now, from correctness point of view, this is not a problem at
> all, but I am wondering if xdiff can help to always shift the
> hunk down or up to consistently produce one way or another
> (personally I feel the former is easier to read).

Next on your screens, Junio and Linus in the new commedy "Pickier and Pickiest" :)



> Here is a rough sketch of what I think I want.  When we have
> additions, as long as the first line added happens to match the
> first line that is common between the versions that comes after
> the added hunk (that is, in the case of the second hunk above,
> the empty line before "gitlink:git-rm[1]" happens to match the
> empty line after the added three lines), roll the hunk down by
> one, until you cannot roll it down anymore.
>
> Just in case I get misinterpreted, I am not talking about
> treating empty lines in any special way.  It is more about
> "starting the hunk with actually changed line".  The first hunk
> above clearly begins with something added, while the second one
> does not.
>
> Is this something easy to do with the xdiff code?

Yes, this is what GNU diff does. It's a post-process of the edit script. 
Not a problem at all. Till this weekend (included) I'm pretty booked, but 
I'll do that in the following days.



- Davide

Re: [RFH] shifting xdiff hunks?

[Jakub Narebski]

Junio C. Hamano wrote:
 
> Now, from correctness point of view, this is not a problem at
> all, but I am wondering if xdiff can help to always shift the
> hunk down or up to consistently produce one way or another
> (personally I feel the former is easier to read).

This would also help with adding new functions, as sometimes diff begins
with the closing brace of the preceding function, instead of ending with
closing brace of the added function.

Just my own 0.2 eurocents.

-- 
Jakub Narebski
Warsaw, Poland

Re: [RFH] shifting xdiff hunks?

[Davide Libenzi]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 419 bytes --]

On Wed, 12 Apr 2006, Davide Libenzi wrote:

> Yes, this is what GNU diff does. It's a post-process of the edit script. Not 
> a problem at all. Till this weekend (included) I'm pretty booked, but I'll do 
> that in the following days.

Dang, that was a short weekend. I found a lunch-time hour for this. Would 
you try to see if this libxdiff-based diff merges on your tree?
See also how it looks for you.



- Davide


[-- Attachment #2: Type: TEXT/plain, Size: 4294 bytes --]

--- a/xdiffi.c
+++ b/xdiffi.c
@@ -45,6 +45,8 @@
 		      long *kvdf, long *kvdb, int need_min, xdpsplit_t *spl,
 		      xdalgoenv_t *xenv);
 static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1, long chg2);
+static int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo);
+
 
 
 
@@ -394,6 +396,110 @@
 }
 
 
+static int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo) {
+	long ix, ixo, ixs, ixref, grpsiz, nrec = xdf->nrec;
+	char *rchg = xdf->rchg, *rchgo = xdfo->rchg;
+	xrecord_t **recs = xdf->recs;
+
+	/*
+	 * This is the same of what GNU diff does. Move back and forward
+	 * change groups for a consistent and pretty diff output. This also
+	 * helps in finding joineable change groups and reduce the diff size.
+	 */
+	for (ix = ixo = 0;;) {
+		/*
+		 * Find the first changed line in the to-be-compacted file.
+		 * We need to keep track of both indexes, so if we find a
+		 * changed lines group on the other file, while scanning the
+		 * to-be-compacted file, we need to skip it properly. Note
+		 * that loops that are testing for changed lines on rchg* do
+		 * not need index bounding since the array is prepared with
+		 * a zero at position -1 and N.
+		 */
+		for (; ix < nrec && !rchg[ix]; ix++)
+			while (rchgo[ixo++]);
+		if (ix == nrec)
+			break;
+
+		/*
+		 * Record the start of a changed-group in the to-be-compacted file
+		 * and find the end of it, on both to-be-compacted and other file
+		 * indexes (ix and ixo).
+		 */
+		ixs = ix;
+		for (ix++; rchg[ix]; ix++);
+		for (; rchgo[ixo]; ixo++);
+
+		do {
+			grpsiz = ix - ixs;
+
+			/*
+			 * If the line before the current change group, is equal to
+			 * the last line of the current change group, shift backward
+			 * the group.
+			 */
+			while (ixs > 0 && recs[ixs - 1]->ha == recs[ix - 1]->ha &&
+			       XDL_RECMATCH(recs[ixs - 1], recs[ix - 1])) {
+				rchg[--ixs] = 1;
+				rchg[--ix] = 0;
+
+				/*
+				 * This change might have joined two change groups,
+				 * so we try to take this scenario in account by moving
+				 * the start index accordingly (and so the other-file
+				 * end-of-group index).
+				 */
+				for (; rchg[ixs - 1]; ixs--);
+				while (rchgo[--ixo]);
+			}
+
+			/*
+			 * Record the end-of-group position in case we are matched
+			 * with a group of changes in the other file (that is, the
+			 * change record before the enf-of-group index in the other
+			 * file is set).
+			 */
+			ixref = rchgo[ixo - 1] ? ix: nrec;
+
+			/*
+			 * If the first line of the current change group, is equal to
+			 * the line next of the current change group, shift forward
+			 * the group.
+			 */
+			while (ix < nrec && recs[ixs]->ha == recs[ix]->ha &&
+			       XDL_RECMATCH(recs[ixs], recs[ix])) {
+				rchg[ixs++] = 0;
+				rchg[ix++] = 1;
+
+				/*
+				 * This change might have joined two change groups,
+				 * so we try to take this scenario in account by moving
+				 * the start index accordingly (and so the other-file
+				 * end-of-group index). Keep tracking the reference
+				 * index in case we are shifting together with a
+				 * corresponding group of changes in the other file.
+				 */
+				for (; rchg[ix]; ix++);
+				while (rchgo[++ixo])
+					ixref = ix;
+			}
+		} while (grpsiz != ix - ixs);
+
+		/*
+		 * Try to move back the possibly merged group of changes, to match
+		 * the recorded postion in the other file.
+		 */
+		while (ixref < ix) {
+			rchg[--ixs] = 1;
+			rchg[--ix] = 0;
+			while (rchgo[--ixo]);
+		}
+	}
+
+	return 0;
+}
+
+
 int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) {
 	xdchange_t *cscr = NULL, *xch;
 	char *rchg1 = xe->xdf1.rchg, *rchg2 = xe->xdf2.rchg;
@@ -439,13 +545,13 @@
 
 		return -1;
 	}
-
-	if (xdl_build_script(&xe, &xscr) < 0) {
+	if (xdl_change_compact(&xe.xdf1, &xe.xdf2) < 0 ||
+	    xdl_change_compact(&xe.xdf2, &xe.xdf1) < 0 ||
+	    xdl_build_script(&xe, &xscr) < 0) {
 
 		xdl_free_env(&xe);
 		return -1;
 	}
-
 	if (xscr) {
 		if (xdl_emit_diff(&xe, xscr, ecb, xecfg) < 0) {
 
@@ -453,10 +559,8 @@
 			xdl_free_env(&xe);
 			return -1;
 		}
-
 		xdl_free_script(xscr);
 	}
-
 	xdl_free_env(&xe);
 
 	return 0;

Re: [RFH] shifting xdiff hunks?

[Junio C Hamano]

Davide Libenzi <davidel@xmailserver.org> writes:

> On Wed, 12 Apr 2006, Davide Libenzi wrote:
>
>> Yes, this is what GNU diff does. It's a post-process of the edit
>> script. Not a problem at all. Till this weekend (included) I'm
>> pretty booked, but I'll do that in the following days.
>
> Dang, that was a short weekend. I found a lunch-time hour for
> this. Would you try to see if this libxdiff-based diff merges on your
> tree?
> See also how it looks for you.

Very impressed, and pleased with the result.  I've only taken a
cursory look, but with a very limited number of tests, it looks
much better.  Thanks.

For the sake of full disclosure, the reason I wanted consistency
was not for the diff output I quoted earlier, but to help making
the combined patch output cleaner.  It does reduce false match
from the infamous 12-way Octopus by Len Brown:

	git diff-tree --cc 9fdb62af92c741addbea15545f214a6e89460865