# HG changeset patch # User Pierre-Yves David # Date 1489889213 -3600 # Node ID d07bb7cbae2fa1e0e7ca2839090e703ff7b3ec37 # Parent 318aba30dec354d79ab5148930b6a0da8d69c699 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. diff -r 318aba30dec3 -r d07bb7cbae2f hgext3rd/evolve/obsdiscovery.py --- 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 diff -r 318aba30dec3 -r d07bb7cbae2f hgext3rd/evolve/stablerange.py --- 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):