Mercurial Mercurial > pub > hg > evolve / changeset
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | raw | zip | gz | bz2 | help
Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
stablesort: start implementing more advanced version of headstart sorting
authorPierre-Yves David <pierre-yves.david@octobus.net>
Sat, 25 Nov 2017 16:05:09 -0500
changeset 3262 774f69d74ec2
parent 3261 85160bd3f641
child 3263 07678f7a4481
stablesort: start implementing more advanced version of headstart sorting Now that we can validate the sort with a basic implementation, we can start implementing a version that will support caching and other goodies.
hgext3rd/evolve/stablerange.py file | annotate | diff | comparison | revisions
hgext3rd/evolve/stablesort.py file | annotate | diff | comparison | revisions
tests/test-stablesort-criss-cross.t file | annotate | diff | comparison | revisions
tests/test-stablesort.t file | annotate | diff | comparison | revisions 
--- a/hgext3rd/evolve/stablerange.py	Sun Dec 10 01:38:48 2017 +0100
+++ b/hgext3rd/evolve/stablerange.py	Sat Nov 25 16:05:09 2017 -0500
@@ -317,7 +317,7 @@
         <head>, skipping the <index>th lower revisions.
         """
         limit = self.rangelength(repo, rangeid)
-        return stablesort.stablesort_mergepoint_head_basic(repo, [rangeid[0]],
+        return stablesort.stablesort_mergepoint_head_debug(repo, [rangeid[0]],
                                                            limit=limit)
 
 class stablerange(stablerangecached):
--- a/hgext3rd/evolve/stablesort.py	Sun Dec 10 01:38:48 2017 +0100
+++ b/hgext3rd/evolve/stablesort.py	Sat Nov 25 16:05:09 2017 -0500
@@ -245,8 +245,55 @@
         return revs
     return revs[-limit:]
 
+def stablesort_mergepoint_head_debug(repo, revs, limit=None):
+    heads = repo.revs('heads(%ld)', revs)
+    if not heads:
+        return []
+    elif 2 < len(heads):
+        raise error.Abort('cannot use head based merging, %d heads found'
+                          % len(heads))
+    head = heads.first()
+    revs = stablesort_mergepoint_head(repo, head)
+    if limit is None:
+        return revs
+    return revs[-limit:]
+
+def stablesort_mergepoint_head(repo, head):
+    """return '::rev' topologically sorted in "stable" order
+
+    This is a depth first traversal starting from 'rev' (toward root), using node as a
+    tie breaker.
+    """
+    cl = repo.changelog
+    parents = cl.parentrevs
+    tiebreaker = _mergepoint_tie_breaker(repo)
+
+    top = [head]
+    mid = []
+    bottom = []
+
+    ps = [p for p in parents(head) if p is not nodemod.nullrev]
+    while len(ps) == 1:
+        top.append(ps[0])
+        ps = [p for p in parents(ps[0]) if p is not nodemod.nullrev]
+    top.reverse()
+    if len(ps) == 2:
+        ps.sort(key=tiebreaker)
+
+        # get the part from the highest parent. This is the part that changes
+        mid_revs = repo.revs('only(%d, %d)', ps[1], ps[0])
+        if mid_revs:
+            mid = stablesort_mergepoint_bounded(repo, ps[1], mid_revs)
+
+        # And follow up with part othe parent we can inherit from
+        bottom_revs = cl.ancestors([ps[0]], inclusive=True)
+        bottom = stablesort_mergepoint_bounded(repo, ps[0], bottom_revs)
+
+    return bottom + mid + top
+
 _methodmap = {
     'branchpoint': stablesort_branchpoint,
     'basic-mergepoint': stablesort_mergepoint_multirevs,
     'basic-headstart': stablesort_mergepoint_head_basic,
+    'headstart': stablesort_mergepoint_head_debug,
 }
--- a/tests/test-stablesort-criss-cross.t	Sun Dec 10 01:38:48 2017 +0100
+++ b/tests/test-stablesort-criss-cross.t	Sat Nov 25 16:05:09 2017 -0500
@@ -9,7 +9,7 @@
   > [ui]
   > logtemplate = "{rev} {node|short} {desc} {tags}\n"
   > [alias]
-  > showsort = debugstablesort --template="{node|short}\n" --method basic-headstart
+  > showsort = debugstablesort --template="{node|short}\n" --method headstart
   > EOF
 
   $ checktopo () {
--- a/tests/test-stablesort.t	Sun Dec 10 01:38:48 2017 +0100
+++ b/tests/test-stablesort.t	Sat Nov 25 16:05:09 2017 -0500
@@ -10,7 +10,7 @@
   > logtemplate = "{rev} {node|short} {desc} {tags}\n"
   > [alias]
   > showsort = debugstablesort --template="{node|short}\n" --method basic-mergepoint
-  > showsorthead = debugstablesort --template="{node|short}\n" --method basic-headstart
+  > showsorthead = debugstablesort --template="{node|short}\n" --method headstart
   > EOF
evolve