Hi Michael! On Sun, Sep 11, 2022 at 9:10 PM Michael Haggerty <mhagger@xxxxxxxxxxxx> wrote: > > Hi! > > I haven't been around here lately, but that doesn't mean that I've stopped thinking about Git :-) > > 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) I had a little trouble finding [1]; it appears to be https://softwareswirl.blogspot.com/2022/09/beyond-three-way-merge.html . merge-ort and merge-recursive are indeed built on the same recursive algorithm; `ort` even stands for `Ostensibly Recursive's Twin` due to the intent to copy the high-level "recursive" design (and because I thought `git merge -sort` looked amusing.) > sometimes produces very questionable results, I'll comment more on this later, but... > and sometimes reports conflicts in cases that I think could be resolved automatically. > For example, in the following situation, I argue that the correct merge result is "e", whereas recursive merge reports a conflict: > > ---a-------b---d---e ← main > \ \ / \ > \ \ / \ > \ \ / \ > \ ⋅ ? ← desired merge commit > \ / \ / > \ / \ / > \ / \ / > c---c---f ← branch > > > 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. This is very interesting! From the blog post, the rationale is basically that the "f" on "branch" was created via a three-way merge of {a,b,c}->f, therefore, since the virtual merge base also needs to do a three-way merge of {a,b,c} there is no need to conflict because that result is known to be f from elsewhere. That means the outer merge becomes a three-way merge of {f,f,e} which trivially resolves to e. That makes sense to me. But, I came away from your blog post with a lot of questions, possibly more than what I started with. And a few comments... === Questions === 1) Your statistics show there are a significant number of cases with more than 2 merge bases (at least relative to the number of cases with 2 merge bases), but your algorithm is tied to there being exactly 2 merge bases. You stated this limitation, but didn't state what should be done for the other cases. Fall back to a `recursive` merge? You did at least mention that you didn't know, wondering aloud whether such merges could be composed. But, I'm wondering too now. :-) 2) You didn't explicitly state that your merge bases themselves need to have a unique merge base, but it seems to me to be intrinsic to your description. What do you do if your merge bases have multiple merge bases? Fall back to merging the merge bases? Find some other way to make your algorithm recursive? (And does recursiveness for your algorithm even make sense given the heavy reliance on change-then-revert in your problem descriptions? I started getting confused just thinking about it...) 3) Your description depended on your graph that you "simplified to the bare minimum", namely: ---A-------B---D---F ← main \ \ / \ \ \ / \ \ \ / \ \ ⋅ ? ← desired merge commit \ / \ / \ / \ / \ / \ / C---E---G ← branch I think this graph is actually simplified beyond the bare minimum. In particular, your descriptions rely on F and G both being the cross-branch merge commits *and* being the final commit on their branch. I think an improved minimum graph would be: ---A-------B---D---F---H ← main \ \ / \ \ \ / \ \ \ / \ \ ⋅ ? ← desired merge commit \ / \ / \ / \ / \ / \ / C---E---G---I ← branch Can your ideas be extended to handle these kinds of cases? Would that end up with a 9-way merge instead of a 7-way, or would you just fall back to recursive merges when either F!=H or G!=I? 4) The above graph is oversimplified in another dimension. In fact, it took me a while to determine what {D,F} and {E,G} are for the generic case. From reading your post and the arguments, I work out the following: * B and C are the two merge bases for the merge you are trying to resolve. * A is the unique merge base of B and C. * F is the "first" merge commit on "main" which includes C in its history. (By "first" I mean none of its ancestors include C). * G is the "first" merge commit on "branch" which includes B in its history. * D is the parent of F which contains B in its history. * E is the parent of G which contains C in its history. * In my graph, H and I are the final commits on "main" and "branch", respectively. * Other than (D,F) and (E,G), there could be many commits in "main" and "branch" between any two points on the above graph * There are a few places where there could be zero commits between points on the graph, resulting in any of the following commits being dropped as redundant: D, E, H, I. * If any commits are dropped as redundant, the commit before it on the same branch serves a second purpose. (for example, if there is no D, then B is F's first parent) Above, you'll note some assumptions: * There are exactly 2 merge bases for the merge, namely B&C * There is exactly 1 merge base of B & C (namely A) * In your graph, you have assumed that H and I are not separate from F & G * There is a single "first" merge commit on "main" containing C. * There is a single "first" merge commit on "branch" containing B. * [I think] First parent history of F leads to B, and likewise for G leading to C. The first three of these assumptions were addressed previously, as my first three questions. The last I'll address in the next item. For now, I want to concentrate on the "first" merge commit assumption. What do you do when there is more than one first merge commit on either of the branches? Would you pick one randomly or based on some criteria (possibly getting different results based on which one you picked?) Would you try to merge them together to get a unique first merge commit? Would you just bail and use the current recursive algorithm? 5) Above I mentioned a possible assumption that the first parent history of F leads to B and likewise G leads to C. Perhaps that isn't quite the assumption, but you have drawn {A,B,F} as being part of the "main" branch, and {A,C,G} as being part of the "branch" branch. But that choice seems arbitrary. What if we instead considered {A,C,F} as part of "main" and {A,B,G} as part of "branch" (swapping which branches B & C are considered part of)? Does your algorithm in some fashion depend on the order of the parents in the F & G merge commits? If not, how is it decided which branch B and C are on? If the user performed one of the prior merge commits differently than you expect (perhaps the first parent history leads to B for both of them), does it negate the applicability of your algorithm? Modify your algorithm results? Or is there some kind of symmetry that makes this not matter? Even if there is some kind of symmetry related to the merges, swapping which branches include which merge base would lead to different choices for D & E. In particular, those commits would be required to be whichever immediate parent of F or G contained the relevant merge base in its history. Does changing D & E to accommodate the swap of B & C change the merge results from your algorithm? If so, does that represent some kind of weird ill-posedness or directional dependence of merge results? Perhaps an example would help. Let's use your example from the email I'm responding to. That example could either be reduced to a---b---d | | | c---⋅---e | | | c---f---? as you did in your blog OR if the merge-bases are discovered slightly differently it could be reduced to a---b---b | | | c---⋅---f | | | c---e---? The former reduction appears resolvable using your earlier trick, but the latter isn't resolvable because we didn't find the earlier {a,b,c}->f 3-way merge, meaning I think it would result in a conflict. Or does your idea require that we find all previous merge commits in the history of the two sides since the merge bases, and look carefully at conflict resolutions involving the parents in each direction? And do we need to do this at the individual hunk level for all those merges and parents? 6) You did not address how to write out conflicts to text files in your blog post. If using the standard merge.conflictStyle=merge, then there's no problem, we can just do the standard showing of the endpoint differences. But what about merge.conflictStyle=diff3? Your algorithm attempts to bypass the construction of a unique merge base, so it's ill-defined what one would even write for diff3. Would you attempt to create a merge base in such a case? (And if you do, is that misleading since that merge-base isn't really part of the algorithm used to determine how things should be merged?). Alternatively, would there be a diff7 or diff9 variant only applicable in these special recursive merges where you are applying your new rules? 7) The focus only on scalars left me wondering whether the algorithm applied only at the entire-file level, or whether it applied to individual patch hunks. I had to re-read it before I caught it ("This algorithm could be applied one hunk at a time."). But does that mean you want to extend xdiff to implement 9-way or even 7-way merges? Would those even have reasonable hunk regions to investigate, or would one of the many sides have some slight differences resulting in unreasonably extended hunk sizes and frequently resulting in complex 9-way conflicts? Maybe it wouldn't, but I'm more than a little worried that your attempt to reduce unnecessary conflicts would have the opposite effect in practice -- not only making conflicts more frequent but perhaps even more complex too. In part, this is because it is known that diff3 will at times have larger context regions than when only looking at two sides, so 9-way or even 7-way just seems likely to exacerbate that problem. 8) I am very confused about your usage of "twice" in "But recursive merge doesn't notice that that conflict has already been resolved by the user (twice!) in the form of commits f and e". As far as I can tell, the {a,b,c} 3-way merge has only been resolved once, with the result of f. There was also an {a,d,c} 3-way merge that was resolved to e, but that's a different merge. Perhaps you were thinking of "d" as "b" plus some changes in an area disjoint from what was changed in c, but that makes no sense given that your blog post explicitly mentioned you were merging scalars throughout the article. So, I'm quite confused about where you get your "twice" from. Am I missing something? === Comments === 1) Regarding: "Moreover, when a multiple-merge-base merge fails, it can fail in a most baffling way, with conflict markers nested inside of other conflict markers, that is almost impossible to make sense out of." I don't disagree with this, but I have some comments/questions: * I'm curious how much of this statement was due to experience from the time when we didn't adjust the conflict marker length for inner merges. * This might be irrelevant to your blog post, but I'm curious if there's an implicit assumption here that nested conflict markers only happen when there are multiple merge bases (I've certainly seen other Git developers assume such). Nested conflict markers can also happen with a unique merge base, though those cases are perhaps much more rare. * There is a potential way to avoid the nested conflict markers which are due to recursive merges: XDL_MERGE_FAVOR_BASE (https://lore.kernel.org/git/CABPp-BFPaHEUzJsBO1dyv+7DteZfJX=Qfi2dLaYS5J30VAVAcA@xxxxxxxxxxxxxx/). I haven't gotten around to cleaning it up and submitting it. Replaying merges will probably spur me to do so, though. 2) Regarding: "Also check whether there were diff hunks that didn't conflict, but where users changed the automatic merge resolution" --remerge-diff may come in handy! 3) Big picture: Much of the blog post seems to conflate recursive merge issues with 3-way-content merge issues. In particular, it focuses on "change-then-revert" cases, which are an area where folks tend to complain about 3-way-merge behavior. Enough so that we documented it specifically in git-merge(1) to point it out: """ With the strategies that use 3-way merge (including the default, ort), if a change is made on both branches, but later reverted on one of the branches, that change will be present in the merged result; some people find this behavior confusing. It occurs because only the heads and the merge base are considered when performing a merge, not the individual commits. The merge algorithm therefore considers the reverted change as no change at all, and substitutes the changed version instead. """ It appears in several cases that you are ultimately just arguing against this behavior of 3-way merges, but hidden in a way that seems to attribute it to recursiveness. Some examples below, but first a few comments: * I think your arguments about surprising results often do not apply to the recursive merge being performed, but to the non-recursive merges performed previously which are inputs to the recursive merge. * It's possible that I'm just confused about something with your arguments, and the above conflation is merely unfortunate. However, I'm pretty sure at least one of us is confused by it. Coming up with examples that don't involve "change-then-revert" would really help clear things up. * I'm reminded of other attempts to "fix" change-then-revert, in a negative way. It seems to always be an attempt to say that merging should depend not only on the end results of the branches we are merging, but on the particular path by which the user arrived at those end results. While ignoring the path by which the user arrived at their results (an intrinsic "feature" of three-way merges) does have some downsides, I feel like attempting to pay attention to that history ends up pushing us into deep complexity with rough tradeoffs that feel like they'll be worse than the original problem. See, for example, [2] for another instance where this came up. * If "change-then-revert" really is the core problem you are trying to solve, I do have a potential idea of interest in this area that I've never floated before...though it'd be very expensive and would have to be selected through a non-default option. (Also, not sure it's relevant, but I previously thought about that option mostly in the context of non-recursive merges.) [2] https://lore.kernel.org/git/CABPp-BF5S6QT6Hn-1wf6w67-ayWfX5WZLZqueNMMeqp1jtXirg@xxxxxxxxxxxxxx/ 4) I disagree with some of the suggested alternative resolutions or claims about unexpected results, in part because of the conflation above. Let me quote and respond to two examples: 4a) """ Change b made then reverted on one branch; kept on the other branch [...] a---b---a a---b---a | | | | | | b---⋅---b → b--(b)--b | | | | | | b---b---? b---b---b [...] There are two plausible narratives here: Maybe change b was implemented then reverted on one branch, but then it was independently implemented on the other branch, possibly for another reason. In this case, it would be correct to keep b as the merge resolution. Maybe change b was cherry-picked from one branch to the other, then on one branch it was discovered that the change was bad, so it was reverted. In that case, one would want the revert back to a to be used as the merge resolution. """ All the above arguments apply to the top part of that graph, whether you meant to or not: a---b---a a---b---a | | | | b---⋅---b → b---.---b The arguments suggest you perhaps feel that the prior merge was wrong and should not have picked b. If you had argued that, I'd understand, though I'd say it's somewhat fundamental to 3-way merges[2]. And, actually, we don't know that the merge algorithm picked b. We have pluggable merge backends, after all, and allow user-written ones, even ones not based on 3-way merge. The merge backend the user was using for that prior merge could have presented a conflict for all we know. Whether they were presented with a conflict, the user was given a chance to inspect the result, run regression and integration tests, put it up for review, and decide whether to publish it. So, this result has been blessed by the user. That merge may have been performed weeks or months ago, but regardless, it is an input to the merge you are now running. And I don't see how to arrive at your conclusion on the current merge case without treating that user-blessed result as either erroneous or just outright disregarding it. As such, I disagree with your claims about this case. I would have filed it in the category of cases where recursive merge succeeds. There's a further issue with this example as well: I'm curious whether this example makes your blog less self-consistent. In particular, the idea I commented on at the beginning of this email about how previous merge resolutions could be re-used for the merge base appears useful here. Looking at this example from that lens, there was already a 3-way merge of {a,b,b} resolved in favor of b (bottom middle merge commit). As such, shouldn't the virtual merge base, which is also an {a,b,b} 3-way merge be resolved to b? And shouldn't that result in a 3-way merge of {b,b,b} for the outer merge? This logic came from your "The example that motivated this study" section of your blog, and unless I'm missing something, it appears to be in conflict with your suggestion that the example here should result in a merge conflict. 4b) """ Same change made then reverted on both branches: a---b---a a---b---a | | | | | | b---⋅---b → b--(b)--b | | | | | | a---b---? a---b---b In this case, arguably since change b was made then reverted on each of the branches, then the user merges are not needed, and the final result should be a. An alternative interpretation (which I think is less persuasive) is that the pre-done merges in both cases favored contents b over a, so the final result should also favor b. I think that the result should either be a conflict or a, whereas recursive merge gives b. """ To me, "user merges are not needed" translates to "user-blessed results are wrong and/or can be ignored". People inspected, tested, posted for review, and published those results. Or at least had every opportunity to. So we clearly disagree here. But I'm perhaps more surprised by the other statement you made here, where you suggest that even when the tips of both branches being merged exactly match each other, that the merge result should cleanly be something else? I have a hard time thinking of something that I believe would confuse users more about merges if this were to be implemented. === Summary === Anyway, among my many questions and few disagreements, it may well be that I've just misunderstood various points. Totally possible. Regardless of whether I did, it was a very interesting read and a new and refreshing take. And even despite questions and some disagreements, I agree that one of your examples seems legitimate and very interesting. I'm not sure exactly how or if it translates in practice, but we'll probably have fun discussing this at the contributor summit. See you tomorrow!
