[PATCH v2 0/3] Fix dual rename into each other plus conflicting adds

This series adds some testcases based on the tensorflow repository issue reported by Glen Choo at [1], demonstrating bugs in both the ort and recursive strategies. It also provides a fix for the ort strategy.

Changes since v1:

 * Fixed some wording issues in comments, and added a bit more details to
   one of the commit messages

[1] https://lore.kernel.org/git/kl6lee006mle.fsf@chooglen-macbookpro.roam.corp.google.com/

Elijah Newren (3):
  t6423: add tests of dual directory rename plus add/add conflict
  merge-ort: shuffle the computation and cleanup of potential collisions
  merge-ort: fix issue with dual rename and add/add conflict

 merge-ort.c                         |  63 +++++++++++------
 t/t6423-merge-rename-directories.sh | 102 ++++++++++++++++++++++++++++
 2 files changed, 145 insertions(+), 20 deletions(-)

base-commit: e54793a95afeea1e10de1e5ad7eab914e7416250
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1268%2Fnewren%2Ffix-dual-rename-into-each-other-plus-conflicting-adds-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1268/newren/fix-dual-rename-into-each-other-plus-conflicting-adds-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/1268

Range-diff vs v1:

 1:  69d62041843 ! 1:  bf4c03d01d5 t6423: add tests of dual directory rename plus add/add conflict
     @@ t/t6423-merge-rename-directories.sh: test_expect_success '12k: Directory rename
       '
       
      +# Testcase 12l, Both sides rename a directory into the other side, both add
     -+#   a file with after directory renames are the same filename
     ++#   a file which after directory renames are the same filename
      +#   Commit O: sub1/file,                 sub2/other
      +#   Commit A: sub3/file,                 sub2/{other, new_add_add_file_1}
      +#   Commit B: sub1/{file, newfile}, sub1/sub2/{other, new_add_add_file_2}
     @@ t/t6423-merge-rename-directories.sh: test_expect_success '12k: Directory rename
      +#     B: sub2/ -> sub1/sub2, add sub1/newfile, add sub1/sub2/new_add_add_file_2
      +#
      +#   Expected: sub3/{file, newfile, sub2/other}
     -+#             CONFLICT (add/add): sub3/sub2/new_add_add_file
     ++#             CONFLICT (add/add): sub1/sub2/new_add_add_file
      +
      +test_setup_12l () {
      +	test_create_repo 12l_$1 &&
 2:  d8c13e56209 = 2:  cfa38f01481 merge-ort: shuffle the computation and cleanup of potential collisions
 3:  bb2badccb71 ! 3:  da3ae38e390 merge-ort: fix issue with dual rename and add/add conflict
     @@ Commit message
          with it.  So, let's just turn off directory rename detection in this
          case as well.
      
     +    Another way to look at this is that if the source name involved in a
     +    directory rename on one side is the target name of a directory rename
     +    operation for a file from the other side, then we avoid the doubly
     +    transitive rename.  (More concretely, if a directory rename on side D
     +    wants to rename a file on side E from OLD_NAME -> NEW_NAME, and side D
     +    already had a file named NEW_NAME, and a directory rename on side E
     +    wants to rename side D's NEW_NAME -> NEWER_NAME, then we turn off the
     +    directory rename detection for NEW_NAME to prevent the
     +    NEW_NAME -> NEWER_NAME rename, and instead end up with an add/add
     +    conflict on NEW_NAME.)
     +
          Signed-off-by: Elijah Newren <newren@gmail.com>
      
       ## merge-ort.c ##
     @@ merge-ort.c: static char *check_for_directory_rename(struct merge_options *opt,
       	const char *new_dir;
      +	int other_side = 3 - side_index;
       
     -+	/* Cases where there is no new path, so we return NULL */
     ++	/*
     ++	 * Cases where we don't have or don't want a directory rename for
     ++	 * this path, so we return NULL.
     ++	 */
       	if (strmap_empty(dir_renames))
       		return new_path;
      +	if (strmap_get(&collisions[other_side], path))