Re: [PATCH 3/6] find_reference_location(): make function safe for empty snapshots
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". > > 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
Re: [PATCH 3/6] find_reference_location(): make function safe for empty snapshots
Jeff King writes:
> 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.
> 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.
Re: [PATCH 3/6] find_reference_location(): make function safe for empty snapshots
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 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.
-Peff
[PATCH 3/6] find_reference_location(): make function safe for empty snapshots
This function had two problems if called for an empty snapshot (i.e.,
`snapshot->start == snapshot->eof == NULL`):
* It checked `NULL < NULL`, which is undefined by C (albeit highly
unlikely to fail in the real world).
* (Assuming the above comparison behaved as expected), it returned
NULL when `mustexist` was false, contrary to its docstring.
Change the check and fix the docstring.
Signed-off-by: Michael Haggerty
---
refs/packed-backend.c | 10 ++
1 file changed, 6 insertions(+), 4 deletions(-)
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
@@ -519,9 +519,11 @@ static int load_contents(struct snapshot *snapshot)
* `refname` starts. If `mustexist` is true and the reference doesn't
* exist, then return NULL. If `mustexist` is false and the reference
* doesn't exist, then return the point where that reference would be
- * inserted. In the latter mode, `refname` doesn't have to be a proper
- * reference name; for example, one could search for "refs/replace/"
- * to find the start of any replace references.
+ * inserted, or `snapshot->eof` (which might be NULL) if it would be
+ * inserted at the end of the file. In the latter mode, `refname`
+ * doesn't have to be a proper reference name; for example, one could
+ * search for "refs/replace/" to find the start of any replace
+ * references.
*
* The record is sought using a binary search, so `snapshot->buf` must
* be sorted.
@@ -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;
--
2.14.2
