From ab176ac4ae9456a97ff4904c0222c6a0fc63a130 Mon Sep 17 00:00:00 2001 From: Derrick Stolee Date: Fri, 20 Jul 2018 16:33:15 +0000 Subject: test-reach: create new test tool for ref_newer As we prepare to change the behavior of the algorithms in commit-reach.c, create a new test-tool subcommand 'reach' to test these methods on interesting commit-graph shapes. To use the new test-tool, use 'test-tool reach ' and provide input to stdin that describes the inputs to the method. Currently, we only implement the ref_newer method, which requires two commits. Use lines "A:" and "B:" for the two inputs. We will expand this input later to accommodate methods that take lists of commits. The test t6600-test-reach.sh creates a repo whose commits form a two-dimensional grid. This grid makes it easy for us to determine reachability because commit-A-B can reach commit-X-Y if and only if A is at least X and B is at least Y. This helps create interesting test cases for each result of the methods in commit-reach.c. We test all methods in three different states of the commit-graph file: Non-existent (no generation numbers), fully computed, and mixed (some commits have generation numbers and others do not). Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano --- t/helper/test-reach.c | 63 +++++++++++++++++++++++++++++++++++++++++++++++++++ t/helper/test-tool.c | 1 + t/helper/test-tool.h | 1 + 3 files changed, 65 insertions(+) create mode 100644 t/helper/test-reach.c (limited to 't/helper') diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c new file mode 100644 index 0000000000..620bb46041 --- /dev/null +++ b/t/helper/test-reach.c @@ -0,0 +1,63 @@ +#include "test-tool.h" +#include "cache.h" +#include "commit.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 strbuf buf = STRBUF_INIT; + struct repository *r = the_repository; + + setup_git_directory(); + + if (ac < 2) + exit(1); + + + 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); + break; + + case 'B': + oidcpy(&oid_B, &oid); + 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)); + + exit(0); +} diff --git a/t/helper/test-tool.c b/t/helper/test-tool.c index dafc91c240..582d02adfd 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 80cbcf0857..a7e53c420e 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); -- cgit v1.2.3 From 5cd52de3264a0a93fad8a0a770445657438bf660 Mon Sep 17 00:00:00 2001 From: Derrick Stolee Date: Fri, 20 Jul 2018 16:33:17 +0000 Subject: test-reach: test in_merge_bases Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano --- t/helper/test-reach.c | 6 ++++++ 1 file changed, 6 insertions(+) (limited to 't/helper') diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c index 620bb46041..f93ad5084d 100644 --- a/t/helper/test-reach.c +++ b/t/helper/test-reach.c @@ -9,6 +9,7 @@ int cmd__reach(int ac, const char **av) { struct object_id oid_A, oid_B; + struct commit *A, *B; struct strbuf buf = STRBUF_INIT; struct repository *r = the_repository; @@ -17,6 +18,7 @@ int cmd__reach(int ac, const char **av) if (ac < 2) exit(1); + A = B = NULL; while (strbuf_getline(&buf, stdin) != EOF) { struct object_id oid; @@ -44,10 +46,12 @@ int cmd__reach(int ac, const char **av) switch (buf.buf[0]) { case 'A': oidcpy(&oid_A, &oid); + A = c; break; case 'B': oidcpy(&oid_B, &oid); + B = c; break; default: @@ -58,6 +62,8 @@ int cmd__reach(int ac, const char **av) 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)); exit(0); } -- cgit v1.2.3 From 6255232ec13b038a48326135f2e479797cd0d1f9 Mon Sep 17 00:00:00 2001 From: Derrick Stolee Date: Fri, 20 Jul 2018 16:33:18 +0000 Subject: test-reach: test is_descendant_of The is_descendant_of method takes a single commit as its first parameter and a list of commits as its second parameter. Extend the input of the 'test-tool reach' command to take multiple lines of the form "X:" to construct a list of commits. Pass these to is_descendant_of and create tests that check each result. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano --- t/helper/test-reach.c | 8 ++++++++ 1 file changed, 8 insertions(+) (limited to 't/helper') diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c index f93ad5084d..dccbd48178 100644 --- a/t/helper/test-reach.c +++ b/t/helper/test-reach.c @@ -10,6 +10,7 @@ int cmd__reach(int ac, const char **av) { struct object_id oid_A, oid_B; struct commit *A, *B; + struct commit_list *X; struct strbuf buf = STRBUF_INIT; struct repository *r = the_repository; @@ -19,6 +20,7 @@ int cmd__reach(int ac, const char **av) exit(1); A = B = NULL; + X = NULL; while (strbuf_getline(&buf, stdin) != EOF) { struct object_id oid; @@ -54,6 +56,10 @@ int cmd__reach(int ac, const char **av) B = c; break; + case 'X': + commit_list_insert(c, &X); + break; + default: die("unexpected start of line: %c", buf.buf[0]); } @@ -64,6 +70,8 @@ int cmd__reach(int ac, const char **av) 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)); exit(0); } -- cgit v1.2.3 From 324dec0191e7579e3990e707d334652c0fe4a786 Mon Sep 17 00:00:00 2001 From: Derrick Stolee Date: Fri, 20 Jul 2018 16:33:20 +0000 Subject: test-reach: test get_merge_bases_many The get_merge_bases_many method returns a list of merge bases for a single commit (A) against a list of commits (X). Some care is needed in constructing the expected behavior because the result is not the expected merge-base for an octopus merge with those parents but instead the set of maximal commits that are reachable from A and at least one of the commits in X. Add get_merge_bases_many to 'test-tool reach' and create a test that demonstrates that this output returns multiple results. Specifically, we select a list of three commits such that we output two commits that are reachable from one of the first two, respectively, and none are reachable from the third. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano --- t/helper/test-reach.c | 31 +++++++++++++++++++++++++++++++ 1 file changed, 31 insertions(+) (limited to 't/helper') diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c index dccbd48178..4df01187c9 100644 --- a/t/helper/test-reach.c +++ b/t/helper/test-reach.c @@ -4,13 +4,34 @@ #include "commit-reach.h" #include "config.h" #include "parse-options.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; + struct commit **X_array; + int X_nr, X_alloc; struct strbuf buf = STRBUF_INIT; struct repository *r = the_repository; @@ -21,6 +42,9 @@ int cmd__reach(int ac, const char **av) A = B = NULL; X = NULL; + X_nr = 0; + X_alloc = 16; + ALLOC_ARRAY(X_array, X_alloc); while (strbuf_getline(&buf, stdin) != EOF) { struct object_id oid; @@ -58,6 +82,8 @@ int cmd__reach(int ac, const char **av) case 'X': commit_list_insert(c, &X); + ALLOC_GROW(X_array, X_nr + 1, X_alloc); + X_array[X_nr++] = c; break; default: @@ -72,6 +98,11 @@ int cmd__reach(int ac, const char **av) 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); + } exit(0); } -- cgit v1.2.3 From 0c89f715d06082216cc312dcd39e09cb80f7aad7 Mon Sep 17 00:00:00 2001 From: Derrick Stolee Date: Fri, 20 Jul 2018 16:33:22 +0000 Subject: test-reach: test reduce_heads Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano --- t/helper/test-reach.c | 4 ++++ 1 file changed, 4 insertions(+) (limited to 't/helper') diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c index 4df01187c9..e32e193b70 100644 --- a/t/helper/test-reach.c +++ b/t/helper/test-reach.c @@ -102,6 +102,10 @@ int cmd__reach(int ac, const char **av) 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); } exit(0); -- cgit v1.2.3 From 1792bc125069e3e5b59f0158e259335a07aa7cf5 Mon Sep 17 00:00:00 2001 From: Derrick Stolee Date: Fri, 20 Jul 2018 16:33:23 +0000 Subject: test-reach: test can_all_from_reach_with_flags The can_all_from_reach_with_flags method is used by ok_to_give_up in upload-pack.c to see if we have done enough negotiation during a fetch. This method is intentionally created to preserve state between calls to assist with stateful negotiation, such as over SSH. To make this method testable, add a new can_all_from_reach method that does the initial setup and final tear-down. We will later use this method in production code. Call the method from 'test-tool reach' for now. Since this is a many-to-many reachability query, add a new type of input to the 'test-tool reach' input format. Lines "Y:" create a list of commits to be the reachability targets from the commits in the 'X' list. In the context of fetch negotiation, the 'X' commits are the 'want' commits and the 'Y' commits are the 'have' commits. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano --- t/helper/test-reach.c | 10 ++++++++-- 1 file changed, 8 insertions(+), 2 deletions(-) (limited to 't/helper') diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c index e32e193b70..c79729cac0 100644 --- a/t/helper/test-reach.c +++ b/t/helper/test-reach.c @@ -29,7 +29,7 @@ int cmd__reach(int ac, const char **av) { struct object_id oid_A, oid_B; struct commit *A, *B; - struct commit_list *X; + struct commit_list *X, *Y; struct commit **X_array; int X_nr, X_alloc; struct strbuf buf = STRBUF_INIT; @@ -41,7 +41,7 @@ int cmd__reach(int ac, const char **av) exit(1); A = B = NULL; - X = NULL; + X = Y = NULL; X_nr = 0; X_alloc = 16; ALLOC_ARRAY(X_array, X_alloc); @@ -86,6 +86,10 @@ int cmd__reach(int ac, const char **av) X_array[X_nr++] = c; break; + case 'Y': + commit_list_insert(c, &Y); + break; + default: die("unexpected start of line: %c", buf.buf[0]); } @@ -106,6 +110,8 @@ int cmd__reach(int ac, const char **av) 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)); } exit(0); -- cgit v1.2.3 From 1fee1242577ae23b32c33ff1122402bb228f2692 Mon Sep 17 00:00:00 2001 From: Derrick Stolee Date: Fri, 20 Jul 2018 16:33:25 +0000 Subject: test-reach: test commit_contains The commit_contains method has two modes which depend on the given ref_filter struct. We have the "normal" algorithm (which is also the typically-slow operation) and the "tag" algorithm. This difference is essentially what changes performance for 'git branch --contains' versus 'git tag --contains'. There are thoughts that the data shapes used by these two applications justify the different implementations. Create tests using 'test-tool reach commit_contains [--tag]' to cover both methods. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano --- t/helper/test-reach.c | 12 ++++++++++++ 1 file changed, 12 insertions(+) (limited to 't/helper') diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c index c79729cac0..eb21103998 100644 --- a/t/helper/test-reach.c +++ b/t/helper/test-reach.c @@ -4,6 +4,7 @@ #include "commit-reach.h" #include "config.h" #include "parse-options.h" +#include "ref-filter.h" #include "string-list.h" #include "tag.h" @@ -112,6 +113,17 @@ int cmd__reach(int ac, const char **av) 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); -- cgit v1.2.3