Skip to main content


Eclipse Community Forums
Forum Search:

Search      Help    Register    Login    Home
Home » Eclipse Projects » EGit / JGit » How to implement a breadth-first rev walker to find closest branch for HEAD
How to implement a breadth-first rev walker to find closest branch for HEAD [message #1849887] Mon, 07 February 2022 15:16
Julien HENRY is currently offline Julien HENRYFriend
Messages: 11
Registered: July 2009
Junior Member
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)
}





Previous Topic:Unable to delete .pack file from submodule git folder
Next Topic:Authentication/Transport Error
Goto Forum:
  


Current Time: Tue Sep 27 16:44:13 GMT 2022

Powered by FUDForum. Page generated in 0.01908 seconds
.:: Contact :: Home ::.

Powered by: FUDforum 3.0.2.
Copyright ©2001-2010 FUDforum Bulletin Board Software

Back to the top