Directory rename detection testcases and rules
PATCH 3/4 t6423: update directory rename detection tests with new rule
In reply to Elijah Newren via GitGitGadgetFrom: Elijah Newren <[email protected]>
While investigating the issues highlighted by the testcase in the previous patch, I also found a shortcoming in the directory rename detection rules. Split testcase 6b into two to explain this issue and update directory-rename-detection.txt to remove one of the previous rules that I know believe to be detrimental. Also, update the wording around testcase 8e; while we are not modifying the results of that testcase, we were previously unsure of the appropriate resolution of that test and the new rule makes the previously chosen resolution for that testcase a bit more solid.
--- .../technical/directory-rename-detection.txt | 5 +- t/t6423-merge-rename-directories.sh | 144 +++++++++++++++--- 2 files changed, 124 insertions(+), 25 deletions(-)
Documentation/technical/directory-rename-detection.txt +1 -4
@@ -70,10 +70,7 @@ additional rules: a) If renames split a directory into two or more others, the directory with the most renames, "wins". - b) Avoid directory-rename-detection for a path, if that path is the - source of a rename on either side of a merge. - - c) Only apply implicit directory renames to directories if the other side + b) Only apply implicit directory renames to directories if the other side of history is the one doing the renaming. Limitations -- support in different commands
t/t6423-merge-rename-directories.sh +123 -21
181 lines not on this page · raw message
Signature · 1 line
gitgitgadget
PATCH 4/4 t6423: more involved rules for renaming directories into each other
In reply to Elijah Newren via GitGitGadgetFrom: Elijah Newren <[email protected]>
Testcases 12b and 12c were both slightly weird; they were marked as having a weird resolution, but with the note that even straightforward simple rules can give weird results when the input is bizarre.
However, during optimization work for merge-ort, I discovered a significant speedup that is possible if we add one more fairly straightforward rule: we don't bother doing directory rename detection if there are no new files added to the directory on the other side of the history to be affected by the directory rename. This seems like an obvious and straightforward rule, but there was one funny corner case where directory rename detection could affect only existing files: the funny corner case where two directories are renamed into each other on opposite sides of history. In other words, it only results in a different output for testcases 12b and 12c.
Since we already thought testcases 12b and 12c were weird anyway, and because the optimization often has a significant effect on common cases (but is entirely prevented if we can't change how 12b and 12c function), let's add the additional rule and tweak how 12b and 12c work. Split both testcases into two (one where we add no new files, and one where the side that doesn't rename a given directory will add files to it), and mark them with the new expectation.
--- .../technical/directory-rename-detection.txt | 3 + t/t6423-merge-rename-directories.sh | 253 ++++++++++++++++-- 2 files changed, 230 insertions(+), 26 deletions(-)
Documentation/technical/directory-rename-detection.txt +3 -0
@@ -73,6 +73,9 @@ additional rules: b) Only apply implicit directory renames to directories if the other side of history is the one doing the renaming. + c) Do not perform directory rename detection for directories which had no + new paths added to them. + Limitations -- support in different commands --------------------------------------------
t/t6423-merge-rename-directories.sh +227 -26
344 lines not on this page · raw message
Signature · 1 line
gitgitgadget
PATCH 1/4 directory-rename-detection.txt: update references to regression tests
In reply to Elijah Newren via GitGitGadgetFrom: Elijah Newren <[email protected]>
The regression tests for directory rename detection were renamed from t6043 to t6423 in commit 919df31955 ("Collect merge-related tests to t64xx", 2020-08-10); update this file to match. Also, add a small clarification to nearby text while we're at it.
--- Documentation/technical/directory-rename-detection.txt | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-)
Documentation/technical/directory-rename-detection.txt +4 -3
@@ -18,7 +18,8 @@ It is perhaps easiest to start with an example: More interesting possibilities exist, though, such as: * one side of history renames x -> z, and the other renames some file to - x/e, causing the need for the merge to do a transitive rename. + x/e, causing the need for the merge to do a transitive rename so that + the rename ends up at z/e. * one side of history renames x -> z, but also renames all files within x. For example, x/a -> z/alpha, x/b -> z/bravo, etc.
@@ -35,7 +36,7 @@ More interesting possibilities exist, though, such as: directory itself contained inner directories that were renamed to yet other locations). - * combinations of the above; see t/t6043-merge-rename-directories.sh for + * combinations of the above; see t/t6423-merge-rename-directories.sh for various interesting cases. Limitations -- applicability of directory renames
@@ -62,7 +63,7 @@ directory rename detection applies: Limitations -- detailed rules and testcases ------------------------------------------- -t/t6043-merge-rename-directories.sh contains extensive tests and commentary +t/t6423-merge-rename-directories.sh contains extensive tests and commentary which generate and explore the rules listed above. It also lists a few additional rules:
Signature · 1 line
gitgitgadget
cover Directory rename detection testcases and rules
While testing merge-ort on some real world repositories a little while back, I found some issues with directory rename detection...some of which were issues in the current merge-recursive as well. Also, I found that there was a nice optimization I could use if a new obvious-looking rule was added, though it has one slight side effect to one corner case. Fixing the bugs and implementing the new rules is a bit more involved, so for now this series just updates the rule descriptions and adds or modifies tests to document the various cases.
Elijah Newren (4):
directory-rename-detection.txt: update references to regression tests
t6423: more involved directory rename test
t6423: update directory rename detection tests with new rule
t6423: more involved rules for renaming directories into each other
.../technical/directory-rename-detection.txt | 15 +- t/t6423-merge-rename-directories.sh | 592 ++++++++++++++++-- 2 files changed, 553 insertions(+), 54 deletions(-)
base-commit: d4a392452e292ff924e79ec8458611c0f679d6d4
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-879%2Fnewren%2Fdrd-testcases-and-rules-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-879/newren/drd-testcases-and-rules-v1
Pull-Request: https://github.com/git/git/pull/879
Signature · 1 line
gitgitgadget
PATCH 2/4 t6423: more involved directory rename test
From: Elijah Newren <[email protected]>
Add a new testcase modelled on a real world repository example that served multiple purposes:
* it uncovered a bug in the current directory rename detection implementation.
* it is a good test of needing to do directory rename detection for a series of commits instead of just one (and uses rebase instead of just merge like all the other tests in this testfile).
* it is an excellent stress test for some of the optimizations in my new merge-ort engine
I can expand on the final item later when I have submitted more of merge-ort, but the bug is the main immediate concern. It arises as follows:
* dir/subdir/ has several files
* almost all files in dir/subdir/ are renamed to folder/subdir/
* one of the files in dir/subdir/ is renamed to folder/subdir/newsubdir/
* If the other side of history (that doesn't do the renames) adds a new file to dir/subdir/, where should it be placed after the merge?
The most obvious two choices are: (1) leave the new file in dir/subdir/, don't make it follow the rename, and (2) move the new file to folder/subdir/, following the rename of most the files. However, there's a possible third choice here: (3) move the new file to folder/subdir/newsubdir/. The choice reinforce the fact that merge.directoryRenames=conflict is a good default, but when the merge machinery needs to stick it somewhere and notify the user of the possibility that they might want to place it elsewhere. Surprisingly, the current code would always choose (3), while the real world repository was clearly expecting (2) -- move the file along with where the herd of files was going, not with the special exception.
The problem here is that for the majority of the file renames,
dir/subdir/ -> folder/subdir/
is actually represented as
dir/ -> folder/
This directory rename would have a big weight associated with it since most the files followed that rename. However, we always consult the most immediate directory first, and there is only one rename rule for it:
dir/subdir/ -> folder/subdir/newsubdir/
Since this rule is the only one for mapping from dir/subdir/, it automatically wins and that directory rename was followed instead of the desired dir/subdir/ -> folder/subdir/.
Unfortunately, the fix is a bit involved so for now just add the testcase documenting the issue.
--- t/t6423-merge-rename-directories.sh | 195 ++++++++++++++++++++++++++++ 1 file changed, 195 insertions(+)
t/t6423-merge-rename-directories.sh +195 -0
@@ -4227,6 +4227,201 @@ test_expect_success '12e: Rename/merge subdir into the root, variant 2' ' ) ' +# Testcase 12f, Rebase of patches with big directory rename +# Commit O: +# dir/subdir/{a,b,c,d,e_O,Makefile_TOP_O} +# dir/subdir/tweaked/{f,g,h,Makefile_SUB_O} +# dir/unchanged/<LOTS OF FILES> +# Commit A: +# (Remove f & g, move e into newsubdir, rename dir/->folder/, modify files) +# folder/subdir/{a,b,c,d,Makefile_TOP_A} +# folder/subdir/newsubdir/e_A +# folder/subdir/tweaked/{h,Makefile_SUB_A} +# folder/unchanged/<LOTS OF FILES> +# Commit B1: +# (add newfile.{c,py}, modify underscored files) +# dir/{a,b,c,d,e_B1,Makefile_TOP_B1,newfile.c} +# dir/tweaked/{f,g,h,Makefile_SUB_B1,newfile.py} +# dir/unchanged/<LOTS OF FILES> +# Commit B2: +# (Modify e further, add newfile.rs) +# dir/{a,b,c,d,e_B2,Makefile_TOP_B1,newfile.c,newfile.rs} +# dir/tweaked/{f,g,h,Makefile_SUB_B1,newfile.py} +# dir/unchanged/<LOTS OF FILES> +# Expected: +# B1-picked: +# folder/subdir/{a,b,c,d,Makefile_TOP_Merge1,newfile.c} +# folder/subdir/newsubdir/e_Merge1 +# folder/subdir/tweaked/{h,Makefile_SUB_Merge1,newfile.py} +# folder/unchanged/<LOTS OF FILES> +# B2-picked: +# folder/subdir/{a,b,c,d,Makefile_TOP_Merge1,newfile.c,newfile.rs} +# folder/subdir/newsubdir/e_Merge2 +# folder/subdir/tweaked/{h,Makefile_SUB_Merge1,newfile.py} +# folder/unchanged/<LOTS OF FILES> +# +# Notes: This testcase happens to exercise lots of the +# optimization-specific codepaths in merge-ort, and also +# demonstrated a failing of the directory rename detection algorithm +# in merge-recursive; newfile.c should not get pushed into +# folder/subdir/newsubdir/, yet merge-recursive put it there because +# the rename of dir/subdir/{a,b,c,d} -> folder/subdir/{a,b,c,d} +# looks like +# dir/ -> folder/, +# whereas the rename of dir/subdir/e -> folder/subdir/newsubdir/e +# looks like +# dir/subdir/ -> folder/subdir/newsubdir/ +# and if we note that newfile.c is found in dir/subdir/, we might +# overlook the dir/ -> folder/ rule that has more weight. + +test_setup_12f () { + test_create_repo 12f && + ( + cd 12f && + + mkdir -p dir/unchanged && + mkdir -p dir/subdir/tweaked && + echo a >dir/subdir/a && + echo b >dir/subdir/b && + echo c >dir/subdir/c && + echo d >dir/subdir/d && + test_seq 1 10 >dir/subdir/e && + test_seq 10 20 >dir/subdir/Makefile && + echo f >dir/subdir/tweaked/f && + echo g >dir/subdir/tweaked/g && + echo h >dir/subdir/tweaked/h && + test_seq 20 30 >dir/subdir/tweaked/Makefile && + for i in `test_seq 1 88`; do + echo content $i >dir/unchanged/file_$i + done && + git add . && + git commit -m "O" && + + git branch O && + git branch A && + git branch B && + + git switch A && + git rm dir/subdir/tweaked/f dir/subdir/tweaked/g && + test_seq 2 10 >dir/subdir/e && + test_seq 11 20 >dir/subdir/Makefile && + test_seq 21 30 >dir/subdir/tweaked/Makefile && + mkdir dir/subdir/newsubdir && + git mv dir/subdir/e dir/subdir/newsubdir/ && + git mv dir folder && + git add . && + git commit -m "A" && + + git switch B && + mkdir dir/subdir/newsubdir/ && + echo c code >dir/subdir/newfile.c && + echo python code >dir/subdir/newsubdir/newfile.py && + test_seq 1 11 >dir/subdir/e && + test_seq 10 21 >dir/subdir/Makefile && + test_seq 20 31 >dir/subdir/tweaked/Makefile && + git add . && + git commit -m "B1" && + + echo rust code >dir/subdir/newfile.rs && + test_seq 1 12 >dir/subdir/e && + git add . && + git commit -m "B2" + ) +} + +test_expect_failure '12f: Trivial directory resolve, caching, all kinds of fun' ' + test_setup_12f && + ( + cd 12f && + + git checkout A^0 && + git branch Bmod B && + + git -c merge.directoryRenames=true rebase A Bmod && + + echo Checking the pick of B1... && + + test_must_fail git rev-parse Bmod~1:dir && + + git ls-tree -r Bmod~1 >out && + test_line_count = 98 out && + + git diff --name-status A Bmod~1 >actual && + q_to_tab >expect <<-\EOF && + MQfolder/subdir/Makefile + AQfolder/subdir/newfile.c + MQfolder/subdir/newsubdir/e + AQfolder/subdir/newsubdir/newfile.py + MQfolder/subdir/tweaked/Makefile + EOF + test_cmp expect actual && + + # Three-way merged files + test_seq 2 11 >e_Merge1 && + test_seq 11 21 >Makefile_TOP && + test_seq 21 31 >Makefile_SUB && + git hash-object >expect \ + e_Merge1 \ + Makefile_TOP \ + Makefile_SUB && + git rev-parse >actual \ + Bmod~1:folder/subdir/newsubdir/e \ + Bmod~1:folder/subdir/Makefile \ + Bmod~1:folder/subdir/tweaked/Makefile && + test_cmp expect actual && + + # New files showed up at the right location with right contents + git rev-parse >expect \ + B~1:dir/subdir/newfile.c \ + B~1:dir/subdir/newsubdir/newfile.py && + git rev-parse >actual \ + Bmod~1:folder/subdir/newfile.c \ + Bmod~1:folder/subdir/newsubdir/newfile.py && + test_cmp expect actual && + + # Removed files + test_path_is_missing folder/subdir/tweaked/f && + test_path_is_missing folder/subdir/tweaked/g && + + # Unchanged files or directories + git rev-parse >actual \ + Bmod~1:folder/subdir/a \ + Bmod~1:folder/subdir/b \ + Bmod~1:folder/subdir/c \ + Bmod~1:folder/subdir/d \ + Bmod~1:folder/unchanged \ + Bmod~1:folder/subdir/tweaked/h && + git rev-parse >expect \ + O:dir/subdir/a \ + O:dir/subdir/b \ + O:dir/subdir/c \ + O:dir/subdir/d \ + O:dir/unchanged \ + O:dir/subdir/tweaked/h && + test_cmp expect actual && + + echo Checking the pick of B2... && + + test_must_fail git rev-parse Bmod:dir && + + git ls-tree -r Bmod >out && + test_line_count = 99 out && + + git diff --name-status Bmod~1 Bmod >actual && + q_to_tab >expect <<-\EOF && + AQfolder/subdir/newfile.rs + MQfolder/subdir/newsubdir/e + EOF + test_cmp expect actual && + + # Three-way merged file + test_seq 2 12 >e_Merge2 && + git hash-object e_Merge2 >expect && + git rev-parse Bmod:folder/subdir/newsubdir/e >actual && + test_cmp expect actual + ) +' + ########################################################################### # SECTION 13: Checking informational and conflict messages #
Signature · 1 line
gitgitgadget
Re: [PATCH 2/4] t6423: more involved directory rename test
Quoted 2 lines · Elijah Newren via GitGitGadget
Add a new testcase modelled on a real world repository example that served multiple purposes:
A couple minor style nits I noticed while quickly running my eye over the patch...
t/t6423-merge-rename-directories.sh test_expect_success '12e: Rename/merge subdir into the root, variant 2' ' · line 4296
Quoted 3 lines
t/t6423-merge-rename-directories.sh +3
-0+ for i in `test_seq 1 88`; do + echo content $i >dir/unchanged/file_$i + done &&
'do' on its own line, and prefer $(...) over ...:
for i in $(test_seq 1 88)
do
echo content $i >dir/unchanged/file_$i
done &&(Not necessarily worth a re-roll, though.)