{"thread":{"id":"58046","subject":"[PATCH 0/3] Fix dual rename into each other plus conflicting adds","startedAt":"2022-06-22T04:21:16Z","lastAt":"2022-07-26T04:48:40Z","messageCount":45,"participants":["Elijah Newren via GitGitGadget","Elijah Newren","Jonathan Tan","Calvin Wan","Ævar Arnfjörð Bjarmason","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"457673","messageId":"pull.1268.git.1655871651.gitgitgadget@gmail.com","threadId":"58046","inReplyTo":null,"subject":"[PATCH 0/3] Fix dual rename into each other plus conflicting adds","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-06-22T04:20:48Z","receivedAt":"2022-06-22T04:21:16Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This series adds some testcases based on the tensorflow repository issue\nreported by Glen Choo at [1], demonstrating bugs in both the ort and\nrecursive strategies. It also provides a fix for the ort strategy.\n\n[1]\nhttps://lore.kernel.org/git/kl6lee006mle.fsf@chooglen-macbookpro.roam.corp.google.com/\n\nElijah Newren (3):\n t6423: add tests of dual directory rename plus add/add conflict\n merge-ort: shuffle the computation and cleanup of potential collisions\n merge-ort: fix issue with dual rename and add/add conflict\n\n merge-ort.c | 60 ++++++++++------\n t/t6423-merge-rename-directories.sh | 102 ++++++++++++++++++++++++++++\n 2 files changed, 142 insertions(+), 20 deletions(-)\n\n\nbase-commit: e54793a95afeea1e10de1e5ad7eab914e7416250\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1268%2Fnewren%2Ffix-dual-rename-into-each-other-plus-conflicting-adds-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1268/newren/fix-dual-rename-into-each-other-plus-conflicting-adds-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/1268\n-- \ngitgitgadget\n"},{"id":"457674","messageId":"69d6204184363e491acb68f744ded0991be63a47.1655871652.git.gitgitgadget@gmail.com","threadId":"58046","inReplyTo":"pull.1268.git.1655871651.gitgitgadget@gmail.com","subject":"[PATCH 1/3] t6423: add tests of dual directory rename plus add/add conflict","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-06-22T04:20:49Z","receivedAt":"2022-06-22T04:21:34Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nThis is an attempt at minimalizing a testcase reported by Glen Choo\nwith tensorflow where merge-ort would report an assertion failure:\n\n Assertion failed: (ci->filemask == 2 || ci->filemask == 4), function apply_directory_rename_modifications, file merge-ort.c, line 2410\n\nreversing the direction of the merge provides a different error:\n\n error: cache entry has null sha1: ...\n fatal: unable to write .git/index\n\nso we add testcases for both. With these new testcases, the\nrecursive strategy differs in that it returns the latter error for\nboth merge directions.\n\nThese testcases are somehow a little different than Glen's original\ntensorflow testcase in that these ones trigger a bug with the recursive\nalgorithm whereas his testcase didn't. I figure that means these\ntestcases somehow manage to be more comprehensive.\n\nReported-by: Glen Choo \nSigned-off-by: Elijah Newren \n---\n t/t6423-merge-rename-directories.sh | 102 ++++++++++++++++++++++++++++\n 1 file changed, 102 insertions(+)\n\ndiff --git a/t/t6423-merge-rename-directories.sh b/t/t6423-merge-rename-directories.sh\nindex 479db32cd62..296c04f8046 100755\n--- a/t/t6423-merge-rename-directories.sh\n+++ b/t/t6423-merge-rename-directories.sh\n@@ -5199,6 +5199,108 @@ test_expect_success '12k: Directory rename with sibling causes rename-to-self' '\n \t)\n '\n \n+# Testcase 12l, Both sides rename a directory into the other side, both add\n+# a file with after directory renames are the same filename\n+# Commit O: sub1/file, sub2/other\n+# Commit A: sub3/file, sub2/{other, new_add_add_file_1}\n+# Commit B: sub1/{file, newfile}, sub1/sub2/{other, new_add_add_file_2}\n+#\n+# In words:\n+# A: sub1/ -> sub3/, add sub2/new_add_add_file_1\n+# B: sub2/ -> sub1/sub2, add sub1/newfile, add sub1/sub2/new_add_add_file_2\n+#\n+# Expected: sub3/{file, newfile, sub2/other}\n+# CONFLICT (add/add): sub3/sub2/new_add_add_file\n+\n+test_setup_12l () {\n+\ttest_create_repo 12l_$1 &&\n+\t(\n+\t\tcd 12l_$1 &&\n+\n+\t\tmkdir -p sub1 sub2\n+\t\techo file >sub1/file &&\n+\t\techo other >sub2/other &&\n+\t\tgit add sub1 sub2 &&\n+\t\tgit commit -m \"O\" &&\n+\n+\t\tgit branch O &&\n+\t\tgit branch A &&\n+\t\tgit branch B &&\n+\n+\t\tgit checkout A &&\n+\t\tgit mv sub1 sub3 &&\n+\t\techo conflicting >sub2/new_add_add_file &&\n+\t\tgit add sub2 &&\n+\t\ttest_tick &&\n+\t\tgit add -u &&\n+\t\tgit commit -m \"A\" &&\n+\n+\t\tgit checkout B &&\n+\t\techo dissimilar >sub2/new_add_add_file &&\n+\t\techo brand >sub1/newfile &&\n+\t\tgit add sub1 sub2 &&\n+\t\tgit mv sub2 sub1 &&\n+\t\ttest_tick &&\n+\t\tgit commit -m \"B\"\n+\t)\n+}\n+\n+test_expect_merge_algorithm failure failure '12l (B into A): Rename into each other + add/add conflict' '\n+\ttest_setup_12l BintoA &&\n+\t(\n+\t\tcd 12l_BintoA &&\n+\n+\t\tgit checkout -q A^0 &&\n+\n+\t\ttest_must_fail git -c merge.directoryRenames=true merge -s recursive B^0 &&\n+\n+\t\tgit ls-files -s >out &&\n+\t\ttest_line_count = 5 out &&\n+\n+\t\tgit rev-parse >actual \\\n+\t\t\t:0:sub3/file :0:sub3/newfile :0:sub3/sub2/other \\\n+\t\t\t:2:sub1/sub2/new_add_add_file \\\n+\t\t\t:3:sub1/sub2/new_add_add_file &&\n+\t\tgit rev-parse >expect \\\n+\t\t\tO:sub1/file B:sub1/newfile O:sub2/other \\\n+\t\t\tA:sub2/new_add_add_file \\\n+\t\t\tB:sub1/sub2/new_add_add_file &&\n+\t\ttest_cmp expect actual &&\n+\n+\t\tgit ls-files -o >actual &&\n+\t\ttest_write_lines actual expect out >expect &&\n+\t\ttest_cmp expect actual\n+\t)\n+'\n+\n+test_expect_merge_algorithm failure failure '12l (A into B): Rename into each other + add/add conflict' '\n+\ttest_setup_12l AintoB &&\n+\t(\n+\t\tcd 12l_AintoB &&\n+\n+\t\tgit checkout -q B^0 &&\n+\n+\t\ttest_must_fail git -c merge.directoryRenames=true merge -s recursive A^0 &&\n+\n+\t\tgit ls-files -s >out &&\n+\t\ttest_line_count = 5 out &&\n+\n+\t\tgit rev-parse >actual \\\n+\t\t\t:0:sub3/file :0:sub3/newfile :0:sub3/sub2/other \\\n+\t\t\t:2:sub1/sub2/new_add_add_file \\\n+\t\t\t:3:sub1/sub2/new_add_add_file &&\n+\t\tgit rev-parse >expect \\\n+\t\t\tO:sub1/file B:sub1/newfile O:sub2/other \\\n+\t\t\tB:sub1/sub2/new_add_add_file \\\n+\t\t\tA:sub2/new_add_add_file &&\n+\t\ttest_cmp expect actual &&\n+\n+\t\tgit ls-files -o >actual &&\n+\t\ttest_write_lines actual expect out >expect &&\n+\t\ttest_cmp expect actual\n+\t)\n+'\n+\n ###########################################################################\n # SECTION 13: Checking informational and conflict messages\n #\n-- \ngitgitgadget\n\n"},{"id":"457675","messageId":"d8c13e56209ebb6d1d3c521b6522a1bc64909108.1655871652.git.gitgitgadget@gmail.com","threadId":"58046","inReplyTo":"pull.1268.git.1655871651.gitgitgadget@gmail.com","subject":"[PATCH 2/3] merge-ort: shuffle the computation and cleanup of potential collisions","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-06-22T04:20:50Z","receivedAt":"2022-06-22T04:21:54Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nRun compute_collisions() for renames on both sides of history before\nany calls to collect_renames(), and do not free the computed collisions\nuntil after both calls to collect_renames(). This is just a code\nreorganization at this point that doesn't make sense on its own, but\nwill permit us to use the computed collision info from both sides\nwithin each call to collect_renames() in a subsequent commit.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 56 ++++++++++++++++++++++++++++++++++-------------------\n 1 file changed, 36 insertions(+), 20 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 8545354dafd..fa6667de18c 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2259,6 +2259,27 @@ static void compute_collisions(struct strmap *collisions,\n \t}\n }\n \n+static void free_collisions(struct strmap *collisions)\n+{\n+\tstruct hashmap_iter iter;\n+\tstruct strmap_entry *entry;\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+}\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@@ -2314,7 +2335,8 @@ static char *check_for_directory_rename(struct merge_options *opt,\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\t\t\t\t rename_info,\n+\t\t\t\t\t &collisions[side_index]);\n \t*clean_merge &= (new_path != NULL);\n \n \treturn new_path;\n@@ -3023,18 +3045,15 @@ static int detect_regular_renames(struct merge_options *opt,\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 struct strmap *collisions,\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@@ -3050,7 +3069,7 @@ static int collect_renames(struct merge_options *opt,\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 collisions,\n \t\t\t\t\t\t &clean);\n \n \t\tpossibly_cache_new_pair(renames, p, side_index, new_path);\n@@ -3076,20 +3095,6 @@ 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@@ -3100,6 +3105,7 @@ static int detect_and_process_renames(struct merge_options *opt,\n {\n \tstruct diff_queue_struct combined = { 0 };\n \tstruct rename_info *renames = &opt->priv->renames;\n+\tstruct strmap collisions[3];\n \tint need_dir_renames, s, i, clean = 1;\n \tunsigned detection_run = 0;\n \n@@ -3149,12 +3155,22 @@ 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+\tfor (int i = MERGE_SIDE1; i <= MERGE_SIDE2; i++) {\n+\t\tint other_side = 3 - i;\n+\t\tcompute_collisions(&collisions[i],\n+\t\t\t\t &renames->dir_renames[other_side],\n+\t\t\t\t &renames->pairs[i]);\n+\t}\n \tclean &= collect_renames(opt, &combined, MERGE_SIDE1,\n+\t\t\t\t collisions,\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 collisions,\n \t\t\t\t &renames->dir_renames[1],\n \t\t\t\t &renames->dir_renames[2]);\n+\tfor (int i = MERGE_SIDE1; i <= MERGE_SIDE2; i++)\n+\t\tfree_collisions(&collisions[i]);\n \tSTABLE_QSORT(combined.queue, combined.nr, compare_pairs);\n \ttrace2_region_leave(\"merge\", \"directory renames\", opt->repo);\n \n-- \ngitgitgadget\n\n"},{"id":"457676","messageId":"bb2badccb71d76efe0e47431246376b1e7016b05.1655871652.git.gitgitgadget@gmail.com","threadId":"58046","inReplyTo":"pull.1268.git.1655871651.gitgitgadget@gmail.com","subject":"[PATCH 3/3] merge-ort: fix issue with dual rename and add/add conflict","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-06-22T04:20:51Z","receivedAt":"2022-06-22T04:22:09Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nThere is code in both merge-recursive and merge-ort for avoiding doubly\ntransitive renames (i.e. one side renames directory A/ -> B/, and the\nother side renames directory B/ -> C/), because this combination would\notherwise make a mess for new files added to A/ on the first side and\nwondering which directory they end up in -- especially if there were\neven more renames such as the first side renaming C/ -> D/. In such\ncases, it just turns \"off\" directory rename detection for the higher\norder transitive cases.\n\nThe testcases added in t6423 a couple commits ago are slightly different\nbut similar in principle. They involve a similar case of paired\nrenaming but instead of A/ -> B/ and B/ -> C/, the second side renames\na leading directory of B/ to C/. And both sides add a new file\nsomewhere under the directory that the other side will rename. While\nthe new files added start within different directories and thus could\nlogically end up within different directories, it is weird for a file\non one side to end up where the other one started and not move along\nwith it. So, let's just turn off directory rename detection in this\ncase as well.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 4 ++++\n t/t6423-merge-rename-directories.sh | 4 ++--\n 2 files changed, 6 insertions(+), 2 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex fa6667de18c..5bcb9a4980b 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2292,9 +2292,13 @@ static char *check_for_directory_rename(struct merge_options *opt,\n \tstruct strmap_entry *rename_info;\n \tstruct strmap_entry *otherinfo = NULL;\n \tconst char *new_dir;\n+\tint other_side = 3 - side_index;\n \n+\t/* Cases where there is no new path, so we return NULL */\n \tif (strmap_empty(dir_renames))\n \t\treturn new_path;\n+\tif (strmap_get(&collisions[other_side], path))\n+\t\treturn new_path;\n \trename_info = check_dir_renamed(path, dir_renames);\n \tif (!rename_info)\n \t\treturn new_path;\ndiff --git a/t/t6423-merge-rename-directories.sh b/t/t6423-merge-rename-directories.sh\nindex 296c04f8046..4286ae987c4 100755\n--- a/t/t6423-merge-rename-directories.sh\n+++ b/t/t6423-merge-rename-directories.sh\n@@ -5245,7 +5245,7 @@ test_setup_12l () {\n \t)\n }\n \n-test_expect_merge_algorithm failure failure '12l (B into A): Rename into each other + add/add conflict' '\n+test_expect_merge_algorithm failure success '12l (B into A): Rename into each other + add/add conflict' '\n \ttest_setup_12l BintoA &&\n \t(\n \t\tcd 12l_BintoA &&\n@@ -5273,7 +5273,7 @@ test_expect_merge_algorithm failure failure '12l (B into A): Rename into each ot\n \t)\n '\n \n-test_expect_merge_algorithm failure failure '12l (A into B): Rename into each other + add/add conflict' '\n+test_expect_merge_algorithm failure success '12l (A into B): Rename into each other + add/add conflict' '\n \ttest_setup_12l AintoB &&\n \t(\n \t\tcd 12l_AintoB &&\n-- \ngitgitgadget\n"},{"id":"457678","messageId":"CABPp-BFiw3szsGDkhN4+Q0_JDNkEQoB6CuGj+39ryL7ToNgP1A@mail.gmail.com","threadId":"58046","inReplyTo":"pull.1268.git.1655871651.gitgitgadget@gmail.com","subject":"Re: [PATCH 0/3] Fix dual rename into each other plus conflicting adds","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2022-06-22T04:36:03Z","receivedAt":"2022-06-22T04:36:18Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Tue, Jun 21, 2022 at 9:21 PM Elijah Newren via GitGitGadget\n wrote:\n>\n> This series adds some testcases based on the tensorflow repository issue\n> reported by Glen Choo at [1], demonstrating bugs in both the ort and\n> recursive strategies. It also provides a fix for the ort strategy.\n\nAlso, just to be clear, this is not a regression since 2.36. It's\nbeen with the ort strategy since it was introduced, and with the\nrecursive strategy for a number of years.\n"},{"id":"457924","messageId":"20220627182024.1358144-1-jonathantanmy@google.com","threadId":"58046","inReplyTo":"69d6204184363e491acb68f744ded0991be63a47.1655871652.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/3] t6423: add tests of dual directory rename plus add/add conflict","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2022-06-27T18:20:23Z","receivedAt":"2022-06-27T18:20:33Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"\"Elijah Newren via GitGitGadget\" writes:\n\n> From: Elijah Newren \n> \n> This is an attempt at minimalizing a testcase reported by Glen Choo\n> with tensorflow where merge-ort would report an assertion failure:\n> \n> Assertion failed: (ci->filemask == 2 || ci->filemask == 4), function apply_directory_rename_modifications, file merge-ort.c, line 2410\n\nFirst of all, thanks for this fix - I've verified with Glen Choo's test\ncases and it does fix it.\n\n> diff --git a/t/t6423-merge-rename-directories.sh b/t/t6423-merge-rename-directories.sh\n> index 479db32cd62..296c04f8046 100755\n> --- a/t/t6423-merge-rename-directories.sh\n> +++ b/t/t6423-merge-rename-directories.sh\n> @@ -5199,6 +5199,108 @@ test_expect_success '12k: Directory rename with sibling causes rename-to-self' '\n> \t)\n> '\n> \n> +# Testcase 12l, Both sides rename a directory into the other side, both add\n> +# a file with after directory renames are the same filename\n> +# Commit O: sub1/file, sub2/other\n> +# Commit A: sub3/file, sub2/{other, new_add_add_file_1}\n> +# Commit B: sub1/{file, newfile}, sub1/sub2/{other, new_add_add_file_2}\n> +#\n> +# In words:\n> +# A: sub1/ -> sub3/, add sub2/new_add_add_file_1\n> +# B: sub2/ -> sub1/sub2, add sub1/newfile, add sub1/sub2/new_add_add_file_2\n> +#\n> +# Expected: sub3/{file, newfile, sub2/other}\n> +# CONFLICT (add/add): sub3/sub2/new_add_add_file\n\nThe \"expected\" might need to be updated. After all patches are applied,\nthis is the tree I get (note that it's \"sub1/sub2/new_add_add_file, not\n\"sub3/sub2/new_add_add_file\"):\n\n .\n |-- sub1\n | `-- sub2\n | `-- new_add_add_file\n `-- sub3\n |-- file\n |-- newfile\n `-- sub2\n `-- other\n\nAlso, at first glance, \"newfile\" shouldn't belong in a minimal\nreproduction, but it somehow changes the output. When I apply this diff\n(to the state after all patches are applied):\n\n diff --git a/t/t6423-merge-rename-directories.sh b/t/t6423-merge-rename-directories.sh\n index 4286ae987c..9472fb7233 100755\n --- a/t/t6423-merge-rename-directories.sh\n +++ b/t/t6423-merge-rename-directories.sh\n @@ -5237,7 +5237,6 @@ test_setup_12l () {\n \n git checkout B &&\n echo dissimilar >sub2/new_add_add_file &&\n - echo brand >sub1/newfile &&\n git add sub1 sub2 &&\n git mv sub2 sub1 &&\n test_tick &&\n @@ -5255,14 +5254,14 @@ test_expect_merge_algorithm failure success '12l (B into A): Rename into each ot\n test_must_fail git -c merge.directoryRenames=true merge -s recursive B^0 &&\n \n git ls-files -s >out &&\n - test_line_count = 5 out &&\n + test_line_count = 4 out &&\n \n git rev-parse >actual \\\n - :0:sub3/file :0:sub3/newfile :0:sub3/sub2/other \\\n + :0:sub3/file :0:sub3/sub2/other \\\n :2:sub1/sub2/new_add_add_file \\\n :3:sub1/sub2/new_add_add_file &&\n git rev-parse >expect \\\n - O:sub1/file B:sub1/newfile O:sub2/other \\\n + O:sub1/file O:sub2/other \\\n A:sub2/new_add_add_file \\\n B:sub1/sub2/new_add_add_file &&\n test_cmp expect actual &&\n\nI get:\n\n .\n |-- sub1\n | `-- sub2\n | |-- new_add_add_file\n | `-- other\n `-- sub3\n `-- file\n\n(Note the path to \"other\".) I haven't figured out what's going on,\nthough.\n"},{"id":"457956","messageId":"20220627184744.1361309-1-jonathantanmy@google.com","threadId":"58046","inReplyTo":"bb2badccb71d76efe0e47431246376b1e7016b05.1655871652.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 3/3] merge-ort: fix issue with dual rename and add/add conflict","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2022-06-27T18:47:44Z","receivedAt":"2022-06-27T18:48:09Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"\"Elijah Newren via GitGitGadget\" writes:\n> The testcases added in t6423 a couple commits ago are slightly different\n> but similar in principle. They involve a similar case of paired\n> renaming but instead of A/ -> B/ and B/ -> C/, the second side renames\n> a leading directory of B/ to C/. \n\nHmm...one side moved sub1 -> sub3 and the other moved sub2 from the root\nto under sub1, right? So it's more like A/ -> B/ and C/ -> A/C/.\n\n> And both sides add a new file\n> somewhere under the directory that the other side will rename. \n\nRename or move, I think.\n\n> While\n> the new files added start within different directories and thus could\n> logically end up within different directories, it is weird for a file\n> on one side to end up where the other one started and not move along\n> with it. So, let's just turn off directory rename detection in this\n> case as well.\n\nMakes sense.\n\n> diff --git a/merge-ort.c b/merge-ort.c\n> index fa6667de18c..5bcb9a4980b 100644\n> --- a/merge-ort.c\n> +++ b/merge-ort.c\n> @@ -2292,9 +2292,13 @@ static char *check_for_directory_rename(struct merge_options *opt,\n> \tstruct strmap_entry *rename_info;\n> \tstruct strmap_entry *otherinfo = NULL;\n> \tconst char *new_dir;\n> +\tint other_side = 3 - side_index;\n> \n> +\t/* Cases where there is no new path, so we return NULL */\n\nWhat do you mean by \"no new path\"?\n\n> \tif (strmap_empty(dir_renames))\n> \t\treturn new_path;\n> +\tif (strmap_get(&collisions[other_side], path))\n> +\t\treturn new_path;\n\nSo as far as I understand, collisions here, for a given side, is a map.\nThe map's keys are all the filenames of added and renamed files (I'm\nassuming that's what 'A' and 'R' are) from that side after any directory\nmoves on the other side are applied. So, for example, if we add \"foo/a\"\non side A and rename \"foo/\" to \"bar/\" on side B, then side A's collision\nmap would have a key \"bar/a\". So I'm not sure if \"collision\" is the\nright name here, but the existing code already uses it so I'll leave it\nbe.\n\nIt makes sense that this situation (of side A having \"bar/a\" because\nside B renamed \"foo/\" to \"bar/\", and at the same time, side B adds its\nown \"bar/a\") is weird, as stated in the commit message, so I don't mind\ndisabling checking for directory rename in this case. However, in\ntheory, I don't see how disabling this check would fix anything, since\nthe bug seems to be about two different files on different sides being\nrenamed to the same filename through some convoluted means. (Unless this\nis the only convoluted means to do it, and disabling it means that the\nbug wouldn't occur.)\n"},{"id":"457957","messageId":"20220627184847.1361980-1-jonathantanmy@google.com","threadId":"58046","inReplyTo":"d8c13e56209ebb6d1d3c521b6522a1bc64909108.1655871652.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 2/3] merge-ort: shuffle the computation and cleanup of potential collisions","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2022-06-27T18:48:47Z","receivedAt":"2022-06-27T18:48:52Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"\"Elijah Newren via GitGitGadget\" writes:\n> @@ -2314,7 +2335,8 @@ static char *check_for_directory_rename(struct merge_options *opt,\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\t\t\t\t rename_info,\n> +\t\t\t\t\t &collisions[side_index]);\n\nIs this a fix of a latent bug? handle_path_level_conflicts() is not\nchanged in this patch.\n"},{"id":"457964","messageId":"20220627210406.2802452-1-calvinwan@google.com","threadId":"58046","inReplyTo":"20220627184847.1361980-1-jonathantanmy@google.com","subject":"Re: [PATCH 2/3] merge-ort: shuffle the computation and cleanup of potential collisions","fromName":"Calvin Wan","fromEmail":"calvinwan@google.com","sentAt":"2022-06-27T21:04:06Z","receivedAt":"2022-06-27T21:04:22Z","isPatch":true,"sender":{"key":"calvinwan@google.com","avatar":"https://avatars.githubusercontent.com/u/92547554?v=4"},"body":"Jonathan Tan writes:\n> \"Elijah Newren via GitGitGadget\" writes:\n> > @@ -2314,7 +2335,8 @@ static char *check_for_directory_rename(struct merge_options *opt,\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\t\t\t\t rename_info,\n> > +\t\t\t\t\t &collisions[side_index]);\n> \n> Is this a fix of a latent bug? handle_path_level_conflicts() is not\n> changed in this patch.\n> \n\nI don't think so. IIUC this is what's happening given the callstack:\n\ndetect_and_process_renames()\n - Now defines `struct strmap collisions[3];` and computes all\n three collisions here\n - Passes collisions into collect_renames()\ncollect_renames()\n - Originally defined as `struct strmap collisions;` and computed\n collisions in here\n - Now takes collisions as an argument\n - Passes collisions into check_for_directory_rename()\ncheck_for_directory_rename()\n - Collisions isn't used in this function at all except to pass into\n handle_path_level_conflicts\nhandle_path_level_conflicts()\n - Expecting pointer to singular collisions, not an array so side_index\n is now required\n"},{"id":"457974","messageId":"20220627223017.2852209-1-calvinwan@google.com","threadId":"58046","inReplyTo":"69d6204184363e491acb68f744ded0991be63a47.1655871652.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/3] t6423: add tests of dual directory rename plus add/add conflict","fromName":"Calvin Wan","fromEmail":"calvinwan@google.com","sentAt":"2022-06-27T22:30:17Z","receivedAt":"2022-06-27T22:30:36Z","isPatch":true,"sender":{"key":"calvinwan@google.com","avatar":"https://avatars.githubusercontent.com/u/92547554?v=4"},"body":"\"Elijah Newren via GitGitGadget\" writes:\n> +# Testcase 12l, Both sides rename a directory into the other side, both add\n> +# a file with after directory renames are the same filename\n> +# Commit O: sub1/file, sub2/other\n> +# Commit A: sub3/file, sub2/{other, new_add_add_file_1}\n> +# Commit B: sub1/{file, newfile}, sub1/sub2/{other, new_add_add_file_2}\n> +#\n> +# In words:\n> +# A: sub1/ -> sub3/, add sub2/new_add_add_file_1\n> +# B: sub2/ -> sub1/sub2, add sub1/newfile, add sub1/sub2/new_add_add_file_2\n> +#\n> +# Expected: sub3/{file, newfile, sub2/other}\n> +# CONFLICT (add/add): sub3/sub2/new_add_add_file\n\nGrammatically, I could not understand\n\n\"both add a file with after directory renames are the same filename\"\n\nI also found the same issue with `Expected` that Jonathan mentions. I ran the\ncommand separately and got\n\nCONFLICT (add/add): Merge conflict in sub1/sub2/new_add_add_file\n"},{"id":"458138","messageId":"CABPp-BG8r4zUOKZ+DzZOdsEwr+580cK=SvZ4n_euPOV1Nocu+A@mail.gmail.com","threadId":"58046","inReplyTo":"20220627184744.1361309-1-jonathantanmy@google.com","subject":"Re: [PATCH 3/3] merge-ort: fix issue with dual rename and add/add conflict","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2022-06-30T00:05:22Z","receivedAt":"2022-06-30T00:05:39Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Mon, Jun 27, 2022 at 11:47 AM Jonathan Tan wrote:\n>\n> \"Elijah Newren via GitGitGadget\" writes:\n> > The testcases added in t6423 a couple commits ago are slightly different\n> > but similar in principle. They involve a similar case of paired\n> > renaming but instead of A/ -> B/ and B/ -> C/, the second side renames\n> > a leading directory of B/ to C/.\n>\n> Hmm...one side moved sub1 -> sub3 and the other moved sub2 from the root\n> to under sub1, right? So it's more like A/ -> B/ and C/ -> A/C/.\n\nHmm, maybe I should have been more explicit in my mapping:\n A = sub2\n B = sub1/sub2\n leading directory of B = sub1\n C = sub3\n\n> > And both sides add a new file\n> > somewhere under the directory that the other side will rename.\n>\n> Rename or move, I think.\n\nI'm confused; I don't understand what this comment means. Renames\ntend to be created using \"git mv\", before or after making content\nchanges, so to me a file being renamed or a file being moved to a\ndifferent location are synonymous. What distinction are you making\nbetween renames and moves?\n\n> > While\n> > the new files added start within different directories and thus could\n> > logically end up within different directories, it is weird for a file\n> > on one side to end up where the other one started and not move along\n> > with it. So, let's just turn off directory rename detection in this\n> > case as well.\n>\n> Makes sense.\n>\n> > diff --git a/merge-ort.c b/merge-ort.c\n> > index fa6667de18c..5bcb9a4980b 100644\n> > --- a/merge-ort.c\n> > +++ b/merge-ort.c\n> > @@ -2292,9 +2292,13 @@ static char *check_for_directory_rename(struct merge_options *opt,\n> > struct strmap_entry *rename_info;\n> > struct strmap_entry *otherinfo = NULL;\n> > const char *new_dir;\n> > + int other_side = 3 - side_index;\n> >\n> > + /* Cases where there is no new path, so we return NULL */\n>\n> What do you mean by \"no new path\"?\n\nHmm, perhaps I should change this to:\n\n/* Cases where we don't have or don't want a directory rename for this\npath, so we return NULL */\n\nThe purpose of this function is to check whether a given path would be\nmodified by directory renaming to get a new path. So, \"no new path\"\nmeans we don't have an applicable directory rename or don't want to\nuse it.\n\n> > if (strmap_empty(dir_renames))\n> > return new_path;\n> > + if (strmap_get(&collisions[other_side], path))\n> > + return new_path;\n>\n> So as far as I understand, collisions here, for a given side, is a map.\n> The map's keys are all the filenames of added and renamed files (I'm\n> assuming that's what 'A' and 'R' are) from that side after any directory\n> moves on the other side are applied. So, for example, if we add \"foo/a\"\n> on side A and rename \"foo/\" to \"bar/\" on side B, then side A's collision\n> map would have a key \"bar/a\". So I'm not sure if \"collision\" is the\n> right name here, but the existing code already uses it so I'll leave it\n> be.\n\nLet's take your example a bit further, to discuss the original kind of\nusecase that \"collisions\" was written for. In addition to adding\n\"foo/a\" on side A, we also add \"foo2/a\" and \"foo3/a\". And then in\naddition to renaming \"foo/\" to \"bar/\" on side B, we also rename\n\"foo2/\" to \"bar/\" and \"foo3/\" to \"bar/\", thus merging all of foo/,\nfoo2/, and foo3/ into a single directory named bar/. If the files in\nfoo/, foo2/, and foo3/ on side B were all unique, you can see how\nthere'd be no problem merging these directories together. The problem\nonly comes at merge time when you attempt to apply the directory\nrenames from side B to the new files on side A. That's when you get\ncollisions, in this case three files that would be named bar/a.\n\nChecking for such collisions was the purpose of the \"collisions\"\nmetadata, so I think the name is fitting. The only problem is that\nwe're reusing that data now for a slightly different purpose, though I\nthink it's still \"collision-y\".\n\n> It makes sense that this situation (of side A having \"bar/a\" because\n> side B renamed \"foo/\" to \"bar/\", and at the same time, side B adds its\n> own \"bar/a\") is weird, as stated in the commit message, so I don't mind\n> disabling checking for directory rename in this case. However, in\n> theory, I don't see how disabling this check would fix anything, since\n> the bug seems to be about two different files on different sides being\n> renamed to the same filename through some convoluted means. (Unless this\n> is the only convoluted means to do it, and disabling it means that the\n> bug wouldn't occur.)\n\nHmm...let me see if I can explain this a different way.\n\nThe short version of the issue here is that if a directory rename\nwants to rename NEWFILE -> ALTERNATE_NEWFILE, but there is another\ndirectory rename on the other side of history that wants to rename\nANOTHER_FILE -> NEWFILE, then we run into problems and have to turn\noff the NEWFILE -> ALTERNATE_NEWFILE. This check here is all about\nthis case.\n\nTo see why this is the problematic setup...\n\nThe primary data structure in merge-ort is opt->priv->paths, a strmap\nwhich maps: (path involved in the merge) -> (conflict_info).\n(Technically, it could have a merged_info instead of a conflict_info\nif the file was trivially resolvable early on but since merged_info is\nthe first entry in a conflict_info, logically it can still be thought\nof as a conflict_info just with less data.). Now a conflict_info\nstores information about the OIDs and modes for all three sides of the\nmerge (i.e. both sides of the merge and the base). Whenever a rename\nis processed, we have to update this map, because the rename makes the\nconflict_info now apply to a different path. In the simple cases, the\nconflict_info from the source path needs to be merged with the\nconflict_info for the target path, and the source path's conflict_info\nneeds to be marked as null (literally setting the .is_null field to\n1). rename/rename and such can make this a bit more complicated.\n\nNormally, directory renames would actually be a simpler case for this\nmerging of conflict_info structs rather than a more complicated case.\nThere cannot be a directory rename if the directory exists on both\nsides, so we don't need to worry about there already being a file on\nthe other side whose conflict_info we need to merge with the source\nconflict_info. So, the code just added an assertion that there wasn't\none. The problem is, that _another_ directory rename for the other\nside of history can move a file into the way of where our directory\nrename wants to operate on. Let's jump into the example testcase I\nadded to make this more concrete:\n\n # Commit O: sub1/file, sub2/other\n # Commit A: sub3/file, sub2/{other, new_add_add_file_1}\n # Commit B: sub1/{file, newfile}, sub1/sub2/{other, new_add_add_file_2}\n #\n # In words:\n # A: sub1/ -> sub3/, add sub2/new_add_add_file_1\n # B: sub2/ -> sub1/sub2, add sub1/newfile, add\nsub1/sub2/new_add_add_file_2\n\nHere, the sub2/sub1/sub2/ rename on sideB will rename A's\nsub2/new_add_add_file to sub1/sub2/new_add_add_file, which is at the\nsame location as B's sub1/sub2/new_add_add_file (and which A's sub1/\n-> sub3/ directory rename would normally operate on).\n\nGiven our opt->priv->paths data structure, if we wanted to let both\ndirectory renames take effect, then the order would matter:\n\n* If the sub1/ -> sub3/ directory rename is applied first, then:\n * B's sub1/sub2/new_add_add_file gets renamed to sub3/sub2/new_add_add_file\n * sub1/sub2/new_add_add_file is marked as .is_null=1\n * A's sub2/new_add_add_file gets renamed to\nsub1/sub2/new_add_add_file (which was already marked as null)\n\nThis set of steps seems to trigger the \"error: cache entry has null\nsha1\" fatal error I mentioned earlier. In contrast, if we take the\nother order:\n\n* If the sub2/ -> sub1/sub2/ rename is applied first, then:\n * A's sub2/new_add_add_file gets renamed to sub1/sub2/new_add_add_file\n * the conflict_info for the two sub1/sub2/new_add_add_file's are now merged\n * the sub1/ -> sub3/ directory rename is applied to move this file\nto sub3/sub2/new_add_add_file\n\nThis second order may not sound so bad. And, in fact, you can get\nthis behavior simply by relaxing (or commenting out) the assertion\nGlen reported hitting. However, that results in making the merge have\na fatal error when you reverse its direction (i.e. when swapping HEAD\nand MERGE_HEAD), and seems somewhat confusing to me given that A's\nsub2/new_add_add_file was renamed twice, going against the general\n\"avoid-mutiply-transitive-renames\" rule employed elsewhere in\ndirectory rename detection.\n\nTo avoid this order dependence, and the weird multiple-renaming of a\nsingle path, we just want to turn off directory renames when the\nsource of a directory rename on one side is the target of a directory\nrename on the other. That's what this patch does.\n\n\nDoes that help? Or did I make it more confusing?\n"},{"id":"458139","messageId":"CABPp-BGycqhbhYtM+kzB5zLSX0sZ_rwz_DagDkp4oJQbZgS-ew@mail.gmail.com","threadId":"58046","inReplyTo":"20220627210406.2802452-1-calvinwan@google.com","subject":"Re: [PATCH 2/3] merge-ort: shuffle the computation and cleanup of potential collisions","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2022-06-30T00:05:40Z","receivedAt":"2022-06-30T00:05:57Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Mon, Jun 27, 2022 at 2:04 PM Calvin Wan wrote:\n>\n> Jonathan Tan writes:\n> > \"Elijah Newren via GitGitGadget\" writes:\n> > > @@ -2314,7 +2335,8 @@ static char *check_for_directory_rename(struct merge_options *opt,\n> > > }\n> > >\n> > > new_path = handle_path_level_conflicts(opt, path, side_index,\n> > > - rename_info, collisions);\n> > > + rename_info,\n> > > + &collisions[side_index]);\n> >\n> > Is this a fix of a latent bug? handle_path_level_conflicts() is not\n> > changed in this patch.\n> >\n>\n> I don't think so. IIUC this is what's happening given the callstack:\n>\n> detect_and_process_renames()\n> - Now defines `struct strmap collisions[3];` and computes all\n> three collisions here\n> - Passes collisions into collect_renames()\n> collect_renames()\n> - Originally defined as `struct strmap collisions;` and computed\n> collisions in here\n> - Now takes collisions as an argument\n> - Passes collisions into check_for_directory_rename()\n> check_for_directory_rename()\n> - Collisions isn't used in this function at all except to pass into\n> handle_path_level_conflicts\n> handle_path_level_conflicts()\n> - Expecting pointer to singular collisions, not an array so side_index\n> is now required\n\nSweet, thanks for answering for me. This is exactly right.\n"},{"id":"458140","messageId":"CABPp-BGtKQVgaf9ttwRMAE6AvH1QC3TqFcFwiAOpnm-SqKnNCQ@mail.gmail.com","threadId":"58046","inReplyTo":"20220627182024.1358144-1-jonathantanmy@google.com","subject":"Re: [PATCH 1/3] t6423: add tests of dual directory rename plus add/add conflict","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2022-06-30T00:06:51Z","receivedAt":"2022-06-30T00:07:10Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Mon, Jun 27, 2022 at 11:20 AM Jonathan Tan wrote:\n>\n> \"Elijah Newren via GitGitGadget\" writes:\n>\n> > From: Elijah Newren \n> >\n> > This is an attempt at minimalizing a testcase reported by Glen Choo\n> > with tensorflow where merge-ort would report an assertion failure:\n> >\n> > Assertion failed: (ci->filemask == 2 || ci->filemask == 4), function apply_directory_rename_modifications, file merge-ort.c, line 2410\n>\n> First of all, thanks for this fix - I've verified with Glen Choo's test\n> cases and it does fix it.\n\n:-)\n\n> > diff --git a/t/t6423-merge-rename-directories.sh b/t/t6423-merge-rename-directories.sh\n> > index 479db32cd62..296c04f8046 100755\n> > --- a/t/t6423-merge-rename-directories.sh\n> > +++ b/t/t6423-merge-rename-directories.sh\n> > @@ -5199,6 +5199,108 @@ test_expect_success '12k: Directory rename with sibling causes rename-to-self' '\n> > )\n> > '\n> >\n> > +# Testcase 12l, Both sides rename a directory into the other side, both add\n> > +# a file with after directory renames are the same filename\n> > +# Commit O: sub1/file, sub2/other\n> > +# Commit A: sub3/file, sub2/{other, new_add_add_file_1}\n> > +# Commit B: sub1/{file, newfile}, sub1/sub2/{other, new_add_add_file_2}\n> > +#\n> > +# In words:\n> > +# A: sub1/ -> sub3/, add sub2/new_add_add_file_1\n> > +# B: sub2/ -> sub1/sub2, add sub1/newfile, add sub1/sub2/new_add_add_file_2\n> > +#\n> > +# Expected: sub3/{file, newfile, sub2/other}\n> > +# CONFLICT (add/add): sub3/sub2/new_add_add_file\n>\n> The \"expected\" might need to be updated.\n\nOops! Yes, I kept changing and editing the testcase and the\ncomments...but didn't quite get all the updates I needed when I was\nrevising.\n\n> After all patches are applied,\n> this is the tree I get (note that it's \"sub1/sub2/new_add_add_file, not\n> \"sub3/sub2/new_add_add_file\"):\n>\n> .\n> |-- sub1\n> | `-- sub2\n> | `-- new_add_add_file\n> `-- sub3\n> |-- file\n> |-- newfile\n> `-- sub2\n> `-- other\n\nYes, that's right.\n\n> Also, at first glance, \"newfile\" shouldn't belong in a minimal\n> reproduction\n\nAh, I can see you've looked at this very closely. Thanks for digging\nin! I know it's counter-intuitive at first, but the file is\nnecessary in order to get the sub1/ -> sub3/ rename. The reasoning is\nas follows: We don't need to detect a directory rename for a directory\nwhere the other side added no new files into that directory...because\nthe whole point of directory renames is to move new files in a\ndirectory to the new location. Therefore, no new files in the\ndirectory on one side, means no need to detect a directory rename for\nit on the other side. For a deeper discussion of this, see commit\nc64432aacd (t6423: more involved rules for renaming directories into\neach other, 2020-10-15).\n\n\n>, but it somehow changes the output. When I apply this diff\n> (to the state after all patches are applied):\n>\n> diff --git a/t/t6423-merge-rename-directories.sh b/t/t6423-merge-rename-directories.sh\n> index 4286ae987c..9472fb7233 100755\n> --- a/t/t6423-merge-rename-directories.sh\n> +++ b/t/t6423-merge-rename-directories.sh\n> @@ -5237,7 +5237,6 @@ test_setup_12l () {\n>\n> git checkout B &&\n> echo dissimilar >sub2/new_add_add_file &&\n> - echo brand >sub1/newfile &&\n> git add sub1 sub2 &&\n> git mv sub2 sub1 &&\n> test_tick &&\n> @@ -5255,14 +5254,14 @@ test_expect_merge_algorithm failure success '12l (B into A): Rename into each ot\n> test_must_fail git -c merge.directoryRenames=true merge -s recursive B^0 &&\n>\n> git ls-files -s >out &&\n> - test_line_count = 5 out &&\n> + test_line_count = 4 out &&\n>\n> git rev-parse >actual \\\n> - :0:sub3/file :0:sub3/newfile :0:sub3/sub2/other \\\n> + :0:sub3/file :0:sub3/sub2/other \\\n> :2:sub1/sub2/new_add_add_file \\\n> :3:sub1/sub2/new_add_add_file &&\n> git rev-parse >expect \\\n> - O:sub1/file B:sub1/newfile O:sub2/other \\\n> + O:sub1/file O:sub2/other \\\n> A:sub2/new_add_add_file \\\n> B:sub1/sub2/new_add_add_file &&\n> test_cmp expect actual &&\n>\n> I get:\n>\n> .\n> |-- sub1\n> | `-- sub2\n> | |-- new_add_add_file\n> | `-- other\n> `-- sub3\n> `-- file\n>\n> (Note the path to \"other\".) I haven't figured out what's going on,\n> though.\n\nYeah, this is the result of having no directory rename due to having\nno new files that need to be moved by a directory rename.\n"},{"id":"458141","messageId":"CABPp-BFphDUrxnW0tC0yNZkHPgwSEtxod2Q4UMVjE3beaA0=dA@mail.gmail.com","threadId":"58046","inReplyTo":"20220627223017.2852209-1-calvinwan@google.com","subject":"Re: [PATCH 1/3] t6423: add tests of dual directory rename plus add/add conflict","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2022-06-30T00:07:18Z","receivedAt":"2022-06-30T00:07:37Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Mon, Jun 27, 2022 at 3:30 PM Calvin Wan wrote:\n>\n> \"Elijah Newren via GitGitGadget\" writes:\n> > +# Testcase 12l, Both sides rename a directory into the other side, both add\n> > +# a file with after directory renames are the same filename\n> > +# Commit O: sub1/file, sub2/other\n> > +# Commit A: sub3/file, sub2/{other, new_add_add_file_1}\n> > +# Commit B: sub1/{file, newfile}, sub1/sub2/{other, new_add_add_file_2}\n> > +#\n> > +# In words:\n> > +# A: sub1/ -> sub3/, add sub2/new_add_add_file_1\n> > +# B: sub2/ -> sub1/sub2, add sub1/newfile, add sub1/sub2/new_add_add_file_2\n> > +#\n> > +# Expected: sub3/{file, newfile, sub2/other}\n> > +# CONFLICT (add/add): sub3/sub2/new_add_add_file\n>\n> Grammatically, I could not understand\n>\n> \"both add a file with after directory renames are the same filename\"\n\nOops, that should be \"with\" -> \"which\".\n\n> I also found the same issue with `Expected` that Jonathan mentions. I ran the\n> command separately and got\n>\n> CONFLICT (add/add): Merge conflict in sub1/sub2/new_add_add_file\n\nYeah, repeatedly revising stuff is fine as long as you remember to\nupdate all the parts. (I was swapping which directories were named\n\"sub1\", \"sub2\" and \"sub3\" to see if lexicographic ordering might be\nrelated to why this simpler test triggered a bug in the \"recursive\"\nstrategy but Glen's bigger testcase didn't.). Anyway, I just missed\nupdating one of the locations while doing that revision; sorry about\nthat. Will fix.\n"},{"id":"458161","messageId":"pull.1268.v2.git.1656572225.gitgitgadget@gmail.com","threadId":"58046","inReplyTo":"pull.1268.git.1655871651.gitgitgadget@gmail.com","subject":"[PATCH v2 0/3] Fix dual rename into each other plus conflicting adds","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-06-30T06:57:02Z","receivedAt":"2022-06-30T06:57:15Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This series adds some testcases based on the tensorflow repository issue\nreported by Glen Choo at [1], demonstrating bugs in both the ort and\nrecursive strategies. It also provides a fix for the ort strategy.\n\nChanges since v1:\n\n * Fixed some wording issues in comments, and added a bit more details to\n one of the commit messages\n\n[1]\nhttps://lore.kernel.org/git/kl6lee006mle.fsf@chooglen-macbookpro.roam.corp.google.com/\n\nElijah Newren (3):\n t6423: add tests of dual directory rename plus add/add conflict\n merge-ort: shuffle the computation and cleanup of potential collisions\n merge-ort: fix issue with dual rename and add/add conflict\n\n merge-ort.c | 63 +++++++++++------\n t/t6423-merge-rename-directories.sh | 102 ++++++++++++++++++++++++++++\n 2 files changed, 145 insertions(+), 20 deletions(-)\n\n\nbase-commit: e54793a95afeea1e10de1e5ad7eab914e7416250\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1268%2Fnewren%2Ffix-dual-rename-into-each-other-plus-conflicting-adds-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1268/newren/fix-dual-rename-into-each-other-plus-conflicting-adds-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/1268\n\nRange-diff vs v1:\n\n 1: 69d62041843 ! 1: bf4c03d01d5 t6423: add tests of dual directory rename plus add/add conflict\n @@ t/t6423-merge-rename-directories.sh: test_expect_success '12k: Directory rename\n '\n \n +# Testcase 12l, Both sides rename a directory into the other side, both add\n -+# a file with after directory renames are the same filename\n ++# a file which after directory renames are the same filename\n +# Commit O: sub1/file, sub2/other\n +# Commit A: sub3/file, sub2/{other, new_add_add_file_1}\n +# Commit B: sub1/{file, newfile}, sub1/sub2/{other, new_add_add_file_2}\n @@ t/t6423-merge-rename-directories.sh: test_expect_success '12k: Directory rename\n +# B: sub2/ -> sub1/sub2, add sub1/newfile, add sub1/sub2/new_add_add_file_2\n +#\n +# Expected: sub3/{file, newfile, sub2/other}\n -+# CONFLICT (add/add): sub3/sub2/new_add_add_file\n ++# CONFLICT (add/add): sub1/sub2/new_add_add_file\n +\n +test_setup_12l () {\n +\ttest_create_repo 12l_$1 &&\n 2: d8c13e56209 = 2: cfa38f01481 merge-ort: shuffle the computation and cleanup of potential collisions\n 3: bb2badccb71 ! 3: da3ae38e390 merge-ort: fix issue with dual rename and add/add conflict\n @@ Commit message\n with it. So, let's just turn off directory rename detection in this\n case as well.\n \n + Another way to look at this is that if the source name involved in a\n + directory rename on one side is the target name of a directory rename\n + operation for a file from the other side, then we avoid the doubly\n + transitive rename. (More concretely, if a directory rename on side D\n + wants to rename a file on side E from OLD_NAME -> NEW_NAME, and side D\n + already had a file named NEW_NAME, and a directory rename on side E\n + wants to rename side D's NEW_NAME -> NEWER_NAME, then we turn off the\n + directory rename detection for NEW_NAME to prevent the\n + NEW_NAME -> NEWER_NAME rename, and instead end up with an add/add\n + conflict on NEW_NAME.)\n +\n Signed-off-by: Elijah Newren \n \n ## merge-ort.c ##\n @@ merge-ort.c: static char *check_for_directory_rename(struct merge_options *opt,\n \tconst char *new_dir;\n +\tint other_side = 3 - side_index;\n \n -+\t/* Cases where there is no new path, so we return NULL */\n ++\t/*\n ++\t * Cases where we don't have or don't want a directory rename for\n ++\t * this path, so we return NULL.\n ++\t */\n \tif (strmap_empty(dir_renames))\n \t\treturn new_path;\n +\tif (strmap_get(&collisions[other_side], path))\n\n-- \ngitgitgadget\n"},{"id":"458162","messageId":"bf4c03d01d5730503eb710e92a80136d5caa981a.1656572225.git.gitgitgadget@gmail.com","threadId":"58046","inReplyTo":"pull.1268.v2.git.1656572225.gitgitgadget@gmail.com","subject":"[PATCH v2 1/3] t6423: add tests of dual directory rename plus add/add conflict","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-06-30T06:57:03Z","receivedAt":"2022-06-30T06:57:15Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nThis is an attempt at minimalizing a testcase reported by Glen Choo\nwith tensorflow where merge-ort would report an assertion failure:\n\n Assertion failed: (ci->filemask == 2 || ci->filemask == 4), function apply_directory_rename_modifications, file merge-ort.c, line 2410\n\nreversing the direction of the merge provides a different error:\n\n error: cache entry has null sha1: ...\n fatal: unable to write .git/index\n\nso we add testcases for both. With these new testcases, the\nrecursive strategy differs in that it returns the latter error for\nboth merge directions.\n\nThese testcases are somehow a little different than Glen's original\ntensorflow testcase in that these ones trigger a bug with the recursive\nalgorithm whereas his testcase didn't. I figure that means these\ntestcases somehow manage to be more comprehensive.\n\nReported-by: Glen Choo \nSigned-off-by: Elijah Newren \n---\n t/t6423-merge-rename-directories.sh | 102 ++++++++++++++++++++++++++++\n 1 file changed, 102 insertions(+)\n\ndiff --git a/t/t6423-merge-rename-directories.sh b/t/t6423-merge-rename-directories.sh\nindex 479db32cd62..db13bb995f3 100755\n--- a/t/t6423-merge-rename-directories.sh\n+++ b/t/t6423-merge-rename-directories.sh\n@@ -5199,6 +5199,108 @@ test_expect_success '12k: Directory rename with sibling causes rename-to-self' '\n \t)\n '\n \n+# Testcase 12l, Both sides rename a directory into the other side, both add\n+# a file which after directory renames are the same filename\n+# Commit O: sub1/file, sub2/other\n+# Commit A: sub3/file, sub2/{other, new_add_add_file_1}\n+# Commit B: sub1/{file, newfile}, sub1/sub2/{other, new_add_add_file_2}\n+#\n+# In words:\n+# A: sub1/ -> sub3/, add sub2/new_add_add_file_1\n+# B: sub2/ -> sub1/sub2, add sub1/newfile, add sub1/sub2/new_add_add_file_2\n+#\n+# Expected: sub3/{file, newfile, sub2/other}\n+# CONFLICT (add/add): sub1/sub2/new_add_add_file\n+\n+test_setup_12l () {\n+\ttest_create_repo 12l_$1 &&\n+\t(\n+\t\tcd 12l_$1 &&\n+\n+\t\tmkdir -p sub1 sub2\n+\t\techo file >sub1/file &&\n+\t\techo other >sub2/other &&\n+\t\tgit add sub1 sub2 &&\n+\t\tgit commit -m \"O\" &&\n+\n+\t\tgit branch O &&\n+\t\tgit branch A &&\n+\t\tgit branch B &&\n+\n+\t\tgit checkout A &&\n+\t\tgit mv sub1 sub3 &&\n+\t\techo conflicting >sub2/new_add_add_file &&\n+\t\tgit add sub2 &&\n+\t\ttest_tick &&\n+\t\tgit add -u &&\n+\t\tgit commit -m \"A\" &&\n+\n+\t\tgit checkout B &&\n+\t\techo dissimilar >sub2/new_add_add_file &&\n+\t\techo brand >sub1/newfile &&\n+\t\tgit add sub1 sub2 &&\n+\t\tgit mv sub2 sub1 &&\n+\t\ttest_tick &&\n+\t\tgit commit -m \"B\"\n+\t)\n+}\n+\n+test_expect_merge_algorithm failure failure '12l (B into A): Rename into each other + add/add conflict' '\n+\ttest_setup_12l BintoA &&\n+\t(\n+\t\tcd 12l_BintoA &&\n+\n+\t\tgit checkout -q A^0 &&\n+\n+\t\ttest_must_fail git -c merge.directoryRenames=true merge -s recursive B^0 &&\n+\n+\t\tgit ls-files -s >out &&\n+\t\ttest_line_count = 5 out &&\n+\n+\t\tgit rev-parse >actual \\\n+\t\t\t:0:sub3/file :0:sub3/newfile :0:sub3/sub2/other \\\n+\t\t\t:2:sub1/sub2/new_add_add_file \\\n+\t\t\t:3:sub1/sub2/new_add_add_file &&\n+\t\tgit rev-parse >expect \\\n+\t\t\tO:sub1/file B:sub1/newfile O:sub2/other \\\n+\t\t\tA:sub2/new_add_add_file \\\n+\t\t\tB:sub1/sub2/new_add_add_file &&\n+\t\ttest_cmp expect actual &&\n+\n+\t\tgit ls-files -o >actual &&\n+\t\ttest_write_lines actual expect out >expect &&\n+\t\ttest_cmp expect actual\n+\t)\n+'\n+\n+test_expect_merge_algorithm failure failure '12l (A into B): Rename into each other + add/add conflict' '\n+\ttest_setup_12l AintoB &&\n+\t(\n+\t\tcd 12l_AintoB &&\n+\n+\t\tgit checkout -q B^0 &&\n+\n+\t\ttest_must_fail git -c merge.directoryRenames=true merge -s recursive A^0 &&\n+\n+\t\tgit ls-files -s >out &&\n+\t\ttest_line_count = 5 out &&\n+\n+\t\tgit rev-parse >actual \\\n+\t\t\t:0:sub3/file :0:sub3/newfile :0:sub3/sub2/other \\\n+\t\t\t:2:sub1/sub2/new_add_add_file \\\n+\t\t\t:3:sub1/sub2/new_add_add_file &&\n+\t\tgit rev-parse >expect \\\n+\t\t\tO:sub1/file B:sub1/newfile O:sub2/other \\\n+\t\t\tB:sub1/sub2/new_add_add_file \\\n+\t\t\tA:sub2/new_add_add_file &&\n+\t\ttest_cmp expect actual &&\n+\n+\t\tgit ls-files -o >actual &&\n+\t\ttest_write_lines actual expect out >expect &&\n+\t\ttest_cmp expect actual\n+\t)\n+'\n+\n ###########################################################################\n # SECTION 13: Checking informational and conflict messages\n #\n-- \ngitgitgadget\n\n"},{"id":"458163","messageId":"cfa38f01481d6a13a676e250e8254182733e0dd1.1656572226.git.gitgitgadget@gmail.com","threadId":"58046","inReplyTo":"pull.1268.v2.git.1656572225.gitgitgadget@gmail.com","subject":"[PATCH v2 2/3] merge-ort: shuffle the computation and cleanup of potential collisions","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-06-30T06:57:04Z","receivedAt":"2022-06-30T06:57:19Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nRun compute_collisions() for renames on both sides of history before\nany calls to collect_renames(), and do not free the computed collisions\nuntil after both calls to collect_renames(). This is just a code\nreorganization at this point that doesn't make sense on its own, but\nwill permit us to use the computed collision info from both sides\nwithin each call to collect_renames() in a subsequent commit.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 56 ++++++++++++++++++++++++++++++++++-------------------\n 1 file changed, 36 insertions(+), 20 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 8545354dafd..fa6667de18c 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2259,6 +2259,27 @@ static void compute_collisions(struct strmap *collisions,\n \t}\n }\n \n+static void free_collisions(struct strmap *collisions)\n+{\n+\tstruct hashmap_iter iter;\n+\tstruct strmap_entry *entry;\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+}\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@@ -2314,7 +2335,8 @@ static char *check_for_directory_rename(struct merge_options *opt,\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\t\t\t\t rename_info,\n+\t\t\t\t\t &collisions[side_index]);\n \t*clean_merge &= (new_path != NULL);\n \n \treturn new_path;\n@@ -3023,18 +3045,15 @@ static int detect_regular_renames(struct merge_options *opt,\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 struct strmap *collisions,\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@@ -3050,7 +3069,7 @@ static int collect_renames(struct merge_options *opt,\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 collisions,\n \t\t\t\t\t\t &clean);\n \n \t\tpossibly_cache_new_pair(renames, p, side_index, new_path);\n@@ -3076,20 +3095,6 @@ 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@@ -3100,6 +3105,7 @@ static int detect_and_process_renames(struct merge_options *opt,\n {\n \tstruct diff_queue_struct combined = { 0 };\n \tstruct rename_info *renames = &opt->priv->renames;\n+\tstruct strmap collisions[3];\n \tint need_dir_renames, s, i, clean = 1;\n \tunsigned detection_run = 0;\n \n@@ -3149,12 +3155,22 @@ 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+\tfor (int i = MERGE_SIDE1; i <= MERGE_SIDE2; i++) {\n+\t\tint other_side = 3 - i;\n+\t\tcompute_collisions(&collisions[i],\n+\t\t\t\t &renames->dir_renames[other_side],\n+\t\t\t\t &renames->pairs[i]);\n+\t}\n \tclean &= collect_renames(opt, &combined, MERGE_SIDE1,\n+\t\t\t\t collisions,\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 collisions,\n \t\t\t\t &renames->dir_renames[1],\n \t\t\t\t &renames->dir_renames[2]);\n+\tfor (int i = MERGE_SIDE1; i <= MERGE_SIDE2; i++)\n+\t\tfree_collisions(&collisions[i]);\n \tSTABLE_QSORT(combined.queue, combined.nr, compare_pairs);\n \ttrace2_region_leave(\"merge\", \"directory renames\", opt->repo);\n \n-- \ngitgitgadget\n\n"},{"id":"458164","messageId":"da3ae38e390df8acf86e910389d1620569a95a87.1656572226.git.gitgitgadget@gmail.com","threadId":"58046","inReplyTo":"pull.1268.v2.git.1656572225.gitgitgadget@gmail.com","subject":"[PATCH v2 3/3] merge-ort: fix issue with dual rename and add/add conflict","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-06-30T06:57:05Z","receivedAt":"2022-06-30T06:57:26Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nThere is code in both merge-recursive and merge-ort for avoiding doubly\ntransitive renames (i.e. one side renames directory A/ -> B/, and the\nother side renames directory B/ -> C/), because this combination would\notherwise make a mess for new files added to A/ on the first side and\nwondering which directory they end up in -- especially if there were\neven more renames such as the first side renaming C/ -> D/. In such\ncases, it just turns \"off\" directory rename detection for the higher\norder transitive cases.\n\nThe testcases added in t6423 a couple commits ago are slightly different\nbut similar in principle. They involve a similar case of paired\nrenaming but instead of A/ -> B/ and B/ -> C/, the second side renames\na leading directory of B/ to C/. And both sides add a new file\nsomewhere under the directory that the other side will rename. While\nthe new files added start within different directories and thus could\nlogically end up within different directories, it is weird for a file\non one side to end up where the other one started and not move along\nwith it. So, let's just turn off directory rename detection in this\ncase as well.\n\nAnother way to look at this is that if the source name involved in a\ndirectory rename on one side is the target name of a directory rename\noperation for a file from the other side, then we avoid the doubly\ntransitive rename. (More concretely, if a directory rename on side D\nwants to rename a file on side E from OLD_NAME -> NEW_NAME, and side D\nalready had a file named NEW_NAME, and a directory rename on side E\nwants to rename side D's NEW_NAME -> NEWER_NAME, then we turn off the\ndirectory rename detection for NEW_NAME to prevent the\nNEW_NAME -> NEWER_NAME rename, and instead end up with an add/add\nconflict on NEW_NAME.)\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 7 +++++++\n t/t6423-merge-rename-directories.sh | 4 ++--\n 2 files changed, 9 insertions(+), 2 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex fa6667de18c..17db4c30e5b 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2292,9 +2292,16 @@ static char *check_for_directory_rename(struct merge_options *opt,\n \tstruct strmap_entry *rename_info;\n \tstruct strmap_entry *otherinfo = NULL;\n \tconst char *new_dir;\n+\tint other_side = 3 - side_index;\n \n+\t/*\n+\t * Cases where we don't have or don't want a directory rename for\n+\t * this path, so we return NULL.\n+\t */\n \tif (strmap_empty(dir_renames))\n \t\treturn new_path;\n+\tif (strmap_get(&collisions[other_side], path))\n+\t\treturn new_path;\n \trename_info = check_dir_renamed(path, dir_renames);\n \tif (!rename_info)\n \t\treturn new_path;\ndiff --git a/t/t6423-merge-rename-directories.sh b/t/t6423-merge-rename-directories.sh\nindex db13bb995f3..1300a01206a 100755\n--- a/t/t6423-merge-rename-directories.sh\n+++ b/t/t6423-merge-rename-directories.sh\n@@ -5245,7 +5245,7 @@ test_setup_12l () {\n \t)\n }\n \n-test_expect_merge_algorithm failure failure '12l (B into A): Rename into each other + add/add conflict' '\n+test_expect_merge_algorithm failure success '12l (B into A): Rename into each other + add/add conflict' '\n \ttest_setup_12l BintoA &&\n \t(\n \t\tcd 12l_BintoA &&\n@@ -5273,7 +5273,7 @@ test_expect_merge_algorithm failure failure '12l (B into A): Rename into each ot\n \t)\n '\n \n-test_expect_merge_algorithm failure failure '12l (A into B): Rename into each other + add/add conflict' '\n+test_expect_merge_algorithm failure success '12l (A into B): Rename into each other + add/add conflict' '\n \ttest_setup_12l AintoB &&\n \t(\n \t\tcd 12l_AintoB &&\n-- \ngitgitgadget\n"},{"id":"458178","messageId":"220630.86tu82e9b8.gmgdl@evledraar.gmail.com","threadId":"58046","inReplyTo":"bf4c03d01d5730503eb710e92a80136d5caa981a.1656572225.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 1/3] t6423: add tests of dual directory rename plus add/add conflict","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2022-06-30T10:21:29Z","receivedAt":"2022-06-30T10:27:11Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Thu, Jun 30 2022, Elijah Newren via GitGitGadget wrote:\n\n> From: Elijah Newren \n\n> +test_setup_12l () {\n> +\ttest_create_repo 12l_$1 &&\n\nCan & should just be \"git init\", see f0d4d398e28 (test-lib: split up and\ndeprecate test_create_repo(), 2021-05-10).\n\n\n> +\t(\n> +\t\tcd 12l_$1 &&\n> +\n> +\t\tmkdir -p sub1 sub2\n\nThe \"-p\" here isn't needed, you're not creating recursive directories. \n\n> +\t\tgit ls-files -s >out &&\n> +\t\ttest_line_count = 5 out &&\n\nCan't this just use test_stdout_line_count? Except...\n\n> +\n> +\t\tgit rev-parse >actual \\\n> +\t\t\t:0:sub3/file :0:sub3/newfile :0:sub3/sub2/other \\\n> +\t\t\t:2:sub1/sub2/new_add_add_file \\\n> +\t\t\t:3:sub1/sub2/new_add_add_file &&\n> +\t\tgit rev-parse >expect \\\n> +\t\t\tO:sub1/file B:sub1/newfile O:sub2/other \\\n> +\t\t\tA:sub2/new_add_add_file \\\n> +\t\t\tB:sub1/sub2/new_add_add_file &&\n> +\t\ttest_cmp expect actual &&\n> +\n> +\t\tgit ls-files -o >actual &&\n> +\t\ttest_write_lines actual expect out >expect &&\n> +\t\ttest_cmp expect actual\n\nThis test seems a bit odd, here we're just checking that we've created\nscratch files for the internal use of our test, why is it important that\nwe have an \"out\" file, when the only reason we have it is because we\nneeded it for checking the \"ls-files\" line count above?\n\n> +\t)\n> +'\n> +\n> +test_expect_merge_algorithm failure failure '12l (A into B): Rename into each other + add/add conflict' '\n> +\ttest_setup_12l AintoB &&\n> +\t(\n> +\t\tcd 12l_AintoB &&\n> +\n> +\t\tgit checkout -q B^0 &&\n> +\n> +\t\ttest_must_fail git -c merge.directoryRenames=true merge -s recursive A^0 &&\n> +\n> +\t\tgit ls-files -s >out &&\n> +\t\ttest_line_count = 5 out &&\n\nditto.\n\n> +\t\tgit rev-parse >actual \\\n> +\t\t\t:0:sub3/file :0:sub3/newfile :0:sub3/sub2/other \\\n> +\t\t\t:2:sub1/sub2/new_add_add_file \\\n> +\t\t\t:3:sub1/sub2/new_add_add_file &&\n> +\t\tgit rev-parse >expect \\\n> +\t\t\tO:sub1/file B:sub1/newfile O:sub2/other \\\n> +\t\t\tB:sub1/sub2/new_add_add_file \\\n> +\t\t\tA:sub2/new_add_add_file &&\n> +\t\ttest_cmp expect actual &&\n> +\n> +\t\tgit ls-files -o >actual &&\n> +\t\ttest_write_lines actual expect out >expect &&\n\nditto\n"},{"id":"458179","messageId":"220630.86pmiqe96x.gmgdl@evledraar.gmail.com","threadId":"58046","inReplyTo":"cfa38f01481d6a13a676e250e8254182733e0dd1.1656572226.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 2/3] merge-ort: shuffle the computation and cleanup of potential collisions","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2022-06-30T10:28:04Z","receivedAt":"2022-06-30T10:29:21Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Thu, Jun 30 2022, Elijah Newren via GitGitGadget wrote:\n\n> From: Elijah Newren \n>\n> Run compute_collisions() for renames on both sides of history before\n> any calls to collect_renames(), and do not free the computed collisions\n> until after both calls to collect_renames(). This is just a code\n> reorganization at this point that doesn't make sense on its own, but\n> will permit us to use the computed collision info from both sides\n> within each call to collect_renames() in a subsequent commit.\n\nI think this would be easier to follow if split in two, since...\n\n> +static void free_collisions(struct strmap *collisions)\n> +{\n> +\tstruct hashmap_iter iter;\n> +\tstruct strmap_entry *entry;\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> +}\n\n...a large part of it...\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\n..is moving existing code into a utility function...\n\n> \treturn clean;\n> }\n> \n> @@ -3100,6 +3105,7 @@ static int detect_and_process_renames(struct merge_options *opt,\n> {\n> \tstruct diff_queue_struct combined = { 0 };\n> \tstruct rename_info *renames = &opt->priv->renames;\n> +\tstruct strmap collisions[3];\n> \tint need_dir_renames, s, i, clean = 1;\n> \tunsigned detection_run = 0;\n> \n> @@ -3149,12 +3155,22 @@ 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> +\tfor (int i = MERGE_SIDE1; i <= MERGE_SIDE2; i++) {\n> +\t\tint other_side = 3 - i;\n> +\t\tcompute_collisions(&collisions[i],\n> +\t\t\t\t &renames->dir_renames[other_side],\n> +\t\t\t\t &renames->pairs[i]);\n> +\t}\n> \tclean &= collect_renames(opt, &combined, MERGE_SIDE1,\n> +\t\t\t\t collisions,\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 collisions,\n> \t\t\t\t &renames->dir_renames[1],\n> \t\t\t\t &renames->dir_renames[2]);\n> +\tfor (int i = MERGE_SIDE1; i <= MERGE_SIDE2; i++)\n> +\t\tfree_collisions(&collisions[i]);\n> \tSTABLE_QSORT(combined.queue, combined.nr, compare_pairs);\n> \ttrace2_region_leave(\"merge\", \"directory renames\", opt->repo);\n\n...which when looking at it makes the functional change harder to follow\nthan it otherwise would be.\n"},{"id":"458180","messageId":"220630.86letee8mz.gmgdl@evledraar.gmail.com","threadId":"58046","inReplyTo":"da3ae38e390df8acf86e910389d1620569a95a87.1656572226.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 3/3] merge-ort: fix issue with dual rename and add/add conflict","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2022-06-30T10:31:52Z","receivedAt":"2022-06-30T10:43:18Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Thu, Jun 30 2022, Elijah Newren via GitGitGadget wrote:\n\n> From: Elijah Newren \n>\n> There is code in both merge-recursive and merge-ort for avoiding doubly\n> transitive renames (i.e. one side renames directory A/ -> B/, and the\n> other side renames directory B/ -> C/), because this combination would\n> otherwise make a mess for new files added to A/ on the first side and\n> wondering which directory they end up in -- especially if there were\n> even more renames such as the first side renaming C/ -> D/. In such\n> cases, it just turns \"off\" directory rename detection for the higher\n> order transitive cases.\n>\n> The testcases added in t6423 a couple commits ago are slightly different\n> but similar in principle. They involve a similar case of paired\n> renaming but instead of A/ -> B/ and B/ -> C/, the second side renames\n> a leading directory of B/ to C/. And both sides add a new file\n> somewhere under the directory that the other side will rename. While\n> the new files added start within different directories and thus could\n> logically end up within different directories, it is weird for a file\n> on one side to end up where the other one started and not move along\n> with it. So, let's just turn off directory rename detection in this\n> case as well.\n>\n> Another way to look at this is that if the source name involved in a\n> directory rename on one side is the target name of a directory rename\n> operation for a file from the other side, then we avoid the doubly\n> transitive rename. (More concretely, if a directory rename on side D\n> wants to rename a file on side E from OLD_NAME -> NEW_NAME, and side D\n> already had a file named NEW_NAME, and a directory rename on side E\n> wants to rename side D's NEW_NAME -> NEWER_NAME, then we turn off the\n> directory rename detection for NEW_NAME to prevent the\n> NEW_NAME -> NEWER_NAME rename, and instead end up with an add/add\n> conflict on NEW_NAME.)\n>\n> Signed-off-by: Elijah Newren \n> ---\n> merge-ort.c | 7 +++++++\n> t/t6423-merge-rename-directories.sh | 4 ++--\n> 2 files changed, 9 insertions(+), 2 deletions(-)\n>\n> diff --git a/merge-ort.c b/merge-ort.c\n> index fa6667de18c..17db4c30e5b 100644\n> --- a/merge-ort.c\n> +++ b/merge-ort.c\n> @@ -2292,9 +2292,16 @@ static char *check_for_directory_rename(struct merge_options *opt,\n> \tstruct strmap_entry *rename_info;\n> \tstruct strmap_entry *otherinfo = NULL;\n> \tconst char *new_dir;\n> +\tint other_side = 3 - side_index;\n> \n> +\t/*\n> +\t * Cases where we don't have or don't want a directory rename for\n> +\t * this path, so we return NULL.\n> +\t */\n> \tif (strmap_empty(dir_renames))\n> \t\treturn new_path;\n> +\tif (strmap_get(&collisions[other_side], path))\n> +\t\treturn new_path;\n\nI realize from looking at merge-recursive.c that this is carrying\nforward some legacy debt, but I find this code and the need for a\ncomment more complex than it needs to. On top of master this will work\njust as well:\n\t\n\tdiff --git a/merge-ort.c b/merge-ort.c\n\tindex b5015b9afd4..f5a02b1ff6f 100644\n\t--- a/merge-ort.c\n\t+++ b/merge-ort.c\n\t@@ -2268,16 +2268,16 @@ static char *check_for_directory_rename(struct merge_options *opt,\n\t \t\t\t\t\tstruct strmap *collisions,\n\t \t\t\t\t\tint *clean_merge)\n\t {\n\t-\tchar *new_path = NULL;\n\t+\tchar *new_path;\n\t \tstruct strmap_entry *rename_info;\n\t \tstruct strmap_entry *otherinfo = NULL;\n\t \tconst char *new_dir;\n\t \n\t \tif (strmap_empty(dir_renames))\n\t-\t\treturn new_path;\n\t+\t\treturn NULL;\n\t \trename_info = check_dir_renamed(path, dir_renames);\n\t \tif (!rename_info)\n\t-\t\treturn new_path;\n\t+\t\treturn NULL;\n\t \t/* old_dir = rename_info->key; */\n\t \tnew_dir = rename_info->value;\n\nI.e. we're really just making the reader squint to see that we're\nactually returning NULL here, it's only later that we have an actual\n\"new path\".\n\nWouldn't sticking that earlier in this series be an improvement? The\nreason you need to explain \"so we return NULL\" is because we're carrying\nforward this oddity, but if we just don't initialize it and return NULL\ninstead...\n\nIf you want to keep this pretty much as-is I think you should add a \\n\nbefore the (not seen in your context) \"old_dir\" comment seen in the\ncontext here above, to make it visually clear that your new comment is\nreferring to these chains of returns. That could also be made clearer\nwith (again, on top of master, and could be combined with the above):\n\t\n\tdiff --git a/merge-ort.c b/merge-ort.c\n\tindex b5015b9afd4..a418f81a3eb 100644\n\t--- a/merge-ort.c\n\t+++ b/merge-ort.c\n\t@@ -2278,8 +2278,6 @@ static char *check_for_directory_rename(struct merge_options *opt,\n\t \trename_info = check_dir_renamed(path, dir_renames);\n\t \tif (!rename_info)\n\t \t\treturn new_path;\n\t-\t/* old_dir = rename_info->key; */\n\t-\tnew_dir = rename_info->value;\n\t \n\t \t/*\n\t \t * This next part is a little weird. We do not want to do an\n\t@@ -2305,6 +2303,7 @@ static char *check_for_directory_rename(struct merge_options *opt,\n\t \t * As it turns out, this also prevents N-way transient rename\n\t \t * confusion; See testcases 9c and 9d of t6043.\n\t \t */\n\t+\tnew_dir = rename_info->value; /* old_dir = rename_info->key; */\n\t \totherinfo = strmap_get_entry(dir_rename_exclusions, new_dir);\n\t \tif (otherinfo) {\n\t \t\tpath_msg(opt, rename_info->key, 1,\n"},{"id":"458288","messageId":"20220630223250.2843332-1-jonathantanmy@google.com","threadId":"58046","inReplyTo":"CABPp-BGtKQVgaf9ttwRMAE6AvH1QC3TqFcFwiAOpnm-SqKnNCQ@mail.gmail.com","subject":"Re: [PATCH 1/3] t6423: add tests of dual directory rename plus add/add conflict","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2022-06-30T22:32:49Z","receivedAt":"2022-06-30T22:32:59Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Elijah Newren writes:\n> Ah, I can see you've looked at this very closely. Thanks for digging\n> in! I know it's counter-intuitive at first, but the file is\n> necessary in order to get the sub1/ -> sub3/ rename. The reasoning is\n> as follows: We don't need to detect a directory rename for a directory\n> where the other side added no new files into that directory...because\n> the whole point of directory renames is to move new files in a\n> directory to the new location. Therefore, no new files in the\n> directory on one side, means no need to detect a directory rename for\n> it on the other side. For a deeper discussion of this, see commit\n> c64432aacd (t6423: more involved rules for renaming directories into\n> each other, 2020-10-15).\n\nThanks! This makes sense. Might be worth including as a comment\n(explaining why \"newfile\" is there) in the test.\n"},{"id":"458327","messageId":"CABPp-BEcojvfeuhp7rSi-O+9oEu4KpwPDwbKS-MiD1qCKde-CA@mail.gmail.com","threadId":"58046","inReplyTo":"220630.86tu82e9b8.gmgdl@evledraar.gmail.com","subject":"Re: [PATCH v2 1/3] t6423: add tests of dual directory rename plus add/add conflict","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2022-07-01T02:57:41Z","receivedAt":"2022-07-01T02:57:58Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Jun 30, 2022 at 3:26 AM Ævar Arnfjörð Bjarmason\n wrote:\n>\n> On Thu, Jun 30 2022, Elijah Newren via GitGitGadget wrote:\n>\n> > From: Elijah Newren \n>\n> > +test_setup_12l () {\n> > + test_create_repo 12l_$1 &&\n>\n> Can & should just be \"git init\", see f0d4d398e28 (test-lib: split up and\n> deprecate test_create_repo(), 2021-05-10).\n\nI've switched to \"git init\" and even encouraged others to do the same\nin other test scripts, but since literally every other test in this\nfile uses test_create_repo, I think they should all be converted at\nonce and just be consistent here. But, so we can stop having this\nconversation, after this series lands, I'll send one in to update the\nvarious merge testfiles that make heavy use of test_create_repo and\nconvert them over.\n\n> > + (\n> > + cd 12l_$1 &&\n> > +\n> > + mkdir -p sub1 sub2\n>\n> The \"-p\" here isn't needed, you're not creating recursive directories.\n\nIndeed; will fix.\n\n> > + git ls-files -s >out &&\n> > + test_line_count = 5 out &&\n>\n> Can't this just use test_stdout_line_count? Except...\n\nOoh, new function from late last year that I was unaware of. Yeah,\nI'm happy to start using it.\n\n> > +\n> > + git rev-parse >actual \\\n> > + :0:sub3/file :0:sub3/newfile :0:sub3/sub2/other \\\n> > + :2:sub1/sub2/new_add_add_file \\\n> > + :3:sub1/sub2/new_add_add_file &&\n> > + git rev-parse >expect \\\n> > + O:sub1/file B:sub1/newfile O:sub2/other \\\n> > + A:sub2/new_add_add_file \\\n> > + B:sub1/sub2/new_add_add_file &&\n> > + test_cmp expect actual &&\n> > +\n> > + git ls-files -o >actual &&\n> > + test_write_lines actual expect out >expect &&\n> > + test_cmp expect actual\n>\n> This test seems a bit odd, here we're just checking that we've created\n> scratch files for the internal use of our test, why is it important that\n> we have an \"out\" file, when the only reason we have it is because we\n> needed it for checking the \"ls-files\" line count above?\n\nNah, you've misunderstood the purpose of the check. It isn't \"make\nsure that these untracked files are present among whatever else might\nalso be present\", it's \"make sure the merge step did not introduce\n*any* untracked files\" (something the recursive backend periodically\ndid, and they weren't cruft untracked files but stored actual merge\nresults). There wasn't a nice easy check for that, the closest was to\ntranslate the requirement to \"make sure the only untracked files are\nthe ones explicitly added by this test script\", which is the check you\nsee here. I don't actually care about \"actual\", \"expect\", or \"out\", I\njust care that there aren't any _other_ untracked files.\n"},{"id":"458328","messageId":"CABPp-BEZqATCZdqO0xzwZnS5TTu=4z_-h9yusJmhvxHs-kHUzA@mail.gmail.com","threadId":"58046","inReplyTo":"20220630223250.2843332-1-jonathantanmy@google.com","subject":"Re: [PATCH 1/3] t6423: add tests of dual directory rename plus add/add conflict","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2022-07-01T02:57:43Z","receivedAt":"2022-07-01T02:58:01Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Jun 30, 2022 at 3:32 PM Jonathan Tan wrote:\n>\n> Elijah Newren writes:\n> > Ah, I can see you've looked at this very closely. Thanks for digging\n> > in! I know it's counter-intuitive at first, but the file is\n> > necessary in order to get the sub1/ -> sub3/ rename. The reasoning is\n> > as follows: We don't need to detect a directory rename for a directory\n> > where the other side added no new files into that directory...because\n> > the whole point of directory renames is to move new files in a\n> > directory to the new location. Therefore, no new files in the\n> > directory on one side, means no need to detect a directory rename for\n> > it on the other side. For a deeper discussion of this, see commit\n> > c64432aacd (t6423: more involved rules for renaming directories into\n> > each other, 2020-10-15).\n>\n> Thanks! This makes sense. Might be worth including as a comment\n> (explaining why \"newfile\" is there) in the test.\n\nSure, will do.\n"},{"id":"458329","messageId":"CABPp-BFp1JYGmeqj=1HC3X4Eca72spcF2BX=aZ_tkbEdhvHsCw@mail.gmail.com","threadId":"58046","inReplyTo":"220630.86pmiqe96x.gmgdl@evledraar.gmail.com","subject":"Re: [PATCH v2 2/3] merge-ort: shuffle the computation and cleanup of potential collisions","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2022-07-01T03:02:07Z","receivedAt":"2022-07-01T03:02:23Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Jun 30, 2022 at 3:29 AM Ævar Arnfjörð Bjarmason\n wrote:\n>\n> On Thu, Jun 30 2022, Elijah Newren via GitGitGadget wrote:\n>\n> > From: Elijah Newren \n> >\n> > Run compute_collisions() for renames on both sides of history before\n> > any calls to collect_renames(), and do not free the computed collisions\n> > until after both calls to collect_renames(). This is just a code\n> > reorganization at this point that doesn't make sense on its own, but\n> > will permit us to use the computed collision info from both sides\n> > within each call to collect_renames() in a subsequent commit.\n>\n> I think this would be easier to follow if split in two, since...\n>\n> > +static void free_collisions(struct strmap *collisions)\n> > +{\n> > + struct hashmap_iter iter;\n> > + struct strmap_entry *entry;\n> > +\n> > + /* Free each value in the collisions map */\n> > + strmap_for_each_entry(collisions, &iter, entry) {\n> > + struct collision_info *info = entry->value;\n> > + string_list_clear(&info->source_files, 0);\n> > + }\n> > + /*\n> > + * In compute_collisions(), we set collisions.strdup_strings to 0\n> > + * so that we wouldn't have to make another copy of the new_path\n> > + * allocated by apply_dir_rename(). But now that we've used them\n> > + * and have no other references to these strings, it is time to\n> > + * deallocate them.\n> > + */\n> > + free_strmap_strings(collisions);\n> > + strmap_clear(collisions, 1);\n> > +}\n>\n> ...a large part of it...\n> >\n> > - /* Free each value in the collisions map */\n> > - strmap_for_each_entry(&collisions, &iter, entry) {\n> > - struct collision_info *info = entry->value;\n> > - string_list_clear(&info->source_files, 0);\n> > - }\n> > - /*\n> > - * In compute_collisions(), we set collisions.strdup_strings to 0\n> > - * so that we wouldn't have to make another copy of the new_path\n> > - * allocated by apply_dir_rename(). But now that we've used them\n> > - * and have no other references to these strings, it is time to\n> > - * deallocate them.\n> > - */\n> > - free_strmap_strings(&collisions);\n> > - strmap_clear(&collisions, 1);\n>\n> ..is moving existing code into a utility function...\n>\n> > return clean;\n> > }\n> >\n> > @@ -3100,6 +3105,7 @@ static int detect_and_process_renames(struct merge_options *opt,\n> > {\n> > struct diff_queue_struct combined = { 0 };\n> > struct rename_info *renames = &opt->priv->renames;\n> > + struct strmap collisions[3];\n> > int need_dir_renames, s, i, clean = 1;\n> > unsigned detection_run = 0;\n> >\n> > @@ -3149,12 +3155,22 @@ static int detect_and_process_renames(struct merge_options *opt,\n> > ALLOC_GROW(combined.queue,\n> > renames->pairs[1].nr + renames->pairs[2].nr,\n> > combined.alloc);\n> > + for (int i = MERGE_SIDE1; i <= MERGE_SIDE2; i++) {\n> > + int other_side = 3 - i;\n> > + compute_collisions(&collisions[i],\n> > + &renames->dir_renames[other_side],\n> > + &renames->pairs[i]);\n> > + }\n> > clean &= collect_renames(opt, &combined, MERGE_SIDE1,\n> > + collisions,\n> > &renames->dir_renames[2],\n> > &renames->dir_renames[1]);\n> > clean &= collect_renames(opt, &combined, MERGE_SIDE2,\n> > + collisions,\n> > &renames->dir_renames[1],\n> > &renames->dir_renames[2]);\n> > + for (int i = MERGE_SIDE1; i <= MERGE_SIDE2; i++)\n> > + free_collisions(&collisions[i]);\n> > STABLE_QSORT(combined.queue, combined.nr, compare_pairs);\n> > trace2_region_leave(\"merge\", \"directory renames\", opt->repo);\n>\n> ...which when looking at it makes the functional change harder to follow\n> than it otherwise would be.\n\nGood point; will split.\n"},{"id":"458330","messageId":"CABPp-BHmuDx0+JBbar3jZRWFxFruaxSWkohy=BzOsqBUZENyvw@mail.gmail.com","threadId":"58046","inReplyTo":"220630.86letee8mz.gmgdl@evledraar.gmail.com","subject":"Re: [PATCH v2 3/3] merge-ort: fix issue with dual rename and add/add conflict","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2022-07-01T03:03:30Z","receivedAt":"2022-07-01T03:03:47Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Jun 30, 2022 at 3:41 AM Ævar Arnfjörð Bjarmason\n wrote:\n>\n> On Thu, Jun 30 2022, Elijah Newren via GitGitGadget wrote:\n>\n> > From: Elijah Newren \n> >\n> > There is code in both merge-recursive and merge-ort for avoiding doubly\n> > transitive renames (i.e. one side renames directory A/ -> B/, and the\n> > other side renames directory B/ -> C/), because this combination would\n> > otherwise make a mess for new files added to A/ on the first side and\n> > wondering which directory they end up in -- especially if there were\n> > even more renames such as the first side renaming C/ -> D/. In such\n> > cases, it just turns \"off\" directory rename detection for the higher\n> > order transitive cases.\n> >\n> > The testcases added in t6423 a couple commits ago are slightly different\n> > but similar in principle. They involve a similar case of paired\n> > renaming but instead of A/ -> B/ and B/ -> C/, the second side renames\n> > a leading directory of B/ to C/. And both sides add a new file\n> > somewhere under the directory that the other side will rename. While\n> > the new files added start within different directories and thus could\n> > logically end up within different directories, it is weird for a file\n> > on one side to end up where the other one started and not move along\n> > with it. So, let's just turn off directory rename detection in this\n> > case as well.\n> >\n> > Another way to look at this is that if the source name involved in a\n> > directory rename on one side is the target name of a directory rename\n> > operation for a file from the other side, then we avoid the doubly\n> > transitive rename. (More concretely, if a directory rename on side D\n> > wants to rename a file on side E from OLD_NAME -> NEW_NAME, and side D\n> > already had a file named NEW_NAME, and a directory rename on side E\n> > wants to rename side D's NEW_NAME -> NEWER_NAME, then we turn off the\n> > directory rename detection for NEW_NAME to prevent the\n> > NEW_NAME -> NEWER_NAME rename, and instead end up with an add/add\n> > conflict on NEW_NAME.)\n> >\n> > Signed-off-by: Elijah Newren \n> > ---\n> > merge-ort.c | 7 +++++++\n> > t/t6423-merge-rename-directories.sh | 4 ++--\n> > 2 files changed, 9 insertions(+), 2 deletions(-)\n> >\n> > diff --git a/merge-ort.c b/merge-ort.c\n> > index fa6667de18c..17db4c30e5b 100644\n> > --- a/merge-ort.c\n> > +++ b/merge-ort.c\n> > @@ -2292,9 +2292,16 @@ static char *check_for_directory_rename(struct merge_options *opt,\n> > struct strmap_entry *rename_info;\n> > struct strmap_entry *otherinfo = NULL;\n> > const char *new_dir;\n> > + int other_side = 3 - side_index;\n> >\n> > + /*\n> > + * Cases where we don't have or don't want a directory rename for\n> > + * this path, so we return NULL.\n> > + */\n> > if (strmap_empty(dir_renames))\n> > return new_path;\n> > + if (strmap_get(&collisions[other_side], path))\n> > + return new_path;\n>\n> I realize from looking at merge-recursive.c that this is carrying\n> forward some legacy debt\n\n...which was introduced by me as well...\n\n> , but I find this code and the need for a\n> comment more complex than it needs to. On top of master this will work\n> just as well:\n>\n> diff --git a/merge-ort.c b/merge-ort.c\n> index b5015b9afd4..f5a02b1ff6f 100644\n> --- a/merge-ort.c\n> +++ b/merge-ort.c\n> @@ -2268,16 +2268,16 @@ static char *check_for_directory_rename(struct merge_options *opt,\n> struct strmap *collisions,\n> int *clean_merge)\n> {\n> - char *new_path = NULL;\n> + char *new_path;\n> struct strmap_entry *rename_info;\n> struct strmap_entry *otherinfo = NULL;\n> const char *new_dir;\n>\n> if (strmap_empty(dir_renames))\n> - return new_path;\n> + return NULL;\n> rename_info = check_dir_renamed(path, dir_renames);\n> if (!rename_info)\n> - return new_path;\n> + return NULL;\n> /* old_dir = rename_info->key; */\n> new_dir = rename_info->value;\n\nYou know, while making this patch series I was asking myself, \"Why\ndidn't I just explicitly return NULL here?\" I don't know why I did it\nthis way, but it now seems slightly odd to me too. I decided to not\nfix it up and just provide a more targeted fix, but since it tripped\nyou up, I'm happy to add this as a preparatory cleanup.\n\n> I.e. we're really just making the reader squint to see that we're\n> actually returning NULL here, it's only later that we have an actual\n> \"new path\".\n>\n> Wouldn't sticking that earlier in this series be an improvement? The\n> reason you need to explain \"so we return NULL\" is because we're carrying\n> forward this oddity, but if we just don't initialize it and return NULL\n> instead...\n\nI still think the comment makes sense to add, other than the \"so we\nreturn NULL\" bit, even after this change. But yeah, we can strike the\n\"so we return NULL\" part of it after this cleanup.\n\n> If you want to keep this pretty much as-is I think you should add a \\n\n> before the (not seen in your context) \"old_dir\" comment seen in the\n> context here above, to make it visually clear that your new comment is\n> referring to these chains of returns. That could also be made clearer\n> with (again, on top of master, and could be combined with the above):\n>\n> diff --git a/merge-ort.c b/merge-ort.c\n> index b5015b9afd4..a418f81a3eb 100644\n> --- a/merge-ort.c\n> +++ b/merge-ort.c\n> @@ -2278,8 +2278,6 @@ static char *check_for_directory_rename(struct merge_options *opt,\n> rename_info = check_dir_renamed(path, dir_renames);\n> if (!rename_info)\n> return new_path;\n> - /* old_dir = rename_info->key; */\n> - new_dir = rename_info->value;\n>\n> /*\n> * This next part is a little weird. We do not want to do an\n> @@ -2305,6 +2303,7 @@ static char *check_for_directory_rename(struct merge_options *opt,\n> * As it turns out, this also prevents N-way transient rename\n> * confusion; See testcases 9c and 9d of t6043.\n> */\n> + new_dir = rename_info->value; /* old_dir = rename_info->key; */\n> otherinfo = strmap_get_entry(dir_rename_exclusions, new_dir);\n> if (otherinfo) {\n> path_msg(opt, rename_info->key, 1,\n\nSure, seems fine.\n"},{"id":"458338","messageId":"pull.1268.v3.git.1656653000.gitgitgadget@gmail.com","threadId":"58046","inReplyTo":"pull.1268.v2.git.1656572225.gitgitgadget@gmail.com","subject":"[PATCH v3 0/5] Fix dual rename into each other plus conflicting adds","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-07-01T05:23:15Z","receivedAt":"2022-07-01T05:23:26Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This series adds some testcases based on the tensorflow repository issue\nreported by Glen Choo at [1], demonstrating bugs in both the ort and\nrecursive strategies. It also provides a fix for the ort strategy.\n\nChanges since v2:\n\n * Added a couple preparatory cleanup patches\n * Added a comment about why sub1/newfile is important to the new testcases\n * A couple other minor code cleanups\n\nChanges since v1:\n\n * Fixed some wording issues in comments, and added a bit more details to\n one of the commit messages\n\n[1]\nhttps://lore.kernel.org/git/kl6lee006mle.fsf@chooglen-macbookpro.roam.corp.google.com/\n\nElijah Newren (5):\n t6423: add tests of dual directory rename plus add/add conflict\n merge-ort: small cleanups of check_for_directory_rename\n merge-ort: make a separate function for freeing struct collisions\n merge-ort: shuffle the computation and cleanup of potential collisions\n merge-ort: fix issue with dual rename and add/add conflict\n\n merge-ort.c | 74 +++++++++++++-------\n t/t6423-merge-rename-directories.sh | 105 ++++++++++++++++++++++++++++\n 2 files changed, 153 insertions(+), 26 deletions(-)\n\n\nbase-commit: e54793a95afeea1e10de1e5ad7eab914e7416250\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1268%2Fnewren%2Ffix-dual-rename-into-each-other-plus-conflicting-adds-v3\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1268/newren/fix-dual-rename-into-each-other-plus-conflicting-adds-v3\nPull-Request: https://github.com/gitgitgadget/git/pull/1268\n\nRange-diff vs v2:\n\n 1: bf4c03d01d5 ! 1: a16a1c4d947 t6423: add tests of dual directory rename plus add/add conflict\n @@ t/t6423-merge-rename-directories.sh: test_expect_success '12k: Directory rename\n +#\n +# Expected: sub3/{file, newfile, sub2/other}\n +# CONFLICT (add/add): sub1/sub2/new_add_add_file\n ++#\n ++# Note that sub1/newfile is not extraneous. Directory renames are only\n ++# detected if they are needed, and they are only needed if the old directory\n ++# had a new file added on the opposite side of history. So sub1/newfile\n ++# is needed for there to be a sub1/ -> sub3/ rename.\n +\n +test_setup_12l () {\n +\ttest_create_repo 12l_$1 &&\n +\t(\n +\t\tcd 12l_$1 &&\n +\n -+\t\tmkdir -p sub1 sub2\n ++\t\tmkdir sub1 sub2\n +\t\techo file >sub1/file &&\n +\t\techo other >sub2/other &&\n +\t\tgit add sub1 sub2 &&\n @@ t/t6423-merge-rename-directories.sh: test_expect_success '12k: Directory rename\n +\n +\t\ttest_must_fail git -c merge.directoryRenames=true merge -s recursive B^0 &&\n +\n -+\t\tgit ls-files -s >out &&\n -+\t\ttest_line_count = 5 out &&\n ++\t\ttest_stdout_line_count = 5 git ls-files -s &&\n +\n +\t\tgit rev-parse >actual \\\n +\t\t\t:0:sub3/file :0:sub3/newfile :0:sub3/sub2/other \\\n @@ t/t6423-merge-rename-directories.sh: test_expect_success '12k: Directory rename\n +\t\ttest_cmp expect actual &&\n +\n +\t\tgit ls-files -o >actual &&\n -+\t\ttest_write_lines actual expect out >expect &&\n ++\t\ttest_write_lines actual expect >expect &&\n +\t\ttest_cmp expect actual\n +\t)\n +'\n @@ t/t6423-merge-rename-directories.sh: test_expect_success '12k: Directory rename\n +\n +\t\ttest_must_fail git -c merge.directoryRenames=true merge -s recursive A^0 &&\n +\n -+\t\tgit ls-files -s >out &&\n -+\t\ttest_line_count = 5 out &&\n ++\t\ttest_stdout_line_count = 5 git ls-files -s &&\n +\n +\t\tgit rev-parse >actual \\\n +\t\t\t:0:sub3/file :0:sub3/newfile :0:sub3/sub2/other \\\n @@ t/t6423-merge-rename-directories.sh: test_expect_success '12k: Directory rename\n +\t\ttest_cmp expect actual &&\n +\n +\t\tgit ls-files -o >actual &&\n -+\t\ttest_write_lines actual expect out >expect &&\n ++\t\ttest_write_lines actual expect >expect &&\n +\t\ttest_cmp expect actual\n +\t)\n +'\n -: ----------- > 2: 297fef60b19 merge-ort: small cleanups of check_for_directory_rename\n -: ----------- > 3: f5f87acbbd2 merge-ort: make a separate function for freeing struct collisions\n 2: cfa38f01481 ! 4: d3eac3d0bf6 merge-ort: shuffle the computation and cleanup of potential collisions\n @@ Commit message\n Signed-off-by: Elijah Newren \n \n ## merge-ort.c ##\n -@@ merge-ort.c: static void compute_collisions(struct strmap *collisions,\n - \t}\n - }\n - \n -+static void free_collisions(struct strmap *collisions)\n -+{\n -+\tstruct hashmap_iter iter;\n -+\tstruct strmap_entry *entry;\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 -+}\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 @@ merge-ort.c: static char *check_for_directory_rename(struct merge_options *opt,\n \t}\n \n @@ merge-ort.c: static int detect_regular_renames(struct merge_options *opt,\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 @@ merge-ort.c: 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 +-\tfree_collisions(&collisions);\n \treturn clean;\n }\n \n 3: da3ae38e390 ! 5: 121761e26e2 merge-ort: fix issue with dual rename and add/add conflict\n @@ Commit message\n ## merge-ort.c ##\n @@ merge-ort.c: static char *check_for_directory_rename(struct merge_options *opt,\n \tstruct strmap_entry *rename_info;\n - \tstruct strmap_entry *otherinfo = NULL;\n + \tstruct strmap_entry *otherinfo;\n \tconst char *new_dir;\n +\tint other_side = 3 - side_index;\n \n +-\t/* Cases where we don't have a directory rename for this path */\n +\t/*\n +\t * Cases where we don't have or don't want a directory rename for\n -+\t * this path, so we return NULL.\n ++\t * this path.\n +\t */\n \tif (strmap_empty(dir_renames))\n - \t\treturn new_path;\n + \t\treturn NULL;\n +\tif (strmap_get(&collisions[other_side], path))\n -+\t\treturn new_path;\n ++\t\treturn NULL;\n \trename_info = check_dir_renamed(path, dir_renames);\n \tif (!rename_info)\n - \t\treturn new_path;\n + \t\treturn NULL;\n \n ## t/t6423-merge-rename-directories.sh ##\n @@ t/t6423-merge-rename-directories.sh: test_setup_12l () {\n\n-- \ngitgitgadget\n"},{"id":"458339","messageId":"a16a1c4d947d66751db1a4c0ab832c67fc3c9ce2.1656653000.git.gitgitgadget@gmail.com","threadId":"58046","inReplyTo":"pull.1268.v3.git.1656653000.gitgitgadget@gmail.com","subject":"[PATCH v3 1/5] t6423: add tests of dual directory rename plus add/add conflict","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-07-01T05:23:16Z","receivedAt":"2022-07-01T05:23:29Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nThis is an attempt at minimalizing a testcase reported by Glen Choo\nwith tensorflow where merge-ort would report an assertion failure:\n\n Assertion failed: (ci->filemask == 2 || ci->filemask == 4), function apply_directory_rename_modifications, file merge-ort.c, line 2410\n\nreversing the direction of the merge provides a different error:\n\n error: cache entry has null sha1: ...\n fatal: unable to write .git/index\n\nso we add testcases for both. With these new testcases, the\nrecursive strategy differs in that it returns the latter error for\nboth merge directions.\n\nThese testcases are somehow a little different than Glen's original\ntensorflow testcase in that these ones trigger a bug with the recursive\nalgorithm whereas his testcase didn't. I figure that means these\ntestcases somehow manage to be more comprehensive.\n\nReported-by: Glen Choo \nSigned-off-by: Elijah Newren \n---\n t/t6423-merge-rename-directories.sh | 105 ++++++++++++++++++++++++++++\n 1 file changed, 105 insertions(+)\n\ndiff --git a/t/t6423-merge-rename-directories.sh b/t/t6423-merge-rename-directories.sh\nindex 479db32cd62..ed5586de28c 100755\n--- a/t/t6423-merge-rename-directories.sh\n+++ b/t/t6423-merge-rename-directories.sh\n@@ -5199,6 +5199,111 @@ test_expect_success '12k: Directory rename with sibling causes rename-to-self' '\n \t)\n '\n \n+# Testcase 12l, Both sides rename a directory into the other side, both add\n+# a file which after directory renames are the same filename\n+# Commit O: sub1/file, sub2/other\n+# Commit A: sub3/file, sub2/{other, new_add_add_file_1}\n+# Commit B: sub1/{file, newfile}, sub1/sub2/{other, new_add_add_file_2}\n+#\n+# In words:\n+# A: sub1/ -> sub3/, add sub2/new_add_add_file_1\n+# B: sub2/ -> sub1/sub2, add sub1/newfile, add sub1/sub2/new_add_add_file_2\n+#\n+# Expected: sub3/{file, newfile, sub2/other}\n+# CONFLICT (add/add): sub1/sub2/new_add_add_file\n+#\n+# Note that sub1/newfile is not extraneous. Directory renames are only\n+# detected if they are needed, and they are only needed if the old directory\n+# had a new file added on the opposite side of history. So sub1/newfile\n+# is needed for there to be a sub1/ -> sub3/ rename.\n+\n+test_setup_12l () {\n+\ttest_create_repo 12l_$1 &&\n+\t(\n+\t\tcd 12l_$1 &&\n+\n+\t\tmkdir sub1 sub2\n+\t\techo file >sub1/file &&\n+\t\techo other >sub2/other &&\n+\t\tgit add sub1 sub2 &&\n+\t\tgit commit -m \"O\" &&\n+\n+\t\tgit branch O &&\n+\t\tgit branch A &&\n+\t\tgit branch B &&\n+\n+\t\tgit checkout A &&\n+\t\tgit mv sub1 sub3 &&\n+\t\techo conflicting >sub2/new_add_add_file &&\n+\t\tgit add sub2 &&\n+\t\ttest_tick &&\n+\t\tgit add -u &&\n+\t\tgit commit -m \"A\" &&\n+\n+\t\tgit checkout B &&\n+\t\techo dissimilar >sub2/new_add_add_file &&\n+\t\techo brand >sub1/newfile &&\n+\t\tgit add sub1 sub2 &&\n+\t\tgit mv sub2 sub1 &&\n+\t\ttest_tick &&\n+\t\tgit commit -m \"B\"\n+\t)\n+}\n+\n+test_expect_merge_algorithm failure failure '12l (B into A): Rename into each other + add/add conflict' '\n+\ttest_setup_12l BintoA &&\n+\t(\n+\t\tcd 12l_BintoA &&\n+\n+\t\tgit checkout -q A^0 &&\n+\n+\t\ttest_must_fail git -c merge.directoryRenames=true merge -s recursive B^0 &&\n+\n+\t\ttest_stdout_line_count = 5 git ls-files -s &&\n+\n+\t\tgit rev-parse >actual \\\n+\t\t\t:0:sub3/file :0:sub3/newfile :0:sub3/sub2/other \\\n+\t\t\t:2:sub1/sub2/new_add_add_file \\\n+\t\t\t:3:sub1/sub2/new_add_add_file &&\n+\t\tgit rev-parse >expect \\\n+\t\t\tO:sub1/file B:sub1/newfile O:sub2/other \\\n+\t\t\tA:sub2/new_add_add_file \\\n+\t\t\tB:sub1/sub2/new_add_add_file &&\n+\t\ttest_cmp expect actual &&\n+\n+\t\tgit ls-files -o >actual &&\n+\t\ttest_write_lines actual expect >expect &&\n+\t\ttest_cmp expect actual\n+\t)\n+'\n+\n+test_expect_merge_algorithm failure failure '12l (A into B): Rename into each other + add/add conflict' '\n+\ttest_setup_12l AintoB &&\n+\t(\n+\t\tcd 12l_AintoB &&\n+\n+\t\tgit checkout -q B^0 &&\n+\n+\t\ttest_must_fail git -c merge.directoryRenames=true merge -s recursive A^0 &&\n+\n+\t\ttest_stdout_line_count = 5 git ls-files -s &&\n+\n+\t\tgit rev-parse >actual \\\n+\t\t\t:0:sub3/file :0:sub3/newfile :0:sub3/sub2/other \\\n+\t\t\t:2:sub1/sub2/new_add_add_file \\\n+\t\t\t:3:sub1/sub2/new_add_add_file &&\n+\t\tgit rev-parse >expect \\\n+\t\t\tO:sub1/file B:sub1/newfile O:sub2/other \\\n+\t\t\tB:sub1/sub2/new_add_add_file \\\n+\t\t\tA:sub2/new_add_add_file &&\n+\t\ttest_cmp expect actual &&\n+\n+\t\tgit ls-files -o >actual &&\n+\t\ttest_write_lines actual expect >expect &&\n+\t\ttest_cmp expect actual\n+\t)\n+'\n+\n ###########################################################################\n # SECTION 13: Checking informational and conflict messages\n #\n-- \ngitgitgadget\n\n"},{"id":"458340","messageId":"297fef60b19b28a24c449eb42948e0e9138cfdaa.1656653000.git.gitgitgadget@gmail.com","threadId":"58046","inReplyTo":"pull.1268.v3.git.1656653000.gitgitgadget@gmail.com","subject":"[PATCH v3 2/5] merge-ort: small cleanups of check_for_directory_rename","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-07-01T05:23:17Z","receivedAt":"2022-07-01T05:23:33Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nNo functional changes, just some preparatory cleanups.\n\nSuggested-by: Ævar Arnfjörð Bjarmason \nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 12 ++++++------\n 1 file changed, 6 insertions(+), 6 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 8545354dafd..ff037cca8d2 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2267,18 +2267,17 @@ 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-\tchar *new_path = NULL;\n+\tchar *new_path;\n \tstruct strmap_entry *rename_info;\n-\tstruct strmap_entry *otherinfo = NULL;\n+\tstruct strmap_entry *otherinfo;\n \tconst char *new_dir;\n \n+\t/* Cases where we don't have a directory rename for this path */\n \tif (strmap_empty(dir_renames))\n-\t\treturn new_path;\n+\t\treturn NULL;\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+\t\treturn NULL;\n \n \t/*\n \t * This next part is a little weird. We do not want to do an\n@@ -2304,6 +2303,7 @@ static char *check_for_directory_rename(struct merge_options *opt,\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+\tnew_dir = rename_info->value; /* old_dir = rename_info->key; */\n \totherinfo = strmap_get_entry(dir_rename_exclusions, new_dir);\n \tif (otherinfo) {\n \t\tpath_msg(opt, rename_info->key, 1,\n-- \ngitgitgadget\n\n"},{"id":"458341","messageId":"f5f87acbbd281966288968288ed78fe053933786.1656653000.git.gitgitgadget@gmail.com","threadId":"58046","inReplyTo":"pull.1268.v3.git.1656653000.gitgitgadget@gmail.com","subject":"[PATCH v3 3/5] merge-ort: make a separate function for freeing struct collisions","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-07-01T05:23:18Z","receivedAt":"2022-07-01T05:23:36Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nThis commit makes no functional changes, it's just some code movement in\npreparation for later changes.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 38 ++++++++++++++++++++++----------------\n 1 file changed, 22 insertions(+), 16 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex ff037cca8d2..1514dd173c0 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2259,6 +2259,27 @@ static void compute_collisions(struct strmap *collisions,\n \t}\n }\n \n+static void free_collisions(struct strmap *collisions)\n+{\n+\tstruct hashmap_iter iter;\n+\tstruct strmap_entry *entry;\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+}\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@@ -3029,8 +3050,6 @@ static int collect_renames(struct merge_options *opt,\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@@ -3076,20 +3095,7 @@ 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+\tfree_collisions(&collisions);\n \treturn clean;\n }\n \n-- \ngitgitgadget\n\n"},{"id":"458342","messageId":"d3eac3d0bf6539d81751813d89ec5158dcb57338.1656653000.git.gitgitgadget@gmail.com","threadId":"58046","inReplyTo":"pull.1268.v3.git.1656653000.gitgitgadget@gmail.com","subject":"[PATCH v3 4/5] merge-ort: shuffle the computation and cleanup of potential collisions","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-07-01T05:23:19Z","receivedAt":"2022-07-01T05:23:38Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nRun compute_collisions() for renames on both sides of history before\nany calls to collect_renames(), and do not free the computed collisions\nuntil after both calls to collect_renames(). This is just a code\nreorganization at this point that doesn't make sense on its own, but\nwill permit us to use the computed collision info from both sides\nwithin each call to collect_renames() in a subsequent commit.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 20 +++++++++++++++-----\n 1 file changed, 15 insertions(+), 5 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 1514dd173c0..b496f0e3803 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2335,7 +2335,8 @@ static char *check_for_directory_rename(struct merge_options *opt,\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\t\t\t\t rename_info,\n+\t\t\t\t\t &collisions[side_index]);\n \t*clean_merge &= (new_path != NULL);\n \n \treturn new_path;\n@@ -3044,16 +3045,15 @@ static int detect_regular_renames(struct merge_options *opt,\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 struct strmap *collisions,\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 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@@ -3069,7 +3069,7 @@ static int collect_renames(struct merge_options *opt,\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 collisions,\n \t\t\t\t\t\t &clean);\n \n \t\tpossibly_cache_new_pair(renames, p, side_index, new_path);\n@@ -3095,7 +3095,6 @@ static int collect_renames(struct merge_options *opt,\n \t\tresult->queue[result->nr++] = p;\n \t}\n \n-\tfree_collisions(&collisions);\n \treturn clean;\n }\n \n@@ -3106,6 +3105,7 @@ static int detect_and_process_renames(struct merge_options *opt,\n {\n \tstruct diff_queue_struct combined = { 0 };\n \tstruct rename_info *renames = &opt->priv->renames;\n+\tstruct strmap collisions[3];\n \tint need_dir_renames, s, i, clean = 1;\n \tunsigned detection_run = 0;\n \n@@ -3155,12 +3155,22 @@ 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+\tfor (int i = MERGE_SIDE1; i <= MERGE_SIDE2; i++) {\n+\t\tint other_side = 3 - i;\n+\t\tcompute_collisions(&collisions[i],\n+\t\t\t\t &renames->dir_renames[other_side],\n+\t\t\t\t &renames->pairs[i]);\n+\t}\n \tclean &= collect_renames(opt, &combined, MERGE_SIDE1,\n+\t\t\t\t collisions,\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 collisions,\n \t\t\t\t &renames->dir_renames[1],\n \t\t\t\t &renames->dir_renames[2]);\n+\tfor (int i = MERGE_SIDE1; i <= MERGE_SIDE2; i++)\n+\t\tfree_collisions(&collisions[i]);\n \tSTABLE_QSORT(combined.queue, combined.nr, compare_pairs);\n \ttrace2_region_leave(\"merge\", \"directory renames\", opt->repo);\n \n-- \ngitgitgadget\n\n"},{"id":"458343","messageId":"121761e26e2468d77910a7bee2e1f18776995c68.1656653000.git.gitgitgadget@gmail.com","threadId":"58046","inReplyTo":"pull.1268.v3.git.1656653000.gitgitgadget@gmail.com","subject":"[PATCH v3 5/5] merge-ort: fix issue with dual rename and add/add conflict","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-07-01T05:23:20Z","receivedAt":"2022-07-01T05:23:41Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nThere is code in both merge-recursive and merge-ort for avoiding doubly\ntransitive renames (i.e. one side renames directory A/ -> B/, and the\nother side renames directory B/ -> C/), because this combination would\notherwise make a mess for new files added to A/ on the first side and\nwondering which directory they end up in -- especially if there were\neven more renames such as the first side renaming C/ -> D/. In such\ncases, it just turns \"off\" directory rename detection for the higher\norder transitive cases.\n\nThe testcases added in t6423 a couple commits ago are slightly different\nbut similar in principle. They involve a similar case of paired\nrenaming but instead of A/ -> B/ and B/ -> C/, the second side renames\na leading directory of B/ to C/. And both sides add a new file\nsomewhere under the directory that the other side will rename. While\nthe new files added start within different directories and thus could\nlogically end up within different directories, it is weird for a file\non one side to end up where the other one started and not move along\nwith it. So, let's just turn off directory rename detection in this\ncase as well.\n\nAnother way to look at this is that if the source name involved in a\ndirectory rename on one side is the target name of a directory rename\noperation for a file from the other side, then we avoid the doubly\ntransitive rename. (More concretely, if a directory rename on side D\nwants to rename a file on side E from OLD_NAME -> NEW_NAME, and side D\nalready had a file named NEW_NAME, and a directory rename on side E\nwants to rename side D's NEW_NAME -> NEWER_NAME, then we turn off the\ndirectory rename detection for NEW_NAME to prevent the\nNEW_NAME -> NEWER_NAME rename, and instead end up with an add/add\nconflict on NEW_NAME.)\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 8 +++++++-\n t/t6423-merge-rename-directories.sh | 4 ++--\n 2 files changed, 9 insertions(+), 3 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex b496f0e3803..daa0e4496f8 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2292,10 +2292,16 @@ static char *check_for_directory_rename(struct merge_options *opt,\n \tstruct strmap_entry *rename_info;\n \tstruct strmap_entry *otherinfo;\n \tconst char *new_dir;\n+\tint other_side = 3 - side_index;\n \n-\t/* Cases where we don't have a directory rename for this path */\n+\t/*\n+\t * Cases where we don't have or don't want a directory rename for\n+\t * this path.\n+\t */\n \tif (strmap_empty(dir_renames))\n \t\treturn NULL;\n+\tif (strmap_get(&collisions[other_side], path))\n+\t\treturn NULL;\n \trename_info = check_dir_renamed(path, dir_renames);\n \tif (!rename_info)\n \t\treturn NULL;\ndiff --git a/t/t6423-merge-rename-directories.sh b/t/t6423-merge-rename-directories.sh\nindex ed5586de28c..99baf77cbfd 100755\n--- a/t/t6423-merge-rename-directories.sh\n+++ b/t/t6423-merge-rename-directories.sh\n@@ -5250,7 +5250,7 @@ test_setup_12l () {\n \t)\n }\n \n-test_expect_merge_algorithm failure failure '12l (B into A): Rename into each other + add/add conflict' '\n+test_expect_merge_algorithm failure success '12l (B into A): Rename into each other + add/add conflict' '\n \ttest_setup_12l BintoA &&\n \t(\n \t\tcd 12l_BintoA &&\n@@ -5277,7 +5277,7 @@ test_expect_merge_algorithm failure failure '12l (B into A): Rename into each ot\n \t)\n '\n \n-test_expect_merge_algorithm failure failure '12l (A into B): Rename into each other + add/add conflict' '\n+test_expect_merge_algorithm failure success '12l (A into B): Rename into each other + add/add conflict' '\n \ttest_setup_12l AintoB &&\n \t(\n \t\tcd 12l_AintoB &&\n-- \ngitgitgadget\n"},{"id":"458346","messageId":"220701.86o7y9b2ys.gmgdl@evledraar.gmail.com","threadId":"58046","inReplyTo":"d3eac3d0bf6539d81751813d89ec5158dcb57338.1656653000.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v3 4/5] merge-ort: shuffle the computation and cleanup of potential collisions","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2022-07-01T09:16:33Z","receivedAt":"2022-07-01T09:24:32Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Fri, Jul 01 2022, Elijah Newren via GitGitGadget wrote:\n\n> From: Elijah Newren \n>\n> Run compute_collisions() for renames on both sides of history before\n> any calls to collect_renames(), and do not free the computed collisions\n> until after both calls to collect_renames(). This is just a code\n> reorganization at this point that doesn't make sense on its own, but\n> will permit us to use the computed collision info from both sides\n> within each call to collect_renames() in a subsequent commit.\n>\n> Signed-off-by: Elijah Newren \n\nThis is much easier to read & review with the prep patches, thanks a\nlot.\n\nB.t.w. on the \"legacy code\" comment wrt merge-{ort,recursive}.c : I\ndidn't look in that case, but I've seen that you've copied various older\ncode from merge-recursive.c to merge-ort.c (which makes sense) in the\npast, but I didn't check the origin in that case. Sorry :)\n\n> @@ -3106,6 +3105,7 @@ static int detect_and_process_renames(struct merge_options *opt,\n> {\n> \tstruct diff_queue_struct combined = { 0 };\n> \tstruct rename_info *renames = &opt->priv->renames;\n> +\tstruct strmap collisions[3];\n> \tint need_dir_renames, s, i, clean = 1;\n> \tunsigned detection_run = 0;\n> \n> @@ -3155,12 +3155,22 @@ 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> +\tfor (int i = MERGE_SIDE1; i <= MERGE_SIDE2; i++) {\n\nThe \"int i\" here will need to be pre-declared earlier, per: 6563706568b\n(CodingGuidelines: give deadline for \"for (int i = 0; ...\", 2022-03-30)\n\nI also don't mind us just saying \"we've waited enough\". Junio?\n\n> +\t\tint other_side = 3 - i;\n> +\t\tcompute_collisions(&collisions[i],\n> +\t\t\t\t &renames->dir_renames[other_side],\n> +\t\t\t\t &renames->pairs[i]);\n> +\t}\n> \tclean &= collect_renames(opt, &combined, MERGE_SIDE1,\n> +\t\t\t\t collisions,\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 collisions,\n> \t\t\t\t &renames->dir_renames[1],\n> \t\t\t\t &renames->dir_renames[2]);\n> +\tfor (int i = MERGE_SIDE1; i <= MERGE_SIDE2; i++)\n> +\t\tfree_collisions(&collisions[i]);\n> \tSTABLE_QSORT(combined.queue, combined.nr, compare_pairs);\n> \ttrace2_region_leave(\"merge\", \"directory renames\", opt->repo);\n\n"},{"id":"458350","messageId":"220701.86bku9b2cb.gmgdl@evledraar.gmail.com","threadId":"58046","inReplyTo":"CABPp-BEcojvfeuhp7rSi-O+9oEu4KpwPDwbKS-MiD1qCKde-CA@mail.gmail.com","subject":"Re: [PATCH v2 1/3] t6423: add tests of dual directory rename plus add/add conflict","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2022-07-01T09:29:32Z","receivedAt":"2022-07-01T09:37:46Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Thu, Jun 30 2022, Elijah Newren wrote:\n\n> On Thu, Jun 30, 2022 at 3:26 AM Ævar Arnfjörð Bjarmason\n> wrote:\n>>\n>> On Thu, Jun 30 2022, Elijah Newren via GitGitGadget wrote:\n>>\n>> > From: Elijah Newren \n>>\n>> > +test_setup_12l () {\n>> > + test_create_repo 12l_$1 &&\n>>\n>> Can & should just be \"git init\", see f0d4d398e28 (test-lib: split up and\n>> deprecate test_create_repo(), 2021-05-10).\n>\n> I've switched to \"git init\" and even encouraged others to do the same\n> in other test scripts, but since literally every other test in this\n> file uses test_create_repo, I think they should all be converted at\n> once and just be consistent here. But, so we can stop having this\n> conversation, after this series lands, I'll send one in to update the\n> various merge testfiles that make heavy use of test_create_repo and\n> convert them over.\n\nSorry, genuinely I didn't mean to mention it again, just saw it scroll\npast & wondered if it was intentional. I'm fine with keeping it...\n\n>> > + (\n>> > + cd 12l_$1 &&\n>> > +\n>> > + mkdir -p sub1 sub2\n>>\n>> The \"-p\" here isn't needed, you're not creating recursive directories.\n>\n> Indeed; will fix.\n\nThanks!\n\n>> > + git ls-files -s >out &&\n>> > + test_line_count = 5 out &&\n>>\n>> Can't this just use test_stdout_line_count? Except...\n>\n> Ooh, new function from late last year that I was unaware of. Yeah,\n> I'm happy to start using it.\n>\n>> > +\n>> > + git rev-parse >actual \\\n>> > + :0:sub3/file :0:sub3/newfile :0:sub3/sub2/other \\\n>> > + :2:sub1/sub2/new_add_add_file \\\n>> > + :3:sub1/sub2/new_add_add_file &&\n>> > + git rev-parse >expect \\\n>> > + O:sub1/file B:sub1/newfile O:sub2/other \\\n>> > + A:sub2/new_add_add_file \\\n>> > + B:sub1/sub2/new_add_add_file &&\n>> > + test_cmp expect actual &&\n>> > +\n>> > + git ls-files -o >actual &&\n>> > + test_write_lines actual expect out >expect &&\n>> > + test_cmp expect actual\n>>\n>> This test seems a bit odd, here we're just checking that we've created\n>> scratch files for the internal use of our test, why is it important that\n>> we have an \"out\" file, when the only reason we have it is because we\n>> needed it for checking the \"ls-files\" line count above?\n>\n> Nah, you've misunderstood the purpose of the check. It isn't \"make\n> sure that these untracked files are present among whatever else might\n> also be present\", it's \"make sure the merge step did not introduce\n> *any* untracked files\" (something the recursive backend periodically\n> did, and they weren't cruft untracked files but stored actual merge\n> results). \n\nAh, thanks!\n\n> There wasn't a nice easy check for that, the closest was to\n> translate the requirement to \"make sure the only untracked files are\n> the ones explicitly added by this test script\", which is the check you\n> see here. I don't actually care about \"actual\", \"expect\", or \"out\", I\n> just care that there aren't any _other_ untracked files.\n\nI'm fine with keeping this as-is, but FWIW perhaps this pattern is more\nexplicit about the intent:\n\n\ttest_expect_success 'do merge stuff' '\n\t\t... &&\n\t\trm -f expect actual &&\n\t\tgit ls-files -o ':!out' >out &&\n\t\ttest_must_be_empty out\n\t'\n\nOr piping it to \".git/out\", to avoid the path exclude, but like this is\nalso fine:) Thanks.\n"},{"id":"458460","messageId":"pull.1268.v4.git.1656984823.gitgitgadget@gmail.com","threadId":"58046","inReplyTo":"pull.1268.v3.git.1656653000.gitgitgadget@gmail.com","subject":"[PATCH v4 0/5] Fix dual rename into each other plus conflicting adds","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-07-05T01:33:38Z","receivedAt":"2022-07-05T01:33:51Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This series adds some testcases based on the tensorflow repository issue\nreported by Glen Choo at [1], demonstrating bugs in both the ort and\nrecursive strategies. It also provides a fix for the ort strategy.\n\nChanges since v3:\n\n * Remove use of for-initializer\n\nChanges since v2:\n\n * Added a couple preparatory cleanup patches\n * Added a comment about why sub1/newfile is important to the new testcases\n * A couple other minor code cleanups\n\nChanges since v1:\n\n * Fixed some wording issues in comments, and added a bit more details to\n one of the commit messages\n\n[1]\nhttps://lore.kernel.org/git/kl6lee006mle.fsf@chooglen-macbookpro.roam.corp.google.com/\n\nElijah Newren (5):\n t6423: add tests of dual directory rename plus add/add conflict\n merge-ort: small cleanups of check_for_directory_rename\n merge-ort: make a separate function for freeing struct collisions\n merge-ort: shuffle the computation and cleanup of potential collisions\n merge-ort: fix issue with dual rename and add/add conflict\n\n merge-ort.c | 74 +++++++++++++-------\n t/t6423-merge-rename-directories.sh | 105 ++++++++++++++++++++++++++++\n 2 files changed, 153 insertions(+), 26 deletions(-)\n\n\nbase-commit: e54793a95afeea1e10de1e5ad7eab914e7416250\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1268%2Fnewren%2Ffix-dual-rename-into-each-other-plus-conflicting-adds-v4\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1268/newren/fix-dual-rename-into-each-other-plus-conflicting-adds-v4\nPull-Request: https://github.com/gitgitgadget/git/pull/1268\n\nRange-diff vs v3:\n\n 1: a16a1c4d947 = 1: a16a1c4d947 t6423: add tests of dual directory rename plus add/add conflict\n 2: 297fef60b19 = 2: 297fef60b19 merge-ort: small cleanups of check_for_directory_rename\n 3: f5f87acbbd2 = 3: f5f87acbbd2 merge-ort: make a separate function for freeing struct collisions\n 4: d3eac3d0bf6 ! 4: 9d813116112 merge-ort: shuffle the computation and cleanup of potential collisions\n @@ merge-ort.c: 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 -+\tfor (int i = MERGE_SIDE1; i <= MERGE_SIDE2; i++) {\n ++\tfor (i = MERGE_SIDE1; i <= MERGE_SIDE2; i++) {\n +\t\tint other_side = 3 - i;\n +\t\tcompute_collisions(&collisions[i],\n +\t\t\t\t &renames->dir_renames[other_side],\n @@ merge-ort.c: static int detect_and_process_renames(struct merge_options *opt,\n +\t\t\t\t collisions,\n \t\t\t\t &renames->dir_renames[1],\n \t\t\t\t &renames->dir_renames[2]);\n -+\tfor (int i = MERGE_SIDE1; i <= MERGE_SIDE2; i++)\n ++\tfor (i = MERGE_SIDE1; i <= MERGE_SIDE2; i++)\n +\t\tfree_collisions(&collisions[i]);\n \tSTABLE_QSORT(combined.queue, combined.nr, compare_pairs);\n \ttrace2_region_leave(\"merge\", \"directory renames\", opt->repo);\n 5: 121761e26e2 = 5: 993ac405408 merge-ort: fix issue with dual rename and add/add conflict\n\n-- \ngitgitgadget\n"},{"id":"458461","messageId":"a16a1c4d947d66751db1a4c0ab832c67fc3c9ce2.1656984823.git.gitgitgadget@gmail.com","threadId":"58046","inReplyTo":"pull.1268.v4.git.1656984823.gitgitgadget@gmail.com","subject":"[PATCH v4 1/5] t6423: add tests of dual directory rename plus add/add conflict","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-07-05T01:33:39Z","receivedAt":"2022-07-05T01:33:57Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nThis is an attempt at minimalizing a testcase reported by Glen Choo\nwith tensorflow where merge-ort would report an assertion failure:\n\n Assertion failed: (ci->filemask == 2 || ci->filemask == 4), function apply_directory_rename_modifications, file merge-ort.c, line 2410\n\nreversing the direction of the merge provides a different error:\n\n error: cache entry has null sha1: ...\n fatal: unable to write .git/index\n\nso we add testcases for both. With these new testcases, the\nrecursive strategy differs in that it returns the latter error for\nboth merge directions.\n\nThese testcases are somehow a little different than Glen's original\ntensorflow testcase in that these ones trigger a bug with the recursive\nalgorithm whereas his testcase didn't. I figure that means these\ntestcases somehow manage to be more comprehensive.\n\nReported-by: Glen Choo \nSigned-off-by: Elijah Newren \n---\n t/t6423-merge-rename-directories.sh | 105 ++++++++++++++++++++++++++++\n 1 file changed, 105 insertions(+)\n\ndiff --git a/t/t6423-merge-rename-directories.sh b/t/t6423-merge-rename-directories.sh\nindex 479db32cd62..ed5586de28c 100755\n--- a/t/t6423-merge-rename-directories.sh\n+++ b/t/t6423-merge-rename-directories.sh\n@@ -5199,6 +5199,111 @@ test_expect_success '12k: Directory rename with sibling causes rename-to-self' '\n \t)\n '\n \n+# Testcase 12l, Both sides rename a directory into the other side, both add\n+# a file which after directory renames are the same filename\n+# Commit O: sub1/file, sub2/other\n+# Commit A: sub3/file, sub2/{other, new_add_add_file_1}\n+# Commit B: sub1/{file, newfile}, sub1/sub2/{other, new_add_add_file_2}\n+#\n+# In words:\n+# A: sub1/ -> sub3/, add sub2/new_add_add_file_1\n+# B: sub2/ -> sub1/sub2, add sub1/newfile, add sub1/sub2/new_add_add_file_2\n+#\n+# Expected: sub3/{file, newfile, sub2/other}\n+# CONFLICT (add/add): sub1/sub2/new_add_add_file\n+#\n+# Note that sub1/newfile is not extraneous. Directory renames are only\n+# detected if they are needed, and they are only needed if the old directory\n+# had a new file added on the opposite side of history. So sub1/newfile\n+# is needed for there to be a sub1/ -> sub3/ rename.\n+\n+test_setup_12l () {\n+\ttest_create_repo 12l_$1 &&\n+\t(\n+\t\tcd 12l_$1 &&\n+\n+\t\tmkdir sub1 sub2\n+\t\techo file >sub1/file &&\n+\t\techo other >sub2/other &&\n+\t\tgit add sub1 sub2 &&\n+\t\tgit commit -m \"O\" &&\n+\n+\t\tgit branch O &&\n+\t\tgit branch A &&\n+\t\tgit branch B &&\n+\n+\t\tgit checkout A &&\n+\t\tgit mv sub1 sub3 &&\n+\t\techo conflicting >sub2/new_add_add_file &&\n+\t\tgit add sub2 &&\n+\t\ttest_tick &&\n+\t\tgit add -u &&\n+\t\tgit commit -m \"A\" &&\n+\n+\t\tgit checkout B &&\n+\t\techo dissimilar >sub2/new_add_add_file &&\n+\t\techo brand >sub1/newfile &&\n+\t\tgit add sub1 sub2 &&\n+\t\tgit mv sub2 sub1 &&\n+\t\ttest_tick &&\n+\t\tgit commit -m \"B\"\n+\t)\n+}\n+\n+test_expect_merge_algorithm failure failure '12l (B into A): Rename into each other + add/add conflict' '\n+\ttest_setup_12l BintoA &&\n+\t(\n+\t\tcd 12l_BintoA &&\n+\n+\t\tgit checkout -q A^0 &&\n+\n+\t\ttest_must_fail git -c merge.directoryRenames=true merge -s recursive B^0 &&\n+\n+\t\ttest_stdout_line_count = 5 git ls-files -s &&\n+\n+\t\tgit rev-parse >actual \\\n+\t\t\t:0:sub3/file :0:sub3/newfile :0:sub3/sub2/other \\\n+\t\t\t:2:sub1/sub2/new_add_add_file \\\n+\t\t\t:3:sub1/sub2/new_add_add_file &&\n+\t\tgit rev-parse >expect \\\n+\t\t\tO:sub1/file B:sub1/newfile O:sub2/other \\\n+\t\t\tA:sub2/new_add_add_file \\\n+\t\t\tB:sub1/sub2/new_add_add_file &&\n+\t\ttest_cmp expect actual &&\n+\n+\t\tgit ls-files -o >actual &&\n+\t\ttest_write_lines actual expect >expect &&\n+\t\ttest_cmp expect actual\n+\t)\n+'\n+\n+test_expect_merge_algorithm failure failure '12l (A into B): Rename into each other + add/add conflict' '\n+\ttest_setup_12l AintoB &&\n+\t(\n+\t\tcd 12l_AintoB &&\n+\n+\t\tgit checkout -q B^0 &&\n+\n+\t\ttest_must_fail git -c merge.directoryRenames=true merge -s recursive A^0 &&\n+\n+\t\ttest_stdout_line_count = 5 git ls-files -s &&\n+\n+\t\tgit rev-parse >actual \\\n+\t\t\t:0:sub3/file :0:sub3/newfile :0:sub3/sub2/other \\\n+\t\t\t:2:sub1/sub2/new_add_add_file \\\n+\t\t\t:3:sub1/sub2/new_add_add_file &&\n+\t\tgit rev-parse >expect \\\n+\t\t\tO:sub1/file B:sub1/newfile O:sub2/other \\\n+\t\t\tB:sub1/sub2/new_add_add_file \\\n+\t\t\tA:sub2/new_add_add_file &&\n+\t\ttest_cmp expect actual &&\n+\n+\t\tgit ls-files -o >actual &&\n+\t\ttest_write_lines actual expect >expect &&\n+\t\ttest_cmp expect actual\n+\t)\n+'\n+\n ###########################################################################\n # SECTION 13: Checking informational and conflict messages\n #\n-- \ngitgitgadget\n\n"},{"id":"458462","messageId":"297fef60b19b28a24c449eb42948e0e9138cfdaa.1656984823.git.gitgitgadget@gmail.com","threadId":"58046","inReplyTo":"pull.1268.v4.git.1656984823.gitgitgadget@gmail.com","subject":"[PATCH v4 2/5] merge-ort: small cleanups of check_for_directory_rename","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-07-05T01:33:40Z","receivedAt":"2022-07-05T01:33:58Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nNo functional changes, just some preparatory cleanups.\n\nSuggested-by: Ævar Arnfjörð Bjarmason \nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 12 ++++++------\n 1 file changed, 6 insertions(+), 6 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 8545354dafd..ff037cca8d2 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2267,18 +2267,17 @@ 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-\tchar *new_path = NULL;\n+\tchar *new_path;\n \tstruct strmap_entry *rename_info;\n-\tstruct strmap_entry *otherinfo = NULL;\n+\tstruct strmap_entry *otherinfo;\n \tconst char *new_dir;\n \n+\t/* Cases where we don't have a directory rename for this path */\n \tif (strmap_empty(dir_renames))\n-\t\treturn new_path;\n+\t\treturn NULL;\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+\t\treturn NULL;\n \n \t/*\n \t * This next part is a little weird. We do not want to do an\n@@ -2304,6 +2303,7 @@ static char *check_for_directory_rename(struct merge_options *opt,\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+\tnew_dir = rename_info->value; /* old_dir = rename_info->key; */\n \totherinfo = strmap_get_entry(dir_rename_exclusions, new_dir);\n \tif (otherinfo) {\n \t\tpath_msg(opt, rename_info->key, 1,\n-- \ngitgitgadget\n\n"},{"id":"458463","messageId":"f5f87acbbd281966288968288ed78fe053933786.1656984823.git.gitgitgadget@gmail.com","threadId":"58046","inReplyTo":"pull.1268.v4.git.1656984823.gitgitgadget@gmail.com","subject":"[PATCH v4 3/5] merge-ort: make a separate function for freeing struct collisions","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-07-05T01:33:41Z","receivedAt":"2022-07-05T01:34:00Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nThis commit makes no functional changes, it's just some code movement in\npreparation for later changes.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 38 ++++++++++++++++++++++----------------\n 1 file changed, 22 insertions(+), 16 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex ff037cca8d2..1514dd173c0 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2259,6 +2259,27 @@ static void compute_collisions(struct strmap *collisions,\n \t}\n }\n \n+static void free_collisions(struct strmap *collisions)\n+{\n+\tstruct hashmap_iter iter;\n+\tstruct strmap_entry *entry;\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+}\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@@ -3029,8 +3050,6 @@ static int collect_renames(struct merge_options *opt,\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@@ -3076,20 +3095,7 @@ 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+\tfree_collisions(&collisions);\n \treturn clean;\n }\n \n-- \ngitgitgadget\n\n"},{"id":"458464","messageId":"9d813116112fb3d841480baad8d939aa7c714811.1656984823.git.gitgitgadget@gmail.com","threadId":"58046","inReplyTo":"pull.1268.v4.git.1656984823.gitgitgadget@gmail.com","subject":"[PATCH v4 4/5] merge-ort: shuffle the computation and cleanup of potential collisions","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-07-05T01:33:42Z","receivedAt":"2022-07-05T01:34:02Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nRun compute_collisions() for renames on both sides of history before\nany calls to collect_renames(), and do not free the computed collisions\nuntil after both calls to collect_renames(). This is just a code\nreorganization at this point that doesn't make sense on its own, but\nwill permit us to use the computed collision info from both sides\nwithin each call to collect_renames() in a subsequent commit.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 20 +++++++++++++++-----\n 1 file changed, 15 insertions(+), 5 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 1514dd173c0..a37c1c19aca 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2335,7 +2335,8 @@ static char *check_for_directory_rename(struct merge_options *opt,\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\t\t\t\t rename_info,\n+\t\t\t\t\t &collisions[side_index]);\n \t*clean_merge &= (new_path != NULL);\n \n \treturn new_path;\n@@ -3044,16 +3045,15 @@ static int detect_regular_renames(struct merge_options *opt,\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 struct strmap *collisions,\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 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@@ -3069,7 +3069,7 @@ static int collect_renames(struct merge_options *opt,\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 collisions,\n \t\t\t\t\t\t &clean);\n \n \t\tpossibly_cache_new_pair(renames, p, side_index, new_path);\n@@ -3095,7 +3095,6 @@ static int collect_renames(struct merge_options *opt,\n \t\tresult->queue[result->nr++] = p;\n \t}\n \n-\tfree_collisions(&collisions);\n \treturn clean;\n }\n \n@@ -3106,6 +3105,7 @@ static int detect_and_process_renames(struct merge_options *opt,\n {\n \tstruct diff_queue_struct combined = { 0 };\n \tstruct rename_info *renames = &opt->priv->renames;\n+\tstruct strmap collisions[3];\n \tint need_dir_renames, s, i, clean = 1;\n \tunsigned detection_run = 0;\n \n@@ -3155,12 +3155,22 @@ 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+\tfor (i = MERGE_SIDE1; i <= MERGE_SIDE2; i++) {\n+\t\tint other_side = 3 - i;\n+\t\tcompute_collisions(&collisions[i],\n+\t\t\t\t &renames->dir_renames[other_side],\n+\t\t\t\t &renames->pairs[i]);\n+\t}\n \tclean &= collect_renames(opt, &combined, MERGE_SIDE1,\n+\t\t\t\t collisions,\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 collisions,\n \t\t\t\t &renames->dir_renames[1],\n \t\t\t\t &renames->dir_renames[2]);\n+\tfor (i = MERGE_SIDE1; i <= MERGE_SIDE2; i++)\n+\t\tfree_collisions(&collisions[i]);\n \tSTABLE_QSORT(combined.queue, combined.nr, compare_pairs);\n \ttrace2_region_leave(\"merge\", \"directory renames\", opt->repo);\n \n-- \ngitgitgadget\n\n"},{"id":"458465","messageId":"993ac4054087846bde0261a309167eb947c27f50.1656984824.git.gitgitgadget@gmail.com","threadId":"58046","inReplyTo":"pull.1268.v4.git.1656984823.gitgitgadget@gmail.com","subject":"[PATCH v4 5/5] merge-ort: fix issue with dual rename and add/add conflict","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-07-05T01:33:43Z","receivedAt":"2022-07-05T01:34:05Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nThere is code in both merge-recursive and merge-ort for avoiding doubly\ntransitive renames (i.e. one side renames directory A/ -> B/, and the\nother side renames directory B/ -> C/), because this combination would\notherwise make a mess for new files added to A/ on the first side and\nwondering which directory they end up in -- especially if there were\neven more renames such as the first side renaming C/ -> D/. In such\ncases, it just turns \"off\" directory rename detection for the higher\norder transitive cases.\n\nThe testcases added in t6423 a couple commits ago are slightly different\nbut similar in principle. They involve a similar case of paired\nrenaming but instead of A/ -> B/ and B/ -> C/, the second side renames\na leading directory of B/ to C/. And both sides add a new file\nsomewhere under the directory that the other side will rename. While\nthe new files added start within different directories and thus could\nlogically end up within different directories, it is weird for a file\non one side to end up where the other one started and not move along\nwith it. So, let's just turn off directory rename detection in this\ncase as well.\n\nAnother way to look at this is that if the source name involved in a\ndirectory rename on one side is the target name of a directory rename\noperation for a file from the other side, then we avoid the doubly\ntransitive rename. (More concretely, if a directory rename on side D\nwants to rename a file on side E from OLD_NAME -> NEW_NAME, and side D\nalready had a file named NEW_NAME, and a directory rename on side E\nwants to rename side D's NEW_NAME -> NEWER_NAME, then we turn off the\ndirectory rename detection for NEW_NAME to prevent the\nNEW_NAME -> NEWER_NAME rename, and instead end up with an add/add\nconflict on NEW_NAME.)\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 8 +++++++-\n t/t6423-merge-rename-directories.sh | 4 ++--\n 2 files changed, 9 insertions(+), 3 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex a37c1c19aca..3855f9de25e 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2292,10 +2292,16 @@ static char *check_for_directory_rename(struct merge_options *opt,\n \tstruct strmap_entry *rename_info;\n \tstruct strmap_entry *otherinfo;\n \tconst char *new_dir;\n+\tint other_side = 3 - side_index;\n \n-\t/* Cases where we don't have a directory rename for this path */\n+\t/*\n+\t * Cases where we don't have or don't want a directory rename for\n+\t * this path.\n+\t */\n \tif (strmap_empty(dir_renames))\n \t\treturn NULL;\n+\tif (strmap_get(&collisions[other_side], path))\n+\t\treturn NULL;\n \trename_info = check_dir_renamed(path, dir_renames);\n \tif (!rename_info)\n \t\treturn NULL;\ndiff --git a/t/t6423-merge-rename-directories.sh b/t/t6423-merge-rename-directories.sh\nindex ed5586de28c..99baf77cbfd 100755\n--- a/t/t6423-merge-rename-directories.sh\n+++ b/t/t6423-merge-rename-directories.sh\n@@ -5250,7 +5250,7 @@ test_setup_12l () {\n \t)\n }\n \n-test_expect_merge_algorithm failure failure '12l (B into A): Rename into each other + add/add conflict' '\n+test_expect_merge_algorithm failure success '12l (B into A): Rename into each other + add/add conflict' '\n \ttest_setup_12l BintoA &&\n \t(\n \t\tcd 12l_BintoA &&\n@@ -5277,7 +5277,7 @@ test_expect_merge_algorithm failure failure '12l (B into A): Rename into each ot\n \t)\n '\n \n-test_expect_merge_algorithm failure failure '12l (A into B): Rename into each other + add/add conflict' '\n+test_expect_merge_algorithm failure success '12l (A into B): Rename into each other + add/add conflict' '\n \ttest_setup_12l AintoB &&\n \t(\n \t\tcd 12l_AintoB &&\n-- \ngitgitgadget\n"},{"id":"458528","messageId":"xmqqwncqi3oi.fsf@gitster.g","threadId":"58046","inReplyTo":"pull.1268.v4.git.1656984823.gitgitgadget@gmail.com","subject":"Re: [PATCH v4 0/5] Fix dual rename into each other plus conflicting adds","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-07-06T16:52:45Z","receivedAt":"2022-07-06T16:52:52Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Elijah Newren via GitGitGadget\" writes:\n\n> This series adds some testcases based on the tensorflow repository issue\n> reported by Glen Choo at [1], demonstrating bugs in both the ort and\n> recursive strategies. It also provides a fix for the ort strategy.\n>\n> Changes since v3:\n>\n> * Remove use of for-initializer\n\nI missed them while queuing the previous round and updates look OK.\n\nI however personally find the resulting code irritating to read.\nThe counter 'i', which never is used for two purposes at the same\ntime, has multiple \"hiding\" declarations in this function, in\naddition to its top-level declaration. It forces the readers to\nthink about which variable each reference of 'i' talks about, and\nmore importantly, if the value in outer 'i' of its last use, after\nan inner 'i' is used, matters.\n\nWill queue.\n\nThanks.\n"},{"id":"458530","messageId":"20220706172505.270363-1-jonathantanmy@google.com","threadId":"58046","inReplyTo":"CABPp-BG8r4zUOKZ+DzZOdsEwr+580cK=SvZ4n_euPOV1Nocu+A@mail.gmail.com","subject":"Re: [PATCH 3/3] merge-ort: fix issue with dual rename and add/add conflict","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2022-07-06T17:25:05Z","receivedAt":"2022-07-06T17:25:18Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Sorry for getting back to this so late. I don't have any issues with the\npatches, but just to close the loop:\n\nElijah Newren writes:\n> On Mon, Jun 27, 2022 at 11:47 AM Jonathan Tan wrote:\n> >\n> > \"Elijah Newren via GitGitGadget\" writes:\n> > > The testcases added in t6423 a couple commits ago are slightly different\n> > > but similar in principle. They involve a similar case of paired\n> > > renaming but instead of A/ -> B/ and B/ -> C/, the second side renames\n> > > a leading directory of B/ to C/.\n> >\n> > Hmm...one side moved sub1 -> sub3 and the other moved sub2 from the root\n> > to under sub1, right? So it's more like A/ -> B/ and C/ -> A/C/.\n> \n> Hmm, maybe I should have been more explicit in my mapping:\n> A = sub2\n> B = sub1/sub2\n> leading directory of B = sub1\n> C = sub3\n\nSubstituting into A/ -> B/ and \"a leading directory of B/ to C/\", we\nget:\n\n sub2 -> sub1/sub2 and sub1 -> sub3\n\nwhich is indeed what is happening. I see, thanks.\n\n> > > And both sides add a new file\n> > > somewhere under the directory that the other side will rename.\n> >\n> > Rename or move, I think.\n> \n> I'm confused; I don't understand what this comment means. Renames\n> tend to be created using \"git mv\", before or after making content\n> changes, so to me a file being renamed or a file being moved to a\n> different location are synonymous. What distinction are you making\n> between renames and moves?\n\nI was thinking that a rename means that the directory still has the same\nparent directory, whereas a move means that the directory keeps its\nbasename but has a different parent directory. Maybe it's just the way I\nthink about things, but the important thing here is that a directory was\nmoved so that its parent directory is a directory that is different and\nthat already exists, and I think that this meaning is lost when we say\n\"rename\". But it might just be me.\n\n> Hmm, perhaps I should change this to:\n> \n> /* Cases where we don't have or don't want a directory rename for this\n> path, so we return NULL */\n> \n> The purpose of this function is to check whether a given path would be\n> modified by directory renaming to get a new path. So, \"no new path\"\n> means we don't have an applicable directory rename or don't want to\n> use it.\n\nI see - the new text makes sense.\n\n> > > if (strmap_empty(dir_renames))\n> > > return new_path;\n> > > + if (strmap_get(&collisions[other_side], path))\n> > > + return new_path;\n> >\n> > So as far as I understand, collisions here, for a given side, is a map.\n> > The map's keys are all the filenames of added and renamed files (I'm\n> > assuming that's what 'A' and 'R' are) from that side after any directory\n> > moves on the other side are applied. So, for example, if we add \"foo/a\"\n> > on side A and rename \"foo/\" to \"bar/\" on side B, then side A's collision\n> > map would have a key \"bar/a\". So I'm not sure if \"collision\" is the\n> > right name here, but the existing code already uses it so I'll leave it\n> > be.\n> \n> Let's take your example a bit further, to discuss the original kind of\n> usecase that \"collisions\" was written for. In addition to adding\n> \"foo/a\" on side A, we also add \"foo2/a\" and \"foo3/a\". And then in\n> addition to renaming \"foo/\" to \"bar/\" on side B, we also rename\n> \"foo2/\" to \"bar/\" and \"foo3/\" to \"bar/\", thus merging all of foo/,\n> foo2/, and foo3/ into a single directory named bar/. If the files in\n> foo/, foo2/, and foo3/ on side B were all unique, you can see how\n> there'd be no problem merging these directories together. The problem\n> only comes at merge time when you attempt to apply the directory\n> renames from side B to the new files on side A. That's when you get\n> collisions, in this case three files that would be named bar/a.\n> \n> Checking for such collisions was the purpose of the \"collisions\"\n> metadata, so I think the name is fitting. The only problem is that\n> we're reusing that data now for a slightly different purpose, though I\n> think it's still \"collision-y\".\n\nThat makes sense, thanks.\n\n> > It makes sense that this situation (of side A having \"bar/a\" because\n> > side B renamed \"foo/\" to \"bar/\", and at the same time, side B adds its\n> > own \"bar/a\") is weird, as stated in the commit message, so I don't mind\n> > disabling checking for directory rename in this case. However, in\n> > theory, I don't see how disabling this check would fix anything, since\n> > the bug seems to be about two different files on different sides being\n> > renamed to the same filename through some convoluted means. (Unless this\n> > is the only convoluted means to do it, and disabling it means that the\n> > bug wouldn't occur.)\n\n[snip]\n\n> Hmm...let me see if I can explain this a different way.\n> \n> The short version of the issue here is that if a directory rename\n> wants to rename NEWFILE -> ALTERNATE_NEWFILE, but there is another\n> directory rename on the other side of history that wants to rename\n> ANOTHER_FILE -> NEWFILE, then we run into problems and have to turn\n> off the NEWFILE -> ALTERNATE_NEWFILE. This check here is all about\n> this case.\n> \n> To see why this is the problematic setup...\n> \n> Now a conflict_info\n> stores information about the OIDs and modes for all three sides of the\n> merge (i.e. both sides of the merge and the base). Whenever a rename\n> is processed, we have to update this map, because the rename makes the\n> conflict_info now apply to a different path. In the simple cases, the\n> conflict_info from the source path needs to be merged with the\n> conflict_info for the target path, and the source path's conflict_info\n> needs to be marked as null (literally setting the .is_null field to\n> 1). rename/rename and such can make this a bit more complicated.\n\nAh, I think I was missing this part. The intention is that processing\none side in this way (and thus modifying its conflict_info) would not\naffect the processing of any other sides, but there is a bug that makes\nit not so. (And the intention is not, say, when processing all sides,\nto write the output in a new data structure so that the result is the\nsame no matter the order.)\n\nSo I think the answer to my question is: no, we do not want to be able\nto rename two different files on different sides to the same filename\nthrough any convoluted means, and if that happens, it's a bug.\n\n[snip illustration of what happens in either merge order]\n\n> To avoid this order dependence, and the weird multiple-renaming of a\n> single path, we just want to turn off directory renames when the\n> source of a directory rename on one side is the target of a directory\n> rename on the other. That's what this patch does.\n> \n> \n> Does that help? Or did I make it more confusing?\n\nI think that helped, thanks.\n"},{"id":"459861","messageId":"220725.86zggxpfed.gmgdl@evledraar.gmail.com","threadId":"58046","inReplyTo":"220701.86o7y9b2ys.gmgdl@evledraar.gmail.com","subject":"C99 \"for (int ...\" form on \"master\" (was: [PATCH v3 4/5] merge-ort: shuffle the computation and cleanup of potential collisions)","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2022-07-25T12:00:05Z","receivedAt":"2022-07-25T12:04:32Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Fri, Jul 01 2022, Ævar Arnfjörð Bjarmason wrote:\n\n> On Fri, Jul 01 2022, Elijah Newren via GitGitGadget wrote:\n> [...]\n>> @@ -3106,6 +3105,7 @@ static int detect_and_process_renames(struct merge_options *opt,\n>> {\n>> \tstruct diff_queue_struct combined = { 0 };\n>> \tstruct rename_info *renames = &opt->priv->renames;\n>> +\tstruct strmap collisions[3];\n>> \tint need_dir_renames, s, i, clean = 1;\n>> \tunsigned detection_run = 0;\n>> \n>> @@ -3155,12 +3155,22 @@ 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>> +\tfor (int i = MERGE_SIDE1; i <= MERGE_SIDE2; i++) {\n>\n> The \"int i\" here will need to be pre-declared earlier, per: 6563706568b\n> (CodingGuidelines: give deadline for \"for (int i = 0; ...\", 2022-03-30)\n>\n> I also don't mind us just saying \"we've waited enough\". Junio?\n\nThis case got fixed, but per the changed $subject others have snuck\nthrough.\n\nSince be733e12001 (Merge branch 'en/merge-tree', 2022-07-14) we've had\nthese forms on \"master\", see 6debb7527b0 (merge-ort: store messages in a\nlist, not in a single strbuf, 2022-06-18) and cb2607759e2 (merge-ort:\nstore more specific conflict information, 2022-06-18).\n\nWe could \"fix\" those, but per the above I think it's just as valid to\njust move up the deadline & say that 2.38.0 will have a hard dependency\non this C99 feature...\n"},{"id":"459955","messageId":"CABPp-BHvQwct2WRRYGyzm=YVkjmwBqoe1DUtCicuQW=jrQ2hdA@mail.gmail.com","threadId":"58046","inReplyTo":"220725.86zggxpfed.gmgdl@evledraar.gmail.com","subject":"Re: C99 \"for (int ...\" form on \"master\" (was: [PATCH v3 4/5] merge-ort: shuffle the computation and cleanup of potential collisions)","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2022-07-26T02:14:12Z","receivedAt":"2022-07-26T02:14:27Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Mon, Jul 25, 2022 at 5:04 AM Ævar Arnfjörð Bjarmason\n wrote:\n>\n> On Fri, Jul 01 2022, Ævar Arnfjörð Bjarmason wrote:\n>\n> > On Fri, Jul 01 2022, Elijah Newren via GitGitGadget wrote:\n> > [...]\n> >> @@ -3106,6 +3105,7 @@ static int detect_and_process_renames(struct merge_options *opt,\n> >> {\n> >> struct diff_queue_struct combined = { 0 };\n> >> struct rename_info *renames = &opt->priv->renames;\n> >> + struct strmap collisions[3];\n> >> int need_dir_renames, s, i, clean = 1;\n> >> unsigned detection_run = 0;\n> >>\n> >> @@ -3155,12 +3155,22 @@ static int detect_and_process_renames(struct merge_options *opt,\n> >> ALLOC_GROW(combined.queue,\n> >> renames->pairs[1].nr + renames->pairs[2].nr,\n> >> combined.alloc);\n> >> + for (int i = MERGE_SIDE1; i <= MERGE_SIDE2; i++) {\n> >\n> > The \"int i\" here will need to be pre-declared earlier, per: 6563706568b\n> > (CodingGuidelines: give deadline for \"for (int i = 0; ...\", 2022-03-30)\n> >\n> > I also don't mind us just saying \"we've waited enough\". Junio?\n>\n> This case got fixed, but per the changed $subject others have snuck\n> through.\n>\n> Since be733e12001 (Merge branch 'en/merge-tree', 2022-07-14) we've had\n> these forms on \"master\", see 6debb7527b0 (merge-ort: store messages in a\n> list, not in a single strbuf, 2022-06-18) and cb2607759e2 (merge-ort:\n> store more specific conflict information, 2022-06-18).\n>\n> We could \"fix\" those, but per the above I think it's just as valid to\n> just move up the deadline & say that 2.38.0 will have a hard dependency\n> on this C99 feature...\n\nThanks for catching this and bringing it up; sorry for missing it earlier.\n\n6563706568b says we should \"revisit this *around* November 2022\"\n(emphasis added). 2.38 will be released in October 2022. So, maybe\nit's fine as-is.\n\nBut if others prefer these be fixed over moving up the deadline, I'll\ngo ahead and submit a patch.\n\nI guess we just need a call. Junio?\n"},{"id":"459959","messageId":"xmqqy1wgwkbj.fsf@gitster.g","threadId":"58046","inReplyTo":"CABPp-BHvQwct2WRRYGyzm=YVkjmwBqoe1DUtCicuQW=jrQ2hdA@mail.gmail.com","subject":"Re: C99 \"for (int ...\" form on \"master\"","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-07-26T04:48:32Z","receivedAt":"2022-07-26T04:48:40Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Elijah Newren writes:\n\n> Thanks for catching this and bringing it up; sorry for missing it earlier.\n>\n> 6563706568b says we should \"revisit this *around* November 2022\"\n> (emphasis added). 2.38 will be released in October 2022. So, maybe\n> it's fine as-is.\n>\n> But if others prefer these be fixed over moving up the deadline, I'll\n> go ahead and submit a patch.\n>\n> I guess we just need a call. Junio?\n\nI do not see a need to do anything special at this moment.\n\nWhen somebody reports that their favorite compiler does not yet grok\nthe syntax, we can ask them to ensure that there are only two places\nthat need \"fixing\" for them to compile. It would have been ideal if\nwe kept the \"weather balloon\" to the only one known place, but the\nsecond one would not be a disaster.\n\nWe would re-evaluate the situation when such a report comes, but\neven if we decide to stay away from the syntax a bit longer, we know\nexactly where the only two places we need to revert are.\n\nOne thing we should absolutely avoid is to open the floodgate and\ndeliberately add more of them, just for the sake of adding more of\nthem.\n\nThanks.\n\nP.S. Tomorrow is that \"gitster goes offline every other Tuesday\"\nday.\n"}]}