src/topic/stack.py
changeset 1897 38570c53b1cf
parent 1896 4ae421cbb07c
child 1898 2b65c5a6591c
--- 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