diff options
Diffstat (limited to 'src/merge.c')
| -rw-r--r-- | src/merge.c | 196 |
1 files changed, 196 insertions, 0 deletions
diff --git a/src/merge.c b/src/merge.c index 135af6a8c..c795b808b 100644 --- a/src/merge.c +++ b/src/merge.c @@ -6,12 +6,14 @@ */ #include "repository.h" +#include "revwalk.h" #include "buffer.h" #include "merge.h" #include "refs.h" #include "git2/repository.h" #include "git2/merge.h" #include "git2/reset.h" +#include "commit_list.h" int git_merge__cleanup(git_repository *repo) { @@ -46,3 +48,197 @@ cleanup: return error; } +int git_merge_base_many(git_oid *out, git_repository *repo, const git_oid input_array[], size_t length) +{ + git_revwalk *walk; + git_vector list; + git_commit_list *result = NULL; + int error = -1; + unsigned int i; + git_commit_list_node *commit; + + assert(out && repo && input_array); + + if (length < 2) { + giterr_set(GITERR_INVALID, "At least two commits are required to find an ancestor. Provided 'length' was %u.", length); + return -1; + } + + if (git_vector_init(&list, length - 1, NULL) < 0) + return -1; + + if (git_revwalk_new(&walk, repo) < 0) + goto cleanup; + + for (i = 1; i < length; i++) { + commit = commit_lookup(walk, &input_array[i]); + if (commit == NULL) + goto cleanup; + + git_vector_insert(&list, commit); + } + + commit = commit_lookup(walk, &input_array[0]); + if (commit == NULL) + goto cleanup; + + if (git_merge__bases_many(&result, walk, commit, &list) < 0) + goto cleanup; + + if (!result) { + error = GIT_ENOTFOUND; + goto cleanup; + } + + git_oid_cpy(out, &result->item->oid); + + error = 0; + +cleanup: + git_commit_list_free(&result); + git_revwalk_free(walk); + git_vector_free(&list); + return error; +} + +int git_merge_base(git_oid *out, git_repository *repo, const git_oid *one, const git_oid *two) +{ + git_revwalk *walk; + git_vector list; + git_commit_list *result = NULL; + git_commit_list_node *commit; + void *contents[1]; + + if (git_revwalk_new(&walk, repo) < 0) + return -1; + + commit = commit_lookup(walk, two); + if (commit == NULL) + goto on_error; + + /* This is just one value, so we can do it on the stack */ + memset(&list, 0x0, sizeof(git_vector)); + contents[0] = commit; + list.length = 1; + list.contents = contents; + + commit = commit_lookup(walk, one); + if (commit == NULL) + goto on_error; + + if (git_merge__bases_many(&result, walk, commit, &list) < 0) + goto on_error; + + if (!result) { + git_revwalk_free(walk); + giterr_clear(); + return GIT_ENOTFOUND; + } + + git_oid_cpy(out, &result->item->oid); + git_commit_list_free(&result); + git_revwalk_free(walk); + + return 0; + +on_error: + git_revwalk_free(walk); + return -1; +} + +static int interesting(git_pqueue *list) +{ + unsigned int i; + /* element 0 isn't used - we need to start at 1 */ + for (i = 1; i < list->size; i++) { + git_commit_list_node *commit = list->d[i]; + if ((commit->flags & STALE) == 0) + return 1; + } + + return 0; +} + +int git_merge__bases_many(git_commit_list **out, git_revwalk *walk, git_commit_list_node *one, git_vector *twos) +{ + int error; + unsigned int i; + git_commit_list_node *two; + git_commit_list *result = NULL, *tmp = NULL; + git_pqueue list; + + /* if the commit is repeated, we have a our merge base already */ + git_vector_foreach(twos, i, two) { + if (one == two) + return git_commit_list_insert(one, out) ? 0 : -1; + } + + if (git_pqueue_init(&list, twos->length * 2, git_commit_list_time_cmp) < 0) + return -1; + + if (git_commit_list_parse(walk, one) < 0) + return -1; + + one->flags |= PARENT1; + if (git_pqueue_insert(&list, one) < 0) + return -1; + + git_vector_foreach(twos, i, two) { + git_commit_list_parse(walk, two); + two->flags |= PARENT2; + if (git_pqueue_insert(&list, two) < 0) + return -1; + } + + /* as long as there are non-STALE commits */ + while (interesting(&list)) { + git_commit_list_node *commit; + int flags; + + commit = git_pqueue_pop(&list); + + flags = commit->flags & (PARENT1 | PARENT2 | STALE); + if (flags == (PARENT1 | PARENT2)) { + if (!(commit->flags & RESULT)) { + commit->flags |= RESULT; + if (git_commit_list_insert(commit, &result) == NULL) + return -1; + } + /* we mark the parents of a merge stale */ + flags |= STALE; + } + + for (i = 0; i < commit->out_degree; i++) { + git_commit_list_node *p = commit->parents[i]; + if ((p->flags & flags) == flags) + continue; + + if ((error = git_commit_list_parse(walk, p)) < 0) + return error; + + p->flags |= flags; + if (git_pqueue_insert(&list, p) < 0) + return -1; + } + } + + git_pqueue_free(&list); + + /* filter out any stale commits in the results */ + tmp = result; + result = NULL; + + while (tmp) { + struct git_commit_list *next = tmp->next; + if (!(tmp->item->flags & STALE)) + if (git_commit_list_insert_by_date(tmp->item, &result) == NULL) + return -1; + + git__free(tmp); + tmp = next; + } + + *out = result; + return 0; +} + |