[PATCH 1/2] fast-export: deletion action first

[PATCH 1/2] fast-export: deletion action first

[Miguel Torroja]

The delete operations of the fast-export output should precede any addition
belonging to the same commit, Addition and deletion with the same name
entry could happen in case of file to directory and viceversa.

The fast-export sorting was added in 060df62 (fast-export: Fix output
order of D/F changes). That change was made in order to fix the case of
directory to file in the same commit, but it broke the reverse case
(File to directory).

Signed-off-by: Miguel Torroja <miguel.torroja@gmail.com>
---
 builtin/fast-export.c | 25 +++++++++----------------
 1 file changed, 9 insertions(+), 16 deletions(-)

diff --git a/builtin/fast-export.c b/builtin/fast-export.c
index e022063..a3ab7da 100644
--- a/builtin/fast-export.c
+++ b/builtin/fast-export.c
@@ -260,26 +260,19 @@ static void export_blob(const struct object_id *oid)
 		free(buf);
 }
 
-static int depth_first(const void *a_, const void *b_)
+/*
+ * Compares two diff types to order based on output priorities.
+ */
+static int diff_type_cmp(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;
-	cmp = len_b - len_a;
+	/*
+	 * Move Delete entries first so that an addition is always reported after
+	 */
+	cmp = (b->status == DIFF_STATUS_DELETED) - (a->status == DIFF_STATUS_DELETED);
 	if (cmp)
 		return cmp;
 	/*
@@ -347,7 +340,7 @@ static void show_filemodify(struct diff_queue_struct *q,
 	 * 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, depth_first);
+	QSORT(q->queue, q->nr, diff_type_cmp);
 
 	for (i = 0; i < q->nr; i++) {
 		struct diff_filespec *ospec = q->queue[i]->one;
-- 
2.1.4

[PATCH 2/2] fast-export: DIFF_STATUS_RENAMED instead of 'R'

[Miguel Torroja]

Minor change to be consistent with the rest of the fast-export code.
DIFF_STATUS_RENAMED is defined as 'R'.

Signed-off-by: Miguel Torroja <miguel.torroja@gmail.com>
---
 builtin/fast-export.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/builtin/fast-export.c b/builtin/fast-export.c
index a3ab7da..4d39324 100644
--- a/builtin/fast-export.c
+++ b/builtin/fast-export.c
@@ -280,7 +280,7 @@ static int diff_type_cmp(const void *a_, const void *b_)
 	 * appear in the output before it is renamed (e.g., when a file
 	 * was copied and renamed in the same commit).
 	 */
-	return (a->status == 'R') - (b->status == 'R');
+	return (a->status == DIFF_STATUS_RENAMED) - (b->status == DIFF_STATUS_RENAMED);
 }
 
 static void print_path_1(const char *path)
-- 
2.1.4

Re: [PATCH 1/2] fast-export: deletion action first

[Jeff King]

On Tue, Apr 25, 2017 at 02:12:16AM +0200, Miguel Torroja wrote:

> The delete operations of the fast-export output should precede any addition
> belonging to the same commit, Addition and deletion with the same name
> entry could happen in case of file to directory and viceversa.
> 
> The fast-export sorting was added in 060df62 (fast-export: Fix output
> order of D/F changes). That change was made in order to fix the case of
> directory to file in the same commit, but it broke the reverse case
> (File to directory).

That explanation makes sense.

>  builtin/fast-export.c | 25 +++++++++----------------
>  1 file changed, 9 insertions(+), 16 deletions(-)

Perhaps we would want a test for the case you are fixing (to be sure it
is not re-broken), as well as confirming that we have not re-broken the
original case (it looks like 060df62 added a test, so we may be OK with
that).

