Merge "Revert "RevWalk: stop mixing lines of history in topo sort""
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 d1522e9..8623902 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 @@
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 45225a2..4e0bba2 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 @@
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 @@
.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 @@
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 @@
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 @@
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 @@
/**
* <pre>
* a4
- * |
- * a3
- * | \\
- * a2 \\
- * | \\
- * | b3 ||
- * | | ||
- * | b2 ||
- * | | //
- * | b1
- * | |
+ * | b3
+ * a3 |
+ * | \\|
+ * | |\\
+ * | b2||
+ * a2 | //
+ * | b1
* | /
* a1
* </pre>
@@ -561,10 +552,10 @@
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 @@
* b2
* a4 |
* | \ |
- * | b1
- * a3 |
+ * a3 \|
* | \ |
* | c |
* | / |
* a2 |
- * | |
- * | /
+ * | b1
+ * /
* | /
* a1
* </pre>
@@ -614,10 +604,10 @@
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 3f29e09..6f110fa 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 @@
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 1abcf69..5ce4bc3 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 @@
* 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 383428c..f425e87 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 @@
/**
* 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 3c553b0..7a5db43 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 @@
/** 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 @@
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 @@
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;
}
}
