Mercurial revsets alias that lets you merge two complex branches while avoiding "criss-cross" merges

nextMerge

[revsetalias]

# The first parameter is the merge destination. The second is the set of changesets that you'd ultimately like to merge.
# If multiple changesets are returned, recursion is required. Please rerun with the head changeset as the second argument.
#
# Implementing this within Mercurial or as an extension would be better because we'd be able to automatically perform the recursion.
nextMerge($1,$2) = nextMergeForSingleHead( $1, oldest( heads( $2 - ancestors($1) ) ) )


# In the following aliases, each parameter should be a single changeset.

# only one term at a time should return results
nextMergeForSingleHead($1,$2) = headMerge($1,$2) | safeMergeCandidateAndAncestors($1,$2) | noOpMerge($1,$2)

# the unmerged head, if only a single GCA exists
headMerge($1,$2) = $2 & firstGcaChangesets($1,$2)

safeMergeCandidateAndAncestors($1,$2) = ancestors( safeMergeCandidate($1,$2) ) & unmergedAncestors($1,$2)

# the oldest unmerged parent of the oldest multi-GCA changeset
safeMergeCandidate($1,$2) = oldest( unmergedAncestors($1,$2) & parents( oldestMultiGcaChangeset($1,$2) ) ) & noOpMergeMask($1,$2)

# The oldest unmerged changeset that descends from the first GCA and one or more other GCAs. Will always be a merge changeset.
oldestMultiGcaChangeset($1,$2) = oldest( ( unmergedAncestors($1,$2) & descendants( firstGca($1,$2) ) ) - firstGcaChangesets($1,$2) )

# the changesets that descend from the first GCA and not from any others
firstGcaChangesets($1,$2) = descendants( firstGca($1,$2) ) - descendants( greatestCommonAncestors($1,$2) - firstGca($1,$2) )

noOpMergeMask($1,$2) = not descendants( ancestors( noOpMergeChangesets($1,$2) ) )

# the oldest head of the no-op merge changesets
noOpMerge($1,$2) = oldest( heads( noOpMergeChangesets($1,$2) ) )

# the GCA-child merge changesets that, when merged into the destination, will eliminate GCAs without changing anything
noOpMergeChangesets($1,$2) = gcaChildMergeChangesets($1,$2) - descendants( unmergedAncestors($1,$2) - merge() )

# the unmerged merge changesets that are children of a GCA
gcaChildMergeChangesets($1,$2) = unmergedAncestors($1,$2) & merge() & children( greatestCommonAncestors($1,$2) )

# The first GCA of the oldest unmerged child of a GCA. If the oldest unmerged child of a GCA is a merge with two GCA parents, one is chosen arbitrarily.
firstGca($1,$2) = first( parents( oldest( children( greatestCommonAncestors($1,$2) ) & unmergedAncestors($1,$2) ) ) & greatestCommonAncestors($1,$2) )

unmergedAncestors($1,$2) = ancestors($2) - ancestors($1)


oldest($1) = first( sort($1,rev) )

# Similar to the *ancestor* predicate, but not limited to one result. Each parameter should be a single changeset.
greatestCommonAncestors($1,$2) = heads( ancestors($1) & ancestors($2) )

# Rationale:
# 
# Merging algorithms depend on finding the Greatest Common Ancestor (GCA) of the two changesets being merged, so they'll work most predictably when this is not
# ambiguous. This means that, in general, we should avoid these "criss-cross" merges. When we cannot avoid them, we should first perform merges into the
# destination that get us in a position to perform a criss-cross merge that consists solely of merge changesets (i.e. a "no-op" merge). We can repeat this
# process until only a single GCA remains, at which point we can safely complete the original merge.
# References:
# http://codicesoftware.blogspot.com/2011/09/merge-recursive-strategy.html
# http://article.gmane.org/gmane.comp.version-control.mercurial.general/29523