[JGIT PATCH 1/2] Fix long running merge base computations

From: Shawn O. Pearce <spearce@spearce.org>
Date: Mar 18, 2009, 18:01 UTC
Message-ID: <1237399309-29493-1-git-send-email-spearce@spearce.org>

If a part of the project history is reachable by more than one path through the revision graph, we only need to traverse down it once through the first detected path when marking parents as reachable from an input branch.

Previously, JGit recomputed the entire project history for each path it was reachable through. On linux-2.6 based histories we got stuck for hours computing a merge base, as we kept passing back through the same sections of the revision graph.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../spearce/jgit/revwalk/MergeBaseGenerator.java   |    9 ++++++++-
 1 files changed, 8 insertions(+), 1 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/MergeBaseGenerator.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/MergeBaseGenerator.java
index 1676caa..2eb9688 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/MergeBaseGenerator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/MergeBaseGenerator.java
@@ -184,7 +184,9 @@ private void carryOntoHistory(RevCommit c, final int carry) {
 	}
 
 	private boolean carryOntoOne(final RevCommit p, final int carry) {
+		final boolean haveAll = (p.flags & carry) == carry;
 		p.flags |= carry;
+
 		if ((p.flags & POPPED) != 0 && (carry & MERGE_BASE) == 0
 				&& (p.flags & branchMask) == branchMask) {
 			// We were popped without being a merge base, but we just got
@@ -197,6 +199,11 @@ private boolean carryOntoOne(final RevCommit p, final int carry) {
 			carryOntoHistory(p, branchMask | MERGE_BASE);
 			return true;
 		}
-		return false;
+
+		// If we already had all carried flags, our parents do too.
+		// Return true to stop the caller from running down this leg
+		// of the revision graph any further.
+		//
+		return haveAll;
 	}
 }

-- 
1.6.2.1.337.g6270ba