# HG changeset patch # User Pierre-Yves David # Date 1511451290 -3600 # Node ID 556316fe4b4f4c729362dda5d1c6533516891256 # Parent 55e1ad0d71748234fbb382c7f5891e7afb131bf2 stablesort: extract in its own module We are going to introduce variants, cache and more complex logic, we move that in its own repository beforehand. diff -r 55e1ad0d7174 -r 556316fe4b4f hgext3rd/evolve/stablerange.py --- a/hgext3rd/evolve/stablerange.py Wed Nov 29 12:48:45 2017 -0500 +++ b/hgext3rd/evolve/stablerange.py Thu Nov 23 16:34:50 2017 +0100 @@ -7,7 +7,6 @@ # 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 import heapq import math import os @@ -16,8 +15,6 @@ import weakref from mercurial import ( - commands, - cmdutil, error, localrepo, node as nodemod, @@ -29,12 +26,12 @@ from mercurial.i18n import _ from . import ( - depthcache, + stablesort, exthelper, ) eh = exthelper.exthelper() -eh.merge(depthcache.eh) +eh.merge(stablesort.eh) # prior to hg-4.2 there are not util.timer if util.safehasattr(util, 'timer'): @@ -46,106 +43,6 @@ else: timer = time.time -################################## -### 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, mergecallback=None): - """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 - if mergecallback is not None and p2 != nullrev: - mergecallback(result, current) - 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 ################################# ### Stable Range computation ### @@ -369,8 +266,9 @@ if allrevs is None: allrevs = self._getrevsfrommerge(repo, headrev) if allrevs is None: - allrevs = stablesort(repo, [headrev], - mergecallback=self._filestablesortcache) + mc = self._filestablesortcache + allrevs = stablesort.stablesort(repo, [headrev], + mergecallback=mc) self._stablesortcache[headrev] = allrevs # takes from index revs = allrevs[index:] diff -r 55e1ad0d7174 -r 556316fe4b4f hgext3rd/evolve/stablesort.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/hgext3rd/evolve/stablesort.py Thu Nov 23 16:34:50 2017 +0100 @@ -0,0 +1,125 @@ +# Code dedicated to the computation of stable sorting +# +# These stable sorting are used stable ranges +# +# Copyright 2017 Pierre-Yves David +# +# 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, + node as nodemod, + scmutil, +) + +from mercurial.i18n import _ + +from . import ( + depthcache, + exthelper, +) + +eh = exthelper.exthelper() +eh.merge(depthcache.eh) + +@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, mergecallback=None): + """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 + if mergecallback is not None and p2 != nullrev: + mergecallback(result, current) + 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