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

From: Jeff King <peff@peff.net>
Date: Apr 4, 2018, 19:42 UTC
Message-ID: <20180404194248.GA14055@sigill.intra.peff.net>
In-Reply-To: <fcded90f-cb12-dafd-f21a-18ea67e99406@gmail.com>

On Wed, Apr 04, 2018 at 03:22:01PM -0400, Derrick Stolee wrote:

Show 8 quoted lines

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