From 284a71b3ed78135bb92c4fa38d20ba41dd432c05 Mon Sep 17 00:00:00 2001
From: Silvan Mosberger <silvan.mosberger@tweag.io>
Date: Tue, 13 Dec 2022 06:59:05 +0100
Subject: lib/tests: Add randomized path.subpath.normalise property checks

---
 lib/tests/path.sh           | 159 ++++++++++++++++++++++++++++++++++++++++++++
 lib/tests/pathNormalise.nix |  32 +++++++++
 lib/tests/pathgen.awk       |  45 +++++++++++++
 lib/tests/release.nix       |   5 ++
 4 files changed, 241 insertions(+)
 create mode 100755 lib/tests/path.sh
 create mode 100644 lib/tests/pathNormalise.nix
 create mode 100644 lib/tests/pathgen.awk

diff --git a/lib/tests/path.sh b/lib/tests/path.sh
new file mode 100755
index 000000000000..34815b86c7c6
--- /dev/null
+++ b/lib/tests/path.sh
@@ -0,0 +1,159 @@
+#!/usr/bin/env bash
+set -euo pipefail
+shopt -s inherit_errexit
+
+if test -z "${TEST_LIB:-}"; then
+  TEST_LIB="$(cd "$(dirname "${BASH_SOURCE[0]}")/.."; pwd)"
+fi
+
+tmp="$(mktemp -d)"
+clean_up() {
+  rm -rf "$tmp"
+}
+trap clean_up EXIT
+mkdir -p "$tmp/work"
+cd "$tmp/work"
+
+# Deterministic seed for random generator
+seed=${1:-$RANDOM}
+echo >&2 "Using seed $seed, use \`lib/tests/path.sh $seed\` to reproduce this result"
+
+# The number of random paths to generate
+count=500
+
+# Set this to 1 or 2 to enable debug output
+debug=0
+
+# Fine tuning of the path generator in ./pathgen.awk
+# These values were chosen to balance the number of generated invalid paths
+# to the variance in generated paths. Enable debug output to see the paths
+extradotweight=64   # The larger this value, the more dots are generated
+extraslashweight=64 # The larger this value, the more slashes are generated
+extranullweight=16  # The larger this value, the shorter the generated strings
+
+# Use
+#     || die
+die() {
+  echo >&2 "test case failed: " "$@"
+  exit 1
+}
+
+if [[ "$debug" -ge 1 ]]; then
+    echo >&2 "Generating $count random path-like strings"
+fi
+
+mkdir -p "$tmp/strings"
+index=0
+while [[ "$index" -lt "$count" ]] && IFS= read -r -d $'\0' str; do
+    echo -n "$str" > "$tmp/strings/$index"
+    ((index++)) || true
+done < <(awk \
+    -v seed="$seed" \
+    -v extradotweight="$extradotweight" \
+    -v extraslashweight="$extraslashweight" \
+    -v extranullweight="$extranullweight" \
+    -f "$TEST_LIB"/tests/pathgen.awk)
+
+if [[ "$debug" -ge 1 ]]; then
+    echo >&2 "Trying to normalise the generated path-like strings with Nix"
+fi
+
+nix-instantiate --eval --strict --json --read-write-mode \
+    --arg libpath "$TEST_LIB" \
+    --arg dir "$tmp/strings" \
+    "$TEST_LIB"/tests/pathNormalise.nix \
+    >"$tmp/result.json"
+
+# Turns the results into an associative bash array
+declare -A results="($(jq '
+    to_entries
+    | map("[\(.key | @sh)]=\(.value | @sh)")
+    | join(" \n")' -r < "$tmp/result.json"))"
+
+# Looks up the normalisation result while, while checking that it only failed for invalid paths
+# Returns 0 for valid paths, 1 for invalid paths
+# Prints a valid path on stdout
+normalise() {
+    local str=$1
+    # Uses the same check for validity as in ../path.nix
+    if [[ "$str" == "" || "$str" == /* || "$str" =~ ^(.*/)?\.\.(/.*)?$ ]]; then
+        valid=
+    else
+        valid=1
+    fi
+
+    normalised=${results[$str]}
+    # An empty string indicates failure
+    if [[ -n "$normalised" ]]; then
+        if [[ -n "$valid" ]]; then
+            echo "$normalised"
+        else
+            die "For invalid subpath \"$str\", lib.path.subpath.normalise returned this result: \"$normalised\""
+        fi
+    else
+        if [[ -n "$valid" ]]; then
+            die "For valid subpath \"$str\", lib.path.subpath.normalise failed"
+        else
+            if [[ "$debug" -ge 2 ]]; then
+                echo >&2 "String $str is not a valid substring"
+            fi
+            # Invalid and it correctly failed, we let the caller continue if they catch the exit code
+            return 1
+        fi
+    fi
+}
+
+if [[ "$debug" -ge 1 ]]; then
+    echo >&2 "Checking idempotency of each result and making sure the realpath result isn't changed"
+fi
+
+declare -A norm_to_real
+invalid=0
+
+for str in "${!results[@]}"; do
+    if ! result=$(normalise "$str"); then
+        ((invalid++)) || true
+        continue
+    fi
+
+    if ! doubleResult=$(normalise "$result"); then
+        die "For valid subpath \"$str\", the normalisation \"$result\" was not a valid subpath"
+    fi
+
+    # Checking idempotency law
+    if [[ "$doubleResult" != "$result" ]]; then
+        die "For valid subpath \"$str\", normalising it once gives \"$result\" but normalising it twice gives a different result: \"$doubleResult\""
+    fi
+
+    # Check the law that it doesn't change the result of a realpath
+    mkdir -p -- "$str" "$result"
+    real_orig=$(realpath -- "$str")
+    real_norm=$(realpath -- "$result")
+
+    if [[ "$real_orig" != "$real_norm" ]]; then
+        die "realpath of the original string \"$str\" (\"$real_orig\") is not the same as realpath of the normalisation \"$result\" (\"$real_norm\")"
+    fi
+
+    if [[ "$debug" -ge 2 ]]; then
+        echo >&2 "String $str gets normalised to $result and file path $real_orig"
+    fi
+    norm_to_real["$result"]="$real_orig"
+done
+
+if [[ "$debug" -ge 1 ]]; then
+    echo >&2 "$(bc <<< "scale=1; 100 / $count * $invalid")% of the total $count generated strings were invalid subpath strings"
+    echo >&2 "Checking for the uniqueness law"
+fi
+
+for norm_p in "${!norm_to_real[@]}"; do
+    real_p=${norm_to_real["$norm_p"]}
+    for norm_q in "${!norm_to_real[@]}"; do
+        real_q=${norm_to_real["$norm_q"]}
+        # Checks normalisation uniqueness law
+        if [[ "$norm_p" != "$norm_q" && "$real_p" == "$real_q" ]]; then
+            die "Normalisations \"$norm_p\" and \"$norm_q\" are different, but the realpath of them is the same: \"$real_p\""
+        fi
+    done
+done
+
+echo >&2 tests ok
diff --git a/lib/tests/pathNormalise.nix b/lib/tests/pathNormalise.nix
new file mode 100644
index 000000000000..f76b6326b3f7
--- /dev/null
+++ b/lib/tests/pathNormalise.nix
@@ -0,0 +1,32 @@
+# Used by ./path.sh
+# dir is a flat directory containing files with randomly-generated path-like values
+# This file should return a { <value> = <lib.path.subpath.normalise value>; }
+# attribute set. If `normalise` fails to evaluate, "" is returned instead.
+# If "" is a value, it's not included in the result
+{ libpath, dir }:
+let
+  lib = import libpath;
+  inherit (lib.path.subpath) normalise;
+
+  list = builtins.concatMap (name:
+    let
+      str = builtins.readFile (dir + "/${name}");
+      onceRes = builtins.tryEval (normalise str);
+      twiceRes = builtins.tryEval (normalise onceRes.value);
+
+      once = {
+        name = str;
+        value = if onceRes.success then onceRes.value else "";
+      };
+      twice = {
+        name = onceRes.value;
+        value = if twiceRes.success then twiceRes.value else "";
+      };
+    in [ once ] ++ lib.optional onceRes.success twice
+  ) (builtins.attrNames (builtins.readDir dir));
+
+  attrs = builtins.listToAttrs list;
+
+  # Remove "" because bash can't handle that
+  result = removeAttrs attrs [""];
+in result
diff --git a/lib/tests/pathgen.awk b/lib/tests/pathgen.awk
new file mode 100644
index 000000000000..b205527127dd
--- /dev/null
+++ b/lib/tests/pathgen.awk
@@ -0,0 +1,45 @@
+# AWK script to generate random path-like strings
+BEGIN {
+  # Seed with 0 for reproducibility
+  srand(seed)
+
+  # Don't include 127 == DEL
+  upperascii = 127
+
+  # Creates array chr containing a mapping from integer to the ascii character representing it
+  for (i = 0; i < upperascii; i++) {
+    chr[i] = sprintf("%c", i)
+  }
+
+  # 32 extra weight for .
+  upperdot = upperascii + extradotweight
+  # 32 extra weight for /
+  upperslash = upperdot + extraslashweight
+  # 32 extra weight for null, indicating the end of the string
+  # Must be at least 1 to trigger the end at all
+  total = upperslash + 1 + extranullweight
+
+  new=1
+  while (1) {
+    value = int(rand() * total)
+    if (value < 32) {
+      # Don't output non-printable characters, the bash code can't handle newlines well
+      continue
+    } else if (value < upperascii) {
+      printf chr[value]
+      new=0
+    } else if (value < upperdot) {
+      printf "."
+      new=0
+    } else if (value < upperslash) {
+      # If it's the start of a new path, only generate a / in 10% of cases
+      if (new && rand() > 0.1) continue
+      printf "/"
+    } else {
+      # If it's the start of a new path, only generate a null in 10% of cases
+      if (new && rand() > 0.1) continue
+      printf "\x00"
+      new=1
+    }
+  }
+}
diff --git a/lib/tests/release.nix b/lib/tests/release.nix
index b93a4236f91e..5d6e340be252 100644
--- a/lib/tests/release.nix
+++ b/lib/tests/release.nix
@@ -6,6 +6,8 @@
 pkgs.runCommand "nixpkgs-lib-tests" {
   buildInputs = [
     pkgs.nix
+    pkgs.jq
+    pkgs.bc
     (import ./check-eval.nix)
     (import ./maintainers.nix {
       inherit pkgs;
@@ -40,5 +42,8 @@ pkgs.runCommand "nixpkgs-lib-tests" {
     echo "Running lib/tests/sources.sh"
     TEST_LIB=$PWD/lib bash lib/tests/sources.sh
 
+    echo "Running lib/tests/path.sh"
+    TEST_LIB=$PWD/lib bash lib/tests/path.sh
+
     touch $out
 ''
-- 
cgit v1.2.3