Re: [RFC/PATCHv2 6/6] limit "contains" traversals based on commit generation

[Junio C Hamano <gitster@pobox.com>]

Jeff King <peff@peff.net> writes:

>>    So how about marking commits (using the metainfo-cache facility) that
>>    has an ancestor (not necessarily its direct parent) that records a
>>    younger timestamp (e.g. 1 is such a commit, as its ancestors include
>>    things like 2 and 4)? There should be relatively small number of them,
>>    and still_interesting() logic can be told to dig through such commits
>>    even if everybody is uninteresting in the active list.
> ...
>>  * As to "tag --contains", when timestamp based heuristics breaks down is
>>    when a tagged commit incorrectly records way young timestamp or the
>>    "want" commit records way old timetsamp. I haven't thought things
>>    through, but the same metainfo-cache may be useful to detect which
>>    commit to dig through ignoring the cutoff heuristics.
>
> It can also break down if intermediate commits are wrong, because we
> have to traverse backwards, and we may erroneously cutoff early.
>
> For example:
>
>    A--B--C
>
>    timestamp(A) = 2
>    timestamp(B) = 1 # skewed!
>    timestamp(C) = 3
>
> If tag=C and want=A, then we traverse backwards from C. We can't stop
> immediately because we know that 2 < 3. But we go back to B, and see
> that 2 > 1, and assume that A cannot possibly be an ancestor of B.

I envisioned that the metainfo-cache to help rev-list I mentioned earlier
would mark B having an ancestor A that has a timestamp younger than it, so
I think we can certainly notice that we have to "dig through" B.