merge!

1 files changed, 843 insertions, 3 deletions

diff --git a/src/merge.c b/src/merge.c
index e0010d6a4..8df156abe 100644
--- a/src/merge.c
+++ b/src/merge.c
@@ -5,15 +5,52 @@
  * a Linking Exception. For full terms see the included COPYING file.
  */
 
+#include "common.h"
+#include "posix.h"
+#include "buffer.h"
 #include "repository.h"
 #include "revwalk.h"
-#include "buffer.h"
+#include "commit_list.h"
 #include "merge.h"
+#include "path.h"
 #include "refs.h"
+#include "object.h"
+#include "iterator.h"
+#include "refs.h"
+#include "diff.h"
+#include "checkout.h"
+#include "tree.h"
+#include "merge_file.h"
+#include "blob.h"
+#include "hashsig.h"
+
+#include "git2/types.h"
 #include "git2/repository.h"
+#include "git2/object.h"
+#include "git2/commit.h"
 #include "git2/merge.h"
+#include "git2/refs.h"
 #include "git2/reset.h"
-#include "commit_list.h"
+#include "git2/checkout.h"
+#include "git2/signature.h"
+#include "git2/config.h"
+#include "git2/tree.h"
+
+#define GIT_MERGE_INDEX_ENTRY_EXISTS(X)	((X).mode != 0)
+
+typedef enum {
+	TREE_IDX_ANCESTOR = 0,
+	TREE_IDX_OURS = 1,
+	TREE_IDX_THEIRS = 2
+} merge_tree_index_t;
+
+/* Tracks D/F conflicts */
+struct merge_diff_df_data {
+	const char *df_path;
+	const char *prev_path;
+	git_merge_diff *prev_conflict;
+};
+
 
 int git_repository_merge_cleanup(git_repository *repo)
 {
@@ -48,6 +85,8 @@ cleanup:
 	return error;
 }
 
