lib/path/tests/prop.sh

   1 #!/usr/bin/env bash
   2
   3 # Property tests for lib/path/default.nix
   4 # It generates random path-like strings and runs the functions on
   5 # them, checking that the expected laws of the functions hold
   6 # Run:
   7 # [nixpkgs]$ lib/path/tests/prop.sh
   8 # or:
   9 # [nixpkgs]$ nix-build lib/tests/release.nix
  10
  11 set -euo pipefail
  12 shopt -s inherit_errexit
  13
  14 # https://stackoverflow.com/a/246128
  15 SCRIPT_DIR=$( cd -- "$( dirname -- "${BASH_SOURCE[0]}" )" &> /dev/null && pwd )
  16
  17 if test -z "${TEST_LIB:-}"; then
  18     TEST_LIB=$SCRIPT_DIR/../..
  19 fi
  20
  21 tmp="$(mktemp -d)"
  22 clean_up() {
  23     rm -rf "$tmp"
  24 }
  25 trap clean_up EXIT
  26 mkdir -p "$tmp/work"
  27 cd "$tmp/work"
  28
  29 # Defaulting to a random seed but the first argument can override this
  30 seed=${1:-$RANDOM}
  31 echo >&2 "Using seed $seed, use \`lib/path/tests/prop.sh $seed\` to reproduce this result"
  32
  33 # The number of random paths to generate. This specific number was chosen to
  34 # be fast enough while still generating enough variety to detect bugs.
  35 count=500
  36
  37 debug=0
  38 # debug=1 # print some extra info
  39 # debug=2 # print generated values
  40
  41 # Fine tuning parameters to balance the number of generated invalid paths
  42 # to the variance in generated paths.
  43 extradotweight=64   # Larger value: more dots
  44 extraslashweight=64 # Larger value: more slashes
  45 extranullweight=16  # Larger value: shorter strings
  46
  47 die() {
  48     echo >&2 "test case failed: " "$@"
  49     exit 1
  50 }
  51
  52 if [[ "$debug" -ge 1 ]]; then
  53     echo >&2 "Generating $count random path-like strings"
  54 fi
  55
  56 # Read stream of null-terminated strings entry-by-entry into bash,
  57 # write it to a file and the `strings` array.
  58 declare -a strings=()
  59 mkdir -p "$tmp/strings"
  60 while IFS= read -r -d $'\0' str; do
  61     printf "%s" "$str" > "$tmp/strings/${#strings[@]}"
  62     strings+=("$str")
  63 done < <(awk \
  64     -f "$SCRIPT_DIR"/generate.awk \
  65     -v seed="$seed" \
  66     -v count="$count" \
  67     -v extradotweight="$extradotweight" \
  68     -v extraslashweight="$extraslashweight" \
  69     -v extranullweight="$extranullweight")
  70
  71 if [[ "$debug" -ge 1 ]]; then
  72     echo >&2 "Trying to normalise the generated path-like strings with Nix"
  73 fi
  74
  75 # Precalculate all normalisations with a single Nix call. Calling Nix for each
  76 # string individually would take way too long
  77 nix-instantiate --eval --strict --json --show-trace \
  78     --argstr libpath "$TEST_LIB" \
  79     --argstr dir "$tmp/strings" \
  80     "$SCRIPT_DIR"/prop.nix \
  81     >"$tmp/result.json"
  82
  83 # Uses some jq magic to turn the resulting attribute set into an associative
  84 # bash array assignment
  85 declare -A normalised_result="($(jq '
  86     to_entries
  87     | map("[\(.key | @sh)]=\(.value | @sh)")
  88     | join(" \n")' -r < "$tmp/result.json"))"
  89
  90 # Looks up a normalisation result for a string
  91 # Checks that the normalisation is only failing iff it's an invalid subpath
  92 # For valid subpaths, returns 0 and prints the normalisation result
  93 # For invalid subpaths, returns 1
  94 normalise() {
  95     local str=$1
  96     # Uses the same check for validity as in the library implementation
  97     if [[ "$str" == "" || "$str" == /* || "$str" =~ ^(.*/)?\.\.(/.*)?$ ]]; then
  98         valid=
  99     else
 100         valid=1
 101     fi
 102
 103     normalised=${normalised_result[$str]}
 104     # An empty string indicates failure, this is encoded in ./prop.nix
 105     if [[ -n "$normalised" ]]; then
 106         if [[ -n "$valid" ]]; then
 107             echo "$normalised"
 108         else
 109             die "For invalid subpath \"$str\", lib.path.subpath.normalise returned this result: \"$normalised\""
 110         fi
 111     else
 112         if [[ -n "$valid" ]]; then
 113             die "For valid subpath \"$str\", lib.path.subpath.normalise failed"
 114         else
 115             if [[ "$debug" -ge 2 ]]; then
 116                 echo >&2 "String \"$str\" is not a valid subpath"
 117             fi
 118             # Invalid and it correctly failed, we let the caller continue if they catch the exit code
 119             return 1
 120         fi
 121     fi
 122 }
 123
 124 # Intermediate result populated by test_idempotency_realpath
 125 # and used in test_normalise_uniqueness
 126 #
 127 # Contains a mapping from a normalised subpath to the realpath result it represents
 128 declare -A norm_to_real
 129
 130 test_idempotency_realpath() {
 131     if [[ "$debug" -ge 1 ]]; then
 132         echo >&2 "Checking idempotency of each result and making sure the realpath result isn't changed"
 133     fi
 134
 135     # Count invalid subpaths to display stats
 136     invalid=0
 137     for str in "${strings[@]}"; do
 138         if ! result=$(normalise "$str"); then
 139             ((invalid++)) || true
 140             continue
 141         fi
 142
 143         # Check the law that it doesn't change the result of a realpath
 144         mkdir -p -- "$str" "$result"
 145         real_orig=$(realpath -- "$str")
 146         real_norm=$(realpath -- "$result")
 147
 148         if [[ "$real_orig" != "$real_norm" ]]; then
 149             die "realpath of the original string \"$str\" (\"$real_orig\") is not the same as realpath of the normalisation \"$result\" (\"$real_norm\")"
 150         fi
 151
 152         if [[ "$debug" -ge 2 ]]; then
 153             echo >&2 "String \"$str\" gets normalised to \"$result\" and file path \"$real_orig\""
 154         fi
 155         norm_to_real["$result"]="$real_orig"
 156     done
 157     if [[ "$debug" -ge 1 ]]; then
 158         echo >&2 "$(bc <<< "scale=1; 100 / $count * $invalid")% of the total $count generated strings were invalid subpath strings, and were therefore ignored"
 159     fi
 160 }
 161
 162 test_normalise_uniqueness() {
 163     if [[ "$debug" -ge 1 ]]; then
 164         echo >&2 "Checking for the uniqueness law"
 165     fi
 166
 167     for norm_p in "${!norm_to_real[@]}"; do
 168         real_p=${norm_to_real["$norm_p"]}
 169         for norm_q in "${!norm_to_real[@]}"; do
 170             real_q=${norm_to_real["$norm_q"]}
 171             # Checks normalisation uniqueness law for each pair of values
 172             if [[ "$norm_p" != "$norm_q" && "$real_p" == "$real_q" ]]; then
 173                 die "Normalisations \"$norm_p\" and \"$norm_q\" are different, but the realpath of them is the same: \"$real_p\""
 174             fi
 175         done
 176     done
 177 }
 178
 179 test_idempotency_realpath
 180 test_normalise_uniqueness
 181
 182 echo >&2 tests ok