support git 2.19's commit-graph
Nobody has claimed this yet.
- Dominant language
- C
- Stars
- 10.6k
- Forks
- 2.7k
- PR merge metrics
- No merged PRs in 30d
Description
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-graphfiles, and a fuzzer because parsing is hard. #5762 - Support for reading the commit metadata and generation numbers from existing
commit-graphfiles. (in other words, this will ignore any path-based bloom filters). #5763 - Support knowing whether a
commit-graphfile has been modified since it was parsed #5764 - Modify
git_commit_list_parse()to take advantage of thecommit-graphmetadata, if available, which avoids going to the odb, looking up the object, and parsing the commit. #5765 - Modify the functions
mark_parents()andpaint_down_to_common()to take advantage of thecommit-graphmetadata, if available, which can prevent multiple visitations due to commit time inversions. #5766 - Refactor
git_merge__bases_many()so that it can take a minimum generation number. That waygit_graph_descendant_of()can specify this minimum generation number to cut down the BFS earlier than what it would in a regulargit_merge_base(), and implementgit_graph_reachable_from_any()which is analogous togit_merge_base_many()and uses the fancy newgit_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) #5767 - Support for creating a
commit-graphfile from an open repository. #5778 - Support for creating
commit-graphchains, so that the cost of updating acommit-graphis reduced to only the commits that have changed since the last file / chain was written.
Relevant documentation:
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with the Git commit-graph technical documentation and libgit2's existing support for creating a commit-graph file, including the completed work linked in this issue. Trace how updates currently write graph data, then define the chain behavior so updating a graph processes only commits changed since the previous file or chain was written. Done means commit-graph chains can be created and reduce update cost as described.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- c, git
- Domain
- devtools
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100