<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
</head>
<body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">
<br class="">
<div>
<blockquote type="cite" class="">
<div class="">On Jun 4, 2015, at 10:00 AM, Pierre-Yves David <<a href="mailto:pierre-yves.david@ens-lyon.org" class="">pierre-yves.david@ens-lyon.org</a>> wrote:</div>
<br class="Apple-interchange-newline">
<div class=""><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">On
06/04/2015 09:54 AM, Laurent Charignon wrote:</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<blockquote type="cite" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<br class="">
<blockquote type="cite" class="">On Jun 4, 2015, at 9:19 AM, Pierre-Yves David <<a href="mailto:pierre-yves.david@ens-lyon.org" class="">pierre-yves.david@ens-lyon.org</a>> wrote:<br class="">
<br class="">
<br class="">
<br class="">
On 06/03/2015 02:04 PM, Laurent Charignon wrote:<br class="">
<blockquote type="cite" class=""># HG changeset patch<br class="">
# User Laurent Charignon <<a href="mailto:lcharignon@fb.com" class="">lcharignon@fb.com</a>><br class="">
# Date 1433283749 25200<br class="">
# Tue Jun 02 15:22:29 2015 -0700<br class="">
# Node ID 16e32f9b706fa06a5a3c88e8a26139bfd128f4bf<br class="">
# Parent b4a62d6f03534de6e65962c0e92cadea4b6cbad1<br class="">
evolve: add ordering of the revisions for evolve --rev<br class="">
<br class="">
When running evolve --rev we want to process the revisions in an optimal fashion<br class="">
to solve the maximum amount of trouble in the minimum number of steps.<br class="">
This patch adds a step to evolve --rev to order the revision before solving<br class="">
the troubles. A simple test is added to cover a basic case.<br class="">
</blockquote>
<br class="">
We are getting there. I will take a version with fixed docstring, see below (and discuss).<br class="">
<br class="">
<blockquote type="cite" class="">diff --git a/hgext/evolve.py b/hgext/evolve.py<br class="">
--- a/hgext/evolve.py<br class="">
+++ b/hgext/evolve.py<br class="">
@@ -28,6 +28,7 @@<br class="">
from StringIO import StringIO<br class="">
import struct<br class="">
import re<br class="">
+import collections<br class="">
import socket<br class="">
import errno<br class="">
sha1re = re.compile(r'\b[0-9a-f]{6,40}\b')<br class="">
@@ -1232,6 +1233,69 @@<br class="">
if repo['.'] != startnode:<br class="">
ui.status(_('working directory is now at %s\n') % repo['.'])<br class="">
<br class="">
+def _singlesuccessor(repo, p):<br class="">
</blockquote>
<br class="">
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.)<br class="">
<br class="">
<blockquote type="cite" class="">+ if not p.obsolete():<br class="">
+ return p<br class="">
+ obs = repo[p]<br class="">
+ ui = repo.ui<br class="">
+ newer = obsolete.successorssets(repo, obs.node())<br class="">
+ # search of a parent which is not killed<br class="">
+ while not newer or newer == [()]:<br class="">
+ ui.debug("stabilize target %s is plain dead,"<br class="">
+ " trying to stabilize on its parent\n" %<br class="">
+ obs)<br class="">
+ obs = obs.parents()[0]<br class="">
+ newer = obsolete.successorssets(repo, obs.node())<br class="">
+ if len(newer) > 1:<br class="">
+ raise util.Abort(_("conflict rewriting. can't choose destination\n"))<br class="">
+ return repo[newer[0][0]].rev()<br class="">
+<br class="">
+def orderrevs(repo, revs):<br class="">
+ """ Compute an ordering to solve instability for the given revs<br class="">
+<br class="">
+ - Takes revs a list of troubled revisions<br class="">
+ - Returns the same revisions ordered to solve their instability<br class="">
+<br class="">
+ First we compute dependencies between the revs.<br class="">
+ For each troubled revision we keep track of what instability if any should<br class="">
+ be resolved in order to resolve it.<br class="">
+<br class="">
+ Then we remove the revisions with no dependency(A) and add them to the<br class="">
+ ordering.<br class="">
+ Removing these revisions leads to new revisions with no dependency (the one<br class="">
+ depending on A) that we can remove from the dependency graph and add to the<br class="">
+ ordering. We progress in a similar fashion until the ordering is build<br class="">
+ """<br class="">
</blockquote>
<br class="">
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.<br class="">
<br class="">
What this function do is something along the line of<br class="">
<br class="">
- return revision from the bottom to the top of the -final- stack that the stabilization process will produce.<br class="">
<br class="">
And this important because:<br class="">
<br class="">
- 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)<br class="">
</blockquote>
<br class="">
Ok<br class="">
<br class="">
<blockquote type="cite" class=""><br class="">
<blockquote type="cite" class="">+ # dependencies = {3: [6], 6:[]}<br class="">
+ # Means that: 6 has no dependency, 3 depends on 6 to be solved<br class="">
+ dependencies = {}<br class="">
+ # rdependencies is the inverted dict of dependencies<br class="">
+ rdependencies = collections.defaultdict(set)<br class="">
+<br class="">
+ # Step 1: Build the dependency graph<br class="">
+ for r in revs:<br class="">
+ dependencies[r] = set()<br class="">
+ for p in repo[r].parents():<br class="">
+ succ = _singlesuccessor(repo, p)<br class="">
+ if succ in revs:<br class="">
+ dependencies[r].add(succ)<br class="">
+ rdependencies[succ].add(r)<br class="">
+<br class="">
+ # Step 2: Build the ordering<br class="">
+ solvablerevs = collections.deque([ r for r in sorted(dependencies.keys())\<br class="">
+ if len(dependencies[r]) == 0 ])<br class="">
</blockquote>
<br class="">
Small nits:<br class="">
- you could use a heap, they are sorted by definition<br class="">
- You may want to use a stack instead this would give some of the 'one branch after the other' property for free.<br class="">
</blockquote>
<br class="">
I think that it is the best option, let's go for that<br class="">
</blockquote>
<br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">I
think I would be happy to take this patch as is (with fixed docstring) and take code refactor in another patch. To make the topic move forward.</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<blockquote type="cite" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<blockquote type="cite" class="">- you can use dependencies.items() to get both key value in the same go<br class="">
</blockquote>
<br class="">
Yes but it makes the sorting code more complicated if we don't go with the heap.<br class="">
</blockquote>
<br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">does
it?</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">[key
for key, value in sorted(dependencies.keys()) if value]</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
</div>
</blockquote>
<div><br class="">
</div>
<div>That does not work but solvablerevs = [ r for (r, d) in sorted(dependencies.items()) if not d] does</div>
<br class="">
<blockquote type="cite" class="">
<div class=""><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">(other
nit, not space inside (), [] amd {})</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
</div>
</blockquote>
Ok<br class="">
<blockquote type="cite" class="">
<div class=""><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<blockquote type="cite" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<blockquote type="cite" class="">- Python style recommendation is to use `if not dep[r]` instead of checking len to 0<br class="">
</blockquote>
<br class="">
Ok<br class="">
<br class="">
<blockquote type="cite" class=""><br class="">
<blockquote type="cite" class="">+ ordering = []<br class="">
+ while solvablerevs:<br class="">
+ rev = solvablerevs.popleft()<br class="">
+ for dependent in rdependencies[rev]:<br class="">
+ dependencies[dependent].remove(rev)<br class="">
+ if len(dependencies[dependent]) == 0:<br class="">
</blockquote>
<br class="">
(ditto, small nits, regarding len usage here)<br class="">
<br class="">
<blockquote type="cite" class="">+ solvablerevs.append(dependent)<br class="">
+ ordering.append(rev)<br class="">
</blockquote>
<br class="">
V2 looks simpler and more efficient, nice job.<br class="">
<br class="">
--<br class="">
Pierre-Yves David<br class="">
</blockquote>
<br class="">
</blockquote>
<br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">--<span class="Apple-converted-space"> </span></span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">Pierre-Yves
David</span></div>
</blockquote>
</div>
<br class="">
</body>
</html>