diff options
6 files changed, 64 insertions, 192 deletions
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/api/RebaseCommandTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/api/RebaseCommandTest.java index d1522e98e2..86239023dc 100644 --- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/api/RebaseCommandTest.java +++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/api/RebaseCommandTest.java @@ -563,10 +563,10 @@ public class RebaseCommandTest extends RepositoryTestCase { RevCommit newD = rw.next(); assertDerivedFrom(newD, d); assertEquals(2, newD.getParentCount()); - RevCommit newE = rw.next(); - assertEquals(e, newE); RevCommit newC = rw.next(); assertDerivedFrom(newC, c); + RevCommit newE = rw.next(); + assertEquals(e, newE); assertEquals(newC, newD.getParent(0)); assertEquals(e, newD.getParent(1)); assertEquals(g, rw.next()); diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revplot/PlotCommitListTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revplot/PlotCommitListTest.java index 45225a2bdc..4e0bba2f28 100644 --- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revplot/PlotCommitListTest.java +++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revplot/PlotCommitListTest.java @@ -254,12 +254,12 @@ public class PlotCommitListTest extends RevWalkTestCase { int posI = test.commit(i).lanePos(childPositions).parents(h) .getLanePos(); test.commit(h).lanePos(posI).parents(f); + test.commit(g).lanePos(childPositions).parents(a); test.commit(f).lanePos(posI).parents(e, d); - test.commit(d).lanePos(1).parents(b); test.commit(e).lanePos(posI).parents(c); + test.commit(d).lanePos(2).parents(b); test.commit(c).lanePos(posI).parents(b); test.commit(b).lanePos(posI).parents(a); - test.commit(g).lanePos(childPositions).parents(a); test.commit(a).lanePos(0).parents(); } } @@ -325,42 +325,42 @@ public class PlotCommitListTest extends RevWalkTestCase { .lanePos(mainPos); test.commit(merge_update_eclipse) .parents(add_a_clear, update_eclipse).lanePos(mainPos); - test.commit(update_eclipse).parents(add_Maven).lanePos(2); test.commit(add_a_clear).parents(fix_broken).lanePos(mainPos); test.commit(fix_broken).parents(merge_disable_comment) .lanePos(mainPos); test.commit(merge_disable_comment) .parents(merge_resolve_handler, disable_comment) .lanePos(mainPos); - test.commit(disable_comment).parents(clone_operation).lanePos(3); + test.commit(disable_comment).parents(clone_operation).lanePos(2); test.commit(merge_resolve_handler) .parents(clone_operation, resolve_handler).lanePos(mainPos); - test.commit(resolve_handler).parents(merge_fix).lanePos(4); + test.commit(update_eclipse).parents(add_Maven).lanePos(3); test.commit(clone_operation).parents(merge_changeset_implementation) .lanePos(mainPos); test.commit(merge_changeset_implementation) .parents(merge_disable_source, changeset_implementation) .lanePos(mainPos); - test.commit(changeset_implementation).parents(clear_repositorycache) - .lanePos(1); test.commit(merge_disable_source) .parents(update_eclipse_iplog2, disable_source) .lanePos(mainPos); - test.commit(disable_source).parents(merge_use_remote).lanePos(3); test.commit(update_eclipse_iplog2).parents(merge_use_remote) .lanePos(mainPos); + test.commit(disable_source).parents(merge_use_remote).lanePos(1); test.commit(merge_use_remote) .parents(update_eclipse_iplog, use_remote).lanePos(mainPos); - test.commit(use_remote).parents(clear_repositorycache).lanePos(3); + test.commit(changeset_implementation).parents(clear_repositorycache) + .lanePos(2); test.commit(update_eclipse_iplog).parents(merge_add_Maven) .lanePos(mainPos); test.commit(merge_add_Maven).parents(findToolBar_layout, add_Maven) .lanePos(mainPos); - test.commit(add_Maven).parents(clear_repositorycache).lanePos(2); test.commit(findToolBar_layout).parents(clear_repositorycache) .lanePos(mainPos); + test.commit(use_remote).parents(clear_repositorycache).lanePos(1); + test.commit(add_Maven).parents(clear_repositorycache).lanePos(3); test.commit(clear_repositorycache).parents(merge_remove) .lanePos(mainPos); + test.commit(resolve_handler).parents(merge_fix).lanePos(4); test.commit(merge_remove).parents(add_simple, remove_unused) .lanePos(mainPos); test.commit(remove_unused).parents(merge_fix).lanePos(1); @@ -453,36 +453,33 @@ public class PlotCommitListTest extends RevWalkTestCase { pcl.source(pw); pcl.fillTo(Integer.MAX_VALUE); - Set<Integer> positions = asSet(0, 1); - CommitListAssert test = new CommitListAssert(pcl); - int posA = test.commit(a5).lanePos(positions).getLanePos(); - test.commit(a4); - test.commit(a3).lanePos(posA); - test.commit(e); - test.commit(d); - test.commit(a2).lanePos(posA); - int posB = test.commit(b3).lanePos(positions).getLanePos(); - test.commit(b2).lanePos(posB); - test.commit(b1).lanePos(posB); - test.commit(c); - test.commit(a1).lanePos(posA); - test.noMoreCommits(); - assertNotEquals("a lane is the same as b lane", posA, posB); + // test that the commits b1, b2 and b3 are on the same position + int bPos = pcl.get(9).lane.position; // b1 + assertEquals("b2 is an a different position", bPos, + pcl.get(7).lane.position); + assertEquals("b3 is on a different position", bPos, + pcl.get(4).lane.position); + + // test that nothing blocks the connections between b1, b2 and b3 + assertNotEquals("b lane is blocked by c", bPos, + pcl.get(8).lane.position); + assertNotEquals("b lane is blocked by a2", bPos, + pcl.get(6).lane.position); + assertNotEquals("b lane is blocked by d", bPos, + pcl.get(5).lane.position); } } /** * <pre> * b3 - * a5 | - * | | * a4 | * | \| * | b2 * a3 | * | \| - * | b1 * a2 | + * | b1 * | / * a1 * </pre> @@ -497,11 +494,10 @@ public class PlotCommitListTest extends RevWalkTestCase { final RevCommit a3 = commit(a2, b1); final RevCommit b2 = commit(b1); final RevCommit a4 = commit(a3, b2); - final RevCommit a5 = commit(a4); final RevCommit b3 = commit(b2); try (PlotWalk pw = new PlotWalk(db)) { - pw.markStart(pw.lookupCommit(a5)); + pw.markStart(pw.lookupCommit(a4)); pw.markStart(pw.lookupCommit(b3)); PlotCommitList<PlotLane> pcl = new PlotCommitList<>(); pcl.source(pw); @@ -510,12 +506,11 @@ public class PlotCommitListTest extends RevWalkTestCase { Set<Integer> positions = asSet(0, 1); CommitListAssert test = new CommitListAssert(pcl); int posB = test.commit(b3).lanePos(positions).getLanePos(); - int posA = test.commit(a5).lanePos(positions).getLanePos(); - test.commit(a4).lanePos(posA); + int posA = test.commit(a4).lanePos(positions).getLanePos(); test.commit(b2).lanePos(posB); test.commit(a3).lanePos(posA); - test.commit(b1).lanePos(posB); test.commit(a2).lanePos(posA); + test.commit(b1).lanePos(posB); test.commit(a1).lanePos(posA); test.noMoreCommits(); } @@ -524,17 +519,13 @@ public class PlotCommitListTest extends RevWalkTestCase { /** * <pre> * a4 - * | - * a3 - * | \\ - * a2 \\ - * | \\ - * | b3 || - * | | || - * | b2 || - * | | // - * | b1 - * | | + * | b3 + * a3 | + * | \\| + * | |\\ + * | b2|| + * a2 | // + * | b1 * | / * a1 * </pre> @@ -561,10 +552,10 @@ public class PlotCommitListTest extends RevWalkTestCase { Set<Integer> positions = asSet(0, 1); CommitListAssert test = new CommitListAssert(pcl); int posA = test.commit(a4).lanePos(positions).getLanePos(); - test.commit(a3).lanePos(posA); - test.commit(a2).lanePos(posA); int posB = test.commit(b3).lanePos(positions).getLanePos(); + test.commit(a3).lanePos(posA); test.commit(b2).lanePos(posB); + test.commit(a2).lanePos(posA); // b1 is not repositioned, uses "detour lane" // (drawn as a double arc in the ascii graph above) test.commit(b1).lanePos(posB); @@ -578,14 +569,13 @@ public class PlotCommitListTest extends RevWalkTestCase { * b2 * a4 | * | \ | - * | b1 - * a3 | + * a3 \| * | \ | * | c | * | / | * a2 | - * | | - * | / + * | b1 + * / * | / * a1 * </pre> @@ -614,10 +604,10 @@ public class PlotCommitListTest extends RevWalkTestCase { CommitListAssert test = new CommitListAssert(pcl); int posB = test.commit(b2).lanePos(positions).getLanePos(); int posA = test.commit(a4).lanePos(positions).getLanePos(); - test.commit(b1).lanePos(posB); // repositioned to go around c test.commit(a3).lanePos(posA); test.commit(c).lanePos(positions); test.commit(a2).lanePos(posA); + test.commit(b1).lanePos(posB); // repositioned to go around c test.commit(a1).lanePos(posA); test.noMoreCommits(); } diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkSortTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkSortTest.java index 3f29e09e39..6f110fa317 100644 --- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkSortTest.java +++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkSortTest.java @@ -144,110 +144,4 @@ public class RevWalkSortTest extends RevWalkTestCase { assertCommit(d, rw.next()); assertNull(rw.next()); } - - @Test - public void testSort_TOPO_OutOfOrderCommitTimes() throws Exception { - // b is committed before c2 in a different line of history. - // - final RevCommit a = commit(); - final RevCommit c1 = commit(a); - final RevCommit b = commit(a); - final RevCommit c2 = commit(c1); - final RevCommit d = commit(b, c2); - - rw.sort(RevSort.TOPO); - markStart(d); - assertCommit(d, rw.next()); - assertCommit(c2, rw.next()); - assertCommit(c1, rw.next()); - assertCommit(b, rw.next()); - assertCommit(a, rw.next()); - assertNull(rw.next()); - } - - @Test - public void testSort_TOPO_MultipleLinesOfHistory() throws Exception { - final RevCommit a1 = commit(); - final RevCommit b1 = commit(a1); - final RevCommit a2 = commit(a1, b1); - final RevCommit b2 = commit(b1); - final RevCommit b3 = commit(b1); - final RevCommit a3 = commit(a2, b2); - final RevCommit a4 = commit(a3, b3); - - rw.sort(RevSort.TOPO); - markStart(a4); - assertCommit(a4, rw.next()); - assertCommit(b3, rw.next()); - assertCommit(a3, rw.next()); - assertCommit(b2, rw.next()); - assertCommit(a2, rw.next()); - assertCommit(b1, rw.next()); - assertCommit(a1, rw.next()); - assertNull(rw.next()); - } - - @Test - public void testSort_TOPO_REVERSE_MultipleLinesOfHistory() - throws Exception { - final RevCommit a1 = commit(); - final RevCommit b1 = commit(a1); - final RevCommit a2 = commit(a1, b1); - final RevCommit b2 = commit(b1); - final RevCommit b3 = commit(b1); - final RevCommit a3 = commit(a2, b2); - final RevCommit a4 = commit(a3, b3); - - rw.sort(RevSort.TOPO); - rw.sort(RevSort.REVERSE, true); - markStart(a4); - assertCommit(a1, rw.next()); - assertCommit(b1, rw.next()); - assertCommit(a2, rw.next()); - assertCommit(b2, rw.next()); - assertCommit(a3, rw.next()); - assertCommit(b3, rw.next()); - assertCommit(a4, rw.next()); - assertNull(rw.next()); - } - - @Test - public void testSort_TOPO_ParentOfMultipleStartChildren() throws Exception { - final RevCommit a = commit(); - final RevCommit b = commit(a); - final RevCommit c = commit(a); - final RevCommit d1 = commit(a); - final RevCommit d2 = commit(d1); - final RevCommit e = commit(a); - - rw.sort(RevSort.TOPO); - markStart(b); - markStart(c); - markStart(d2); - markStart(e); - assertCommit(e, rw.next()); - assertCommit(d2, rw.next()); - assertCommit(d1, rw.next()); - assertCommit(c, rw.next()); - assertCommit(b, rw.next()); - assertCommit(a, rw.next()); - assertNull(rw.next()); - } - - @Test - public void testSort_TOPO_Uninteresting() throws Exception { - final RevCommit a1 = commit(); - final RevCommit a2 = commit(a1); - final RevCommit a3 = commit(a2); - final RevCommit b = commit(a1); - final RevCommit a4 = commit(a3, b); - - rw.sort(RevSort.TOPO); - markStart(a4); - markUninteresting(a2); - assertCommit(a4, rw.next()); - assertCommit(b, rw.next()); - assertCommit(a3, rw.next()); - assertNull(rw.next()); - } } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevObject.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevObject.java index 1abcf6962f..5ce4bc33b5 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevObject.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevObject.java @@ -151,7 +151,7 @@ public abstract class RevObject extends ObjectIdOwnerMap.Entry { * buffer to append a debug description of core RevFlags onto. */ protected void appendCoreFlags(StringBuilder s) { - s.append((flags & RevWalk.TOPO_QUEUED) != 0 ? 'o' : '-'); + s.append((flags & RevWalk.TOPO_DELAY) != 0 ? 'o' : '-'); s.append((flags & RevWalk.TEMP_MARK) != 0 ? 't' : '-'); s.append((flags & RevWalk.REWRITE) != 0 ? 'r' : '-'); s.append((flags & RevWalk.UNINTERESTING) != 0 ? 'u' : '-'); diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java index 383428c858..f425e87618 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java @@ -125,11 +125,11 @@ public class RevWalk implements Iterable<RevCommit>, AutoCloseable { /** * Temporary mark for use within {@link TopoSortGenerator}. * <p> - * This mark indicates the commit has been queued for emission in - * {@link TopoSortGenerator} and can be produced. This mark is removed when - * the commit has been produced. + * This mark indicates the commit could not produce when it wanted to, as at + * least one child was behind it. Commits with this flag are delayed until + * all children have been output first. */ - static final int TOPO_QUEUED = 1 << 5; + static final int TOPO_DELAY = 1 << 5; /** Number of flag bits we keep internal for our own use. See above flags. */ static final int RESERVED_FLAGS = 6; diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/TopoSortGenerator.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/TopoSortGenerator.java index 3c553b06cf..7a5db43a7a 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/TopoSortGenerator.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/TopoSortGenerator.java @@ -17,7 +17,7 @@ import org.eclipse.jgit.errors.MissingObjectException; /** Sorts commits in topological order. */ class TopoSortGenerator extends Generator { - private static final int TOPO_QUEUED = RevWalk.TOPO_QUEUED; + private static final int TOPO_DELAY = RevWalk.TOPO_DELAY; private final FIFORevQueue pending; @@ -47,16 +47,12 @@ class TopoSortGenerator extends Generator { if (c == null) { break; } - if ((c.flags & TOPO_QUEUED) == 0) { - for (RevCommit p : c.parents) { - p.inDegree++; - - if (firstParent) { - break; - } + for (RevCommit p : c.parents) { + p.inDegree++; + if (firstParent) { + break; } } - c.flags |= TOPO_QUEUED; pending.add(c); } } @@ -75,42 +71,34 @@ class TopoSortGenerator extends Generator { RevCommit next() throws MissingObjectException, IncorrectObjectTypeException, IOException { for (;;) { - RevCommit c = pending.next(); - if (c == null) { + final RevCommit c = pending.next(); + if (c == null) return null; - } if (c.inDegree > 0) { // At least one of our children is missing. We delay // production until all of our children are output. // + c.flags |= TOPO_DELAY; continue; } - if ((c.flags & TOPO_QUEUED) == 0) { - // c is a parent that already produced or a parent that - // was never in the priority queue and should never produce. - // - continue; - } - + // All of our children have already produced, + // so it is OK for us to produce now as well. + // for (RevCommit p : c.parents) { - if (--p.inDegree == 0 && (p.flags & TOPO_QUEUED) != 0) { - // The parent has no unproduced interesting children. unpop - // the parent so it goes right behind this child. This means - // that this parent commit may appear in "pending" more than - // once, but this is safe since upon the second and - // subsequent iterations with this commit, it will no longer - // have TOPO_QUEUED set, and thus will be skipped. + if (--p.inDegree == 0 && (p.flags & TOPO_DELAY) != 0) { + // This parent tried to come before us, but we are + // his last child. unpop the parent so it goes right + // behind this child. // + p.flags &= ~TOPO_DELAY; pending.unpop(p); } if (firstParent) { break; } } - - c.flags &= ~TOPO_QUEUED; return c; } } |