Re: [PATCH v2 2/2] fsck: use oidset for skiplist

["René Scharfe" <l.s.r@web.de>]

Am 27.08.2018 um 09:37 schrieb Ævar Arnfjörð Bjarmason:
> 
> On Sat, Aug 25 2018, René Scharfe wrote:
> 
>> diff --git a/Documentation/config.txt b/Documentation/config.txt
>> index 2fa65b7516..80ab570579 100644
>> --- a/Documentation/config.txt
>> +++ b/Documentation/config.txt
>> @@ -1715,7 +1715,7 @@ doing the same for `receive.fsck.<msg-id>` and `fetch.fsck.<msg-id>`
>>  will only cause git to warn.
>>
>>  fsck.skipList::
>> -	The path to a sorted list of object names (i.e. one SHA-1 per
>> +	The path to a list of object names (i.e. one SHA-1 per
>>  	line) that are known to be broken in a non-fatal way and should
>>  	be ignored. This feature is useful when an established project
>>  	should be accepted despite early commits containing errors that
> 
> I was going to say that since this is a file format we're likely to
> support across versions we should make a note that "up to version
> so-and-so this needed to be sorted, but that's longer the case. So
> e.g. someone wouldn't test this on 2.20 (or read the online docs) and
> then deploy this for older clients..
> 
> But...
> 
>> -	if (options->skiplist)
>> -		sorted = options->skiplist->sorted;
>> -	else {
>> -		sorted = 1;
>> -		options->skiplist = &skiplist;
>> -	}
>> -
>>  	fp = fopen(path, "r");
>>  	if (!fp)
>>  		die("Could not open skip list: %s", path);
>> @@ -202,19 +192,12 @@ static void init_skiplist(struct fsck_options *options, const char *path)
>>  		const char *p;
>>  		if (parse_oid_hex(sb.buf, &oid, &p) || *p != '\0')
>>  			die("Invalid SHA-1: %s", sb.buf);
>> -		oid_array_append(&skiplist, &oid);
>> -		if (sorted && skiplist.nr > 1 &&
>> -				oidcmp(&skiplist.oid[skiplist.nr - 2],
>> -				       &oid) > 0)
>> -			sorted = 0;
>> +		oidset_insert(&options->skiplist, &oid);
> 
> ...reading this implementation, where we always called
> oid_array_append(), but then just kept track of whether the set was
> sorted...
> 
>>  	}
>>  	if (ferror(fp))
>>  		die_errno("Could not read '%s'", path);
>>  	fclose(fp);
>>  	strbuf_release(&sb);
>> -
>> -	if (sorted)
>> -		skiplist.sorted = 1;
> 
> ...and here where we assigned to the .sorted member of the oid_array...
> 
>>  static int object_on_skiplist(struct fsck_options *opts, struct object *obj)
>>  {
>> -	if (opts && opts->skiplist && obj)
>> -		return oid_array_lookup(opts->skiplist, &obj->oid) >= 0;
>> -	return 0;
>> +	return opts && obj && oidset_contains(&opts->skiplist, &obj->oid);
>>  }
> 
> ....and here where we'd always do the lookup if the skiplist was
> initialized, *not* just if it's sorted, and how the sha1-array.c code
> has looked ever since cd94c6f91 ("fsck: git receive-pack: support
> excluding objects from fsck'ing", 2015-06-22) when this was first added:
> 
>     $ git show cd94c6f91:sha1-array.c|grep -A5 sha1_array_lookup
>     int sha1_array_lookup(struct sha1_array *array, const unsigned char *sha1)
>     {
>             if (!array->sorted)
>                     sha1_array_sort(array);
>             return sha1_pos(sha1, array->sha1, array->nr, sha1_access);
>     }
> 
> So I think it makes sense to make this series a three-part, where in the
> first part we only change these docs to say s/sorted //, and modify the
> tests I added in 65a836fa6b ("fsck: add stress tests for fsck.skipList",
> 2018-07-27) to assert that an unsorted & sorted list of SHA-1s works
> just as well.
> 
> Then following up with your [12]/2, where the internal implementation is
> changed, but we make it clear that it's *just* the internal
> implementation. I.e. from a UI perspective the list never had to be
> pre-sorted, we'd just spend some work sorting it on the first lookup if
> it wasn't sorted already.
> 
> Now without some very careful reading it's not clear what "we don't need
> to worry about any sort order anymore" in the commit message means,
> i.e. what it really means is "for the purposes of the internal
> implementation, and as an opt-in user-side optimization ...".
> 
> I.e. an alternate version of this whole patch series could also be:
> 
>     diff --git a/Documentation/config.txt b/Documentation/config.txt
>     index 1c4236498..930807e43 100644
>     --- a/Documentation/config.txt
>     +++ b/Documentation/config.txt
>     @@ -1709,5 +1709,5 @@ will only cause git to warn.
> 
>      fsck.skipList::
>     -       The path to a sorted list of object names (i.e. one SHA-1 per
>     +       The path to a list of object names (i.e. one SHA-1 per
>             line) that are known to be broken in a non-fatal way and should
>             be ignored. This feature is useful when an established project
>     diff --git a/fsck.c b/fsck.c
>     index a0cee0be5..9d4e938ad 100644
>     --- a/fsck.c
>     +++ b/fsck.c
>     @@ -184,14 +184,10 @@ static void init_skiplist(struct fsck_options *options, const char *path)
>      {
>             static struct oid_array skiplist = OID_ARRAY_INIT;
>     -       int sorted, fd;
>     +       int fd;
>             char buffer[GIT_MAX_HEXSZ + 1];
>             struct object_id oid;
> 
>     -       if (options->skiplist)
>     -               sorted = options->skiplist->sorted;
>     -       else {
>     -               sorted = 1;
>     +       if (!options->skiplist)
>                     options->skiplist = &skiplist;
>     -       }
> 
>             fd = open(path, O_RDONLY);
>     @@ -208,13 +204,6 @@ static void init_skiplist(struct fsck_options *options, const char *path)
>                             die("Invalid SHA-1: %s", buffer);
>                     oid_array_append(&skiplist, &oid);
>     -               if (sorted && skiplist.nr > 1 &&
>     -                               oidcmp(&skiplist.oid[skiplist.nr - 2],
>     -                                      &oid) > 0)
>     -                       sorted = 0;
>             }
>             close(fd);
>     -
>     -       if (sorted)
>     -               skiplist.sorted = 1;
>      }
> 
> Now, I like yours much better. I'm just saying that currently the
> patch/commit message combo is confusing about *what* it's
> doing. I.e. let's not mix up the correction of docs that were always
> wrong with a non-change in the user facing implementation, and some
> internal optimization all in one patch.

Now you have me confused.  Unsorted lists were always accepted, but the
documentation asked for a sorted one anyway, probably to avoid sorting
it with every use.  Switching the underlying data structure makes that a
moot point -- sortedness is no longer a concern at all -- not in the
code, and not for users.

Inviting users to run the array implementation with unsorted lists is
not incorrect, but it also doesn't help anyone.  We could clarify that
sorted lists are preferred or recommended instead of required.  I don't
see value in perfecting the documentation of a quirk just before
removing it, though.

René