[PATCH 00/11] Build in merge

[PATCH 00/11] Build in merge

[Miklos Vajna]

Hi,

Changes since the previous series I sent out to the list:

- get_octopus_merge_bases() now always does a cleanup

- added a new test to make sure git-merge handles more than 25 refs

As usual, comments are welcome. :-)

Miklos Vajna (11):
  Move split_cmdline() to alias.c
  Move commit_list_count() to commit.c
  Move parse-options's skip_prefix() to git-compat-util.h
  Add new test to ensure git-merge handles pull.twohead and
    pull.octopus
  parseopt: add a new PARSE_OPT_ARGV0_IS_AN_OPTION option
  Move read_cache_unmerged() to read-cache.c
  git-fmt-merge-msg: make it usable from other builtins
  Introduce get_octopus_merge_bases() in commit.c
  Introduce filter_independent() in commit.c
  Build in merge
  Add new test to ensure git-merge handles more than 25 refs.

 Makefile                                      |    2 +-
 alias.c                                       |   54 ++
 builtin-fmt-merge-msg.c                       |  157 ++--
 builtin-merge-recursive.c                     |    8 -
 builtin-merge.c                               | 1128 +++++++++++++++++++++++++
 builtin-read-tree.c                           |   24 -
 builtin-remote.c                              |   39 +-
 builtin.h                                     |    4 +
 cache.h                                       |    3 +
 commit.c                                      |   51 ++
 commit.h                                      |    3 +
 git-merge.sh => contrib/examples/git-merge.sh |    0 
 git-compat-util.h                             |    6 +
 git.c                                         |   54 +--
 parse-options.c                               |   11 +-
 parse-options.h                               |    1 +
 read-cache.c                                  |   31 +
 t/t7601-merge-pull-config.sh                  |   72 ++
 t/t7602-merge-octopus-many.sh                 |   52 ++
 19 files changed, 1529 insertions(+), 171 deletions(-)
 create mode 100644 builtin-merge.c
 rename git-merge.sh => contrib/examples/git-merge.sh (100%)
 create mode 100755 t/t7601-merge-pull-config.sh
 create mode 100755 t/t7602-merge-octopus-many.sh

[PATCH 01/11] Move split_cmdline() to alias.c

[Miklos Vajna]

split_cmdline() is currently used for aliases only, but later it can be
useful for other builtins as well. Move it to alias.c for now,
indicating that originally it's for aliases, but we'll have it in libgit
this way.

Signed-off-by: Miklos Vajna <vmiklos@frugalware.org>
---
 alias.c |   54 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 cache.h |    1 +
 git.c   |   53 -----------------------------------------------------
 3 files changed, 55 insertions(+), 53 deletions(-)

diff --git a/alias.c b/alias.c
index 995f3e6..ccb1108 100644
--- a/alias.c
+++ b/alias.c
@@ -21,3 +21,57 @@ char *alias_lookup(const char *alias)
 	git_config(alias_lookup_cb, NULL);
 	return alias_val;
 }
+
+int split_cmdline(char *cmdline, const char ***argv)
+{
+	int src, dst, count = 0, size = 16;
+	char quoted = 0;
+
+	*argv = xmalloc(sizeof(char*) * size);
+
+	/* split alias_string */
+	(*argv)[count++] = cmdline;
+	for (src = dst = 0; cmdline[src];) {
+		char c = cmdline[src];
+		if (!quoted && isspace(c)) {
+			cmdline[dst++] = 0;
+			while (cmdline[++src]
+					&& isspace(cmdline[src]))
+				; /* skip */
+			if (count >= size) {
+				size += 16;
+				*argv = xrealloc(*argv, sizeof(char*) * size);
+			}
+			(*argv)[count++] = cmdline + dst;
+		} else if (!quoted && (c == '\'' || c == '"')) {
+			quoted = c;
+			src++;
+		} else if (c == quoted) {
+			quoted = 0;
+			src++;
+		} else {
+			if (c == '\\' && quoted != '\'') {
+				src++;
+				c = cmdline[src];
+				if (!c) {
+					free(*argv);
+					*argv = NULL;
+					return error("cmdline ends with \\");
+				}
+			}
+			cmdline[dst++] = c;
+			src++;
+		}
+	}
+
+	cmdline[dst] = 0;
+
+	if (quoted) {
+		free(*argv);
+		*argv = NULL;
+		return error("unclosed quote");
+	}
+
+	return count;
+}
+
diff --git a/cache.h b/cache.h
index 81b7e17..26b2cad 100644
--- a/cache.h
+++ b/cache.h
@@ -827,5 +827,6 @@ int report_path_error(const char *ps_matched, const char **pathspec, int prefix_
 void overlay_tree_on_cache(const char *tree_name, const char *prefix);
 
 char *alias_lookup(const char *alias);
+int split_cmdline(char *cmdline, const char ***argv);
 
 #endif /* CACHE_H */
diff --git a/git.c b/git.c
index 59f0fcc..2fbe96b 100644
--- a/git.c
+++ b/git.c
@@ -90,59 +90,6 @@ static int handle_options(const char*** argv, int* argc, int* envchanged)
 	return handled;
 }
 
-static int split_cmdline(char *cmdline, const char ***argv)
-{
-	int src, dst, count = 0, size = 16;
-	char quoted = 0;
-
-	*argv = xmalloc(sizeof(char*) * size);
-
-	/* split alias_string */
-	(*argv)[count++] = cmdline;
-	for (src = dst = 0; cmdline[src];) {
-		char c = cmdline[src];
-		if (!quoted && isspace(c)) {
-			cmdline[dst++] = 0;
-			while (cmdline[++src]
-					&& isspace(cmdline[src]))
-				; /* skip */
-			if (count >= size) {
-				size += 16;
-				*argv = xrealloc(*argv, sizeof(char*) * size);
-			}
-			(*argv)[count++] = cmdline + dst;
-		} else if(!quoted && (c == '\'' || c == '"')) {
-			quoted = c;
-			src++;
-		} else if (c == quoted) {
-			quoted = 0;
-			src++;
-		} else {
-			if (c == '\\' && quoted != '\'') {
-				src++;
-				c = cmdline[src];
-				if (!c) {
-					free(*argv);
-					*argv = NULL;
-					return error("cmdline ends with \\");
-				}
-			}
-			cmdline[dst++] = c;
-			src++;
-		}
-	}
-
-	cmdline[dst] = 0;
-
-	if (quoted) {
-		free(*argv);
-		*argv = NULL;
-		return error("unclosed quote");
-	}
-
-	return count;
-}
-
 static int handle_alias(int *argcp, const char ***argv)
 {
 	int envchanged = 0, ret = 0, saved_errno = errno;
-- 
1.5.6

[PATCH 02/11] Move commit_list_count() to commit.c

[Miklos Vajna]

This function is useful outside builtin-merge-recursive, for example in
builtin-merge.

Signed-off-by: Miklos Vajna <vmiklos@frugalware.org>
---
 builtin-merge-recursive.c |    8 --------
 commit.c                  |    8 ++++++++
 commit.h                  |    1 +
 3 files changed, 9 insertions(+), 8 deletions(-)

diff --git a/builtin-merge-recursive.c b/builtin-merge-recursive.c
index 4aa28a1..98b09fb 100644
--- a/builtin-merge-recursive.c
+++ b/builtin-merge-recursive.c
@@ -42,14 +42,6 @@ static struct tree *shift_tree_object(struct tree *one, struct tree *two)
  * - *(int *)commit->object.sha1 set to the virtual id.
  */
 
-static unsigned commit_list_count(const struct commit_list *l)
-{
-	unsigned c = 0;
-	for (; l; l = l->next )
-		c++;
-	return c;
-}
-
 static struct commit *make_virtual_commit(struct tree *tree, const char *comment)
 {
 	struct commit *commit = xcalloc(1, sizeof(struct commit));
diff --git a/commit.c b/commit.c
index e2d8624..bbf9c75 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) {
diff --git a/commit.h b/commit.h
index 2d94d41..7f8c5ee 100644
--- a/commit.h
+++ b/commit.h
@@ -41,6 +41,7 @@ int parse_commit_buffer(struct commit *item, void *buffer, unsigned long size);
 int parse_commit(struct commit *item);
 
 struct commit_list * commit_list_insert(struct commit *item, struct commit_list **list_p);
+unsigned commit_list_count(const struct commit_list *l);
 struct commit_list * insert_by_date(struct commit *item, struct commit_list **list);
 
 void free_commit_list(struct commit_list *list);
-- 
1.5.6

[PATCH 03/11] Move parse-options's skip_prefix() to git-compat-util.h

[Miklos Vajna]

builtin-remote.c and parse-options.c both have a skip_prefix() function,
for the same purpose. Move parse-options's one to git-compat-util.h and
let builtin-remote use it as well.

Signed-off-by: Miklos Vajna <vmiklos@frugalware.org>
---
 builtin-remote.c  |   39 ++++++++++++++++++++++++++-------------
 git-compat-util.h |    6 ++++++
 parse-options.c   |    6 ------
 3 files changed, 32 insertions(+), 19 deletions(-)

diff --git a/builtin-remote.c b/builtin-remote.c
index 145dd85..1491354 100644
--- a/builtin-remote.c
+++ b/builtin-remote.c
@@ -29,12 +29,6 @@ static inline int postfixcmp(const char *string, const char *postfix)
 	return strcmp(string + len1 - len2, postfix);
 }
 
-static inline const char *skip_prefix(const char *name, const char *prefix)
-{
-	return !name ? "" :
-		prefixcmp(name, prefix) ?  name : name + strlen(prefix);
-}
-
 static int opt_parse_track(const struct option *opt, const char *arg, int not)
 {
 	struct path_list *list = opt->value;
@@ -182,12 +176,18 @@ static int config_read_branches(const char *key, const char *value, void *cb)
 			info->remote = xstrdup(value);
 		} else {
 			char *space = strchr(value, ' ');
-			value = skip_prefix(value, "refs/heads/");
+			const char *ptr = skip_prefix(value, "refs/heads/");
+			if (ptr)
+				value = ptr;
 			while (space) {
 				char *merge;
 				merge = xstrndup(value, space - value);
 				path_list_append(merge, &info->merge);
-				value = skip_prefix(space + 1, "refs/heads/");
+				ptr = skip_prefix(space + 1, "refs/heads/");
+				if (ptr)
+					value = ptr;
+				else
+					value = space + 1;
 				space = strchr(value, ' ');
 			}
 			path_list_append(xstrdup(value), &info->merge);
@@ -219,7 +219,12 @@ static int handle_one_branch(const char *refname,
 	refspec.dst = (char *)refname;
 	if (!remote_find_tracking(states->remote, &refspec)) {
 		struct path_list_item *item;
-		const char *name = skip_prefix(refspec.src, "refs/heads/");
+		const char *name, *ptr;
+		ptr = skip_prefix(refspec.src, "refs/heads/");
+		if (ptr)
+			name = ptr;
+		else
+			name = refspec.src;
 		/* symbolic refs pointing nowhere were handled already */
 		if ((flags & REF_ISSYMREF) ||
 				unsorted_path_list_has_path(&states->tracked,
@@ -248,6 +253,7 @@ static int get_ref_states(const struct ref *ref, struct ref_states *states)
 		struct path_list *target = &states->tracked;
 		unsigned char sha1[20];
 		void *util = NULL;
+		const char *ptr;
 
 		if (!ref->peer_ref || read_ref(ref->peer_ref->name, sha1))
 			target = &states->new;
@@ -256,8 +262,10 @@ static int get_ref_states(const struct ref *ref, struct ref_states *states)
 			if (hashcmp(sha1, ref->new_sha1))
 				util = &states;
 		}
-		path_list_append(skip_prefix(ref->name, "refs/heads/"),
-				target)->util = util;
+		ptr = skip_prefix(ref->name, "refs/heads/");
+		if (!ptr)
+			ptr = ref->name;
+		path_list_append(ptr, target)->util = util;
 	}
 	free_refs(fetch_map);
 
@@ -522,10 +530,15 @@ static int show(int argc, const char **argv)
 					"es" : "");
 			for (i = 0; i < states.remote->push_refspec_nr; i++) {
 				struct refspec *spec = states.remote->push + i;
+				const char *p = "", *q = "";
+				if (spec->src)
+					p = skip_prefix(spec->src, "refs/heads/");
+				if (spec->dst)
+					q = skip_prefix(spec->dst, "refs/heads/");
 				printf(" %s%s%s%s", spec->force ? "+" : "",
-					skip_prefix(spec->src, "refs/heads/"),
+					p ? p : spec->src,
 					spec->dst ? ":" : "",
-					skip_prefix(spec->dst, "refs/heads/"));
+					q ? q : spec->dst);
 			}
 			printf("\n");
 		}
diff --git a/git-compat-util.h b/git-compat-util.h
index c04e8ba..6470d6c 100644
--- a/git-compat-util.h
+++ b/git-compat-util.h
@@ -127,6 +127,12 @@ extern void set_warn_routine(void (*routine)(const char *warn, va_list params));
 
 extern int prefixcmp(const char *str, const char *prefix);
 
+static inline const char *skip_prefix(const char *str, const char *prefix)
+{
+	size_t len = strlen(prefix);
+	return strncmp(str, prefix, len) ? NULL : str + len;
+}
+
 #ifdef NO_MMAP
 
 #ifndef PROT_READ
diff --git a/parse-options.c b/parse-options.c
index acf3fe3..b98833c 100644
--- a/parse-options.c
+++ b/parse-options.c
@@ -22,12 +22,6 @@ static inline const char *get_arg(struct optparse_t *p)
 	return *++p->argv;
 }
 
