Re: [RFH] revision limiting sometimes ignored

From: Junio C Hamano <gitster@pobox.com>
Date: Feb 6, 2008, 01:51 UTC
Message-ID: <7v7ihi7syj.fsf@gitster.siamese.dyndns.org>
In-Reply-To: <alpine.LSU.1.00.0802052228280.8543@racer.site>

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

> In our case, this would mean that the revision walker should realise that 
> a child whose date is not older than its parent commit must be wrong.  And 
> just take the parent's date instead (but maybe only for the purpose of 
> limiting).

No.

	1---2---3---4

Timestamps are 2 < 3 < 4 < 1 and you ask:

	$ git rev-list 1 ^4

We push 1 and ^4 in "list". We pick 1 and push it out to "newlist" (possible results, but the hope is they may later be marked as UNINTERESTING as we traverse the remaining one still on "list"). We pick ^4, mark 3 as UNINTERESTING and push ^3 into "list", and realize there is nobody that is still positive (i.e. without UNINTERESTING bit). We have "clever" optimization that stops in such a case.

Nowhere in this sequence we can notice that "A child whose date is not older than its parent". We do not even get to commit 2 during the traversal.

In order to notice the problem, you need to make sure we will see the link between 1 and 2 (i.e. the fact that 1 has a child that is older than itself). That would take traversing "all the way down".

The "all the way down" is not quite correct, though. If we have other commits, like this:

              B---C
             /
     ---0---A---1---2---3---4

where timestamps are 0 < A < B < C < 2 < 3 < 4 < 1, and if you ask:

	$ git rev-list 1 ^4 ^A
	$ git rev-list 1 ^4 ^B
	$ git rev-list 1 ^4 ^C

we will have a similar issue. We do not have to go down the potentially long history beyond A. But we at least need to traverse down to the merge base of negatives in "list" and positives in "newlist" when "list" becomes all UNINTERESTING (in this case, traverse all paths as if we are trying to find out the merge-base between 1 and 3. That traversal will see 2 and we will see your clock skew).

But the point is that the condition you mentioned cannot be found out unless you traverse to 2, and at that point you have traversed enough already.

As Linus earlier said, the question really is: for positive commits in "newlist", have we not missed any its UNINTERESTING descendants?

For a toy-scale graph, a parallel merge-base traversal like what show-branch does may work, but for a real workload, newlist would contain literally hundreds of commits, so using unaltered "merge-base" algorithm is probably not an option either.