[PATCH 00/10] Build in merge

[PATCH 00/10] Build in merge

[Miklos Vajna]

Hi,

It was almost a week ago I posted the previous series here and there
were numerous improvements since then.

A short changelog:

 - introducing filter_independent() in commit.c

 - avoiding commit_list_append()

 - using parseopt's skip_prefix()

 - avoiding unnecessary strbuf_addf() in builtin-fmt-merge-msg.c

As always, comments are welcome. I hope I addressed all the issues which
were pointed out in the previous thread. If this is not the case, please
correct me.

Thanks.

Miklos Vajna (10):
  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

 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                                      |   56 ++
 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 ++
 18 files changed, 1482 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

[PATCH 01/10] 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 0a63c0e..18ec38c 100644
--- a/cache.h
+++ b/cache.h
@@ -832,5 +832,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 15a0e71..0a0b11e 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.rc2.dirty

[PATCH 02/10] 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.rc2.dirty

[PATCH 03/10] 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 c49f00f..2bf0593 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);
 
@@ -504,10 +512,15 @@ static int show_or_prune(int argc, const char **argv, int prune)
 					"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.rc2.dirty

[PATCH 04/10] 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.rc2.dirty

[PATCH 05/10] 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.rc2.dirty

[PATCH 06/10] 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 18ec38c..54368cc 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.rc2.dirty

[PATCH 07/10] 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.rc2.dirty

[PATCH 08/10] 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 |   32 ++++++++++++++++++++++++++++++++
 commit.h |    1 +
 2 files changed, 33 insertions(+), 0 deletions(-)

diff --git a/commit.c b/commit.c
index bbf9c75..13fa39d 100644
--- a/commit.c
+++ b/commit.c
@@ -600,6 +600,38 @@ 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, int cleanup)
+{
+	struct commit_list *i, *j, *k, *ret = NULL;
+
+	for (i = in; i; i = i->next) {
+		if (!ret)
+			commit_list_append(i->item, &ret);
+		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, cleanup);
+				/*
+				 * Now we just append bases to new, but
+				 * calling commit_list_append() for each
+				 * item would be expensive, so do it by
+				 * hand.
+				 */
+				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..ca858ed 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, int cleanup);
 
 extern int register_shallow(const unsigned char *sha1);
 extern int unregister_shallow(const unsigned char *sha1);
-- 
1.5.6.rc2.dirty

[PATCH 09/10] 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 13fa39d..54079df 100644
--- a/commit.c
+++ b/commit.c
@@ -710,3 +710,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, 0);
+
+	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 ca858ed..22839ac 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.rc2.dirty

[PATCH 10/10] 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 1937507..2830cca 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..54561ea
--- /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, 1);
+	}
+
+	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 0a0b11e..b389dd5 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.rc2.dirty

[PATCH] 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>
---

On Wed, Jun 11, 2008 at 10:50:32PM +0200, Miklos Vajna <vmiklos@frugalware.org> wrote:
> +                     commit_list_append(i->item, &ret);

Oops, sorry. When I cherry-picked the old get_octopus_merge_bases(), I
picked the version that did not use commit_list_insert() here yet.

Here is the correct version, which one I have in my working branch.

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

diff --git a/commit.c b/commit.c
index bbf9c75..f9410d8 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, int cleanup)
+{
+	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, cleanup);
+				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..ca858ed 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, int cleanup);
 
 extern int register_shallow(const unsigned char *sha1);
 extern int unregister_shallow(const unsigned char *sha1);
-- 
1.5.6.rc2.dirty

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

[Junio C Hamano]

Miklos Vajna <vmiklos@frugalware.org> writes:

> diff --git a/commit.c b/commit.c
> index bbf9c75..f9410d8 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, int cleanup)
> +{
> +	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, cleanup);

Why is passing "cleanup" through to get_merge_bases() safe, even when you
are running it more than once?

get_merge_bases() uses PARENT1, PARENT2 and other flags internally, and
the information necessary to clean them efficiently (i.e. the set of
commits that could be smudged with these flags due to its operation) is
known only to it _after it finishes_.  You cannot even say "previous run
did not clean things up, so please clean-up before starting this round"
upfront.  That is why we have clean-up loops at the _end_ of the function
after it finishes computing what it wants to return.

