Mercurial > evolve
changeset 3262:774f69d74ec2
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.
| author | Pierre-Yves David <pierre-yves.david@octobus.net> |
|---|---|
| date | Sat, 25 Nov 2017 16:05:09 -0500 |
| parents | 85160bd3f641 |
| children | 07678f7a4481 |
| files | hgext3rd/evolve/stablerange.py hgext3rd/evolve/stablesort.py tests/test-stablesort-criss-cross.t tests/test-stablesort.t |
| diffstat | 4 files changed, 50 insertions(+), 3 deletions(-) [+] |
line wrap: on
line diff
--- 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