Merge branch 'hv/submodule-find-ff-merge'

* hv/submodule-find-ff-merge:
  Implement automatic fast-forward merge for submodules
  setup_revisions(): Allow walking history in a submodule
  Teach ref iteration module about submodules

Conflicts:
	submodule.c

10 files changed, 476 insertions, 55 deletions

diff --git a/cache.h b/cache.h
index 37ef9d8a0..94dde5312 100644
--- a/cache.h
+++ b/cache.h
@@ -641,6 +641,9 @@ extern char *git_pathdup(const char *fmt, ...)
 /* Return a statically allocated filename matching the sha1 signature */
 extern char *mkpath(const char *fmt, ...) __attribute__((format (printf, 1, 2)));
 extern char *git_path(const char *fmt, ...) __attribute__((format (printf, 1, 2)));
+extern char *git_path_submodule(const char *path, const char *fmt, ...)
+	__attribute__((format (printf, 2, 3)));
+
 extern char *sha1_file_name(const unsigned char *sha1);
 extern char *sha1_pack_name(const unsigned char *sha1);
 extern char *sha1_pack_index_name(const unsigned char *sha1);
diff --git a/merge-recursive.c b/merge-recursive.c
index 656e769b4..638076ec6 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -20,6 +20,7 @@
 #include "attr.h"
 #include "merge-recursive.h"
 #include "dir.h"
+#include "submodule.h"
 
 static struct tree *shift_tree_object(struct tree *one, struct tree *two,
 				      const char *subtree_shift)
@@ -519,13 +520,15 @@ static void update_file_flags(struct merge_options *o,
 		void *buf;
 		unsigned long size;
 
-		if (S_ISGITLINK(mode))
+		if (S_ISGITLINK(mode)) {
 			/*
 			 * We may later decide to recursively descend into
 			 * the submodule directory and update its index
 			 * and/or work tree, but we do not do that now.
 			 */
+			update_wd = 0;
 			goto update_index;
+		}
 
 		buf = read_sha1_file(sha, &type, &size);
 		if (!buf)
@@ -710,8 +713,8 @@ static struct merge_file_info merge_file(struct merge_options *o,
 			free(result_buf.ptr);
 			result.clean = (merge_status == 0);
 		} else if (S_ISGITLINK(a->mode)) {
-			result.clean = 0;
-			hashcpy(result.sha, a->sha1);
+			result.clean = merge_submodule(result.sha, one->path, one->sha1,
+						       a->sha1, b->sha1);
 		} else if (S_ISLNK(a->mode)) {
 			hashcpy(result.sha, a->sha1);
 
diff --git a/path.c b/path.c
index 6b2302309..a2c9d1e24 100644
--- a/path.c
+++ b/path.c
@@ -122,6 +122,44 @@ char *git_path(const char *fmt, ...)
 	return cleanup_path(pathname);
 }
 
+char *git_path_submodule(const char *path, const char *fmt, ...)
+{
+	char *pathname = get_pathname();
+	struct strbuf buf = STRBUF_INIT;
+	const char *git_dir;
+	va_list args;
+	unsigned len;
+
+	len = strlen(path);
+	if (len > PATH_MAX-100)
+		return bad_path;
+
+	strbuf_addstr(&buf, path);
+	if (len && path[len-1] != '/')
+		strbuf_addch(&buf, '/');
+	strbuf_addstr(&buf, ".git");
+
+	git_dir = read_gitfile_gently(buf.buf);
+	if (git_dir) {
+		strbuf_reset(&buf);
+		strbuf_addstr(&buf, git_dir);
+	}
+	strbuf_addch(&buf, '/');
+
+	if (buf.len >= PATH_MAX)
+		return bad_path;
+	memcpy(pathname, buf.buf, buf.len + 1);
+
+	strbuf_release(&buf);
+	len = strlen(pathname);
+
+	va_start(args, fmt);
+	len += vsnprintf(pathname + len, PATH_MAX - len, fmt, args);
+	va_end(args);
+	if (len >= PATH_MAX)
+		return bad_path;
+	return cleanup_path(pathname);
+}
 
 /* git_mkstemp() - create tmp file honoring TMPDIR variable */
 int git_mkstemp(char *path, size_t len, const char *template)
diff --git a/refs.c b/refs.c
index b5400674d..e3c05110e 100644
--- a/refs.c
+++ b/refs.c
@@ -157,7 +157,7 @@ static struct cached_refs {
 	char did_packed;
 	struct ref_list *loose;
 	struct ref_list *packed;
-} cached_refs;
+} cached_refs, submodule_refs;
 static struct ref_list *current_ref;
 
 static struct ref_list *extra_refs;
