merge: with merge.preferancestor=*, run an auction with bids from ancestors

The basic idea is to do the merge planning with all the available ancestors,
consider the resulting actions as "bids", make an "auction" and
automatically pick the most favourable action for each file.

This implements the basic functionality and will only consider "keep" and
"get" actions. The heuristics for picking the best action can be tweaked later
on.

By default it will only pass ctx.ancestor as the single ancestor to
calculateupdates. The code path for merging with a single ancestor is not
changed.

mercurial/merge.py

@@ -723,12 +723,69 b' def calculateupdates(repo, wctx, mctx, a'
                      acceptremote, followcopies):
     "Calculate the actions needed to merge mctx into wctx using ancestors"
 
-    ancestor = ancestors[0]
+    if len(ancestors) == 1: # default
+        actions = manifestmerge(repo, wctx, mctx, ancestors[0],
+                                branchmerge, force,
+                                partial, acceptremote, followcopies)
 
-    actions = manifestmerge(repo, wctx, mctx,
-                             ancestor,
+    else: # only when merge.preferancestor=* - experimentalish code
+        # Call for bids
+        fbids = {} # mapping filename to list af action bids
+        for ancestor in ancestors:
+            repo.ui.note(_('\ncalculating bids for ancestor %s\n') % ancestor)
+            actions = manifestmerge(repo, wctx, mctx, ancestor,
                              branchmerge, force,
                              partial, acceptremote, followcopies)
+            for a in sorted(actions):
+                repo.ui.debug(' %s: %s\n' % (a[0], a[1]))
+                f = a[0]
+                if f in fbids:
+                    fbids[f].append(a)
+                else:
+                    fbids[f] = [a]
+
+        # Pick the best bid for each file
+        repo.ui.note(_('\nauction for merging merge bids\n'))
+        actions = []
+        for f, bidsl in sorted(fbids.items()):
+            # Consensus?
+            a0 = bidsl[0]
+            if util.all(a == a0 for a in bidsl[1:]): # len(bidsl) is > 1
+                repo.ui.note(" %s: consensus for %s\n" % (f, a0[1]))
+                actions.append(a0)
+                continue
+            # Group bids by kind of action
+            bids = {}
+            for a in bidsl:
+                m = a[1]
+                if m in bids:
+                    bids[m].append(a)
+                else:
+                    bids[m] = [a]
+            # If keep is an option, just do it.
+            if "k" in bids:
+                repo.ui.note(" %s: picking 'keep' action\n" % f)
+                actions.append(bids["k"][0])
+                continue
+            # If all gets agree [how could they not?], just do it.
+            if "g" in bids:
+                ga0 = bids["g"][0]
+                if util.all(a == ga0 for a in bids["g"][1:]):
+                    repo.ui.note(" %s: picking 'get' action\n" % f)
+                    actions.append(ga0)
+                    continue
+            # TODO: Consider other simple actions such as mode changes
+            # Handle inefficient democrazy.
+            repo.ui.note(_(' %s: multiple merge bids:\n') % (f, m))
+            for a in bidsl:
+                repo.ui.note('  %s: %s\n' % (f, a[1]))
+            # Pick random action. TODO: Instead, prompt user when resolving
+            a0 = bidsl[0]
+            repo.ui.warn(_(' %s: ambiguous merge - picked %s action)\n') %
+                         (f, a0[1]))
+            actions.append(a0)
+            continue
+        repo.ui.note(_('end of auction\n\n'))
 
     # Filter out prompts.
     newactions, prompts = [], []
@@ -926,6 +983,10 b' def update(repo, node, branchmerge, forc'
 
         p2 = repo[node]
         if pas[0] is None:
+            if repo.ui.config("merge", "preferancestor") == '*':
+                cahs = repo.changelog.commonancestorsheads(p1.node(), p2.node())
+                pas = [repo[anc] for anc in (sorted(cahs) or [nullid])]
+            else:
             pas = [p1.ancestor(p2)]
 
         fp1, fp2, xp1, xp2 = p1.node(), p2.node(), str(p1), str(p2)

tests/test-merge-criss-cross.t

@@ -123,4 +123,145 b' Criss cross merging'
   use 'hg resolve' to retry unresolved file merges or 'hg update -C .' to abandon
   [1]
 
+Redo merge with merge.preferancestor="*" to enable bid merge
+
+  $ rm f*
+  $ hg up -qC .
+  $ hg merge -v --debug --tool internal:dump 5 --config merge.preferancestor="*"
+  
+  calculating bids for ancestor 0f6b37dbe527
+    searching for copies back to rev 3
+  resolving manifests
+   branchmerge: True, force: False, partial: False
+   ancestor: 0f6b37dbe527, local: 3b08d01b0ab5+, remote: adfe50279922
+   f1: g
+   f2: m
+  
+  calculating bids for ancestor 40663881a6dd
+    searching for copies back to rev 3
+  resolving manifests
+   branchmerge: True, force: False, partial: False
+   ancestor: 40663881a6dd, local: 3b08d01b0ab5+, remote: adfe50279922
+   f1: m
+   f2: k
+  
+  auction for merging merge bids
+   f1: picking 'get' action
+   f2: picking 'keep' action
+  end of auction
+  
+   f1: remote is newer -> g
+   f2: keep -> k
+  getting f1
+  updating: f1 1/1 files (100.00%)
+  1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+  (branch merge, don't forget to commit)
+
+  $ head *
+  ==> f1 <==
+  5 second change
+  
+  ==> f2 <==
+  6 second change
+
+
+The other way around:
+
+  $ hg up -C -r5
+  note: using 0f6b37dbe527 as ancestor of 3b08d01b0ab5 and adfe50279922
+        alternatively, use --config merge.preferancestor=40663881a6dd
+  2 files updated, 0 files merged, 0 files removed, 0 files unresolved
+  $ hg merge -v --debug --config merge.preferancestor="*"
+  
+  calculating bids for ancestor 0f6b37dbe527
+    searching for copies back to rev 3
+  resolving manifests
+   branchmerge: True, force: False, partial: False
+   ancestor: 0f6b37dbe527, local: adfe50279922+, remote: 3b08d01b0ab5
+   f1: k
+   f2: m
+  
+  calculating bids for ancestor 40663881a6dd
+    searching for copies back to rev 3
+  resolving manifests
+   branchmerge: True, force: False, partial: False
+   ancestor: 40663881a6dd, local: adfe50279922+, remote: 3b08d01b0ab5
+   f1: m
+   f2: g
+  
+  auction for merging merge bids
+   f1: picking 'keep' action
+   f2: picking 'get' action
+  end of auction
+  
+   f1: keep -> k
+   f2: remote is newer -> g
+  getting f2
+  updating: f2 1/1 files (100.00%)
+  1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+  (branch merge, don't forget to commit)
+
+  $ head *
+  ==> f1 <==
+  5 second change
+  
+  ==> f2 <==
+  6 second change
+
+Verify how the output looks and and how verbose it is:
+
+  $ hg up -qC
+  $ hg merge --config merge.preferancestor="*"
+  1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+  (branch merge, don't forget to commit)
+
+  $ hg up -qC
+  $ hg merge -v --config merge.preferancestor="*"
+  
+  calculating bids for ancestor 0f6b37dbe527
+  resolving manifests
+  
+  calculating bids for ancestor 40663881a6dd
+  resolving manifests
+  
+  auction for merging merge bids
+   f1: picking 'get' action
+   f2: picking 'keep' action
+  end of auction
+  
+  getting f1
+  1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+  (branch merge, don't forget to commit)
+
+  $ hg up -qC
+  $ hg merge -v --debug --config merge.preferancestor="*"
+  
+  calculating bids for ancestor 0f6b37dbe527
+    searching for copies back to rev 3
+  resolving manifests
+   branchmerge: True, force: False, partial: False
+   ancestor: 0f6b37dbe527, local: 3b08d01b0ab5+, remote: adfe50279922
+   f1: g
+   f2: m
+  
+  calculating bids for ancestor 40663881a6dd
+    searching for copies back to rev 3
+  resolving manifests
+   branchmerge: True, force: False, partial: False
+   ancestor: 40663881a6dd, local: 3b08d01b0ab5+, remote: adfe50279922
+   f1: m
+   f2: k
+  
+  auction for merging merge bids
+   f1: picking 'get' action
+   f2: picking 'keep' action
+  end of auction
+  
+   f1: remote is newer -> g
+   f2: keep -> k
+  getting f1
+  updating: f1 1/1 files (100.00%)
+  1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+  (branch merge, don't forget to commit)
+
   $ cd ..