Re: git and time

From: Junio C Hamano <junkio@cox.net>
Date: Oct 1, 2006, 08:07 UTC
Message-ID: <7vbqow5uht.fsf@assigned-by-dhcp.cox.net>
In-Reply-To: <7v64f47uix.fsf@assigned-by-dhcp.cox.net>

Junio C Hamano <junkio@cox.net> writes:

Show 24 quoted lines

> Linus Torvalds <torvalds@osdl.org> writes:
>
>> On Sat, 30 Sep 2006, Junio C Hamano wrote:
>>> 
>>> Especially, "find the closest ancestor" behaviour means when you
>>> get "tag-gXXXX" as an answer, the tag proper does _not_ contain
>>> the given commit (e.g. commit v1.4.2-g4839bd8 is not part of
>>> v1.4.2).
>>
>> Correct.
>>
>> But that just means that we should take the _next_ one in the time-ordered 
>> list, no?
>
> I do not think so.
>
> Extending the example (sorry for doing the same topic on two
> separate threads) I just gave Jeff on "fix based on v0.99",
> after finding that the fix is based on v0.99, finding another
> commit that immediately followed the v0.99 commit on my master
> branch does not help finding out that I very recently merged the
> fix in at all.  I think we cannot get away without honestly
> doing the first descendant, which is unfortunately a lot more
> expensive.

Maybe not *that* expensive.  Here is an outline, thinking aloud.

When describing a commit and a ref, we first run the ancestry traversal algorithm merge-base uses internally. If the tip of the ref is not a descendant of the commit, abort (I'll justify this in a moment).

Otherwise, we would already have parsed all the necessary commits we need to determine which commits on the given ref's ancestry is the first one that is a descendant of the target commit at this point. We collect these commits in a set, and then mark the ones that are immediate children of the target commit, then the ones that are children of them, etc. until we find all the descendant of the target commit.

After that, we can bisect the reflog for the ref to find the first commit that we have marked as a descendant of the target commit in the above process.

If the tip of the ref is not a descendant of the commit to begin with, that does not automatically mean that the target commit has never been part of the ref -- the ref _could_ have contained it and then later got rewound. But then the question "when did the commit has become part of this branch" itself stops being interesting. It would not do us much good if we know it was part of the branch for only two days last week but it is not contained in the branch anymore.