{"thread":{"id":"1641","subject":"[RFC] Looking at multiple ancestors in merge","startedAt":"2005-08-25T03:32:19Z","lastAt":"2005-08-26T15:47:29Z","messageCount":7,"participants":["Daniel Barkalow","A Large Angry SCM","Matthias Urlichs","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"7736","messageId":"Pine.LNX.4.63.0508242249030.23242@iabervon.org","threadId":"1641","inReplyTo":null,"subject":"[RFC] Looking at multiple ancestors in merge","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-08-25T03:32:19Z","receivedAt":"2005-08-25T03:32:19Z","isPatch":false,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"I'm starting to work on letting the merging process see multiple\nancestors, and I think it's messy enough that I should actually discuss\nit.\n\nReview of the issue:\n\nIt is possible to lost reverts in cases when merging two commits with\nmultiple ancestors, in the following pattern: (letters representing blobs\nat some filename, children to the right)\n\na-b-b-a-?\n \\ X   /\n  a-b-b\n\nYou form a branch with unrelated changes, apply a patch in the top line,\nseparately merge both ways, do unrelated development in the bottom line,\nand revert the patch in the top line. Then you're trying to merge the two\nlines. There are two candidates for the common ancestor, the two in the\nsecond column. If you pick the top one, you get the revert; if you pick\nthe bottom one, you don't. This is a bug, because it ignores the 'a'\nversion due to it being \"unchanged\", but it actually did change and\nchanged back.\n\nNote that the revert is going to also be ignored if there isn't the \"X\" in\nthe middle of that diagram and the a->b change on the bottom is due to\nindependantly applying the same patch. Users are more likely to expect\nthis, however, than the situation above, where the side that is causing\nthe patch to be included never applied it explicitly at all; it just\nmerged at an unfortunate moment.\n\nMy theory is that we should handle merges by passing all of the ancestors\nto read-tree, and having it use the following additions to the rules for\ntrivial merges:\n\n - If any of the ancestors matches a side, don't use that side\n - If you eliminate both side, don't do the trivial merge\n\n(The first of these also means that it'll pick the best combination of\nancestors for maximizing trivial merges, as a nice side effect; the second\nmeans that it'll avoid messing up with reverts when it has a chance of\nunderstanding them)\n\nIf it doesn't do the trivial merge, it just puts the blob from the first\nlisted ancestor in stage 1, rather than trying anything fancy.\n\n(As a further improvement, we could actually look through the history for\nreasons to disregard a similarity, which would determine that there isn't\na continuous line of similarity from the recent 'a' to the common ancestor\n'a', and therefore that it should be retained; but I'll be satisfied for\nnow with having it just not do the incorrect trivial merge.)\n\nOf course, this is going to take a bit of work, because read-tree\ncurrently puts all of its arguments into the cache and then works on\nmerging, and taking multiple ancestors requires putting them somewhere\nelse, because they won't fit in the cache.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"7739","messageId":"430D4B75.6060102@gmail.com","threadId":"1641","inReplyTo":"Pine.LNX.4.63.0508242249030.23242@iabervon.org","subject":"Re: [RFC] Looking at multiple ancestors in merge","fromName":"A Large Angry SCM","fromEmail":"gitzilla@gmail.com","sentAt":"2005-08-25T04:39:17Z","receivedAt":"2005-08-25T04:39:17Z","isPatch":false,"sender":{"key":"gitzilla@gmail.com","avatar":"https://gravatar.com/avatar/354625c442439908ff3dd99757dee330e29e9df7847472384faf7a00add247fb?d=mp&s=160"},"body":"Daniel Barkalow wrote:\n> I'm starting to work on letting the merging process see multiple\n> ancestors, and I think it's messy enough that I should actually discuss\n> it.\n> \n> Review of the issue:\n> \n> It is possible to lost reverts in cases when merging two commits with\n> multiple ancestors, in the following pattern: (letters representing blobs\n> at some filename, children to the right)\n> \n> a-b-b-a-?\n>  \\ X   /\n>   a-b-b\n> \n[Lots of stuff deleted]\n\nThere seems to be a lot of effort being put into auto-magically choosing\nthe \"right\" merge in the presence of multiple possible merge bases.\nUnfortunately, most (all?) of the proposals are attempting to divine\nintent, and so, are guaranteed to be 100% wrong at least some of the time.\n\nWouldn't it be better, instead, to detect that current merge being\nattempted is ambiguous and require the user to specify the correct merge\nbase? The alternative is a tool that appears to work all of the time but\ndoes the wrong thing some of the time.\n"},{"id":"7741","messageId":"Pine.LNX.4.63.0508250108100.23242@iabervon.org","threadId":"1641","inReplyTo":"430D4B75.6060102@gmail.com","subject":"Re: [RFC] Looking at multiple ancestors in merge","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-08-25T05:20:31Z","receivedAt":"2005-08-25T05:20:31Z","isPatch":false,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Wed, 24 Aug 2005, A Large Angry SCM wrote:\n\n> Daniel Barkalow wrote:\n> > I'm starting to work on letting the merging process see multiple\n> > ancestors, and I think it's messy enough that I should actually discuss\n> > it.\n> >\n> > Review of the issue:\n> >\n> > It is possible to lost reverts in cases when merging two commits with\n> > multiple ancestors, in the following pattern: (letters representing blobs\n> > at some filename, children to the right)\n> >\n> > a-b-b-a-?\n> >  \\ X   /\n> >   a-b-b\n> >\n> [Lots of stuff deleted]\n>\n> There seems to be a lot of effort being put into auto-magically choosing\n> the \"right\" merge in the presence of multiple possible merge bases.\n> Unfortunately, most (all?) of the proposals are attempting to divine\n> intent, and so, are guaranteed to be 100% wrong at least some of the time.\n>\n> Wouldn't it be better, instead, to detect that current merge being\n> attempted is ambiguous and require the user to specify the correct merge\n> base? The alternative is a tool that appears to work all of the time but\n> does the wrong thing some of the time.\n\nMy proposal is actually to detect when a merge is ambiguous. In order to\ndetermine that, however, you have to evaluate multiple potential outcomes\nand see if they are actually different. I'm working on an efficient way to\ndo that.\n\nThen further work could look into eliminating possibilities when\ninformation about the history excludes them. There were two issues in the\ncase that Tony hit: it ignored a potential correct outcome for the merge,\nand it didn't ignore an outcome which could be demonstrated to be\nincorrect. The priority is to resolve the first, but things which improve\nthe second or help with solutions to the second are worth understanding.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"7743","messageId":"pan.2005.08.25.06.56.22.883900@smurf.noris.de","threadId":"1641","inReplyTo":"Pine.LNX.4.63.0508250108100.23242@iabervon.org","subject":"Re: [RFC] Looking at multiple ancestors in merge","fromName":"Matthias Urlichs","fromEmail":"smurf@smurf.noris.de","sentAt":"2005-08-25T06:56:25Z","receivedAt":"2005-08-25T06:56:25Z","isPatch":false,"sender":{"key":"matthias@urlichs.de","avatar":"https://gravatar.com/avatar/2708905af227313eba6f2b2ae0f7d0259b5ac5d71baef58fe5a13c699ce0bbf0?d=mp&s=160"},"body":"Hi, Daniel Barkalow wrote:\n\n> My proposal is actually to detect when a merge is ambiguous. In order to\n> determine that, however, you have to evaluate multiple potential outcomes\n> and see if they are actually different. I'm working on an efficient way to\n> do that.\n\nGood.\n\nThere's also a related problem which I've hit last month or so, where one\nview has the same file (or at least one with the same name) added to both\nsides of the branch, but the other view doesn't.\n\nUnfortunately, that can happen to both branches independently, so you\nreally need to choose a merge base per file instead of globally. I suspect\nthat many of the problem cases simply go away when you do that.\n\n-- \nMatthias Urlichs   |   {M:U} IT Design @ m-u-it.de   |  smurf@smurf.noris.de\nDisclaimer: The quote was selected randomly. Really. | http://smurf.noris.de\n - -\nJones' Second Law:\n\tThe man who smiles when things go wrong has thought of someone\n\tto blame it on.\n"},{"id":"7787","messageId":"Pine.LNX.4.63.0508260108290.23242@iabervon.org","threadId":"1641","inReplyTo":"Pine.LNX.4.63.0508242249030.23242@iabervon.org","subject":"Re: [RFC] Looking at multiple ancestors in merge","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-08-26T05:16:55Z","receivedAt":"2005-08-26T05:16:55Z","isPatch":false,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Wed, 24 Aug 2005, Daniel Barkalow wrote:\n\n> Of course, this is going to take a bit of work, because read-tree\n> currently puts all of its arguments into the cache and then works on\n> merging, and taking multiple ancestors requires putting them somewhere\n> else, because they won't fit in the cache.\n\nI've started this, and have gotten as far as having read-tree accept > 3\ntrees and ignore everything but the last 3. Am I correct in assuming that\nif I break read-tree in any way, some test will fail?\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"7793","messageId":"7vwtm9f3me.fsf@assigned-by-dhcp.cox.net","threadId":"1641","inReplyTo":"Pine.LNX.4.63.0508260108290.23242@iabervon.org","subject":"Re: [RFC] Looking at multiple ancestors in merge","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-08-26T09:29:13Z","receivedAt":"2005-08-26T09:29:13Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Daniel Barkalow <barkalow@iabervon.org> writes:\n\n> I've started this, and have gotten as far as having read-tree accept > 3\n> trees and ignore everything but the last 3. Am I correct in assuming that\n> if I break read-tree in any way, some test will fail?\n\nIf some test fails you would know you broke it, but the inverse\nis probably not always true.\n\nI think the current read-tree test suite has reasonably wide\ncoverage of all the interesting cases.  But the definition of\n\"interesting\" was derived from the current world order (IOW, the\ntest suite was designed around the way we do things right now as\na whitebox test, not a blackbox test).  I would not be surprised\nif some of them did not catch breakage you may introduce during\nthe development.\n\nI wonder however if extending the current way of doing things in\nthe cache is the right thing.  Right now we use two bits out of\nthe top four bits for recording stage, one bit for the update\nbit, so you have only one extra bit to extend the number of\nstages, which means you could hold at most 7 trees at once.\n\nYou \"ignore things but the last 3\", so this may not be too much\nof a problem, but I am a bit puzzled what you meant by it\nthough.  Are you talking about reading more than 3 trees and\nkeeping only the 3 to be merged, discarding the rest, doing the\nselection per path?\n"},{"id":"7810","messageId":"Pine.LNX.4.63.0508261123150.23242@iabervon.org","threadId":"1641","inReplyTo":"7vwtm9f3me.fsf@assigned-by-dhcp.cox.net","subject":"Re: [RFC] Looking at multiple ancestors in merge","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-08-26T15:47:29Z","receivedAt":"2005-08-26T15:47:29Z","isPatch":false,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Fri, 26 Aug 2005, Junio C Hamano wrote:\n\n> Daniel Barkalow <barkalow@iabervon.org> writes:\n>\n> > I've started this, and have gotten as far as having read-tree accept > 3\n> > trees and ignore everything but the last 3. Am I correct in assuming that\n> > if I break read-tree in any way, some test will fail?\n>\n> If some test fails you would know you broke it, but the inverse\n> is probably not always true.\n>\n> I think the current read-tree test suite has reasonably wide\n> coverage of all the interesting cases.  But the definition of\n> \"interesting\" was derived from the current world order (IOW, the\n> test suite was designed around the way we do things right now as\n> a whitebox test, not a blackbox test).  I would not be surprised\n> if some of them did not catch breakage you may introduce during\n> the development.\n\nOkay; I think the only thing that I'm going to change with respect to how\nit makes decisions will be with 4+ trees, and those will obviously need\nnew tests,\n\n> I wonder however if extending the current way of doing things in\n> the cache is the right thing.  Right now we use two bits out of\n> the top four bits for recording stage, one bit for the update\n> bit, so you have only one extra bit to extend the number of\n> stages, which means you could hold at most 7 trees at once.\n>\n> You \"ignore things but the last 3\", so this may not be too much\n> of a problem, but I am a bit puzzled what you meant by it\n> though.  Are you talking about reading more than 3 trees and\n> keeping only the 3 to be merged, discarding the rest, doing the\n> selection per path?\n\nFor each path, I intend to look at all the entries and make trivial merge\njudgements on them, but then only leave the usual stage 2 and stage 3, and\na chosen stage 1. The way I'm writing the changes is:\n\nIn the argument parsing loop, just form a list of the tree objects, and\nactually read them after the whole list is ready. If there are more than\n3, ignore all but the last 3. This lets you give an arbitary number of\ncommon ancestors to read-tree, and it won't mess up, but it will only use\none of them. I've done this.\n\nNext, scan through the tree entry lists for all the trees together, and\ngenerate cache entries for the same path in the different trees at the\nsame time. I've written this, but I've got a few bugs, and the 3way merge\ntests are dutifully failing.\n\nThen, I'll do the trivial merge on tree entries rather than cache\nentries.\n\nFinally, I'll extend the trivial merge to use the extra ancestors.\n\nSince merge(1) doesn't handle multiple common ancestors, having more than\n3 stages in the cache after the trivial merge isn't going to be useful for\nnow.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"}]}