[PATCH 1 of 3 evolve-ext-V2] evolve: add ordering of the revisions for evolve --rev

Laurent Charignon lcharignon at fb.com
Thu Jun 4 11:54:08 CDT 2015


> On Jun 4, 2015, at 9:19 AM, Pierre-Yves David <pierre-yves.david at ens-lyon.org> wrote:
> 
> 
> 
> On 06/03/2015 02:04 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 16e32f9b706fa06a5a3c88e8a26139bfd128f4bf
>> # 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.
> 
> We are getting there. I will take a version with fixed docstring, see below (and discuss).
> 
>> 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,69 @@
>>      if repo['.'] != startnode:
>>          ui.status(_('working directory is now at %s\n') % repo['.'])
>> 
>> +def _singlesuccessor(repo, p):
> 
> This function is non trivial and need a docstring explaining what is its purpose (returning the one unique latest successors of 'p' or die trying.)
> 
>> +    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
>> +
>> +    First we compute dependencies between the revs.
>> +    For each troubled revision we keep track of what instability if any should
>> +    be resolved in order to resolve it.
>> +
>> +    Then we 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 build
>> +    """
> 
> That docstring is full of good inforation, however it a bit too low level for a docstring. Most of it should be moved as inline comment (#). The goal of the docstring is to carry the 'contract' of the function, its high level goal. The current content is details about the implementation.
> 
> What this function do is something along the line of
> 
> - return revision from the bottom to the top of the -final- stack that the stabilization process will produce.
> 
> And this important because:
> 
> - This ensure we can stabilize each revision on its final destination. (or phrased the other way. final destination is always available when we process a revision)

Ok

> 
>> +    # 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)
>> +
>> +    # Step 1: Build the dependency graph
>> +    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
>> +    solvablerevs = collections.deque([ r for r in sorted(dependencies.keys())\
>> +                                         if len(dependencies[r]) == 0 ])
> 
> Small nits:
> - you could use a heap, they are sorted by definition
> - You may want to use a stack instead this would give some of the 'one branch after the other' property for free.

I think that it is the best option, let's go for that

> - you can use dependencies.items() to get both key value in the same go

Yes but it makes the sorting code more complicated if we don't go with the heap.

> - Python style recommendation is to use `if not dep[r]` instead of checking len to 0

Ok

> 
>> +    ordering = []
>> +    while solvablerevs:
>> +        rev = solvablerevs.popleft()
>> +        for dependent in rdependencies[rev]:
>> +            dependencies[dependent].remove(rev)
>> +            if len(dependencies[dependent]) == 0:
> 
> (ditto, small nits, regarding len usage here)
> 
>> +                solvablerevs.append(dependent)
>> +        ordering.append(rev)
> 
> V2 looks simpler and more efficient, nice job.
> 
> -- 
> Pierre-Yves David



More information about the Mercurial-devel mailing list