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

From: Jeff King <peff@peff.net>
Date: Jan 24, 2018, 21:34 UTC
Message-ID: <20180124213410.GA8952@sigill.intra.peff.net>
In-Reply-To: <xmqq8tcnc68r.fsf@gitster.mtv.corp.google.com>

On Wed, Jan 24, 2018 at 01:11:00PM -0800, Junio C Hamano wrote:

> > 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.

Er, yeah. Sorry about that.

> 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.

I thought at first that this was due to the way the record-finding happens, but I think even in our normal binary searches, it is an invariant that "lo <= hi".

Show 15 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.

Yes, I agree that would also work.

-Peff