libgit2 / libgit2/libgit2

support git 2.19's commit-graph

Open
#5,757 0 comments 0 reactions 0 assignees View on GitHub

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-graph files, and a fuzzer because parsing is hard. #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). #5763
  • Support knowing whether a commit-graph file has been modified since it was parsed #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. #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. #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) #5767
  • Support for creating a commit-graph file from an open repository. #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:

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.