Tricky corner case with merging a merge ("duplicate deltas")

[Jilles Tjoelker]

On Wed, May 12, 2010 at 05:14:14PM -0400, Greg Ward wrote:
>   http://www.gerg.ca/dupdelta-anim.odp  (OpenOffice 3)
>   http://www.gerg.ca/dupdelta-anim.pdf  (any PDF viewer)

> If you step through those slides, you'll see Alice and Bob gradually
> build up that hairy graph.

> Now, the problem: Carl doesn't know anything about Bob's code.  He
> doesn't have a clue how to resolve the conflict.  If he tries, he'll
> probably get it wrong.  And besides, Bob *already* resolved the conflict
> once; why should Carl have to do it again?

> (And the bigger problem: what if Bob didn't have a conflict, but instead
> dummy-merged his fix from 1.0 to 1.1: that is, Bob's change to 1.0 is a
> nasty hack that is a special case for the single customer still running
> 1.0.  Bob doesn't want this hack leaking onto other branches, so he
> prevents Mercurial from merging it forward by doing a dummy merge from
> 1.0 to 1.1.  Then Carl comes along and inadvertently applies Bob's nasty
> hack to 1.1 through the side door.  Yuck!)

> Here is a naive explanation of the problem, using revision numbers from
> the slides (sorry, I don't know how else to explain this without
> referencing the pretty pictures):

> Notation: let d(n,m) be the delta from rev n to m, i.e. the patch that
> "hg diff -r n:m" produces.  For example, Alice's original fix on branch
> 1.0 is d(1,4).  Since Alice had no conflict merging to 1.1 or default,
> her patch looks the same in all three branches: d(1,4) == d(3,5) ==
> d(2,6).  But Bob had a conflict merging 1.0 to 1.1, so d(1,7) != d(3,8)
> -- even though the patch has the same effect, it's textually different.

> Now look at slide 11, where Carl is trying to merge branch 1.0 (rev 10)
> to branch 1.1 (rev 11).  d(4,10) duplicates Bob's patch on branch 1.0,
> just as d(7,10) duplicates Alice's patch on the same branch.
> I.e. d(4,10) == d(1,7) and d(7,10) == d(1,4).  That's why we've taken to
> calling this the "duplicate delta" problem.

> But recall that Bob got a conflict merging to 1.1, i.e. his original
> patch d(1,7) does not apply cleanly on 1.1.  So why should d(4,10) apply
> cleanly?  In fact, it does not: Carl gets the same conflict merging rev
> 10 to 11 that Bob got merging rev 7 to 3.

> Of course, we all know that Mercurial doesn't do merges by applying
> patches.  If it did, the above would be a good explanation, but that's
> just not the way things are.  Rather, Mercurial does file merges by
> digging through history looking for the common ancestor and passing all
> three file revisions (local, other, base) to the relevant merge tool.
> >From Carl's perspective, though, it doesn't really matter.  He's still
> stuck with a conflict that 1) he doesn't know how to resolve and 2) has
> already been resolved anyways.

The problem is that there are two common ancestors (4 and 7).

This seems to match what's in the git documentation about their
"recursive" merge strategy (git help merge): it merges the common
ancestors to create the reference for the actual merge. In this
particular case, that's easy as the merge of 4 and 7 is 10, and
therefore the result of the merge is identical to 11.

Things will be more complicated when for example 4 was modified by
another changeset, say 4*, before being merged with 7. Then it may be
harder to get a good reference for the merge. Trying to merge 4 and 7
could give conflicts then, making the recursive approach not useful.

That problem could be solved manually, by first merging 4* with 11,
giving 11*, then merging 10 with 11* which has 10 as its reference
following the recursive algorithm.

> Thoughts?  I'm still trying to figure out if this is a bug in Mercurial,
> a feature request for Mercurial ("handle this case better!"), or a flaw
> in our workflow.  I'm pretty sure we could avoid it much of the time
> with rebase, but that won't always work.  (We have multi-level workflow,
> and obviously you should not rebase changesets that you have already
> pushed.)

Probably a feature request, although the problem is also caused by the
workflow.

-- 
Jilles Tjoelker