-static inline const char *skip_prefix(const char *str, const char *prefix)
-{
-	size_t len = strlen(prefix);
-	return strncmp(str, prefix, len) ? NULL : str + len;
-}
-
 static int opterror(const struct option *opt, const char *reason, int flags)
 {
 	if (flags & OPT_SHORT)
-- 
1.5.6

[PATCH 04/11] Add new test to ensure git-merge handles pull.twohead and pull.octopus

[Miklos Vajna]

Test if the given strategies are used and test the case when multiple
strategies are configured using a space separated list.

Signed-off-by: Miklos Vajna <vmiklos@frugalware.org>
---
 t/t7601-merge-pull-config.sh |   72 ++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 72 insertions(+), 0 deletions(-)
 create mode 100755 t/t7601-merge-pull-config.sh

diff --git a/t/t7601-merge-pull-config.sh b/t/t7601-merge-pull-config.sh
new file mode 100755
index 0000000..c0b550e
--- /dev/null
+++ b/t/t7601-merge-pull-config.sh
@@ -0,0 +1,72 @@
+#!/bin/sh
+
+test_description='git-merge
+
+Testing pull.* configuration parsing.'
+
+. ./test-lib.sh
+
+test_expect_success 'setup' '
+	echo c0 >c0.c &&
+	git add c0.c &&
+	git commit -m c0 &&
+	git tag c0 &&
+	echo c1 >c1.c &&
+	git add c1.c &&
+	git commit -m c1 &&
+	git tag c1 &&
+	git reset --hard c0 &&
+	echo c2 >c2.c &&
+	git add c2.c &&
+	git commit -m c2 &&
+	git tag c2
+	git reset --hard c0 &&
+	echo c3 >c3.c &&
+	git add c3.c &&
+	git commit -m c3 &&
+	git tag c3
+'
+
+test_expect_success 'merge c1 with c2' '
+	git reset --hard c1 &&
+	test -f c0.c &&
+	test -f c1.c &&
+	test ! -f c2.c &&
+	test ! -f c3.c &&
+	git merge c2 &&
+	test -f c1.c &&
+	test -f c2.c
+'
+
+test_expect_success 'merge c1 with c2 (ours in pull.twohead)' '
+	git reset --hard c1 &&
+	git config pull.twohead ours &&
+	git merge c2 &&
+	test -f c1.c &&
+	! test -f c2.c
+'
+
+test_expect_success 'merge c1 with c2 and c3 (recursive in pull.octopus)' '
+	git reset --hard c1 &&
+	git config pull.octopus "recursive" &&
+	test_must_fail git merge c2 c3 &&
+	test "$(git rev-parse c1)" = "$(git rev-parse HEAD)"
+'
+
+test_expect_success 'merge c1 with c2 and c3 (recursive and octopus in pull.octopus)' '
+	git reset --hard c1 &&
+	git config pull.octopus "recursive octopus" &&
+	git merge c2 c3 &&
+	test "$(git rev-parse c1)" != "$(git rev-parse HEAD)" &&
+	test "$(git rev-parse c1)" = "$(git rev-parse HEAD^1)" &&
+	test "$(git rev-parse c2)" = "$(git rev-parse HEAD^2)" &&
+	test "$(git rev-parse c3)" = "$(git rev-parse HEAD^3)"
+	test "$(git rev-parse c3)" = "$(git rev-parse HEAD^3)" &&
+	git diff --exit-code &&
+	test -f c0.c &&
+	test -f c1.c &&
+	test -f c2.c &&
+	test -f c3.c
+'
+
+test_done
-- 
1.5.6

[PATCH 05/11] parseopt: add a new PARSE_OPT_ARGV0_IS_AN_OPTION option

[Miklos Vajna]

This new option tells parse-options not to ignore argv[0]. This is
useful when argv cames from split_cmdline(), as in that case argv[0]
contains a valuable option as well.

Signed-off-by: Miklos Vajna <vmiklos@frugalware.org>
---
 parse-options.c |    5 +++++
 parse-options.h |    1 +
 2 files changed, 6 insertions(+), 0 deletions(-)

diff --git a/parse-options.c b/parse-options.c
index b98833c..1d01a86 100644
--- a/parse-options.c
+++ b/parse-options.c
@@ -249,6 +249,11 @@ int parse_options(int argc, const char **argv, const struct option *options,
 {
 	struct optparse_t args = { argv + 1, argv, argc - 1, 0, NULL };
 
+	if (flags & PARSE_OPT_ARGV0_IS_AN_OPTION) {
+		args.argv = argv;
+		args.argc = argc;
+	}
+
 	for (; args.argc; args.argc--, args.argv++) {
 		const char *arg = args.argv[0];
 
diff --git a/parse-options.h b/parse-options.h
index 4ee443d..3238401 100644
--- a/parse-options.h
+++ b/parse-options.h
@@ -20,6 +20,7 @@ enum parse_opt_type {
 enum parse_opt_flags {
 	PARSE_OPT_KEEP_DASHDASH = 1,
 	PARSE_OPT_STOP_AT_NON_OPTION = 2,
+	PARSE_OPT_ARGV0_IS_AN_OPTION = 4,
 };
 
 enum parse_opt_option_flags {
-- 
1.5.6

[PATCH 06/11] Move read_cache_unmerged() to read-cache.c

[Miklos Vajna]

builtin-read-tree has a read_cache_unmerged() which is useful for other
builtins, for example builtin-merge uses it as well. Move it to
read-cache.c to avoid code duplication.

Signed-off-by: Miklos Vajna <vmiklos@frugalware.org>
---
 builtin-read-tree.c |   24 ------------------------
 cache.h             |    2 ++
 read-cache.c        |   31 +++++++++++++++++++++++++++++++
 3 files changed, 33 insertions(+), 24 deletions(-)

diff --git a/builtin-read-tree.c b/builtin-read-tree.c
index 5a09e17..72a6de3 100644
--- a/builtin-read-tree.c
+++ b/builtin-read-tree.c
@@ -29,30 +29,6 @@ static int list_tree(unsigned char *sha1)
 	return 0;
 }
 
-static int read_cache_unmerged(void)
-{
-	int i;
-	struct cache_entry **dst;
-	struct cache_entry *last = NULL;
-
-	read_cache();
-	dst = active_cache;
-	for (i = 0; i < active_nr; i++) {
-		struct cache_entry *ce = active_cache[i];
-		if (ce_stage(ce)) {
-			remove_name_hash(ce);
-			if (last && !strcmp(ce->name, last->name))
-				continue;
-			cache_tree_invalidate_path(active_cache_tree, ce->name);
-			last = ce;
-			continue;
-		}
-		*dst++ = ce;
-	}
-	active_nr = dst - active_cache;
-	return !!last;
-}
-
 static void prime_cache_tree_rec(struct cache_tree *it, struct tree *tree)
 {
 	struct tree_desc desc;
diff --git a/cache.h b/cache.h
index 26b2cad..02fb7cb 100644
--- a/cache.h
+++ b/cache.h
@@ -254,6 +254,7 @@ static inline void remove_name_hash(struct cache_entry *ce)
 
 #define read_cache() read_index(&the_index)
 #define read_cache_from(path) read_index_from(&the_index, (path))
+#define read_cache_unmerged() read_index_unmerged(&the_index)
 #define write_cache(newfd, cache, entries) write_index(&the_index, (newfd))
 #define discard_cache() discard_index(&the_index)
 #define unmerged_cache() unmerged_index(&the_index)
@@ -357,6 +358,7 @@ extern int init_db(const char *template_dir, unsigned int flags);
 /* Initialize and use the cache information */
 extern int read_index(struct index_state *);
 extern int read_index_from(struct index_state *, const char *path);
+extern int read_index_unmerged(struct index_state *);
 extern int write_index(const struct index_state *, int newfd);
 extern int discard_index(struct index_state *);
 extern int unmerged_index(const struct index_state *);
diff --git a/read-cache.c b/read-cache.c
index 8e5fbb6..ea23726 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -1394,3 +1394,34 @@ int write_index(const struct index_state *istate, int newfd)
 	}
 	return ce_flush(&c, newfd);
 }
+
+/*
+ * Read the index file that is potentially unmerged into given
+ * index_state, dropping any unmerged entries.  Returns true is
+ * the index is unmerged.  Callers who want to refuse to work
+ * from an unmerged state can call this and check its return value,
+ * instead of calling read_cache().
+ */
+int read_index_unmerged(struct index_state *istate)
+{
+	int i;
+	struct cache_entry **dst;
+	struct cache_entry *last = NULL;
+
+	read_index(istate);
+	dst = istate->cache;
+	for (i = 0; i < istate->cache_nr; i++) {
+		struct cache_entry *ce = istate->cache[i];
+		if (ce_stage(ce)) {
+			remove_name_hash(ce);
+			if (last && !strcmp(ce->name, last->name))
+				continue;
+			cache_tree_invalidate_path(istate->cache_tree, ce->name);
+			last = ce;
+			continue;
+		}
+		*dst++ = ce;
+	}
+	istate->cache_nr = dst - istate->cache;
+	return !!last;
+}
-- 
1.5.6

[PATCH 07/11] git-fmt-merge-msg: make it usable from other builtins

[Miklos Vajna]

Move all functionality (except config and option parsing) from
cmd_fmt_merge_msg() to fmt_merge_msg(), so that other builtins can use
it without a child process.

All functions have been changed to use strbufs, and now only
cmd_fmt_merge_msg() reads directly from a file / writes anything to
stdout.

Signed-off-by: Miklos Vajna <vmiklos@frugalware.org>
---
 builtin-fmt-merge-msg.c |  157 +++++++++++++++++++++++++++--------------------
 builtin.h               |    3 +
 2 files changed, 94 insertions(+), 66 deletions(-)

diff --git a/builtin-fmt-merge-msg.c b/builtin-fmt-merge-msg.c
index b892621..91f08e9 100644
--- a/builtin-fmt-merge-msg.c
+++ b/builtin-fmt-merge-msg.c
@@ -159,23 +159,24 @@ static int handle_line(char *line)
 }
 
 static void print_joined(const char *singular, const char *plural,
-		struct list *list)
+		struct list *list, struct strbuf *out)
 {
 	if (list->nr == 0)
 		return;
 	if (list->nr == 1) {
-		printf("%s%s", singular, list->list[0]);
+		strbuf_addf(out, "%s%s", singular, list->list[0]);
 	} else {
 		int i;
-		printf("%s", plural);
+		strbuf_addstr(out, plural);
 		for (i = 0; i < list->nr - 1; i++)
-			printf("%s%s", i > 0 ? ", " : "", list->list[i]);
-		printf(" and %s", list->list[list->nr - 1]);
+			strbuf_addf(out, "%s%s", i > 0 ? ", " : "", list->list[i]);
+		strbuf_addf(out, " and %s", list->list[list->nr - 1]);
 	}
 }
 
 static void shortlog(const char *name, unsigned char *sha1,
-		struct commit *head, struct rev_info *rev, int limit)
+		struct commit *head, struct rev_info *rev, int limit,
+		struct strbuf *out)
 {
 	int i, count = 0;
 	struct commit *commit;
@@ -232,15 +233,15 @@ static void shortlog(const char *name, unsigned char *sha1,
 	}
 
 	if (count > limit)
-		printf("\n* %s: (%d commits)\n", name, count);
+		strbuf_addf(out, "\n* %s: (%d commits)\n", name, count);
 	else
-		printf("\n* %s:\n", name);
+		strbuf_addf(out, "\n* %s:\n", name);
 
 	for (i = 0; i < subjects.nr; i++)
 		if (i >= limit)
-			printf("  ...\n");
+			strbuf_addf(out, "  ...\n");
 		else
-			printf("  %s\n", subjects.list[i]);
+			strbuf_addf(out, "  %s\n", subjects.list[i]);
 
 	clear_commit_marks((struct commit *)branch, flags);
 	clear_commit_marks(head, flags);
@@ -251,43 +252,13 @@ static void shortlog(const char *name, unsigned char *sha1,
 	free_list(&subjects);
 }
 
-int cmd_fmt_merge_msg(int argc, const char **argv, const char *prefix)
-{
-	int limit = 20, i = 0;
+int fmt_merge_msg(int merge_summary, struct strbuf *in, struct strbuf *out) {
+	int limit = 20, i = 0, pos = 0;
 	char line[1024];
-	FILE *in = stdin;
-	const char *sep = "";
+	char *p = line, *sep = "";
 	unsigned char head_sha1[20];
 	const char *current_branch;
 
-	git_config(fmt_merge_msg_config, NULL);
-
-	while (argc > 1) {
-		if (!strcmp(argv[1], "--log") || !strcmp(argv[1], "--summary"))
-			merge_summary = 1;
-		else if (!strcmp(argv[1], "--no-log")
-				|| !strcmp(argv[1], "--no-summary"))
-			merge_summary = 0;
-		else if (!strcmp(argv[1], "-F") || !strcmp(argv[1], "--file")) {
-			if (argc < 3)
-				die ("Which file?");
-			if (!strcmp(argv[2], "-"))
-				in = stdin;
-			else {
-				fclose(in);
-				in = fopen(argv[2], "r");
-				if (!in)
-					die("cannot open %s", argv[2]);
-			}
-			argc--; argv++;
-		} else
-			break;
-		argc--; argv++;
-	}
-
-	if (argc > 1)
-		usage(fmt_merge_msg_usage);
-
 	/* get current branch */
 	current_branch = resolve_ref("HEAD", head_sha1, 1, NULL);
 	if (!current_branch)
@@ -295,75 +266,129 @@ int cmd_fmt_merge_msg(int argc, const char **argv, const char *prefix)
 	if (!prefixcmp(current_branch, "refs/heads/"))
 		current_branch += 11;
 
-	while (fgets(line, sizeof(line), in)) {
+	/* get a line */
+	for (;;) {
+		int len;
+		char *newline;
+
+		if (pos >= in->len)
+			break;
+		p = in->buf + pos;
+		newline = strchr(p, '\n');
+		len = newline ? newline - p : strlen(p);
+		pos += len + !!newline;
 		i++;
-		if (line[0] == 0)
-			continue;
-		if (handle_line(line))
-			die ("Error in line %d: %s", i, line);
+		p[len] = 0;
+		if (handle_line(p))
+			die ("Error in line %d: %.*s", i, len, p);
 	}
 
-	printf("Merge ");
+	strbuf_addstr(out, "Merge ");
 	for (i = 0; i < srcs.nr; i++) {
 		struct src_data *src_data = srcs.payload[i];
 		const char *subsep = "";
 
-		printf(sep);
+		strbuf_addstr(out, sep);
 		sep = "; ";
 
 		if (src_data->head_status == 1) {
-			printf(srcs.list[i]);
+			strbuf_addstr(out, srcs.list[i]);
 			continue;
 		}
 		if (src_data->head_status == 3) {
 			subsep = ", ";
-			printf("HEAD");
+			strbuf_addstr(out, "HEAD");
 		}
 		if (src_data->branch.nr) {
-			printf(subsep);
+			strbuf_addstr(out, subsep);
 			subsep = ", ";
-			print_joined("branch ", "branches ", &src_data->branch);
+			print_joined("branch ", "branches ", &src_data->branch,
+					out);
 		}
 		if (src_data->r_branch.nr) {
-			printf(subsep);
+			strbuf_addstr(out, subsep);
 			subsep = ", ";
 			print_joined("remote branch ", "remote branches ",
-					&src_data->r_branch);
+					&src_data->r_branch, out);
 		}
 		if (src_data->tag.nr) {
-			printf(subsep);
+			strbuf_addstr(out, subsep);
 			subsep = ", ";
-			print_joined("tag ", "tags ", &src_data->tag);
+			print_joined("tag ", "tags ", &src_data->tag, out);
 		}
 		if (src_data->generic.nr) {
-			printf(subsep);
-			print_joined("commit ", "commits ", &src_data->generic);
+			strbuf_addstr(out, subsep);
+			print_joined("commit ", "commits ", &src_data->generic,
+					out);
 		}
 		if (strcmp(".", srcs.list[i]))
-			printf(" of %s", srcs.list[i]);
+			strbuf_addf(out, " of %s", srcs.list[i]);
 	}
 
 	if (!strcmp("master", current_branch))
-		putchar('\n');
+		strbuf_addch(out, '\n');
 	else
-		printf(" into %s\n", current_branch);
+		strbuf_addf(out, " into %s\n", current_branch);
 
 	if (merge_summary) {
 		struct commit *head;
 		struct rev_info rev;
 
 		head = lookup_commit(head_sha1);
-		init_revisions(&rev, prefix);
+		init_revisions(&rev, NULL);
 		rev.commit_format = CMIT_FMT_ONELINE;
 		rev.ignore_merges = 1;
 		rev.limited = 1;
 
 		for (i = 0; i < origins.nr; i++)
 			shortlog(origins.list[i], origins.payload[i],
-					head, &rev, limit);
+					head, &rev, limit, out);
 	}
+	return 0;
+}
+
+int cmd_fmt_merge_msg(int argc, const char **argv, const char *prefix)
+{
+	FILE *in = stdin;
+	struct strbuf input, output;
+	int ret;
+
+	git_config(fmt_merge_msg_config, NULL);
+
+	while (argc > 1) {
+		if (!strcmp(argv[1], "--log") || !strcmp(argv[1], "--summary"))
+			merge_summary = 1;
+		else if (!strcmp(argv[1], "--no-log")
+				|| !strcmp(argv[1], "--no-summary"))
+			merge_summary = 0;
+		else if (!strcmp(argv[1], "-F") || !strcmp(argv[1], "--file")) {
+			if (argc < 3)
+				die ("Which file?");
+			if (!strcmp(argv[2], "-"))
+				in = stdin;
+			else {
+				fclose(in);
+				in = fopen(argv[2], "r");
+				if (!in)
+					die("cannot open %s", argv[2]);
+			}
+			argc--; argv++;
+		} else
+			break;
+		argc--; argv++;
+	}
+
+	if (argc > 1)
+		usage(fmt_merge_msg_usage);
 
-	/* No cleanup yet; is standalone anyway */
+	strbuf_init(&input, 0);
+	if (strbuf_read(&input, fileno(in), 0) < 0)
+		die("could not read input file %s", strerror(errno));
+	strbuf_init(&output, 0);
 
+	ret = fmt_merge_msg(merge_summary, &input, &output);
+	if (ret)
+		return ret;
+	printf("%s", output.buf);
 	return 0;
 }
diff --git a/builtin.h b/builtin.h
index b460b2d..2b01fea 100644
--- a/builtin.h
+++ b/builtin.h
@@ -2,6 +2,7 @@
 #define BUILTIN_H
 
 #include "git-compat-util.h"
+#include "strbuf.h"
 
 extern const char git_version_string[];
 extern const char git_usage_string[];
@@ -11,6 +12,8 @@ extern void list_common_cmds_help(void);
 extern void help_unknown_cmd(const char *cmd);
 extern void prune_packed_objects(int);
 extern int read_line_with_nul(char *buf, int size, FILE *file);
+extern int fmt_merge_msg(int merge_summary, struct strbuf *in,
+	struct strbuf *out);
 
 extern int cmd_add(int argc, const char **argv, const char *prefix);
 extern int cmd_annotate(int argc, const char **argv, const char *prefix);
-- 
1.5.6

[PATCH 08/11] Introduce get_octopus_merge_bases() in commit.c

[Miklos Vajna]

This is like get_merge_bases() but it works for multiple heads, like
show-branch --merge-base.

Signed-off-by: Miklos Vajna <vmiklos@frugalware.org>
---
 commit.c |   27 +++++++++++++++++++++++++++
 commit.h |    1 +
 2 files changed, 28 insertions(+), 0 deletions(-)

diff --git a/commit.c b/commit.c
index bbf9c75..6052ca3 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 7f8c5ee..dcec7fb 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);
-- 
1.5.6

[PATCH 09/11] Introduce filter_independent() in commit.c

[Miklos Vajna]

This is similar to git-show-branch --independent: It filters out commits
which are reachable from any other item from the input list.

Signed-off-by: Miklos Vajna <vmiklos@frugalware.org>
---
 commit.c |   16 ++++++++++++++++
 commit.h |    1 +
 2 files changed, 17 insertions(+), 0 deletions(-)

diff --git a/commit.c b/commit.c
index 6052ca3..0dbf4b7 100644
--- a/commit.c
+++ b/commit.c
@@ -705,3 +705,19 @@ int in_merge_bases(struct commit *commit, struct commit **reference, int num)
 	free_commit_list(bases);
 	return ret;
 }
+
+struct commit_list *filter_independent(unsigned char *head,
+	struct commit_list *heads)
+{
+	struct commit_list *i, *bases, *ret = NULL;
+	struct commit_list **pptr = &ret;
+
+	commit_list_insert(lookup_commit(head), &heads);
+
+	bases = get_octopus_merge_bases(heads);
+
+	for (i = heads; i; i = i->next)
+		if (!(i->item->object.flags & RESULT))
+			pptr = &commit_list_insert(i->item, pptr)->next;
+	return ret;
+}
diff --git a/commit.h b/commit.h
index dcec7fb..0aef7e4 100644
--- a/commit.h
+++ b/commit.h
@@ -131,6 +131,7 @@ extern struct commit_list *get_shallow_commits(struct object_array *heads,
 		int depth, int shallow_flag, int not_shallow_flag);
 
 int in_merge_bases(struct commit *, struct commit **, int);
+struct commit_list *filter_independent(unsigned char *head, struct commit_list *heads);
 
 extern int interactive_add(int argc, const char **argv, const char *prefix);
 extern int rerere(void);
-- 
1.5.6

[PATCH 10/11] Build in merge

[Miklos Vajna]

Mentored-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>
Signed-off-by: Miklos Vajna <vmiklos@frugalware.org>
---
 Makefile                                      |    2 +-
 builtin-merge.c                               | 1128 +++++++++++++++++++++++++
 builtin.h                                     |    1 +
 git-merge.sh => contrib/examples/git-merge.sh |    0 
 git.c                                         |    1 +
 5 files changed, 1131 insertions(+), 1 deletions(-)
 create mode 100644 builtin-merge.c
 rename git-merge.sh => contrib/examples/git-merge.sh (100%)

diff --git a/Makefile b/Makefile
index b003e3e..3d8c3d2 100644
--- a/Makefile
+++ b/Makefile
@@ -240,7 +240,6 @@ SCRIPT_SH += git-lost-found.sh
 SCRIPT_SH += git-merge-octopus.sh
 SCRIPT_SH += git-merge-one-file.sh
 SCRIPT_SH += git-merge-resolve.sh
-SCRIPT_SH += git-merge.sh
 SCRIPT_SH += git-merge-stupid.sh
 SCRIPT_SH += git-mergetool.sh
 SCRIPT_SH += git-parse-remote.sh
@@ -511,6 +510,7 @@ BUILTIN_OBJS += builtin-ls-remote.o
 BUILTIN_OBJS += builtin-ls-tree.o
 BUILTIN_OBJS += builtin-mailinfo.o
 BUILTIN_OBJS += builtin-mailsplit.o
+BUILTIN_OBJS += builtin-merge.o
 BUILTIN_OBJS += builtin-merge-base.o
 BUILTIN_OBJS += builtin-merge-file.o
 BUILTIN_OBJS += builtin-merge-ours.o
