Re: [PATCH] name-rev: test showing failure with non-monotonic commit dates

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

Derrick Stolee <derrickstolee@github.com> writes:

> I initially thought that generation numbers could help. The usual way
> is to use a priority queue that explores by generation, not commit
> date. This approach was immediately stifled by these lines:
>
> 	memset(&queue, 0, sizeof(queue)); /* Use the prio_queue as LIFO */
> 	prio_queue_put(&queue, start_commit);
>
> So the queue is really a stack.

Hmph, I am not sure if stifled is a word, but I agree that this one
is not solvable by "we have a priority queue that explores by commit
date, and using generation numbers instead of commit date will give
us a more stable result when clock skews are involved", because the
traversal is not the usual "we pop the newest commit seen so far to
dig into older history".

However.

> It is still possible that the cutoff could be altered to use generation
> numbers instead of commit dates, but I haven't looked closely enough to
> be sure.

In "name-rev [--tags] C", we look for a tag to use in describing the
given commit C as an ancestry path starting at the tag T (e.g. T~4,
T~2^2).  There can be multiple such tags (e.g. it is likely that a
commit that is v1.0~2 is also reachable from tag v2.0, even though
it would require more hops).  We try to and find a tag that gives
the "simplest" path.  For that purpose, it is no use to consider any
tag that is not a descendant of the given commit, because doing an
ancestry traversal starting from such a tag will never reach the
commit.  In a world where everybody's clock is in sync, if commit
was made at time X, any tag that was made before time X will not be
a descendant of the commit, so we do not add such a tag to the
candidate pool.

I think the idea of "cutoff" heuristic is exactly what generation
numbers can improve, in an imperfect world where there are imperfect
clocks.