[RFH] xdiff shows trivially redundant diff.

$ git diff-tree -p 52e8a6^2 52d8a6 -- git-fetch.sh

shows a change that trivially is redundant, like this:

    diff --git a/git-fetch.sh b/git-fetch.sh
    index b4325d9..de4f011 100755
    --- a/git-fetch.sh
    +++ b/git-fetch.sh
    @@ -320,7 +320,7 @@ fetch_main () {
         ( : subshell because we muck with IFS
           IFS="    $LF"
           (
    -         git-fetch-pack $exec $keep "$remo...
    +         git-fetch-pack $exec $keep --thin...
           ) |
           while read sha1 remote_name
           do
    @@ -367,21 +367,26 @@ fetch_main "$reflist"

     # automated tag following
     case "$no_tags$tags" in
    -'')
    -       taglist=$(IFS=" " &&
    -       git-ls-remote $upload_pack --tags "$remote" |
    ...
    -       done)
    +'')
    +       case "$reflist" in
    +       *:refs/*)
    ...

Notice the first '-' and '+' lines of second hunk are identical?

There is another interesting thing.  This is running diff
between 52e8a6^2 and 52d8a6 blobs, but if I change them slightly
so that the first hunk is not different, then this anomaly
disappears.

On Sun, 2 Apr 2006, Junio C Hamano wrote:

$ git diff-tree -p 52e8a6^2 52d8a6 -- git-fetch.sh

shows a change that trivially is redundant, like this:

   diff --git a/git-fetch.sh b/git-fetch.sh
   index b4325d9..de4f011 100755
   --- a/git-fetch.sh
   +++ b/git-fetch.sh
   @@ -320,7 +320,7 @@ fetch_main () {
        ( : subshell because we muck with IFS
          IFS="    $LF"
          (
   -         git-fetch-pack $exec $keep "$remo...
   +         git-fetch-pack $exec $keep --thin...
          ) |
          while read sha1 remote_name
          do
   @@ -367,21 +367,26 @@ fetch_main "$reflist"

    # automated tag following
    case "$no_tags$tags" in
   -'')
   -       taglist=$(IFS=" " &&
   -       git-ls-remote $upload_pack --tags "$remote" |
   ...
   -       done)
   +'')
   +       case "$reflist" in
   +       *:refs/*)
   ...

Notice the first '-' and '+' lines of second hunk are identical?

There is another interesting thing.  This is running diff
between 52e8a6^2 and 52d8a6 blobs, but if I change them slightly
so that the first hunk is not different, then this anomaly
disappears.

Could you send me the two files that creates the above diff?


- Davide

Davide Libenzi [off-list ref] writes:

On Sun, 2 Apr 2006, Junio C Hamano wrote:

quoted

$ git diff-tree -p 52e8a6^2 52d8a6 -- git-fetch.sh

shows a change that trivially is redundant, like this:

   diff --git a/git-fetch.sh b/git-fetch.sh
   index b4325d9..de4f011 100755
   --- a/git-fetch.sh
   +++ b/git-fetch.sh
   @@ -320,7 +320,7 @@ fetch_main () {
..
Notice the first '-' and '+' lines of second hunk are identical?

There is another interesting thing.  This is running diff
between 52e8a6^2 and 52d8a6 blobs, but if I change them slightly
so that the first hunk is not different, then this anomaly
disappears.

Could you send me the two files that creates the above diff?

I should have tried your pristine xdiff code myself before
bothering you, but I haven't (sorry).

The problem is from the "stripped down" version we use in git,
so you may or may not see the problem in your version.  Attached
are the files.

On Sun, 2 Apr 2006, Junio C Hamano wrote:

I should have tried your pristine xdiff code myself before
bothering you, but I haven't (sorry).

It definitely happens with plain libxdiff-0.17 too.

In general, unless it's related to the "\ No newline" or the extra stuff 
on the "@@"-line, I'd be very surprised if we have any differences in the 
diff output wrt libxdiff-0.17. I was really pretty careful, and didn't 
change the code at all, just removed unnecessary files and functions.

		Linus

On Sun, 2 Apr 2006, Junio C Hamano wrote:

I should have tried your pristine xdiff code myself before
bothering you, but I haven't (sorry).

The problem is from the "stripped down" version we use in git,
so you may or may not see the problem in your version.  Attached
are the files.

Yes, it does even vanilla libxdiff ;) It's not a problem though, since it 
is created in xdl_cleanup_records() that tries to do a fast pass over the 
records to try to simplify the real diff operation. In trying to be fast, 
only hashes are compared, and it happens that the hash for "'')" collides 
with another one (try to replace one of the "'')" chars with another one). 
Why is this not a problem? Because what this lead to is only lines to be 
marked as changed, with a probability of about N/2^(8 * sizeof(long) - 1), 
even though they are not. And this happens only during sequential groups 
of lines changed, that is when the hash-colliding line is either at the 
begin or the end of the run.



- Davide

On Sun, 2 Apr 2006, Linus Torvalds wrote:

On Sun, 2 Apr 2006, Junio C Hamano wrote:

quoted

I should have tried your pristine xdiff code myself before
bothering you, but I haven't (sorry).

It definitely happens with plain libxdiff-0.17 too.

In general, unless it's related to the "\ No newline" or the extra stuff
on the "@@"-line, I'd be very surprised if we have any differences in the
diff output wrt libxdiff-0.17. I was really pretty careful, and didn't
change the code at all, just removed unnecessary files and functions.

So it does 0.18, that contains the "\ No newline" handling for text diff 
and patch. See my reply to Junio also.



- Davide

On Sun, 2 Apr 2006, Davide Libenzi wrote:

Yes, it does even vanilla libxdiff ;) It's not a problem though, since it is
created in xdl_cleanup_records() that tries to do a fast pass over the records
to try to simplify the real diff operation. In trying to be fast, only hashes
are compared, and it happens that the hash for "'')" collides with another one
(try to replace one of the "'')" chars with another one). Why is this not a
problem? Because what this lead to is only lines to be marked as changed, with
a probability of about N/2^(8 * sizeof(long) - 1), even though they are not.
And this happens only during sequential groups of lines changed, that is when
the hash-colliding line is either at the begin or the end of the run.

Hmm. It's still ugly, though. No possibility to have a "clean up identical 
initial and final lines" stage to get rid of extraneous bogus diffs?

I look at diffs a lot, and while this may be rare, if I were to end up 
having to wonder what the difference is and it turns out that it's just 
due to a libxdelta thing, I'd be a bit irritated and wish it gave me a 
proper diff..

		Linus

On Sun, 2 Apr 2006, Linus Torvalds wrote:

On Sun, 2 Apr 2006, Davide Libenzi wrote:

quoted

Yes, it does even vanilla libxdiff ;) It's not a problem though, since it is
created in xdl_cleanup_records() that tries to do a fast pass over the records
to try to simplify the real diff operation. In trying to be fast, only hashes
are compared, and it happens that the hash for "'')" collides with another one
(try to replace one of the "'')" chars with another one). Why is this not a
problem? Because what this lead to is only lines to be marked as changed, with
a probability of about N/2^(8 * sizeof(long) - 1), even though they are not.
And this happens only during sequential groups of lines changed, that is when
the hash-colliding line is either at the begin or the end of the run.

Hmm. It's still ugly, though. No possibility to have a "clean up identical
initial and final lines" stage to get rid of extraneous bogus diffs?

It does ;) If you make the second hunk (the one with the '') line) to be 
the first, the shrink-initial-and-final lines optimizations will make it 
eat the '') line.

I look at diffs a lot, and while this may be rare, if I were to end up
having to wonder what the difference is and it turns out that it's just
due to a libxdelta thing, I'd be a bit irritated and wish it gave me a
proper diff..

Tomorrow I'll take a look at it.


- Davide

On Sun, 2 Apr 2006, Davide Libenzi wrote:

Tomorrow I'll take a look at it.

Thanks. I've made the first "release" (2.6.17-rc1) with the new built-in 
diff, let's see if somebody has any issues.

But just the fact that I could do an almost 24MB diff (6MB compressed) 
with 738 _thousand_ lines in about 4 seconds is damn nice. The script I 
use to cut releases (logs, diffstats, tar-files etc) used to take a long 
time with BK, these days it's a couple of seconds.

		Linus

On Sun, 2 Apr 2006, Linus Torvalds wrote:

On Sun, 2 Apr 2006, Davide Libenzi wrote:

quoted

Tomorrow I'll take a look at it.

Thanks. I've made the first "release" (2.6.17-rc1) with the new built-in
diff, let's see if somebody has any issues.

No problem. That's only an eye-issue though, since the diff is still a 
valid diff according to its definition where D=A-B => B+D==A && A-D==B
From the day I released 0.18, xregression is continuosly running w/out any 
issue. I'll check it out though ...



- Davide

On Sun, 2 Apr 2006, Junio C Hamano wrote:

Davide Libenzi [off-list ref] writes:

quoted

On Sun, 2 Apr 2006, Junio C Hamano wrote:

quoted

$ git diff-tree -p 52e8a6^2 52d8a6 -- git-fetch.sh

shows a change that trivially is redundant, like this:

   diff --git a/git-fetch.sh b/git-fetch.sh
   index b4325d9..de4f011 100755
   --- a/git-fetch.sh
   +++ b/git-fetch.sh
   @@ -320,7 +320,7 @@ fetch_main () {
..
Notice the first '-' and '+' lines of second hunk are identical?

There is another interesting thing.  This is running diff
between 52e8a6^2 and 52d8a6 blobs, but if I change them slightly
so that the first hunk is not different, then this anomaly
disappears.

Could you send me the two files that creates the above diff?

I should have tried your pristine xdiff code myself before
bothering you, but I haven't (sorry).

The problem is from the "stripped down" version we use in git,
so you may or may not see the problem in your version.  Attached
are the files.

This is the change I made to libxdiff. Xregression already made a few 
thousands on iterations w/out problems.



- Davide

--- xdiff/xdiffi.c
+++ xdiff/xdiffi.c

@@ -349,12 +349,7 @@
  	kvdf += xe->xdf2.nreff + 1;
  	kvdb += xe->xdf2.nreff + 1;

-	/*
-	 * Classical integer square root approximation using shifts.
-	 */
-	xenv.mxcost = 1;
-	for (; ndiags; ndiags >>= 2)
-		xenv.mxcost <<= 1;
+	xenv.mxcost = xdl_bogosqrt(ndiags);
  	if (xenv.mxcost < XDL_MAX_COST_MIN)
  		xenv.mxcost = XDL_MAX_COST_MIN;
  	xenv.snake_cnt = XDL_SNAKE_CNT;


