[PATCH 1 of 3 evolve-ext-V3] evolve: add ordering of the revisions for evolve --rev
Laurent Charignon
lcharignon at fb.com
Thu Jun 4 17:31:28 UTC 2015
# HG changeset patch
# User Laurent Charignon <lcharignon at fb.com>
# Date 1433283749 25200
# Tue Jun 02 15:22:29 2015 -0700
# Node ID 62a2906c45be56f77a05bb58e2475bdd4a43fa5f
# Parent b4a62d6f03534de6e65962c0e92cadea4b6cbad1
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,74 @@
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 troubled 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
+ evenutally
+
+ 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 +1376,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,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
+
More information about the Mercurial-devel
mailing list