Derrick Stolee <derrickstolee@xxxxxxxxxx> 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.
