[PATCH 3/5] commit: add commit_generation function

A commit's generation is its height in the history graph, as measured from the farthest root. It is defined as:

  - If the commit has no parents, then its generation is 0.

  - Otherwise, its generation is 1 more than the maximum of
    its parents generations.

The following diagram shows a sample history with generations:

  A(0)--B(1)--C(2)------G(5)--H(6)
         \             /
          D(2)--E(3)--F(4)

Note that C and D have the same generation, as they are both children of B. Note also that the merge commit G's generation is 5, not 3, as we take the maximum of its parents' generations.

Generation numbers can be useful for bounding traversals. For example, if we have two commits with generations 500 and 600, we know that the second cannot be an ancestor of the first. The first could be an ancestor of the second, but we can't know unless we traverse the history graph. However, when walking backwards from the "600" commit, once we reach generation "499", we know that the "500" commit cannot be an ancestor of the "499" commit, and we can stop the traversal without even looking at the earlier parts of the history.

We already do something similar with commit timestamps in many traversals. However, timestamps are somewhat untrustworthy, as we have to deal with clock skew and with imports from buggy systems.

Generation numbers are easy to calculate recursively, though you have to go to the roots to do so. This patch calculates and stores them in a persistent cache. It uses a simple recursive algorithm; you could probably drop the recursion by topologically sorting a list of all commits and filling in generation numbers left to right. But the recursive definition coupled with the cache make it very cheap to calculate generation numbers for new commits at the tip of history (you only have to traverse back to the last cached parents).

We could also store generation numbers in the commit header directly. These would be faster to look at than an external cache (they would be on par speed-wise with commit timestamps). But there are a few reasons not to:

  1. The reason to avoid commit timestamps is that they are
     unreliable. Generation numbers would probably be more
     reliable, but they are still redundant with the actual
     graph structure represented by the parent pointers, and
     can therefore be out of sync with the parent
     information. By calculating them ourselves, we know
     they are correct.

  2. With grafts and replacement objects, the graph
     structure (and thus the generation numbers) can be
     changed. So the generation number, while immutable for
     a given commit object, can be changed when we "lie"
     about the graph structure via these mechanisms. Being
     able to simply clear the cache when these things are
     changed is helpful.

  3. There's a lot of existing git history without
     generation headers. So we'd still need to have the same
     cache to handle those cases.

  4. It generally pollutes the header with redundant
     information, which we try to avoid. Putting it in the
     commit header is purely a speedup, and it seems we can
     get similar performance with a generation cache.

Signed-off-by: Jeff King <peff@peff.net>
---
 commit.c |   48 ++++++++++++++++++++++++++++++++++++++++++++++++
 commit.h |    2 ++
 2 files changed, 50 insertions(+), 0 deletions(-)