libgit2/libgit2 — pull request #1131 by scottjg (2012-12-10 06:10:02+00:00)
Title: Fix an issue with ahead-behind for lopsided traversal

The ahead-behind algorithm previously relied on merge-base as a first pass, to mark all commit as a parent of either the first or second commit passed to the ahead-behind function. Unfortunately there are some cases where the merge-base algorithm can bail out early, which leaves certain paths unmarked. Normally, this is unlikely, due to the timestamp priority-queue traversal heuristic, but it can happen.

Each iteration of the merge-base loop will check all pending commits in the traversal queue. If any commit is on a path that's not marked as STALE (parent of a merge-base), it is considered "interesting", and the loop will continue. The trouble starts when one traversal path reaches a root commit and thus, queues no children. Now, only the remaining paths on the queue will be verified as interesting. If all of them are un-interesting, the loop will stop, but the path that led to the root commit may be unmarked.

This fix forks the merge-base code into a mark_parents() function, which specifically addresses the issue with root commits by keeping any root commits in a traversal in a separate list, which is also verified during the STALE check, on each loop iteration. If ever hit a root commit during the traversal, the root commit will have to be marked before the mark_parents() function can stop traversing the commits.

In the common case, where we don't hit a root commit, the behavior should remain the same as it was (no root commits end up queued or checked).

@peff and I had talked about this problem somewhat. This was the best solution I could come up with, but I'm all ears if someone has a better idea.