#!/usr/bin/env bash
# Finds tests that catch nothing another test doesn't already catch (Impatient
# Programming, rule 26). `cargo impish mutate` asks the same of an obligation;
# this asks it of each test, across the whole workspace.
# Each mutant cargo-mutants makes is run against the whole suite; every test that
# fails "kills" that mutant. A test that kills nothing, or only mutants other
# tests also kill, is a candidate to delete. It only suggests: contract tests
# are spec, and a test may guard code that is never mutated (.cargo/mutants.toml).
#
#   scripts/kill-matrix.sh 'src/check.rs'           # sweep files, print the report
#   scripts/kill-matrix.sh --report                 # re-print the last sweep
#   scripts/kill-matrix.sh --test contract/check::a_held_contract_passes_and_says_what_it_checked \
#                          'src/check.rs'           # does this one test earn its place?
#
# Nightly (.github/workflows/kill-matrix.yml) sweeps one small shard and adds it
# to the results so far; once every shard has run it files one issue per suspect:
#
#   scripts/kill-matrix.sh --shard 7/16 --data DIR [--file-issues]
#
# Test ids are <target>/<path>, e.g. `contract/…` for tests/contract.
# KILLMX_OUT (default /tmp/impish-killmx) holds cargo-mutants output;
# KILLMX_JOBS (default 1) sets cargo-mutants -j. Runs niced.
set -euo pipefail

out="${KILLMX_OUT:-/tmp/impish-killmx}"
export CARGO_BUILD_JOBS="${CARGO_BUILD_JOBS:-4}" RUST_TEST_THREADS="${RUST_TEST_THREADS:-4}"
# Tests that check structure, not behaviour: they kill nothing by design.
no_kills_expected='^(architecture/|contract/the_attribute_made_the_contract_tests$)'
max_new_issues=3

mkdir -p "$out"

# The workspace: cargo-impish, impish-core and the impish attribute.
mutants() { nice -n 19 cargo mutants --workspace -j "${KILLMX_JOBS:-1}" --no-shuffle "$@"; }

# Sets the array `args` to `-f <glob>` for each glob (bash 3.2 has no mapfile).
globs() { args=(); for g in "$@"; do args+=(-f "$g"); done; }

# "mutant<TAB>outcome<TAB>log" for every mutant in a cargo-mutants output dir.
outcomes() {
  jq -r '.outcomes[] | select(.scenario != "Baseline")
         | [.scenario.Mutant.name, .summary, .log_path] | @tsv' "$1/mutants.out/outcomes.json"
}

