### -*-autotest-*-
###
### Test script
###
### (c) 2024 Straylight/Edgeware
###

###----- Licensing notice ---------------------------------------------------
###
### This file is part of Xyla, a library of binary trees.
###
### Xyla is free software: you can redistribute it and/or modify it under
### the terms of the GNU Lesser General Public License as published by the
### Free Software Foundation; either version 3 of the License, or (at your
### option) any later version.
###
### Xyla is distributed in the hope that it will be useful, but WITHOUT
### ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
### FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
### License for more details.
###
### You should have received a copy of the GNU Lesser General Public
### License along with Xyla.  If not, see <https://www.gnu.org/licenses/>.

m4_define([TESTINPUT_PATH], [$abs_top_srcdir/t])
m4_define([TESTPROG_PATH], [$abs_top_builddir/t])
m4_define([LTRUN], [$abs_top_builddir/libtool --mode=execute])

m4_define([_FOREACH], [dnl
m4_if([$#], [1], [_foreach_func($1)],
	[_foreach_func($1)[]_FOREACH(m4_shift($@))])])
m4_define([FOREACH], [dnl
m4_pushdef([_foreach_func], [$2])dnl
_FOREACH($1)[]dnl
m4_popdef([_foreach_func])])

m4_define([DOL], [$])

m4_define([VALGRIND_DEFAULTS],
[--leak-check=full --show-leak-kinds=all dnl
--errors-for-leak-kinds=all --track-origins=yes --error-exitcode=3])
m4_define([DIRECT_NSTEPS], [1000000])
m4_define([VALGRIND_NSTEPS], [100000])

m4_define([TREES], [avl, rb, splay, treap])
m4_define([COMMON_TESTS], [commontest])
m4_define([avl_TESTS], [avltest, avlregress])
m4_define([rb_TESTS], [rbtest, rbregress])
m4_define([splay_TESTS], [splaytest])
m4_define([treap_TESTS], [treaptest])

###--------------------------------------------------------------------------
### Option parsing.

AT_ARG_OPTION_ARG([xyla-launder],
	[AS_HELP_STRING([--xyla-launder=FILTER],
			[apply FILTER for test output])],
	[AS_CASE([$at_optarg],
	  [nil],
	    [filter=cat],
	  [ignseq],
	    [filter="sed 's/@%:@0x@<:@0-9a-f@:>@*/@%:@0x......../g'"],
	  [AS_ECHO([unknown launder]) >&2; AS_EXIT([2])])],
	[filter=cat])

AT_ARG_OPTION_ARG([xyla-runner],
	[AS_HELP_STRING([--xyla-runner=WRAPPER],
			[apply WRAPPER around test programs])],
	[AS_CASE([$at_optarg],
	  [direct],
	    [adverb= dflt_steps=DIRECT_NSTEPS],
	  [valgrind],
	    [adverb="valgrind ${VALGRIND_OPTS-VALGRIND_DEFAULTS} \
		--log-file=valgrind.out"
	     dflt_steps=VALGRIND_NSTEPS],
	  [vgdb],
	    [adverb="valgrind ${VALGRIND_OPTS-VALGRIND_DEFAULTS} \
		--vgdb=full --vgdb-error=1 --vgdb-shadow-registers=yes"
	     dflt_steps=VALGRIND_NSTEPS],
	  [AS_ECHO([unknown runner]) >&2; AS_EXIT([2])])],
	[adverb= dflt_steps=DIRECT_NSTEPS])

AT_ARG_OPTION([xyla-setref],
	[AS_HELP_STRING([--xyla-setref],
			[set reference file from test output])])

AT_ARG_OPTION([xyla-soak],
	[AS_HELP_STRING([--xyla-soak], [run soak tests])])

AT_ARG_OPTION_ARG([xyla-soak-seed],
	[AS_HELP_STRING([--xyla-soak-seed=SEED],
			[force soak-test seed])],
	[soak_seed=$at_optarg],
	[soak_seed=nil])

AT_ARG_OPTION_ARG([xyla-soak-steps],
	[AS_HELP_STRING([--xyla-soak-steps=NSTEPS],
			[run NSTEPS soak steps])],
	[soak_steps=$at_optarg],
	[soak_steps=nil])

###--------------------------------------------------------------------------
m4_define([DEF_KAT1], [AT_SETUP([$1-$2])

AT_KEYWORDS([$1 $2 kat $1-$2])

cp TESTINPUT_PATH/$2.in in
AT_CHECK([LTRUN $adverb TESTPROG_PATH/$1test -oout in], [0], [], [])
if test -r TESTINPUT_PATH/$1-$2.ref; then
  eval $filter <out >out.filtered
  eval $filter <TESTINPUT_PATH/$1-$2.ref >ref.filtered
  AT_CHECK([diff -u out.filtered ref.filtered], [0], [], [])
else
  AS_CASE([$at_arg_xyla_setref],
    [:], [cp out TESTINPUT_PATH/$1-$2.ref],
    [AT_CHECK([echo missing ref file TESTINPUT_PATH/$1-$2.ref; AS_EXIT([99])])])
fi

AT_CLEANUP])

FOREACH([TREES],
	[FOREACH([COMMON_TESTS, $1_TESTS],
		 [DEF_KAT1([$1], ]DOL()1[)])])

###--------------------------------------------------------------------------
### Verify checking is working properly.

AT_SETUP([avl-check])
AT_KEYWORDS([avl avl-check])
AT_DATA([in], [= (_ -4 (_ =3 _)) !
])
XYLA_REDACT_ADDRESSES=t; export XYLA_REDACT_ADDRESSES
AT_CHECK([LTRUN TESTPROG_PATH/avltest in], [2],
[offending tree...
	@%:@0x00000001 (n =   2)	(-) 4
	@%:@0x00000000 (n =   1)	    (=) 3
],
[XYLA-BT @%:@<root @<:@ADDR@:>@> BUG: @%:@<node @%:@0x00000000 3> key not above lower bound
XYLA-AVL @%:@<root @<:@ADDR@:>@> BUG: @%:@<node @%:@0x00000001 4> incorrect balance annotation `-' /= left 0 - 1 right
BUG: check failed: tree structure invalid (input pos = 19)
])
AT_CLEANUP

AT_SETUP([rb-check])
AT_KEYWORDS([rb rb-check])
AT_DATA([in], [= ((_ 2 _) 4 (_ *3 _)) !
])
XYLA_REDACT_ADDRESSES=t; export XYLA_REDACT_ADDRESSES
AT_CHECK([LTRUN TESTPROG_PATH/rbtest in], [2],
[offending tree...
	@%:@0x00000000 (n =   1)	    ( ) 2
	@%:@0x00000002 (n =   3)	( ) 4
	@%:@0x00000001 (n =   1)	        (*) 3
],
[XYLA-RB @%:@<root @<:@ADDR@:>@> BUG: root @%:@<node @%:@0x00000002 4> is red
XYLA-RB @%:@<root @<:@ADDR@:>@> BUG: red @%:@<node @%:@0x00000000 2> has red parent @%:@<node @%:@0x00000002 4>
XYLA-BT @%:@<root @<:@ADDR@:>@> BUG: @%:@<node @%:@0x00000001 3> key not above lower bound
XYLA-RB @%:@<root @<:@ADDR@:>@> BUG: @%:@<node @%:@0x00000002 4> left black-height 0 /= 1 right black-height
BUG: check failed: tree structure invalid (input pos = 24)
])
AT_CLEANUP

AT_SETUP([splay-check])
AT_KEYWORDS([splay splay-check])
AT_DATA([in], [= (_ 4 (_ 3 _)) !
])
XYLA_REDACT_ADDRESSES=t; export XYLA_REDACT_ADDRESSES
AT_CHECK([LTRUN TESTPROG_PATH/splaytest in], [2],
[offending tree...
	@%:@0x00000001 (n =   2)	(*) 4
	@%:@0x00000000 (n =   1)	    (*) 3
],
[XYLA-BT @%:@<root @<:@ADDR@:>@> BUG: @%:@<node @%:@0x00000000 3> key not above lower bound
BUG: check failed: tree structure invalid (input pos = 17)
])
AT_CLEANUP

AT_SETUP([treap-check])
AT_KEYWORDS([treap treap-check])
AT_DATA([in], [= (_ 2$ 4 (_ 1$ 3 _)) !
])
XYLA_REDACT_ADDRESSES=t; export XYLA_REDACT_ADDRESSES
AT_CHECK([LTRUN TESTPROG_PATH/treaptest in], [2],
[offending tree...
	@%:@0x00000001 (n =   2)	(*) 0x00000002$ 4
	@%:@0x00000000 (n =   1)	    (*) 0x00000001$ 3
],
[XYLA-TREAP @%:@<root @<:@ADDR@:>@> BUG: @%:@<node @%:@0x00000000 0x00000001$ 3> weight 1 < 2 weight of parent @%:@<node @%:@0x00000001 0x00000002$ 4>
XYLA-BT @%:@<root @<:@ADDR@:>@> BUG: @%:@<node @%:@0x00000000 0x00000001$ 3> key not above lower bound
BUG: check failed: tree structure invalid (input pos = 23)
])
AT_CLEANUP

###--------------------------------------------------------------------------
AT_SETUP([treap-bounds])

AT_KEYWORDS([treap treap-bounds])

## A 64-bit host has space to cope with a treap with weight 538, following
## the analysis in <xyla/treap.h>.  So we'll blow the path structure if we
## make a tree with height 539.  The test program starts with a fixed seed to
## make the tests reproducible, so we can `predict' the RNG output by just
## running the test.
AT_DATA([setup], [@%:@539 D
])
AT_CHECK([LTRUN $adverb TESTPROG_PATH/treaptest -oout setup], [0], [], [])
## Extract the sequence of weights.  Attach their initial ordering.  Sort by
## the weights, lightest first.  Attach /this/ ordering too: those are going
## to be the keys associated with each weight; since weights and keys both
## increase monotonically, we'll end up with a vine.  Restore the initial
## ordering by sorting.  Trim off everything other than the keys, and attach
## the insertion command to each line.  Finally, find the last node and
## descend to one of its nil links.
sed '1d; s/^.*\(0x@<:@0-9a-f@:>@*\)\$.*$/\1/' out |
  nl | sort -k2 | nl | sort -k2n |
  sed 's/^.@<:@@<:@:space:@:>@@:>@*//; s/@<:@@<:@:space:@:>@@:>@.*$/+/; $a\
@:>@}' >killme
AT_CHECK([LTRUN $adverb TESTPROG_PATH/treaptest killme],
	 [ignore], [stdout], [stderr],
	 [], [rc=$at_status])
if test $rc -gt 128; then sig=$(kill -l $rc); else sig=nil; fi
AT_CHECK([
  case $sig in
    ABRT) ;;
    *) echo "unexpected exit status $rc (sig = $sig)"; exit 1 ;;
  esac
])

AT_CLEANUP

###--------------------------------------------------------------------------
AT_SETUP([examples])

AT_KEYWORDS([examples])

AT_CHECK([LTRUN $adverb TESTPROG_PATH/example dnl
	  <TESTINPUT_PATH/example.in >out ], [0], [], [])
AT_CHECK([diff -u out TESTINPUT_PATH/example.ref], [0], [], [])

AT_CLEANUP

###--------------------------------------------------------------------------
m4_define([DEF_SOAK], [AT_SETUP([$1-soak])

AT_KEYWORDS([soak $1 $1-soak])
AT_SKIP_IF([test $at_arg_xyla_soak != :])
AT_SKIP_IF([test $PYTHON = :])

args=
AS_CASE([$soak_steps], [nil], [soak_steps=$dflt_steps])
args=${args+$args }-n$soak_steps
AS_CASE([$soak_seed], [nil], [], [args="${args+$args }-s '$soak_seed'"])
AT_CHECK([$PYTHON TESTINPUT_PATH/soak $args dnl
	 LTRUN $adverb TESTPROG_PATH/$1test], [0], [], [])

AT_CLEANUP])

FOREACH([TREES], [DEF_SOAK([$1])])

###----- That's all, folks --------------------------------------------------