From 653194758ee338b7c87d011007c532ed5cf68d45 Mon Sep 17 00:00:00 2001 From: Miklos Vajna Date: Fri, 27 Jun 2008 18:21:55 +0200 Subject: Move commit_list_count() to commit.c This function is useful outside builtin-merge-recursive, for example in builtin-merge. Signed-off-by: Miklos Vajna Signed-off-by: Junio C Hamano --- commit.c | 8 ++++++++ 1 file changed, 8 insertions(+) (limited to 'commit.c') diff --git a/commit.c b/commit.c index e2d8624d9c..bbf9c75416 100644 --- a/commit.c +++ b/commit.c @@ -325,6 +325,14 @@ struct commit_list *commit_list_insert(struct commit *item, struct commit_list * return new_list; } +unsigned commit_list_count(const struct commit_list *l) +{ + unsigned c = 0; + for (; l; l = l->next ) + c++; + return c; +} + void free_commit_list(struct commit_list *list) { while (list) { -- cgit v1.2.3 From 5240c9d75d8e1b747da427ba6320432d3201168a Mon Sep 17 00:00:00 2001 From: Miklos Vajna Date: Fri, 27 Jun 2008 18:22:00 +0200 Subject: Introduce get_octopus_merge_bases() in commit.c This is like get_merge_bases() but it works for multiple heads, like show-branch --merge-base. Signed-off-by: Miklos Vajna Signed-off-by: Junio C Hamano --- commit.c | 27 +++++++++++++++++++++++++++ commit.h | 1 + 2 files changed, 28 insertions(+) (limited to 'commit.c') diff --git a/commit.c b/commit.c index bbf9c75416..6052ca34c8 100644 --- a/commit.c +++ b/commit.c @@ -600,6 +600,33 @@ static struct commit_list *merge_bases(struct commit *one, struct commit *two) return result; } +struct commit_list *get_octopus_merge_bases(struct commit_list *in) +{ + struct commit_list *i, *j, *k, *ret = NULL; + struct commit_list **pptr = &ret; + + for (i = in; i; i = i->next) { + if (!ret) + pptr = &commit_list_insert(i->item, pptr)->next; + else { + struct commit_list *new = NULL, *end = NULL; + + for (j = ret; j; j = j->next) { + struct commit_list *bases; + bases = get_merge_bases(i->item, j->item, 1); + if (!new) + new = bases; + else + end->next = bases; + for (k = bases; k; k = k->next) + end = k; + } + ret = new; + } + } + return ret; +} + struct commit_list *get_merge_bases(struct commit *one, struct commit *two, int cleanup) { diff --git a/commit.h b/commit.h index 7f8c5ee0fc..dcec7fb9a2 100644 --- a/commit.h +++ b/commit.h @@ -121,6 +121,7 @@ int read_graft_file(const char *graft_file); struct commit_graft *lookup_commit_graft(const unsigned char *sha1); extern struct commit_list *get_merge_bases(struct commit *rev1, struct commit *rev2, int cleanup); +extern struct commit_list *get_octopus_merge_bases(struct commit_list *in); extern int register_shallow(const unsigned char *sha1); extern int unregister_shallow(const unsigned char *sha1); -- cgit v1.2.3 From 6a938648e1454842157b84408acbb6471ec6745f Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Fri, 27 Jun 2008 18:22:02 +0200 Subject: Introduce get_merge_bases_many() This introduces a new function get_merge_bases_many() which is a natural extension of two commit merge base computation. It is given one commit (one) and a set of other commits (twos), and computes the merge base of one and a merge across other commits. This is mostly useful to figure out the common ancestor when iterating over heads during an octopus merge. When making an octopus between commits A, B, C and D, we first merge tree of A and B, and then try to merge C with it. If we were making pairwise merge, we would be recording the tree resulting from the merge between A and B as a commit, say M, and then the next round we will be computing the merge base between M and C. o---C...* / . o---B...M / . o---o---A But during an octopus merge, we actually do not create a commit M. In order to figure out that the common ancestor to use for this merge, instead of computing the merge base between C and M, we can call merge_bases_many() with one set to C and twos containing A and B. Signed-off-by: Junio C Hamano --- commit.c | 56 ++++++++++++++++++++++++++++++++++++++------------------ 1 file changed, 38 insertions(+), 18 deletions(-) (limited to 'commit.c') diff --git a/commit.c b/commit.c index 6052ca34c8..cafed26928 100644 --- a/commit.c +++ b/commit.c @@ -533,26 +533,34 @@ static struct commit *interesting(struct commit_list *list) return NULL; } -static struct commit_list *merge_bases(struct commit *one, struct commit *two) +static struct commit_list *merge_bases_many(struct commit *one, int n, struct commit **twos) { struct commit_list *list = NULL; struct commit_list *result = NULL; + int i; - if (one == two) - /* We do not mark this even with RESULT so we do not - * have to clean it up. - */ - return commit_list_insert(one, &result); + for (i = 0; i < n; i++) { + if (one == twos[i]) + /* + * We do not mark this even with RESULT so we do not + * have to clean it up. + */ + return commit_list_insert(one, &result); + } if (parse_commit(one)) return NULL; - if (parse_commit(two)) - return NULL; + for (i = 0; i < n; i++) { + if (parse_commit(twos[i])) + return NULL; + } one->object.flags |= PARENT1; - two->object.flags |= PARENT2; insert_by_date(one, &list); - insert_by_date(two, &list); + for (i = 0; i < n; i++) { + twos[i]->object.flags |= PARENT2; + insert_by_date(twos[i], &list); + } while (interesting(list)) { struct commit *commit; @@ -627,21 +635,26 @@ struct commit_list *get_octopus_merge_bases(struct commit_list *in) return ret; } -struct commit_list *get_merge_bases(struct commit *one, - struct commit *two, int cleanup) +struct commit_list *get_merge_bases_many(struct commit *one, + int n, + struct commit **twos, + int cleanup) { struct commit_list *list; struct commit **rslt; struct commit_list *result; int cnt, i, j; - result = merge_bases(one, two); - if (one == two) - return result; + result = merge_bases_many(one, n, twos); + for (i = 0; i < n; i++) { + if (one == twos[i]) + return result; + } if (!result || !result->next) { if (cleanup) { clear_commit_marks(one, all_flags); - clear_commit_marks(two, all_flags); + for (i = 0; i < n; i++) + clear_commit_marks(twos[i], all_flags); } return result; } @@ -659,12 +672,13 @@ struct commit_list *get_merge_bases(struct commit *one, free_commit_list(result); clear_commit_marks(one, all_flags); - clear_commit_marks(two, all_flags); + for (i = 0; i < n; i++) + clear_commit_marks(twos[i], all_flags); for (i = 0; i < cnt - 1; i++) { for (j = i+1; j < cnt; j++) { if (!rslt[i] || !rslt[j]) continue; - result = merge_bases(rslt[i], rslt[j]); + result = merge_bases_many(rslt[i], 1, &rslt[j]); clear_commit_marks(rslt[i], all_flags); clear_commit_marks(rslt[j], all_flags); for (list = result; list; list = list->next) { @@ -686,6 +700,12 @@ struct commit_list *get_merge_bases(struct commit *one, return result; } +struct commit_list *get_merge_bases(struct commit *one, struct commit *two, + int cleanup) +{ + return get_merge_bases_many(one, 1, &two, cleanup); +} + int in_merge_bases(struct commit *commit, struct commit **reference, int num) { struct commit_list *bases, *b; -- cgit v1.2.3 From 98cf9c3bd7504d36e6049939bf9cc624f2cf5b9f Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Fri, 27 Jun 2008 18:22:03 +0200 Subject: Introduce reduce_heads() The new function reduce_heads() is given a list of commits, and removes ones that can be reached from other commits in the list. It is useful for reducing the commits randomly thrown at the git-merge command and remove redundant commits that the user shouldn't have given to it. The implementation uses the get_merge_bases_many() introduced in the previous commit. If the merge base between one commit taken from the list and the remaining commits is the commit itself, that means the commit is reachable from some of the other commits. Signed-off-by: Junio C Hamano --- commit.c | 45 +++++++++++++++++++++++++++++++++++++++++++++ commit.h | 2 ++ 2 files changed, 47 insertions(+) (limited to 'commit.c') diff --git a/commit.c b/commit.c index cafed26928..d20b14ee3e 100644 --- a/commit.c +++ b/commit.c @@ -725,3 +725,48 @@ int in_merge_bases(struct commit *commit, struct commit **reference, int num) free_commit_list(bases); return ret; } + +struct commit_list *reduce_heads(struct commit_list *heads) +{ + struct commit_list *p; + struct commit_list *result = NULL, **tail = &result; + struct commit **other; + size_t num_head, num_other; + + if (!heads) + return NULL; + + /* Avoid unnecessary reallocations */ + for (p = heads, num_head = 0; p; p = p->next) + num_head++; + other = xcalloc(sizeof(*other), num_head); + + /* For each commit, see if it can be reached by others */ + for (p = heads; p; p = p->next) { + struct commit_list *q, *base; + + num_other = 0; + for (q = heads; q; q = q->next) { + if (p == q) + continue; + other[num_other++] = q->item; + } + if (num_other) { + base = get_merge_bases_many(p->item, num_other, other, 1); + } else + base = NULL; + /* + * If p->item does not have anything common with other + * commits, there won't be any merge base. If it is + * reachable from some of the others, p->item will be + * the merge base. If its history is connected with + * others, but p->item is not reachable by others, we + * will get something other than p->item back. + */ + if (!base || (base->item != p->item)) + tail = &(commit_list_insert(p->item, tail)->next); + free_commit_list(base); + } + free(other); + return result; +} diff --git a/commit.h b/commit.h index dcec7fb9a2..2acfc79d34 100644 --- a/commit.h +++ b/commit.h @@ -140,4 +140,6 @@ static inline int single_parent(struct commit *commit) return commit->parents && !commit->parents->next; } +struct commit_list *reduce_heads(struct commit_list *heads); + #endif /* COMMIT_H */ -- cgit v1.2.3 From 3d1dd4728b83e4c08d9fa7aaf2aa946e1012e061 Mon Sep 17 00:00:00 2001 From: Sverre Hvammen Johansen Date: Sun, 13 Jul 2008 08:13:55 +0000 Subject: reduce_heads(): thinkofix When comparing two commit objects for equality, it is sufficient to compare their in-core pointers because the object layer guarantees the uniqueness. However, comparing pointers to two "struct commit_list" instances that point at the same commit does not make any sense. Spotted by Sverre Hvammen Johansen who wrote an additional test to expose the problem, fixed by Miklos Vajna. Signed-off-by: Junio C Hamano --- commit.c | 2 +- t/t7600-merge.sh | 11 +++++++++++ 2 files changed, 12 insertions(+), 1 deletion(-) (limited to 'commit.c') diff --git a/commit.c b/commit.c index d20b14ee3e..03e73f323a 100644 --- a/commit.c +++ b/commit.c @@ -747,7 +747,7 @@ struct commit_list *reduce_heads(struct commit_list *heads) num_other = 0; for (q = heads; q; q = q->next) { - if (p == q) + if (p->item == q->item) continue; other[num_other++] = q->item; } diff --git a/t/t7600-merge.sh b/t/t7600-merge.sh index 72ef2e55d9..f035ea376e 100755 --- a/t/t7600-merge.sh +++ b/t/t7600-merge.sh @@ -479,4 +479,15 @@ test_expect_success 'merge log message' ' test_debug 'gitk --all' +test_expect_success 'merge c1 with c0, c2, c0, and c1' ' + git reset --hard c1 && + git config branch.master.mergeoptions "" && + test_tick && + git merge c0 c2 c0 c1 && + verify_merge file result.1-5 && + verify_parents $c1 $c2 +' + +test_debug 'gitk --all' + test_done -- cgit v1.2.3 From 711f6b295cf463aae07eb76e009faed3d3699623 Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Mon, 14 Jul 2008 00:09:41 -0700 Subject: reduce_heads(): protect from duplicate input Because we do not try computing merge base with itself for obvious reasons, the code was not prepared for an arguably insane case of the caller feeding the same commit twice to it. Noticed and test written by Sverre Hvammen Johansen Signed-off-by: Junio C Hamano --- commit.c | 11 +++++++++-- t/t7600-merge.sh | 22 ++++++++++++++++++++++ 2 files changed, 31 insertions(+), 2 deletions(-) (limited to 'commit.c') diff --git a/commit.c b/commit.c index 03e73f323a..5148ec5527 100644 --- a/commit.c +++ b/commit.c @@ -745,15 +745,22 @@ struct commit_list *reduce_heads(struct commit_list *heads) for (p = heads; p; p = p->next) { struct commit_list *q, *base; + /* Do we already have this in the result? */ + for (q = result; q; q = q->next) + if (p->item == q->item) + break; + if (q) + continue; + num_other = 0; for (q = heads; q; q = q->next) { if (p->item == q->item) continue; other[num_other++] = q->item; } - if (num_other) { + if (num_other) base = get_merge_bases_many(p->item, num_other, other, 1); - } else + else base = NULL; /* * If p->item does not have anything common with other diff --git a/t/t7600-merge.sh b/t/t7600-merge.sh index f035ea376e..d4cf6289a4 100755 --- a/t/t7600-merge.sh +++ b/t/t7600-merge.sh @@ -490,4 +490,26 @@ test_expect_success 'merge c1 with c0, c2, c0, and c1' ' test_debug 'gitk --all' +test_expect_success 'merge c1 with c0, c2, c0, and c1' ' + git reset --hard c1 && + git config branch.master.mergeoptions "" && + test_tick && + git merge c0 c2 c0 c1 && + verify_merge file result.1-5 && + verify_parents $c1 $c2 +' + +test_debug 'gitk --all' + +test_expect_success 'merge c1 with c1 and c2' ' + git reset --hard c1 && + git config branch.master.mergeoptions "" && + test_tick && + git merge c1 c2 && + verify_merge file result.1-5 && + verify_parents $c1 $c2 +' + +test_debug 'gitk --all' + test_done -- cgit v1.2.3