[PATCH 5/7] merge-base: mark bases that are on first-parent chain
- From
Junio C Hamano <gitster@pobox.com>
- Date
- Oct 19, 2016, 04:23 UTC
- Message-ID
- <20161019042345.29766-6-gitster@pobox.com>
- In-Reply-To
- <20161019042345.29766-1-gitster@pobox.com>
In a workflow where topic branches are first merged to the 'next' integration branch to be tested before getting merged down to the 'master' integration branch to be consumed by the end users, merging the 'master' branch back to the 'next' happens after topics graduate to 'master' and release notes entries are written for them.
Git finds many merge bases between 'master' and 'next' while creating this merge. In addition to the tip of 'master' back when we made such a merge back from 'master' to 'next' was made the last time, which is the most reasonable merge base to explain the histories of both branches, all the tips of topic branches that graduated recently are merge bases. Because these tips of topic branches were already in 'next', the tip of 'next' reaches them, and because they just graduated to 'master', the tip of 'master' reaches them, too. And these topics are independent most of the time (that is the point of employing the topic-branch workflow), so they cannot be reduced.
The merge-recursive machinery is very inefficient to compute this merge, because it needs to create pointless virtual merge-base commits across these many merge bases. Conceptually, the point where the histories of 'master' and 'next' diverged was the tip of 'master' back when we created such a merge back from 'master' to 'next' the last time, and in practice that is the only merge base that matters.
Update the logic in paint_down_to_common() so that it can mark if a merge-base commit was reached by following the first-parent chain of either side of the merge to find such commit, and give an option to get_merge_bases_opt() to return only merge-base commits that are on the first-parent chain, so that a later step of this series can introduce a command line option to enable it and avoid feeding useless merge bases to the merge machinery.
Signed-off-by: Junio C Hamano <gitster@pobox.com> --- commit.c | 17 +++++++++++++++-- commit.h | 1 + object.h | 2 +- 3 files changed, 17 insertions(+), 3 deletions(-)
diff --git a/commit.c b/commit.c index 92d23b1082..8e90531b05 100644 --- a/commit.c +++ b/commit.c @@ -765,8 +765,9 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so #define PARENT2 (1u<<17) #define STALE (1u<<18) #define RESULT (1u<<19) +#define FPCHAIN (1u<<20) -static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT); +static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT | FPCHAIN); static int queue_has_nonstale(struct prio_queue *queue) { @@ -802,6 +803,7 @@ static struct commit_list *paint_down_to_common(struct commit *one, int n, struc struct commit *commit = prio_queue_get(&queue); struct commit_list *parents; int flags; + int nth_parent = 0; flags = commit->object.flags & (PARENT1 | PARENT2 | STALE); if (flags == (PARENT1 | PARENT2)) { @@ -816,11 +818,14 @@ static struct commit_list *paint_down_to_common(struct commit *one, int n, struc while (parents) { struct commit *p = parents->item; parents = parents->next; + nth_parent++; if ((p->object.flags & flags) == flags) continue; if (parse_commit(p)) return NULL; p->object.flags |= flags; + if (nth_parent == 1) + p->object.flags |= FPCHAIN; prio_queue_put(&queue, p); } } @@ -951,6 +956,8 @@ struct commit_list *get_merge_bases_opt(struct commit *one, struct commit_list *result; int cnt, i; int cleanup = !!(flags & MB_POSTCLEAN); + int fpchain = !!(flags & MB_FPCHAIN); + char *on_fpchain; result = merge_bases_many(one, n, twos); @@ -975,21 +982,27 @@ struct commit_list *get_merge_bases_opt(struct commit *one, /* There are more than one */ cnt = commit_list_count(result); rslt = xcalloc(cnt, sizeof(*rslt)); + on_fpchain = xcalloc(cnt, sizeof(*on_fpchain)); for (list = result, i = 0; list; list = list->next) rslt[i++] = list->item; free_commit_list(result); + for (i = 0; i < cnt; i++) + on_fpchain[i] = !!(rslt[i]->object.flags & FPCHAIN); + clear_commit_marks(one, all_flags); clear_commit_marks_many(n, twos, all_flags); mark_redundant(rslt, cnt); result = NULL; for (i = 0; i < cnt; i++) - if (!(rslt[i]->object.flags & STALE)) + if (!(rslt[i]->object.flags & STALE) && + (!fpchain || on_fpchain[i])) commit_list_insert_by_date(rslt[i], &result); else rslt[i]->object.flags &= ~STALE; free(rslt); + free(on_fpchain); return result; } diff --git a/commit.h b/commit.h index 557f2814b7..ec6e09a985 100644 --- a/commit.h +++ b/commit.h @@ -254,6 +254,7 @@ extern struct commit_list *get_merge_bases_many(struct commit *one, int n, struc extern struct commit_list *get_octopus_merge_bases(struct commit_list *in); #define MB_POSTCLEAN 01 +#define MB_FPCHAIN 02 extern struct commit_list *get_merge_bases_opt(struct commit *one, int n, struct commit **twos, unsigned flags); #define get_merge_bases_many_dirty(one, n, twos) get_merge_bases_opt((one),(n),(twos),MB_POSTCLEAN) diff --git a/object.h b/object.h index f8e218eccd..7e6729158a 100644 --- a/object.h +++ b/object.h @@ -36,7 +36,7 @@ struct object_array { * bisect.c: 16 * bundle.c: 16 * http-push.c: 16-----19 - * commit.c: 16-----19 + * commit.c: 16-------20 */ #define FLAG_BITS 27
-- 2.10.1-631-gb2c64dcf30