Merge branch 'ks/combine-diff'

Teach combine-diff to honour the path-output-order imposed by
diffcore-order, and optimize how matching paths are found in
the N-way diffs made with parents.

* ks/combine-diff:
  tests: add checking that combine-diff emits only correct paths
  combine-diff: simplify intersect_paths() further
  combine-diff: combine_diff_path.len is not needed anymore
  combine-diff: optimize combine_diff_path sets intersection
  diff test: add tests for combine-diff with orderfile
  diffcore-order: export generic ordering interface

7 files changed, 246 insertions, 65 deletions

diff --git a/combine-diff.c b/combine-diff.c
index 3b92c44880..24ca7e2334 100644
--- a/combine-diff.c
+++ b/combine-diff.c
@@ -15,11 +15,10 @@
 static struct combine_diff_path *intersect_paths(struct combine_diff_path *curr, int n, int num_parent)
 {
 	struct diff_queue_struct *q = &diff_queued_diff;
-	struct combine_diff_path *p;
-	int i;
+	struct combine_diff_path *p, **tail = &curr;
+	int i, cmp;
 
 	if (!n) {
-		struct combine_diff_path *list = NULL, **tail = &list;
 		for (i = 0; i < q->nr; i++) {
 			int len;
 			const char *path;
@@ -31,7 +30,6 @@ static struct combine_diff_path *intersect_paths(struct combine_diff_path *curr,
 			p->path = (char *) &(p->parent[num_parent]);
 			memcpy(p->path, path, len);
 			p->path[len] = 0;
-			p->len = len;
 			p->next = NULL;
 			memset(p->parent, 0,
 			       sizeof(p->parent[0]) * num_parent);
@@ -44,31 +42,37 @@ static struct combine_diff_path *intersect_paths(struct combine_diff_path *curr,
 			*tail = p;
 			tail = &p->next;
 		}
-		return list;
+		return curr;
 	}
 
-	for (p = curr; p; p = p->next) {
-		int found = 0;
-		if (!p->len)
+	/*
+	 * paths in curr (linked list) and q->queue[] (array) are
+	 * both sorted in the tree order.
+	 */
+	i = 0;
+	while ((p = *tail) != NULL) {
+		cmp = ((i >= q->nr)
+		       ? -1 : strcmp(p->path, q->queue[i]->two->path));
+
+		if (cmp < 0) {
+			/* p->path not in q->queue[]; drop it */
+			*tail = p->next;
+			free(p);
 			continue;
-		for (i = 0; i < q->nr; i++) {
-			const char *path;
-			int len;
+		}
 
-			if (diff_unmodified_pair(q->queue[i]))
-				continue;
-			path = q->queue[i]->two->path;
-			len = strlen(path);
-			if (len == p->len && !memcmp(path, p->path, len)) {
-				found = 1;
-				hashcpy(p->parent[n].sha1, q->queue[i]->one->sha1);
-				p->parent[n].mode = q->queue[i]->one->mode;
-				p->parent[n].status = q->queue[i]->status;
-				break;
-			}
+		if (cmp > 0) {
+			/* q->queue[i] not in p->path; skip it */
+			i++;
+			continue;
 		}
-		if (!found)
-			p->len = 0;
+
+		hashcpy(p->parent[n].sha1, q->queue[i]->one->sha1);
+		p->parent[n].mode = q->queue[i]->one->mode;
+		p->parent[n].status = q->queue[i]->status;
+
+		tail = &p->next;
+		i++;
 	}
 	return curr;
 }
@@ -1219,8 +1223,6 @@ void show_combined_diff(struct combine_diff_path *p,
 {
 	struct diff_options *opt = &rev->diffopt;
 
-	if (!p->len)
-		return;
 	if (opt->output_format & (DIFF_FORMAT_RAW |
 				  DIFF_FORMAT_NAME |
 				  DIFF_FORMAT_NAME_STATUS))
@@ -1284,17 +1286,21 @@ static void handle_combined_callback(struct diff_options *opt,
 	q.queue = xcalloc(num_paths, sizeof(struct diff_filepair *));
 	q.alloc = num_paths;
 	q.nr = num_paths;
-	for (i = 0, p = paths; p; p = p->next) {
-		if (!p->len)
-			continue;
+	for (i = 0, p = paths; p; p = p->next)
 		q.queue[i++] = combined_pair(p, num_parent);
-	}
 	opt->format_callback(&q, opt, opt->format_callback_data);
 	for (i = 0; i < num_paths; i++)
 		free_combined_pair(q.queue[i]);
 	free(q.queue);
 }
 
+static const char *path_path(void *obj)
+{
+	struct combine_diff_path *path = (struct combine_diff_path *)obj;
+
+	return path->path;
+}
+
 void diff_tree_combined(const unsigned char *sha1,
 			const struct sha1_array *parents,
 			int dense,
@@ -1310,6 +1316,8 @@ void diff_tree_combined(const unsigned char *sha1,
 	diffopts.output_format = DIFF_FORMAT_NO_OUTPUT;
 	DIFF_OPT_SET(&diffopts, RECURSIVE);
 	DIFF_OPT_CLR(&diffopts, ALLOW_EXTERNAL);
+	/* tell diff_tree to emit paths in sorted (=tree) order */
+	diffopts.orderfile = NULL;
 
 	show_log_first = !!rev->loginfo && !rev->no_commit_id;
 	needsep = 0;
@@ -1335,22 +1343,46 @@ void diff_tree_combined(const unsigned char *sha1,
 				printf("%s%c", diff_line_prefix(opt),
 				       opt->line_termination);
 		}
+
+		/* if showing diff, show it in requested order */
+		if (diffopts.output_format != DIFF_FORMAT_NO_OUTPUT &&
+		    opt->orderfile) {
+			diffcore_order(opt->orderfile);
+		}
+
 		diff_flush(&diffopts);
 	}
 
-	/* find out surviving paths */
-	for (num_paths = 0, p = paths; p; p = p->next) {
-		if (p->len)
-			num_paths++;
+	/* find out number of surviving paths */
+	for (num_paths = 0, p = paths; p; p = p->next)
+		num_paths++;
+
+	/* order paths according to diffcore_order */
+	if (opt->orderfile && num_paths) {
+		struct obj_order *o;
+
+		o = xmalloc(sizeof(*o) * num_paths);
+		for (i = 0, p = paths; p; p = p->next, i++)
+			o[i].obj = p;
+		order_objects(opt->orderfile, path_path, o, num_paths);
+		for (i = 0; i < num_paths - 1; i++) {
+			p = o[i].obj;
+			p->next = o[i+1].obj;
+		}
+
+		p = o[num_paths-1].obj;
+		p->next = NULL;
+		paths = o[0].obj;
+		free(o);
 	}
+
+
 	if (num_paths) {
 		if (opt->output_format & (DIFF_FORMAT_RAW |
 					  DIFF_FORMAT_NAME |
 					  DIFF_FORMAT_NAME_STATUS)) {
-			for (p = paths; p; p = p->next) {
-				if (p->len)
-					show_raw_diff(p, num_parent, rev);
-			}
+			for (p = paths; p; p = p->next)
+				show_raw_diff(p, num_parent, rev);
 			needsep = 1;
 		}
 		else if (opt->output_format &
@@ -1363,11 +1395,9 @@ void diff_tree_combined(const unsigned char *sha1,
 			if (needsep)
 				printf("%s%c", diff_line_prefix(opt),
 				       opt->line_termination);
-			for (p = paths; p; p = p->next) {
-				if (p->len)
-					show_patch_diff(p, num_parent, dense,
-							0, rev);
-			}
+			for (p = paths; p; p = p->next)
+				show_patch_diff(p, num_parent, dense,
+						0, rev);
 		}
 	}
 
diff --git a/diff-lib.c b/diff-lib.c
index 2eddc66bbd..ec5f722eff 100644
--- a/diff-lib.c
+++ b/diff-lib.c
@@ -125,7 +125,6 @@ int run_diff_files(struct rev_info *revs, unsigned int option)
 			dpath->path = (char *) &(dpath->parent[5]);
 
 			dpath->next = NULL;
-			dpath->len = path_len;
 			memcpy(dpath->path, ce->name, path_len);
 			dpath->path[path_len] = '\0';
 			hashclr(dpath->sha1);
@@ -327,7 +326,6 @@ static int show_modified(struct rev_info *revs,
 		p = xmalloc(combine_diff_path_size(2, pathlen));
 		p->path = (char *) &p->parent[2];
 		p->next = NULL;
-		p->len = pathlen;
 		memcpy(p->path, new->name, pathlen);
 		p->path[pathlen] = 0;
 		p->mode = mode;
diff --git a/diff.h b/diff.h
index ce123fa06f..e79f3b3ff0 100644
--- a/diff.h
+++ b/diff.h
@@ -198,7 +198,6 @@ extern int diff_root_tree_sha1(const unsigned char *new, const char *base,
 
 struct combine_diff_path {
 	struct combine_diff_path *next;
-	int len;
 	char *path;
 	unsigned int mode;
 	unsigned char sha1[20];
diff --git a/diffcore-order.c b/diffcore-order.c
index fe7f1f4647..1bfcc39f90 100644
--- a/diffcore-order.c
+++ b/diffcore-order.c
@@ -57,12 +57,6 @@ static void prepare_order(const char *orderfile)
 	}
 }
 
-struct pair_order {
-	struct diff_filepair *pair;
-	int orig_order;
-	int order;
-};
-
 static int match_order(const char *path)
 {
 	int i;
@@ -84,35 +78,54 @@ static int match_order(const char *path)
 	return order_cnt;
 }
 
-static int compare_pair_order(const void *a_, const void *b_)
+static int compare_objs_order(const void *a_, const void *b_)
 {
-	struct pair_order const *a, *b;
-	a = (struct pair_order const *)a_;
-	b = (struct pair_order const *)b_;
+	struct obj_order const *a, *b;
+	a = (struct obj_order const *)a_;
+	b = (struct obj_order const *)b_;
 	if (a->order != b->order)
 		return a->order - b->order;
 	return a->orig_order - b->orig_order;
 }
 
+void order_objects(const char *orderfile, obj_path_fn_t obj_path,
+		   struct obj_order *objs, int nr)
+{
+	int i;
+
+	if (!nr)
+		return;
+
+	prepare_order(orderfile);
+	for (i = 0; i < nr; i++) {
+		objs[i].orig_order = i;
+		objs[i].order = match_order(obj_path(objs[i].obj));
+	}
+	qsort(objs, nr, sizeof(*objs), compare_objs_order);
+}
+
+static const char *pair_pathtwo(void *obj)
+{
+	struct diff_filepair *pair = (struct diff_filepair *)obj;
+
+	return pair->two->path;
+}
+
 void diffcore_order(const char *orderfile)
 {
 	struct diff_queue_struct *q = &diff_queued_diff;
-	struct pair_order *o;
+	struct obj_order *o;
 	int i;
 
 	if (!q->nr)
 		return;
 
 	o = xmalloc(sizeof(*o) * q->nr);
-	prepare_order(orderfile);
-	for (i = 0; i < q->nr; i++) {
-		o[i].pair = q->queue[i];
-		o[i].orig_order = i;
-		o[i].order = match_order(o[i].pair->two->path);
-	}
-	qsort(o, q->nr, sizeof(*o), compare_pair_order);
 	for (i = 0; i < q->nr; i++)
-		q->queue[i] = o[i].pair;
+		o[i].obj = q->queue[i];
+	order_objects(orderfile, pair_pathtwo, o, q->nr);
+	for (i = 0; i < q->nr; i++)
+		q->queue[i] = o[i].obj;
 	free(o);
 	return;
 }
diff --git a/diffcore.h b/diffcore.h
index 1315cfd4ef..92788ee4de 100644
--- a/diffcore.h
+++ b/diffcore.h
@@ -111,6 +111,20 @@ extern void diffcore_merge_broken(void);
 extern void diffcore_pickaxe(struct diff_options *);
 extern void diffcore_order(const char *orderfile);
 
+/* low-level interface to diffcore_order */
+struct obj_order {
+	void *obj;	/* setup by caller */
+
+	/* setup/used by order_objects() */
+	int orig_order;
+	int order;
+};
+
+typedef const char *(*obj_path_fn_t)(void *obj);
+
+void order_objects(const char *orderfile, obj_path_fn_t obj_path,
+		   struct obj_order *objs, int nr);
+
 #define DIFF_DEBUG 0
 #if DIFF_DEBUG
 void diff_debug_filespec(struct diff_filespec *, int, const char *);
diff --git a/t/t4056-diff-order.sh b/t/t4056-diff-order.sh
index 9e2b29ede5..c0460bb0e5 100755
--- a/t/t4056-diff-order.sh
+++ b/t/t4056-diff-order.sh
@@ -97,4 +97,25 @@ do
 	'
 done
 
+test_expect_success 'setup for testing combine-diff order' '
+	git checkout -b tmp HEAD~ &&
+	create_files 3 &&
+	git checkout master &&
+	git merge --no-commit -s ours tmp &&
+	create_files 5
+'
+
+test_expect_success "combine-diff: no order (=tree object order)" '
+	git diff --name-only HEAD HEAD^ HEAD^2 >actual &&
+	test_cmp expect_none actual
+'
+
+for i in 1 2
+do
+	test_expect_success "combine-diff: orderfile using option ($i)" '
+		git diff -Oorder_file_$i --name-only HEAD HEAD^ HEAD^2 >actual &&
+		test_cmp expect_$i actual
+	'
+done
+
 test_done
diff --git a/t/t4057-diff-combined-paths.sh b/t/t4057-diff-combined-paths.sh
new file mode 100755
index 0000000000..097e63215e
--- /dev/null
+++ b/t/t4057-diff-combined-paths.sh
@@ -0,0 +1,106 @@
+#!/bin/sh
+
+test_description='combined diff show only paths that are different to all parents'
+
+. ./test-lib.sh
+
+# verify that diffc.expect matches output of
+# `git diff -c --name-only HEAD HEAD^ HEAD^2`
+diffc_verify () {
+	git diff -c --name-only HEAD HEAD^ HEAD^2 >diffc.actual &&
+	test_cmp diffc.expect diffc.actual
+}
+
+test_expect_success 'trivial merge - combine-diff empty' '
+	for i in $(test_seq 1 9)
+	do
+		echo $i >$i.txt	&&
+		git add $i.txt
+	done &&
+	git commit -m "init" &&
+	git checkout -b side &&
+	for i in $(test_seq 2 9)
+	do
+		echo $i/2 >>$i.txt
+	done &&
+	git commit -a -m "side 2-9" &&
+	git checkout master &&
+	echo 1/2 >1.txt &&
+	git commit -a -m "master 1" &&
+	git merge side &&
+	>diffc.expect &&
+	diffc_verify
+'
+
+
+test_expect_success 'only one trully conflicting path' '
+	git checkout side &&
+	for i in $(test_seq 2 9)
+	do
+		echo $i/3 >>$i.txt
+	done &&
+	echo "4side" >>4.txt &&
+	git commit -a -m "side 2-9 +4" &&
+	git checkout master &&
+	for i in $(test_seq 1 9)
+	do
+		echo $i/3 >>$i.txt
+	done &&
+	echo "4master" >>4.txt &&
+	git commit -a -m "master 1-9 +4" &&
+	test_must_fail git merge side &&
+	cat <<-\EOF >4.txt &&
+	4
+	4/2
+	4/3
+	4master
+	4side
+	EOF
+	git add 4.txt &&
+	git commit -m "merge side (2)" &&
+	echo 4.txt >diffc.expect &&
+	diffc_verify
+'
+
+test_expect_success 'merge introduces new file' '
+	git checkout side &&
+	for i in $(test_seq 5 9)
+	do
+		echo $i/4 >>$i.txt
+	done &&
+	git commit -a -m "side 5-9" &&
+	git checkout master &&
+	for i in $(test_seq 1 3)
+	do
+		echo $i/4 >>$i.txt
+	done &&
+	git commit -a -m "master 1-3 +4hello" &&
+	git merge side &&
+	echo "Hello World" >4hello.txt &&
+	git add 4hello.txt &&
+	git commit --amend &&
+	echo 4hello.txt >diffc.expect &&
+	diffc_verify
+'
+
+test_expect_success 'merge removed a file' '
+	git checkout side &&
+	for i in $(test_seq 5 9)
+	do
+		echo $i/5 >>$i.txt
+	done &&
+	git commit -a -m "side 5-9" &&
+	git checkout master &&
+	for i in $(test_seq 1 3)
+	do
+		echo $i/4 >>$i.txt
+	done &&
+	git commit -a -m "master 1-3" &&
+	git merge side &&
+	git rm 4.txt &&
+	git commit --amend &&
+	echo 4.txt >diffc.expect &&
+	diffc_verify
+'
+
+test_done