test-stabletailgraph.t
710 lines
| 14.1 KiB
| text/troff
|
Tads3Lexer
/ tests / test-stabletailgraph.t
|
r51288 | ==================================== | ||
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 .. | ||||