changeset 3243:556316fe4b4f

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 ###
-##################################
[e-mail](
-    '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 <[e-mail]>
+#
+# 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)
+
[e-mail](
+    '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