[PATCH v2 00/10] Compute and consume generation numbers

Thanks for the lively discussion of this patch series in v1!

I've incorporated the feedback from the previous round, added patches [7/6] and [8/6], expanded the discussion of generation numbers in the design document, and added another speedup for 'git branch --contains'.

One major difference: I renamed the macros from _UNDEF to _INFINITY and _NONE to _ZERO. This communicates their value more clearly, since the previous names were unclear about which was larger than the "real" generation numbers.

Patch 2 includes a change to builtin/merge.c and a new test in t5318-commit-graph.sh that exposes a problem I found when testing the previous patch series on my box. The "BUG: bad generation skip" message from "commit.c: use generation to halt paint walk" would halt a fast- forward merge since the HEAD commit was loaded before the core.commitGraph config setting was loaded. It is crucial that all commits that exist in the commit-graph file are loaded from that file or else we will lose our expected inequalities of generation numbers.

Thanks, -Stolee

-- >8 --

This is the one of several "small" patches that follow the serialized Git commit graph patch (ds/commit-graph).

As described in Documentation/technical/commit-graph.txt, the generation number of a commit is one more than the maximum generation number among its parents (trivially, a commit with no parents has generation number one). This section is expanded to describe the interaction with special generation numbers GENERATION_NUMBER_INFINITY (commits not in the commit-graph file) and *_ZERO (commits in a commit-graph file written before generation numbers were implemented).

This series makes the computation of generation numbers part of the commit-graph write process.

Finally, generation numbers are used to order commits in the priority queue in paint_down_to_common(). This allows a constant-time check in queue_has_nonstale() instead of the previous linear-time check.

Further, use generation numbers for '--contains' queries in 'git tag' and 'git branch', providing a significant speedup (at least 95% for some cases).

A more substantial refactoring of revision.c is required before making 'git log --graph' use generation numbers effectively.

This patch series depends on v7 of ds/commit-graph.

Derrick Stolee (10):
  object.c: parse commit in graph first
  merge: check config before loading commits
  commit: add generation number to struct commmit
  commit-graph: compute generation numbers
  commit: use generations in paint_down_to_common()
  commit.c: use generation to halt paint walk
  commit-graph.txt: update future work
  ref-filter: use generation number for --contains
  commit: use generation numbers for in_merge_bases()
  commit: add short-circuit to paint_down_to_common()

 Documentation/technical/commit-graph.txt | 50 +++++++++++++--
 alloc.c                                  |  1 +
 builtin/merge.c                          |  5 +-
 commit-graph.c                           | 48 +++++++++++++++
 commit.c                                 | 78 ++++++++++++++++++++----
 commit.h                                 |  5 ++
 object.c                                 |  4 +-
 ref-filter.c                             | 24 ++++++--
 t/t5318-commit-graph.sh                  |  9 +++
 9 files changed, 197 insertions(+), 27 deletions(-)