Merge branch 'cc/merge-base-many'

* cc/merge-base-many:
  git-merge-octopus: use (merge-base A (merge B C D E...)) for stepwise merge
  merge-base-many: add trivial tests based on the documentation
  documentation: merge-base: explain "git merge-base" with more than 2 args
  merge-base: teach "git merge-base" to drive underlying merge_bases_many()

5 files changed, 133 insertions, 28 deletions

diff --git a/Documentation/git-merge-base.txt b/Documentation/git-merge-base.txt
index 1a7ecbf8f3..2f0c5259e0 100644
--- a/Documentation/git-merge-base.txt
+++ b/Documentation/git-merge-base.txt
@@ -8,26 +8,81 @@ git-merge-base - Find as good common ancestors as possible for a merge
 
 SYNOPSIS
 --------
-'git merge-base' [--all] <commit> <commit>
+'git merge-base' [--all] <commit> <commit>...
 
 DESCRIPTION
 -----------
 
-'git-merge-base' finds as good a common ancestor as possible between
-the two commits. That is, given two commits A and B, `git merge-base A
-B` will output a commit which is reachable from both A and B through
-the parent relationship.
+'git-merge-base' finds best common ancestor(s) between two commits to use
+in a three-way merge.  One common ancestor is 'better' than another common
+ancestor if the latter is an ancestor of the former.  A common ancestor
+that does not have any better common ancestor than it is a 'best common
+ancestor', i.e. a 'merge base'.  Note that there can be more than one
+merge bases between two commits.
 
-Given a selection of equally good common ancestors it should not be
-relied on to decide in any particular way.
-
-The 'git-merge-base' algorithm is still in flux - use the source...
+Among the two commits to compute their merge bases, one is specified by
+the first commit argument on the command line; the other commit is a
+(possibly hypothetical) commit that is a merge across all the remaining
+commits on the command line.  As the most common special case, giving only
+two commits from the command line means computing the merge base between
+the given two commits.
 
 OPTIONS
 -------
 --all::
-	Output all common ancestors for the two commits instead of
-	just one.
+	Output all merge bases for the commits, instead of just one.
+
+DISCUSSION
+----------
+
+Given two commits 'A' and 'B', `git merge-base A B` will output a commit
+which is reachable from both 'A' and 'B' through the parent relationship.
+
+For example, with this topology:
+
+		 o---o---o---B
+		/
+	---o---1---o---o---o---A
+
+the merge base between 'A' and 'B' is '1'.
+
+Given three commits 'A', 'B' and 'C', `git merge-base A B C` will compute the
+merge base between 'A' and an hypothetical commit 'M', which is a merge
+between 'B' and 'C'.  For example, with this topology:
+
+	       o---o---o---o---C
+	      /
+	     /   o---o---o---B
+	    /   /
+	---2---1---o---o---o---A
+
+the result of `git merge-base A B C` is '1'.  This is because the
+equivalent topology with a merge commit 'M' between 'B' and 'C' is:
+
+
+	       o---o---o---o---o
+	      /                 \
+	     /   o---o---o---o---M
+	    /   /
+	---2---1---o---o---o---A
+
+and the result of `git merge-base A M` is '1'.  Commit '2' is also a
+common ancestor between 'A' and 'M', but '1' is a better common ancestor,
+because '2' is an ancestor of '1'.  Hence, '2' is not a merge base.
+
+When the history involves criss-cross merges, there can be more than one
+'best' common ancestors between two commits.  For example, with this
+topology:
+
+       ---1---o---A
+	   \ /
+	    X
+	   / \
+       ---2---o---o---B
+
+both '1' and '2' are merge-base of A and B.  Neither one is better than
+the other (both are 'best' merge base).  When `--all` option is not given,
+it is unspecified which best one is output.
 
 Author
 ------
diff --git a/builtin-merge-base.c b/builtin-merge-base.c
index 3382b1382a..b08da516e4 100644
--- a/builtin-merge-base.c
+++ b/builtin-merge-base.c
@@ -2,9 +2,11 @@
 #include "cache.h"
 #include "commit.h"
 
