chiark - git - mdw - xyla/blob - t/tests.at

   1 ### -*-autotest-*-
   2 ###
   3 ### Test script
   4 ###
   5 ### (c) 2024 Straylight/Edgeware
   6 ###
   7
   8 ###----- Licensing notice ---------------------------------------------------
   9 ###
  10 ### This file is part of Xyla, a library of binary trees.
  11 ###
  12 ### Xyla is free software: you can redistribute it and/or modify it under
  13 ### the terms of the GNU Lesser General Public License as published by the
  14 ### Free Software Foundation; either version 3 of the License, or (at your
  15 ### option) any later version.
  16 ###
  17 ### Xyla is distributed in the hope that it will be useful, but WITHOUT
  18 ### ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  19 ### FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  20 ### License for more details.
  21 ###
  22 ### You should have received a copy of the GNU Lesser General Public
  23 ### License along with Xyla.  If not, see <https://www.gnu.org/licenses/>.
  24
  25 m4_define([TESTINPUT_PATH], [$abs_top_srcdir/t])
  26 m4_define([TESTPROG_PATH], [$abs_top_builddir/t])
  27 m4_define([LTRUN], [$abs_top_builddir/libtool --mode=execute])
  28
  29 m4_define([_FOREACH], [dnl
  30 m4_if([$#], [1], [_foreach_func($1)],
  31         [_foreach_func($1)[]_FOREACH(m4_shift($@))])])
  32 m4_define([FOREACH], [dnl
  33 m4_pushdef([_foreach_func], [$2])dnl
  34 _FOREACH($1)[]dnl
  35 m4_popdef([_foreach_func])])
  36
  37 m4_define([DOL], [$])
  38
  39 m4_define([VALGRIND_DEFAULTS],
  40 [--leak-check=full --show-leak-kinds=all dnl
  41 --errors-for-leak-kinds=all --track-origins=yes --error-exitcode=3])
  42 m4_define([DIRECT_NSTEPS], [1000000])
  43 m4_define([VALGRIND_NSTEPS], [100000])
  44
  45 m4_define([TREES], [avl, rb, splay, treap])
  46 m4_define([COMMON_TESTS], [commontest])
  47 m4_define([avl_TESTS], [avltest, avlregress])
  48 m4_define([rb_TESTS], [rbtest, rbregress])
  49 m4_define([splay_TESTS], [splaytest])
  50 m4_define([treap_TESTS], [treaptest])
  51
  52 ###--------------------------------------------------------------------------
  53 ### Option parsing.
  54
  55 AT_ARG_OPTION_ARG([xyla-launder],
  56         [AS_HELP_STRING([--xyla-launder=FILTER],
  57                         [apply FILTER for test output])],
  58         [AS_CASE([$at_optarg],
  59           [nil],
  60             [filter=cat],
  61           [ignseq],
  62             [filter="sed 's/@%:@0x@<:@0-9a-f@:>@*/@%:@0x......../g'"],
  63           [AS_ECHO([unknown launder]) >&2; AS_EXIT([2])])],
  64         [filter=cat])
  65
  66 AT_ARG_OPTION_ARG([xyla-runner],
  67         [AS_HELP_STRING([--xyla-runner=WRAPPER],
  68                         [apply WRAPPER around test programs])],
  69         [AS_CASE([$at_optarg],
  70           [direct],
  71             [adverb= dflt_steps=DIRECT_NSTEPS],
  72           [valgrind],
  73             [adverb="valgrind ${VALGRIND_OPTS-VALGRIND_DEFAULTS} \
  74                 --log-file=valgrind.out"
  75              dflt_steps=VALGRIND_NSTEPS],
  76           [vgdb],
  77             [adverb="valgrind ${VALGRIND_OPTS-VALGRIND_DEFAULTS} \
  78                 --vgdb=full --vgdb-error=1 --vgdb-shadow-registers=yes"
  79              dflt_steps=VALGRIND_NSTEPS],
  80           [AS_ECHO([unknown runner]) >&2; AS_EXIT([2])])],
  81         [adverb= dflt_steps=DIRECT_NSTEPS])
  82
  83 AT_ARG_OPTION([xyla-setref],
  84         [AS_HELP_STRING([--xyla-setref],
  85                         [set reference file from test output])])
  86
  87 AT_ARG_OPTION([xyla-soak],
  88         [AS_HELP_STRING([--xyla-soak], [run soak tests])])
  89
  90 AT_ARG_OPTION_ARG([xyla-soak-seed],
  91         [AS_HELP_STRING([--xyla-soak-seed=SEED],
  92                         [force soak-test seed])],
  93         [soak_seed=$at_optarg],
  94         [soak_seed=nil])
  95
  96 AT_ARG_OPTION_ARG([xyla-soak-steps],
  97         [AS_HELP_STRING([--xyla-soak-steps=NSTEPS],
  98                         [run NSTEPS soak steps])],
  99         [soak_steps=$at_optarg],
 100         [soak_steps=nil])
 101
 102 ###--------------------------------------------------------------------------
 103 m4_define([DEF_KAT1], [AT_SETUP([$1-$2])
 104
 105 AT_KEYWORDS([$1 $2 kat $1-$2])
 106
 107 cp TESTINPUT_PATH/$2.in in
 108 AT_CHECK([LTRUN $adverb TESTPROG_PATH/$1test -oout in], [0], [], [])
 109 if test -r TESTINPUT_PATH/$1-$2.ref; then
 110   eval $filter <out >out.filtered
 111   eval $filter <TESTINPUT_PATH/$1-$2.ref >ref.filtered
 112   AT_CHECK([diff -u out.filtered ref.filtered], [0], [], [])
 113 else
 114   AS_CASE([$at_arg_xyla_setref],
 115     [:], [cp out TESTINPUT_PATH/$1-$2.ref],
 116     [AT_CHECK([echo missing ref file TESTINPUT_PATH/$1-$2.ref; AS_EXIT([99])])])
 117 fi
 118
 119 AT_CLEANUP])
 120
 121 FOREACH([TREES],
 122         [FOREACH([COMMON_TESTS, $1_TESTS],
 123                  [DEF_KAT1([$1], ]DOL()1[)])])
 124
 125 ###--------------------------------------------------------------------------
 126 ### Verify checking is working properly.
 127
 128 AT_SETUP([avl-check])
 129 AT_KEYWORDS([avl avl-check])
 130 AT_DATA([in], [= (_ -4 (_ =3 _)) !
 131 ])
 132 XYLA_REDACT_ADDRESSES=t; export XYLA_REDACT_ADDRESSES
 133 AT_CHECK([LTRUN TESTPROG_PATH/avltest in], [2],
 134 [offending tree...
 135         @%:@0x00000001 (n =   2)        (-) 4
 136         @%:@0x00000000 (n =   1)            (=) 3
 137 ],
 138 [XYLA-BT @%:@<root @<:@ADDR@:>@> BUG: @%:@<node @%:@0x00000000 3> key not above lower bound
 139 XYLA-AVL @%:@<root @<:@ADDR@:>@> BUG: @%:@<node @%:@0x00000001 4> incorrect balance annotation `-' /= left 0 - 1 right
 140 BUG: check failed: tree structure invalid (input pos = 19)
 141 ])
 142 AT_CLEANUP
 143
 144 AT_SETUP([rb-check])
 145 AT_KEYWORDS([rb rb-check])
 146 AT_DATA([in], [= ((_ 2 _) 4 (_ *3 _)) !
 147 ])
 148 XYLA_REDACT_ADDRESSES=t; export XYLA_REDACT_ADDRESSES
 149 AT_CHECK([LTRUN TESTPROG_PATH/rbtest in], [2],
 150 [offending tree...
 151         @%:@0x00000000 (n =   1)            ( ) 2
 152         @%:@0x00000002 (n =   3)        ( ) 4
 153         @%:@0x00000001 (n =   1)                (*) 3
 154 ],
 155 [XYLA-RB @%:@<root @<:@ADDR@:>@> BUG: root @%:@<node @%:@0x00000002 4> is red
 156 XYLA-RB @%:@<root @<:@ADDR@:>@> BUG: red @%:@<node @%:@0x00000000 2> has red parent @%:@<node @%:@0x00000002 4>
 157 XYLA-BT @%:@<root @<:@ADDR@:>@> BUG: @%:@<node @%:@0x00000001 3> key not above lower bound
 158 XYLA-RB @%:@<root @<:@ADDR@:>@> BUG: @%:@<node @%:@0x00000002 4> left black-height 0 /= 1 right black-height
 159 BUG: check failed: tree structure invalid (input pos = 24)
 160 ])
 161 AT_CLEANUP
 162
 163 AT_SETUP([splay-check])
 164 AT_KEYWORDS([splay splay-check])
 165 AT_DATA([in], [= (_ 4 (_ 3 _)) !
 166 ])
 167 XYLA_REDACT_ADDRESSES=t; export XYLA_REDACT_ADDRESSES
 168 AT_CHECK([LTRUN TESTPROG_PATH/splaytest in], [2],
 169 [offending tree...
 170         @%:@0x00000001 (n =   2)        (*) 4
 171         @%:@0x00000000 (n =   1)            (*) 3
 172 ],
 173 [XYLA-BT @%:@<root @<:@ADDR@:>@> BUG: @%:@<node @%:@0x00000000 3> key not above lower bound
 174 BUG: check failed: tree structure invalid (input pos = 17)
 175 ])
 176 AT_CLEANUP
 177
 178 AT_SETUP([treap-check])
 179 AT_KEYWORDS([treap treap-check])
 180 AT_DATA([in], [= (_ 2$ 4 (_ 1$ 3 _)) !
 181 ])
 182 XYLA_REDACT_ADDRESSES=t; export XYLA_REDACT_ADDRESSES
 183 AT_CHECK([LTRUN TESTPROG_PATH/treaptest in], [2],
 184 [offending tree...
 185         @%:@0x00000001 (n =   2)        (*) 0x00000002$ 4
 186         @%:@0x00000000 (n =   1)            (*) 0x00000001$ 3
 187 ],
 188 [XYLA-TREAP @%:@<root @<:@ADDR@:>@> BUG: @%:@<node @%:@0x00000000 0x00000001$ 3> weight 1 < 2 weight of parent @%:@<node @%:@0x00000001 0x00000002$ 4>
 189 XYLA-BT @%:@<root @<:@ADDR@:>@> BUG: @%:@<node @%:@0x00000000 0x00000001$ 3> key not above lower bound
 190 BUG: check failed: tree structure invalid (input pos = 23)
 191 ])
 192 AT_CLEANUP
 193
 194 ###--------------------------------------------------------------------------
 195 AT_SETUP([treap-bounds])
 196
 197 AT_KEYWORDS([treap treap-bounds])
 198
 199 ## A 64-bit host has space to cope with a treap with weight 538, following
 200 ## the analysis in <xyla/treap.h>.  So we'll blow the path structure if we
 201 ## make a tree with height 539.  The test program starts with a fixed seed to
 202 ## make the tests reproducible, so we can `predict' the RNG output by just
 203 ## running the test.
 204 AT_DATA([setup], [@%:@539 D
 205 ])
 206 AT_CHECK([LTRUN $adverb TESTPROG_PATH/treaptest -oout setup], [0], [], [])
 207 ## Extract the sequence of weights.  Attach their initial ordering.  Sort by
 208 ## the weights, lightest first.  Attach /this/ ordering too: those are going
 209 ## to be the keys associated with each weight; since weights and keys both
 210 ## increase monotonically, we'll end up with a vine.  Restore the initial
 211 ## ordering by sorting.  Trim off everything other than the keys, and attach
 212 ## the insertion command to each line.  Finally, find the last node and
 213 ## descend to one of its nil links.
 214 sed '1d; s/^.*\(0x@<:@0-9a-f@:>@*\)\$.*$/\1/' out |
 215   nl | sort -k2 | nl | sort -k2n |
 216   sed 's/^.@<:@@<:@:space:@:>@@:>@*//; s/@<:@@<:@:space:@:>@@:>@.*$/+/; $a\
 217 @:>@}' >killme
 218 AT_CHECK([LTRUN $adverb TESTPROG_PATH/treaptest killme],
 219          [ignore], [stdout], [stderr],
 220          [], [rc=$at_status])
 221 if test $rc -gt 128; then sig=$(kill -l $rc); else sig=nil; fi
 222 AT_CHECK([
 223   case $sig in
 224     ABRT) ;;
 225     *) echo "unexpected exit status $rc (sig = $sig)"; exit 1 ;;
 226   esac
 227 ])
 228
 229 AT_CLEANUP
 230
 231 ###--------------------------------------------------------------------------
 232 m4_define([DEF_SOAK], [AT_SETUP([$1-soak])
 233
 234 AT_KEYWORDS([soak $1 $1-soak])
 235 AT_SKIP_IF([test $at_arg_xyla_soak != :])
 236 AT_SKIP_IF([test $PYTHON = :])
 237
 238 args=
 239 AS_CASE([$soak_steps], [nil], [soak_steps=$dflt_steps])
 240 args=${args+$args }-n$soak_steps
 241 AS_CASE([$soak_seed], [nil], [], [args="${args+$args }-s '$soak_seed'"])
 242 AT_CHECK([$PYTHON TESTINPUT_PATH/soak $args dnl
 243          LTRUN $adverb TESTPROG_PATH/$1test], [0], [], [])
 244
 245 AT_CLEANUP])
 246
 247 FOREACH([TREES], [DEF_SOAK([$1])])
 248
 249 ###----- That's all, folks --------------------------------------------------