Re: [PATCH 09/10] Introduce get_octopus_merge_bases() in commit.c

[Junio C Hamano <gitster@pobox.com>]

Junio C Hamano <gitster@pobox.com> writes:

> When you want to merge A, B and C, because internally we always do
> pairwise, you would first compute:
>
> 	T(A,B) == merge_3way(mb(A,B), A, B)
>
> and then you would want to pick some merge base to merge that result with
> C:
>
> 	T(A,B,C) == merge_3way(???, T(A,B), C)
>
> I do not think using mb(mb(A,B),C) as ??? is necessary nor optimal.
>
>           o---o---A
>          /         .
>     ----1---2---B...T(A,B)
>              \       .
>               o---C...T(A,B,C)
>
> "1" above is mb(A,B) (i.e. the merge base between A and B) that you would
> use when you merge A and B to compute an internal merge result T(A,B).
> And "1" also is mb(mb(A,B),C).
>
> But if you are doing 3-way merge to arrive at T(A,B,C) by merging T(A,B)
> and C, don't you want to be using "2" as the merge base, not "1"?
>
> The big comment on $MRC at the end of git-merge-octopus is about this
> issue.  In earlier implementation, we used to use "1" to create T(A,B) and
> then also used it to update the variable $MRC, which is used to compute
> the merge base to use when the tentative tree T(A,B) is merged with the
> other remote in the next round.  It was a mistake.
>
> Ideally we should pick a better base between mb(A,C) and mb(B,C) (and if
> we used mb(B,C) that's "2" and is a much better base than "1" when merging
> T(A,B) and C).  Using mb(mb(A,B),C) means we are guaranteed to pick the
> worst base for that last merge.

Something like this might be enough to get us started.  Instead of finding
out the merge bases between two commits, "one" and "two", this would find
merge base between "one" and a commit that would be a merge across all the
"two"s.  To apply it to the above example, you would give "C" as "one",
and "A" and "B" as "twos" to it, to compute "2".

 commit.c |   32 ++++++++++++++++++++++----------
 1 files changed, 22 insertions(+), 10 deletions(-)

diff --git a/commit.c b/commit.c
index 94d5b3d..816eed1 100644
--- a/commit.c
+++ b/commit.c
@@ -531,26 +531,33 @@ 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;
@@ -598,6 +605,11 @@ static struct commit_list *merge_bases(struct commit *one, struct commit *two)
 	return result;
 }
 
+static struct commit_list *merge_bases(struct commit *one, struct commit *two)
+{
+	return merge_bases_many(one, 1, &two);
+}
+
 struct commit_list *get_merge_bases(struct commit *one,
 					struct commit *two, int cleanup)
 {