-static int show_merge_base(struct commit *rev1, struct commit *rev2, int show_all)
+static int show_merge_base(struct commit **rev, int rev_nr, int show_all)
 {
-	struct commit_list *result = get_merge_bases(rev1, rev2, 0);
+	struct commit_list *result;
+
+	result = get_merge_bases_many(rev[0], rev_nr - 1, rev + 1, 0);
 
 	if (!result)
 		return 1;
@@ -20,7 +22,7 @@ static int show_merge_base(struct commit *rev1, struct commit *rev2, int show_al
 }
 
 static const char merge_base_usage[] =
-"git merge-base [--all] <commit-id> <commit-id>";
+"git merge-base [--all] <commit-id> <commit-id>...";
 
 static struct commit *get_commit_reference(const char *arg)
 {
@@ -38,7 +40,8 @@ static struct commit *get_commit_reference(const char *arg)
 
 int cmd_merge_base(int argc, const char **argv, const char *prefix)
 {
-	struct commit *rev1, *rev2;
+	struct commit **rev;
+	int rev_nr = 0;
 	int show_all = 0;
 
 	git_config(git_default_config, NULL);
@@ -51,10 +54,15 @@ int cmd_merge_base(int argc, const char **argv, const char *prefix)
 			usage(merge_base_usage);
 		argc--; argv++;
 	}
-	if (argc != 3)
+	if (argc < 3)
 		usage(merge_base_usage);
-	rev1 = get_commit_reference(argv[1]);
-	rev2 = get_commit_reference(argv[2]);
 
-	return show_merge_base(rev1, rev2, show_all);
+	rev = xmalloc((argc - 1) * sizeof(*rev));
+
+	do {
+		rev[rev_nr++] = get_commit_reference(argv[1]);
+		argc--; argv++;
+	} while (argc > 1);
+
+	return show_merge_base(rev, rev_nr, show_all);
 }
diff --git a/commit.h b/commit.h
index 77de9621d9..d163c7487b 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_merge_bases_many(struct commit *one, int n, struct commit **twos, int cleanup);
 extern struct commit_list *get_octopus_merge_bases(struct commit_list *in);
 
 extern int register_shallow(const unsigned char *sha1);
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
 
diff --git a/t/t6010-merge-base.sh b/t/t6010-merge-base.sh
index b6e57b2426..04e4b7c5c2 100755
--- a/t/t6010-merge-base.sh
+++ b/t/t6010-merge-base.sh
@@ -108,4 +108,52 @@ test_expect_success 'compute merge-base (all)' \
     'MB=$(git merge-base --all PL PR) &&
      expr "$(git name-rev "$MB")" : "[0-9a-f]* tags/C2"'
 
+# Another set to demonstrate base between one commit and a merge
+# in the documentation.
+
+test_expect_success 'merge-base for octopus-step (setup)' '
+	test_tick && git commit --allow-empty -m root && git tag MMR &&
+	test_tick && git commit --allow-empty -m 1 && git tag MM1 &&
+	test_tick && git commit --allow-empty -m o &&
+	test_tick && git commit --allow-empty -m o &&
+	test_tick && git commit --allow-empty -m o &&
+	test_tick && git commit --allow-empty -m A && git tag MMA &&
+	git checkout MM1 &&
+	test_tick && git commit --allow-empty -m o &&
+	test_tick && git commit --allow-empty -m o &&
+	test_tick && git commit --allow-empty -m o &&
+	test_tick && git commit --allow-empty -m B && git tag MMB &&
+	git checkout MMR &&
+	test_tick && git commit --allow-empty -m o &&
+	test_tick && git commit --allow-empty -m o &&
+	test_tick && git commit --allow-empty -m o &&
+	test_tick && git commit --allow-empty -m o &&
+	test_tick && git commit --allow-empty -m C && git tag MMC
+'
+
+test_expect_success 'merge-base A B C' '
+	MB=$(git merge-base --all MMA MMB MMC) &&
+	MM1=$(git rev-parse --verify MM1) &&
+	test "$MM1" = "$MB"
+'
+
+test_expect_success 'criss-cross merge-base for octopus-step (setup)' '
+	git reset --hard MMR &&
+	test_tick && git commit --allow-empty -m 1 && git tag CC1 &&
+	git reset --hard E &&
+	test_tick && git commit --allow-empty -m 2 && git tag CC2 &&
+	test_tick && git merge -s ours CC1 &&
+	test_tick && git commit --allow-empty -m o &&
+	test_tick && git commit --allow-empty -m B && git tag CCB &&
+	git reset --hard CC1 &&
+	test_tick && git merge -s ours CC2 &&
+	test_tick && git commit --allow-empty -m A && git tag CCA
+'
+
+test_expect_success 'merge-base B A^^ A^^2' '
+	MB0=$(git merge-base --all CCB CCA^^ CCA^^2 | sort) &&
+	MB1=$(git rev-parse CC1 CC2 | sort) &&
+	test "$MB0" = "$MB1"
+'
+
 test_done