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

From: Junio C Hamano <gitster@pobox.com>
Date: Feb 16, 2022, 00:51 UTC
Message-ID: <xmqq1r03zl9z.fsf@gitster.g>
In-Reply-To: <42d2a9fe-a3f2-f841-dcd1-27a0440521b6@github.com>

Derrick Stolee <derrickstolee@github.com> writes:

Show 8 quoted lines

> 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.