RevWalk: stop mixing lines of history in topo sort
The topological sort algorithm in TopoSortGenerator for RevWalk may mix
multiple lines of history, producing results that differ from C git's
git log whose man page states: "Show no parents before all of its
children are shown, and avoid showing commits on multiple lines of
history intermixed." Lines of history are mixed because
TopoSortGenerator merely delays a commit until all of its children have
been produced; it does not immediately produce a commit after its last
child has been produced.
Therefore, when the last child of a commit has been produced, unpop the
commit so that it will be returned upon the subsequent call to next() in
TopoSortGenerator. To avoid producing duplicates, mark commits that
have not yet been produced as TOPO_QUEUED so that when a commit is
popped, it is produced if and only if TOPO_QUEUED is set.
To support nesting with other generators that may produce the same
commit multiple times like DepthGenerator (for example, StartGenerator
does this), do not increment parent inDegree for the same child commit
more than once.
Modify tests that assert that TopoSortGenerator mixes lines of commit
history.
Change-Id: I4ee03c7a8e5265d61230b2a01ae3858745b2432b
Signed-off-by: Alex Spradlin <alexaspradlin@google.com>
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 8623902..d1522e9 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 newC = rw.next();
- assertDerivedFrom(newC, c);
RevCommit newE = rw.next();
assertEquals(e, newE);
+ RevCommit newC = rw.next();
+ assertDerivedFrom(newC, c);
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 4e0bba2..45225a2 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(2);
+ test.commit(disable_comment).parents(clone_operation).lanePos(3);
test.commit(merge_resolve_handler)
.parents(clone_operation, resolve_handler).lanePos(mainPos);
- test.commit(update_eclipse).parents(add_Maven).lanePos(3);
+ test.commit(resolve_handler).parents(merge_fix).lanePos(4);
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(changeset_implementation).parents(clear_repositorycache)
- .lanePos(2);
+ test.commit(use_remote).parents(clear_repositorycache).lanePos(3);
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,33 +453,36 @@
pcl.source(pw);
pcl.fillTo(Integer.MAX_VALUE);
- // 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);
+ 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);
}
}
/**
* <pre>
* b3
+ * a5 |
+ * | |
* a4 |
* | \|
* | b2
* a3 |
* | \|
- * a2 |
* | b1
+ * a2 |
* | /
* a1
* </pre>
@@ -494,10 +497,11 @@
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(a4));
+ pw.markStart(pw.lookupCommit(a5));
pw.markStart(pw.lookupCommit(b3));
PlotCommitList<PlotLane> pcl = new PlotCommitList<>();
pcl.source(pw);
@@ -506,11 +510,12 @@
Set<Integer> positions = asSet(0, 1);
CommitListAssert test = new CommitListAssert(pcl);
int posB = test.commit(b3).lanePos(positions).getLanePos();
- int posA = test.commit(a4).lanePos(positions).getLanePos();
+ int posA = test.commit(a5).lanePos(positions).getLanePos();
+ test.commit(a4).lanePos(posA);
test.commit(b2).lanePos(posB);
test.commit(a3).lanePos(posA);
- test.commit(a2).lanePos(posA);
test.commit(b1).lanePos(posB);
+ test.commit(a2).lanePos(posA);
test.commit(a1).lanePos(posA);
test.noMoreCommits();
}
@@ -519,13 +524,17 @@
/**
* <pre>
* a4
- * | b3
- * a3 |
- * | \\|
- * | |\\
- * | b2||
- * a2 | //
- * | b1
+ * |
+ * a3
+ * | \\
+ * a2 \\
+ * | \\
+ * | b3 ||
+ * | | ||
+ * | b2 ||
+ * | | //
+ * | b1
+ * | |
* | /
* a1
* </pre>
@@ -552,10 +561,10 @@
Set<Integer> positions = asSet(0, 1);
CommitListAssert test = new CommitListAssert(pcl);
int posA = test.commit(a4).lanePos(positions).getLanePos();
- int posB = test.commit(b3).lanePos(positions).getLanePos();
test.commit(a3).lanePos(posA);
- test.commit(b2).lanePos(posB);
test.commit(a2).lanePos(posA);
+ int posB = test.commit(b3).lanePos(positions).getLanePos();
+ test.commit(b2).lanePos(posB);
// b1 is not repositioned, uses "detour lane"
// (drawn as a double arc in the ascii graph above)
test.commit(b1).lanePos(posB);
@@ -569,13 +578,14 @@
* b2
* a4 |
* | \ |
- * a3 \|
+ * | b1
+ * a3 |
* | \ |
* | c |
* | / |
* a2 |
- * | b1
- * /
+ * | |
+ * | /
* | /
* a1
* </pre>
@@ -604,10 +614,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 6f110fa..3f29e09 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,4 +144,110 @@
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 5ce4bc3..1abcf69 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_DELAY) != 0 ? 'o' : '-');
+ s.append((flags & RevWalk.TOPO_QUEUED) != 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 f425e87..383428c 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 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.
+ * 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.
*/
- static final int TOPO_DELAY = 1 << 5;
+ static final int TOPO_QUEUED = 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 7a5db43..3c553b0 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_DELAY = RevWalk.TOPO_DELAY;
+ private static final int TOPO_QUEUED = RevWalk.TOPO_QUEUED;
private final FIFORevQueue pending;
@@ -47,12 +47,16 @@
if (c == null) {
break;
}
- for (RevCommit p : c.parents) {
- p.inDegree++;
- if (firstParent) {
- break;
+ if ((c.flags & TOPO_QUEUED) == 0) {
+ for (RevCommit p : c.parents) {
+ p.inDegree++;
+
+ if (firstParent) {
+ break;
+ }
}
}
+ c.flags |= TOPO_QUEUED;
pending.add(c);
}
}
@@ -71,34 +75,42 @@
RevCommit next() throws MissingObjectException,
IncorrectObjectTypeException, IOException {
for (;;) {
- final RevCommit c = pending.next();
- if (c == null)
+ 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;
}
- // All of our children have already produced,
- // so it is OK for us to produce now as well.
- //
+ 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;
+ }
+
for (RevCommit p : c.parents) {
- 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.
+ 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.
//
- p.flags &= ~TOPO_DELAY;
pending.unpop(p);
}
if (firstParent) {
break;
}
}
+
+ c.flags &= ~TOPO_QUEUED;
return c;
}
}
