Re: [PATCH 3/6] find_reference_location(): make function safe for empty snapshots

From: Junio C Hamano <gitster@pobox.com>
Date: Jan 24, 2018, 21:11 UTC
Message-ID: <xmqq8tcnc68r.fsf@gitster.mtv.corp.google.com>
In-Reply-To: <20180124202754.GA7773@sigill.intra.peff.net>

Jeff King <peff@peff.net> writes:

Show 18 quoted lines

> On Wed, Jan 24, 2018 at 12:14:13PM +0100, Michael Haggerty wrote:
>
>> diff --git a/refs/packed-backend.c b/refs/packed-backend.c
>> index 08698de6ea..361affd7ad 100644
>> --- a/refs/packed-backend.c
>> +++ b/refs/packed-backend.c
>> [...]
>> @@ -551,7 +553,7 @@ static const char *find_reference_location(struct snapshot *snapshot,
>>  	 */
>>  	const char *hi = snapshot->eof;
>>  
>> -	while (lo < hi) {
>> +	while (lo != hi) {
>>  		const char *mid, *rec;
>>  		int cmp;
>
> This tightens the binary search termination condition. If we ever did
> see "hi > lo", we'd want to terminate the loop. Is that ever possible?

I think you meant "lo > hi", but I shared the same "Huh?" moment.

Because "While lo is strictly lower than hi" is a so well established binary search pattern, even though we know that it is equivalent to "While lo and hi is different" due to your analysis below, the new code looks somewhat strange at the first glance.

Show 6 quoted lines

> I think the answer is "no". Our "hi" here is an exclusive bound, so we
> should never go past it via find_end_of_record() when assigning "lo".
> And "hi" is always assigned from the start of the current record. That
> can never cross "lo", because find_start_of_record() ensures it.
>
> So I think it's fine, but I wanted to double check.

It would be much simpler to reason about if we instead do

	#define is_empty_snapshot(s) ((s)->start == NULL)

	if (is_empty_snapshot(snapshot))
		return NULL;

or something like that upfront.