Re: [PATCH] git-merge: Reduce heads before trying to merge them

[Junio C Hamano <gitster@pobox.com>]

Junio C Hamano <gitster@pobox.com> writes:

> Michał Kiedrowicz <michal.kiedrowicz@gmail.com> writes:
>
>> Junio C Hamano <gitster@pobox.com> wrote:
>>  
>>> I was cooking a fix on-and-off since yesterday evening, and sent it out a
>>> few minutes ago. I think the spirit is almost the same as Michał's updated
>>> patch, but it reduces the heads even earlier to catch cases where Michał's
>>> updated patch may misdiagnose arity of the resulting merge due to its use
>>> of remoteheads->next before the list is reduced (namely, the choice of the
>>> default strategy based on how many we are merging).
>>
>> I like your patches, especially how reducing heads is now done in
>> collect_parents() instead of doing it twice (before merging and in
>> finish_automerge()).  And that you got rid of global remoteheads too.
>
> Thanks.  Linus also said "Yes, that sounds right (on the road with just my
> phone, sorry for the html)" off-list to the series.

There was another bit still missing from my 4-patch series.

"merge" passes the updated test only because it runs the fmt_merge_msg()
internally after the reduction of the remotes, but without this update to
builtin/fmt-merge.msg.c, "pull" doesn't and its merge summary lists
unnecessary heads, because it calls the plumbing version from the script
with full set of possibly redundant parents.

-- >8 --
Subject: [PATCH] fmt-merge-msg: discard needless merge parents

This is used by "git pull" to construct a merge message from list of
remote refs.  When pulling redundant set of refs, however, it did not
filter them even though the merge itself discards them as unnecessary.

Teach the command to do the same for consistency.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 builtin/fmt-merge-msg.c       |  125 ++++++++++++++++++++++++++++++++++++++---
 t/t7603-merge-reduce-heads.sh |   31 +++++++++-
 2 files changed, 146 insertions(+), 10 deletions(-)

diff --git a/builtin/fmt-merge-msg.c b/builtin/fmt-merge-msg.c
index c81a7fe..dcc12ea 100644
--- a/builtin/fmt-merge-msg.c
+++ b/builtin/fmt-merge-msg.c
@@ -53,7 +53,47 @@ static void init_src_data(struct src_data *data)
 static struct string_list srcs = STRING_LIST_INIT_DUP;
 static struct string_list origins = STRING_LIST_INIT_DUP;
 
-static int handle_line(char *line)
+struct merge_parents {
+	int alloc, nr;
+	struct merge_parent {
+		unsigned char given[20];
+		unsigned char commit[20];
+		unsigned char used;
+	} *item;
+};
+
+/*
+ * I know, I know, this is inefficient, but you won't be pulling and merging
+ * hundreds of heads at a time anyway.
+ */
+static struct merge_parent *find_merge_parent(struct merge_parents *table,
+					      unsigned char *given,
+					      unsigned char *commit)
+{
+	int i;
+	for (i = 0; i < table->nr; i++) {
+		if (given && hashcmp(table->item[i].given, given))
+			continue;
+		if (commit && hashcmp(table->item[i].commit, commit))
+			continue;
+		return &table->item[i];
+	}
+	return NULL;
+}
+
+static void add_merge_parent(struct merge_parents *table,
+			     unsigned char *given,
+			     unsigned char *commit)
+{
+	if (table->nr && find_merge_parent(table, given, commit))
+		return;
+	ALLOC_GROW(table->item, table->nr + 1, table->alloc);
+	hashcpy(table->item[table->nr].given, given);
+	hashcpy(table->item[table->nr].commit, commit);
+	table->nr++;
+}
+
+static int handle_line(char *line, struct merge_parents *merge_parents)
 {
 	int i, len = strlen(line);
 	struct origin_data *origin_data;
@@ -61,6 +101,7 @@ static int handle_line(char *line)
 	struct src_data *src_data;
 	struct string_list_item *item;
 	int pulling_head = 0;
+	unsigned char sha1[20];
 
 	if (len < 43 || line[40] != '\t')
 		return 1;
@@ -71,14 +112,15 @@ static int handle_line(char *line)
 	if (line[41] != '\t')
 		return 2;
 
-	line[40] = 0;
-	origin_data = xcalloc(1, sizeof(struct origin_data));
-	i = get_sha1(line, origin_data->sha1);
-	line[40] = '\t';
-	if (i) {
-		free(origin_data);
+	i = get_sha1_hex(line, sha1);
+	if (i)
 		return 3;
-	}
+
+	if (!find_merge_parent(merge_parents, sha1, NULL))
+		return 0; /* subsumed by other parents */
+
+	origin_data = xcalloc(1, sizeof(struct origin_data));
+	hashcpy(origin_data->sha1, sha1);
 
 	if (line[len - 1] == '\n')
 		line[len - 1] = 0;
@@ -366,6 +408,68 @@ static void fmt_merge_msg_sigs(struct strbuf *out)
 	strbuf_release(&tagbuf);
 }
 
