diff options
| -rw-r--r-- | merge-base.c | 74 |
1 files changed, 68 insertions, 6 deletions
diff --git a/merge-base.c b/merge-base.c index 18d81d08a5..923256c821 100644 --- a/merge-base.c +++ b/merge-base.c @@ -6,18 +6,82 @@ #define PARENT2 2 #define UNINTERESTING 4 -static int interesting(struct commit_list *list) +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 1; + return commit; } - return 0; + 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. + */ + static struct commit *common_ancestor(struct commit *rev1, struct commit *rev2) { struct commit_list *list = NULL; @@ -58,9 +122,7 @@ static struct commit *common_ancestor(struct commit *rev1, struct commit *rev2) insert_by_date(p, &list); } } - if (!result) - return NULL; - return result->item; + return interesting(result); } int main(int argc, char **argv) |