[PATCH] Re-re-re-fix common tail optimization

Jeff King [off-list ref] writes:

No, I think it's right as-is. We forget about the blocks during the
recovery section of the code. IOW, we just keep reading forward until we
find all of the context lines, or we run out of trimmed content. In the
first case, we are fine (we restored the right number of context lines).
In the latter case, we are also fine, because we end up trimming nothing
(IOW, there _weren't_ enough context lines in the first place).

Kind'a embarrassing that both of us cannot get this right without so
many rounds, isn't it?

-- >8 --
Subject: [PATCH] Re-re-re-fix common tail optimization

We need to be extra careful recovering the removed common section, so
that we do not break context nor the changed incomplete line (i.e. the
last line that does not end with LF).

Signed-off-by: Junio C Hamano <redacted>
---

 t/t4024-diff-optimize-common.sh |   69 +++++++++++++++++++++++++++++++++++++++
 xdiff-interface.c               |    2 +-
 2 files changed, 70 insertions(+), 1 deletions(-)

diff --git a/t/t4024-diff-optimize-common.sh b/t/t4024-diff-optimize-common.sh
new file mode 100755
index 0000000..10405f1
--- /dev/null
+++ b/t/t4024-diff-optimize-common.sh

@@ -0,0 +1,69 @@
+#!/bin/sh
+
+test_description='common tail optimization'
+
+. ./test-lib.sh
+
+z=zzzzzzzz ;# 8
+z="$z$z$z$z$z$z$z$z" ;# 64
+z="$z$z$z$z$z$z$z$z" ;# 512
+z="$z$z$z$z" ;# 2048
+z2047=$(expr "$z" : '.\(.*\)') ; #2047
+
+test_expect_success setup '
+
+	echo "a$z2047" >file-a &&
+	echo "b" >file-b &&
+	echo "$z2047" >>file-b &&
+	echo "c$z2047" | tr -d "\012" >file-c &&
+	echo "d" >file-d &&
+	echo "$z2047" | tr -d "\012" >>file-d &&
+
+	git add file-a file-b file-c file-d &&
+
+	echo "A$z2047" >file-a &&
+	echo "B" >file-b &&
+	echo "$z2047" >>file-b &&
+	echo "C$z2047" | tr -d "\012" >file-c &&
+	echo "D" >file-d &&
+	echo "$z2047" | tr -d "\012" >>file-d
+
+'
+
+echo >expect <<\EOF
+diff --git a/file-a b/file-a
+--- a/file-a
++++ b/file-a
+@@ -1 +1 @@
+-aZ
++AZ
+diff --git a/file-b b/file-b
+--- a/file-b
++++ b/file-b
+@@ -1 +1 @@
+-b
++B
+diff --git a/file-c b/file-c
+--- a/file-c
++++ b/file-c
+@@ -1 +1 @@
+-cZ
+\ No newline at end of file
++CZ
+\ No newline at end of file
+diff --git a/file-d b/file-d
+--- a/file-d
++++ b/file-d
+@@ -1 +1 @@
+-d
++D
+EOF
+
+test_expect_success 'diff -U0' '
+
+	git diff -U0 | sed -e "/^index/d" -e "s/$z2047/Z/g" >actual &&
+	diff -u expect actual
+
+'
+
+test_done

diff --git a/xdiff-interface.c b/xdiff-interface.c
index 98b02ed..9ee877c 100644
--- a/xdiff-interface.c
+++ b/xdiff-interface.c

@@ -121,7 +121,7 @@ static void trim_common_tail(mmfile_t *a, mmfile_t *b, long ctx)
 		bp -= blk;
 	}
 
-	while (recovered < trimmed && ctx)
+	while (recovered < trimmed && 0 <= ctx)
 		if (ap[recovered++] == '\n')
 			ctx--;
 	a->size -= (trimmed - recovered);

On Sun, Dec 16, 2007 at 01:49:17PM -0800, Junio C Hamano wrote:

Kind'a embarrassing that both of us cannot get this right without so
many rounds, isn't it?

Good thing we can just delete the emails and nobody will be the wiser...

+echo >expect <<\EOF

This would probably work better as 'cat'.