@@ -229,23 +229,45 @@ void clear_extra_refs(void)
 	extra_refs = NULL;
 }
 
-static struct ref_list *get_packed_refs(void)
+static struct ref_list *get_packed_refs(const char *submodule)
 {
-	if (!cached_refs.did_packed) {
-		FILE *f = fopen(git_path("packed-refs"), "r");
-		cached_refs.packed = NULL;
+	const char *packed_refs_file;
+	struct cached_refs *refs;
+
+	if (submodule) {
+		packed_refs_file = git_path_submodule(submodule, "packed-refs");
+		refs = &submodule_refs;
+		free_ref_list(refs->packed);
+	} else {
+		packed_refs_file = git_path("packed-refs");
+		refs = &cached_refs;
+	}
+
+	if (!refs->did_packed || submodule) {
+		FILE *f = fopen(packed_refs_file, "r");
+		refs->packed = NULL;
 		if (f) {
-			read_packed_refs(f, &cached_refs);
+			read_packed_refs(f, refs);
 			fclose(f);
 		}
-		cached_refs.did_packed = 1;
+		refs->did_packed = 1;
 	}
-	return cached_refs.packed;
+	return refs->packed;
 }
 
-static struct ref_list *get_ref_dir(const char *base, struct ref_list *list)
+static struct ref_list *get_ref_dir(const char *submodule, const char *base,
+				    struct ref_list *list)
 {
-	DIR *dir = opendir(git_path("%s", base));
+	DIR *dir;
+	const char *path;
+
+	if (submodule)
+		path = git_path_submodule(submodule, "%s", base);
+	else
+		path = git_path("%s", base);
+
+
+	dir = opendir(path);
 
 	if (dir) {
 		struct dirent *de;
@@ -261,6 +283,7 @@ static struct ref_list *get_ref_dir(const char *base, struct ref_list *list)
 			struct stat st;
 			int flag;
 			int namelen;
+			const char *refdir;
 
 			if (de->d_name[0] == '.')
 				continue;
@@ -270,16 +293,27 @@ static struct ref_list *get_ref_dir(const char *base, struct ref_list *list)
 			if (has_extension(de->d_name, ".lock"))
 				continue;
 			memcpy(ref + baselen, de->d_name, namelen+1);
-			if (stat(git_path("%s", ref), &st) < 0)
+			refdir = submodule
+				? git_path_submodule(submodule, "%s", ref)
+				: git_path("%s", ref);
+			if (stat(refdir, &st) < 0)
 				continue;
 			if (S_ISDIR(st.st_mode)) {
-				list = get_ref_dir(ref, list);
+				list = get_ref_dir(submodule, ref, list);
 				continue;
 			}
-			if (!resolve_ref(ref, sha1, 1, &flag)) {
+			if (submodule) {
 				hashclr(sha1);
-				flag |= REF_BROKEN;
-			}
+				flag = 0;
+				if (resolve_gitlink_ref(submodule, ref, sha1) < 0) {
+					hashclr(sha1);
+					flag |= REF_BROKEN;
+				}
+			} else
+				if (!resolve_ref(ref, sha1, 1, &flag)) {
+					hashclr(sha1);
+					flag |= REF_BROKEN;
+				}
 			list = add_ref(ref, sha1, flag, list, NULL);
 		}
 		free(ref);
@@ -322,10 +356,16 @@ void warn_dangling_symref(FILE *fp, const char *msg_fmt, const char *refname)
 	for_each_rawref(warn_if_dangling_symref, &data);
 }
 
-static struct ref_list *get_loose_refs(void)
+static struct ref_list *get_loose_refs(const char *submodule)
 {
+	if (submodule) {
+		free_ref_list(submodule_refs.loose);
+		submodule_refs.loose = get_ref_dir(submodule, "refs", NULL);
+		return submodule_refs.loose;
+	}
+
 	if (!cached_refs.did_loose) {
-		cached_refs.loose = get_ref_dir("refs", NULL);
+		cached_refs.loose = get_ref_dir(NULL, "refs", NULL);
 		cached_refs.did_loose = 1;
 	}
 	return cached_refs.loose;
@@ -459,7 +499,7 @@ const char *resolve_ref(const char *ref, unsigned char *sha1, int reading, int *
 		git_snpath(path, sizeof(path), "%s", ref);
 		/* Special case: non-existing file. */
 		if (lstat(path, &st) < 0) {
-			struct ref_list *list = get_packed_refs();
+			struct ref_list *list = get_packed_refs(NULL);
 			while (list) {
 				if (!strcmp(ref, list->name)) {
 					hashcpy(sha1, list->sha1);
@@ -588,7 +628,7 @@ int peel_ref(const char *ref, unsigned char *sha1)
 		return -1;
 
 	if ((flag & REF_ISPACKED)) {
-		struct ref_list *list = get_packed_refs();
+		struct ref_list *list = get_packed_refs(NULL);
 
 		while (list) {
 			if (!strcmp(list->name, ref)) {
@@ -615,12 +655,12 @@ fallback:
 	return -1;
 }
 
-static int do_for_each_ref(const char *base, each_ref_fn fn, int trim,
-			   int flags, void *cb_data)
+static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn fn,
+			   int trim, int flags, void *cb_data)
 {
 	int retval = 0;
-	struct ref_list *packed = get_packed_refs();
-	struct ref_list *loose = get_loose_refs();
+	struct ref_list *packed = get_packed_refs(submodule);
+	struct ref_list *loose = get_loose_refs(submodule);
 
 	struct ref_list *extra;
 
@@ -657,24 +697,54 @@ end_each:
 	return retval;
 }
 
-int head_ref(each_ref_fn fn, void *cb_data)
+
+static int do_head_ref(const char *submodule, each_ref_fn fn, void *cb_data)
 {
 	unsigned char sha1[20];
 	int flag;
 
+	if (submodule) {
+		if (resolve_gitlink_ref(submodule, "HEAD", sha1) == 0)
+			return fn("HEAD", sha1, 0, cb_data);
+
+		return 0;
+	}
+
 	if (resolve_ref("HEAD", sha1, 1, &flag))
 		return fn("HEAD", sha1, flag, cb_data);
+
 	return 0;
 }
 
+int head_ref(each_ref_fn fn, void *cb_data)
+{
+	return do_head_ref(NULL, fn, cb_data);
+}
+
+int head_ref_submodule(const char *submodule, each_ref_fn fn, void *cb_data)
+{
+	return do_head_ref(submodule, fn, cb_data);
+}
+
 int for_each_ref(each_ref_fn fn, void *cb_data)
 {
-	return do_for_each_ref("refs/", fn, 0, 0, cb_data);
+	return do_for_each_ref(NULL, "refs/", fn, 0, 0, cb_data);
+}
+
+int for_each_ref_submodule(const char *submodule, each_ref_fn fn, void *cb_data)
+{
+	return do_for_each_ref(submodule, "refs/", fn, 0, 0, cb_data);
 }
 
 int for_each_ref_in(const char *prefix, each_ref_fn fn, void *cb_data)
 {
-	return do_for_each_ref(prefix, fn, strlen(prefix), 0, cb_data);
+	return do_for_each_ref(NULL, prefix, fn, strlen(prefix), 0, cb_data);
+}
+
+int for_each_ref_in_submodule(const char *submodule, const char *prefix,
+		each_ref_fn fn, void *cb_data)
+{
+	return do_for_each_ref(submodule, prefix, fn, strlen(prefix), 0, cb_data);
 }
 
 int for_each_tag_ref(each_ref_fn fn, void *cb_data)
@@ -682,19 +752,34 @@ int for_each_tag_ref(each_ref_fn fn, void *cb_data)
 	return for_each_ref_in("refs/tags/", fn, cb_data);
 }
 
+int for_each_tag_ref_submodule(const char *submodule, each_ref_fn fn, void *cb_data)
+{
+	return for_each_ref_in_submodule(submodule, "refs/tags/", fn, cb_data);
+}
+
 int for_each_branch_ref(each_ref_fn fn, void *cb_data)
 {
 	return for_each_ref_in("refs/heads/", fn, cb_data);
 }
 
+int for_each_branch_ref_submodule(const char *submodule, each_ref_fn fn, void *cb_data)
+{
+	return for_each_ref_in_submodule(submodule, "refs/heads/", fn, cb_data);
+}
+
 int for_each_remote_ref(each_ref_fn fn, void *cb_data)
 {
 	return for_each_ref_in("refs/remotes/", fn, cb_data);
 }
 
+int for_each_remote_ref_submodule(const char *submodule, each_ref_fn fn, void *cb_data)
+{
+	return for_each_ref_in_submodule(submodule, "refs/remotes/", fn, cb_data);
+}
+
 int for_each_replace_ref(each_ref_fn fn, void *cb_data)
 {
-	return do_for_each_ref("refs/replace/", fn, 13, 0, cb_data);
+	return do_for_each_ref(NULL, "refs/replace/", fn, 13, 0, cb_data);
 }
 
 int for_each_glob_ref_in(each_ref_fn fn, const char *pattern,
@@ -734,7 +819,7 @@ int for_each_glob_ref(each_ref_fn fn, const char *pattern, void *cb_data)
 
 int for_each_rawref(each_ref_fn fn, void *cb_data)
 {
-	return do_for_each_ref("refs/", fn, 0,
+	return do_for_each_ref(NULL, "refs/", fn, 0,
 			       DO_FOR_EACH_INCLUDE_BROKEN, cb_data);
 }
 
@@ -958,7 +1043,7 @@ static struct ref_lock *lock_ref_sha1_basic(const char *ref, const unsigned char
 	 * name is a proper prefix of our refname.
 	 */
 	if (missing &&
-	     !is_refname_available(ref, NULL, get_packed_refs(), 0)) {
+	     !is_refname_available(ref, NULL, get_packed_refs(NULL), 0)) {
 		last_errno = ENOTDIR;
 		goto error_return;
 	}
@@ -1021,7 +1106,7 @@ static int repack_without_ref(const char *refname)
 	int fd;
 	int found = 0;
 
-	packed_ref_list = get_packed_refs();
+	packed_ref_list = get_packed_refs(NULL);
 	for (list = packed_ref_list; list; list = list->next) {
 		if (!strcmp(refname, list->name)) {
 			found = 1;
@@ -1119,10 +1204,10 @@ int rename_ref(const char *oldref, const char *newref, const char *logmsg)
 	if (!symref)
 		return error("refname %s not found", oldref);
 
-	if (!is_refname_available(newref, oldref, get_packed_refs(), 0))
+	if (!is_refname_available(newref, oldref, get_packed_refs(NULL), 0))
 		return 1;
 
-	if (!is_refname_available(newref, oldref, get_loose_refs(), 0))
+	if (!is_refname_available(newref, oldref, get_loose_refs(NULL), 0))
 		return 1;
 
 	lock = lock_ref_sha1_basic(renamed_ref, NULL, 0, NULL);
diff --git a/refs.h b/refs.h
index 762ce504b..5e7a9a59f 100644
--- a/refs.h
+++ b/refs.h
@@ -28,6 +28,14 @@ extern int for_each_replace_ref(each_ref_fn, void *);
 extern int for_each_glob_ref(each_ref_fn, const char *pattern, void *);
 extern int for_each_glob_ref_in(each_ref_fn, const char *pattern, const char* prefix, void *);
 
+extern int head_ref_submodule(const char *submodule, each_ref_fn fn, void *cb_data);
+extern int for_each_ref_submodule(const char *submodule, each_ref_fn fn, void *cb_data);
+extern int for_each_ref_in_submodule(const char *submodule, const char *prefix,
+		each_ref_fn fn, void *cb_data);
+extern int for_each_tag_ref_submodule(const char *submodule, each_ref_fn fn, void *cb_data);
+extern int for_each_branch_ref_submodule(const char *submodule, each_ref_fn fn, void *cb_data);
+extern int for_each_remote_ref_submodule(const char *submodule, each_ref_fn fn, void *cb_data);
+
 static inline const char *has_glob_specials(const char *pattern)
 {
 	return strpbrk(pattern, "?*[");
diff --git a/revision.c b/revision.c
index 7e82efd93..5f2cf1e84 100644
--- a/revision.c
+++ b/revision.c
@@ -820,12 +820,12 @@ static void init_all_refs_cb(struct all_refs_cb *cb, struct rev_info *revs,
 	cb->all_flags = flags;
 }
 
-static void handle_refs(struct rev_info *revs, unsigned flags,
-		int (*for_each)(each_ref_fn, void *))
+static void handle_refs(const char *submodule, struct rev_info *revs, unsigned flags,
+		int (*for_each)(const char *, each_ref_fn, void *))
 {
 	struct all_refs_cb cb;
 	init_all_refs_cb(&cb, revs, flags);
-	for_each(handle_one_ref, &cb);
+	for_each(submodule, handle_one_ref, &cb);
 }
 
 static void handle_one_reflog_commit(unsigned char *sha1, void *cb_data)
@@ -1417,14 +1417,14 @@ void parse_revision_opt(struct rev_info *revs, struct parse_opt_ctx_t *ctx,
 	ctx->argc -= n;
 }
 
-static int for_each_bad_bisect_ref(each_ref_fn fn, void *cb_data)
+static int for_each_bad_bisect_ref(const char *submodule, each_ref_fn fn, void *cb_data)
 {
-	return for_each_ref_in("refs/bisect/bad", fn, cb_data);
+	return for_each_ref_in_submodule(submodule, "refs/bisect/bad", fn, cb_data);
 }
 
-static int for_each_good_bisect_ref(each_ref_fn fn, void *cb_data)
+static int for_each_good_bisect_ref(const char *submodule, each_ref_fn fn, void *cb_data)
 {
-	return for_each_ref_in("refs/bisect/good", fn, cb_data);
+	return for_each_ref_in_submodule(submodule, "refs/bisect/good", fn, cb_data);
 }
 
 static void append_prune_data(const char ***prune_data, const char **av)
@@ -1466,6 +1466,10 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct s
 {
 	int i, flags, left, seen_dashdash, read_from_stdin, got_rev_arg = 0;
 	const char **prune_data = NULL;
+	const char *submodule = NULL;
+
+	if (opt)
+		submodule = opt->submodule;
 
 	/* First, search for "--" */
 	seen_dashdash = 0;
@@ -1490,26 +1494,26 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct s
 			int opts;
 
 			if (!strcmp(arg, "--all")) {
-				handle_refs(revs, flags, for_each_ref);
-				handle_refs(revs, flags, head_ref);
+				handle_refs(submodule, revs, flags, for_each_ref_submodule);
+				handle_refs(submodule, revs, flags, head_ref_submodule);
 				continue;
 			}
 			if (!strcmp(arg, "--branches")) {
-				handle_refs(revs, flags, for_each_branch_ref);
+				handle_refs(submodule, revs, flags, for_each_branch_ref_submodule);
 				continue;
 			}
 			if (!strcmp(arg, "--bisect")) {
-				handle_refs(revs, flags, for_each_bad_bisect_ref);
-				handle_refs(revs, flags ^ UNINTERESTING, for_each_good_bisect_ref);
+				handle_refs(submodule, revs, flags, for_each_bad_bisect_ref);
+				handle_refs(submodule, revs, flags ^ UNINTERESTING, for_each_good_bisect_ref);
 				revs->bisect = 1;
 				continue;
 			}
 			if (!strcmp(arg, "--tags")) {
-				handle_refs(revs, flags, for_each_tag_ref);
+				handle_refs(submodule, revs, flags, for_each_tag_ref_submodule);
 				continue;
 			}
 			if (!strcmp(arg, "--remotes")) {
-				handle_refs(revs, flags, for_each_remote_ref);
+				handle_refs(submodule, revs, flags, for_each_remote_ref_submodule);
 				continue;
 			}
 			if (!prefixcmp(arg, "--glob=")) {
diff --git a/revision.h b/revision.h
index 36fdf22b2..05659c64a 100644
--- a/revision.h
+++ b/revision.h
@@ -151,6 +151,7 @@ extern volatile show_early_output_fn_t show_early_output;
 struct setup_revision_opt {
 	const char *def;
 	void (*tweak)(struct rev_info *, struct setup_revision_opt *);
+	const char *submodule;
 };
 
 extern void init_revisions(struct rev_info *revs, const char *prefix);
diff --git a/submodule.c b/submodule.c
index 7f0da48bc..91a475874 100644
--- a/submodule.c
+++ b/submodule.c
@@ -6,6 +6,7 @@
 #include "revision.h"
 #include "run-command.h"
 #include "diffcore.h"
+#include "refs.h"
 #include "string-list.h"
 
 struct string_list config_name_for_path;
@@ -296,3 +297,163 @@ unsigned is_submodule_modified(const char *path, int ignore_untracked)
 	strbuf_release(&buf);
 	return dirty_submodule;
 }
+
+static int find_first_merges(struct object_array *result, const char *path,
+		struct commit *a, struct commit *b)
+{
+	int i, j;
+	struct object_array merges;
+	struct commit *commit;
+	int contains_another;
+
+	char merged_revision[42];
+	const char *rev_args[] = { "rev-list", "--merges", "--ancestry-path",
+				   "--all", merged_revision, NULL };
+	struct rev_info revs;
+	struct setup_revision_opt rev_opts;
+
+	memset(&merges, 0, sizeof(merges));
+	memset(result, 0, sizeof(struct object_array));
+	memset(&rev_opts, 0, sizeof(rev_opts));
+
+	/* get all revisions that merge commit a */
+	snprintf(merged_revision, sizeof(merged_revision), "^%s",
+			sha1_to_hex(a->object.sha1));
+	init_revisions(&revs, NULL);
+	rev_opts.submodule = path;
+	setup_revisions(sizeof(rev_args)/sizeof(char *)-1, rev_args, &revs, &rev_opts);
+
+	/* save all revisions from the above list that contain b */
+	if (prepare_revision_walk(&revs))
+		die("revision walk setup failed");
+	while ((commit = get_revision(&revs)) != NULL) {
+		struct object *o = &(commit->object);
+		if (in_merge_bases(b, &commit, 1))
+			add_object_array(o, NULL, &merges);
+	}
+
+	/* Now we've got all merges that contain a and b. Prune all
+	 * merges that contain another found merge and save them in
+	 * result.
+	 */
+	for (i = 0; i < merges.nr; i++) {
+		struct commit *m1 = (struct commit *) merges.objects[i].item;
+
+		contains_another = 0;
+		for (j = 0; j < merges.nr; j++) {
+			struct commit *m2 = (struct commit *) merges.objects[j].item;
+			if (i != j && in_merge_bases(m2, &m1, 1)) {
+				contains_another = 1;
+				break;
+			}
+		}
+
+		if (!contains_another)
+			add_object_array(merges.objects[i].item,
+					 merges.objects[i].name, result);
+	}
+
+	free(merges.objects);
+	return result->nr;
+}
+
+static void print_commit(struct commit *commit)
+{
+	struct strbuf sb = STRBUF_INIT;
+	struct pretty_print_context ctx = {0};
+	ctx.date_mode = DATE_NORMAL;
+	format_commit_message(commit, " %h: %m %s", &sb, &ctx);
+	fprintf(stderr, "%s\n", sb.buf);
+	strbuf_release(&sb);
+}
+
+#define MERGE_WARNING(path, msg) \
+	warning("Failed to merge submodule %s (%s)", path, msg);
+
+int merge_submodule(unsigned char result[20], const char *path,
+		    const unsigned char base[20], const unsigned char a[20],
+		    const unsigned char b[20])
+{
+	struct commit *commit_base, *commit_a, *commit_b;
+	int parent_count;
+	struct object_array merges;
+
+	int i;
+
+	/* store a in result in case we fail */
+	hashcpy(result, a);
+
+	/* we can not handle deletion conflicts */
+	if (is_null_sha1(base))
+		return 0;
+	if (is_null_sha1(a))
+		return 0;
+	if (is_null_sha1(b))
+		return 0;
+
+	if (add_submodule_odb(path)) {
+		MERGE_WARNING(path, "not checked out");
+		return 0;
+	}
+
+	if (!(commit_base = lookup_commit_reference(base)) ||
+	    !(commit_a = lookup_commit_reference(a)) ||
+	    !(commit_b = lookup_commit_reference(b))) {
+		MERGE_WARNING(path, "commits not present");
+		return 0;
+	}
+
+	/* check whether both changes are forward */
+	if (!in_merge_bases(commit_base, &commit_a, 1) ||
+	    !in_merge_bases(commit_base, &commit_b, 1)) {
+		MERGE_WARNING(path, "commits don't follow merge-base");
+		return 0;
+	}
+
+	/* Case #1: a is contained in b or vice versa */
+	if (in_merge_bases(commit_a, &commit_b, 1)) {
+		hashcpy(result, b);
+		return 1;
+	}
+	if (in_merge_bases(commit_b, &commit_a, 1)) {
+		hashcpy(result, a);
+		return 1;
+	}
+
+	/*
+	 * Case #2: There are one or more merges that contain a and b in
+	 * the submodule. If there is only one, then present it as a
+	 * suggestion to the user, but leave it marked unmerged so the
+	 * user needs to confirm the resolution.
+	 */
+
+	/* find commit which merges them */
+	parent_count = find_first_merges(&merges, path, commit_a, commit_b);
+	switch (parent_count) {
+	case 0:
+		MERGE_WARNING(path, "merge following commits not found");
+		break;
+
+	case 1:
+		MERGE_WARNING(path, "not fast-forward");
+		fprintf(stderr, "Found a possible merge resolution "
+				"for the submodule:\n");
+		print_commit((struct commit *) merges.objects[0].item);
+		fprintf(stderr,
+			"If this is correct simply add it to the index "
+			"for example\n"
+			"by using:\n\n"
+			"  git update-index --cacheinfo 160000 %s \"%s\"\n\n"
+			"which will accept this suggestion.\n",
+			sha1_to_hex(merges.objects[0].item->sha1), path);
+		break;
+
+	default:
+		MERGE_WARNING(path, "multiple merges found");
+		for (i = 0; i < merges.nr; i++)
+			print_commit((struct commit *) merges.objects[i].item);
+	}
+
+	free(merges.objects);
+	return 0;
+}
diff --git a/submodule.h b/submodule.h
index 8ac4037b5..386f410a6 100644
--- a/submodule.h
+++ b/submodule.h
@@ -13,5 +13,7 @@ void show_submodule_summary(FILE *f, const char *path,
 		unsigned dirty_submodule,
 		const char *del, const char *add, const char *reset);
 unsigned is_submodule_modified(const char *path, int ignore_untracked);
+int merge_submodule(unsigned char result[20], const char *path, const unsigned char base[20],
+		    const unsigned char a[20], const unsigned char b[20]);
 
 #endif
diff --git a/t/t7405-submodule-merge.sh b/t/t7405-submodule-merge.sh
index 4a7b8933f..6ec559db0 100755
--- a/t/t7405-submodule-merge.sh
+++ b/t/t7405-submodule-merge.sh
@@ -54,13 +54,129 @@ test_expect_success setup '
 	git merge -s ours a
 '
 
-test_expect_success 'merging with modify/modify conflict' '
+# History setup
+#
+#      b
+#    /   \
+#   a     d
+#    \   /
+#      c
+#
+# a in the main repository records to sub-a in the submodule and
+# analogous b and c. d should be automatically found by merging c into
+# b in the main repository.
+test_expect_success 'setup for merge search' '
+	mkdir merge-search &&
+	cd merge-search &&
+	git init &&
+	mkdir sub &&
+	(cd sub &&
+	 git init &&
+	 echo "file-a" > file-a &&
+	 git add file-a &&
+	 git commit -m "sub-a" &&
+	 git branch sub-a) &&
+	git add sub &&
+	git commit -m "a" &&
+	git branch a &&
+
+	git checkout -b b &&
+	(cd sub &&
+	 git checkout -b sub-b &&
+	 echo "file-b" > file-b &&
+	 git add file-b &&
+	 git commit -m "sub-b") &&
+	git commit -a -m "b" &&
+
+	git checkout -b c a &&
+	(cd sub &&
+	 git checkout -b sub-c sub-a &&
+	 echo "file-c" > file-c &&
+	 git add file-c &&
+	 git commit -m "sub-c") &&
+	git commit -a -m "c" &&
+
+	git checkout -b d a &&
+	(cd sub &&
+	 git checkout -b sub-d sub-b &&
+	 git merge sub-c) &&
+	git commit -a -m "d" &&
+	git branch test b &&
+	cd ..
+'
+
+test_expect_success 'merge with one side as a fast-forward of the other' '
+	(cd merge-search &&
+	 git checkout -b test-forward b &&
+	 git merge d &&
+	 git ls-tree test-forward sub | cut -f1 | cut -f3 -d" " > actual &&
+	 (cd sub &&
+	  git rev-parse sub-d > ../expect) &&
+	 test_cmp actual expect)
+'
+
+test_expect_success 'merging should conflict for non fast-forward' '
+	(cd merge-search &&
+	 git checkout -b test-nonforward b &&
+	 (cd sub &&
+	  git rev-parse sub-d > ../expect) &&
+	 test_must_fail git merge c 2> actual  &&
+	 grep $(cat expect) actual > /dev/null &&
+	 git reset --hard)
+'
+
+test_expect_success 'merging should fail for ambiguous common parent' '
+	cd merge-search &&
+	git checkout -b test-ambiguous b &&
+	(cd sub &&
+	 git checkout -b ambiguous sub-b &&
+	 git merge sub-c &&
+	 git rev-parse sub-d > ../expect1 &&
+	 git rev-parse ambiguous > ../expect2) &&
+	test_must_fail git merge c 2> actual &&
+	grep $(cat expect1) actual > /dev/null &&
+	grep $(cat expect2) actual > /dev/null &&
+	git reset --hard &&
+	cd ..
+'
+
+# in a situation like this
+#
+# submodule tree:
+#
+#    sub-a --- sub-b --- sub-d
+#
+# main tree:
+#
+#    e (sub-a)
+#   /
+#  bb (sub-b)
+#   \
+#    f (sub-d)
+#
+# A merge between e and f should fail because one of the submodule
+# commits (sub-a) does not descend from the submodule merge-base (sub-b).
+#
+test_expect_success 'merging should fail for changes that are backwards' '
+	cd merge-search &&
+	git checkout -b bb a &&
+	(cd sub &&
+	 git checkout sub-b) &&
+	git commit -a -m "bb" &&
+
+	git checkout -b e bb &&
+	(cd sub &&
+	 git checkout sub-a) &&
+	git commit -a -m "e" &&
+
+	git checkout -b f bb &&
+	(cd sub &&
+	 git checkout sub-d) &&
+	git commit -a -m "f" &&
 
-	git checkout -b test1 a &&
-	test_must_fail git merge b &&
-	test -f .git/MERGE_MSG &&
-	git diff &&
-	test -n "$(git ls-files -u)"
+	git checkout -b test-backward e &&
+	test_must_fail git merge f &&
+	cd ..
 '
 
 test_expect_success 'merging with a modify/modify conflict between merge bases' '