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

[Jakub Narebski <jnareb@gmail.com>]

On Sat, 10 Feb 2008, Linus Torvalds wrote:
> 
> 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.

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

> 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