Re: Add "--show-all" revision walker flag for debugging

From: Jakub Narebski <jnareb@gmail.com>
Date: Feb 10, 2008, 22:53 UTC
Message-ID: <200802102353.40230.jnareb@gmail.com>
In-Reply-To: <alpine.LFD.1.00.0802101241590.2896@woody.linux-foundation.org>

On Sat, 10 Feb 2008, Linus Torvalds wrote:

Show 11 quoted lines

> 
> On Sun, 10 Feb 2008, Jakub Narebski wrote:
> > 
> > P.S. Would having generation + roots be enough?
>
> I'm wavering here. Maybe just "generation" works (the longest path from 
> any root), because what we are looking for is essentially "guarantee that 
> this commit cannot possibly be reached from that other commit", and I 
> guess a simple generation count actually does work for that (if the 
> generation of "x" is smaller than the generation of "y", we definitely 
> cannot reach y from x).

Well, "generation" number alone would work quote well as an exclusion mechanism; generation + roots would work better, I think.

Lets take for an example the following revision graph:

roots: a a a aA aA gen: 1 2 3 4 5

       a----b----c----d----e
                     /
            A----B--/

gen: 1 2 roots: A A

For example lone generation number is enough to decide that 'c' (generation 3) cannot be reached from 'a' (generation 1 < 3), and that 'c' (generation 3) cannot be reached from 'B' (generation 2 < 3). Roots allow for easy check that 'B' (gen: 2, roots: A) cannot be reached from 'c' (roots: a, and A \not\in a), but can be reached from 'e' (gen: 5 > 2, roots: aA \ni a).

What I don't know if generation number would be enough to avoid "going to root" or "going to common ancestor" costly case when calculating excluded commits.

Show 5 quoted lines

> At the same time, I'm still not really convinced we need to add the 
> redundant info. I do think I *should* have designed it that way to start 
> with (and I thought so two years ago - blaah), so the strongest reason for 
> "we should add generation numbers" at least for me is that I actually 
> think it's a GoodThing(tm) to have.

While this information can be calculated from revision graph it is I think costly enough that it truly would be better to have it in commit object.

Well, we could always start using core.repositoryFormatVersion ;-)

Show 5 quoted lines

> But adding it is a pretty invasive thing, and would force people to 
> upgrade (it really isn't backwards compatible - old versions of git would 
> immediately refuse to touch archives with even just a single top commit 
> that has a generation number in it, unless we'd hide it at the end of the 
> buffer and just uglify things in general).

Well, we could always add it as a local (per repository) "cache". With only generation numbers we could use pack-index-like format to store a mapping "commit sha-1 => generation number", just like now pack index stores mapping "object sha-1 => offset in pack".

If we want to store also roots, we could either map "commit sha-1 => generation number, roots set offset / id" (constant length value)[*1*], or have gen-*.gen file with generation numbers and roots, and gen-*.idx as index to that file.

[*1*] If I understand math correctly it would limit us in theory to up to 64 roots (git.git has 8 roots IIRC).

-- 
Jakub Narebski
Poland