{"thread":{"id":"25288","subject":"RFC: How to handle merge-recursive corner cases?","startedAt":"2010-09-29T19:16:49Z","lastAt":"2010-09-29T19:51:26Z","messageCount":2,"participants":["Elijah Newren","Jonathan Nieder"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"152077","messageId":"AANLkTimwUQafGDrjxWrfU9uY1uKoFLJhxYs=vssOPqdf@mail.gmail.com","threadId":"25288","inReplyTo":null,"subject":"RFC: How to handle merge-recursive corner cases?","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2010-09-29T19:16:49Z","receivedAt":"2010-09-29T19:16:49Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Hi,\n\nSorry for the lengthy email, but I'm still working on my patch series\nauditing merge-recursive corner cases, and I've run into criss-cross\nmerges that I don't know how to solve.  In some cases, even the\n'right' answer (in terms of what unmerged entries the index should\ncontain when there are conflicts) isn't entirely clear to me, much\nless how to implement it.  I'm hoping someone else has some bright\nideas.\n\nThe basic setup is the following:\n#      B   D\n#      o---o\n#     / \\ / \\\n#  A o   X   ? F\n#     \\ / \\ /\n#      o---o\n#      C   E\nIn other words, there\n\nLet's start with a simple though very contrived case that will\nillustrate issues later, namely a repository with exactly one file\nnamed 'file', with the following contents at different points in\nhistory:\n\nCommit A: file has contents 'A\\n'\nCommit B: file has contents 'B\\n'\nCommit C: file has contents 'C\\n'\nCommit D: file has contents 'D\\n'\nCommit E: file has the following 5 lines in it:\n<<<<<<< Temporary merge branch 1\nC\n=======\nB\n>>>>>>> Temporary merge branch 2\n\nNow, if we try to merge D & E, clearly there should be a conflict.\nBut git merges cleanly, giving file the contents 'D\\n'.  The reason\nfor this is that git notices there are two merge bases, B & C, tries\nto merge them in-core, notices the conflict, stores the 3-way merged\ncontents as the version of 'file' in the new virtual ancestor, and\nthen does a three-way merge between that virtual ancestor and D & E.\nSince the contents of 'file' match between the virtual ancestor and E,\nthe contents of file from D are selected as the merge resolution.\nIt's wrong, but the only way to fix it is to somehow have an entry in\nthe virtual ancestor tree where the conflict region(s) of file are\nguaranteed to not match the corresponding content locations of file\nfor either D or E.  (Perhaps by adding random content on the line\nafter the ='s?)\n\nGiven the extremely contrived nature of this example, perhaps we don't\ncare.  But the basic problem that we need some kind of entry in the\nvirtual ancestor that makes sense for a conflict case can come up in\nother less-contrived scenarios.  For example, with directory/file\nconflicts...\n\nLet's look at a slightly more complicated example, a repository with\nup to three files: 'junk', 'a' and 'a/file':\n\nCommit A: Only 'junk' exists\nCommit B: Adds file 'a'\nCommit C: Adds file 'a/file'\nCommit D: Merges B & C, keeping 'a' and deleting 'a/file'\nCommit E: Merges B & C, deleting 'a' but keeping 'a/file'\n\nNow, merging D & E should result in a (directory/file) conflict, with\nboth 'a' and 'a/file' left in the index (at stages 2 and 3 -- what, if\nanything, exists at stage 1 is unclear to me) and both 'a/file' and\n'a~<branch>' existing in the working copy.  But how/if that happens,\ndepends on the virtual ancestor created when merging B & C in-core.\nPossibilities:\n\nPossibility 1: Virtual ancestor somehow contains both 'a' and 'a/file'\n(currently impossible in git, since this virtual ancestor is written\nas a tree and there's code to prevent writing trees with D/F\nconflicts).  This would mean that 'a' is unchanged between the virtual\nancestor and D and thus should be deleted as in E.  Also, 'a/file' is\nunchanged between the virtual ancestor and E and thus should be\ndeleted as in D.  So we get a clean merge without either 'a' or\n'a/file' present.  Bad.\n\nPossibility 2: Virtual ancestor contains 'a' but not 'a/file'.  This\nmeans the virtual ancestor matches commit D exactly, so git can\ncleanly merge by just selecting the contents of E.  Bad.\n\nPossibility 3: Virtual ancestor contains 'a/file' but not 'a'.  Like\npossibility 2, in reverse: this time the merge is clean having the\ncontents of D.  Bad.\n\nPossibility 4: Virtual ancestor contains neither 'a' nor 'a/file'.\nThis case will correctly detect an (add/add) conflict of the\ndirectory/file variety.  Stage 1 will be empty, but stages 2 and 3\nwill have the appropriate contents.\n\n\nSo possibility 4 sounds great, right?  Let's say we use that\nalgorithm, but now we have a different situation:\nCommits A, B, C, & D: all as above\nCommit E2: Merges B & C, keeping a slightly modified version of 'a'\nand deleting 'a/file'.\n\nMerging D & E2 should be clean, with 'a/file' being removed (since\nboth D and E2 removed it) and the slightly modified version of 'a'\nfrom E2 appearing in the result (since 'a' is unmodified in D).\nHowever, having the virtual ancestor contain neither 'a' nor 'a/file'\nwill cause an add/add conflict when merging D & E2.  Bad.\n\n\nThe only way out of this that I see (and I'm hoping I'm just missing\nsomething), is a modification of possibility 1: make the virtual\nancestor contain both 'a' and 'a/file', but with both files modified\nsomehow to ensure they don't match the contents of D, E, or E2 (maybe\nby appending some random data? something extremely unlikely to match\nthe contents of the file in any of D, E, or E2 such as a timestamp?).\nThat would result in merging D & E giving the appropriate conflict\n(detected as a modify/delete), and merging D & E2 to go cleanly so\nlong as the modification of 'a' in E2 didn't appear near the random\nmodification of 'a' in the virtual ancestor.\n\n\nUgh.  Seems like a mess.  Anyone have any bright ideas?\n\nElijah\n"},{"id":"152080","messageId":"20100929195125.GA28181@capella.cs.uchicago.edu","threadId":"25288","inReplyTo":"AANLkTimwUQafGDrjxWrfU9uY1uKoFLJhxYs=vssOPqdf@mail.gmail.com","subject":"Re: RFC: How to handle merge-recursive corner cases?","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2010-09-29T19:51:26Z","receivedAt":"2010-09-29T19:51:26Z","isPatch":false,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Hi Elijah,\n\nElijah Newren wrote:\n\n> #      B   D\n> #      o---o\n> #     / \\ / \\\n> #  A o   X   ? F\n> #     \\ / \\ /\n> #      o---o\n> #      C   E\n> In other words, there\n> \n> Let's start with a simple though very contrived case that will\n> illustrate issues later, namely a repository with exactly one file\n> named 'file', with the following contents at different points in\n> history:\n> \n> Commit A: file has contents 'A\\n'\n> Commit B: file has contents 'B\\n'\n> Commit C: file has contents 'C\\n'\n> Commit D: file has contents 'D\\n'\n> Commit E: file has the following 5 lines in it:\n> <<<<<<< Temporary merge branch 1\n> C\n> =======\n> B\n> >>>>>>> Temporary merge branch 2\n> \n> Now, if we try to merge D & E, clearly there should be a conflict.\n> But git merges cleanly, giving file the contents 'D\\n'.\n\nFunny.  A different problem is that with a less unusual history (i.e.\nno conflict hunks committed) with \"[merge] conflictstyle=diff3\", if\nthere are conflicts in an early stage of recursive merge, we get\nnested conflict hunks, leaving rerere and humans confused.\n\nI have wondered: why doesn't merge-recursive implicitly use the union\nmerge driver for its in-core merge of ancestors?  The resulting\ndiff3-style conflict hunks from the final 3-way merge would be more\nreadable, but now you've provided an answer: coincidences of matching\ncontent like you describe would become more likely.\n\n[...]\n> It's wrong, but the only way to fix it is to somehow have an entry in\n> the virtual ancestor tree where the conflict region(s) of file are\n> guaranteed to not match the corresponding content locations of file\n> for either D or E.  (Perhaps by adding random content on the line\n> after the ='s?)\n\nRandom content does not provides a guarantee.\n\nMaybe merge_recursive()/merge_trees() could steal a flag bit from\nstruct object for \"conflicted\"?  No, that would give only one bit\nfor the entire tree, and we need one bit per path.\n\nHow about using index entries for this?\n\n>From the signature of git_merge_trees(1, ...) it is not obvious\nto me where it reports conflicts.  From the start to\nwrite_tree_from_memory() I would guess it does not at all.\n\n[...]\n> Possibility 1: Virtual ancestor somehow contains both 'a' and 'a/file'\n> (currently impossible in git, since this virtual ancestor is written\n> as a tree\n[...]\n> The only way out of this that I see (and I'm hoping I'm just missing\n> something), is a modification of possibility 1: make the virtual\n> ancestor contain both 'a' and 'a/file'\n\nHmm, D/F is a little harder than the content conflict case, I guess.\n;-)  But I think in general, the thing to do is to keep something\nother than a tree.\n\nThanks for the food for thought.\nJonathan\n"}]}