The only reason clean-up is optional to the function is because there are
one-shot callers such as "git merge-base" that do not want to pay penalty
for cleaning up (the only time you do not have to tell it to clean up is
when you know the invocation is the _last_ invocation of the function, iow
there is no later invocation that will be harmed by leftover flags).

[PATCH] 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>
---

On Wed, Jun 11, 2008 at 04:51:49PM -0700, Junio C Hamano <gitster@pobox.com> wrote:
> Why is passing "cleanup" through to get_merge_bases() safe, even when you
> are running it more than once?
>
> get_merge_bases() uses PARENT1, PARENT2 and other flags internally, and
> the information necessary to clean them efficiently (i.e. the set of
> commits that could be smudged with these flags due to its operation) is
> known only to it _after it finishes_.  You cannot even say "previous run
> did not clean things up, so please clean-up before starting this round"
> upfront.  That is why we have clean-up loops at the _end_ of the function
> after it finishes computing what it wants to return.
>
> The only reason clean-up is optional to the function is because there are
> one-shot callers such as "git merge-base" that do not want to pay penalty
> for cleaning up (the only time you do not have to tell it to clean up is
> when you know the invocation is the _last_ invocation of the function, iow
> there is no later invocation that will be harmed by leftover flags).

Yes, you have reason, cleanup in get_octopus_merge_bases() should not be
optional. Here is an updated patch that does not have this problem.

(Also available in my working branch where I fixed up 9/10 and 10/10 to
reflect this change.)

 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.rc2.dirty

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

[Junio C Hamano]

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

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

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

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

diff --git a/commit.c b/commit.c
index 94d5b3d..816eed1 100644
--- a/commit.c
+++ b/commit.c
@@ -531,26 +531,33 @@ static struct commit *interesting(struct commit_list *list)
 	return NULL;
 }
 
