diff --git a/Documentation/technical/reftable.md b/Documentation/technical/reftable.md
index 1236a79..ebef68f 100644
--- a/Documentation/technical/reftable.md
+++ b/Documentation/technical/reftable.md
@@ -773,9 +773,6 @@
 
 ### Layout
 
-The `$GIT_DIR/refs` path is a file when reftable is configured, not a
-directory.  This prevents loose references from being stored.
-
 A collection of reftable files are stored in the `$GIT_DIR/reftable/`
 directory:
 
@@ -789,28 +786,38 @@
 Log-only files use the `.log` extension, while ref-only and mixed ref
 and log files use `.ref`.  extension.
 
-The stack ordering file is `$GIT_DIR/refs` and lists the current
-files, one per line, in order, from oldest (base) to newest (most
-recent):
 
-    $ cat .git/refs
+The stack ordering file is `$GIT_DIR/reftable/tables.list` and lists the current
+files, one per line, in order, from oldest (base) to newest (most recent):
+
+    $ cat .git/reftable/tables.list
     00000001-00000001.log
     00000002-00000002.ref
     00000003-00000003.ref
 
-Readers must read `$GIT_DIR/refs` to determine which files are
-relevant right now, and search through the stack in reverse order
-(last reftable is examined first).
+Readers must read `$GIT_DIR/reftable/tables.list` to determine which files are
+relevant right now, and search through the stack in reverse order (last reftable
+is examined first).
 