> +/*
> + * Compares two diff types to order based on output priorities.
> + */
> +static int diff_type_cmp(const void *a_, const void *b_)
> [...]
> +	/*
> +	 * Move Delete entries first so that an addition is always reported after
> +	 */
> +	cmp = (b->status == DIFF_STATUS_DELETED) - (a->status == DIFF_STATUS_DELETED);
>  	if (cmp)
>  		return cmp;
>  	/*

So we sort deletions first. And the bit that the context doesn't quite
show here is that we then compare renames and push them to the end.
Everything else will compare equal.

Is qsort() guaranteed to be stable? If not, then we'll get the majority
of entries in a non-deterministic order. Should we fallback to strcmp()
so that within a given class, the entries are sorted by name?

-Peff

Re: [PATCH 1/2] fast-export: deletion action first

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> Perhaps we would want a test for the case you are fixing (to be sure it
> is not re-broken), as well as confirming that we have not re-broken the
> original case (it looks like 060df62 added a test, so we may be OK with
> that).

Good suggestion.

>
>> +/*
>> + * Compares two diff types to order based on output priorities.
>> + */
>> +static int diff_type_cmp(const void *a_, const void *b_)
>> [...]
>> +	/*
>> +	 * Move Delete entries first so that an addition is always reported after
>> +	 */
>> +	cmp = (b->status == DIFF_STATUS_DELETED) - (a->status == DIFF_STATUS_DELETED);
>>  	if (cmp)
>>  		return cmp;
>>  	/*
>
> So we sort deletions first. And the bit that the context doesn't quite
> show here is that we then compare renames and push them to the end.
> Everything else will compare equal.

Wait--we also allow renames?  Rename is like delete in the context
of discussing d/f conflicts, in that it tells us that the source
path will be missing in the end result.  If you rename a file "d" to
"e", then there is a room for you to create a directory "d" to store
a file "d/f" in.  Shouldn't it participate also in this "delete
before add to avoid d/f conflict" logic?

> Is qsort() guaranteed to be stable? If not, then we'll get the majority
> of entries in a non-deterministic order. Should we fallback to strcmp()
> so that within a given class, the entries are sorted by name?

Again, very good point, especially with the existing comment in the
comparison function that explains why renames are shown last.

Re: [PATCH 1/2] fast-export: deletion action first

[Jeff King]

On Mon, Apr 24, 2017 at 09:24:59PM -0700, Junio C Hamano wrote:

> > So we sort deletions first. And the bit that the context doesn't quite
> > show here is that we then compare renames and push them to the end.
> > Everything else will compare equal.
> 
> Wait--we also allow renames?  Rename is like delete in the context
> of discussing d/f conflicts, in that it tells us that the source
> path will be missing in the end result.  If you rename a file "d" to
> "e", then there is a room for you to create a directory "d" to store
> a file "d/f" in.  Shouldn't it participate also in this "delete
> before add to avoid d/f conflict" logic?

Hrm. Yeah, I agree that case is problematic. But putting the renames
early creates the opposite problem. If you delete "d/f" to make way for
a rename to a file "d", then that deletion has to come first.

So naively you might think that pure deletions come first, then renames.
But I think you could have dependencies within the renames. For
instance:

  git init
  mkdir a b c
  seq 1 1000 >a/f
  seq 1001 2000 >b/f
  seq 2001 3000 >c/f
  git add .
  git commit -m base

  git mv a tmp
  git mv b/f a; rmdir b
  git mv c/f b; rmdir c
  git mv tmp/f c; rmdir tmp

There's no correct order there; it's a cycle.

So I suspect that any reader that accepts renames needs to be able to
handle the inputs in any order (I'd also suspect that many
implementations _don't_, but get by because people don't do silly things
like this in practice).

Anyway. I don't think Miguel's patch needs to solve all of the lingering
rename cases. But I am curious whether it makes some rename cases worse,
because the depth-sorting was kicking in before and making them work.

-Peff

Re: [PATCH 1/2] fast-export: deletion action first

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> Anyway. I don't think Miguel's patch needs to solve all of the lingering
> rename cases. But I am curious whether it makes some rename cases worse,
> because the depth-sorting was kicking in before and making them work.

I agree with you on both counts, and I care more about the second
sentence, not just "am curious", but "am worried".  I am not sure
that this patch is safe---it looked more like robbing peter to pay
paul or the other way around.  Fixing for one class of breakage
without regressing is one thing and it is perfectly fine to leave
some already broken case broken with such a fix.  Claiming to fix
one class and breaking other class that was happily working is quite
different, and that is where my "Wait, we also allow renames?" comes
from.

Re: [PATCH 1/2] fast-export: deletion action first

[Jeff King]

On Mon, Apr 24, 2017 at 10:33:11PM -0700, Junio C Hamano wrote:

> Jeff King <peff@peff.net> writes:
> 
> > Anyway. I don't think Miguel's patch needs to solve all of the lingering
> > rename cases. But I am curious whether it makes some rename cases worse,
> > because the depth-sorting was kicking in before and making them work.
> 
> I agree with you on both counts, and I care more about the second
> sentence, not just "am curious", but "am worried".  I am not sure
> that this patch is safe---it looked more like robbing peter to pay
> paul or the other way around.  Fixing for one class of breakage
> without regressing is one thing and it is perfectly fine to leave
> some already broken case broken with such a fix.  Claiming to fix
> one class and breaking other class that was happily working is quite
> different, and that is where my "Wait, we also allow renames?" comes
> from.

Yeah, I don't disagree. I am just curious first, then worried second. :)

If I had to choose, though, I'd rather see the order be reliable for the
no-renames case. IOW, if we must rob one peter, I'd rather it be the
renames, which already have tons of corner cases (and which I do not
think can be plugged for a reader which depends on the order of the
entries; the dependencies can be cycles).

Of course if we can make it work correctly in all of the non-cyclical
cases, all the better.

-Peff

[PATCH] fast-export: deletion action first

[Miguel Torroja]

The delete operations of the fast-export output should precede any addition
belonging to the same commit, Addition and deletion with the same name
entry could happen in case of file to directory and viceversa.

As an equal comparison doesn't have any deterministic final order,
it's better to keep original diff order input when there is no prefer order
( that's done comparing pointers)

The fast-export sorting was added in 060df62 (fast-export: Fix output
order of D/F changes). That change was made in order to fix the case of
directory to file in the same commit, but it broke the reverse case
(File to directory).

The test "file becomes directory" has been added in order to exercise
the original motivation of the deletion reorder.

Signed-off-by: Miguel Torroja <miguel.torroja@gmail.com>
---
 builtin/fast-export.c  | 32 +++++++++++++++-----------------
 t/t9350-fast-export.sh | 25 +++++++++++++++++++++++++
 2 files changed, 40 insertions(+), 17 deletions(-)

diff --git a/builtin/fast-export.c b/builtin/fast-export.c
index e022063..e82f654 100644
--- a/builtin/fast-export.c
+++ b/builtin/fast-export.c
@@ -260,26 +260,19 @@ static void export_blob(const struct object_id *oid)
 		free(buf);
 }
 
-static int depth_first(const void *a_, const void *b_)
+/*
+ * Compares two diff types to order based on output priorities.
+ */
+static int diff_type_cmp(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;
-	cmp = len_b - len_a;
+	/*
+	 * Move Delete entries first so that an addition is always reported after
+	 */
+	cmp = (b->status == DIFF_STATUS_DELETED) - (a->status == DIFF_STATUS_DELETED);
 	if (cmp)
 		return cmp;
 	/*
@@ -287,7 +280,12 @@ static int depth_first(const void *a_, const void *b_)
 	 * appear in the output before it is renamed (e.g., when a file
 	 * was copied and renamed in the same commit).
 	 */
-	return (a->status == 'R') - (b->status == 'R');
+	cmp = (a->status == DIFF_STATUS_RENAMED) - (b->status == DIFF_STATUS_RENAMED);
+	if (cmp)
+		return cmp;
+
+	/* For the remaining cases we keep the original ordering comparing the pointers */
+	return (a-b);
 }
 
 static void print_path_1(const char *path)
