[RFC/PATCH v3] merge-base: teach "git merge-base" to accept more than 2 arguments

[RFC/PATCH v3] merge-base: teach "git merge-base" to accept more than 2 arguments

[Christian Couder]

Before this patch "git merge-base" accepted only 2 arguments, so
only merge bases between 2 references could be computed.

The purpose of this patch is to make "git merge-base" accept more
than 2 arguments, so that the merge bases between the first given
reference and all the other references can be computed.

This is easily implemented because the "get_merge_bases_many"
function in "commit.c" already implements the needed computation.

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
---
 Documentation/git-merge-base.txt |   27 +++++++++++++++--------
 builtin-merge-base.c             |   43 ++++++++++++++++++++++++-------------
 commit.h                         |    2 +
 3 files changed, 48 insertions(+), 24 deletions(-)

	I only changed the code (according to what Dscho asked) not the
	documentation in this version as I had not much time and I need
	to think more about it.

diff --git a/Documentation/git-merge-base.txt b/Documentation/git-merge-base.txt
index 1a7ecbf..463c230 100644
--- a/Documentation/git-merge-base.txt
+++ b/Documentation/git-merge-base.txt
@@ -8,26 +8,35 @@ 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 as good common ancestors as possible between
+the first commit and the other commits. The default behavior is to
+output only one as good as possible common ancestor, called a merge
+base.
+
+For example, 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.
+
+Given three commits A, B and C, `git merge-base A B C` will output a
+commit which is reachable through the parent relationship from both A
+and B, or from both A and C.
 
 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...
-
 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. No
+	merge bases in the output should be an ancestor of another
+	merge base in the output. Each common ancestor of the first
+	commit and any of the other commits passed as arguments,
+	should be an ancestor of one of the merge bases in the output.
 
 Author
 ------
diff --git a/builtin-merge-base.c b/builtin-merge-base.c
index 1cb2925..881363f 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,13 +22,21 @@ 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)
+{
+	unsigned char revkey[20];
+	if (get_sha1(arg, revkey))
+		die("Not a valid object name %s", arg);
+	return lookup_commit_reference(revkey);
+}
 
 int cmd_merge_base(int argc, const char **argv, const char *prefix)
 {
-	struct commit *rev1, *rev2;
-	unsigned char rev1key[20], rev2key[20];
+	struct commit **rev;
 	int show_all = 0;
+	int rev_nr = 0;
 
 	git_config(git_default_config, NULL);
 
@@ -38,15 +48,18 @@ 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);
-	if (get_sha1(argv[1], rev1key))
-		die("Not a valid object name %s", argv[1]);
-	if (get_sha1(argv[2], rev2key))
-		die("Not a valid object name %s", argv[2]);
-	rev1 = lookup_commit_reference(rev1key);
-	rev2 = lookup_commit_reference(rev2key);
-	if (!rev1 || !rev2)
-		return 1;
-	return show_merge_base(rev1, rev2, show_all);
+
+	rev = xmalloc((argc - 1) * sizeof(*rev));
+
+	do {
+		struct commit *r = get_commit_reference(argv[1]);
+		if (!r)
+			return 1;
+		rev[rev_nr++] = r;
+		argc--; argv++;
+	} while (argc > 1);
+
+	return show_merge_base(rev, rev_nr, show_all);
 }
diff --git a/commit.h b/commit.h
index 77de962..4829a5c 100644
--- a/commit.h
+++ b/commit.h
@@ -121,6 +121,8 @@ 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);
-- 
1.6.0.rc0.43.g00eb.dirty

Re: [RFC/PATCH v3] merge-base: teach "git merge-base" to accept more than 2 arguments

[Junio C Hamano]

Christian Couder <chriscool@tuxfamily.org> writes:

> Before this patch "git merge-base" accepted only 2 arguments, so
> only merge bases between 2 references could be computed.
>
> The purpose of this patch is to make "git merge-base" accept more
> than 2 arguments, so that the merge bases between the first given
> reference and all the other references can be computed.

I have trouble with this wording, but I'll comment on the documentation
part in a separate message.

> +static struct commit *get_commit_reference(const char *arg)
> +{
> +	unsigned char revkey[20];
> +	if (get_sha1(arg, revkey))
> +		die("Not a valid object name %s", arg);
> +	return lookup_commit_reference(revkey);
> +}

This returns a NULL when you feed a tree to the command, and...

