Mercurial > hg-stable
changeset 50562:8fb3e942473a
stabletailgraph: naive version of leap computation
This adds a naive reference implementation of the computation of leap and
specific leap sets (described in the code documentation).
The existing tests are enriched accordingly.
| author | pacien <pacien.trangirard@pacien.net> |
|---|---|
| date | Fri, 21 Apr 2023 14:33:33 +0200 |
| parents | dc372251d4dc |
| children | 027481f19944 |
| files | mercurial/debugcommands.py mercurial/stabletailgraph/stabletailsort.py tests/test-completion.t tests/test-help.t tests/test-stabletailgraph.t |
| diffstat | 5 files changed, 261 insertions(+), 1 deletions(-) [+] |
line wrap: on
line diff
--- a/mercurial/debugcommands.py Fri Apr 21 16:19:32 2023 +0200 +++ b/mercurial/debugcommands.py Fri Apr 21 14:33:33 2023 +0200 @@ -3677,6 +3677,36 @@ @command( + b'debug::stable-tail-sort-leaps', + [ + ( + b'T', + b'template', + b'{rev}', + _(b'display with template'), + _(b'TEMPLATE'), + ), + (b's', b'specific', False, _(b'restrict to specific leaps')), + ], + b'REV', +) +def debug_stable_tail_sort_leaps(ui, repo, rspec, template, specific, **opts): + """display the leaps in the stable-tail sort of a node, one per line""" + rev = logcmdutil.revsingle(repo, rspec).rev() + + if specific: + get_leaps = stabletailsort._find_specific_leaps_naive + else: + get_leaps = stabletailsort._find_all_leaps_naive + + displayer = logcmdutil.maketemplater(ui, repo, template) + for source, target in get_leaps(repo.changelog, rev): + displayer.show(repo[source]) + displayer.show(repo[target]) + ui.write(b'\n') + + +@command( b"debugbackupbundle", [ (
--- a/mercurial/stabletailgraph/stabletailsort.py Fri Apr 21 16:19:32 2023 +0200 +++ b/mercurial/stabletailgraph/stabletailsort.py Fri Apr 21 14:33:33 2023 +0200 @@ -118,3 +118,55 @@ 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 + + +def _find_all_leaps_naive(cl, head_rev): + """ + Yields the leaps in the stable-tail sort of the given revision. + + A leap is a pair of revisions (source, target) consecutive in the + stable-tail sort of a head, for which target != px(source). + + Leaps are yielded in the same order as encountered in the stable-tail sort, + from head to root. + """ + sts = _stable_tail_sort_naive(cl, head_rev) + prev = next(sts) + for current in sts: + if current != _parents(cl, prev)[0]: + yield (prev, current) + + prev = current + + +def _find_specific_leaps_naive(cl, head_rev): + """ + Returns the specific leaps in the stable-tail sort of the given revision. + + Specific leaps are leaps appear in the stable-tail sort of a given + revision, but not in the stable-tail sort of any of its ancestors. + + The final leaps (leading to the pt of the considered merge) are omitted. + + Only merge nodes can have associated specific leaps. + + This implementations uses the whole leap sets of the given revision and + of its parents. + """ + px, pt = _parents(cl, head_rev) + if px == nullrev or pt == nullrev: + return # linear nodes cannot have specific leaps + + parents_leaps = set(_find_all_leaps_naive(cl, px)) + + sts = _stable_tail_sort_naive(cl, head_rev) + prev = next(sts) + for current in sts: + if current == pt: + break + if current != _parents(cl, prev)[0]: + leap = (prev, current) + if leap not in parents_leaps: + yield leap + + prev = current
--- a/tests/test-completion.t Fri Apr 21 16:19:32 2023 +0200 +++ b/tests/test-completion.t Fri Apr 21 14:33:33 2023 +0200 @@ -79,6 +79,7 @@ debug-revlog-index debug-revlog-stats debug::stable-tail-sort + debug::stable-tail-sort-leaps debugancestor debugantivirusrunning debugapplystreamclonebundle @@ -275,6 +276,7 @@ debug-revlog-index: changelog, manifest, dir, template debug-revlog-stats: changelog, manifest, filelogs, template debug::stable-tail-sort: template + debug::stable-tail-sort-leaps: template, specific debugancestor: debugantivirusrunning: debugapplystreamclonebundle:
--- a/tests/test-help.t Fri Apr 21 16:19:32 2023 +0200 +++ b/tests/test-help.t Fri Apr 21 14:33:33 2023 +0200 @@ -989,6 +989,9 @@ display statistics about revlogs in the store debug::stable-tail-sort display the stable-tail sort of the ancestors of a given node + debug::stable-tail-sort-leaps + display the leaps in the stable-tail sort of a node, one per + line debugancestor find the ancestor revision of two revisions in a given index debugantivirusrunning
--- a/tests/test-stabletailgraph.t Fri Apr 21 16:19:32 2023 +0200 +++ b/tests/test-stabletailgraph.t Fri Apr 21 14:33:33 2023 +0200 @@ -8,7 +8,9 @@ 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 (with the linear parts globbed). +- the stable-tail sort output (with the linear parts globbed), +- the leap set, +- the specific leap set. 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 @@ -29,6 +31,7 @@ > > [alias] > test-sts = debug::stable-tail-sort -T '{tags},' + > test-leaps = debug::stable-tail-sort-leaps -T '{tags}' > test-log = log --graph -T '{tags} rank={_fast_rank}' --rev 'tagged()' > EOF @@ -87,6 +90,27 @@ $ hg test-sts f f,e,c,d,*,b,a, (no-eol) (glob) +Check the leaps of "e": arriving at "c", the sort continues at "d", which +which breaks the child-parent chain and results in a leap. + + $ hg test-leaps e + cd + +Check that this leap is indeed specific to "e", i.e. that it appears in its +stable-tail sort, but not in any stable-tail sort of its ancestors. + + $ hg test-leaps --specific e + +Check that this leap is inherited by its direct ancestor "f". + + $ hg test-leaps f + cd + +Check that this leap is not classified as specific to "f", since it is specific +to "e". + + $ hg test-leaps --specific f + $ cd .. @@ -146,6 +170,23 @@ $ hg test-sts g g,e,c,d,*,b,f,*,a, (no-eol) (glob) +Check the leaps of "e". + + $ hg test-leaps e + cd + + $ hg test-leaps --specific e + +Check that "g" inherits a leap from "e" in addition of its own. + + $ hg test-leaps g + cd + bf + +Check that only the additional leap of "g" is classified as specific. + + $ hg test-leaps --specific g + $ cd .. @@ -205,6 +246,21 @@ $ hg test-sts f f,d,b,e,*,c,*,a, (no-eol) (glob) +Check the leaps of "d". + + $ hg test-leaps d + bc + + $ hg test-leaps --specific d + +Check thet leaps of "f", which, despite being a descendant of "f", has a +different stable-tail sort which does not reuse any leap of "d". + + $ hg test-leaps f + be + + $ hg test-leaps --specific f + $ cd .. @@ -263,6 +319,22 @@ $ hg test-sts f f,d,b,*,e,*,c,a, (no-eol) (glob) +Check the leaps of "d". + + $ hg test-leaps d + cb + + $ hg test-leaps --specific d + +Check the leaps of "f". + + $ hg test-leaps f + db + e* (glob) + + $ hg test-leaps --specific f + db + $ cd .. @@ -322,6 +394,21 @@ $ hg test-sts f f,d,g,b,*,e,*,c,a, (no-eol) (glob) +Check the leaps of "d". + + $ hg test-leaps d + cb + $ hg test-leaps --specific d + +Check the leaps of "f". + + $ hg test-leaps f + gb + e* (glob) + + $ hg test-leaps --specific f + gb + $ cd .. @@ -381,6 +468,21 @@ $ hg test-sts g g,d,f,e,b,c,*,a, (no-eol) (glob) +Check the leaps of "f". + + $ hg test-leaps f + bc + + $ hg test-leaps --specific f + +Check the leaps of "g". + + $ hg test-leaps g + df + bc + + $ hg test-leaps --specific g + $ cd .. @@ -461,6 +563,30 @@ $ hg test-sts l l,j,e,g,*,f,k,h,*,d,c,b,i,*,a, (no-eol) (glob) +Check the leaps of "j". + + $ hg test-leaps j + cg + + $ hg test-leaps --specific j + +Check the leaps of "k". + + $ hg test-leaps k + bi + + $ hg test-leaps --specific k + +Check the leaps of "l". + + $ hg test-leaps l + eg + fk + bi + + $ hg test-leaps --specific l + eg + $ cd .. @@ -535,6 +661,29 @@ $ hg test-sts j j,g,c,f,i,e,d,b,h,*,a, (no-eol) (glob) +Check the leaps of "g". + + $ hg test-leaps g + cf + $ hg test-leaps g + cf + +Check the leaps of "i". + + $ hg test-leaps i + bh + + $ hg test-leaps --specific i + +Check the leaps of "j". + + $ hg test-leaps j + cf + fi + bh + + $ hg test-leaps --specific j + $ cd .. @@ -613,4 +762,28 @@ $ hg test-sts k k,i,c,f,e,j,g,*,b,h,*,d,a, (no-eol) (glob) +Check the leaps of "i". + + $ hg test-leaps i + bf + + $ hg test-leaps --specific i + +Check the leaps of "j". + + $ hg test-leaps j + bh + + $ hg test-leaps --specific j + +Check the leaps of "k". + + $ hg test-leaps k + cf + ej + bh + + $ hg test-leaps --specific k + cf + $ cd ..