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

This series depends on a merge of en/merge-ort-3 and en/merge-ort-recursive. It does not depend on the (not-yet-picked-up) ort-conflict-handling series[1].

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 the ort-conflict-handling series[1], 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 packed 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.

[1] https://lore.kernel.org/git/pull.815.v2.git.1609468488.gitgitgadget@gmail.com/

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(-)