Merge branch 'ds/reachable'

The code for computing history reachability has been shuffled,
obtained a bunch of new tests to cover them, and then being
improved.

* ds/reachable:
  commit-reach: correct accidental #include of C file
  commit-reach: use can_all_from_reach
  commit-reach: make can_all_from_reach... linear
  commit-reach: replace ref_newer logic
  test-reach: test commit_contains
  test-reach: test can_all_from_reach_with_flags
  test-reach: test reduce_heads
  test-reach: test get_merge_bases_many
  test-reach: test is_descendant_of
  test-reach: test in_merge_bases
  test-reach: create new test tool for ref_newer
  commit-reach: move can_all_from_reach_with_flags
  upload-pack: generalize commit date cutoff
  upload-pack: refactor ok_to_give_up()
  upload-pack: make reachable() more generic
  commit-reach: move commit_contains from ref-filter
  commit-reach: move ref_newer from remote.c
  commit.h: remove method declarations
  commit-reach: move walk methods from commit.c

4 files changed, 374 insertions, 0 deletions

diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c
new file mode 100644
index 0000000000..eb21103998
--- /dev/null
+++ b/t/helper/test-reach.c
@@ -0,0 +1,130 @@
+#include "test-tool.h"
+#include "cache.h"
+#include "commit.h"
+#include "commit-reach.h"
+#include "config.h"
+#include "parse-options.h"
+#include "ref-filter.h"
+#include "string-list.h"
+#include "tag.h"
+
+static void print_sorted_commit_ids(struct commit_list *list)
+{
+	int i;
+	struct string_list s = STRING_LIST_INIT_DUP;
+
+	while (list) {
+		string_list_append(&s, oid_to_hex(&list->item->object.oid));
+		list = list->next;
+	}
+
+	string_list_sort(&s);
+
+	for (i = 0; i < s.nr; i++)
+		printf("%s\n", s.items[i].string);
+
+	string_list_clear(&s, 0);
+}
+
+int cmd__reach(int ac, const char **av)
+{
+	struct object_id oid_A, oid_B;
+	struct commit *A, *B;
+	struct commit_list *X, *Y;
+	struct commit **X_array;
+	int X_nr, X_alloc;
+	struct strbuf buf = STRBUF_INIT;
+	struct repository *r = the_repository;
+
+	setup_git_directory();
+
+	if (ac < 2)
+		exit(1);
+
+	A = B = NULL;
+	X = Y = NULL;
+	X_nr = 0;
+	X_alloc = 16;
+	ALLOC_ARRAY(X_array, X_alloc);
+
+	while (strbuf_getline(&buf, stdin) != EOF) {
+		struct object_id oid;
+		struct object *o;
+		struct commit *c;
+		if (buf.len < 3)
+			continue;
+
+		if (get_oid_committish(buf.buf + 2, &oid))
+			die("failed to resolve %s", buf.buf + 2);
+
+		o = parse_object(r, &oid);
+		o = deref_tag_noverify(o);
+
+		if (!o)
+			die("failed to load commit for input %s resulting in oid %s\n",
+			    buf.buf, oid_to_hex(&oid));
+
+		c = object_as_type(r, o, OBJ_COMMIT, 0);
+
+		if (!c)
+			die("failed to load commit for input %s resulting in oid %s\n",
+			    buf.buf, oid_to_hex(&oid));
+
+		switch (buf.buf[0]) {
+			case 'A':
+				oidcpy(&oid_A, &oid);
+				A = c;
+				break;
+
+			case 'B':
+				oidcpy(&oid_B, &oid);
+				B = c;
+				break;
+
+			case 'X':
+				commit_list_insert(c, &X);
+				ALLOC_GROW(X_array, X_nr + 1, X_alloc);
+				X_array[X_nr++] = c;
+				break;
+
+			case 'Y':
+				commit_list_insert(c, &Y);
+				break;
+
+			default:
+				die("unexpected start of line: %c", buf.buf[0]);
+		}
+	}
+	strbuf_release(&buf);
+
+	if (!strcmp(av[1], "ref_newer"))
+		printf("%s(A,B):%d\n", av[1], ref_newer(&oid_A, &oid_B));
+	else if (!strcmp(av[1], "in_merge_bases"))
+		printf("%s(A,B):%d\n", av[1], in_merge_bases(A, B));
+	else if (!strcmp(av[1], "is_descendant_of"))
+		printf("%s(A,X):%d\n", av[1], is_descendant_of(A, X));
+	else if (!strcmp(av[1], "get_merge_bases_many")) {
+		struct commit_list *list = get_merge_bases_many(A, X_nr, X_array);
+		printf("%s(A,X):\n", av[1]);
+		print_sorted_commit_ids(list);
+	} else if (!strcmp(av[1], "reduce_heads")) {
+		struct commit_list *list = reduce_heads(X);
+		printf("%s(X):\n", av[1]);
+		print_sorted_commit_ids(list);
+	} else if (!strcmp(av[1], "can_all_from_reach")) {
+		printf("%s(X,Y):%d\n", av[1], can_all_from_reach(X, Y, 1));
+	} else if (!strcmp(av[1], "commit_contains")) {
+		struct ref_filter filter;
+		struct contains_cache cache;
+		init_contains_cache(&cache);
+
+		if (ac > 2 && !strcmp(av[2], "--tag"))
+			filter.with_commit_tag_algo = 1;
+		else
+			filter.with_commit_tag_algo = 0;
+
+		printf("%s(_,A,X,_):%d\n", av[1], commit_contains(&filter, A, X, &cache));
+	}
+
+	exit(0);
+}
diff --git a/t/helper/test-tool.c b/t/helper/test-tool.c
index 3276701710..bef50c4dcc 100644
--- a/t/helper/test-tool.c
+++ b/t/helper/test-tool.c
@@ -27,6 +27,7 @@ static struct test_cmd cmds[] = {
 	{ "online-cpus", cmd__online_cpus },
 	{ "path-utils", cmd__path_utils },
 	{ "prio-queue", cmd__prio_queue },
+	{ "reach", cmd__reach },
 	{ "read-cache", cmd__read_cache },
 	{ "read-midx", cmd__read_midx },
 	{ "ref-store", cmd__ref_store },
diff --git a/t/helper/test-tool.h b/t/helper/test-tool.h
index 710fb1b286..321982e4bc 100644
--- a/t/helper/test-tool.h
+++ b/t/helper/test-tool.h
@@ -23,6 +23,7 @@ int cmd__mktemp(int argc, const char **argv);
 int cmd__online_cpus(int argc, const char **argv);
 int cmd__path_utils(int argc, const char **argv);
 int cmd__prio_queue(int argc, const char **argv);
+int cmd__reach(int argc, const char **argv);
 int cmd__read_cache(int argc, const char **argv);
 int cmd__read_midx(int argc, const char **argv);
 int cmd__ref_store(int argc, const char **argv);
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
new file mode 100755
index 0000000000..d139a00d1d
--- /dev/null
+++ b/t/t6600-test-reach.sh
@@ -0,0 +1,242 @@
+#!/bin/sh
+
+test_description='basic commit reachability tests'
+
+. ./test-lib.sh
+
+# Construct a grid-like commit graph with points (x,y)
+# with 1 <= x <= 10, 1 <= y <= 10, where (x,y) has
+# parents (x-1, y) and (x, y-1), keeping in mind that
+# we drop a parent if a coordinate is nonpositive.
+#
+#             (10,10)
+#            /       \
+#         (10,9)    (9,10)
+#        /     \   /      \
+#    (10,8)    (9,9)      (8,10)
+#   /     \    /   \      /    \
+#         ( continued...)
+#   \     /    \   /      \    /
+#    (3,1)     (2,2)      (1,3)
+#        \     /    \     /
+#         (2,1)      (2,1)
+#              \    /
+#              (1,1)
+#
+# We use branch 'commit-x-y' to refer to (x,y).
+# This grid allows interesting reachability and
+# non-reachability queries: (x,y) can reach (x',y')
+# if and only if x' <= x and y' <= y.
+test_expect_success 'setup' '
+	for i in $(test_seq 1 10)
+	do
+		test_commit "1-$i" &&
+		git branch -f commit-1-$i
+	done &&
+	for j in $(test_seq 1 9)
+	do
+		git reset --hard commit-$j-1 &&
+		x=$(($j + 1)) &&
+		test_commit "$x-1" &&
+		git branch -f commit-$x-1 &&
+
+		for i in $(test_seq 2 10)
+		do
+			git merge commit-$j-$i -m "$x-$i" &&
+			git branch -f commit-$x-$i
+		done
+	done &&
+	git commit-graph write --reachable &&
+	mv .git/objects/info/commit-graph commit-graph-full &&
+	git show-ref -s commit-5-5 | git commit-graph write --stdin-commits &&
+	mv .git/objects/info/commit-graph commit-graph-half &&
+	git config core.commitGraph true
+'
+
+test_three_modes () {
+	test_when_finished rm -rf .git/objects/info/commit-graph &&
+	test-tool reach $1 <input >actual &&
+	test_cmp expect actual &&
+	cp commit-graph-full .git/objects/info/commit-graph &&
+	test-tool reach $1 <input >actual &&
+	test_cmp expect actual &&
+	cp commit-graph-half .git/objects/info/commit-graph &&
+	test-tool reach $1 <input >actual &&
+	test_cmp expect actual
+}
+
+test_expect_success 'ref_newer:miss' '
+	cat >input <<-\EOF &&
+	A:commit-5-7
+	B:commit-4-9
+	EOF
+	echo "ref_newer(A,B):0" >expect &&
+	test_three_modes ref_newer
+'
+
+test_expect_success 'ref_newer:hit' '
+	cat >input <<-\EOF &&
+	A:commit-5-7
+	B:commit-2-3
+	EOF
+	echo "ref_newer(A,B):1" >expect &&
+	test_three_modes ref_newer
+'
+
+test_expect_success 'in_merge_bases:hit' '
+	cat >input <<-\EOF &&
+	A:commit-5-7
+	B:commit-8-8
+	EOF
+	echo "in_merge_bases(A,B):1" >expect &&
+	test_three_modes in_merge_bases
+'
+
+test_expect_success 'in_merge_bases:miss' '
+	cat >input <<-\EOF &&
+	A:commit-6-8
+	B:commit-5-9
+	EOF
+	echo "in_merge_bases(A,B):0" >expect &&
+	test_three_modes in_merge_bases
+'
+
+test_expect_success 'is_descendant_of:hit' '
+	cat >input <<-\EOF &&
+	A:commit-5-7
+	X:commit-4-8
+	X:commit-6-6
+	X:commit-1-1
+	EOF
+	echo "is_descendant_of(A,X):1" >expect &&
+	test_three_modes is_descendant_of
+'
+
+test_expect_success 'is_descendant_of:miss' '
+	cat >input <<-\EOF &&
+	A:commit-6-8
+	X:commit-5-9
+	X:commit-4-10
+	X:commit-7-6
+	EOF
+	echo "is_descendant_of(A,X):0" >expect &&
+	test_three_modes is_descendant_of
+'
+
+test_expect_success 'get_merge_bases_many' '
+	cat >input <<-\EOF &&
+	A:commit-5-7
+	X:commit-4-8
+	X:commit-6-6
+	X:commit-8-3
+	EOF
+	{
+		echo "get_merge_bases_many(A,X):" &&
+		git rev-parse commit-5-6 \
+			      commit-4-7 | sort
+	} >expect &&
+	test_three_modes get_merge_bases_many
+'
+
+test_expect_success 'reduce_heads' '
+	cat >input <<-\EOF &&
+	X:commit-1-10
+	X:commit-2-8
+	X:commit-3-6
+	X:commit-4-4
+	X:commit-1-7
+	X:commit-2-5
+	X:commit-3-3
+	X:commit-5-1
+	EOF
+	{
+		echo "reduce_heads(X):" &&
+		git rev-parse commit-5-1 \
+			      commit-4-4 \
+			      commit-3-6 \
+			      commit-2-8 \
+			      commit-1-10 | sort
+	} >expect &&
+	test_three_modes reduce_heads
+'
+
+test_expect_success 'can_all_from_reach:hit' '
+	cat >input <<-\EOF &&
+	X:commit-2-10
+	X:commit-3-9
+	X:commit-4-8
+	X:commit-5-7
+	X:commit-6-6
+	X:commit-7-5
+	X:commit-8-4
+	X:commit-9-3
+	Y:commit-1-9
+	Y:commit-2-8
+	Y:commit-3-7
+	Y:commit-4-6
+	Y:commit-5-5
+	Y:commit-6-4
+	Y:commit-7-3
+	Y:commit-8-1
+	EOF
+	echo "can_all_from_reach(X,Y):1" >expect &&
+	test_three_modes can_all_from_reach
+'
+
+test_expect_success 'can_all_from_reach:miss' '
+	cat >input <<-\EOF &&
+	X:commit-2-10
+	X:commit-3-9
+	X:commit-4-8
+	X:commit-5-7
+	X:commit-6-6
+	X:commit-7-5
+	X:commit-8-4
+	X:commit-9-3
+	Y:commit-1-9
+	Y:commit-2-8
+	Y:commit-3-7
+	Y:commit-4-6
+	Y:commit-5-5
+	Y:commit-6-4
+	Y:commit-8-5
+	EOF
+	echo "can_all_from_reach(X,Y):0" >expect &&
+	test_three_modes can_all_from_reach
+'
+
+test_expect_success 'commit_contains:hit' '
+	cat >input <<-\EOF &&
+	A:commit-7-7
+	X:commit-2-10
+	X:commit-3-9
+	X:commit-4-8
+	X:commit-5-7
+	X:commit-6-6
+	X:commit-7-5
+	X:commit-8-4
+	X:commit-9-3
+	EOF
+	echo "commit_contains(_,A,X,_):1" >expect &&
+	test_three_modes commit_contains &&
+	test_three_modes commit_contains --tag
+'
+
+test_expect_success 'commit_contains:miss' '
+	cat >input <<-\EOF &&
+	A:commit-6-5
+	X:commit-2-10
+	X:commit-3-9
+	X:commit-4-8
+	X:commit-5-7
+	X:commit-6-6
+	X:commit-7-5
+	X:commit-8-4
+	X:commit-9-3
+	EOF
+	echo "commit_contains(_,A,X,_):0" >expect &&
+	test_three_modes commit_contains &&
+	test_three_modes commit_contains --tag
+'
+
+test_done