{"thread":{"id":"55120","subject":"Directory rename detection breaks if repo has a lot of similar/identical files","startedAt":"2021-02-08T17:33:32Z","lastAt":"2021-02-08T23:37:08Z","messageCount":2,"participants":["Yannis Zarkadas","Elijah Newren"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"416420","messageId":"4ceea1ec-59fe-af8e-b91d-aced4e6a1b0f@arrikto.com","threadId":"55120","inReplyTo":null,"subject":"Directory rename detection breaks if repo has a lot of similar/identical files","fromName":"Yannis Zarkadas","fromEmail":"yanniszark@arrikto.com","sentAt":"2021-02-08T17:30:22Z","receivedAt":"2021-02-08T17:33:32Z","isPatch":false,"sender":{"key":"yanniszark@arrikto.com","avatar":null},"body":"Hi everyone! I believe I have found a use-case that breaks git's directory\nrename detection algorithm. In short, when a repo has a lot of identical \nfiles,\ndirectory rename detection breaks. I believe this happens because git feeds\nmisleading renames to the directory rename detection algorithm.\n\nFor example, suppose a changeset (COMMIT_A, COMMIT_B). If `x/a` and `y/b` in\nCOMMIT_A are the same as `new/x/a` and `new/y/b` in COMMIT_B, then git may\ndecide the renames are `x/a -> new/y/b` and `y/b -> new/x/a` instead of\n`x/a -> new/x/a` and `y/b -> new/y/b`. Of course, this confuses the \ndirectory\nrename detection algorithm.\n\nTo make a long story short (I am including all the individual steps to\ninvestigate this below), it seems the following enhancement would work \nto solve\nthis particular problem:\n\nIf file `a/base/base.txt` in COMMIT_A is the same as \n`new/a/base/base.txt` AND\n`new/z/base/base.txt` in COMMIT_B, then prefer the rename\n`a/base/base.txt->new/a/base/base.txt` over the rename\n`a/base/base.txt->new/z/base/base.txt`. I have included a more generic \nalgorithm\nbelow.\n\n\nProblem\n=======\n\nThe original repo was very large, so I tried to find a simpler example that\ncaused git to detect directory renames incorrectly. I managed to create such\nan environment with the following script:\nhttps://gist.github.com/yanniszark/4165bd8f92d9838e143495e5a8df2ce0\n\nThe script creates a repo (/tmp/demo) with 3 branches:\n- *upstream*: Contains a lot of folders, with some files being identical \nacross\n   folders.\n- *upstream-restructured*: Same as upstream, but with all folders moved \nunder\n   `new/`. For example, `a/`->`new/a`\n- *downstream*: Based on upstream, adds some extra files under every \nfolder of\n   upstream.\n\nThen, it tries to rebase downstream ontop of upstream-restructured. Git \ndetects\nthe WRONG directory rename `z/->new/a/` and fails with a wrong conflict.\n\n$ git -c merge.directoryRenames=true rebase -v -m --onto \nupstream-restructured upstream\nPath updated: z/overlays/develop/overlay.txt added in 9bf94f0 (Add \noverlay for z) inside a directory that was renamed in HEAD; moving it to \nnew/a/overlays/develop/overlay.txt.\nCONFLICT (rename/rename): Rename \na/overlays/develop/overlay.txt->new/a/overlays/develop/overlay.txt in \nHEAD. Rename \nz/overlays/develop/overlay.txt->new/a/overlays/develop/overlay.txt in \n9bf94f0 (Add overlay for z)\n\n\nWe are going to work with this example for the rest of this mail.\n\n\nAnalysis\n========\n\nAfter learning a bit about how git works internally, I found out:\n- Rebasing with the merge backend (`-m`) uses cherry-pick underneath.\n- Cherry-pick frames the problem as a merge, with the merge-base being the\n   parent of the REMOTE commit.\n- The merge algorithm accepts 3 inputs (BASE, LOCAL, REMOTE), computes the\n   changesets of (BASE, LOCAL) and (BASE, REMOTE), and finally combines \nthem.\n\n\nWith this background in mind, I run the demo script and got this message:\n\nPath updated: z/overlays/develop/overlay.txt added in 9bf94f0 (Add \noverlay for z) inside a directory that was renamed in HEAD; moving it to \nnew/a/overlays/develop/overlay.txt.\nCONFLICT (rename/rename): Rename \na/overlays/develop/overlay.txt->new/a/overlays/develop/overlay.txt in \nHEAD. Rename \nz/overlays/develop/overlay.txt->new/a/overlays/develop/overlay.txt in \n9bf94f0 (Add overlay for z)\n\nApplying our knowledge of rebase, cherry-pick and merge from above, let's\ncalculate the BASE, LOCAL and REMOTE commits.\n\nLOCAL=HEAD\nREMOTE=9bf94f0  # same as the error message\nBASE=REMOTE~    # based on how cherry-pick works\n\nAt this point, we can peek at what changesets git's merge algorithm is \nseeing:\n\ngit diff --find-renames --stat $BASE $LOCAL\ngit diff --find-renames --stat $BASE $REMOTE\n\nThe first command is the interesting one and returns suspicious entries \nlike the\nfollowing:\n\n{z => new/a}/base/base.txt                   | 0\n{a => new/a}/overlays/develop/overlay.txt    | 0\n{a => new/a}/overlays/upstream/file_1.txt    | 0\n{z => new/a}/overlays/upstream/file_3.txt    | 0\n{z => new/a}/overlays/upstream/file_5.txt    | 0\n{a => new/a}/overlays/upstream/file_a.txt    | 0\n{z => new/a}/overlays/upstream/overlay.txt   | 0\n[...]\n{a => new/z}/base/base.txt                   | 0\n{z => new/z}/overlays/upstream/file_1.txt    | 0\n{a => new/z}/overlays/upstream/file_3.txt    | 0\n{a => new/z}/overlays/upstream/file_5.txt    | 0\n{z => new/z}/overlays/upstream/file_z.txt    | 0\n{a => new/z}/overlays/upstream/overlay.txt   | 0\n\n\nHypothesis\n==========\n\nAt this point, I formed a hypothesis:\n- git detects renames between (BASE, LOCAL) as they appear in the `git diff`\n   command above.\n- git feeds those renames in the directory rename detection algorithm, which\n   gets confused about what directory renames actually happened.\n\n\nConfirming the Hypothesis\n=========================\n\nI tried to confirm my hypothesis by diving in the source code. My C is a bit\nrusty, but I managed to find out the function that handles the renames, \ncalled\n`detect_and_process_renames` (inside `merge-recursive.c`). The following \npart\nis particularly interesting:\n\nhead_pairs = get_diffpairs(opt, common, head);\nmerge_pairs = get_diffpairs(opt, common, merge);\n[...]\n     dir_re_head = get_directory_renames(head_pairs);\n     dir_re_merge = get_directory_renames(merge_pairs);\n\nThe first part is computing the changeset for (BASE, LOCAL) and (BASE, \nREMOTE).\nThe second part is feeding the changeset to the get_directory_renames \nfunction\nfor calculating directory renames.\n\nBy inspecting the `head_pairs` variable with my debugger, I confirmed \nthat the\nchangeset is the one I saw with `git diff`. Indeed, git is feeding the\n`get_directory_renames` function confusing renames.\n\n\nProposed Enhancement\n====================\n\nNow that we know what is most likely going on, I can describe what I \nwould like\ngit to do.\n\nIntuition: If file `a/base/base.txt` in BASE is the same as\n`new/a/base/base.txt` AND `new/z/base/base.txt` in LOCAL, then prefer \nthe rename\n`a/base/base.txt->new/a/base/base.txt` over the rename\n`a/base/base.txt->new/z/base/base.txt`.\n\nIn other words, if multiple rename candidates are possible, prefer the \nones that\nlook more like the user move the file/folder from one path to another.\n\nPossible Algorithm:\n\nMore generally, if files `A1`, `A2`, ..., `An` in commit A are the same \nas `B1`,\n`B2`, `Bm` in commit B, then:\n- Calculate a sorted list of scores `S(Ai, Bj), i=1,...,n and \nj=1,...,m`, where\n   `S(Ai, Bj)` is the length of the suffix match of `Ai` and `Bj`.\n- Walk the sorted list and for each element:\n     - If `Ai` and `Bj` is not used in a rename yet, apply the rename.\n     - Stop when you have found `min(n, m)` renames.\n- The remaining `max(n, m) - min(n, m)` files are either deletes (if \nthey are on\n   commit A) or copies (if they are on commit B).\n\n\nConclusion\n==========\n\nI want to attempt to implement something like what I described above, when I\nhave more time to get familiar with diff's internals. In the meantime, I \nwould\nlove to hear the opinion of more seasoned git developers on this issue. \nDo you\nagree with my findings and the direction I proposed? Is there something \nI have\noverlooked? Perhaps someone is already having these problems.\n\n\nThanks in advance,\nYannis Zarkadas\n\n"},{"id":"416460","messageId":"CABPp-BGydzR2NDvG_q7NJyLBTDxQZbvjgwfmeXnmhtPCf+FxRg@mail.gmail.com","threadId":"55120","inReplyTo":"4ceea1ec-59fe-af8e-b91d-aced4e6a1b0f@arrikto.com","subject":"Re: Directory rename detection breaks if repo has a lot of similar/identical files","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-02-08T23:35:45Z","receivedAt":"2021-02-08T23:37:08Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Hello Yannis, and welcome!\n\nOn Mon, Feb 8, 2021 at 9:37 AM Yannis Zarkadas <yanniszark@arrikto.com> wrote:\n>\n> Hi everyone! I believe I have found a use-case that breaks git's directory\n> rename detection algorithm. In short, when a repo has a lot of identical\n> files,\n> directory rename detection breaks. I believe this happens because git feeds\n> misleading renames to the directory rename detection algorithm.\n\nThe directory rename detection logic doesn't seem to have any issues\nhere; the problem is in the data fed to that logic, which is\nessentially random.  Thus, this lies more on the side of rename\ndetection than directory rename detection, even if you paid more\nattention to the issues once they started affecting directory rename\ndetection.  That's worth noting because directory rename detection\ncode is in merge-recursive.c, while normal rename detection code is in\ndiffcore-rename.c.  Just want to make sure we're looking at the right\ncode if you want to dive in.\n\n\nIn diffcore-rename.c, in the function named find_identical_files(),\nties will be broken based on whether basenames match:\n\n    score += basename_same(source, target);\n    if (score > best_score) {\n\nIf you have multiple identical files AND they have matching basenames,\nthen they'll all have the same score.  Since it only records a new\nbest if it is *better* than the previous, it will thus take whichever\none was first.  The ordering of which is first depends on the random\norder that the hashmap decides to iterate over them.\n\nOf course, this is only for identical files.  However, basename_same()\nis used in one other place in the file, in association with inexact\nrenames, but has identical usage where the tie-breaker for files with\nthe same content similarity percentage are broken by whether the have\nthe same basename -- but any other path components are ignored.\n\n...snip a bunch of good analysis...\n\n> git diff --find-renames --stat $BASE $LOCAL\n> git diff --find-renames --stat $BASE $REMOTE\n>\n> The first command is the interesting one and returns suspicious entries\n> like the\n> following:\n>\n> {z => new/a}/base/base.txt                   | 0\n> {a => new/a}/overlays/develop/overlay.txt    | 0\n> {a => new/a}/overlays/upstream/file_1.txt    | 0\n> {z => new/a}/overlays/upstream/file_3.txt    | 0\n> {z => new/a}/overlays/upstream/file_5.txt    | 0\n> {a => new/a}/overlays/upstream/file_a.txt    | 0\n> {z => new/a}/overlays/upstream/overlay.txt   | 0\n> [...]\n> {a => new/z}/base/base.txt                   | 0\n> {z => new/z}/overlays/upstream/file_1.txt    | 0\n> {a => new/z}/overlays/upstream/file_3.txt    | 0\n> {a => new/z}/overlays/upstream/file_5.txt    | 0\n> {z => new/z}/overlays/upstream/file_z.txt    | 0\n> {a => new/z}/overlays/upstream/overlay.txt   | 0\n\nAnd yep, that seems to be what you're seeing.  And if the renames look\nlike this, then trying infer directory renames based on the renames is\ngoing to be a mess.\n\nSo it all boils down to the fact that you have identical files with\nidentical basenames, and renames don't currently know how to\ndifferentiate between such files to get the \"right\" rename.\n\n> Proposed Enhancement\n> ====================\n>\n> Now that we know what is most likely going on, I can describe what I\n> would like\n> git to do.\n>\n> Intuition: If file `a/base/base.txt` in BASE is the same as\n> `new/a/base/base.txt` AND `new/z/base/base.txt` in LOCAL, then prefer\n> the rename\n> `a/base/base.txt->new/a/base/base.txt` over the rename\n> `a/base/base.txt->new/z/base/base.txt`.\n>\n> In other words, if multiple rename candidates are possible, prefer the\n> ones that\n> look more like the user move the file/folder from one path to another.\n\nStated differently, break ties for rename detection based on the\nnumber of matching trailing path components.  For example, if the\nbasename was the only path component that was the same (e.g.\nsrc/base.txt and source/base.txt), then we'd add one to the score.  If\nthe basenames were the same and two of the directories before that\nmatched as well (e.g. src/a/base/base.txt and source/a/base/base.txt)\nthen we'd add three to the score or name_score.  To implement this,\nyou'd only have to change the basename_same() function to: (1) rename\nit (since it's no longer just about the basename), (2) make it keep\ngoing past the first '/' component, and (3) change the 0...1 scoring\nrange to 0...N based on the number of '/' characters you passed while\nwalking backwards (except that reaching the toplevel counts the same\nas hitting a '/' character, e.g. foo.txt and src/foo.txt have 1\nmatching path component rather than 0).\n\n> Possible Algorithm:\n>\n> More generally, if files `A1`, `A2`, ..., `An` in commit A are the same\n> as `B1`,\n> `B2`, `Bm` in commit B, then:\n> - Calculate a sorted list of scores `S(Ai, Bj), i=1,...,n and\n> j=1,...,m`, where\n>    `S(Ai, Bj)` is the length of the suffix match of `Ai` and `Bj`.\n> - Walk the sorted list and for each element:\n>      - If `Ai` and `Bj` is not used in a rename yet, apply the rename.\n>      - Stop when you have found `min(n, m)` renames.\n> - The remaining `max(n, m) - min(n, m)` files are either deletes (if\n> they are on\n>    commit A) or copies (if they are on commit B).\n\nThis would require a bigger code restructure, and I think it's no\ndifferent than my suggested changes to basename_same().\n\n> Conclusion\n> ==========\n>\n> I want to attempt to implement something like what I described above, when I\n> have more time to get familiar with diff's internals. In the meantime, I\n> would\n> love to hear the opinion of more seasoned git developers on this issue.\n> Do you\n> agree with my findings and the direction I proposed? Is there something\n> I have\n> overlooked? Perhaps someone is already having these problems.\n\nYou're the first I know of to have identical files in different\ndirectories with identical basenames, and then attempt to rename them\nand do directory rename detection based on that combination.  But just\nbecause you're the first I know of doesn't imply that you're the only\none or the last one, of course.  I think the basename_same() change\nwould probably fix this up nicely for you.\n\n\nYou'll need  to be aware, though, that I'm making lots of changes to\ndiffcore-rename.c right now, though, so there is a risk of conflicts.\nJust since git-2.30, see these commits:\n\n350410f6b1 (diffcore-rename: remove unnecessary duplicate entry\nchecks, 2020-12-29)\n9db2ac5616 (diffcore-rename: accelerate rename_dst setup, 2020-12-11)\nb970b4ef62 (diffcore-rename: simplify and accelerate\nregister_rename_src(), 2020-12-11)\n81c4bf0296 (diffcore-rename: reduce jumpiness in progress counters, 2020-12-11)\nad8a1be529 (diffcore-rename: simplify limit check, 2020-12-11)\n00b8cccdd8 (diffcore-rename: avoid usage of global in\ntoo_many_rename_candidates(), 2020-12-11)\n26a66a6b1c (diffcore-rename: rename num_create to num_destinations, 2020-12-11)\n\nplus many of the commits found in each of the pull requests up at\nhttps://github.com/gitgitgadget/git/pulls?q=is%3Apr+author%3Anewren+Optimization+batch.\nThat shouldn't stop you, but be aware that you might need to rebase a\nfew times, or let me take over and keep rebasing your patches on top\nof mine (retaining you as author) in order to get all the series of\npatches through.\n\n\nHope that helps,\nElijah\n"}]}