-static struct commit_list *merge_bases(struct commit *one, struct commit *two)
+static struct commit_list *merge_bases_many(struct commit *one, int n, struct commit **twos)
 {
 	struct commit_list *list = NULL;
 	struct commit_list *result = NULL;
+	int i;
 
-	if (one == two)
-		/* We do not mark this even with RESULT so we do not
-		 * have to clean it up.
-		 */
-		return commit_list_insert(one, &result);
+	for (i = 0; i < n; i++) {
+		if (one == twos[i])
+			/* We do not mark this even with RESULT so we do not
+			 * have to clean it up.
+			 */
+			return commit_list_insert(one, &result);
+	}
 
 	if (parse_commit(one))
 		return NULL;
-	if (parse_commit(two))
-		return NULL;
+	for (i = 0; i < n; i++) {
+		if (parse_commit(twos[i]))
+			return NULL;
+	}
 
 	one->object.flags |= PARENT1;
-	two->object.flags |= PARENT2;
 	insert_by_date(one, &list);
-	insert_by_date(two, &list);
+	for (i = 0; i < n; i++) {
+		twos[i]->object.flags |= PARENT2;
+		insert_by_date(twos[i], &list);
+	}
 
 	while (interesting(list)) {
 		struct commit *commit;
@@ -598,6 +605,11 @@ static struct commit_list *merge_bases(struct commit *one, struct commit *two)
 	return result;
 }
 
+static struct commit_list *merge_bases(struct commit *one, struct commit *two)
+{
+	return merge_bases_many(one, 1, &two);
+}
+
 struct commit_list *get_merge_bases(struct commit *one,
 					struct commit *two, int cleanup)
 {

[PATCH] Introduce get_octopus_merge_bases() in commit.c

[Miklos Vajna]

This is like get_merge_bases() but it works for multiple heads.
Internally it uses merge_bases_many() but it has the ability to clear
commit marks like get_merge_bases().

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

On Thu, Jun 05, 2008 at 10:53:59PM -0700, Junio C Hamano <gitster@pobox.com> wrote:
> Something like this might be enough to get us started.  Instead of
> finding
> out the merge bases between two commits, "one" and "two", this would
> find
> merge base between "one" and a commit that would be a merge across all
> the
> "two"s.  To apply it to the above example, you would give "C" as
> "one",
> and "A" and "B" as "twos" to it, to compute "2".

Here is what I pushed to my working branch, on top of your patch.

BTW: How should I credit your patch? Add a Signed-off-by? If I make you
the author I don't know how send-email handles the situation.

Thanks.

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

diff --git a/commit.c b/commit.c
index 1dba717..685a144 100644
--- a/commit.c
+++ b/commit.c
@@ -618,6 +618,23 @@ static struct commit_list *merge_bases(struct commit *one, struct commit *two)
 	return merge_bases_many(one, 1, &two);
 }
 
+struct commit_list *get_octopus_merge_bases(struct commit_list *in, int cleanup)
+{
+	struct commit *head = in->item;
+	int n = 0;
+	struct commit **commits = xmalloc(n*sizeof(struct commit *));
+	struct commit_list *ret, *i;
+
+	for(i = in; i; i = i->next, n++)
+		commits[n] = i->item;
+	ret = merge_bases_many(head, n, commits);
+	free(commits);
+	if (cleanup)
+		for(i = in; i; i = i->next)
+			clear_commit_marks(i->item, all_flags);
+	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..ca858ed 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, int cleanup);
 
 extern int register_shallow(const unsigned char *sha1);
 extern int unregister_shallow(const unsigned char *sha1);
-- 
1.5.6.rc0.dirty

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

[Johannes Schindelin]

Hi,

On Sat, 7 Jun 2008, Miklos Vajna wrote:

> diff --git a/commit.c b/commit.c
> index 1dba717..685a144 100644
> --- a/commit.c
> +++ b/commit.c
> @@ -618,6 +618,23 @@ static struct commit_list *merge_bases(struct commit *one, struct commit *two)
>  	return merge_bases_many(one, 1, &two);
>  }
>  
> +struct commit_list *get_octopus_merge_bases(struct commit_list *in, int cleanup)
> +{
> +	struct commit *head = in->item;
> +	int n = 0;
> +	struct commit **commits = xmalloc(n*sizeof(struct commit *));

Here, n will be 0 and therefore commits will be xmalloc(0), right?

> +	struct commit_list *ret, *i;
> +
> +	for(i = in; i; i = i->next, n++)
> +		commits[n] = i->item;

And here, commits will never be realloc()ed.

> +	ret = merge_bases_many(head, n, commits);

If merge_bases_many took a commit_list (yes, as I suggested to Junio), 
this transformation would not be necessary.

IIRC nothing in merge_bases_many() needed a commit array.

Oh, and whose responsibility is it to free "in"?  Caller or callee?  
(Because it is a non-const parameter, I would have expected the callee, 
but I think it makes more sense if the caller can do whatever she wants 
with the heads after calling octopus_merge_bases()).

Ciao,
Dscho

[PATCH] Introduce get_octopus_merge_bases() in commit.c

[Miklos Vajna]

This is like get_merge_bases() but it works for multiple heads.
Internally it uses merge_bases_many() but it has the ability to clear
commit marks like get_merge_bases().

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

On Mon, Jun 09, 2008 at 03:02:07PM +0100, Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:
> > +   int n = 0;
> > +   struct commit **commits = xmalloc(n*sizeof(struct commit *));
>
> Here, n will be 0 and therefore commits will be xmalloc(0), right?
>
> > +   struct commit_list *ret, *i;
> > +
> > +   for(i = in; i; i = i->next, n++)
> > +           commits[n] = i->item;
>
> And here, commits will never be realloc()ed.

Ouch, yes.

> > +   ret = merge_bases_many(head, n, commits);
>
> If merge_bases_many took a commit_list (yes, as I suggested to Junio),
> this transformation would not be necessary.
>
> IIRC nothing in merge_bases_many() needed a commit array.

Exactly. I modified merge_bases_many() to use a commit list.

> Oh, and whose responsibility is it to free "in"?  Caller or callee?
> (Because it is a non-const parameter, I would have expected the
> callee,
> but I think it makes more sense if the caller can do whatever she
> wants
> with the heads after calling octopus_merge_bases()).

The previous. I think using const would be a mistake since we do modify
the flags, but I still would prefer free the list in the caller, since
the list is still usable. That's exactly why the cleanup flag is there:
in case the non-empty objects flags would cause any problem later in the
caller.

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

diff --git a/commit.c b/commit.c
index 033c1e8..f3ca099 100644
--- a/commit.c
+++ b/commit.c
@@ -615,6 +615,17 @@ static struct commit_list *merge_bases(struct commit *one, struct commit *two)
 	return merge_bases_many(one, list);
 }
 
