patch, 5 partsStore submodules in a hash, not a linked list

> Move the responsibility for registering the ref_store for a submodule
> from base_ref_store_init() to a new function, register_ref_store(). Call
> the latter from ref_store_init().
>
> This means that base_ref_store_init() can lose its submodule argument,
> further weakening the 1:1 relationship between ref_stores and
> submodules.
>
> Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
> ---

> +
>  struct ref_store *ref_store_init(const char *submodule)
>  {
>         const char *be_name = "files";
>         struct ref_storage_be *be = find_ref_storage_backend(be_name);
> +       struct ref_store *refs;
>
>         if (!be)
>                 die("BUG: reference backend %s is unknown", be_name);
>
>         if (!submodule || !*submodule)
> -               return be->init(NULL);
> +               refs = be->init(NULL);
>         else
> -               return be->init(submodule);
> +               refs = be->init(submodule);
> +
> +       register_ref_store(refs, submodule);
> +       return refs;
>  }

> On Thu, Feb 9, 2017 at 5:27 AM, Michael Haggerty <mhagger@alum.mit.edu> wrote:
>> Move the responsibility for registering the ref_store for a submodule
>> from base_ref_store_init() to a new function, register_ref_store(). Call
>> the latter from ref_store_init().
>>
>> This means that base_ref_store_init() can lose its submodule argument,
>> further weakening the 1:1 relationship between ref_stores and
>> submodules.
>>
>> Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
>> ---
> 
> 
> 
> 
>> +
>>  struct ref_store *ref_store_init(const char *submodule)
>>  {
>>         const char *be_name = "files";
>>         struct ref_storage_be *be = find_ref_storage_backend(be_name);
>> +       struct ref_store *refs;
>>
>>         if (!be)
>>                 die("BUG: reference backend %s is unknown", be_name);
>>
>>         if (!submodule || !*submodule)
>> -               return be->init(NULL);
>> +               refs = be->init(NULL);
>>         else
>> -               return be->init(submodule);
>> +               refs = be->init(submodule);
>> +
>> +       register_ref_store(refs, submodule);
>> +       return refs;
>>  }
> 
> This function is already very readable, though maybe it would be
> more readable like so:
> 
> {
>     const char *be_name = "files";
>     struct ref_storage_be *be = find_ref_storage_backend(be_name);
> 
>     if (!be)
>         die("BUG: reference backend %s is unknown", be_name);
> 
>     /* replace empty string by NULL */
>     if (submodule && !*submodule)
>         submodule = NULL;
> 
>     register_ref_store(be->init(submodule), submodule);
>     return refs;
> }
> 
> Well, I dunno; the function inside the arguments to register seems ugly, though.

> Move the responsibility for registering the ref_store for a submodule
> from base_ref_store_init() to a new function, register_ref_store(). Call
> the latter from ref_store_init().
>
> This means that base_ref_store_init() can lose its submodule argument,
> further weakening the 1:1 relationship between ref_stores and
> submodules.

