[PATCH v2 00/17] Add directory rename detection to merge-ort

[Sorry for the deluge of email. Only change since v1 is dropping the "DO NOT SUBMIT" patch at the end that was meant to be part of later optimization work. Now this series actually matches what I sent on Monday at https://lore.kernel.org/git/20210104235006.2867404-1-newren@gmail.com/, as I meant to do with v1.]

This series depends on a merge of en/merge-ort-3 and en/merge-ort-recursive. It does not depend on the en/ort-conflict-handling.

This series mostly implements directory rename detection for merge-ort; I'll cover the "mostly" bit below. If one merges this series with en/merge-tests and en/ort-conflict-handling, then this series drops the number of failing tests in the testsuite under GIT_TEST_MERGE_ALGORITHM=ort from 60 down to 8.

There's a lot of code here, but almost all of the logic is just copied over from similarly named functions in merge-recursive.c, as repeatedly noted in the commit messages. There are several minor differences spread throughout that make it not be a direct copy:

 * using strmap API instead of direct hashmap calls
 * ort keeps track of all files and directories and their shas in
   opt->priv->paths; no need to re-walk tree objects
 * keeping the necessary invariants for opt->priv->paths
 * we can pre-compute which directories are removed (stored in
   dirs_removed), avoiding the need for some post-processing
 * since ort already has struct rename_info, add the extra data there and
   allocate/free it with the rest of the rename_info
 * no non_unique_new_dir field, leading to the failure of test 2b; this will
   be addressed in a different way with upcoming performance work.

These differences make a direct comparison difficult, but there's not really any new or novel logic; the logic for how directory rename detection is performed is identical to what is found in merge-recursive; it's just packaged slightly differently.

...with one exception -- the final patch in the series modifies the logic and makes it different than merge-recursive in order to fix a known bug (testcase 12f of t6423).

There are still four failing tests in t6423 (directory rename tests) after this series:

 * one test (2b) where merge-ort erroneously prints a "directory rename
   split" conflict message, despite the fact that there is no new file and
   thus no need for a directory rename to be detected. This comes from the
   lack of a non_unique_new_dir field that I didn't bother copying, since
   performance work will address it in a completely different way.

 * two tests (12b1 and 12c1) where merge-ort produces the same result at
   merge-recursive (these tests are marked as test_expect_failure for
   merge-recursive). Some performance work will fix these two tests.

 * one test (12f) where merge-ort produces a better result than
   merge-recursive.c (this test is marked as test_expect_failure for
   merge-recursive), but where merge-ort does not yet manage to pass the
   final four lines of the test related to performance checking.

Elijah Newren (17):
  merge-ort: add new data structures for directory rename detection
  merge-ort: initialize and free new directory rename data structures
  merge-ort: collect which directories are removed in dirs_removed
  merge-ort: add outline for computing directory renames
  merge-ort: add outline of get_provisional_directory_renames()
  merge-ort: copy get_renamed_dir_portion() from merge-recursive.c
  merge-ort: implement compute_rename_counts()
  merge-ort: implement handle_directory_level_conflicts()
  merge-ort: modify collect_renames() for directory rename handling
  merge-ort: implement compute_collisions()
  merge-ort: implement apply_dir_rename() and check_dir_renamed()
  merge-ort: implement check_for_directory_rename()
  merge-ort: implement handle_path_level_conflicts()
  merge-ort: add a new toplevel_dir field
  merge-ort: implement apply_directory_rename_modifications()
  merge-ort: process_renames() now needs more defensiveness
  merge-ort: fix a directory rename detection bug

 merge-ort.c | 831 ++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 812 insertions(+), 19 deletions(-)

base-commit: 9c85b62e817e83401855e4f2e11283be8386739e
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-835%2Fnewren%2Fort-directory-renames-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-835/newren/ort-directory-renames-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/835

Range-diff vs v1:

  1:  41a99640cc5 =  1:  41a99640cc5 merge-ort: add new data structures for directory rename detection
  2:  762151802be =  2:  762151802be merge-ort: initialize and free new directory rename data structures
  3:  bb4b6d20480 =  3:  bb4b6d20480 merge-ort: collect which directories are removed in dirs_removed
  4:  ccb30dfc3c4 =  4:  ccb30dfc3c4 merge-ort: add outline for computing directory renames
  5:  bb4285250cd =  5:  bb4285250cd merge-ort: add outline of get_provisional_directory_renames()
  6:  4e79a96ba1c =  6:  4e79a96ba1c merge-ort: copy get_renamed_dir_portion() from merge-recursive.c
  7:  1e48cde01b9 =  7:  1e48cde01b9 merge-ort: implement compute_rename_counts()
  8:  f6efa4350d6 =  8:  f6efa4350d6 merge-ort: implement handle_directory_level_conflicts()
  9:  bdd9d6cd702 =  9:  bdd9d6cd702 merge-ort: modify collect_renames() for directory rename handling
 10:  9a06c698857 = 10:  9a06c698857 merge-ort: implement compute_collisions()
 11:  2ffb93c37ac = 11:  2ffb93c37ac merge-ort: implement apply_dir_rename() and check_dir_renamed()
 12:  cbfdf4d9ba0 = 12:  cbfdf4d9ba0 merge-ort: implement check_for_directory_rename()
 13:  734891cb315 = 13:  734891cb315 merge-ort: implement handle_path_level_conflicts()
 14:  4b912f2c025 = 14:  4b912f2c025 merge-ort: add a new toplevel_dir field
 15:  d74417e86c5 = 15:  d74417e86c5 merge-ort: implement apply_directory_rename_modifications()
 16:  11e45af831d = 16:  11e45af831d merge-ort: process_renames() now needs more defensiveness
 17:  551878bd84d = 17:  551878bd84d merge-ort: fix a directory rename detection bug
 18:  786dc8f0c44 <  -:  ----------- DO NOT SUBMIT: directory rename stuff for redo_after_renames