diff --git a/builtin-merge.c b/builtin-merge.c
new file mode 100644
index 0000000..cc6b88b
--- /dev/null
+++ b/builtin-merge.c
@@ -0,0 +1,1128 @@
+/*
+ * Builtin "git merge"
+ *
+ * Copyright (c) 2008 Miklos Vajna <vmiklos@frugalware.org>
+ *
+ * Based on git-merge.sh by Junio C Hamano.
+ */
+
+#include "cache.h"
+#include "parse-options.h"
+#include "builtin.h"
+#include "run-command.h"
+#include "path-list.h"
+#include "diff.h"
+#include "refs.h"
+#include "commit.h"
+#include "diffcore.h"
+#include "revision.h"
+#include "unpack-trees.h"
+#include "cache-tree.h"
+#include "dir.h"
+#include "utf8.h"
+#include "log-tree.h"
+
+enum strategy {
+	DEFAULT_TWOHEAD = 1,
+	DEFAULT_OCTOPUS = 2,
+	NO_FAST_FORWARD = 4,
+	NO_TRIVIAL = 8
+};
+
+static const char * const builtin_merge_usage[] = {
+	"git-merge [options] <remote>...",
+	"git-merge [options] <msg> HEAD <remote>",
+	NULL
+};
+
+static int show_diffstat = 1, option_log, squash;
+static int option_commit = 1, allow_fast_forward = 1;
+static int allow_trivial = 1, have_message;
+static struct strbuf merge_msg;
+static struct commit_list *remoteheads;
+static unsigned char head[20];
+static struct path_list use_strategies;
+static const char *branch;
+
+static struct path_list_item strategy_items[] = {
+	{ "recur",      (void *)NO_TRIVIAL },
+	{ "recursive",  (void *)(DEFAULT_TWOHEAD | NO_TRIVIAL) },
+	{ "octopus",    (void *)DEFAULT_OCTOPUS },
+	{ "resolve",    (void *)0 },
+	{ "stupid",     (void *)0 },
+	{ "ours",       (void *)(NO_FAST_FORWARD | NO_TRIVIAL) },
+	{ "subtree",    (void *)(NO_FAST_FORWARD | NO_TRIVIAL) },
+};
+static struct path_list strategies = { strategy_items,
+	ARRAY_SIZE(strategy_items), 0, 0 };
+
+static const char *pull_twohead, *pull_octopus;
+
+static int option_parse_message(const struct option *opt,
+	const char *arg, int unset)
+{
+	struct strbuf *buf = opt->value;
+
+	if (unset)
+		strbuf_setlen(buf, 0);
+	else {
+		strbuf_addstr(buf, arg);
+		have_message = 1;
+	}
+	return 0;
+}
+
+static struct path_list_item *unsorted_path_list_lookup(const char *path,
+	struct path_list *list)
+{
+	int i;
+
+	if (!path)
+		return NULL;
+
+	for (i = 0; i < list->nr; i++)
+		if (!strcmp(path, list->items[i].path))
+			return &list->items[i];
+	return NULL;
+}
+
+static inline void path_list_append_strategy(const char *path, void *util,
+	struct path_list *list)
+{
+	path_list_append(path, list)->util = util;
+}
+
+static int option_parse_strategy(const struct option *opt,
+	const char *arg, int unset)
+{
+	int i;
+	struct path_list *list = opt->value;
+	struct path_list_item *item =
+		unsorted_path_list_lookup(arg, &strategies);
+
+	if (unset)
+		return 0;
+
+	if (item)
+		path_list_append_strategy(arg, item->util, list);
+	else {
+		struct strbuf err;
+		strbuf_init(&err, 0);
+		for (i = 0; i < strategies.nr; i++)
+			strbuf_addf(&err, " %s", strategies.items[i].path);
+		fprintf(stderr, "Could not find merge strategy '%s'.\n", arg);
+		fprintf(stderr, "Available strategies are:%s.\n", err.buf);
+		exit(1);
+	}
+	return 0;
+}
+
+static int option_parse_n(const struct option *opt,
+		const char *arg, int unset)
+{
+	show_diffstat = unset;
+	return 0;
+}
+
+static struct option builtin_merge_options[] = {
+	{ OPTION_CALLBACK, 'n', NULL, NULL, NULL,
+		"do not show a diffstat at the end of the merge",
+		PARSE_OPT_NOARG, option_parse_n },
+	OPT_BOOLEAN(0, "stat", &show_diffstat,
+		"show a diffstat at the end of the merge"),
+	OPT_BOOLEAN(0, "summary", &show_diffstat, "(synonym to --stat)"),
+	OPT_BOOLEAN(0, "log", &option_log,
+		"add list of one-line log to merge commit message"),
+	OPT_BOOLEAN(0, "squash", &squash,
+		"create a single commit instead of doing a merge"),
+	OPT_BOOLEAN(0, "commit", &option_commit,
+		"perform a commit if the merge sucesses (default)"),
+	OPT_BOOLEAN(0, "ff", &allow_fast_forward,
+		"allow fast forward (default)"),
+	OPT_CALLBACK('s', "strategy", &use_strategies, "strategy",
+		"merge strategy to use", option_parse_strategy),
+	OPT_CALLBACK('m', "message", &merge_msg, "message",
+		"message to be used for the merge commit (if any)",
+		option_parse_message),
+	OPT_END()
+};
+
+/* Cleans up metadata that is uninteresting after a succeeded merge. */
+static void dropsave()
+{
+	unlink(git_path("MERGE_HEAD"));
+	unlink(git_path("MERGE_MSG"));
+	unlink(git_path("MERGE_STASH"));
+}
+
+static void save_state()
+{
+	int fd;
+	struct child_process stash;
+	const char *argv[] = {"stash", "create", NULL};
+
+	fd = open(git_path("MERGE_STASH"), O_WRONLY | O_CREAT, 0666);
+	if (fd < 0)
+		die("Could not write to %s", git_path("MERGE_STASH"));
+	memset(&stash, 0, sizeof(stash));
+	stash.argv = argv;
+	stash.out = fd;
+	stash.git_cmd = 1;
+	run_command(&stash);
+}
+
+static void reset_hard(unsigned const char *sha1, int verbose)
+{
+	struct tree *tree;
+	struct unpack_trees_options opts;
+	struct tree_desc t;
+
+	memset(&opts, 0, sizeof(opts));
+	opts.head_idx = -1;
+	opts.src_index = &the_index;
+	opts.dst_index = &the_index;
+	opts.update = 1;
+	opts.reset = 1;
+	if (verbose)
+		opts.verbose_update = 1;
+
+	tree = parse_tree_indirect(sha1);
+	if (!tree)
+		die("failed to unpack %s tree object", sha1_to_hex(sha1));
+	parse_tree(tree);
+	init_tree_desc(&t, tree->buffer, tree->size);
+	if (unpack_trees(1, &t, &opts))
+		exit(128); /* We've already reported the error, finish dying */
+}
+
+static void restore_state()
+{
+	struct strbuf sb;
+	const char *args[] = { "stash", "apply", NULL, NULL };
+
+	if (access(git_path("MERGE_STASH"), R_OK) < 0)
+		return;
+
+	reset_hard(head, 1);
+
+	strbuf_init(&sb, 0);
+	if (strbuf_read_file(&sb, git_path("MERGE_STASH"), 0) < 0)
+		die("could not read MERGE_STASH: %s", strerror(errno));
+	args[2] = sb.buf;
+
+	/*
+	 * It is OK to ignore error here, for example when there was
+	 * nothing to restore.
+	 */
+	run_command_v_opt(args, RUN_GIT_CMD);
+
+	refresh_cache(REFRESH_QUIET);
+}
+
+/* This is called when no merge was necessary. */
+static void finish_up_to_date(const char *msg)
+{
+	if (squash)
+		printf("%s (nothing to squash)\n", msg);
+	else
+		printf("%s\n", msg);
+	dropsave();
+}
+
+static void squash_message(int out_fd)
+{
+	struct rev_info rev;
+	struct commit *commit;
+	struct strbuf out;
+	struct commit_list *j;
+
+	init_revisions(&rev, NULL);
+	rev.ignore_merges = 1;
+	rev.commit_format = CMIT_FMT_MEDIUM;
+
+	commit = lookup_commit(head);
+	commit->object.flags |= UNINTERESTING;
+	add_pending_object(&rev, &commit->object, NULL);
+
+	for (j = remoteheads; j; j = j->next) {
+		j->item->object.flags &= ~UNINTERESTING;
+		add_pending_object(&rev, &j->item->object, NULL);
+	}
+
+	setup_revisions(0, NULL, &rev, NULL);
+	if (prepare_revision_walk(&rev))
+		die("revision walk setup failed");
+
+	strbuf_init(&out, 0);
+	strbuf_addstr(&out, "Squashed commit of the following:\n");
+	while ((commit = get_revision(&rev)) != NULL) {
+		strbuf_addch(&out, '\n');
+		strbuf_addf(&out, "commit %s\n",
+			sha1_to_hex(commit->object.sha1));
+		pretty_print_commit(rev.commit_format, commit, &out, rev.abbrev,
+			NULL, NULL, rev.date_mode, 0);
+	}
+	write(out_fd, out.buf, out.len);
+	strbuf_release(&out);
+}
+
+static int run_hook(const char *name)
+{
+	struct child_process hook;
+	const char *argv[3], *env[2];
+	char index[PATH_MAX];
+
+	snprintf(index, sizeof(index), "GIT_INDEX_FILE=%s", get_index_file());
+	env[0] = index;
+	env[1] = NULL;
+
+	argv[0] = git_path("hooks/%s", name);
+	if (squash)
+		argv[1] = "1";
+	else
+		argv[1] = "0";
+	argv[2] = NULL;
+
+	if (access(argv[0], X_OK) < 0)
+		return 0;
+
+	memset(&hook, 0, sizeof(hook));
+	hook.argv = argv;
+	hook.no_stdin = 1;
+	hook.stdout_to_stderr = 1;
+	hook.env = env;
+
+	return run_command(&hook);
+}
+
+static void finish(const unsigned char *new_head, const char *msg)
+{
+	struct strbuf reflog_message;
+	const char *argv_gc_auto[] = { "gc", "--auto", NULL };
+	struct diff_options opts;
+
+	strbuf_init(&reflog_message, 0);
+	if (!msg)
+		strbuf_addstr(&reflog_message, getenv("GIT_REFLOG_ACTION"));
+	else {
+		printf("%s\n", msg);
+		strbuf_addf(&reflog_message, "%s: %s",
+			getenv("GIT_REFLOG_ACTION"), msg);
+	}
+	if (squash) {
+		int fd;
+		printf("Squash commit -- not updating HEAD\n");
+		fd = open(git_path("SQUASH_MSG"), O_WRONLY | O_CREAT, 0666);
+		if (fd < 0)
+			die("Could not write to %s", git_path("SQUASH_MSG"));
+		squash_message(fd);
+		close(fd);
+	} else {
+		if (!merge_msg.len)
+			printf("No merge message -- not updating HEAD\n");
+		else {
+			update_ref(reflog_message.buf, "HEAD",
+				new_head, head, 0,
+				DIE_ON_ERR);
+			/*
+			 * We ignore errors in 'gc --auto', since the
+			 * user should see them.
+			 */
+			run_command_v_opt(argv_gc_auto, RUN_GIT_CMD);
+		}
+	}
+	if (new_head && show_diffstat) {
+		diff_setup(&opts);
+		opts.output_format |=
+			DIFF_FORMAT_SUMMARY | DIFF_FORMAT_DIFFSTAT;
+		opts.detect_rename = DIFF_DETECT_RENAME;
+		diff_tree_sha1(head, new_head, "", &opts);
+		diffcore_std(&opts);
+		diff_flush(&opts);
+	}
+
+	/* Run a post-merge hook */
+	run_hook("post-merge");
+
+	strbuf_release(&reflog_message);
+}
+
+/* Get the name for the merge commit's message. */
+static void merge_name(const char *remote, struct strbuf *msg)
+{
+	struct object *remote_head;
+	unsigned char branch_head[20], buf_sha[20];
+	struct strbuf buf;
+	char *ptr;
+	int match = 0;
+
+	memset(branch_head, 0, sizeof(branch_head));
+	remote_head = peel_to_type(remote, 0, NULL, OBJ_COMMIT);
+	if (!remote_head)
+		return;
+
+	strbuf_init(&buf, 0);
+	strbuf_addstr(&buf, "refs/heads/");
+	strbuf_addstr(&buf, remote);
+	get_sha1(buf.buf, branch_head);
+
+	if (!hashcmp(remote_head->sha1, branch_head)) {
+		strbuf_addf(msg, "%s\t\tbranch '%s' of .\n",
+			sha1_to_hex(branch_head), remote);
+		return;
+	}
+	/* See if remote matches <name>~<number>, or <name>^ */
+	ptr = strrchr(remote, '^');
+	if (ptr && *(ptr+1) == '\0')
+		match = 1;
+	else {
+		ptr = strrchr(remote, '~');
+		if (ptr && *(ptr+1) != '0' && isdigit(*(ptr+1))) {
+			ptr++;
+			match = 1;
+			while (*(++ptr))
+				if (!isdigit(*ptr)) {
+					match = 0;
+					break;
+				}
+		}
+	}
+	if (match) {
+		struct strbuf truname;
+		strbuf_addstr(&truname, remote);
+		strbuf_setlen(&truname, strrchr(truname.buf, '~')-truname.buf);
+		if (!get_sha1(truname.buf, buf_sha)) {
+			strbuf_addf(msg,
+				"%s\t\tbranch '%s' (early part) of .\n",
+				sha1_to_hex(remote_head->sha1), truname.buf);
+			return;
+		}
+	}
+
+	if (!strcmp(remote, "FETCH_HEAD") &&
+		!access(git_path("FETCH_HEAD"), R_OK)) {
+		FILE *fp;
+		struct strbuf line;
+		char *ptr;
+
+		strbuf_init(&line, 0);
+		fp = fopen(git_path("FETCH_HEAD"), "r");
+		if (fp == NULL)
+			die("could not open %s for reading: %s",
+				git_path("FETCH_HEAD"), strerror(errno));
+		strbuf_getline(&line, fp, '\n');
+		fclose(fp);
+		ptr = strstr(line.buf, "\tnot-for-merge\t");
+		if (ptr)
+			strbuf_remove(&line, ptr-line.buf+1, 13);
+		strbuf_addbuf(msg, &line);
+		strbuf_release(&line);
+		return;
+	}
+	strbuf_addf(msg, "%s\t\tcommit '%s'\n",
+		sha1_to_hex(remote_head->sha1), remote);
+}
+
+int git_merge_config(const char *k, const char *v, void *cb)
+{
+	if (branch && !prefixcmp(k, "branch.") &&
+		!prefixcmp(k + 7, branch) &&
+		!strcmp(k + 7 + strlen(branch), ".mergeoptions")) {
+		const char **argv;
+		int argc;
+		char *buf;
+
+		buf = xstrdup(v);
+		argc = split_cmdline(buf, &argv);
+		parse_options(argc, argv, builtin_merge_options,
+				builtin_merge_usage,
+				PARSE_OPT_ARGV0_IS_AN_OPTION);
+		free(buf);
+	}
+
+	if (!strcmp(k, "merge.diffstat") || !strcmp(k, "merge.stat"))
+		show_diffstat = git_config_bool(k, v);
+	else if (!strcmp(k, "pull.twohead"))
+		return git_config_string(&pull_twohead, k, v);
+	else if (!strcmp(k, "pull.octopus"))
+		return git_config_string(&pull_octopus, k, v);
+	return 0;
+}
+
+static int read_tree_trivial(unsigned char *common, unsigned char *head,
+	unsigned char *one)
+{
+	int i, nr_trees = 0;
+	struct tree *trees[MAX_UNPACK_TREES];
+	struct tree_desc t[MAX_UNPACK_TREES];
+	struct unpack_trees_options opts;
+
+	memset(&opts, 0, sizeof(opts));
+	opts.head_idx = -1;
+	opts.src_index = &the_index;
+	opts.dst_index = &the_index;
+	opts.update = 1;
+	opts.verbose_update = 1;
+	opts.trivial_merges_only = 1;
+	opts.merge = 1;
+	trees[nr_trees] = parse_tree_indirect(common);
+	if (!trees[nr_trees++])
+		return -1;
+	trees[nr_trees] = parse_tree_indirect(head);
+	if (!trees[nr_trees++])
+		return -1;
+	trees[nr_trees] = parse_tree_indirect(one);
+	if (!trees[nr_trees++])
+		return -1;
+	opts.fn = threeway_merge;
+	cache_tree_free(&active_cache_tree);
+	opts.head_idx = 2;
+	for (i = 0; i < nr_trees; i++) {
+		parse_tree(trees[i]);
+		init_tree_desc(t+i, trees[i]->buffer, trees[i]->size);
+	}
+	if (unpack_trees(nr_trees, t, &opts))
+		return -1;
+	return 0;
+}
+
+static int commit_tree_trivial(const char *msg, unsigned const char *tree,
+		struct commit_list *parents, unsigned char *ret)
+{
+	struct commit_list *i;
+	struct strbuf buf;
+	int encoding_is_utf8;
+
+	/* Not having i18n.commitencoding is the same as having utf-8 */
+	encoding_is_utf8 = is_encoding_utf8(git_commit_encoding);
+
+	strbuf_init(&buf, 8192); /* should avoid reallocs for the headers */
+	strbuf_addf(&buf, "tree %s\n", sha1_to_hex(tree));
+
+	for (i = parents; i; i = i->next)
+		strbuf_addf(&buf, "parent %s\n",
+			sha1_to_hex(i->item->object.sha1));
+
+	/* Person/date information */
+	strbuf_addf(&buf, "author %s\n",
+		git_author_info(IDENT_ERROR_ON_NO_NAME));
+	strbuf_addf(&buf, "committer %s\n",
+		git_committer_info(IDENT_ERROR_ON_NO_NAME));
+	if (!encoding_is_utf8)
+		strbuf_addf(&buf, "encoding %s\n", git_commit_encoding);
+	strbuf_addch(&buf, '\n');
+
+	/* And add the comment */
+	strbuf_addstr(&buf, msg);
+
+	write_sha1_file(buf.buf, buf.len, commit_type, ret);
+	strbuf_release(&buf);
+	return *ret;
+}
+
+static void write_tree_trivial(unsigned char *sha1)
+{
+	if (write_cache_as_tree(sha1, 0, NULL))
+		die("git write-tree failed to write a tree");
+}
+
+static int try_merge_strategy(char *strategy, struct commit_list *common,
+	struct strbuf *head_arg)
+{
+	const char **args;
+	int i = 0, ret;
+	struct commit_list *j;
+	struct strbuf buf;
+
+	args = xmalloc((4 + commit_list_count(common) +
+			commit_list_count(remoteheads)) * sizeof(char *));
+	strbuf_init(&buf, 0);
+	strbuf_addf(&buf, "merge-%s", strategy);
+	args[i++] = buf.buf;
+	for (j = common; j; j = j->next)
+		args[i++] = xstrdup(sha1_to_hex(j->item->object.sha1));
+	args[i++] = "--";
+	args[i++] = head_arg->buf;
+	for (j = remoteheads; j; j = j->next)
+		args[i++] = xstrdup(sha1_to_hex(j->item->object.sha1));
+	args[i] = NULL;
+	ret = run_command_v_opt(args, RUN_GIT_CMD);
+	strbuf_release(&buf);
+	i = 1;
+	for (j = common; j; j = j->next)
+		free((void *)args[i++]);
+	i += 2;
+	for (j = remoteheads; j; j = j->next)
+		free((void *)args[i++]);
+	free(args);
+	return -ret;
+}
+
+static void count_diff_files(struct diff_queue_struct *q,
+		struct diff_options *opt, void *data)
+{
+	int *count = data;
+
+	(*count) += q->nr;
+}
+
+static int count_unmerged_entries(void)
+{
+	const struct index_state *state = &the_index;
+	int i, ret = 0;
+
+	for (i = 0; i < state->cache_nr; i++)
+		if (ce_stage(state->cache[i]))
+			ret++;
+
+	return ret;
+}
+
+static int merge_one_remote(unsigned char *head, unsigned char *remote)
+{
+	struct tree *trees[MAX_UNPACK_TREES];
+	struct unpack_trees_options opts;
+	struct tree_desc t[MAX_UNPACK_TREES];
+	int i, fd, nr_trees = 0;
+	struct dir_struct *dir;
+	struct lock_file lock_file;
+
+	memset(&lock_file, 0, sizeof(lock_file));
+	if (read_cache_unmerged())
+		die("you need to resolve your current index first");
+
+	fd = hold_locked_index(&lock_file, 1);
+
+	memset(&trees, 0, sizeof(trees));
+	memset(&opts, 0, sizeof(opts));
+	memset(&t, 0, sizeof(t));
+	dir = xcalloc(1, sizeof(*opts.dir));
+	dir->show_ignored = 1;
+	dir->exclude_per_dir = ".gitignore";
+	opts.dir = dir;
+
+	opts.head_idx = 1;
+	opts.src_index = &the_index;
+	opts.dst_index = &the_index;
+	opts.update = 1;
+	opts.verbose_update = 1;
+	opts.merge = 1;
+	opts.fn = twoway_merge;
+
+	trees[nr_trees] = parse_tree_indirect(head);
+	if (!trees[nr_trees++])
+		return -1;
+	trees[nr_trees] = parse_tree_indirect(remote);
+	if (!trees[nr_trees++])
+		return -1;
+	for (i = 0; i < nr_trees; i++) {
+		parse_tree(trees[i]);
+		init_tree_desc(t+i, trees[i]->buffer, trees[i]->size);
+	}
+	if (unpack_trees(nr_trees, t, &opts))
+		return -1;
+	if (write_cache(fd, active_cache, active_nr) ||
+		commit_locked_index(&lock_file))
+		die("unable to write new index file");
+	return 0;
+}
+
+static void split_merge_strategies(const char *string, struct path_list *list)
+{
+	char *p, *q, *buf;
+
+	if (!string)
+		return;
+
+	list->strdup_paths = 1;
+	buf = xstrdup(string);
+	q = buf;
+	while (1) {
+		p = strchr(q, ' ');
+		if (!p) {
+			path_list_append(q, list);
+			free(buf);
+			return;
+		} else {
+			*p = '\0';
+			path_list_append(q, list);
+			q = ++p;
+		}
+	}
+}
+
+static void add_strategies(const char *string, enum strategy strategy)
+{
+	struct path_list list;
+	int i;
+
+	memset(&list, 0, sizeof(list));
+	split_merge_strategies(string, &list);
+	if (list.nr) {
+		for (i = 0; i < list.nr; i++) {
+			struct path_list_item *item;
+
+			item = unsorted_path_list_lookup(list.items[i].path,
+				&strategies);
+			if (item)
+				path_list_append_strategy(list.items[i].path,
+					item->util, &use_strategies);
+		}
+		return;
+	}
+	for (i = 0; i < strategies.nr; i++)
+		if ((enum strategy)strategies.items[i].util & strategy)
+			path_list_append_strategy(strategies.items[i].path,
+				strategies.items[i].util,
+				&use_strategies);
+}
+
+int cmd_merge(int argc, const char **argv, const char *prefix)
+{
+	unsigned char sha1[20], result_tree[20];
+	struct object *second_token = NULL;
+	struct strbuf buf, head_arg;
+	int flag, head_invalid, i, single_strategy;
+	int best_cnt = -1, merge_was_ok = 0, automerge_was_ok = 0;
+	struct commit_list *common = NULL;
+	struct path_list_item *best_strategy = NULL, *wt_strategy = NULL;
+	struct commit_list **remotes = &remoteheads;
+
+	setup_work_tree();
+	if (unmerged_cache())
+		die("You are in the middle of a conflicted merge.");
+
+	/*
+	 * Check if we are _not_ on a detached HEAD, i.e. if there is a
+	 * current branch.
+	 */
+	branch = resolve_ref("HEAD", sha1, 0, &flag);
+	if (branch && flag & REF_ISSYMREF) {
+		const char *ptr = skip_prefix(branch, "refs/heads/");
+		if (ptr)
+			branch = ptr;
+	}
+
+	git_config(git_merge_config, NULL);
+
+	argc = parse_options(argc, argv, builtin_merge_options,
+			builtin_merge_usage, 0);
+
+	if (squash) {
+		if (!allow_fast_forward)
+			die("You cannot combine --squash with --no-ff.");
+		option_commit = 0;
+	}
+
+	if (argc == 0)
+		usage_with_options(builtin_merge_usage,
+			builtin_merge_options);
+
+	/*
+	 * This could be traditional "merge <msg> HEAD <commit>..."  and
+	 * the way we can tell it is to see if the second token is HEAD,
+	 * but some people might have misused the interface and used a
+	 * committish that is the same as HEAD there instead.
+	 * Traditional format never would have "-m" so it is an
+	 * additional safety measure to check for it.
+	 */
+	strbuf_init(&buf, 0);
+	strbuf_init(&head_arg, 0);
+	if (argc > 1)
+		second_token = peel_to_type(argv[1], 0, NULL, OBJ_COMMIT);
+	head_invalid = get_sha1("HEAD", head);
+
+	if (!have_message && second_token &&
+		!hashcmp(second_token->sha1, head)) {
+		strbuf_addstr(&merge_msg, argv[0]);
+		strbuf_addstr(&head_arg, argv[1]);
+		argv += 2;
+		argc -= 2;
+	} else if (head_invalid) {
+		struct object *remote_head;
+		/*
+		 * If the merged head is a valid one there is no reason
+		 * to forbid "git merge" into a branch yet to be born.
+		 * We do the same for "git pull".
+		 */
+		if (argc != 1)
+			die("Can merge only exactly one commit into "
+				"empty head");
+		remote_head = peel_to_type(argv[0], 0, NULL, OBJ_COMMIT);
+		if (!remote_head)
+			die("%s - not something we can merge", argv[0]);
+		update_ref("initial pull", "HEAD", remote_head->sha1, NULL, 0,
+				DIE_ON_ERR);
+		reset_hard(remote_head->sha1, 0);
+		return 0;
+	} else {
+		/* We are invoked directly as the first-class UI. */
+		strbuf_addstr(&head_arg, "HEAD");
+		if (!merge_msg.len) {
+			/*
+			 * All the rest are the commits being merged;
+			 * prepare the standard merge summary message to
+			 * be appended to the given message.  If remote
+			 * is invalid we will die later in the common
+			 * codepath so we discard the error in this
+			 * loop.
+			 */
+			struct strbuf msg;
+
+			strbuf_init(&msg, 0);
+			for (i = 0; i < argc; i++)
+				merge_name(argv[i], &msg);
+			fmt_merge_msg(option_log, &msg, &merge_msg);
+			if (merge_msg.len)
+				strbuf_setlen(&merge_msg, merge_msg.len-1);
+		}
+	}
+
+	if (head_invalid || argc == 0)
+		usage_with_options(builtin_merge_usage,
+			builtin_merge_options);
+
+	strbuf_addstr(&buf, "merge");
+	for (i = 0; i < argc; i++)
+		strbuf_addf(&buf, " %s", argv[i]);
+	setenv("GIT_REFLOG_ACTION", buf.buf, 0);
+	strbuf_reset(&buf);
+
+	for (i = 0; i < argc; i++) {
+		struct object *o;
+
+		o = peel_to_type(argv[i], 0, NULL, OBJ_COMMIT);
+		if (!o)
+			die("%s - not something we can merge", argv[i]);
+		remotes = &commit_list_insert(lookup_commit(o->sha1),
+			remotes)->next;
+
+		strbuf_addf(&buf, "GITHEAD_%s", sha1_to_hex(o->sha1));
+		setenv(buf.buf, argv[i], 1);
+		strbuf_reset(&buf);
+	}
+
+	if (!use_strategies.nr) {
+		if (!remoteheads->next)
+			add_strategies(pull_twohead, DEFAULT_TWOHEAD);
+		else
+			add_strategies(pull_octopus, DEFAULT_OCTOPUS);
+	}
+
+	for (i = 0; i < use_strategies.nr; i++) {
+		if ((unsigned int)use_strategies.items[i].util &
+			NO_FAST_FORWARD)
+			allow_fast_forward = 0;
+		if ((unsigned int)use_strategies.items[i].util & NO_TRIVIAL)
+			allow_trivial = 0;
+	}
+
+	if (!remoteheads->next)
+		common = get_merge_bases(lookup_commit(head),
+				remoteheads->item, 1);
+	else {
+		struct commit_list *list = remoteheads;
+		commit_list_insert(lookup_commit(head), &list);
+		common = get_octopus_merge_bases(list);
+	}
+
+	update_ref("updating ORIG_HEAD", "ORIG_HEAD", head, NULL, 0,
+		DIE_ON_ERR);
+
+	if (!common)
+		; /* No common ancestors found. We need a real merge. */
+	else if (!remoteheads->next &&
+		!hashcmp(common->item->object.sha1,
+		remoteheads->item->object.sha1)) {
+		/*
+		 * If head can reach all the merge then we are up to
+		 * date.
+		 */
+		finish_up_to_date("Already up-to-date.");
+		return 0;
+	} else if (allow_fast_forward && !remoteheads->next &&
+		!hashcmp(common->item->object.sha1, head)) {
+		/* Again the most common case of merging one remote. */
+		struct strbuf msg;
+		struct object *o;
+
+		printf("Updating %s..%s\n",
+			find_unique_abbrev(head, DEFAULT_ABBREV),
+			find_unique_abbrev(remoteheads->item->object.sha1,
+			DEFAULT_ABBREV));
+		refresh_cache(REFRESH_QUIET);
+		strbuf_init(&msg, 0);
+		strbuf_addstr(&msg, "Fast forward");
+		if (have_message)
+			strbuf_addstr(&msg,
+				" (no commit created; -m option ignored)");
+		o = peel_to_type(sha1_to_hex(remoteheads->item->object.sha1),
+			0, NULL, OBJ_COMMIT);
+		if (!o)
+			return 0;
+
+		if (merge_one_remote(head, remoteheads->item->object.sha1))
+			return 0;
+
+		finish(o->sha1, msg.buf);
+		dropsave();
+		return 0;
+	} else if (!remoteheads->next && common->next)
+		;
+		/*
+		 * We are not doing octopus and not fast forward.  Need
+		 * a real merge.
+		 */
+	else if (!remoteheads->next && option_commit) {
+		/*
+		 * We are not doing octopus and not fast forward.  Need
+		 * a real merge.
+		 */
+		refresh_cache(REFRESH_QUIET);
+		if (allow_trivial) {
+			/* See if it is really trivial. */
+			git_committer_info(IDENT_ERROR_ON_NO_NAME);
+			printf("Trying really trivial in-index merge...\n");
+			if (!read_tree_trivial(common->item->object.sha1,
+					head, remoteheads->item->object.sha1)) {
+				unsigned char result_tree[20],
+					result_commit[20];
+				struct commit_list parent;
+
+				write_tree_trivial(result_tree);
+				printf("Wonderful.\n");
+				parent.item = remoteheads->item;
+				parent.next = NULL;
+				commit_tree_trivial(merge_msg.buf,
+					result_tree, &parent,
+					result_commit);
+				finish(result_commit, "In-index merge");
+				dropsave();
+				return 0;
+			}
+			printf("Nope.\n");
+		}
+	} else {
+		/*
+		 * An octopus.  If we can reach all the remote we are up
+		 * to date.
+		 */
+		int up_to_date = 1;
+		struct commit_list *j;
+
+		for (j = remoteheads; j; j = j->next) {
+			struct commit_list *common_one;
+
+			common_one = get_merge_bases(lookup_commit(head),
+				j->item, 1);
+			if (hashcmp(common_one->item->object.sha1,
+				j->item->object.sha1)) {
+				up_to_date = 0;
+				break;
+			}
+		}
+		if (up_to_date) {
+			finish_up_to_date("Already up-to-date. Yeeah!");
+			return 0;
+		}
+	}
+
+	/* We are going to make a new commit. */
+	git_committer_info(IDENT_ERROR_ON_NO_NAME);
+
+	/*
+	 * At this point, we need a real merge.  No matter what strategy
+	 * we use, it would operate on the index, possibly affecting the
+	 * working tree, and when resolved cleanly, have the desired
+	 * tree in the index -- this means that the index must be in
+	 * sync with the head commit.  The strategies are responsible
+	 * to ensure this.
+	 */
+	if (use_strategies.nr != 1) {
+		/*
+		 * Stash away the local changes so that we can try more
+		 * than one.
+		 */
+		save_state();
+		single_strategy = 0;
+	} else {
+		unlink(git_path("MERGE_STASH"));
+		single_strategy = 1;
+	}
+
+	for (i = 0; i < use_strategies.nr; i++) {
+		int ret;
+		if (i) {
+			printf("Rewinding the tree to pristine...\n");
+			restore_state();
+		}
+		if (!single_strategy)
+			printf("Trying merge strategy %s...\n",
+				use_strategies.items[i].path);
+		/*
+		 * Remember which strategy left the state in the working
+		 * tree.
+		 */
+		wt_strategy = &use_strategies.items[i];
+
+		ret = try_merge_strategy(use_strategies.items[i].path,
+			common, &head_arg);
+		if (!option_commit && !ret) {
+			merge_was_ok = 1;
+			ret = 1;
+		}
+
+		if (ret) {
+			/*
+			 * The backend exits with 1 when conflicts are
+			 * left to be resolved, with 2 when it does not
+			 * handle the given merge at all.
+			 */
+			if (ret == 1) {
+				int cnt = 0;
+				struct rev_info rev;
+
+				if (read_cache() < 0)
+					die("failed to read the cache");
+
+				/* Check how many files differ. */
+				init_revisions(&rev, "");
+				setup_revisions(0, NULL, &rev, NULL);
+				rev.diffopt.output_format |=
+					DIFF_FORMAT_CALLBACK;
+				rev.diffopt.format_callback = count_diff_files;
+				rev.diffopt.format_callback_data = &cnt;
+				run_diff_files(&rev, 0);
+
+				/*
+				 * Check how many unmerged entries are
+				 * there.
+				 */
+				cnt += count_unmerged_entries();
+
+				if (best_cnt <= 0 || cnt <= best_cnt) {
+					best_strategy =
+						&use_strategies.items[i];
+					best_cnt = cnt;
+				}
+			}
+			continue;
+		}
+
+		/* Automerge succeeded. */
+		write_tree_trivial(result_tree);
+		automerge_was_ok = 1;
+		break;
+	}
+
+	/*
+	 * If we have a resulting tree, that means the strategy module
+	 * auto resolved the merge cleanly.
+	 */
+	if (automerge_was_ok) {
+		struct commit_list *parents = NULL, *j;
+		unsigned char result_commit[20];
+
+		free_commit_list(common);
+		if (allow_fast_forward)
+			parents = filter_independent(head, remoteheads);
+		else {
+			struct commit_list **pptr = &parents;
+
+			pptr = &commit_list_insert(lookup_commit(head),
+				pptr)->next;
+			for (j = remoteheads; j; j = j->next)
+				pptr = &commit_list_insert(j->item, pptr)->next;
+		}
+		free_commit_list(remoteheads);
+		strbuf_addch(&merge_msg, '\n');
+		commit_tree_trivial(merge_msg.buf, result_tree, parents,
+			result_commit);
+		free_commit_list(parents);
+		strbuf_addf(&buf, "Merge made by %s.", wt_strategy->path);
+		finish(result_commit, buf.buf);
+		strbuf_release(&buf);
+		dropsave();
+		return 0;
+	}
+
+	/*
+	 * Pick the result from the best strategy and have the user fix
+	 * it up.
+	 */
+	if (!best_strategy) {
+		restore_state();
+		if (use_strategies.nr > 1)
+			fprintf(stderr,
+				"No merge strategy handled the merge.\n");
+		else
+			fprintf(stderr, "Merge with strategy %s failed.\n",
+				use_strategies.items[0].path);
+		return 2;
+	} else if (best_strategy == wt_strategy)
+		; /* We already have its result in the working tree. */
+	else {
+		printf("Rewinding the tree to pristine...\n");
+		restore_state();
+		printf("Using the %s to prepare resolving by hand.\n",
+			best_strategy->path);
+		try_merge_strategy(best_strategy->path, common, &head_arg);
+	}
+
+	if (squash)
+		finish(NULL, NULL);
+	else {
+		int fd;
+		struct commit_list *j;
+
+		for (j = remoteheads; j; j = j->next)
+			strbuf_addf(&buf, "%s\n",
+				sha1_to_hex(j->item->object.sha1));
+		fd = open(git_path("MERGE_HEAD"), O_WRONLY | O_CREAT, 0666);
+		if (fd < 0)
+			die("Could open %s for writing",
+				git_path("MERGE_HEAD"));
+		if (write_in_full(fd, buf.buf, buf.len) != buf.len)
+			die("Could not write to %s", git_path("MERGE_HEAD"));
+		close(fd);
+		strbuf_addch(&merge_msg, '\n');
+		fd = open(git_path("MERGE_MSG"), O_WRONLY | O_CREAT, 0666);
+		if (fd < 0)
+			die("Could open %s for writing", git_path("MERGE_MSG"));
+		if (write_in_full(fd, merge_msg.buf, merge_msg.len) !=
+			merge_msg.len)
+			die("Could not write to %s", git_path("MERGE_MSG"));
+		close(fd);
+	}
+
+	if (merge_was_ok) {
+		fprintf(stderr, "Automatic merge went well; "
+			"stopped before committing as requested\n");
+		return 0;
+	} else {
+		FILE *fp;
+		int pos;
+		const char *argv_rerere[] = { "rerere", NULL };
+
+		fp = fopen(git_path("MERGE_MSG"), "a");
+		if (!fp)
+			die("Could open %s for writing", git_path("MERGE_MSG"));
+		fprintf(fp, "\nConflicts:\n");
+		for (pos = 0; pos < active_nr; pos++) {
+			struct cache_entry *ce = active_cache[pos];
+
+			if (ce_stage(ce)) {
+				fprintf(fp, "\t%s\n", ce->name);
+				while (pos + 1 < active_nr &&
+					!strcmp(ce->name,
+					active_cache[pos + 1]->name))
+					pos++;
+			}
+		}
+		fclose(fp);
+		run_command_v_opt(argv_rerere, RUN_GIT_CMD);
+		printf("Automatic merge failed; "
+			"fix conflicts and then commit the result.\n");
+		return 1;
+	}
+}
diff --git a/builtin.h b/builtin.h
index 2b01fea..8bf5280 100644
--- a/builtin.h
+++ b/builtin.h
@@ -60,6 +60,7 @@ extern int cmd_ls_tree(int argc, const char **argv, const char *prefix);
 extern int cmd_ls_remote(int argc, const char **argv, const char *prefix);
 extern int cmd_mailinfo(int argc, const char **argv, const char *prefix);
 extern int cmd_mailsplit(int argc, const char **argv, const char *prefix);
