diff options
author | Edward Thomson <ethomson@github.com> | 2021-07-27 18:59:15 -0400 |
---|---|---|
committer | GitHub <noreply@github.com> | 2021-07-27 18:59:15 -0400 |
commit | f08cae109d9475a29209d444cf312388e7e64d83 (patch) | |
tree | 8198be68b85ccf4d2e79a6a48d530e13c4fd46e1 | |
parent | 08c79128be38b6704cfdf01bca037f3fbaabf847 (diff) | |
parent | 8d453f16385c04abfba0211f1e7fb1621f26d609 (diff) | |
download | libgit2-f08cae109d9475a29209d444cf312388e7e64d83.tar.gz |
Merge pull request #5767 from lhchavez/cgraph-reachable-from-any
-rw-r--r-- | include/git2/graph.h | 22 | ||||
-rw-r--r-- | src/graph.c | 71 | ||||
-rw-r--r-- | src/merge.c | 28 | ||||
-rw-r--r-- | src/merge.h | 3 | ||||
-rw-r--r-- | tests/graph/reachable_from_any.c | 236 |
5 files changed, 340 insertions, 20 deletions
diff --git a/include/git2/graph.h b/include/git2/graph.h index 213ae9777..712ae474a 100644 --- a/include/git2/graph.h +++ b/include/git2/graph.h @@ -43,8 +43,9 @@ GIT_EXTERN(int) git_graph_ahead_behind(size_t *ahead, size_t *behind, git_reposi * Note that a commit is not considered a descendant of itself, in contrast * to `git merge-base --is-ancestor`. * - * @param commit a previously loaded commit. - * @param ancestor a potential ancestor commit. + * @param repo the repository where the commits exist + * @param commit a previously loaded commit + * @param ancestor a potential ancestor commit * @return 1 if the given commit is a descendant of the potential ancestor, * 0 if not, error code otherwise. */ @@ -53,6 +54,23 @@ GIT_EXTERN(int) git_graph_descendant_of( const git_oid *commit, const git_oid *ancestor); +/** + * Determine if a commit is reachable from any of a list of commits by + * following parent edges. + * + * @param repo the repository where the commits exist + * @param commit a previously loaded commit + * @param length the number of commits in the provided `descendant_array` + * @param descendant_array oids of the commits + * @return 1 if the given commit is an ancestor of any of the given potential + * descendants, 0 if not, error code otherwise. + */ +GIT_EXTERN(int) git_graph_reachable_from_any( + git_repository *repo, + const git_oid *commit, + const git_oid descendant_array[], + size_t length); + /** @} */ GIT_END_DECL #endif diff --git a/src/graph.c b/src/graph.c index 45fae847e..35e914f74 100644 --- a/src/graph.c +++ b/src/graph.c @@ -176,19 +176,74 @@ on_error: int git_graph_descendant_of(git_repository *repo, const git_oid *commit, const git_oid *ancestor) { - git_oid merge_base; - int error; - if (git_oid_equal(commit, ancestor)) return 0; - error = git_merge_base(&merge_base, repo, commit, ancestor); - /* No merge-base found, it's not a descendant */ - if (error == GIT_ENOTFOUND) + return git_graph_reachable_from_any(repo, ancestor, commit, 1); +} + +int git_graph_reachable_from_any( + git_repository *repo, + const git_oid *commit_id, + const git_oid descendant_array[], + size_t length) +{ + git_revwalk *walk = NULL; + git_vector list; + git_commit_list *result = NULL; + git_commit_list_node *commit; + size_t i; + uint32_t minimum_generation = 0xffffffff; + int error = 0; + + if (!length) return 0; - if (error < 0) + for (i = 0; i < length; ++i) { + if (git_oid_equal(commit_id, &descendant_array[i])) + return 1; + } + + if ((error = git_vector_init(&list, length + 1, NULL)) < 0) return error; - return git_oid_equal(&merge_base, ancestor); + if ((error = git_revwalk_new(&walk, repo)) < 0) + goto done; + + for (i = 0; i < length; i++) { + commit = git_revwalk__commit_lookup(walk, &descendant_array[i]); + if (commit == NULL) { + error = -1; + goto done; + } + + git_vector_insert(&list, commit); + if (minimum_generation > commit->generation) + minimum_generation = commit->generation; + } + + commit = git_revwalk__commit_lookup(walk, commit_id); + if (commit == NULL) { + error = -1; + goto done; + } + + if (minimum_generation > commit->generation) + minimum_generation = commit->generation; + + if ((error = git_merge__bases_many(&result, walk, commit, &list, minimum_generation)) < 0) + goto done; + + if (result) { + error = git_oid_equal(commit_id, &result->item->oid); + } else { + /* No merge-base found, it's not a descendant */ + error = 0; + } + +done: + git_commit_list_free(&result); + git_vector_free(&list); + git_revwalk_free(walk); + return error; } diff --git a/src/merge.c b/src/merge.c index fe450b0e7..0e4bb582a 100644 --- a/src/merge.c +++ b/src/merge.c @@ -112,7 +112,7 @@ static int merge_bases_many(git_commit_list **out, git_revwalk **walk_out, git_r if (commit == NULL) goto on_error; - if (git_merge__bases_many(&result, walk, commit, &list) < 0) + if (git_merge__bases_many(&result, walk, commit, &list, 0) < 0) goto on_error; if (!result) { @@ -243,7 +243,7 @@ static int merge_bases(git_commit_list **out, git_revwalk **walk_out, git_reposi if (commit == NULL) goto on_error; - if (git_merge__bases_many(&result, walk, commit, &list) < 0) + if (git_merge__bases_many(&result, walk, commit, &list, 0) < 0) goto on_error; if (!result) { @@ -378,7 +378,11 @@ static int clear_commit_marks(git_commit_list_node *commit, unsigned int mark) } static int paint_down_to_common( - git_commit_list **out, git_revwalk *walk, git_commit_list_node *one, git_vector *twos) + git_commit_list **out, + git_revwalk *walk, + git_commit_list_node *one, + git_vector *twos, + uint32_t minimum_generation) { git_pqueue list; git_commit_list *result = NULL; @@ -399,7 +403,6 @@ static int paint_down_to_common( return -1; two->flags |= PARENT2; - if (git_pqueue_insert(&list, two) < 0) return -1; } @@ -427,6 +430,8 @@ static int paint_down_to_common( git_commit_list_node *p = commit->parents[i]; if ((p->flags & flags) == flags) continue; + if (p->generation < minimum_generation) + continue; if ((error = git_commit_list_parse(walk, p)) < 0) return error; @@ -442,7 +447,7 @@ static int paint_down_to_common( return 0; } -static int remove_redundant(git_revwalk *walk, git_vector *commits) +static int remove_redundant(git_revwalk *walk, git_vector *commits, uint32_t minimum_generation) { git_vector work = GIT_VECTOR_INIT; unsigned char *redundant; @@ -478,7 +483,7 @@ static int remove_redundant(git_revwalk *walk, git_vector *commits) goto done; } - error = paint_down_to_common(&common, walk, commit, &work); + error = paint_down_to_common(&common, walk, commit, &work, minimum_generation); if (error < 0) goto done; @@ -510,7 +515,12 @@ done: return error; } -int git_merge__bases_many(git_commit_list **out, git_revwalk *walk, git_commit_list_node *one, git_vector *twos) +int git_merge__bases_many( + git_commit_list **out, + git_revwalk *walk, + git_commit_list_node *one, + git_vector *twos, + uint32_t minimum_generation) { int error; unsigned int i; @@ -532,7 +542,7 @@ int git_merge__bases_many(git_commit_list **out, git_revwalk *walk, git_commit_l if (git_commit_list_parse(walk, one) < 0) return -1; - error = paint_down_to_common(&result, walk, one, twos); + error = paint_down_to_common(&result, walk, one, twos, minimum_generation); if (error < 0) return error; @@ -559,7 +569,7 @@ int git_merge__bases_many(git_commit_list **out, git_revwalk *walk, git_commit_l if ((error = clear_commit_marks(one, ALL_FLAGS)) < 0 || (error = clear_commit_marks_many(twos, ALL_FLAGS)) < 0 || - (error = remove_redundant(walk, &redundant)) < 0) { + (error = remove_redundant(walk, &redundant, minimum_generation)) < 0) { git_vector_free(&redundant); return error; } diff --git a/src/merge.h b/src/merge.h index b0a7de2be..3e7f80c6e 100644 --- a/src/merge.h +++ b/src/merge.h @@ -129,7 +129,8 @@ int git_merge__bases_many( git_commit_list **out, git_revwalk *walk, git_commit_list_node *one, - git_vector *twos); + git_vector *twos, + uint32_t minimum_generation); /* * Three-way tree differencing diff --git a/tests/graph/reachable_from_any.c b/tests/graph/reachable_from_any.c new file mode 100644 index 000000000..5c8416499 --- /dev/null +++ b/tests/graph/reachable_from_any.c @@ -0,0 +1,236 @@ +#include "clar_libgit2.h" + +#include <git2.h> + +#include "commit_graph.h" +#include "bitvec.h" +#include "vector.h" + +static git_repository *repo; + +#define TEST_REPO_PATH "merge-recursive" + +void test_graph_reachable_from_any__initialize(void) +{ + git_oid oid; + git_commit *commit; + + repo = cl_git_sandbox_init(TEST_REPO_PATH); + + git_oid_fromstr(&oid, "539bd011c4822c560c1d17cab095006b7a10f707"); + cl_git_pass(git_commit_lookup(&commit, repo, &oid)); + cl_git_pass(git_reset(repo, (git_object *)commit, GIT_RESET_HARD, NULL)); + git_commit_free(commit); +} + +void test_graph_reachable_from_any__cleanup(void) +{ + cl_git_sandbox_cleanup(); +} + +void test_graph_reachable_from_any__returns_correct_result(void) +{ + git_object *branchA1, *branchA2, *branchB1, *branchB2, *branchC1, *branchC2, *branchH1, + *branchH2; + git_oid descendants[7]; + + cl_git_pass(git_revparse_single(&branchA1, repo, "branchA-1")); + cl_git_pass(git_revparse_single(&branchA2, repo, "branchA-2")); + cl_git_pass(git_revparse_single(&branchB1, repo, "branchB-1")); + cl_git_pass(git_revparse_single(&branchB2, repo, "branchB-2")); + cl_git_pass(git_revparse_single(&branchC1, repo, "branchC-1")); + cl_git_pass(git_revparse_single(&branchC2, repo, "branchC-2")); + cl_git_pass(git_revparse_single(&branchH1, repo, "branchH-1")); + cl_git_pass(git_revparse_single(&branchH2, repo, "branchH-2")); + + cl_assert_equal_i( + git_graph_reachable_from_any( + repo, git_object_id(branchH1), git_object_id(branchA1), 1), + 0); + cl_assert_equal_i( + git_graph_reachable_from_any( + repo, git_object_id(branchH1), git_object_id(branchA2), 1), + 0); + + cl_git_pass(git_oid_cpy(&descendants[0], git_object_id(branchA1))); + cl_git_pass(git_oid_cpy(&descendants[1], git_object_id(branchA2))); + cl_git_pass(git_oid_cpy(&descendants[2], git_object_id(branchB1))); + cl_git_pass(git_oid_cpy(&descendants[3], git_object_id(branchB2))); + cl_git_pass(git_oid_cpy(&descendants[4], git_object_id(branchC1))); + cl_git_pass(git_oid_cpy(&descendants[5], git_object_id(branchC2))); + cl_git_pass(git_oid_cpy(&descendants[6], git_object_id(branchH2))); + cl_assert_equal_i( + git_graph_reachable_from_any(repo, git_object_id(branchH2), descendants, 6), + 0); + cl_assert_equal_i( + git_graph_reachable_from_any(repo, git_object_id(branchH2), descendants, 7), + 1); + + git_object_free(branchA1); + git_object_free(branchA2); + git_object_free(branchB1); + git_object_free(branchB2); + git_object_free(branchC1); + git_object_free(branchC2); + git_object_free(branchH1); + git_object_free(branchH2); +} + +struct exhaustive_state { + git_odb *db; + git_vector commits; +}; + +/** Get all commits from the repository. */ +static int exhaustive_commits(const git_oid *id, void *payload) +{ + struct exhaustive_state *mc = (struct exhaustive_state *)payload; + size_t header_len; + git_object_t header_type; + int error = 0; + + error = git_odb_read_header(&header_len, &header_type, mc->db, id); + if (error < 0) + return error; + + if (header_type == GIT_OBJECT_COMMIT) { + git_commit *commit = NULL; + + cl_git_pass(git_commit_lookup(&commit, repo, id)); + cl_git_pass(git_vector_insert(&mc->commits, commit)); + } + + return 0; +} + +/** Compare the `git_oid`s of two `git_commit` objects. */ +static int commit_id_cmp(const void *a, const void *b) +{ + return git_oid_cmp( + git_commit_id((const git_commit *)a), git_commit_id((const git_commit *)b)); +} + +/** Find a `git_commit` whose ID matches the provided `git_oid` key. */ +static int id_commit_id_cmp(const void *key, const void *commit) +{ + return git_oid_cmp((const git_oid *)key, git_commit_id((const git_commit *)commit)); +} + +void test_graph_reachable_from_any__exhaustive(void) +{ + struct exhaustive_state mc = { + .db = NULL, + .commits = GIT_VECTOR_INIT, + }; + size_t child_idx, commit_count; + size_t n_descendants; + git_commit *child_commit; + git_bitvec reachable; + + cl_git_pass(git_repository_odb(&mc.db, repo)); + cl_git_pass(git_odb_foreach(mc.db, &exhaustive_commits, &mc)); + git_vector_set_cmp(&mc.commits, commit_id_cmp); + git_vector_sort(&mc.commits); + cl_git_pass(git_bitvec_init( + &reachable, + git_vector_length(&mc.commits) * git_vector_length(&mc.commits))); + + commit_count = git_vector_length(&mc.commits); + git_vector_foreach (&mc.commits, child_idx, child_commit) { + unsigned int parent_i; + + /* We treat each commit as being able to reach itself. */ + git_bitvec_set(&reachable, child_idx * commit_count + child_idx, true); + + for (parent_i = 0; parent_i < git_commit_parentcount(child_commit); ++parent_i) { + size_t parent_idx = -1; + cl_git_pass(git_vector_bsearch2( + &parent_idx, + &mc.commits, + id_commit_id_cmp, + git_commit_parent_id(child_commit, parent_i))); + + /* We have established that parent_idx is reachable from child_idx */ + git_bitvec_set(&reachable, parent_idx * commit_count + child_idx, true); + } + } + + /* Floyd-Warshall */ + { + size_t i, j, k; + for (k = 0; k < commit_count; ++k) { + for (i = 0; i < commit_count; ++i) { + if (!git_bitvec_get(&reachable, i * commit_count + k)) + continue; + for (j = 0; j < commit_count; ++j) { + if (!git_bitvec_get(&reachable, k * commit_count + j)) + continue; + git_bitvec_set(&reachable, i * commit_count + j, true); + } + } + } + } + + /* Try 1000 subsets of 1 through 10 entries each. */ + srand(0x223ddc4b); + for (n_descendants = 1; n_descendants < 10; ++n_descendants) { + size_t test_iteration; + git_oid descendants[10]; + + for (test_iteration = 0; test_iteration < 1000; ++test_iteration) { + size_t descendant_i; + size_t child_idx, parent_idx; + int expected_reachable = false, actual_reachable; + git_commit *child_commit, *parent_commit; + + parent_idx = rand() % commit_count; + parent_commit = (git_commit *)git_vector_get(&mc.commits, parent_idx); + for (descendant_i = 0; descendant_i < n_descendants; ++descendant_i) { + child_idx = rand() % commit_count; + child_commit = (git_commit *)git_vector_get(&mc.commits, child_idx); + expected_reachable |= git_bitvec_get( + &reachable, parent_idx * commit_count + child_idx); + git_oid_cpy(&descendants[descendant_i], + git_commit_id(child_commit)); + } + + actual_reachable = git_graph_reachable_from_any( + repo, + git_commit_id(parent_commit), + descendants, + n_descendants); + if (actual_reachable != expected_reachable) { + git_buf error_message_buf = GIT_BUF_INIT; + char parent_oidbuf[9] = {0}, child_oidbuf[9] = {0}; + + cl_git_pass(git_oid_nfmt( + parent_oidbuf, 8, git_commit_id(parent_commit))); + git_buf_printf(&error_message_buf, + "git_graph_reachable_from_any(\"%s\", %zu, " + "{", + parent_oidbuf, + n_descendants); + for (descendant_i = 0; descendant_i < n_descendants; + ++descendant_i) { + cl_git_pass( + git_oid_nfmt(child_oidbuf, + 8, + &descendants[descendant_i])); + git_buf_printf(&error_message_buf, " \"%s\"", child_oidbuf); + } + git_buf_printf(&error_message_buf, + " }) = %d, expected = %d", + actual_reachable, + expected_reachable); + cl_check_(actual_reachable == expected_reachable, + git_buf_cstr(&error_message_buf)); + } + } + } + + git_vector_foreach (&mc.commits, child_idx, child_commit) + git_commit_free(child_commit); + git_bitvec_free(&reachable); + git_vector_free(&mc.commits); + git_odb_free(mc.db); +} |