diff options
author | Vicent Marti <tanoku@gmail.com> | 2015-10-30 11:45:52 +0100 |
---|---|---|
committer | Vicent Marti <tanoku@gmail.com> | 2015-11-02 13:47:04 +0100 |
commit | 136a71f4eee60052cd1b55ba7c9b600871baf6d4 (patch) | |
tree | e6cea3d77826d2970720e3bffffe104ea22b348c | |
parent | d571a54e603c9bf46c7836124fded8c160b1eb5a (diff) | |
download | libgit2-136a71f4eee60052cd1b55ba7c9b600871baf6d4.tar.gz |
merge-base: Remove redundant merge bases
-rw-r--r-- | src/commit_list.h | 1 | ||||
-rw-r--r-- | src/merge.c | 187 |
2 files changed, 166 insertions, 22 deletions
diff --git a/src/commit_list.h b/src/commit_list.h index b1d88e016..a6967bcef 100644 --- a/src/commit_list.h +++ b/src/commit_list.h @@ -13,6 +13,7 @@ #define PARENT2 (1 << 1) #define RESULT (1 << 2) #define STALE (1 << 3) +#define ALL_FLAGS (PARENT1 | PARENT2 | STALE | RESULT) #define PARENTS_PER_COMMIT 2 #define COMMIT_ALLOC \ diff --git a/src/merge.c b/src/merge.c index ac0caeabd..0c132c4a3 100644 --- a/src/merge.c +++ b/src/merge.c @@ -302,30 +302,59 @@ static int interesting(git_pqueue *list) return 0; } -int git_merge__bases_many(git_commit_list **out, git_revwalk *walk, git_commit_list_node *one, git_vector *twos) +static void clear_commit_marks_1(git_commit_list **plist, + git_commit_list_node *commit, unsigned int mark) { - int error; - unsigned int i; - git_commit_list_node *two; - git_commit_list *result = NULL, *tmp = NULL; - git_pqueue list; + while (commit) { + unsigned int i; - /* If there's only the one commit, there can be no merge bases */ - if (twos->length == 0) { - *out = NULL; - return 0; + if (!(mark & commit->flags)) + return; + + commit->flags &= ~mark; + + for (i = 1; i < commit->out_degree; i++) { + git_commit_list_node *p = commit->parents[i]; + git_commit_list_insert(p, plist); + } + + commit = commit->parents[0]; } +} - /* 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; +static void clear_commit_marks_many(git_vector *commits, unsigned int mark) +{ + git_commit_list *list = NULL; + git_commit_list_node *c; + unsigned int i; + + git_vector_foreach(commits, i, c) { + git_commit_list_insert(c, &list); } - if (git_pqueue_init(&list, 0, twos->length * 2, git_commit_list_time_cmp) < 0) - return -1; + while (list) + clear_commit_marks_1(&list, git_commit_list_pop(&list), mark); +} - if (git_commit_list_parse(walk, one) < 0) +static void clear_commit_marks(git_commit_list_node *commit, unsigned int mark) +{ + git_commit_list *list = NULL; + git_commit_list_insert(commit, &list); + while (list) + clear_commit_marks_1(&list, git_commit_list_pop(&list), mark); +} + +static int paint_down_to_common( + git_commit_list **out, git_revwalk *walk, git_commit_list_node *one, git_vector *twos) +{ + git_pqueue list; + git_commit_list *result = NULL; + git_commit_list_node *two; + + int error; + unsigned int i; + + if (git_pqueue_init(&list, 0, twos->length * 2, git_commit_list_time_cmp) < 0) return -1; one->flags |= PARENT1; @@ -376,19 +405,133 @@ int git_merge__bases_many(git_commit_list **out, git_revwalk *walk, git_commit_l } git_pqueue_free(&list); + *out = result; + return 0; +} + +static int remove_redundant(git_revwalk *walk, git_vector *commits) +{ + git_vector work = GIT_VECTOR_INIT; + unsigned char *redundant; + unsigned int *filled_index; + unsigned int i, j; + int error = 0; + + redundant = git__calloc(commits->length, 1); + filled_index = git__calloc((commits->length - 1), sizeof(unsigned int)); + + for (i = 0; i < commits->length; ++i) { + if ((error = git_commit_list_parse(walk, commits->contents[i])) < 0) + goto done; + } + + for (i = 0; i < commits->length; ++i) { + git_commit_list *common = NULL; + git_commit_list_node *commit = commits->contents[i]; + + if (redundant[i]) + continue; + + git_vector_clear(&work); + + for (j = 0; j < commits->length; j++) { + if (i == j || redundant[j]) + continue; + + filled_index[work.length] = j; + if ((error = git_vector_insert(&work, commits->contents[j])) < 0) + goto done; + } + + error = paint_down_to_common(&common, walk, commit, &work); + if (error < 0) + goto done; + + if (commit->flags & PARENT2) + redundant[i] = 1; + + for (j = 0; j < work.length; j++) { + git_commit_list_node *w = work.contents[j]; + if (w->flags & PARENT1) + redundant[filled_index[j]] = 1; + } + + clear_commit_marks(commit, ALL_FLAGS); + clear_commit_marks_many(&work, ALL_FLAGS); + + git_commit_list_free(&common); + } + + for (i = 0; i < commits->length; ++i) { + if (redundant[i]) + commits->contents[i] = NULL; + } + +done: + git__free(redundant); + git__free(filled_index); + git_vector_free(&work); + return error; +} + +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; + + /* If there's only the one commit, there can be no merge bases */ + if (twos->length == 0) { + *out = NULL; + return 0; + } + + /* 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_commit_list_parse(walk, one) < 0) + return -1; + + error = paint_down_to_common(&result, walk, one, twos); + if (error < 0) + return error; /* 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) + git_commit_list_node *c = git_commit_list_pop(&tmp); + if (!(c->flags & STALE)) + if (git_commit_list_insert_by_date(c, &result) == NULL) return -1; + } + + /* more than one merge base -- remove redundants */ + if (result && result->next) { + git_vector redundant = GIT_VECTOR_INIT; + + while (result) + git_vector_insert(&redundant, git_commit_list_pop(&result)); + + clear_commit_marks(one, ALL_FLAGS); + clear_commit_marks_many(twos, ALL_FLAGS); + + if ((error = remove_redundant(walk, &redundant)) < 0) { + git_vector_free(&redundant); + return error; + } + + git_vector_foreach(&redundant, i, two) { + if (two != NULL) + git_commit_list_insert_by_date(two, &result); + } - git__free(tmp); - tmp = next; + git_vector_free(&redundant); } *out = result; |