#!/usr/bin/env python3
"""Run command lines through real dash and bash, and write down what they did.

The Shell Expansion page has an engine that predicts, for a typed command
line, the argument vector each command receives and the file descriptor table
it inherits. Nothing in this repository can tell whether those predictions are
right except the shells themselves, so this script asks them.

Every case runs three times, once in each shell the page offers:

    dash -c LINE              Debian's Almquist shell, which follows POSIX here
    bash -c LINE              GNU bash, which does not, in places it documents
    bash --posix -c LINE      bash told to follow POSIX, which mostly does

in a fresh scratch directory holding a fixed set of files (dotfiles, a name
with a space, two .xyz files so a pattern can match twice, a README so upper
case sorts first), with LC_ALL=C and a PATH holding nothing but the probe in
scripts/shell-expansion-probe.c, installed under every command name the page
accepts. The probe writes down its argv and its descriptor table, including
which descriptors share an open file description (kcmp), and exits. Standard
input, output and error are three separate files, so a test can tell which of
the three a descriptor ended up as.

What it records per run: the probes' reports in fork order, which files in the
directory were created or truncated, the exit status and whatever the shell
wrote to its standard error. Pipe inode numbers are replaced by the order in
which the pipes are first seen, so two runs of one line compare equal.

It also runs strace on a handful of lines, to record the order of the open and
dup2 calls the shells make for redirections.

    python3 scripts/shell-expansion-oracle.py                  write the fixture
    python3 scripts/shell-expansion-oracle.py --check          rerun, compare, write nothing

The sweep is drawn from a fixed seed, so the same lines are generated every
time; the fixture records the shells' versions, the kernel and the date.
"""
from __future__ import annotations

import argparse
import json
import os
import platform
import random
import re
import shutil
import subprocess
import sys
import tempfile
from datetime import date
from pathlib import Path

ROOT = Path(__file__).resolve().parent.parent
PROBE_SRC = ROOT / "scripts" / "shell-expansion-probe.c"
FIXTURE = ROOT / "tests" / "fixtures" / "shell-expansion-oracle.json"

# The directory every line runs in. Each file holds its own name and a newline,
# so a truncation shows as a size of zero.
FILES = ["README", "a.txt", "b.txt", "c.log", "my file.txt", "x.xyz", "y.xyz",
         ".hidden.txt", ".profile"]
# Every command name the page accepts. None of them is built into either shell,
# which this script checks rather than assumes (see classify_names).
COMMANDS = ["ls", "cat", "wc", "grep", "sort", "rm", "cp", "mv", "touch", "head"]
# Names the page refuses because both shells run them without exec.
BUILTINS = ["echo", "printf", "cd", "pwd", "test", "[", "true", "false", "read",
            "export", "set", "unset", "exec", "eval", "type", "kill", "wait",
            "umask", "shift", "trap", "getopts", "command", "hash", "exit",
            "return", "break", "continue", ":", ".", "alias", "times", "local"]
VARS = {"c": "ls", "d": ".*", "e": "", "f": "my file.txt", "g": "*.txt *.txt",
        "n": "nomatch*", "p": "*", "q": "[ab].txt", "s": "  a.txt   b.txt  ",
        "t": "a.txt", "w": "   ", "x": "*.xyz"}
SHELLS = {"dash": ["/usr/bin/dash", "-c"],
          "bash": ["/usr/bin/bash", "-c"],
          "posix": ["/usr/bin/bash", "--posix", "-c"]}

