{"thread":{"id":"20021","subject":"Wrong file diff for merge conflict","startedAt":"2009-07-04T07:53:34Z","lastAt":"2009-07-06T14:44:56Z","messageCount":7,"participants":["Stefan Bucur","Linus Torvalds","Jakub Narebski","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"117432","messageId":"loom.20090704T072854-229@post.gmane.org","threadId":"20021","inReplyTo":null,"subject":"Wrong file diff for merge conflict","fromName":"Stefan Bucur","fromEmail":"stefan.bucur@gmail.com","sentAt":"2009-07-04T07:53:34Z","receivedAt":"2009-07-04T07:53:34Z","isPatch":false,"sender":{"key":"stefan.bucur@gmail.com","avatar":"https://gravatar.com/avatar/8c4605309711962e4ef009d2d01730506cbb10a50100d87a9f7de36de15ea2d2?d=mp&s=160"},"body":"Hi!\n\nI would like to point out a very strange behavior of git merge, which led to\ndata loss or data duplication in the conflict file generated during a diff merge.\n\nI had to merge two branches (A and B) which contained more files (e.g.\nhttp://pastebin.ca/1483691 - before splitting branches) which were affected in\nthe following way:\n* The files were formatted (indented) in branch A: http://pastebin.ca/1483684\n* In branch B, their contents were altered in various points, but not\nsignificantly (refactored some statements into macros): http://pastebin.ca/1483683\n\nI checked out branch A, and I ran \"git merge B\", and (obviously) there was a\nconflict with this file. The big surprise was to see that the generated diff\nfile looks like this:\n\nhttp://pastebin.ca/1483228\n\nThe problem is with the last diff in the file, where the left portion is empty,\nand the right portion contains code which already was marked as merged (common),\nright before the start of the diff. Therefore, the mark at line 127 should\nreally have been before line 114.\n\nIs this a bug or I am missing something?\n\nThanks,\nStefan Bucur\n"},{"id":"117463","messageId":"alpine.LFD.2.01.0907051113240.3210@localhost.localdomain","threadId":"20021","inReplyTo":"loom.20090704T072854-229@post.gmane.org","subject":"Re: Wrong file diff for merge conflict","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-07-05T18:43:14Z","receivedAt":"2009-07-05T18:43:14Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 4 Jul 2009, Stefan Bucur wrote:\n> \n> http://pastebin.ca/1483228\n> \n> The problem is with the last diff in the file, where the left portion is empty,\n> and the right portion contains code which already was marked as merged (common),\n> right before the start of the diff. Therefore, the mark at line 127 should\n> really have been before line 114.\n> \n> Is this a bug or I am missing something?\n\nI suspect (but without the origin files/history I can't verify) that what \nhappens is that the \"successfully merged\" code was seen as a fully new \nsnippet of code (probably due to getting re-indented?), and the other part \nof that action on that branch was the removal of the old code.\n\nThat _removal_ is then shown as a conflict against the other branch, which \npresumably didn't re-indent things (of course, it could be exactly the \nother way around too), and so now you end up having the \"conflict\" being \nseen as \"one branch removes this code (empty conflict part), the other one \npresumably changed it some way\".\n\nIs that what you wanted? Obviously not. To you, the conflict makes no \nsense. You're a human, who tries to understand what wen't wrong, and to \nyou, the end result of the conflict resolution makes no sense.\n\nOn the other hand, it probably _does_ make sense from the standpoint of a \nfairly stupid simple three-way merge that is also (on purpose) tuned to \ntry to give minimal merge conflicts (the \"XDL_MERGE_ZEALOUS\" flag) that \nare often easier for humans to then correct because they have limited \ncontext.\n\nAnd the thing is, that zealous merge conflict minimization generally does \nresult in conflicts that are easier to work with, because you end up with \na much smaller conflict - rather than having one huge conflict that in \nyour case would probably have covered pretty much the whole 'realloc()' \nfunction, the zealous merge has tried to really zoom in on just the \ncritical parts, and has turned it into three conflicts that are fairly \nsmall (one is just two trivial lines).\n\nIn this case, I can also guess at why you then end up with a very odd \nconflict: when one side has re-indented the code, the only lines that tend \nto match after the re-indentation are the trivial lines that have just a \nsingle closing brace, or perhaps a \"} else {\" that actually ends up \nmatching the _wrong_ indentation level, but because it existed in both \nindentation levels, the stupid line-based merge logic picked it as a \ncommon feature - even though it very much is exactly the _wrong_ kind of \ncommon feature to pick.\n\nSo is it a bug? Nope. I can pretty much guarantee that it's not a bug. The \nwhole zealous merge thing is very much a feature. The \"take whitespace \ninto account when comparing lines\" is also a feature, even though it \nobviously matches up the wrong lines in re-indentation cases like this. I \nbet you've seen diffs (not just merges) that you think look \"stupid\", and \nthey look stupid exactly for the same reason - diff matches the wrong \nclosing braces across re-indentation.\n\nNow, that said - it may not be a bug, but it's clearly not what you want, \nso how do you fix it?\n\nThere's a couple of things to do:\n\n - Try to make the merging smarter, and not do this mistake.\n\n   I'd love to have that, but quite frankly, I don't think it's \n   reasonable. As mentioned, aggressively minimizing merge conflicts \n   really does do the right thing most of the time, and non-aggressive \n   merges - while obviously \"safer\" - are really irritating.\n\n   So the merge is not hugely smart, and _despite_ it being pretty stupid \n   it's also pretty aggressive. Not generally a good combination, but so \n   far, the alternatives have always been way worse.\n\n - Tune the zealous merge a bit, and in particular try to avoid the cases \n   where this happens (as mentioned, in C code, it's often re-indentation \n   together with trivial lines that match after it).\n\n   This is kind of what the \"patience\" diff algorithm tries to do: use \n   primarily non-trivial sequences as the anchors for similarity, and \n   ignore the trivial ones. We have a \"--patience\" switch to \"git diff\", \n   maybe we could tune the three-way merge somehow similarly.\n\n   (We did already soem time ago add _some_ tuning, in the form of \n   ZEALOUS_ALNUM that only combines non-conflicting lines if they are \n   non-trivial in the sense that they have some alphanumeric characters. \n   But all that happens after the diff algorithm itself has generated the \n   chunks, so the empty '}' lines still do matter for merging. Also, it \n   still considers things like '} else {' to be \"meaningful\" by virtue of \n   having alphanumerics on it.)\n\n - Don't rely so heavily on just the traditional three-way merge result.\n\n   This is what I personally do. The trivial 3-way merge result is \n   wondeful for the truly trivial merges, when it gives trivial results \n   that are easy to fix up. But let's face it, the traditional 3-way merge \n   result just sucks for anything more complicated. When you have an empty \n   side on one of the conflicts, is that because the other side added \n   everything, or is it because oen side removed it? Or is it, like in \n   this case, simply because trivially similar lines got the whole diff \n   confused about which parts didn't change at all?\n\n   The good news is that git does have a few nice merge tools. One is \n   \"git diff\", which actually shows way more than the trivial three-way \n   end result, in that you can diff against either side, and by default it \n   does that fairly complex \"diff against both sides\" thing that is also \n   quite useful once you get used to it.\n\n   Another is \"gitk --merge [filename]\" which is wonderful as a tool to \n   see what both sides actually did, to figure out what the intent of both \n   branches were when the three-way merge result is just noise.\n\nThe right answer is probably some combination of \"all of the above\". In \nthe meantime, right now, only the last one is somethign git itself will \nhelp you with.\n\n\t\t\tLinus\n"},{"id":"117468","messageId":"m3vdm7ue8k.fsf@localhost.localdomain","threadId":"20021","inReplyTo":"alpine.LFD.2.01.0907051113240.3210@localhost.localdomain","subject":"Re: Wrong file diff for merge conflict","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2009-07-05T19:22:22Z","receivedAt":"2009-07-05T19:22:22Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n> On Sat, 4 Jul 2009, Stefan Bucur wrote:\n> > \n> > http://pastebin.ca/1483228\n> > \n> > The problem is with the last diff in the file, where the left portion is empty,\n> > and the right portion contains code which already was marked as merged (common),\n> > right before the start of the diff. Therefore, the mark at line 127 should\n> > really have been before line 114.\n> > \n> > Is this a bug or I am missing something?\n> \n> I suspect (but without the origin files/history I can't verify) that what \n> happens is that the \"successfully merged\" code was seen as a fully new \n> snippet of code (probably due to getting re-indented?), and the other part \n> of that action on that branch was the removal of the old code.\n> \n> That _removal_ is then shown as a conflict against the other branch, which \n> presumably didn't re-indent things (of course, it could be exactly the \n> other way around too), and so now you end up having the \"conflict\" being \n> seen as \"one branch removes this code (empty conflict part), the other one \n> presumably changed it some way\".\n> \n> Is that what you wanted? Obviously not. To you, the conflict makes no \n> sense. You're a human, who tries to understand what wen't wrong, and to \n> you, the end result of the conflict resolution makes no sense.\n\n[...]\n>  - Don't rely so heavily on just the traditional three-way merge result.\n> \n>    This is what I personally do. The trivial 3-way merge result is \n>    wondeful for the truly trivial merges, when it gives trivial results \n>    that are easy to fix up. But let's face it, the traditional 3-way merge \n>    result just sucks for anything more complicated. When you have an empty \n>    side on one of the conflicts, is that because the other side added \n>    everything, or is it because oen side removed it? Or is it, like in \n>    this case, simply because trivially similar lines got the whole diff \n>    confused about which parts didn't change at all?\n> \n>    The good news is that git does have a few nice merge tools. One is \n>    \"git diff\", which actually shows way more than the trivial three-way \n>    end result, in that you can diff against either side, and by default it \n>    does that fairly complex \"diff against both sides\" thing that is also \n>    quite useful once you get used to it.\n> \n>    Another is \"gitk --merge [filename]\" which is wonderful as a tool to \n>    see what both sides actually did, to figure out what the intent of both \n>    branches were when the three-way merge result is just noise.\n\nThere is also \"git mergetool\" which runs graphical merge tool of your\nchoice.  It can be easier to work with GUI here.\n\n\nAnd git also supports diff3 conflict merge markers, which shows our\nand their side, and also the ancestor side; in your case it would make\neasy to distinguish between 'one side added' and 'other side removed'.\nYou can get it using \n\n  $ git checkout --conflict=diff3 <file>\n \n(where <file> can be '.').  You would need modern git (post 1.6.2\nI think) for that.\n\n> The right answer is probably some combination of \"all of the above\". In \n> the meantime, right now, only the last one is something git itself will \n> help you with.\n\n-- \nJakub Narebski\nPoland\nShadeHawk on #git\n"},{"id":"117469","messageId":"7vws6nhr1s.fsf@alter.siamese.dyndns.org","threadId":"20021","inReplyTo":"alpine.LFD.2.01.0907051113240.3210@localhost.localdomain","subject":"Re: Wrong file diff for merge conflict","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-07-05T19:23:59Z","receivedAt":"2009-07-05T19:23:59Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> So is it a bug? Nope. I can pretty much guarantee that it's not a bug....\n\nWithout the precise common ancestor version it is hard to tell, but using\nthe \"one old version http://pastebin.ca/1483691\" as a base and running\ndiff3 (or merge from RCS suite) yields identical results as ours, so in\nthat sense it is not a bug.\n\n>  - Tune the zealous merge a bit, and in particular try to avoid the cases \n>    where this happens (as mentioned, in C code, it's often re-indentation \n>    together with trivial lines that match after it).\n>\n>    This is kind of what the \"patience\" diff algorithm tries to do: use \n>    primarily non-trivial sequences as the anchors for similarity, and \n>    ignore the trivial ones. We have a \"--patience\" switch to \"git diff\", \n>    maybe we could tune the three-way merge somehow similarly.\n\nHmm. I have to think about this a bit.\n\n>  - Don't rely so heavily on just the traditional three-way merge result.\n>\n>    This is what I personally do. The trivial 3-way merge result is \n>    wondeful for the truly trivial merges, when it gives trivial results \n>    that are easy to fix up. But let's face it, the traditional 3-way merge \n>    result just sucks for anything more complicated. When you have an empty \n>    side on one of the conflicts, is that because the other side added \n>    everything, or is it because oen side removed it? Or is it, like in \n>    this case, simply because trivially similar lines got the whole diff \n>    confused about which parts didn't change at all?\n>\n>    The good news is that git does have a few nice merge tools. One is \n>    \"git diff\", which actually shows way more than the trivial three-way \n>    end result, in that you can diff against either side, and by default it \n>    does that fairly complex \"diff against both sides\" thing that is also \n>    quite useful once you get used to it.\n>\n>    Another is \"gitk --merge [filename]\" which is wonderful as a tool to \n>    see what both sides actually did, to figure out what the intent of both \n>    branches were when the three-way merge result is just noise.\n\nTwo other are \"git log --merge -p\" and \"git checkout --conflicts=diff3\".\n\n> The right answer is probably some combination of \"all of the above\". In \n> the meantime, right now, only the last one is somethign git itself will \n> help you with.\n"},{"id":"117480","messageId":"8cdebd3f0907051523q73494603ka8a50b19b1238a@mail.gmail.com","threadId":"20021","inReplyTo":"alpine.LFD.2.01.0907051113240.3210@localhost.localdomain","subject":"Re: Wrong file diff for merge conflict","fromName":"Stefan Bucur","fromEmail":"stefan.bucur@gmail.com","sentAt":"2009-07-05T22:23:44Z","receivedAt":"2009-07-05T22:23:44Z","isPatch":false,"sender":{"key":"stefan.bucur@gmail.com","avatar":"https://gravatar.com/avatar/8c4605309711962e4ef009d2d01730506cbb10a50100d87a9f7de36de15ea2d2?d=mp&s=160"},"body":"On Sun, Jul 5, 2009 at 9:43 PM, Linus\nTorvalds<torvalds@linux-foundation.org> wrote:\n>\n>\n> On Sat, 4 Jul 2009, Stefan Bucur wrote:\n>>\n>> http://pastebin.ca/1483228\n>>\n>> The problem is with the last diff in the file, where the left portion is empty,\n>> and the right portion contains code which already was marked as merged (common),\n>> right before the start of the diff. Therefore, the mark at line 127 should\n>> really have been before line 114.\n>>\n>> Is this a bug or I am missing something?\n>\n> I suspect (but without the origin files/history I can't verify) that what\n> happens is that the \"successfully merged\" code was seen as a fully new\n> snippet of code (probably due to getting re-indented?), and the other part\n> of that action on that branch was the removal of the old code.\n>\n> That _removal_ is then shown as a conflict against the other branch, which\n> presumably didn't re-indent things (of course, it could be exactly the\n> other way around too), and so now you end up having the \"conflict\" being\n> seen as \"one branch removes this code (empty conflict part), the other one\n> presumably changed it some way\".\n>\n> Is that what you wanted? Obviously not. To you, the conflict makes no\n> sense. You're a human, who tries to understand what wen't wrong, and to\n> you, the end result of the conflict resolution makes no sense.\n\n\nThank you for your suggestions for a better and more efficient merging\nexperience, as I'm sure they will help me from now on. However, I\nthink I did not make myself clear: I was not arguing the fact that the\nmerge result was suboptimal, but the fact that _the generated conflict\nfile is semantically wrong_. So, to reiterate, we have this git\ngenerated file:\n\nhttp://pastebin.ca/1483228\n\nBasically, if one would take the common (successfully merged) parts\nand keep the \"left\" parts in the conflict sections, one would obtain\nthe first branch version of the file (with minor modifications).\nSimilarly, if one would opt to keep only the \"right\" parts in the\nconflict section, one would obtain the version found in the second\nbranch before merge.\n\nHowever, this is _not_ true in my case. If you take the last conflict\nsection in the file, if you would keep the left part, you would obtain\nthe correct left branch file, while if you keep the right part, you\nwould obtain duplicate code (the common code right before + the\ndisputed part). And that's why I think this is wrong behavior.\n\nMoreover, now I was able to trigger the bug in a way that leads to\n_data loss_. You can find here [1] an archive with a simple git\nrepository with two branches, \"a\" and \"b\", right after a merge between\nthe two, in a conflict state. The conflict file contains code which is\nmissing data in one of the two diff sides:\n\nhttp://pastebin.ca/1485051\n\nYou can notice, in the first conflict section, that the right brace of\nthe inner structure is present in the left part, while it is missing\nin the right part (feel free to reset the merge and do it again to see\nit for yourself). If you would blindly select the right part for\nconflict resolution, you would get erroneous code.\n\nDo you still think it is not a bug?\n\nThank you,\nStefan Bucur\n\n\n[1] http://terminus.zytor.com/~stefanb/git/testrepo.tgz\n"},{"id":"117486","messageId":"alpine.LFD.2.01.0907051726020.3210@localhost.localdomain","threadId":"20021","inReplyTo":"8cdebd3f0907051523q73494603ka8a50b19b1238a@mail.gmail.com","subject":"Re: Wrong file diff for merge conflict","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-07-06T00:33:36Z","receivedAt":"2009-07-06T00:33:36Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 6 Jul 2009, Stefan Bucur wrote:\n> \n> Thank you for your suggestions for a better and more efficient merging\n> experience, as I'm sure they will help me from now on. However, I\n> think I did not make myself clear: I was not arguing the fact that the\n> merge result was suboptimal, but the fact that _the generated conflict\n> file is semantically wrong_.\n\nOh. \n\nNo, you're confused about what a conflict file is.\n\n> Basically, if one would take the common (successfully merged) parts\n> and keep the \"left\" parts in the conflict sections, one would obtain\n> the first branch version of the file (with minor modifications).\n\nNo. This is not how conflicts work.\n\nIf you blindly do that, you'll always get the wrong answer. Why? Because \nyou're ignoring the parts of the file that didn't conflict. Those will be \n_outside_ the conflict markers in all cases.\n\n> Similarly, if one would opt to keep only the \"right\" parts in the\n> conflict section, one would obtain the version found in the second\n> branch before merge.\n\nSame problem. What you expect from a conflicting file is simply not true.\n\nThe fact is, a traditional rcs three-way merge (which is pretty much what \nyou get with git, ignoring the fact that we have other tools in addition \nto it, and ignoring things like criss-cross merges etc) just doesn't work \nthe way you seem to think it should work. You simply don't get the \noriginal of one side by picking one side of the conflict markers. It will \nhave merged the stuff that it thought merged cleanly, and not have any \nconflict markers at all for those parts.\n\nOf course, \"what it thought merged cleanly\" may not be what you want it to \nbe. Sometimes you get a clean merge for things that you'd have wanted to \nconflict. And sometimes you get conflicts for stuff that you'd think is \njust silly and shouldn't have. \n\nThere are no perfect file merge algorithms that I know of. Lots of people \nhate the diff3/merge behavior - it's by no means perfect. But so far, I've \nnever seen anybody successfully advocate anything better either.\n\n\t\tLinus\n"},{"id":"117507","messageId":"8cdebd3f0907060744l75a11160v8b01e6923cc5c70e@mail.gmail.com","threadId":"20021","inReplyTo":"alpine.LFD.2.01.0907051726020.3210@localhost.localdomain","subject":"Re: Wrong file diff for merge conflict","fromName":"Stefan Bucur","fromEmail":"stefan.bucur@gmail.com","sentAt":"2009-07-06T14:44:56Z","receivedAt":"2009-07-06T14:44:56Z","isPatch":false,"sender":{"key":"stefan.bucur@gmail.com","avatar":"https://gravatar.com/avatar/8c4605309711962e4ef009d2d01730506cbb10a50100d87a9f7de36de15ea2d2?d=mp&s=160"},"body":"On Mon, Jul 6, 2009 at 3:33 AM, Linus\nTorvalds<torvalds@linux-foundation.org> wrote:\n[...]\n>\n> The fact is, a traditional rcs three-way merge (which is pretty much what\n> you get with git, ignoring the fact that we have other tools in addition\n> to it, and ignoring things like criss-cross merges etc) just doesn't work\n> the way you seem to think it should work. You simply don't get the\n> original of one side by picking one side of the conflict markers. It will\n> have merged the stuff that it thought merged cleanly, and not have any\n> conflict markers at all for those parts.\n>\n> Of course, \"what it thought merged cleanly\" may not be what you want it to\n> be. Sometimes you get a clean merge for things that you'd have wanted to\n> conflict. And sometimes you get conflicts for stuff that you'd think is\n> just silly and shouldn't have.\n>\n> There are no perfect file merge algorithms that I know of. Lots of people\n> hate the diff3/merge behavior - it's by no means perfect. But so far, I've\n> never seen anybody successfully advocate anything better either.\n>\n>                Linus\n>\n\nIndeed it seems I had a wrong image of how a conflict file should\nlook. In the light of what you've told me now, everything makes sense\n:) Thank you very much for taking your time to explain these things!\n\nCheers,\nStefan Bucur\n"}]}