--- xdiff/xprepare.c
+++ xdiff/xprepare.c

@@ -25,6 +25,7 @@


  #define XDL_KPDIS_RUN 4
+#define XDL_MAX_EQLIMIT 1024

@@ -305,26 +306,48 @@


  static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {
-	long r, rdis, rpdis;
+	long r, rdis0, rpdis0, rdis1, rpdis1;

-	for (r = 1, rdis = 0, rpdis = 1; (i - r) >= s; r++) {
+	/*
+	 * Scans the lines before 'i' to find a run of lines that either
+	 * have no match (dis[j] == 0) or have multiple matches (dis[j] > 1).
+	 * Note that we always call this function with dis[i] > 1, so the
+	 * current line (i) is already a multimatch line.
+	 */
+	for (r = 1, rdis0 = 0, rpdis0 = 1; (i - r) >= s; r++) {
  		if (!dis[i - r])
-			rdis++;
+			rdis0++;
  		else if (dis[i - r] == 2)
-			rpdis++;
+			rpdis0++;
  		else
  			break;
  	}
-	for (r = 1; (i + r) <= e; r++) {
+	/*
+	 * If the run before the line 'i' found only multimatch lines, we
+	 * return 0 and hence we don't make the current line (i) discarded.
+	 * We want to discard multimatch lines only when they appear in the
+	 * middle of runs with nomatch lines (dis[j] == 0).
+	 */
+	if (rdis0 == 0)
+		return 0;
+	for (r = 1, rdis1 = 0, rpdis1 = 1; (i + r) <= e; r++) {
  		if (!dis[i + r])
-			rdis++;
+			rdis1++;
  		else if (dis[i + r] == 2)
-			rpdis++;
+			rpdis1++;
  		else
  			break;
  	}
+	/*
+	 * If the run after the line 'i' found only multimatch lines, we
+	 * return 0 and hence we don't make the current line (i) discarded.
+	 */
+	if (rdis1 == 0)
+		return 0;
+	rdis1 += rdis0;
+	rpdis1 += rpdis0;

-	return rpdis * XDL_KPDIS_RUN < (rpdis + rdis);
+	return rpdis1 * XDL_KPDIS_RUN < (rpdis1 + rdis1);
  }

@@ -334,34 +357,40 @@
   * might be potentially discarded if they happear in a run of discardable.
   */
  static int xdl_cleanup_records(xdfile_t *xdf1, xdfile_t *xdf2) {
-	long i, rhi, nreff;
+	long i, nm, rhi, nreff, mlim;
  	unsigned long hav;
  	xrecord_t **recs;
  	xrecord_t *rec;
  	char *dis, *dis1, *dis2;

-	if (!(dis = (char *) xdl_malloc((xdf1->nrec + xdf2->nrec + 2) * sizeof(char)))) {
+	if (!(dis = (char *) xdl_malloc(xdf1->nrec + xdf2->nrec + 2))) {

  		return -1;
  	}
-	memset(dis, 0, (xdf1->nrec + xdf2->nrec + 2) * sizeof(char));
+	memset(dis, 0, xdf1->nrec + xdf2->nrec + 2);
  	dis1 = dis;
  	dis2 = dis1 + xdf1->nrec + 1;

+	if ((mlim = xdl_bogosqrt(xdf1->nrec)) > XDL_MAX_EQLIMIT)
+		mlim = XDL_MAX_EQLIMIT;
  	for (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) {
  		hav = (*recs)->ha;
  		rhi = (long) XDL_HASHLONG(hav, xdf2->hbits);
-		for (rec = xdf2->rhash[rhi]; rec; rec = rec->next)
-			if (rec->ha == hav && ++dis1[i] == 2)
+		for (nm = 0, rec = xdf2->rhash[rhi]; rec; rec = rec->next)
+			if (rec->ha == hav && ++nm == mlim)
  				break;
+		dis1[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;
  	}

+	if ((mlim = xdl_bogosqrt(xdf2->nrec)) > XDL_MAX_EQLIMIT)
+		mlim = XDL_MAX_EQLIMIT;
  	for (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) {
  		hav = (*recs)->ha;
  		rhi = (long) XDL_HASHLONG(hav, xdf1->hbits);
-		for (rec = xdf1->rhash[rhi]; rec; rec = rec->next)
-			if (rec->ha == hav && ++dis2[i] == 2)
+		for (nm = 0, rec = xdf1->rhash[rhi]; rec; rec = rec->next)
+			if (rec->ha == hav && ++nm == mlim)
  				break;
+		dis2[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;
  	}

  	for (nreff = 0, i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart];


--- xdiff/xutils.c
+++ xdiff/xutils.c

@@ -29,6 +29,19 @@



+long xdl_bogosqrt(long n) {
+	long i;
+
+	/*
+	 * Classical integer square root approximation using shifts.
+	 */
+	for (i = 1; n > 0; n >>= 2)
+		i <<= 1;
+
+	return i;
+}
+
+
  int xdl_emit_diffrec(char const *rec, long size, char const *pre, long psize,
  		     xdemitcb_t *ecb) {
  	int i = 2;


--- xdiff/xutils.h
+++ xdiff/xutils.h

@@ -25,6 +25,7 @@



+long xdl_bogosqrt(long n);
  int xdl_emit_diffrec(char const *rec, long size, char const *pre, long psize,
  		     xdemitcb_t *ecb);
  int xdl_mmfile_outf(void *priv, mmbuffer_t *mb, int nbuf);