Re: Beyond recursive merge

[Elijah Newren <newren@gmail.com>]

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!