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

quoted text
> 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.
-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html