From 52cab8a0848463d793a3fc819b6d604ffc077ac1 Mon Sep 17 00:00:00 2001 From: Johannes Schindelin Date: Thu, 29 Jun 2006 15:16:46 +0200 Subject: refactor merge_bases() as preparation to libify merge-base Signed-off-by: Junio C Hamano diff --git a/merge-base.c b/merge-base.c index 4856ca0..7d87c20 100644 --- a/merge-base.c +++ b/merge-base.c @@ -124,8 +124,6 @@ static struct commit *interesting(struct commit_list *list) * to contaminate D and E. */ -static int show_all = 0; - static void mark_reachable_commits(struct commit_list *result, struct commit_list *list) { @@ -167,34 +165,33 @@ static void mark_reachable_commits(struct commit_list *result, } } -static int merge_base(struct commit *rev1, struct commit *rev2) +struct commit_list *get_merge_bases(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; - } + if (rev1 == rev2) + return commit_list_insert(rev1, &result); parse_commit(rev1); parse_commit(rev2); - rev1->object.flags |= 1; - rev2->object.flags |= 2; + 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 & 7; + int flags = commit->object.flags + & (PARENT1 | PARENT2 | UNINTERESTING); tmp = list; list = list->next; free(tmp); - if (flags == 3) { + if (flags == (PARENT1 | PARENT2)) { insert_by_date(commit, &result); /* Mark parents of a found merge uninteresting */ @@ -213,21 +210,52 @@ static int merge_base(struct commit *rev1, struct commit *rev2) } if (!result) - return 1; + return NULL; 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 & UNINTERESTING) { + if (list != NULL) + list->next = next; + free(tmp); + } else { + if (list == NULL) + result = tmp; + list = tmp; + commit->object.flags |= UNINTERESTING; + } + + tmp = next; + } + + /* reset flags */ + clear_commit_marks(rev1, PARENT1 | PARENT2 | UNINTERESTING); + clear_commit_marks(rev2, PARENT1 | PARENT2 | UNINTERESTING); + + return result; +} + +static int show_all = 0; + +static int merge_base(struct commit *rev1, struct commit *rev2) +{ + struct commit_list *result = get_merge_bases(rev1, rev2); + + if (!result) + return 1; + 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; } -- cgit v0.10.2-6-g49f6 From 7c6f8aaf6d795f0c9a75671acceb9754ea06fd81 Mon Sep 17 00:00:00 2001 From: Johannes Schindelin Date: Thu, 29 Jun 2006 15:17:32 +0200 Subject: move get_merge_bases() to core lib. Signed-off-by: Junio C Hamano diff --git a/commit.c b/commit.c index e51ffa1..0431027 100644 --- a/commit.c +++ b/commit.c @@ -846,3 +846,243 @@ void sort_in_topological_order_fn(struct commit_list ** list, int lifo, } free(nodes); } + +/* merge-rebase stuff */ + +#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 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); + } + } + } +} + +struct commit_list *get_merge_bases(struct commit *rev1, struct commit *rev2) +{ + 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 | UNINTERESTING); + + tmp = list; + list = list->next; + free(tmp); + if (flags == (PARENT1 | PARENT2)) { + 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); + } + } + + if (!result) + return NULL; + + 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 & UNINTERESTING) { + if (list != NULL) + list->next = next; + free(tmp); + } else { + if (list == NULL) + result = tmp; + list = tmp; + commit->object.flags |= UNINTERESTING; + } + + tmp = next; + } + + /* reset flags */ + clear_commit_marks(rev1, PARENT1 | PARENT2 | UNINTERESTING); + clear_commit_marks(rev2, PARENT1 | PARENT2 | UNINTERESTING); + + return result; +} diff --git a/commit.h b/commit.h index 7c9ca3f..89b9dad 100644 --- a/commit.h +++ b/commit.h @@ -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); + #endif /* COMMIT_H */ diff --git a/merge-base.c b/merge-base.c index 7d87c20..b41f76c 100644 --- a/merge-base.c +++ b/merge-base.c @@ -2,244 +2,6 @@ #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 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); - } - } - } -} - -struct commit_list *get_merge_bases(struct commit *rev1, struct commit *rev2) -{ - 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 | UNINTERESTING); - - tmp = list; - list = list->next; - free(tmp); - if (flags == (PARENT1 | PARENT2)) { - 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); - } - } - - if (!result) - return NULL; - - 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 & UNINTERESTING) { - if (list != NULL) - list->next = next; - free(tmp); - } else { - if (list == NULL) - result = tmp; - list = tmp; - commit->object.flags |= UNINTERESTING; - } - - tmp = next; - } - - /* reset flags */ - clear_commit_marks(rev1, PARENT1 | PARENT2 | UNINTERESTING); - clear_commit_marks(rev2, PARENT1 | PARENT2 | UNINTERESTING); - - return result; -} - static int show_all = 0; static int merge_base(struct commit *rev1, struct commit *rev2) -- cgit v0.10.2-6-g49f6 From 31609c17251f368584f7b94d44b06194112b4251 Mon Sep 17 00:00:00 2001 From: Rene Scharfe Date: Sun, 2 Jul 2006 01:29:26 +0200 Subject: Add get_merge_bases_clean() Add get_merge_bases_clean(), a wrapper for get_merge_bases() that cleans up after doing its work and make get_merge_bases() NOT clean up. Single-shot programs like git-merge-base can use the dirty and fast version. Also move the object flags used in get_merge_bases() out of the range defined in revision.h. This fixes the "66ae0c77...ced9456a 89719209...262a6ef7" test of the ... operator which is introduced with the next patch. Signed-off-by: Rene Scharfe Signed-off-by: Junio C Hamano diff --git a/commit.c b/commit.c index 0431027..593414d 100644 --- a/commit.c +++ b/commit.c @@ -849,9 +849,10 @@ void sort_in_topological_order_fn(struct commit_list ** list, int lifo, /* merge-rebase stuff */ -#define PARENT1 1 -#define PARENT2 2 -#define UNINTERESTING 4 +/* bits #0..7 in revision.h */ +#define PARENT1 (1u<< 8) +#define PARENT2 (1u<< 9) +#define UNINTERESTING (1u<<10) static struct commit *interesting(struct commit_list *list) { @@ -1080,9 +1081,20 @@ struct commit_list *get_merge_bases(struct commit *rev1, struct commit *rev2) tmp = next; } - /* reset flags */ + return result; +} + +struct commit_list *get_merge_bases_clean(struct commit *rev1, + struct commit *rev2) +{ + unsigned int flags1 = rev1->object.flags; + unsigned int flags2 = rev2->object.flags; + struct commit_list *result = get_merge_bases(rev1, rev2); + clear_commit_marks(rev1, PARENT1 | PARENT2 | UNINTERESTING); clear_commit_marks(rev2, PARENT1 | PARENT2 | UNINTERESTING); + rev1->object.flags = flags1; + rev2->object.flags = flags2; return result; } diff --git a/commit.h b/commit.h index 89b9dad..3a26e29 100644 --- a/commit.h +++ b/commit.h @@ -106,5 +106,6 @@ 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); +extern struct commit_list *get_merge_bases_clean(struct commit *rev1, struct commit *rev2); #endif /* COMMIT_H */ -- cgit v0.10.2-6-g49f6 From 0d2c9d67d9e1a2fd87b2daeefffffaff0b3f3a49 Mon Sep 17 00:00:00 2001 From: Rene Scharfe Date: Sun, 2 Jul 2006 01:29:37 +0200 Subject: Add '...' operator for revisions 'A...B' is a shortcut for 'A B --not $(git-merge-base --all A B)'. This XOR-like operation is called symmetric difference in set theory. The symbol '...' has been chosen because it's rather similar to the existing '..' operator and the somewhat more natural caret ('^') is already taken. Signed-off-by: Rene Scharfe Signed-off-by: Junio C Hamano diff --git a/Documentation/git-rev-list.txt b/Documentation/git-rev-list.txt index ad6d14c..6c370e1 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 .. can be used as a short-hand for {caret} . +Another special notation is ... 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 . diff --git a/revision.c b/revision.c index b963f2a..9eb0b6d 100644 --- a/revision.c +++ b/revision.c @@ -536,6 +536,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. @@ -771,27 +783,45 @@ 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_clean(a, b); + add_pending_commit_list(revs, exclude, + flags_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 = '.'; -- cgit v0.10.2-6-g49f6 From 31aea7ef77aff64a02afe1ea5f10375565911808 Mon Sep 17 00:00:00 2001 From: Rene Scharfe Date: Sun, 2 Jul 2006 01:29:58 +0200 Subject: Make clear_commit_marks() clean harder Don't care if objects have been parsed or not and don't stop when we reach a commit that is already clean -- its parents could be dirty. Signed-off-by: Rene Scharfe Signed-off-by: Junio C Hamano diff --git a/commit.c b/commit.c index 593414d..70a4eff 100644 --- a/commit.c +++ b/commit.c @@ -397,13 +397,12 @@ void clear_commit_marks(struct commit *commit, unsigned int mark) { struct commit_list *parents; + if (!commit) + return; parents = commit->parents; commit->object.flags &= ~mark; while (parents) { - struct commit *parent = parents->item; - if (parent && parent->object.parsed && - (parent->object.flags & mark)) - clear_commit_marks(parent, mark); + clear_commit_marks(parents->item, mark); parents = parents->next; } } -- cgit v0.10.2-6-g49f6 From c0fa8255c652e148f0910425d2cc2b8029065008 Mon Sep 17 00:00:00 2001 From: Rene Scharfe Date: Sun, 2 Jul 2006 11:49:38 +0200 Subject: Fold get_merge_bases_clean() into get_merge_bases() Change get_merge_bases() to be able to clean up after itself if needed by adding a cleanup parameter. We don't need to save the flags and restore them afterwards anymore; that was a leftover from before the flags were moved out of the range used in revision.c. clear_commit_marks() sets them to zero, which is enough. Signed-off-by: Rene Scharfe Acked-by: Johannes Schindelin Signed-off-by: Junio C Hamano diff --git a/commit.c b/commit.c index 70a4eff..94c1d0e 100644 --- a/commit.c +++ b/commit.c @@ -1012,7 +1012,8 @@ static void mark_reachable_commits(struct commit_list *result, } } -struct commit_list *get_merge_bases(struct commit *rev1, struct commit *rev2) +struct commit_list *get_merge_bases(struct commit *rev1, struct commit *rev2, + int cleanup) { struct commit_list *list = NULL; struct commit_list *result = NULL; @@ -1080,20 +1081,10 @@ struct commit_list *get_merge_bases(struct commit *rev1, struct commit *rev2) tmp = next; } - return result; -} - -struct commit_list *get_merge_bases_clean(struct commit *rev1, - struct commit *rev2) -{ - unsigned int flags1 = rev1->object.flags; - unsigned int flags2 = rev2->object.flags; - struct commit_list *result = get_merge_bases(rev1, rev2); - - clear_commit_marks(rev1, PARENT1 | PARENT2 | UNINTERESTING); - clear_commit_marks(rev2, PARENT1 | PARENT2 | UNINTERESTING); - rev1->object.flags = flags1; - rev2->object.flags = flags2; + if (cleanup) { + clear_commit_marks(rev1, PARENT1 | PARENT2 | UNINTERESTING); + clear_commit_marks(rev2, PARENT1 | PARENT2 | UNINTERESTING); + } return result; } diff --git a/commit.h b/commit.h index 3a26e29..779ed82 100644 --- a/commit.h +++ b/commit.h @@ -105,7 +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); -extern struct commit_list *get_merge_bases_clean(struct commit *rev1, struct commit *rev2); +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 b41f76c..59f723f 100644 --- a/merge-base.c +++ b/merge-base.c @@ -6,7 +6,7 @@ static int show_all = 0; static int merge_base(struct commit *rev1, struct commit *rev2) { - struct commit_list *result = get_merge_bases(rev1, rev2); + struct commit_list *result = get_merge_bases(rev1, rev2, 0); if (!result) return 1; diff --git a/revision.c b/revision.c index 9eb0b6d..27fc1e3 100644 --- a/revision.c +++ b/revision.c @@ -813,7 +813,7 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch } if (symmetric) { - exclude = get_merge_bases_clean(a, b); + exclude = get_merge_bases(a, b, 1); add_pending_commit_list(revs, exclude, flags_exclude); a->object.flags |= flags; -- cgit v0.10.2-6-g49f6 From 542ccefe896a8960a6ce0b0ba4519537649ae29a Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Sun, 2 Jul 2006 11:34:17 -0700 Subject: commit.c: do not redefine UNINTERESTING bit. Signed-off-by: Junio C Hamano diff --git a/commit.c b/commit.c index 94c1d0e..a608faf 100644 --- a/commit.c +++ b/commit.c @@ -851,14 +851,14 @@ void sort_in_topological_order_fn(struct commit_list ** list, int lifo, /* bits #0..7 in revision.h */ #define PARENT1 (1u<< 8) #define PARENT2 (1u<< 9) -#define UNINTERESTING (1u<<10) +#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 & UNINTERESTING) + if (commit->object.flags & STALE) continue; return commit; } @@ -920,17 +920,17 @@ static struct commit *interesting(struct commit_list *list) * * 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: + * 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 uninteresting. Which is + * 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 UNINTERESTING before we introduced the + * ancestor of a merge base as STALE before we introduced the * postprocessing phase (mark_reachable_commits). * * 2 @@ -960,8 +960,8 @@ static struct commit *interesting(struct commit_list *list) * 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. + * 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 @@ -981,10 +981,10 @@ static void mark_reachable_commits(struct commit_list *result, */ for (tmp = result; tmp; tmp = tmp->next) { struct commit *c = tmp->item; - /* Reinject uninteresting ones to list, + /* Reinject stale ones to list, * so we can scan their parents. */ - if (c->object.flags & UNINTERESTING) + if (c->object.flags & STALE) commit_list_insert(c, &list); } while (list) { @@ -995,8 +995,8 @@ static void mark_reachable_commits(struct commit_list *result, list = list->next; free(tmp); - /* Anything taken out of the list is uninteresting, so - * mark all its parents uninteresting. We do not + /* 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). */ @@ -1004,8 +1004,8 @@ static void mark_reachable_commits(struct commit_list *result, while (parents) { struct commit *p = parents->item; parents = parents->next; - if (!(p->object.flags & UNINTERESTING)) { - p->object.flags |= UNINTERESTING; + if (!(p->object.flags & STALE)) { + p->object.flags |= STALE; commit_list_insert(p, &list); } } @@ -1034,7 +1034,7 @@ struct commit_list *get_merge_bases(struct commit *rev1, struct commit *rev2, struct commit *commit = list->item; struct commit_list *parents; int flags = commit->object.flags - & (PARENT1 | PARENT2 | UNINTERESTING); + & (PARENT1 | PARENT2 | STALE); tmp = list; list = list->next; @@ -1042,8 +1042,8 @@ struct commit_list *get_merge_bases(struct commit *rev1, struct commit *rev2, if (flags == (PARENT1 | PARENT2)) { insert_by_date(commit, &result); - /* Mark parents of a found merge uninteresting */ - flags |= UNINTERESTING; + /* Mark parents of a found merge stale */ + flags |= STALE; } parents = commit->parents; while (parents) { @@ -1067,7 +1067,7 @@ struct commit_list *get_merge_bases(struct commit *rev1, struct commit *rev2, for (tmp = result, list = NULL; tmp; ) { struct commit *commit = tmp->item; struct commit_list *next = tmp->next; - if (commit->object.flags & UNINTERESTING) { + if (commit->object.flags & STALE) { if (list != NULL) list->next = next; free(tmp); @@ -1075,15 +1075,15 @@ struct commit_list *get_merge_bases(struct commit *rev1, struct commit *rev2, if (list == NULL) result = tmp; list = tmp; - commit->object.flags |= UNINTERESTING; + commit->object.flags |= STALE; } tmp = next; } if (cleanup) { - clear_commit_marks(rev1, PARENT1 | PARENT2 | UNINTERESTING); - clear_commit_marks(rev2, PARENT1 | PARENT2 | UNINTERESTING); + clear_commit_marks(rev1, PARENT1 | PARENT2 | STALE); + clear_commit_marks(rev2, PARENT1 | PARENT2 | STALE); } return result; -- cgit v0.10.2-6-g49f6 From 2ef108013ec15e8d5feee6d5c42692ae956ee302 Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Mon, 3 Jul 2006 03:02:27 -0700 Subject: get_merge_bases: clean up even when there is no common commit. Actually in this case we would have traversed a lot of commits, so cleaning things up is even more important. Signed-off-by: Junio C Hamano diff --git a/commit.c b/commit.c index a608faf..12882fd 100644 --- a/commit.c +++ b/commit.c @@ -1058,7 +1058,7 @@ struct commit_list *get_merge_bases(struct commit *rev1, struct commit *rev2, } if (!result) - return NULL; + goto finish; if (result->next && list) mark_reachable_commits(result, list); @@ -1081,6 +1081,7 @@ struct commit_list *get_merge_bases(struct commit *rev1, struct commit *rev2, tmp = next; } + finish: if (cleanup) { clear_commit_marks(rev1, PARENT1 | PARENT2 | STALE); clear_commit_marks(rev2, PARENT1 | PARENT2 | STALE); -- cgit v0.10.2-6-g49f6 From 160b7983034cdd24ea1bf6ef7a2532a2296461c6 Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Mon, 3 Jul 2006 03:05:20 -0700 Subject: revert clear-commit-marks for now. Earlier change broke "git describe A B" among other things. Revert it for now, and clean the commits smudged by get_merge_bases using clear_object_marks() function. For complex commit ancestry graph, this is way cheaper as well. Signed-off-by: Junio C Hamano diff --git a/commit.c b/commit.c index 12882fd..0439064 100644 --- a/commit.c +++ b/commit.c @@ -397,12 +397,13 @@ void clear_commit_marks(struct commit *commit, unsigned int mark) { struct commit_list *parents; - if (!commit) - return; parents = commit->parents; commit->object.flags &= ~mark; while (parents) { - clear_commit_marks(parents->item, mark); + struct commit *parent = parents->item; + if (parent && parent->object.parsed && + (parent->object.flags & mark)) + clear_commit_marks(parent, mark); parents = parents->next; } } @@ -1082,10 +1083,8 @@ struct commit_list *get_merge_bases(struct commit *rev1, struct commit *rev2, } finish: - if (cleanup) { - clear_commit_marks(rev1, PARENT1 | PARENT2 | STALE); - clear_commit_marks(rev2, PARENT1 | PARENT2 | STALE); - } + if (cleanup) + clear_object_marks(PARENT1 | PARENT2 | STALE); return result; } diff --git a/object.c b/object.c index 37784ce..9caba4f 100644 --- a/object.c +++ b/object.c @@ -217,3 +217,12 @@ void add_object_array(struct object *obj, const char *name, struct object_array objects[nr].name = name; array->nr = ++nr; } + +void clear_object_marks(unsigned mark) +{ + int i; + + for (i = 0; i < obj_allocs; i++) + if (objs[i]) + objs[i]->flags &= ~mark; +} diff --git a/object.h b/object.h index 6f23a9a..7ac1011 100644 --- a/object.h +++ b/object.h @@ -83,4 +83,6 @@ int object_list_contains(struct object_list *list, struct object *obj); /* Object array handling .. */ void add_object_array(struct object *obj, const char *name, struct object_array *array); +void clear_object_marks(unsigned); + #endif /* OBJECT_H */ -- cgit v0.10.2-6-g49f6 From 3dd4e7320de037a5b0adf3c53fbf5baf94a6c540 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Santi=20B=C3=A9jar?= Date: Tue, 4 Jul 2006 11:02:22 +0200 Subject: Teach rev-parse the ... syntax. MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit [jc: moved the difference code around into its own function.] Signed-off-by: Santi Béjar Signed-off-by: Junio C Hamano diff --git a/builtin-rev-parse.c b/builtin-rev-parse.c index 5f5ade4..4377d35 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(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; -- cgit v0.10.2-6-g49f6 From 4205eca8de6163385eb1b6eb6577ef7acfe116e7 Mon Sep 17 00:00:00 2001 From: Rene Scharfe Date: Tue, 4 Jul 2006 21:22:20 +0200 Subject: rev-list: free commit_list in ... handler Johannes noticed the missing call to free_commit_list() in the patch from Santi to add ... support to rev-parse. Turns out I forgot it too in rev-list. This patch is against the next branch (3b1d06a). Signed-off-by: Rene Scharfe Signed-off-by: Junio C Hamano diff --git a/revision.c b/revision.c index 56bc4ff..b4157cb 100644 --- a/revision.c +++ b/revision.c @@ -817,6 +817,7 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch 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; -- cgit v0.10.2-6-g49f6 From 58ecf5c1cd9b2f712f85e23f065d3214cd867a71 Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Tue, 4 Jul 2006 17:45:22 -0700 Subject: Re-fix clear_commit_marks(). Fix clear_commit_marks() enough to be usable in get_merge_bases(), and retire now unused clear_object_marks(). Signed-off-by: Junio C Hamano diff --git a/commit.c b/commit.c index 0439064..c6bf10d 100644 --- a/commit.c +++ b/commit.c @@ -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; } @@ -1083,8 +1084,10 @@ struct commit_list *get_merge_bases(struct commit *rev1, struct commit *rev2, } finish: - if (cleanup) - clear_object_marks(PARENT1 | PARENT2 | STALE); + if (cleanup) { + clear_commit_marks(rev1, PARENT1 | PARENT2 | STALE); + clear_commit_marks(rev2, PARENT1 | PARENT2 | STALE); + } return result; } diff --git a/object.c b/object.c index 1c36759..37277f9 100644 --- a/object.c +++ b/object.c @@ -235,12 +235,3 @@ void add_object_array(struct object *obj, const char *name, struct object_array objects[nr].name = name; array->nr = ++nr; } - -void clear_object_marks(unsigned mark) -{ - int i; - - for (i = 0; i < obj_hash_size; i++) - if (obj_hash[i]) - obj_hash[i]->flags &= ~mark; -} diff --git a/object.h b/object.h index d8a76ea..e0125e1 100644 --- a/object.h +++ b/object.h @@ -84,6 +84,4 @@ int object_list_contains(struct object_list *list, struct object *obj); /* Object array handling .. */ void add_object_array(struct object *obj, const char *name, struct object_array *array); -void clear_object_marks(unsigned); - #endif /* OBJECT_H */ -- cgit v0.10.2-6-g49f6 From b7d936b2fd917bef7acf0edb086de5902449b780 Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Thu, 6 Jul 2006 00:16:35 -0700 Subject: builtin-rev-parse.c: constness tightening Signed-off-by: Junio C Hamano diff --git a/builtin-rev-parse.c b/builtin-rev-parse.c index 4377d35..b3e4386 100644 --- a/builtin-rev-parse.c +++ b/builtin-rev-parse.c @@ -164,7 +164,7 @@ static int show_file(const char *arg) return 0; } -static int try_difference(char *arg) +static int try_difference(const char *arg) { char *dotdot; unsigned char sha1[20]; -- cgit v0.10.2-6-g49f6