>> @@ -1402,17 +1435,17 @@ struct ref_store *ref_store_init(const char *submodule)
>>
>>  struct ref_store *lookup_ref_store(const char *submodule)
>>  {
> 
>> +       if (!submodule_ref_stores.tablesize)
>> +               hashmap_init(&submodule_ref_stores, submodule_hash_cmp, 20);
> 
> 
> So we can lookup a submodule even before we initialized the subsystem?
> Does that actually happen? (It sounds like a bug to me.)
>
> Instead of initializing, you could return NULL directly here.

> On 02/09/2017 05:58 PM, Stefan Beller wrote:
>>> @@ -1402,17 +1435,17 @@ struct ref_store *ref_store_init(const char *submodule)
>>>
>>>  struct ref_store *lookup_ref_store(const char *submodule)
>>>  {
>>
>>> +       if (!submodule_ref_stores.tablesize)
>>> +               hashmap_init(&submodule_ref_stores, submodule_hash_cmp, 20);
>>
>>
>> So we can lookup a submodule even before we initialized the subsystem?
>> Does that actually happen? (It sounds like a bug to me.)
>>
>> Instead of initializing, you could return NULL directly here.
>
> The lines you quoted are only concerned with bringing the (empty)
> hashmap into existence if it hasn't been initialized already. (There's
> no HASHMAP_INIT.) I don't know what you mean by "initialize the
> subsystem". The only way to bring a ref_store *object* into existence is
> currently to call get_ref_store(submodule), which calls
> lookup_ref_store(submodule) to see if it already exists, and if not
> calls ref_store_init(submodule) to instantiate it and register it in the
> hashmap. There's nothing else that has to be initialize before that
> (except maybe the usual startup config reading etc.)
>
> I suppose this code path could be changed to return NULL without
> initializing the hashmap, but the hashmap will be initialized a moment
> later by ref_store_init(), so I don't see much difference either way.

> On 02/09/2017 05:58 PM, Stefan Beller wrote:
> >> @@ -1402,17 +1435,17 @@ struct ref_store *ref_store_init(const char *submodule)
> >>
> >>  struct ref_store *lookup_ref_store(const char *submodule)
> >>  {
> > 
> >> +       if (!submodule_ref_stores.tablesize)
> >> +               hashmap_init(&submodule_ref_stores, submodule_hash_cmp, 20);
> > 
> > 
> > So we can lookup a submodule even before we initialized the subsystem?
> > Does that actually happen? (It sounds like a bug to me.)
> >
> > Instead of initializing, you could return NULL directly here.
> [...]
> I suppose this code path could be changed to return NULL without
> initializing the hashmap, but the hashmap will be initialized a moment
> later by ref_store_init(), so I don't see much difference either way.

> +struct submodule_hash_entry
> +{
> +	struct hashmap_entry ent; /* must be the first member! */
> +
> +	struct ref_store *refs;
> +
> +	/* NUL-terminated name of submodule: */
> +	char submodule[FLEX_ARRAY];
> +};
> +
> +static int submodule_hash_cmp(const void *entry, const void *entry_or_key,
> +			      const void *keydata)
> +{
> +	const struct submodule_hash_entry *e1 = entry, *e2 = entry_or_key;
> +	const char *submodule = keydata;
> +
> +	return strcmp(e1->submodule, submodule ? submodule : e2->submodule);

> +}
> +
> +static struct submodule_hash_entry *alloc_submodule_hash_entry(
> +		const char *submodule, struct ref_store *refs)
> +{
> +	size_t len = strlen(submodule);
> +	struct submodule_hash_entry *entry = malloc(sizeof(*entry) + len + 1);

> +	hashmap_entry_init(entry, strhash(submodule));
> +	entry->refs = refs;
> +	memcpy(entry->submodule, submodule, len + 1);
> +	return entry;
> +}
> ...
> @@ -1373,16 +1405,17 @@ void base_ref_store_init(struct ref_store *refs,
>  			die("BUG: main_ref_store initialized twice");
>  
>  		refs->submodule = "";
> -		refs->next = NULL;
>  		main_ref_store = refs;
>  	} else {
> -		if (lookup_ref_store(submodule))
> +		refs->submodule = xstrdup(submodule);
> +
> +		if (!submodule_ref_stores.tablesize)
> +			hashmap_init(&submodule_ref_stores, submodule_hash_cmp, 20);

> > +static struct submodule_hash_entry *alloc_submodule_hash_entry(
> > +		const char *submodule, struct ref_store *refs)
> > +{
> > +	size_t len = strlen(submodule);
> > +	struct submodule_hash_entry *entry = malloc(sizeof(*entry) + len + 1);
> 
> I think this (and the later memcpy) is what FLEX_ALLOC_MEM() was
> invented for.

> > @@ -1373,16 +1405,17 @@ void base_ref_store_init(struct ref_store *refs,
> >  			die("BUG: main_ref_store initialized twice");
> >  
> >  		refs->submodule = "";
> > -		refs->next = NULL;
> >  		main_ref_store = refs;
> >  	} else {
> > -		if (lookup_ref_store(submodule))
> > +		refs->submodule = xstrdup(submodule);
> > +
> > +		if (!submodule_ref_stores.tablesize)
> > +			hashmap_init(&submodule_ref_stores, submodule_hash_cmp, 20);
> 
> Makes me wonder what "20" stands for.  Perhaps the caller should be
> allowed to say "I do not quite care what initial size is" by passing
> 0 or some equally but more clealy meaningless value (which of course
> would be outside the scope of this series).

> Michael Haggerty <mhagger@alum.mit.edu> writes:
>> [...]
>> +static int submodule_hash_cmp(const void *entry, const void *entry_or_key,
>> +			      const void *keydata)
>> +{
>> +	const struct submodule_hash_entry *e1 = entry, *e2 = entry_or_key;
>> +	const char *submodule = keydata;
>> +
>> +	return strcmp(e1->submodule, submodule ? submodule : e2->submodule);
> 
> I would have found it more readable if it were like so:
> 
> 	const char *submodule = keydata ? keydata : e2->submodule;
> 
> 	return strcmp(e1->submodule, submodule);
> 
> but I suspect the difference is not that huge.

> On Thu, Feb 09, 2017 at 12:34:04PM -0800, Junio C Hamano wrote:
>
>>> +static struct submodule_hash_entry *alloc_submodule_hash_entry(
>>> +		const char *submodule, struct ref_store *refs)
>>> +{
>>> +	size_t len = strlen(submodule);
>>> +	struct submodule_hash_entry *entry = malloc(sizeof(*entry) + len + 1);
>>
>> I think this (and the later memcpy) is what FLEX_ALLOC_MEM() was
>> invented for.
>
> Yes, it was. Though since the length comes from a strlen() call, it can
> actually use the _STR variant, like:
>
>   FLEX_ALLOC_STR(entry, submodule, submodule);
>
> Besides being shorter, this does integer-overflow checks on the final
> length.

>>> @@ -1373,16 +1405,17 @@ void base_ref_store_init(struct ref_store *refs,
>>>  			die("BUG: main_ref_store initialized twice");
>>>
>>>  		refs->submodule = "";
>>> -		refs->next = NULL;
>>>  		main_ref_store = refs;
>>>  	} else {
>>> -		if (lookup_ref_store(submodule))
>>> +		refs->submodule = xstrdup(submodule);
>>> +
>>> +		if (!submodule_ref_stores.tablesize)
>>> +			hashmap_init(&submodule_ref_stores, submodule_hash_cmp, 20);
>>
>> Makes me wonder what "20" stands for.  Perhaps the caller should be
>> allowed to say "I do not quite care what initial size is" by passing
>> 0 or some equally but more clealy meaningless value (which of course
>> would be outside the scope of this series).
>
> I think this is what "0" already does (grep for HASHMAP_INITIAL_SIZE).
> In fact, that constant is 64. The 20 we pass in goes through some magic
> load-factor computation and ends up as 25. That being smaller than the
> INITIAL_SIZE constant, I believe that we end up allocating 64 entries
> either way (that's just from reading the code, though; I didn't run it
> to double check).

> The old practice of storing the empty string in this member for the main
> repository was a holdover from before 00eebe3 (refs: create a base class
> "ref_store" for files_ref_store, 2016-09-04), when the submodule was
> stored in a flex array at the end of `struct files_ref_store`. Storing
> NULL for this case is more idiomatic and a tiny bit less code.
>
> Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
> ---

> The old practice of storing the empty string in this member for the main
> repository was a holdover from before 00eebe3 (refs: create a base class
> "ref_store" for files_ref_store, 2016-09-04), when the submodule was
> stored in a flex array at the end of `struct files_ref_store`. Storing
> NULL for this case is more idiomatic and a tiny bit less code.

>  struct ref_store *ref_store_init(const char *submodule)
>  {
>  	const char *be_name = "files";
>  	struct ref_storage_be *be = find_ref_storage_backend(be_name);
> +	struct ref_store *refs;
>  
>  	if (!be)
>  		die("BUG: reference backend %s is unknown", be_name);
>  
>  	if (!submodule || !*submodule)
> -		return be->init(NULL);
> +		refs = be->init(NULL);
>  	else
> -		return be->init(submodule);
> +		refs = be->init(submodule);

> --- a/refs/files-backend.c
> +++ b/refs/files-backend.c
> @@ -980,7 +980,7 @@ static struct ref_store *files_ref_store_create(const char *submodule)
>  	struct files_ref_store *refs = xcalloc(1, sizeof(*refs));
>  	struct ref_store *ref_store = (struct ref_store *)refs;
>  
> -	base_ref_store_init(ref_store, &refs_be_files, submodule);
> +	base_ref_store_init(ref_store, &refs_be_files);
>  
>  	refs->submodule = submodule ? xstrdup(submodule) : "";

>>       if (!submodule || !*submodule)
>> -             return be->init(NULL);
>> +             refs = be->init(NULL);
>>       else
>> -             return be->init(submodule);
>> +             refs = be->init(submodule);
>
> Can't we also lose this "if !*submodule, turn it to NULL"?

> There is no need to call read_ref_full() or resolve_gitlink_ref() from
> read_loose_refs(), because we already have a ref_store object in hand.
> So we can call resolve_ref_recursively() ourselves. Happily, this
> unifies the code for the submodule vs. non-submodule cases.
>
> This requires resolve_ref_recursively() to be exposed to the refs
> subsystem, though not to non-refs code.
>
> Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
> ---

> Push the submodule attribute down from ref_store to files_ref_store.
> This is another step towards loosening the 1:1 connection between
> ref_stores and submodules.
>
> Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>

> I have mentioned this patch series on the mailing list a couple of
> time [1,2] but haven't submitted it before. I just rebased it to
> current master. It is available from my Git fork [3] as branch
> "submodule-hash".
>
> The first point of this patch series is to optimize submodule
> `ref_store` lookup by storing the `ref_store`s in a hashmap rather
> than a linked list. But a more interesting second point is to weaken
> the 1:1 relationship between submodules and `ref_stores` a little bit
> more.
>
> A `files_ref_store` would be perfectly happy to represent, say, the
> references *physically* stored in a linked worktree (e.g., `HEAD`,
> `refs/bisect/*`, etc) even though that is not the complete collection
> of refs that are *logically* visible from that worktree (which
> includes references from the main repository, too). But the old code
> was confusing the two things by storing "submodule" in every
> `ref_store` instance.
>
> So push the submodule attribute down to the `files_ref_store` class
> (but continue to let the `ref_store`s be looked up by submodule).
>
> The last commit is relatively orthogonal to the others; it simplifies
> read_loose_refs() by calling resolve_ref_recursively() directly using
> the `ref_store` instance that it already has in hand, rather than
> indirectly via the public wrappers.
>
> Michael
>
> [1] http://public-inbox.org/git/341999fc-4496-b974-c117-c18a2fca1358@alum.mit.edu/
> [2] http://public-inbox.org/git/37fe2024-0378-a974-a28d-18a89d3e2312@alum.mit.edu/
> [3] https://github.com/mhagger/git
>
> Michael Haggerty (5):
>   refs: store submodule ref stores in a hashmap
>   refs: push the submodule attribute down
>   register_ref_store(): new function
>   files_ref_store::submodule: use NULL for the main repository
>   read_loose_refs(): read refs using resolve_ref_recursively()

> I have mentioned this patch series on the mailing list a couple of
> time [1,2] but haven't submitted it before. I just rebased it to
> current master. It is available from my Git fork [3] as branch
> "submodule-hash".
> 
> The first point of this patch series is to optimize submodule
> `ref_store` lookup by storing the `ref_store`s in a hashmap rather
> than a linked list. But a more interesting second point is to weaken
> the 1:1 relationship between submodules and `ref_stores` a little bit
> more.

> A `files_ref_store` would be perfectly happy to represent, say, the
> references *physically* stored in a linked worktree (e.g., `HEAD`,
> `refs/bisect/*`, etc) even though that is not the complete collection
> of refs that are *logically* visible from that worktree (which
> includes references from the main repository, too). But the old code
> was confusing the two things by storing "submodule" in every
> `ref_store` instance.
> 
> So push the submodule attribute down to the `files_ref_store` class
> (but continue to let the `ref_store`s be looked up by submodule).

> On Thu, Feb 09, 2017 at 02:26:57PM +0100, Michael Haggerty wrote:
> [...]
>> A `files_ref_store` would be perfectly happy to represent, say, the
>> references *physically* stored in a linked worktree (e.g., `HEAD`,
>> `refs/bisect/*`, etc) even though that is not the complete collection
>> of refs that are *logically* visible from that worktree (which
>> includes references from the main repository, too). But the old code
>> was confusing the two things by storing "submodule" in every
>> `ref_store` instance.
>>
>> So push the submodule attribute down to the `files_ref_store` class
>> (but continue to let the `ref_store`s be looked up by submodule).
> 
> I'm not sure I understand all of the ramifications here. It _sounds_ like
> pushing this down into the files-backend code would make it harder to
> have mixed ref-backends for different submodules. Or is this just
> pushing down an implementation detail of the files backend, and future
> code is free to have as many different ref_stores as it likes?

> >> So push the submodule attribute down to the `files_ref_store` class
> >> (but continue to let the `ref_store`s be looked up by submodule).
> > 
> > I'm not sure I understand all of the ramifications here. It _sounds_ like
> > pushing this down into the files-backend code would make it harder to
> > have mixed ref-backends for different submodules. Or is this just
> > pushing down an implementation detail of the files backend, and future
> > code is free to have as many different ref_stores as it likes?
> 
> I don't understand how this would make it harder, aside from the fact
> that a new backend class might also need a path member and have to
> maintain its own copy rather than using one that the base class provides.

> On Thu, Feb 09, 2017 at 10:23:35PM +0100, Michael Haggerty wrote:
> 
>>>> So push the submodule attribute down to the `files_ref_store` class
>>>> (but continue to let the `ref_store`s be looked up by submodule).
>>>
>>> I'm not sure I understand all of the ramifications here. It _sounds_ like
>>> pushing this down into the files-backend code would make it harder to
>>> have mixed ref-backends for different submodules. Or is this just
>>> pushing down an implementation detail of the files backend, and future
>>> code is free to have as many different ref_stores as it likes?
>>
>> I don't understand how this would make it harder, aside from the fact
>> that a new backend class might also need a path member and have to
>> maintain its own copy rather than using one that the base class provides.
> 
> Probably the answer is "I'm really confused".
> 
> But here's how my line of reasoning went:
> 
>   Right now we have a main ref-store that points to the submodule
>   ref-stores. I don't know the current state of it, but in theory those
>   could all use different backends.
> 
>   This seems like it's pushing that submodule linkage down into the
>   backend.
> 
> But I think from your response that the answer is no, the thing that is
> being pushed down is not the right way for the main ref store and the
> submodules to be linked. In fact, there is no reason at all for the
> main ref store to know or care about submodules. Anybody who wants to
> know about a submodule's refs should ask the hashmap.

> On Thu, Feb 09, 2017 at 10:23:35PM +0100, Michael Haggerty wrote:
> 
> > >> So push the submodule attribute down to the `files_ref_store` class
> > >> (but continue to let the `ref_store`s be looked up by submodule).
> > > 
> > > I'm not sure I understand all of the ramifications here. It _sounds_ like
> > > pushing this down into the files-backend code would make it harder to
> > > have mixed ref-backends for different submodules. Or is this just
> > > pushing down an implementation detail of the files backend, and future
> > > code is free to have as many different ref_stores as it likes?
> > 
> > I don't understand how this would make it harder, aside from the fact
> > that a new backend class might also need a path member and have to
> > maintain its own copy rather than using one that the base class provides.
> 
> Probably the answer is "I'm really confused".
> 
> But here's how my line of reasoning went:
> 
>   Right now we have a main ref-store that points to the submodule
>   ref-stores. I don't know the current state of it, but in theory those
>   could all use different backends.
> 
>   This seems like it's pushing that submodule linkage down into the
>   backend.
> 
> But I think from your response that the answer is no, the thing that is
> being pushed down is not the right way for the main ref store and the
> submodules to be linked.