WIP: diff-b-m

Starting from two significantly different files, file0 and file1, if
you edit file1 to make it very similar to the original file0 and
remove file0, i.e.

	$ cat file0 >file1
	$ edit file1 ;# a little
	$ rm file0
	$ git commit -m 'retire file0, update file1'
	$ git show -B -M

the output would become concise if resulting file1 is expressed in
terms of the original file0 (i.e. copy or rename).  The current code
expresses it as "rename file0 to create file1".

This however is problematic for two reasons:

 - "rename file0 to create file1" implies that file1 should not
   exist in the target tree for such a diff to apply, but the very
   old tree this diff was taken from does have file1, so the patch
   does not even apply to the old tree to recreate the new tree.

 - Applying such a diff in reverse to the new tree ought to produce
   the old tree, but because "rename file0 to create file1" does not
   say how the original file1 in the old tree used to look like and
   there is no way to recover that information. In fact, the reverse
   of "rename file0 to create file1" is "rename file1 to create
   file0", so such a diff will apply without an error in reverse,
   but the end result will lose file1 completely, which is worse.

 - Such a diff is very inconsistent with its reverse.  Starting from
   a single file file1, if you copy it to file0 and made a small
   edit, and completely rewrite file1, that would be the reverse of
   the above scenario.  Such a change is described by the current
   code as two changes, "copy file1 to create file0" and "rewrite
   file1".  The reverse of these two at least ought to say "delete
   file0", regardless of how changes to file1 is expressed.

The updated expected results for tests in t4008 reflects the above
thinking.

This update is still broken and breaks a few tests:

    4008 4023

2 files changed, 41 insertions, 45 deletions

diff --git a/diffcore-rename.c b/diffcore-rename.c
index f1f6d6f1be..f3dc434db1 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -648,15 +648,22 @@ void diffcore_rename(struct diff_options *options)
 	 */
 	diff_debug_queue("begin turning a/d into renames", q);
 
+	/*
+	 * Unlike the usual "queue in outq while freeing unneeded
+	 * elements and then swap outq into *q", we just leave the
+	 * entries to be later freed in *q in this loop and then
+	 * clean up after we are done.  This is because we want to
+	 * peek into rename_src, which has pointers into the filepairs
+	 * still in *q.
+	 */
 	DIFF_QUEUE_CLEAR(&outq);
 	for (i = 0; i < q->nr; i++) {
 		struct diff_filepair *p = q->queue[i];
-		struct diff_filepair *pair_to_free = NULL;
 
 		if (DIFF_PAIR_UNMERGED(p)) {
 			diff_q(&outq, p);
-		}
-		else if (!DIFF_FILE_VALID(p->one) && DIFF_FILE_VALID(p->two)) {
+			q->queue[i] = NULL;
+		} else if (!DIFF_FILE_VALID(p->one) && DIFF_FILE_VALID(p->two)) {
 			/*
 			 * Creation
 			 *
@@ -668,59 +675,38 @@ void diffcore_rename(struct diff_options *options)
 				locate_rename_dst(p->two, 0);
 			if (dst && dst->pair) {
 				diff_q(&outq, dst->pair);
-				pair_to_free = p;
-			}
-			else
+			} else {
 				/* no matching rename/copy source, so
 				 * record this as a creation.
 				 */
 				diff_q(&outq, p);
-		}
-		else if (DIFF_FILE_VALID(p->one) && !DIFF_FILE_VALID(p->two)) {
+				q->queue[i] = NULL;
+			}
+		} else if (DIFF_FILE_VALID(p->one) && !DIFF_FILE_VALID(p->two)) {
 			/*
 			 * Deletion
 			 *
-			 * We would output this delete record if:
-			 *
-			 * (1) this is a broken delete and the counterpart
-			 *     broken create remains in the output; or
-			 * (2) this is not a broken delete, and rename_dst
-			 *     does not have a rename/copy to move p->one->path
-			 *     out of existence.
-			 *
-			 * Otherwise, the counterpart broken create
-			 * has been turned into a rename-edit; or
-			 * delete did not have a matching create to
-			 * begin with.
+			 * Did the content go to somewhere?
 			 */
-			if (DIFF_PAIR_BROKEN(p)) {
-				/* broken delete */
-				struct diff_rename_dst *dst =
-					locate_rename_dst(p->one, 0);
-				if (dst && dst->pair)
-					/* counterpart is now rename/copy */
-					pair_to_free = p;
-			}
-			else {
-				if (p->one->rename_used)
-					/* this path remains */
-					pair_to_free = p;
-			}
-
-			if (pair_to_free)
-				;
-			else
+			struct diff_rename_src *src =
+				locate_rename_src(p->one, 0);
+			if (!src || !src->p->one->rename_used) {
 				diff_q(&outq, p);
-		}
-		else if (!diff_unmodified_pair(p))
+				q->queue[i] = NULL;
+			}
+		} else if (!diff_unmodified_pair(p)) {
 			/* all the usual ones need to be kept */
 			diff_q(&outq, p);
-		else
+			q->queue[i] = NULL;
+		} else {
 			/* no need to keep unmodified pairs */
-			pair_to_free = p;
+			;
+		}
+	}
 
