[PATCH 2 of 4 evolve-ext] evolve: add ordering of the revisions for evolve --rev

Pierre-Yves David pierre-yves.david at ens-lyon.org
Wed Jun 3 15:04:12 CDT 2015



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.

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?.

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.

> +
> +    # 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?

> +        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.

> +                # 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
-----------------------

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