merge: use annotated commits for recursion

Use annotated commits to act as our virtual bases, instead of regular
commits, to avoid polluting the odb with virtual base commits and
trees.  Instead, build an annotated commit with an index and pointers
to the commits that it was merged from.

3 files changed, 122 insertions, 68 deletions

diff --git a/src/annotated_commit.c b/src/annotated_commit.c
index 3998a1af1..e53b95dee 100644
--- a/src/annotated_commit.c
+++ b/src/annotated_commit.c
@@ -15,6 +15,8 @@
 #include "git2/repository.h"
 #include "git2/annotated_commit.h"
 #include "git2/revparse.h"
+#include "git2/tree.h"
+#include "git2/index.h"
 
 static int annotated_commit_init(
 	git_annotated_commit **out,
@@ -108,6 +110,8 @@ int git_annotated_commit_from_commit(
 	annotated_commit = git__calloc(1, sizeof(git_annotated_commit));
 	GITERR_CHECK_ALLOC(annotated_commit);
 
+	annotated_commit->type = GIT_ANNOTATED_COMMIT_REAL;
+
 	git_cached_obj_incref(commit);
 	annotated_commit->commit = commit;
 
@@ -179,14 +183,20 @@ void git_annotated_commit_free(git_annotated_commit *annotated_commit)
 	if (annotated_commit == NULL)
 		return;
 
-	if (annotated_commit->commit != NULL)
-		git_commit_free(annotated_commit->commit);
-
-	if (annotated_commit->ref_name != NULL)
-		git__free(annotated_commit->ref_name);
-
-	if (annotated_commit->remote_url != NULL)
-		git__free(annotated_commit->remote_url);
+	switch (annotated_commit->type) {
+		case GIT_ANNOTATED_COMMIT_REAL:
+			git_commit_free(annotated_commit->commit);
+			git_tree_free(annotated_commit->tree);
+			git__free(annotated_commit->ref_name);
+			git__free(annotated_commit->remote_url);
+			break;
+		case GIT_ANNOTATED_COMMIT_VIRTUAL:
+			git_index_free(annotated_commit->index);
+			git_array_clear(annotated_commit->parents);
+			break;
+		default:
+			abort();
+	}
 
 	git__free(annotated_commit);
 }
diff --git a/src/annotated_commit.h b/src/annotated_commit.h
index 9a041176e..cbb88fd22 100644
--- a/src/annotated_commit.h
+++ b/src/annotated_commit.h
@@ -7,11 +7,31 @@
 #ifndef INCLUDE_annotated_commit_h__
 #define INCLUDE_annotated_commit_h__
 
+#include "oidarray.h"
+
 #include "git2/oid.h"
 
-/** Internal structure for merge inputs */
+typedef enum {
+	GIT_ANNOTATED_COMMIT_REAL = 1,
+	GIT_ANNOTATED_COMMIT_VIRTUAL = 2,
+} git_annotated_commit_t;
+
+/**
+ * Internal structure for merge inputs.  An annotated commit is generally
+ * "real" and backed by an actual commit in the repository, but merge will
+ * internally create "virtual" commits that are in-memory intermediate
+ * commits backed by an index.
+ */
 struct git_annotated_commit {
+	git_annotated_commit_t type;
+
+	/* real commit */
 	git_commit *commit;
+	git_tree *tree;
+
+	/* virtual commit structure */
+	git_index *index;
+	git_array_oid_t parents;
 
 	char *ref_name;
 	char *remote_url;
diff --git a/src/merge.c b/src/merge.c
index 59ac8e1ed..64c8f1116 100644
--- a/src/merge.c
+++ b/src/merge.c
@@ -1928,58 +1928,59 @@ static int merge_annotated_commits(
 	git_index **index_out,
 	git_annotated_commit **base_out,
 	git_repository *repo,
-	const git_annotated_commit *our_commit,
-	const git_annotated_commit *their_commit,
+	git_annotated_commit *our_commit,
+	git_annotated_commit *their_commit,
 	size_t recursion_level,
 	const git_merge_options *opts);
 
+GIT_INLINE(int) insert_head_ids(
+	git_array_oid_t *ids,
+	const git_annotated_commit *annotated_commit)
+{
+	git_oid *id;
+	size_t i;
+
+	if (annotated_commit->type == GIT_ANNOTATED_COMMIT_REAL) {
+		id = git_array_alloc(*ids);
+		GITERR_CHECK_ALLOC(id);
+
+		git_oid_cpy(id, git_commit_id(annotated_commit->commit));
+	} else {
+		for (i = 0; i < annotated_commit->parents.size; i++) {
+			id = git_array_alloc(*ids);
+			GITERR_CHECK_ALLOC(id);
+
+			git_oid_cpy(id, &annotated_commit->parents.ptr[i]);
+		}
+	}
+
+	return 0;
+}
+
 static int create_virtual_base(
 	git_annotated_commit **out,
 	git_repository *repo,
-	const git_annotated_commit *one,
-	const git_annotated_commit *two,
+	git_annotated_commit *one,
+	git_annotated_commit *two,
 	size_t recursion_level)
 {
+	git_annotated_commit *result = NULL;
 	git_index *index = NULL;
-	git_tree *tree = NULL;
-	git_commit *commit = NULL;
-	git_oid id, tree_id;
-	const git_commit *parents[2];
-	git_signature *signature = NULL;
-	int error;
-
-	parents[0] = one->commit;
-	parents[1] = two->commit;
-
-	if ((error = merge_annotated_commits(&index, NULL, repo, one, two,
-			recursion_level + 1, NULL)) < 0 ||
-		(error = git_index_write_tree_to(&tree_id, index, repo)) < 0 ||
-		(error = git_tree_lookup(&tree, repo, &tree_id)) < 0 ||
-		(error = git_signature_now(&signature, "Virtual", "virtual")) < 0 ||
-		(error = git_commit_create(&id, repo, NULL, signature, signature,
-			NULL, "virtual merged tree", tree, 2, parents)) < 0 ||
-		(error = git_commit_lookup(&commit, repo, &id)) < 0)
-		goto done;
 
-	error = git_annotated_commit_from_commit(out, commit);
+	result = git__calloc(1, sizeof(git_annotated_commit));
+	GITERR_CHECK_ALLOC(result);
 
-done:
-	git_commit_free(commit);
-	git_tree_free(tree);
-	git_index_free(index);
-	git_signature_free(signature);
+	if ((merge_annotated_commits(&index, NULL, repo, one, two,
+			recursion_level + 1, NULL)) < 0)
+		return -1;
 
-	return error;
-}
+	result->type = GIT_ANNOTATED_COMMIT_VIRTUAL;
+	result->index = index;
 
-GIT_INLINE(int) insert_head_ids(
-	git_array_oid_t *ids,
-	const git_annotated_commit *annotated_commit)
-{
-	git_oid *id = git_array_alloc(*ids);
-	GITERR_CHECK_ALLOC(id);
+	insert_head_ids(&result->parents, one);
+	insert_head_ids(&result->parents, two);
 
-	git_oid_cpy(id, git_commit_id(annotated_commit->commit));
+	*out = result;
 	return 0;
 }
 
@@ -2039,35 +2040,59 @@ done:
 	return error;
 }
 
+static int iterator_for_annotated_commit(
+	git_iterator **out,
+	git_annotated_commit *commit)
+{
+	git_iterator_options opts = GIT_ITERATOR_OPTIONS_INIT;
+	int error;
+
+	opts.flags = GIT_ITERATOR_DONT_IGNORE_CASE;
+
+	if (commit == NULL) {
+		error = git_iterator_for_nothing(out, &opts); 
+	} else if (commit->type == GIT_ANNOTATED_COMMIT_VIRTUAL) {
+		error = git_iterator_for_index(out, commit->index, &opts);
+	} else {
+		if (!commit->tree &&
+			(error = git_commit_tree(&commit->tree, commit->commit)) < 0)
+			goto done;
+
+		error = git_iterator_for_tree(out, commit->tree, &opts);
+	}
+
+done:
+	return error;
+}
+
 static int merge_annotated_commits(
 	git_index **index_out,
 	git_annotated_commit **base_out,
 	git_repository *repo,
-	const git_annotated_commit *our_commit,
-	const git_annotated_commit *their_commit,
+	git_annotated_commit *ours,
+	git_annotated_commit *theirs,
 	size_t recursion_level,
 	const git_merge_options *opts)
 {
 	git_annotated_commit *base = NULL;
-	git_tree *base_tree = NULL, *our_tree = NULL, *their_tree = NULL;
+	git_iterator *base_iter = NULL, *our_iter = NULL, *their_iter = NULL;
 	bool recurse = !opts || !(opts->flags & GIT_MERGE_NO_RECURSIVE);
 	int error;
 
-    if ((error = compute_base(&base, repo, our_commit, their_commit,
-		recurse, recursion_level)) < 0) {
+    if ((error = compute_base(&base, repo, ours, theirs, recurse,
+		recursion_level)) < 0) {
 
         if (error != GIT_ENOTFOUND)
             goto done;
 
         giterr_clear();
-    } else if ((error = git_commit_tree(&base_tree, base->commit)) < 0) {
-		goto done;
-	}
+    }
 
-	if ((error = git_commit_tree(&our_tree, our_commit->commit)) < 0 ||
-		(error = git_commit_tree(&their_tree, their_commit->commit)) < 0 ||
-		(error = git_merge_trees(index_out, repo, base_tree, our_tree,
-			their_tree, opts)) < 0)
+	if ((error = iterator_for_annotated_commit(&base_iter, base)) < 0 ||
+		(error = iterator_for_annotated_commit(&our_iter, ours)) < 0 ||
+		(error = iterator_for_annotated_commit(&their_iter, theirs)) < 0 ||
+		(error = git_merge__iterators(index_out, repo, base_iter, our_iter,
+			their_iter, opts)) < 0)
 		goto done;
 
 	if (base_out) {
@@ -2077,9 +2102,9 @@ static int merge_annotated_commits(
 
 done:
 	git_annotated_commit_free(base);
-	git_tree_free(our_tree);
-	git_tree_free(their_tree);
-	git_tree_free(base_tree);
+	git_iterator_free(base_iter);
+	git_iterator_free(our_iter);
+	git_iterator_free(their_iter);
 	return error;
 }
 
@@ -2558,14 +2583,13 @@ static int merge_normalize_checkout_opts(
 
 	out->checkout_strategy = checkout_strategy;
 
-	/* TODO: disambiguate between merged common ancestors and no common
-	 * ancestor (although git.git does not!)
-	 */
 	if (!out->ancestor_label) {
-		if (ancestor)
+		if (ancestor && ancestor->type == GIT_ANNOTATED_COMMIT_REAL)
 			out->ancestor_label = git_commit_summary(ancestor->commit);
-		else
+		else if (ancestor)
 			out->ancestor_label = "merged common ancestors";
+		else
+			out->ancestor_label = "empty base";
 	}
 
 	if (!out->our_label) {
@@ -2967,7 +2991,7 @@ int git_merge(
 	/* TODO: octopus */
 
 	if ((error = merge_annotated_commits(&index, &base, repo, our_head,
-			their_heads[0], 0, merge_opts)) < 0 ||
+			(git_annotated_commit *)their_heads[0], 0, merge_opts)) < 0 ||
 		(error = git_merge__check_result(repo, index)) < 0 ||
 		(error = git_merge__append_conflicts_to_merge_msg(repo, index)) < 0)
 		goto done;