Message ID | 20190127194415.171035-5-sxenos@google.com (mailing list archive) |
---|---|
State | New, archived |
Headers | show |
Series | [v3,1/8] technical doc: add a design doc for the evolve command | expand |
Hi Stefan, I did not yet have time to study your proposal in detail, but hope to do so before the Contributor Summit so that I can have an informed opinion. Just one thing: On Sun, 27 Jan 2019, sxenos@google.com wrote: > From: Stefan Xenos <sxenos@google.com> > > A change table stores a list of changes, and supports efficient lookup > from a commit hash to the list of changes that reference that commit > directly. > > It can be used to look up content commits or metacommits at the head > of a change, but does not support lookup of commits referenced as part > of the commit history. > > Signed-off-by: Stefan Xenos <sxenos@google.com> > --- > Makefile | 1 + > change-table.c | 207 +++++++++++++++++++++++++++++++++++++++++++++++++ > change-table.h | 138 +++++++++++++++++++++++++++++++++ > 3 files changed, 346 insertions(+) > create mode 100644 change-table.c > create mode 100644 change-table.h > > diff --git a/Makefile b/Makefile > index 7ffc383f2b..09cfd3ef1b 100644 > --- a/Makefile > +++ b/Makefile > @@ -844,6 +844,7 @@ LIB_OBJS += branch.o > LIB_OBJS += bulk-checkin.o > LIB_OBJS += bundle.o > LIB_OBJS += cache-tree.o > +LIB_OBJS += change-table.o > LIB_OBJS += chdir-notify.o > LIB_OBJS += checkout.o > LIB_OBJS += color.o > diff --git a/change-table.c b/change-table.c > new file mode 100644 > index 0000000000..6daff5f58c > --- /dev/null > +++ b/change-table.c > @@ -0,0 +1,207 @@ > +#include "cache.h" > +#include "change-table.h" > +#include "commit.h" > +#include "ref-filter.h" > +#include "metacommit-parser.h" > + > +void change_table_init(struct change_table *to_initialize) > +{ > + memset(to_initialize, 0, sizeof(*to_initialize)); > + mem_pool_init(&(to_initialize->memory_pool), 0); > + to_initialize->memory_pool->block_alloc = 4*1024 - sizeof(struct mp_block); > + oidmap_init(&(to_initialize->oid_to_metadata_index), 0); > + string_list_init(&(to_initialize->refname_to_change_head), 1); > +} > + > +static void change_list_clear(struct change_list *to_clear) { > + string_list_clear(&to_clear->additional_refnames, 0); > +} > + > +static void commit_change_list_entry_clear( > + struct commit_change_list_entry *to_clear) { > + change_list_clear(&(to_clear->changes)); > +} > + > +static void change_head_array_clear(struct change_head_array *to_clear) > +{ > + FREE_AND_NULL(to_clear->array); > +} > + > +void change_table_clear(struct change_table *to_clear) > +{ > + struct oidmap_iter iter; > + struct commit_change_list_entry *next; > + for (next = oidmap_iter_first(&to_clear->oid_to_metadata_index, &iter); > + next; > + next = oidmap_iter_next(&iter)) { > + > + commit_change_list_entry_clear(next); > + } > + > + oidmap_free(&to_clear->oid_to_metadata_index, 0); > + string_list_clear(&(to_clear->refname_to_change_head), 0); > + change_head_array_clear(&to_clear->heads); > + mem_pool_discard(to_clear->memory_pool, 0); > +} > + > +/* > + * Appends a new, empty, change_head struct to the end of the given array. > + * Returns the index of the newly-added struct. > + */ > +static int change_head_array_append(struct change_head_array *to_add) > +{ > + int index = to_add->nr++; > + struct change_head *new_head; > + ALLOC_GROW(to_add->array, to_add->nr, to_add->alloc); > + new_head = &(to_add->array[index]); > + memset(new_head, 0, sizeof(*new_head)); > + return index; > +} > + > +static void add_head_to_commit(struct change_table *to_modify, > + const struct object_id *to_add, const char *refname) > +{ > + struct commit_change_list_entry *entry; > + > + // Note: the indices in the map are 1-based. 0 is used to indicate a missing > + // element. > + entry = oidmap_get(&(to_modify->oid_to_metadata_index), to_add); > + if (!entry) { > + entry = mem_pool_calloc(to_modify->memory_pool, 1, > + sizeof(*entry)); > + oidcpy(&entry->entry.oid, to_add); > + oidmap_put(&(to_modify->oid_to_metadata_index), entry); > + string_list_init(&(entry->changes.additional_refnames), 0); > + } > + > + if (entry->changes.first_refname == NULL) { > + entry->changes.first_refname = refname; > + } else { > + string_list_insert(&entry->changes.additional_refnames, refname); > + } > +} > + > +void change_table_add(struct change_table *to_modify, const char *refname, > + struct commit *to_add) > +{ > + struct change_head *new_head; > + struct string_list_item *new_item; > + long index; > + int metacommit_type; > + > + index = change_head_array_append(&to_modify->heads); > + new_head = &(to_modify->heads.array[index]); > + > + oidcpy(&new_head->head, &(to_add->object.oid)); > + > + metacommit_type = get_metacommit_content(to_add, &new_head->content); > + if (metacommit_type == METACOMMIT_TYPE_NONE) { > + oidcpy(&new_head->content, &(to_add->object.oid)); > + } > + new_head->abandoned = (metacommit_type == METACOMMIT_TYPE_ABANDONED); > + new_head->remote = starts_with(refname, "refs/remote/"); > + new_head->hidden = starts_with(refname, "refs/hiddenmetas/"); > + > + new_item = string_list_insert(&to_modify->refname_to_change_head, refname); > + new_item->util = (void*)index; This is not good. You are using a `long` here. The 80s called and want their now-obsolete data types back. If you want a data type that can take an integer but also a pointer, use `intptr_t` instead. But even that is not good practice. What you really want here is to use a union of the data types that you want to store in that `util` field. This is not merely academic, your code causes compile errors on Windows: https://dev.azure.com/gitgitgadget/git/_build/results?buildId=400&view=logs&jobId=fd490c07-0b22-5182-fac9-6d67fe1e939b&taskId=ce91d5d6-0c55-50f5-8ab9-6695c03ab102&lineStart=430&lineEnd=440&colStart=1&colEnd=1 Ciao, Johannes > + // Use pointers to the copy of the string we're retaining locally > + refname = new_item->string; > + > + if (!oideq(&new_head->content, &new_head->head)) { > + add_head_to_commit(to_modify, &(new_head->content), refname); > + } > + add_head_to_commit(to_modify, &(new_head->head), refname); > +} > + > +void change_table_add_all_visible(struct change_table *to_modify, > + struct repository* repo) > +{ > + struct ref_filter filter; > + const char *name_patterns[] = {NULL}; > + memset(&filter, 0, sizeof(filter)); > + filter.kind = FILTER_REFS_CHANGES; > + filter.name_patterns = name_patterns; > + > + change_table_add_matching_filter(to_modify, repo, &filter); > +} > + > +void change_table_add_matching_filter(struct change_table *to_modify, > + struct repository* repo, struct ref_filter *filter) > +{ > + struct ref_array matching_refs; > + int i; > + > + memset(&matching_refs, 0, sizeof(matching_refs)); > + filter_refs(&matching_refs, filter, filter->kind); > + > + // Determine the object id for the latest content commit for each change. > + // Fetch the commit at the head of each change ref. If it's a normal commit, > + // that's the commit we want. If it's a metacommit, locate its content parent > + // and use that. > + > + for (i = 0; i < matching_refs.nr; i++) { > + struct ref_array_item *item = matching_refs.items[i]; > + struct commit *commit = item->commit; > + > + commit = lookup_commit_reference_gently(repo, &(item->objectname), 1); > + > + if (commit != NULL) { > + change_table_add(to_modify, item->refname, commit); > + } > + } > + > + ref_array_clear(&matching_refs); > +} > + > +static int return_true_callback(const char *refname, void *cb_data) > +{ > + return 1; > +} > + > +int change_table_has_change_referencing(struct change_table *changes, > + const struct object_id *referenced_commit_id) > +{ > + return for_each_change_referencing(changes, referenced_commit_id, > + return_true_callback, NULL); > +} > + > +int for_each_change_referencing(struct change_table *table, > + const struct object_id *referenced_commit_id, each_change_fn fn, void *cb_data) > +{ > + const struct change_list *changes; > + int i; > + int retvalue; > + struct commit_change_list_entry *entry; > + > + entry = oidmap_get(&table->oid_to_metadata_index, > + referenced_commit_id); > + // If this commit isn't referenced by any changes, it won't be in the map > + if (!entry) { > + return 0; > + } > + changes = &(entry->changes); > + if (changes->first_refname == NULL) { > + return 0; > + } > + retvalue = fn(changes->first_refname, cb_data); > + for (i = 0; retvalue == 0 && i < changes->additional_refnames.nr; i++) { > + retvalue = fn(changes->additional_refnames.items[i].string, cb_data); > + } > + return retvalue; > +} > + > +struct change_head* get_change_head(struct change_table *heads, > + const char* refname) > +{ > + struct string_list_item *item = string_list_lookup( > + &heads->refname_to_change_head, refname); > + long index; > + > + if (!item) { > + return NULL; > + } > + > + index = (long)item->util; > + return &(heads->heads.array[index]); > +} > + > diff --git a/change-table.h b/change-table.h > new file mode 100644 > index 0000000000..85bb19c3bf > --- /dev/null > +++ b/change-table.h > @@ -0,0 +1,138 @@ > +#ifndef CHANGE_TABLE_H > +#define CHANGE_TABLE_H > + > +#include "oidmap.h" > + > +struct commit; > +struct ref_filter; > + > +/* > + * This struct holds a list of change refs. The first element is stored inline, > + * to optimize for small lists. > + */ > +struct change_list { > + /* Ref name for the first change in the list, or null if none. > + * > + * This field is private. Use for_each_change_in to read. > + */ > + const char* first_refname; > + /* List of additional change refs. Note that this is empty if the list > + * contains 0 or 1 elements. > + * > + * This field is private. Use for_each_change_in to read. > + */ > + struct string_list additional_refnames; > +}; > + > +/* > + * Holds information about the head of a single change. > + */ > +struct change_head { > + /* > + * The location pointed to by the head of the change. May be a commit or a > + * metacommit. > + */ > + struct object_id head; > + /* > + * The content commit for the latest commit in the change. Always points to a > + * real commit, never a metacommit. > + */ > + struct object_id content; > + /* > + * Abandoned: indicates that the content commit should be removed from the > + * history. > + * > + * Hidden: indicates that the change is an inactive change from the > + * hiddenmetas namespace. Such changes will be hidden from the user by > + * default. > + * > + * Deleted: indicates that the change has been removed from the repository. > + * That is the ref was deleted since the time this struct was created. Such > + * entries should be ignored. > + */ > + int abandoned:1, > + hidden:1, > + remote:1, > + deleted:1; > +}; > + > +/* > + * An array of change_head. > + */ > +struct change_head_array { > + struct change_head* array; > + int nr; > + int alloc; > +}; > + > +/* > + * Holds the list of change refs whose content points to a particular content > + * commit. > + */ > +struct commit_change_list_entry { > + struct oidmap_entry entry; > + struct change_list changes; > +}; > + > +/* > + * Holds information about the heads of each change, and permits effecient > + * lookup from a commit to the changes that reference it directly. > + * > + * All fields should be considered private. Use the change_table functions > + * to interact with this struct. > + */ > +struct change_table { > + /** > + * Memory pool for the objects allocated by the change table. > + */ > + struct mem_pool *memory_pool; > + /* Map object_id to commit_change_list_entry structs. */ > + struct oidmap oid_to_metadata_index; > + /* List of ref names. The util value is an int index into change_metadata > + * array. > + */ > + struct string_list refname_to_change_head; > + /* change_head structures for each head */ > + struct change_head_array heads; > +}; > + > +extern void change_table_init(struct change_table *to_initialize); > +extern void change_table_clear(struct change_table *to_clear); > + > +/* Adds the given change head to the change_table struct */ > +extern void change_table_add(struct change_table *to_modify, > + const char *refname, struct commit *target); > + > +/* Adds the non-hidden local changes to the given change_table struct. > + */ > +extern void change_table_add_all_visible(struct change_table *to_modify, > + struct repository *repo); > + > +/* > + * Adds all changes matching the given ref filter to the given change_table > + * struct. > + */ > +extern void change_table_add_matching_filter(struct change_table *to_modify, > + struct repository* repo, struct ref_filter *filter); > + > +typedef int each_change_fn(const char *refname, void *cb_data); > + > +extern int change_table_has_change_referencing(struct change_table *changes, > + const struct object_id *referenced_commit_id); > + > +/* Iterates over all changes that reference the given commit. For metacommits, > + * this is the list of changes that point directly to that metacommit. > + * For normal commits, this is the list of changes that have this commit as > + * their latest content. > + */ > +extern int for_each_change_referencing(struct change_table *heads, > + const struct object_id *referenced_commit_id, each_change_fn fn, void *cb_data); > + > +/** > + * Returns the change head for the given refname. Returns NULL if no such change > + * exists. > + */ > +extern struct change_head* get_change_head(struct change_table *heads, > + const char* refname); > + > +#endif > -- > 2.20.1.495.gaa96b0ce6b-goog > > >
Hi Junio, On Mon, 28 Jan 2019, Johannes Schindelin wrote: > On Sun, 27 Jan 2019, sxenos@google.com wrote: > > > + new_item->util = (void*)index; > > This is not good. You are using a `long` here. The 80s called and want > their now-obsolete data types back. > > If you want a data type that can take an integer but also a pointer, use > `intptr_t` instead. > > But even that is not good practice. What you really want here is to use a > union of the data types that you want to store in that `util` field. > > This is not merely academic, your code causes compile errors on Windows: > > https://dev.azure.com/gitgitgadget/git/_build/results?buildId=400&view=logs&jobId=fd490c07-0b22-5182-fac9-6d67fe1e939b&taskId=ce91d5d6-0c55-50f5-8ab9-6695c03ab102&lineStart=430&lineEnd=440&colStart=1&colEnd=1 Since Stefan did not grace us with an answer, Junio, could I ask you to squash this in (which is by no means a satisfactory fix, but it is a stopgap to get `pu` building again)? -- snipsnap -- diff --git a/change-table.c b/change-table.c index 2e0d935de846..197ce2783532 100644 --- a/change-table.c +++ b/change-table.c @@ -103,7 +103,7 @@ void change_table_add(struct change_table *to_modify, const char *refname, new_head->hidden = starts_with(refname, "refs/hiddenmetas/"); new_item = string_list_insert(&to_modify->refname_to_change_head, refname); - new_item->util = (void*)index; + new_item->util = (void *)(intptr_t)index; // Use pointers to the copy of the string we're retaining locally refname = new_item->string; @@ -201,6 +201,6 @@ struct change_head* get_change_head(struct change_table *heads, return NULL; } - index = (long)item->util; + index = (long)(intptr_t)item->util; return &(heads->heads.array[index]); }
Sorry, folks. I normally can't do any open source work on weekdays. That also includes writing responses on the mailing list, so there will normally be a week or two lag for me to iterate on this sort of thing. Feel free to either include this fix or revert my patch if there's a problem with it - just let me know what you selected. I'll roll with it and either resubmit with the requested changes or submit the requested changes as follow-ups. - Stefan On Mon, Jan 28, 2019 at 3:08 PM Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote: > > Hi Junio, > > On Mon, 28 Jan 2019, Johannes Schindelin wrote: > > > On Sun, 27 Jan 2019, sxenos@google.com wrote: > > > > > + new_item->util = (void*)index; > > > > This is not good. You are using a `long` here. The 80s called and want > > their now-obsolete data types back. > > > > If you want a data type that can take an integer but also a pointer, use > > `intptr_t` instead. > > > > But even that is not good practice. What you really want here is to use a > > union of the data types that you want to store in that `util` field. > > > > This is not merely academic, your code causes compile errors on Windows: > > > > https://dev.azure.com/gitgitgadget/git/_build/results?buildId=400&view=logs&jobId=fd490c07-0b22-5182-fac9-6d67fe1e939b&taskId=ce91d5d6-0c55-50f5-8ab9-6695c03ab102&lineStart=430&lineEnd=440&colStart=1&colEnd=1 > > Since Stefan did not grace us with an answer, Junio, could I ask you to > squash this in (which is by no means a satisfactory fix, but it is a > stopgap to get `pu` building again)? > > -- snipsnap -- > diff --git a/change-table.c b/change-table.c > index 2e0d935de846..197ce2783532 100644 > --- a/change-table.c > +++ b/change-table.c > @@ -103,7 +103,7 @@ void change_table_add(struct change_table *to_modify, const char *refname, > new_head->hidden = starts_with(refname, "refs/hiddenmetas/"); > > new_item = string_list_insert(&to_modify->refname_to_change_head, refname); > - new_item->util = (void*)index; > + new_item->util = (void *)(intptr_t)index; > // Use pointers to the copy of the string we're retaining locally > refname = new_item->string; > > @@ -201,6 +201,6 @@ struct change_head* get_change_head(struct change_table *heads, > return NULL; > } > > - index = (long)item->util; > + index = (long)(intptr_t)item->util; > return &(heads->heads.array[index]); > } >
Stefan Xenos <sxenos@google.com> writes: > Sorry, folks. I normally can't do any open source work on weekdays. > That also includes writing responses on the mailing list, so there > will normally be a week or two lag for me to iterate on this sort of > thing. > > Feel free to either include this fix or revert my patch if there's a > problem with it - just let me know what you selected. I'll roll with > it and either resubmit with the requested changes or submit the > requested changes as follow-ups. I think double casting Dscho did was not his ideal "fix" but he did it as a mere workaround to force the 'pu' branch to compile. And I also agree with him that the double casting workaround is too ugly to live, compared to a union he suggests. So I'd rather kick the branch out of 'pu' for now. Thanks, both. > > - Stefan > > On Mon, Jan 28, 2019 at 3:08 PM Johannes Schindelin > <Johannes.Schindelin@gmx.de> wrote: >> >> Hi Junio, >> >> On Mon, 28 Jan 2019, Johannes Schindelin wrote: >> >> > On Sun, 27 Jan 2019, sxenos@google.com wrote: >> > >> > > + new_item->util = (void*)index; >> > >> > This is not good. You are using a `long` here. The 80s called and want >> > their now-obsolete data types back. >> > >> > If you want a data type that can take an integer but also a pointer, use >> > `intptr_t` instead. >> > >> > But even that is not good practice. What you really want here is to use a >> > union of the data types that you want to store in that `util` field. >> > >> > This is not merely academic, your code causes compile errors on Windows: >> > >> > https://dev.azure.com/gitgitgadget/git/_build/results?buildId=400&view=logs&jobId=fd490c07-0b22-5182-fac9-6d67fe1e939b&taskId=ce91d5d6-0c55-50f5-8ab9-6695c03ab102&lineStart=430&lineEnd=440&colStart=1&colEnd=1 >> >> Since Stefan did not grace us with an answer, Junio, could I ask you to >> squash this in (which is by no means a satisfactory fix, but it is a >> stopgap to get `pu` building again)? >> >> -- snipsnap -- >> diff --git a/change-table.c b/change-table.c >> index 2e0d935de846..197ce2783532 100644 >> --- a/change-table.c >> +++ b/change-table.c >> @@ -103,7 +103,7 @@ void change_table_add(struct change_table *to_modify, const char *refname, >> new_head->hidden = starts_with(refname, "refs/hiddenmetas/"); >> >> new_item = string_list_insert(&to_modify->refname_to_change_head, refname); >> - new_item->util = (void*)index; >> + new_item->util = (void *)(intptr_t)index; >> // Use pointers to the copy of the string we're retaining locally >> refname = new_item->string; >> >> @@ -201,6 +201,6 @@ struct change_head* get_change_head(struct change_table *heads, >> return NULL; >> } >> >> - index = (long)item->util; >> + index = (long)(intptr_t)item->util; >> return &(heads->heads.array[index]); >> } >>
Works with me. I'll resubmit without the double casting next chance I have to work on it. My long-term plan for that struct was to use the memory pool for all allocations anyway. I think that should let me implement it without moving objects around, which will make their addresses stable. That should let me use pointers for everything, without the ints - so I probably won't need the union. On Tue, Jan 29, 2019 at 10:02 AM Junio C Hamano <gitster@pobox.com> wrote: > > Stefan Xenos <sxenos@google.com> writes: > > > Sorry, folks. I normally can't do any open source work on weekdays. > > That also includes writing responses on the mailing list, so there > > will normally be a week or two lag for me to iterate on this sort of > > thing. > > > > Feel free to either include this fix or revert my patch if there's a > > problem with it - just let me know what you selected. I'll roll with > > it and either resubmit with the requested changes or submit the > > requested changes as follow-ups. > > I think double casting Dscho did was not his ideal "fix" but he did > it as a mere workaround to force the 'pu' branch to compile. And I > also agree with him that the double casting workaround is too ugly > to live, compared to a union he suggests. So I'd rather kick the > branch out of 'pu' for now. > > Thanks, both. > > > > > - Stefan > > > > On Mon, Jan 28, 2019 at 3:08 PM Johannes Schindelin > > <Johannes.Schindelin@gmx.de> wrote: > >> > >> Hi Junio, > >> > >> On Mon, 28 Jan 2019, Johannes Schindelin wrote: > >> > >> > On Sun, 27 Jan 2019, sxenos@google.com wrote: > >> > > >> > > + new_item->util = (void*)index; > >> > > >> > This is not good. You are using a `long` here. The 80s called and want > >> > their now-obsolete data types back. > >> > > >> > If you want a data type that can take an integer but also a pointer, use > >> > `intptr_t` instead. > >> > > >> > But even that is not good practice. What you really want here is to use a > >> > union of the data types that you want to store in that `util` field. > >> > > >> > This is not merely academic, your code causes compile errors on Windows: > >> > > >> > https://dev.azure.com/gitgitgadget/git/_build/results?buildId=400&view=logs&jobId=fd490c07-0b22-5182-fac9-6d67fe1e939b&taskId=ce91d5d6-0c55-50f5-8ab9-6695c03ab102&lineStart=430&lineEnd=440&colStart=1&colEnd=1 > >> > >> Since Stefan did not grace us with an answer, Junio, could I ask you to > >> squash this in (which is by no means a satisfactory fix, but it is a > >> stopgap to get `pu` building again)? > >> > >> -- snipsnap -- > >> diff --git a/change-table.c b/change-table.c > >> index 2e0d935de846..197ce2783532 100644 > >> --- a/change-table.c > >> +++ b/change-table.c > >> @@ -103,7 +103,7 @@ void change_table_add(struct change_table *to_modify, const char *refname, > >> new_head->hidden = starts_with(refname, "refs/hiddenmetas/"); > >> > >> new_item = string_list_insert(&to_modify->refname_to_change_head, refname); > >> - new_item->util = (void*)index; > >> + new_item->util = (void *)(intptr_t)index; > >> // Use pointers to the copy of the string we're retaining locally > >> refname = new_item->string; > >> > >> @@ -201,6 +201,6 @@ struct change_head* get_change_head(struct change_table *heads, > >> return NULL; > >> } > >> > >> - index = (long)item->util; > >> + index = (long)(intptr_t)item->util; > >> return &(heads->heads.array[index]); > >> } > >>
diff --git a/Makefile b/Makefile index 7ffc383f2b..09cfd3ef1b 100644 --- a/Makefile +++ b/Makefile @@ -844,6 +844,7 @@ LIB_OBJS += branch.o LIB_OBJS += bulk-checkin.o LIB_OBJS += bundle.o LIB_OBJS += cache-tree.o +LIB_OBJS += change-table.o LIB_OBJS += chdir-notify.o LIB_OBJS += checkout.o LIB_OBJS += color.o diff --git a/change-table.c b/change-table.c new file mode 100644 index 0000000000..6daff5f58c --- /dev/null +++ b/change-table.c @@ -0,0 +1,207 @@ +#include "cache.h" +#include "change-table.h" +#include "commit.h" +#include "ref-filter.h" +#include "metacommit-parser.h" + +void change_table_init(struct change_table *to_initialize) +{ + memset(to_initialize, 0, sizeof(*to_initialize)); + mem_pool_init(&(to_initialize->memory_pool), 0); + to_initialize->memory_pool->block_alloc = 4*1024 - sizeof(struct mp_block); + oidmap_init(&(to_initialize->oid_to_metadata_index), 0); + string_list_init(&(to_initialize->refname_to_change_head), 1); +} + +static void change_list_clear(struct change_list *to_clear) { + string_list_clear(&to_clear->additional_refnames, 0); +} + +static void commit_change_list_entry_clear( + struct commit_change_list_entry *to_clear) { + change_list_clear(&(to_clear->changes)); +} + +static void change_head_array_clear(struct change_head_array *to_clear) +{ + FREE_AND_NULL(to_clear->array); +} + +void change_table_clear(struct change_table *to_clear) +{ + struct oidmap_iter iter; + struct commit_change_list_entry *next; + for (next = oidmap_iter_first(&to_clear->oid_to_metadata_index, &iter); + next; + next = oidmap_iter_next(&iter)) { + + commit_change_list_entry_clear(next); + } + + oidmap_free(&to_clear->oid_to_metadata_index, 0); + string_list_clear(&(to_clear->refname_to_change_head), 0); + change_head_array_clear(&to_clear->heads); + mem_pool_discard(to_clear->memory_pool, 0); +} + +/* + * Appends a new, empty, change_head struct to the end of the given array. + * Returns the index of the newly-added struct. + */ +static int change_head_array_append(struct change_head_array *to_add) +{ + int index = to_add->nr++; + struct change_head *new_head; + ALLOC_GROW(to_add->array, to_add->nr, to_add->alloc); + new_head = &(to_add->array[index]); + memset(new_head, 0, sizeof(*new_head)); + return index; +} + +static void add_head_to_commit(struct change_table *to_modify, + const struct object_id *to_add, const char *refname) +{ + struct commit_change_list_entry *entry; + + // Note: the indices in the map are 1-based. 0 is used to indicate a missing + // element. + entry = oidmap_get(&(to_modify->oid_to_metadata_index), to_add); + if (!entry) { + entry = mem_pool_calloc(to_modify->memory_pool, 1, + sizeof(*entry)); + oidcpy(&entry->entry.oid, to_add); + oidmap_put(&(to_modify->oid_to_metadata_index), entry); + string_list_init(&(entry->changes.additional_refnames), 0); + } + + if (entry->changes.first_refname == NULL) { + entry->changes.first_refname = refname; + } else { + string_list_insert(&entry->changes.additional_refnames, refname); + } +} + +void change_table_add(struct change_table *to_modify, const char *refname, + struct commit *to_add) +{ + struct change_head *new_head; + struct string_list_item *new_item; + long index; + int metacommit_type; + + index = change_head_array_append(&to_modify->heads); + new_head = &(to_modify->heads.array[index]); + + oidcpy(&new_head->head, &(to_add->object.oid)); + + metacommit_type = get_metacommit_content(to_add, &new_head->content); + if (metacommit_type == METACOMMIT_TYPE_NONE) { + oidcpy(&new_head->content, &(to_add->object.oid)); + } + new_head->abandoned = (metacommit_type == METACOMMIT_TYPE_ABANDONED); + new_head->remote = starts_with(refname, "refs/remote/"); + new_head->hidden = starts_with(refname, "refs/hiddenmetas/"); + + new_item = string_list_insert(&to_modify->refname_to_change_head, refname); + new_item->util = (void*)index; + // Use pointers to the copy of the string we're retaining locally + refname = new_item->string; + + if (!oideq(&new_head->content, &new_head->head)) { + add_head_to_commit(to_modify, &(new_head->content), refname); + } + add_head_to_commit(to_modify, &(new_head->head), refname); +} + +void change_table_add_all_visible(struct change_table *to_modify, + struct repository* repo) +{ + struct ref_filter filter; + const char *name_patterns[] = {NULL}; + memset(&filter, 0, sizeof(filter)); + filter.kind = FILTER_REFS_CHANGES; + filter.name_patterns = name_patterns; + + change_table_add_matching_filter(to_modify, repo, &filter); +} + +void change_table_add_matching_filter(struct change_table *to_modify, + struct repository* repo, struct ref_filter *filter) +{ + struct ref_array matching_refs; + int i; + + memset(&matching_refs, 0, sizeof(matching_refs)); + filter_refs(&matching_refs, filter, filter->kind); + + // Determine the object id for the latest content commit for each change. + // Fetch the commit at the head of each change ref. If it's a normal commit, + // that's the commit we want. If it's a metacommit, locate its content parent + // and use that. + + for (i = 0; i < matching_refs.nr; i++) { + struct ref_array_item *item = matching_refs.items[i]; + struct commit *commit = item->commit; + + commit = lookup_commit_reference_gently(repo, &(item->objectname), 1); + + if (commit != NULL) { + change_table_add(to_modify, item->refname, commit); + } + } + + ref_array_clear(&matching_refs); +} + +static int return_true_callback(const char *refname, void *cb_data) +{ + return 1; +} + +int change_table_has_change_referencing(struct change_table *changes, + const struct object_id *referenced_commit_id) +{ + return for_each_change_referencing(changes, referenced_commit_id, + return_true_callback, NULL); +} + +int for_each_change_referencing(struct change_table *table, + const struct object_id *referenced_commit_id, each_change_fn fn, void *cb_data) +{ + const struct change_list *changes; + int i; + int retvalue; + struct commit_change_list_entry *entry; + + entry = oidmap_get(&table->oid_to_metadata_index, + referenced_commit_id); + // If this commit isn't referenced by any changes, it won't be in the map + if (!entry) { + return 0; + } + changes = &(entry->changes); + if (changes->first_refname == NULL) { + return 0; + } + retvalue = fn(changes->first_refname, cb_data); + for (i = 0; retvalue == 0 && i < changes->additional_refnames.nr; i++) { + retvalue = fn(changes->additional_refnames.items[i].string, cb_data); + } + return retvalue; +} + +struct change_head* get_change_head(struct change_table *heads, + const char* refname) +{ + struct string_list_item *item = string_list_lookup( + &heads->refname_to_change_head, refname); + long index; + + if (!item) { + return NULL; + } + + index = (long)item->util; + return &(heads->heads.array[index]); +} + diff --git a/change-table.h b/change-table.h new file mode 100644 index 0000000000..85bb19c3bf --- /dev/null +++ b/change-table.h @@ -0,0 +1,138 @@ +#ifndef CHANGE_TABLE_H +#define CHANGE_TABLE_H + +#include "oidmap.h" + +struct commit; +struct ref_filter; + +/* + * This struct holds a list of change refs. The first element is stored inline, + * to optimize for small lists. + */ +struct change_list { + /* Ref name for the first change in the list, or null if none. + * + * This field is private. Use for_each_change_in to read. + */ + const char* first_refname; + /* List of additional change refs. Note that this is empty if the list + * contains 0 or 1 elements. + * + * This field is private. Use for_each_change_in to read. + */ + struct string_list additional_refnames; +}; + +/* + * Holds information about the head of a single change. + */ +struct change_head { + /* + * The location pointed to by the head of the change. May be a commit or a + * metacommit. + */ + struct object_id head; + /* + * The content commit for the latest commit in the change. Always points to a + * real commit, never a metacommit. + */ + struct object_id content; + /* + * Abandoned: indicates that the content commit should be removed from the + * history. + * + * Hidden: indicates that the change is an inactive change from the + * hiddenmetas namespace. Such changes will be hidden from the user by + * default. + * + * Deleted: indicates that the change has been removed from the repository. + * That is the ref was deleted since the time this struct was created. Such + * entries should be ignored. + */ + int abandoned:1, + hidden:1, + remote:1, + deleted:1; +}; + +/* + * An array of change_head. + */ +struct change_head_array { + struct change_head* array; + int nr; + int alloc; +}; + +/* + * Holds the list of change refs whose content points to a particular content + * commit. + */ +struct commit_change_list_entry { + struct oidmap_entry entry; + struct change_list changes; +}; + +/* + * Holds information about the heads of each change, and permits effecient + * lookup from a commit to the changes that reference it directly. + * + * All fields should be considered private. Use the change_table functions + * to interact with this struct. + */ +struct change_table { + /** + * Memory pool for the objects allocated by the change table. + */ + struct mem_pool *memory_pool; + /* Map object_id to commit_change_list_entry structs. */ + struct oidmap oid_to_metadata_index; + /* List of ref names. The util value is an int index into change_metadata + * array. + */ + struct string_list refname_to_change_head; + /* change_head structures for each head */ + struct change_head_array heads; +}; + +extern void change_table_init(struct change_table *to_initialize); +extern void change_table_clear(struct change_table *to_clear); + +/* Adds the given change head to the change_table struct */ +extern void change_table_add(struct change_table *to_modify, + const char *refname, struct commit *target); + +/* Adds the non-hidden local changes to the given change_table struct. + */ +extern void change_table_add_all_visible(struct change_table *to_modify, + struct repository *repo); + +/* + * Adds all changes matching the given ref filter to the given change_table + * struct. + */ +extern void change_table_add_matching_filter(struct change_table *to_modify, + struct repository* repo, struct ref_filter *filter); + +typedef int each_change_fn(const char *refname, void *cb_data); + +extern int change_table_has_change_referencing(struct change_table *changes, + const struct object_id *referenced_commit_id); + +/* Iterates over all changes that reference the given commit. For metacommits, + * this is the list of changes that point directly to that metacommit. + * For normal commits, this is the list of changes that have this commit as + * their latest content. + */ +extern int for_each_change_referencing(struct change_table *heads, + const struct object_id *referenced_commit_id, each_change_fn fn, void *cb_data); + +/** + * Returns the change head for the given refname. Returns NULL if no such change + * exists. + */ +extern struct change_head* get_change_head(struct change_table *heads, + const char* refname); + +#endif