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, sxe...@google.com wrote:
> From: Stefan Xenos <sxe...@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 <sxe...@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
>
>
>
