{"thread":{"id":"58429","subject":"Re: Beyond recursive merge","startedAt":"2022-09-14T02:25:17Z","lastAt":"2022-09-20T01:43:48Z","messageCount":2,"participants":["Elijah Newren"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"463011","messageId":"CABPp-BHTDpHdpC70YUWT9_E5iz-4HvwfJtwO0T1_VfNzWw48pw@mail.gmail.com","threadId":"58429","inReplyTo":"CAMy9T_EN_Vz=y6R9H03HOh2o+SbENZtxH78HJuS4skQHHYpLVw@mail.gmail.com","subject":"Re: Beyond recursive merge","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2022-09-14T02:24:52Z","receivedAt":"2022-09-14T02:25:17Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Hi Michael!\n\nOn Sun, Sep 11, 2022 at 9:10 PM Michael Haggerty <mhagger@alum.mit.edu> wrote:\n>\n> Hi!\n>\n> I haven't been around here lately, but that doesn't mean that I've stopped thinking about Git :-)\n>\n> I just published a blog post [1] in which I argue that recursive merge (and presumably merge-ort, which I think uses the same recursive algorithm)\n\nI had a little trouble finding [1]; it appears to be\nhttps://softwareswirl.blogspot.com/2022/09/beyond-three-way-merge.html\n.\n\nmerge-ort and merge-recursive are indeed built on the same recursive\nalgorithm; `ort` even stands for `Ostensibly Recursive's Twin` due to\nthe intent to copy the high-level \"recursive\" design (and because I\nthought `git merge -sort` looked amusing.)\n\n> sometimes produces very questionable results,\n\nI'll comment more on this later, but...\n\n> and sometimes reports conflicts in cases that I think could be resolved automatically.\n> For example, in the following situation, I argue that the correct merge result is \"e\", whereas recursive merge reports a conflict:\n>\n> ---a-------b---d---e          ← main\n>     \\       \\     / \\\n>      \\       \\   /   \\\n>       \\       \\ /     \\\n>        \\       ⋅       ?      ← desired merge commit\n>         \\     / \\     /\n>          \\   /   \\   /\n>           \\ /     \\ /\n>            c---c---f          ← branch\n>\n>\n> If you are interested, please check out the blog post. I'll also be hanging around the Git Merge contributor's summit, in case anybody wants to talk about the subject.\n\nThis is very interesting!  From the blog post, the rationale is\nbasically that the \"f\" on \"branch\" was created via a three-way merge\nof {a,b,c}->f, therefore, since the virtual merge base also needs to\ndo a three-way merge of {a,b,c} there is no need to conflict because\nthat result is known to be f from elsewhere.  That means the outer\nmerge becomes a three-way merge of {f,f,e} which trivially resolves to\ne.  That makes sense to me.\n\nBut, I came away from your blog post with a lot of questions, possibly\nmore than what I started with.  And a few comments...\n\n=== Questions ===\n\n1) Your statistics show there are a significant number of cases with\nmore than 2 merge bases (at least relative to the number of cases with\n2 merge bases), but your algorithm is tied to there being exactly 2\nmerge bases.  You stated this limitation, but didn't state what should\nbe done for the other cases.  Fall back to a `recursive` merge?  You\ndid at least mention that you didn't know, wondering aloud whether\nsuch merges could be composed.  But, I'm wondering too now.  :-)\n\n2) You didn't explicitly state that your merge bases themselves need\nto have a unique merge base, but it seems to me to be intrinsic to\nyour description.  What do you do if your merge bases have multiple\nmerge bases?  Fall back to merging the merge bases?  Find some other\nway to make your algorithm recursive?  (And does recursiveness for\nyour algorithm even make sense given the heavy reliance on\nchange-then-revert in your problem descriptions?  I started getting\nconfused just thinking about it...)\n\n3) Your description depended on your graph that you \"simplified to the\nbare minimum\", namely:\n---A-------B---D---F          ← main\n    \\       \\     / \\\n     \\       \\   /   \\\n      \\       \\ /     \\\n       \\       ⋅       ?      ← desired merge commit\n        \\     / \\     /\n         \\   /   \\   /\n          \\ /     \\ /\n           C---E---G          ← branch\nI think this graph is actually simplified beyond the bare minimum.  In\nparticular, your descriptions rely on F and G both being the\ncross-branch merge commits *and* being the final commit on their branch.\nI think an improved minimum graph would be:\n---A-------B---D---F---H          ← main\n    \\       \\     /     \\\n     \\       \\   /       \\\n      \\       \\ /         \\\n       \\       ⋅           ?      ← desired merge commit\n        \\     / \\         /\n         \\   /   \\       /\n          \\ /     \\     /\n           C---E---G---I          ← branch\nCan your ideas be extended to handle these kinds of cases?  Would that\nend up with a 9-way merge instead of a 7-way, or would you just fall\nback to recursive merges when either F!=H or G!=I?\n\n4) The above graph is oversimplified in another dimension.  In fact,\nit took me a while to determine what {D,F} and {E,G} are for the\ngeneric case.  From reading your post and the arguments, I work out\nthe following:\n  * B and C are the two merge bases for the merge you are trying to resolve.\n  * A is the unique merge base of B and C.\n  * F is the \"first\" merge commit on \"main\" which includes C in its\nhistory.  (By \"first\" I mean none of its ancestors include C).\n  * G is the \"first\" merge commit on \"branch\" which includes B in its history.\n  * D is the parent of F which contains B in its history.\n  * E is the parent of G which contains C in its history.\n  * In my graph, H and I are the final commits on \"main\" and \"branch\",\nrespectively.\n  * Other than (D,F) and (E,G), there could be many commits in \"main\"\nand \"branch\" between any two points on the above graph\n  * There are a few places where there could be zero commits between\npoints on the graph, resulting in any of the following commits being\ndropped as redundant: D, E, H, I.\n  * If any commits are dropped as redundant, the commit before it on\nthe same branch serves a second purpose.  (for example, if there is no\nD, then B is F's first parent)\nAbove, you'll note some assumptions:\n  * There are exactly 2 merge bases for the merge, namely B&C\n  * There is exactly 1 merge base of B & C (namely A)\n  * In your graph, you have assumed that H and I are not separate from F & G\n  * There is a single \"first\" merge commit on \"main\" containing C.\n  * There is a single \"first\" merge commit on \"branch\" containing B.\n  * [I think] First parent history of F leads to B, and likewise for G\nleading to C.\nThe first three of these assumptions were addressed previously, as my\nfirst three questions.  The last I'll address in the next item.  For\nnow, I want to concentrate on the \"first\" merge commit assumption.\nWhat do you do when there is more than one first merge commit on\neither of the branches?  Would you pick one randomly or based on some\ncriteria (possibly getting different results based on which one you\npicked?)  Would you try to merge them together to get a unique first\nmerge commit?  Would you just bail and use the current recursive\nalgorithm?\n\n5) Above I mentioned a possible assumption that the first parent history\nof F leads to B and likewise G leads to C.  Perhaps that isn't quite\nthe assumption, but you have drawn {A,B,F} as being part of the \"main\"\nbranch, and {A,C,G} as being part of the \"branch\" branch.  But that\nchoice seems arbitrary.  What if we instead considered {A,C,F} as part\nof \"main\" and {A,B,G} as part of \"branch\" (swapping which branches B &\nC are considered part of)?  Does your algorithm in some fashion depend\non the order of the parents in the F & G merge commits?  If not, how\nis it decided which branch B and C are on?  If the user performed one\nof the prior merge commits differently than you expect (perhaps the first\nparent history leads to B for both of them), does it negate the\napplicability of your algorithm?  Modify your algorithm results?  Or\nis there some kind of symmetry that makes this not matter?  Even if\nthere is some kind of symmetry related to the merges, swapping\nwhich branches include which merge base would lead to different\nchoices for D & E.  In particular, those commits would be required to\nbe whichever immediate parent of F or G contained the relevant merge\nbase in its history. Does changing D & E to accommodate the swap of B\n& C change the merge results from your algorithm?  If so, does that\nrepresent some kind of weird ill-posedness or directional dependence\nof merge results?\n\nPerhaps an example would help.  Let's use your example from the email\nI'm responding to.  That example could either be reduced to\n    a---b---d\n    |   |   |\n    c---⋅---e\n    |   |   |\n    c---f---?\nas you did in your blog OR if the merge-bases are discovered slightly\ndifferently it could be reduced to\n    a---b---b\n    |   |   |\n    c---⋅---f\n    |   |   |\n   c---e---?\nThe former reduction appears resolvable using your earlier trick, but\nthe latter isn't resolvable because we didn't find the earlier\n{a,b,c}->f 3-way merge, meaning I think it would result in a conflict.\nOr does your\nidea require that we find all previous merge commits in the history of\nthe two sides since the merge bases, and look carefully at conflict\nresolutions involving the parents in each direction?  And do we need\nto do this at the individual hunk level for all those merges and parents?\n\n6) You did not address how to write out conflicts to text files in\nyour blog post.  If using the standard merge.conflictStyle=merge, then\nthere's no problem, we can just do the standard showing of the\nendpoint differences.  But what about merge.conflictStyle=diff3?  Your\nalgorithm attempts to bypass the construction of a unique merge base,\nso it's ill-defined what one would even write for diff3.  Would you attempt to\ncreate a merge base in such a case?  (And if you do, is that misleading since\nthat merge-base isn't really part of the algorithm used to determine\nhow things should be merged?).  Alternatively, would there be a diff7\nor diff9 variant only applicable in these special recursive merges\nwhere you are applying your new rules?\n\n7) The focus only on scalars left me wondering whether the algorithm\napplied only at the entire-file level, or whether it applied to\nindividual patch hunks.  I had to re-read it before I caught it (\"This\nalgorithm could be applied one hunk at a time.\").  But does that mean\nyou want to extend xdiff to implement 9-way or even 7-way merges?\nWould those even have reasonable hunk regions to investigate, or would\none of the many sides have some slight differences resulting in\nunreasonably extended hunk sizes and frequently resulting in complex\n9-way conflicts?  Maybe it wouldn't, but I'm more than a little\nworried that your attempt to reduce unnecessary conflicts would have\nthe opposite effect in practice -- not only making conflicts more frequent\nbut perhaps even more complex too.  In part, this is because it is\nknown that diff3 will at times have larger context regions than when\nonly looking at two sides, so 9-way or even 7-way just seems likely to\nexacerbate that problem.\n\n8) I am very confused about your usage of \"twice\" in \"But recursive\nmerge doesn't notice that that conflict has already been resolved by\nthe user (twice!) in the form of commits f and e\".  As far as I can\ntell, the {a,b,c} 3-way merge has only been resolved once, with the\nresult of f.  There was also an {a,d,c} 3-way merge that was resolved\nto e, but that's a different merge.  Perhaps you were thinking of \"d\"\nas \"b\" plus some changes in an area disjoint from what was changed in\nc, but that makes no sense given that your blog post explicitly\nmentioned you were merging scalars throughout the article.  So, I'm\nquite confused about where you get your \"twice\" from.  Am I missing\nsomething?\n\n\n=== Comments ===\n\n1) Regarding: \"Moreover, when a multiple-merge-base merge fails, it\ncan fail in a most baffling way, with conflict markers nested inside\nof other conflict markers, that is almost impossible to make sense out\nof.\"\n\nI don't disagree with this, but I have some comments/questions:\n\n* I'm curious how much of this statement was due to experience from\nthe time when we didn't adjust the conflict marker length for inner\nmerges.\n* This might be irrelevant to your blog post, but I'm curious if\nthere's an implicit assumption here that nested conflict markers only\nhappen when there are multiple merge bases (I've certainly seen other\nGit developers assume such).  Nested conflict markers can also happen\nwith a unique merge base, though those cases are perhaps much more\nrare.\n* There is a potential way to avoid the nested conflict markers which are due to\nrecursive merges: XDL_MERGE_FAVOR_BASE\n(https://lore.kernel.org/git/CABPp-BFPaHEUzJsBO1dyv+7DteZfJX=Qfi2dLaYS5J30VAVAcA@mail.gmail.com/).\nI haven't gotten around to cleaning it up and submitting it. Replaying\nmerges will probably spur me to do so, though.\n\n2) Regarding: \"Also check whether there were diff hunks that didn't\nconflict, but where users changed the automatic merge resolution\"\n\n--remerge-diff may come in handy!\n\n3) Big picture: Much of the blog post seems to conflate recursive\nmerge issues with 3-way-content merge issues.  In particular, it\nfocuses on \"change-then-revert\" cases, which are an area where folks\ntend to complain about 3-way-merge behavior.  Enough so that we\ndocumented it specifically in git-merge(1) to point it out:\n\"\"\"\n       With the strategies that use 3-way merge (including the default, ort),\n       if a change is made on both branches, but later reverted on one of the\n       branches, that change will be present in the merged result; some people\n       find this behavior confusing. It occurs because only the heads and the\n       merge base are considered when performing a merge, not the individual\n       commits. The merge algorithm therefore considers the reverted change as\n       no change at all, and substitutes the changed version instead.\n\"\"\"\nIt appears in several cases that you are ultimately just arguing\nagainst this behavior of 3-way merges, but hidden in a way that seems\nto attribute it to recursiveness.  Some examples below, but first a\nfew comments:\n* I think your arguments about surprising results often do not apply\nto the recursive merge being performed, but to the non-recursive\nmerges performed previously which are inputs to the recursive merge.\n* It's possible that I'm just confused about something with your\narguments, and the above conflation is merely unfortunate.  However,\nI'm pretty sure at least one of us is confused by it.  Coming up with\nexamples that don't involve \"change-then-revert\" would really help\nclear things up.\n* I'm reminded of other attempts to \"fix\" change-then-revert, in a\nnegative way.  It seems to always be an attempt to say that merging\nshould depend not only on the end results of the branches we are\nmerging, but on the particular path by which the user arrived at those\nend results.  While ignoring the path by which the user arrived at\ntheir results (an intrinsic \"feature\" of three-way merges) does have\nsome downsides, I feel like attempting to pay\nattention to that history ends up pushing us into deep complexity with\nrough tradeoffs that feel like they'll be worse than the original\nproblem.  See, for example, [2] for another instance where this came\nup.\n* If \"change-then-revert\" really is the core problem you are trying to\nsolve, I do have a potential idea of interest in this area that I've\nnever floated before...though it'd be very expensive and would have to\nbe selected through a non-default option.  (Also, not sure it's\nrelevant, but I previously thought\nabout that option mostly in the context of non-recursive merges.)\n\n[2] https://lore.kernel.org/git/CABPp-BF5S6QT6Hn-1wf6w67-ayWfX5WZLZqueNMMeqp1jtXirg@mail.gmail.com/\n\n\n4) I disagree with some of the suggested alternative resolutions or\nclaims about unexpected results, in part because of the conflation\nabove.  Let me quote and respond to two examples:\n\n4a)\n\"\"\"\nChange b made then reverted on one branch; kept on the other branch\n[...]\n    a---b---a       a---b---a\n    |   |   |       |   |   |\n    b---⋅---b   →   b--(b)--b\n    |   |   |       |   |   |\n    b---b---?       b---b---b\n[...]\nThere are two plausible narratives here:\n\nMaybe change b was implemented then reverted on one branch, but then\nit was independently implemented on the other branch, possibly for\nanother reason. In this case, it would be correct to keep b as the\nmerge resolution.\n\nMaybe change b was cherry-picked from one branch to the other, then on\none branch it was discovered that the change was bad, so it was\nreverted. In that case, one would want the revert back to a to be used\nas the merge resolution.\n\"\"\"\n\nAll the above arguments apply to the top part of that graph, whether\nyou meant to or not:\n    a---b---a       a---b---a\n    |       |       |       |\n    b---⋅---b   →   b---.---b\nThe arguments suggest you perhaps feel that the prior merge was wrong\nand should not\nhave picked b.  If you had argued that, I'd understand, though I'd say\nit's somewhat fundamental to 3-way merges[2].  And, actually, we don't\nknow that the merge algorithm picked b.  We have pluggable merge\nbackends, after all, and allow user-written ones, even ones not based\non 3-way merge.  The merge backend the user was using for that prior\nmerge could have\npresented a conflict for all we know.  Whether they were presented\nwith a conflict, the user was given a chance to inspect the result,\nrun regression and integration tests, put it up for review, and decide\nwhether to publish it.  So, this result has been blessed by the user.\nThat merge may have been performed weeks or months ago, but\nregardless, it is an input to the merge you are now running.  And I\ndon't see how to arrive at your conclusion on the current merge case\nwithout treating that user-blessed result as either erroneous or just\noutright disregarding it.  As such, I disagree with your claims about\nthis case.  I would have filed it in the category of cases where\nrecursive merge succeeds.\n\nThere's a further issue with this example as well: I'm curious whether\nthis example makes your blog less self-consistent.  In particular, the\nidea I commented on at the beginning of this email about how previous\nmerge resolutions could be re-used for the merge base appears useful\nhere.  Looking at this example from that lens, there was already a\n3-way merge of {a,b,b} resolved in favor of b (bottom middle merge\ncommit).  As such, shouldn't the virtual merge base, which is also an\n{a,b,b} 3-way merge be resolved to b?  And shouldn't that result in a\n3-way merge of {b,b,b} for the outer merge?  This logic came from your\n\"The example that motivated this study\" section of your blog, and\nunless I'm missing something, it appears to be in conflict with your\nsuggestion that the example here should result in a merge conflict.\n\n4b)\n\"\"\"\nSame change made then reverted on both branches:\n\na---b---a       a---b---a\n|   |   |       |   |   |\nb---⋅---b   →   b--(b)--b\n|   |   |       |   |   |\na---b---?       a---b---b\nIn this case, arguably since change b was made then reverted on each\nof the branches, then the user merges are not needed, and the final\nresult should be a. An alternative interpretation (which I think is\nless persuasive) is that the pre-done merges in both cases favored\ncontents b over a, so the final result should also favor b. I think\nthat the result should either be a conflict or a, whereas recursive\nmerge gives b.\n\"\"\"\n\nTo me, \"user merges are not needed\" translates to \"user-blessed\nresults are wrong and/or can be ignored\".  People inspected, tested, posted for\nreview, and published those results.  Or at least had every\nopportunity to.  So we clearly disagree here.  But I'm perhaps more\nsurprised by the other statement you made here, where you suggest that\neven when the tips of both branches being merged exactly match each\nother, that the merge result should cleanly be something else?  I have\na hard time thinking of something that I believe would confuse users\nmore about merges if this were to be implemented.\n\n\n=== Summary ===\n\nAnyway, among my many questions and few disagreements, it may well be\nthat I've just misunderstood various points.  Totally possible.\nRegardless of whether I did, it was a very interesting read and a new\nand refreshing take.  And even despite questions and some\ndisagreements, I agree that one of your examples seems legitimate and\nvery interesting.  I'm not sure exactly how or if it translates in\npractice, but we'll probably have fun discussing this at the\ncontributor summit.\n\nSee you tomorrow!\n"},{"id":"463252","messageId":"CABPp-BFzOs7e61JZocjW0=kZYms74uqhzyqPhAL3ZDi84EwQ5Q@mail.gmail.com","threadId":"58429","inReplyTo":"CABPp-BHTDpHdpC70YUWT9_E5iz-4HvwfJtwO0T1_VfNzWw48pw@mail.gmail.com","subject":"Re: Beyond recursive merge","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2022-09-20T01:42:12Z","receivedAt":"2022-09-20T01:43:48Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"As a quick follow-up, Michael and I talked about this a bit at Git\nMerge.  We didn't have time to discuss everything, but a few points:\n  * Michael was just exploring ideas, I was treating it as an\nimplementation suggestion (thus my focus on edge and corner cases).\n  * I was mistaken in my understanding leading to question #5.  F & G\nwill each have B or C as a direct parent, and the merge base that\nisn't a direct parent is the one you consider to be one the same\nbranch.  (Thus, e.g. F has C as a direct parent, so F & B are\nconsidered to be the same branch.)\n  * Michael seemed to really like the XDL_MERGE_PREFER_BASE idea, so I\nshould probably clean up that patch and submit it.\n\nIf I've missed any important points, I'm sure he'll chime in.\n\nOn Tue, Sep 13, 2022 at 7:24 PM Elijah Newren <newren@gmail.com> wrote:\n>\n> Hi Michael!\n>\n> On Sun, Sep 11, 2022 at 9:10 PM Michael Haggerty <mhagger@alum.mit.edu> wrote:\n> >\n> > Hi!\n> >\n> > I haven't been around here lately, but that doesn't mean that I've stopped thinking about Git :-)\n> >\n> > I just published a blog post [1] in which I argue that recursive merge (and presumably merge-ort, which I think uses the same recursive algorithm)\n>\n> I had a little trouble finding [1]; it appears to be\n> https://softwareswirl.blogspot.com/2022/09/beyond-three-way-merge.html\n> .\n>\n> merge-ort and merge-recursive are indeed built on the same recursive\n> algorithm; `ort` even stands for `Ostensibly Recursive's Twin` due to\n> the intent to copy the high-level \"recursive\" design (and because I\n> thought `git merge -sort` looked amusing.)\n>\n> > sometimes produces very questionable results,\n>\n> I'll comment more on this later, but...\n>\n> > and sometimes reports conflicts in cases that I think could be resolved automatically.\n> > For example, in the following situation, I argue that the correct merge result is \"e\", whereas recursive merge reports a conflict:\n> >\n> > ---a-------b---d---e          ← main\n> >     \\       \\     / \\\n> >      \\       \\   /   \\\n> >       \\       \\ /     \\\n> >        \\       ⋅       ?      ← desired merge commit\n> >         \\     / \\     /\n> >          \\   /   \\   /\n> >           \\ /     \\ /\n> >            c---c---f          ← branch\n> >\n> >\n> > If you are interested, please check out the blog post. I'll also be hanging around the Git Merge contributor's summit, in case anybody wants to talk about the subject.\n>\n> This is very interesting!  From the blog post, the rationale is\n> basically that the \"f\" on \"branch\" was created via a three-way merge\n> of {a,b,c}->f, therefore, since the virtual merge base also needs to\n> do a three-way merge of {a,b,c} there is no need to conflict because\n> that result is known to be f from elsewhere.  That means the outer\n> merge becomes a three-way merge of {f,f,e} which trivially resolves to\n> e.  That makes sense to me.\n>\n> But, I came away from your blog post with a lot of questions, possibly\n> more than what I started with.  And a few comments...\n>\n> === Questions ===\n>\n> 1) Your statistics show there are a significant number of cases with\n> more than 2 merge bases (at least relative to the number of cases with\n> 2 merge bases), but your algorithm is tied to there being exactly 2\n> merge bases.  You stated this limitation, but didn't state what should\n> be done for the other cases.  Fall back to a `recursive` merge?  You\n> did at least mention that you didn't know, wondering aloud whether\n> such merges could be composed.  But, I'm wondering too now.  :-)\n>\n> 2) You didn't explicitly state that your merge bases themselves need\n> to have a unique merge base, but it seems to me to be intrinsic to\n> your description.  What do you do if your merge bases have multiple\n> merge bases?  Fall back to merging the merge bases?  Find some other\n> way to make your algorithm recursive?  (And does recursiveness for\n> your algorithm even make sense given the heavy reliance on\n> change-then-revert in your problem descriptions?  I started getting\n> confused just thinking about it...)\n>\n> 3) Your description depended on your graph that you \"simplified to the\n> bare minimum\", namely:\n> ---A-------B---D---F          ← main\n>     \\       \\     / \\\n>      \\       \\   /   \\\n>       \\       \\ /     \\\n>        \\       ⋅       ?      ← desired merge commit\n>         \\     / \\     /\n>          \\   /   \\   /\n>           \\ /     \\ /\n>            C---E---G          ← branch\n> I think this graph is actually simplified beyond the bare minimum.  In\n> particular, your descriptions rely on F and G both being the\n> cross-branch merge commits *and* being the final commit on their branch.\n> I think an improved minimum graph would be:\n> ---A-------B---D---F---H          ← main\n>     \\       \\     /     \\\n>      \\       \\   /       \\\n>       \\       \\ /         \\\n>        \\       ⋅           ?      ← desired merge commit\n>         \\     / \\         /\n>          \\   /   \\       /\n>           \\ /     \\     /\n>            C---E---G---I          ← branch\n> Can your ideas be extended to handle these kinds of cases?  Would that\n> end up with a 9-way merge instead of a 7-way, or would you just fall\n> back to recursive merges when either F!=H or G!=I?\n>\n> 4) The above graph is oversimplified in another dimension.  In fact,\n> it took me a while to determine what {D,F} and {E,G} are for the\n> generic case.  From reading your post and the arguments, I work out\n> the following:\n>   * B and C are the two merge bases for the merge you are trying to resolve.\n>   * A is the unique merge base of B and C.\n>   * F is the \"first\" merge commit on \"main\" which includes C in its\n> history.  (By \"first\" I mean none of its ancestors include C).\n>   * G is the \"first\" merge commit on \"branch\" which includes B in its history.\n>   * D is the parent of F which contains B in its history.\n>   * E is the parent of G which contains C in its history.\n>   * In my graph, H and I are the final commits on \"main\" and \"branch\",\n> respectively.\n>   * Other than (D,F) and (E,G), there could be many commits in \"main\"\n> and \"branch\" between any two points on the above graph\n>   * There are a few places where there could be zero commits between\n> points on the graph, resulting in any of the following commits being\n> dropped as redundant: D, E, H, I.\n>   * If any commits are dropped as redundant, the commit before it on\n> the same branch serves a second purpose.  (for example, if there is no\n> D, then B is F's first parent)\n> Above, you'll note some assumptions:\n>   * There are exactly 2 merge bases for the merge, namely B&C\n>   * There is exactly 1 merge base of B & C (namely A)\n>   * In your graph, you have assumed that H and I are not separate from F & G\n>   * There is a single \"first\" merge commit on \"main\" containing C.\n>   * There is a single \"first\" merge commit on \"branch\" containing B.\n>   * [I think] First parent history of F leads to B, and likewise for G\n> leading to C.\n> The first three of these assumptions were addressed previously, as my\n> first three questions.  The last I'll address in the next item.  For\n> now, I want to concentrate on the \"first\" merge commit assumption.\n> What do you do when there is more than one first merge commit on\n> either of the branches?  Would you pick one randomly or based on some\n> criteria (possibly getting different results based on which one you\n> picked?)  Would you try to merge them together to get a unique first\n> merge commit?  Would you just bail and use the current recursive\n> algorithm?\n>\n> 5) Above I mentioned a possible assumption that the first parent history\n> of F leads to B and likewise G leads to C.  Perhaps that isn't quite\n> the assumption, but you have drawn {A,B,F} as being part of the \"main\"\n> branch, and {A,C,G} as being part of the \"branch\" branch.  But that\n> choice seems arbitrary.  What if we instead considered {A,C,F} as part\n> of \"main\" and {A,B,G} as part of \"branch\" (swapping which branches B &\n> C are considered part of)?  Does your algorithm in some fashion depend\n> on the order of the parents in the F & G merge commits?  If not, how\n> is it decided which branch B and C are on?  If the user performed one\n> of the prior merge commits differently than you expect (perhaps the first\n> parent history leads to B for both of them), does it negate the\n> applicability of your algorithm?  Modify your algorithm results?  Or\n> is there some kind of symmetry that makes this not matter?  Even if\n> there is some kind of symmetry related to the merges, swapping\n> which branches include which merge base would lead to different\n> choices for D & E.  In particular, those commits would be required to\n> be whichever immediate parent of F or G contained the relevant merge\n> base in its history. Does changing D & E to accommodate the swap of B\n> & C change the merge results from your algorithm?  If so, does that\n> represent some kind of weird ill-posedness or directional dependence\n> of merge results?\n>\n> Perhaps an example would help.  Let's use your example from the email\n> I'm responding to.  That example could either be reduced to\n>     a---b---d\n>     |   |   |\n>     c---⋅---e\n>     |   |   |\n>     c---f---?\n> as you did in your blog OR if the merge-bases are discovered slightly\n> differently it could be reduced to\n>     a---b---b\n>     |   |   |\n>     c---⋅---f\n>     |   |   |\n>    c---e---?\n> The former reduction appears resolvable using your earlier trick, but\n> the latter isn't resolvable because we didn't find the earlier\n> {a,b,c}->f 3-way merge, meaning I think it would result in a conflict.\n> Or does your\n> idea require that we find all previous merge commits in the history of\n> the two sides since the merge bases, and look carefully at conflict\n> resolutions involving the parents in each direction?  And do we need\n> to do this at the individual hunk level for all those merges and parents?\n>\n> 6) You did not address how to write out conflicts to text files in\n> your blog post.  If using the standard merge.conflictStyle=merge, then\n> there's no problem, we can just do the standard showing of the\n> endpoint differences.  But what about merge.conflictStyle=diff3?  Your\n> algorithm attempts to bypass the construction of a unique merge base,\n> so it's ill-defined what one would even write for diff3.  Would you attempt to\n> create a merge base in such a case?  (And if you do, is that misleading since\n> that merge-base isn't really part of the algorithm used to determine\n> how things should be merged?).  Alternatively, would there be a diff7\n> or diff9 variant only applicable in these special recursive merges\n> where you are applying your new rules?\n>\n> 7) The focus only on scalars left me wondering whether the algorithm\n> applied only at the entire-file level, or whether it applied to\n> individual patch hunks.  I had to re-read it before I caught it (\"This\n> algorithm could be applied one hunk at a time.\").  But does that mean\n> you want to extend xdiff to implement 9-way or even 7-way merges?\n> Would those even have reasonable hunk regions to investigate, or would\n> one of the many sides have some slight differences resulting in\n> unreasonably extended hunk sizes and frequently resulting in complex\n> 9-way conflicts?  Maybe it wouldn't, but I'm more than a little\n> worried that your attempt to reduce unnecessary conflicts would have\n> the opposite effect in practice -- not only making conflicts more frequent\n> but perhaps even more complex too.  In part, this is because it is\n> known that diff3 will at times have larger context regions than when\n> only looking at two sides, so 9-way or even 7-way just seems likely to\n> exacerbate that problem.\n>\n> 8) I am very confused about your usage of \"twice\" in \"But recursive\n> merge doesn't notice that that conflict has already been resolved by\n> the user (twice!) in the form of commits f and e\".  As far as I can\n> tell, the {a,b,c} 3-way merge has only been resolved once, with the\n> result of f.  There was also an {a,d,c} 3-way merge that was resolved\n> to e, but that's a different merge.  Perhaps you were thinking of \"d\"\n> as \"b\" plus some changes in an area disjoint from what was changed in\n> c, but that makes no sense given that your blog post explicitly\n> mentioned you were merging scalars throughout the article.  So, I'm\n> quite confused about where you get your \"twice\" from.  Am I missing\n> something?\n>\n>\n> === Comments ===\n>\n> 1) Regarding: \"Moreover, when a multiple-merge-base merge fails, it\n> can fail in a most baffling way, with conflict markers nested inside\n> of other conflict markers, that is almost impossible to make sense out\n> of.\"\n>\n> I don't disagree with this, but I have some comments/questions:\n>\n> * I'm curious how much of this statement was due to experience from\n> the time when we didn't adjust the conflict marker length for inner\n> merges.\n> * This might be irrelevant to your blog post, but I'm curious if\n> there's an implicit assumption here that nested conflict markers only\n> happen when there are multiple merge bases (I've certainly seen other\n> Git developers assume such).  Nested conflict markers can also happen\n> with a unique merge base, though those cases are perhaps much more\n> rare.\n> * There is a potential way to avoid the nested conflict markers which are due to\n> recursive merges: XDL_MERGE_FAVOR_BASE\n> (https://lore.kernel.org/git/CABPp-BFPaHEUzJsBO1dyv+7DteZfJX=Qfi2dLaYS5J30VAVAcA@mail.gmail.com/).\n> I haven't gotten around to cleaning it up and submitting it. Replaying\n> merges will probably spur me to do so, though.\n>\n> 2) Regarding: \"Also check whether there were diff hunks that didn't\n> conflict, but where users changed the automatic merge resolution\"\n>\n> --remerge-diff may come in handy!\n>\n> 3) Big picture: Much of the blog post seems to conflate recursive\n> merge issues with 3-way-content merge issues.  In particular, it\n> focuses on \"change-then-revert\" cases, which are an area where folks\n> tend to complain about 3-way-merge behavior.  Enough so that we\n> documented it specifically in git-merge(1) to point it out:\n> \"\"\"\n>        With the strategies that use 3-way merge (including the default, ort),\n>        if a change is made on both branches, but later reverted on one of the\n>        branches, that change will be present in the merged result; some people\n>        find this behavior confusing. It occurs because only the heads and the\n>        merge base are considered when performing a merge, not the individual\n>        commits. The merge algorithm therefore considers the reverted change as\n>        no change at all, and substitutes the changed version instead.\n> \"\"\"\n> It appears in several cases that you are ultimately just arguing\n> against this behavior of 3-way merges, but hidden in a way that seems\n> to attribute it to recursiveness.  Some examples below, but first a\n> few comments:\n> * I think your arguments about surprising results often do not apply\n> to the recursive merge being performed, but to the non-recursive\n> merges performed previously which are inputs to the recursive merge.\n> * It's possible that I'm just confused about something with your\n> arguments, and the above conflation is merely unfortunate.  However,\n> I'm pretty sure at least one of us is confused by it.  Coming up with\n> examples that don't involve \"change-then-revert\" would really help\n> clear things up.\n> * I'm reminded of other attempts to \"fix\" change-then-revert, in a\n> negative way.  It seems to always be an attempt to say that merging\n> should depend not only on the end results of the branches we are\n> merging, but on the particular path by which the user arrived at those\n> end results.  While ignoring the path by which the user arrived at\n> their results (an intrinsic \"feature\" of three-way merges) does have\n> some downsides, I feel like attempting to pay\n> attention to that history ends up pushing us into deep complexity with\n> rough tradeoffs that feel like they'll be worse than the original\n> problem.  See, for example, [2] for another instance where this came\n> up.\n> * If \"change-then-revert\" really is the core problem you are trying to\n> solve, I do have a potential idea of interest in this area that I've\n> never floated before...though it'd be very expensive and would have to\n> be selected through a non-default option.  (Also, not sure it's\n> relevant, but I previously thought\n> about that option mostly in the context of non-recursive merges.)\n>\n> [2] https://lore.kernel.org/git/CABPp-BF5S6QT6Hn-1wf6w67-ayWfX5WZLZqueNMMeqp1jtXirg@mail.gmail.com/\n>\n>\n> 4) I disagree with some of the suggested alternative resolutions or\n> claims about unexpected results, in part because of the conflation\n> above.  Let me quote and respond to two examples:\n>\n> 4a)\n> \"\"\"\n> Change b made then reverted on one branch; kept on the other branch\n> [...]\n>     a---b---a       a---b---a\n>     |   |   |       |   |   |\n>     b---⋅---b   →   b--(b)--b\n>     |   |   |       |   |   |\n>     b---b---?       b---b---b\n> [...]\n> There are two plausible narratives here:\n>\n> Maybe change b was implemented then reverted on one branch, but then\n> it was independently implemented on the other branch, possibly for\n> another reason. In this case, it would be correct to keep b as the\n> merge resolution.\n>\n> Maybe change b was cherry-picked from one branch to the other, then on\n> one branch it was discovered that the change was bad, so it was\n> reverted. In that case, one would want the revert back to a to be used\n> as the merge resolution.\n> \"\"\"\n>\n> All the above arguments apply to the top part of that graph, whether\n> you meant to or not:\n>     a---b---a       a---b---a\n>     |       |       |       |\n>     b---⋅---b   →   b---.---b\n> The arguments suggest you perhaps feel that the prior merge was wrong\n> and should not\n> have picked b.  If you had argued that, I'd understand, though I'd say\n> it's somewhat fundamental to 3-way merges[2].  And, actually, we don't\n> know that the merge algorithm picked b.  We have pluggable merge\n> backends, after all, and allow user-written ones, even ones not based\n> on 3-way merge.  The merge backend the user was using for that prior\n> merge could have\n> presented a conflict for all we know.  Whether they were presented\n> with a conflict, the user was given a chance to inspect the result,\n> run regression and integration tests, put it up for review, and decide\n> whether to publish it.  So, this result has been blessed by the user.\n> That merge may have been performed weeks or months ago, but\n> regardless, it is an input to the merge you are now running.  And I\n> don't see how to arrive at your conclusion on the current merge case\n> without treating that user-blessed result as either erroneous or just\n> outright disregarding it.  As such, I disagree with your claims about\n> this case.  I would have filed it in the category of cases where\n> recursive merge succeeds.\n>\n> There's a further issue with this example as well: I'm curious whether\n> this example makes your blog less self-consistent.  In particular, the\n> idea I commented on at the beginning of this email about how previous\n> merge resolutions could be re-used for the merge base appears useful\n> here.  Looking at this example from that lens, there was already a\n> 3-way merge of {a,b,b} resolved in favor of b (bottom middle merge\n> commit).  As such, shouldn't the virtual merge base, which is also an\n> {a,b,b} 3-way merge be resolved to b?  And shouldn't that result in a\n> 3-way merge of {b,b,b} for the outer merge?  This logic came from your\n> \"The example that motivated this study\" section of your blog, and\n> unless I'm missing something, it appears to be in conflict with your\n> suggestion that the example here should result in a merge conflict.\n>\n> 4b)\n> \"\"\"\n> Same change made then reverted on both branches:\n>\n> a---b---a       a---b---a\n> |   |   |       |   |   |\n> b---⋅---b   →   b--(b)--b\n> |   |   |       |   |   |\n> a---b---?       a---b---b\n> In this case, arguably since change b was made then reverted on each\n> of the branches, then the user merges are not needed, and the final\n> result should be a. An alternative interpretation (which I think is\n> less persuasive) is that the pre-done merges in both cases favored\n> contents b over a, so the final result should also favor b. I think\n> that the result should either be a conflict or a, whereas recursive\n> merge gives b.\n> \"\"\"\n>\n> To me, \"user merges are not needed\" translates to \"user-blessed\n> results are wrong and/or can be ignored\".  People inspected, tested, posted for\n> review, and published those results.  Or at least had every\n> opportunity to.  So we clearly disagree here.  But I'm perhaps more\n> surprised by the other statement you made here, where you suggest that\n> even when the tips of both branches being merged exactly match each\n> other, that the merge result should cleanly be something else?  I have\n> a hard time thinking of something that I believe would confuse users\n> more about merges if this were to be implemented.\n>\n>\n> === Summary ===\n>\n> Anyway, among my many questions and few disagreements, it may well be\n> that I've just misunderstood various points.  Totally possible.\n> Regardless of whether I did, it was a very interesting read and a new\n> and refreshing take.  And even despite questions and some\n> disagreements, I agree that one of your examples seems legitimate and\n> very interesting.  I'm not sure exactly how or if it translates in\n> practice, but we'll probably have fun discussing this at the\n> contributor summit.\n>\n> See you tomorrow!\n"}]}