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

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