[v3,5/8] evolve: Add the change-table structure

Commit Message

Stefan Xenos Jan. 27, 2019, 7:44 p.m. UTC

From: Stefan Xenos <[e-mail]>

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 <[e-mail]>
---
 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

Comments

Johannes Schindelin Jan. 28, 2019, 8:01 a.m. UTC | #1

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, [e-mail] wrote:

> From: Stefan Xenos <[e-mail]>
> 
> 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 <[e-mail]>
> ---
>  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
> 
> 
>

Johannes Schindelin Jan. 28, 2019, 11:08 p.m. UTC | #2

Hi Junio,

On Mon, 28 Jan 2019, Johannes Schindelin wrote:

> On Sun, 27 Jan 2019, [e-mail] 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 Jan. 28, 2019, 11:24 p.m. UTC | #3

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
<[e-mail]> wrote:
>
> Hi Junio,
>
> On Mon, 28 Jan 2019, Johannes Schindelin wrote:
>
> > On Sun, 27 Jan 2019, [e-mail] 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]);
>  }
>

Junio C Hamano Jan. 29, 2019, 6:02 p.m. UTC | #4

Stefan Xenos <[e-mail]> 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
> <[e-mail]> wrote:
>>
>> Hi Junio,
>>
>> On Mon, 28 Jan 2019, Johannes Schindelin wrote:
>>
>> > On Sun, 27 Jan 2019, [e-mail] 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 Jan. 29, 2019, 6:09 p.m. UTC | #5

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 <[e-mail]> wrote:
>
> Stefan Xenos <[e-mail]> 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
> > <[e-mail]> wrote:
> >>
> >> Hi Junio,
> >>
> >> On Mon, 28 Jan 2019, Johannes Schindelin wrote:
> >>
> >> > On Sun, 27 Jan 2019, [e-mail] 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]);
> >>  }
> >>

Patch

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