{"thread":{"id":"54929","subject":"[PATCH 08/17] merge-ort: implement handle_directory_level_conflicts()","startedAt":"2021-01-04T23:51:15Z","lastAt":"2021-01-04T23:51:51Z","messageCount":18,"participants":["Elijah Newren"],"isPatch":true,"patchVersion":1,"patchTotal":17},"messages":[{"id":"413392","messageId":"20210104235006.2867404-9-newren@gmail.com","threadId":"54929","inReplyTo":"20210104235006.2867404-1-newren@gmail.com","subject":"[PATCH 08/17] merge-ort: implement handle_directory_level_conflicts()","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-01-04T23:49:57Z","receivedAt":"2021-01-04T23:51:15Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This is modelled on the version of handle_directory_level_conflicts()\nfrom merge-recursive.c, but is massively simplified due to the following\nfactors:\n * strmap API provides simplifications over using direct hashamp\n * we have a dirs_removed field in struct rename_info that we have an\n easy way to populate from collect_merge_info(); this was already\n used in compute_rename_counts() and thus we do not need to check\n for condition #2.\n * The removal of condition #2 by handling it earlier in the code also\n obviates the need to check for condition #3 -- if both sides renamed\n a directory, meaning that the directory no longer exists on either\n side, then neither side could have added any new files to that\n directory, and thus there are no files whose locations we need to\n move due to such a directory rename.\n\nIn fact, the same logic that makes condition #3 irrelevant means\ncondition #1 is also irrelevant so we could drop this function.\nHowever, it is cheap to check if both sides rename the same directory,\nand doing so can save future computation. So, simply remove any\ndirectories that both sides renamed from the list of directory renames.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 18 +++++++++++++++++-\n 1 file changed, 17 insertions(+), 1 deletion(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 05bac9c5bd..c4f437d4c0 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -1359,7 +1359,23 @@ static void get_provisional_directory_renames(struct merge_options *opt,\n \n static void handle_directory_level_conflicts(struct merge_options *opt)\n {\n-\tdie(\"Not yet implemented!\");\n+\tstruct hashmap_iter iter;\n+\tstruct strmap_entry *entry;\n+\tstruct string_list duplicated = STRING_LIST_INIT_NODUP;\n+\tstruct strmap *side1_dir_renames = &opt->priv->renames.dir_renames[1];\n+\tstruct strmap *side2_dir_renames = &opt->priv->renames.dir_renames[2];\n+\tint i;\n+\n+\tstrmap_for_each_entry(side1_dir_renames, &iter, entry) {\n+\t\tif (strmap_contains(side2_dir_renames, entry->key))\n+\t\t\tstring_list_append(&duplicated, entry->key);\n+\t}\n+\n+\tfor (i=0; i\n---\n merge-ort.c | 35 +++++++++++++++++++++++++++++++++++\n 1 file changed, 35 insertions(+)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 719cc1c582..8b190b0ea5 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -311,8 +311,12 @@ static void free_strmap_strings(struct strmap *map)\n static void clear_or_reinit_internal_opts(struct merge_options_internal *opti,\n \t\t\t\t\t int reinitialize)\n {\n+\tstruct rename_info *renames = &opti->renames;\n+\tint i;\n \tvoid (*strmap_func)(struct strmap *, int) =\n \t\treinitialize ? strmap_partial_clear : strmap_clear;\n+\tvoid (*strset_func)(struct strset *) =\n+\t\treinitialize ? strset_partial_clear : strset_clear;\n \n \t/*\n \t * We marked opti->paths with strdup_strings = 0, so that we\n@@ -342,6 +346,23 @@ static void clear_or_reinit_internal_opts(struct merge_options_internal *opti,\n \tstring_list_clear(&opti->paths_to_free, 0);\n \topti->paths_to_free.strdup_strings = 0;\n \n+\t/* Free memory used by various renames maps */\n+\tfor (i = MERGE_SIDE1; i <= MERGE_SIDE2; ++i) {\n+\t\tstruct hashmap_iter iter;\n+\t\tstruct strmap_entry *entry;\n+\n+\t\tstrset_func(&renames->dirs_removed[i]);\n+\n+\t\tstrmap_for_each_entry(&renames->dir_rename_count[i],\n+\t\t\t\t &iter, entry) {\n+\t\t\tstruct strintmap *counts = entry->value;\n+\t\t\tstrintmap_clear(counts);\n+\t\t}\n+\t\tstrmap_func(&renames->dir_rename_count[i], 1);\n+\n+\t\tstrmap_func(&renames->dir_renames[i], 0);\n+\t}\n+\n \tif (!reinitialize) {\n \t\tstruct hashmap_iter iter;\n \t\tstruct strmap_entry *e;\n@@ -2447,6 +2468,9 @@ static struct commit *make_virtual_commit(struct repository *repo,\n \n static void merge_start(struct merge_options *opt, struct merge_result *result)\n {\n+\tstruct rename_info *renames;\n+\tint i;\n+\n \t/* Sanity checks on opt */\n \tassert(opt->repo);\n \n@@ -2481,6 +2505,17 @@ static void merge_start(struct merge_options *opt, struct merge_result *result)\n \t/* Initialization of opt->priv, our internal merge data */\n \topt->priv = xcalloc(1, sizeof(*opt->priv));\n \n+\t/* Initialization of various renames fields */\n+\trenames = &opt->priv->renames;\n+\tfor (i = MERGE_SIDE1; i <= MERGE_SIDE2; i++) {\n+\t\tstrset_init_with_options(&renames->dirs_removed[i],\n+\t\t\t\t\t NULL, 0);\n+\t\tstrmap_init_with_options(&renames->dir_rename_count[i],\n+\t\t\t\t\t NULL, 1);\n+\t\tstrmap_init_with_options(&renames->dir_renames[i],\n+\t\t\t\t\t NULL, 0);\n+\t}\n+\n \t/*\n \t * Although we initialize opt->priv->paths with strdup_strings=0,\n \t * that's just to avoid making yet another copy of an allocated\n-- \n2.29.1.106.g3ff750dc32.dirty\n\n"},{"id":"413394","messageId":"20210104235006.2867404-11-newren@gmail.com","threadId":"54929","inReplyTo":"20210104235006.2867404-1-newren@gmail.com","subject":"[PATCH 10/17] merge-ort: implement compute_collisions()","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-01-04T23:49:59Z","receivedAt":"2021-01-04T23:51:15Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This is nearly a wholesale copy of compute_collisions() from\nmerge-recursive.c, and the logic remains the same, but it has been\ntweaked slightly due to:\n\n * using strmap.h API (instead of direct hashmaps)\n * allocation/freeing of data structures were done separately in\n merge_start() and clear_or_reinit_internal_opts() in an earlier\n patch in this series\n * there is no non_unique_new_dir data field in merge-ort; that will\n be handled a different way\n\nIt does depend on two new functions, apply_dir_rename() and\ncheck_dir_renamed() which were introduced with simple\ndie-not-yet-implemented shells and will be implemented in subsequent\npatches.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 68 ++++++++++++++++++++++++++++++++++++++++++++++++++++-\n 1 file changed, 67 insertions(+), 1 deletion(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex a52905c4ee..9c9be645ea 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -1144,6 +1144,19 @@ struct collision_info {\n \tunsigned reported_already:1;\n };\n \n+/*\n+ * Return a new string that replaces the beginning portion (which matches\n+ * rename_info->key), with rename_info->util.new_dir. In perl-speak:\n+ * new_path_name = (old_path =~ s/rename_info->key/rename_info->value/);\n+ * NOTE:\n+ * Caller must ensure that old_path starts with rename_info->key + '/'.\n+ */\n+static char *apply_dir_rename(struct strmap_entry *rename_info,\n+\t\t\t const char *old_path)\n+{\n+\tdie(\"Not yet implemented!\");\n+}\n+\n static void get_renamed_dir_portion(const char *old_path, const char *new_path,\n \t\t\t\t char **old_dir, char **new_dir)\n {\n@@ -1383,11 +1396,64 @@ static void handle_directory_level_conflicts(struct merge_options *opt)\n \tstring_list_clear(&duplicated, 0);\n }\n \n+static struct strmap_entry *check_dir_renamed(const char *path,\n+\t\t\t\t\t struct strmap *dir_renames)\n+{\n+\tdie(\"Not yet implemented!\");\n+}\n+\n static void compute_collisions(struct strmap *collisions,\n \t\t\t struct strmap *dir_renames,\n \t\t\t struct diff_queue_struct *pairs)\n {\n-\tdie(\"Not yet implemented.\");\n+\tint i;\n+\n+\tstrmap_init_with_options(collisions, NULL, 0);\n+\tif (strmap_empty(dir_renames))\n+\t\treturn;\n+\n+\t/*\n+\t * Multiple files can be mapped to the same path due to directory\n+\t * renames done by the other side of history. Since that other\n+\t * side of history could have merged multiple directories into one,\n+\t * if our side of history added the same file basename to each of\n+\t * those directories, then all N of them would get implicitly\n+\t * renamed by the directory rename detection into the same path,\n+\t * and we'd get an add/add/.../add conflict, and all those adds\n+\t * from *this* side of history. This is not representable in the\n+\t * index, and users aren't going to easily be able to make sense of\n+\t * it. So we need to provide a good warning about what's\n+\t * happening, and fall back to no-directory-rename detection\n+\t * behavior for those paths.\n+\t *\n+\t * See testcases 9e and all of section 5 from t6043 for examples.\n+\t */\n+\tfor (i = 0; i < pairs->nr; ++i) {\n+\t\tstruct strmap_entry *rename_info;\n+\t\tstruct collision_info *collision_info;\n+\t\tchar *new_path;\n+\t\tstruct diff_filepair *pair = pairs->queue[i];\n+\n+\t\tif (pair->status != 'A' && pair->status != 'R')\n+\t\t\tcontinue;\n+\t\trename_info = check_dir_renamed(pair->two->path, dir_renames);\n+\t\tif (!rename_info)\n+\t\t\tcontinue;\n+\n+\t\tnew_path = apply_dir_rename(rename_info, pair->two->path);\n+\t\tassert(new_path);\n+\t\tcollision_info = strmap_get(collisions, new_path);\n+\t\tif (collision_info) {\n+\t\t\tfree(new_path);\n+\t\t} else {\n+\t\t\tcollision_info = xcalloc(1,\n+\t\t\t\t\t\t sizeof(struct collision_info));\n+\t\t\tstring_list_init(&collision_info->source_files, 0);\n+\t\t\tstrmap_put(collisions, new_path, collision_info);\n+\t\t}\n+\t\tstring_list_insert(&collision_info->source_files,\n+\t\t\t\t pair->two->path);\n+\t}\n }\n \n static char *check_for_directory_rename(struct merge_options *opt,\n-- \n2.29.1.106.g3ff750dc32.dirty\n\n"},{"id":"413395","messageId":"20210104235006.2867404-2-newren@gmail.com","threadId":"54929","inReplyTo":"20210104235006.2867404-1-newren@gmail.com","subject":"[PATCH 01/17] merge-ort: add new data structures for directory rename detection","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-01-04T23:49:50Z","receivedAt":"2021-01-04T23:51:15Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Signed-off-by: Elijah Newren \n---\n merge-ort.c | 34 +++++++++++++++++++++++++++++++---\n 1 file changed, 31 insertions(+), 3 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 6900ab9e7f..719cc1c582 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -52,14 +52,42 @@ enum merge_side {\n };\n \n struct rename_info {\n+\t/*\n+\t * All variables that are arrays of size 3 correspond to data tracked\n+\t * for the sides in enum merge_side. Index 0 is almost always unused\n+\t * because we often only need to track information for MERGE_SIDE1 and\n+\t * MERGE_SIDE2 (MERGE_BASE can't have rename information since renames\n+\t * are determined relative to what changed since the MERGE_BASE).\n+\t */\n+\n \t/*\n \t * pairs: pairing of filenames from diffcore_rename()\n-\t *\n-\t * Index 1 and 2 correspond to sides 1 & 2 as used in\n-\t * conflict_info.stages. Index 0 unused.\n \t */\n \tstruct diff_queue_struct pairs[3];\n \n+\t/*\n+\t * dirs_removed: directories removed on a given side of history.\n+\t */\n+\tstruct strset dirs_removed[3];\n+\n+\t/*\n+\t * dir_rename_count: tracking where parts of a directory were renamed to\n+\t *\n+\t * When files in a directory are renamed, they may not all go to the\n+\t * same location. Each strmap here tracks:\n+\t * old_dir => {new_dir => int}\n+\t * That is, dir_rename_count[side] is a strmap to a strintmap.\n+\t */\n+\tstruct strmap dir_rename_count[3];\n+\n+\t/*\n+\t * dir_renames: computed directory renames\n+\t *\n+\t * This is a map of old_dir => new_dir and is derived in part from\n+\t * dir_rename_count.\n+\t */\n+\tstruct strmap dir_renames[3];\n+\n \t/*\n \t * needed_limit: value needed for inexact rename detection to run\n \t *\n-- \n2.29.1.106.g3ff750dc32.dirty\n\n"},{"id":"413396","messageId":"20210104235006.2867404-13-newren@gmail.com","threadId":"54929","inReplyTo":"20210104235006.2867404-1-newren@gmail.com","subject":"[PATCH 12/17] merge-ort: implement check_for_directory_rename()","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-01-04T23:50:01Z","receivedAt":"2021-01-04T23:51:15Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This is copied from merge-recursive.c, with minor tweaks due to using strmap\nAPI and the fact that it can use opt->priv->paths to get all pathnames that\nexist instead of taking a tree object.\n\nThis depends on a new function, handle_path_level_conflicts(), which\njust has a placeholder die-not-yet-implemented implementation for now; a\nsubsequent patch will implement it.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 67 ++++++++++++++++++++++++++++++++++++++++++++++++++++-\n 1 file changed, 66 insertions(+), 1 deletion(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex f7f2470c96..84f4f4776b 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -1282,6 +1282,21 @@ static void get_renamed_dir_portion(const char *old_path, const char *new_path,\n \t*new_dir = xstrndup(new_path, end_of_new - new_path);\n }\n \n+/*\n+ * See if there is a directory rename for path, and if there are any file\n+ * level conflicts on the given side for the renamed location. If there is\n+ * a rename and there are no conflicts, return the new name. Otherwise,\n+ * return NULL.\n+ */\n+static char *handle_path_level_conflicts(struct merge_options *opt,\n+\t\t\t\t\t const char *path,\n+\t\t\t\t\t unsigned side_index,\n+\t\t\t\t\t struct strmap_entry *rename_info,\n+\t\t\t\t\t struct strmap *collisions)\n+{\n+\tdie(\"Not yet implemented\");\n+}\n+\n static void increment_count(struct strmap *dir_rename_count,\n \t\t\t char *old_dir,\n \t\t\t char *new_dir)\n@@ -1497,7 +1512,57 @@ static char *check_for_directory_rename(struct merge_options *opt,\n \t\t\t\t\tstruct strmap *collisions,\n \t\t\t\t\tint *clean_merge)\n {\n-\tdie(\"Not yet implemented.\");\n+\tchar *new_path = NULL;\n+\tstruct strmap_entry *rename_info;\n+\tstruct strmap_entry *otherinfo = NULL;\n+\tconst char *new_dir;\n+\n+\tif (strmap_empty(dir_renames))\n+\t\treturn new_path;\n+\trename_info = check_dir_renamed(path, dir_renames);\n+\tif (!rename_info)\n+\t\treturn new_path;\n+\t/* old_dir = rename_info->key; */\n+\tnew_dir = rename_info->value;\n+\n+\t/*\n+\t * This next part is a little weird. We do not want to do an\n+\t * implicit rename into a directory we renamed on our side, because\n+\t * that will result in a spurious rename/rename(1to2) conflict. An\n+\t * example:\n+\t * Base commit: dumbdir/afile, otherdir/bfile\n+\t * Side 1: smrtdir/afile, otherdir/bfile\n+\t * Side 2: dumbdir/afile, dumbdir/bfile\n+\t * Here, while working on Side 1, we could notice that otherdir was\n+\t * renamed/merged to dumbdir, and change the diff_filepair for\n+\t * otherdir/bfile into a rename into dumbdir/bfile. However, Side\n+\t * 2 will notice the rename from dumbdir to smrtdir, and do the\n+\t * transitive rename to move it from dumbdir/bfile to\n+\t * smrtdir/bfile. That gives us bfile in dumbdir vs being in\n+\t * smrtdir, a rename/rename(1to2) conflict. We really just want\n+\t * the file to end up in smrtdir. And the way to achieve that is\n+\t * to not let Side1 do the rename to dumbdir, since we know that is\n+\t * the source of one of our directory renames.\n+\t *\n+\t * That's why otherinfo and dir_rename_exclusions is here.\n+\t *\n+\t * As it turns out, this also prevents N-way transient rename\n+\t * confusion; See testcases 9c and 9d of t6043.\n+\t */\n+\totherinfo = strmap_get_entry(dir_rename_exclusions, new_dir);\n+\tif (otherinfo) {\n+\t\tpath_msg(opt, rename_info->key, 1,\n+\t\t\t _(\"WARNING: Avoiding applying %s -> %s rename \"\n+\t\t\t \"to %s, because %s itself was renamed.\"),\n+\t\t\t rename_info->key, new_dir, path, new_dir);\n+\t\treturn NULL;\n+\t}\n+\n+\tnew_path = handle_path_level_conflicts(opt, path, side_index,\n+\t\t\t\t\t rename_info, collisions);\n+\t*clean_merge &= (new_path != NULL);\n+\n+\treturn new_path;\n }\n \n static void apply_directory_rename_modifications(struct merge_options *opt,\n-- \n2.29.1.106.g3ff750dc32.dirty\n\n"},{"id":"413397","messageId":"20210104235006.2867404-4-newren@gmail.com","threadId":"54929","inReplyTo":"20210104235006.2867404-1-newren@gmail.com","subject":"[PATCH 03/17] merge-ort: collect which directories are removed in dirs_removed","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-01-04T23:49:52Z","receivedAt":"2021-01-04T23:51:15Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Signed-off-by: Elijah Newren \n---\n merge-ort.c | 27 +++++++++++++++++++++++++++\n 1 file changed, 27 insertions(+)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 8b190b0ea5..f67ecdd171 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -532,6 +532,27 @@ static void setup_path_info(struct merge_options *opt,\n \tresult->util = mi;\n }\n \n+static void collect_rename_info(struct merge_options *opt,\n+\t\t\t\tstruct name_entry *names,\n+\t\t\t\tconst char *dirname,\n+\t\t\t\tconst char *fullname,\n+\t\t\t\tunsigned filemask,\n+\t\t\t\tunsigned dirmask,\n+\t\t\t\tunsigned match_mask)\n+{\n+\tstruct rename_info *renames = &opt->priv->renames;\n+\n+\t/* Update dirs_removed, as needed */\n+\tif (dirmask == 1 || dirmask == 3 || dirmask == 5) {\n+\t\t/* absent_mask = 0x07 - dirmask; sides = absent_mask/2 */\n+\t\tunsigned sides = (0x07 - dirmask)/2;\n+\t\tif (sides & 1)\n+\t\t\tstrset_add(&renames->dirs_removed[1], fullname);\n+\t\tif (sides & 2)\n+\t\t\tstrset_add(&renames->dirs_removed[2], fullname);\n+\t}\n+}\n+\n static int collect_merge_info_callback(int n,\n \t\t\t\t unsigned long mask,\n \t\t\t\t unsigned long dirmask,\n@@ -632,6 +653,12 @@ static int collect_merge_info_callback(int n,\n \t\treturn mask;\n \t}\n \n+\t/*\n+\t * Gather additional information used in rename detection.\n+\t */\n+\tcollect_rename_info(opt, names, dirname, fullpath,\n+\t\t\t filemask, dirmask, match_mask);\n+\n \t/*\n \t * Record information about the path so we can resolve later in\n \t * process_entries.\n-- \n2.29.1.106.g3ff750dc32.dirty\n\n"},{"id":"413398","messageId":"20210104235006.2867404-1-newren@gmail.com","threadId":"54929","inReplyTo":null,"subject":"[PATCH 00/17] Add directory rename detection to merge-ort","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-01-04T23:49:49Z","receivedAt":"2021-01-04T23:51:15Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This series depends on a merge of en/merge-ort-3 and\nen/merge-ort-recursive. It does not depend on the (not-yet-picked-up)\nort-conflict-handling series[1].\n\nThis series mostly implements directory rename detection for\nmerge-ort; I'll cover the \"mostly\" bit below. If one merges this\nseries with en/merge-tests and the ort-conflict-handling series[1],\nthen this series drops the number of failing tests in the testsuite\nunder GIT_TEST_MERGE_ALGORITHM=ort from 60 down to 8.\n\nThere's a lot of code here, but almost all of the logic is just copied\nover from similarly named functions in merge-recursive.c, as\nrepeatedly noted in the commit messages. There are several minor\ndifferences spread throughout that make it not be a direct copy:\n\n * using strmap API instead of direct hashmap calls\n * ort keeps track of all files and directories and their shas in\n opt->priv->paths; no need to re-walk tree objects\n * keeping the necessary invariants for opt->priv->paths\n * we can pre-compute which directories are removed (stored in\n dirs_removed), avoiding the need for some post-processing\n * since ort already has struct rename_info, add the extra data\n there and allocate/free it with the rest of the rename_info\n * no non_unique_new_dir field, leading to the failure of test 2b;\n this will be addressed in a different way with upcoming\n performance work.\n\nThese differences make a direct comparison difficult, but there's not\nreally any new or novel logic; the logic for how directory rename\ndetection is performed is identical to what is found in\nmerge-recursive; it's just packed slightly differently.\n\n...with one exception -- the final patch in the series modifies the\nlogic and makes it different than merge-recursive in order to fix a\nknown bug (testcase 12f of t6423).\n\nThere are still four failing tests in t6423 (directory rename tests)\nafter this series:\n\n * one test (2b) where merge-ort erroneously prints a \"directory\n rename split\" conflict message, despite the fact that there is no\n new file and thus no need for a directory rename to be detected.\n This comes from the lack of a non_unique_new_dir field that I\n didn't bother copying, since performance work will address it in a\n completely different way.\n \n * two tests (12b1 and 12c1) where merge-ort produces the same result\n at merge-recursive (these tests are marked as test_expect_failure\n for merge-recursive). Some performance work will fix these two\n tests.\n\n * one test (12f) where merge-ort produces a better result than\n merge-recursive.c (this test is marked as test_expect_failure for\n merge-recursive), but where merge-ort does not yet manage to pass\n the final four lines of the test related to performance checking.\n\n[1] https://lore.kernel.org/git/pull.815.v2.git.1609468488.gitgitgadget@gmail.com/\n\nElijah Newren (17):\n merge-ort: add new data structures for directory rename detection\n merge-ort: initialize and free new directory rename data structures\n merge-ort: collect which directories are removed in dirs_removed\n merge-ort: add outline for computing directory renames\n merge-ort: add outline of get_provisional_directory_renames()\n merge-ort: copy get_renamed_dir_portion() from merge-recursive.c\n merge-ort: implement compute_rename_counts()\n merge-ort: implement handle_directory_level_conflicts()\n merge-ort: modify collect_renames() for directory rename handling\n merge-ort: implement compute_collisions()\n merge-ort: implement apply_dir_rename() and check_dir_renamed()\n merge-ort: implement check_for_directory_rename()\n merge-ort: implement handle_path_level_conflicts()\n merge-ort: add a new toplevel_dir field\n merge-ort: implement apply_directory_rename_modifications()\n merge-ort: process_renames() now needs more defensiveness\n merge-ort: fix a directory rename detection bug\n\n merge-ort.c | 831 ++++++++++++++++++++++++++++++++++++++++++++++++++--\n 1 file changed, 812 insertions(+), 19 deletions(-)\n\n-- \n2.29.1.106.g3ff750dc32.dirty\n\n"},{"id":"413399","messageId":"20210104235006.2867404-5-newren@gmail.com","threadId":"54929","inReplyTo":"20210104235006.2867404-1-newren@gmail.com","subject":"[PATCH 04/17] merge-ort: add outline for computing directory renames","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-01-04T23:49:53Z","receivedAt":"2021-01-04T23:51:34Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Port some directory rename handling changes from merge-recursive.c's\ndetect_and_process_renames() to the same-named function of merge-ort.c.\nThis does not yet add any use or handling of directory renames, just the\noutline for where we start to compute them. Thus, a future patch will\nadd port additional changes to merge-ort's detect_and_process_renames().\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 25 ++++++++++++++++++++++++-\n 1 file changed, 24 insertions(+), 1 deletion(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex f67ecdd171..0bd0ab1e8b 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -1139,6 +1139,18 @@ static int handle_content_merge(struct merge_options *opt,\n \n /*** Function Grouping: functions related to directory rename detection ***/\n \n+static void get_provisional_directory_renames(struct merge_options *opt,\n+\t\t\t\t\t unsigned side,\n+\t\t\t\t\t int *clean)\n+{\n+\tdie(\"Not yet implemented!\");\n+}\n+\n+static void handle_directory_level_conflicts(struct merge_options *opt)\n+{\n+\tdie(\"Not yet implemented!\");\n+}\n+\n /*** Function Grouping: functions related to regular rename detection ***/\n \n static int process_renames(struct merge_options *opt,\n@@ -1504,13 +1516,24 @@ static int detect_and_process_renames(struct merge_options *opt,\n {\n \tstruct diff_queue_struct combined;\n \tstruct rename_info *renames = &opt->priv->renames;\n-\tint s, clean = 1;\n+\tint need_dir_renames, s, clean = 1;\n \n \tmemset(&combined, 0, sizeof(combined));\n \n \tdetect_regular_renames(opt, merge_base, side1, MERGE_SIDE1);\n \tdetect_regular_renames(opt, merge_base, side2, MERGE_SIDE2);\n \n+\tneed_dir_renames =\n+\t !opt->priv->call_depth &&\n+\t (opt->detect_directory_renames == MERGE_DIRECTORY_RENAMES_TRUE ||\n+\t opt->detect_directory_renames == MERGE_DIRECTORY_RENAMES_CONFLICT);\n+\n+\tif (need_dir_renames) {\n+\t\tfor (s = MERGE_SIDE1; s <= MERGE_SIDE2; s++)\n+\t\t\tget_provisional_directory_renames(opt, s, &clean);\n+\t\thandle_directory_level_conflicts(opt);\n+\t}\n+\n \tALLOC_GROW(combined.queue,\n \t\t renames->pairs[1].nr + renames->pairs[2].nr,\n \t\t combined.alloc);\n-- \n2.29.1.106.g3ff750dc32.dirty\n\n"},{"id":"413400","messageId":"20210104235006.2867404-7-newren@gmail.com","threadId":"54929","inReplyTo":"20210104235006.2867404-1-newren@gmail.com","subject":"[PATCH 06/17] merge-ort: copy get_renamed_dir_portion() from merge-recursive.c","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-01-04T23:49:55Z","receivedAt":"2021-01-04T23:51:34Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Signed-off-by: Elijah Newren \n---\n merge-ort.c | 104 ++++++++++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 104 insertions(+)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 6ccc7a1a45..19c3f8d41d 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -1139,6 +1139,110 @@ static int handle_content_merge(struct merge_options *opt,\n \n /*** Function Grouping: functions related to directory rename detection ***/\n \n+MAYBE_UNUSED\n+static void get_renamed_dir_portion(const char *old_path, const char *new_path,\n+\t\t\t\t char **old_dir, char **new_dir)\n+{\n+\tchar *end_of_old, *end_of_new;\n+\n+\t/* Default return values: NULL, meaning no rename */\n+\t*old_dir = NULL;\n+\t*new_dir = NULL;\n+\n+\t/*\n+\t * For\n+\t * \"a/b/c/d/e/foo.c\" -> \"a/b/some/thing/else/e/foo.c\"\n+\t * the \"e/foo.c\" part is the same, we just want to know that\n+\t * \"a/b/c/d\" was renamed to \"a/b/some/thing/else\"\n+\t * so, for this example, this function returns \"a/b/c/d\" in\n+\t * *old_dir and \"a/b/some/thing/else\" in *new_dir.\n+\t */\n+\n+\t/*\n+\t * If the basename of the file changed, we don't care. We want\n+\t * to know which portion of the directory, if any, changed.\n+\t */\n+\tend_of_old = strrchr(old_path, '/');\n+\tend_of_new = strrchr(new_path, '/');\n+\n+\t/*\n+\t * If end_of_old is NULL, old_path wasn't in a directory, so there\n+\t * could not be a directory rename (our rule elsewhere that a\n+\t * directory which still exists is not considered to have been\n+\t * renamed means the root directory can never be renamed -- because\n+\t * the root directory always exists).\n+\t */\n+\tif (end_of_old == NULL)\n+\t\treturn; /* Note: *old_dir and *new_dir are still NULL */\n+\n+\t/*\n+\t * If new_path contains no directory (end_of_new is NULL), then we\n+\t * have a rename of old_path's directory to the root directory.\n+\t */\n+\tif (end_of_new == NULL) {\n+\t\t*old_dir = xstrndup(old_path, end_of_old - old_path);\n+\t\t*new_dir = xstrdup(\"\");\n+\t\treturn;\n+\t}\n+\n+\t/* Find the first non-matching character traversing backwards */\n+\twhile (*--end_of_new == *--end_of_old &&\n+\t end_of_old != old_path &&\n+\t end_of_new != new_path)\n+\t\t; /* Do nothing; all in the while loop */\n+\n+\t/*\n+\t * If both got back to the beginning of their strings, then the\n+\t * directory didn't change at all, only the basename did.\n+\t */\n+\tif (end_of_old == old_path && end_of_new == new_path &&\n+\t *end_of_old == *end_of_new)\n+\t\treturn; /* Note: *old_dir and *new_dir are still NULL */\n+\n+\t/*\n+\t * If end_of_new got back to the beginning of its string, and\n+\t * end_of_old got back to the beginning of some subdirectory, then\n+\t * we have a rename/merge of a subdirectory into the root, which\n+\t * needs slightly special handling.\n+\t *\n+\t * Note: There is no need to consider the opposite case, with a\n+\t * rename/merge of the root directory into some subdirectory\n+\t * because as noted above the root directory always exists so it\n+\t * cannot be considered to be renamed.\n+\t */\n+\tif (end_of_new == new_path &&\n+\t end_of_old != old_path && end_of_old[-1] == '/') {\n+\t\t*old_dir = xstrndup(old_path, --end_of_old - old_path);\n+\t\t*new_dir = xstrdup(\"\");\n+\t\treturn;\n+\t}\n+\n+\t/*\n+\t * We've found the first non-matching character in the directory\n+\t * paths. That means the current characters we were looking at\n+\t * were part of the first non-matching subdir name going back from\n+\t * the end of the strings. Get the whole name by advancing both\n+\t * end_of_old and end_of_new to the NEXT '/' character. That will\n+\t * represent the entire directory rename.\n+\t *\n+\t * The reason for the increment is cases like\n+\t * a/b/star/foo/whatever.c -> a/b/tar/foo/random.c\n+\t * After dropping the basename and going back to the first\n+\t * non-matching character, we're now comparing:\n+\t * a/b/s and a/b/\n+\t * and we want to be comparing:\n+\t * a/b/star/ and a/b/tar/\n+\t * but without the pre-increment, the one on the right would stay\n+\t * a/b/.\n+\t */\n+\tend_of_old = strchr(++end_of_old, '/');\n+\tend_of_new = strchr(++end_of_new, '/');\n+\n+\t/* Copy the old and new directories into *old_dir and *new_dir. */\n+\t*old_dir = xstrndup(old_path, end_of_old - old_path);\n+\t*new_dir = xstrndup(new_path, end_of_new - new_path);\n+}\n+\n static void compute_rename_counts(struct diff_queue_struct *pairs,\n \t\t\t\t struct strmap *dir_rename_count,\n \t\t\t\t struct strset *dirs_removed)\n-- \n2.29.1.106.g3ff750dc32.dirty\n\n"},{"id":"413401","messageId":"20210104235006.2867404-15-newren@gmail.com","threadId":"54929","inReplyTo":"20210104235006.2867404-1-newren@gmail.com","subject":"[PATCH 14/17] merge-ort: add a new toplevel_dir field","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-01-04T23:50:03Z","receivedAt":"2021-01-04T23:51:34Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Due to the string-equality-iff-pointer-equality requirements placed on\nmerged_info.directory_name, apply_directory_rename_modifications() will\nneed to have access to the exact toplevel directory name string pointer\nand can't just use a new empty string. Store it in a field that we can\nuse.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 15 +++++++++------\n 1 file changed, 9 insertions(+), 6 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex d0fb8f4282..230224e680 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -171,12 +171,15 @@ struct merge_options_internal {\n \tstruct rename_info renames;\n \n \t/*\n-\t * current_dir_name: temporary var used in collect_merge_info_callback()\n+\t * current_dir_name, toplevel_dir: temporary vars\n \t *\n-\t * Used to set merged_info.directory_name; see documentation for that\n-\t * variable and the requirements placed on that field.\n+\t * These are used in collect_merge_info_callback(), and will set the\n+\t * various merged_info.directory_name for the various paths we get;\n+\t * see documentation for that variable and the requirements placed on\n+\t * that field.\n \t */\n \tconst char *current_dir_name;\n+\tconst char *toplevel_dir;\n \n \t/* call_depth: recursion level counter for merging merge bases */\n \tint call_depth;\n@@ -734,10 +737,10 @@ static int collect_merge_info(struct merge_options *opt,\n \tint ret;\n \tstruct tree_desc t[3];\n \tstruct traverse_info info;\n-\tconst char *toplevel_dir_placeholder = \"\";\n \n-\topt->priv->current_dir_name = toplevel_dir_placeholder;\n-\tsetup_traverse_info(&info, toplevel_dir_placeholder);\n+\topt->priv->toplevel_dir = \"\";\n+\topt->priv->current_dir_name = opt->priv->toplevel_dir;\n+\tsetup_traverse_info(&info, opt->priv->toplevel_dir);\n \tinfo.fn = collect_merge_info_callback;\n \tinfo.data = opt;\n \tinfo.show_all_errors = 1;\n-- \n2.29.1.106.g3ff750dc32.dirty\n\n"},{"id":"413402","messageId":"20210104235006.2867404-6-newren@gmail.com","threadId":"54929","inReplyTo":"20210104235006.2867404-1-newren@gmail.com","subject":"[PATCH 05/17] merge-ort: add outline of get_provisional_directory_renames()","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-01-04T23:49:54Z","receivedAt":"2021-01-04T23:51:34Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This function is based on merge-recursive.c's get_directory_renames(),\nexcept that the first half has been split out into a not-yet-implemented\ncompute_rename_counts(). The primary difference here is our lack of the\nnon_unique_new_dir boolean in our strmap. The lack of that field will\nat first cause us to fail testcase 2b of t6423; however, future\noptimizations will obviate the need for that ugly field so we have just\nleft it out.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 60 ++++++++++++++++++++++++++++++++++++++++++++++++++++-\n 1 file changed, 59 insertions(+), 1 deletion(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 0bd0ab1e8b..6ccc7a1a45 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -1139,11 +1139,69 @@ static int handle_content_merge(struct merge_options *opt,\n \n /*** Function Grouping: functions related to directory rename detection ***/\n \n+static void compute_rename_counts(struct diff_queue_struct *pairs,\n+\t\t\t\t struct strmap *dir_rename_count,\n+\t\t\t\t struct strset *dirs_removed)\n+{\n+\tdie(\"Not yet implemented!\");\n+}\n+\n static void get_provisional_directory_renames(struct merge_options *opt,\n \t\t\t\t\t unsigned side,\n \t\t\t\t\t int *clean)\n {\n-\tdie(\"Not yet implemented!\");\n+\tstruct hashmap_iter iter;\n+\tstruct strmap_entry *entry;\n+\tstruct rename_info *renames = &opt->priv->renames;\n+\n+\tcompute_rename_counts(&renames->pairs[side],\n+\t\t\t &renames->dir_rename_count[side],\n+\t\t\t &renames->dirs_removed[side]);\n+\t/*\n+\t * Collapse\n+\t * dir_rename_count: old_directory -> {new_directory -> count}\n+\t * down to\n+\t * dir_renames: old_directory -> best_new_directory\n+\t * where best_new_directory is the one with the unique highest count.\n+\t */\n+\tstrmap_for_each_entry(&renames->dir_rename_count[side], &iter, entry) {\n+\t\tconst char *source_dir = entry->key;\n+\t\tstruct strintmap *counts = entry->value;\n+\t\tstruct hashmap_iter count_iter;\n+\t\tstruct strmap_entry *count_entry;\n+\t\tint max = 0;\n+\t\tint bad_max = 0;\n+\t\tconst char *best = NULL;\n+\n+\t\tstrintmap_for_each_entry(counts, &count_iter, count_entry) {\n+\t\t\tconst char *target_dir = count_entry->key;\n+\t\t\tintptr_t count = (intptr_t)count_entry->value;\n+\n+\t\t\tif (count == max)\n+\t\t\t\tbad_max = max;\n+\t\t\telse if (count > max) {\n+\t\t\t\tmax = count;\n+\t\t\t\tbest = target_dir;\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (max == 0)\n+\t\t\tcontinue;\n+\n+\t\tif (bad_max == max) {\n+\t\t\tpath_msg(opt, source_dir, 0,\n+\t\t\t _(\"CONFLICT (directory rename split): \"\n+\t\t\t\t \"Unclear where to rename %s to; it was \"\n+\t\t\t\t \"renamed to multiple other directories, with \"\n+\t\t\t\t \"no destination getting a majority of the \"\n+\t\t\t\t \"files.\"),\n+\t\t\t source_dir);\n+\t\t\t*clean &= 0;\n+\t\t} else {\n+\t\t\tstrmap_put(&renames->dir_renames[side],\n+\t\t\t\t source_dir, (void*)best);\n+\t\t}\n+\t}\n }\n \n static void handle_directory_level_conflicts(struct merge_options *opt)\n-- \n2.29.1.106.g3ff750dc32.dirty\n\n"},{"id":"413403","messageId":"20210104235006.2867404-10-newren@gmail.com","threadId":"54929","inReplyTo":"20210104235006.2867404-1-newren@gmail.com","subject":"[PATCH 09/17] merge-ort: modify collect_renames() for directory rename handling","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-01-04T23:49:58Z","receivedAt":"2021-01-04T23:51:34Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"collect_renames() is similar to merge-recursive.c's get_renames(), but\nlacks the directory rename handling found in the latter. Port that code\nstructure over to merge-ort. This introduces three new\ndie-not-yet-implemented functions that will be defined in future\ncommits.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 78 ++++++++++++++++++++++++++++++++++++++++++++++++++---\n 1 file changed, 74 insertions(+), 4 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex c4f437d4c0..a52905c4ee 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -1139,6 +1139,11 @@ static int handle_content_merge(struct merge_options *opt,\n \n /*** Function Grouping: functions related to directory rename detection ***/\n \n+struct collision_info {\n+\tstruct string_list source_files;\n+\tunsigned reported_already:1;\n+};\n+\n static void get_renamed_dir_portion(const char *old_path, const char *new_path,\n \t\t\t\t char **old_dir, char **new_dir)\n {\n@@ -1378,6 +1383,31 @@ static void handle_directory_level_conflicts(struct merge_options *opt)\n \tstring_list_clear(&duplicated, 0);\n }\n \n+static void compute_collisions(struct strmap *collisions,\n+\t\t\t struct strmap *dir_renames,\n+\t\t\t struct diff_queue_struct *pairs)\n+{\n+\tdie(\"Not yet implemented.\");\n+}\n+\n+static char *check_for_directory_rename(struct merge_options *opt,\n+\t\t\t\t\tconst char *path,\n+\t\t\t\t\tunsigned side_index,\n+\t\t\t\t\tstruct strmap *dir_renames,\n+\t\t\t\t\tstruct strmap *dir_rename_exclusions,\n+\t\t\t\t\tstruct strmap *collisions,\n+\t\t\t\t\tint *clean_merge)\n+{\n+\tdie(\"Not yet implemented.\");\n+}\n+\n+static void apply_directory_rename_modifications(struct merge_options *opt,\n+\t\t\t\t\t\t struct diff_filepair *pair,\n+\t\t\t\t\t\t char *new_path)\n+{\n+\tdie(\"Not yet implemented.\");\n+}\n+\n /*** Function Grouping: functions related to regular rename detection ***/\n \n static int process_renames(struct merge_options *opt,\n@@ -1703,22 +1733,44 @@ static void detect_regular_renames(struct merge_options *opt,\n */\n static int collect_renames(struct merge_options *opt,\n \t\t\t struct diff_queue_struct *result,\n-\t\t\t unsigned side_index)\n+\t\t\t unsigned side_index,\n+\t\t\t struct strmap *dir_renames_for_side,\n+\t\t\t struct strmap *rename_exclusions)\n {\n \tint i, clean = 1;\n+\tstruct strmap collisions;\n \tstruct diff_queue_struct *side_pairs;\n+\tstruct hashmap_iter iter;\n+\tstruct strmap_entry *entry;\n \tstruct rename_info *renames = &opt->priv->renames;\n \n \tside_pairs = &renames->pairs[side_index];\n+\tcompute_collisions(&collisions, dir_renames_for_side, side_pairs);\n \n \tfor (i = 0; i < side_pairs->nr; ++i) {\n \t\tstruct diff_filepair *p = side_pairs->queue[i];\n+\t\tchar *new_path; /* non-NULL only with directory renames */\n \n-\t\tif (p->status != 'R') {\n+\t\tif (p->status != 'A' && p->status != 'R') {\n \t\t\tdiff_free_filepair(p);\n \t\t\tcontinue;\n \t\t}\n \n+\t\tnew_path = check_for_directory_rename(opt, p->two->path,\n+\t\t\t\t\t\t side_index,\n+\t\t\t\t\t\t dir_renames_for_side,\n+\t\t\t\t\t\t rename_exclusions,\n+\t\t\t\t\t\t &collisions,\n+\t\t\t\t\t\t &clean);\n+\n+\t\tif (p->status != 'R' && !new_path) {\n+\t\t\tdiff_free_filepair(p);\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tif (new_path)\n+\t\t\tapply_directory_rename_modifications(opt, p, new_path);\n+\n \t\t/*\n \t\t * p->score comes back from diffcore_rename_extended() with\n \t\t * the similarity of the renamed file. The similarity is\n@@ -1733,6 +1785,20 @@ static int collect_renames(struct merge_options *opt,\n \t\tresult->queue[result->nr++] = p;\n \t}\n \n+\t/* Free each value in the collisions map */\n+\tstrmap_for_each_entry(&collisions, &iter, entry) {\n+\t\tstruct collision_info *info = entry->value;\n+\t\tstring_list_clear(&info->source_files, 0);\n+\t}\n+\t/*\n+\t * In compute_collisions(), we set collisions.strdup_strings to 0\n+\t * so that we wouldn't have to make another copy of the new_path\n+\t * allocated by apply_dir_rename(). But now that we've used them\n+\t * and have no other references to these strings, it is time to\n+\t * deallocate them.\n+\t */\n+\tfree_strmap_strings(&collisions);\n+\tstrmap_clear(&collisions, 1);\n \treturn clean;\n }\n \n@@ -1764,8 +1830,12 @@ static int detect_and_process_renames(struct merge_options *opt,\n \tALLOC_GROW(combined.queue,\n \t\t renames->pairs[1].nr + renames->pairs[2].nr,\n \t\t combined.alloc);\n-\tclean &= collect_renames(opt, &combined, MERGE_SIDE1);\n-\tclean &= collect_renames(opt, &combined, MERGE_SIDE2);\n+\tclean &= collect_renames(opt, &combined, MERGE_SIDE1,\n+\t\t\t\t &renames->dir_renames[2],\n+\t\t\t\t &renames->dir_renames[1]);\n+\tclean &= collect_renames(opt, &combined, MERGE_SIDE2,\n+\t\t\t\t &renames->dir_renames[1],\n+\t\t\t\t &renames->dir_renames[2]);\n \tQSORT(combined.queue, combined.nr, compare_pairs);\n \n \tclean &= process_renames(opt, &combined);\n-- \n2.29.1.106.g3ff750dc32.dirty\n\n"},{"id":"413404","messageId":"20210104235006.2867404-8-newren@gmail.com","threadId":"54929","inReplyTo":"20210104235006.2867404-1-newren@gmail.com","subject":"[PATCH 07/17] merge-ort: implement compute_rename_counts()","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-01-04T23:49:56Z","receivedAt":"2021-01-04T23:51:34Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This function is based on the first half of get_directory_renames() from\nmerge-recursive.c\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 53 +++++++++++++++++++++++++++++++++++++++++++++++++++--\n 1 file changed, 51 insertions(+), 2 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 19c3f8d41d..05bac9c5bd 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -1139,7 +1139,6 @@ static int handle_content_merge(struct merge_options *opt,\n \n /*** Function Grouping: functions related to directory rename detection ***/\n \n-MAYBE_UNUSED\n static void get_renamed_dir_portion(const char *old_path, const char *new_path,\n \t\t\t\t char **old_dir, char **new_dir)\n {\n@@ -1243,11 +1242,61 @@ static void get_renamed_dir_portion(const char *old_path, const char *new_path,\n \t*new_dir = xstrndup(new_path, end_of_new - new_path);\n }\n \n+static void increment_count(struct strmap *dir_rename_count,\n+\t\t\t char *old_dir,\n+\t\t\t char *new_dir)\n+{\n+\tstruct strintmap *counts;\n+\tstruct strmap_entry *e;\n+\n+\t/* Get the {new_dirs -> counts} mapping using old_dir */\n+\te = strmap_get_entry(dir_rename_count, old_dir);\n+\tif (e) {\n+\t\tcounts = e->value;\n+\t} else {\n+\t\tcounts = xmalloc(sizeof(*counts));\n+\t\tstrintmap_init_with_options(counts, 0, NULL, 1);\n+\t\tstrmap_put(dir_rename_count, old_dir, counts);\n+\t}\n+\n+\t/* Increment the count for new_dir */\n+\tstrintmap_incr(counts, new_dir, 1);\n+}\n+\n static void compute_rename_counts(struct diff_queue_struct *pairs,\n \t\t\t\t struct strmap *dir_rename_count,\n \t\t\t\t struct strset *dirs_removed)\n {\n-\tdie(\"Not yet implemented!\");\n+\tint i;\n+\n+\tfor (i = 0; i < pairs->nr; ++i) {\n+\t\tchar *old_dir, *new_dir;\n+\t\tstruct diff_filepair *pair = pairs->queue[i];\n+\n+\t\tif (pair->status != 'R')\n+\t\t\tcontinue;\n+\n+\t\t/* Get the old and new directory names */\n+\t\tget_renamed_dir_portion(pair->one->path, pair->two->path,\n+\t\t\t\t\t&old_dir, &new_dir);\n+\t\tif (!old_dir)\n+\t\t\t/* Directory didn't change at all; ignore this one. */\n+\t\t\tcontinue;\n+\n+\t\t/*\n+\t\t * Make dir_rename_count contain a map of a map:\n+\t\t * old_directory -> {new_directory -> count}\n+\t\t * In other words, for every pair look at the directories for\n+\t\t * the old filename and the new filename and count how many\n+\t\t * times that pairing occurs.\n+\t\t */\n+\t\tif (strset_contains(dirs_removed, old_dir))\n+\t\t\tincrement_count(dir_rename_count, old_dir, new_dir);\n+\n+\t\t/* Free resources we don't need anymore */\n+\t\tfree(old_dir);\n+\t\tfree(new_dir);\n+\t}\n }\n \n static void get_provisional_directory_renames(struct merge_options *opt,\n-- \n2.29.1.106.g3ff750dc32.dirty\n\n"},{"id":"413405","messageId":"20210104235006.2867404-16-newren@gmail.com","threadId":"54929","inReplyTo":"20210104235006.2867404-1-newren@gmail.com","subject":"[PATCH 15/17] merge-ort: implement apply_directory_rename_modifications()","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-01-04T23:50:04Z","receivedAt":"2021-01-04T23:51:34Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This function roughly follows the same outline as the function of the\nsame name from merge-recursive.c, but the code diverges in multiple\nways due to some special considerations:\n * merge-ort's version needs to update opt->priv->paths with any new\n paths (and opt->priv->paths points to struct conflict_infos which\n track quite a bit of metadata for each path); merge-recursive's\n version would directly update the index\n * merge-ort requires that opt->priv->paths has any leading directories\n of any relevant files also be included in the set of paths. And\n due to pointer equality requirements on merged_info.directory_name,\n we have to be careful how we compute and insert these.\n * due to the above requirements on opt->priv->paths, merge-ort's\n version starts with a long comment to explain all the special\n considerations that need to be handled\n * merge-ort can use the full data stored in opt->priv->paths to avoid\n making expensive get_tree_entry() calls to regather the necessary\n data.\n * due to messages being deferred automatically in merge-ort, this is\n the best place to handle conflict messages whereas in\n merge-recursive.c they are deferred manually so that processing of\n entries does all the printing\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 168 +++++++++++++++++++++++++++++++++++++++++++++++++++-\n 1 file changed, 167 insertions(+), 1 deletion(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 230224e680..115ff6d2d5 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -1642,7 +1642,173 @@ static void apply_directory_rename_modifications(struct merge_options *opt,\n \t\t\t\t\t\t struct diff_filepair *pair,\n \t\t\t\t\t\t char *new_path)\n {\n-\tdie(\"Not yet implemented.\");\n+\t/*\n+\t * The basic idea is to get the conflict_info from opt->priv->paths\n+\t * at old path, and insert it into new_path; basically just this:\n+\t * ci = strmap_get(&opt->priv->paths, old_path);\n+\t * strmap_remove(&opt->priv->paths, old_path, 0);\n+\t * strmap_put(&opt->priv->paths, new_path, ci);\n+\t * However, there are some factors complicating this:\n+\t * - opt->priv->paths may already have an entry at new_path\n+\t * - Each ci tracks its containing directory, so we need to\n+\t * update that\n+\t * - If another ci has the same containing directory, then\n+\t * the two char*'s MUST point to the same location. See the\n+\t * comment in struct merged_info. strcmp equality is not\n+\t * enough; we need pointer equality.\n+\t * - opt->priv->paths must hold the parent directories of any\n+\t * entries that are added. So, if this directory rename\n+\t * causes entirely new directories, we must recursively add\n+\t * parent directories.\n+\t * - For each parent directory added to opt->priv->paths, we\n+\t * also need to get its parent directory stored in its\n+\t * conflict_info->merged.directory_name with all the same\n+\t * requirements about pointer equality.\n+\t */\n+\tstruct string_list dirs_to_insert = STRING_LIST_INIT_NODUP;\n+\tstruct conflict_info *ci, *new_ci;\n+\tstruct strmap_entry *entry;\n+\tconst char *branch_with_new_path, *branch_with_dir_rename;\n+\tconst char *old_path = pair->two->path;\n+\tconst char *parent_name;\n+\tconst char *cur_path;\n+\tint i, len;\n+\n+\tentry = strmap_get_entry(&opt->priv->paths, old_path);\n+\told_path = entry->key;\n+\tci = entry->value;\n+\tVERIFY_CI(ci);\n+\n+\t/* Find parent directories missing from opt->priv->paths */\n+\tcur_path = new_path;\n+\twhile (1) {\n+\t\t/* Find the parent directory of cur_path */\n+\t\tchar *last_slash = strrchr(cur_path, '/');\n+\t\tif (last_slash) {\n+\t\t\tparent_name = xstrndup(cur_path, last_slash - cur_path);\n+\t\t} else {\n+\t\t\tparent_name = opt->priv->toplevel_dir;\n+\t\t\tbreak;\n+\t\t}\n+\n+\t\t/* Look it up in opt->priv->paths */\n+\t\tentry = strmap_get_entry(&opt->priv->paths, parent_name);\n+\t\tif (entry) {\n+\t\t\tfree((char*)parent_name);\n+\t\t\tparent_name = entry->key; /* reuse known pointer */\n+\t\t\tbreak;\n+\t\t}\n+\n+\t\t/* Record this is one of the directories we need to insert */\n+\t\tstring_list_append(&dirs_to_insert, parent_name);\n+\t\tcur_path = parent_name;\n+\t}\n+\n+\t/* Traverse dirs_to_insert and insert them into opt->priv->paths */\n+\tfor (i = dirs_to_insert.nr-1; i >= 0; --i) {\n+\t\tstruct conflict_info *dir_ci;\n+\t\tchar *cur_dir = dirs_to_insert.items[i].string;\n+\n+\t\tdir_ci = xcalloc(1, sizeof(*dir_ci));\n+\n+\t\tdir_ci->merged.directory_name = parent_name;\n+\t\tlen = strlen(parent_name);\n+\t\t/* len+1 because of trailing '/' character */\n+\t\tdir_ci->merged.basename_offset = (len > 0 ? len+1 : len);\n+\t\tdir_ci->dirmask = ci->filemask;\n+\t\tstrmap_put(&opt->priv->paths, cur_dir, dir_ci);\n+\n+\t\tparent_name = cur_dir;\n+\t}\n+\n+\t/*\n+\t * We are removing old_path from opt->priv->paths. old_path also will\n+\t * eventually need to be freed, but it may still be used by e.g.\n+\t * ci->pathnames. So, store it in another string-list for now.\n+\t */\n+\tstring_list_append(&opt->priv->paths_to_free, old_path);\n+\n+\tassert(ci->filemask == 2 || ci->filemask == 4);\n+\tassert(ci->dirmask == 0);\n+\tstrmap_remove(&opt->priv->paths, old_path, 0);\n+\n+\tbranch_with_new_path = (ci->filemask == 2) ? opt->branch1 : opt->branch2;\n+\tbranch_with_dir_rename = (ci->filemask == 2) ? opt->branch2 : opt->branch1;\n+\n+\t/* Now, finally update ci and stick it into opt->priv->paths */\n+\tci->merged.directory_name = parent_name;\n+\tlen = strlen(parent_name);\n+\tci->merged.basename_offset = (len > 0 ? len+1 : len);\n+\tnew_ci = strmap_get(&opt->priv->paths, new_path);\n+\tif (!new_ci) {\n+\t\t/* Place ci back into opt->priv->paths, but at new_path */\n+\t\tstrmap_put(&opt->priv->paths, new_path, ci);\n+\t} else {\n+\t\tint index;\n+\n+\t\t/* A few sanity checks */\n+\t\tVERIFY_CI(new_ci);\n+\t\tassert(ci->filemask == 2 || ci->filemask == 4);\n+\t\tassert((new_ci->filemask & ci->filemask) == 0);\n+\t\tassert(!new_ci->merged.clean);\n+\n+\t\t/* Copy stuff from ci into new_ci */\n+\t\tnew_ci->filemask |= ci->filemask;\n+\t\tif (new_ci->dirmask)\n+\t\t\tnew_ci->df_conflict = 1;\n+\t\tindex = (ci->filemask >> 1);\n+\t\tnew_ci->pathnames[index] = ci->pathnames[index];\n+\t\tnew_ci->stages[index].mode = ci->stages[index].mode;\n+\t\toidcpy(&new_ci->stages[index].oid, &ci->stages[index].oid);\n+\n+\t\tfree(ci);\n+\t\tci = new_ci;\n+\t}\n+\n+\tif (opt->detect_directory_renames == MERGE_DIRECTORY_RENAMES_TRUE) {\n+\t\t/* Notify user of updated path */\n+\t\tif (pair->status == 'A')\n+\t\t\tpath_msg(opt, new_path, 1,\n+\t\t\t\t _(\"Path updated: %s added in %s inside a \"\n+\t\t\t\t \"directory that was renamed in %s; moving \"\n+\t\t\t\t \"it to %s.\"),\n+\t\t\t\t old_path, branch_with_new_path,\n+\t\t\t\t branch_with_dir_rename, new_path);\n+\t\telse\n+\t\t\tpath_msg(opt, new_path, 1,\n+\t\t\t\t _(\"Path updated: %s renamed to %s in %s, \"\n+\t\t\t\t \"inside a directory that was renamed in %s; \"\n+\t\t\t\t \"moving it to %s.\"),\n+\t\t\t\t pair->one->path, old_path, branch_with_new_path,\n+\t\t\t\t branch_with_dir_rename, new_path);\n+\t} else {\n+\t\t/*\n+\t\t * opt->detect_directory_renames has the value\n+\t\t * MERGE_DIRECTORY_RENAMES_CONFLICT, so mark these as conflicts.\n+\t\t */\n+\t\tci->path_conflict = 1;\n+\t\tif (pair->status == 'A')\n+\t\t\tpath_msg(opt, new_path, 0,\n+\t\t\t\t _(\"CONFLICT (file location): %s added in %s \"\n+\t\t\t\t \"inside a directory that was renamed in %s, \"\n+\t\t\t\t \"suggesting it should perhaps be moved to \"\n+\t\t\t\t \"%s.\"),\n+\t\t\t\t old_path, branch_with_new_path,\n+\t\t\t\t branch_with_dir_rename, new_path);\n+\t\telse\n+\t\t\tpath_msg(opt, new_path, 0,\n+\t\t\t\t _(\"CONFLICT (file location): %s renamed to %s \"\n+\t\t\t\t \"in %s, inside a directory that was renamed \"\n+\t\t\t\t \"in %s, suggesting it should perhaps be \"\n+\t\t\t\t \"moved to %s.\"),\n+\t\t\t\t pair->one->path, old_path, branch_with_new_path,\n+\t\t\t\t branch_with_dir_rename, new_path);\n+\t}\n+\n+\t/*\n+\t * Finally, record the new location.\n+\t */\n+\tpair->two->path = new_path;\n }\n \n /*** Function Grouping: functions related to regular rename detection ***/\n-- \n2.29.1.106.g3ff750dc32.dirty\n\n"},{"id":"413406","messageId":"20210104235006.2867404-18-newren@gmail.com","threadId":"54929","inReplyTo":"20210104235006.2867404-1-newren@gmail.com","subject":"[PATCH 17/17] merge-ort: fix a directory rename detection bug","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-01-04T23:50:06Z","receivedAt":"2021-01-04T23:51:34Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"As noted in commit 902c521a35 (\"t6423: more involved directory rename\ntest\", 2020-10-15), when we have a case where\n\n * dir/subdir/ has several files\n * almost all files in dir/subdir/ are renamed to folder/subdir/\n * one of the files in dir/subdir/ is renamed to folder/subdir/newsubdir/\n * the other side of history (that doesn't do the renames) adds a\n new file to dir/subdir/\n\nThen for the majority of the file renames, the directory rename of\n dir/subdir/ -> folder/subdir/\nis actually not represented that way but as\n dir/ -> folder/\nWe also had one rename that was represented as\n dir/subdir/ -> folder/subdir/newsubdir/\n\nNow, since there's a new file in dir/subdir/, where does it go? Well,\nthere's only one rule for dir/subdir/, so the code previously noted that\nthis rule had the \"majority\" of the one \"relevant\" rename and thus\nerroneously used it to place the file in folder/subdir/newsubdir/. We\nreally want the heavy weight associated with dir/ -> folder/ to also be\ntreated as dir/subdir/ -> folder/subdir/, so that we correctly place the\nfile in folder/subdir/.\n\nAdd a bunch of logic to make sure that we use all relevant renamings in\ndirectory rename detection.\n\nNote that testcase 12f of t6423 still fails after this, but it gets\nfurther than merge-recursive does. There are some performance related\nbits in that testcase (the region_enter messages) that do not yet\nsucceed, but the rest of the testcase works after this patch.\nSubsequent patch series will fix up the performance side.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 198 +++++++++++++++++++++-------------------------------\n 1 file changed, 81 insertions(+), 117 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 480f212cff..8f4ca4fe83 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -1182,109 +1182,6 @@ static char *apply_dir_rename(struct strmap_entry *rename_info,\n \treturn strbuf_detach(&new_path, NULL);\n }\n \n-static void get_renamed_dir_portion(const char *old_path, const char *new_path,\n-\t\t\t\t char **old_dir, char **new_dir)\n-{\n-\tchar *end_of_old, *end_of_new;\n-\n-\t/* Default return values: NULL, meaning no rename */\n-\t*old_dir = NULL;\n-\t*new_dir = NULL;\n-\n-\t/*\n-\t * For\n-\t * \"a/b/c/d/e/foo.c\" -> \"a/b/some/thing/else/e/foo.c\"\n-\t * the \"e/foo.c\" part is the same, we just want to know that\n-\t * \"a/b/c/d\" was renamed to \"a/b/some/thing/else\"\n-\t * so, for this example, this function returns \"a/b/c/d\" in\n-\t * *old_dir and \"a/b/some/thing/else\" in *new_dir.\n-\t */\n-\n-\t/*\n-\t * If the basename of the file changed, we don't care. We want\n-\t * to know which portion of the directory, if any, changed.\n-\t */\n-\tend_of_old = strrchr(old_path, '/');\n-\tend_of_new = strrchr(new_path, '/');\n-\n-\t/*\n-\t * If end_of_old is NULL, old_path wasn't in a directory, so there\n-\t * could not be a directory rename (our rule elsewhere that a\n-\t * directory which still exists is not considered to have been\n-\t * renamed means the root directory can never be renamed -- because\n-\t * the root directory always exists).\n-\t */\n-\tif (end_of_old == NULL)\n-\t\treturn; /* Note: *old_dir and *new_dir are still NULL */\n-\n-\t/*\n-\t * If new_path contains no directory (end_of_new is NULL), then we\n-\t * have a rename of old_path's directory to the root directory.\n-\t */\n-\tif (end_of_new == NULL) {\n-\t\t*old_dir = xstrndup(old_path, end_of_old - old_path);\n-\t\t*new_dir = xstrdup(\"\");\n-\t\treturn;\n-\t}\n-\n-\t/* Find the first non-matching character traversing backwards */\n-\twhile (*--end_of_new == *--end_of_old &&\n-\t end_of_old != old_path &&\n-\t end_of_new != new_path)\n-\t\t; /* Do nothing; all in the while loop */\n-\n-\t/*\n-\t * If both got back to the beginning of their strings, then the\n-\t * directory didn't change at all, only the basename did.\n-\t */\n-\tif (end_of_old == old_path && end_of_new == new_path &&\n-\t *end_of_old == *end_of_new)\n-\t\treturn; /* Note: *old_dir and *new_dir are still NULL */\n-\n-\t/*\n-\t * If end_of_new got back to the beginning of its string, and\n-\t * end_of_old got back to the beginning of some subdirectory, then\n-\t * we have a rename/merge of a subdirectory into the root, which\n-\t * needs slightly special handling.\n-\t *\n-\t * Note: There is no need to consider the opposite case, with a\n-\t * rename/merge of the root directory into some subdirectory\n-\t * because as noted above the root directory always exists so it\n-\t * cannot be considered to be renamed.\n-\t */\n-\tif (end_of_new == new_path &&\n-\t end_of_old != old_path && end_of_old[-1] == '/') {\n-\t\t*old_dir = xstrndup(old_path, --end_of_old - old_path);\n-\t\t*new_dir = xstrdup(\"\");\n-\t\treturn;\n-\t}\n-\n-\t/*\n-\t * We've found the first non-matching character in the directory\n-\t * paths. That means the current characters we were looking at\n-\t * were part of the first non-matching subdir name going back from\n-\t * the end of the strings. Get the whole name by advancing both\n-\t * end_of_old and end_of_new to the NEXT '/' character. That will\n-\t * represent the entire directory rename.\n-\t *\n-\t * The reason for the increment is cases like\n-\t * a/b/star/foo/whatever.c -> a/b/tar/foo/random.c\n-\t * After dropping the basename and going back to the first\n-\t * non-matching character, we're now comparing:\n-\t * a/b/s and a/b/\n-\t * and we want to be comparing:\n-\t * a/b/star/ and a/b/tar/\n-\t * but without the pre-increment, the one on the right would stay\n-\t * a/b/.\n-\t */\n-\tend_of_old = strchr(++end_of_old, '/');\n-\tend_of_new = strchr(++end_of_new, '/');\n-\n-\t/* Copy the old and new directories into *old_dir and *new_dir. */\n-\t*old_dir = xstrndup(old_path, end_of_old - old_path);\n-\t*new_dir = xstrndup(new_path, end_of_new - new_path);\n-}\n-\n static int path_in_way(struct strmap *paths, const char *path, unsigned side_mask)\n {\n \tstruct merged_info *mi = strmap_get(paths, path);\n@@ -1370,6 +1267,14 @@ static char *handle_path_level_conflicts(struct merge_options *opt,\n \treturn new_path;\n }\n \n+static void dirname_munge(char *filename)\n+{\n+\tchar *slash = strrchr(filename, '/');\n+\tif (!slash)\n+\t\tslash = filename;\n+\t*slash = '\\0';\n+}\n+\n static void increment_count(struct strmap *dir_rename_count,\n \t\t\t char *old_dir,\n \t\t\t char *new_dir)\n@@ -1391,6 +1296,76 @@ static void increment_count(struct strmap *dir_rename_count,\n \tstrintmap_incr(counts, new_dir, 1);\n }\n \n+static void update_dir_rename_counts(struct strmap *dir_rename_count,\n+\t\t\t\t struct strset *dirs_removed,\n+\t\t\t\t const char *oldname,\n+\t\t\t\t const char *newname)\n+{\n+\tchar *old_dir = xstrdup(oldname);\n+\tchar *new_dir = xstrdup(newname);\n+\tchar new_dir_first_char = new_dir[0];\n+\tint first_time_in_loop = 1;\n+\n+\twhile (1) {\n+\t\tdirname_munge(old_dir);\n+\t\tdirname_munge(new_dir);\n+\n+\t\t/*\n+\t\t * When renaming\n+\t\t * \"a/b/c/d/e/foo.c\" -> \"a/b/some/thing/else/e/foo.c\"\n+\t\t * then this suggests that both\n+\t\t * a/b/c/d/e/ => a/b/some/thing/else/e/\n+\t\t * a/b/c/d/ => a/b/some/thing/else/\n+\t\t * so we want to increment counters for both. We do NOT,\n+\t\t * however, also want to suggest that there was the following\n+\t\t * rename:\n+\t\t * a/b/c/ => a/b/some/thing/\n+\t\t * so we need to quit at that point.\n+\t\t *\n+\t\t * Note the when first_time_in_loop, we only strip off the\n+\t\t * basename, and we don't care if that's different.\n+\t\t */\n+\t\tif (!first_time_in_loop) {\n+\t\t\tchar *old_sub_dir = strchr(old_dir, '\\0')+1;\n+\t\t\tchar *new_sub_dir = strchr(new_dir, '\\0')+1;\n+\t\t\tif (!*new_dir) {\n+\t\t\t\t/*\n+\t\t\t\t * Special case when renaming to root directory,\n+\t\t\t\t * i.e. when new_dir == \"\". In this case, we had\n+\t\t\t\t * something like\n+\t\t\t\t * a/b/subdir => subdir\n+\t\t\t\t * and so dirname_munge() sets things up so that\n+\t\t\t\t * old_dir = \"a/b\\0subdir\\0\"\n+\t\t\t\t * new_dir = \"\\0ubdir\\0\"\n+\t\t\t\t * We didn't have a '/' to overwrite a '\\0' onto\n+\t\t\t\t * in new_dir, so we have to compare differently.\n+\t\t\t\t */\n+\t\t\t\tif (new_dir_first_char != old_sub_dir[0] ||\n+\t\t\t\t strcmp(old_sub_dir+1, new_sub_dir))\n+\t\t\t\t\tbreak;\n+\t\t\t} else {\n+\t\t\t\tif (strcmp(old_sub_dir, new_sub_dir))\n+\t\t\t\t\tbreak;\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (strset_contains(dirs_removed, old_dir))\n+\t\t\tincrement_count(dir_rename_count, old_dir, new_dir);\n+\t\telse\n+\t\t\tbreak;\n+\n+\t\t/* If we hit toplevel directory (\"\") for old or new dir, quit */\n+\t\tif (!*old_dir || !*new_dir)\n+\t\t\tbreak;\n+\n+\t\tfirst_time_in_loop = 0;\n+\t}\n+\n+\t/* Free resources we don't need anymore */\n+\tfree(old_dir);\n+\tfree(new_dir);\n+}\n+\n static void compute_rename_counts(struct diff_queue_struct *pairs,\n \t\t\t\t struct strmap *dir_rename_count,\n \t\t\t\t struct strset *dirs_removed)\n@@ -1398,19 +1373,11 @@ static void compute_rename_counts(struct diff_queue_struct *pairs,\n \tint i;\n \n \tfor (i = 0; i < pairs->nr; ++i) {\n-\t\tchar *old_dir, *new_dir;\n \t\tstruct diff_filepair *pair = pairs->queue[i];\n \n \t\tif (pair->status != 'R')\n \t\t\tcontinue;\n \n-\t\t/* Get the old and new directory names */\n-\t\tget_renamed_dir_portion(pair->one->path, pair->two->path,\n-\t\t\t\t\t&old_dir, &new_dir);\n-\t\tif (!old_dir)\n-\t\t\t/* Directory didn't change at all; ignore this one. */\n-\t\t\tcontinue;\n-\n \t\t/*\n \t\t * Make dir_rename_count contain a map of a map:\n \t\t * old_directory -> {new_directory -> count}\n@@ -1418,12 +1385,9 @@ static void compute_rename_counts(struct diff_queue_struct *pairs,\n \t\t * the old filename and the new filename and count how many\n \t\t * times that pairing occurs.\n \t\t */\n-\t\tif (strset_contains(dirs_removed, old_dir))\n-\t\t\tincrement_count(dir_rename_count, old_dir, new_dir);\n-\n-\t\t/* Free resources we don't need anymore */\n-\t\tfree(old_dir);\n-\t\tfree(new_dir);\n+\t\tupdate_dir_rename_counts(dir_rename_count, dirs_removed,\n+\t\t\t\t\t pair->one->path,\n+\t\t\t\t\t pair->two->path);\n \t}\n }\n \n-- \n2.29.1.106.g3ff750dc32.dirty\n\n"},{"id":"413407","messageId":"20210104235006.2867404-12-newren@gmail.com","threadId":"54929","inReplyTo":"20210104235006.2867404-1-newren@gmail.com","subject":"[PATCH 11/17] merge-ort: implement apply_dir_rename() and check_dir_renamed()","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-01-04T23:50:00Z","receivedAt":"2021-01-04T23:51:34Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Both of these are copied from merge-recursive.c, with just minor tweaks\ndue to using strmap API and not having a non_unique_new_dir field.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 37 +++++++++++++++++++++++++++++++++++--\n 1 file changed, 35 insertions(+), 2 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 9c9be645ea..f7f2470c96 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -1154,7 +1154,29 @@ struct collision_info {\n static char *apply_dir_rename(struct strmap_entry *rename_info,\n \t\t\t const char *old_path)\n {\n-\tdie(\"Not yet implemented!\");\n+\tstruct strbuf new_path = STRBUF_INIT;\n+\tconst char *old_dir = rename_info->key;\n+\tconst char *new_dir = rename_info->value;\n+\tint oldlen, newlen, new_dir_len;\n+\n+\toldlen = strlen(old_dir);\n+\tif (*new_dir == '\\0')\n+\t\t/*\n+\t\t * If someone renamed/merged a subdirectory into the root\n+\t\t * directory (e.g. 'some/subdir' -> ''), then we want to\n+\t\t * avoid returning\n+\t\t * '' + '/filename'\n+\t\t * as the rename; we need to make old_path + oldlen advance\n+\t\t * past the '/' character.\n+\t\t */\n+\t\toldlen++;\n+\tnew_dir_len = strlen(new_dir);\n+\tnewlen = new_dir_len + (strlen(old_path) - oldlen) + 1;\n+\tstrbuf_grow(&new_path, newlen);\n+\tstrbuf_add(&new_path, new_dir, new_dir_len);\n+\tstrbuf_addstr(&new_path, &old_path[oldlen]);\n+\n+\treturn strbuf_detach(&new_path, NULL);\n }\n \n static void get_renamed_dir_portion(const char *old_path, const char *new_path,\n@@ -1399,7 +1421,18 @@ static void handle_directory_level_conflicts(struct merge_options *opt)\n static struct strmap_entry *check_dir_renamed(const char *path,\n \t\t\t\t\t struct strmap *dir_renames)\n {\n-\tdie(\"Not yet implemented!\");\n+\tchar *temp = xstrdup(path);\n+\tchar *end;\n+\tstruct strmap_entry *e = NULL;\n+\n+\twhile ((end = strrchr(temp, '/'))) {\n+\t\t*end = '\\0';\n+\t\te = strmap_get_entry(dir_renames, temp);\n+\t\tif (e)\n+\t\t\tbreak;\n+\t}\n+\tfree(temp);\n+\treturn e;\n }\n \n static void compute_collisions(struct strmap *collisions,\n-- \n2.29.1.106.g3ff750dc32.dirty\n\n"},{"id":"413408","messageId":"20210104235006.2867404-14-newren@gmail.com","threadId":"54929","inReplyTo":"20210104235006.2867404-1-newren@gmail.com","subject":"[PATCH 13/17] merge-ort: implement handle_path_level_conflicts()","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-01-04T23:50:02Z","receivedAt":"2021-01-04T23:51:36Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This is copied from merge-recursive.c, with minor tweaks due to:\n * using strmap API\n * merge-ort not using the non_unique_new_dir field, since it'll\n obviate its need entirely later with performance improvements\n * adding a new path_in_way() function that uses opt->priv->paths\n instead of doing an expensive tree_has_path() lookup to see if\n a tree has a given path.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 72 ++++++++++++++++++++++++++++++++++++++++++++++++++++-\n 1 file changed, 71 insertions(+), 1 deletion(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 84f4f4776b..d0fb8f4282 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -1282,6 +1282,16 @@ static void get_renamed_dir_portion(const char *old_path, const char *new_path,\n \t*new_dir = xstrndup(new_path, end_of_new - new_path);\n }\n \n+static int path_in_way(struct strmap *paths, const char *path, unsigned side_mask)\n+{\n+\tstruct merged_info *mi = strmap_get(paths, path);\n+\tstruct conflict_info *ci;\n+\tif (!mi)\n+\t\treturn 0;\n+\tINITIALIZE_CI(ci, mi);\n+\treturn mi->clean || (side_mask & (ci->filemask | ci->dirmask));\n+}\n+\n /*\n * See if there is a directory rename for path, and if there are any file\n * level conflicts on the given side for the renamed location. If there is\n@@ -1294,7 +1304,67 @@ static char *handle_path_level_conflicts(struct merge_options *opt,\n \t\t\t\t\t struct strmap_entry *rename_info,\n \t\t\t\t\t struct strmap *collisions)\n {\n-\tdie(\"Not yet implemented\");\n+\tchar *new_path = NULL;\n+\tstruct collision_info *c_info;\n+\tint clean = 1;\n+\tstruct strbuf collision_paths = STRBUF_INIT;\n+\n+\t/*\n+\t * entry has the mapping of old directory name to new directory name\n+\t * that we want to apply to path.\n+\t */\n+\tnew_path = apply_dir_rename(rename_info, path);\n+\tif (!new_path)\n+\t\tBUG(\"Failed to apply directory rename!\");\n+\n+\t/*\n+\t * The caller needs to have ensured that it has pre-populated\n+\t * collisions with all paths that map to new_path. Do a quick check\n+\t * to ensure that's the case.\n+\t */\n+\tc_info = strmap_get(collisions, new_path);\n+\tif (c_info == NULL)\n+\t\tBUG(\"c_info is NULL\");\n+\n+\t/*\n+\t * Check for one-sided add/add/.../add conflicts, i.e.\n+\t * where implicit renames from the other side doing\n+\t * directory rename(s) can affect this side of history\n+\t * to put multiple paths into the same location. Warn\n+\t * and bail on directory renames for such paths.\n+\t */\n+\tif (c_info->reported_already) {\n+\t\tclean = 0;\n+\t} else if (path_in_way(&opt->priv->paths, new_path, 1 << side_index)) {\n+\t\tc_info->reported_already = 1;\n+\t\tstrbuf_add_separated_string_list(&collision_paths, \", \",\n+\t\t\t\t\t\t &c_info->source_files);\n+\t\tpath_msg(opt, new_path, 0,\n+\t\t\t _(\"CONFLICT (implicit dir rename): Existing file/dir \"\n+\t\t\t \"at %s in the way of implicit directory rename(s) \"\n+\t\t\t \"putting the following path(s) there: %s.\"),\n+\t\t new_path, collision_paths.buf);\n+\t\tclean = 0;\n+\t} else if (c_info->source_files.nr > 1) {\n+\t\tc_info->reported_already = 1;\n+\t\tstrbuf_add_separated_string_list(&collision_paths, \", \",\n+\t\t\t\t\t\t &c_info->source_files);\n+\t\tpath_msg(opt, new_path, 0,\n+\t\t\t _(\"CONFLICT (implicit dir rename): Cannot map more \"\n+\t\t\t \"than one path to %s; implicit directory renames \"\n+\t\t\t \"tried to put these paths there: %s\"),\n+\t\t new_path, collision_paths.buf);\n+\t\tclean = 0;\n+\t}\n+\n+\t/* Free memory we no longer need */\n+\tstrbuf_release(&collision_paths);\n+\tif (!clean && new_path) {\n+\t\tfree(new_path);\n+\t\treturn NULL;\n+\t}\n+\n+\treturn new_path;\n }\n \n static void increment_count(struct strmap *dir_rename_count,\n-- \n2.29.1.106.g3ff750dc32.dirty\n\n"},{"id":"413409","messageId":"20210104235006.2867404-17-newren@gmail.com","threadId":"54929","inReplyTo":"20210104235006.2867404-1-newren@gmail.com","subject":"[PATCH 16/17] merge-ort: process_renames() now needs more defensiveness","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-01-04T23:50:05Z","receivedAt":"2021-01-04T23:51:51Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Since directory rename detection adds new paths to opt->priv->paths and\nremoves old ones, process_renames() needs to now check whether\npair->one->path actually exists in opt->priv->paths instead of just\nassuming it does.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 26 +++++++++++++++++++++-----\n 1 file changed, 21 insertions(+), 5 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 115ff6d2d5..480f212cff 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -1829,12 +1829,28 @@ static int process_renames(struct merge_options *opt,\n \t\tconst char *rename_branch = NULL, *delete_branch = NULL;\n \n \t\told_ent = strmap_get_entry(&opt->priv->paths, pair->one->path);\n-\t\toldpath = old_ent->key;\n-\t\toldinfo = old_ent->value;\n-\n \t\tnew_ent = strmap_get_entry(&opt->priv->paths, pair->two->path);\n-\t\tnewpath = new_ent->key;\n-\t\tnewinfo = new_ent->value;\n+\t\tif (old_ent) {\n+\t\t\toldpath = old_ent->key;\n+\t\t\toldinfo = old_ent->value;\n+\t\t}\n+\t\tnewpath = pair->two->path;\n+\t\tif (new_ent) {\n+\t\t\tnewpath = new_ent->key;\n+\t\t\tnewinfo = new_ent->value;\n+\t\t}\n+\n+\t\t/*\n+\t\t * If pair->one->path isn't in opt->priv->paths, that means\n+\t\t * that either directory rename detection removed that\n+\t\t * path, or a parent directory of oldpath was resolved and\n+\t\t * we don't even need the rename; in either case, we can\n+\t\t * skip it. If oldinfo->merged.clean, then the other side\n+\t\t * of history had no changes to oldpath and we don't need\n+\t\t * the rename and can skip it.\n+\t\t */\n+\t\tif (!oldinfo || oldinfo->merged.clean)\n+\t\t\tcontinue;\n \n \t\t/*\n \t\t * diff_filepairs have copies of pathnames, thus we have to\n-- \n2.29.1.106.g3ff750dc32.dirty\n\n"}]}