[PATCH 1 of 3 evolve-ext-V3] evolve: add ordering of the revisions for evolve --rev

Laurent Charignon lcharignon at fb.com
Thu Jun 4 12:31:28 CDT 2015


# HG changeset patch
# User Laurent Charignon <lcharignon at fb.com>
# Date 1433283749 25200
#      Tue Jun 02 15:22:29 2015 -0700
# Node ID 62a2906c45be56f77a05bb58e2475bdd4a43fa5f
# Parent  b4a62d6f03534de6e65962c0e92cadea4b6cbad1
evolve: add ordering of the revisions for evolve --rev

When running evolve --rev we want to process the revisions in an optimal fashion
to solve the maximum amount of trouble in the minimum number of steps.
This patch adds a step to evolve --rev to order the revision before solving
the troubles. A simple test is added to cover a basic case.

diff --git a/hgext/evolve.py b/hgext/evolve.py
--- a/hgext/evolve.py
+++ b/hgext/evolve.py
@@ -28,6 +28,7 @@
 from StringIO import StringIO
 import struct
 import re
+import collections
 import socket
 import errno
 sha1re = re.compile(r'\b[0-9a-f]{6,40}\b')
@@ -1232,6 +1233,74 @@
     if repo['.'] != startnode:
         ui.status(_('working directory is now at %s\n') % repo['.'])
 
+def _singlesuccessor(repo, p):
+    """ Returns p if not obsolete or its unique latest successors; fail if there
+    are no such successor"""
+
+    if not p.obsolete():
+        return p
+    obs = repo[p]
+    ui = repo.ui
+    newer = obsolete.successorssets(repo, obs.node())
+    # search of a parent which is not killed
+    while not newer or newer == [()]:
+        ui.debug("stabilize target %s is plain dead,"
+                 " trying to stabilize on its parent\n" %
+                 obs)
+        obs = obs.parents()[0]
+        newer = obsolete.successorssets(repo, obs.node())
+    if len(newer) > 1:
+        raise util.Abort(_("conflict rewriting. can't choose destination\n"))
+    return repo[newer[0][0]].rev()
+
+def orderrevs(repo, revs):
+    """ Compute an ordering to solve instability for the given revs
+
+    - Takes revs a list of troubled revisions
+    - Returns the same revisions ordered to solve their instability from the
+    bottom to the top of the stack that the stabilization process will produce
+    evenutally
+
+    This ensure the minimal number of stabilization as we can stabilize each
+    revision on its final, stabilized, destination.
+
+    """
+
+    # Step 1: Build the dependency graph
+    # For each troubled revision we keep track of what instability if any should
+    # be resolved in order to resolve it. Example:
+    # dependencies = {3: [6], 6:[]}
+    # Means that: 6 has no dependency, 3 depends on 6 to be solved
+    dependencies = {}
+    # rdependencies is the inverted dict of dependencies
+    rdependencies = collections.defaultdict(set)
+
+    for r in revs:
+        dependencies[r] = set()
+        for p in repo[r].parents():
+            succ = _singlesuccessor(repo, p)
+            if succ in revs:
+                dependencies[r].add(succ)
+                rdependencies[succ].add(r)
+
+    # Step 2: Build the ordering
+    # Remove the revisions with no dependency(A) and add them to the ordering.
+    # Removing these revisions leads to new revisions with no dependency (the one
+    # depending on A) that we can remove from the dependency graph and add to the
+    # ordering. We progress in a similar fashion until the ordering is built
+    solvablerevs = collections.deque([r for r in sorted(dependencies.keys())\
+                                        if not dependencies[r]])
+    ordering = []
+    while solvablerevs:
+        rev = solvablerevs.popleft()
+        for dependent in rdependencies[rev]:
+            dependencies[dependent].remove(rev)
+            if not dependencies[dependent]:
+                solvablerevs.append(dependent)
+        ordering.append(rev)
+
+    return ordering
+
 @command('^evolve|stabilize|solve',
     [('n', 'dry-run', False,
         'do not perform actions, just print what would be done'),
@@ -1307,6 +1376,8 @@
         else:
             # For the progress bar to show
             count = len(_revs)
+            # Order the revisions
+            _revs = orderrevs(repo, _revs)
             for rev in _revs:
                 progresscb()
                 _solveone(ui, repo, repo[rev], dryrunopt, confirmopt,
diff --git a/tests/test-evolve.t b/tests/test-evolve.t
--- a/tests/test-evolve.t
+++ b/tests/test-evolve.t
@@ -1068,3 +1068,15 @@
   $ hg evolve --rev 23
   cannot solve instability of c70048fd3350, skipping
 
+evolve --rev reordering
+-----------------------
+
+evolve --rev reorders the rev to solve instability, trivial case 2 revs wrong order
+
+  $ hg evolve --rev '23 + 22'
+  move:[22] add j2
+  atop:[25] add j1
+  move:[23] add j3
+  atop:[26] add j2
+  working directory is now at 928e4c317356
+


More information about the Mercurial-devel mailing list