+test_expect_success 'diff -U0' '
+
+	git diff -U0 | sed -e "/^index/d" -e "s/$z2047/Z/g" >actual &&
+	diff -u expect actual

Aren't we using "git diff" for the second diff there nowadays?

-	while (recovered < trimmed && ctx)
+	while (recovered < trimmed && 0 <= ctx)
 		if (ap[recovered++] == '\n')
 			ctx--;
 	a->size -= (trimmed - recovered);

Oops (I think maybe I misunderstood what you were asking in the last
email). This fix is correct, though the code is now kind of subtle. I
think it would be more obvious as:

  /* finish off any changed line we are in */
  while (recovered < trimmed && ap[recovered++] != '\n')
    /* nothing */;
  /* recover context lines */
  while (recovered < trimmed && ctx)
    if (ap[recovered++] == '\n')
      ctx--;

Your loop does both actions in the same loop, which is correct, but took
me 10 minutes of thinking and staring to realize what was going on.

-Peff

On Sun, Dec 16, 2007 at 01:49:17PM -0800, Junio C Hamano wrote:

Kind'a embarrassing that both of us cannot get this right without so
many rounds, isn't it?

-- >8 --
Subject: [PATCH] Re-re-re-fix common tail optimization

We need to be extra careful recovering the removed common section, so
that we do not break context nor the changed incomplete line (i.e. the
last line that does not end with LF).

Signed-off-by: Junio C Hamano <redacted>

Just to add to the woe on this one, this test breaks on MacOS X due to
the pattern length limitations of the default sed on that platform.

Interested in a patch?

Charles.

On Wed, Dec 19, 2007 at 02:18:45PM +0000, Charles Bailey wrote:

Just to add to the woe on this one, this test breaks on MacOS X due to
the pattern length limitations of the default sed on that platform.

Interested in a patch?

Somebody beat you to it. :) Can you confirm that the fix in

  [off-list ref]

works for you?

-Peff

On Wed, Dec 19, 2007 at 09:27:15AM -0500, Jeff King wrote:

On Wed, Dec 19, 2007 at 02:18:45PM +0000, Charles Bailey wrote:

quoted

Just to add to the woe on this one, this test breaks on MacOS X due to
the pattern length limitations of the default sed on that platform.

Interested in a patch?

Somebody beat you to it. :) Can you confirm that the fix in

  [off-list ref]

works for you?

-Peff

Ooh, the excitement, I've never had the opportunity to "git am"
before.

Yes, I can confirm.  It works for me.

For reference I had the following, which is fewer lines but not
inherently better in any other way.

Charles.

diff --git a/t/t4024-diff-optimize-common.sh b/t/t4024-diff-optimize-common.sh
index 20fe87b..ffb2c8f 100755
--- a/t/t4024-diff-optimize-common.sh
+++ b/t/t4024-diff-optimize-common.sh

@@ -7,8 +7,9 @@ test_description='common tail optimization'
 z=zzzzzzzz ;# 8
 z="$z$z$z$z$z$z$z$z" ;# 64
 z="$z$z$z$z$z$z$z$z" ;# 512
-z="$z$z$z$z" ;# 2048
-z2047=$(expr "$z" : '.\(.*\)') ; #2047
+z="$z$z" ;# 1024
+z1023=$(expr "$z" : '.\(.*\)') ; #1023
+z2047=$z$z1023
 
 test_expect_success setup '
 

@@ -35,8 +36,8 @@ diff --git a/file-a b/file-a
 --- a/file-a
 +++ b/file-a
 @@ -1 +1 @@
--aZ
-+AZ
+-aZZz
++AZZz
 diff --git a/file-b b/file-b
 --- a/file-b
 +++ b/file-b

@@ -47,9 +48,9 @@ diff --git a/file-c b/file-c
 --- a/file-c
 +++ b/file-c
 @@ -1 +1 @@
--cZ
+-cZZz
 \ No newline at end of file
-+CZ
++CZZz
 \ No newline at end of file
 diff --git a/file-d b/file-d
 --- a/file-d

@@ -61,7 +62,7 @@ EOF
 
 test_expect_success 'diff -U0' '
 
