Patchwork [16,of,16] merge: take bids for merge actions for different ancestors and pick the best

login
register
mail settings
Submitter Mads Kiilerich
Date March 2, 2014, 7:15 p.m.
Message ID <148ab12191db5a193890.1393787749@localhost.localdomain>
Download mbox | patch
Permalink /patch/3828/
State Deferred
Headers show

Comments

Mads Kiilerich - March 2, 2014, 7:15 p.m.
# HG changeset patch
# User Mads Kiilerich <madski@unity3d.com>
# Date 1393728157 -3600
#      Sun Mar 02 03:42:37 2014 +0100
# Node ID 148ab12191db5a193890bcb961f4071407df85c8
# Parent  ce8005617789415633a79cd654f788b6f8dd41f2
merge: take bids for merge actions for different ancestors and pick the best

This is inspired by and similar to "Consensus Merge". Conceptually I find it
essential that this is all about handling the situation where there _not_ is
consensus but where we want to make an automatic and clever decision anyway.

The basic idea is to do the merge planning with all the available ancestors and
then automatically pick the best and simplest actions.

The algorithm used here makes a call for bids for merging with all the possible
merge ancestors and uses simple heuristics for picking the best and simplest
merge action for each file.

This just implements the basic functionality. The heuristics for picking the
best action can be tweaked later on. The decision of what to do in the case
where there is no obvious good solution should be moved to the resolve phase
where it is most convenient for the user to make the choice.

Patch

diff --git a/mercurial/merge.py b/mercurial/merge.py
--- a/mercurial/merge.py
+++ b/mercurial/merge.py
@@ -667,14 +667,70 @@  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:
-        ancestor = wctx.ancestor(mctx)
-
-    actions = manifestmerge(repo, wctx, mctx,
+    # Call for bids
+    bids = {} # mapping filename to mapping from method to action list
+    for ancestor in ancestors:
+        if len(ancestors) > 1:
+            repo.ui.status(_('getting merge bid for ancestor %s\n') % ancestor)
+        actions = manifestmerge(repo, wctx, mctx,
                              ancestor,
                              branchmerge, force,
                              partial, acceptremote, followcopies)
+        if len(ancestors) > 1:
+            for a in sorted(actions):
+                repo.ui.status(' %s\n' % (a,))
+                f = a[0]
+                try:
+                    fbids = bids[f]
+                except KeyError:
+                    fbids = bids[f] = {}
+                m = a[1]
+                try:
+                    fbids[m].append(a)
+                except KeyError:
+                    fbids[m] = [a]
+
+    # Pick the best bid for each file
+    if len(ancestors) > 1:
+        repo.ui.status(_('merging merge bids:\n'))
+        actions = []
+        for f, fbids in sorted(bids.items()):
+            # Did everybody vote? Not voting means keep - pick that.
+            if sum(len(l) for l in fbids.values()) < len(ancestors):
+                repo.ui.status(" %s: picking no action\n" % f)
+                continue
+            # Consensus?
+            if len(fbids) == 1:
+                m, l = fbids.items()[0]
+                a0 = l[0]
+                if util.all(a == a0 for a in l[1:]):
+                    repo.ui.status(" %s: consensus for %s\n" % (f, m))
+                    actions.append(a0)
+                    continue
+            # If all gets agree, pick that.
+            elif "g" in fbids:
+                l = fbids["g"]
+                a0 = l[0]
+                if util.all(a0 == a for a in l[1:]):
+                    repo.ui.status(" %s: picking g\n" % f)
+                    actions.append(a0)
+                    continue
+            # Report inefficient democrazy
+            for m, l in fbids.items():
+                repo.ui.note(_(' %s: bids for %s:\n') % (f, m))
+                for a in l:
+                    repo.ui.note('  %s\n' % (a,))
+            # TODO: Prompt user instead of picking a random action.
+            a0 = min(min(fbids.values()))
+            repo.ui.warn(_(' %s: ambiguous merge - picked a %s)\n') % (f, a0))
+            actions.append(a0)
+            continue
+
+        actions.sort()
+
+        repo.ui.status(_('actions after bid merging:\n'))
+        for a in actions:
+            repo.ui.status(' %s\n' % (a,))
 
     # Filter out prompts.
     newactions, prompts = [], []
diff --git a/tests/test-merge-criss-cross.t b/tests/test-merge-criss-cross.t
--- a/tests/test-merge-criss-cross.t
+++ b/tests/test-merge-criss-cross.t
@@ -72,22 +72,29 @@  Criss cross merging
   
 
   $ hg merge -v --debug --tool internal:dump 5
+  getting merge bid 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', ('',), 'remote is newer')
+   ('f2', 'm', ('f2', 'f2', 'f2', False, "\x0fk7\xdb\xe5'\x0b\xce\xe4K\xa1\xcd\x04\xef\xb5\x8a+\x1d}\xc0"), 'versions differ')
+  getting merge bid 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', ('f1', 'f1', 'f1', False, '@f8\x81\xa6\xdd\xe9+\xb7[p\xc3\x99\x0b\xad\x94\x8b\x98\x85R'), 'versions differ')
+  merging merge bids:
+   f1: picking g
+   f2: picking no action
+  actions after bid merging:
+   ('f1', 'g', ('',), 'remote is newer')
    f1: remote is newer -> g
-   f2: versions differ -> m
-    preserving f2 for resolve of f2
   getting f1
-  updating: f1 1/2 files (50.00%)
-  updating: f2 2/2 files (100.00%)
-  picked tool 'internal:dump' for f2 (binary False symlink False)
-  merging f2
-  my f2@3b08d01b0ab5+ other f2@adfe50279922 ancestor f2@40494bf2444c
-  1 files updated, 0 files merged, 0 files removed, 1 files unresolved
-  use 'hg resolve' to retry unresolved file merges or 'hg update -C .' to abandon
-  [1]
+  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 <==
@@ -95,17 +102,5 @@  Criss cross merging
   
   ==> f2 <==
   6 second change
-  
-  ==> f2.base <==
-  0 base
-  
-  ==> f2.local <==
-  6 second change
-  
-  ==> f2.orig <==
-  6 second change
-  
-  ==> f2.other <==
-  2 first change
 
   $ cd ..