[PATCH 2 of 4 evolve-ext] evolve: add ordering of the revisions for evolve --rev

Laurent Charignon lcharignon at fb.com
Tue Jun 2 18:01:49 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 52e325a0430924dfacb71d7bad3d41b027efb1ba
# Parent  9a20329fa7e7d62ad59053be9353ec1285023763
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,88 @@
     if repo['.'] != startnode:
         ui.status(_('working directory is now at %s\n') % repo['.'])
 
+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 optimaly to solve instability
+
+    """
+    ui = repo.ui
+    def _nonobsoletesuccessor(p):
+        obs = repo[p]
+        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 addlink(a,b):
+        """ Add a link between a and b in the dependency graph
+
+        Only adds the link if b is troubles"""
+        if b in revs and b is not None:
+            dependencies[a].add(b)
+            rdependencies[b].add(a)
+
+    # Dict to keep track of resolution dependencies between troubled revs
+    dependencies = {}
+    # rdependencies is the inverted dict of dependencies
+    rdependencies = collections.defaultdict(set)
+
+    # Step 1: Build the dependency graph
+    for r in revs:
+        dependencies[r] = set()
+        parents = repo[r].parents()
+        p1 = parents[0].rev()
+        p2 = parents[1].rev() if len(parents) > 1 else None
+
+        addlink(r, p1)
+        addlink(r, p2)
+        if repo[p1].obsolete():
+            addlink(r, _nonobsoletesuccessor(p1))
+        if p2 is not None and repo[p2].obsolete():
+            addlink(r, _nonobsoletesuccessor(p2))
+
+    # Step 2: Derive the ordering from the dependency graph
+    ordering = []
+    lively = True
+
+    # Example:
+    # dependencies = {4: [3], 5: [3], 3: [6], 6:[]}
+    # Means that:
+    # - to solve 4 and 5, one need to solve 3 first
+    # - to solve 3, one need to solve 6 first
+    # - 6 can be solved straight away
+    # In that case the ordering will be  [6, 3, 4, 5]
+
+    while lively and len(ordering) != len(revs):
+        # We don't want to go overboard in infinite loop
+        assert(len(ordering) < len(revs))
+        lively = False
+
+        # To ensure consistency of the traversal we sort the keys
+        traversalorder = sorted(dependencies.keys())
+
+        for rev in traversalorder:
+            deps = dependencies[rev]
+            if len(deps) == 0:
+                # No dependency left on this rev, cleanup dependents
+                for rdependency in rdependencies[rev]:
+                    dependencies[rdependency].remove(rev)
+                # And queue it
+                del dependencies[rev]
+                ordering.append(rev)
+                lively = True
+    return ordering
+
 @command('^evolve|stabilize|solve',
     [('n', 'dry-run', False,
         'do not perform actions, just print what would be done'),
@@ -1307,6 +1390,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,12 @@
   $ hg evolve --rev 23
   Cannot solve instability of c70048fd3350, skipping
 
+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