We now calculate generation numbers in the commit-graph file and use them in paint_down_to_common().

Expand the section on generation numbers to discuss how the two "special" generation numbers GENERATION_NUMBER_INFINITY and *_ZERO interact with other generation numbers. Signed-off-by: Derrick Stolee <dsto...@microsoft.com> --- Documentation/technical/commit-graph.txt | 50 +++++++++++++++++++++--- 1 file changed, 44 insertions(+), 6 deletions(-) diff --git a/Documentation/technical/commit-graph.txt b/Documentation/technical/commit-graph.txt index 0550c6d0dc..a8df0ae9db 100644 --- a/Documentation/technical/commit-graph.txt +++ b/Documentation/technical/commit-graph.txt @@ -77,6 +77,49 @@ in the commit graph. We can treat these commits as having "infinite" generation number and walk until reaching commits with known generation number. +We use the macro GENERATION_NUMBER_INFINITY = 0xFFFFFFFF to mark commits not +in the commit-graph file. If a commit-graph file was written by a version +of Git that did not compute generation numbers, then those commits will +have generation number represented by the macro GENERATION_NUMBER_ZERO = 0. + +Since the commit-graph file is closed under reachability, we can guarantee +the following weaker condition on all commits: + + If A and B are commits with generation numbers N amd M, respectively, + and N < M, then A cannot reach B. + +Note how the strict inequality differs from the inequality when we have +fully-computed generation numbers. Using strict inequality may result in +walking a few extra commits, but the simplicity in dealing with commits +with generation number *_INFINITY or *_ZERO is valuable. + +Here is a diagram to visualize the shape of the full commit graph, and +how different generation numbers relate: + + +-----------------------------------------+ + | GENERATION_NUMBER_INFINITY = 0xFFFFFFFF | + +-----------------------------------------+ + | | ^ + | | | + | +------+ + | [gen(A) = gen(B)] + V + +-------------------------------------+ + | 0 < commit->generation < 0x40000000 | + +-------------------------------------+ + | | ^ + | | | + | +------+ + | [gen(A) > gen(B)] + V + +-------------------------------------+ + | GENERATION_NUMBER_ZERO = 0 | + +-------------------------------------+ + | ^ + | | + +------+ + [gen(A) = gen(B)] + Design Details -------------- @@ -98,17 +141,12 @@ Future Work - The 'commit-graph' subcommand does not have a "verify" mode that is necessary for integration with fsck. -- The file format includes room for precomputed generation numbers. These - are not currently computed, so all generation numbers will be marked as - 0 (or "uncomputed"). A later patch will include this calculation. - - After computing and storing generation numbers, we must make graph walks aware of generation numbers to gain the performance benefits they enable. This will mostly be accomplished by swapping a commit-date-ordered priority queue with one ordered by generation number. The following - operations are important candidates: + operation is an important candidate: - - paint_down_to_common() - 'log --topo-order' - Currently, parse_commit_gently() requires filling in the root tree -- 2.17.0