#!/bin/bash
# Mutation checks for the scheduler's invariants (zero-downtime plan 5, task
# 16). Each mutant rewrites one marked line (// rolloutsim:Mn) in a scratch
# copy of the committed tree (git archive HEAD), never in the checkout, and
# runs TestSimInvariants against it. A clean baseline run of the unmutated
# copy comes first: a kill means nothing if the simulation fails anyway.
#
# A mutant whose invariant the simulation cannot reach names a unit test
# instead (its third field "test:TestName"; zero-downtime flag readiness,
# task 16 rule 2). Its run is that one test (-run '^TestName$'), and the
# test gets a clean baseline run of its own on the unmutated copy too. Such
# a mutant is the exception: each says in the list below why the simulation
# cannot catch it.
#
#   internal/rollout/testdata/rolloutsim/mutate.sh          # 200 seeds
#   internal/rollout/testdata/rolloutsim/mutate.sh 300      # 300 seeds
#   internal/rollout/testdata/rolloutsim/mutate.sh 200 M3   # only M3
#
# The script runs at nice 19 (it re-executes itself under nice if it has to,
# and warns if it cannot) and one run at a time with GOMAXPROCS=2 (the CPU
# budget on shared boxes). Each go test run's timeout grows with the seeds,
# SEEDS * 3 / 100 + 20 minutes (3000 seeds: 110 minutes); the header prints
# it. A fixed 20 minutes was too short for 3000 seeds (round 1).
#
# The simulation's invariants are I1 to I10 (TestSimInvariants' doc). I9
# and I10 run only on the seeds whose failure book is on disk, which the
# simulation turns off when it runs as root (root writes into a read-only
# directory, so it cannot fail a save): as root, M13 to M17 read MISSED.
#
# Execution integrity is recorded apart from detection. A run must build,
# start, and end in its own --- PASS or --- FAIL line for the test it ran
# (TestSimInvariants, or a unit-test mutant's own test), with no panic, no
# timeout and no "rolloutsim: crash at seed" line (a panic of the simulation
# or of the code under test, which the test recovers and reports apart from
# violations). A run that breaks integrity fails the mutant's gate even when
# it also reported the expected violation; that kill is still printed, as a
# diagnostic.
#
# Verdicts:
#   CAUGHT    the run executed intact and reported a violation of the
#             mutant's own invariant ("rolloutsim: I2 violated at seed",
#             any of I1 to I10), or, for a unit-test mutant, its own test
#             ended in --- FAIL
#   BROKEN    the run panicked, timed out, crashed or never ran
#   MISSED    the run passed, or reported only other invariants' violations
#   ERROR     the marker is not on exactly one line, the substitution did not
#             apply, or the copy did not build
# Each baseline (the simulation's, and one per unit test a selected mutant
# names) is PASSED or, like a mutant, BROKEN or FAILED. The simulation's
# baseline runs only when a selected mutant runs the simulation. Exit 1 on
# anything but a PASSED baseline and CAUGHT for every mutant.
#
# A mutant named on the command line that is not in the list below is an
# ERROR, reported before anything runs, and the script exits 1: a typo must
# never pass as a selection that checked nothing.
#
# Scratch: one fresh directory per run, made with mktemp -d under $TMPDIR
# (named zdd5-mut.XXXXXX) and printed first. When the run ends with a PASSED
# baseline and every selected mutant CAUGHT, the whole directory is removed
# on exit. On any other outcome (a failure, an interrupted run) only its tree
# copy is removed, and its path is printed again: the logs stay there to be
# read, and removed by hand after. The script never touches any other path.
set -u
if [ "$(nice)" -lt 19 ] && [ -z "${ROLLOUTSIM_RENICED:-}" ]; then
	ROLLOUTSIM_RENICED=1 exec nice -n 19 "$0" "$@"
fi
if [ "$(nice)" -lt 19 ]; then
	echo "warning: running at niceness $(nice), not 19" >&2
