Recursive merge strategy
Michał Sznajder
in situation when
merge has two "common" ancestors (also know as criss-cross merge)
According to http://codicesoftware.blogspot.com/2011/09/merge-recursive-strategy.html
Mercurial
does not support it but I wanted to ask to make sure that nothing has changed.
Michal Sznajder
_______________________________________________
Mercurial mailing list
Merc...@selenic.com
http://selenic.com/mailman/listinfo/mercurial
Matt Mackall
> Does Mercurial supports recursive merge strategy like git? It is used
> in situation when
> merge has two "common" ancestors (also know as criss-cross merge)
>
> According to http://codicesoftware.blogspot.com/2011/09/merge-recursive-strategy.html
> Mercurial
> does not support it but I wanted to ask to make sure that nothing has changed.
Indeed. But you shouldn't judge the situation from this blog post as
it's not coherent.
In particular, the example given under "Why merge recursive is better –
a step by step example" doesn't appear to be a recursive merge situation
at all! Notice the key difference in topology as compared with the
initial diagrams: no criss-crossing merges leading up to the merge. Some
kind of bait and switch happening here.
In the example itself, Git will choose the same (single) ancestor in a
merge between nodes 5 and 4 as Mercurial would, 0. And thus both give
the result 'bcdE'. So we've learned precisely nothing about recursive
merge and how it compares to Mercurial from this example. The claim that
Mercurial chooses the "deepest" ancestor: also wrong and nonsensical.
The deepest ancestor is the root.
This seems to be yet another instance of "Git is incomprehensible,
therefore Git is magic, therefore Git magically works better" logic at
work.
Let's _actually_ work his original example diagram which has the
criss-crossing merges (which I guess he copied from someone who knew
what they were talking about). I'm going to ignore the blogger's
nonsensical use of arrows that point the wrong way for branch merges and
thus add cycles into the "directed acyclic graph". Here history flows
from left to right, thus the edges are right to left:
a---b-d-f---?
\ \ / /
\ X /
\ / \ /
c-e-g
Let's make up a simple set of changes to go with that picture. Again,
think of each character as a line:
a = "a"
b = "a1"
c = "1a"
d = "a2"
e = "2a"
f = merge of d and c = "1a2"
g = merge of e and b = "2a1"
When we merge f and g, our greatest common ancestor is either b or c. So
we've got the following cases:
b: we had a1 originally, and are looking at 1a2 and 2a1. So we have a
conflict at the start, but can simply choose 2 for the end as only one
side touched the end.
c: we had 1a originally, and are looking at 1a2 and 2a1. So we have a
conflict at the end, but can simply choose 2 for the start as only one
side touched the start.
Mercurial will choose whichever one of these it finds first, so we have
one conflict to resolve. It definitely does not choose 'a' as the
ancestor, which would give two conflicts.
Now what a recursive merge would do would be merging b and c first,
giving us "1a1". So now when we merge, we don't have conflicts at the
front or the back.
So yay, in this simplest of examples, it's a win. But cases where this
actually matters aren't terribly common (let's call it 1% to be
generous) and cases where it actually automatically solves the problem
for you seamlessly are actually less than half of THOSE cases.
Instead, if you've got conflicts in your recursive merge, now you've
made the whole situation more confusing. Take your blog post as Exhibit
A that most people don't understand recursive merge at all which means
when a merge goes wrong, not only do you need an expert to diagnose it,
you need an expert to tell you who the 'experts' even are.
We talk about recursive merge occasionally. But as it happens, for the
cases where ancestor ambiguity is the most interesting (merging with
backouts, exec bit changes), recursive merges don't help at all. So I
don't think they warrant the extra complexity.
--
Mathematics is the supreme nostalgia of our time.
Gour
Matt Mackall <m...@selenic.com> wrote:
Hello Matt,
> This seems to be yet another instance of "Git is incomprehensible,
> therefore Git is magic, therefore Git magically works better" logic at
> work.
Few days ago I was considering to take a closer look at Git seeing that
many projects I'm interested are heading towards Github...
However, after starting reading Pro Git book and some of the design
choices in Git (mostly how much info is leaking to the poor end-user), I
quit with reading soon being thankful to you for providing Mercurial
which is human-friendly DVCS and have started re-reading Hg book in
order to learn more and master Mercurial properly.
Sincerely,
Gour
--
In the material world, one who is unaffected by whatever good
or evil he may obtain, neither praising it nor despising it,
is firmly fixed in perfect knowledge.
http://atmarama.net | Hlapicina (Croatia) | GPG: 52B5C810
Martin Geisler
> On Mon, 2012-01-16 at 10:30 +0100, Michał Sznajder wrote:
>> Does Mercurial supports recursive merge strategy like git? It is used
>> in situation when merge has two "common" ancestors (also know as
>> criss-cross merge)
>>
>> According to
>> http://codicesoftware.blogspot.com/2011/09/merge-recursive-strategy.html
>> Mercurial does not support it but I wanted to ask to make sure that
>> nothing has changed.
>
> Indeed. But you shouldn't judge the situation from this blog post as
> it's not coherent.
Thanks for debunking this. I've added a comment with link back to your
mail. It's currently in moderation... but I hope the author will let it
go through.
--
Martin Geisler
Mercurial links: http://mercurial.ch/
psantosl
> > Indeed. But you shouldn't judge the situation from this blog post as
> > it's not coherent.
>
> Thanks for debunking this. I've added a comment with link back to your
> mail. It's currently in moderation... but I hope the author will let it
> go through.
Yes, it is already published.
I'm the author of the blog post and co-founder at Plastic SCM
(www.plasticscm.com), and happy to discuss about the recursive merge
implementation.
I'll clarify the nonsense comments first, and later I'll discuss the
technical details, ok?
Let's go:
> This seems to be yet another instance of "Git is incomprehensible,
> therefore Git is magic, therefore Git magically works better" logic at
> work.
Funny comment, but unfortunately you're wrong: we've implemented our
own 'recursive merge' so I'm afraid "magic and incomprehensible" is
not an option. I wrote this blog post trying to share what we learnt
while implementing our new merge system in plastic 4.0.
> Let's _actually_ work his original example diagram which has the
> criss-crossing merges (which I guess he copied from someone who knew
> what they were talking about).
Thanks!
> I'm going to ignore the blogger's nonsensical use of arrows that
> point the wrong way for branch merges and thus add cycles into
> the "directed acyclic graph".
We render arrows to 'parent changesets' but we also render (and
track!) merge-links separately. We always rendered merges in "source
to destination" direction, and we keep the same style in our newest
release, and that's why I keep drawing them this way. It is a matter
of preference but I simply find "merge arrows" simpler to understand
when they go from "merge source" to "merge destination". That's all.
Saying they're "nonsensical" and "point to the wrong direction"
doesn't give you a better position to talk about SCM, I'm afraid.
That being said, if it is fine for you, I'll come back with a in-depth
explanation about the merge algorithm itself.
Regards,
Pablo Santos
www.plasticscm.com
Matt Mackall
> Hi,
>
> > > Indeed. But you shouldn't judge the situation from this blog post as
> > > it's not coherent.
> >
> > Thanks for debunking this. I've added a comment with link back to your
> > mail. It's currently in moderation... but I hope the author will let it
> > go through.
>
> Yes, it is already published.
>
> I'm the author of the blog post and co-founder at Plastic SCM
> (www.plasticscm.com), and happy to discuss about the recursive merge
> implementation.
>
> I'll clarify the nonsense comments first, and later I'll discuss the
> technical details, ok?
>
> Let's go:
>
> > This seems to be yet another instance of "Git is incomprehensible,
> > therefore Git is magic, therefore Git magically works better" logic at
> > work.
>
> Funny comment, but unfortunately you're wrong: we've implemented our
> own 'recursive merge' so I'm afraid "magic and incomprehensible" is
> not an option. I wrote this blog post trying to share what we learnt
> while implementing our new merge system in plastic 4.0.
I see. I assumed PlasticSCM was some sort of Git wrapper, since the just
about the whole post is talking about Git (and I've never heard of it
before).
> > Let's _actually_ work his original example diagram which has the
> > criss-crossing merges (which I guess he copied from someone who knew
> > what they were talking about).
>
> Thanks!
>
> > I'm going to ignore the blogger's nonsensical use of arrows that
> > point the wrong way for branch merges and thus add cycles into
> > the "directed acyclic graph".
>
> We render arrows to 'parent changesets' but we also render (and
> track!) merge-links separately. We always rendered merges in "source
> to destination" direction, and we keep the same style in our newest
> release, and that's why I keep drawing them this way. It is a matter
> of preference but I simply find "merge arrows" simpler to understand
> when they go from "merge source" to "merge destination". That's all.
> Saying they're "nonsensical" and "point to the wrong direction"
> doesn't give you a better position to talk about SCM, I'm afraid.
Use a different color for merges, sure. But history in Git and Mercurial
are DAGs. DAG stands for DIRECTED acyclic graph. Pointing the arrows
the wrong way makes you look clueless and makes your graph appear to
contain cycles by all the long-established conventions of graph theory.
If you want to look clueless, fine by me.
> That being said, if it is fine for you, I'll come back with a in-depth
> explanation about the merge algorithm itself.
Why don't you start by correcting your blog post to actually work an
example that actually requires a recursive merge (preferably by not
switching examples in the middle of the post) and then -actually test it
in Mercurial- before claiming "Hg will break the result". I'll be happy
to fact-check your rewrite.
--
Mathematics is the supreme nostalgia of our time.
pablosantosluaces
I see. I assumed PlasticSCM was some sort of Git wrapper, since the just
about the whole post is talking about Git (and I've never heard of it
before).
> We render arrows to 'parent changesets' but we also render (and
> track!) merge-links separately. We always rendered merges in "source
> to destination" direction, and we keep the same style in our newest
> release, and that's why I keep drawing them this way. It is a matter
> of preference but I simply find "merge arrows" simpler to understand
> when they go from "merge source" to "merge destination". That's all.
> Saying they're "nonsensical" and "point to the wrong direction"
> doesn't give you a better position to talk about SCM, I'm afraid.
Use a different color for merges, sure. But history in Git and Mercurial
are DAGs. DAG stands for DIRECTED acyclic graph. Pointing the arrows
the wrong way makes you look clueless and makes your graph appear to
contain cycles by all the long-established conventions of graph theory.
If you want to look clueless, fine by me.
> That being said, if it is fine for you, I'll come back with a in-depth
> explanation about the merge algorithm itself.
Why don't you start by correcting your blog post to actually work an
example that actually requires a recursive merge (preferably by not
switching examples in the middle of the post) and then -actually test it
in Mercurial- before claiming "Hg will break the result". I'll be happy
to fact-check your rewrite.
psantosl
I added another small example: http://codicesoftware.blogspot.com/2012/01/more-on-recursive-merge-strategy.html
Matt, the recursive merge strategy is not only useful in criss-cross
merging, we came up with this example because it *does* use recursive.
Regarding your previous notes:
> The claim that Mercurial chooses
> the "deepest" ancestor: also wrong and nonsensical.
> The deepest ancestor is the root.
In Plastic we measure "depth" from the root of the tree.
Maybe you measure "depth" from the "head" instead.
Just a naming convention difference.
Regards,
pablo
Matt Mackall
> Hi again,
>
> I added another small example: http://codicesoftware.blogspot.com/2012/01/more-on-recursive-merge-strategy.html
>
> Matt, the recursive merge strategy is not only useful in criss-cross
> merging, we came up with this example because it *does* use recursive.
I see. I have in fact read your example wrong. Please add edges to the
graph representing the merge in question. Let me redraw your example
graph:
0-2-5------7
\ \ /
1 3-6 /
\ / /
4--'
At this point, I've read the whole thing as being about cset 7 because
(a) that's how you diagrammed it in your intro example (right-most node
was the merge in question) and (b) the whole description about the merge
is under bullet point 7, presumably corresponding with cset 7 and (c)
weird non-DAG-like arrows.
But if you add the actual merge in question into the graph:
0-2-5------7
\ \ / \
1 3-6--/---?
\ / /
4--'
...we can reshape this into the immediately recognizable criss-cross
shape from your original example thusly:
2-5-7
/ 3 / \
0 X ?
1 / \ /
4---6
(It is in fact impossible to draw this graph without crossing edges in
two dimensions while still preserving left-to-right partial ordering.)
--
Mathematics is the supreme nostalgia of our time.