Re: topological index field for commit objects

[Jeff King <peff@peff.net>]

On Wed, Jun 29, 2016 at 01:39:17PM -0700, Junio C Hamano wrote:

> > Would it make sense to refuse creating commits that have a commit date
> > prior to its parents commit date (except when the user gives a
> > `--dammit-I-know-I-break-a-wildy-used-heuristic`)?
> 
> I think that has also been discussed in the past.  I do not think it
> would help very much in practice, as projects already have up to 10
> years (and the ones migrated from CVS, even more) worth of commits
> they cannot rewrite that may record incorrect committer dates.

Yep, it has been discussed and I agree it runs into a lot of corner
cases.

> If the use of generation number can somehow be limited narrowly, we
> may be able to incrementally introduce it only for new commits, but
> I haven't thought things through, so let me do so aloud here ;-)

I think the problem is that you really _do_ want generation numbers for
old commits. One of the most obvious cases is something like "tag
--contains HEAD", because it has to examine older tags.

So your history looks something like:

  A -- B -- ... Z
        \        \
	 v1.0     HEAD

Without generation numbers (or some proxy), you have to walk the history
between B..Z to find the answer. With generation numbers, it is
immediately obvious.

So this is the ideal case for generation numbers (the worst cases are
when the things you are looking for are in branchy, close history where
the generation numbers don't tell you much; but in such cases the
walking is usually not too bad).

So I think you really do want to be able to generate and store
generation numbers after the fact. That has an added bonus that you do
not have to worry about baking incorrect values into your objects; you
do the topological walk once, and you _know_ it is correct (at least as
correct as the parent links, but that is our source of truth).

I have patches that generate and store the numbers at pack time, similar
to the way we do the reachability bitmaps. They're not production ready,
but they could probably be made so without too much effort. You wouldn't
have ready-made generation numbers for commits since the last full
repack, but you can compute them incrementally based on what you do have
at a cost linear to the unpacked commits (this is the same for bitmaps).

-Peff