[PATCH 2 of 4 evolve-ext] evolve: add ordering of the revisions for evolve --rev
Laurent Charignon
lcharignon at fb.com
Tue Jun 2 18:01:49 CDT 2015
# HG changeset patch
# User Laurent Charignon <lcharignon at fb.com>
# Date 1433283749 25200
# Tue Jun 02 15:22:29 2015 -0700
# Node ID 52e325a0430924dfacb71d7bad3d41b027efb1ba
# Parent 9a20329fa7e7d62ad59053be9353ec1285023763
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,88 @@
if repo['.'] != startnode:
ui.status(_('working directory is now at %s\n') % repo['.'])
+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 optimaly to solve instability
+
+ """
+ ui = repo.ui
+ def _nonobsoletesuccessor(p):
+ obs = repo[p]
+ 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 addlink(a,b):
+ """ Add a link between a and b in the dependency graph
+
+ Only adds the link if b is troubles"""
+ if b in revs and b is not None:
+ dependencies[a].add(b)
+ rdependencies[b].add(a)
+
+ # Dict to keep track of resolution dependencies between troubled revs
+ dependencies = {}
+ # rdependencies is the inverted dict of dependencies
+ rdependencies = collections.defaultdict(set)
+
+ # Step 1: Build the dependency graph
+ for r in revs:
+ dependencies[r] = set()
+ parents = repo[r].parents()
+ p1 = parents[0].rev()
+ p2 = parents[1].rev() if len(parents) > 1 else None
+
+ addlink(r, p1)
+ addlink(r, p2)
+ if repo[p1].obsolete():
+ addlink(r, _nonobsoletesuccessor(p1))
+ if p2 is not None and repo[p2].obsolete():
+ addlink(r, _nonobsoletesuccessor(p2))
+
+ # Step 2: Derive the ordering from the dependency graph
+ ordering = []
+ lively = True
+
+ # Example:
+ # dependencies = {4: [3], 5: [3], 3: [6], 6:[]}
+ # Means that:
+ # - to solve 4 and 5, one need to solve 3 first
+ # - to solve 3, one need to solve 6 first
+ # - 6 can be solved straight away
+ # In that case the ordering will be [6, 3, 4, 5]
+
+ while lively and len(ordering) != len(revs):
+ # We don't want to go overboard in infinite loop
+ assert(len(ordering) < len(revs))
+ lively = False
+
+ # To ensure consistency of the traversal we sort the keys
+ traversalorder = sorted(dependencies.keys())
+
+ for rev in traversalorder:
+ deps = dependencies[rev]
+ if len(deps) == 0:
+ # No dependency left on this rev, cleanup dependents
+ for rdependency in rdependencies[rev]:
+ dependencies[rdependency].remove(rev)
+ # And queue it
+ del dependencies[rev]
+ ordering.append(rev)
+ lively = True
+ return ordering
+
@command('^evolve|stabilize|solve',
[('n', 'dry-run', False,
'do not perform actions, just print what would be done'),
@@ -1307,6 +1390,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,12 @@
$ hg evolve --rev 23
Cannot solve instability of c70048fd3350, skipping
+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