-	git diff -U0 | sed -e "/^index/d" -e "s/$z2047/Z/g" >actual &&
+	git diff -U0 | sed -e "/^index/d" -e "s/$z1023/Z/g" >actual &&
 	diff -u expect actual
 
 '

-- 
1.5.3.7.11.ga3d7

Charles Bailey [off-list ref] writes:

On Wed, Dec 19, 2007 at 09:27:15AM -0500, Jeff King wrote:
...

quoted

Somebody beat you to it. :) Can you confirm that the fix in

  [off-list ref]

works for you?

Ooh, the excitement, I've never had the opportunity to "git am"
before.

Well, if Wincent had sent the patch as plain text without MIME
quoted-printable, you did not have to even have the excitement of
running "git am", but a simple "git apply" would have sufficed.

    ...
    How about the following? This swaps in perl in place of sed, which we c=
    an
    hopefully rely upon to work across platforms.

    Cheers,
    Wincent

    -------- 8< --------
    =46ix tests for broken sed on Leopard

    The newly-added common-tail-optimization test fails on Leopard because
    the broken sed implementation bails with a spurious "unterminated
    substitute pattern" error because of the length of one of the
    arguments.

Just for future reference, I do not mind avoiding "top-post" style patch
using "-- >8 --" cut markers, but do not have three or more dashes in
the cut marker.  "mailinfo" will split the message at that line and the
portion intended as the proposed commit log message will be taken as
part of garbage in front of the patch.  Using "-- >8 --" (two dashes,
space, scissors, ...) keeps both the front matter and the log text
together so that "am -i" or "commit --amend" can work on both parts.


By the way, how does this rewrite look?

-- >8 --
t4024: fix test script to use simpler sed pattern

The earlier test stripped away expected number of 'z' but the output
would have been very hard to read once somebody broke the common tail
optimization.  Instead, count the number of 'z' and show it, to help
diagnosing the problem better in the future.

Signed-off-by: Junio C Hamano <redacted>
---

 t/t4024-diff-optimize-common.sh |  158 ++++++++++++++++++++++++++++++---------
 1 files changed, 123 insertions(+), 35 deletions(-)

diff --git a/t/t4024-diff-optimize-common.sh b/t/t4024-diff-optimize-common.sh
index 20fe87b..3c66102 100755
--- a/t/t4024-diff-optimize-common.sh
+++ b/t/t4024-diff-optimize-common.sh

@@ -10,58 +10,146 @@ z="$z$z$z$z$z$z$z$z" ;# 512
 z="$z$z$z$z" ;# 2048
 z2047=$(expr "$z" : '.\(.*\)') ; #2047
 
-test_expect_success setup '
-
-	echo "a$z2047" >file-a &&
-	echo "b" >file-b &&
-	echo "$z2047" >>file-b &&
-	echo "c$z2047" | tr -d "\012" >file-c &&
-	echo "d" >file-d &&
-	echo "$z2047" | tr -d "\012" >>file-d &&
+x=zzzzzzzzzz			;# 10
+y="$x$x$x$x$x$x$x$x$x$x"	;# 100
+z="$y$y$y$y$y$y$y$y$y$y"	;# 1000
+z1000=$z
+z100=$y
+z10=$x
 
-	git add file-a file-b file-c file-d &&
+zs() {
+	count="$1"
+	while test "$count" -ge 1000
+	do
+		count=$(($count - 1000))
+		printf "%s" $z1000
+	done
+	while test "$count" -ge 100
+	do
+		count=$(($count - 100))
+		printf "%s" $z100
+	done
+	while test "$count" -ge 10
+	do
+		count=$(($count - 10))
+		printf "%s" $z10
+	done
+	while test "$count" -ge 1
+	do
+		count=$(($count - 1))
+		printf "z"
+	done
+}
 
