---
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
