From c5dc9a28298afb75d2be6b212d420fc89c258aa0 Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Sun, 27 Jul 2008 13:47:22 -0700 Subject: [PATCH] git-merge-octopus: use (merge-base A (merge B C D E...)) for stepwise merge Suppose you have this topology, and you are trying to make an octopus across A, B and C (you are at C and merging A and B into your branch). The protoccol between "git merge" and merge strategies is for the former to pass common ancestor(s), '--' and then commits being merged. git-merge-octopus does not produce the final merge in one-go. It iteratively produces pairwise merges. So the first step might be to come up with a merge between B and C: o---o---o---o---C / : / o---o---o---B..(M) / / ---1---2---o---o---o---A and for that, "1" is used as the merge base, not because it is the base across A, B and C but because it is the base between B and C. For this merge, A does not matter. I drew M in parentheses and lines between B and C to it in dotted line because we actually do _not_ create a real commit --- the only thing we need is a tree object, in order to proceed to the next step. Then the final merge result is obtained by merging tree of (M) and A using their common ancestor. For that, we _could_ still use "1" as the merge base. But if you imagine a case where you started from A and M, you would _not_ pick "1" as the merge base; you would rather use "2" which is a better base for this merge. That is why git-merge-octopus ignores the merge base given by "merge" but computes its own. The comment at the end of git-merge-octopus talks about "merge reference commit", that we used to update it to common found in this round, and that that updating was pointless. After the first round of merge to produce the tree for M (but without actually creating the commit object M itself), in order to figure out the merge base used to merge that with A in the second round, we used to use A and "1" (which was merge base between B and C). That was pointless --- "merge-base A 1" is guaranteed to give a base that is no better than either "merge-base A B" or "merge-base A C". So the current code keeps using the original head (iow, MRC=C, because in this case we are starting from C and merging B and then A into it). This trickerly was necessary only because we avoided creating the extra merge commit object M. Side note. An alternative implementation could have been to actually record it as a real merge commit M, and then let the two-commit merge-base compute the base between A and M when merging A to the result of the previous round, but we avoided creating M, at the expense of potentially using suboptimal base in the later rounds. But we do not have to be that pessimistic. We can instead accumulate the commits we have merged so far in MRC, and have merge_bases_many() compute the merge base for the new head being merged and the heads we have processed so far, which can give a better base than what we currently do. Signed-off-by: Junio C Hamano --- git-merge-octopus.sh | 11 ++--------- 1 file changed, 2 insertions(+), 9 deletions(-) diff --git a/git-merge-octopus.sh b/git-merge-octopus.sh index 645e1147dc..1dadbb4966 100755 --- a/git-merge-octopus.sh +++ b/git-merge-octopus.sh @@ -61,7 +61,7 @@ do exit 2 esac - common=$(git merge-base --all $MRC $SHA1) || + common=$(git merge-base --all $SHA1 $MRC) || die "Unable to find common commit with $SHA1" case "$LF$common$LF" in @@ -100,14 +100,7 @@ do next=$(git write-tree 2>/dev/null) fi - # We have merged the other branch successfully. Ideally - # we could implement OR'ed heads in merge-base, and keep - # a list of commits we have merged so far in MRC to feed - # them to merge-base, but we approximate it by keep using - # the current MRC. We used to update it to $common, which - # was incorrectly doing AND'ed merge-base here, which was - # unneeded. - + MRC="$MRC $SHA1" MRT=$next done -- 2.11.4.GIT