# HG changeset patch # User Pierre-Yves David # Date 1511643909 18000 # Node ID 774f69d74ec29509a7a07d5ef6fc86e6c38af4a0 # Parent 85160bd3f641039b86254c98c5668fe7d1bd3193 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. diff -r 85160bd3f641 -r 774f69d74ec2 hgext3rd/evolve/stablerange.py --- 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 @@ , skipping the 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): diff -r 85160bd3f641 -r 774f69d74ec2 hgext3rd/evolve/stablesort.py --- 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, } diff -r 85160bd3f641 -r 774f69d74ec2 tests/test-stablesort-criss-cross.t --- 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 () { diff -r 85160bd3f641 -r 774f69d74ec2 tests/test-stablesort.t --- 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