+extern int cmd_merge(int argc, const char **argv, const char *prefix);
 extern int cmd_merge_base(int argc, const char **argv, const char *prefix);
 extern int cmd_merge_ours(int argc, const char **argv, const char *prefix);
 extern int cmd_merge_file(int argc, const char **argv, const char *prefix);
diff --git a/git-merge.sh b/contrib/examples/git-merge.sh
similarity index 100%
rename from git-merge.sh
rename to contrib/examples/git-merge.sh
diff --git a/git.c b/git.c
index 2fbe96b..770aadd 100644
--- a/git.c
+++ b/git.c
@@ -271,6 +271,7 @@ static void handle_internal_command(int argc, const char **argv)
 		{ "ls-remote", cmd_ls_remote },
 		{ "mailinfo", cmd_mailinfo },
 		{ "mailsplit", cmd_mailsplit },
+		{ "merge", cmd_merge, RUN_SETUP | NEED_WORK_TREE },
 		{ "merge-base", cmd_merge_base, RUN_SETUP },
 		{ "merge-file", cmd_merge_file },
 		{ "merge-ours", cmd_merge_ours, RUN_SETUP },
-- 
1.5.6

[PATCH 11/11] Add new test to ensure git-merge handles more than 25 refs.

[Miklos Vajna]

The old shell version handled only 25 refs but we no longer have this
limitation. Add a test to make sure this limitation will not be
introduced again in the future.

Signed-off-by: Miklos Vajna <vmiklos@frugalware.org>
---
 t/t7602-merge-octopus-many.sh |   52 +++++++++++++++++++++++++++++++++++++++++
 1 files changed, 52 insertions(+), 0 deletions(-)
 create mode 100755 t/t7602-merge-octopus-many.sh

diff --git a/t/t7602-merge-octopus-many.sh b/t/t7602-merge-octopus-many.sh
new file mode 100755
index 0000000..fcb8285
--- /dev/null
+++ b/t/t7602-merge-octopus-many.sh
@@ -0,0 +1,52 @@
+#!/bin/sh
+
+test_description='git-merge
+
+Testing octopus merge with more than 25 refs.'
+
+. ./test-lib.sh
+
+test_expect_success 'setup' '
+	echo c0 > c0.c &&
+	git add c0.c &&
+	git commit -m c0 &&
+	git tag c0 &&
+	i=1 &&
+	while test $i -le 30
+	do
+		git reset --hard c0 &&
+		echo c$i > c$i.c &&
+		git add c$i.c &&
+		git commit -m c$i &&
+		git tag c$i &&
+		i=`expr $i + 1` || return 1
+	done
+'
+
+test_expect_success 'merge c1 with c2, c3, c4, ... c29' '
+	git reset --hard c1 &&
+	i=2 &&
+	refs="" &&
+	while test $i -le 30
+	do
+		refs="$refs c$i"
+		i=`expr $i + 1`
+	done
+	git merge $refs &&
+	test "$(git rev-parse c1)" != "$(git rev-parse HEAD)" &&
+	i=1 &&
+	while test $i -le 30
+	do
+		test "$(git rev-parse c$i)" = "$(git rev-parse HEAD^$i)" &&
+		i=`expr $i + 1` || return 1
+	done &&
+	git diff --exit-code &&
+	i=1 &&
+	while test $i -le 30
+	do
+		test -f c$i.c &&
+		i=`expr $i + 1` || return 1
+	done
+'
+
+test_done
-- 
1.5.6

Re: [PATCH 09/11] Introduce filter_independent() in commit.c

[Junio C Hamano]

Miklos Vajna <vmiklos@frugalware.org> writes:

> This is similar to git-show-branch --independent: It filters out commits
> which are reachable from any other item from the input list.
>
> Signed-off-by: Miklos Vajna <vmiklos@frugalware.org>
> ---
>  commit.c |   16 ++++++++++++++++
>  commit.h |    1 +
>  2 files changed, 17 insertions(+), 0 deletions(-)
>
> diff --git a/commit.c b/commit.c
> index 6052ca3..0dbf4b7 100644
> --- a/commit.c
> +++ b/commit.c
> @@ -705,3 +705,19 @@ int in_merge_bases(struct commit *commit, struct commit **reference, int num)
>  	free_commit_list(bases);
>  	return ret;
>  }
> +
> +struct commit_list *filter_independent(unsigned char *head,
> +	struct commit_list *heads)
> +{
> +	struct commit_list *i, *bases, *ret = NULL;
> +	struct commit_list **pptr = &ret;
> +
> +	commit_list_insert(lookup_commit(head), &heads);
> +
> +	bases = get_octopus_merge_bases(heads);
> +
> +	for (i = heads; i; i = i->next)
> +		if (!(i->item->object.flags & RESULT))
> +			pptr = &commit_list_insert(i->item, pptr)->next;

Hmm.  How well was this function tested?

Because RESULT is an implementation detail of merge_bases(), I do not
think we would want to expose it outside of it.

More worryingly, the flag is supposed to be cleaned from the objects after
get_merge_bases() returns.  I am not sure what you'll learn by looking at
the flag here.

Re: [PATCH 00/11] Build in merge

[Junio C Hamano]

Miklos Vajna <vmiklos@frugalware.org> writes:

> Changes since the previous series I sent out to the list:
>
> - get_octopus_merge_bases() now always does a cleanup
>
> - added a new test to make sure git-merge handles more than 25 refs
>
> As usual, comments are welcome. :-)

Thanks.

I take that last line of comment to mean "this is still RFC and not for
inclusion yet" ;-) I think the series is fine up to eighth patch (get
octopus merge base).

I'll queue the whole thing (still strictly as "test merge" basis) to 'pu';
I've fixed 3 "old-style C function definition" issues you have in the
tenth patch (build in merge), and I have some other issues with the ninth
one (filter independent).

Re: [PATCH 09/11] Introduce filter_independent() in commit.c

[Johannes Schindelin]

Hi,

On Thu, 19 Jun 2008, Junio C Hamano wrote:

