Significant rename detection rewrite

This flips rename detection around so instead of creating a
forward mapping from deltas to possible rename targets, instead
it creates a reverse mapping, looking at possible targets and
trying to find a source that they could have been renamed or
copied from.  This is important because each output can only
have a single source, but a given source could map to multiple
outputs (in the form of COPIED records).

Additionally, this makes a couple of tweaks to the public rename
detection APIs, mostly renaming a couple of options that control
the behavior to make more sense and to be more like core Git.

I walked through the tests looking at the exact results and
updated the expectations based on what I saw.  The new code is
different from the old because it cannot give some nonsense
results (like A was renamed to both B and C) which were part of
the outputs previously.

1 files changed, 28 insertions, 6 deletions

diff --git a/tests-clar/diff/rename.c b/tests-clar/diff/rename.c
index a78e33939..b4f9df713 100644
--- a/tests-clar/diff/rename.c
+++ b/tests-clar/diff/rename.c
@@ -15,6 +15,18 @@ void test_diff_rename__cleanup(void)
 }
 
 /*
+static int debug_print(
+    const git_diff_delta *delta, const git_diff_range *range, char usage,
+    const char *line, size_t line_len, void *data)
+{
+    GIT_UNUSED(delta); GIT_UNUSED(range); GIT_UNUSED(usage);
+    GIT_UNUSED(line_len); GIT_UNUSED(data);
+    fputs(line, stderr);
+    return 0;
+}
+*/
+
+/*
  * Renames repo has:
  *
  * commit 31e47d8c1fa36d7f8d537b96158e3f024de0a9f2 -
@@ -72,8 +84,10 @@ void test_diff_rename__match_oid(void)
 
 	/* git diff 31e47d8c1fa36d7f8d537b96158e3f024de0a9f2 \
 	 *          2bc7f351d20b53f1c72c16c4b036e491c478c49a
+	 * don't use NULL opts to avoid config `diff.renames` contamination
 	 */
-	cl_git_pass(git_diff_find_similar(diff, NULL));
+	opts.flags = GIT_DIFF_FIND_RENAMES;
+	cl_git_pass(git_diff_find_similar(diff, &opts));
 
 	memset(&exp, 0, sizeof(exp));
 	cl_git_pass(git_diff_foreach(
@@ -243,8 +257,8 @@ void test_diff_rename__not_exact_match(void)
 	cl_assert_equal_i(5, exp.files);
 	cl_assert_equal_i(1, exp.file_status[GIT_DELTA_UNMODIFIED]);
 	cl_assert_equal_i(1, exp.file_status[GIT_DELTA_MODIFIED]);
-	cl_assert_equal_i(1, exp.file_status[GIT_DELTA_DELETED]);
 	cl_assert_equal_i(1, exp.file_status[GIT_DELTA_ADDED]);
+	cl_assert_equal_i(1, exp.file_status[GIT_DELTA_DELETED]);
 	cl_assert_equal_i(1, exp.file_status[GIT_DELTA_COPIED]);
 
 	git_diff_list_free(diff);
@@ -429,8 +443,8 @@ void test_diff_rename__working_directory_changes(void)
 
 	cl_assert_equal_i(6, exp.files);
 	cl_assert_equal_i(1, exp.file_status[GIT_DELTA_MODIFIED]);
-	cl_assert_equal_i(3, exp.file_status[GIT_DELTA_UNTRACKED]);
 	cl_assert_equal_i(2, exp.file_status[GIT_DELTA_DELETED]);
+	cl_assert_equal_i(3, exp.file_status[GIT_DELTA_UNTRACKED]);
 
 	/* git diff -M 2bc7f351d20b53f1c72c16c4b036e491c478c49a */
 	opts.flags = GIT_DIFF_FIND_ALL;
@@ -441,7 +455,8 @@ void test_diff_rename__working_directory_changes(void)
 		diff, diff_file_cb, diff_hunk_cb, diff_line_cb, &exp));
 
 	cl_assert_equal_i(5, exp.files);
-	cl_assert_equal_i(3, exp.file_status[GIT_DELTA_RENAMED]);
+	cl_assert_equal_i(2, exp.file_status[GIT_DELTA_RENAMED]);
+	cl_assert_equal_i(1, exp.file_status[GIT_DELTA_DELETED]);
 	cl_assert_equal_i(2, exp.file_status[GIT_DELTA_UNTRACKED]);
 
 	git_diff_list_free(diff);
@@ -466,7 +481,8 @@ void test_diff_rename__working_directory_changes(void)
 		diff, diff_file_cb, diff_hunk_cb, diff_line_cb, &exp));
 
 	cl_assert_equal_i(5, exp.files);
-	cl_assert_equal_i(3, exp.file_status[GIT_DELTA_RENAMED]);
+	cl_assert_equal_i(2, exp.file_status[GIT_DELTA_RENAMED]);
+	cl_assert_equal_i(1, exp.file_status[GIT_DELTA_DELETED]);
 	cl_assert_equal_i(2, exp.file_status[GIT_DELTA_UNTRACKED]);
 
 	git_diff_list_free(diff);
@@ -521,13 +537,19 @@ void test_diff_rename__working_directory_changes(void)
 	opts.flags = GIT_DIFF_FIND_ALL | GIT_DIFF_FIND_EXACT_MATCH_ONLY;
 	cl_git_pass(git_diff_find_similar(diff, &opts));
 
+	/*
+	fprintf(stderr, "\n\n");
+    cl_git_pass(git_diff_print_raw(diff, debug_print, NULL));
+	*/
+
 	memset(&exp, 0, sizeof(exp));
 	cl_git_pass(git_diff_foreach(
 		diff, diff_file_cb, diff_hunk_cb, diff_line_cb, &exp));
 
 	cl_assert_equal_i(5, exp.files);
 	cl_assert_equal_i(1, exp.file_status[GIT_DELTA_MODIFIED]);
-	cl_assert_equal_i(2, exp.file_status[GIT_DELTA_RENAMED]);
+	cl_assert_equal_i(1, exp.file_status[GIT_DELTA_DELETED]);
+	cl_assert_equal_i(1, exp.file_status[GIT_DELTA_RENAMED]);
 	cl_assert_equal_i(2, exp.file_status[GIT_DELTA_UNTRACKED]);
 
 	git_diff_list_free(diff);