Patchwork [6,of,6,bid,merge,v2,RFC] merge: take bids for merge actions for different ancestors and pick the best

login
register
mail settings
Submitter Mads Kiilerich
Date April 7, 2014, 12:19 a.m.
Message ID <29b10f9b64e6efc8830f.1396829942@localhost.localdomain>
Download mbox | patch
Permalink /patch/4240/
State Deferred
Headers show

Comments

Mads Kiilerich - April 7, 2014, 12:19 a.m.
# HG changeset patch
# User Mads Kiilerich <madski@unity3d.com>
# Date 1393728157 -3600
#      Sun Mar 02 03:42:37 2014 +0100
# Node ID 29b10f9b64e6efc8830fd68b2bf3f32d1f64e472
# Parent  b8eaf05d1ce2dcacbfcf0168053568cd539f561c
[RFC] merge: take bids for merge actions for different ancestors and pick the best

The basic idea is to do the merge planning with all the available ancestors,
consider the resulting actions as "bids" and make an "auction" and
automatically pick the most favourable action for each file.

This just implements the basic functionality and do just consider "keep" and
"get" actions. The heuristics for picking the best action can be tweaked later
on.

The code path for merging with a single ancestor is not changed. Only the
special case that can benefit from it will collect bids and make an auction.
Mads Kiilerich - April 7, 2014, 12:20 a.m.
Most of the necessary preliminary refactorings from 
http://markmail.org/message/r2lifdz5m5e5ynw7 have now been merged. I 
have updated the remaining patches and will add some comments to 
supplement the discussion of the patch actually implementing "bid merge".

What I call "Bid merge" is inspired by "Consensus merge" 
http://mercurial.selenic.com/wiki/ConsensusMerge . It might essentially 
be the same but it also seems to be different in some essential ways - 
for a starter, I think it has nothing to do with "consensus". I hope the 
approaches can be merged and parts of this text can be used on the wiki. 
For now I will keep the concepts separate to avoid confusion.

No matter the name, the whole point for this multiple ancestor merge is 
to make a clever choice of merge strategy that takes all the ancestors 
into account. Refactorings have made the actions returned from 
manifestmerge more self-contained and we are getting to the point where 
we have all the information in the right place in calculateupdates for 
making an informed decision.

We assume that the definition of Mercurial manifest merge will make sure 
that exactly the same files will be produced, no matter which ancestor 
is used. That assumption might be wrong in very rare cases that really 
not is a problem.

For the actual algorithm for merging manifest merges using multiple 
ancestors:

If there is consensus from all the ancestors then there is no doubt what 
to do. A clever result will be indistinguishable from just picking a 
random bid. The consensus case is thus not only trivial, it is also 
already handled perfectly.

The most obvious advantage of considering multiple ancestors is the case 
where some of the bids for a file is a "real" (interactive) merge but 
where one or more bids just take on of the parent revisions. That would 
be the case where merging with one of the ancestors gave one side 
without changes (and where merging with other ancestors would give a 
file merge with pretty much the same change on both sides). Nothing can 
possibly be better than just taking one of the parents.

"Keep local and do nothing" used to be an implicit action. One remaining 
refactoring will introduce an action for this. The "auction" for merging 
the bids just have to prefer the "keep" and "get from other" actions 
without considering what other actions could be available.

Some observations:

Experience with bid merge shows that many merges that actually have a 
very simple solution (because only one side changed) only can be solved 
efficiently when we start looking at file content in filemerge ... and 
it thus also requires all ancestors passed to filemerge. That is because 
Mercurial includes the history in filelog hashes. A file with changes 
that ends up not changing the content (could be change + backout or 
graft + merge or criss cross merges) still shows up as a changed file to 
manifestmerge. (The git data model has an advantage here when it uses 
pure content hashes.) One way to handle that would be to refactor 
manifestmerge, resolve and filemerge so they become more of the same thing.

There is also cases where different conflicting chunks could benefit 
from using multiple ancestors in filemerge - but that will require merge 
tools with fancy support for switching ancestor in 3-way merge. That is 
left as an exercise for another day. That seems to be a case where 
"recursive merge" has an advantage.

The current manifest merge actions are very low level imperative and not 
symmetrical. They do not only describe how two manifests should be 
merged, they also describe a strategy for changing a context from a 
state where it is one of the parents to the state where it is the result 
of the merge with the other parent. I can imagine that manifestmerge 
could be simplified (and made more suitable for in memory merges) by 
separating the abstract merge actions from the actual file system 
operation actions. A more clever wcontext could perhaps also take care 
of some of the branchmerge special cases.