> Miklos Vajna <vmiklos@frugalware.org> writes:
> 
> > This is similar to git-show-branch --independent: It filters out commits
> > which are reachable from any other item from the input list.
> >
> > Signed-off-by: Miklos Vajna <vmiklos@frugalware.org>
> > ---
> >  commit.c |   16 ++++++++++++++++
> >  commit.h |    1 +
> >  2 files changed, 17 insertions(+), 0 deletions(-)
> >
> > diff --git a/commit.c b/commit.c
> > index 6052ca3..0dbf4b7 100644
> > --- a/commit.c
> > +++ b/commit.c
> > @@ -705,3 +705,19 @@ int in_merge_bases(struct commit *commit, struct commit **reference, int num)
> >  	free_commit_list(bases);
> >  	return ret;
> >  }
> > +
> > +struct commit_list *filter_independent(unsigned char *head,
> > +	struct commit_list *heads)
> > +{
> > +	struct commit_list *i, *bases, *ret = NULL;
> > +	struct commit_list **pptr = &ret;
> > +
> > +	commit_list_insert(lookup_commit(head), &heads);
> > +
> > +	bases = get_octopus_merge_bases(heads);
> > +
> > +	for (i = heads; i; i = i->next)
> > +		if (!(i->item->object.flags & RESULT))
> > +			pptr = &commit_list_insert(i->item, pptr)->next;
> 
> Hmm.  How well was this function tested?
> 
> Because RESULT is an implementation detail of merge_bases(), I do not
> think we would want to expose it outside of it.

Well, filter_independent() lives in commit.c, too, so it is in the same 
scope as merge_branches().

> More worryingly, the flag is supposed to be cleaned from the objects 
> after get_merge_bases() returns.  I am not sure what you'll learn by 
> looking at the flag here.

That is a valid point, methinks.  Probably the octopus_merge_base and the 
cleanup have to be decoupled here.  The cleanup should be nothing more 
than calling clear_commit_marks() for every head.

A test case would be desirable, but probably pretty complicated.  Hmm.  I 
like tests when they are simple, because they are easy to verify by a 
human.  Miklos, any chance for such a test case?

Ciao,
Dscho

Re: [PATCH 09/11] Introduce filter_independent() in commit.c

[Miklos Vajna]

[-- Attachment #1: Type: text/plain, Size: 879 bytes --]

On Fri, Jun 20, 2008 at 01:53:06PM +0200, Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:
> > More worryingly, the flag is supposed to be cleaned from the objects 
> > after get_merge_bases() returns.  I am not sure what you'll learn by 
> > looking at the flag here.
> 
> That is a valid point, methinks.  Probably the octopus_merge_base and the 
> cleanup have to be decoupled here.  The cleanup should be nothing more 
> than calling clear_commit_marks() for every head.

Actually get_octopus_merge_bases() _needs_ to clean up the flags as it
calls get_merge_bases() multiple times and get_merge_bases() expects
empty flags.

> A test case would be desirable, but probably pretty complicated.  Hmm.  I 
> like tests when they are simple, because they are easy to verify by a 
> human.  Miklos, any chance for such a test case?

Sure, I'll write one.

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: [PATCH 09/11] Introduce filter_independent() in commit.c

[Johannes Schindelin]

Hi,

On Fri, 20 Jun 2008, Miklos Vajna wrote:

> On Fri, Jun 20, 2008 at 01:53:06PM +0200, Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:
> > > More worryingly, the flag is supposed to be cleaned from the objects 
> > > after get_merge_bases() returns.  I am not sure what you'll learn by 
> > > looking at the flag here.
> > 
> > That is a valid point, methinks.  Probably the octopus_merge_base and 
> > the cleanup have to be decoupled here.  The cleanup should be nothing 
> > more than calling clear_commit_marks() for every head.
> 
> Actually get_octopus_merge_bases() _needs_ to clean up the flags as it 
> calls get_merge_bases() multiple times and get_merge_bases() expects 
> empty flags.

Oh darn, you are right.

> > A test case would be desirable, but probably pretty complicated.  
> > Hmm.  I like tests when they are simple, because they are easy to 
> > verify by a human.  Miklos, any chance for such a test case?
> 
> Sure, I'll write one.

Thanks,
Dscho

Re: [PATCH 09/11] Introduce filter_independent() in commit.c

[Miklos Vajna]

[-- Attachment #1: Type: text/plain, Size: 484 bytes --]

On Fri, Jun 20, 2008 at 01:53:06PM +0200, Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:
> A test case would be desirable, but probably pretty complicated.  Hmm.  I 
> like tests when they are simple, because they are easy to verify by a 
> human.  Miklos, any chance for such a test case?

Not that complicated:

http://repo.or.cz/w/git/vmiklos.git?a=commit;h=c19b568714c7141e9f96ebea3990f7dae615223b

At the moment it passes on master and fails on mv/merge-in-c.

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

[PATCH] Introduce filter_independent() in commit.c

[Miklos Vajna]

This is similar to git-show-branch --independent: It filters out commits
which are reachable from any other item from the input list.

Signed-off-by: Miklos Vajna <vmiklos@frugalware.org>
---

On Thu, Jun 19, 2008 at 08:03:58PM -0700, Junio C Hamano <gitster@pobox.com> wrote:
> > +   for (i = heads; i; i = i->next)
> > +           if (!(i->item->object.flags & RESULT))
> > +                   pptr = &commit_list_insert(i->item, pptr)->next;
>
> Hmm.  How well was this function tested?

As Dscho pointed out in an other mail there was no testcase for it, I
wrote one and it pointed out what you said: it was buggy.

> Because RESULT is an implementation detail of merge_bases(), I do not
> think we would want to expose it outside of it.

The new version does not have this problem, either.

> More worryingly, the flag is supposed to be cleaned from the objects
> after get_merge_bases() returns.  I am not sure what you'll learn by
> looking at the flag here.

Yes, you are right. In fact the idea to use get_octopus_merge_bases()
was wrong, since it does not do what we need.

Here is an example:

	A - B
	  \ C
	  \ D
	  \ E - F

In this case get_octopus_merge_bases() will return only A, which is what
it should do, but we need E in filter_indepenent() as well.

Below is what I pushed to my working branch.

This version now passes the test that was failed for the previous one.

 commit.c |   32 ++++++++++++++++++++++++++++++++
 commit.h |    1 +
 2 files changed, 33 insertions(+), 0 deletions(-)

diff --git a/commit.c b/commit.c
index 6052ca3..17e18d7 100644
--- a/commit.c
+++ b/commit.c
@@ -705,3 +705,35 @@ int in_merge_bases(struct commit *commit, struct commit **reference, int num)
 	free_commit_list(bases);
 	return ret;
 }
+
+struct commit_list *filter_independent(unsigned char *head,
+	struct commit_list *heads)
+{
+	struct commit_list *b, *i, *j, *k, *bases = NULL, *ret = NULL;
+	struct commit_list **pptr = &ret;
+
+	commit_list_insert(lookup_commit(head), &heads);
+
+	for (i = heads; i; i = i->next) {
+		for (j = heads; j; j = j->next) {
+			if (i == j)
+				continue;
+			b = get_merge_bases(i->item, j->item, 1);
+			for (k = b; k; k = k->next)
+				commit_list_insert(k->item, &bases);
+		}
+	}
+
+	for (i = heads; i; i = i->next) {
+		int found = 0;
+		for (b = bases; b; b = b->next) {
+			if (!hashcmp(i->item->object.sha1, b->item->object.sha1)) {
+				found = 1;
+				break;
+			}
+		}
+		if (!found)
+			pptr = &commit_list_insert(i->item, pptr)->next;
+	}
+	return ret;
+}
diff --git a/commit.h b/commit.h
index dcec7fb..0aef7e4 100644
--- a/commit.h
+++ b/commit.h
@@ -131,6 +131,7 @@ extern struct commit_list *get_shallow_commits(struct object_array *heads,
 		int depth, int shallow_flag, int not_shallow_flag);
 
 int in_merge_bases(struct commit *, struct commit **, int);
+struct commit_list *filter_independent(unsigned char *head, struct commit_list *heads);
 
 extern int interactive_add(int argc, const char **argv, const char *prefix);
 extern int rerere(void);
-- 
1.5.6

Re: [PATCH 00/11] Build in merge

[Miklos Vajna]

[-- Attachment #1: Type: text/plain, Size: 997 bytes --]

On Thu, Jun 19, 2008 at 08:04:14PM -0700, Junio C Hamano <gitster@pobox.com> wrote:
> > As usual, comments are welcome. :-)
> 
> Thanks.
> 
> I take that last line of comment to mean "this is still RFC and not for
> inclusion yet" ;-) I think the series is fine up to eighth patch (get
> octopus merge base).

In fact only the version that had "WIP" in the subject was sent not for
inclusion. ;-)

> I'll queue the whole thing (still strictly as "test merge" basis) to 'pu';
> I've fixed 3 "old-style C function definition" issues you have in the
> tenth patch (build in merge), and I have some other issues with the ninth
> one (filter independent).

Thanks. I'm using the kernel's scripts/checkpatch.pl, but it does not
have such a check, and I missed it.

Currently I have 12 patches in my branch; if there will be no objections
to the new "filter independent" one, then I will resend the series
excluding the first 8 to avoid unnecessary traffic, if that is OK to
you.

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: [PATCH] Introduce filter_independent() in commit.c

[Junio C Hamano]

Miklos Vajna <vmiklos@frugalware.org> writes:

