Re: [PATCH v2 03/10] commit: add generation number to struct commmit

From: Junio C Hamano <gitster@pobox.com>
Date: Apr 11, 2018, 02:31 UTC
Message-ID: <xmqqefjmzd67.fsf@gitster-ct.c.googlers.com>
In-Reply-To: <20180409164131.37312-4-dstolee@microsoft.com>

Derrick Stolee <dstolee@microsoft.com> writes:

Show 17 quoted lines

> The generation number of a commit is defined recursively as follows:
>
> * If a commit A has no parents, then the generation number of A is one.
> * If a commit A has parents, then the generation number of A is one
>   more than the maximum generation number among the parents of A.
>
> Add a uint32_t generation field to struct commit so we can pass this
> information to revision walks. We use two special values to signal
> the generation number is invalid:
>
> GENERATION_NUMBER_ININITY 0xFFFFFFFF
> GENERATION_NUMBER_ZERO 0
>
> The first (_INFINITY) means the generation number has not been loaded or
> computed. The second (_ZERO) means the generation number was loaded
> from a commit graph file that was stored before generation numbers
> were computed.

Should it also be possible for a caller to tell if a given commit has too deep a history, i.e. we do not know its generation number exactly, but we know it is larger than 1<<30?

It seems that we only have a 30-bit field in the file, so wouldn't we need a special value defined in (e.g. "0") so that we can tell that the commit has such a large generation number? E.g.

> +	item->generation = get_be32(commit_data + g->hash_len + 8) >> 2;

	if (!item->generation)
		item->generation = GENERATION_NUMBER_OVERFLOW;

when we read it from the file?

We obviously need to do something similar when assigning a generation number to a child commit, perhaps like

	#define GENERATION_NUMBER_OVERFLOW (GENERATION_NUMBER_MAX + 1)

	commit->generation = 1; /* assume no parent */
	for (p = commit->parents; p; p++) {
		uint32_t gen = p->item->generation + 1;

		if (gen >= GENERATION_NUMBER_OVERFLOW) {
			commit->generation = GENERATION_NUMBER_OVERFLOW;
			break;
		} else if (commit->generation < gen)
			commit->generation = gen;
	}
        
or something?  And then on the writing side you'd encode too large a
generation as '0'.