git@vger.kernel.org mailing list mirror (one of many)
 help / color / mirror / code / Atom feed
* Re: Beyond recursive merge
       [not found] <CAMy9T_EN_Vz=y6R9H03HOh2o+SbENZtxH78HJuS4skQHHYpLVw@mail.gmail.com>
@ 2022-09-14  2:24 ` Elijah Newren
  2022-09-20  1:42   ` Elijah Newren
  0 siblings, 1 reply; 2+ messages in thread
From: Elijah Newren @ 2022-09-14  2:24 UTC (permalink / raw)
  To: Michael Haggerty; +Cc: Git Mailing List

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

* 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

end of thread, other threads:[~2022-09-20  1:43 UTC | newest]

Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
     [not found] <CAMy9T_EN_Vz=y6R9H03HOh2o+SbENZtxH78HJuS4skQHHYpLVw@mail.gmail.com>
2022-09-14  2:24 ` Beyond recursive merge Elijah Newren
2022-09-20  1:42   ` Elijah Newren

Code repositories for project(s) associated with this public inbox

	https://80x24.org/mirrors/git.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).