> +struct commit_list *filter_independent(unsigned char *head,
> +	struct commit_list *heads)
> +{
> +	struct commit_list *b, *i, *j, *k, *bases = NULL, *ret = NULL;
> +	struct commit_list **pptr = &ret;
> +
> +	commit_list_insert(lookup_commit(head), &heads);

Isn't the special casing of head making this function less easier to reuse
in other contexts?  "show-branch --independent" is about getting N commits
and removing commits from that set that can be reachable from another
commit, so there is no need nor reason to treat one "head" in any special
way.

> +	for (i = heads; i; i = i->next) {
> +		for (j = heads; j; j = j->next) {
> +			if (i == j)
> +				continue;
> +			b = get_merge_bases(i->item, j->item, 1);
> +			for (k = b; k; k = k->next)
> +				commit_list_insert(k->item, &bases);
> +		}
> +	}

You run (N-1)*N merge-base computation to get all pairwise merge-bases
here.  As merge-base(A,B) == merge-base(B,A), this is computing the same
thing twice.

Isn't your "b" leaking?

> +	for (i = heads; i; i = i->next) {
> +		int found = 0;
> +		for (b = bases; b; b = b->next) {
> +			if (!hashcmp(i->item->object.sha1, b->item->object.sha1)) {
> +				found = 1;

Then you see if the given heads exactly match one of the merge bases you
found earlier.  But does this have to be in a separate pass?

Isn't your "bases" list leaking?

Even though you may be able to reduce more than 25 heads, you run N^2
merge base traversals, which means 625 merge base traversals for 25 heads;
show-branch engine can do the same thing with a single traversal.

Can't we do better than O(N^2)?

Let's step back a bit and think.  You have N commits (stop thinking about
"my head and N other heads" like your function signature suggests).  For
each one, you would want to see if it is reachable from any of the other
(N-1) commits, and if so, you would exclude it from the resulting set.
And you do that for all N commits and you are done.  You can relatively
easily do this with an O(N) traversals.

Now, if you have one commit and other (N-1) commits, is there a way to
efficiently figure out if that one commit is reachable from any of the
other (N-1) commits?

If there were a merge of these other (N-1) commits, and if you compute a
merge base between that merge commit and the one commit you are looking
at, what would you get?  Yes, you will get your commit back if and only if
it is reachable from some of these (N-1) commits.

If you recall the merge-base-many patch we discussed earlier, that is
exactly what it computes, isn't it?

[PATCH 1/2] Introduce get_merge_bases_many()

[Junio C Hamano]

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 <gitster@pobox.com>
---
 commit.c |   56 ++++++++++++++++++++++++++++++++++++++------------------
 1 files changed, 38 insertions(+), 18 deletions(-)

diff --git a/commit.c b/commit.c
index e2d8624..4ee234d 100644
--- a/commit.c
+++ b/commit.c
@@ -525,26 +525,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;
@@ -592,21 +600,26 @@ static struct commit_list *merge_bases(struct commit *one, struct commit *two)
 	return result;
 }
 
-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;
 	}
@@ -624,12 +637,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) {
@@ -651,6 +665,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;
-- 
1.5.6.6.gd3e97

[PATCH 2/2] Introduce reduce_heads()

[Junio C Hamano]

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 <gitster@pobox.com>
---
 * The important part of this patch is the addition to commit.c to show
   how I would write your filter_independent().  The new command is not
   essential, but is included as a demonstration.

 Makefile               |    1 +
 builtin-reduce-heads.c |   44 ++++++++++++++++++++++++++++++++++++++++++++
 builtin.h              |    1 +
 commit.c               |   45 +++++++++++++++++++++++++++++++++++++++++++++
 commit.h               |    2 ++
 git.c                  |    1 +
 6 files changed, 94 insertions(+), 0 deletions(-)
 create mode 100644 builtin-reduce-heads.c

diff --git a/Makefile b/Makefile
index b003e3e..d660756 100644
--- a/Makefile
+++ b/Makefile
@@ -522,6 +522,7 @@ BUILTIN_OBJS += builtin-pack-refs.o
 BUILTIN_OBJS += builtin-prune-packed.o
 BUILTIN_OBJS += builtin-prune.o
 BUILTIN_OBJS += builtin-push.o
+BUILTIN_OBJS += builtin-reduce-heads.o
 BUILTIN_OBJS += builtin-read-tree.o
 BUILTIN_OBJS += builtin-reflog.o
 BUILTIN_OBJS += builtin-remote.o
diff --git a/builtin-reduce-heads.c b/builtin-reduce-heads.c
new file mode 100644
index 0000000..ff6178d
--- /dev/null
+++ b/builtin-reduce-heads.c
@@ -0,0 +1,44 @@
+#include "cache.h"
+#include "commit.h"
+#include "strbuf.h"
+
+static void show_commit_list(struct commit_list *list)
+{
+	while (list) {
+		struct strbuf it;
+		struct commit *commit = list->item;
+
+		list = list->next;
+		strbuf_init(&it, 128);
+		parse_commit(commit);
+		pretty_print_commit(CMIT_FMT_ONELINE, commit, &it,
+				    0, NULL, NULL, 0, 0);
+		puts(it.buf);
+		strbuf_release(&it);
+	}
+}
+
+int cmd_reduce_heads(int ac, const char **av, const char *prefix)
+{
+	struct commit_list *list = NULL, **tail = &list;
+	int i;
+
+	for (i = 1; i < ac; i++) {
+		struct commit *commit;
+		unsigned char sha1[20];
+
+		if (get_sha1(av[i], sha1))
+			die("'%s' is not a valid ref.", av[i]);
+		commit = lookup_commit_reference(sha1);
+		if (!commit)
+			die("cannot find commit %s", av[i]);
+		tail = &commit_list_insert(commit, tail)->next;
+	}
+
+	show_commit_list(list);
+	putchar('\n');
+
+	list = reduce_heads(list);
+	show_commit_list(list);
+	return 0;
+}
diff --git a/builtin.h b/builtin.h
index b460b2d..b6fb163 100644
--- a/builtin.h
+++ b/builtin.h
@@ -72,6 +72,7 @@ extern int cmd_read_tree(int argc, const char **argv, const char *prefix);
 extern int cmd_reflog(int argc, const char **argv, const char *prefix);
 extern int cmd_remote(int argc, const char **argv, const char *prefix);
 extern int cmd_config(int argc, const char **argv, const char *prefix);
+extern int cmd_reduce_heads(int argc, const char **argv, const char *prefix);
 extern int cmd_rerere(int argc, const char **argv, const char *prefix);
 extern int cmd_reset(int argc, const char **argv, const char *prefix);
 extern int cmd_rev_list(int argc, const char **argv, const char *prefix);
diff --git a/commit.c b/commit.c
index 4ee234d..0fc4acb 100644
--- a/commit.c
+++ b/commit.c
@@ -690,3 +690,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 2d94d41..ec95102 100644
--- a/commit.h
+++ b/commit.h
@@ -138,4 +138,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 */
diff --git a/git.c b/git.c
index 59f0fcc..23b690d 100644
--- a/git.c
+++ b/git.c
@@ -338,6 +338,7 @@ static void handle_internal_command(int argc, const char **argv)
 		{ "prune-packed", cmd_prune_packed, RUN_SETUP },
 		{ "push", cmd_push, RUN_SETUP },
 		{ "read-tree", cmd_read_tree, RUN_SETUP },
+		{ "reduce-heads", cmd_reduce_heads, RUN_SETUP },
 		{ "reflog", cmd_reflog, RUN_SETUP },
 		{ "remote", cmd_remote, RUN_SETUP },
 		{ "repo-config", cmd_config },
-- 
1.5.6.6.gd3e97

[PATCH 00/13] Build in merge

[Miklos Vajna]

On Sat, Jun 21, 2008 at 02:45:38AM -0700, Junio C Hamano <gitster@pobox.com> wrote:
> Miklos Vajna <vmiklos@frugalware.org> writes:
>
> > +struct commit_list *filter_independent(unsigned char *head,
> > +   struct commit_list *heads)
> > +{
> > +   struct commit_list *b, *i, *j, *k, *bases = NULL, *ret = NULL;
> > +   struct commit_list **pptr = &ret;
> > +
> > +   commit_list_insert(lookup_commit(head), &heads);
>
> Isn't the special casing of head making this function less easier to
> reuse in other contexts?  "show-branch --independent" is about getting
> N commits and removing commits from that set that can be reachable
> from another commit, so there is no need nor reason to treat one
> "head" in any special way.

Yes, sure. It originally it was in builtin-merge.c and _there_ it was
easier this way but in commit.c this should be generalized.

> > +   for (i = heads; i; i = i->next) {
> > +           for (j = heads; j; j = j->next) {
> > +                   if (i == j)
> > +                           continue;
> > +                   b = get_merge_bases(i->item, j->item, 1);
> > +                   for (k = b; k; k = k->next)
> > +                           commit_list_insert(k->item, &bases);
> > +           }
> > +   }
>
> You run (N-1)*N merge-base computation to get all pairwise merge-bases
> here.  As merge-base(A,B) == merge-base(B,A), this is computing the
> same
> thing twice.
>
> Isn't your "b" leaking?
>
> > +   for (i = heads; i; i = i->next) {
> > +           int found = 0;
> > +           for (b = bases; b; b = b->next) {
> > +                   if (!hashcmp(i->item->object.sha1, b->item->object.sha1)) {
> > +                           found = 1;
>
> Then you see if the given heads exactly match one of the merge bases
> you
> found earlier.  But does this have to be in a separate pass?
>
> Isn't your "bases" list leaking?
>
> Even though you may be able to reduce more than 25 heads, you run N^2
> merge base traversals, which means 625 merge base traversals for 25
> heads;
> show-branch engine can do the same thing with a single traversal.
>
> Can't we do better than O(N^2)?

Right, actually my primary target was to achieve the right behaviour and
I did not care enough about performance and memory leaks, my bad.

> Let's step back a bit and think.  You have N commits (stop thinking
> about "my head and N other heads" like your function signature
> suggests).  For each one, you would want to see if it is reachable
> from any of the other (N-1) commits, and if so, you would exclude it
> from the resulting set.  And you do that for all N commits and you are
> done.  You can relatively easily do this with an O(N) traversals.
>
> Now, if you have one commit and other (N-1) commits, is there a way to
> efficiently figure out if that one commit is reachable from any of the
> other (N-1) commits?
>
> If there were a merge of these other (N-1) commits, and if you compute
> a merge base between that merge commit and the one commit you are
> looking at, what would you get?  Yes, you will get your commit back if
> and only if it is reachable from some of these (N-1) commits.
>
> If you recall the merge-base-many patch we discussed earlier, that is
> exactly what it computes, isn't it?

Exactly. :-)

Now I dropped the filter_independent() patch from my branch and replaced
it with your ones, since reduce_heads() does exactly the same, but it
performs much better.

So, changes since the previous series:

- added a testcase to make sure parents are reduced properly (as
  suggested by Dscho)

- port 037e98f20241bf013cd007b0924936a29c3cacfa to builtin-merge.c ("fix
  typo in usage message")

- dropped filter_independent() and replaced it with reduce_heads() (your
  two patches)

I'm not sending patches 01-08 (up to "Introduce
get_octopus_merge_bases()") since they are unchanged and to avoid
unnecessary traffic.

Junio C Hamano (2):
  Introduce get_merge_bases_many()
  Introduce reduce_heads()

Miklos Vajna (11):
  Move split_cmdline() to alias.c
  Move commit_list_count() to commit.c
  Move parse-options's skip_prefix() to git-compat-util.h
  Add new test to ensure git-merge handles pull.twohead and
    pull.octopus
  parseopt: add a new PARSE_OPT_ARGV0_IS_AN_OPTION option
  Move read_cache_unmerged() to read-cache.c
  git-fmt-merge-msg: make it usable from other builtins
  Introduce get_octopus_merge_bases() in commit.c
  Add new test to ensure git-merge handles more than 25 refs.
  Build in merge
  Add new test case to ensure git-merge filters for independent parents

 Makefile                                      |    3 +-
 alias.c                                       |   54 ++
 builtin-fmt-merge-msg.c                       |  157 ++--
 builtin-merge-recursive.c                     |    8 -
 builtin-merge.c                               | 1130 +++++++++++++++++++++++++
 builtin-read-tree.c                           |   24 -
 builtin-reduce-heads.c                        |   44 +
 builtin-remote.c                              |   39 +-
 builtin.h                                     |    5 +
 cache.h                                       |    3 +
 commit.c                                      |  136 +++-
 commit.h                                      |    4 +
 git-merge.sh => contrib/examples/git-merge.sh |    0 
 git-compat-util.h                             |    6 +
 git.c                                         |   55 +--
 parse-options.c                               |   11 +-
 parse-options.h                               |    1 +
 read-cache.c                                  |   31 +
 t/t7601-merge-pull-config.sh                  |   72 ++
 t/t7602-merge-octopus-many.sh                 |   52 ++
 t/t7603-merge-filter-independent.sh           |   63 ++
 21 files changed, 1709 insertions(+), 189 deletions(-)
 create mode 100644 builtin-merge.c
 create mode 100644 builtin-reduce-heads.c
 rename git-merge.sh => contrib/examples/git-merge.sh (100%)
 create mode 100755 t/t7601-merge-pull-config.sh
 create mode 100755 t/t7602-merge-octopus-many.sh
 create mode 100755 t/t7603-merge-filter-independent.sh

[PATCH 09/13] Add new test to ensure git-merge handles more than 25 refs.

[Miklos Vajna]

The old shell version handled only 25 refs but we no longer have this
limitation. Add a test to make sure this limitation will not be
introduced again in the future.

Signed-off-by: Miklos Vajna <vmiklos@frugalware.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 t/t7602-merge-octopus-many.sh |   52 +++++++++++++++++++++++++++++++++++++++++
 1 files changed, 52 insertions(+), 0 deletions(-)
 create mode 100755 t/t7602-merge-octopus-many.sh

diff --git a/t/t7602-merge-octopus-many.sh b/t/t7602-merge-octopus-many.sh
new file mode 100755
index 0000000..fcb8285
--- /dev/null
+++ b/t/t7602-merge-octopus-many.sh
@@ -0,0 +1,52 @@
+#!/bin/sh
+
+test_description='git-merge
+
+Testing octopus merge with more than 25 refs.'
+
+. ./test-lib.sh
+
+test_expect_success 'setup' '
+	echo c0 > c0.c &&
+	git add c0.c &&
+	git commit -m c0 &&
+	git tag c0 &&
+	i=1 &&
+	while test $i -le 30
+	do
+		git reset --hard c0 &&
+		echo c$i > c$i.c &&
+		git add c$i.c &&
+		git commit -m c$i &&
+		git tag c$i &&
+		i=`expr $i + 1` || return 1
+	done
+'
+
+test_expect_success 'merge c1 with c2, c3, c4, ... c29' '
+	git reset --hard c1 &&
+	i=2 &&
+	refs="" &&
+	while test $i -le 30
+	do
+		refs="$refs c$i"
+		i=`expr $i + 1`
+	done
+	git merge $refs &&
+	test "$(git rev-parse c1)" != "$(git rev-parse HEAD)" &&
+	i=1 &&
+	while test $i -le 30
+	do
+		test "$(git rev-parse c$i)" = "$(git rev-parse HEAD^$i)" &&
+		i=`expr $i + 1` || return 1
+	done &&
+	git diff --exit-code &&
+	i=1 &&
+	while test $i -le 30
+	do
+		test -f c$i.c &&
+		i=`expr $i + 1` || return 1
+	done
+'
+
+test_done
-- 
1.5.6

[PATCH 10/13] Introduce get_merge_bases_many()

[Miklos Vajna]

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

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 <gitster@pobox.com>
---
 commit.c |   56 ++++++++++++++++++++++++++++++++++++++------------------
 1 files changed, 38 insertions(+), 18 deletions(-)

diff --git a/commit.c b/commit.c
index 6052ca3..cafed26 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;
-- 
1.5.6

[PATCH 11/13] Introduce reduce_heads()

[Miklos Vajna]

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

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 <gitster@pobox.com>
---
 Makefile               |    1 +
 builtin-reduce-heads.c |   44 ++++++++++++++++++++++++++++++++++++++++++++
 builtin.h              |    1 +
 commit.c               |   45 +++++++++++++++++++++++++++++++++++++++++++++
 commit.h               |    2 ++
 git.c                  |    1 +
 6 files changed, 94 insertions(+), 0 deletions(-)
 create mode 100644 builtin-reduce-heads.c

diff --git a/Makefile b/Makefile
index b003e3e..d660756 100644
--- a/Makefile
+++ b/Makefile
@@ -522,6 +522,7 @@ BUILTIN_OBJS += builtin-pack-refs.o
 BUILTIN_OBJS += builtin-prune-packed.o
 BUILTIN_OBJS += builtin-prune.o
 BUILTIN_OBJS += builtin-push.o
+BUILTIN_OBJS += builtin-reduce-heads.o
 BUILTIN_OBJS += builtin-read-tree.o
 BUILTIN_OBJS += builtin-reflog.o
 BUILTIN_OBJS += builtin-remote.o
diff --git a/builtin-reduce-heads.c b/builtin-reduce-heads.c
new file mode 100644
index 0000000..ff6178d
--- /dev/null
+++ b/builtin-reduce-heads.c
@@ -0,0 +1,44 @@
+#include "cache.h"
+#include "commit.h"
+#include "strbuf.h"
+
+static void show_commit_list(struct commit_list *list)
+{
+	while (list) {
+		struct strbuf it;
+		struct commit *commit = list->item;
+
+		list = list->next;
+		strbuf_init(&it, 128);
+		parse_commit(commit);
+		pretty_print_commit(CMIT_FMT_ONELINE, commit, &it,
+				    0, NULL, NULL, 0, 0);
+		puts(it.buf);
+		strbuf_release(&it);
+	}
+}
+
+int cmd_reduce_heads(int ac, const char **av, const char *prefix)
+{
+	struct commit_list *list = NULL, **tail = &list;
+	int i;
+
+	for (i = 1; i < ac; i++) {
+		struct commit *commit;
+		unsigned char sha1[20];
+
+		if (get_sha1(av[i], sha1))
+			die("'%s' is not a valid ref.", av[i]);
+		commit = lookup_commit_reference(sha1);
+		if (!commit)
+			die("cannot find commit %s", av[i]);
+		tail = &commit_list_insert(commit, tail)->next;
+	}
+
+	show_commit_list(list);
+	putchar('\n');
+
+	list = reduce_heads(list);
+	show_commit_list(list);
+	return 0;
+}
diff --git a/builtin.h b/builtin.h
index 2b01fea..f069ee7 100644
--- a/builtin.h
+++ b/builtin.h
@@ -75,6 +75,7 @@ extern int cmd_read_tree(int argc, const char **argv, const char *prefix);
 extern int cmd_reflog(int argc, const char **argv, const char *prefix);
 extern int cmd_remote(int argc, const char **argv, const char *prefix);
 extern int cmd_config(int argc, const char **argv, const char *prefix);
+extern int cmd_reduce_heads(int argc, const char **argv, const char *prefix);
 extern int cmd_rerere(int argc, const char **argv, const char *prefix);
 extern int cmd_reset(int argc, const char **argv, const char *prefix);
 extern int cmd_rev_list(int argc, const char **argv, const char *prefix);
diff --git a/commit.c b/commit.c
index cafed26..d20b14e 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 dcec7fb..2acfc79 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 */
diff --git a/git.c b/git.c
index 2fbe96b..80b16ce 100644
--- a/git.c
+++ b/git.c
@@ -285,6 +285,7 @@ static void handle_internal_command(int argc, const char **argv)
 		{ "prune-packed", cmd_prune_packed, RUN_SETUP },
 		{ "push", cmd_push, RUN_SETUP },
 		{ "read-tree", cmd_read_tree, RUN_SETUP },
+		{ "reduce-heads", cmd_reduce_heads, RUN_SETUP },
 		{ "reflog", cmd_reflog, RUN_SETUP },
 		{ "remote", cmd_remote, RUN_SETUP },
 		{ "repo-config", cmd_config },
-- 
1.5.6

[PATCH 12/13] Build in merge

[Miklos Vajna]

Mentored-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>
Signed-off-by: Miklos Vajna <vmiklos@frugalware.org>
---
 Makefile                                      |    2 +-
 builtin-merge.c                               | 1130 +++++++++++++++++++++++++
 builtin.h                                     |    1 +
 git-merge.sh => contrib/examples/git-merge.sh |    0 
 git.c                                         |    1 +
 5 files changed, 1133 insertions(+), 1 deletions(-)
 create mode 100644 builtin-merge.c
 rename git-merge.sh => contrib/examples/git-merge.sh (100%)

diff --git a/Makefile b/Makefile
index d660756..f822458 100644
--- a/Makefile
+++ b/Makefile
@@ -240,7 +240,6 @@ SCRIPT_SH += git-lost-found.sh
 SCRIPT_SH += git-merge-octopus.sh
 SCRIPT_SH += git-merge-one-file.sh
 SCRIPT_SH += git-merge-resolve.sh
-SCRIPT_SH += git-merge.sh
 SCRIPT_SH += git-merge-stupid.sh
 SCRIPT_SH += git-mergetool.sh
 SCRIPT_SH += git-parse-remote.sh
@@ -511,6 +510,7 @@ BUILTIN_OBJS += builtin-ls-remote.o
 BUILTIN_OBJS += builtin-ls-tree.o
 BUILTIN_OBJS += builtin-mailinfo.o
 BUILTIN_OBJS += builtin-mailsplit.o
+BUILTIN_OBJS += builtin-merge.o
 BUILTIN_OBJS += builtin-merge-base.o
 BUILTIN_OBJS += builtin-merge-file.o
 BUILTIN_OBJS += builtin-merge-ours.o
diff --git a/builtin-merge.c b/builtin-merge.c
new file mode 100644
index 0000000..dadde80
--- /dev/null
+++ b/builtin-merge.c
@@ -0,0 +1,1130 @@
+/*
+ * Builtin "git merge"
+ *
+ * Copyright (c) 2008 Miklos Vajna <vmiklos@frugalware.org>
+ *
+ * Based on git-merge.sh by Junio C Hamano.
+ */
+
+#include "cache.h"
+#include "parse-options.h"
+#include "builtin.h"
+#include "run-command.h"
+#include "path-list.h"
+#include "diff.h"
+#include "refs.h"
+#include "commit.h"
+#include "diffcore.h"
+#include "revision.h"
+#include "unpack-trees.h"
+#include "cache-tree.h"
+#include "dir.h"
+#include "utf8.h"
+#include "log-tree.h"
+
+enum strategy {
+	DEFAULT_TWOHEAD = 1,
+	DEFAULT_OCTOPUS = 2,
+	NO_FAST_FORWARD = 4,
+	NO_TRIVIAL = 8
+};
+
+static const char * const builtin_merge_usage[] = {
+	"git-merge [options] <remote>...",
+	"git-merge [options] <msg> HEAD <remote>",
+	NULL
+};
+
+static int show_diffstat = 1, option_log, squash;
+static int option_commit = 1, allow_fast_forward = 1;
+static int allow_trivial = 1, have_message;
+static struct strbuf merge_msg;
+static struct commit_list *remoteheads;
+static unsigned char head[20];
+static struct path_list use_strategies;
+static const char *branch;
+
+static struct path_list_item strategy_items[] = {
+	{ "recur",      (void *)NO_TRIVIAL },
+	{ "recursive",  (void *)(DEFAULT_TWOHEAD | NO_TRIVIAL) },
+	{ "octopus",    (void *)DEFAULT_OCTOPUS },
+	{ "resolve",    (void *)0 },
+	{ "stupid",     (void *)0 },
+	{ "ours",       (void *)(NO_FAST_FORWARD | NO_TRIVIAL) },
+	{ "subtree",    (void *)(NO_FAST_FORWARD | NO_TRIVIAL) },
+};
+static struct path_list strategies = { strategy_items,
+	ARRAY_SIZE(strategy_items), 0, 0 };
+
+static const char *pull_twohead, *pull_octopus;
+
+static int option_parse_message(const struct option *opt,
+	const char *arg, int unset)
+{
+	struct strbuf *buf = opt->value;
+
+	if (unset)
+		strbuf_setlen(buf, 0);
+	else {
+		strbuf_addstr(buf, arg);
+		have_message = 1;
+	}
+	return 0;
+}
+
+static struct path_list_item *unsorted_path_list_lookup(const char *path,
+	struct path_list *list)
+{
+	int i;
+
+	if (!path)
+		return NULL;
+
+	for (i = 0; i < list->nr; i++)
+		if (!strcmp(path, list->items[i].path))
+			return &list->items[i];
+	return NULL;
+}
+
+static inline void path_list_append_strategy(const char *path, void *util,
+	struct path_list *list)
+{
+	path_list_append(path, list)->util = util;
+}
+
+static int option_parse_strategy(const struct option *opt,
+	const char *arg, int unset)
+{
+	int i;
+	struct path_list *list = opt->value;
+	struct path_list_item *item =
+		unsorted_path_list_lookup(arg, &strategies);
+
+	if (unset)
+		return 0;
+
+	if (item)
+		path_list_append_strategy(arg, item->util, list);
+	else {
+		struct strbuf err;
+		strbuf_init(&err, 0);
+		for (i = 0; i < strategies.nr; i++)
+			strbuf_addf(&err, " %s", strategies.items[i].path);
+		fprintf(stderr, "Could not find merge strategy '%s'.\n", arg);
+		fprintf(stderr, "Available strategies are:%s.\n", err.buf);
+		exit(1);
+	}
+	return 0;
+}
+
+static int option_parse_n(const struct option *opt,
+		const char *arg, int unset)
+{
+	show_diffstat = unset;
+	return 0;
+}
+
+static struct option builtin_merge_options[] = {
+	{ OPTION_CALLBACK, 'n', NULL, NULL, NULL,
+		"do not show a diffstat at the end of the merge",
+		PARSE_OPT_NOARG, option_parse_n },
+	OPT_BOOLEAN(0, "stat", &show_diffstat,
+		"show a diffstat at the end of the merge"),
+	OPT_BOOLEAN(0, "summary", &show_diffstat, "(synonym to --stat)"),
+	OPT_BOOLEAN(0, "log", &option_log,
+		"add list of one-line log to merge commit message"),
+	OPT_BOOLEAN(0, "squash", &squash,
+		"create a single commit instead of doing a merge"),
+	OPT_BOOLEAN(0, "commit", &option_commit,
+		"perform a commit if the merge succeeds (default)"),
+	OPT_BOOLEAN(0, "ff", &allow_fast_forward,
+		"allow fast forward (default)"),
+	OPT_CALLBACK('s', "strategy", &use_strategies, "strategy",
+		"merge strategy to use", option_parse_strategy),
+	OPT_CALLBACK('m', "message", &merge_msg, "message",
+		"message to be used for the merge commit (if any)",
+		option_parse_message),
+	OPT_END()
+};
+
+/* Cleans up metadata that is uninteresting after a succeeded merge. */
+static void dropsave(void)
+{
+	unlink(git_path("MERGE_HEAD"));
+	unlink(git_path("MERGE_MSG"));
+	unlink(git_path("MERGE_STASH"));
+}
+
+static void save_state(void)
+{
+	int fd;
+	struct child_process stash;
+	const char *argv[] = {"stash", "create", NULL};
+
+	fd = open(git_path("MERGE_STASH"), O_WRONLY | O_CREAT, 0666);
+	if (fd < 0)
+		die("Could not write to %s", git_path("MERGE_STASH"));
+	memset(&stash, 0, sizeof(stash));
+	stash.argv = argv;
+	stash.out = fd;
+	stash.git_cmd = 1;
+	run_command(&stash);
+}
+
+static void reset_hard(unsigned const char *sha1, int verbose)
+{
+	struct tree *tree;
+	struct unpack_trees_options opts;
+	struct tree_desc t;
+
+	memset(&opts, 0, sizeof(opts));
+	opts.head_idx = -1;
+	opts.src_index = &the_index;
+	opts.dst_index = &the_index;
+	opts.update = 1;
+	opts.reset = 1;
+	if (verbose)
+		opts.verbose_update = 1;
+
+	tree = parse_tree_indirect(sha1);
+	if (!tree)
+		die("failed to unpack %s tree object", sha1_to_hex(sha1));
+	parse_tree(tree);
+	init_tree_desc(&t, tree->buffer, tree->size);
+	if (unpack_trees(1, &t, &opts))
+		exit(128); /* We've already reported the error, finish dying */
+}
+
+static void restore_state(void)
+{
+	struct strbuf sb;
+	const char *args[] = { "stash", "apply", NULL, NULL };
+
+	if (access(git_path("MERGE_STASH"), R_OK) < 0)
+		return;
+
+	reset_hard(head, 1);
+
+	strbuf_init(&sb, 0);
+	if (strbuf_read_file(&sb, git_path("MERGE_STASH"), 0) < 0)
+		die("could not read MERGE_STASH: %s", strerror(errno));
+	args[2] = sb.buf;
+
+	/*
+	 * It is OK to ignore error here, for example when there was
+	 * nothing to restore.
+	 */
+	run_command_v_opt(args, RUN_GIT_CMD);
+
+	refresh_cache(REFRESH_QUIET);
+}
+
+/* This is called when no merge was necessary. */
+static void finish_up_to_date(const char *msg)
+{
+	if (squash)
+		printf("%s (nothing to squash)\n", msg);
+	else
+		printf("%s\n", msg);
+	dropsave();
+}
+
+static void squash_message(int out_fd)
+{
+	struct rev_info rev;
+	struct commit *commit;
+	struct strbuf out;
+	struct commit_list *j;
+
+	init_revisions(&rev, NULL);
+	rev.ignore_merges = 1;
+	rev.commit_format = CMIT_FMT_MEDIUM;
+
+	commit = lookup_commit(head);
+	commit->object.flags |= UNINTERESTING;
+	add_pending_object(&rev, &commit->object, NULL);
+
+	for (j = remoteheads; j; j = j->next) {
+		j->item->object.flags &= ~UNINTERESTING;
+		add_pending_object(&rev, &j->item->object, NULL);
+	}
+
+	setup_revisions(0, NULL, &rev, NULL);
+	if (prepare_revision_walk(&rev))
+		die("revision walk setup failed");
+
+	strbuf_init(&out, 0);
+	strbuf_addstr(&out, "Squashed commit of the following:\n");
+	while ((commit = get_revision(&rev)) != NULL) {
+		strbuf_addch(&out, '\n');
+		strbuf_addf(&out, "commit %s\n",
+			sha1_to_hex(commit->object.sha1));
+		pretty_print_commit(rev.commit_format, commit, &out, rev.abbrev,
+			NULL, NULL, rev.date_mode, 0);
+	}
+	write(out_fd, out.buf, out.len);
+	strbuf_release(&out);
+}
+
+static int run_hook(const char *name)
+{
+	struct child_process hook;
+	const char *argv[3], *env[2];
+	char index[PATH_MAX];
+
+	snprintf(index, sizeof(index), "GIT_INDEX_FILE=%s", get_index_file());
+	env[0] = index;
+	env[1] = NULL;
+
+	argv[0] = git_path("hooks/%s", name);
+	if (squash)
+		argv[1] = "1";
+	else
+		argv[1] = "0";
+	argv[2] = NULL;
+
+	if (access(argv[0], X_OK) < 0)
+		return 0;
+
+	memset(&hook, 0, sizeof(hook));
+	hook.argv = argv;
+	hook.no_stdin = 1;
+	hook.stdout_to_stderr = 1;
+	hook.env = env;
+
+	return run_command(&hook);
+}
+
+static void finish(const unsigned char *new_head, const char *msg)
+{
+	struct strbuf reflog_message;
+	const char *argv_gc_auto[] = { "gc", "--auto", NULL };
+	struct diff_options opts;
+
+	strbuf_init(&reflog_message, 0);
+	if (!msg)
+		strbuf_addstr(&reflog_message, getenv("GIT_REFLOG_ACTION"));
+	else {
+		printf("%s\n", msg);
+		strbuf_addf(&reflog_message, "%s: %s",
+			getenv("GIT_REFLOG_ACTION"), msg);
+	}
+	if (squash) {
+		int fd;
+		printf("Squash commit -- not updating HEAD\n");
+		fd = open(git_path("SQUASH_MSG"), O_WRONLY | O_CREAT, 0666);
+		if (fd < 0)
+			die("Could not write to %s", git_path("SQUASH_MSG"));
+		squash_message(fd);
+		close(fd);
+	} else {
+		if (!merge_msg.len)
+			printf("No merge message -- not updating HEAD\n");
+		else {
+			update_ref(reflog_message.buf, "HEAD",
+				new_head, head, 0,
+				DIE_ON_ERR);
+			/*
+			 * We ignore errors in 'gc --auto', since the
+			 * user should see them.
+			 */
+			run_command_v_opt(argv_gc_auto, RUN_GIT_CMD);
+		}
+	}
+	if (new_head && show_diffstat) {
+		diff_setup(&opts);
+		opts.output_format |=
+			DIFF_FORMAT_SUMMARY | DIFF_FORMAT_DIFFSTAT;
+		opts.detect_rename = DIFF_DETECT_RENAME;
+		diff_tree_sha1(head, new_head, "", &opts);
+		diffcore_std(&opts);
+		diff_flush(&opts);
+	}
+
+	/* Run a post-merge hook */
+	run_hook("post-merge");
+
+	strbuf_release(&reflog_message);
+}
+
+/* Get the name for the merge commit's message. */
+static void merge_name(const char *remote, struct strbuf *msg)
+{
+	struct object *remote_head;
+	unsigned char branch_head[20], buf_sha[20];
+	struct strbuf buf;
+	char *ptr;
+	int match = 0;
+
+	memset(branch_head, 0, sizeof(branch_head));
+	remote_head = peel_to_type(remote, 0, NULL, OBJ_COMMIT);
+	if (!remote_head)
+		return;
+
+	strbuf_init(&buf, 0);
+	strbuf_addstr(&buf, "refs/heads/");
+	strbuf_addstr(&buf, remote);
+	get_sha1(buf.buf, branch_head);
+
+	if (!hashcmp(remote_head->sha1, branch_head)) {
+		strbuf_addf(msg, "%s\t\tbranch '%s' of .\n",
+			sha1_to_hex(branch_head), remote);
+		return;
+	}
+	/* See if remote matches <name>~<number>, or <name>^ */
+	ptr = strrchr(remote, '^');
+	if (ptr && *(ptr+1) == '\0')
+		match = 1;
+	else {
+		ptr = strrchr(remote, '~');
+		if (ptr && *(ptr+1) != '0' && isdigit(*(ptr+1))) {
+			ptr++;
+			match = 1;
+			while (*(++ptr))
+				if (!isdigit(*ptr)) {
+					match = 0;
+					break;
+				}
+		}
+	}
+	if (match) {
+		struct strbuf truname;
+		strbuf_addstr(&truname, remote);
+		strbuf_setlen(&truname, strrchr(truname.buf, '~')-truname.buf);
+		if (!get_sha1(truname.buf, buf_sha)) {
+			strbuf_addf(msg,
+				"%s\t\tbranch '%s' (early part) of .\n",
+				sha1_to_hex(remote_head->sha1), truname.buf);
+			return;
+		}
+	}
+
+	if (!strcmp(remote, "FETCH_HEAD") &&
+		!access(git_path("FETCH_HEAD"), R_OK)) {
+		FILE *fp;
+		struct strbuf line;
+		char *ptr;
+
+		strbuf_init(&line, 0);
+		fp = fopen(git_path("FETCH_HEAD"), "r");
+		if (fp == NULL)
+			die("could not open %s for reading: %s",
+				git_path("FETCH_HEAD"), strerror(errno));
+		strbuf_getline(&line, fp, '\n');
+		fclose(fp);
+		ptr = strstr(line.buf, "\tnot-for-merge\t");
+		if (ptr)
+			strbuf_remove(&line, ptr-line.buf+1, 13);
+		strbuf_addbuf(msg, &line);
+		strbuf_release(&line);
+		return;
+	}
+	strbuf_addf(msg, "%s\t\tcommit '%s'\n",
+		sha1_to_hex(remote_head->sha1), remote);
+}
+
+int git_merge_config(const char *k, const char *v, void *cb)
+{
+	if (branch && !prefixcmp(k, "branch.") &&
+		!prefixcmp(k + 7, branch) &&
+		!strcmp(k + 7 + strlen(branch), ".mergeoptions")) {
+		const char **argv;
+		int argc;
+		char *buf;
+
+		buf = xstrdup(v);
+		argc = split_cmdline(buf, &argv);
+		parse_options(argc, argv, builtin_merge_options,
+				builtin_merge_usage,
+				PARSE_OPT_ARGV0_IS_AN_OPTION);
+		free(buf);
+	}
+
+	if (!strcmp(k, "merge.diffstat") || !strcmp(k, "merge.stat"))
+		show_diffstat = git_config_bool(k, v);
+	else if (!strcmp(k, "pull.twohead"))
+		return git_config_string(&pull_twohead, k, v);
+	else if (!strcmp(k, "pull.octopus"))
+		return git_config_string(&pull_octopus, k, v);
+	return 0;
+}
+
+static int read_tree_trivial(unsigned char *common, unsigned char *head,
+	unsigned char *one)
+{
+	int i, nr_trees = 0;
+	struct tree *trees[MAX_UNPACK_TREES];
+	struct tree_desc t[MAX_UNPACK_TREES];
+	struct unpack_trees_options opts;
+
+	memset(&opts, 0, sizeof(opts));
+	opts.head_idx = -1;
+	opts.src_index = &the_index;
+	opts.dst_index = &the_index;
+	opts.update = 1;
+	opts.verbose_update = 1;
+	opts.trivial_merges_only = 1;
+	opts.merge = 1;
+	trees[nr_trees] = parse_tree_indirect(common);
+	if (!trees[nr_trees++])
+		return -1;
+	trees[nr_trees] = parse_tree_indirect(head);
+	if (!trees[nr_trees++])
+		return -1;
+	trees[nr_trees] = parse_tree_indirect(one);
+	if (!trees[nr_trees++])
+		return -1;
+	opts.fn = threeway_merge;
+	cache_tree_free(&active_cache_tree);
+	opts.head_idx = 2;
+	for (i = 0; i < nr_trees; i++) {
+		parse_tree(trees[i]);
+		init_tree_desc(t+i, trees[i]->buffer, trees[i]->size);
+	}
+	if (unpack_trees(nr_trees, t, &opts))
+		return -1;
+	return 0;
+}
+
+static int commit_tree_trivial(const char *msg, unsigned const char *tree,
+		struct commit_list *parents, unsigned char *ret)
+{
+	struct commit_list *i;
+	struct strbuf buf;
+	int encoding_is_utf8;
+
+	/* Not having i18n.commitencoding is the same as having utf-8 */
+	encoding_is_utf8 = is_encoding_utf8(git_commit_encoding);
+
+	strbuf_init(&buf, 8192); /* should avoid reallocs for the headers */
+	strbuf_addf(&buf, "tree %s\n", sha1_to_hex(tree));
+
+	for (i = parents; i; i = i->next)
+		strbuf_addf(&buf, "parent %s\n",
+			sha1_to_hex(i->item->object.sha1));
+
+	/* Person/date information */
+	strbuf_addf(&buf, "author %s\n",
+		git_author_info(IDENT_ERROR_ON_NO_NAME));
+	strbuf_addf(&buf, "committer %s\n",
+		git_committer_info(IDENT_ERROR_ON_NO_NAME));
+	if (!encoding_is_utf8)
+		strbuf_addf(&buf, "encoding %s\n", git_commit_encoding);
+	strbuf_addch(&buf, '\n');
+
+	/* And add the comment */
+	strbuf_addstr(&buf, msg);
+
+	write_sha1_file(buf.buf, buf.len, commit_type, ret);
+	strbuf_release(&buf);
+	return *ret;
+}
+
+static void write_tree_trivial(unsigned char *sha1)
+{
+	if (write_cache_as_tree(sha1, 0, NULL))
+		die("git write-tree failed to write a tree");
+}
+
+static int try_merge_strategy(char *strategy, struct commit_list *common,
+	struct strbuf *head_arg)
+{
+	const char **args;
+	int i = 0, ret;
+	struct commit_list *j;
+	struct strbuf buf;
+
+	args = xmalloc((4 + commit_list_count(common) +
+			commit_list_count(remoteheads)) * sizeof(char *));
+	strbuf_init(&buf, 0);
+	strbuf_addf(&buf, "merge-%s", strategy);
+	args[i++] = buf.buf;
+	for (j = common; j; j = j->next)
+		args[i++] = xstrdup(sha1_to_hex(j->item->object.sha1));
+	args[i++] = "--";
+	args[i++] = head_arg->buf;
+	for (j = remoteheads; j; j = j->next)
+		args[i++] = xstrdup(sha1_to_hex(j->item->object.sha1));
+	args[i] = NULL;
+	ret = run_command_v_opt(args, RUN_GIT_CMD);
+	strbuf_release(&buf);
+	i = 1;
+	for (j = common; j; j = j->next)
+		free((void *)args[i++]);
+	i += 2;
+	for (j = remoteheads; j; j = j->next)
+		free((void *)args[i++]);
+	free(args);
+	return -ret;
+}
+
+static void count_diff_files(struct diff_queue_struct *q,
+		struct diff_options *opt, void *data)
+{
+	int *count = data;
+
+	(*count) += q->nr;
+}
+
+static int count_unmerged_entries(void)
+{
+	const struct index_state *state = &the_index;
+	int i, ret = 0;
+
+	for (i = 0; i < state->cache_nr; i++)
+		if (ce_stage(state->cache[i]))
+			ret++;
+
+	return ret;
+}
+
+static int merge_one_remote(unsigned char *head, unsigned char *remote)
+{
+	struct tree *trees[MAX_UNPACK_TREES];
+	struct unpack_trees_options opts;
+	struct tree_desc t[MAX_UNPACK_TREES];
+	int i, fd, nr_trees = 0;
+	struct dir_struct *dir;
+	struct lock_file lock_file;
+
+	memset(&lock_file, 0, sizeof(lock_file));
+	if (read_cache_unmerged())
+		die("you need to resolve your current index first");
+
+	fd = hold_locked_index(&lock_file, 1);
+
+	memset(&trees, 0, sizeof(trees));
+	memset(&opts, 0, sizeof(opts));
+	memset(&t, 0, sizeof(t));
+	dir = xcalloc(1, sizeof(*opts.dir));
+	dir->show_ignored = 1;
+	dir->exclude_per_dir = ".gitignore";
+	opts.dir = dir;
+
+	opts.head_idx = 1;
+	opts.src_index = &the_index;
+	opts.dst_index = &the_index;
+	opts.update = 1;
+	opts.verbose_update = 1;
+	opts.merge = 1;
+	opts.fn = twoway_merge;
+
+	trees[nr_trees] = parse_tree_indirect(head);
+	if (!trees[nr_trees++])
+		return -1;
+	trees[nr_trees] = parse_tree_indirect(remote);
+	if (!trees[nr_trees++])
+		return -1;
+	for (i = 0; i < nr_trees; i++) {
+		parse_tree(trees[i]);
+		init_tree_desc(t+i, trees[i]->buffer, trees[i]->size);
+	}
+	if (unpack_trees(nr_trees, t, &opts))
+		return -1;
+	if (write_cache(fd, active_cache, active_nr) ||
+		commit_locked_index(&lock_file))
+		die("unable to write new index file");
+	return 0;
+}
+
+static void split_merge_strategies(const char *string, struct path_list *list)
+{
+	char *p, *q, *buf;
+
+	if (!string)
+		return;
+
+	list->strdup_paths = 1;
+	buf = xstrdup(string);
+	q = buf;
+	while (1) {
+		p = strchr(q, ' ');
+		if (!p) {
+			path_list_append(q, list);
+			free(buf);
+			return;
+		} else {
+			*p = '\0';
+			path_list_append(q, list);
+			q = ++p;
+		}
+	}
+}
+
+static void add_strategies(const char *string, enum strategy strategy)
+{
+	struct path_list list;
+	int i;
+
+	memset(&list, 0, sizeof(list));
+	split_merge_strategies(string, &list);
+	if (list.nr) {
+		for (i = 0; i < list.nr; i++) {
+			struct path_list_item *item;
+
+			item = unsorted_path_list_lookup(list.items[i].path,
+				&strategies);
+			if (item)
+				path_list_append_strategy(list.items[i].path,
+					item->util, &use_strategies);
+		}
+		return;
+	}
+	for (i = 0; i < strategies.nr; i++)
+		if ((enum strategy)strategies.items[i].util & strategy)
+			path_list_append_strategy(strategies.items[i].path,
+				strategies.items[i].util,
+				&use_strategies);
+}
+
+int cmd_merge(int argc, const char **argv, const char *prefix)
+{
+	unsigned char sha1[20], result_tree[20];
+	struct object *second_token = NULL;
+	struct strbuf buf, head_arg;
+	int flag, head_invalid, i, single_strategy;
+	int best_cnt = -1, merge_was_ok = 0, automerge_was_ok = 0;
+	struct commit_list *common = NULL;
+	struct path_list_item *best_strategy = NULL, *wt_strategy = NULL;
+	struct commit_list **remotes = &remoteheads;
+
+	setup_work_tree();
+	if (unmerged_cache())
+		die("You are in the middle of a conflicted merge.");
+
+	/*
+	 * Check if we are _not_ on a detached HEAD, i.e. if there is a
+	 * current branch.
+	 */
+	branch = resolve_ref("HEAD", sha1, 0, &flag);
+	if (branch && flag & REF_ISSYMREF) {
+		const char *ptr = skip_prefix(branch, "refs/heads/");
+		if (ptr)
+			branch = ptr;
+	}
+
+	git_config(git_merge_config, NULL);
+
+	argc = parse_options(argc, argv, builtin_merge_options,
+			builtin_merge_usage, 0);
+
+	if (squash) {
+		if (!allow_fast_forward)
+			die("You cannot combine --squash with --no-ff.");
+		option_commit = 0;
+	}
+
+	if (argc == 0)
+		usage_with_options(builtin_merge_usage,
+			builtin_merge_options);
+
+	/*
+	 * This could be traditional "merge <msg> HEAD <commit>..."  and
+	 * the way we can tell it is to see if the second token is HEAD,
+	 * but some people might have misused the interface and used a
+	 * committish that is the same as HEAD there instead.
+	 * Traditional format never would have "-m" so it is an
+	 * additional safety measure to check for it.
+	 */
+	strbuf_init(&buf, 0);
+	strbuf_init(&head_arg, 0);
+	if (argc > 1)
+		second_token = peel_to_type(argv[1], 0, NULL, OBJ_COMMIT);
+	head_invalid = get_sha1("HEAD", head);
+
+	if (!have_message && second_token &&
+		!hashcmp(second_token->sha1, head)) {
+		strbuf_addstr(&merge_msg, argv[0]);
+		strbuf_addstr(&head_arg, argv[1]);
+		argv += 2;
+		argc -= 2;
+	} else if (head_invalid) {
+		struct object *remote_head;
+		/*
+		 * If the merged head is a valid one there is no reason
+		 * to forbid "git merge" into a branch yet to be born.
+		 * We do the same for "git pull".
+		 */
+		if (argc != 1)
+			die("Can merge only exactly one commit into "
+				"empty head");
+		remote_head = peel_to_type(argv[0], 0, NULL, OBJ_COMMIT);
+		if (!remote_head)
+			die("%s - not something we can merge", argv[0]);
+		update_ref("initial pull", "HEAD", remote_head->sha1, NULL, 0,
+				DIE_ON_ERR);
+		reset_hard(remote_head->sha1, 0);
+		return 0;
+	} else {
+		/* We are invoked directly as the first-class UI. */
+		strbuf_addstr(&head_arg, "HEAD");
+		if (!merge_msg.len) {
+			/*
+			 * All the rest are the commits being merged;
+			 * prepare the standard merge summary message to
+			 * be appended to the given message.  If remote
+			 * is invalid we will die later in the common
+			 * codepath so we discard the error in this
+			 * loop.
+			 */
+			struct strbuf msg;
+
+			strbuf_init(&msg, 0);
+			for (i = 0; i < argc; i++)
+				merge_name(argv[i], &msg);
+			fmt_merge_msg(option_log, &msg, &merge_msg);
+			if (merge_msg.len)
+				strbuf_setlen(&merge_msg, merge_msg.len-1);
+		}
+	}
+
+	if (head_invalid || argc == 0)
+		usage_with_options(builtin_merge_usage,
+			builtin_merge_options);
+
+	strbuf_addstr(&buf, "merge");
+	for (i = 0; i < argc; i++)
+		strbuf_addf(&buf, " %s", argv[i]);
+	setenv("GIT_REFLOG_ACTION", buf.buf, 0);
+	strbuf_reset(&buf);
+
+	for (i = 0; i < argc; i++) {
+		struct object *o;
+
+		o = peel_to_type(argv[i], 0, NULL, OBJ_COMMIT);
+		if (!o)
+			die("%s - not something we can merge", argv[i]);
+		remotes = &commit_list_insert(lookup_commit(o->sha1),
+			remotes)->next;
+
+		strbuf_addf(&buf, "GITHEAD_%s", sha1_to_hex(o->sha1));
+		setenv(buf.buf, argv[i], 1);
+		strbuf_reset(&buf);
+	}
+
+	if (!use_strategies.nr) {
+		if (!remoteheads->next)
+			add_strategies(pull_twohead, DEFAULT_TWOHEAD);
+		else
+			add_strategies(pull_octopus, DEFAULT_OCTOPUS);
+	}
+
+	for (i = 0; i < use_strategies.nr; i++) {
+		if ((unsigned int)use_strategies.items[i].util &
+			NO_FAST_FORWARD)
+			allow_fast_forward = 0;
+		if ((unsigned int)use_strategies.items[i].util & NO_TRIVIAL)
+			allow_trivial = 0;
+	}
+
+	if (!remoteheads->next)
+		common = get_merge_bases(lookup_commit(head),
+				remoteheads->item, 1);
+	else {
+		struct commit_list *list = remoteheads;
+		commit_list_insert(lookup_commit(head), &list);
+		common = get_octopus_merge_bases(list);
+	}
+
+	update_ref("updating ORIG_HEAD", "ORIG_HEAD", head, NULL, 0,
+		DIE_ON_ERR);
+
+	if (!common)
+		; /* No common ancestors found. We need a real merge. */
+	else if (!remoteheads->next &&
+		!hashcmp(common->item->object.sha1,
+		remoteheads->item->object.sha1)) {
+		/*
+		 * If head can reach all the merge then we are up to
+		 * date.
+		 */
+		finish_up_to_date("Already up-to-date.");
+		return 0;
+	} else if (allow_fast_forward && !remoteheads->next &&
+		!hashcmp(common->item->object.sha1, head)) {
+		/* Again the most common case of merging one remote. */
+		struct strbuf msg;
+		struct object *o;
+
+		printf("Updating %s..%s\n",
+			find_unique_abbrev(head, DEFAULT_ABBREV),
+			find_unique_abbrev(remoteheads->item->object.sha1,
+			DEFAULT_ABBREV));
+		refresh_cache(REFRESH_QUIET);
+		strbuf_init(&msg, 0);
+		strbuf_addstr(&msg, "Fast forward");
+		if (have_message)
+			strbuf_addstr(&msg,
+				" (no commit created; -m option ignored)");
+		o = peel_to_type(sha1_to_hex(remoteheads->item->object.sha1),
+			0, NULL, OBJ_COMMIT);
+		if (!o)
+			return 0;
+
+		if (merge_one_remote(head, remoteheads->item->object.sha1))
+			return 0;
+
+		finish(o->sha1, msg.buf);
+		dropsave();
+		return 0;
+	} else if (!remoteheads->next && common->next)
+		;
+		/*
+		 * We are not doing octopus and not fast forward.  Need
+		 * a real merge.
+		 */
+	else if (!remoteheads->next && option_commit) {
+		/*
+		 * We are not doing octopus and not fast forward.  Need
+		 * a real merge.
+		 */
+		refresh_cache(REFRESH_QUIET);
+		if (allow_trivial) {
+			/* See if it is really trivial. */
+			git_committer_info(IDENT_ERROR_ON_NO_NAME);
+			printf("Trying really trivial in-index merge...\n");
+			if (!read_tree_trivial(common->item->object.sha1,
+					head, remoteheads->item->object.sha1)) {
+				unsigned char result_tree[20],
+					result_commit[20];
+				struct commit_list parent;
+
+				write_tree_trivial(result_tree);
+				printf("Wonderful.\n");
+				parent.item = remoteheads->item;
+				parent.next = NULL;
+				commit_tree_trivial(merge_msg.buf,
+					result_tree, &parent,
+					result_commit);
+				finish(result_commit, "In-index merge");
+				dropsave();
+				return 0;
+			}
+			printf("Nope.\n");
+		}
+	} else {
+		/*
+		 * An octopus.  If we can reach all the remote we are up
+		 * to date.
+		 */
+		int up_to_date = 1;
+		struct commit_list *j;
+
+		for (j = remoteheads; j; j = j->next) {
+			struct commit_list *common_one;
+
+			common_one = get_merge_bases(lookup_commit(head),
+				j->item, 1);
+			if (hashcmp(common_one->item->object.sha1,
+				j->item->object.sha1)) {
+				up_to_date = 0;
+				break;
+			}
+		}
+		if (up_to_date) {
+			finish_up_to_date("Already up-to-date. Yeeah!");
+			return 0;
+		}
+	}
+
+	/* We are going to make a new commit. */
+	git_committer_info(IDENT_ERROR_ON_NO_NAME);
+
+	/*
+	 * At this point, we need a real merge.  No matter what strategy
+	 * we use, it would operate on the index, possibly affecting the
+	 * working tree, and when resolved cleanly, have the desired
+	 * tree in the index -- this means that the index must be in
+	 * sync with the head commit.  The strategies are responsible
+	 * to ensure this.
+	 */
+	if (use_strategies.nr != 1) {
+		/*
+		 * Stash away the local changes so that we can try more
+		 * than one.
+		 */
+		save_state();
+		single_strategy = 0;
+	} else {
+		unlink(git_path("MERGE_STASH"));
+		single_strategy = 1;
+	}
+
+	for (i = 0; i < use_strategies.nr; i++) {
+		int ret;
+		if (i) {
+			printf("Rewinding the tree to pristine...\n");
+			restore_state();
+		}
+		if (!single_strategy)
+			printf("Trying merge strategy %s...\n",
+				use_strategies.items[i].path);
+		/*
+		 * Remember which strategy left the state in the working
+		 * tree.
+		 */
+		wt_strategy = &use_strategies.items[i];
+
+		ret = try_merge_strategy(use_strategies.items[i].path,
+			common, &head_arg);
+		if (!option_commit && !ret) {
+			merge_was_ok = 1;
+			ret = 1;
+		}
+
+		if (ret) {
+			/*
+			 * The backend exits with 1 when conflicts are
+			 * left to be resolved, with 2 when it does not
+			 * handle the given merge at all.
+			 */
+			if (ret == 1) {
+				int cnt = 0;
+				struct rev_info rev;
+
+				if (read_cache() < 0)
+					die("failed to read the cache");
+
+				/* Check how many files differ. */
+				init_revisions(&rev, "");
+				setup_revisions(0, NULL, &rev, NULL);
+				rev.diffopt.output_format |=
+					DIFF_FORMAT_CALLBACK;
+				rev.diffopt.format_callback = count_diff_files;
+				rev.diffopt.format_callback_data = &cnt;
+				run_diff_files(&rev, 0);
+
+				/*
+				 * Check how many unmerged entries are
+				 * there.
+				 */
+				cnt += count_unmerged_entries();
+
+				if (best_cnt <= 0 || cnt <= best_cnt) {
+					best_strategy =
+						&use_strategies.items[i];
+					best_cnt = cnt;
+				}
+			}
+			continue;
+		}
+
+		/* Automerge succeeded. */
+		write_tree_trivial(result_tree);
+		automerge_was_ok = 1;
+		break;
+	}
+
+	/*
+	 * If we have a resulting tree, that means the strategy module
+	 * auto resolved the merge cleanly.
+	 */
+	if (automerge_was_ok) {
+		struct commit_list *parents = NULL, *j;
+		unsigned char result_commit[20];
+
+		free_commit_list(common);
+		if (allow_fast_forward) {
+			parents = remoteheads;
+			commit_list_insert(lookup_commit(head), &parents);
+			parents = reduce_heads(parents);
+		} else {
+			struct commit_list **pptr = &parents;
+
+			pptr = &commit_list_insert(lookup_commit(head),
+				pptr)->next;
+			for (j = remoteheads; j; j = j->next)
+				pptr = &commit_list_insert(j->item, pptr)->next;
+		}
+		free_commit_list(remoteheads);
+		strbuf_addch(&merge_msg, '\n');
+		commit_tree_trivial(merge_msg.buf, result_tree, parents,
+			result_commit);
+		free_commit_list(parents);
+		strbuf_addf(&buf, "Merge made by %s.", wt_strategy->path);
+		finish(result_commit, buf.buf);
+		strbuf_release(&buf);
+		dropsave();
+		return 0;
+	}
+
+	/*
+	 * Pick the result from the best strategy and have the user fix
+	 * it up.
+	 */
+	if (!best_strategy) {
+		restore_state();
+		if (use_strategies.nr > 1)
+			fprintf(stderr,
+				"No merge strategy handled the merge.\n");
+		else
+			fprintf(stderr, "Merge with strategy %s failed.\n",
+				use_strategies.items[0].path);
+		return 2;
+	} else if (best_strategy == wt_strategy)
+		; /* We already have its result in the working tree. */
+	else {
+		printf("Rewinding the tree to pristine...\n");
+		restore_state();
+		printf("Using the %s to prepare resolving by hand.\n",
+			best_strategy->path);
+		try_merge_strategy(best_strategy->path, common, &head_arg);
+	}
+
+	if (squash)
+		finish(NULL, NULL);
+	else {
+		int fd;
+		struct commit_list *j;
+
+		for (j = remoteheads; j; j = j->next)
+			strbuf_addf(&buf, "%s\n",
+				sha1_to_hex(j->item->object.sha1));
+		fd = open(git_path("MERGE_HEAD"), O_WRONLY | O_CREAT, 0666);
+		if (fd < 0)
+			die("Could open %s for writing",
+				git_path("MERGE_HEAD"));
+		if (write_in_full(fd, buf.buf, buf.len) != buf.len)
+			die("Could not write to %s", git_path("MERGE_HEAD"));
+		close(fd);
+		strbuf_addch(&merge_msg, '\n');
+		fd = open(git_path("MERGE_MSG"), O_WRONLY | O_CREAT, 0666);
+		if (fd < 0)
+			die("Could open %s for writing", git_path("MERGE_MSG"));
+		if (write_in_full(fd, merge_msg.buf, merge_msg.len) !=
+			merge_msg.len)
+			die("Could not write to %s", git_path("MERGE_MSG"));
+		close(fd);
+	}
+
+	if (merge_was_ok) {
+		fprintf(stderr, "Automatic merge went well; "
+			"stopped before committing as requested\n");
+		return 0;
+	} else {
+		FILE *fp;
+		int pos;
+		const char *argv_rerere[] = { "rerere", NULL };
+
+		fp = fopen(git_path("MERGE_MSG"), "a");
+		if (!fp)
+			die("Could open %s for writing", git_path("MERGE_MSG"));
+		fprintf(fp, "\nConflicts:\n");
+		for (pos = 0; pos < active_nr; pos++) {
+			struct cache_entry *ce = active_cache[pos];
+
+			if (ce_stage(ce)) {
+				fprintf(fp, "\t%s\n", ce->name);
+				while (pos + 1 < active_nr &&
+					!strcmp(ce->name,
+					active_cache[pos + 1]->name))
+					pos++;
+			}
+		}
+		fclose(fp);
+		run_command_v_opt(argv_rerere, RUN_GIT_CMD);
+		printf("Automatic merge failed; "
+			"fix conflicts and then commit the result.\n");
+		return 1;
+	}
+}
diff --git a/builtin.h b/builtin.h
index f069ee7..64830ae 100644
--- a/builtin.h
+++ b/builtin.h
@@ -60,6 +60,7 @@ extern int cmd_ls_tree(int argc, const char **argv, const char *prefix);
 extern int cmd_ls_remote(int argc, const char **argv, const char *prefix);
 extern int cmd_mailinfo(int argc, const char **argv, const char *prefix);
 extern int cmd_mailsplit(int argc, const char **argv, const char *prefix);
+extern int cmd_merge(int argc, const char **argv, const char *prefix);
 extern int cmd_merge_base(int argc, const char **argv, const char *prefix);
 extern int cmd_merge_ours(int argc, const char **argv, const char *prefix);
 extern int cmd_merge_file(int argc, const char **argv, const char *prefix);
diff --git a/git-merge.sh b/contrib/examples/git-merge.sh
similarity index 100%
rename from git-merge.sh
rename to contrib/examples/git-merge.sh
diff --git a/git.c b/git.c
index 80b16ce..d4c5027 100644
--- a/git.c
+++ b/git.c
@@ -271,6 +271,7 @@ static void handle_internal_command(int argc, const char **argv)
 		{ "ls-remote", cmd_ls_remote },
 		{ "mailinfo", cmd_mailinfo },
 		{ "mailsplit", cmd_mailsplit },
+		{ "merge", cmd_merge, RUN_SETUP | NEED_WORK_TREE },
 		{ "merge-base", cmd_merge_base, RUN_SETUP },
 		{ "merge-file", cmd_merge_file },
 		{ "merge-ours", cmd_merge_ours, RUN_SETUP },
-- 
1.5.6

[PATCH 13/13] Add new test case to ensure git-merge filters for independent parents

[Miklos Vajna]

The old shell version used show-branch --independent to filter for the
ones that cannot be reached from any other reference.

The new C version uses filter_independent() from commit.c for this, so
add test to ensure it works as expected.

Signed-off-by: Miklos Vajna <vmiklos@frugalware.org>
---
 t/t7603-merge-filter-independent.sh |   63 +++++++++++++++++++++++++++++++++++
 1 files changed, 63 insertions(+), 0 deletions(-)
 create mode 100755 t/t7603-merge-filter-independent.sh

diff --git a/t/t7603-merge-filter-independent.sh b/t/t7603-merge-filter-independent.sh
new file mode 100755
index 0000000..e9249cd
--- /dev/null
+++ b/t/t7603-merge-filter-independent.sh
@@ -0,0 +1,63 @@
+#!/bin/sh
+
+test_description='git-merge
+
+Testing octopus merge when filtering independent branches.'
+
+. ./test-lib.sh
+
+# 0 - 1
+#   \ 2
+#   \ 3
+#   \ 4 - 5
+#
+# So 1, 2, 3 and 5 should be kept, 4 should be filtered.
+
+test_expect_success 'setup' '
+	echo c0 > c0.c &&
+	git add c0.c &&
+	git commit -m c0 &&
+	git tag c0 &&
+	echo c1 > c1.c &&
+	git add c1.c &&
+	git commit -m c1 &&
+	git tag c1 &&
+	git reset --hard c0 &&
+	echo c2 > c2.c &&
+	git add c2.c &&
+	git commit -m c2 &&
+	git tag c2 &&
+	git reset --hard c0 &&
+	echo c3 > c3.c &&
+	git add c3.c &&
+	git commit -m c3 &&
+	git tag c3 &&
+	git reset --hard c0 &&
+	echo c4 > c4.c &&
+	git add c4.c &&
+	git commit -m c4 &&
+	git tag c4 &&
+	echo c5 > c5.c &&
+	git add c5.c &&
+	git commit -m c5 &&
+	git tag c5
+'
+
+test_expect_success 'merge c1 with c2, c3, c4, c5' '
+	git reset --hard c1 &&
+	git merge c2 c3 c4 c5 &&
+	test "$(git rev-parse c1)" != "$(git rev-parse HEAD)" &&
+	test "$(git rev-parse c1)" = "$(git rev-parse HEAD^1)" &&
+	test "$(git rev-parse c2)" = "$(git rev-parse HEAD^2)" &&
+	test "$(git rev-parse c3)" = "$(git rev-parse HEAD^3)" &&
+	test "$(git rev-parse c5)" = "$(git rev-parse HEAD^4)" &&
+	git diff --exit-code &&
+	test -f c0.c &&
+	test -f c1.c &&
+	test -f c2.c &&
+	test -f c3.c &&
+	test -f c4.c &&
+	test -f c5.c
+'
+
+test_done
-- 
1.5.6

[PATCH 13/13] Add new test case to ensure git-merge reduces octopus parents when possible

[Miklos Vajna]

The old shell version used show-branch --independent to filter for the
ones that cannot be reached from any other reference.

The new C version uses reduce_heads() from commit.c for this, so
add test to ensure it works as expected.

Signed-off-by: Miklos Vajna <vmiklos@frugalware.org>
---

On Sat, Jun 21, 2008 at 07:00:50PM +0200, Miklos Vajna <vmiklos@frugalware.org> wrote:
> The new C version uses filter_independent() from commit.c for this, so
> add test to ensure it works as expected.

Ouch, this info is now outdated. I updated the commit message and
renamed the test, no functional changes.

 t/t7603-merge-reduce-heads.sh |   63 +++++++++++++++++++++++++++++++++++++++++
 1 files changed, 63 insertions(+), 0 deletions(-)
 create mode 100755 t/t7603-merge-reduce-heads.sh

diff --git a/t/t7603-merge-reduce-heads.sh b/t/t7603-merge-reduce-heads.sh
new file mode 100755
index 0000000..17b19dc
--- /dev/null
+++ b/t/t7603-merge-reduce-heads.sh
@@ -0,0 +1,63 @@
+#!/bin/sh
+
+test_description='git-merge
+
+Testing octopus merge when reducing parents to independent branches.'
+
+. ./test-lib.sh
+
+# 0 - 1
+#   \ 2
+#   \ 3
+#   \ 4 - 5
+#
+# So 1, 2, 3 and 5 should be kept, 4 should be avoided.
+
+test_expect_success 'setup' '
+	echo c0 > c0.c &&
+	git add c0.c &&
+	git commit -m c0 &&
+	git tag c0 &&
+	echo c1 > c1.c &&
+	git add c1.c &&
+	git commit -m c1 &&
+	git tag c1 &&
+	git reset --hard c0 &&
+	echo c2 > c2.c &&
+	git add c2.c &&
+	git commit -m c2 &&
+	git tag c2 &&
+	git reset --hard c0 &&
+	echo c3 > c3.c &&
+	git add c3.c &&
+	git commit -m c3 &&
+	git tag c3 &&
+	git reset --hard c0 &&
+	echo c4 > c4.c &&
+	git add c4.c &&
+	git commit -m c4 &&
+	git tag c4 &&
+	echo c5 > c5.c &&
+	git add c5.c &&
+	git commit -m c5 &&
+	git tag c5
+'
+
+test_expect_success 'merge c1 with c2, c3, c4, c5' '
+	git reset --hard c1 &&
+	git merge c2 c3 c4 c5 &&
+	test "$(git rev-parse c1)" != "$(git rev-parse HEAD)" &&
+	test "$(git rev-parse c1)" = "$(git rev-parse HEAD^1)" &&
+	test "$(git rev-parse c2)" = "$(git rev-parse HEAD^2)" &&
+	test "$(git rev-parse c3)" = "$(git rev-parse HEAD^3)" &&
+	test "$(git rev-parse c5)" = "$(git rev-parse HEAD^4)" &&
+	git diff --exit-code &&
+	test -f c0.c &&
+	test -f c1.c &&
+	test -f c2.c &&
+	test -f c3.c &&
+	test -f c4.c &&
+	test -f c5.c
+'
+
+test_done
-- 
1.5.6

Re: [PATCH 12/13] Build in merge

[Olivier Marin]

Hi,

I did not read your patches yet but I noticed the two following bugs while testing
current pu.

Miklos Vajna a écrit :
>
> +static void finish(const unsigned char *new_head, const char *msg)
> +{

[...]

> +	if (new_head && show_diffstat) {
> +		diff_setup(&opts);
> +		opts.output_format |=
> +			DIFF_FORMAT_SUMMARY | DIFF_FORMAT_DIFFSTAT;
> +		opts.detect_rename = DIFF_DETECT_RENAME;

You probably want to add DIFF_OPT_SET(&opts, COLOR_DIFF) to have a nice colored diff
like the original script.

> +		diff_tree_sha1(head, new_head, "", &opts);
> +		diffcore_std(&opts);
> +		diff_flush(&opts);
> +	}

[...]

> +int cmd_merge(int argc, const char **argv, const char *prefix)
> +{

[...]

> +	} else if (allow_fast_forward && !remoteheads->next &&
> +		!hashcmp(common->item->object.sha1, head)) {
> +		/* Again the most common case of merging one remote. */
> +		struct strbuf msg;
> +		struct object *o;
> +
> +		printf("Updating %s..%s\n",
> +			find_unique_abbrev(head, DEFAULT_ABBREV),
> +			find_unique_abbrev(remoteheads->item->object.sha1,
> +			DEFAULT_ABBREV));

Here, the second call to find_unique_abbrev() will overwrite the previous returned
value because this function return a pointer to a static buffer.

Olivier.

Re: [PATCH 12/13] Build in merge

[Miklos Vajna]

[-- Attachment #1: Type: text/plain, Size: 2670 bytes --]

On Wed, Jun 25, 2008 at 06:22:45PM +0200, Olivier Marin <dkr+ml.git@free.fr> wrote:
> > +	if (new_head && show_diffstat) {
> > +		diff_setup(&opts);
> > +		opts.output_format |=
> > +			DIFF_FORMAT_SUMMARY | DIFF_FORMAT_DIFFSTAT;
> > +		opts.detect_rename = DIFF_DETECT_RENAME;
> 
> You probably want to add DIFF_OPT_SET(&opts, COLOR_DIFF) to have a nice colored diff
> like the original script.

That would always turn colors on.

This should respect diff.color:

diff --git a/builtin-merge.c b/builtin-merge.c
index 66189d2..c2a32ee 100644
--- a/builtin-merge.c
+++ b/builtin-merge.c
@@ -331,6 +331,8 @@ static void finish(const unsigned char *new_head, const char *msg)
 		opts.output_format |=
 			DIFF_FORMAT_SUMMARY | DIFF_FORMAT_DIFFSTAT;
 		opts.detect_rename = DIFF_DETECT_RENAME;
+		if (diff_use_color_default > 0)
+			DIFF_OPT_SET(&opts, COLOR_DIFF);
 		diff_tree_sha1(head, new_head, "", &opts);
 		diffcore_std(&opts);
 		diff_flush(&opts);
@@ -693,6 +695,7 @@ int cmd_merge(int argc, const char **argv, const char *prefix)
 	}
 
 	git_config(git_merge_config, NULL);
+	git_config(git_diff_ui_config, NULL);
 
 	argc = parse_options(argc, argv, builtin_merge_options,
 			builtin_merge_usage, 0);

> > +int cmd_merge(int argc, const char **argv, const char *prefix)
> > +{
> 
> [...]
> 
> > +	} else if (allow_fast_forward && !remoteheads->next &&
> > +		!hashcmp(common->item->object.sha1, head)) {
> > +		/* Again the most common case of merging one remote. */
> > +		struct strbuf msg;
> > +		struct object *o;
> > +
> > +		printf("Updating %s..%s\n",
> > +			find_unique_abbrev(head, DEFAULT_ABBREV),
> > +			find_unique_abbrev(remoteheads->item->object.sha1,
> > +			DEFAULT_ABBREV));
> 
> Here, the second call to find_unique_abbrev() will overwrite the previous returned
> value because this function return a pointer to a static buffer.

This should fix it:

diff --git a/builtin-merge.c b/builtin-merge.c
index cc04d01..77de9e8 100644
--- a/builtin-merge.c
+++ b/builtin-merge.c
@@ -836,9 +836,12 @@ int cmd_merge(int argc, const char **argv, const char *prefix)
 		/* Again the most common case of merging one remote. */
 		struct strbuf msg;
 		struct object *o;
+		char hex[41];
+
+		memcpy(hex, find_unique_abbrev(head, DEFAULT_ABBREV), 41);
 
 		printf("Updating %s..%s\n",
-			find_unique_abbrev(head, DEFAULT_ABBREV),
+			hex,
 			find_unique_abbrev(remoteheads->item->object.sha1,
 			DEFAULT_ABBREV));
 		refresh_cache(REFRESH_QUIET);

I pushed both to my working branch and I'll send proper patches to this
list among with other small changes soon.

Thanks!

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: [PATCH 12/13] Build in merge

[Olivier Marin]

Miklos Vajna a écrit :
> 
> This should respect diff.color:

Absolutely. And also color.ui. The following patch should do the trick:

diff --git a/builtin-merge.c b/builtin-merge.c
index 98adca5..cf557f7 100644
--- a/builtin-merge.c
+++ b/builtin-merge.c
@@ -7,6 +7,7 @@
  */
 
 #include "cache.h"
+#include "color.h"
 #include "parse-options.h"
 #include "builtin.h"
 #include "run-command.h"
@@ -712,6 +713,9 @@ int cmd_merge(int argc, const char **argv, const char *prefix)
        git_config(git_merge_config, NULL);
        git_config(git_diff_ui_config, NULL);
 
+       if (diff_use_color_default == -1)
+               diff_use_color_default = git_use_color_default;
+
        argc = parse_options(argc, argv, builtin_merge_options,
                        builtin_merge_usage, 0);
 

Olivier.

Re: [PATCH 12/13] Build in merge

[Johannes Schindelin]

Hi,

On Fri, 27 Jun 2008, Miklos Vajna wrote:

> diff --git a/builtin-merge.c b/builtin-merge.c
> index cc04d01..77de9e8 100644
> --- a/builtin-merge.c
> +++ b/builtin-merge.c
> @@ -836,9 +836,12 @@ int cmd_merge(int argc, const char **argv, const char *prefix)
>  		/* Again the most common case of merging one remote. */
>  		struct strbuf msg;
>  		struct object *o;
> +		char hex[41];
> +
> +		memcpy(hex, find_unique_abbrev(head, DEFAULT_ABBREV), 41);

Maybe strcpy(hex, find_unique_abbrev(head, DEFAULT_ABBREV)) would be more 
intuitive?

Ciao,
Dscho

Re: [PATCH 12/13] Build in merge

[Miklos Vajna]

[-- Attachment #1: Type: text/plain, Size: 1033 bytes --]

On Fri, Jun 27, 2008 at 01:03:20PM +0200, Olivier Marin <dkr+ml.git@free.fr> wrote:
> Absolutely. And also color.ui. The following patch should do the trick:
> 
> diff --git a/builtin-merge.c b/builtin-merge.c
> index 98adca5..cf557f7 100644
> --- a/builtin-merge.c
> +++ b/builtin-merge.c
> @@ -7,6 +7,7 @@
>   */
>  
>  #include "cache.h"
> +#include "color.h"
>  #include "parse-options.h"
>  #include "builtin.h"
>  #include "run-command.h"
> @@ -712,6 +713,9 @@ int cmd_merge(int argc, const char **argv, const char *prefix)
>         git_config(git_merge_config, NULL);
>         git_config(git_diff_ui_config, NULL);
>  
> +       if (diff_use_color_default == -1)
> +               diff_use_color_default = git_use_color_default;
> +
>         argc = parse_options(argc, argv, builtin_merge_options,
>                         builtin_merge_usage, 0);

Have you tried this?

First, you need to call git_get_colorbool_config(), second this won't
respect diff.color, while my patch does.

Thanks.

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: [PATCH 12/13] Build in merge

[Miklos Vajna]

[-- Attachment #1: Type: text/plain, Size: 322 bytes --]

On Fri, Jun 27, 2008 at 12:56:02PM +0100, Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:
> > +		char hex[41];
> > +
> > +		memcpy(hex, find_unique_abbrev(head, DEFAULT_ABBREV), 41);
> 
> Maybe strcpy(hex, find_unique_abbrev(head, DEFAULT_ABBREV)) would be more 
> intuitive?

Ah yes. Changed.

Thanks.

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: [PATCH 12/13] Build in merge

[Olivier Marin]

Miklos Vajna a écrit :
> On Fri, Jun 27, 2008 at 01:03:20PM +0200, Olivier Marin <dkr+ml.git@free.fr> wrote:
>> Absolutely. And also color.ui. The following patch should do the trick:
>>
>> diff --git a/builtin-merge.c b/builtin-merge.c
>> index 98adca5..cf557f7 100644
>> --- a/builtin-merge.c
>> +++ b/builtin-merge.c
>> @@ -7,6 +7,7 @@
>>   */
>>  
>>  #include "cache.h"
>> +#include "color.h"
>>  #include "parse-options.h"
>>  #include "builtin.h"
>>  #include "run-command.h"
>> @@ -712,6 +713,9 @@ int cmd_merge(int argc, const char **argv, const char *prefix)
>>         git_config(git_merge_config, NULL);
>>         git_config(git_diff_ui_config, NULL);
>>  
>> +       if (diff_use_color_default == -1)
>> +               diff_use_color_default = git_use_color_default;
>> +
>>         argc = parse_options(argc, argv, builtin_merge_options,
>>                         builtin_merge_usage, 0);
> 
> Have you tried this?

I did. I forget to say that it's on top of your patch, sorry.

> First, you need to call git_get_colorbool_config(), second this won't
> respect diff.color, while my patch does.

git_get_colorbool_config() is called via git_diff_ui_config.

Olivier.

Re: [PATCH 12/13] Build in merge

[Miklos Vajna]

[-- Attachment #1: Type: text/plain, Size: 578 bytes --]

On Fri, Jun 27, 2008 at 03:04:52PM +0200, Olivier Marin <dkr@freesurf.fr> wrote:
> >> +       if (diff_use_color_default == -1)
> >> +               diff_use_color_default = git_use_color_default;
> >> +
> >>         argc = parse_options(argc, argv, builtin_merge_options,
> >>                         builtin_merge_usage, 0);
> > 
> > Have you tried this?
> 
> I did. I forget to say that it's on top of your patch, sorry.

Aah. I should have noticed that.

I see now, your hunk is necessary when color.diff and diff.color is not
set but color.ui is.

Thanks.

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]