@@ -347,7 +345,7 @@ static void show_filemodify(struct diff_queue_struct *q,
 	 * 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, depth_first);
+	QSORT(q->queue, q->nr, diff_type_cmp);
 
 	for (i = 0; i < q->nr; i++) {
 		struct diff_filespec *ospec = q->queue[i]->one;
diff --git a/t/t9350-fast-export.sh b/t/t9350-fast-export.sh
index b5149fd..d4f369a 100755
--- a/t/t9350-fast-export.sh
+++ b/t/t9350-fast-export.sh
@@ -419,6 +419,31 @@ test_expect_success 'directory becomes symlink'        '
 	(cd result && git show master:foo)
 '
 
+test_expect_success 'file becomes directory'  '
+	git init filetodir_orig &&
+	git init --bare filetodir_replica.git &&
+	(
+		cd filetodir_orig &&
+		echo foo > filethendir &&
+		git add filethendir &&
+		test_tick &&
+		git commit -mfile &&
+		git rm filethendir &&
+		mkdir filethendir &&
+		echo bar > filethendir/a &&
+		git add filethendir/a &&
+		test_tick &&
+		git commit -mdir
+	) &&
+	git --git-dir=filetodir_orig/.git fast-export master  |
+		git --git-dir=filetodir_replica.git/ fast-import &&
+	(
+		ORIG=$(git --git-dir=filetodir_orig/.git rev-parse --verify master) &&
+		REPLICA=$(git --git-dir=filetodir_replica.git rev-parse --verify master) &&
+		test $ORIG = $REPLICA
+	)
+'
+
 test_expect_success 'fast-export quotes pathnames' '
 	git init crazy-paths &&
 	(cd crazy-paths &&
-- 
2.1.4

Re: [PATCH] fast-export: deletion action first

[miguel torroja]

The previous patch reorders the delete operations in fast-export
(preceding any other one), keeps renaming as last operations to
process (as original source code) and for any other operation it keeps
the same order as "diff"

The non deterministic reordering was one of the concerns when I first
sent the patch.
The behavior for the other corner cases pointed out by Jeff
(delete/rename dir/file ) are not tackled in this patch and the final
result is unknown.


On Thu, May 4, 2017 at 9:36 PM, Miguel Torroja <miguel.torroja@gmail.com> wrote:
>
> The delete operations of the fast-export output should precede any addition
> belonging to the same commit, Addition and deletion with the same name
> entry could happen in case of file to directory and viceversa.
>
> As an equal comparison doesn't have any deterministic final order,
> it's better to keep original diff order input when there is no prefer order
> ( that's done comparing pointers)
>
> The fast-export sorting was added in 060df62 (fast-export: Fix output
> order of D/F changes). That change was made in order to fix the case of
> directory to file in the same commit, but it broke the reverse case
> (File to directory).
>
> The test "file becomes directory" has been added in order to exercise
> the original motivation of the deletion reorder.
>
> Signed-off-by: Miguel Torroja <miguel.torroja@gmail.com>
> ---
>  builtin/fast-export.c  | 32 +++++++++++++++-----------------
>  t/t9350-fast-export.sh | 25 +++++++++++++++++++++++++
>  2 files changed, 40 insertions(+), 17 deletions(-)
>
> diff --git a/builtin/fast-export.c b/builtin/fast-export.c
> index e022063..e82f654 100644
> --- a/builtin/fast-export.c
> +++ b/builtin/fast-export.c
> @@ -260,26 +260,19 @@ static void export_blob(const struct object_id *oid)
>                 free(buf);
>  }
>
> -static int depth_first(const void *a_, const void *b_)
> +/*
> + * Compares two diff types to order based on output priorities.
> + */
> +static int diff_type_cmp(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;
> -       cmp = len_b - len_a;
> +       /*
> +        * Move Delete entries first so that an addition is always reported after
> +        */
> +       cmp = (b->status == DIFF_STATUS_DELETED) - (a->status == DIFF_STATUS_DELETED);
>         if (cmp)
>                 return cmp;
>         /*
> @@ -287,7 +280,12 @@ static int depth_first(const void *a_, const void *b_)
>          * appear in the output before it is renamed (e.g., when a file
>          * was copied and renamed in the same commit).
>          */
> -       return (a->status == 'R') - (b->status == 'R');
> +       cmp = (a->status == DIFF_STATUS_RENAMED) - (b->status == DIFF_STATUS_RENAMED);
> +       if (cmp)
> +               return cmp;
> +
> +       /* For the remaining cases we keep the original ordering comparing the pointers */
> +       return (a-b);
>  }
>
>  static void print_path_1(const char *path)
> @@ -347,7 +345,7 @@ static void show_filemodify(struct diff_queue_struct *q,
>          * 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, depth_first);
> +       QSORT(q->queue, q->nr, diff_type_cmp);
>
>         for (i = 0; i < q->nr; i++) {
>                 struct diff_filespec *ospec = q->queue[i]->one;
> diff --git a/t/t9350-fast-export.sh b/t/t9350-fast-export.sh
> index b5149fd..d4f369a 100755
> --- a/t/t9350-fast-export.sh
> +++ b/t/t9350-fast-export.sh
> @@ -419,6 +419,31 @@ test_expect_success 'directory becomes symlink'        '
>         (cd result && git show master:foo)
>  '
>
> +test_expect_success 'file becomes directory'  '
> +       git init filetodir_orig &&
> +       git init --bare filetodir_replica.git &&
> +       (
> +               cd filetodir_orig &&
> +               echo foo > filethendir &&
> +               git add filethendir &&
> +               test_tick &&
> +               git commit -mfile &&
> +               git rm filethendir &&
> +               mkdir filethendir &&
> +               echo bar > filethendir/a &&
> +               git add filethendir/a &&
> +               test_tick &&
> +               git commit -mdir
> +       ) &&
> +       git --git-dir=filetodir_orig/.git fast-export master  |
> +               git --git-dir=filetodir_replica.git/ fast-import &&
> +       (
> +               ORIG=$(git --git-dir=filetodir_orig/.git rev-parse --verify master) &&
> +               REPLICA=$(git --git-dir=filetodir_replica.git rev-parse --verify master) &&
> +               test $ORIG = $REPLICA
> +       )
> +'
> +
>  test_expect_success 'fast-export quotes pathnames' '
>         git init crazy-paths &&
>         (cd crazy-paths &&
> --
> 2.1.4
>

[PATCH 1/2] fast-export: deletion action first

[Miguel Torroja]

The delete operations of the fast-export output should precede any addition
belonging to the same commit, Addition and deletion with the same name
entry could happen in case of file to directory and viceversa.

The fast-export sorting was added in 060df62 (fast-export: Fix output
order of D/F changes). That change was made in order to fix the case of
directory to file in the same commit, but it broke the reverse case
(File to directory).

Signed-off-by: Miguel Torroja <miguel.torroja@gmail.com>
---
 builtin/fast-export.c | 25 +++++++++----------------
 1 file changed, 9 insertions(+), 16 deletions(-)

diff --git a/builtin/fast-export.c b/builtin/fast-export.c
index e022063..a3ab7da 100644
--- a/builtin/fast-export.c
+++ b/builtin/fast-export.c
@@ -260,26 +260,19 @@ static void export_blob(const struct object_id *oid)
 		free(buf);
 }
 
-static int depth_first(const void *a_, const void *b_)
+/*
+ * Compares two diff types to order based on output priorities.
+ */
+static int diff_type_cmp(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;
-	cmp = len_b - len_a;
+	/*
+	 * Move Delete entries first so that an addition is always reported after
+	 */
+	cmp = (b->status == DIFF_STATUS_DELETED) - (a->status == DIFF_STATUS_DELETED);
 	if (cmp)
 		return cmp;
 	/*
@@ -347,7 +340,7 @@ static void show_filemodify(struct diff_queue_struct *q,
 	 * 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, depth_first);
+	QSORT(q->queue, q->nr, diff_type_cmp);
 
 	for (i = 0; i < q->nr; i++) {
 		struct diff_filespec *ospec = q->queue[i]->one;
-- 
2.1.4

[PATCH 1/2] fast-export: deletion action first

[Miguel Torroja]

The delete operations of the fast-export output should precede any addition
belonging to the same commit, Addition and deletion with the same name
entry could happen in case of file to directory and viceversa.

The fast-export sorting was added in 060df62 (fast-export: Fix output
order of D/F changes). That change was made in order to fix the case of
directory to file in the same commit, but it broke the reverse case
(File to directory).

Signed-off-by: Miguel Torroja <miguel.torroja@gmail.com>
---
 builtin/fast-export.c | 25 +++++++++----------------
 1 file changed, 9 insertions(+), 16 deletions(-)

diff --git a/builtin/fast-export.c b/builtin/fast-export.c
index e022063..a3ab7da 100644
--- a/builtin/fast-export.c
+++ b/builtin/fast-export.c
@@ -260,26 +260,19 @@ static void export_blob(const struct object_id *oid)
 		free(buf);
 }
 
-static int depth_first(const void *a_, const void *b_)
+/*
+ * Compares two diff types to order based on output priorities.
+ */
+static int diff_type_cmp(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;
-	cmp = len_b - len_a;
+	/*
+	 * Move Delete entries first so that an addition is always reported after
+	 */
+	cmp = (b->status == DIFF_STATUS_DELETED) - (a->status == DIFF_STATUS_DELETED);
 	if (cmp)
 		return cmp;
 	/*
@@ -347,7 +340,7 @@ static void show_filemodify(struct diff_queue_struct *q,
 	 * 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, depth_first);
+	QSORT(q->queue, q->nr, diff_type_cmp);
 
 	for (i = 0; i < q->nr; i++) {
 		struct diff_filespec *ospec = q->queue[i]->one;
-- 
2.1.4