[PATCH 2 of 4 evolve-ext] evolve: add ordering of the revisions for evolve --rev
Laurent Charignon
lcharignon at fb.com
Wed Jun 3 15:33:02 CDT 2015
> On Jun 3, 2015, at 1:04 PM, Pierre-Yves David <pierre-yves.david at ens-lyon.org> wrote:
>
>
>
> On 06/02/2015 04:01 PM, Laurent Charignon wrote:
>> # 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
>
> We have to define optimaly here. we also have to write in with two 'l' (optimally)
>
>> +
>> + """
>> + ui = repo.ui
>> + def _nonobsoletesuccessor(p):
>
> We actively avoid closure except when there is a very good reason, having them in the function scope make thing harder to read, maintain and extend. Please move this to real function (and add a docstring)
>
> Could that be name '_singlesuccessor' to mirror 'successorssets'? and 'singlerev'
>
>> + 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"))
>
> (unrelated to your patch since it existed before)
>
> This message could use some information (like what changeset we were trying to evolve and the potential destinations).
>
> I also think We should also move that to skipping instead of aborting.
>
>> + return repo[newer[0][0]].rev()
>> +
>> +
>> + def addlink(a,b):
>> + """ Add a link between a and b in the dependency graph
>
> Small growling about closure, this one looks more legitimate though because it looks like a small helper to double add a value
>
>> +
>> + Only adds the link if b is troubles"""
>> + if b in revs and b is not None:
>
> But then I'm a bit surprised to see this business check here.
- I understand, I started putting it below but it just adds 4 ifs and makes the code much harder to read.
- I test explicitly against None as we know that None will be frequent because of "p2 = parents[1].rev() if len(parents) > 1 else None", since we don't expect None in revs let's remove it you are right, I thought it made the code path for that case more legible
>
> Can we have None in revs?
>
>> + 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))
>
> I'm a bit surprise to see both the parent and '_nonobsoletesuccessor' here. Why do we care about p1 if it is already obsolete? and why doesn't '_nonobsoletesuccessor(X)' return X if X is not obsolete?
It is an excellent idea, I will use it for V2 and that will address the other concern you have above
>
> we could also use a for loop to avoid the duplicated list.
>
> for p in repo[r].parents():
> bla
> bla
> bla
>
> These both step would have the sweet side effect of making this closure irrelevant.
:) Awesome
>
>> +
>> + # 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))
>
> Why don't you put the < in the while conditional?
Because, let's say that we end up with len(ordering) > len(revs) it would stop the conditional and we would still have to fail after with an error, it saves a line
>
>> + 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:
>
> This search is potentially going to be N². We could have a set of rev with no dependency such set being emptied when we build the dependency graph and slowly refilled when we drop dependency, later in this loop.
>
> This could simplify the while loop condition as you keep working until no revision are available.
Good idea
>
>> + # No dependency left on this rev, cleanup dependents
>> + for rdependency in rdependencies[rev]:
>> + dependencies[rdependency].remove(rev)
>
> This is the point were we could detect newly 'available' revision.
>
>> + # 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
>
> small nit: You can probably mark a whole test section for that
>
> If you have a lot of them coming, I'm okay with a dedicated test file for this case.
>
> evolve --rev reordering
> -----------------------
ok
>
> trivial case, 2 rev provided in the 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
>
> --
> Pierre-Yves David
More information about the Mercurial-devel
mailing list