[PATCH 00/10] Build in merge

[PATCH 00/10] Build in merge

[Miklos Vajna]

This series is a rewrite of git-merge in C.

I already sent a WIP version of this series, it already worked at that
time, but I had numerous internal TODOs in the code.

I also tried to use the internal API wherever it was possible to avoid
the expensive run_command() calls.

At the moment I am not aware of any bugs in ugly parts in the code, so I
would appreciate if I could get some comments (positive or negative) on
it.

And yes, I'm aware that it's already late for 1.5.6, I'm sending it out
so that I can work on issues pointed out by others in the meantime.

Thanks.

Miklos Vajna (10):
  Move split_cmdline() to alias.c
  Move commit_list_count() to commit.c
  Move builtin-remote'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 useable from other builtins
  Introduce commit_list_append() in commit.c
  Introduce get_octopus_merge_bases() 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                               | 1147 +++++++++++++++++++++++++
 builtin-read-tree.c                           |   24 -
 builtin-remote.c                              |    6 -
 builtin.h                                     |    4 +
 cache.h                                       |    3 +
 commit.c                                      |   59 ++
 commit.h                                      |    3 +
 git-merge.sh => contrib/examples/git-merge.sh |    0 
 git-compat-util.h                             |    6 +
 git.c                                         |   54 +--
 parse-options.c                               |   19 +-
 parse-options.h                               |    1 +
 read-cache.c                                  |   24 +
 t/t7601-merge-pull-config.sh                  |   57 ++
 18 files changed, 1460 insertions(+), 168 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 092a997..e342ad3 100644
--- a/cache.h
+++ b/cache.h
@@ -831,5 +831,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 272bf03..9935069 100644
--- a/git.c
+++ b/git.c
@@ -87,59 +87,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.rc0.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 362c290..0afd4a4 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 94d5b3d..b45ec9b 100644
--- a/commit.c
+++ b/commit.c
@@ -331,6 +331,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.rc0.dirty

[PATCH 03/10] Move builtin-remote'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 builtin-remote's one to git-compat-util.h and
let parse-options use it as well.

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

diff --git a/builtin-remote.c b/builtin-remote.c
index c49f00f..9c25018 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;
diff --git a/git-compat-util.h b/git-compat-util.h
index 01c4045..af515d4 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 *name, const char *prefix)
+{
+	return !name ? "" :
+		prefixcmp(name, prefix) ?  name : name + strlen(prefix);
+}
+
 #ifdef NO_MMAP
 
 #ifndef PROT_READ
