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.
--- 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:]
--- /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 <pierre-yves.david@ens-lyon.org>
+#
+# 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