# HG changeset patch
# User Laurent Charignon <lcharignon@fb.com>
# Date 1433450112 25200
# Node ID 3bb7a080da4d2a6b83fdf0d6b22b9a5f414f7e98
# Parent  aff6bc2a6b2de0ed37daa8928b8ca9c00a4f7099
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 -r aff6bc2a6b2d -r 3bb7a080da4d README
--- a/README	Thu Jun 04 13:26:58 2015 -0700
+++ b/README	Thu Jun 04 13:35:12 2015 -0700
@@ -51,6 +51,13 @@
 Changelog
 =========
 
+5.2.0 --
+
+- evolve: gain a --rev option to control what revisions to evolve (issue4391)
+- evolve: revision are processed in the order they stack on destination
+- evolve: properly skip unstable revision with non-evolved unstable parent
+
+
 5.1.5 --
 
 - minor documentation cleanup
diff -r aff6bc2a6b2d -r 3bb7a080da4d hgext/evolve.py
--- a/hgext/evolve.py	Thu Jun 04 13:26:58 2015 -0700
+++ b/hgext/evolve.py	Thu Jun 04 13:35:12 2015 -0700
@@ -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,76 @@
     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 instable 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
+    eventually.
+
+    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 +1378,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 -r aff6bc2a6b2d -r 3bb7a080da4d tests/test-evolve.t
--- a/tests/test-evolve.t	Thu Jun 04 13:26:58 2015 -0700
+++ b/tests/test-evolve.t	Thu Jun 04 13:35:12 2015 -0700
@@ -1066,3 +1066,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
+