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

[Derrick Stolee <dstolee@microsoft.com>]

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(-)

-- 
2.17.0