check_everything_connected: assume alternate ref tips are valid

When we receive a remote ref update to sha1 "X", we want to check that
we have all of the objects needed by "X". We can assume that our
repository is not currently corrupted, and therefore if we have a ref
pointing at "Y", we have all of its objects. So we can stop our
traversal from "X" as soon as we hit "Y".

If we make the same non-corruption assumption about any repositories we
use to store alternates, then we can also use their ref tips to shorten
the traversal.

This is especially useful when cloning with "--reference", as we
otherwise do not have any local refs to check against, and have to
traverse the whole history, even though the other side may have sent us
few or no objects. Here are results for the included perf test (which
shows off more or less the maximal savings, getting one new commit and
sharing the whole history):

Test                        HEAD^             HEAD
--------------------------------------------------------------------
[on git.git]
5600.3: clone --reference   2.94(2.86+0.08)   0.09(0.08+0.01) -96.9%
[on linux.git]
5600.3: clone --reference   45.74(45.34+0.41)   0.36(0.30+0.08) -99.2%

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

2 files changed, 87 insertions, 0 deletions

diff --git a/t/perf/p5600-clone-reference.sh b/t/perf/p5600-clone-reference.sh
new file mode 100755
index 0000000000..68fed66347
--- /dev/null
+++ b/t/perf/p5600-clone-reference.sh
@@ -0,0 +1,27 @@
+#!/bin/sh
+
+test_description='speed of clone --reference'
+. ./perf-lib.sh
+
+test_perf_default_repo
+
+test_expect_success 'create shareable repository' '
+	git clone --bare . shared.git
+'
+
+test_expect_success 'advance base repository' '
+	# Do not use test_commit here; its test_tick will
+	# use some ancient hard-coded date. The resulting clock
+	# skew will cause pack-objects to traverse in a very
+	# sub-optimal order, skewing the results.
+	echo content >new-file-that-does-not-exist &&
+	git add new-file-that-does-not-exist &&
+	git commit -m "new commit"
+'
+
+test_perf 'clone --reference' '
+	rm -rf dst.git &&
+	git clone --no-local --bare --reference shared.git . dst.git
+'
+
+test_done
diff --git a/t/t5618-alternate-refs.sh b/t/t5618-alternate-refs.sh
new file mode 100755
index 0000000000..3353216f09
--- /dev/null
+++ b/t/t5618-alternate-refs.sh
@@ -0,0 +1,60 @@
+#!/bin/sh
+
+test_description='test handling of --alternate-refs traversal'
+. ./test-lib.sh
+
+# Avoid test_commit because we want a specific and known set of refs:
+#
+#  base -- one
+#      \      \
+#       two -- merged
+#
+# where "one" and "two" are on separate refs, and "merged" is available only in
+# the dependent child repository.
+test_expect_success 'set up local refs' '
+	git checkout -b one &&
+	test_tick &&
+	git commit --allow-empty -m base &&
+	test_tick &&
+	git commit --allow-empty -m one &&
+	git checkout -b two HEAD^ &&
+	test_tick &&
+	git commit --allow-empty -m two
+'
+
+# We'll enter the child repository after it's set up since that's where
+# all of the subsequent tests will want to run (and it's easy to forget a
+# "-C child" and get nonsense results).
+test_expect_success 'set up shared clone' '
+	git clone -s . child &&
+	cd child &&
+	git merge origin/one
+'
+
+test_expect_success 'rev-list --alternate-refs' '
+	git rev-list --remotes=origin >expect &&
+	git rev-list --alternate-refs >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'rev-list --not --alternate-refs' '
+	git rev-parse HEAD >expect &&
+	git rev-list HEAD --not --alternate-refs >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'limiting with alternateRefsPrefixes' '
+	test_config core.alternateRefsPrefixes refs/heads/one &&
+	git rev-list origin/one >expect &&
+	git rev-list --alternate-refs >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'log --source shows .alternate marker' '
+	git log --oneline --source --remotes=origin >expect.orig &&
+	sed "s/origin.* /.alternate /" <expect.orig >expect &&
+	git log --oneline --source --alternate-refs >actual &&
+	test_cmp expect actual
+'
+
+test_done