# The witnesses the page itself prints, and the cases that pin one rule each.
HAND = [
    # splitting before globbing
    "ls $g", 'ls "$g"', "ls *.txt *.txt", "ls $f", 'ls "$f"', "ls $f*", 'ls "$f"*',
    # implicit and explicit nulls
    "ls $e", 'ls "$e"', "ls $e$e", 'ls "$e"$e', "ls ''", "ls a$e", "ls $w", "ls x$w",
    'ls "$e"$w', 'ls $w"$e"', "ls $w''$w", 'ls x"$e"', "ls $s", 'ls "$s"', 'ls x$s"y"',
    # patterns
    "ls *", "ls $p", 'ls "$p"', "ls .*", "ls $d", "ls .?*", "ls ..*", "ls .h*",
    "ls '.'*", "ls \\.*", "ls [ab].txt", "ls [!a].txt", "ls [^a].txt", "ls ?.txt",
    "ls *.TXT", "ls nomatch*", "ls $n", 'ls "$n"', "ls '*.txt'", "ls \\*.txt",
    'ls "*".txt', "ls $q", 'ls "$q"', "ls [a-c]*", "ls [.]*", "ls [.h]*", "ls *e",
    "ls R*", "ls [R]*", "ls [a-]*", "ls []a]*", "ls [a", "ls a]", "ls [", "ls [ab",
    "ls []", "ls [!]", "ls [!]]*", "ls [a-a]*", "ls [c-a]*", "ls [--0]*", "ls *[",
    "ls a[.]txt", "ls a?txt", "ls a*txt", "ls *.t*t", 'ls "a".*', 'ls a"*"',
    'ls a"*"$p', 'ls [a"b"].txt', 'ls ["!"a].txt', 'ls ["^"a].txt', 'ls [a"-"c]*',
    "ls [!.]*", "ls [!a-b]*", 'ls *"."*', "ls ?", "ls ??????", "ls *.???",
    "ls *' '*", "ls *\\ *", "ls my\\ file.txt", "ls my' 'f*", "ls *$e", "ls cost$",
    "ls $.", "ls a{b", "ls a~b",
    # the redirection target, which POSIX does not glob and bash does
    "ls > *.xyz", "ls > $x", 'ls > "$x"', "ls > a*", "ls > R*", "ls > $p",
    "ls > $n", "ls > nomatch*", "ls > $t", "ls > $f", 'ls > "$f"', "ls > $s",
    "ls > $g", "ls > $q", "ls > $w", 'ls > $e"x"', "ls > $e", 'ls > "$e"',
    "ls > $e$e", "ls > ''", "ls < $q", "cat < $f", 'cat < "my file.txt"',
    "cat < my\\ file.txt", "cat <$t", "ls < nofile", "ls $w > $w", 'ls "$e" > o',
    # dup2, left to right
    "ls >o 2>&1", "ls 2>&1 >o", "ls >o 2>o", "ls 2>o 2>&1", "ls 1>o 1>p 1>q",
    "ls >o 2>&1 1>p", "ls 3>o 1>&3", "ls 3>o 4>&3 1>&4 3>&-", "ls 2>&-", "ls <&-",
    "ls >&-", "ls >&2", "ls 1>&5", "ls >o 2>&5", "ls 2>&5 >o", "ls >o 3<nofile",
    "ls 3<a.txt 0<&3", "ls 3<a.txt 3<&-", "ls 5>&-", "ls 2<&1", "ls 1>&0",
    "ls 2>&1 1>&2", "ls 1>&1", "ls 0<a.txt 1<b.txt", "ls 0>o", "ls 1<a.txt",
    "ls 4<&0", "ls <a.txt 2<&0", "ls <&- >o", "ls 0<&- 1>o", "ls 9>o",
    "ls >>c.log", "ls 2>>c.log >c.log", "ls >o 1>>o", "ls 2>/dev/null",
    "ls 3<a.txt >o",
    # where a failed redirection's complaint goes: whatever fd 2 is by then
    "ls 2>o 2>&7", "ls 2>o 1>&7", "ls 2>o 2<nofile", "ls 2>&1 1<nofile",
    "ls 2>o > $e", "ls 2>o > $g", "ls 2<nofile", "ls 2>''", "ls 2>o 1>&7 >p",
    "ls >>c.log 2>&1",
    # no command at all
    "> new.txt", "$e", "$e > new.txt", "$e ls", ">o ls", "2>&1 >o ls a.txt",
    "ls a.txt 2>e b.txt", "$c *.log", "$c $g > $t",
    # the pipe, wired before the command's own redirections
    "ls | wc", "ls 2>&1 | wc", "ls 2>&1 | wc >o", "ls >o | wc", "ls | wc <a.txt",
    "ls | wc | sort", "ls 2>&1 1>/dev/null | wc", "ls 3>o 1>&3 | wc",
    "ls | wc 2>&1 | sort 2>o", "cat <a.txt | wc >o 2>&1", "ls *.txt | grep $g",
    "ls $g | wc", "ls > *.xyz | wc",
]

# strace is asked about these only: the order of open and dup2 is the claim.
TRACED = ["ls >o 2>&1", "ls 2>&1 >o", "ls 3<a.txt >o", "ls 3>o 1>&3 3>&-",
          "ls 2>&1 | wc", "ls >>c.log 2>&1", "ls <a.txt", "ls <&- >o"]


