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
23print_ver_ shuf
24expensive_
25require_valgrind_
26
27# Only exit with error for leaks when in development mode
28# in which case we enable code to suppress inconsequential leaks.
29grep '^#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.
33run_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).
62TEST_LINES="0 1 5 1023 1024 1025 3071 3072 3073"
63
64for 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
71done
72
73Exit $fail
74