{"thread":{"id":"354","subject":"The criss-cross merge case","startedAt":"2005-04-27T20:25:18Z","lastAt":"2005-04-28T11:16:48Z","messageCount":9,"participants":["Bram Cohen","Daniel Barkalow","Tupshin Harper","Benedikt Schmidt","Zed A. Shaw","David Roundy"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"1898","messageId":"Pine.LNX.4.44.0504271254120.4678-100000@wax.eds.org","threadId":"354","inReplyTo":null,"subject":"The criss-cross merge case","fromName":"Bram Cohen","fromEmail":"bram@bitconjurer.org","sentAt":"2005-04-27T20:25:18Z","receivedAt":"2005-04-27T20:25:18Z","isPatch":false,"sender":{"key":"bram@bitconjurer.org","avatar":null},"body":"Here's an example of where simple three-way merge can't do the right\nthing. Each letter represents a snapshot of the history, and time goes\ndownwards. The numbers after some letters refer to which line number was\nmodified at that time.\n\n\nA\n|\\\n| \\\n|  \\\n|   \\\n|    \\\n|     \\\n|      \\\nB8      C3\n|\\     /|\n| \\   / |\n|  \\ /  |\n|   X   |\n|  / \\  |\n| /   \\ |\n|/     \\|\nD8      E3\n \\      |\n  \\     |\n   \\    |\n    \\   |\n     \\  |\n      \\ |\n       \\|\n        ?\n\nIn this case the ? should have a clean merge with the D vesion of line 8\n(because it was made with the B version already in the history) and the E\nversion of line 3 (because it was made with the C version already in the\nhistory).\n\nThe problem is that there's no single ancestor for the three-way merge\nwhich does the right thing. If one picks B, then there will be an\nunnecessary merge conflict at line 3, because D will have the C version\nand E will have the E version but B will have neither. Likewise if one\npicks C, there will be an unnecessary conflict at line 8 because D will\nhave the D version and E will have the B version but C will have neither.\nPicking A will cause unnecessary conflicts on *both* lines.\n\nThe problem can actually be much worse than a simple unnecesary conflict,\nbecause if the later updates were strict undos of the earlier updates,\nthen picking either B or C will merge something *wrong*. Using A as the\nancestor will keep that from happening, but it also maximizes unnecessary\nconflicts.\n\nNote that the above criss-cross case only involves two branches, using the\nmethodology of each one modifying their own section and pulling in old\nversions of the other one from time to time. Cogito's interface encourages\nexactly this work flow, which is not a bad thing from a work flow\nperspective, but does make it hit this case regularly.\n\nThe way Git handles this currently is very bad, because it forces the\ncommon ancestor to be from the same snapshot across all files, so this\nproblem will happen if the modifications are made even in different files,\nnot just different lines within the same file. That could be improved\ngreatly by finding an LCA for each file individually, which is what\nMonotone does. Darcs, Codeville, and all the Arch descendants have better\nmerge algorithms which don't have to pick a single common ancestor.\n\n-Bram\n\n"},{"id":"1935","messageId":"Pine.LNX.4.21.0504271854240.30848-100000@iabervon.org","threadId":"354","inReplyTo":"Pine.LNX.4.44.0504271254120.4678-100000@wax.eds.org","subject":"Re: The criss-cross merge case","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-04-27T23:32:08Z","receivedAt":"2005-04-27T23:32:08Z","isPatch":false,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Wed, 27 Apr 2005, Bram Cohen wrote:\n\n> The way Git handles this currently is very bad, because it forces the\n> common ancestor to be from the same snapshot across all files, so this\n> problem will happen if the modifications are made even in different files,\n> not just different lines within the same file. That could be improved\n> greatly by finding an LCA for each file individually, which is what\n> Monotone does.\n\nThe git core is perfectly sufficient for getting all LCAs or\nper-file best LCAs; merge-base doesn't bother, currently, because the\ndeficiencies of \"merge\" (a.k.a. diff3) are worse than the issues with\nchosing a suboptimal LCA.\n\nMy plan is to implement multi-file diff and merge with a suffix tree-based\nalgorithm, and then revisit the history stuff once we have a merger that\ncan do sensible things with this information.\n\nNote that the present very bad merger is actually seems to be sufficient\nfor the Linux kernel, where patches from different sides of a merge are\ngenerally either unrelated or are identical, and, otherwise, they tend to\nbe true conflicts where people fixed the same bug independantly in\ndifferent ways.\n\n> Darcs, Codeville, and all the Arch descendants have better merge\n> algorithms which don't have to pick a single common ancestor.\n\nI've been looking at Darcs (which seems to have a good method, although I\nthink the underlying diff isn't great), and Codeville still doesn't have\nany documentation. Arch's method is strictly weaker than 3-way merge, and\ngenerates more rejects (not even conflicts) in my experience than even\nCVS. \n\n\t-Daniel\n*This .sig left intentionally blank*\n\n"},{"id":"1951","messageId":"42703194.80409@tupshin.com","threadId":"354","inReplyTo":"Pine.LNX.4.21.0504271854240.30848-100000@iabervon.org","subject":"Re: The criss-cross merge case","fromName":"Tupshin Harper","fromEmail":"tupshin@tupshin.com","sentAt":"2005-04-28T00:43:00Z","receivedAt":"2005-04-28T00:43:00Z","isPatch":false,"sender":{"key":"tupshin@tupshin.com","avatar":null},"body":"Daniel Barkalow wrote:\n\n>I've been looking at Darcs (which seems to have a good method, although I\n>think the underlying diff isn't great), and Codeville still doesn't have\n>any documentation. Arch's method is strictly weaker than 3-way merge, and\n>generates more rejects (not even conflicts) in my experience than even\n>CVS. \n>\n>\t-Daniel\n>  \n>\nCan you clarify what you mean by darcs' underlying diff not being that\ngreat? It seems to function pretty much identically to gnu diff. In what\nway would you want the underlying diff to be improved?\n\n-Tupshin\n"},{"id":"1962","messageId":"Pine.LNX.4.21.0504272051390.30848-100000@iabervon.org","threadId":"354","inReplyTo":"42703194.80409@tupshin.com","subject":"Re: The criss-cross merge case","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-04-28T01:16:34Z","receivedAt":"2005-04-28T01:16:34Z","isPatch":false,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Wed, 27 Apr 2005, Tupshin Harper wrote:\n\n> Can you clarify what you mean by darcs' underlying diff not being that\n> great? It seems to function pretty much identically to gnu diff. In what\n> way would you want the underlying diff to be improved?\n\nGNU diff uses an algorithm which is tuned to handle finding the shortest\ndiff among a large set of similar-length alternatives while comparing\nfiles which have a lot of repeated lines. The author of the paper it cites\nis really thinking about diffing DNA sequences or similar things. It also\ncan't detect content moves, which are a common thing to have, and which\nwill be important in the long run, when we're trying to track\nmodifications to content which also moved from place to place.\n\n\t-Daniel\n*This .sig left intentionally blank*\n\n"},{"id":"1973","messageId":"87d5sf7il2.fsf@rzstud4.rz.uni-karlsruhe.de","threadId":"354","inReplyTo":"Pine.LNX.4.21.0504272051390.30848-100000@iabervon.org","subject":"Re: The criss-cross merge case","fromName":"Benedikt Schmidt","fromEmail":"ry102@rz.uni-karlsruhe.de","sentAt":"2005-04-28T02:15:05Z","receivedAt":"2005-04-28T02:15:05Z","isPatch":false,"sender":{"key":"ry102@rz.uni-karlsruhe.de","avatar":null},"body":"Daniel Barkalow <barkalow@iabervon.org> writes:\n\n> On Wed, 27 Apr 2005, Tupshin Harper wrote:\n>\n>> Can you clarify what you mean by darcs' underlying diff not being that\n>> great? It seems to function pretty much identically to gnu diff. In what\n>> way would you want the underlying diff to be improved?\n>\n> GNU diff uses an algorithm which is tuned to handle finding the shortest\n> diff among a large set of similar-length alternatives while comparing\n> files which have a lot of repeated lines. The author of the paper it cites\n> is really thinking about diffing DNA sequences or similar things.\n\nAFAIK the paper mentioned in the GNU diff sources [1] is an improvement\nto an earlier paper by the same author titled\n\"A File Comparison Program\" - Miller, Myers - 1985.\n\nCan you be more specific why the algorithm is a bad choice (performance,\nquality of diff output)?\n\n> It also can't detect content moves, which are a common thing to have, and\n> which will be important in the long run, when we're trying to track\n> modifications to content which also moved from place to place.\n\nOk, darcs doesn't handle block moves, so there is no need for an algorithm that\nsupports them (yet). Is there any free SCM that has support for block moves at\nthe moment? It seems like clearcase detects them, but I don't know where it\ntakes advantage of it.\n\nBenedikt\n\n[1] http://citeseer.ist.psu.edu/myers86ond.html\n\n"},{"id":"1978","messageId":"Pine.LNX.4.21.0504272209390.30848-100000@iabervon.org","threadId":"354","inReplyTo":"87d5sf7il2.fsf@rzstud4.rz.uni-karlsruhe.de","subject":"Re: The criss-cross merge case","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-04-28T02:19:17Z","receivedAt":"2005-04-28T02:19:17Z","isPatch":false,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Thu, 28 Apr 2005, Benedikt Schmidt wrote:\n\n> AFAIK the paper mentioned in the GNU diff sources [1] is an improvement\n> to an earlier paper by the same author titled\n> \"A File Comparison Program\" - Miller, Myers - 1985.\n\nGNU diff is based on a better algorithm than traditional diff, reportly,\nbut there are better algorithms still, developed since, at least according\nto a brief literature search on Google Scholar. (bdiff and vdelta, for\nexample, which can identify block moves as well.)\n\n> Can you be more specific why the algorithm is a bad choice (performance,\n> quality of diff output)?\n\nI suspect that the speed is suboptimal (for the cases under which it is\nactually used). The quality of the output is about ideal, lacking a\nrepresentation for block moves, but I'm hoping to have a diff/merge set\nthat handles block moves effectively, even if it can't report them in diff\nformat. I'm also hoping for an annotate function that could use block\nmoves.\n\n> Ok, darcs doesn't handle block moves, so there is no need for an algorithm that\n> supports them (yet). Is there any free SCM that has support for block moves at\n> the moment? It seems like clearcase detects them, but I don't know where it\n> takes advantage of it.\n\nI would think that darcs would be able to do neat things in its merger if\nit knew about block moves. Obviously, it only makes sense to add support\nfor identifying them and using them at the same time.\n\n\t-Daniel\n*This .sig left intentionally blank*\n\n"},{"id":"1984","messageId":"1114659700.5910.10.camel@thamachine","threadId":"354","inReplyTo":"Pine.LNX.4.21.0504271854240.30848-100000@iabervon.org","subject":"suffix array/tree deltas (Was: The criss-cross merge case)","fromName":"Zed A. Shaw","fromEmail":"zedshaw@zedshaw.com","sentAt":"2005-04-28T03:41:40Z","receivedAt":"2005-04-28T03:41:40Z","isPatch":false,"sender":{"key":"zedshaw@zedshaw.com","avatar":null},"body":"On Wed, 2005-04-27 at 19:32 -0400, Daniel Barkalow wrote:\n> On Wed, 27 Apr 2005, Bram Cohen wrote:\n> \n\n> My plan is to implement multi-file diff and merge with a suffix tree-based\n> algorithm, and then revisit the history stuff once we have a merger that\n> can do sensible things with this information.\n\nHey, that's neat.  I've already implemented two versions of this very\nthing with FastCST.  The original used suffix trees, but I found that\nthere were plenty of pathological cases which chewed memory and\nprocessor.  Most of these cases were large (>1MB) PDF files.  Don't ask\nme why PDF drove suffix tree algorithms insane, but they just did.\n\nI recently switched to a suffix array based algorithm which actually\nends up being faster than the suffix tree alternative.  I'm not using\nthe most recent fastest algorithm and it still compares favorably with\nxdelta.\n\nThere's tons of weird things about doing a delta based on suffix\narrays/trees, so feel free to pick my brain or the FastCST code if you\nattempt it.  The difficult parts turn out to be making the suffix array\nand searching for the matching/non-matching regions.  Once you do that\nthe actual delta algorithm is a simple while loop that keeps doing the\nmatch/non-match detection.\n\nZed\n"},{"id":"1989","messageId":"Pine.LNX.4.21.0504280016000.30848-100000@iabervon.org","threadId":"354","inReplyTo":"1114659700.5910.10.camel@thamachine","subject":"Re: suffix array/tree deltas (Was: The criss-cross merge case)","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-04-28T04:30:25Z","receivedAt":"2005-04-28T04:30:25Z","isPatch":false,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Wed, 27 Apr 2005, Zed A. Shaw wrote:\n\n> On Wed, 2005-04-27 at 19:32 -0400, Daniel Barkalow wrote:\n> \n> > My plan is to implement multi-file diff and merge with a suffix tree-based\n> > algorithm, and then revisit the history stuff once we have a merger that\n> > can do sensible things with this information.\n> \n> Hey, that's neat.  I've already implemented two versions of this very\n> thing with FastCST.  The original used suffix trees, but I found that\n> there were plenty of pathological cases which chewed memory and\n> processor.  Most of these cases were large (>1MB) PDF files.  Don't ask\n> me why PDF drove suffix tree algorithms insane, but they just did.\n\nI'm not too surprised; but can you hope to merge or compare PDFs\nanyway? I'd think that you'd just screw up alignment or something. (Note\nthat we aren't using deltas for history storage, so we're not interested\nin the \"compressing multiple versions\" aspect of diffs.) I think I want to\npunt anything too binary-like and try to find an unambiguous history-based\ndifference (i.e., there was some commit in the past that replaced one of\nthe versions with the other; therefore, we want the replacing one).\n\nI'm thinking of line-based compressed suffix trees, with the obvious delta\nalgorithm: make the trees, find the longest prefix of the file, find the\nlongest prefix of the rest of the file, add an insertion for a line\nthat doesn't match, repeat. I probably need a few extra things to\nstabilize the process (prefer that the next chunk come from the same file,\nprefer that it come from next in the file, ignore copied lines without\nenough content).\n\nI haven't actually started yet; I'm waiting for a weekend when I'm feeling\ninspired and not too fried.\n\n\t-Daniel\n*This .sig left intentionally blank*\n\n"},{"id":"2026","messageId":"20050428111647.GB9422@abridgegame.org","threadId":"354","inReplyTo":"Pine.LNX.4.21.0504272209390.30848-100000@iabervon.org","subject":"Re: The criss-cross merge case","fromName":"David Roundy","fromEmail":"droundy@abridgegame.org","sentAt":"2005-04-28T11:16:48Z","receivedAt":"2005-04-28T11:16:48Z","isPatch":false,"sender":{"key":"droundy@abridgegame.org","avatar":"https://gravatar.com/avatar/e8bcfd76f63303732bdfcdba6fc8ac6ccdff8f5a224a25ffaca24bd8a4c4571f?d=mp&s=160"},"body":"On Wed, Apr 27, 2005 at 10:19:17PM -0400, Daniel Barkalow wrote:\n> On Thu, 28 Apr 2005, Benedikt Schmidt wrote:\n> > Ok, darcs doesn't handle block moves, so there is no need for an\n> > algorithm that supports them (yet). Is there any free SCM that has\n> > support for block moves at the moment? It seems like clearcase detects\n> > them, but I don't know whqere it takes advantage of it.\n> \n> I would think that darcs would be able to do neat things in its merger if\n> it knew about block moves. Obviously, it only makes sense to add support\n> for identifying them and using them at the same time.\n\nIndeed, handling block moves would definitely be *very* nice.  An ancient\nversion of darcs actually did this (it's not in the current darcs history,\nsince it was so ancient and buggy), although it had a terrible diff\nalgorithm.  But I really didn't understand the theory back then, and when I\nrewrote everything, I never added the block moves back in.  They complicate\nconflict situations a bit, and once I found that darcs was actually\nuseable, I started focusing on other issues.  (Most recently efficiency\nissues.)\n-- \nDavid Roundy\nhttp://www.darcs.net\n"}]}