reftable: enforce ascending order in sortAndWriteRefs

MergedReftableTest#scanDuplicates tests whether we can write duplicate
keys in a merged reftable. Apparently, the first key appearing should
get precedence, and this works because the sort() algorithm on ordered
collections is stable.

This is potentially confusing behavior, because you can write data
into the table that cannot be retrieved (Merged table can only have
one entry per key), and the APIs such as exactRef() only return a
single value.

Make this consistent with behavior introduced in I04f55c481 "reftable:
enforce ordering for ref and log writes" by considering a duplicate key
in sortAndWriteRefs as a fatal runtime error.

Change-Id: I1eedd18f028180069f78c5c467169dcfe1521157
Signed-off-by: Han-Wen Nienhuys <hanwen@google.com>

4 files changed, 17 insertions, 27 deletions

diff --git a/Documentation/technical/reftable.md b/Documentation/technical/reftable.md
index 9e5c521fca..1236a79098 100644
--- a/Documentation/technical/reftable.md
+++ b/Documentation/technical/reftable.md
@@ -89,6 +89,10 @@ Reference names are an uninterpreted sequence of bytes that must pass
 
 [ref-fmt]: https://git-scm.com/docs/git-check-ref-format
 
+### Key unicity
+
+Each entry must have a unique key; repeated keys are disallowed.
+
 ### Network byte order
 
 All multi-byte, fixed width fields are in network byte order.
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/reftable/MergedReftableTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/reftable/MergedReftableTest.java
index 5f5ab72671..53d13f1d60 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/reftable/MergedReftableTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/reftable/MergedReftableTest.java
@@ -238,29 +238,6 @@ public class MergedReftableTest {
 	}
 
 	@Test
-	public void scanDuplicates() throws IOException {
-		List<Ref> delta1 = Arrays.asList(
-				ref("refs/heads/apple", 1),
-				ref("refs/heads/banana", 2));
-		List<Ref> delta2 = Arrays.asList(
-				ref("refs/heads/apple", 3),
-				ref("refs/heads/apple", 4));
-
-		MergedReftable mr = merge(write(delta1, 1000), write(delta2, 2000));
-		try (RefCursor rc = mr.allRefs()) {
-			assertTrue(rc.next());
-			assertEquals("refs/heads/apple", rc.getRef().getName());
-			assertEquals(id(3), rc.getRef().getObjectId());
-			assertEquals(2000, rc.getRef().getUpdateIndex());
-			assertTrue(rc.next());
-			assertEquals("refs/heads/banana", rc.getRef().getName());
-			assertEquals(id(2), rc.getRef().getObjectId());
-			assertEquals(1000, rc.getRef().getUpdateIndex());
-			assertFalse(rc.next());
-		}
-	}
-
-	@Test
 	public void scanIncludeDeletes() throws IOException {
 		List<Ref> delta1 = Arrays.asList(ref("refs/heads/next", 4));
 		List<Ref> delta2 = Arrays.asList(delete("refs/heads/next"));
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/reftable/ReftableTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/reftable/ReftableTest.java
index 1c04733f63..45e6c7d128 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/reftable/ReftableTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/reftable/ReftableTest.java
@@ -421,18 +421,20 @@ public class ReftableTest {
 	}
 
 	@Test
-	public void invalidRefWriteOrder() throws IOException {
+	public void invalidRefWriteOrderSortAndWrite() {
 		Ref master = ref(MASTER, 1);
-		Ref next = ref(NEXT, 2);
 		ReftableWriter writer = new ReftableWriter(new ByteArrayOutputStream())
 			.setMinUpdateIndex(1)
 			.setMaxUpdateIndex(1)
 			.begin();
 
-		writer.writeRef(next);
+		List<Ref> refs = new ArrayList<>();
+		refs.add(master);
+		refs.add(master);
+
 		IllegalArgumentException e  = assertThrows(
 			IllegalArgumentException.class,
-			() -> writer.writeRef(master));
+			() -> writer.sortAndWriteRefs(refs));
 		assertThat(e.getMessage(), containsString("records must be increasing"));
 	}
 
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/ReftableWriter.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/ReftableWriter.java
index 0bb0a24d58..d06fee3427 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/ReftableWriter.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/ReftableWriter.java
@@ -230,6 +230,7 @@ public class ReftableWriter {
 
 	/**
 	 * Sort a collection of references and write them to the reftable.
+	 * The input refs may not have duplicate names.
 	 *
 	 * @param refsToPack
 	 *            references to sort and write.
@@ -243,10 +244,16 @@ public class ReftableWriter {
 				.map(r -> new RefEntry(r, maxUpdateIndex - minUpdateIndex))
 				.sorted(Entry::compare)
 				.iterator();
+		RefEntry last = null;
 		while (itr.hasNext()) {
 			RefEntry entry = itr.next();
+			if (last != null && Entry.compare(last, entry) == 0) {
+				throwIllegalEntry(last, entry);
+			}
+
 			long blockPos = refs.write(entry);
 			indexRef(entry.ref, blockPos);
+			last = entry;
 		}
 		return this;
 	}