Hi,
Here is my use case: we have a provided list of branch names (aka candidates). We want an efficient way to detect what is the best match for the current repository HEAD.
By best match, we mean the branch pointing to the closest commit regarding the distance in term of number of commits (navigation could be going up or down in the tree).
My current approach is to compute the distance between HEAD and each candidate branch, then return the one with the shortest distance.
(I took inspiration from the BranchTrackingStatus class to compute the distance):
for (String branchCandidate : branchCandidates) {
int distance = computeDistanceFromHead(branchCandidate);
// collect branch + distance
}
// return the branch having the smallest distance
int computeDistanceFromHead(String branchName) {
try (RevWalk walk = new RevWalk(repository)) {
RevCommit fromCommit = walk.parseCommit(repo.exactRef(Constants.HEAD).getObjectId());
RevCommit toCommit = walk.parseCommit(repo.exactRef(branchName).getObjectId());
walk.setRevFilter(RevFilter.MERGE_BASE);
walk.markStart(fromCommit);
walk.markStart(toCommit);
RevCommit mergeBase = walk.next();
walk.reset();
walk.setRevFilter(RevFilter.ALL);
int aheadCount = RevWalkUtils.count(walk, fromCommit, mergeBase);
int behindCount = RevWalkUtils.count(walk, toCommit,
mergeBase);
return aheadCount + behindCount;
}
}
The problem here is that the complexity is increasing based on the number of candidate branches.
I'm pretty sure there is a more efficient way, since I just want to get the closest branch in a Breadth-First Traversal of the revision graph, starting from HEAD commit.
Is it possible using JGit? How can I efficiently navigate in the revision graph (considering both parents/children directions)?
Something like:
var queue = [HEAD]
while (queue not empty) {
var currentCommit = queue.pop
if (any branchCandidates points to currentCommit) {
return branchCandidates for currentCommit
}
queue.addAll(currentCommit.parents)
queue.addAll(currentCommit.children)
}