stablesort: move into the stablerange module
The stable range rely on the stable sort so it make senses to move it there.
Will need direct access to it in the future.
--- a/hgext3rd/evolve/obsdiscovery.py Wed Mar 22 03:49:40 2017 +0100
+++ b/hgext3rd/evolve/obsdiscovery.py Sun Mar 19 03:06:53 2017 +0100
@@ -22,7 +22,6 @@
import io
StringIO = io.StringIO
-import collections
import hashlib
import heapq
import math
@@ -30,8 +29,6 @@
from mercurial import (
bundle2,
- cmdutil,
- commands,
dagutil,
error,
exchange,
@@ -380,105 +377,6 @@
op.records.add('_donotusemeever_evoext_obshashrange_1', {'key': key, 'value': rhash})
data = inpart.read(44)
-##################################
-### Stable topological sorting ###
-##################################
-@eh.command(
- 'debugstablesort',
- [
- ('', 'rev', [], 'heads to start from'),
- ] + commands.formatteropts,
- _(''))
-def debugstablesort(ui, repo, **opts):
- """display the ::REVS set topologically sorted in a stable way
- """
- revs = scmutil.revrange(repo, opts['rev'])
- displayer = cmdutil.show_changeset(ui, repo, opts, buffered=True)
- for r in _stablesort(repo, revs):
- ctx = repo[r]
- displayer.show(ctx)
- displayer.flush(ctx)
- displayer.close()
-
-def _stablesort(repo, revs):
- """return '::revs' topologically sorted in "stable" order
-
- This is a depth first traversal starting from 'nullrev', using node as a
- tie breaker.
- """
- # Various notes:
- #
- # * Bitbucket is used dates as tie breaker, that might be a good idea.
- #
- # * It seemds we can traverse in the same order from (one) head to bottom,
- # if we the following record data for each merge:
- #
- # - highest (stablesort-wise) common ancestors,
- # - order of parents (tablesort-wise)
- cl = repo.changelog
- parents = cl.parentrevs
- nullrev = node.nullrev
- n = cl.node
- # step 1: We need a parents -> children mapping for 2 reasons.
- #
- # * we build the order from nullrev to tip
- #
- # * we need to detect branching
- children = collections.defaultdict(list)
- for r in cl.ancestors(revs, inclusive=True):
- p1, p2 = parents(r)
- children[p1].append(r)
- if p2 != nullrev:
- children[p2].append(r)
- # step two: walk back up
- # * pick lowest node in case of branching
- # * stack disregarded part of the branching
- # * process merge when both parents are yielded
-
- # track what changeset has been
- seen = [0] * (max(revs) + 2)
- seen[-1] = True # nullrev is known
- # starts from repository roots
- # reuse the list form the mapping as we won't need it again anyway
- stack = children[nullrev]
- if not stack:
- return []
- if 1 < len(stack):
- stack.sort(key=n, reverse=True)
-
- # list of rev, maybe we should yield, but since we built a children mapping we are 'O(N)' already
- result = []
-
- current = stack.pop()
- while current is not None or stack:
- if current is None:
- # previous iteration reached a merge or an unready merge,
- current = stack.pop()
- if seen[current]:
- current = None
- continue
- p1, p2 = parents(current)
- if not (seen[p1] and seen[p2]):
- # we can't iterate on this merge yet because other child is not
- # yielded yet (and we are topo sorting) we can discard it for now
- # because it will be reached from the other child.
- current = None
- continue
- assert not seen[current]
- seen[current] = True
- result.append(current) # could be yield, cf earlier comment
- cs = children[current]
- if not cs:
- current = None
- elif 1 == len(cs):
- current = cs[0]
- else:
- cs.sort(key=n, reverse=True)
- current = cs.pop() # proceed on smallest
- stack.extend(cs) # stack the rest for later
- assert len(result) == len(set(result))
- return result
-
##############################
### Range Hash computation ###
##############################
@@ -559,7 +457,7 @@
@util.propertycache
def _revs(self):
- r = _stablesort(self._repo, [self.head])[self.index:]
+ r = stablerange.stablesort(self._repo, [self.head])[self.index:]
assert len(r) == len(self), (self.head, self.index, len(r), len(self))
return r
--- a/hgext3rd/evolve/stablerange.py Wed Mar 22 03:49:40 2017 +0100
+++ b/hgext3rd/evolve/stablerange.py Sun Mar 19 03:06:53 2017 +0100
@@ -7,17 +7,122 @@
# This software may be used and distributed according to the terms of the
# GNU General Public License version 2 or any later version.
+import collections
from mercurial import (
+ commands,
+ cmdutil,
localrepo,
node as nodemod,
+ scmutil,
)
+from mercurial.i18n import _
+
from . import (
exthelper,
)
eh = exthelper.exthelper()
+##################################
+### Stable topological sorting ###
+##################################
+@eh.command(
+ 'debugstablesort',
+ [
+ ('', 'rev', [], 'heads to start from'),
+ ] + commands.formatteropts,
+ _(''))
+def debugstablesort(ui, repo, **opts):
+ """display the ::REVS set topologically sorted in a stable way
+ """
+ revs = scmutil.revrange(repo, opts['rev'])
+ displayer = cmdutil.show_changeset(ui, repo, opts, buffered=True)
+ for r in stablesort(repo, revs):
+ ctx = repo[r]
+ displayer.show(ctx)
+ displayer.flush(ctx)
+ displayer.close()
+
+def stablesort(repo, revs):
+ """return '::revs' topologically sorted in "stable" order
+
+ This is a depth first traversal starting from 'nullrev', using node as a
+ tie breaker.
+ """
+ # Various notes:
+ #
+ # * Bitbucket is used dates as tie breaker, that might be a good idea.
+ #
+ # * It seemds we can traverse in the same order from (one) head to bottom,
+ # if we the following record data for each merge:
+ #
+ # - highest (stablesort-wise) common ancestors,
+ # - order of parents (tablesort-wise)
+ cl = repo.changelog
+ parents = cl.parentrevs
+ nullrev = nodemod.nullrev
+ n = cl.node
+ # step 1: We need a parents -> children mapping for 2 reasons.
+ #
+ # * we build the order from nullrev to tip
+ #
+ # * we need to detect branching
+ children = collections.defaultdict(list)
+ for r in cl.ancestors(revs, inclusive=True):
+ p1, p2 = parents(r)
+ children[p1].append(r)
+ if p2 != nullrev:
+ children[p2].append(r)
+ # step two: walk back up
+ # * pick lowest node in case of branching
+ # * stack disregarded part of the branching
+ # * process merge when both parents are yielded
+
+ # track what changeset has been
+ seen = [0] * (max(revs) + 2)
+ seen[-1] = True # nullrev is known
+ # starts from repository roots
+ # reuse the list form the mapping as we won't need it again anyway
+ stack = children[nullrev]
+ if not stack:
+ return []
+ if 1 < len(stack):
+ stack.sort(key=n, reverse=True)
+
+ # list of rev, maybe we should yield, but since we built a children mapping we are 'O(N)' already
+ result = []
+
+ current = stack.pop()
+ while current is not None or stack:
+ if current is None:
+ # previous iteration reached a merge or an unready merge,
+ current = stack.pop()
+ if seen[current]:
+ current = None
+ continue
+ p1, p2 = parents(current)
+ if not (seen[p1] and seen[p2]):
+ # we can't iterate on this merge yet because other child is not
+ # yielded yet (and we are topo sorting) we can discard it for now
+ # because it will be reached from the other child.
+ current = None
+ continue
+ assert not seen[current]
+ seen[current] = True
+ result.append(current) # could be yield, cf earlier comment
+ cs = children[current]
+ if not cs:
+ current = None
+ elif 1 == len(cs):
+ current = cs[0]
+ else:
+ cs.sort(key=n, reverse=True)
+ current = cs.pop() # proceed on smallest
+ stack.extend(cs) # stack the rest for later
+ assert len(result) == len(set(result))
+ return result
+
class stablerangecache(dict):
def __init__(self):