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

[Mads Kiilerich]

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