/Mads
Mads Kiilerich - April 21, 2014, 11:40 a.m.
On 04/07/2014 02:20 AM, Mads Kiilerich wrote:
> Most of the necessary preliminary refactorings from 
> http://markmail.org/message/r2lifdz5m5e5ynw7 have now been merged. I 
> have updated the remaining patches and will add some comments to 
> supplement the discussion of the patch actually implementing "bid merge".

This has been merged for 3.0.

Bid merge is enabled by setting the configuration value 
"merge.preferancestor=*". With this setting, Mercurial will perform a 
bid merge in the cases where a merge otherwise would emit a 
"note: using X as ancestor of X and X" message.

See http://mercurial.selenic.com/wiki/BidMerge for an updated online 
description of what it is.

/Mads


>
> What I call "Bid merge" is inspired by "Consensus merge" 
> http://mercurial.selenic.com/wiki/ConsensusMerge . It might 
> essentially be the same but it also seems to be different in some 
> essential ways - for a starter, I think it has nothing to do with 
> "consensus". I hope the approaches can be merged and parts of this 
> text can be used on the wiki. For now I will keep the concepts 
> separate to avoid confusion.
>
> No matter the name, the whole point for this multiple ancestor merge 
> is to make a clever choice of merge strategy that takes all the 
> ancestors into account. Refactorings have made the actions returned 
> from manifestmerge more self-contained and we are getting to the point 
> where we have all the information in the right place in 
> calculateupdates for making an informed decision.
>
> We assume that the definition of Mercurial manifest merge will make 
> sure that exactly the same files will be produced, no matter which 
> ancestor is used. That assumption might be wrong in very rare cases 
> that really not is a problem.
>
> For the actual algorithm for merging manifest merges using multiple 
> ancestors:
>
> If there is consensus from all the ancestors then there is no doubt 
> what to do. A clever result will be indistinguishable from just 
> picking a random bid. The consensus case is thus not only trivial, it 
> is also already handled perfectly.
>
> The most obvious advantage of considering multiple ancestors is the 
> case where some of the bids for a file is a "real" (interactive) merge 
> but where one or more bids just take on of the parent revisions. That 
> would be the case where merging with one of the ancestors gave one 
> side without changes (and where merging with other ancestors would 
> give a file merge with pretty much the same change on both sides). 
> Nothing can possibly be better than just taking one of the parents.
>
> "Keep local and do nothing" used to be an implicit action. One 
> remaining refactoring will introduce an action for this. The "auction" 
> for merging the bids just have to prefer the "keep" and "get from 
> other" actions without considering what other actions could be available.
>
> Some observations:
>
> Experience with bid merge shows that many merges that actually have a 
> very simple solution (because only one side changed) only can be 
> solved efficiently when we start looking at file content in filemerge 
> ... and it thus also requires all ancestors passed to filemerge. That 
> is because Mercurial includes the history in filelog hashes. A file 
> with changes that ends up not changing the content (could be change + 
> backout or graft + merge or criss cross merges) still shows up as a 
> changed file to manifestmerge. (The git data model has an advantage 
> here when it uses pure content hashes.) One way to handle that would 
> be to refactor manifestmerge, resolve and filemerge so they become 
> more of the same thing.
>
> There is also cases where different conflicting chunks could benefit 
> from using multiple ancestors in filemerge - but that will require 
> merge tools with fancy support for switching ancestor in 3-way merge. 
> That is left as an exercise for another day. That seems to be a case 
> where "recursive merge" has an advantage.
>
> The current manifest merge actions are very low level imperative and 
> not symmetrical. They do not only describe how two manifests should be 
> merged, they also describe a strategy for changing a context from a 
> state where it is one of the parents to the state where it is the 
> result of the merge with the other parent. I can imagine that 
> manifestmerge could be simplified (and made more suitable for in 
> memory merges) by separating the abstract merge actions from the 
> actual file system operation actions. A more clever wcontext could 
> perhaps also take care of some of the branchmerge special cases.
>
> /Mads
Martin Geisler - April 21, 2014, 1:28 p.m.
Mads Kiilerich <mads@kiilerich.com> writes:

> On 04/07/2014 02:20 AM, Mads Kiilerich wrote:
>> Most of the necessary preliminary refactorings from
>> http://markmail.org/message/r2lifdz5m5e5ynw7 have now been merged. I
>> have updated the remaining patches and will add some comments to
>> supplement the discussion of the patch actually implementing "bid
>> merge".
>
> This has been merged for 3.0.
>
> Bid merge is enabled by setting the configuration value
> "merge.preferancestor=*". With this setting, Mercurial will perform a
> bid merge in the cases where a merge otherwise would emit a "note:
> using X as ancestor of X and X" message.
>
> See http://mercurial.selenic.com/wiki/BidMerge for an updated online
> description of what it is.

Very nice! This makes my answer here obsolete in Mercurial 3.0:

  http://stackoverflow.com/a/9430810/110204

There I create a criss-cross merge situation and show that picking
different ancestors can give different merge results -- with no
conflicts involved.


By the way, I think the message format is a little verbose and unusual
here:

  $ hg merge
  note: using eb49ad46fd72 as ancestor of 333411d2f751 and 7d1f71140c74
        alternatively, use --config merge.preferancestor=fdf4b78f5292
  merging x
  0 files updated, 1 files merged, 0 files removed, 0 files unresolved
  (branch merge, don't forget to commit)

The hanging indentation looks unusual to my eyes. The hint is repeated
if there are multiple alternative ancestors and I think that looks even
more funny:

  $ hg merge
  note: using eb49ad46fd72 as ancestor of 333411d2f751 and 7d1f71140c74
        alternatively, use --config merge.preferancestor=fdf4b78f5292
        alternatively, use --config merge.preferancestor=30c60e28aa9b
        alternatively, use --config merge.preferancestor=a63958bcf63a
  merging x
  0 files updated, 1 files merged, 0 files removed, 0 files unresolved
  (branch merge, don't forget to commit)

For a single alternative, I would suggest using the normal hint style:

  $ hg merge
  note: using eb49ad46fd72 as ancestor of 333411d2f751 and 7d1f71140c74
  (alternatively, use --config merge.preferancestor=fdf4b78f5292)
  merging x

When there are multiple alternatives, I will argue that listing them
isn't super helpful: I think the kind of user who want this information
and who will know what to do with it will want to inspect the ancestors
before proceeding.

So my suggestion would be to instead include the log command needed to
see the ancestors. Something like:

  $ hg merge
  note: using eb49ad46fd72 as ancestor of 333411d2f751 and 7d1f71140c74
  (use 'hg log -r "heads(::333411d2f751 and ::7d1f71140c74)"' to see them all)
  merging x
  0 files updated, 1 files merged, 0 files removed, 0 files unresolved
  (branch merge, don't forget to commit)

That's still a bit long and unhelpful -- people would still need to know
why they might want to pick another merge base. Maybe an even better
idea would be to refer people to a help topic. We could add a verbose
section to 'hg help merge' that describes this, for example.

I think the feature is undocumented right now -- I can add a paragraph
to 'hg help merge' and config.txt if people like that idea?
Mads Kiilerich - April 21, 2014, 3:27 p.m.
On 04/21/2014 03:28 PM, Martin Geisler wrote:
> Mads Kiilerich <mads@kiilerich.com> writes:
>> This has been merged for 3.0.
>>
>> Bid merge is enabled by setting the configuration value
>> "merge.preferancestor=*". With this setting, Mercurial will perform a
>> bid merge in the cases where a merge otherwise would emit a "note:
>> using X as ancestor of X and X" message.
>>
>> See http://mercurial.selenic.com/wiki/BidMerge for an updated online
>> description of what it is.
> Very nice! This makes my answer here obsolete in Mercurial 3.0:
>
>    http://stackoverflow.com/a/9430810/110204

Yes - I implemented it because that dude and his co-workers need it ;-)

For the record: The things you point out here is for user controlled 
manual ancestor selection. Bid merge is about automatically using all of 
them.

How can we make bid merge work better for the case you give?

> By the way, I think the message format is a little verbose and unusual
> here:
>
>    $ hg merge
>    note: using eb49ad46fd72 as ancestor of 333411d2f751 and 7d1f71140c74
>          alternatively, use --config merge.preferancestor=fdf4b78f5292
>    merging x
>    0 files updated, 1 files merged, 0 files removed, 0 files unresolved
>    (branch merge, don't forget to commit)
>
> The hanging indentation looks unusual to my eyes. The hint is repeated
> if there are multiple alternative ancestors and I think that looks even
> more funny:
>
>    $ hg merge
>    note: using eb49ad46fd72 as ancestor of 333411d2f751 and 7d1f71140c74
>          alternatively, use --config merge.preferancestor=fdf4b78f5292
>          alternatively, use --config merge.preferancestor=30c60e28aa9b
>          alternatively, use --config merge.preferancestor=a63958bcf63a
>    merging x
>    0 files updated, 1 files merged, 0 files removed, 0 files unresolved
>    (branch merge, don't forget to commit)

We did a bit of bike shedding. It can probably take another layer of 
paint - feel free to propose a patch ;-)

I used the unusual indentation to make it more clear that it was a 
single multi line note, not a part of the progress info shown on the 
following lines.

> For a single alternative, I would suggest using the normal hint style:
>
>    $ hg merge
>    note: using eb49ad46fd72 as ancestor of 333411d2f751 and 7d1f71140c74
>    (alternatively, use --config merge.preferancestor=fdf4b78f5292)
>    merging x

Are hints normal for notes (which in this case actually is a status 
message)?

> When there are multiple alternatives, I will argue that listing them
> isn't super helpful: I think the kind of user who want this information
> and who will know what to do with it will want to inspect the ancestors
> before proceeding.

I disagree. The kind of user who need it is the ordinary user who for 
some reason ends up in an unfortunate situation. It might even more 
often be the more novice users who have a messy history and don't know 
how to use version control efficiently.

> So my suggestion would be to instead include the log command needed to
> see the ancestors. Something like:
>
>    $ hg merge
>    note: using eb49ad46fd72 as ancestor of 333411d2f751 and 7d1f71140c74
>    (use 'hg log -r "heads(::333411d2f751 and ::7d1f71140c74)"' to see them all)
>    merging x
>    0 files updated, 1 files merged, 0 files removed, 0 files unresolved
>    (branch merge, don't forget to commit)

Why should we show a scary revset to the user and ask him to run it? Why 
not just run it and give the user the info he can use?

 >2 ancestors will happen more rarely than 2 ancestors. I think it is 
important that they use the same message and don't look like something 
different. I do not think it matters that the message looks a bit 
inelegant and funny if just it is clear. I would suggest just repeating 
the "(alternatively, ...)" messages.

> That's still a bit long and unhelpful -- people would still need to know
> why they might want to pick another merge base. Maybe an even better
> idea would be to refer people to a help topic. We could add a verbose
> section to 'hg help merge' that describes this, for example.
>
> I think the feature is undocumented right now -- I can add a paragraph
> to 'hg help merge' and config.txt if people like that idea?

Thanks, that could perhaps be helpful.

Users should however never add it to their hgrc so describing it in 
config.txt could be misleading.

The option should only be used after an ordinary merge has shown the 
ambiguity and suggested some values. Most users will probably never see 
it. It should thus not take too much attention for people reading the help.

Note: Bid merge has not seen a lot of testing and feedback. It could be 
considered kind of experimental and is so far not documented.

/Mads
Martin Geisler - April 22, 2014, 8:05 a.m.
Mads Kiilerich <mads@kiilerich.com> writes:

> On 04/21/2014 03:28 PM, Martin Geisler wrote:
>> Mads Kiilerich <mads@kiilerich.com> writes:
>>> This has been merged for 3.0.
>>>
>>> Bid merge is enabled by setting the configuration value
>>> "merge.preferancestor=*". With this setting, Mercurial will perform a
>>> bid merge in the cases where a merge otherwise would emit a "note:
>>> using X as ancestor of X and X" message.
>>>
>>> See http://mercurial.selenic.com/wiki/BidMerge for an updated online
>>> description of what it is.
>> Very nice! This makes my answer here obsolete in Mercurial 3.0:
>>
>>    http://stackoverflow.com/a/9430810/110204
>
> Yes - I implemented it because that dude and his co-workers need it ;-)

You're awesome! :)

> For the record: The things you point out here is for user controlled
> manual ancestor selection. Bid merge is about automatically using all
> of them.

I see how bid merge is a superset of the functionality in the little
extension I wrote the answer.

> How can we make bid merge work better for the case you give?

I think it's pretty good -- adding a real --ancestor command line flag
to merge would make it a little easier to discover this feature. But I
take it that you want to keep this feature a little under the radar for
now.

>>    $ hg merge
>>    note: using eb49ad46fd72 as ancestor of 333411d2f751 and 7d1f71140c74
>>          alternatively, use --config merge.preferancestor=fdf4b78f5292
>>          alternatively, use --config merge.preferancestor=30c60e28aa9b
>>          alternatively, use --config merge.preferancestor=a63958bcf63a
>>    merging x
>>    0 files updated, 1 files merged, 0 files removed, 0 files unresolved
>>    (branch merge, don't forget to commit)
>
> We did a bit of bike shedding. It can probably take another layer of
> paint - feel free to propose a patch ;-)
>
> I used the unusual indentation to make it more clear that it was a
> single multi line note, not a part of the progress info shown on the
> following lines.

Yes, that does make some sense :) You basically have a multi-line note
where the second and following lines are optional. From a translation
point of view that's not optimal: translators love to get full sentences
with full context.

>> For a single alternative, I would suggest using the normal hint style:
>>
>>    $ hg merge
>>    note: using eb49ad46fd72 as ancestor of 333411d2f751 and 7d1f71140c74
>>    (alternatively, use --config merge.preferancestor=fdf4b78f5292)
>>    merging x
>
> Are hints normal for notes (which in this case actually is a status
> message)?

No, they're actually not normal... we only have hints when we abort the
execution by raising util.Abort.

>> When there are multiple alternatives, I will argue that listing them
>> isn't super helpful: I think the kind of user who want this
>> information and who will know what to do with it will want to inspect
>> the ancestors before proceeding.
>
> I disagree. The kind of user who need it is the ordinary user who for
> some reason ends up in an unfortunate situation. It might even more
> often be the more novice users who have a messy history and don't know
> how to use version control efficiently.

It's just a guess, but I think these messages will confuse many users.
We're both power users and I don't know how I should react to these
messages -- why would I want to pick one over the other ancestor? Can I
somehow evaluate the quality of the ancestors?

>> So my suggestion would be to instead include the log command needed
>> to see the ancestors. Something like:
>>
>>    $ hg merge
>>    note: using eb49ad46fd72 as ancestor of 333411d2f751 and 7d1f71140c74
>>    (use 'hg log -r "heads(::333411d2f751 and ::7d1f71140c74)"' to
>> see them all)
>>    merging x
>>    0 files updated, 1 files merged, 0 files removed, 0 files unresolved
>>    (branch merge, don't forget to commit)
>
> Why should we show a scary revset to the user and ask him to run it?
> Why not just run it and give the user the info he can use?

Because I feel that we don't know what information the users really
needs. Listing the changeset IDs is not enough for me to decide which
ancestor to use -- I think I'll need to go lookup the ancestors somehow?

Maybe I'm wrong, maybe you expect users to retry the merge with the
other ancestor and see what happens?

As a curious users, I would probably do that. In that case, it would be
helpful if Mercurial could already tell me if the merge result would
differ depending on which ancestor I pick. In my criss-cross merge
example above, the merge result was different depending on the ancestor
chosen -- that's important information.

> 2 ancestors will happen more rarely than 2 ancestors. I think it is
> important that they use the same message and don't look like something
> different. I do not think it matters that the message looks a bit
> inelegant and funny if just it is clear. I would suggest just
> repeating the "(alternatively, ...)" messages.

You're right that this case wont be so common.

>> That's still a bit long and unhelpful -- people would still need to
>> know why they might want to pick another merge base. Maybe an even
>> better idea would be to refer people to a help topic. We could add a
>> verbose section to 'hg help merge' that describes this, for example.
>>
>> I think the feature is undocumented right now -- I can add a
>> paragraph to 'hg help merge' and config.txt if people like that idea?
>
> Thanks, that could perhaps be helpful.
>
> Users should however never add it to their hgrc so describing it in
> config.txt could be misleading.
>
> The option should only be used after an ordinary merge has shown the
> ambiguity and suggested some values. Most users will probably never
> see it. It should thus not take too much attention for people reading
> the help.

So maybe a verbose section in 'hg help merge' is better. I would then
prefer a hint-like message of the form

  $ hg merge
  note: using eb49ad46fd72 as ancestor of 333411d2f751 and 7d1f71140c74
  (alternatives: fdf4b78f5292, 30c60e28aa9b, see 'hg help -v merge')

> Note: Bid merge has not seen a lot of testing and feedback. It could
> be considered kind of experimental and is so far not documented.

Yeah, the full power of this is still experimental. But I think the
notes (potentally) printed by 'hg merge' make the feature quite public.
That means that we should come up with some documentation.
Mads Kiilerich - April 22, 2014, 2:02 p.m.
On 04/22/2014 10:05 AM, Martin Geisler wrote:
>> How can we make bid merge work better for the case you give?
> I think it's pretty good -- adding a real --ancestor command line flag
> to merge would make it a little easier to discover this feature. But I
> take it that you want to keep this feature a little under the radar for
> now.

Yes. But it should also add it to graft and rebase and update and 
backout ... and everything that uses revsets.

>>> When there are multiple alternatives, I will argue that listing them
>>> isn't super helpful: I think the kind of user who want this
>>> information and who will know what to do with it will want to inspect
>>> the ancestors before proceeding.
>> I disagree. The kind of user who need it is the ordinary user who for
>> some reason ends up in an unfortunate situation. It might even more
>> often be the more novice users who have a messy history and don't know
>> how to use version control efficiently.
> It's just a guess, but I think these messages will confuse many users.

I think it primarily will make the user wonder. The user will be alert 
and think about what is going on ... and hopefully deal with it, no 
matter if he has full or limited understanding of the situation.

I will reserve the word "confuse" to situations where the tool gives 
vague or misleading hints without helping the user to understand or deal 
with the situation.

> We're both power users and I don't know how I should react to these
> messages -- why would I want to pick one over the other ancestor? Can I
> somehow evaluate the quality of the ancestors?

I don't think we can say anything beyond "you can try the alternative, 
and if you like that better, use it".

>
>>> So my suggestion would be to instead include the log command needed
>>> to see the ancestors. Something like:
>>>
>>>     $ hg merge
>>>     note: using eb49ad46fd72 as ancestor of 333411d2f751 and 7d1f71140c74
>>>     (use 'hg log -r "heads(::333411d2f751 and ::7d1f71140c74)"' to
>>> see them all)
>>>     merging x
>>>     0 files updated, 1 files merged, 0 files removed, 0 files unresolved
>>>     (branch merge, don't forget to commit)
>> Why should we show a scary revset to the user and ask him to run it?
>> Why not just run it and give the user the info he can use?
> Because I feel that we don't know what information the users really
> needs. Listing the changeset IDs is not enough for me to decide which
> ancestor to use -- I think I'll need to go lookup the ancestors somehow?

The only way you can decide is to try them (which pretty much is what 
bid merge do). All the info you need to try a different ancestor is the 
--config syntax and the revision hash.

> Maybe I'm wrong, maybe you expect users to retry the merge with the
> other ancestor and see what happens?

That would in many situations be the recommended action, yes.

> As a curious users, I would probably do that. In that case, it would be
> helpful if Mercurial could already tell me if the merge result would
> differ depending on which ancestor I pick. In my criss-cross merge
> example above, the merge result was different depending on the ancestor
> chosen -- that's important information.

I think most cases either will be simple (where the first try is 
completely smoorth) so the user won't retry, or it will be complex and 
it probably will make a difference. Whether it makes a real difference 
or not depends on the details of the conflict and the merge tool.

Again, this is something bid merge try to automate.

>
>>> That's still a bit long and unhelpful -- people would still need to
>>> know why they might want to pick another merge base. Maybe an even
>>> better idea would be to refer people to a help topic. We could add a
>>> verbose section to 'hg help merge' that describes this, for example.
>>>
>>> I think the feature is undocumented right now -- I can add a
>>> paragraph to 'hg help merge' and config.txt if people like that idea?
>> Thanks, that could perhaps be helpful.
>>
>> Users should however never add it to their hgrc so describing it in
>> config.txt could be misleading.
>>
>> The option should only be used after an ordinary merge has shown the
>> ambiguity and suggested some values. Most users will probably never
>> see it. It should thus not take too much attention for people reading
>> the help.
> So maybe a verbose section in 'hg help merge' is better. I would then
> prefer a hint-like message of the form
>
>    $ hg merge
>    note: using eb49ad46fd72 as ancestor of 333411d2f751 and 7d1f71140c74
>    (alternatives: fdf4b78f5292, 30c60e28aa9b, see 'hg help -v merge')

That could work. But I think it is valuable to give the user exactly the 
information he needs (ie the config syntax and name).

>
>> Note: Bid merge has not seen a lot of testing and feedback. It could
>> be considered kind of experimental and is so far not documented.
> Yeah, the full power of this is still experimental. But I think the
> notes (potentally) printed by 'hg merge' make the feature quite public.
> That means that we should come up with some documentation.

Yes, preferancestor is public. And no, the hints do not mention "*" and 
bidmerge.

/Mads
Matt Mackall - April 22, 2014, 3:30 p.m.
On Tue, 2014-04-22 at 10:05 +0200, Martin Geisler wrote:
> I think it's pretty good -- adding a real --ancestor command line flag
> to merge would make it a little easier to discover this feature. But I
> take it that you want to keep this feature a little under the radar for
> now.

FYI, I plan to make multi-ancestor merge on-by-default after the freeze.

Patch

diff --git a/mercurial/merge.py b/mercurial/merge.py
--- a/mercurial/merge.py
+++ b/mercurial/merge.py
@@ -723,15 +723,64 @@  def calculateupdates(repo, wctx, mctx, a
                      acceptremote, followcopies):
     "Calculate the actions needed to merge mctx into wctx using ancestors"
 
-    ancestor = ancestors[0]
+    # Call for bids
+    fbids = {} # mapping filename to list af action bids
+    for ancestor in ancestors:
+        if len(ancestors) > 1:
+            repo.ui.note(_('calculating bids for ancestor %s\n') % ancestor)
+        actions = manifestmerge(repo, wctx, mctx, ancestor, branchmerge, force,
+                                partial, acceptremote, followcopies)
+        if len(ancestors) > 1:
+            for a in sorted(actions):
+                repo.ui.debug(' %s: %s\n' % (a[0], a[1]))
+                f = a[0]
+                if f in fbids:
+                    fbids[f].append(a)
+                else:
+                    fbids[f] = [a]
+
+    # Pick the best bid for each file
     if len(ancestors) > 1:
-        ancestor = wctx.ancestor(mctx)
-        assert ancestor in ancestors
-
-    actions = manifestmerge(repo, wctx, mctx,
-                             ancestor,
-                             branchmerge, force,
-                             partial, acceptremote, followcopies)
+        repo.ui.note(_('merging merge bids\n'))
+        actions = []
+        for f, bidsl in sorted(fbids.items()):
+            # Consensus?
+            a0 = bidsl[0]
+            if util.all(a == a0 for a in bidsl[1:]): # len(bidsl) is > 1
+                repo.ui.note(" %s: consensus for %s\n" % (f, a0[1]))
+                actions.append(a0)
+                continue
+            # Group bids by kind of action
+            bids = {}
+            for a in bidsl:
+                m = a[1]
+                if m in bids:
+                    bids[m].append(a)
+                else:
+                    bids[m] = [a]
+            # If keep is an option, just do it.
+            if "k" in bids:
+                repo.ui.note(" %s: picking 'keep' action\n" % f)
+                actions.append(bids["k"][0])
+                continue
+            # If all gets agree [how could they not?], just do it.
+            if "g" in bids:
+                ga0 = bids["g"][0]
+                if util.all(a == ga0 for a in bids["g"][1:]):
+                    repo.ui.note(" %s: picking 'get' action\n" % f)
+                    actions.append(ga0)
+                    continue
+            # TODO: Consider other simple actions such as mode changes
+            # Handle inefficient democrazy.
+            repo.ui.note(_(' %s: multiple merge bids:\n') % (f, m))
+            for a in bidsl:
+                repo.ui.note('  %s: %s\n' % (f, a[1]))
+            # Pick random action. TODO: Instead, prompt user when resolving
+            a0 = bidsl[0]
+            repo.ui.warn(_(' %s: ambiguous merge - picked %s action)\n') %
+                         (f, a0[1]))
+            actions.append(a0)
+            continue
 
     # Filter out prompts.
     newactions, prompts = [], []
diff --git a/tests/test-merge-criss-cross.t b/tests/test-merge-criss-cross.t
--- a/tests/test-merge-criss-cross.t
+++ b/tests/test-merge-criss-cross.t
@@ -72,22 +72,29 @@  Criss cross merging
   
 
   $ hg merge -v --debug --tool internal:dump 5
+  calculating bids for ancestor 0f6b37dbe527
     searching for copies back to rev 3
   resolving manifests
    branchmerge: True, force: False, partial: False
    ancestor: 0f6b37dbe527, local: 3b08d01b0ab5+, remote: adfe50279922
+   f1: g
+   f2: m
+  calculating bids for ancestor 40663881a6dd
+    searching for copies back to rev 3
+  resolving manifests
+   branchmerge: True, force: False, partial: False
+   ancestor: 40663881a6dd, local: 3b08d01b0ab5+, remote: adfe50279922
+   f1: m
+   f2: k
+  merging merge bids
+   f1: picking 'get' action
+   f2: picking 'keep' action
    f1: remote is newer -> g
-   f2: versions differ -> m
-    preserving f2 for resolve of f2
+   f2: keep -> k
   getting f1
-  updating: f1 1/2 files (50.00%)
-  updating: f2 2/2 files (100.00%)
-  picked tool 'internal:dump' for f2 (binary False symlink False)
-  merging f2
-  my f2@3b08d01b0ab5+ other f2@adfe50279922 ancestor f2@40494bf2444c
-  1 files updated, 0 files merged, 0 files removed, 1 files unresolved
-  use 'hg resolve' to retry unresolved file merges or 'hg update -C .' to abandon
-  [1]
+  updating: f1 1/1 files (100.00%)
+  1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+  (branch merge, don't forget to commit)
 
   $ head *
   ==> f1 <==
@@ -95,17 +102,88 @@  Criss cross merging
   
   ==> f2 <==
   6 second change
+
+The other way around:
+
+  $ hg up -C -r5
+  2 files updated, 0 files merged, 0 files removed, 0 files unresolved
+  $ hg merge -v --debug
+  calculating bids for ancestor 0f6b37dbe527
+    searching for copies back to rev 3
+  resolving manifests
+   branchmerge: True, force: False, partial: False
+   ancestor: 0f6b37dbe527, local: adfe50279922+, remote: 3b08d01b0ab5
+   f1: k
+   f2: m
+  calculating bids for ancestor 40663881a6dd
+    searching for copies back to rev 3
+  resolving manifests
+   branchmerge: True, force: False, partial: False
+   ancestor: 40663881a6dd, local: adfe50279922+, remote: 3b08d01b0ab5
+   f1: m
+   f2: g
+  merging merge bids
+   f1: picking 'keep' action
+   f2: picking 'get' action
+   f1: keep -> k
+   f2: remote is newer -> g
+  getting f2
+  updating: f2 1/1 files (100.00%)
+  1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+  (branch merge, don't forget to commit)
+
+  $ head *
+  ==> f1 <==
+  5 second change
   
-  ==> f2.base <==
-  0 base
-  
-  ==> f2.local <==
+  ==> f2 <==
   6 second change
-  
-  ==> f2.orig <==
-  6 second change
-  
-  ==> f2.other <==
-  2 first change
+
+Verify how the output looks and and how verbose it is:
+
+  $ hg up -qC
+  $ hg merge
+  1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+  (branch merge, don't forget to commit)
+
+  $ hg up -qC
+  $ hg merge -v
+  calculating bids for ancestor 0f6b37dbe527
+  resolving manifests
+  calculating bids for ancestor 40663881a6dd
+  resolving manifests
+  merging merge bids
+   f1: picking 'get' action
+   f2: picking 'keep' action
+  getting f1
+  1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+  (branch merge, don't forget to commit)
+
+  $ hg up -qC
+  $ hg merge -v --debug
+  calculating bids for ancestor 0f6b37dbe527
+    searching for copies back to rev 3
+  resolving manifests
+   branchmerge: True, force: False, partial: False
+   ancestor: 0f6b37dbe527, local: 3b08d01b0ab5+, remote: adfe50279922
+   f1: g
+   f2: m
+  calculating bids for ancestor 40663881a6dd
+    searching for copies back to rev 3
+  resolving manifests
+   branchmerge: True, force: False, partial: False
+   ancestor: 40663881a6dd, local: 3b08d01b0ab5+, remote: adfe50279922
+   f1: m
+   f2: k
+  merging merge bids
+   f1: picking 'get' action
+   f2: picking 'keep' action
+   f1: remote is newer -> g
+   f2: keep -> k
+  getting f1
+  updating: f1 1/1 files (100.00%)
+  1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+  (branch merge, don't forget to commit)
+
 
   $ cd ..