Re: [PATCH 7/6] ref-filter: use generation number for --contains

[Jeff King <peff@peff.net>]

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