+/* Merge base computation */
+
 int git_merge_base_many(git_oid *out, git_repository *repo, const git_oid input_array[], size_t length)
 {
 	git_revwalk *walk;
@@ -177,7 +216,7 @@ int git_merge__bases_many(git_commit_list **out, git_revwalk *walk, git_commit_l
 		return -1;
 
 	if (git_commit_list_parse(walk, one) < 0)
-	    return -1;
+		return -1;
 
 	one->flags |= PARENT1;
 	if (git_pqueue_insert(&list, one) < 0)
@@ -294,3 +333,804 @@ cleanup:
 
 	return error;
 }
+
+GIT_INLINE(int) index_entry_cmp(const git_index_entry *a, const git_index_entry *b)
+{
+	int value = 0;
+
+	if (a->path == NULL)
+		return (b->path == NULL) ? 0 : 1;
+
+	if ((value = a->mode - b->mode) == 0 &&
+		(value = git_oid__cmp(&a->oid, &b->oid)) == 0)
+		value = strcmp(a->path, b->path);
+
+	return value;
+}
+
+/* Conflict resolution */
+
+static int merge_conflict_resolve_trivial(
+	int *resolved,
+	git_merge_diff_list *diff_list,
+	const git_merge_diff *conflict)
+{
+	int ancestor_empty, ours_empty, theirs_empty;
+	int ours_changed, theirs_changed, ours_theirs_differ;
+	git_index_entry const *result = NULL;
+	int error = 0;
+
+	assert(resolved && diff_list && conflict);
+
+	*resolved = 0;
+
+	if (conflict->type == GIT_MERGE_DIFF_DIRECTORY_FILE ||
+		conflict->type == GIT_MERGE_DIFF_RENAMED_ADDED)
+		return 0;
+	
+	if (conflict->our_status == GIT_DELTA_RENAMED ||
+		conflict->their_status == GIT_DELTA_RENAMED)
+		return 0;
+
+	ancestor_empty = !GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->ancestor_entry);
+	ours_empty = !GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->our_entry);
+	theirs_empty = !GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->their_entry);
+	
+	ours_changed = (conflict->our_status != GIT_DELTA_UNMODIFIED);
+	theirs_changed = (conflict->their_status != GIT_DELTA_UNMODIFIED);
+	ours_theirs_differ = ours_changed && theirs_changed &&
+		index_entry_cmp(&conflict->our_entry, &conflict->their_entry);
+
+	/*
+	 * Note: with only one ancestor, some cases are not distinct:
+	 *
+	 * 16: ancest:anc1/anc2, head:anc1, remote:anc2 = result:no merge
+	 * 3: ancest:(empty)^, head:head, remote:(empty) = result:no merge
+	 * 2: ancest:(empty)^, head:(empty), remote:remote = result:no merge
+	 *
+	 * Note that the two cases that take D/F conflicts into account
+	 * specifically do not need to be explicitly tested, as D/F conflicts
+	 * would fail the *empty* test:
+	 *
+	 * 3ALT: ancest:(empty)+, head:head, remote:*empty* = result:head
+	 * 2ALT: ancest:(empty)+, head:*empty*, remote:remote = result:remote
+	 *
+	 * Note that many of these cases need not be explicitly tested, as
+	 * they simply degrade to "all different" cases (eg, 11):
+	 *
+	 * 4: ancest:(empty)^, head:head, remote:remote = result:no merge
+	 * 7: ancest:ancest+, head:(empty), remote:remote = result:no merge
+	 * 9: ancest:ancest+, head:head, remote:(empty) = result:no merge
+	 * 11: ancest:ancest+, head:head, remote:remote = result:no merge
+	 */
+
+	/* 5ALT: ancest:*, head:head, remote:head = result:head */
+	if (ours_changed && !ours_empty && !ours_theirs_differ)
+		result = &conflict->our_entry;
+	/* 6: ancest:ancest+, head:(empty), remote:(empty) = result:no merge */
+	else if (ours_changed && ours_empty && theirs_empty)
+		*resolved = 0;
+	/* 8: ancest:ancest^, head:(empty), remote:ancest = result:no merge */
+	else if (ours_empty && !theirs_changed)
+		*resolved = 0;
+	/* 10: ancest:ancest^, head:ancest, remote:(empty) = result:no merge */
+	else if (!ours_changed && theirs_empty)
+		*resolved = 0;
+	/* 13: ancest:ancest+, head:head, remote:ancest = result:head */
+	else if (ours_changed && !theirs_changed)
+		result = &conflict->our_entry;
+	/* 14: ancest:ancest+, head:ancest, remote:remote = result:remote */
+	else if (!ours_changed && theirs_changed)
+		result = &conflict->their_entry;
+	else
+		*resolved = 0;
+
+	if (result != NULL &&
+		GIT_MERGE_INDEX_ENTRY_EXISTS(*result) &&
+		(error = git_vector_insert(&diff_list->staged, (void *)result)) >= 0)
+		*resolved = 1;
+
+	/* Note: trivial resolution does not update the REUC. */
+	
+	return error;
+}
+
+static int merge_conflict_resolve_one_removed(
+	int *resolved,
+	git_merge_diff_list *diff_list,
+	const git_merge_diff *conflict)
+{
+	int ours_empty, theirs_empty;
+	int ours_changed, theirs_changed;
+	int error = 0;
+
+	assert(resolved && diff_list && conflict);
+
+	*resolved = 0;
+
+	if (conflict->type == GIT_MERGE_DIFF_DIRECTORY_FILE ||
+		conflict->type == GIT_MERGE_DIFF_RENAMED_ADDED)
+		return 0;
+
+	ours_empty = !GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->our_entry);
+	theirs_empty = !GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->their_entry);
+
+	ours_changed = (conflict->our_status != GIT_DELTA_UNMODIFIED);
+	theirs_changed = (conflict->their_status != GIT_DELTA_UNMODIFIED);
+
+	/* Removed in both */
+	if (ours_changed && ours_empty && theirs_empty)
+		*resolved = 1;
+	/* Removed in ours */
+	else if (ours_empty && !theirs_changed)
+		*resolved = 1;
+	/* Removed in theirs */
+	else if (!ours_changed && theirs_empty)
+		*resolved = 1;
+
+	if (*resolved)
+		git_vector_insert(&diff_list->resolved, (git_merge_diff *)conflict);
+
+	return error;
+}
+
+
+static int merge_conflict_resolve_one_renamed(
+	int *resolved,
+	git_merge_diff_list *diff_list,
+	const git_merge_diff *conflict)
+{
+	int ours_renamed, theirs_renamed;
+	int ours_changed, theirs_changed;
+	git_index_entry *merged;
+	int error = 0;
+	
+	assert(resolved && diff_list && conflict);
+	
+	*resolved = 0;
+
+	if (!GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->our_entry) ||
+		!GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->their_entry))
+		return 0;
+
+	ours_renamed = (conflict->our_status == GIT_DELTA_RENAMED);
+	theirs_renamed = (conflict->their_status == GIT_DELTA_RENAMED);
+	
+	if (!ours_renamed && !theirs_renamed)
+		return 0;
+
+	/* Reject one file in a 2->1 conflict */
+	if (conflict->type == GIT_MERGE_DIFF_BOTH_RENAMED_2_TO_1 ||
+		conflict->type == GIT_MERGE_DIFF_BOTH_RENAMED_1_TO_2 ||
+		conflict->type == GIT_MERGE_DIFF_RENAMED_ADDED)
+		return 0;
+
+	ours_changed = (git_oid__cmp(&conflict->ancestor_entry.oid, &conflict->our_entry.oid) != 0);
+	theirs_changed = (git_oid__cmp(&conflict->ancestor_entry.oid, &conflict->their_entry.oid) != 0);
+	
+	/* if both are modified (and not to a common target) require a merge */
+	if (ours_changed && theirs_changed &&
+		git_oid__cmp(&conflict->our_entry.oid, &conflict->their_entry.oid) != 0)
+		return 0;
+
+	if ((merged = git_pool_malloc(&diff_list->pool, sizeof(git_index_entry))) == NULL)
+		return -1;
+	
+	if (ours_changed)
+		memcpy(merged, &conflict->our_entry, sizeof(git_index_entry));
+	else
+		memcpy(merged, &conflict->their_entry, sizeof(git_index_entry));
+
+	if (ours_renamed)
+		merged->path = conflict->our_entry.path;
+	else
+		merged->path = conflict->their_entry.path;
+	
+	*resolved = 1;
+	
+	git_vector_insert(&diff_list->staged, merged);
+	git_vector_insert(&diff_list->resolved, (git_merge_diff *)conflict);
+	
+	return error;
+}
+
+static int merge_conflict_resolve_automerge(
+	int *resolved,
+	git_merge_diff_list *diff_list,
+	const git_merge_diff *conflict,
+	unsigned int automerge_flags)
+{
+	git_merge_file_input ancestor = GIT_MERGE_FILE_INPUT_INIT,
+		ours = GIT_MERGE_FILE_INPUT_INIT,
+		theirs = GIT_MERGE_FILE_INPUT_INIT;
+	git_merge_file_result result = GIT_MERGE_FILE_RESULT_INIT;
+	git_index_entry *index_entry;
+	git_odb *odb = NULL;
+	git_oid automerge_oid;
+	int error = 0;
+	
+	assert(resolved && diff_list && conflict);
+	
+	*resolved = 0;
+	
+	if (automerge_flags == GIT_MERGE_AUTOMERGE_NONE)
+		return 0;
+
+	/* Reject D/F conflicts */
+	if (conflict->type == GIT_MERGE_DIFF_DIRECTORY_FILE)
+		return 0;
+
+	/* Reject link/file conflicts. */
+	if ((S_ISLNK(conflict->ancestor_entry.mode) ^ S_ISLNK(conflict->our_entry.mode)) ||
+		(S_ISLNK(conflict->ancestor_entry.mode) ^ S_ISLNK(conflict->their_entry.mode)))
+		return 0;
+
+	/* Reject name conflicts */
+	if (conflict->type == GIT_MERGE_DIFF_BOTH_RENAMED_2_TO_1 ||
+		conflict->type == GIT_MERGE_DIFF_RENAMED_ADDED)
+		return 0;
+
+	if ((conflict->our_status & GIT_DELTA_RENAMED) == GIT_DELTA_RENAMED &&
+		(conflict->their_status & GIT_DELTA_RENAMED) == GIT_DELTA_RENAMED &&
+		strcmp(conflict->ancestor_entry.path, conflict->their_entry.path) != 0)
+		return 0;
+
+	if ((error = git_repository_odb(&odb, diff_list->repo)) < 0 ||
+		(error = git_merge_file_input_from_index_entry(&ancestor, diff_list->repo, &conflict->ancestor_entry)) < 0 ||
+		(error = git_merge_file_input_from_index_entry(&ours, diff_list->repo, &conflict->our_entry)) < 0 ||
+		(error = git_merge_file_input_from_index_entry(&theirs, diff_list->repo, &conflict->their_entry)) < 0 ||
+		(error = git_merge_files(&result, &ancestor, &ours, &theirs, automerge_flags)) < 0 ||
+		!result.automergeable ||
+		(error = git_odb_write(&automerge_oid, odb, result.data, result.len, GIT_OBJ_BLOB)) < 0)
+		goto done;
+	
+	if ((index_entry = git_pool_malloc(&diff_list->pool, sizeof(git_index_entry))) == NULL)
+	GITERR_CHECK_ALLOC(index_entry);
+
+	index_entry->path = git_pool_strdup(&diff_list->pool, result.path);
+	GITERR_CHECK_ALLOC(index_entry->path);
+
+	index_entry->file_size = result.len;
+	index_entry->mode = result.mode;
+	git_oid_cpy(&index_entry->oid, &automerge_oid);
+	
+	git_vector_insert(&diff_list->staged, index_entry);
+	git_vector_insert(&diff_list->resolved, (git_merge_diff *)conflict);
+
+	*resolved = 1;
+
+done:
+	git_merge_file_input_free(&ancestor);
+	git_merge_file_input_free(&ours);
+	git_merge_file_input_free(&theirs);
+	git_merge_file_result_free(&result);
+	git_odb_free(odb);
+	
+	return error;
+}
+
+static int merge_conflict_resolve(
+	int *out,
+	git_merge_diff_list *diff_list,
+	const git_merge_diff *conflict,
+	unsigned int automerge_flags)
+{
+	int resolved = 0;
+	int error = 0;
+	
+	*out = 0;
+	
+	if ((error = merge_conflict_resolve_trivial(&resolved, diff_list, conflict)) < 0)
+		goto done;
+
+	if (automerge_flags != GIT_MERGE_AUTOMERGE_NONE) {
+		if (!resolved && (error = merge_conflict_resolve_one_removed(&resolved, diff_list, conflict)) < 0)
+			goto done;
+		
+		if (!resolved && (error = merge_conflict_resolve_one_renamed(&resolved, diff_list, conflict)) < 0)
+			goto done;
+
+		if (!resolved && (error = merge_conflict_resolve_automerge(&resolved, diff_list, conflict, automerge_flags)) < 0)
+			goto done;
+	}
+
+	*out = resolved;
+	
+done:
+	return error;
+}
+
+/* Directory/file conflict handling */
+
+GIT_INLINE(const char *) merge_diff_path(
+	const git_merge_diff *conflict)
+{
+	if (GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->ancestor_entry))
+		return conflict->ancestor_entry.path;
+	else if (GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->our_entry))
+		return conflict->our_entry.path;
+	else if (GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->their_entry))
+		return conflict->their_entry.path;
+	
+	return NULL;
+}
+
+GIT_INLINE(bool) merge_diff_any_side_added_or_modified(
+	const git_merge_diff *conflict)
+{
+	if (conflict->our_status == GIT_DELTA_ADDED ||
+		conflict->our_status == GIT_DELTA_MODIFIED ||
+		conflict->their_status == GIT_DELTA_ADDED ||
+		conflict->their_status == GIT_DELTA_MODIFIED)
+		return true;
+	
+	return false;
+}
+
+GIT_INLINE(bool) path_is_prefixed(const char *parent, const char *child)
+{
+	size_t child_len = strlen(child);
+	size_t parent_len = strlen(parent);
+	
+	if (child_len < parent_len ||
+		strncmp(parent, child, parent_len) != 0)
+		return 0;
+	
+	return (child[parent_len] == '/');
+}
+
+GIT_INLINE(int) merge_diff_detect_df_conflict(
+	struct merge_diff_df_data *df_data,
+	git_merge_diff *conflict)
+{
+	const char *cur_path = merge_diff_path(conflict);
+	
+	/* Determine if this is a D/F conflict or the child of one */
+	if (df_data->df_path &&
+		path_is_prefixed(df_data->df_path, cur_path))
+		conflict->type = GIT_MERGE_DIFF_DF_CHILD;
+	else if(df_data->df_path)
+		df_data->df_path = NULL;
+	else if (df_data->prev_path &&
+		merge_diff_any_side_added_or_modified(df_data->prev_conflict) &&
+		merge_diff_any_side_added_or_modified(conflict) &&
+		path_is_prefixed(df_data->prev_path, cur_path)) {
+		conflict->type = GIT_MERGE_DIFF_DF_CHILD;
+		
+		df_data->prev_conflict->type = GIT_MERGE_DIFF_DIRECTORY_FILE;
+		df_data->df_path = df_data->prev_path;
+	}
+	
+	df_data->prev_path = cur_path;
+	df_data->prev_conflict = conflict;
+	
+	return 0;
+}
+
+/* Conflict handling */
+
+GIT_INLINE(int) merge_diff_detect_type(
+	git_merge_diff *conflict)
+{
+	if (conflict->our_status == GIT_DELTA_ADDED &&
+		conflict->their_status == GIT_DELTA_ADDED)
+		conflict->type = GIT_MERGE_DIFF_BOTH_ADDED;
+	else if (conflict->our_status == GIT_DELTA_MODIFIED &&
+			 conflict->their_status == GIT_DELTA_MODIFIED)
+		conflict->type = GIT_MERGE_DIFF_BOTH_MODIFIED;
+	else if (conflict->our_status == GIT_DELTA_DELETED &&
+			 conflict->their_status == GIT_DELTA_DELETED)
+		conflict->type = GIT_MERGE_DIFF_BOTH_DELETED;
+	else if (conflict->our_status == GIT_DELTA_MODIFIED &&
+			 conflict->their_status == GIT_DELTA_DELETED)
+		conflict->type = GIT_MERGE_DIFF_MODIFIED_DELETED;
+	else if (conflict->our_status == GIT_DELTA_DELETED &&
+			 conflict->their_status == GIT_DELTA_MODIFIED)
+		conflict->type = GIT_MERGE_DIFF_MODIFIED_DELETED;
+	else
+		conflict->type = GIT_MERGE_DIFF_NONE;
+	
+	return 0;
+}
+
+GIT_INLINE(int) index_entry_dup(
+	git_index_entry *out,
+	git_pool *pool,
+	const git_index_entry *src)
+{
+	if (src != NULL) {
+		memcpy(out, src, sizeof(git_index_entry));
+		
+		if ((out->path = git_pool_strdup(pool, src->path)) == NULL)
+			return -1;
+	}
+	
+	return 0;
+}
+
+GIT_INLINE(int) merge_delta_type_from_index_entries(
+	const git_index_entry *ancestor,
+	const git_index_entry *other)
+{
+	if (ancestor == NULL && other == NULL)
+		return GIT_DELTA_UNMODIFIED;
+	else if (ancestor == NULL && other != NULL)
+		return GIT_DELTA_ADDED;
+	else if (ancestor != NULL && other == NULL)
+		return GIT_DELTA_DELETED;
+	else if (S_ISDIR(ancestor->mode) ^ S_ISDIR(other->mode))
+		return GIT_DELTA_TYPECHANGE;
+	else if(S_ISLNK(ancestor->mode) ^ S_ISLNK(other->mode))
+		return GIT_DELTA_TYPECHANGE;
+	else if (git_oid__cmp(&ancestor->oid, &other->oid) ||
+			 ancestor->mode != other->mode)
+		return GIT_DELTA_MODIFIED;
+	
+	return GIT_DELTA_UNMODIFIED;
+}
+
+static git_merge_diff *merge_diff_from_index_entries(
+	git_merge_diff_list *diff_list,
+	const git_index_entry **entries)
+{
+	git_merge_diff *conflict;
+	git_pool *pool = &diff_list->pool;
+	
+	if ((conflict = git_pool_malloc(pool, sizeof(git_merge_diff))) == NULL)
+		return NULL;
+	
+	if (index_entry_dup(&conflict->ancestor_entry, pool, entries[TREE_IDX_ANCESTOR]) < 0 ||
+		index_entry_dup(&conflict->our_entry, pool, entries[TREE_IDX_OURS]) < 0 ||
+		index_entry_dup(&conflict->their_entry, pool, entries[TREE_IDX_THEIRS]) < 0)
+		return NULL;
+	
+	conflict->our_status = merge_delta_type_from_index_entries(
+		entries[TREE_IDX_ANCESTOR], entries[TREE_IDX_OURS]);
+	conflict->their_status = merge_delta_type_from_index_entries(
+		entries[TREE_IDX_ANCESTOR], entries[TREE_IDX_THEIRS]);
+	
+	return conflict;
+}
+
+/* Merge trees */
+
+static int merge_index_insert_conflict(
+	git_merge_diff_list *diff_list,
+	struct merge_diff_df_data *merge_df_data,
+	const git_index_entry *tree_items[3])
+{
+	git_merge_diff *conflict;
+	
+	if ((conflict = merge_diff_from_index_entries(diff_list, tree_items)) == NULL ||
+		merge_diff_detect_type(conflict) < 0 ||
+		merge_diff_detect_df_conflict(merge_df_data, conflict) < 0 ||
+		git_vector_insert(&diff_list->conflicts, conflict) < 0)
+		return -1;
+	
+	return 0;
+}
+
+static int merge_index_insert_unmodified(
+	git_merge_diff_list *diff_list,
+	const git_index_entry *tree_items[3])
+{
+	int error = 0;
+	git_index_entry *entry;
+	
+	entry = git_pool_malloc(&diff_list->pool, sizeof(git_index_entry));
+	GITERR_CHECK_ALLOC(entry);
+	
+	if ((error = index_entry_dup(entry, &diff_list->pool, tree_items[0])) >= 0)
+		error = git_vector_insert(&diff_list->staged, entry);
+	
+	return error;
+}
+
+int git_merge_diff_list__find_differences(
+	git_merge_diff_list *diff_list,
+	const git_tree *ancestor_tree,
+	const git_tree *our_tree,
+	const git_tree *their_tree)
+{
+	git_iterator *iterators[3] = {0};
+	git_index_entry *items[3] = {0}, *best_cur_item, *cur_items[3];
+	git_vector_cmp entry_compare = git_index_entry__cmp;
+	struct merge_diff_df_data df_data = {0};
+	int cur_item_modified;
+	size_t i;
+	int error = 0;
+	
+	assert(diff_list && our_tree && their_tree);
+
+	if ((error = git_iterator_for_tree(&iterators[TREE_IDX_ANCESTOR], (git_tree *)ancestor_tree, GIT_ITERATOR_DONT_IGNORE_CASE, NULL, NULL)) < 0 ||
+		(error = git_iterator_for_tree(&iterators[TREE_IDX_OURS], (git_tree *)our_tree, GIT_ITERATOR_DONT_IGNORE_CASE, NULL, NULL)) < 0 ||
+		(error = git_iterator_for_tree(&iterators[TREE_IDX_THEIRS], (git_tree *)their_tree, GIT_ITERATOR_DONT_IGNORE_CASE, NULL, NULL)) < 0)
+		goto done;
+	
+	/* Set up the iterators */
+	for (i = 0; i < 3; i++) {
+		if ((error = git_iterator_current(&items[i], iterators[i])) < 0)
+			goto done;
+	}
+	
+	while (true) {
+		memset(cur_items, 0x0, sizeof(git_index_entry *) * 3);
+		best_cur_item = NULL;
+		cur_item_modified = 0;
+		
+		/* Find the next path(s) to consume from each iterator */
+		for (i = 0; i < 3; i++) {
+			if (items[i] == NULL) {
+				cur_item_modified = 1;
+				continue;
+			}
+			
+			if (best_cur_item == NULL) {
+				best_cur_item = items[i];
+				cur_items[i] = items[i];
+			} else {
+				int path_diff = entry_compare(items[i], best_cur_item);
+				
+				if (path_diff < 0) {
+					/*
+					 * Found an item that sorts before our current item, make
+					 * our current item this one.
+					 */
+					memset(cur_items, 0x0, sizeof(git_index_entry *) * 3);
+					cur_item_modified = 1;
+					best_cur_item = items[i];
+					cur_items[i] = items[i];
+				} else if (path_diff > 0) {
+					/* No entry for the current item, this is modified */
+					cur_item_modified = 1;
+				} else if (path_diff == 0) {
+					cur_items[i] = items[i];
+					
+					if (!cur_item_modified)
+						cur_item_modified = index_entry_cmp(best_cur_item, items[i]);
+				}
+			}
+		}
+		
+		if (best_cur_item == NULL)
+			break;
+		
+		if (cur_item_modified)
+			error = merge_index_insert_conflict(diff_list, &df_data, cur_items);
+		else
+			error = merge_index_insert_unmodified(diff_list, cur_items);
+		
+		/* Advance each iterator that participated */
+		for (i = 0; i < 3; i++) {
+			if (cur_items[i] != NULL &&
+				(error = git_iterator_advance(&items[i], iterators[i])) < 0)
+				goto done;
+		}
+	}
+	
+done:
+	for (i = 0; i < 3; i++)
+		git_iterator_free(iterators[i]);
+	
+	return error;
+}
+
+git_merge_diff_list *git_merge_diff_list__alloc(git_repository *repo)
+{
+	git_merge_diff_list *diff_list = git__calloc(1, sizeof(git_merge_diff_list));
+	
+	if (diff_list == NULL)
+		return NULL;
+	
+	diff_list->repo = repo;
+	
+	if (git_vector_init(&diff_list->staged, 0, NULL) < 0 ||
+		git_vector_init(&diff_list->conflicts, 0, NULL) < 0 ||
+		git_vector_init(&diff_list->resolved, 0, NULL) < 0 ||
+		git_pool_init(&diff_list->pool, 1, 0) < 0)
+		return NULL;
+	
+	return diff_list;
+}
+
+static int merge_tree_normalize_opts(
+	git_repository *repo,
+	git_merge_tree_opts *opts,
+	const git_merge_tree_opts *given)
+{
+	git_config *cfg = NULL;
+	int error = 0;
+	
+	assert(repo && opts);
+	
+	if ((error = git_repository_config__weakptr(&cfg, repo)) < 0)
+		return error;
+	
+	if (given != NULL)
+		memcpy(opts, given, sizeof(git_merge_tree_opts));
+	else {
+		git_merge_tree_opts init = GIT_MERGE_TREE_OPTS_INIT;
+		memcpy(opts, &init, sizeof(init));
+	}
+	
+	return 0;
+}
+
+
+static int merge_index_insert_reuc(
+	git_index *index,
+	size_t idx,
+	const git_index_entry *entry)
+{
+	const git_index_reuc_entry *reuc;
+	int mode[3] = { 0, 0, 0 };
+	git_oid const *oid[3] = { NULL, NULL, NULL };
+	size_t i;
+	
+	if (!GIT_MERGE_INDEX_ENTRY_EXISTS(*entry))
+		return 0;
+	
+	if ((reuc = git_index_reuc_get_bypath(index, entry->path)) != NULL) {
+		for (i = 0; i < 3; i++) {
+			mode[i] = reuc->mode[i];
+			oid[i] = &reuc->oid[i];
+		}
+	}
+	
+	mode[idx] = entry->mode;
+	oid[idx] = &entry->oid;
+	
+	return git_index_reuc_add(index, entry->path,
+		mode[0], oid[0], mode[1], oid[1], mode[2], oid[2]);
+}
+
+int index_from_diff_list(git_index **out, git_merge_diff_list *diff_list)
+{
+	git_index *index;
+	size_t i;
+	git_index_entry *entry;
+	git_merge_diff *conflict;
+	int error = 0;
+	
+	*out = NULL;
+	
+	if ((error = git_index_new(&index)) < 0)
+		return error;
+	
+	git_vector_foreach(&diff_list->staged, i, entry) {
+		if ((error = git_index_add(index, entry)) < 0)
+			goto on_error;
+	}
+	
+	git_vector_foreach(&diff_list->conflicts, i, conflict) {
+		const git_index_entry *ancestor =
+			GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->ancestor_entry) ?
+			&conflict->ancestor_entry : NULL;
+		
+		const git_index_entry *ours =
+			GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->our_entry) ?
+			&conflict->our_entry : NULL;
+		
+		const git_index_entry *theirs =
+			GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->their_entry) ?
+			&conflict->their_entry : NULL;
+		
+		if ((error = git_index_conflict_add(index, ancestor, ours, theirs)) < 0)
+			goto on_error;
+	}
+	
+	/* Add each rename entry to the rename portion of the index. */
+	git_vector_foreach(&diff_list->conflicts, i, conflict) {
+		const char *ancestor_path, *our_path, *their_path;
+		
+		if (!GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->ancestor_entry))
+			continue;
+		
+		ancestor_path = conflict->ancestor_entry.path;
+		
+		our_path =
+			GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->our_entry) ?
+			conflict->our_entry.path : NULL;
+		
+		their_path =
+			GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->their_entry) ?
+			conflict->their_entry.path : NULL;
+	}
+	
+	/* Add each entry in the resolved conflict to the REUC independently, since
+	 * the paths may differ due to renames. */
+	git_vector_foreach(&diff_list->resolved, i, conflict) {
+		const git_index_entry *ancestor =
+			GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->ancestor_entry) ?
+			&conflict->ancestor_entry : NULL;
+
+		const git_index_entry *ours =
+			GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->our_entry) ?
+			&conflict->our_entry : NULL;
+		
+		const git_index_entry *theirs =
+			GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->their_entry) ?
+			&conflict->their_entry : NULL;
+
+		if (ancestor != NULL &&
+			(error = merge_index_insert_reuc(index, TREE_IDX_ANCESTOR, ancestor)) < 0)
+			goto on_error;
+		
+		if (ours != NULL &&
+			(error = merge_index_insert_reuc(index, TREE_IDX_OURS, ours)) < 0)
+			goto on_error;
+		
+		if (theirs != NULL &&
+			(error = merge_index_insert_reuc(index, TREE_IDX_THEIRS, theirs)) < 0)
+			goto on_error;
+	}
+	
+	*out = index;
+	return 0;
+	
+on_error:
+	git_index_free(index);
+	
+	return error;
+}
+
+int git_merge_trees(
+	git_index **out,
+	git_repository *repo,
+	const git_tree *ancestor_tree,
+	const git_tree *our_tree,
+	const git_tree *their_tree,
+	const git_merge_tree_opts *given_opts)
+{
+	git_merge_diff_list *diff_list;
+	git_merge_tree_opts opts;
+	git_merge_diff *conflict;
+	git_vector changes;
+	size_t i;
+	int error = 0;
+
+	assert(out && repo && our_tree && their_tree);
+
+	*out = NULL;
+	
+	if ((error = merge_tree_normalize_opts(repo, &opts, given_opts)) < 0)
+		return error;
+
+	diff_list = git_merge_diff_list__alloc(repo);
+	GITERR_CHECK_ALLOC(diff_list);
+	
+	if ((error = git_merge_diff_list__find_differences(diff_list, ancestor_tree, our_tree, their_tree)) < 0)
+		goto done;
+	
+	memcpy(&changes, &diff_list->conflicts, sizeof(git_vector));
+	git_vector_clear(&diff_list->conflicts);
+	
+	git_vector_foreach(&changes, i, conflict) {
+		int resolved = 0;
+		
+		if ((error = merge_conflict_resolve(&resolved, diff_list, conflict, opts.automerge_flags)) < 0)
+			goto done;
+		
+		if (!resolved)
+			git_vector_insert(&diff_list->conflicts, conflict);
+	}
+	
+	error = index_from_diff_list(out, diff_list);
+
+done:
+	git_merge_diff_list__free(diff_list);
+
+	return error;
+}
+
+void git_merge_diff_list__free(git_merge_diff_list *diff_list)
+{
+	if (!diff_list)
+		return;
+	
+	git_vector_free(&diff_list->staged);
+	git_vector_free(&diff_list->conflicts);
+	git_vector_free(&diff_list->resolved);
+	git_pool_clear(&diff_list->pool);
+	git__free(diff_list);
+}