Calculating a reachability "diff", a la git rebase

[BatmanAoD]

Apologies in advance if there's a walkthrough or something that I missed when looking through the documentation; this seems like a fairly simple operation conceptually, but I can't tell from the raw gix_commitgraph::Graph API how to implement it.

How can I determine the set of all commits reachable from one commit, but not reachable from another commit? This should be exactly the set of commits that would be included in git rebase -i <other_commit>.

(For context: I believe this is exactly the set of commits that should be considered when determining the list of changes made since the last major release of a codebase: knope-dev/knope#505 (comment))

[Byron]

No worries, there is no high-level overview or 'by-example' book just yet.

This sounds very much like making a revision traversal from a given commit, but not letting it traverse past another commit (the previous release, for instance). This should be possible by using a revision walk with a filter, as it should traverse exactly the commits you would be interested in.

Please note that the commitgraph is an acceleration data structure which is already being used when available for an about 7x speedup.

I hope that helps.

[BatmanAoD]

Thanks!

Trying it out (with gix = "0.53.1"), and looking a little at the code (though I don't understand it thoroughly), it looks like the selected function relies on the filter to return false for the first commit that should be excluded in every possible depth-first path. In other words, when there is a merge structure that allows "bypassing" the filtered tag, I don't know of any efficient way to exclude commits that are reachable by going "around" the previous tag as well as "through" it.

Here's a graphical representation of that situation:

Here's a repo whose commit history is modeled off of that graph. Starting from main (5179399) and filtering out v2.0.0 (ab9826b), then commit dd9a275 should not be included, since it is an ancestor of v2.0.0, but when I use a simple ID equality check in the filter, only ab9826b itself is filtered out.

Git itself must have some efficient way of doing this, I think, based on finding a complete set of common ancestors when starting a rebase operation.

[Byron]

Thanks for making the problem clear! Indeed, the simple filter won't help you when the search reaches a commit through multiple paths.

For this to work, you will need to 'paint' the graph so all ancestors of the excluded commit are identifiable. Then it's possible to extend the filter so it also ignores all ancestors.

The 'trick' then lies in finding a good abort-criterium so you won't have to go through the entire 1.1 million commits of the linux kernel each time.

An example for how to do this is the implementation of git describe, which uses the gix::revwalk::Graph and gix::revwalk::PriorityQueue to orchestrate a traversal (PriorityQueue) and memorize information about the graph (Graph). Early aborts in this case can probably be done if it's clear that all queued commits are in the ancestry of the respective commit.

Please note that usually I study how git implements these algorithms and then 'just' translate these to Rust using the two mentioned data structure - doing so would help you to not miss certain optimisations.

Before I forget, the gix-negotiate crate also has example on how to use these data structures, but it's, to my mind, all a bit difficult to understand due to the level of abstraction and the lack of visualisation.

Lastly, I also think these standard searches should be provided by gix or gix-* crates, so if you come up with anything, please let me know - maybe the code can be adopted.

[dbanty]

I think what we'll want is something like git rev-list, so maybe we can look into the implementation of that command to find what algorithms they use.

[BatmanAoD]

I was curious how jj implements its nearest-common-ancestor function, so I looked for it: https://github.com/martinvonz/jj/blob/main/lib/src/dag_walk.rs#L382

I think in the case of knope it's probably reasonable to just limit the graph search to successors of the common ancestor. For full correctness of implementing rebase I think you'd have to find all common ancestors or just do the paint algorithm on the full graph.

(That jj source file may be useful as reference for its other functions as well.)