Fix merge-base calculation

Fix JGits merge-base calculation in case of inconsistent commit times.
JGit was potentially failing to compute correct merge-bases when the
commit times where inconsistent (a parent commit was younger than a
child commit). The code in MergeBaseGenerator was aware of the fact that
sometimes the discovery of a merge base x can occur after the parents of
x have been seen (see comment in #carryOntoOne()). But in the light of
inconsistent commit times it was possible that these parents of a
merge-base have already been returned as a merge-base.

This commit fixes the bug by buffering all commits generated by
MergeBaseGenerator. It is expected that this buffer will be small
because the number of merge-bases will be small. Additionally a new
flag is used to mark the ancestors of merge-bases. This allows to filter
out the unwanted commits.

Bug: 507584
Change-Id: I9cc140b784c3231b972bd2c3de61a789365237ab

1 files changed, 26 insertions, 1 deletions

diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkMergeBaseTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkMergeBaseTest.java
index b5d4909f39..2451c50f6f 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkMergeBaseTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkMergeBaseTest.java
@@ -146,4 +146,29 @@ public class RevWalkMergeBaseTest extends RevWalkTestCase {
 		assertCommit(b, rw.next());
 		assertNull(rw.next());
 	}
-}
+
+	@Test
+	public void testInconsistentCommitTimes() throws Exception {
+		// When commit times are inconsistent (a parent is younger than a child)
+		// make sure that not both, parent and child, are reported as merge
+		// base. In the following repo the merge base between C,D should be B.
+		// But when A is younger than B the MergeBaseGenerator used to generate
+		// A before it detected that B is also a merge base.
+		//
+		//   +---C
+		//  /   /
+		// A---B---D
+
+		final RevCommit a = commit(2);
+		final RevCommit b = commit(-1, a);
+		final RevCommit c = commit(2, b, a);
+		final RevCommit d = commit(1, b);
+
+		rw.setRevFilter(RevFilter.MERGE_BASE);
+		markStart(d);
+		markStart(c);
+		assertCommit(b, rw.next());
+		assertNull(rw.next());
+	}
+
+}
\ No newline at end of file