Starting from version 2.19, git supports commit-graph, which allows for some significant improvements in the performance of several graph-based operations. Notably computing the merge base between two (or more) commits and determining whether one commit is ahead/behind of another.

This should be relatively straightforward to implement. Similar to #5399, this can be split into several chunks for ease of reviewing:

• Support for parsing existing commit-graph files, and a fuzzer because parsing is hard. commit-graph: Introduce a parser for commit-graph files #5762
• Support for reading the commit metadata and generation numbers from existing commit-graph files. (in other words, this will ignore any path-based bloom filters). commit-graph: Support lookups of entries in a commit-graph #5763
• Support knowing whether a commit-graph file has been modified since it was parsed commit-graph: Introduce git_commit_graph_needs_refresh() #5764
• Modify git_commit_list_parse() to take advantage of the commit-graph metadata, if available, which avoids going to the odb, looking up the object, and parsing the commit. commit-graph: Use the commit-graph in revwalks #5765
• Modify the functions mark_parents() and paint_down_to_common() to take advantage of the commit-graph metadata, if available, which can prevent multiple visitations due to commit time inversions. commit-graph: Introduce git_commit_list_generation_cmp #5766
• Refactor git_merge__bases_many() so that it can take a minimum generation number. That way git_graph_descendant_of() can specify this minimum generation number to cut down the BFS earlier than what it would in a regular git_merge_base(), and implement git_graph_reachable_from_any() which is analogous to git_merge_base_many() and uses the fancy new git_merge__bases_many() that knows about the minimum generation number. This can be used to have the concept of private/protected/public branches, so that users of a repository have different permissions depending on the reachability of a commit from any of a set of tips. (a.k.a. the whole reason I am writing all of this, ha) graph: Create git_graph_reachable_from_any() #5767
• Support for creating a commit-graph file from an open repository. commit-graph: Add a way to write commit-graph files #5778
• Support for creating commit-graph chains, so that the cost of updating a commit-graph is reduced to only the commits that have changed since the last file / chain was written.

Relevant documentation:

• https://github.com/git/git/blob/master/Documentation/technical/commit-graph.txt
• https://github.com/git/git/blob/master/Documentation/technical/commit-graph-format.txt