+struct commit_list *get_octopus_merge_bases(struct commit_list *in, int cleanup)
+{
+	struct commit_list *ret, *i;
+
+	ret = merge_bases_many(in->item, in->next);
+	if (cleanup)
+		for(i = in; i; i = i->next)
+			clear_commit_marks(i->item, all_flags);
+	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..ca858ed 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, int cleanup);
 
 extern int register_shallow(const unsigned char *sha1);
 extern int unregister_shallow(const unsigned char *sha1);
-- 
1.5.6.rc2.dirty

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

[Junio C Hamano]

Miklos Vajna <vmiklos@frugalware.org> writes:

> Exactly. I modified merge_bases_many() to use a commit list.

I just looked at your f755fb6; from the point of view of merge_bases()
which is far more often used, I think this is not an improvement but
actively wrong thing to do.  Most of the time callers compute merge base
of two, and the codepath should be optimized for that case.

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

[Johannes Schindelin]

Hi,

On Mon, 9 Jun 2008, Junio C Hamano wrote:

> Miklos Vajna <vmiklos@frugalware.org> writes:
> 
> > Exactly. I modified merge_bases_many() to use a commit list.
> 
> I just looked at your f755fb6; from the point of view of merge_bases() 
> which is far more often used, I think this is not an improvement but 
> actively wrong thing to do.  Most of the time callers compute merge base 
> of two, and the codepath should be optimized for that case.

But how much work is

	struct commit_list list = { two, NULL };

	merge_bases_many(one, &list);

?  merge_bases_many() does not modify the list IIRC, and it looks 
conceptually clean while being pretty much in the same performance 
ballpark.

Ciao,
Dscho

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

[Junio C Hamano]

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

> On Mon, 9 Jun 2008, Junio C Hamano wrote:
>
>> Miklos Vajna <vmiklos@frugalware.org> writes:
>> 
>> > Exactly. I modified merge_bases_many() to use a commit list.
>> 
>> I just looked at your f755fb6; from the point of view of merge_bases() 
>> which is far more often used, I think this is not an improvement but 
>> actively wrong thing to do.  Most of the time callers compute merge base 
>> of two, and the codepath should be optimized for that case.
>
> But how much work is
>
> 	struct commit_list list = { two, NULL };
>
> 	merge_bases_many(one, &list);

But (1) that is not what f755fb6 does; it does commit_list_insert() that
has an allocation, and (2) how much work is to count, allocate and pass
array for slow and less frequent codepath which octopus-merge-base is?

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

[Miklos Vajna]

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

On Mon, Jun 09, 2008 at 04:20:10PM -0700, Junio C Hamano <gitster@pobox.com> wrote:
> > 	struct commit_list list = { two, NULL };
> >
> > 	merge_bases_many(one, &list);
> 
> But (1) that is not what f755fb6 does; it does commit_list_insert() that
> has an allocation, and (2) how much work is to count, allocate and pass
> array for slow and less frequent codepath which octopus-merge-base is?

If (1) is the only problem, I can do it the way Dscho suggested, but I
don't exactly see why using a commit_list* can slow merge_bases() down:

for (i = 0; i < n; i++) {
        ...
}

is probably as fast as

for (i = list; i; i = i->next) {
        ...
}

in case n = 0 / list->next is NULL.

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

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

[Junio C Hamano]

Miklos Vajna <vmiklos@frugalware.org> writes:

