Bid Merge Algorithm

Bid merge is a feature introduced in Mercurial 3.0, a merge algorithm for dealing with complicated merges.

Bid merge is controled by the 'merge.preferancestor' configuration option. The default is set to 'merge.preferancetors=*' and enable bid merge. 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.

Problem it is solving

Mercurial's core merge algorithm is the traditional "three-way merge". This algorithm combines all the changes in two changesets relative to a common ancestor. But with complex DAGs, it is often possible to have more than one "best" common ancestor, with no easy way to distinguish between them.

For example, C and D has 2 common ancestors in the following graph:

C   D
|\ /|
| x |
|/ \|
A   B
 \ /
  R

Mercurial used to arbitrarily chooses the first of these, which can result in various issues:

• unexpected hard 3-way merges that would have been completely trivial if another ancestor had been used
• conflicts that have already been resolved may reappear
• changes that have been reversed can silently oscillate

One common problem is a merge which with the "right" ancestor would be trivial to resolve because only one side changed. Using another ancestor where the same lines are different, it will give an annoying 3-way merge.

Other systems like Git have attacked some of these problems with a so-called "recursive" merge strategy, that internally merges all the possible ancestors to produce a single "virtual" ancestor to merge against. This is awkward as the internal merge itself may involve conflicts (and possibly even multiple levels of recursion), which either requires choosing a conflict disposition (e.g. always choose the local version) or exposing the user to extremely confusing merge prompts for old revisions. Generating the virtual merge also potentially involves invoking filters and extensions.

Concept

(Bid merge is pretty much the same as Consensus merge.)

Bid merge is a strategy that attempts to sensibly combine the results of the multiple possible three-way merges directly without producing a virtual ancestor. The basic idea is that for each ancestor, we perform a top-level manifest merge and generate a list of proposed actions, which we consider "bids". We then make an "auction" among all the bids for each file and pick the most favourable. Some files might be trivial to merge with one ancestor, other files with another ancestor.

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. A bid for just taking an existing revision is very simple and low risk and is an obvious winner.

The auction algorithm for merging the bids is so far very simple:

• If there is consensus from all the ancestors, 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.
• If "keep local" or "get from other" actions is an option (and there is only one such option), just do it.
• If the auction doesn't have a single clear winner, pick one of the bids "randomly" - just as it would have done if only one ancestor was considered.

This meta merge algorithm has room for future improvements, especially for doing better than picking a random bid.

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 hashes of content without history.) One way to handle that would be to refactor manifestmerge, mergestate/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 using multiple ancestors 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.

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.