On Wed, Apr 04, 2018 at 03:22:01PM -0400, Derrick Stolee wrote:
> > I don't know that the reachability property is explicitly promised by
> > your work, but it seems like it would be a natural fallout (after all,
> > you have to know the generation of each ancestor in order to compute the
> > later ones, so you're really just promising that you've actually stored
> > all the ones you've computed).
>
> The commit-graph is closed under reachability, so if a commit has a
> generation number then it is in the graph and so are all its ancestors.
OK, if we assume that it's closed, then I think we can effectively
ignore the UNDEF cases. They'll just work out. And then yes I'd agree
that the:
if (cutoff == UNDEF)
cutoff = NONE;
code is wrong. We'd want to keep it at UNDEF so we stop traversing at
any generation number.
> The reason for GENERATION_NUMBER_NONE is that the commit-graph file stores
> "0" for generation number until this patch. It still satisfies the condition
> that gen(A) < gen(B) if B can reach A, but also gives us a condition for
> "this commit still needs its generation number computed".
OK. I thought at first that would yield wrong results when comparing
UNDEF to NONE, but I think for this kind of --contains traversal, it's
still OK (NONE is less than UNDEF, but we know that the UNDEF thing
cannot be found by traversing from a NONE).
> > If you could make the reachability assumption, I think this question
> > just goes away. As soon as you hit a commit with _any_ generation
> > number, you could quit traversing down that path.
> That is the idea. I should make this clearer in all of my commit messages.
Yes, please. :) And maybe in the documentation of the file format, if
it's not there (I didn't check). It's a very useful property, and we
want to make sure people making use of the graph know they can depend on
it.
-Peff
