merge-base: Remove redundant merge bases

2 files changed, 166 insertions, 22 deletions

diff --git a/src/commit_list.h b/src/commit_list.h
index b1d88e016..a6967bcef 100644
--- a/src/commit_list.h
+++ b/src/commit_list.h
@@ -13,6 +13,7 @@
 #define PARENT2  (1 << 1)
 #define RESULT   (1 << 2)
 #define STALE    (1 << 3)
+#define ALL_FLAGS (PARENT1 | PARENT2 | STALE | RESULT)
 
 #define PARENTS_PER_COMMIT	2
 #define COMMIT_ALLOC \
diff --git a/src/merge.c b/src/merge.c
index 13b524b81..1e523d76c 100644
--- a/src/merge.c
+++ b/src/merge.c
@@ -302,30 +302,59 @@ static int interesting(git_pqueue *list)
 	return 0;
 }
 
-int git_merge__bases_many(git_commit_list **out, git_revwalk *walk, git_commit_list_node *one, git_vector *twos)
+static void clear_commit_marks_1(git_commit_list **plist,
+		git_commit_list_node *commit, unsigned int mark)
 {
-	int error;
-	unsigned int i;
-	git_commit_list_node *two;
-	git_commit_list *result = NULL, *tmp = NULL;
-	git_pqueue list;
+	while (commit) {
+		unsigned int i;
 
-	/* If there's only the one commit, there can be no merge bases */
-	if (twos->length == 0) {
-		*out = NULL;
-		return 0;
+		if (!(mark & commit->flags))
+			return;
+
+		commit->flags &= ~mark;
+
+		for (i = 1; i < commit->out_degree; i++) {
+			git_commit_list_node *p = commit->parents[i];
+			git_commit_list_insert(p, plist);
+		}
+
+		commit = commit->parents[0];
 	}
+}
 
-	/* if the commit is repeated, we have a our merge base already */
-	git_vector_foreach(twos, i, two) {
-		if (one == two)
-			return git_commit_list_insert(one, out) ? 0 : -1;
+static void clear_commit_marks_many(git_vector *commits, unsigned int mark)
+{
+	git_commit_list *list = NULL;
+	git_commit_list_node *c;
+	unsigned int i;
+
+	git_vector_foreach(commits, i, c) {
+		git_commit_list_insert(c, &list);
 	}
 
-	if (git_pqueue_init(&list, 0, twos->length * 2, git_commit_list_time_cmp) < 0)
-		return -1;
+	while (list)
+		clear_commit_marks_1(&list, git_commit_list_pop(&list), mark);
+}
 
-	if (git_commit_list_parse(walk, one) < 0)
+static void clear_commit_marks(git_commit_list_node *commit, unsigned int mark)
+{
+	git_commit_list *list = NULL;
+	git_commit_list_insert(commit, &list);
+	while (list)
+		clear_commit_marks_1(&list, git_commit_list_pop(&list), mark);
+}
+
+static int paint_down_to_common(
+	git_commit_list **out, git_revwalk *walk, git_commit_list_node *one, git_vector *twos)
+{
+	git_pqueue list;
+	git_commit_list *result = NULL;
+	git_commit_list_node *two;
+
+	int error;
+	unsigned int i;
+
+	if (git_pqueue_init(&list, 0, twos->length * 2, git_commit_list_time_cmp) < 0)
 		return -1;
 
 	one->flags |= PARENT1;
@@ -376,19 +405,133 @@ int git_merge__bases_many(git_commit_list **out, git_revwalk *walk, git_commit_l
 	}
 
 	git_pqueue_free(&list);
+	*out = result;
+	return 0;
+}
+
+static int remove_redundant(git_revwalk *walk, git_vector *commits)
+{
+	git_vector work = GIT_VECTOR_INIT;
+	unsigned char *redundant;
+	unsigned int *filled_index;
+	unsigned int i, j;
+	int error = 0;
+
+	redundant = git__calloc(commits->length, 1);
+	filled_index = git__calloc((commits->length - 1), sizeof(unsigned int));
+
+	for (i = 0; i < commits->length; ++i) {
+		if ((error = git_commit_list_parse(walk, commits->contents[i])) < 0)
+			goto done;
+	}
+
+	for (i = 0; i < commits->length; ++i) {
+		git_commit_list *common = NULL;
+		git_commit_list_node *commit = commits->contents[i];
+
+		if (redundant[i])
+			continue;
+
+		git_vector_clear(&work);
+
+		for (j = 0; j < commits->length; j++) {
+			if (i == j || redundant[j])
+				continue;
+
+			filled_index[work.length] = j;
+			if ((error = git_vector_insert(&work, commits->contents[j])) < 0)
+				goto done;
+		}
+
+		error = paint_down_to_common(&common, walk, commit, &work);
+		if (error < 0)
+			goto done;
+
+		if (commit->flags & PARENT2)
+			redundant[i] = 1;
+
+		for (j = 0; j < work.length; j++) {
+			git_commit_list_node *w = work.contents[j];
+			if (w->flags & PARENT1)
+				redundant[filled_index[j]] = 1;
+		}
+
+		clear_commit_marks(commit, ALL_FLAGS);
+		clear_commit_marks_many(&work, ALL_FLAGS);
+
+		git_commit_list_free(&common);
+	}
+
+	for (i = 0; i < commits->length; ++i) {
+		if (redundant[i])
+			commits->contents[i] = NULL;
+	}
+
+done:
+	git__free(redundant);
+	git__free(filled_index);
+	git_vector_free(&work);
+	return error;
+}
+
+int git_merge__bases_many(git_commit_list **out, git_revwalk *walk, git_commit_list_node *one, git_vector *twos)
+{
+	int error;
+	unsigned int i;
+	git_commit_list_node *two;
+	git_commit_list *result = NULL, *tmp = NULL;
+
+	/* If there's only the one commit, there can be no merge bases */
+	if (twos->length == 0) {
+		*out = NULL;
+		return 0;
+	}
+
+	/* if the commit is repeated, we have a our merge base already */
+	git_vector_foreach(twos, i, two) {
+		if (one == two)
+			return git_commit_list_insert(one, out) ? 0 : -1;
+	}
+
+	if (git_commit_list_parse(walk, one) < 0)
+		return -1;
+
+	error = paint_down_to_common(&result, walk, one, twos);
+	if (error < 0)
+		return error;
 
 	/* filter out any stale commits in the results */
 	tmp = result;
 	result = NULL;
 
 	while (tmp) {
-		struct git_commit_list *next = tmp->next;
-		if (!(tmp->item->flags & STALE))
-			if (git_commit_list_insert_by_date(tmp->item, &result) == NULL)
+		git_commit_list_node *c = git_commit_list_pop(&tmp);
+		if (!(c->flags & STALE))
+			if (git_commit_list_insert_by_date(c, &result) == NULL)
 				return -1;
+	}
+
+	/* more than one merge base -- remove redundants */
+	if (result && result->next) {
+		git_vector redundant = GIT_VECTOR_INIT;
+
+		while (result)
+			git_vector_insert(&redundant, git_commit_list_pop(&result));
+
+		clear_commit_marks(one, ALL_FLAGS);
+		clear_commit_marks_many(twos, ALL_FLAGS);
+
+		if ((error = remove_redundant(walk, &redundant)) < 0) {
+			git_vector_free(&redundant);
+			return error;
+		}
+
+		git_vector_foreach(&redundant, i, two) {
+			if (two != NULL)
+				git_commit_list_insert_by_date(two, &result);
+		}
 
-		git__free(tmp);
-		tmp = next;
+		git_vector_free(&redundant);
 	}
 
 	*out = result;