Consensus Merge

A proposed merge algorithm for dealing with complicated merges.

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:

• conflicts that have already been resolved may reappear
• changes that have been reversed can silently oscillate

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:

• if all judgments agree, use that judgment as the consensus action
• if there are no judgments, use the most popular doubt as the consensus action

Some observations:

• judgments indicate more information is available in that perspective than doubts, thus judgments trump
• conflicting judgments probably indicate real conflicts that need resolution (the silent oscillation case)
• three-way merge is a degenerate case of this strategy

3. Implementation strategy

• Extend ancestor.ancestor() code to return all greatest common ancestors
• Separate prompt handling from merge.manifestmerge() into a new merge.resolveprompt() phase
• Add merge.consensus() to loop across ancestors to build perspectives, then build a consensus action list

CategoryDeveloper CategoryNewFeatures