testsuite/tsort.tests

   1 #!/bin/sh
   2
   3 # SUSv3 compliant sort tests.
   4 # Public Domain, David Leonard 2022
   5
   6 . ./testing.sh
   7
   8 #       name cmd expected ./input stdin
   9 testing "" "tsort"       "a\n" "" "a a\n"
  10 testing "" "tsort -"     "a\n" "" "a a\n"
  11 testing "" "tsort input" "a\n" "a a\n" ""
  12 testing "tsort input (w/o eol)" "tsort input" "a\n" "a a" ""
  13 testing "" "tsort /dev/null" "" "" ""
  14
  15 testing "tsort empty" tsort "" "" ""
  16 testing "tsort blank" tsort "" "" "\n"
  17 testing "tsort blanks" tsort "" "" "\n\n \t\n "
  18
  19 # simple inputs having exactly one solution
  20 testing "tsort 1-edge" tsort "a\nb\n" "" "a b\n"
  21 testing "tsort 2-edge" tsort "a\nb\nc\n" "" "a b b c\n"
  22
  23
  24 # The following test helper accommodates future variable output because, as
  25 # tsort is allowed to emit any total ordering that satisfies its input,
  26 # should the implementation changes, these tests will remain valid.
  27 #
  28 # The idea is to verify that:
  29 # - each input word is present EXACTLY ONCE in tsort's output
  30 # - for each input pair 'a b', the occurrence of 'a' APPEARS BEFORE 'b'
  31 # - the exit code is 0
  32
  33 tsort_test () {
  34         fail=
  35         name="$1"; shift
  36         args="$*"
  37         if [ $VERBOSE ]; then
  38                 echo "============"
  39                 echo "echo \"$args\" | tsort >actual"
  40         fi
  41         echo "$args" | tsort >actual
  42         ec=$?
  43         if [ $ec -ne 0 ]; then
  44                 fail "tsort exit $ec, expected 0"
  45         fi
  46         while [ $# -ne 0 ]; do
  47                 a=$1; shift
  48                 b=$1; shift
  49                 aline=$(grep -nxF "$a" <actual | cut -d: -f1)
  50                 bline=$(grep -nxF "$b" <actual | cut -d: -f1)
  51                 case $aline in
  52                         "") fail "word $a missing from output ($args)";;
  53                         *" "*) fail "word $a duplicated ($args)";;
  54                 esac
  55                 case $bline in
  56                         "") fail "word $b missing from output ($args)";;
  57                         *" "*) fail "word $b duplicated ($args)";;
  58                 esac
  59                 if [ $aline -gt $bline ]; then
  60                         fail "$a appears after $b ($args)"
  61                 fi
  62         done
  63         if [ $fail ] && [ $VERBOSE ]; then
  64                 echo "exit $ec, actual:"
  65                 cat actual
  66         fi
  67         rm actual
  68         report "$name"
  69 }
  70
  71 # Test that erroneous input causes an unsuccessful exit code
  72 # we don't test the output error message
  73 tsort_test_err () {
  74         fail=
  75         name="$1"; shift
  76         echo "$*" | tsort >/dev/null 2>/dev/null
  77         ec=$?
  78         if [ $ec -eq 0 ]; then
  79                 fail "$name: unexpected exit 0 ($*)"
  80         fi
  81         report "$name"
  82 }
  83
  84 fail () {
  85         [ $VERBOSE ] && echo "ERROR: $*"
  86         fail=1
  87 }
  88
  89 report () {
  90         if [ $fail ]; then
  91                 FAILCOUNT=$(($FAILCOUNT + 1))
  92                 echo "FAIL: $*"
  93         else
  94                 echo "PASS: $*"
  95         fi
  96 }
  97
  98 tsort_test "tsort empty2"
  99 tsort_test "tsort singleton"    a a
 100 tsort_test "tsort simple"       a b b c
 101 tsort_test "tsort 2singleton"   a a b b
 102 tsort_test "tsort medium"       a b a b b c
 103 tsort_test "tsort std.example"  a b c c d e g g f g e f h h
 104 tsort_test "tsort prefixes"     a aa aa aaa aaaa aaaaa a aaaaa
 105
 106 tsort_test_err "tsort odd"      a
 107 tsort_test_err "tsort odd2"     a b c
 108 tsort_test_err "tsort cycle"    a b b a
 109
 110 exit $FAILCOUNT