{"thread":{"id":"27651","subject":"jk/maint-merge-rename-create [Was: Re: What's cooking in git.git (Jun 2011, #02; Sat, 11)]","startedAt":"2011-06-18T21:49:52Z","lastAt":"2011-06-20T16:08:57Z","messageCount":2,"participants":["Elijah Newren","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"170220","messageId":"BANLkTimkm4SU8nML_6Q7Q34faBziJ=gheA@mail.gmail.com","threadId":"27651","inReplyTo":null,"subject":"jk/maint-merge-rename-create [Was: Re: What's cooking in git.git (Jun 2011, #02; Sat, 11)]","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2011-06-18T21:49:52Z","receivedAt":"2011-06-18T21:49:52Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Hi,\n\nOn Thu, Jun 16, 2011 at 3:05 PM, Jeff King <peff@peff.net> wrote:\n> Thanks. The sticking point in my series that there is a weird regression\n> it introduces, and I haven't quite figured out the cause.\n>\n> I'm cc'ing Jay Soffian, who found it. You can reproduce with this recipe\n> (sorry, the chromium repo is huge, but I don't have a smaller test case\n> yet):\n>\n>  git clone http://git.chromium.org/git/chromium.git &&\n>  cd chromium &&\n>  git config merge.renameLimit 0 &&\n>  git checkout 0f6d00c &&\n>  git cherry-pick d7081a74\n...\n> If you have any input, I'd appreciate it.\n\nThe length of my email may make you change your mind about that.  :-)\n\nTurning on break detection looks like it opens a huge can of worms;\nincluding one issue that I don't understand, namely why break\ndetection doesn't work when I expect it to.  Let me start with that:\n\n--- Why doesn't break detection work as I expect? ---\n$ git init -q\n$ printf \"1\\n2\\n3\\n4\\n5\\n6\\n7\\n8\\n9\\n10\\n\" >a\n$ printf \"a\\nb\\nc\\nd\\ne\\nf\\ng\\nh\\ni\\nj\\n\" >b\n$ git add a b\n$ git commit -q -mA\n\n$ git mv a a2\n$ git mv b b2\n$ git diff --name-status -B -M HEAD\nR100    a       a2\nR100    b       b2\n$ git mv a2 b\n$ git mv b2 a\n$ git diff --name-status -B -M HEAD\nM       a\nM       b\n\nI would have expected the output from the last command above to be\nR100    a       b\nR100    b       a\nWhy are these renames not detected?  Is there a reason, or is this a bug?\n\n\n--- Issues with merge-recursive and break detection ---\nThe chromium repository testcase Jay provided helps uncover a few\nextra issues in merge-recursive when turning on break detection, but I\nbelieve there are a number of others that need consideration as well.\nSorry for the lengthy email, but there are lots of little issues.\n\nWhenever the read_tree logic can't handle a merge trivially at a given\npath (as per Documentation/technical/trivial-merge.txt), it will load\nthe three relevant stages for that path into the index.  For\nsimplicity, let's ignore mode changes, and just consider sha1sums.\nLet me name things so we can talk about the various cases:\n  o_sha - sha1sum of given path in the merge-base\n  a_sha - sha1sum of given path in HEAD\n  b_sha - sha1sum of given path on other branch involved in merge\n\nIn the case of a rename, there are two files involved, and thus (up\nto) 6 relevant stages that merge-recursive.c needs to consider.  Let\nme use s_ as a prefix for the source path of a rename and d_ as a\nprefix for the destination path of a rename.  That means for renames\nthe sha1sums we need to consider are:\n  old_name -> new_name\n  --------    --------\n  s_o_sha     d_o_sha\n  s_a_sha     d_a_sha\n  s_b_sha     d_b_sha\n\nSimple renames will have 3 of those 6 sha1sums be the null sha1; the 3\nnon-null sha1s will either be {s_o_sha, s_a_sha, d_b_sha} or {s_o_sha,\nd_a_sha, s_b_sha}.  Git handles those just fine.\n\nA slight complication is having both of d_[ab]_sha be non-null (while\nd_o_sha remains null).  This case is either a rename/rename(2to1)\nconflict or a rename/add conflict.  Either way, git has long had code\nto handle both of those cases.\n\nA slightly more complicated case is having all three of the s_*_sha be\nnon-null as well as exactly one of d_[ab]_sha.  Such cases would have\npreviously resulted in git ignoring old_name as a rename candidate,\nsince we were not previously using break detection.  Your series is\naimed at handling these cases, so I won't cover them in detail.  I\nthink you do so correctly for almost all such cases, though I'm\nsuspicious that there might still be issues with some corner cases\n(e.g. with D/F conflicts or rename/rename(1to2) cases).\n\nThe problems the chromium repository is triggering is when all d_*_sha\nare non-null.  That was impossible before your patch series, since\nhaving all three be non-null meant it was ignored as a rename\ncandidate.  It also meant no code was ever needed for that case, so\nnone had been written.  There are a number of possibilites, I'll try\nto highlight using example values, using d and e (and later f-i) as\nvariables standing for sha1sums:\n\nBasic d_*_sha all non-null case:\n  old_name    -> new_name\n  -----------    -----------\n  s_o_sha = d    d_o_sha = e\n  s_a_sha = d    d_a_sha = e\n  s_b_sha = 0    d_b_sha = d\nThis suggests that the content originally stored at new_name was\nunmodified on one side of history and deleted (or renamed to something\nelse) on the other.  The content originally stored at old_name has\nmoved to new_name, so the correct resolution is to delete old_name and\nwrite the contents of d to new_name.  git has no code for this; it\nassumes d_o_sha is null and thus sees this case as a rename/add\nconflict.\n\nSlightly more complex; 3-way merge:\n  s_o_sha = d1   d_o_sha = e\n  s_a_sha = d2   d_a_sha = e\n  s_b_sha = 0    d_b_sha = d3\nThis is like the last case, but now we need to do a three way merge of\nd1,d2,d3 and store the results at new_name.  It appears that all of\nthe conflicts you saw with Jay's chromium testcase would be fixed if\nthere were code for this case.\n\nSlightly more complex; 3-way merge + possible conflict:\n  s_o_sha = d1   d_o_sha = e1\n  s_a_sha = d2   d_a_sha = e2\n  s_b_sha = 0    d_b_sha = d3\nIn addition to the three-way content merge of d1,d2,d3 that is\nsupposed to be stored at new_path, there is also a potential\nmodify/delete problem (e1, e2, -nothing-) that ALSO is supposed to be\nstored at new_name.  (What do we call that -- rename+modify/delete\nconflict?)  However, there is also a chance that it's not a\nmodify/delete, but rather another rename using new_path as the source\nof the rename -- in which case there would be no conflict at new_path\nafter all (unless the 3-way merge of d1,d2,d3 had content conflicts).\n\nSlightly more complex: 3-way merge + add conflict despite base presence:\n  s_o_sha = d1   d_o_sha = e\n  s_a_sha = d2   d_a_sha = f\n  s_b_sha = 0    d_b_sha = d3\nHere the original new_name was either rewritten, deleted, or renamed\non both sides of history.  e, f, and d3 all have nothing to do with\neach other, which means that in addition to the three-way content\nmerge of d1,d2,d3 that is supposed to be stored at new_path, there is\nalso an added file that is unrelated.  In other words, we either have\na rename/add conflict or a rename/rename(2to1) conflict.\n\nJust for fun:\n  file_g         file_h         file_i\n  ------------   ------------   ------------\n  g_o_sha = g1   h_o_sha = h1   i_o_sha = i1\n  g_a_sha = g2   h_a_sha = h2   i_a_sha = i2\n  g_b_sha = i3   h_b_sha = g3   i_b_sha = h3\ncyclic rename; the side of history being merged into head also had fun\nwith renames: (file_g, file_h, file_i) -> (file_h, file_i, file_g).\nAlso, each of file_g, file_h, and file_i were modified on both sides.\nCorrect resolution: 3-way merge of g1,g2,g3 stored in file_h, 3-way\nmerge of h1,h2,h3 stored in file_i, and 3-way merge of i1,i2,i3 stored\nin file_g.\n\nMore complexity with more renames:\nThe rename/rename (either 1to2 or 2to1) conflicts will involve 9\nsha1sums rather than six.  Also, as shown in the previous case, either\nthe source or the destination path of a rename could be involved (as\neither source or destination) of yet another rename.\n\nDon't forget the pesky D/F possibilities:\nThe possibility of D/F conflicts complicates things slightly -- for\nexample, both the source and destination paths of a rename could be\ninvolved in a D/F conflict, and thus we may need to record the\nconflicts at an alternate location.  Whether we need to do so or not\ncannot be determined in process_renames(); therefore, the extra\nhandling we add for both source and destination entries (at least the\nfinal index/working-directory changes) should be deferred until later.\n There may also be interesting ramifications for criss-cross merges\ndue to these break rewrite cases as well.\n\nStuff I'm still ignoring:\nAs Junio noted previously, break detection could be used to note that\na modify/delete conflict is really a delete/delete/add and thus there\nshould be no conflict.  Also, a rename/modify that has odd content\nconflicts might be easier to handle if it was determined that it was\nreally a rename/delete/add-source case.  The only thing I'm\nconsidering above is using break-detection as a way to get better\nrename detection.\n\n\nElijah\n"},{"id":"170307","messageId":"7voc1scwo6.fsf@alter.siamese.dyndns.org","threadId":"27651","inReplyTo":"BANLkTimkm4SU8nML_6Q7Q34faBziJ=gheA@mail.gmail.com","subject":"Re: jk/maint-merge-rename-create","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-06-20T16:08:57Z","receivedAt":"2011-06-20T16:08:57Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Elijah Newren <newren@gmail.com> writes:\n\n> --- Why doesn't break detection work as I expect? ---\n> $ git init -q\n> $ printf \"1\\n2\\n3\\n4\\n5\\n6\\n7\\n8\\n9\\n10\\n\" >a\n> $ printf \"a\\nb\\nc\\nd\\ne\\nf\\ng\\nh\\ni\\nj\\n\" >b\n\nUse something non-trivial.  Taking a real-life file COPYING from our\nsource set, I can do this:\n\n\t$ git init\n\t$ cp $git_src/COPYING a\n        $ tr 'A-Za-z' 'N-ZA-Mn-za-m' <a >b\n\t$ git add a b\n        $ git commit -m ab\n        $ git mv a c; git mv b a; git mv c a\n        $ git diff --stat -M -B HEAD\n         b => a | 0\n         a => c | 0\n         2 files changed, 0 insertions(+), 0 deletions(-)\n"}]}