> +struct commit_list *get_octopus_merge_bases(struct commit_list *in, int cleanup)
> +{
> +	struct commit_list *ret, *i;
> +
> +	ret = merge_bases_many(in->item, in->next);
> +	if (cleanup)
> +		for(i = in; i; i = i->next)
> +			clear_commit_marks(i->item, all_flags);
> +	return ret;
> +}

I suspect either me or you are confused, but how is this exactly used?

The code for merge_bases_many(), at least the one I showed you a few days
ago, is not a replacement for "show-branch --merge-base", and I do not
think you would want to use it as such in the rewrite of git-merge, if you
are trying to replace this part of git-merge.sh:

        case "$#" in
        1)
                common=$(git merge-base --all $head "$@")
                ;;
        *)
                common=$(git show-branch --merge-base $head "$@")
                ;;
        esac

The purpose of merge-base-many code was to improve this line in the
git-merge-octopus.sh:

	common=$(git merge-base --all $MRC $SHA1) ||
		die "Unable to find common commit with $SHA1"

Instead of keeping a single MRC, we can compute the merge-base-many
between the SHA1 (i.e. the one we are looking at right now -- it is fed as
"one") and all the previous SHA1's we have already looked at (they become
"two's"), like this:

	common($git merge-base-many $SHA1 $SHA1_SO_FAR)

and you would have at the end of the loop:

	SHA1_SO_FAR="$SHA1_SO_FAR$SHA1 "

or something.

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

[Miklos Vajna]

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

On Mon, Jun 09, 2008 at 04:06:12PM -0700, Junio C Hamano <gitster@pobox.com> wrote:
> Miklos Vajna <vmiklos@frugalware.org> writes:
> 
> > +struct commit_list *get_octopus_merge_bases(struct commit_list *in, int cleanup)
> > +{
> > +	struct commit_list *ret, *i;
> > +
> > +	ret = merge_bases_many(in->item, in->next);
> > +	if (cleanup)
> > +		for(i = in; i; i = i->next)
> > +			clear_commit_marks(i->item, all_flags);
> > +	return ret;
> > +}
> 
> I suspect either me or you are confused, but how is this exactly used?
> 
> The code for merge_bases_many(), at least the one I showed you a few days
> ago, is not a replacement for "show-branch --merge-base", and I do not
> think you would want to use it as such in the rewrite of git-merge, if you
> are trying to replace this part of git-merge.sh:
> 
>         case "$#" in
>         1)
>                 common=$(git merge-base --all $head "$@")
>                 ;;
>         *)
>                 common=$(git show-branch --merge-base $head "$@")
>                 ;;
>         esac

Then I think I'm the one who is confused. My original
get_octopus_merge_bases() - in commit e13c0c2 - was exactly to replace
this part.

So, may I assume that the original get_octopus_merge_bases() is OK for
this purpose?

> The purpose of merge-base-many code was to improve this line in the
> git-merge-octopus.sh:
> 
> 	common=$(git merge-base --all $MRC $SHA1) ||
> 		die "Unable to find common commit with $SHA1"
> 
> Instead of keeping a single MRC, we can compute the merge-base-many
> between the SHA1 (i.e. the one we are looking at right now -- it is fed as
> "one") and all the previous SHA1's we have already looked at (they become
> "two's"), like this:
> 
> 	common($git merge-base-many $SHA1 $SHA1_SO_FAR)
> 
> and you would have at the end of the loop:
> 
> 	SHA1_SO_FAR="$SHA1_SO_FAR$SHA1 "
> 
> or something.