def generate(seed: int = 1979, count: int = 500) -> list[str]:
    """Command lines drawn from the grammar the page accepts, from a fixed seed."""
    rng = random.Random(seed)
    lits = ["a.txt", "b.txt", "c.log", "README", "x.xyz", "nofile", "o",
            "my\\ file.txt", '"my file.txt"', "'my file.txt'", "''", '""',
            '"a b"', "-l"]
    pats = ["*", "*.txt", "*.xyz", "?.txt", "[ab].txt", "[!a]*", "[^a]*", ".*",
            ".?*", "*e", "R*", '"*".txt', "\\*.txt", "'*'.txt", "*' '*",
            "[a-c]*", "[c-a]*", "nomatch*", "[", "[ab", "a]", "*.t*t", "[]a]*",
            ".h*", "[!.]*", "??????"]
    refs = ["$g", '"$g"', "$f", '"$f"', "$e", '"$e"', "$s", '"$s"', "$p",
            '"$p"', "$d", "$q", '"$q"', "$n", "$x", "$t", "$w", "${g}",
            "${f}x", "x${e}y", "$c"]
    targets = ["o", "p", "a.txt", "c.log", "$f", '"$f"', "$e", '"$e"', "*.xyz",
               "$x", "a*", "R*", "$p", "$g", "$q", '"my file.txt"', "$t",
               "$w", "''", "/dev/null", "$s", "$n", '"$g"']
    inputs = ["a.txt", "c.log", '"my file.txt"', "nofile", "$t", "$f", "$q",
              "*.xyz", "[ab].txt", "R*"]

    def word() -> str:
        pool = rng.choice([lits, pats, refs])
        w = rng.choice(pool)
        if rng.random() < 0.3:
            w += rng.choice(rng.choice([lits[:7], pats, refs]))
        return w

    def redir(multi: bool) -> str:
        r = rng.random()
        if r < 0.30:
            return rng.choice(["", "1", "2", "3"]) + rng.choice([">", ">>"]) \
                + rng.choice(["", " "]) + rng.choice(targets)
        if r < 0.45:
            # In a pipeline only an input that already exists, so no member
            # reads a file another member is creating at the same moment.
            pool = inputs if not multi else [i for i in inputs if i != "nofile"]
            return rng.choice(["", "0", "3"]) + "<" + rng.choice(pool)
        return rng.choice(["2>&1", "1>&2", ">&2", "2>&-", "<&-", "1>&3",
                           "0<&3", "3>&1", "2>&3", "3<&0", ">&-", "4>&2"])

    out = []
    while len(out) < count:
        members = rng.choices([1, 2, 3], weights=[70, 22, 8])[0]
        cmds = []
        for _ in range(members):
            parts = []
            # One member in twenty has no command at all, only redirections,
            # which both shells still perform. Never words without a command:
            # the first word would become the command name, and the page
            # accepts only the names above.
            if rng.random() < 0.95:
                parts.append(rng.choice(COMMANDS))
                for _ in range(rng.randint(0, 4)):
                    parts.append(word())
            for _ in range(rng.randint(0, 3)):
                parts.insert(rng.randint(0, len(parts)), redir(members > 1))
            cmds.append(" ".join(parts) if parts else "ls")
        line = " | ".join(cmds)
        if line not in out and line not in HAND:
            out.append(line)
    return out


def build_probe(work: Path) -> Path:
    exe = work / "probe"
    subprocess.run(["cc", "-O2", "-Wall", "-o", str(exe), str(PROBE_SRC)], check=True)
    return exe


def classify(err: str) -> list[str]:
    """What kind of failure each line of the shell's standard error reports."""
    kinds = []
    for line in err.splitlines():
        if "ambiguous redirect" in line:
            kinds.append("ambiguous")
        elif "Bad file descriptor" in line:
            kinds.append("badfd")
        elif re.search(r"No such file|cannot (open|create)|Directory nonexistent", line):
            kinds.append("open")
        elif line.strip():
            kinds.append("other: " + line.split(":", 2)[-1].strip())
    return kinds


