tests/shuf/shuf-reservoir.sh

   1 #!/bin/sh
   2 # Exercise shuf's reservoir-sampling code
   3 # NOTE:
   4 #  These tests do not check valid randomness,
   5 #  they just check memory allocation related code.
   6
   7 # Copyright (C) 2013-2023 Free Software Foundation, Inc.
   8
   9 # This program is free software: you can redistribute it and/or modify
  10 # it under the terms of the GNU General Public License as published by
  11 # the Free Software Foundation, either version 3 of the License, or
  12 # (at your option) any later version.
  13
  14 # This program is distributed in the hope that it will be useful,
  15 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 # GNU General Public License for more details.
  18
  19 # You should have received a copy of the GNU General Public License
  20 # along with this program.  If not, see <https://www.gnu.org/licenses/>.
  21
  22 . "${srcdir=.}/tests/init.sh"; path_prepend_ ./src
  23 print_ver_ shuf
  24 expensive_
  25 require_valgrind_
  26
  27 # Only exit with error for leaks when in development mode
  28 # in which case we enable code to suppress inconsequential leaks.
  29 grep '^#define lint 1' "$CONFIG_HEADER" && leaklevel=full || leaklevel=summary
  30
  31 # Run "shuf" with specific number of input lines and output lines
  32 # Check the output for expected number of lines.
  33 run_shuf_n()
  34 {
  35   INPUT_LINES="$1"
  36   OUTPUT_LINES="$2"
  37
  38   # Critical memory-related bugs will cause a segfault here
  39   # (with varying numbers of input/output lines)
  40   seq "$INPUT_LINES" | valgrind --leak-check=$leaklevel --error-exitcode=1 \
  41   shuf -n "$OUTPUT_LINES" -o "out_${INPUT_LINES}_${OUTPUT_LINES}" || return 1
  42
  43   EXPECTED_LINES="$OUTPUT_LINES"
  44   test "$INPUT_LINES" -lt "$OUTPUT_LINES" && EXPECTED_LINES="$INPUT_LINES"
  45
  46   # There is no sure way to verify shuffled output (as it is random).
  47   # Ensure we have the correct number of all numeric lines non duplicated lines.
  48   GOOD_LINES=$(grep '^[0-9][0-9]*$' "out_${INPUT_LINES}_${OUTPUT_LINES}" |
  49                sort -un | wc -l) || framework_failure_
  50   LINES=$(wc -l < "out_${INPUT_LINES}_${OUTPUT_LINES}") || framework_failure_
  51
  52   test "$EXPECTED_LINES" -eq "$GOOD_LINES" || return 1
  53   test "$EXPECTED_LINES" -eq "$LINES" || return 1
  54
  55   return 0
  56 }
  57
  58 # Test multiple combinations of input lines and output lines.
  59 # (e.g. small number of input lines and large number of output lines,
  60 #  and vice-versa. Also, each reservoir allocation uses a 1024-lines batch,
  61 #  so test 1023/1024/1025 and related values).
  62 TEST_LINES="0 1 5 1023 1024 1025 3071 3072 3073"
  63
  64 for IN_N in $TEST_LINES; do
  65   for OUT_N in $TEST_LINES; do
  66     run_shuf_n "$IN_N" "$OUT_N" || {
  67       fail=1
  68       echo "shuf-reservoir-sampling failed with IN_N=$IN_N OUT_N=$OUT_N" >&2;
  69     }
  70   done
  71 done
  72
  73 Exit $fail