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

Message

John Passaro via GitGitGadget Jan. 7, 2021, 8:01 p.m. UTC

[This is a resend of
https://lore.kernel.org/git/[e-mail]/ from
Monday without any changes; I wanted to move it to gitgitgadget for testing
and such after I remembered I had perms to create temporary branches for the
pull request base.]

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 (18):
  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
  DO NOT SUBMIT: directory rename stuff for redo_after_renames

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


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