-Reftable files not listed in `refs` may be new (and about to be added
+Reftable files not listed in `tables.list` may be new (and about to be added
 to the stack by the active writer), or ancient and ready to be pruned.
 
+### Backward compatibility
+
+Older clients should continue to recognize the directory as a git repository so
+they don't look for an enclosing repository in parent directories. To this end,
+a reftable-enabled repository must contain the following dummy files
+
+*   `.git/HEAD`, a regular file containing `ref: refs/heads/.invalid`.
+*   `.git/refs/`, a directory
+*   `.git/refs/heads`, a regular file
+
 ### Readers
 
 Readers can obtain a consistent snapshot of the reference space by
 following:
 
-1.  Open and read the `refs` file.
+1.  Open and read the `tables.list` file.
 2.  Open each of the reftable files that it mentions.
 3.  If any of the files is missing, goto 1.
 4.  Read from the now-open files as long as necessary.
@@ -820,13 +827,13 @@
 Although reftables are immutable, mutations are supported by writing a
 new reftable and atomically appending it to the stack:
 
-1. Acquire `refs.lock`.
-2. Read `refs` to determine current reftables.
+1. Acquire `tables.list.lock`.
+2. Read `tables.list` to determine current reftables.
 3. Select `update_index` to be most recent file's `max_update_index + 1`.
 4. Prepare temp reftable `tmp_XXXXXX`, including log entries.
 5. Rename `tmp_XXXXXX` to `${update_index}-${update_index}.ref`.
-6. Copy `refs` to `refs.lock`, appending file from (5).
-7. Rename `refs.lock` to `refs`.
+6. Copy `tables.list` to `tables.list.lock`, appending file from (5).
+7. Rename `tables.list.lock` to `tables.list`.
 
 During step 4 the new file's `min_update_index` and `max_update_index`
 are both set to the `update_index` selected by step 3.  All log
@@ -834,9 +841,9 @@
 This enables later correlation of which references were updated by the
 same transaction.
 
-Because a single `refs.lock` file is used to manage locking, the
+Because a single `tables.list.lock` file is used to manage locking, the
 repository is single-threaded for writers.  Writers may have to
-busy-spin (with backoff) around creating `refs.lock`, for up to an
+busy-spin (with backoff) around creating `tables.list.lock`, for up to an
 acceptable wait period, aborting if the repository is too busy to
 mutate.  Application servers wrapped around repositories (e.g.  Gerrit
 Code Review) can layer their own lock/wait queue to improve fairness
@@ -864,21 +871,21 @@
 reftable files (from oldest to newest): A, B, C, and D. The compactor
 is going to compact B and C, leaving A and D alone.
 
-1.  Obtain lock `refs.lock` and read the `refs` file.
+1.  Obtain lock `tables.list.lock` and read the `tables.list` file.
 2.  Obtain locks `B.lock` and `C.lock`.
     Ownership of these locks prevents other processes from trying
     to compact these files.
-3.  Release `refs.lock`.
+3.  Release `tables.list.lock`.
 4.  Compact `B` and `C` into a temp file `${min_update_index}-${max_update_index}_XXXXXX`.
-5.  Reacquire lock `refs.lock`.
+5.  Reacquire lock `tables.list.lock`.
 6.  Verify that `B` and `C` are still in the stack, in that order. This
     should always be the case, assuming that other processes are adhering
     to the locking protocol.
 7.  Rename `${min_update_index}-${max_update_index}_XXXXXX` to
     `${min_update_index}-${max_update_index}.ref`.
-8.  Write the new stack to `refs.lock`, replacing `B` and `C` with the
+8.  Write the new stack to `tables.list.lock`, replacing `B` and `C` with the
     file from (4).
-9.  Rename `refs.lock` to `refs`.
+9.  Rename `tables.list.lock` to `tables.list`.
 10. Delete `B` and `C`, perhaps after a short sleep to avoid forcing
     readers to backtrack.
 
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/internal/storage/dfs/DfsGarbageCollectorTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/dfs/DfsGarbageCollectorTest.java
index 6e0762f..f235b2e 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/dfs/DfsGarbageCollectorTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/dfs/DfsGarbageCollectorTest.java
@@ -19,7 +19,6 @@
 import java.util.concurrent.TimeUnit;
 
 import org.eclipse.jgit.internal.storage.dfs.DfsObjDatabase.PackSource;
-import org.eclipse.jgit.internal.storage.dfs.DfsRefDatabase;
 import org.eclipse.jgit.internal.storage.reftable.RefCursor;
 import org.eclipse.jgit.internal.storage.reftable.ReftableConfig;
 import org.eclipse.jgit.internal.storage.reftable.ReftableReader;
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.test/tst/org/eclipse/jgit/util/StatsTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/util/StatsTest.java
index e492737..6c4b4a4 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/util/StatsTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/util/StatsTest.java
@@ -12,7 +12,6 @@
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertTrue;
 
-import org.eclipse.jgit.util.Stats;
 import org.junit.Test;
 
 public class StatsTest {
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;
 		}
 	}
diff --git a/pom.xml b/pom.xml
index d0a5c83..3d9acd4 100644
--- a/pom.xml
+++ b/pom.xml
@@ -234,7 +234,7 @@
         <plugin>
           <groupId>org.apache.maven.plugins</groupId>
           <artifactId>maven-shade-plugin</artifactId>
-          <version>3.2.1</version>
+          <version>3.2.2</version>
         </plugin>
 
         <plugin>
@@ -846,12 +846,12 @@
               <dependency>
                 <groupId>org.codehaus.plexus</groupId>
                 <artifactId>plexus-compiler-javac</artifactId>
-                <version>2.8.5</version>
+                <version>2.8.6</version>
               </dependency>
               <dependency>
                 <groupId>org.codehaus.plexus</groupId>
                 <artifactId>plexus-compiler-javac-errorprone</artifactId>
-                <version>2.8.5</version>
+                <version>2.8.6</version>
               </dependency>
               <!-- override plexus-compiler-javac-errorprone's dependency on
                   Error Prone with the latest version -->
@@ -890,7 +890,7 @@
               <dependency>
                 <groupId>org.codehaus.plexus</groupId>
                 <artifactId>plexus-compiler-eclipse</artifactId>
-                <version>2.8.5</version>
+                <version>2.8.6</version>
               </dependency>
               <dependency>
                 <groupId>org.eclipse.jdt</groupId>