-	echo "A$z2047" >file-a &&
-	echo "B" >file-b &&
-	echo "$z2047" >>file-b &&
-	echo "C$z2047" | tr -d "\012" >file-c &&
-	echo "D" >file-d &&
-	echo "$z2047" | tr -d "\012" >>file-d
-
-'
+zc () {
+	sed -e "/^index/d" \
+		-e "s/$z1000/Q/g" \
+		-e "s/QQQQQQQQQ/Z9000/g" \
+		-e "s/QQQQQQQQ/Z8000/g" \
+		-e "s/QQQQQQQ/Z7000/g" \
+		-e "s/QQQQQQ/Z6000/g" \
+		-e "s/QQQQQ/Z5000/g" \
+		-e "s/QQQQ/Z4000/g" \
+		-e "s/QQQ/Z3000/g" \
+		-e "s/QQ/Z2000/g" \
+		-e "s/Q/Z1000/g" \
+		-e "s/$z100/Q/g" \
+		-e "s/QQQQQQQQQ/Z900/g" \
+		-e "s/QQQQQQQQ/Z800/g" \
+		-e "s/QQQQQQQ/Z700/g" \
+		-e "s/QQQQQQ/Z600/g" \
+		-e "s/QQQQQ/Z500/g" \
+		-e "s/QQQQ/Z400/g" \
+		-e "s/QQQ/Z300/g" \
+		-e "s/QQ/Z200/g" \
+		-e "s/Q/Z100/g" \
+		-e "s/000Z//g" \
+		-e "s/$z10/Q/g" \
+		-e "s/QQQQQQQQQ/Z90/g" \
+		-e "s/QQQQQQQQ/Z80/g" \
+		-e "s/QQQQQQQ/Z70/g" \
+		-e "s/QQQQQQ/Z60/g" \
+		-e "s/QQQQQ/Z50/g" \
+		-e "s/QQQQ/Z40/g" \
+		-e "s/QQQ/Z30/g" \
+		-e "s/QQ/Z20/g" \
+		-e "s/Q/Z10/g" \
+		-e "s/00Z//g" \
+		-e "s/z/Q/g" \
+		-e "s/QQQQQQQQQ/Z9/g" \
+		-e "s/QQQQQQQQ/Z8/g" \
+		-e "s/QQQQQQQ/Z7/g" \
+		-e "s/QQQQQQ/Z6/g" \
+		-e "s/QQQQQ/Z5/g" \
+		-e "s/QQQQ/Z4/g" \
+		-e "s/QQQ/Z3/g" \
+		-e "s/QQ/Z2/g" \
+		-e "s/Q/Z1/g" \
+		-e "s/0Z//g" \
+	;
+}
 
-cat >expect <<\EOF
-diff --git a/file-a b/file-a
---- a/file-a
-+++ b/file-a
+expect_pattern () {
+	cnt="$1"
+	cat <<EOF
+diff --git a/file-a$cnt b/file-a$cnt
+--- a/file-a$cnt
++++ b/file-a$cnt
 @@ -1 +1 @@
--aZ
-+AZ
-diff --git a/file-b b/file-b
---- a/file-b
-+++ b/file-b
+-Z${cnt}a
++Z${cnt}A
+diff --git a/file-b$cnt b/file-b$cnt
+--- a/file-b$cnt
++++ b/file-b$cnt
 @@ -1 +1 @@
 -b
 +B
-diff --git a/file-c b/file-c
---- a/file-c
-+++ b/file-c
+diff --git a/file-c$cnt b/file-c$cnt
+--- a/file-c$cnt
++++ b/file-c$cnt
 @@ -1 +1 @@
--cZ
+-cZ$cnt
 \ No newline at end of file
-+CZ
++CZ$cnt
 \ No newline at end of file
-diff --git a/file-d b/file-d
---- a/file-d
-+++ b/file-d
+diff --git a/file-d$cnt b/file-d$cnt
+--- a/file-d$cnt
++++ b/file-d$cnt
 @@ -1 +1 @@
 -d
 +D
 EOF
+}
+
+sample='1023 1024 1025 2047 4095'
+
+test_expect_success setup '
+
+	for n in $sample
+	do
+		( zs $n ; echo a ) >file-a$n &&
+		( echo b; zs $n; echo ) >file-b$n &&
+		( printf c; zs $n ) >file-c$n &&
+		( echo d; zs $n ) >file-d$n &&
+
+		git add file-a$n file-b$n file-c$n file-d$n &&
+
+		( zs $n ; echo A ) >file-a$n &&
+		( echo B; zs $n; echo ) >file-b$n &&
+		( printf C; zs $n ) >file-c$n &&
+		( echo D; zs $n ) >file-d$n &&
+
+		expect_pattern $n || break
+
+	done >expect
+'
 
 test_expect_success 'diff -U0' '
 
