Mercurial > evolve
changeset 2129:d07bb7cbae2f
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.
| author | Pierre-Yves David <pierre-yves.david@ens-lyon.org> |
|---|---|
| date | Sun, 19 Mar 2017 03:06:53 +0100 |
| parents | 318aba30dec3 |
| children | d784622dd5dc |
| files | hgext3rd/evolve/obsdiscovery.py hgext3rd/evolve/stablerange.py |
| diffstat | 2 files changed, 106 insertions(+), 103 deletions(-) [+] |
line wrap: on
line diff
--- 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):