[PATCH 1/2] t: add tests for ref tombstone scenarios

["Kristofer Karlsson via GitGitGadget" <gitgitgadget@gmail.com>]

From: Kristofer Karlsson <krka@spotify.com>

Add a performance test and a correctness test for update-ref when
many tombstones are present in a reftable.

The performance test (p1401) exercises two scenarios:

 - All refs are deleted (creating tombstones) and then re-created
   with the same names, which currently exhibits quadratic behavior.

 - An asymmetric variant where refs are deleted and then new,
   differently-named refs are created.  When the tombstones sort
   after the new refs, every create scans all tombstones, making
   this case even worse than re-creating the same refs.

The correctness test (t0610) verifies that refs deleted and then
re-created with the same names are visible afterwards.

Helped-by: Jeff King <peff@peff.net>
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
 t/perf/p1401-ref-store-tombstones.sh | 44 ++++++++++++++++++++++++++++
 t/t0610-reftable-basics.sh           | 22 ++++++++++++++
 2 files changed, 66 insertions(+)
 create mode 100755 t/perf/p1401-ref-store-tombstones.sh

diff --git a/t/perf/p1401-ref-store-tombstones.sh b/t/perf/p1401-ref-store-tombstones.sh
new file mode 100755
index 0000000000..e40a6dcbf4
--- /dev/null
+++ b/t/perf/p1401-ref-store-tombstones.sh
@@ -0,0 +1,44 @@
+#!/bin/sh
+
+test_description="Tests performance of ref operations with many tombstones"
+
+. ./perf-lib.sh
+
+test_expect_success "setup" '
+	git init --ref-format=reftable repo &&
+	blob=$(echo foo | git -C repo hash-object -w --stdin) &&
+	for i in $(test_seq 8000)
+	do
+		printf "create refs/tags/tag-%d %s\n" "$i" "$blob" ||
+		return 1
+	done >repo/input &&
+	git -C repo update-ref --stdin <repo/input &&
+	git -C repo for-each-ref --format="delete %(refname)" |
+	git -C repo update-ref --stdin
+'
+
+test_perf "recreate refs after mass delete" '
+	git -C repo update-ref --stdin <repo/input &&
+	git -C repo for-each-ref --format="delete %(refname)" |
+	git -C repo update-ref --stdin
+'
+
+test_expect_success "setup asymmetric" '
+	for i in $(test_seq 8000)
+	do
+		printf "create refs/tags/old-%d %s\n" "$i" "$blob" ||
+		return 1
+	done >repo/input-old &&
+	sed "s/old-/new-/" <repo/input-old >repo/input-new &&
+	git -C repo update-ref --stdin <repo/input-old &&
+	git -C repo for-each-ref --format="delete %(refname)" |
+	git -C repo update-ref --stdin
+'
+
+test_perf "create new refs after deleting differently-named refs" '
+	git -C repo update-ref --stdin <repo/input-new &&
+	git -C repo for-each-ref --format="delete %(refname)" |
+	git -C repo update-ref --stdin
+'
+
+test_done
diff --git a/t/t0610-reftable-basics.sh b/t/t0610-reftable-basics.sh
index e19e036898..4b7cfe38e4 100755
--- a/t/t0610-reftable-basics.sh
+++ b/t/t0610-reftable-basics.sh
@@ -1163,4 +1163,26 @@ test_expect_success 'writes do not persist peeled value for invalid tags' '
 	)
 '
 
+test_expect_success 'delete and re-create refs with tombstones' '
+	test_when_finished "rm -rf repo" &&
+	git init repo &&
+	test_commit -C repo A &&
+	A=$(git -C repo rev-parse HEAD) &&
+	cat >input <<-EOF &&
+	create refs/tags/a $A
+	create refs/tags/b $A
+	create refs/tags/c $A
+	EOF
+	git -C repo update-ref --stdin <input &&
+
+	# delete all tags, leaving tombstones
+	git -C repo for-each-ref --format="delete %(refname)" refs/tags/ |
+	git -C repo update-ref --stdin &&
+
+	# re-create the same refs and verify they are visible
+	git -C repo update-ref --stdin <input &&
+	git -C repo tag -l >actual &&
+	test_line_count = 3 actual
+'
+
 test_done
-- 
gitgitgadget