From 930cd43553388eefe8890de9ff21ad1d6328eda7 Mon Sep 17 00:00:00 2001 From: Christian Halstrick Date: Wed, 23 Nov 2016 12:52:16 +0100 Subject: 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 --- .../eclipse/jgit/revwalk/RevWalkMergeBaseTest.java | 27 +++++++++++++- .../eclipse/jgit/revwalk/MergeBaseGenerator.java | 43 +++++++++++++++++----- 2 files changed, 59 insertions(+), 11 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 diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/MergeBaseGenerator.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/MergeBaseGenerator.java index f1d7dc8361..3609d46e30 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/MergeBaseGenerator.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/MergeBaseGenerator.java @@ -45,6 +45,7 @@ package org.eclipse.jgit.revwalk; import java.io.IOException; import java.text.MessageFormat; +import java.util.LinkedList; import org.eclipse.jgit.errors.IncorrectObjectTypeException; import org.eclipse.jgit.errors.MissingObjectException; @@ -85,12 +86,15 @@ class MergeBaseGenerator extends Generator { private int recarryMask; + private int mergeBaseAncestor = -1; + private LinkedList ret = new LinkedList(); + MergeBaseGenerator(final RevWalk w) { walker = w; pending = new DateRevQueue(); } - void init(final AbstractRevQueue p) { + void init(final AbstractRevQueue p) throws IOException { try { for (;;) { final RevCommit c = p.next(); @@ -98,17 +102,25 @@ class MergeBaseGenerator extends Generator { break; add(c); } - } finally { - // Always free the flags immediately. This ensures the flags - // 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; + mergeBaseAncestor = walker.allocFlag(); + + for (;;) { + RevCommit c = _next(); + if (c == null) { + break; + } + ret.add(c); + } + } finally { + // Always free the flags immediately. This ensures the flags + // will be available for reuse when the walk resets. + // + walker.freeFlag(branchMask | mergeBaseAncestor); } } @@ -131,8 +143,7 @@ class MergeBaseGenerator extends Generator { return 0; } - @Override - RevCommit next() throws MissingObjectException, + private RevCommit _next() throws MissingObjectException, IncorrectObjectTypeException, IOException { for (;;) { final RevCommit c = pending.next(); @@ -156,7 +167,7 @@ class MergeBaseGenerator extends Generator { // also flagged as being popped, so that they do not // generate to the caller. // - carry |= MERGE_BASE; + carry |= MERGE_BASE | mergeBaseAncestor; } carryOntoHistory(c, carry); @@ -179,6 +190,18 @@ class MergeBaseGenerator extends Generator { } } + @Override + RevCommit next() throws MissingObjectException, + IncorrectObjectTypeException, IOException { + while (!ret.isEmpty()) { + RevCommit commit = ret.remove(); + if ((commit.flags & mergeBaseAncestor) == 0) { + return commit; + } + } + return null; + } + private void carryOntoHistory(RevCommit c, final int carry) { for (;;) { final RevCommit[] pList = c.parents; -- cgit v1.2.3