+static struct merge_parents *find_merge_parents(struct strbuf *in, unsigned char *head)
+{
+	struct commit_list *parents, *next;
+	struct commit *head_commit;
+	struct merge_parents *result = xcalloc(1, sizeof(*result));
+	int pos = 0, i, j;
+
+	parents = NULL;
+	while (pos < in->len) {
+		int len;
+		char *p = in->buf + pos;
+		char *newline = strchr(p, '\n');
+		unsigned char sha1[20];
+		struct commit *parent;
+		struct object *obj;
+
+		len = newline ? newline - p : strlen(p);
+		pos += len + !!newline;
+
+		if (len < 43 ||
+		    get_sha1_hex(p, sha1) ||
+		    p[40] != '\t' ||
+		    p[41] != '\t')
+			continue; /* skip not-for-merge */
+		/*
+		 * Do not use get_merge_parent() here; we do not have
+		 * "name" here and we do not want to contaminate its
+		 * util field yet.
+		 */
+		obj = parse_object(sha1);
+		parent = (struct commit *)peel_to_type(NULL, 0, obj, OBJ_COMMIT);
+		if (!parent)
+			continue;
+		commit_list_insert(parent, &parents);
+		add_merge_parent(result, obj->sha1, parent->object.sha1);
+	}
+	head_commit = lookup_commit(head);
+	if (head_commit)
+		commit_list_insert(head_commit, &parents);
+	parents = reduce_heads(parents);
+
+	while (parents) {
+		for (i = 0; i < result->nr; i++)
+			if (!hashcmp(result->item[i].commit,
+				     parents->item->object.sha1))
+				result->item[i].used = 1;
+		next = parents->next;
+		free(parents);
+		parents = next;
+	}
+
+	for (i = j = 0; i < result->nr; i++) {
+		if (result->item[i].used) {
+			if (i != j)
+				result->item[j] = result->item[i];
+			j++;
+		}
+	}
+	result->nr = j;
+	return result;
+}
+
 int fmt_merge_msg(struct strbuf *in, struct strbuf *out,
 		  struct fmt_merge_msg_opts *opts)
 {
@@ -373,6 +477,7 @@ int fmt_merge_msg(struct strbuf *in, struct strbuf *out,
 	unsigned char head_sha1[20];
 	const char *current_branch;
 	void *current_branch_to_free;
+	struct merge_parents *merge_parents;
 
 	/* get current branch */
 	current_branch = current_branch_to_free =
@@ -382,6 +487,8 @@ int fmt_merge_msg(struct strbuf *in, struct strbuf *out,
 	if (!prefixcmp(current_branch, "refs/heads/"))
 		current_branch += 11;
 
+	merge_parents = find_merge_parents(in, head_sha1);
+
 	/* get a line */
 	while (pos < in->len) {
 		int len;
@@ -392,7 +499,7 @@ int fmt_merge_msg(struct strbuf *in, struct strbuf *out,
 		pos += len + !!newline;
 		i++;
 		p[len] = 0;
-		if (handle_line(p))
+		if (handle_line(p, merge_parents))
 			die ("Error in line %d: %.*s", i, len, p);
 	}
 
diff --git a/t/t7603-merge-reduce-heads.sh b/t/t7603-merge-reduce-heads.sh
index a3b08a6..9894895 100755
--- a/t/t7603-merge-reduce-heads.sh
+++ b/t/t7603-merge-reduce-heads.sh
@@ -57,7 +57,36 @@ test_expect_success 'merge c1 with c2, c3, c4, c5' '
 	test -f c2.c &&
 	test -f c3.c &&
 	test -f c4.c &&
-	test -f c5.c
+	test -f c5.c &&
+	git show --format=%s -s >actual &&
+	! grep c1 actual &&
+	grep c2 actual &&
+	grep c3 actual &&
+	! grep c4 actual &&
+	grep c5 actual
+'
+
+test_expect_success 'pull c2, c3, c4, c5 into c1' '
+	git reset --hard c1 &&
+	git pull . c2 c3 c4 c5 &&
+	test "$(git rev-parse c1)" != "$(git rev-parse HEAD)" &&
+	test "$(git rev-parse c1)" = "$(git rev-parse HEAD^1)" &&
+	test "$(git rev-parse c2)" = "$(git rev-parse HEAD^2)" &&
+	test "$(git rev-parse c3)" = "$(git rev-parse HEAD^3)" &&
+	test "$(git rev-parse c5)" = "$(git rev-parse HEAD^4)" &&
+	git diff --exit-code &&
+	test -f c0.c &&
+	test -f c1.c &&
+	test -f c2.c &&
+	test -f c3.c &&
+	test -f c4.c &&
+	test -f c5.c &&
+	git show --format=%s -s >actual &&
+	! grep c1 actual &&
+	grep c2 actual &&
+	grep c3 actual &&
+	! grep c4 actual &&
+	grep c5 actual
 '
 
 test_expect_success 'setup' '
-- 
1.7.10.333.gf16fa