hgext3rd/evolve/evolvecmd.py
changeset 3469 e97bfd529e72
parent 3466 0a8e3130ad00
child 3470 ece5cd58147d
--- a/hgext3rd/evolve/evolvecmd.py	Sun Jan 21 20:28:06 2018 +0530
+++ b/hgext3rd/evolve/evolvecmd.py	Sun Jan 21 20:33:39 2018 +0530
@@ -398,6 +398,41 @@
 class MergeFailure(error.Abort):
     pass
 
+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 = utility.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 relocate(repo, orig, dest, pctx=None, keepbranch=False):
     """rewrites the orig rev on dest rev