sha1-array: add test-sha1-array and basic tests
PATCH 1/2 sha1-array: add test-sha1-array and basic tests
--- .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
.gitignore +1 -0
@@ -199,6 +199,7 @@ /test-revision-walking /test-run-command /test-sha1 +/test-sha1-array /test-sigchain /test-string-list /test-subprocess
Makefile +1 -0
@@ -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
t/t0064-sha1-array.sh new file +64 -0
64 lines not on this page · raw message
test-sha1-array.c new file +34 -0
@@ -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 ; +}
Signature · 1 line
2.1.2
PATCH 2/2 sha1-lookup: fix handling of duplicates in sha1_pos()
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.
--- sha1-lookup.c | 2 -- t/t0064-sha1-array.sh | 20 ++++++++++++++++++++ 2 files changed, 20 insertions(+), 2 deletions(-)
sha1-lookup.c +0 -2
@@ -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 {
t/t0064-sha1-array.sh +20 -0
@@ -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
Signature · 1 line
2.1.2
Re: [PATCH 2/2] sha1-lookup: fix handling of duplicates in sha1_pos()
Quoted 8 lines · 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.
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:
t/t0064-sha1-array.sh +13 -2
@@ -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()
Am 01.10.2014 um 12:50 schrieb Jeff King:
Quoted 21 lines · René Scharfe
Quoted 9 lines
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.
Quoted 2 lines
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.
Quoted 38 lines
t/t0064-sha1-array.sh +13
-2@@ -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()
Quoted 5 lines · René Scharfe
Quoted 2 lines
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...
Quoted 3 lines
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).
Quoted 2 lines
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()
In reply to René ScharfeQuoted 45 lines · 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 <[email protected]>--- sha1-lookup.c | 2 -- t/t0064-sha1-array.sh | 20 ++++++++++++++++++++ 2 files changed, 20 insertions(+), 2 deletions(-)sha1-lookup.c +0
-2@@ -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 {t/t0064-sha1-array.sh +9
-0@@ -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 +'
t/t0064-sha1-array.sh test_expect_success 'lookup with duplicates' ' · line 82
Quoted 10 lines
t/t0064-sha1-array.sh +10
-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.
Quoted 4 lines
t/t0064-sha1-array.sh +1
-1+ test_done --2.1.2
Quoted 9 lines · René Scharfe
Signed-off-by Rene Scharfe <[email protected]>---
t/t0064-sha1-array.sh new file +1
-0@@ -0,0 +1,64 @@ +#!/bin/sh
t/t0064-sha1-array.sh line 11
Quoted 10 lines
t/t0064-sha1-array.sh new file +10
-0+ +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"
t/t0064-sha1-array.sh line 19
Quoted 8 lines
t/t0064-sha1-array.sh new file +8
-0+ 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 &&
Quoted 45 lines
t/t0064-sha1-array.sh new file +45
-0+ 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
Quoted 7 lines · Eric Sunshine
t/t0064-sha1-array.sh line 11
Quoted 6 lines
t/t0064-sha1-array.sh new file +6
-0+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"
Quoted 5 lines
Each caller of
echo20()manually includes a space at the end of $prefix. Would it make sense to instead haveecho20()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:
Quoted 2 lines
Review
Quoted 2 lines
(quoted diff) +2
-0+test_expect_success 'ordered enumeration' ' + echo20 "" 44 55 88 aa >expect &&
This does not.
Quoted 7 lines
Review
Quoted 2 lines
(quoted diff) +2
-0+ { + 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
Am 01.10.2014 um 16:11 schrieb Eric Sunshine:
Quoted 25 lines · René Scharfe
Quoted 9 lines
Signed-off-by Rene Scharfe <[email protected]>---
t/t0064-sha1-array.sh new file +1
-0@@ -0,0 +1,64 @@ +#!/bin/sht/t0064-sha1-array.sh line 11
Quoted 10 lines
t/t0064-sha1-array.sh new file +10
-0+ +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 haveecho20()do this on behalf of the caller?
Quoted 1 line
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. :)
Quoted 60 lines
t/t0064-sha1-array.sh line 19
Quoted 9 lines
t/t0064-sha1-array.sh new file +8
-0+ 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 &&Quoted 45 lines
t/t0064-sha1-array.sh new file +45
-0+ 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