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

[Mads Kiilerich]

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