fi
SEEDS=${1:-200}
shift $(($# > 0 ? 1 : 0))
ONLY=" $* "
# Each go test run's timeout, scaled with the seeds (3000 seeds: 110m).
TIMEOUT_MIN=$((SEEDS * 3 / 100 + 20))

# name|file|check|perl substitution applied to the marked line only. check
# is the simulation invariant that must catch the mutant (I1 to I10), or
# test:TestName for a unit-test mutant. The marker match is anchored (\b),
# so rolloutsim:M1 never matches rolloutsim:M10. The substitution is the
# last field, so it may contain "|".
#
# M7 to M12 are zero-downtime flag readiness task 16's:
#   M7   decideHoldRan's Blocks check on the marked build (Astra R3 N7): I1.
#   M8   ClearHoldRanBefore's sequence test (Astra R3 N6): I5, at a good
#        write delivered late, after a hold adoption failed on the host.
#   M9   preRetryLocked never reports a failure stale (ruling 191): I7.
#   M10  a Begin whose save failed runs the attempt anyway (F5): I8, on a
#        seed whose book is on disk, across a read-only window.
#   M11  failCohort halts the cohort on a PreRetry failure (plan review
#        finding 3): I7's cohort check.
#   M12  markLocked keeps the marker's Seq for another execution of the
#        same build (plan review finding 4). A unit test, by rule 2: the
#        simulation cannot reach it. The kill needs a good write whose
#        execution began while a marker of build X stood, then a second
#        execution of X marking the host before that write lands. A wake
#        planned under X's marker boots X as a first wake, whose intent
#        refuses every adoption of the host until it settles, so no second
#        run of X can start inside that window; only an ordinary wake of a
#        build the host served before, under another build's marker, leaves
#        it open, and that needs X installed again and adopted on a hold.
#
# M13 to M17 are zero-downtime flag readiness round 2 task 2's (the
# crash-epoch hard limit), each on a seed whose book is on disk:
#   M13  PublishedEpoch ignores its dirty check: I10. A change made while
#        saves fail moves the generation in memory only; status publishes
#        it, and the last landed file holds another.
#   M14  markLocked's marker set, renewed or replaced moves no generation:
#        I9. A grant issued under X's hold-ran marker, then another hold run
#        of X on the host (a first wake under the marker, stopped before it
#        settles: the simulation's rewakeArm and rewakeRun) renews the marker
#        at the same generation, and the grant, delivered after, clears the
#        newer run's marker. (The plan's witness, X's marker replaced by a
#        failed hold run of Y and Y's marker then cleared by a pointer,
#        catches nothing: the pointer's clear, ClearHoldRanOnPointer, moves
#        the generation on its own line.)
#   M15  the reopen's seq keeps only the file's own seq, halved: I9. The
#        max over the saved generations and markers (highestSaved), which
#        would repair a lowered seq, is not taken, so the reopened book
#        hands out again generations it had published (each restart halves
#        it again), and a grant issued before a restart, still pending,
#        matches a restriction that a failure after it made, typically an
#        intent the restart reconciled.
#   M16  RetryHostAt skips the book-identity comparison: I9. A box rebuild
#        opens a new book whose generations start again from one, so a
#        grant for the old book, still pending, matches a restriction the
#        new one made. One of the two rarest kills (with M17): at 300 seeds
#        it rests on a few seeds (rebuilds are drawn 1 step in 150). So a
#        MISSED for M16 at 300 seeds or fewer is not yet a regression: run
#        it again at 3000 seeds (mutate.sh 3000 M16) before reading it as
#        one.
#   M17  a new record moves the app's generation only from zero (the
#        sequence still advances, so nothing else changes): I9. A new
#        record holds every host of the app (spec §8.4), so a grant issued
#        under X's hold-ran marker on h, then a failure of X on another
#        host that writes X's new record, then the grant delivered: it
#        clears the marker and exempts h from the new record. I9 counts a
#        new record as a fact of every host. The random schedule seldom
#        lines this up (a build with a marker and no record has seldom
#        failed anywhere), so the simulation's rewakeArm makes it: when X
#        has no record, the wake after the Retry is another instance's
#        first wake of X, made to fail. Like M16 it rests on
#        few seeds at 300, and the same rule holds: a MISSED at 300 seeds
#        or fewer is re-run at 3000 before it is read as a regression.
#        (Removing the touch outright leaves the generation zero when the
#        new record is the app's first restriction, so every retry is
#        refused and I7 catches it first, which is not the hole this
#        mutant is for.)
MUTANTS='M1|queue.go|I2|s/if q\.running >= q\.concurrency \{/if false \&\& q.running >= q.concurrency {/
M2|queue.go|I3|s/class := classRecover/class := classAdopt/
M3|queue.go|I1|s/res, err = book\.Record\(rec\)/res, err = Recorded, nil/
M4|queue.go|I4|s/h\.buildRev = q\.nextRev\(\)/_ = q.nextRev()/
M5|wakeplan.go|I1|s/if hasGood \&\& in\.Book\.Blocks\(/if false \&\& in.Book.Blocks(/
M6|wakeplan.go|I1|s/plan\.Fallback = \&good/plan.Fallback = nil/
M7|wakeplan.go|I1|s/if hasGood \&\& in\.Book\.Blocks\(/if false \&\& hasGood \&\& in.Book.Blocks(/
M8|failures.go|I5|s/cur\.Seq >= snap \{/cur.Seq > ^uint64(0) {/
M9|failures.go|I7|s/if r\.Seq == 0 \{/if true {/
M10|scheduler.go|I8|s/; err != nil \{/; errors.Is(err, ErrIntentStands) {/
M11|queue.go|I7|s/if res == PreRetry \{/if false \&\& res == PreRetry {/
M12|failures.go|test:TestAnotherExecutionOfTheMarkedBuildRenewsTheMarker|s/h\.Seq = b\.bumpLocked\(\)/if ok \&\& cur.Build == h.Build { h.Seq = cur.Seq } else { h.Seq = b.bumpLocked() }/
M13|failures.go|I10|s/if b\.dirty \{/if false \&\& b.dirty {/
M14|failures.go|I9|s/b\.touchLocked\(h\.Account, h\.App\)//
M15|failures.go|I9|s/b\.seq = f\.highestSaved\(\)/b.seq = f.Seq \/ 2/
M16|failures.go|I9|s/ \|\| book != b\.idLocked\(\)//
M17|failures.go|I9|s/b\.touchLocked\(r\.Account, r\.App\)/if b.gens[genKey(r.Account, r.App)] == 0 { b.touchLocked(r.Account, r.App) } else { b.bumpLocked() }/'

# Every name selected must be a mutant in the list, checked before any work.
KNOWN=" $(printf '%s\n' "$MUTANTS" | cut -d'|' -f1 | tr '\n' ' ')"
unknown=0
for name in "$@"; do
	if [[ "$KNOWN" != *" $name "* ]]; then
		echo "ERROR     $name: no such mutant (known:${KNOWN% })"
		unknown=1
	fi
done
[ $unknown -eq 0 ] || exit 1

export GOMAXPROCS=2
ROOT=$(git -C "$(dirname "$0")" rev-parse --show-toplevel) || exit 2
SCRATCH=$(mktemp -d "${TMPDIR:?}/zdd5-mut.XXXXXX") || exit 2
echo "scratch: $SCRATCH"
# fail is the run's verdict so far; complete is set only once every
# selected mutant has a verdict. The exit trap removes the scratch
# directory whole only when both say the run passed.
fail=0
complete=0
cleanup() {
	if [ $complete -eq 1 ] && [ $fail -eq 0 ]; then
		rm -rf "$SCRATCH"
	else
		rm -rf "$SCRATCH/tree" "$SCRATCH/orig" "$SCRATCH/gowork"
		echo "scratch kept: $SCRATCH (logs in $SCRATCH/logs; remove it after reading)"
	fi
}
trap cleanup EXIT
P=internal/rollout
# The default build cache is read-only inside a sandbox.
if [ -z "${GOCACHE:-}" ] && [ ! -w "$(go env GOCACHE)" ]; then
	export GOCACHE=$TMPDIR/gocache
fi
# An archive has no .git, so VCS stamping must be off.
export GOFLAGS="${GOFLAGS:-} -buildvcs=false"
mkdir -p "$SCRATCH/tree" "$SCRATCH/orig" "$SCRATCH/logs" "$SCRATCH/gowork" || exit 2
export GOTMPDIR=$SCRATCH/gowork
git -C "$ROOT" archive HEAD | tar -x -C "$SCRATCH/tree" || exit 2
echo "tree: $(git -C "$ROOT" rev-parse --short HEAD)"
echo "seeds: $SEEDS; timeout per run: ${TIMEOUT_MIN}m"
cp -a "$SCRATCH/tree/$P/." "$SCRATCH/orig/" || exit 2

# testOf CHECK: the test a mutant's run executes.
testOf() {
	case "$1" in
	test:*) echo "${1#test:}" ;;
	*) echo TestSimInvariants ;;
	esac
}

# run LOG TEST: one go test call of TEST against the scratch tree, verbose
# so that the test prints its --- PASS or --- FAIL line.
run() {
	(cd "$SCRATCH/tree" && ROLLOUT_SIM_SEEDS="$SEEDS" go test -v -p 1 -count=1 -timeout "${TIMEOUT_MIN}m" \
		-run "^$2\$" ./$P/) >"$1" 2>&1
}

# integrity LOG TEST: empty when the run of TEST executed intact, else what
# broke it.
integrity() {
	if grep -q '\[build failed\]\|\[setup failed\]' "$1"; then
		echo BUILD
	elif grep -q '^panic: test timed out' "$1"; then
		echo TIMEOUT
	elif grep -qE '^(panic: |fatal error: )' "$1"; then
		echo PANIC
	elif grep -q 'rolloutsim: crash at seed' "$1"; then
		echo CRASH
	elif ! grep -qE -- "--- (PASS|FAIL): $2 \(" "$1"; then
		echo NOT-RUN
	fi
}

# found LOG: the invariants the run reported violated, e.g. "I1 I3".
found() {
	grep -oE 'rolloutsim: I[0-9]+ violated at seed' "$1" | awk '{print $2}' | sort -u | tr '\n' ' ' | sed 's/ $//'
}

selected() {
	[ "$ONLY" = "  " ] || [[ "$ONLY" == *" $1 "* ]]
}

# The baselines: the simulation's when a selected mutant runs it, and each
# unit test a selected mutant names, once.
tests=$(while IFS='|' read -r name _ check _; do
	selected "$name" && testOf "$check"
done <<<"$MUTANTS" | awk '!seen[$0]++')
for t in $tests; do
	blog="$SCRATCH/logs/baseline-$t.log"
	what="$t"
	[ "$t" = TestSimInvariants ] && what="$SEEDS seeds"
	run "$blog" "$t"
	broke=$(integrity "$blog" "$t")
	if [ -n "$broke" ]; then
		echo "BROKEN    baseline: $t: $broke; see $blog"
		fail=1
	elif grep -qF -- "--- FAIL: $t (" "$blog"; then
		echo "FAILED    baseline: $t failed on the unmutated tree (violations: $(found "$blog")); see $blog"
		fail=1
	else
		echo "PASSED    baseline: $what"
	fi
done

while IFS='|' read -r name file inv sub; do
	if ! selected "$name"; then
		continue
	fi
	test=$(testOf "$inv")
	marker="rolloutsim:$name"
	src="$SCRATCH/tree/$P/$file"
	# Each marker sits on exactly one line of the package's Go sources.
	lines=$(cat "$SCRATCH/orig"/*.go | grep -cE "$marker\\b")
	if [ "$lines" -ne 1 ]; then
		echo "ERROR     $name: $marker is on $lines lines of $P/*.go, not one"
		fail=1
		continue
	fi
	cp "$SCRATCH/orig/$file" "$src"
	perl -pi -e "if (/\\Q$marker\\E\\b/) { $sub }" "$src"
	if cmp -s "$SCRATCH/orig/$file" "$src"; then
		echo "ERROR     $name: the substitution did not apply to $file"
		fail=1
		continue
	fi
	mutated=$(grep -E "$marker\\b" "$src" | sed 's/^[[:space:]]*//')
	log="$SCRATCH/logs/$name.log"
	run "$log" "$test"
	cp "$SCRATCH/orig/$file" "$src"
	broke=$(integrity "$log" "$test")
	caught=0
	if [ "$test" = TestSimInvariants ]; then
		got=$(found "$log")
		[[ " $got " == *" $inv "* ]] && caught=1
		detail="expects $inv; reported: ${got:-none}; line: $mutated"
	else
		got=passed
		grep -qF -- "--- FAIL: $test (" "$log" && got=failed caught=1
		detail="expects $test to fail; it $got; line: $mutated"
	fi
	if [ "$broke" = BUILD ]; then
		echo "ERROR     $name: the mutant did not build; $detail; see $log"
		fail=1
	elif [ -n "$broke" ]; then
		kill="not caught"
		[ $caught -eq 1 ] && kill="caught (diagnostic only)"
		echo "BROKEN    $name: execution integrity failed: $broke; $kill; $detail; see $log"
		fail=1
	elif [ $caught -eq 1 ]; then
		echo "CAUGHT    $name: $detail"
	else
		echo "MISSED    $name: $detail"
		fail=1
	fi
done <<<"$MUTANTS"
complete=1
exit $fail