changeset 1897:38570c53b1cf

stack: fix printing order in case of unstability

The stack was displayed using revision number order, this give good result in
the simple case (straight stack) but give bad result when the stack is not
linear because of unstability.

We fixes it by reusing the evolution logic for sorting. As we do not live next
to evolution yet, we duplicated this logic for now.

--- a/src/topic/stack.py	Mon Mar 14 17:48:31 2016 +0000
+++ b/src/topic/stack.py	Mon Mar 14 18:11:52 2016 +0000
@@ -2,12 +2,16 @@
 #
 # This software may be used and distributed according to the terms of the
 # GNU General Public License version 2 or any later version.
+import collections
 from mercurial.i18n import _
 from mercurial import error
+from mercurial import extensions
+from mercurial import obsolete
 
 def _getstack(repo, topic):
     # XXX need sorting
-    return repo.revs("topic(%s) - obsolete()", topic)
+    trevs = repo.revs("topic(%s) - obsolete()", topic)
+    return _orderrevs(repo, trevs)
 
 def showstack(ui, repo, topic):
     if not topic:
@@ -17,3 +21,98 @@
     for r in _getstack(repo, topic):
         # super crude initial version
         ui.write(repo[r].description().splitlines()[0] + '\n')
+
+
+# Copied from evolve 081605c2e9b6
+
+def _orderrevs(repo, revs):
+    """Compute an ordering to solve instability for the given revs
+
+    revs is a list of unstable 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 ensures the minimal number of stabilizations, as we can stabilize each
+    revision on its final stabilized destination.
+    """
+    # Step 1: Build the dependency graph
+    dependencies, rdependencies = builddependencies(repo, revs)
+    # 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)
+        del dependencies[rev]
+        ordering.append(rev)
+
+    ordering.extend(sorted(dependencies))
+    return ordering
+
+def builddependencies(repo, revs):
+    """returns dependency graphs giving an order to solve instability of revs
+    (see _orderrevs for more information on usage)"""
+
+    # 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():
+            try:
+                succ = _singlesuccessor(repo, p)
+            except MultipleSuccessorsError as exc:
+                dependencies[r] = exc.successorssets
+                continue
+            if succ in revs:
+                dependencies[r].add(succ)
+                rdependencies[succ].add(r)
+    return dependencies, rdependencies
+
+def _singlesuccessor(repo, p):
+    """returns p (as rev) if not obsolete or its unique latest successors
+
+    fail if there are no such successor"""
+
+    if not p.obsolete():
+        return p.rev()
+    obs = repo[p]
+    ui = repo.ui
+    newer = obsolete.successorssets(repo, obs.node())
+    # search of a parent which is not killed
+    while not 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 or len(newer[0]) > 1:
+        raise MultipleSuccessorsError(newer)
+
+    return repo[newer[0][0]].rev()
+
+class MultipleSuccessorsError(RuntimeError):
+    """Exception raised by _singlesuccessor when multiple successor sets exists
+
+    The object contains the list of successorssets in its 'successorssets'
+    attribute to call to easily recover.
+    """
+
+    def __init__(self, successorssets):
+        self.successorssets = successorssets

--- a/tests/test-topic-stack.t	Mon Mar 14 17:48:31 2016 +0000
+++ b/tests/test-topic-stack.t	Mon Mar 14 18:11:52 2016 +0000
@@ -94,6 +94,6 @@
   
   $ hg topic --list
   c_c
+  c_d
   c_e
   c_f
-  c_d