iterator: provide git_iterator_walk

Provide `git_iterator_walk` to walk each iterator in lockstep,
returning each iterator's idea of the contents of the next path.

3 files changed, 133 insertions, 86 deletions

diff --git a/src/iterator.c b/src/iterator.c
index d5f7eec34..45eba3955 100644
--- a/src/iterator.c
+++ b/src/iterator.c
@@ -1843,3 +1843,91 @@ int git_iterator_advance_over_with_status(
 	return error;
 }
 
+int git_iterator_walk(
+	git_iterator **iterators,
+	size_t cnt,
+	git_iterator_walk_cb cb,
+	void *data)
+{
+	const git_index_entry **iterator_item;	/* next in each iterator */
+	const git_index_entry **cur_items;		/* current path in each iter */
+	const git_index_entry *first_match;
+	int cur_item_modified;
+	size_t i, j;
+	int error = 0;
+
+	iterator_item = git__calloc(cnt, sizeof(git_index_entry *));
+	cur_items = git__calloc(cnt, sizeof(git_index_entry *));
+
+	GITERR_CHECK_ALLOC(iterator_item);
+	GITERR_CHECK_ALLOC(cur_items);
+
+	/* Set up the iterators */
+	for (i = 0; i < cnt; i++) {
+		error = git_iterator_current(&iterator_item[i], iterators[i]);
+
+		if (error < 0 && error != GIT_ITEROVER)
+			goto done;
+	}
+
+	while (true) {
+		for (i = 0; i < cnt; i++)
+			cur_items[i] = NULL;
+
+		first_match = NULL;
+		cur_item_modified = 0;
+
+		/* Find the next path(s) to consume from each iterator */
+		for (i = 0; i < cnt; i++) {
+			if (iterator_item[i] == NULL)
+				continue;
+
+			if (first_match == NULL) {
+				first_match = iterator_item[i];
+				cur_items[i] = iterator_item[i];
+			} else {
+				int path_diff = git_index_entry_cmp(iterator_item[i], first_match);
+
+				if (path_diff < 0) {
+					/* Found an index entry that sorts before the one we're
+					 * looking at.  Forget that we've seen the other and
+					 * look at the other iterators for this path.
+					 */
+					for (j = 0; j < i; j++)
+						cur_items[j] = NULL;
+
+					first_match = iterator_item[i];
+					cur_items[i] = iterator_item[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] = iterator_item[i];
+				}
+			}
+		}
+
+		if (first_match == NULL)
+			break;
+
+		if ((error = cb(cur_items, data)) != 0)
+			goto done;
+
+		/* Advance each iterator that participated */
+		for (i = 0; i < cnt; i++) {
+			if (cur_items[i] == NULL)
+				continue;
+
+			error = git_iterator_advance(&iterator_item[i], iterators[i]);
+
+			if (error < 0 && error != GIT_ITEROVER)
+				goto done;
+		}
+	}
+
+done:
+	if (error == GIT_ITEROVER)
+		error = 0;
+
+	return error;
+}
diff --git a/src/iterator.h b/src/iterator.h
index 57f82416a..893e5db50 100644
--- a/src/iterator.h
+++ b/src/iterator.h
@@ -294,4 +294,19 @@ extern int git_iterator_advance_over_with_status(
  */
 extern int git_iterator_index(git_index **out, git_iterator *iter);
 
+typedef int (*git_iterator_walk_cb)(
+	const git_index_entry **entries,
+	void *data);
+
+/**
+ * Walk the given iterators in lock-step.  The given callback will be
+ * called for each unique path, with the index entry in each iterator
+ * (or NULL if the given iterator does not contain that path).
+ */
+extern int git_iterator_walk(
+	git_iterator **iterators,
+	size_t cnt,
+	git_iterator_walk_cb cb,
+	void *data);
+
 #endif
diff --git a/src/merge.c b/src/merge.c
index 517d317de..9d6252ea8 100644
--- a/src/merge.c
+++ b/src/merge.c
@@ -1449,6 +1449,34 @@ static int merge_diff_list_insert_unmodified(
 	return error;
 }
 
+struct merge_diff_find_data {
+	git_merge_diff_list *diff_list;
+	struct merge_diff_df_data df_data;
+};
+
+static int queue_difference(const git_index_entry **entries, void *data)
+{
+	struct merge_diff_find_data *find_data = data;
+	bool item_modified = false;
+	size_t i;
+
+	if (!entries[0] || !entries[1] || !entries[2]) {
+		item_modified = true;
+	} else {
+		for (i = 1; i < 3; i++) {
+			if (index_entry_cmp(entries[0], entries[i]) != 0) {
+				item_modified = true;
+				break;
+			}
+		}
+	}
+
+	return item_modified ?
+		merge_diff_list_insert_conflict(
+			find_data->diff_list, &find_data->df_data, entries) :
+		merge_diff_list_insert_unmodified(find_data->diff_list, entries);
+}
+
 int git_merge_diff_list__find_differences(
 	git_merge_diff_list *diff_list,
 	git_iterator *ancestor_iter,
@@ -1456,93 +1484,9 @@ int git_merge_diff_list__find_differences(
 	git_iterator *their_iter)
 {
 	git_iterator *iterators[3] = { ancestor_iter, our_iter, their_iter };
-	const 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, j;
-	int error = 0;
-
-	assert(diff_list && (our_iter || their_iter));
-
-	/* Set up the iterators */
-	for (i = 0; i < 3; i++) {
-		error = git_iterator_current(&items[i], iterators[i]);
-
-		if (error < 0 && error != GIT_ITEROVER)
-			goto done;
-	}
-
-	while (true) {
-		for (i = 0; i < 3; i++)
-			cur_items[i] = NULL;
-
-		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.
-					 */
-					for (j = 0; j < i; j++)
-						cur_items[j] = NULL;
-
-					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_diff_list_insert_conflict(diff_list, &df_data, cur_items);
-		else
-			error = merge_diff_list_insert_unmodified(diff_list, cur_items);
-		if (error < 0)
-			goto done;
+	struct merge_diff_find_data find_data = { diff_list };
 
-		/* Advance each iterator that participated */
-		for (i = 0; i < 3; i++) {
-			if (cur_items[i] == NULL)
-				continue;
-
-			error = git_iterator_advance(&items[i], iterators[i]);
-
-			if (error < 0 && error != GIT_ITEROVER)
-				goto done;
-		}
-	}
-
-done:
-	if (error == GIT_ITEROVER)
-		error = 0;
-
-	return error;
+	return git_iterator_walk(iterators, 3, queue_difference, &find_data);
 }
 
 git_merge_diff_list *git_merge_diff_list__alloc(git_repository *repo)