[PATCH 1/2] sha1-array: add test-sha1-array and basic tests

[PATCH 1/2] sha1-array: add test-sha1-array and basic tests

[René Scharfe]

Signed-off-by: Rene Scharfe <l.s.r@web.de>
---
 .gitignore            |  1 +
 Makefile              |  1 +
 t/t0064-sha1-array.sh | 64 +++++++++++++++++++++++++++++++++++++++++++++++++++
 test-sha1-array.c     | 34 +++++++++++++++++++++++++++
 4 files changed, 100 insertions(+)
 create mode 100755 t/t0064-sha1-array.sh
 create mode 100644 test-sha1-array.c

diff --git a/.gitignore b/.gitignore
index 5bfb234..9ec40fa 100644
--- a/.gitignore
+++ b/.gitignore
@@ -199,6 +199,7 @@
 /test-revision-walking
 /test-run-command
 /test-sha1
+/test-sha1-array
 /test-sigchain
 /test-string-list
 /test-subprocess
diff --git a/Makefile b/Makefile
index f34a2d4..356feb5 100644
--- a/Makefile
+++ b/Makefile
@@ -568,6 +568,7 @@ TEST_PROGRAMS_NEED_X += test-revision-walking
 TEST_PROGRAMS_NEED_X += test-run-command
 TEST_PROGRAMS_NEED_X += test-scrap-cache-tree
 TEST_PROGRAMS_NEED_X += test-sha1
+TEST_PROGRAMS_NEED_X += test-sha1-array
 TEST_PROGRAMS_NEED_X += test-sigchain
 TEST_PROGRAMS_NEED_X += test-string-list
 TEST_PROGRAMS_NEED_X += test-subprocess
diff --git a/t/t0064-sha1-array.sh b/t/t0064-sha1-array.sh
new file mode 100755
index 0000000..bd68789
--- /dev/null
+++ b/t/t0064-sha1-array.sh
@@ -0,0 +1,64 @@
+#!/bin/sh
+
+test_description='basic tests for the SHA1 array implementation'
+. ./test-lib.sh
+
+echo20() {
+	prefix="$1"
+	shift
+	while test $# -gt 0
+	do
+		echo "$prefix$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1"
+		shift
+	done
+}
+
+test_expect_success 'ordered enumeration' '
+	echo20 "" 44 55 88 aa >expect &&
+	{
+		echo20 "append " 88 44 aa 55 &&
+		echo for_each_unique
+	} | test-sha1-array >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'ordered enumeration with duplicate suppression' '
+	echo20 "" 44 55 88 aa >expect &&
+	{
+		echo20 "append " 88 44 aa 55 &&
+		echo20 "append " 88 44 aa 55 &&
+		echo for_each_unique
+	} | test-sha1-array >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'lookup' '
+	{
+		echo20 "append " 88 44 aa 55 &&
+		echo20 "lookup " 55
+	} | test-sha1-array >actual &&
+	n=$(cat actual) &&
+	test "$n" -eq 1
+'
+
+test_expect_success 'lookup non-existing entry' '
+	{
+		echo20 "append " 88 44 aa 55 &&
+		echo20 "lookup " 33
+	} | test-sha1-array >actual &&
+	n=$(cat actual) &&
+	test "$n" -lt 0
+'
+
+test_expect_success 'lookup with duplicates' '
+	{
+		echo20 "append " 88 44 aa 55 &&
+		echo20 "append " 88 44 aa 55 &&
+		echo20 "lookup " 55
+	} | test-sha1-array >actual &&
+	n=$(cat actual) &&
+	test "$n" -ge 2 &&
+	test "$n" -le 3
+'
+
+test_done
diff --git a/test-sha1-array.c b/test-sha1-array.c
new file mode 100644
index 0000000..ddc491e
--- /dev/null
+++ b/test-sha1-array.c
@@ -0,0 +1,34 @@
+#include "cache.h"
+#include "sha1-array.h"
+
+static void print_sha1(const unsigned char sha1[20], void *data)
+{
+	puts(sha1_to_hex(sha1));
+}
+
+int main(int argc, char **argv)
+{
+	struct sha1_array array = SHA1_ARRAY_INIT;
+	struct strbuf line = STRBUF_INIT;
+
+	while (strbuf_getline(&line, stdin, '\n') != EOF) {
+		const char *arg;
+		unsigned char sha1[20];
+
+		if (skip_prefix(line.buf, "append ", &arg)) {
+			if (get_sha1_hex(arg, sha1))
+				die("not a hexadecimal SHA1: %s", arg);
+			sha1_array_append(&array, sha1);
+		} else if (skip_prefix(line.buf, "lookup ", &arg)) {
+			if (get_sha1_hex(arg, sha1))
+				die("not a hexadecimal SHA1: %s", arg);
+			printf("%d\n", sha1_array_lookup(&array, sha1));
+		} else if (!strcmp(line.buf, "clear"))
+			sha1_array_clear(&array);
+		else if (!strcmp(line.buf, "for_each_unique"))
+			sha1_array_for_each_unique(&array, print_sha1, NULL);
+		else
+			die("unknown command: %s", line.buf);
+	}
+	return 0;
+}
-- 
2.1.2

