diff options
| -rw-r--r-- | Documentation/git-rev-list.txt | 14 | ||||
| -rw-r--r-- | builtin-rev-parse.c | 65 | ||||
| -rw-r--r-- | commit.c | 251 | ||||
| -rw-r--r-- | commit.h | 2 | ||||
| -rw-r--r-- | merge-base.c | 218 | ||||
| -rw-r--r-- | revision.c | 49 |
6 files changed, 355 insertions, 244 deletions
diff --git a/Documentation/git-rev-list.txt b/Documentation/git-rev-list.txt index ad6d14c55a..6c370e1bef 100644 --- a/Documentation/git-rev-list.txt +++ b/Documentation/git-rev-list.txt @@ -15,6 +15,7 @@ SYNOPSIS [ \--sparse ] [ \--no-merges ] [ \--remove-empty ] + [ \--not ] [ \--all ] [ \--topo-order ] [ \--parents ] @@ -37,6 +38,14 @@ not in 'baz'". A special notation <commit1>..<commit2> can be used as a short-hand for {caret}<commit1> <commit2>. +Another special notation is <commit1>...<commit2> which is useful for +merges. The resulting set of commits is the symmetric difference +between the two operands. The following two commands are equivalent: + +------------ +$ git-rev-list A B --not $(git-merge-base --all A B) +$ git-rev-list A...B +------------ OPTIONS ------- @@ -93,6 +102,11 @@ OPTIONS --remove-empty:: Stop when a given path disappears from the tree. +--not:: + Reverses the meaning of the '{caret}' prefix (or lack + thereof) for all following revision specifiers, up to + the next `--not`. + --all:: Pretend as if all the refs in `$GIT_DIR/refs/` are listed on the command line as <commit>. diff --git a/builtin-rev-parse.c b/builtin-rev-parse.c index 5f5ade45ae..b3e4386c1b 100644 --- a/builtin-rev-parse.c +++ b/builtin-rev-parse.c @@ -164,6 +164,51 @@ static int show_file(const char *arg) return 0; } +static int try_difference(const char *arg) +{ + char *dotdot; + unsigned char sha1[20]; + unsigned char end[20]; + const char *next; + const char *this; + int symmetric; + + if (!(dotdot = strstr(arg, ".."))) + return 0; + next = dotdot + 2; + this = arg; + symmetric = (*next == '.'); + + *dotdot = 0; + next += symmetric; + + if (!*next) + next = "HEAD"; + if (dotdot == arg) + this = "HEAD"; + if (!get_sha1(this, sha1) && !get_sha1(next, end)) { + show_rev(NORMAL, end, next); + show_rev(symmetric ? NORMAL : REVERSED, sha1, this); + if (symmetric) { + struct commit_list *exclude; + struct commit *a, *b; + a = lookup_commit_reference(sha1); + b = lookup_commit_reference(end); + exclude = get_merge_bases(a, b, 1); + while (exclude) { + struct commit_list *n = exclude->next; + show_rev(REVERSED, + exclude->item->object.sha1,NULL); + free(exclude); + exclude = n; + } + } + return 1; + } + *dotdot = '.'; + return 0; +} + int cmd_rev_parse(int argc, const char **argv, char **envp) { int i, as_is = 0, verify = 0; @@ -174,7 +219,6 @@ int cmd_rev_parse(int argc, const char **argv, char **envp) for (i = 1; i < argc; i++) { const char *arg = argv[i]; - char *dotdot; if (as_is) { if (show_file(arg) && as_is < 2) @@ -326,23 +370,8 @@ int cmd_rev_parse(int argc, const char **argv, char **envp) } /* Not a flag argument */ - dotdot = strstr(arg, ".."); - if (dotdot) { - unsigned char end[20]; - const char *next = dotdot + 2; - const char *this = arg; - *dotdot = 0; - if (!*next) - next = "HEAD"; - if (dotdot == arg) - this = "HEAD"; - if (!get_sha1(this, sha1) && !get_sha1(next, end)) { - show_rev(NORMAL, end, next); - show_rev(REVERSED, sha1, this); - continue; - } - *dotdot = '.'; - } + if (try_difference(arg)) + continue; if (!get_sha1(arg, sha1)) { show_rev(NORMAL, sha1, arg); continue; @@ -397,12 +397,13 @@ void clear_commit_marks(struct commit *commit, unsigned int mark) { struct commit_list *parents; - parents = commit->parents; commit->object.flags &= ~mark; + parents = commit->parents; while (parents) { struct commit *parent = parents->item; - if (parent && parent->object.parsed && - (parent->object.flags & mark)) + + /* Have we already cleared this? */ + if (mark & parent->object.flags) clear_commit_marks(parent, mark); parents = parents->next; } @@ -846,3 +847,247 @@ void sort_in_topological_order_fn(struct commit_list ** list, int lifo, } free(nodes); } + +/* merge-rebase stuff */ + +/* bits #0..7 in revision.h */ +#define PARENT1 (1u<< 8) +#define PARENT2 (1u<< 9) +#define STALE (1u<<10) + +static struct commit *interesting(struct commit_list *list) +{ + while (list) { + struct commit *commit = list->item; + list = list->next; + if (commit->object.flags & STALE) + 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 + * stale, 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 stale. Which is + * commit B. + * + * + * Another pathological example how this thing used to fail to mark an + * ancestor of a merge base as STALE before we introduced the + * postprocessing phase (mark_reachable_commits). + * + * 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 + * stale, so we fail to complete the following two + * steps to fully marking stale commits. + * + * D7 2 3 7 7 3 2 1 2 + * E7 2 3 7 7 7 2 1 2 + * + * and we ended up showing E as an interesting merge base. + * The postprocessing phase re-injects C and continues traversal + * to contaminate D and E. + */ + +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 stale ones to list, + * so we can scan their parents. + */ + if (c->object.flags & STALE) + 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 stale, so + * mark all its parents stale. 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 & STALE)) { + p->object.flags |= STALE; + commit_list_insert(p, &list); + } + } + } +} + +struct commit_list *get_merge_bases(struct commit *rev1, struct commit *rev2, + int cleanup) +{ + struct commit_list *list = NULL; + struct commit_list *result = NULL; + struct commit_list *tmp = NULL; + + if (rev1 == rev2) + return commit_list_insert(rev1, &result); + + parse_commit(rev1); + parse_commit(rev2); + + rev1->object.flags |= PARENT1; + rev2->object.flags |= PARENT2; + 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 + & (PARENT1 | PARENT2 | STALE); + + tmp = list; + list = list->next; + free(tmp); + if (flags == (PARENT1 | PARENT2)) { + insert_by_date(commit, &result); + + /* Mark parents of a found merge stale */ + flags |= STALE; + } + 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); + } + } + + if (!result) + goto finish; + + if (result->next && list) + mark_reachable_commits(result, list); + + /* cull duplicates */ + for (tmp = result, list = NULL; tmp; ) { + struct commit *commit = tmp->item; + struct commit_list *next = tmp->next; + if (commit->object.flags & STALE) { + if (list != NULL) + list->next = next; + free(tmp); + } else { + if (list == NULL) + result = tmp; + list = tmp; + commit->object.flags |= STALE; + } + + tmp = next; + } + + finish: + if (cleanup) { + clear_commit_marks(rev1, PARENT1 | PARENT2 | STALE); + clear_commit_marks(rev2, PARENT1 | PARENT2 | STALE); + } + + return result; +} @@ -105,4 +105,6 @@ struct commit_graft *read_graft_line(char *buf, int len); int register_commit_graft(struct commit_graft *, int); int read_graft_file(const char *graft_file); +extern struct commit_list *get_merge_bases(struct commit *rev1, struct commit *rev2, int cleanup); + #endif /* COMMIT_H */ diff --git a/merge-base.c b/merge-base.c index 4856ca01c3..59f723f404 100644 --- a/merge-base.c +++ b/merge-base.c @@ -2,232 +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 used to fail to mark an - * ancestor of a merge base as UNINTERESTING before we introduced the - * postprocessing phase (mark_reachable_commits). - * - * 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 ended up showing E as an interesting merge base. - * The postprocessing phase re-injects C and continues traversal - * to contaminate D and E. - */ - 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 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; } diff --git a/revision.c b/revision.c index ab89c22417..a7750e626b 100644 --- a/revision.c +++ b/revision.c @@ -537,6 +537,18 @@ void init_revisions(struct rev_info *revs) diff_setup(&revs->diffopt); } +static void add_pending_commit_list(struct rev_info *revs, + struct commit_list *commit_list, + unsigned int flags) +{ + while (commit_list) { + struct object *object = &commit_list->item->object; + object->flags |= flags; + add_pending_object(revs, object, sha1_to_hex(object->sha1)); + commit_list = commit_list->next; + } +} + /* * Parse revision information, filling in the "rev_info" structure, * and removing the used arguments from the argument list. @@ -772,27 +784,46 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch unsigned char from_sha1[20]; const char *next = dotdot + 2; const char *this = arg; + int symmetric = *next == '.'; + unsigned int flags_exclude = flags ^ UNINTERESTING; + *dotdot = 0; + next += symmetric; + if (!*next) next = "HEAD"; if (dotdot == arg) this = "HEAD"; if (!get_sha1(this, from_sha1) && !get_sha1(next, sha1)) { - struct object *exclude; - struct object *include; - - exclude = get_reference(revs, this, from_sha1, flags ^ UNINTERESTING); - include = get_reference(revs, next, sha1, flags); - if (!exclude || !include) - die("Invalid revision range %s..%s", arg, next); + struct commit *a, *b; + struct commit_list *exclude; + + a = lookup_commit_reference(from_sha1); + b = lookup_commit_reference(sha1); + if (!a || !b) { + die(symmetric ? + "Invalid symmetric difference expression %s...%s" : + "Invalid revision range %s..%s", + arg, next); + } if (!seen_dashdash) { *dotdot = '.'; verify_non_filename(revs->prefix, arg); } - add_pending_object(revs, exclude, this); - add_pending_object(revs, include, next); + + if (symmetric) { + exclude = get_merge_bases(a, b, 1); + add_pending_commit_list(revs, exclude, + flags_exclude); + free_commit_list(exclude); + a->object.flags |= flags; + } else + a->object.flags |= flags_exclude; + b->object.flags |= flags; + add_pending_object(revs, &a->object, this); + add_pending_object(revs, &b->object, next); continue; } *dotdot = '.'; |