# "<target>/<path>" for every test with result $2 (ok or FAILED) in a test log.
# cargo-mutants runs cargo verbosely, so each binary shows as
# `Running `.../deps/<target>-<hash>``, coloured when CARGO_TERM_COLOR=always.
tests_in_log() {
  awk -v want="$2" '
    { gsub(/\033\[[0-9;]*m/, "") }
    /^ *Running / && match($0, /\/deps\/[A-Za-z0-9_]+-[0-9a-f]+/) {
      t = substr($0, RSTART + 6, RLENGTH - 6); sub(/-[0-9a-f]+$/, "", t); target = t; next
    }
    $1 == "test" && $3 == "..." && $4 == want { print target "/" $2 }
  ' "$1"
}

# Writes $out/matrix.tsv ("mutant<TAB>test" per kill) and $out/tests.txt.
collect() {
  local dir="$out/mutants.out" name summary log
  [ -f "$dir/outcomes.json" ] || { echo "no sweep in $out; run a sweep first" >&2; exit 2; }
  outcomes "$out" | while IFS=$'\t' read -r name summary log; do
    [ "$summary" = CaughtMutant ] || continue
    tests_in_log "$dir/$log" FAILED | M="$name" awk '{ print ENVIRON["M"] "\t" $0 }'
  done > "$out/matrix.tsv"
  tests_in_log "$dir/log/baseline.log" ok | sort -u > "$out/tests.txt"
}

# Report over a matrix and a test list. Also writes "<test><TAB>kills" for each
# suspect to $3: tests that kill nothing, and the tests that can be removed
# together (not every test without unique kills: two tests that only duplicate
# each other can't both go).
report() {
  local matrix="$1" tests="$2" suspects="$3"
  # Old rows for tests that no longer exist are dropped.
  awk -F'\t' 'FNR == NR { live[$0]; next } $2 in live' "$tests" "$matrix" > "$out/live.tsv"
  awk -F'\t' -v suspects="$suspects" -v quiet="$no_kills_expected" '
    FNR == NR { kills[$2] = kills[$2] SUBSEP $1; n[$2]++; by[$1]++; m[$1]; next }
    { all[$0] }
    END {
      for (t in n) {
        split(substr(kills[t], 2), ks, SUBSEP)
        for (i in ks) if (by[ks[i]] == 1) uniq[t]++
      }
      # Greedy set cover: keep the test covering most uncovered mutants until all
      # are covered. The rest can go together without losing a kill.
      left = length(m)
      while (left > 0) {
        best = ""; bestn = 0
        for (t in n) if (!(t in keep)) {
          c = 0; split(substr(kills[t], 2), ks, SUBSEP)
          for (i in ks) if (!(ks[i] in covered)) c++
          if (c > bestn || (c == bestn && c > 0 && t < best)) { best = t; bestn = c }
        }
        if (bestn == 0) break
        keep[best]; split(substr(kills[best], 2), ks, SUBSEP)
        for (i in ks) if (!(ks[i] in covered)) { covered[ks[i]]; left-- }
      }
      printf "%d caught mutant(s), killed by %d of %d test(s).\n\n", length(m), length(n), length(all)
      print "Tests that kill something (kills, unique kills):"
      cmd = "sort -k3"
      for (t in n) printf "  %4d %4d  %s%s\n", n[t], uniq[t] + 0, t, (t in keep) ? "" : "   <- removable" | cmd
      close(cmd)
      r = 0; for (t in n) if (!(t in keep)) r++
      printf "\n%d test(s) can be removed together without losing a kill (marked above).\n", r
      z = 0; for (t in all) if (!(t in n)) z++
      printf "%d test(s) killed nothing in what was swept.\n", z
      for (t in n) if (!(t in keep)) print t "\t" n[t] > suspects
      for (t in all) if (!(t in n) && t !~ quiet) print t "\t0" > suspects
      close(suspects)
    }
  ' "$out/live.tsv" "$tests"
}

sweep() {
  local shard="" data="" file_issues="" args
  while [ $# -gt 0 ]; do
    case "$1" in
      --shard) shard="$2"; shift 2 ;;
      --data) data="$2"; shift 2 ;;
      --file-issues) file_issues=1; shift ;;
      *) break ;;
    esac
  done
  [ $# -gt 0 ] || [ -n "$shard" ] || { echo "give file glob(s) or --shard k/n" >&2; exit 2; }
  args=()
  [ $# -eq 0 ] || globs "$@"
  [ -z "$shard" ] || args+=(--shard "$shard")
  rm -rf "$out/mutants.out"
  # --no-fail-fast keeps cargo test running every test binary, so each mutant's
  # log names every test that killed it, not just the first.
  mutants "${args[@]}" --cargo-test-arg=--no-fail-fast --output "$out" || true
  collect

  if [ -z "$data" ]; then
    report "$out/matrix.tsv" "$out/tests.txt" "$out/suspects.tsv"
    echo; echo "Matrix (mutant, killing test): $out/matrix.tsv"
    return
  fi
  [ -n "$shard" ] || { echo "--data needs --shard" >&2; exit 2; }
  local k="${shard%/*}" total="${shard#*/}" done_shards
  mkdir -p "$data/shards"
  cp "$out/matrix.tsv" "$data/shards/$k.tsv"
  cp "$out/tests.txt" "$data/tests.txt"
  done_shards=$(find "$data/shards" -name '*.tsv' | wc -l | tr -d ' ')
  echo "Shard $shard swept. $done_shards of $total shard(s) have results."
  echo
  cat "$data"/shards/*.tsv > "$out/all.tsv"
  report "$out/all.tsv" "$data/tests.txt" "$out/suspects.tsv" | tee "$data/REPORT.md"

  if [ -n "$file_issues" ]; then
    if [ "$done_shards" -lt "$total" ]; then
      echo; echo "No issues filed until every shard has run."
    else
      file_issues "$out/suspects.tsv" "$out/all.tsv"
    fi
  fi
}

# One issue per suspect test, never twice for the same test (closed = keep it).
file_issues() {
  local suspects="$1" matrix="$2" t kills filed=0 body
  gh label create kill-matrix --color BFD4F2 \
    --description "Test the kill matrix suspects adds nothing" 2>/dev/null || true
  while IFS=$'\t' read -r t kills; do
    [ "$filed" -lt "$max_new_issues" ] || break
    [ -z "$(gh issue list --label kill-matrix --state all --search "\"$t\" in:title" --json number -q '.[].number')" ] || continue
    if [ "$kills" -eq 0 ]; then
      body="No mutant made this test fail, across a full kill-matrix cycle. It would pass whatever the code did."
    else
      body="Every mutant this test kills is also killed by another test:"$'\n\n'"$(T="$t" awk -F'\t' '
        FNR == NR { if ($2 == ENVIRON["T"]) mine[$1]; next }
        ($1 in mine) && $2 != ENVIRON["T"] { print "- `" $1 "`: also `" $2 "`" }' "$matrix" "$matrix" | sort -u | head -20)"
    fi
    body+=$'\n\n'"Delete it, or close this issue to keep it (for example, a contract test that is spec). Found by \`scripts/kill-matrix.sh\`."
    gh issue create --label kill-matrix --title "Kill matrix: \`$t\` catches nothing new" --body "$body" >/dev/null
    echo "Filed an issue for $t"
    filed=$((filed + 1))
  done < "$suspects"
}

# Escapes a mutant name for an exact cargo-mutants --re match.
# shellcheck disable=SC2016 # the $ in the sed class is a literal
exact_re() { printf '^%s$' "$(printf '%s' "$1" | sed 's/[][\\.|$(){}?+*^]/\\&/g')"; }

target_args() {
  local target="${1%%/*}"
  case "$target" in
    cargo_impish) echo "--bin cargo-impish" ;;
    impish_core) echo "-p impish-core --lib" ;;
    impish) echo "-p impish --lib" ;;
    *) echo "--test $target" ;;
  esac
}

one_test() {
  local id="$1"; shift
  [ $# -gt 0 ] || { echo "give the file glob(s) the test covers, e.g. 'src/main.rs'" >&2; exit 2; }
  [[ "$id" == */* ]] || { echo "test id must be <target>/<path>, e.g. contract/check::a_held_contract_passes_and_says_what_it_checked" >&2; exit 2; }
  local path="${id#*/}" args re k n
  globs "$@"

  echo "1/2  Which mutants does $id kill on its own?"
  rm -rf "$out/one"
  # shellcheck disable=SC2046 # target_args is two words on purpose
  # One test makes a tiny baseline, so the auto timeout would be too short.
  mutants "${args[@]}" --minimum-test-timeout 120 --output "$out/one" \
    -- $(target_args "$id") -- "$path" --exact || true
  outcomes "$out/one" | awk -F'\t' '$2 == "CaughtMutant" { print $1 }' > "$out/one.kills"
  n=$(wc -l < "$out/one.kills" | tr -d ' ')
  if [ "$n" -eq 0 ]; then
    echo "$id kills nothing in $*: a candidate to delete (or it tests other code)."
    return
  fi
  sed 's/^/     /' "$out/one.kills"

  echo "2/2  Does the rest of the suite catch those $n mutant(s) without it?"
  re=()
  while IFS= read -r k; do re+=(--re "$(exact_re "$k")"); done < "$out/one.kills"
  rm -rf "$out/rest"
  mutants "${args[@]}" "${re[@]}" --output "$out/rest" -- -- --skip "$path" --exact || true
  outcomes "$out/rest" | awk -F'\t' '$2 == "MissedMutant" { print $1 }' > "$out/rest.missed"

  n=$(wc -l < "$out/rest.missed" | tr -d ' ')
  if [ "$n" -eq 0 ]; then
    echo "Every kill is shared: $id is a candidate to delete."
  else
    echo "Keep $id: it alone catches $n mutant(s):"
    sed 's/^/     /' "$out/rest.missed"
  fi
}

case "${1:-}" in
  --report) collect; report "$out/matrix.tsv" "$out/tests.txt" "$out/suspects.tsv" ;;
  --test) [ $# -ge 2 ] || { echo "--test needs a test id" >&2; exit 2; }; shift; one_test "$@" ;;
  -h | --help | "") sed -n '2,22p' "$0" | sed 's/^# \{0,1\}//' ;;
  *) sweep "$@" ;;
esac