====================================

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},'

  > 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  f rank=7

  |

  o    e rank=6

  |\

  | o  d rank=4

  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    g rank=13

  |\

  | o  f rank=7

  |\ \

  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    f rank=9

  |\

  | o  e rank=6

  | o  c rank=3

  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    f rank=10

  |\

  | o  e rank=6

  | o  c rank=2

  | |

  o |  b rank=3

  |/

  o  a rank=1

Display the sort of "d" for reference:

  $ hg test-sts d

  d,c,b,*,a, (no-eol) (glob)

Check 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    f rank=14

  |\

  | o  e rank=8

  |\ \

  | o  c rank=2

  | |

  o |  b rank=4

  |/

  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    g rank=9

  |\

  | o    f rank=7

  | |\

  | | o  e rank=3

  | | |

  o---+  d rank=3

   / /

  o |  c rank=4

  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

#            |

#        ----<----

#        |       |