def run_line(probe: Path, base: Path, line: str, shell: str) -> dict:
    root = Path(tempfile.mkdtemp(dir=base))
    work = root / "w"
    work.mkdir()
    binb = root / "bin"
    binb.mkdir()
    for c in COMMANDS:
        shutil.copy(probe, binb / c)
    for f in FILES:
        (work / f).write_text(f + "\n")
    (root / "IN").write_text("in\n")
    env = {"PATH": str(binb), "LC_ALL": "C", "PROBE_OUT": str(root / "report")}
    env.update(VARS)
    with open(root / "IN") as i, open(root / "OUT", "w") as o, open(root / "ERR", "w") as e:
        r = subprocess.run(SHELLS[shell] + [line], cwd=work, env=env,
                           stdin=i, stdout=o, stderr=e, timeout=20)
    reports = []
    if (root / "report").exists():
        reports = [json.loads(x) for x in (root / "report").read_text().splitlines()]
    reports.sort(key=lambda p: p["pid"])
    pipes: dict[str, str] = {}

    def norm(t: str) -> str:
        for n, k in (("IN", 0), ("OUT", 1), ("ERR", 2)):
            if t == str(root / n):
                return f"inherited {k}"
        if t.startswith(str(work) + "/"):
            return "file " + t[len(str(work)) + 1:]
        m = re.fullmatch(r"pipe:\[(\d+)\]", t)
        if m:
            pipes.setdefault(m.group(1), f"pipe {len(pipes) + 1}")
            return pipes[m.group(1)]
        return t

    procs = [{"argv": p["argv"],
              "fds": [[f["fd"], norm(f["target"]), f["mode"], f["append"], f["shares"]]
                      for f in p["fds"]]} for p in reports]
    sizes = {p.name: p.stat().st_size for p in work.iterdir()}
    changed = sorted([n, s] for n, s in sizes.items()
                     if n not in FILES or s != len(n) + 1)
    missing = sorted(n for n in FILES if n not in sizes)
    err = (root / "ERR").read_text()
    shutil.rmtree(root)
    return {"status": r.returncode, "procs": procs, "changed": changed,
            # Sorted: the members of a pipeline complain concurrently, so the
            # order their lines reach stderr is not part of the outcome.
            "missing": missing, "errors": sorted(classify(err)),
            "stderr": sorted(re.sub(r"^/usr/bin/(da|ba)sh: (line )?1: ", "", x)
                             for x in err.splitlines())}


def trace(probe: Path, base: Path, line: str, shell: str) -> list[str]:
    """The open and dup2 calls made for the redirections, in order, per process."""
    root = Path(tempfile.mkdtemp(dir=base))
    (root / "bin").mkdir()
    for c in COMMANDS:
        shutil.copy(probe, root / "bin" / c)
    for f in FILES:
        (root / f).write_text(f + "\n")
    env = {"PATH": str(root / "bin"), "LC_ALL": "C", "PROBE_OUT": str(root / "rep")}
    out = root / "trace"
    subprocess.run(["/usr/bin/strace", "-f", "-qq", "-e", "trace=openat,dup2,dup3,execve",
                    "-o", str(out)] + SHELLS[shell] + [line], cwd=root, env=env,
                   stdin=subprocess.DEVNULL, stdout=subprocess.DEVNULL,
                   stderr=subprocess.DEVNULL, check=False, timeout=20)
    text = out.read_text()
    shutil.rmtree(root)
    # strace splits a call that another process interrupts into "<unfinished>"
    # and "<... resumed>" halves; put them back together first.
    pending: dict[str, str] = {}
    calls: list[tuple[str, str]] = []
    for raw in text.splitlines():
        m = re.match(r"(\d+)\s+(.*)$", raw)
        if not m:
            continue
        pid, rest = m.groups()
        if rest.endswith("<unfinished ...>"):
            pending[pid] = rest[: -len("<unfinished ...>")].rstrip()
            continue
        r = re.match(r"<\.\.\. \w+ resumed>(.*)$", rest)
        if r:
            rest = pending.pop(pid, "") + r.group(1)
        calls.append((pid, rest))
    # Per process, the calls made before that process's own execve of a probe,
    # keeping only opens of files in the scratch directory and dup2 between
    # descriptors below 10. Both shells park the descriptors they will restore
    # at 10 and above; those moves are bookkeeping, not the redirection.
    by_pid: dict[str, list[str]] = {}
    done: set[str] = set()
    for pid, c in calls:
        if pid in done:
            continue
        if c.startswith("execve(") and "/bin/" in c and "/usr/bin/" not in c.split(",")[0]:
            done.add(pid)
            continue
        m = re.match(r'openat\(AT_FDCWD, "([^"/]+)", ([A-Z_|]+)(?:, \d+)?\)\s*=\s*(-?\d+)', c)
        if m:
            by_pid.setdefault(pid, []).append(f"open {m.group(1)} {m.group(2)} = {m.group(3)}")
            continue
        m = re.match(r"dup2\((\d+), (\d+)\)\s*=\s*(-?\d+)", c)
        if m and int(m.group(1)) < 10 and int(m.group(2)) < 10:
            by_pid.setdefault(pid, []).append(f"dup2 {m.group(1)} {m.group(2)}")
    return [calls_ for _, calls_ in sorted(by_pid.items(), key=lambda kv: int(kv[0]))]


