# HG changeset patch
# User pacien <pacien.trangirard@pacien.net>
# Date 2023-03-30 20:22:44
# Node ID f0d2b18f0274b7d68788b1014c55834562dc4bb3
# Parent  9fa3cda7449e1f2b576d3a8034c070c1e8e61681

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.

diff --git a/mercurial/debugcommands.py b/mercurial/debugcommands.py
--- a/mercurial/debugcommands.py
+++ b/mercurial/debugcommands.py
@@ -93,6 +93,7 @@ from . import (
     wireprotoserver,
 )
 from .interfaces import repository
+from .stabletailgraph import stabletailsort
 from .utils import (
     cborutil,
     compression,
@@ -3644,6 +3645,30 @@ def debugssl(ui, repo, source=None, **op
 
 
 @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",
     [
         (
diff --git a/mercurial/stabletailgraph/__init__.py b/mercurial/stabletailgraph/__init__.py
new file mode 100644
diff --git a/mercurial/stabletailgraph/stabletailsort.py b/mercurial/stabletailgraph/stabletailsort.py
new file mode 100644
--- /dev/null
+++ b/mercurial/stabletailgraph/stabletailsort.py
@@ -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
diff --git a/setup.py b/setup.py
--- a/setup.py
+++ b/setup.py
@@ -1299,6 +1299,7 @@ packages = [
     'mercurial.hgweb',
     'mercurial.interfaces',
     'mercurial.pure',
+    'mercurial.stabletailgraph',
     'mercurial.templates',
     'mercurial.thirdparty',
     'mercurial.thirdparty.attr',
diff --git a/tests/test-completion.t b/tests/test-completion.t
--- a/tests/test-completion.t
+++ b/tests/test-completion.t
@@ -78,6 +78,7 @@ Show debug commands if there are no othe
   debug-repair-issue6528
   debug-revlog-index
   debug-revlog-stats
+  debug::stable-tail-sort
   debugancestor
   debugantivirusrunning
   debugapplystreamclonebundle
@@ -273,6 +274,7 @@ Show all commands + options
   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: 
diff --git a/tests/test-help.t b/tests/test-help.t
--- a/tests/test-help.t
+++ b/tests/test-help.t
@@ -987,6 +987,8 @@ Test list of internal help commands
                  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
diff --git a/tests/test-stabletailgraph.t b/tests/test-stabletailgraph.t
new file mode 100644
--- /dev/null
+++ b/tests/test-stabletailgraph.t
@@ -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 ..