Please consider adding an isAnyReachable method to ReachabilityChecker

[EdwinKempin]

Description

In Gerrit we have a few places where we iterate over a set of commits to see if any of them is reachable from a start commit (e.g. [1,2]). It would be nice if ReachabilityChecker could offer a isAnyReachable method for this, so that we can make a single call to ReachabilityChecker, instead of calling areAllReachable multiple times.

For reference, see the discussion at [3].

[1] https://gerrit-review.git.corp.google.com/c/gerrit/+/501982

[2] https://gerrit-review.git.corp.google.com/c/gerrit/+/502022

[3] https://gerrit-review.git.corp.google.com/c/gerrit/+/501982/2/java/com/google/gerrit/server/git/receive/ReceiveCommits.java#3458

Motivation

We hope that having an isAnyReachable method in ReachabilityChecker could provide better performance than calling areAllReachable multiple times. This would help us (Gerrit team) improve the performance of git pushes to Gerrit.

Alternatives considered

No response

Additional context

No response

[tomaswolf]

Honestly said I'm not exactly convinced that the PedestrianReachabilityChecker in its current form is a good idea. As I understand the implementation of TOPO_SORT, it reads the entire history. I don't see how will scale to very long histories. (I also have a hard time wrapping my head around its logic. I have the feeling the parameter names should be swapped. What is currently called "targets" should be named "starts" and vice versa.)

There are some specialized methods in RevWalk like RevWalk.isMergedIntoAnyCommit(). That looks (superficially, at least -- I didn't dig too deep) like a reasonable approach, and it can leverage a commit graph.

I see some commits related to commit graphs that are still open. What is the status here anyway? And what is the relation between commit graphs and bitmapped index?

[jacksondt]

Just some context - the performance issue in Gerrit was trying to prove that none of the prior patchsets were an ancestor of the new patchset. Since this is all Gerrit metadata, I don't think long histories will be a common problem in our case.

We also don't currently generate commit graphs for Gerrit commits. Without preprocessing I think any form of checking for a merge is at least as complicated as checking for simple ancestry, ie reachability.

[tomaswolf]

trying to prove that none of the prior patchsets were an ancestor of the new patchset. Since this is all Gerrit metadata, I don't think long histories will be a common problem in our case.

I got that. However, each patch set will have as parent a commit that is already merged. (Or another patch set; in that case, that other other patch set will be connected to the repo history.) So why exactly would the TOPO_SORT not load all the history?

[jacksondt]

Once we get the GC packfile, we have bitmaps that answer all remaining reachability questions. So we never have to traverse deep into history.

[jacksondt]

We also haven't yet measured the impact of repeated areAllReachable calls. We know that https://gerrit-review.git.corp.google.com/c/gerrit/+/501982 improved our performance substantially, but we need more data to determine if the repeated areAllReachable calls are still slowing us down.

So we don't need to jump the gun on this feature request.