def classify_names(probe: Path, base: Path) -> dict:
    """Ask each shell whether each name is built in, rather than assuming it."""
    out = {}
    for shell in SHELLS:
        got = {}
        for name in COMMANDS + BUILTINS:
            root = Path(tempfile.mkdtemp(dir=base))
            (root / "bin").mkdir()
            for c in COMMANDS:
                shutil.copy(probe, root / "bin" / c)
            r = subprocess.run(SHELLS[shell] + ['command -V "$1"', "sh", name],
                               cwd=root, env={"PATH": str(root / "bin"), "LC_ALL": "C"},
                               capture_output=True, text=True)
            shutil.rmtree(root)
            said = (r.stdout + r.stderr).strip()
            got[name] = ("builtin" if re.search(r"builtin", said) else
                         "external" if str(root) in said or "/bin/" in said else said)
        out[shell] = got
    return out


def versions() -> dict:
    def first(cmd):
        try:
            return subprocess.run(cmd, capture_output=True, text=True).stdout.strip().splitlines()[0]
        except Exception as e:      # recorded, not hidden
            return f"unavailable: {e}"
    return {"dash": first(["dpkg-query", "-W", "-f", "${Version}\n", "dash"]),
            "bash": first(["/usr/bin/bash", "--version"]),
            "strace": first(["/usr/bin/strace", "-V"]),
            "kernel": platform.release(), "machine": platform.machine(),
            "locale": "LC_ALL=C", "date": date.today().isoformat()}


def main() -> int:
    ap = argparse.ArgumentParser()
    ap.add_argument("--check", action="store_true",
                    help="rerun everything and report differences from the fixture")
    ap.add_argument("--out", default=str(FIXTURE))
    args = ap.parse_args()
    # The scratch area has to allow exec, and /tmp often does not.
    base = Path(tempfile.mkdtemp(prefix="shell-expansion-oracle-",
                                 dir=Path.home() / ".cache"))
    try:
        probe = build_probe(base)
        sweep = generate()
        cases = []
        for kind, lines in (("hand", HAND), ("sweep", sweep)):
            for line in lines:
                cases.append({"line": line, "kind": kind,
                              "shells": {s: run_line(probe, base, line, s) for s in SHELLS}})
        traces = [{"line": line, "shell": s, "procs": trace(probe, base, line, s)}
                  for line in TRACED for s in SHELLS]
        fixture = {"generated_by": "scripts/shell-expansion-oracle.py",
                   "versions": versions(), "files": FILES, "commands": COMMANDS,
                   "builtins": BUILTINS, "vars": VARS, "shells": list(SHELLS),
                   "shell_commands": {k: v[:-1] for k, v in SHELLS.items()},
                   "names": classify_names(probe, base),
                   "seed": 1979, "cases": cases, "traces": traces}
    finally:
        shutil.rmtree(base, ignore_errors=True)
    text = json.dumps(fixture, indent=None, separators=(",", ":"))
    # One case per line, so a regenerated fixture diffs by case.
    text = text.replace(',{"line":', ',\n{"line":')
    if args.check:
        old = json.loads(Path(args.out).read_text())
        diffs = 0
        for a, b in zip(old["cases"], fixture["cases"]):
            if a != b:
                diffs += 1
                print("differs:", a["line"])
        if old["traces"] != fixture["traces"]:
            diffs += 1
            print("the traces differ")
        print(f"{len(fixture['cases'])} cases rerun, {diffs} differ from the fixture")
        return 1 if diffs else 0
    Path(args.out).parent.mkdir(parents=True, exist_ok=True)
    Path(args.out).write_text(text + "\n")
    n = len(fixture["cases"])
    print(f"wrote {args.out}: {n} lines x {len(SHELLS)} shells, "
          f"{len(fixture['traces'])} traces; {fixture['versions']}")
    return 0


if __name__ == "__main__":
    sys.exit(main())