>  int cmd_merge_base(int argc, const char **argv, const char *prefix)
>  {
> +	struct commit **rev;
>  	int show_all = 0;
> +	int rev_nr = 0;
>  
>  	git_config(git_default_config, NULL);
>  
> @@ -38,15 +48,18 @@ int cmd_merge_base(int argc, const char **argv, const char *prefix)
>  			usage(merge_base_usage);
>  		argc--; argv++;
>  	}
> +	if (argc < 3)
>  		usage(merge_base_usage);
> +
> +	rev = xmalloc((argc - 1) * sizeof(*rev));
> +
> +	do {
> +		struct commit *r = get_commit_reference(argv[1]);
> +		if (!r)
> +			return 1;

... the command silently exits with 1.

Re: [RFC/PATCH v3] merge-base: teach "git merge-base" to accept more than 2 arguments

[Christian Couder]

Le lundi 28 juillet 2008, Junio C Hamano a écrit :
> Christian Couder <chriscool@tuxfamily.org> writes:
>
> > +static struct commit *get_commit_reference(const char *arg)
> > +{
> > +	unsigned char revkey[20];
> > +	if (get_sha1(arg, revkey))
> > +		die("Not a valid object name %s", arg);
> > +	return lookup_commit_reference(revkey);
> > +}
>
> This returns a NULL when you feed a tree to the command, and...
>
> >  int cmd_merge_base(int argc, const char **argv, const char *prefix)
> >  {
> > +	struct commit **rev;
> >  	int show_all = 0;
> > +	int rev_nr = 0;
> >
> >  	git_config(git_default_config, NULL);
> >
> > @@ -38,15 +48,18 @@ int cmd_merge_base(int argc, const char **argv,
> > const char *prefix) usage(merge_base_usage);
> >  		argc--; argv++;
> >  	}
> > +	if (argc < 3)
> >  		usage(merge_base_usage);
> > +
> > +	rev = xmalloc((argc - 1) * sizeof(*rev));
> > +
> > +	do {
> > +		struct commit *r = get_commit_reference(argv[1]);
> > +		if (!r)
> > +			return 1;
>
> ... the command silently exits with 1.

In "master" there is:

	rev1 = lookup_commit_reference(rev1key);
	rev2 = lookup_commit_reference(rev2key);
	if (!rev1 || !rev2)
		return 1;
	return show_merge_base(rev1, rev2, show_all);

so I think you found a bug in the current code.
I will post a patch to fix it soon.

It will "die" (with an error ùmessage) in case "lookup_commit_reference" 
returns NULL. I hope it's ok.

Thanks,
Christian.

Re: [RFC/PATCH v3] merge-base: teach "git merge-base" to accept more than 2 arguments

[Junio C Hamano]

Christian Couder <chriscool@tuxfamily.org> writes:

> Before this patch "git merge-base" accepted only 2 arguments, so
> only merge bases between 2 references could be computed.
>
> The purpose of this patch is to make "git merge-base" accept more
> than 2 arguments, so that the merge bases between the first given
> reference and all the other references can be computed.

After thinking about this a bit more, I think that saying "we now allow
computing merge base between more than 2" is misleading.

I ended up rewriting almost all the lines.  The points are:

 * The command is still about computing merge-bases between two commits,
   and one of these two commits is the first command line argument as
   before.  With more than one remaining commits on the command line, you
   can specify a hypothetical commit that is a merge between all of them.

 * We did not formally define what a merge-base is.  Define it.

 * With a proper definition of merge-base as "best common ancestors", with
   the definition of "good/better/best" between common ancestors, we do
   not have to say anything redundant about --all.  It outputs all merge
   bases, as opposed to one chosen at random.

 * Have definition and give illustrations in a new Discussion section.

---
 Documentation/git-merge-base.txt |   77 ++++++++++++++++++++++++++++++++-----
 1 files changed, 66 insertions(+), 11 deletions(-)

diff --git a/Documentation/git-merge-base.txt b/Documentation/git-merge-base.txt
index 1a7ecbf..fd4b5c9 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
 ------

Re: [RFC/PATCH v3] merge-base: teach "git merge-base" to accept more than 2 arguments

[Johannes Schindelin]

Hi,

On Mon, 28 Jul 2008, Christian Couder wrote:

> +	rev = xmalloc((argc - 1) * sizeof(*rev));
> +
> +	do {
> +		struct commit *r = get_commit_reference(argv[1]);
> +		if (!r)
> +			return 1;
> +		rev[rev_nr++] = r;
> +		argc--; argv++;
> +	} while (argc > 1);
> +
> +	return show_merge_base(rev, rev_nr, show_all);

	rev = xmalloc((argc - 1) * sizeof(*rev));

	for (rev_nr = 0; rev_nr + 1 < argc; rev_nr++) {
		rev[rev_nr] = get_commit_reference(argv[rev_nr + 1]);
		if (!rev[rev_nr])
			return !!error("Does not refer to a commit: '%s'",
				argv[rev_nr + 1]);
	}

	return show_merge_base(rev, rev_nr, show_all);

I do not know about you, but I think this is not only shorter (in spite of 
adding a helpful error message), but also simpler to understand (not using 
convoluted do { } while logic), and therefore superior.

Your performance argument is weak IMHO, as this is not a big performance 
hit, and command line parameter parsing is definitely not performance 
critical.

Ciao,
Dscho

Re: [RFC/PATCH v3] merge-base: teach "git merge-base" to accept more than 2 arguments

[Christian Couder]

Hi,

Le lundi 28 juillet 2008, Johannes Schindelin a écrit :
> Hi,
>
> On Mon, 28 Jul 2008, Christian Couder wrote:
> > +	rev = xmalloc((argc - 1) * sizeof(*rev));
> > +
> > +	do {
> > +		struct commit *r = get_commit_reference(argv[1]);
> > +		if (!r)
> > +			return 1;
> > +		rev[rev_nr++] = r;
> > +		argc--; argv++;
> > +	} while (argc > 1);
> > +
> > +	return show_merge_base(rev, rev_nr, show_all);
>
> 	rev = xmalloc((argc - 1) * sizeof(*rev));
>
> 	for (rev_nr = 0; rev_nr + 1 < argc; rev_nr++) {
> 		rev[rev_nr] = get_commit_reference(argv[rev_nr + 1]);
> 		if (!rev[rev_nr])
> 			return !!error("Does not refer to a commit: '%s'",
> 				argv[rev_nr + 1]);
> 	}
>
> 	return show_merge_base(rev, rev_nr, show_all);
>
> I do not know about you, but I think this is not only shorter (in spite
> of adding a helpful error message), but also simpler to understand (not
> using convoluted do { } while logic), and therefore superior.

In my last version the loop is reduced to:

+	do {
+		rev[rev_nr++] = get_commit_reference(argv[1]);
+		argc--; argv++;
+	} while (argc > 1);

so it's very simple.

And the stop condition is simpler in my version.

> Your performance argument is weak IMHO, as this is not a big performance
> hit, and command line parameter parsing is definitely not performance
> critical.

It feels a bit sloppy though.

Regards,
Christian.

Re: [RFC/PATCH v3] merge-base: teach "git merge-base" to accept more than 2 arguments

[Johannes Schindelin]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 2107 bytes --]

Hi,

On Wed, 30 Jul 2008, Christian Couder wrote:

> Le lundi 28 juillet 2008, Johannes Schindelin a écrit :
>
> > On Mon, 28 Jul 2008, Christian Couder wrote:
> > > +	rev = xmalloc((argc - 1) * sizeof(*rev));
> > > +
> > > +	do {
> > > +		struct commit *r = get_commit_reference(argv[1]);
> > > +		if (!r)
> > > +			return 1;
> > > +		rev[rev_nr++] = r;
> > > +		argc--; argv++;
> > > +	} while (argc > 1);
> > > +
> > > +	return show_merge_base(rev, rev_nr, show_all);
> >
> > 	rev = xmalloc((argc - 1) * sizeof(*rev));
> >
> > 	for (rev_nr = 0; rev_nr + 1 < argc; rev_nr++) {
> > 		rev[rev_nr] = get_commit_reference(argv[rev_nr + 1]);
> > 		if (!rev[rev_nr])
> > 			return !!error("Does not refer to a commit: '%s'",
> > 				argv[rev_nr + 1]);
> > 	}
> >
> > 	return show_merge_base(rev, rev_nr, show_all);
> >
> > I do not know about you, but I think this is not only shorter (in spite
> > of adding a helpful error message), but also simpler to understand (not
> > using convoluted do { } while logic), and therefore superior.
> 
> In my last version the loop is reduced to:
> 
> +	do {
> +		rev[rev_nr++] = get_commit_reference(argv[1]);
> +		argc--; argv++;
> +	} while (argc > 1);
> 
> so it's very simple.
> 
> And the stop condition is simpler in my version.

Does not matter.  The logic is convoluted, i.e. not how (most) humans 
think.  And you cheat by putting the argc and argv statements in one line.

And you do not use argc and argv after the loop, so those statements are 
pointless.

And you cheat by not needing that die() anymore because you posted a 
(good!) patch _after_ I sent my version.

So it could e as short as this:

 	while (++rev_nr < argc)
 		rev[rev_nr - 1] = get_commit_reference(argv[rev_nr]);

I would contend that the for() version is more readable.

> > Your performance argument is weak IMHO, as this is not a big 
> > performance hit, and command line parameter parsing is definitely not 
> > performance critical.
> 
> It feels a bit sloppy though.

Sure.

If you think that obviousness in a command line parsing is less important 
than performance.

Ciao,
Dscho