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

From: Jeff King <peff@peff.net>
Date: Oct 1, 2014, 10:50 UTC
Message-ID: <20141001105006.GB10332@peff.net>
In-Reply-To: <542BCCB9.4050908@web.de>

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

Show 8 quoted 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.

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" &&