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

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

[Shawn O. Pearce]

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

[JGIT PATCH 2/2] Micro-optimize the merge base generator

[Shawn O. Pearce]

Instead of doing 3 bit-wise and operations followed by 3 compares
and two boolean and conditions on every commit we evaluate in the
history, we can fold all of the tests into a pair of fields and
do one bit mask and compare.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../spearce/jgit/revwalk/MergeBaseGenerator.java   |   13 +++++++++++--
 1 files changed, 11 insertions(+), 2 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 2eb9688..8694e4c 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/MergeBaseGenerator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/MergeBaseGenerator.java
@@ -73,6 +73,10 @@
 
 	private int branchMask;
 
+	private int recarryTest;
+
+	private int recarryMask;
+
 	MergeBaseGenerator(final RevWalk w) {
 		walker = w;
 		pending = new DateRevQueue();
@@ -91,6 +95,12 @@ void init(final AbstractRevQueue p) {
 			// will be available for reuse when the walk resets.
 			//
 			walker.freeFlag(branchMask);
+
+			// Setup the condition used by carryOntoOne to detect a late
+			// merge base and produce it on the next round.
+			//
+			recarryTest = branchMask | POPPED;
+			recarryMask = branchMask | POPPED | MERGE_BASE;
 		}
 	}
 
@@ -187,8 +197,7 @@ 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) {
+		if ((p.flags & recarryMask) == recarryTest) {
 			// We were popped without being a merge base, but we just got
 			// voted to be one. Inject ourselves back at the front of the
 			// pending queue and tell all of our ancestors they are within
-- 
1.6.2.1.337.g6270ba