[PATCH 2/2] sha1-lookup: fix handling of duplicates in sha1_pos()

[René Scharfe]

If the first 18 bytes of the SHA1's of all entries are the same then
sha1_pos() dies and reports that the lower and upper limits of the
binary search were the same that this wasn't supposed to happen.  This
is wrong because the remaining two bytes could still differ.

Furthermore: It wouldn't be a problem if they actually were the same,
i.e. if all entries have the same SHA1.  The code already handles
duplicates just fine otherwise.  Simply remove the erroneous check.

Signed-off-by: Rene Scharfe <l.s.r@web.de>
---
 sha1-lookup.c         |  2 --
 t/t0064-sha1-array.sh | 20 ++++++++++++++++++++
 2 files changed, 20 insertions(+), 2 deletions(-)

diff --git a/sha1-lookup.c b/sha1-lookup.c
index 2dd8515..5f06921 100644
--- a/sha1-lookup.c
+++ b/sha1-lookup.c
@@ -84,8 +84,6 @@ int sha1_pos(const unsigned char *sha1, void *table, size_t nr,
 				die("BUG: assertion failed in binary search");
 			}
 		}
-		if (18 <= ofs)
-			die("cannot happen -- lo and hi are identical");
 	}
 
 	do {
diff --git a/t/t0064-sha1-array.sh b/t/t0064-sha1-array.sh
index bd68789..3fcb8d8 100755
--- a/t/t0064-sha1-array.sh
+++ b/t/t0064-sha1-array.sh
@@ -61,4 +61,24 @@ test_expect_success 'lookup with duplicates' '
 	test "$n" -le 3
 '
 
+test_expect_success 'lookup with almost duplicate values' '
+	{
+		echo "append 5555555555555555555555555555555555555555" &&
+		echo "append 555555555555555555555555555555555555555f" &&
+		echo20 "lookup " 55
+	} | test-sha1-array >actual &&
+	n=$(cat actual) &&
+	test "$n" -eq 0
+'
+
+test_expect_success 'lookup with single duplicate value' '
+	{
+		echo20 "append " 55 55 &&
+		echo20 "lookup " 55
+	} | test-sha1-array >actual &&
+	n=$(cat actual) &&
+	test "$n" -ge 0 &&
+	test "$n" -le 1
+'
+
 test_done
-- 
2.1.2

Re: [PATCH 2/2] sha1-lookup: fix handling of duplicates in sha1_pos()

[Jeff King]

On Wed, Oct 01, 2014 at 11:43:21AM +0200, René Scharfe wrote:

> If the first 18 bytes of the SHA1's of all entries are the same then
> sha1_pos() dies and reports that the lower and upper limits of the
> binary search were the same that this wasn't supposed to happen.  This
> is wrong because the remaining two bytes could still differ.
> 
> Furthermore: It wouldn't be a problem if they actually were the same,
> i.e. if all entries have the same SHA1.  The code already handles
> duplicates just fine otherwise.  Simply remove the erroneous check.

Yeah, I agree that assertion is just wrong.

Regarding duplicates: in sha1_entry_pos, we had to handle the "not
found" case specially, because we may have found the left-hand or
right-hand side of a run of duplicates, and we want to return the
correct slot where the new item would go (see the comment added by
171bdac). I think we don't have to deal with that here, because we are
just dealing with the initial "mi" selection. The actual binary search
is plain-vanilla, which handles that case just fine.

I wonder if it is worth adding a test (you test only that "not found"
produces a negative index, but not which index). Like:

diff --git a/t/t0064-sha1-array.sh b/t/t0064-sha1-array.sh
index 3fcb8d8..7781129 100755
--- a/t/t0064-sha1-array.sh
+++ b/t/t0064-sha1-array.sh
@@ -42,12 +42,12 @@ test_expect_success 'lookup' '
 '
 
 test_expect_success 'lookup non-existing entry' '
+	echo -1 >expect &&
 	{
 		echo20 "append " 88 44 aa 55 &&
 		echo20 "lookup " 33
 	} | test-sha1-array >actual &&
-	n=$(cat actual) &&
-	test "$n" -lt 0
+	test_cmp expect actual
 '
 
 test_expect_success 'lookup with duplicates' '
@@ -61,6 +61,17 @@ test_expect_success 'lookup with duplicates' '
 	test "$n" -le 3
 '
 
+test_expect_success 'lookup non-existing entry with duplicates' '
+	echo -5 >expect &&
+	{
+		echo20 "append " 88 44 aa 55 &&
+		echo20 "append " 88 44 aa 55 &&
+		echo20 "lookup " 66
+	} | test-sha1-array >actual &&
+	test_cmp expect actual
+'
+
+
 test_expect_success 'lookup with almost duplicate values' '
 	{
 		echo "append 5555555555555555555555555555555555555555" &&

Re: [PATCH 2/2] sha1-lookup: fix handling of duplicates in sha1_pos()

[René Scharfe]

Am 01.10.2014 um 12:50 schrieb Jeff King:
> On Wed, Oct 01, 2014 at 11:43:21AM +0200, René Scharfe wrote:
>
>> If the first 18 bytes of the SHA1's of all entries are the same then
>> sha1_pos() dies and reports that the lower and upper limits of the
>> binary search were the same that this wasn't supposed to happen.  This
>> is wrong because the remaining two bytes could still differ.
>>
>> Furthermore: It wouldn't be a problem if they actually were the same,
>> i.e. if all entries have the same SHA1.  The code already handles
>> duplicates just fine otherwise.  Simply remove the erroneous check.
>
> Yeah, I agree that assertion is just wrong.
>
> Regarding duplicates: in sha1_entry_pos, we had to handle the "not
> found" case specially, because we may have found the left-hand or
> right-hand side of a run of duplicates, and we want to return the
> correct slot where the new item would go (see the comment added by
> 171bdac). I think we don't have to deal with that here, because we are
> just dealing with the initial "mi" selection. The actual binary search
> is plain-vanilla, which handles that case just fine.
>
> I wonder if it is worth adding a test (you test only that "not found"
> produces a negative index, but not which index). Like:

api-sha1-array.txt says about sha1_array_lookup: "If not found, returns 
a negative integer", and that's what the test checks.

I actually like that the value is not specified for that case because no 
existing caller actually uses it and it leaves room to implement the 
function e.g. using bsearch(3).

I agree that adding a "lookup non-existing entry with duplicates" test 
would make t0064 more complete, though.

> diff --git a/t/t0064-sha1-array.sh b/t/t0064-sha1-array.sh
> index 3fcb8d8..7781129 100755
> --- a/t/t0064-sha1-array.sh
> +++ b/t/t0064-sha1-array.sh
> @@ -42,12 +42,12 @@ test_expect_success 'lookup' '
>   '
>
>   test_expect_success 'lookup non-existing entry' '
> +	echo -1 >expect &&
>   	{
>   		echo20 "append " 88 44 aa 55 &&
>   		echo20 "lookup " 33
>   	} | test-sha1-array >actual &&
> -	n=$(cat actual) &&
> -	test "$n" -lt 0
> +	test_cmp expect actual
>   '
>
>   test_expect_success 'lookup with duplicates' '
> @@ -61,6 +61,17 @@ test_expect_success 'lookup with duplicates' '
>   	test "$n" -le 3
>   '
>
> +test_expect_success 'lookup non-existing entry with duplicates' '
> +	echo -5 >expect &&
> +	{
> +		echo20 "append " 88 44 aa 55 &&
> +		echo20 "append " 88 44 aa 55 &&
> +		echo20 "lookup " 66
> +	} | test-sha1-array >actual &&
> +	test_cmp expect actual
> +'
> +
> +
>   test_expect_success 'lookup with almost duplicate values' '
>   	{
>   		echo "append 5555555555555555555555555555555555555555" &&
>

Re: [PATCH 2/2] sha1-lookup: fix handling of duplicates in sha1_pos()

[Jeff King]

On Wed, Oct 01, 2014 at 01:10:12PM +0200, René Scharfe wrote:

> >I wonder if it is worth adding a test (you test only that "not found"
> >produces a negative index, but not which index). Like:
> 
> api-sha1-array.txt says about sha1_array_lookup: "If not found, returns a
> negative integer", and that's what the test checks.

Hmm. I do not recall intentionally leaving the value unspecified; I
think it is more that I was simply not thorough when writing the
documentation. That being said...

> I actually like that the value is not specified for that case because no
> existing caller actually uses it and it leaves room to implement the
> function e.g. using bsearch(3).

Yeah, if no callers actually care right now, that is a reasonable
argument for leaving the exact return value unspecified (and testing
only what the documentation claims).

> I agree that adding a "lookup non-existing entry with duplicates" test would
> make t0064 more complete, though.

Agreed.

-Peff

Re: [PATCH 2/2] sha1-lookup: fix handling of duplicates in sha1_pos()

[Eric Sunshine]

On Wed, Oct 1, 2014 at 5:43 AM, René Scharfe <l.s.r@web.de> wrote:
> If the first 18 bytes of the SHA1's of all entries are the same then
> sha1_pos() dies and reports that the lower and upper limits of the
> binary search were the same that this wasn't supposed to happen.  This
> is wrong because the remaining two bytes could still differ.
>
> Furthermore: It wouldn't be a problem if they actually were the same,
> i.e. if all entries have the same SHA1.  The code already handles
> duplicates just fine otherwise.  Simply remove the erroneous check.
>
> Signed-off-by: Rene Scharfe <l.s.r@web.de>
> ---
>  sha1-lookup.c         |  2 --
>  t/t0064-sha1-array.sh | 20 ++++++++++++++++++++
>  2 files changed, 20 insertions(+), 2 deletions(-)
>
> diff --git a/sha1-lookup.c b/sha1-lookup.c
> index 2dd8515..5f06921 100644
> --- a/sha1-lookup.c
> +++ b/sha1-lookup.c
> @@ -84,8 +84,6 @@ int sha1_pos(const unsigned char *sha1, void *table, size_t nr,
>                                 die("BUG: assertion failed in binary search");
>                         }
>                 }
> -               if (18 <= ofs)
> -                       die("cannot happen -- lo and hi are identical");
>         }
>
>         do {
> diff --git a/t/t0064-sha1-array.sh b/t/t0064-sha1-array.sh
> index bd68789..3fcb8d8 100755
> --- a/t/t0064-sha1-array.sh
> +++ b/t/t0064-sha1-array.sh
> @@ -61,4 +61,24 @@ test_expect_success 'lookup with duplicates' '
>         test "$n" -le 3
>  '
>
> +test_expect_success 'lookup with almost duplicate values' '
> +       {
> +               echo "append 5555555555555555555555555555555555555555" &&
> +               echo "append 555555555555555555555555555555555555555f" &&
> +               echo20 "lookup " 55
> +       } | test-sha1-array >actual &&
> +       n=$(cat actual) &&
> +       test "$n" -eq 0
> +'
> +
> +test_expect_success 'lookup with single duplicate value' '
> +       {
> +               echo20 "append " 55 55 &&
> +               echo20 "lookup " 55
> +       } | test-sha1-array >actual &&
> +       n=$(cat actual) &&
> +       test "$n" -ge 0 &&
> +       test "$n" -le 1
> +'

An alternative would be to introduce these two tests in patch 1/2 as
test_expect_failure and flip them to test_expect_success in this patch
which fixes the problem.

> +
>  test_done
> --
> 2.1.2

Re: [PATCH 1/2] sha1-array: add test-sha1-array and basic tests

[Eric Sunshine]

On Wed, Oct 1, 2014 at 5:40 AM, René Scharfe <l.s.r@web.de> wrote:
> Signed-off-by: Rene Scharfe <l.s.r@web.de>
> ---
> diff --git a/t/t0064-sha1-array.sh b/t/t0064-sha1-array.sh
> new file mode 100755
> index 0000000..bd68789
> --- /dev/null
> +++ b/t/t0064-sha1-array.sh
> @@ -0,0 +1,64 @@
> +#!/bin/sh
> +
> +test_description='basic tests for the SHA1 array implementation'
> +. ./test-lib.sh
> +
> +echo20() {
> +       prefix="$1"
> +       shift
> +       while test $# -gt 0
> +       do
> +               echo "$prefix$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1"

Each caller of echo20() manually includes a space at the end of
$prefix. Would it make sense to instead have echo20() do this on
behalf of the caller?

    echo "$prefix $1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1"

> +               shift
> +       done
> +}
> +
> +test_expect_success 'ordered enumeration' '
> +       echo20 "" 44 55 88 aa >expect &&
> +       {
> +               echo20 "append " 88 44 aa 55 &&

Which would slightly reduce the burden on the caller and make it read
(very slightly) nicer:

    echo20 append 88 44 aa 55 &&

> +               echo for_each_unique
> +       } | test-sha1-array >actual &&
> +       test_cmp expect actual
> +'
> +
> +test_expect_success 'ordered enumeration with duplicate suppression' '
> +       echo20 "" 44 55 88 aa >expect &&
> +       {
> +               echo20 "append " 88 44 aa 55 &&
> +               echo20 "append " 88 44 aa 55 &&
> +               echo for_each_unique
> +       } | test-sha1-array >actual &&
> +       test_cmp expect actual
> +'
> +
> +test_expect_success 'lookup' '
> +       {
> +               echo20 "append " 88 44 aa 55 &&
> +               echo20 "lookup " 55
> +       } | test-sha1-array >actual &&
> +       n=$(cat actual) &&
> +       test "$n" -eq 1
> +'
> +
> +test_expect_success 'lookup non-existing entry' '
> +       {
> +               echo20 "append " 88 44 aa 55 &&
> +               echo20 "lookup " 33
> +       } | test-sha1-array >actual &&
> +       n=$(cat actual) &&
> +       test "$n" -lt 0
> +'
> +
> +test_expect_success 'lookup with duplicates' '
> +       {
> +               echo20 "append " 88 44 aa 55 &&
> +               echo20 "append " 88 44 aa 55 &&
> +               echo20 "lookup " 55
> +       } | test-sha1-array >actual &&
> +       n=$(cat actual) &&
> +       test "$n" -ge 2 &&
> +       test "$n" -le 3
> +'
> +
> +test_done

Re: [PATCH 1/2] sha1-array: add test-sha1-array and basic tests

[René Scharfe]

Am 01.10.2014 um 16:11 schrieb Eric Sunshine:
> On Wed, Oct 1, 2014 at 5:40 AM, René Scharfe <l.s.r@web.de> wrote:
>> Signed-off-by: Rene Scharfe <l.s.r@web.de>
>> ---
>> diff --git a/t/t0064-sha1-array.sh b/t/t0064-sha1-array.sh
>> new file mode 100755
>> index 0000000..bd68789
>> --- /dev/null
>> +++ b/t/t0064-sha1-array.sh
>> @@ -0,0 +1,64 @@
>> +#!/bin/sh
>> +
>> +test_description='basic tests for the SHA1 array implementation'
>> +. ./test-lib.sh
>> +
>> +echo20() {
>> +       prefix="$1"
>> +       shift
>> +       while test $# -gt 0
>> +       do
>> +               echo "$prefix$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1"
>
> Each caller of echo20() manually includes a space at the end of
> $prefix. Would it make sense to instead have echo20() do this on
> behalf of the caller?
>
>      echo "$prefix $1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1"

That wouldn't work if the prefix is the empty string; we don't want a 
space in that case (see the next echo20 call below).

But ${prefix:+$prefix } would do the trick.  Thanks for the idea. :)

>
>> +               shift
>> +       done
>> +}
>> +
>> +test_expect_success 'ordered enumeration' '
>> +       echo20 "" 44 55 88 aa >expect &&
>> +       {
>> +               echo20 "append " 88 44 aa 55 &&
>
> Which would slightly reduce the burden on the caller and make it read
> (very slightly) nicer:
>
>      echo20 append 88 44 aa 55 &&
>
>> +               echo for_each_unique
>> +       } | test-sha1-array >actual &&
>> +       test_cmp expect actual
>> +'
>> +
>> +test_expect_success 'ordered enumeration with duplicate suppression' '
>> +       echo20 "" 44 55 88 aa >expect &&
>> +       {
>> +               echo20 "append " 88 44 aa 55 &&
>> +               echo20 "append " 88 44 aa 55 &&
>> +               echo for_each_unique
>> +       } | test-sha1-array >actual &&
>> +       test_cmp expect actual
>> +'
>> +
>> +test_expect_success 'lookup' '
>> +       {
>> +               echo20 "append " 88 44 aa 55 &&
>> +               echo20 "lookup " 55
>> +       } | test-sha1-array >actual &&
>> +       n=$(cat actual) &&
>> +       test "$n" -eq 1
>> +'
>> +
>> +test_expect_success 'lookup non-existing entry' '
>> +       {
>> +               echo20 "append " 88 44 aa 55 &&
>> +               echo20 "lookup " 33
>> +       } | test-sha1-array >actual &&
>> +       n=$(cat actual) &&
>> +       test "$n" -lt 0
>> +'
>> +
>> +test_expect_success 'lookup with duplicates' '
>> +       {
>> +               echo20 "append " 88 44 aa 55 &&
>> +               echo20 "append " 88 44 aa 55 &&
>> +               echo20 "lookup " 55
>> +       } | test-sha1-array >actual &&
>> +       n=$(cat actual) &&
>> +       test "$n" -ge 2 &&
>> +       test "$n" -le 3
>> +'
>> +
>> +test_done

Re: [PATCH 1/2] sha1-array: add test-sha1-array and basic tests

[Jeff King]

On Wed, Oct 01, 2014 at 10:11:04AM -0400, Eric Sunshine wrote:

> > +echo20() {
> > +       prefix="$1"
> > +       shift
> > +       while test $# -gt 0
> > +       do
> > +               echo "$prefix$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1"
> 
> Each caller of echo20() manually includes a space at the end of
> $prefix. Would it make sense to instead have echo20() do this on
> behalf of the caller?
> 
>     echo "$prefix $1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1"

Not always. For example:

> > +test_expect_success 'ordered enumeration' '
> > +       echo20 "" 44 55 88 aa >expect &&

This does not.

> > +       {
> > +               echo20 "append " 88 44 aa 55 &&
> 
> Which would slightly reduce the burden on the caller and make it read
> (very slightly) nicer:
> 
>     echo20 append 88 44 aa 55 &&

I agree that is more readable. But you'd have to make echo20 more like:

  if test -n "$1"; then
          prefix="$1 "
  else
          prefix=""
  fi

which is not too bad.

-Peff