[PATCHv4 5/6] fast-export: Fix output order of D/F changes

[Elijah Newren <newren@gmail.com>]

The fast-import stream format requires incremental changes which take place
immediately, meaning that for D->F conversions all files below the relevant
directory must be deleted before the resulting file of the same name is
created.  Reversing the order can result in fast-import silently deleting
the file right after creating it, resulting in the file missing from the
resulting repository.

We correct this by first sorting the diff_queue_struct in depth-first
order.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
Email from Junio:
> If all you want is to force a particular order of paths in the output
> (e.g. depth first) in this one single application, the cleanest way might
> be to let the diffcore do its work and at the very end sort the elements
> in the diff_queued_diff to your liking (c.f. diffcore_fix_diff_index()
> that uses diffnamecmp() to sort the list).
This patch is my attempt to do precisely that.

 builtin/fast-export.c  |   29 +++++++++++++++++++++++++++++
 t/t9350-fast-export.sh |    2 +-
 2 files changed, 30 insertions(+), 1 deletions(-)

diff --git a/builtin/fast-export.c b/builtin/fast-export.c
index c6dd71a..965e90e 100644
--- a/builtin/fast-export.c
+++ b/builtin/fast-export.c
@@ -147,10 +147,39 @@ static void handle_object(const unsigned char *sha1)
 	free(buf);
 }
 
+static int depth_first(const void *a_, const void *b_)
+{
+	const struct diff_filepair *a = *((const struct diff_filepair **)a_);
+	const struct diff_filepair *b = *((const struct diff_filepair **)b_);
+	const char *name_a, *name_b;
+	int len_a, len_b, len;
+	int cmp;
+
+	name_a = a->one ? a->one->path : a->two->path;
+	name_b = b->one ? b->one->path : b->two->path;
+
+	len_a = strlen(name_a);
+	len_b = strlen(name_b);
+	len = (len_a < len_b) ? len_a : len_b;
+
+	/* strcmp will sort 'd' before 'd/e', we want 'd/e' before 'd' */
+	cmp = memcmp(name_a, name_b, len);
+	if (cmp)
+		return cmp;
+	return (len_b - len_a);
+}
+
 static void show_filemodify(struct diff_queue_struct *q,
 			    struct diff_options *options, void *data)
 {
 	int i;
+
+	/*
+	 * Handle files below a directory first, in case they are all deleted
+	 * and the directory changes to a file or symlink.
+	 */
+	qsort(q->queue, q->nr, sizeof(q->queue[0]), depth_first);
+
 	for (i = 0; i < q->nr; i++) {
 		struct diff_filespec *ospec = q->queue[i]->one;
 		struct diff_filespec *spec = q->queue[i]->two;
diff --git a/t/t9350-fast-export.sh b/t/t9350-fast-export.sh
index 69179c6..1ee1461 100755
--- a/t/t9350-fast-export.sh
+++ b/t/t9350-fast-export.sh
@@ -376,7 +376,7 @@ test_expect_success 'tree_tag-obj'    'git fast-export tree_tag-obj'
 test_expect_success 'tag-obj_tag'     'git fast-export tag-obj_tag'
 test_expect_success 'tag-obj_tag-obj' 'git fast-export tag-obj_tag-obj'
 
-test_expect_failure 'directory becomes symlink'        '
+test_expect_success 'directory becomes symlink'        '
 	git init dirtosymlink &&
 	git init result &&
 	(
-- 
1.7.1.1.23.gafea6