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

Thanks for the feedback on the previous version. I think this series is stabilizing nicely. I'll reply to this message with an inter-diff as it is not too large to share but would clutter this cover letter.

Thanks, -Stolee

-- >8 --

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

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 short-circuit mechanism to improve performance of `git branch --contains`.

Further, use generation numbers for 'git tag --contains), 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 is built on ds/lazy-load-trees.

Derrick Stolee (10):
  ref-filter: fix outdated comment on in_commit_list
  commit: add generation number to struct commmit
  commit-graph: compute generation numbers
  commit: use generations in paint_down_to_common()
  commit-graph: always load commit-graph information
  ref-filter: use generation number for --contains
  commit: use generation numbers for in_merge_bases()
  commit: add short-circuit to paint_down_to_common()
  merge: check config before loading commits
  commit-graph.txt: update design document

 Documentation/technical/commit-graph.txt | 30 ++++++--
 alloc.c                                  |  1 +
 builtin/merge.c                          |  7 +-
 commit-graph.c                           | 92 ++++++++++++++++++++----
 commit-graph.h                           |  8 +++
 commit.c                                 | 54 +++++++++++---
 commit.h                                 |  7 +-
 object.c                                 |  2 +-
 ref-filter.c                             | 26 +++++--
 sha1_file.c                              |  2 +-
 t/t5318-commit-graph.sh                  |  9 +++
 11 files changed, 198 insertions(+), 40 deletions(-)

base-commit: 7b8a21dba1bce44d64bd86427d3d92437adc4707