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
       \ /
    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.
    (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
    * 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.