This page is primarily intended for developers of Mercurial.

Consensus Merge

A proposed merge algorithm for dealing with complicated merges.

Something similar to this has been implemented in 3.0 as Bid Merge.

1. Problem

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. Mercurial currently arbitrarily chooses the first of these, which can result in various issues:

Other systems like Git have attacked this problem 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.

2. Concept

Consensus 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 call a "perspective". We then compare all the perspectives and construct a "consensus" action for each file. Each definite action (e.g. "get file revision X") is considered to represent a "judgment", while indefinite actions (prompts, file-level merges) are considered "doubts". We then construct a consensus action as follows:

Some observations:

3. Implementation strategy

CategoryDeveloper CategoryOldFeatures

ConsensusMerge (last edited 2017-12-06 21:31:33 by KevinBullock)