Re: topological index field for commit objects

From: Jeff King <peff@peff.net>
Date: Jun 29, 2016, 20:56 UTC
Message-ID: <20160629205647.GA25987@sigill.intra.peff.net>
In-Reply-To: <xmqqk2h73f2i.fsf@gitster.mtv.corp.google.com>

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

Show 8 quoted lines

> > 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