view mercurial/helptext/internals/bid-merge.txt @ 46414:16c18d5e5dc8

merge with stable

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.