[RFC PATCH 07/13] test-reach

[Derrick Stolee <dstolee@microsoft.com>]

---
 Makefile              |   1 +
 t/helper/test-reach.c | 123 ++++++++++++++++++++++++++++++++++++++++++
 t/helper/test-tool.c  |   1 +
 t/helper/test-tool.h  |   1 +
 t/t6600-test-reach.sh |  81 ++++++++++++++++++++++++++++
 5 files changed, 207 insertions(+)
 create mode 100644 t/helper/test-reach.c
 create mode 100755 t/t6600-test-reach.sh

diff --git a/Makefile b/Makefile
index 89ad873ce0..c2a2c6457e 100644
--- a/Makefile
+++ b/Makefile
@@ -716,6 +716,7 @@ TEST_BUILTINS_OBJS += test-mktemp.o
 TEST_BUILTINS_OBJS += test-online-cpus.o
 TEST_BUILTINS_OBJS += test-path-utils.o
 TEST_BUILTINS_OBJS += test-prio-queue.o
+TEST_BUILTINS_OBJS += test-reach.o
 TEST_BUILTINS_OBJS += test-read-cache.o
 TEST_BUILTINS_OBJS += test-ref-store.o
 TEST_BUILTINS_OBJS += test-regex.o
diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c
new file mode 100644
index 0000000000..d57660af45
--- /dev/null
+++ b/t/helper/test-reach.c
@@ -0,0 +1,123 @@
+#include "test-tool.h"
+#include "cache.h"
+#include "commit-reach.h"
+#include "config.h"
+#include "parse-options.h"
+#include "tag.h"
+
+int cmd__reach(int ac, const char **av)
+{
+	struct object_id oid_A, oid_B;
+	struct commit *A, *B;
+	struct commit **X, **Y;
+	int nr_X, alloc_X, nr_Y, alloc_Y;
+	struct commit_list *list_X, *list_Y;
+	struct strbuf buf = STRBUF_INIT;
+
+	setup_git_directory();
+	get_git_config(default_git_config, 0);
+
+	if (argc < 2)
+		exit(1);
+
+	/* load input data */
+	A = B = NULL;
+	list_X = list_Y = NULL;
+	nr_X = nr_Y = 0;
+	alloc_X = alloc_Y = 16;
+	ALLOC_ARRAY(X, alloc_X);
+	ALLOC_ARRAY(Y, alloc_Y);
+
+	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(&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(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':
+				ALLOC_GROW(X, nr_X + 1, alloc_X);
+				X[nr_X++] = c;
+				commit_list_insert(c, &list_X);
+				break;
+
+			case 'Y':
+				ALLOC_GROW(Y, nr_Y + 1, alloc_Y);
+				Y[nr_Y++] = c;
+				commit_list_insert(c, &list_Y);
+				break;
+
+			default:
+				die("unexpected start of line: %c", buf.buf[0]);
+		}
+	}
+	strbuf_release(&buf);
+
+	if (ac > 2 && !strcmp(av[2], "graph:off"))
+		core_commit_graph = 0;
+	if (ac > 2 && !strcmp(av[2], "graph:on"))
+		core_commit_graph = 1;
+
+	if (!strcmp(av[1], "ref_newer"))
+		printf("%s:%d\n", av[1], ref_newer(&oid_A, &oid_B));
+	else if (!strcmp(av[1], "in_merge_base"))
+		printf("%s:%d\n", av[1], in_merge_bases(A, B));
+	else if (!strcmp(av[1], "get_merge_bases_many")) {
+		struct commit_list *list = get_merge_bases_many(A, nr_X, X);
+		printf("%s(A,X):\n", av[1]);
+		while (list) {
+			printf("%s\n", oid_to_hex(&list->item->object.oid));
+			list = list->next;
+		}
+
+		list = get_merge_bases_many(B, nr_Y, Y);
+		printf("%s(B,Y):\n", av[1]);
+		while (list) {
+			printf("%s\n", oid_to_hex(&list->item->object.oid));
+			list = list->next;
+		}
+	} else if (!strcmp(av[1], "reduce_heads")) {
+		struct commit_list *list = reduce_heads(list_X);
+		printf("%s(X):\n", av[1]);
+		while (list) {
+			printf("%s\n", oid_to_hex(&list->item->object.oid));
+			list = list->next;
+		}
+
+		list = reduce_heads(list_Y);
+		printf("%s(Y):\n", av[1]);
+		while (list) {
+			printf("%s\n", oid_to_hex(&list->item->object.oid));
+			list = list->next;
+		}
+	}
+
+	exit(0);
+}
diff --git a/t/helper/test-tool.c b/t/helper/test-tool.c
index 805a45de9c..64d250b602 100644
--- a/t/helper/test-tool.c
+++ b/t/helper/test-tool.c
@@ -26,6 +26,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 },
 	{ "ref-store", cmd__ref_store },
 	{ "regex", cmd__regex },
diff --git a/t/helper/test-tool.h b/t/helper/test-tool.h
index 7116ddfb94..0b1d3534b5 100644
--- a/t/helper/test-tool.h
+++ b/t/helper/test-tool.h
@@ -20,6 +20,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__ref_store(int argc, const char **argv);
 int cmd__regex(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..c9337b6b46
--- /dev/null
+++ b/t/t6600-test-reach.sh
@@ -0,0 +1,81 @@
+#!/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 'comit-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
+'
+
+test_reach_two_modes() {
+	test-tool reach $1 graph:off <input >output &&
+	test_cmp output expect &&
+	test-tool reach $1 graph:on <input >output &&
+	test_cmp output expect
+}
+
+test_expect_success 'ref_newer:miss' '
+	cat >input <<- EOF &&
+	A:commit-5-7
+	B:commit-4-9
+	EOF
+	cat >expect <<- EOF &&
+	ref_newer:0
+	EOF
+	test_reach_two_modes "ref_newer"
+'
+
+test_expect_success 'ref_newer:miss' '
+	cat >input <<- EOF &&
+	A:commit-5-7
+	B:commit-2-3
+	EOF
+	cat >expect <<- EOF &&
+	ref_newer:1
+	EOF
+	test_reach_two_modes "ref_newer"
+'
+
+test_done
-- 
2.18.0.118.gd4f65b8d14