stabletailgraph: naive version of leap computation

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.

--- 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 ..