Mercurial > public > mercurial-scm > evolve
comparison hgext/evolve.py @ 1357:3bb7a080da4d
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.
| author | Laurent Charignon <lcharignon@fb.com> |
|---|---|
| date | Thu, 04 Jun 2015 13:35:12 -0700 |
| parents | b4a62d6f0353 |
| children | 043e5ca9322f |
comparison
equal
deleted
inserted
replaced
| 1356:aff6bc2a6b2d | 1357:3bb7a080da4d |
|---|---|
| 26 import sys, os | 26 import sys, os |
| 27 import random | 27 import random |
| 28 from StringIO import StringIO | 28 from StringIO import StringIO |
| 29 import struct | 29 import struct |
| 30 import re | 30 import re |
| 31 import collections | |
| 31 import socket | 32 import socket |
| 32 import errno | 33 import errno |
| 33 sha1re = re.compile(r'\b[0-9a-f]{6,40}\b') | 34 sha1re = re.compile(r'\b[0-9a-f]{6,40}\b') |
| 34 | 35 |
| 35 import mercurial | 36 import mercurial |
| 1230 if showprogress: | 1231 if showprogress: |
| 1231 ui.progress('evolve', None) | 1232 ui.progress('evolve', None) |
| 1232 if repo['.'] != startnode: | 1233 if repo['.'] != startnode: |
| 1233 ui.status(_('working directory is now at %s\n') % repo['.']) | 1234 ui.status(_('working directory is now at %s\n') % repo['.']) |
| 1234 | 1235 |
| 1236 def _singlesuccessor(repo, p): | |
| 1237 """returns p if not obsolete or its unique latest successors | |
| 1238 | |
| 1239 fail if there are no such successor""" | |
| 1240 | |
| 1241 if not p.obsolete(): | |
| 1242 return p | |
| 1243 obs = repo[p] | |
| 1244 ui = repo.ui | |
| 1245 newer = obsolete.successorssets(repo, obs.node()) | |
| 1246 # search of a parent which is not killed | |
| 1247 while not newer or newer == [()]: | |
| 1248 ui.debug("stabilize target %s is plain dead," | |
| 1249 " trying to stabilize on its parent\n" % | |
| 1250 obs) | |
| 1251 obs = obs.parents()[0] | |
| 1252 newer = obsolete.successorssets(repo, obs.node()) | |
| 1253 if len(newer) > 1: | |
| 1254 raise util.Abort(_("conflict rewriting. can't choose destination\n")) | |
| 1255 return repo[newer[0][0]].rev() | |
| 1256 | |
| 1257 def orderrevs(repo, revs): | |
| 1258 """ Compute an ordering to solve instability for the given revs | |
| 1259 | |
| 1260 - Takes revs a list of instable revisions | |
| 1261 | |
| 1262 - Returns the same revisions ordered to solve their instability from the | |
| 1263 bottom to the top of the stack that the stabilization process will produce | |
| 1264 eventually. | |
| 1265 | |
| 1266 This ensure the minimal number of stabilization as we can stabilize each | |
| 1267 revision on its final, stabilized, destination. | |
| 1268 """ | |
| 1269 | |
| 1270 # Step 1: Build the dependency graph | |
| 1271 # For each troubled revision we keep track of what instability if any should | |
| 1272 # be resolved in order to resolve it. Example: | |
| 1273 # dependencies = {3: [6], 6:[]} | |
| 1274 # Means that: 6 has no dependency, 3 depends on 6 to be solved | |
| 1275 dependencies = {} | |
| 1276 # rdependencies is the inverted dict of dependencies | |
| 1277 rdependencies = collections.defaultdict(set) | |
| 1278 | |
| 1279 for r in revs: | |
| 1280 dependencies[r] = set() | |
| 1281 for p in repo[r].parents(): | |
| 1282 succ = _singlesuccessor(repo, p) | |
| 1283 if succ in revs: | |
| 1284 dependencies[r].add(succ) | |
| 1285 rdependencies[succ].add(r) | |
| 1286 | |
| 1287 # Step 2: Build the ordering | |
| 1288 # Remove the revisions with no dependency(A) and add them to the ordering. | |
| 1289 # Removing these revisions leads to new revisions with no dependency (the | |
| 1290 # one depending on A) that we can remove from the dependency graph and add | |
| 1291 # to the ordering. We progress in a similar fashion until the ordering is | |
| 1292 # built | |
| 1293 solvablerevs = collections.deque([r for r in sorted(dependencies.keys()) | |
| 1294 if not dependencies[r]]) | |
| 1295 ordering = [] | |
| 1296 while solvablerevs: | |
| 1297 rev = solvablerevs.popleft() | |
| 1298 for dependent in rdependencies[rev]: | |
| 1299 dependencies[dependent].remove(rev) | |
| 1300 if not dependencies[dependent]: | |
| 1301 solvablerevs.append(dependent) | |
| 1302 ordering.append(rev) | |
| 1303 | |
| 1304 return ordering | |
| 1305 | |
| 1235 @command('^evolve|stabilize|solve', | 1306 @command('^evolve|stabilize|solve', |
| 1236 [('n', 'dry-run', False, | 1307 [('n', 'dry-run', False, |
| 1237 'do not perform actions, just print what would be done'), | 1308 'do not perform actions, just print what would be done'), |
| 1238 ('', 'confirm', False, | 1309 ('', 'confirm', False, |
| 1239 'ask for confirmation before performing the action'), | 1310 'ask for confirmation before performing the action'), |
| 1305 if not _revs: | 1376 if not _revs: |
| 1306 ui.write_err("No troubled changes in the specified revisions\n") | 1377 ui.write_err("No troubled changes in the specified revisions\n") |
| 1307 else: | 1378 else: |
| 1308 # For the progress bar to show | 1379 # For the progress bar to show |
| 1309 count = len(_revs) | 1380 count = len(_revs) |
| 1381 # Order the revisions | |
| 1382 _revs = orderrevs(repo, _revs) | |
| 1310 for rev in _revs: | 1383 for rev in _revs: |
| 1311 progresscb() | 1384 progresscb() |
| 1312 _solveone(ui, repo, repo[rev], dryrunopt, confirmopt, | 1385 _solveone(ui, repo, repo[rev], dryrunopt, confirmopt, |
| 1313 progresscb) | 1386 progresscb) |
| 1314 seen += 1 | 1387 seen += 1 |