-	git diff -U0 | sed -e "/^index/d" -e "s/$z2047/Z/g" >actual &&
+	for n in $sample
+	do
+		git diff -U0 file-?$n
+	done | zc >actual &&
 	diff -u expect actual
 
 '

El 20/12/2007, a las 1:21, Junio C Hamano escribió:

Charles Bailey [off-list ref] writes:

quoted

On Wed, Dec 19, 2007 at 09:27:15AM -0500, Jeff King wrote:
...

quoted

Somebody beat you to it. :) Can you confirm that the fix in

 [off-list ref]

works for you?

Ooh, the excitement, I've never had the opportunity to "git am"
before.

Well, if Wincent had sent the patch as plain text without MIME
quoted-printable, you did not have to even have the excitement of
running "git am", but a simple "git apply" would have sufficed.

Well, I sent it using "git send-email", so I guess it didn't have MIME  
quoted-printable.

Cheers,
Wincent

On Wed, Dec 19, 2007 at 04:21:30PM -0800, Junio C Hamano wrote:

By the way, how does this rewrite look?

It looks good and the test works on my fedora and Mac OS X boxes.
(Just for reference I'm on 10.4.3, not 'Leopard'.)

I've snipped everything except zc that I wanted to comment on.

The only two really minor nits I have is that zc does bizarre things
without warning for more than 9999 "z" ( e.g. 17000 = 9000 + 8000 =
98000 (!) ) and that, from a function responsibility point of view,
the /^index/d looks rather out of place.

Perhaps a comment saying tha zc is designed for <= 9999 z's?  Given
this, a lot of the /g are redundant.

But hey, it's a test script and it works and I don't have any better
suggestions. :)

Charles.

+zc () {
+	sed -e "/^index/d" \
+		-e "s/$z1000/Q/g" \
+		-e "s/QQQQQQQQQ/Z9000/g" \
+		-e "s/QQQQQQQQ/Z8000/g" \
+		-e "s/QQQQQQQ/Z7000/g" \
+		-e "s/QQQQQQ/Z6000/g" \
+		-e "s/QQQQQ/Z5000/g" \
+		-e "s/QQQQ/Z4000/g" \
+		-e "s/QQQ/Z3000/g" \
+		-e "s/QQ/Z2000/g" \
+		-e "s/Q/Z1000/g" \
+		-e "s/$z100/Q/g" \
+		-e "s/QQQQQQQQQ/Z900/g" \
+		-e "s/QQQQQQQQ/Z800/g" \
+		-e "s/QQQQQQQ/Z700/g" \
+		-e "s/QQQQQQ/Z600/g" \
+		-e "s/QQQQQ/Z500/g" \
+		-e "s/QQQQ/Z400/g" \
+		-e "s/QQQ/Z300/g" \
+		-e "s/QQ/Z200/g" \
+		-e "s/Q/Z100/g" \
+		-e "s/000Z//g" \
+		-e "s/$z10/Q/g" \
+		-e "s/QQQQQQQQQ/Z90/g" \
+		-e "s/QQQQQQQQ/Z80/g" \
+		-e "s/QQQQQQQ/Z70/g" \
+		-e "s/QQQQQQ/Z60/g" \
+		-e "s/QQQQQ/Z50/g" \
+		-e "s/QQQQ/Z40/g" \
+		-e "s/QQQ/Z30/g" \
+		-e "s/QQ/Z20/g" \
+		-e "s/Q/Z10/g" \
+		-e "s/00Z//g" \
+		-e "s/z/Q/g" \
+		-e "s/QQQQQQQQQ/Z9/g" \
+		-e "s/QQQQQQQQ/Z8/g" \
+		-e "s/QQQQQQQ/Z7/g" \
+		-e "s/QQQQQQ/Z6/g" \
+		-e "s/QQQQQ/Z5/g" \
+		-e "s/QQQQ/Z4/g" \
+		-e "s/QQQ/Z3/g" \
+		-e "s/QQ/Z2/g" \
+		-e "s/Q/Z1/g" \
+		-e "s/0Z//g" \
+	;
+}