X-Git-Url: https://git.tokkee.org/?a=blobdiff_plain;f=merge-base.c;h=009caf804b43fdd644ff08991d55d0e417fd34d8;hb=e23ed9a8b4769fcba0944cf121d366ec7db7fe3b;hp=f0dc06ef5546b148fe20d3b1061c7eae0d262cce;hpb=efca578eec57869994da0982e05dcf1dee0bc213;p=git.git diff --git a/merge-base.c b/merge-base.c index f0dc06ef5..009caf804 100644 --- a/merge-base.c +++ b/merge-base.c @@ -2,229 +2,22 @@ #include "cache.h" #include "commit.h" -#define PARENT1 1 -#define PARENT2 2 -#define UNINTERESTING 4 - -static struct commit *interesting(struct commit_list *list) -{ - while (list) { - struct commit *commit = list->item; - list = list->next; - if (commit->object.flags & UNINTERESTING) - continue; - return commit; - } - return NULL; -} - -/* - * A pathological example of how this thing works. - * - * Suppose we had this commit graph, where chronologically - * the timestamp on the commit are A <= B <= C <= D <= E <= F - * and we are trying to figure out the merge base for E and F - * commits. - * - * F - * / \ - * E A D - * \ / / - * B / - * \ / - * C - * - * First we push E and F to list to be processed. E gets bit 1 - * and F gets bit 2. The list becomes: - * - * list=F(2) E(1), result=empty - * - * Then we pop F, the newest commit, from the list. Its flag is 2. - * We scan its parents, mark them reachable from the side that F is - * reachable from, and push them to the list: - * - * list=E(1) D(2) A(2), result=empty - * - * Next pop E and do the same. - * - * list=D(2) B(1) A(2), result=empty - * - * Next pop D and do the same. - * - * list=C(2) B(1) A(2), result=empty - * - * Next pop C and do the same. - * - * list=B(1) A(2), result=empty - * - * Now it is B's turn. We mark its parent, C, reachable from B's side, - * and push it to the list: - * - * list=C(3) A(2), result=empty - * - * Now pop C and notice it has flags==3. It is placed on the result list, - * and the list now contains: - * - * list=A(2), result=C(3) - * - * We pop A and do the same. - * - * list=B(3), result=C(3) - * - * Next, we pop B and something very interesting happens. It has flags==3 - * so it is also placed on the result list, and its parents are marked - * uninteresting, retroactively, and placed back on the list: - * - * list=C(7), result=C(7) B(3) - * - * Now, list does not have any interesting commit. So we find the newest - * commit from the result list that is not marked uninteresting. Which is - * commit B. - * - * - * Another pathological example how this thing can fail to mark an ancestor - * of a merge base as UNINTERESTING without the postprocessing phase. - * - * 2 - * H - * 1 / \ - * G A \ - * |\ / \ - * | B \ - * | \ \ - * \ C F - * \ \ / - * \ D / - * \ | / - * \| / - * E - * - * list A B C D E F G H - * G1 H2 - - - - - - 1 2 - * H2 E1 B1 - 1 - - 1 - 1 2 - * F2 E1 B1 A2 2 1 - - 1 2 1 2 - * E3 B1 A2 2 1 - - 3 2 1 2 - * B1 A2 2 1 - - 3 2 1 2 - * C1 A2 2 1 1 - 3 2 1 2 - * D1 A2 2 1 1 1 3 2 1 2 - * A2 2 1 1 1 3 2 1 2 - * B3 2 3 1 1 3 2 1 2 - * C7 2 3 7 1 3 2 1 2 - * - * At this point, unfortunately, everybody in the list is - * uninteresting, so we fail to complete the following two - * steps to fully marking uninteresting commits. - * - * D7 2 3 7 7 3 2 1 2 - * E7 2 3 7 7 7 2 1 2 - * - * and we end up showing E as an interesting merge base. - */ - -static int show_all = 0; - -static void mark_reachable_commits(struct commit_list *result, - struct commit_list *list) -{ - struct commit_list *tmp; - - /* - * Postprocess to fully contaminate the well. - */ - for (tmp = result; tmp; tmp = tmp->next) { - struct commit *c = tmp->item; - /* Reinject uninteresting ones to list, - * so we can scan their parents. - */ - if (c->object.flags & UNINTERESTING) - commit_list_insert(c, &list); - } - while (list) { - struct commit *c = list->item; - struct commit_list *parents; - - tmp = list; - list = list->next; - free(tmp); - - /* Anything taken out of the list is uninteresting, so - * mark all its parents uninteresting. We do not - * parse new ones (we already parsed all the relevant - * ones). - */ - parents = c->parents; - while (parents) { - struct commit *p = parents->item; - parents = parents->next; - if (!(p->object.flags & UNINTERESTING)) { - p->object.flags |= UNINTERESTING; - commit_list_insert(p, &list); - } - } - } -} +static int show_all; static int merge_base(struct commit *rev1, struct commit *rev2) { - struct commit_list *list = NULL; - struct commit_list *result = NULL; - struct commit_list *tmp = NULL; - - if (rev1 == rev2) { - printf("%s\n", sha1_to_hex(rev1->object.sha1)); - return 0; - } - - parse_commit(rev1); - parse_commit(rev2); - - rev1->object.flags |= 1; - rev2->object.flags |= 2; - insert_by_date(rev1, &list); - insert_by_date(rev2, &list); - - while (interesting(list)) { - struct commit *commit = list->item; - struct commit_list *parents; - int flags = commit->object.flags & 7; - - tmp = list; - list = list->next; - free(tmp); - if (flags == 3) { - insert_by_date(commit, &result); - - /* Mark parents of a found merge uninteresting */ - flags |= UNINTERESTING; - } - parents = commit->parents; - while (parents) { - struct commit *p = parents->item; - parents = parents->next; - if ((p->object.flags & flags) == flags) - continue; - parse_commit(p); - p->object.flags |= flags; - insert_by_date(p, &list); - } - } + struct commit_list *result = get_merge_bases(rev1, rev2, 0); if (!result) return 1; - if (result->next && list) - mark_reachable_commits(result, list); - while (result) { - struct commit *commit = result->item; - result = result->next; - if (commit->object.flags & UNINTERESTING) - continue; - printf("%s\n", sha1_to_hex(commit->object.sha1)); + printf("%s\n", sha1_to_hex(result->item->object.sha1)); if (!show_all) return 0; - commit->object.flags |= UNINTERESTING; + result = result->next; } + return 0; }