* Re: Beyond recursive merge
2022-09-14 2:24 ` Beyond recursive merge Elijah Newren
@ 2022-09-20 1:42 ` Elijah Newren
0 siblings, 0 replies; 2+ messages in thread
From: Elijah Newren @ 2022-09-20 1:42 UTC (permalink / raw)
To: Git Mailing List; +Cc: Michael Haggerty
As a quick follow-up, Michael and I talked about this a bit at Git
Merge. We didn't have time to discuss everything, but a few points:
* Michael was just exploring ideas, I was treating it as an
implementation suggestion (thus my focus on edge and corner cases).
* I was mistaken in my understanding leading to question #5. F & G
will each have B or C as a direct parent, and the merge base that
isn't a direct parent is the one you consider to be one the same
branch. (Thus, e.g. F has C as a direct parent, so F & B are
considered to be the same branch.)
* Michael seemed to really like the XDL_MERGE_PREFER_BASE idea, so I
should probably clean up that patch and submit it.
If I've missed any important points, I'm sure he'll chime in.
On Tue, Sep 13, 2022 at 7:24 PM Elijah Newren <newren@gmail.com> wrote:
>
> Hi Michael!
>
> On Sun, Sep 11, 2022 at 9:10 PM Michael Haggerty <mhagger@alum.mit.edu> 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@mail.gmail.com/).
> 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@mail.gmail.com/
>
>
> 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!
^ permalink raw reply [flat|nested] 2+ messages in thread