[This is a resend of https://lore.kernel.org/git/20210104235006.2867404-1-newren@xxxxxxxxx/ 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 -- gitgitgadget