-		if (pair_to_free)
-			diff_free_filepair(pair_to_free);
+	for (i = 0; i < q->nr; i++) {
+		if (q->queue[i])
+			diff_free_filepair(q->queue[i]);
 	}
 
 	free(q->queue);
diff --git a/t/t4008-diff-break-rewrite.sh b/t/t4008-diff-break-rewrite.sh
index 9dd1bc5e16..8311cd6619 100755
--- a/t/t4008-diff-break-rewrite.sh
+++ b/t/t4008-diff-break-rewrite.sh
@@ -14,7 +14,15 @@ original file1 and creation of completely rewritten file1.  The latter
 two are then merged back into a single "complete rewrite".
 
 Further, with -B and -M together, these three modifications should
-turn into rename-edit of file0 into file1.
+turn into rename-edit of file0 into file1 and deletion of file1.
+Note that the latter deletion is essential for reasons.  Because
+file1 exists in the old tree and disappears from the new tree, we
+cannot just say "a rename creates file1 and its contents comes from
+file0", as such a patch requires that the target tree lacks file1.
+Also taking the same diff in the reverse should say that file0 is
+created by copying file1 and file1 is rewritten, which is more
+consistent with the reverse of "file1 is created by renaming file0
+and the original file1 is deleted".
 
 Starting from the same two files in the tree, we swap file0 and file1.
 With -B, this should be detected as two complete rewrites.
@@ -49,6 +57,7 @@ test_expect_success 'run diff with -B (#1)' '
 test_expect_success 'run diff with -B and -M (#2)' '
 	git diff-index -B -M reference >current &&
 	cat >expect <<-\EOF &&
+	:100644 000000 6ff87c4664981e4397625791c8ea3bbb5f2279a3 0000000000000000000000000000000000000000 D#	file1
 	:100644 100644 548142c327a6790ff8821d67c2ee1eff7a656b52 2fbedd0b5d4b8126e4750c3bee305e8ff79f80ec R100	file0	file1
 	EOF
 	compare_diff_raw expect current
@@ -97,7 +106,7 @@ test_expect_success 'run diff with -B (#5)' '
 	compare_diff_raw expect current
 '
 
-test_expect_success 'run diff with -B -M (#6)' '
+test_expect_failure 'run diff with -B -M (#6)' '
 	git diff-index -B -M reference >current &&
 
 	# file0 changed from regular to symlink.  file1 is the same as the preimage
@@ -145,6 +154,7 @@ test_expect_success 'run diff with -B (#8)' '
 test_expect_success 'run diff with -B -C (#9)' '
 	git diff-index -B -C reference >current &&
 	cat >expect <<-\EOF &&
+	:100644 000000 6ff87c4664981e4397625791c8ea3bbb5f2279a3 0000000000000000000000000000000000000000 D#	file1
 	:100644 100644 548142c327a6790ff8821d67c2ee1eff7a656b52 2fbedd0b5d4b8126e4750c3bee305e8ff79f80ec C095	file0	file1
 	:100644 100644 548142c327a6790ff8821d67c2ee1eff7a656b52 69a939f651686f56322566e2fd76715947a24162 R095	file0	file2
 	EOF