comparison tests/test-stabletailgraph.t @ 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.

50426:f0d2b18f0274

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