diff --git a/parse-options.c b/parse-options.c
index acf3fe3..aa164d0 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)
@@ -161,7 +155,7 @@ static int parse_long_opt(struct optparse_t *p, const char *arg,
 
 		rest = skip_prefix(arg, options->long_name);
 		if (options->type == OPTION_ARGUMENT) {
-			if (!rest)
+			if (!strcmp(rest, arg))
 				continue;
 			if (*rest == '=')
 				return opterror(options, "takes no value", flags);
@@ -170,7 +164,7 @@ static int parse_long_opt(struct optparse_t *p, const char *arg,
 			p->out[p->cpidx++] = arg - 2;
 			return 0;
 		}
-		if (!rest) {
+		if (!strcmp(rest, arg)) {
 			/* abbreviated? */
 			if (!strncmp(options->long_name, arg, arg_end - arg)) {
 is_abbreviated:
@@ -201,9 +195,9 @@ is_abbreviated:
 			flags |= OPT_UNSET;
 			rest = skip_prefix(arg + 3, options->long_name);
 			/* abbreviated and negated? */
-			if (!rest && !prefixcmp(options->long_name, arg + 3))
+			if (!strcmp(rest, arg + 3) && !prefixcmp(options->long_name, arg + 3))
 				goto is_abbreviated;
-			if (!rest)
+			if (!strcmp(rest, arg + 3))
 				continue;
 		}
 		if (*rest) {
-- 
1.5.6.rc0.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 |   57 ++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 57 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..cc595ac
--- /dev/null
+++ b/t/t7601-merge-pull-config.sh
@@ -0,0 +1,57 @@
+#!/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 &&
+	git merge c2 &&
+	test -e c1.c &&
+	test -e 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 -e c1.c &&
+	! test -e c2.c
+'
+
+test_expect_success 'merge c1 with c2 and c3 (recursive in pull.octopus)' '
+	git reset --hard c1 &&
+	git config pull.octopus "recursive" &&
+	! git merge c2 c3
+'
+
+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_done
-- 
1.5.6.rc0.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 aa164d0..4d4f302 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.rc0.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        |   24 ++++++++++++++++++++++++
 3 files changed, 26 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 e342ad3..df0ac56 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..197160c 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -1394,3 +1394,27 @@ int write_index(const struct index_state *istate, int newfd)
 	}
 	return ce_flush(&c, newfd);
 }
+
+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.rc0.dirty

[PATCH 07/10] git-fmt-merge-msg: make it useable 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..5ec7195 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_addf(out, "%s", 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 8bda111..9b928e2 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[];
@@ -10,6 +11,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.rc0.dirty

[PATCH 08/10] Introduce commit_list_append() in commit.c

[Miklos Vajna]

This is like commit_list_insert() but it appends the new commit to the
end of the list, rather than insert to the start of it.

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

diff --git a/commit.c b/commit.c
index b45ec9b..6ba5acb 100644
--- a/commit.c
+++ b/commit.c
@@ -331,6 +331,25 @@ struct commit_list *commit_list_insert(struct commit *item, struct commit_list *
 	return new_list;
 }
 
+struct commit_list *commit_list_append(struct commit *item,
+	struct commit_list **list_p)
+{
+	struct commit_list *i, *prev = NULL, *list = *list_p;
+	struct commit_list *new_list = xmalloc(sizeof(struct commit_list));
+
+	new_list->item = item;
+	new_list->next = NULL;
+
+	if (!list)
+		*list_p = new_list;
+	else {
+		for (i = list; i; i = i->next)
+			prev = i;
+		prev->next = new_list;
+	}
+	return list;
+}
+
 unsigned commit_list_count(const struct commit_list *l)
 {
 	unsigned c = 0;
diff --git a/commit.h b/commit.h
index 7f8c5ee..5d9ac43 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);
+struct commit_list *commit_list_append(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);
 
-- 
1.5.6.rc0.dirty

[PATCH 09/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 6ba5acb..c09b305 100644
--- a/commit.c
+++ b/commit.c
@@ -625,6 +625,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 5d9ac43..201782d 100644
--- a/commit.h
+++ b/commit.h
@@ -122,6 +122,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

[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                               | 1147 +++++++++++++++++++++++++
 builtin.h                                     |    1 +
 git-merge.sh => contrib/examples/git-merge.sh |    0 
 git.c                                         |    1 +
 5 files changed, 1150 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 cce5a6e..748a2ae 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..9ebd990
--- /dev/null
+++ b/builtin-merge.c
@@ -0,0 +1,1147 @@
+/*
+ * 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);
+}
+
+static int commit_list_has_commit(struct commit *commit,
+	struct commit_list *list)
+{
+	struct commit_list *i;
+
+	for (i = list; i; i = i->next) {
+		if (!hashcmp(commit->object.sha1, i->item->object.sha1))
+			return 1;
+	}
+	return 0;
+}
+
+static struct commit_list *filter_independent(unsigned char *head,
+	struct commit_list *heads)
+{
+	struct commit_list *i, *bases, *ret = NULL;
+
+	commit_list_insert(lookup_commit(head), &heads);
+
+	bases = get_octopus_merge_bases(heads, 1);
+
+	for (i = heads; i; i = i->next)
+		if (!commit_list_has_commit(i->item, bases))
+			commit_list_append(i->item, &ret);
+	return ret;
+}
+
+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;
+
+	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)
+		branch = skip_prefix(branch, "refs/heads/");
+
+	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]);
+		commit_list_append(lookup_commit(o->sha1), &remoteheads);
+
+		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 {
+			commit_list_append(lookup_commit(head), &parents);
+			for (j = remoteheads; j; j = j->next)
+				commit_list_append(j->item, &parents);
+		}
+		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 9b928e2..098eaa2 100644
--- a/builtin.h
+++ b/builtin.h
@@ -59,6 +59,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 9935069..7f69c3b 100644
--- a/git.c
+++ b/git.c
@@ -268,6 +268,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.rc0.dirty

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

[Junio C Hamano]

Miklos Vajna <vmiklos@frugalware.org> writes:

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

In what sense is this "like show-branch --merge-base"?

The only similarlity I can spot is that it can take more than two heads,
but what it computes and the way it computes it seem to be different.  It
certainly looks much less efficient as it does not walk the ancestry chain
in one-go like show-branch does.

I haven't looked at [10/10] so I do not know yet how you intend to use
this value, but I am not sure if it makes sense to use the computed value
as the merge base when running an octopus.

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.

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)
 {

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

[Johannes Schindelin]

Hi,

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

> 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)

Clever, but for performance reasons I think it might be better to use a 
commit list here.  This can be a local commit_list in the helper that 
calls merge_bases_many() for the two-head case.

>  {
>  	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;
> +	}

Distracting curly brackets.

>  	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);
> +	}

Ah, now that is clever: I thought we would get into a lot of problems 
because we would need a bit for every initial commit.  But what you are 
basically doing is reusing PARENT2 for all the merge bases that have been 
found for the heads up to, but not including, the current one.

Maybe this should be documented.

But this is not yet enough, right?  You still have to have a loop

merge_bases <- calculate merge bases from the first two heads

foreach head starting from the 3rd one
	merge_bases <- calculate merge_bases_many(this_head, merge_bases)

No?

And these merge_bases are commit_lists, therefore, as mentioned above, the 
signature should not take an array, but the commit_lists.

Ciao,
Dscho

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

[Johannes Schindelin]

Hi,

On Fri, 6 Jun 2008, Johannes Schindelin wrote:

> >  	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);
> > +	}
> 
> Ah, now that is clever: I thought we would get into a lot of problems 
> because we would need a bit for every initial commit.  But what you are 
> basically doing is reusing PARENT2 for all the merge bases that have 
> been found for the heads up to, but not including, the current one.

I spoke too soon.  This is not going to work easily: after doing this for 
two heads, the PARENT1 flag must be reset to PARENT2 before traversing for 
a third head.

Or am I missing something obvious?

Ciao,
Dscho

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

[Junio C Hamano]

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

> Clever, but for performance reasons I think it might be better to use a 
> commit list here.

Why?  We do not iterate this that many times, and you do not gain much
from extra allocations of commit_list structure you would need to do.

>>  	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);
>> +	}
>
> Ah, now that is clever: I thought we would get into a lot of problems 
> because we would need a bit for every initial commit.

That's not coming from being _clever_, but from solving a different
problem than what you thought we are solving.  This is _not_ computing the
"base of all of them" as "git-show-branch --merge-base" computes.

Instead, this is "compute '2' given C and A+B", without actually having to
have a commit T(A,B), for a merge to create T(A,B,C).

>           o---o---A
>          /         .
>     ----1---2---B...T(A,B)
>              \       .
>               o---C...T(A,B,C)

Instead of fabricating a commit T(A,B) and drop it as "two", you
drop "A" and "B" both marked as PARENT2 into the list and have the logic
traverse as before.

The purpose of this exercise is not doing the merge base computation for
an octopus in one round.  In fact, you do _not_ want to compute it
upfront.  Re-read the original message the above picture comes from to
remind you of why (and the loop with a big comment at the bottom of
git-merge-octopus).  This is for a better computation of $MRC in each
round there.
.

[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

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

[Johannes Schindelin]

Hi,

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

> Miklos Vajna <vmiklos@frugalware.org> writes:
> 
> > This is like get_merge_bases() but it works for multiple heads, like
> > show-branch --merge-base.
> 
> In what sense is this "like show-branch --merge-base"?
> 
> The only similarlity I can spot is that it can take more than two heads, 
> but what it computes and the way it computes it seem to be different.  
> It certainly looks much less efficient as it does not walk the ancestry 
> chain in one-go like show-branch does.

Ah, you are right.  I thought that in the typical case (where the initial 
commits are independent), it will never traverse any commit twice.  I did 
not really understand your example quickly enough, so I made up my own:

A - B - C - D - E
  \           X
    F - G - H   I
      \   X   \
        J   \   K
             \
              - L 

Now, let's get the merge bases with Miklos' algorithm for E, I, K and L.

First it will find the merge base for E and I, which is D.  Then it 
calculates the merge base between that merge base and the third head, K, 
which leads us all the way back to A.

Now, calculating the merge base between that merge base and L will 
traverse the commits F, G and H _again_.

Ciao,
Dscho

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

[Miklos Vajna]

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

On Thu, Jun 05, 2008 at 08:51:46PM -0700, Junio C Hamano <gitster@pobox.com> wrote:
> In what sense is this "like show-branch --merge-base"?
> 
> The only similarlity I can spot is that it can take more than two heads,
> but what it computes and the way it computes it seem to be different.  It
> certainly looks much less efficient as it does not walk the ancestry chain
> in one-go like show-branch does.

Exactly. The original idea was to avoid the current limitation:
show-branch uses object flags for each branch, which is not something
that works if you have a lot of ones.

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

Re: [PATCH 08/10] Introduce commit_list_append() in commit.c

[Junio C Hamano]

Miklos Vajna <vmiklos@frugalware.org> writes:

> This is like commit_list_insert() but it appends the new commit to the
> end of the list, rather than insert to the start of it.
>
> Signed-off-by: Miklos Vajna <vmiklos@frugalware.org>
> ---
>  commit.c |   19 +++++++++++++++++++
>  commit.h |    1 +
>  2 files changed, 20 insertions(+), 0 deletions(-)
>
> diff --git a/commit.c b/commit.c
> index b45ec9b..6ba5acb 100644
> --- a/commit.c
> +++ b/commit.c
> @@ -331,6 +331,25 @@ struct commit_list *commit_list_insert(struct commit *item, struct commit_list *
>  	return new_list;
>  }
>  
> +struct commit_list *commit_list_append(struct commit *item,
> +	struct commit_list **list_p)
> +{
> +	struct commit_list *i, *prev = NULL, *list = *list_p;
> +	struct commit_list *new_list = xmalloc(sizeof(struct commit_list));
> +
> +	new_list->item = item;
> +	new_list->next = NULL;
> +
> +	if (!list)
> +		*list_p = new_list;
> +	else {
> +		for (i = list; i; i = i->next)
> +			prev = i;
> +		prev->next = new_list;
> +	}
> +	return list;
> +}

Do you have a caller of this function that keeps a pointer to commit_list
that needs to be appended at the tail or inserted at the beginning
depending on the phase of the moon, or does the caller always append to
that list?

Re: [PATCH 08/10] Introduce commit_list_append() in commit.c

[Miklos Vajna]

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

On Thu, Jun 05, 2008 at 04:16:46PM -0700, Junio C Hamano <gitster@pobox.com> wrote:
> Do you have a caller of this function that keeps a pointer to commit_list
> that needs to be appended at the tail or inserted at the beginning
> depending on the phase of the moon, or does the caller always append to
> that list?

The later. I use it for appending a new parent for the merge commit and
after parsing a new remote head. In both cases I always append a list.

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

Re: [PATCH 08/10] Introduce commit_list_append() in commit.c

[Junio C Hamano]

Miklos Vajna <vmiklos@frugalware.org> writes:

> On Thu, Jun 05, 2008 at 04:16:46PM -0700, Junio C Hamano <gitster@pobox.com> wrote:
>> Do you have a caller of this function that keeps a pointer to commit_list
>> that needs to be appended at the tail or inserted at the beginning
>> depending on the phase of the moon, or does the caller always append to
>> that list?
>
> The later. I use it for appending a new parent for the merge commit and
> after parsing a new remote head. In both cases I always append a list.

If that is the case, you might want to check how parse_commit_buffer() in
commit.c builds "parents" list.  It is a standard pattern to append to the
list using commit_list_insert() and that is the reason why it returns a
pointer.

Re: [PATCH 08/10] Introduce commit_list_append() in commit.c

[Miklos Vajna]

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

On Fri, Jun 06, 2008 at 05:14:35PM -0700, Junio C Hamano <gitster@pobox.com> wrote:
> If that is the case, you might want to check how parse_commit_buffer() in
> commit.c builds "parents" list.  It is a standard pattern to append to the
> list using commit_list_insert() and that is the reason why it returns a
> pointer.

Ah, great, then this patch is not necessary. I removed it from my
working branch.

Thanks.

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

Re: [PATCH 07/10] git-fmt-merge-msg: make it useable from other builtins

[Junio C Hamano]

Miklos Vajna <vmiklos@frugalware.org> writes:

> 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>

The word in the title should be "usable" (s/sea/sa/).

Other than that, looks like a quite straightforward conversion.

Re: [PATCH 07/10] git-fmt-merge-msg: make it useable from other builtins

[Miklos Vajna]

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

On Thu, Jun 05, 2008 at 04:12:00PM -0700, Junio C Hamano <gitster@pobox.com> wrote:
> The word in the title should be "usable" (s/sea/sa/).
> 
> Other than that, looks like a quite straightforward conversion.

OK, I fixed up the patch title in git://repo.or.cz/git/vmiklos.git.

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

Re: [PATCH 07/10] git-fmt-merge-msg: make it useable from other builtins

[Andreas Ericsson]

Miklos Vajna wrote:
> 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.
> 

I have a very nearly identical patch in an ancient offshoot branch
since my attempt to make git-pull a builtin (which was stupid as
it doesn't do anything CPU-intensive apart from merging).

I likes it. For bonus points you could replace some strbuf_addf()
calls with strbuf_addstr() ones, but I don't think anyone really
cares.

So, fwiw,
Liked-by: Andreas Ericsson <ae@op5.se>

-- 
Andreas Ericsson                   andreas.ericsson@op5.se
OP5 AB                             www.op5.se
Tel: +46 8-230225                  Fax: +46 8-230231

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

On Mon, Jun 09, 2008 at 10:58:28AM +0200, Andreas Ericsson <ae@op5.se> wrote:
> I likes it. For bonus points you could replace some strbuf_addf()
> calls with strbuf_addstr() ones, but I don't think anyone really
> cares.

Hopefully this one has no unnecessary strbuf_addf() calls.

> Liked-by: Andreas Ericsson <ae@op5.se>

:-)

 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

Re: [PATCH 06/10] Move read_cache_unmerged() to read-cache.c

[Junio C Hamano]

Miklos Vajna <vmiklos@frugalware.org> writes:

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

Looks good, but as a public interface probably it needs a few lines of
comment in front of the function's definition to describe what it is used
for.  Perhaps like...

/*
 * 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().
 */

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

On Thu, Jun 05, 2008 at 04:05:54PM -0700, Junio C Hamano <gitster@pobox.com> wrote:
> Looks good, but as a public interface probably it needs a few lines of
> comment in front of the function's definition to describe what it is
> used
> for.  Perhaps like...
>
> /*
>  * 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().
>  */

Added. I'm sending the patch I just pushed to my working branch.

 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 e342ad3..df0ac56 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.rc0.dirty

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

[Junio C Hamano]

Miklos Vajna <vmiklos@frugalware.org> writes:

> 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 |   57 ++++++++++++++++++++++++++++++++++++++++++
>  1 files changed, 57 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..cc595ac
> --- /dev/null
> +++ b/t/t7601-merge-pull-config.sh
> @@ -0,0 +1,57 @@
> +#!/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 that c0 and c1 do and c2 and c3 do not exist here, as it is cheap,
and otherwise you may end up chasing wild-goose when somebody breaks
git-reset.  No need to do so in later tests in this script, but it is a
cheap protection for yourself from others' mistakes ;-).

> +	git merge c2 &&
> +	test -e c1.c &&
> +	test -e c2.c
> +'

Nobody runs V7 that lacked "test -e" to run these test scripts, but you
expect them to be regular files at this point of the test, so the correct
way to spell these is with "test -f".

In general, you are better off training yourself to think if you can use
"test -f" before blindly using "test -e".

> +test_expect_success 'merge c1 with c2 (ours in pull.twohead)' '
> +	git reset --hard c1 &&
> +	git config pull.twohead ours &&
> +	git merge c2 &&
> +	test -e c1.c &&
> +	! test -e c2.c
> +'
> +
> +test_expect_success 'merge c1 with c2 and c3 (recursive in pull.octopus)' '
> +	git reset --hard c1 &&
> +	git config pull.octopus "recursive" &&
> +	! git merge c2 c3

Is it because it should dump core, or is it because the command should
decline to work, gracefully failing with an error message and non-zero
exit status?  Use "test_must_fail" to check for the latter.

Don't you want to check how it fails and in what shape the command leaves
the work tree?  I am assuming that recursive sees more than one "remote"
head and declines to work without touching work tree nor the index, so if
that is what you expect, you should check for that.  Otherwise, a
regression that loses local changes will go unnoticed.

> +'
> +
> +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

Likewise, don't you want to check the result of the merge?  Not just
"merge exited with 0", but you would want to see that the HEAD has
advanced, it has the expected parents, there is no unexpected local
changes (because you did not have any when you started the merge), and it
has the expected tree contents.

> +'
> +
> +test_done
> -- 
> 1.5.6.rc0.dirty

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

On Thu, Jun 05, 2008 at 03:58:23PM -0700, Junio C Hamano <gitster@pobox.com> wrote:
> > +test_expect_success 'merge c1 with c2' '
> > +   git reset --hard c1 &&
>
> test that c0 and c1 do and c2 and c3 do not exist here, as it is
> cheap,
> and otherwise you may end up chasing wild-goose when somebody breaks
> git-reset.  No need to do so in later tests in this script, but it is
> a
> cheap protection for yourself from others' mistakes ;-).

Done.

> > +   git merge c2 &&
> > +   test -e c1.c &&
> > +   test -e c2.c
> > +'
>
> Nobody runs V7 that lacked "test -e" to run these test scripts, but
> you
> expect them to be regular files at this point of the test, so the
> correct
> way to spell these is with "test -f".
>
> In general, you are better off training yourself to think if you can
> use
> "test -f" before blindly using "test -e".

Sure, corrected.

> > +test_expect_success 'merge c1 with c2 and c3 (recursive in
> > pull.octopus)' '
> > +   git reset --hard c1 &&
> > +   git config pull.octopus "recursive" &&
> > +   ! git merge c2 c3
>
> Is it because it should dump core, or is it because the command should
> decline to work, gracefully failing with an error message and non-zero
> exit status?  Use "test_must_fail" to check for the latter.

Obviously the later, corrected.

> Don't you want to check how it fails and in what shape the command
> leaves
> the work tree?  I am assuming that recursive sees more than one
> "remote"
> head and declines to work without touching work tree nor the index, so
> if
> that is what you expect, you should check for that.  Otherwise, a
> regression that loses local changes will go unnoticed.

Hm yes. I added checks to ensure nothing happened.

> > +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
>
> Likewise, don't you want to check the result of the merge?  Not just
> "merge exited with 0", but you would want to see that the HEAD has
> advanced, it has the expected parents, there is no unexpected local
> changes (because you did not have any when you started the merge), and
> it
> has the expected tree contents.

Corrected.

I'm sending the version I just pushed to my working branch.

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

Re: [PATCH 03/10] Move builtin-remote's skip_prefix() to git-compat-util.h

[Junio C Hamano]

Miklos Vajna <vmiklos@frugalware.org> writes:

> diff --git a/builtin-remote.c b/builtin-remote.c
> index c49f00f..9c25018 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;
> diff --git a/git-compat-util.h b/git-compat-util.h
> index 01c4045..af515d4 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 *name, const char *prefix)
> +{
> +	return !name ? "" :
> +		prefixcmp(name, prefix) ?  name : name + strlen(prefix);
> +}
> +

Somehow you seemed to have picked the one whose semantics is defined much
less clearly.  For one thing, it takes more effort (and unnatural way to
check) for the caller to detect the case where prefix did not match than
the one that returns NULL.  Worse, I think this one is less efficient,
doing strlen(prefix) twice.

> diff --git a/parse-options.c b/parse-options.c
> index acf3fe3..aa164d0 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)
> @@ -161,7 +155,7 @@ static int parse_long_opt(struct optparse_t *p, const char *arg,
>  
>  		rest = skip_prefix(arg, options->long_name);
>  		if (options->type == OPTION_ARGUMENT) {
> -			if (!rest)
> +			if (!strcmp(rest, arg))

Ugh.

At least please have the courtesy of not making it more expensive than the
original unnecessarily.  Isn't (rest == arg) enough here?

Still, I think the one from builtin-remote.c you used is a much worse
implementation of the same thing between the two.  It was Ok while it was
a local scope hack only for builtin-remote.c's use, but a special calling
convention like "if name is NULL return empty string" should not be
promoted to public utility library status without defending why it is
always a good idea to do so.

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

On Thu, Jun 05, 2008 at 03:38:23PM -0700, Junio C Hamano <gitster@pobox.com> wrote:
> Somehow you seemed to have picked the one whose semantics is defined
> much
> less clearly.  For one thing, it takes more effort (and unnatural way
> to
> check) for the caller to detect the case where prefix did not match
> than
> the one that returns NULL.  Worse, I think this one is less efficient,
> doing strlen(prefix) twice.

Here is what I pushed to my working branch.

 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 01c4045..67a0b81 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.rc0.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] 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