Mercurial > hg
changeset 50426:f0d2b18f0274
stabletailgraph: implement stable-tail sort
This adds the computation of the "stable-tail sort", an incremental node
sorting method. It is a stepping stone for the implementation of faster
label discovery (for example for obs markers) and more caching.
| author | pacien <pacien.trangirard@pacien.net> |
|---|---|
| date | Thu, 30 Mar 2023 22:22:44 +0200 |
| parents | 9fa3cda7449e |
| children | 98fc949bec14 |
| files | mercurial/debugcommands.py mercurial/stabletailgraph/__init__.py mercurial/stabletailgraph/stabletailsort.py setup.py tests/test-completion.t tests/test-help.t tests/test-stabletailgraph.t |
| diffstat | 6 files changed, 850 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- a/mercurial/debugcommands.py Wed Apr 05 16:09:08 2023 +0200 +++ b/mercurial/debugcommands.py Thu Mar 30 22:22:44 2023 +0200 @@ -93,6 +93,7 @@ wireprotoserver, ) from .interfaces import repository +from .stabletailgraph import stabletailsort from .utils import ( cborutil, compression, @@ -3644,6 +3645,30 @@ @command( + b'debug::stable-tail-sort', + [ + ( + b'T', + b'template', + b'{rev}\n', + _(b'display with template'), + _(b'TEMPLATE'), + ), + ], + b'REV', +) +def debug_stable_tail_sort(ui, repo, revspec, template, **opts): + """display the stable-tail sort of the ancestors of a given node""" + rev = logcmdutil.revsingle(repo, revspec).rev() + cl = repo.changelog + + displayer = logcmdutil.maketemplater(ui, repo, template) + sorted_revs = stabletailsort._stable_tail_sort(cl, rev) + for ancestor_rev in sorted_revs: + displayer.show(repo[ancestor_rev]) + + +@command( b"debugbackupbundle", [ (
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/mercurial/stabletailgraph/stabletailsort.py Thu Mar 30 22:22:44 2023 +0200 @@ -0,0 +1,110 @@ +# stabletailsort.py - stable ordering of revisions +# +# Copyright 2021-2023 Pacien TRAN-GIRARD <pacien.trangirard@pacien.net> +# +# This software may be used and distributed according to the terms of the +# GNU General Public License version 2 or any later version. + +""" +Stable-tail sort computation. + +The "stable-tail sort", or STS, is a reverse topological ordering of the +ancestors of a node, which tends to share large suffixes with the stable-tail +sort of ancestors and other nodes, giving it its name. + +Its properties should make it suitable for making chunks of ancestors with high +reuse and incrementality for example. + +This module and implementation are experimental. Most functions are not yet +optimised to operate on large production graphs. +""" + +import itertools +from ..node import nullrev +from .. import ancestor + + +def _sorted_parents(cl, p1, p2): + """ + Chooses and returns the pair (px, pt) from (p1, p2). + + Where + "px" denotes the parent starting the "exclusive" part, and + "pt" denotes the parent starting the "Tail" part. + + "px" is chosen as the parent with the lowest rank with the goal of + minimising the size of the exclusive part and maximise the size of the + tail part, hopefully reducing the overall complexity of the stable sort. + + In case of equal ranks, the stable node ID is used as a tie-breaker. + """ + r1, r2 = cl.fast_rank(p1), cl.fast_rank(p2) + if r1 < r2: + return (p1, p2) + elif r1 > r2: + return (p2, p1) + elif cl.node(p1) < cl.node(p2): + return (p1, p2) + else: + return (p2, p1) + + +def _nonoedipal_parent_revs(cl, rev): + """ + Returns the non-œdipal parent pair of the given revision. + + An œdipal merge is a merge with parents p1, p2 with either + p1 in ancestors(p2) or p2 in ancestors(p1). + In the first case, p1 is the œdipal parent. + In the second case, p2 is the œdipal parent. + + Œdipal edges start empty exclusive parts. They do not bring new ancestors. + As such, they can be skipped when computing any topological sort or any + iteration over the ancestors of a node. + + The œdipal edges are eliminated here using the rank information. + """ + p1, p2 = cl.parentrevs(rev) + if p1 == nullrev or cl.fast_rank(p2) == cl.fast_rank(rev) - 1: + return p2, nullrev + elif p2 == nullrev or cl.fast_rank(p1) == cl.fast_rank(rev) - 1: + return p1, nullrev + else: + return p1, p2 + + +def _stable_tail_sort(cl, head_rev): + """ + Naive topological iterator of the ancestors given by the stable-tail sort. + + The stable-tail sort of a node "h" is defined as the sequence: + sts(h) := [h] + excl(h) + sts(pt(h)) + where excl(h) := u for u in sts(px(h)) if u not in ancestors(pt(h)) + + This implementation uses a call-stack whose size is + O(number of open merges). + + As such, this implementation exists mainly as a defining reference. + """ + cursor_rev = head_rev + while cursor_rev != nullrev: + yield cursor_rev + + p1, p2 = _nonoedipal_parent_revs(cl, cursor_rev) + if p1 == nullrev: + cursor_rev = p2 + elif p2 == nullrev: + cursor_rev = p1 + else: + px, pt = _sorted_parents(cl, p1, p2) + + tail_ancestors = ancestor.lazyancestors( + cl.parentrevs, (pt,), inclusive=True + ) + exclusive_ancestors = ( + a for a in _stable_tail_sort(cl, px) if a not in tail_ancestors + ) + + excl_part_size = cl.fast_rank(cursor_rev) - cl.fast_rank(pt) - 1 + yield from itertools.islice(exclusive_ancestors, excl_part_size) + cursor_rev = pt
--- a/setup.py Wed Apr 05 16:09:08 2023 +0200 +++ b/setup.py Thu Mar 30 22:22:44 2023 +0200 @@ -1299,6 +1299,7 @@ 'mercurial.hgweb', 'mercurial.interfaces', 'mercurial.pure', + 'mercurial.stabletailgraph', 'mercurial.templates', 'mercurial.thirdparty', 'mercurial.thirdparty.attr',
--- a/tests/test-completion.t Wed Apr 05 16:09:08 2023 +0200 +++ b/tests/test-completion.t Thu Mar 30 22:22:44 2023 +0200 @@ -78,6 +78,7 @@ debug-repair-issue6528 debug-revlog-index debug-revlog-stats + debug::stable-tail-sort debugancestor debugantivirusrunning debugapplystreamclonebundle @@ -273,6 +274,7 @@ debug-repair-issue6528: to-report, from-report, paranoid, dry-run debug-revlog-index: changelog, manifest, dir, template debug-revlog-stats: changelog, manifest, filelogs, template + debug::stable-tail-sort: template debugancestor: debugantivirusrunning: debugapplystreamclonebundle:
--- a/tests/test-help.t Wed Apr 05 16:09:08 2023 +0200 +++ b/tests/test-help.t Thu Mar 30 22:22:44 2023 +0200 @@ -987,6 +987,8 @@ dump index data for a revlog debug-revlog-stats display statistics about revlogs in the store + debug::stable-tail-sort + display the stable-tail sort of the ancestors of a given node debugancestor find the ancestor revision of two revisions in a given index debugantivirusrunning
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tests/test-stabletailgraph.t Thu Mar 30 22:22:44 2023 +0200 @@ -0,0 +1,710 @@ +==================================== +Test for the stabletailgraph package +==================================== + +This test file contains a bunch of small test graphs with some minimal yet +non-trivial structure, on which the various stable-tail graph and stable-tail +sort functions are tested. + +Each case consists of the creation of the interesting graph structure, followed +by a check, for each noteworthy node, of: +- the stable-tail sort output. + +In the ASCII art of the diagrams, the side of the exclusive part which is +followed in priority is denoted with "<" or ">" if it is on the left or right +respectively. + +The intermediary linear parts in the example graph are there to force the +exclusive part choice (made on a min rank condition). + + +Setup +===== + +Enable the rank computation to test sorting based on the rank. + + $ cat << EOF >> $HGRCPATH + > [format] + > exp-use-changelog-v2=enable-unstable-format-and-corrupt-my-data + > + > [alias] + > test-sts = debug::stable-tail-sort -T '{tags},' + > test-log = log --graph -T '{tags} rank={_fast_rank}' + > EOF + + +Example 1: single merge node +============================ + +A base case with one branchpoint "b" and one merge node "e". + +The exclusive part, starting with the lowest-ranking parent "c" of "e", +appears first in stable-tail sort of "e" and "f". + +# f +# | +# e +# | +# --<-- +# | | +# c d +# | | +# --+-- <- at this point, the sort of "e" is done consuming its +# | exclusive part [c] and jumps back to its other parent "d" +# b +# | +# a + + $ hg init example-1 + $ cd example-1 + $ hg debugbuilddag '.:a*a:b*b:c<b+2:d*c/d:e*e:f.' + $ hg test-log + o tip rank=8 + | + o f rank=7 + | + o e rank=6 + |\ + | o d rank=4 + | | + | o rank=3 + | | + o | c rank=3 + |/ + o b rank=2 + | + o a rank=1 + + +Check the sort of the base linear case. + + $ hg test-sts c + c,b,a, (no-eol) + +Check the stable-tail sort of "e": "c" should come before "d". + + $ hg test-sts e + e,c,d,*,b,a, (no-eol) (glob) + +Check that the linear descendant of the merge inherits its sort properly. + + $ hg test-sts f + f,e,c,d,*,b,a, (no-eol) (glob) + + $ cd .. + + +Example 2: nested exclusive parts, without specific leap +======================================================== + +"g" is a merge node whose exclusive part contains a merge node "e". +We check that the stable-tail sort recurses properly by delegating. + +Notice that parts of the sort of "e" is an infix of the sort of "g". +This is an expected property of the sort. + +# g +# | +# ---<--- +# | | +# e | <- while processing the sort in the exclusive part of "g" +# | | we recursively process the exclusive part of "e" +# --<-- f +# | | | +# c d | +# | | | +# --+-- | +# | | +# b | +# | | +# ---+--- <- done with excl(g), jump to "f" +# | +# a + + $ hg init example-2 + $ cd example-2 + $ hg debugbuilddag '.:a*a:b*b:c<b+2:d*c/d:e<a+6:f*e/f:g.' + $ hg test-log + o tip rank=14 + | + o g rank=13 + |\ + | o f rank=7 + | | + | o rank=6 + | | + | o rank=5 + | | + | o rank=4 + | | + | o rank=3 + | | + | o rank=2 + | | + o | e rank=6 + |\ \ + | o | d rank=4 + | | | + | o | rank=3 + | | | + o | | c rank=3 + |/ / + o / b rank=2 + |/ + o a rank=1 + +Display the sort of "e" for reference + + $ hg test-sts e + e,c,d,*,b,a, (no-eol) (glob) + +Check the correctness of the sort of "g", +and that a part of the sort of "e" appears as an infix. + + $ hg test-sts g + g,e,c,d,*,b,f,*,a, (no-eol) (glob) + + $ cd .. + + +Example 3: shadowing of a final leap +==================================== + +We have a merge "f" whose exclusive part contains a merge "d". + +The inherited parent of "d" is not in the exclusive part of "f". +At the end of the exclusive part of "d", +the leap to "c" is shadowed by the leap to "e", i.e. the inherited part to "f". + +Notice that emitting "c" before "e" would break the reverse topological +ordering. + +# f +# | +# ---<--- +# | | +# d | +# | e +# --<-- | +# | | | +# | +---- +# b | +# | c +# | | +# --+-- <- at this point, jumping to "e", not the shadowed "c" +# | +# a + + $ hg init example-3 + $ cd example-3 + $ hg debugbuilddag '.:a*a:b<a+2:c*b/c:d<c+3:e*d/e:f.' + $ hg test-log + o tip rank=10 + | + o f rank=9 + |\ + | o e rank=6 + | | + | o rank=5 + | | + | o rank=4 + | | + o | d rank=5 + |\| + | o c rank=3 + | | + | o rank=2 + | | + o | b rank=2 + |/ + o a rank=1 + + +Display the sort of "d" for reference: + + $ hg test-sts d + d,b,c,*,a, (no-eol) (glob) + +Check that we leap from "b" directly to "e" (shadowing the leap to "c"), +and that "c" is then emitted after "e" (its descendant). + + $ hg test-sts f + f,d,b,e,*,c,*,a, (no-eol) (glob) + + $ cd .. + + +Example 4: skipping over nested exclusive part (entirely) +========================================================= + +We have a merge "f" whose exclusive part contains a merge "d". + +The exclusive part of "d" is not in the exclusive part of "f". +However, some of the inherited part of "d" is part of the exclusive part of "f" +and needs to be iterated over before leaping to the inherited part of "f". + +The sort of "d" is partially reused for the ordering of the exclusive part of +"f". However the reused part is not contiguous in the sort of "d". + +# f +# | +# ---<--- +# | | +# d | +# | e +# -->-- | <- in the sort of "f", we need to skip "c" and leap to the +# | | | inherited part of "d" +# | +---- +# b | +# | c +# | | +# --+-- +# | +# a + + $ hg init example-4 + $ cd example-4 + $ hg debugbuilddag '.:a*a+1:b<a+1:c*b/c:d<c+4:e*d/e:f.' + $ hg test-log + o tip rank=11 + | + o f rank=10 + |\ + | o e rank=6 + | | + | o rank=5 + | | + | o rank=4 + | | + | o rank=3 + | | + o | d rank=5 + |\| + | o c rank=2 + | | + o | b rank=3 + | | + o | rank=2 + |/ + o a rank=1 + + +Display the sort of "d" for reference: + + $ hg test-sts d + d,c,b,*,a, (no-eol) (glob) + +Chack that sort "f" leaps from "d" to "b": + + $ hg test-sts f + f,d,b,*,e,*,c,a, (no-eol) (glob) + + $ cd .. + + +Example 5: skipping over nested exclusive part (partially) +========================================================== + +We have a merge "f" whose exclusive part contains a merge "d". + +Similar to example 4, but the exclusive part of "d" is only partially +contained in the inherited part of "f". +So, we need to leap in the middle of the exclusive part of "d". + +# f +# | +# ---<--- +# | | +# d | +# | e +# -->-- | +# | | | +# | g | +# | | | +# | +---- <- in the sort of "f", leaping from "g" to "b" +# b | +# | c +# | | +# --+-- +# | +# a + + $ hg init example-5 + $ cd example-5 + $ hg debugbuilddag '.:a*a+2:b<a+1:c+1:g*b/g:d<c+6:e*d/e:f.' + $ hg test-log + o tip rank=15 + | + o f rank=14 + |\ + | o e rank=8 + | | + | o rank=7 + | | + | o rank=6 + | | + | o rank=5 + | | + | o rank=4 + | | + | o rank=3 + | | + o | d rank=7 + |\ \ + | o | g rank=3 + | |/ + | o c rank=2 + | | + o | b rank=4 + | | + o | rank=3 + | | + o | rank=2 + |/ + o a rank=1 + + +Display the sort of "d" for reference: + + $ hg test-sts d + d,g,c,b,*,a, (no-eol) (glob) + +Check that sort "f" leaps from "g" to "b": + + $ hg test-sts f + f,d,g,b,*,e,*,c,a, (no-eol) (glob) + + $ cd .. + + +Example 6: merge in the inherited part +====================================== + +Variant of example 2, but with a merge ("f") in the inherited part of "g". + +"g" is a merge node whose inherited part contains a merge node "f". +We check that the stable-tail sort delegates properly after the exclusive part. + +# g +# | +# ---<--- +# | | +# d f +# | | +# | ---<--- +# | | | +# | e c +# | | | +# ---+ | <- at this point, we're done (for good) with the exclusive +# | | part of "g" +# b | +# | | +# ---+--- +# | +# a + + $ hg init example-6 + $ cd example-6 + $ hg debugbuilddag '.:a*a:b<a+3:c*b:d*b:e*e/c:f*d/f:g.' + $ hg test-log + o tip rank=10 + | + o g rank=9 + |\ + | o f rank=7 + | |\ + | | o e rank=3 + | | | + o---+ d rank=3 + / / + o | c rank=4 + | | + o | rank=3 + | | + o | rank=2 + | | + | o b rank=2 + |/ + o a rank=1 + + +Display the sort of "f" for reference: + + $ hg test-sts f + f,e,b,c,*,a, (no-eol) (glob) + +Check that the sort of "g" delegates to the sort of "f" after processing its +exclusive part of "g": + + $ hg test-sts g + g,d,f,e,b,c,*,a, (no-eol) (glob) + + $ cd .. + + +Example 7: postponed iteration of common exclusive ancestors +============================================================ + +Sibling merges "j" and "k", with partially shared exclusive parts. + +When considering the sort of "l", the iteration over this shared part cannot +happen when iterating over excl(j) and has to be postponed to excl(k). + +# l +# | +# ----<---- +# | | +# j k +# | | +# -->-- --<-- +# | | | | +# g e h i +# | | | | +# | --+-- | <- at this point, for the sort of "l", the iteration on +# f | | the end of excl(j) is postponed to the iteration of +# | d | excl(k) +# | | | +# | c | +# | | | +# ---+--- | +# | | +# b | +# | | +# ----+----- +# | +# a + + $ hg init example-7 + $ cd example-7 + $ hg debugbuilddag \ + > '.:a*a:b*b:c*c:d*d:e*b:f<f+3:g<d+2:h<a+6:i*e/g:j*h/i:k*j/k:l.' + $ hg test-log + o tip rank=21 + | + o l rank=20 + |\ + | o k rank=13 + | |\ + o \ \ j rank=10 + |\ \ \ + | | | o i rank=7 + | | | | + | | | o rank=6 + | | | | + | | | o rank=5 + | | | | + | | | o rank=4 + | | | | + | | | o rank=3 + | | | | + | | | o rank=2 + | | | | + | | o | h rank=6 + | | | | + | | o | rank=5 + | | | | + | o | | g rank=6 + | | | | + | o | | rank=5 + | | | | + | o | | rank=4 + | | | | + | o | | f rank=3 + | | | | + o---+ | e rank=5 + / / / + | o | d rank=4 + | | | + | o | c rank=3 + |/ / + o / b rank=2 + |/ + o a rank=1 + + +Display the sort of "j" for reference: + + $ hg test-sts j + j,e,d,c,g,*,f,b,a, (no-eol) (glob) + +Display the sort of "k" for reference: + + $ hg test-sts k + k,h,*,d,c,b,i,*,a, (no-eol) (glob) + +Check that the common part of excl(j) and excl(k) is iterated over after "k": + + $ hg test-sts l + l,j,e,g,*,f,k,h,*,d,c,b,i,*,a, (no-eol) (glob) + + $ cd .. + + +Example 8: postponed iteration of common ancestors between parts +================================================================ + +Sibling merges "g" and "i", with some part shared between the inherited part +of "g" and the exclusive part of "i". + +When considering the sort of "j", the iteration over this shared part cannot +happen when iterating over inherited(g) and has to be postponed to excl(i). + +# j +# | +# ----<---- +# | | +# g i +# | | +# --<-- --<-- +# | | | | +# c f | h +# | | | | +# | --+-- | <- at this point, for the sort of "j", the iteration +# | | | on the end of inherited(g) is postponed to the +# | e | iteration of excl(k) +# | | | +# ---+--- | +# b | +# | | +# ----+----- +# | +# a + + $ hg init example-8 + $ cd example-8 + $ hg debugbuilddag '.:a*a:b*b:c*b:d*d:e*e:f*c/f:g<a+5:h*e/h:i*g/i:j.' + $ hg test-log + o tip rank=15 + | + o j rank=14 + |\ + | o i rank=10 + | |\ + | | o h rank=6 + | | | + | | o rank=5 + | | | + | | o rank=4 + | | | + | | o rank=3 + | | | + | | o rank=2 + | | | + o | | g rank=7 + |\ \ \ + | o | | f rank=5 + | |/ / + | o | e rank=4 + | | | + | o | d rank=3 + | | | + o | | c rank=3 + |/ / + o / b rank=2 + |/ + o a rank=1 + + +Display the sort of "g" for reference: + + $ hg test-sts g + g,c,f,e,d,b,a, (no-eol) + +Display the sort of "i" for reference: + + $ hg test-sts i + i,e,d,b,h,*,a, (no-eol) (glob) + +Check that the common part of inherited(g) and excl(k) is iterated over after +"i": + + $ hg test-sts j + j,g,c,f,i,e,d,b,h,*,a, (no-eol) (glob) + + $ cd .. + + +Example 9: postponed iteration of common ancestors between both parts +===================================================================== + +This is a combination of example 7 and 8 at the same time. +Both excl(i) and excl(j) share a common part. +Same with inherited(i) and inherited(j). + +We test that the walk on the common ancestors in both cases is properly +postponed when considering sort(k). + +# k +# | +# ----<---- +# | | +# i j +# | | +# --<-- --<-- +# | | | | +# c f g h +# | | | | +# | e | | +# | | | | +# +--]|[--- | <- rest of excl(i) postponed to excl(j) +# | | | +# b ----+---- <- rest of inherited(i) postponed to inherited(j) +# | | +# | d +# | | +# ----+---- +# | +# a + + $ hg init example-9 + $ cd example-9 + $ hg debugbuilddag '.:a*a:b*b:c*a:d*d:e*e:f<b+2:g<d+3:h*c/f:i*g/h:j*i/j:k.' + $ hg test-log + o tip rank=15 + | + o k rank=14 + |\ + | o j rank=9 + | |\ + o \ \ i rank=7 + |\ \ \ + | | | o h rank=5 + | | | | + | | | o rank=4 + | | | | + | | | o rank=3 + | | | | + | | o | g rank=4 + | | | | + | | o | rank=3 + | | | | + | o | | f rank=4 + | | | | + | o---+ e rank=3 + | / / + | | o d rank=2 + | | | + o | | c rank=3 + |/ / + o / b rank=2 + |/ + o a rank=1 + + +Display sort(i) for reference: + + $ hg test-sts i + i,c,b,f,e,d,a, (no-eol) + +Display sort(j) for reference: + + $ hg test-sts j + j,g,*,b,h,*,d,a, (no-eol) (glob) + +Check that the end of excl(i) is postponed to excl(j), the end of inherited(i) +is postponed to inherited(j) in sort(k): + + $ hg test-sts k + k,i,c,f,e,j,g,*,b,h,*,d,a, (no-eol) (glob) + + $ cd ..