Actually I do not want to touch git-merge-octopus.sh before
builtin-merge is not ready. (I try to "do one thing and do it
well".)

Thanks.

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

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

[Johannes Schindelin]

Hi,

On Mon, 9 Jun 2008, Junio C Hamano wrote:

> Miklos Vajna <vmiklos@frugalware.org> writes:
> 
> > +struct commit_list *get_octopus_merge_bases(struct commit_list *in, int cleanup)
> > +{
> > +	struct commit_list *ret, *i;
> > +
> > +	ret = merge_bases_many(in->item, in->next);
> > +	if (cleanup)
> > +		for(i = in; i; i = i->next)
> > +			clear_commit_marks(i->item, all_flags);
> > +	return ret;
> > +}
> 
> I suspect either me or you are confused, but how is this exactly used?
> 
> The code for merge_bases_many(), at least the one I showed you a few days
> ago, is not a replacement for "show-branch --merge-base", and I do not
> think you would want to use it as such in the rewrite of git-merge, if you
> are trying to replace this part of git-merge.sh:
> 
>         case "$#" in
>         1)
>                 common=$(git merge-base --all $head "$@")
>                 ;;
>         *)
>                 common=$(git show-branch --merge-base $head "$@")
>                 ;;
>         esac
> 
> The purpose of merge-base-many code was to improve this line in the
> git-merge-octopus.sh:
> 
> 	common=$(git merge-base --all $MRC $SHA1) ||
> 		die "Unable to find common commit with $SHA1"
> 
> Instead of keeping a single MRC, we can compute the merge-base-many
> between the SHA1 (i.e. the one we are looking at right now -- it is fed as
> "one") and all the previous SHA1's we have already looked at (they become
> "two's"), like this:
> 
> 	common($git merge-base-many $SHA1 $SHA1_SO_FAR)
> 
> and you would have at the end of the loop:
> 
> 	SHA1_SO_FAR="$SHA1_SO_FAR$SHA1 "
> 
> or something.

Ah!  Even I thought that merge_bases_many() was meant for the show-branch 
--merge-base case.

However, your remark about optimizing for the two-head case got me 
thinking: should we not rather use the simple algorithm Miklos proposed 
for octopus_merge_bases(), even if it is suboptimal?

Octopus is such a rare case that it is more important to have a robust, 
working code, than a fast one, right?  Especially since Octopus will be 
exercized much less often, and therefore has a higher chance of hiding a 
bug.

Ciao,
Dscho

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

[Junio C Hamano]

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

> However, your remark about optimizing for the two-head case got me 
> thinking: should we not rather use the simple algorithm Miklos proposed 
> for octopus_merge_bases(), even if it is suboptimal?

Actually a quick glance at git-merge, a rather large case...esac after
that "show-branch --merge-base" tells me that we do not really use the
output from that operation and instead we check if we are fast-forward
from all the other heads by iterating over them.  merge-octupos would
accept it as the base but never looks at it.

So I think with a proper refactoring of the codepath you probably would
not even have to do the blanket "merge-base across all heads" at all.

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

[Miklos Vajna]

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

On Mon, Jun 09, 2008 at 04:41:06PM -0700, Junio C Hamano <gitster@pobox.com> wrote:
> Actually a quick glance at git-merge, a rather large case...esac after
> that "show-branch --merge-base" tells me that we do not really use the
> output from that operation and instead we check if we are fast-forward
> from all the other heads by iterating over them.  merge-octupos would
> accept it as the base but never looks at it.

I may be wrong but I think it would be still nice to pass a valid base
to the backend, even if _currently_ the only octopus implementation
ignores it.

Actually on "valid" I mean what my original get_octopus_merge_bases()
returned. :-)

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

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

[Johannes Schindelin]

Hi,

On Tue, 10 Jun 2008, Miklos Vajna wrote:

> On Mon, Jun 09, 2008 at 04:41:06PM -0700, Junio C Hamano 
> <gitster@pobox.com> wrote:
>
> > Actually a quick glance at git-merge, a rather large case...esac after 
> > that "show-branch --merge-base" tells me that we do not really use the 
> > output from that operation and instead we check if we are fast-forward 
> > from all the other heads by iterating over them.  merge-octupos would 
> > accept it as the base but never looks at it.
> 
> I may be wrong but I think it would be still nice to pass a valid base 
> to the backend, even if _currently_ the only octopus implementation 
> ignores it.
> 
> Actually on "valid" I mean what my original get_octopus_merge_bases() 
> returned. :-)

IMO that is one of the advantages of making git-merge a builtin: you need 
not work around the lack of performance of shell scripts, but you can 
actually compute what you need to compute.

IOW I agree that we could give the proper list of merge bases to whatever 
octopus backend we use.  And since your original implementation is 
correct, if not super-optimal, I would like to stick to it.

Ciao,
Dscho