open-standards/scripts/wai-conformance-lists.py

#!/usr/bin/env python3
"""wai-conformance-lists.py: the lists wai-conformance.yml runs, derived from the files that
own them, so a change adds a file instead of editing the workflow's shared lists.

Each list below used to be kept by hand in the workflow, and every new module of WAI appended
to it, so any two branches that added one conflicted. Each is now read at run time from its
source:

  .github/wai-conformance/verifiers/*.sh  one file a step of the independent verifiers: its
                                          shell body, and a header of `# key: value` lines that
                                          gives its features, binaries, paths and order. From
                                          them: WAI_FEATURES, WAI_PQ_FEATURES and
                                          WAI_RELEASE_FEATURES, the binaries and tests the job
                                          builds first, the steps it runs, the feature lists the
                                          features-alone job checks, and the paths the workflow's
                                          gate runs on.
  .github/wai-conformance/corpora/*.txt   one file a cargo-class corpus: its tool and directory.
                                          The cargo-classes corpus loop runs them, with the
                                          features their tools require (Cargo.toml) and the
                                          step's own.
  wai/wai-rs/tests/*.rs                   a test file whose line `// wai-conformance: <tag>...`
                                          names a tag is run by the steps that take that tag:
                                          int-kernels (both profiles), int-kernels-release (the
                                          release profile only), int-kernels-amd (the AVX-512
                                          host). Their features are the tests' required-features
                                          and the step's own.

A verifier file's header (the leading `# key: value` lines; the first other line ends it):

  step               its name in the log (required)
  order              an integer: steps run in ascending order, a tie by file name (required)
  features           feature lists, space-separated, each comma-joined: each compiles alone in
                     the features-alone job, and every feature in them joins the build's list
  alone              the lists features-alone checks instead of `features`; `-` for none
  build              union (the default: WAI_FEATURES) or pq (WAI_PQ_FEATURES)
  release-features   features of the optimised build (WAI_RELEASE_FEATURES)
  bins, pq-bins      binaries the job builds first and copies to $RUNNER_TEMP/wai-bins/union or
                     /pq, beside every `wai-bins/union/NAME` and `wai-bins/pq/NAME` the body names
  paths              globs whose change runs the workflow (each under one of its `paths:` globs)
  working-directory  where the body runs, from the repository root (default wai)

The tests the job builds first are the `--test NAME` of the body's lines that build with
"$WAI_FEATURES", and with "$WAI_RELEASE_FEATURES" for the optimised build.

Commands (the workflow runs the first group):

  env                      WAI_FEATURES=..., WAI_PQ_FEATURES=..., WAI_RELEASE_FEATURES=...
  prebuild                 the shell script that builds the binaries and tests first
  run [--only SLUG]...     every verifier step in order, each in a log group; the first that
                           fails stops the run with its exit status
  alone                    the feature lists features-alone checks, one a line
  paths                    the paths the verifier files bring to the gate, one a line
  tests TAG...             `--test NAME` for every test file that carries one of the tags
  features TAG... [--extra-features A,B]
                           the tests' required-features with A,B, comma-joined
  test-tagged TAG... [--extra-features A,B] -- ARGS...
                           cargo test ARGS --features <features> <tests>, printed, then run
  corpora [--verify] [--extra-features A,B]
                           the corpora, `name bin dir` a line; with --verify, run each tool's
                           verify over its corpus (cargo run), each in a log group
  dry-run [--ref REF]      every list and every step the workflow would run, in a stable form;
                           of the tree at REF instead with --ref, read from its files or, before
                           they existed, from the lists its workflow kept by hand. It ends with
                           the cargo command lines of the steps outside the verifiers' job that
                           take derived lists (the integer kernels' two steps, the corpus step,
                           int-kernels-amd, the features-alone loop), read from the workflow's own
                           step text and evaluated, each in one form (flags and features
                           sorted, each target once), and per shell family when the unix legs
                           and the Windows leg differ. A reviewer diffs two dry-runs: the same
                           lines are the same builds and tests.
  baseline --ref REF       the lists REF's workflow kept by hand, as JSON
  check                    every file above is well formed and names what exists
  selftest [--exact]       check, then every list derived here holds every entry of
                           .github/wai-conformance/baseline.json (the hand lists of the commit
                           that moved them out), and every step it names still runs; --exact
                           requires the lists equal, and each step the same body and directory
                           as the hand list's step of its name, in the same order (a step or a
                           corpus the tree adds is named as an addition)

Standard library only; runs on the Python 3.9 the runner images carry. --root DIR reads
another tree.
"""
from __future__ import annotations

import importlib.util
import json
import os
import re
import shlex
import shutil
import subprocess
import sys
import tempfile

HERE = os.path.dirname(os.path.abspath(__file__))
VERIFIERS = ".github/wai-conformance/verifiers"
CORPORA = ".github/wai-conformance/corpora"
BASELINE = ".github/wai-conformance/baseline.json"
WORKFLOW = ".github/workflows/wai-conformance.yml"
CRATE = "wai/wai-rs"
TAGS = ("int-kernels", "int-kernels-release", "int-kernels-amd")

VERIFIER_KEYS = {
    "step": "one", "order": "one", "features": "many", "alone": "many", "build": "one",
    "release-features": "many", "bins": "many", "pq-bins": "many", "paths": "many",
    "working-directory": "one",
}
CORPUS_KEYS = {"corpus": "one", "order": "one", "bin": "one", "dir": "one"}
HEADER = re.compile(r"^# ([a-z][a-z-]*): ?(.*)$")
MARKER = re.compile(r"^//\s*wai-conformance:\s*(.*?)\s*$", re.M)


class Bad(Exception):
    pass


def uniq(xs):
    out, seen = [], set()
    for x in xs:
        if x not in seen:
            seen.add(x)
            out.append(x)
    return out


def gate_module(root):
    """scripts/pr-touches-paths.py, imported: the gate's own reading of paths and headers."""
    path = os.path.join(root, "scripts", "pr-touches-paths.py")
    if not os.path.isfile(path):
        path = os.path.join(HERE, "pr-touches-paths.py")
    spec = importlib.util.spec_from_file_location("pr_touches_paths", path)
    mod = importlib.util.module_from_spec(spec)
    spec.loader.exec_module(mod)
    return mod


# ---------------------------------------------------------------------------- the files


def read_header(path, keys, label):
    """(header, body, errors) of a file whose leading `# key: value` lines are its header;
    `label` names it in the errors. The body is what follows the leading comment block
    (header and prose)."""
    with open(path, encoding="utf-8") as fh:
        lines = fh.read().split("\n")
    head, errs, i = {}, [], 0
    while i < len(lines):
        m = HEADER.match(lines[i])
        if not m:
            break
        k, v = m.group(1), m.group(2).strip()
        if k not in keys:
            errs.append(f"{label}: line {i + 1}: `{k}` is not a key of this file ({', '.join(sorted(keys))})")
        elif keys[k] == "one":
            if k in head:
                errs.append(f"{label}: line {i + 1}: `{k}` is given twice")
            head[k] = v
        else:
            head.setdefault(k, []).extend(v.split())
        i += 1
    while i < len(lines) and lines[i].startswith("#"):
        i += 1
    body = "\n".join(lines[i:]).rstrip("\n")
    return head, body, errs


def joined(body):
    """The body's lines with `\\` continuations joined."""
    return re.sub(r"\\\n\s*", " ", body).split("\n")


def verifiers(root):
    d = os.path.join(root, VERIFIERS)
    if not os.path.isdir(d):
        raise Bad(f"{VERIFIERS}: no such directory")
    mods, errs = [], []
    for f in sorted(os.listdir(d)):
        if not f.endswith(".sh"):
            continue
        rel = f"{VERIFIERS}/{f}"
        h, body, e = read_header(os.path.join(d, f), VERIFIER_KEYS, rel)
        errs += e
        for k in ("step", "order"):
            if k not in h:
                errs.append(f"{rel}: no `{k}:` line in its header")
        try:
            order = int(h.get("order", "0"))
        except ValueError:
            errs.append(f"{rel}: order `{h.get('order')}` is not an integer")
            order = 0
        build = h.get("build", "union")
        if build not in ("union", "pq"):
            errs.append(f"{rel}: build `{build}` is neither union nor pq")
        alone = h.get("alone")
        if alone == ["-"]:
            alone = []
        elif alone is not None and "-" in alone:
            errs.append(f"{rel}: alone `-` stands alone")
        if not body.strip():
            errs.append(f"{rel}: no body: the step would run nothing")
        mods.append({
            "slug": f[:-3], "file": rel, "step": h.get("step", ""), "order": order,
            "features": h.get("features", []), "alone": alone, "build": build,
            "release": h.get("release-features", []), "bins": h.get("bins", []),
            "pq_bins": h.get("pq-bins", []), "paths": h.get("paths", []),
            "wd": h.get("working-directory", "wai"), "body": body,
        })
    mods.sort(key=lambda m: (m["order"], m["slug"]))
    seen = {}
    for m in mods:
        if m["step"] and m["step"] in seen:
            errs.append(f"{m['file']}: step `{m['step']}` is also {seen[m['step']]}'s")
        seen.setdefault(m["step"], m["file"])
    return mods, errs


def corpora(root):
    d = os.path.join(root, CORPORA)
    if not os.path.isdir(d):
        raise Bad(f"{CORPORA}: no such directory")
    out, errs = [], []
    for f in sorted(os.listdir(d)):
        if not f.endswith(".txt"):
            continue
        rel = f"{CORPORA}/{f}"
        h, body, e = read_header(os.path.join(d, f), CORPUS_KEYS, rel)
        errs += e
        for k in CORPUS_KEYS:
            if k not in h:
                errs.append(f"{rel}: no `{k}:` line")
        if body.strip():
            errs.append(f"{rel}: holds lines after its header; a corpus file is its header alone")
        try:
            order = int(h.get("order", "0"))
        except ValueError:
            errs.append(f"{rel}: order `{h.get('order')}` is not an integer")
            order = 0
        out.append({"slug": f[:-4], "file": rel, "corpus": h.get("corpus", ""), "order": order,
                    "bin": h.get("bin", ""), "dir": h.get("dir", "")})
    out.sort(key=lambda c: (c["order"], c["slug"]))
    return out, errs


def cargo_targets(root):
    """{(kind, name): required-features or []} of the crate's [[bin]] and [[test]] entries,
    and the feature names of its [features] table."""
    with open(os.path.join(root, CRATE, "Cargo.toml"), encoding="utf-8") as fh:
        text = fh.read()
    targets = {}
    for block in re.split(r"^\[\[", text, flags=re.M)[1:]:
        kind = block.split("]]", 1)[0]
        body = re.split(r"^\[", block[len(kind) + 2:], flags=re.M)[0]
        name = re.search(r'^name\s*=\s*"([^"]+)"', body, re.M)
        if not name:
            continue
        rf = re.search(r"^required-features\s*=\s*\[(.*?)\]", body, re.M | re.S)
        targets[(kind, name.group(1))] = sorted(re.findall(r'"([^"]+)"', rf.group(1))) if rf else []
    sec = re.search(r"^\[features\]\n(.*?)(?=^\[)", text, re.M | re.S)
    feats = set(re.findall(r"^([A-Za-z0-9_-]+)\s*=", sec.group(1), re.M)) if sec else set()
    return targets, feats


def markers(root):
    """{test name: [tags]} of the crate's test files that carry a `wai-conformance:` line."""
    tdir = os.path.join(root, CRATE, "tests")
    out = {}
    for f in sorted(os.listdir(tdir)):
        if not f.endswith(".rs"):
            continue
        with open(os.path.join(tdir, f), encoding="utf-8") as fh:
            found = MARKER.findall(fh.read())
        if found:
            out[f[:-3]] = uniq(t for line in found for t in line.split())
    return out


# ------------------------------------------------------------------------- derivations


def derive(mods):
    union = [m for m in mods if m["build"] == "union"]
    pq = [m for m in mods if m["build"] == "pq"]
    feats = lambda ms: uniq(f for m in ms for lst in m["features"] for f in lst.split(","))
    tests_with = lambda var: uniq(
        t for m in mods for line in joined(m["body"]) if f'"${var}"' in line for t in re.findall(r"--test[ =]([A-Za-z0-9_-]+)", line))
    bins_of = lambda key, build: uniq(
        b for m in mods for b in m[key] + re.findall(rf"wai-bins/{build}/([A-Za-z0-9_-]+)", m["body"]))
    return {
        "WAI_FEATURES": feats(union),
        "WAI_PQ_FEATURES": feats(pq),
        "WAI_RELEASE_FEATURES": uniq(f for m in mods for f in m["release"]),
        "union_bins": bins_of("bins", "union"),
        "pq_bins": bins_of("pq_bins", "pq"),
        "union_tests": tests_with("WAI_FEATURES"),
        "release_tests": tests_with("WAI_RELEASE_FEATURES"),
        "alone": uniq(lst for m in mods for lst in (m["features"] if m["alone"] is None else m["alone"])),
        "paths": uniq(p for m in mods for p in m["paths"]),
    }


def tagged(root, tags):
    return sorted(t for t, ts in markers(root).items() if set(ts) & set(tags))


def tagged_features(root, tags, extra):
    targets, _ = cargo_targets(root)
    out = set(extra)
    for t in tagged(root, tags):
        out |= set(targets.get(("test", t)) or [])
    return sorted(out)


def corpora_features(root, cs, extra):
    targets, _ = cargo_targets(root)
    out = set(extra)
    for c in cs:
        out |= set(targets.get(("bin", c["bin"])) or [])
    return sorted(out)


def prebuild(d):
    """The build step's script: the binaries the steps run, copied per build, then the test
    builds every step finds fresh. The order matters (see the step's comment)."""
    s = ["set -euo pipefail", 'mkdir -p "$RUNNER_TEMP/wai-bins/union" "$RUNNER_TEMP/wai-bins/pq"']
    def build(var, bins, dest):
        if not bins:
            return
        s.append(f'cargo build --no-default-features --features "${var}" \\')
        s.append("  " + " ".join(f"--bin {b}" for b in bins))
        s.append(f"for b in {' '.join(bins)}; do")
        s.append(f'  cp "${{CARGO_TARGET_DIR:-target}}/debug/$b" "$RUNNER_TEMP/wai-bins/{dest}/"')
        s.append("done")
    build("WAI_FEATURES", d["union_bins"], "union")
    if d["pq_bins"]:
        s.append("# Copied before this build replaces target/debug's copies of the ones it shares.")
    build("WAI_PQ_FEATURES", d["pq_bins"], "pq")
    s.append('cargo test --no-run --no-default-features --features "$WAI_FEATURES" --lib \\')
    s.append("  " + " ".join(f"--test {t}" for t in d["union_tests"]))
    if d["release_tests"]:
        s.append('cargo test --release --no-run --no-default-features --features "$WAI_RELEASE_FEATURES" \\')
        s.append("  " + " ".join(f"--test {t}" for t in d["release_tests"]))
    return "\n".join(s) + "\n"


def workflow_extras(text):
    """The features the workflow's steps add to their derived lists: {command: [features]},
    the command being what precedes `--extra-features` on the step's line."""
    out = {}
    for m in re.finditer(r"wai-conformance-lists\.py ((?:[a-z-]+ )+)--extra-features ([A-Za-z0-9_,-]+)", text):
        out.setdefault(m.group(1).strip(), m.group(2).split(","))
    return out


def wide_globs(text):
    """The globs the workflow's gate replaces with the verifier files' paths (--wide)."""
    return re.findall(r"--wide '([^']+)'", text)


def gate_paths(root):
    """What the gate runs on, as the gate reads it (scripts/pr-touches-paths.py with the
    workflow's --paths-from and --wide): the workflow's paths but the wide ones, and the
    verifier files' paths."""
    gate = gate_module(root)
    from pathlib import Path
    wf = os.path.join(root, WORKFLOW)
    with open(wf, encoding="utf-8") as fh:
        text = fh.read()
    dirs = [Path(os.path.join(root, d)) for d in re.findall(r"--paths-from (\S+)", text)]
    globs = gate.gate_globs(Path(wf), dirs, wide_globs(text))
    if globs is None:
        raise Bad(f"the gate cannot read {WORKFLOW}'s paths with its --paths-from and --wide: it would run on every change")
    return uniq(globs)


def from_tree(root):
    """Every list, as this tree's files give them."""
    mods, errs = verifiers(root)
    cs, e2 = corpora(root)
    if errs + e2:
        raise Bad("\n".join(errs + e2))
    with open(os.path.join(root, WORKFLOW), encoding="utf-8") as fh:
        text = fh.read()
    x = workflow_extras(text)
    d = derive(mods)
    dbg = tagged(root, ["int-kernels"])
    rel = tagged(root, ["int-kernels", "int-kernels-release"])
    return {
        "paths": gate_paths(root),
        "WAI_FEATURES": d["WAI_FEATURES"], "WAI_PQ_FEATURES": d["WAI_PQ_FEATURES"],
        "WAI_RELEASE_FEATURES": d["WAI_RELEASE_FEATURES"],
        "union_bins": d["union_bins"], "pq_bins": d["pq_bins"],
        "union_tests": d["union_tests"], "release_tests": d["release_tests"],
        "alone": d["alone"],
        "steps": [{"step": m["step"], "wd": m["wd"], "body": m["body"]} for m in mods],
        "int_kernels_debug_features": tagged_features(root, ["int-kernels"], x.get("test-tagged int-kernels", [])),
        "int_kernels_debug_tests": dbg,
        "int_kernels_release_features": tagged_features(root, ["int-kernels", "int-kernels-release"], x.get("test-tagged int-kernels int-kernels-release", [])),
        "int_kernels_release_tests": rel,
        "int_kernels_amd_features": tagged_features(root, ["int-kernels"], x.get("features int-kernels", [])),
        "int_kernels_amd_tests": tagged(root, ["int-kernels-amd"]),
        "corpora_features": corpora_features(root, cs, x.get("corpora --verify", [])),
        "corpora": [f"{c['corpus']} {c['bin']} {c['dir']}" for c in cs],
    }


# ------------------------------------------------- the lists a workflow kept by hand


def job_steps(text, job):
    """[{name, wd, body, if, shell}] of a job's steps, read from the workflow text."""
    lines = text.split("\n")
    start = next((i for i, l in enumerate(lines) if l == f"  {job}:"), None)
    if start is None:
        raise Bad(f"{WORKFLOW} has no job `{job}`")
    end = next((i for i in range(start + 1, len(lines)) if re.match(r"^  [a-z0-9_-]+:\s*$", lines[i])), len(lines))
    out, i = [], start
    while i < end:
        m = re.match(r"^      - name: (.*)$", lines[i])
        i += 1
        if not m:
            continue
        s = {"name": m.group(1).strip(), "wd": None, "body": None, "if": None, "shell": None}
        while i < end and lines[i].startswith("        "):
            k = re.match(r"^        ([a-z-]+): ?(.*)$", lines[i])
            if k and k.group(1) == "run" and k.group(2) == "|":
                b = []
                i += 1
                while i < end and (lines[i].startswith("          ") or not lines[i].strip()):
                    b.append(lines[i][10:])
                    i += 1
                s["body"] = "\n".join(b).rstrip("\n")
                continue
            if k and k.group(1) == "run":
                s["body"] = k.group(2)
            elif k and k.group(1) == "working-directory":
                s["wd"] = k.group(2)
            elif k and k.group(1) in ("if", "shell"):
                s[k.group(1)] = k.group(2).strip()
            i += 1
        out.append(s)
    return out


def steps_of_job(text, job):
    """[(name, working-directory, run body)] of a job's steps, read from the workflow text."""
    return [(s["name"], s["wd"], s["body"]) for s in job_steps(text, job)]


def from_hand_lists(root):
    """Every list, as a workflow that kept them by hand states them (before this change)."""
    gate = gate_module(root)
    from pathlib import Path
    wf = os.path.join(root, WORKFLOW)
    with open(wf, encoding="utf-8") as fh:
        text = fh.read()
    env = lambda k: re.search(rf"^      {k}: (.*)$", text, re.M).group(1).split(",")
    iv = steps_of_job(text, "independent-verifiers")
    b = next(n for n, s in enumerate(iv) if s[0].startswith("Build wai-rs once"))
    build = joined(iv[b][2])
    pick = lambda pat: next(l for l in build if re.search(pat, l))
    union_build = pick(r'cargo build .*"\$WAI_FEATURES"')
    pq_build = pick(r'cargo build .*"\$WAI_PQ_FEATURES"')
    union_test = pick(r'cargo test --no-run .*"\$WAI_FEATURES"')
    rel_test = pick(r'cargo test --release --no-run')
    fa = steps_of_job(text, "features-alone")
    loop = re.search(r"for f in (.*?); do", " ".join(joined(fa[[s[0] for s in fa].index("wai-rs, each feature list alone")][2])))
    cc = steps_of_job(text, "cargo-classes")
    ik = lambda name: next(s[2] for s in cc if s[0] == name)
    dbg = ik("Fast integer kernels ≡ reference kernels (overflow checks on)")
    rel = ik("Fast integer kernels ≡ reference kernels (release, overflow checks off)")
    corp = ik("Every cargo-class corpus reproduces its frozen hashes (unix)")
    amd = steps_of_job(text, "int-kernels-amd")[-1][2]
    tests = lambda l: re.findall(r"--test ([A-Za-z0-9_-]+)", l)
    feats = lambda l: re.search(r"--features (\S+)", l).group(1).split(",")
    return {
        "paths": uniq(gate.paths_of(Path(wf))),
        "WAI_FEATURES": env("WAI_FEATURES"), "WAI_PQ_FEATURES": env("WAI_PQ_FEATURES"),
        "WAI_RELEASE_FEATURES": env("WAI_RELEASE_FEATURES"),
        "union_bins": re.findall(r"--bin ([A-Za-z0-9_-]+)", union_build),
        "pq_bins": re.findall(r"--bin ([A-Za-z0-9_-]+)", pq_build),
        "union_tests": tests(union_test), "release_tests": tests(rel_test),
        "alone": loop.group(1).split(),
        "steps": [{"step": n, "wd": wd or ".", "body": body} for n, wd, body in iv[b + 1:]],
        "int_kernels_debug_features": sorted(feats(dbg)), "int_kernels_debug_tests": sorted(tests(dbg)),
        "int_kernels_release_features": sorted(feats(rel)), "int_kernels_release_tests": sorted(tests(rel)),
        "int_kernels_amd_features": sorted(re.search(r"^F=(\S+)$", amd, re.M).group(1).split(",")),
        "int_kernels_amd_tests": sorted(tests(re.search(r'^T="(.*)"$', amd, re.M).group(1))),
        "corpora_features": sorted(re.search(r"^F=(\S+)$", corp, re.M).group(1).split(",")),
        "corpora": [" ".join(m.groups()) for m in re.finditer(r"^v (\S+)\s+(\S+)\s+(\S+)$", corp, re.M)],
    }


def at_ref(ref, fn):
    """fn(root) over the tree at a git ref, extracted to a scratch directory."""
    tmp = tempfile.mkdtemp(prefix="wai-lists-")
    try:
        arch = subprocess.run(["git", "archive", ref, ".github", "scripts", f"{CRATE}/Cargo.toml", f"{CRATE}/tests"],
                              capture_output=True, check=True).stdout
        subprocess.run(["tar", "-x", "-C", tmp], input=arch, check=True)
        return fn(tmp)
    finally:
        shutil.rmtree(tmp, ignore_errors=True)


def lists_of(root):
    return from_tree(root) if os.path.isdir(os.path.join(root, VERIFIERS)) else from_hand_lists(root)


# ------------------------------------------------- the command lines of the other steps

# The steps outside the independent verifiers whose lists are derived: (label, job, the
# start of the step's name). Their names lost the leg's suffix when the corpus step's two
# copies, one a shell family, became one step, so they are found by the start of the name.
COMMAND_STEPS = (
    ("cargo-classes: fast integer kernels, overflow checks on", "cargo-classes",
     "Fast integer kernels ≡ reference kernels (overflow checks on)"),
    ("cargo-classes: fast integer kernels, release", "cargo-classes",
     "Fast integer kernels ≡ reference kernels (release, overflow checks off)"),
    ("cargo-classes: every cargo-class corpus", "cargo-classes",
     "Every cargo-class corpus reproduces its frozen hashes"),
    ("int-kernels-amd", "int-kernels-amd", "Fast integer kernels ≡ reference kernels, every kernel set"),
    ("features-alone", "features-alone", "wai-rs, each feature list alone"),
)
# cargo's options that take a value, as `--opt value` or `--opt=value`.
VALUE_OPTS = {"--features", "-F", "--test", "--bin", "--example", "--bench", "--target", "-p", "--package",
              "--manifest-path", "--profile", "-j", "--jobs", "--target-dir"}
SCRIPT_CALL = re.compile(r"^python3\s+\S*wai-conformance-lists\.py\s+(.*)$")


def tagged_args(rest):
    """(tags, extra features, cargo args) of `tests|features|test-tagged TAG... [--extra-features
    A,B] [-- ARGS...]`, refusing what would run no test."""
    rest = list(rest)
    cargo_args = []
    if "--" in rest:
        cargo_args = rest[rest.index("--") + 1:]
        rest = rest[:rest.index("--")]
    extra = [x for x in (opt(rest, "--extra-features") or "").split(",") if x]
    unknown = [t for t in rest if t not in TAGS]
    if unknown or not rest:
        raise Bad(f"tags: {' '.join(unknown) or '(none given)'}; a tag is one of {', '.join(TAGS)}")
    return rest, extra, cargo_args


def test_tagged_line(root, tags, extra, cargo_args):
    names = tagged(root, tags)
    if not names:
        raise Bad(f"no test file carries {' or '.join(tags)}: the step would run no test")
    feats = tagged_features(root, tags, extra)
    return ["cargo", "test"] + cargo_args + ["--features", ",".join(feats)] + [x for t in names for x in ("--test", t)]


def corpus_lines(root, cs, extra):
    f = ",".join(corpora_features(root, cs, extra))
    return f, [["cargo", "run", "-q", "--no-default-features", "--features", f, "--bin", c["bin"], "--", "verify", c["dir"]]
               for c in cs]


def script_value(root, argv):
    """What `$(python3 .../wai-conformance-lists.py ARGV)` prints, for the commands a step's
    shell takes from it."""
    cmd, rest = argv[0], argv[1:]
    if cmd in ("tests", "features"):
        tags, extra, _ = tagged_args(rest)
        if not tagged(root, tags):
            raise Bad(f"no test file carries {' or '.join(tags)}: the step would run no test")
        if cmd == "tests":
            return " ".join(f"--test {t}" for t in tagged(root, tags))
        return ",".join(tagged_features(root, tags, extra))
    if cmd == "alone":
        mods, errs = verifiers(root)
        if errs:
            raise Bad("\n".join(errs))
        return "\n".join(derive(mods)["alone"])
    raise Bad(f"`$(wai-conformance-lists.py {cmd} ...)`: the dry-run reads no value of `{cmd}`")


def script_commands(root, argv):
    """The cargo command lines `python3 .../wai-conformance-lists.py ARGV` runs."""
    cmd, rest = argv[0], argv[1:]
    if cmd == "test-tagged":
        return [test_tagged_line(root, *tagged_args(rest))]
    if cmd == "corpora" and "--verify" in rest:
        rest = list(rest)
        extra = [x for x in (opt(rest, "--extra-features") or "").split(",") if x]
        cs, errs = corpora(root)
        if errs:
            raise Bad("\n".join(errs))
        return corpus_lines(root, cs, extra)[1]
    raise Bad(f"`wai-conformance-lists.py {cmd}` in a step the dry-run reads: it reads the commands of test-tagged and corpora --verify only")


def subst(s, env):
    """s with `$NAME` and `${NAME}` replaced from env; Bad for a name with no known value."""
    def rep(m):
        name = m.group(1) or m.group(2)
        if env.get(name) is None:
            raise Bad(f"`${name}` has no value the dry-run knows")
        return env[name]
    return re.sub(r"\$\{(\w+)\}|\$(\w+)", rep, s)


def shell_value(rhs, env, root):
    """The value an assignment's right-hand side gives, or None when it reads the runner's
    environment."""
    m = re.match(r"^\$\(\s*(python3\s+\S*wai-conformance-lists\.py\s+.*?)\s*\)$", rhs)
    if m:
        return script_value(root, shlex.split(SCRIPT_CALL.match(m.group(1)).group(1)))
    if rhs.startswith("$(") or "`" in rhs:
        return None
    try:
        if rhs.startswith("'") and rhs.endswith("'") and len(rhs) > 1:
            return rhs[1:-1]
        if rhs.startswith('"') and rhs.endswith('"') and len(rhs) > 1:
            return subst(rhs[1:-1], env)
        return subst(rhs, env)
    except Bad:
        return None


def run_lines(lines, env, funcs, root, out):
    """Append to out the cargo command lines (as argv) that a step's shell lines run: bash or
    PowerShell, as far as the steps COMMAND_STEPS names use them (assignments, `for` loops, a
    function a line calls, the derivations of this script, and cargo itself). A line that names
    cargo but none of these is refused rather than skipped."""
    i = 0
    while i < len(lines):
        line = lines[i].strip()
        i += 1
        if not line or line.startswith("#"):
            continue
        m = re.match(r"^for (\w+) in (.*); do$", line)
        if m:
            depth, j = 1, i
            while j < len(lines):
                t = lines[j].strip()
                if re.match(r"^for \w+ in .*; do$", t):
                    depth += 1
                elif t == "done":
                    depth -= 1
                    if not depth:
                        break
                j += 1
            else:
                raise Bad(f"`{line}` has no `done`")
            for v in shlex.split(subst(m.group(2), env)):
                run_lines(lines[i:j], {**env, m.group(1): v}, funcs, root, out)
            i = j + 1
            continue
        m = re.match(r"^(\w+)\(\)\s*\{\s*(.*?)\s*\}$", line)
        if m:
            funcs[m.group(1)] = (None, m.group(2).split(";"))
            continue
        m = re.match(r"^function (\w+)\((.*)\)\s*\{$", line)
        if m:
            j = next((j for j in range(i, len(lines)) if lines[j].strip() == "}"), None)
            if j is None:
                raise Bad(f"`{line}` has no closing `}}`")
            funcs[m.group(1)] = ([p.strip().lstrip("$") for p in m.group(2).split(",") if p.strip()], lines[i:j])
            i = j + 1
            continue
        m = re.match(r"^(?:export\s+)?\$?([A-Za-z_]\w*)\s*=\s*(.*)$", line)
        if m:
            env[m.group(1)] = shell_value(m.group(2), env, root)
            continue
        word = line.split()[0]
        if word in funcs:
            params, body = funcs[word]
            args = shlex.split(subst(line[len(word):], env))
            e = dict(env)
            for n, a in enumerate(args, 1):
                e[str(n)] = a
            for p, a in zip(params or [], args):
                e[p] = a
            run_lines(body, e, funcs, root, out)
            continue
        m = SCRIPT_CALL.match(line)
        if m:
            out += script_commands(root, shlex.split(subst(m.group(1), env)))
            continue
        if re.search(r"(^|\s)cargo\s", line):
            toks = shlex.split(subst(line, env))
            if "cargo" not in toks:
                raise Bad(f"`{line}`: the dry-run cannot read this command")
            out.append(toks)
            continue
        if "wai-conformance-lists.py" in line:
            raise Bad(f"`{line}`: the dry-run cannot read this call of the script")


def canon(toks):
    """A cargo command line in one form for every spelling of it: its flags sorted, its
    features sorted and comma-joined, each target once and sorted, anything after `--` as it
    was. Two commands that build and run the same thing print the same."""
    at = toks.index("cargo")
    pre, sub, rest = toks[:at], toks[at + 1], toks[at + 2:]
    tail = []
    if "--" in rest:
        tail, rest = rest[rest.index("--"):], rest[:rest.index("--")]
    flags, feats, vals = set(), set(), set()
    i = 0
    while i < len(rest):
        t = rest[i]
        if t.startswith("--") and "=" in t and t.split("=", 1)[0] in VALUE_OPTS:
            k, v = t.split("=", 1)
            i += 1
        elif t in VALUE_OPTS:
            if i + 1 >= len(rest):
                raise Bad(f"`{' '.join(toks)}`: {t} with no value")
            k, v = t, rest[i + 1]
            i += 2
        else:
            flags.add(t)
            i += 1
            continue
        if k in ("--features", "-F"):
            feats |= {f for f in re.split(r"[ ,]+", v) if f}
        else:
            vals.add((k, v))
    out = pre + ["cargo", sub] + sorted(flags) + (["--features", ",".join(sorted(feats))] if feats else [])
    out += [x for k, v in sorted(vals) for x in (k, v)] + tail
    return " ".join(shlex.quote(t) for t in out)


def admits(cond, leg):
    """Whether a step's `if:` lets it run on a leg of the family `leg` (unix or windows)."""
    if cond is None:
        return True
    m = re.fullmatch(r"(?:\$\{\{\s*)?matrix\.os (==|!=) '([a-z0-9-]+)'(?:\s*\}\})?", cond)
    if not m or m.group(2) != "windows":
        raise Bad(f"a step's condition `{cond}` is none the dry-run reads (matrix.os == or != 'windows')")
    return (m.group(1) == "==") == (leg == "windows")


def step_commands(root):
    """[(label, legs, working directories, [command lines])] of the steps COMMAND_STEPS names,
    each command line in canon() form; `legs` is "every leg" when the unix legs and the
    Windows leg run the same, and one entry a family otherwise."""
    with open(os.path.join(root, WORKFLOW), encoding="utf-8") as fh:
        text = fh.read()
    out = []
    for label, job, prefix in COMMAND_STEPS:
        steps = [s for s in job_steps(text, job) if s["name"].startswith(prefix)]
        if not steps:
            raise Bad(f"{WORKFLOW}: job `{job}` has no step `{prefix}...`")
        per = {}
        for leg in ("unix", "windows"):
            cmds, wds = [], []
            for s in steps:
                if not admits(s["if"], leg):
                    continue
                argv = []
                try:
                    run_lines(joined(s["body"] or ""), {}, {}, root, argv)
                except Bad as e:
                    raise Bad(f"{WORKFLOW}: {job} / {s['name']}: {e}")
                if not argv:
                    raise Bad(f"{WORKFLOW}: {job} / {s['name']}: the dry-run finds no cargo command in it")
                cmds += [canon(a) for a in argv]
                wds.append(s["wd"] or ".")
            if label == "features-alone":
                cmds = sorted(cmds)
            per[leg] = (uniq(wds), cmds)
        if per["unix"] == per["windows"]:
            out.append((label, "every leg", *per["unix"]))
        else:
            out += [(label, "unix legs", *per["unix"]), (label, "the Windows leg", *per["windows"])]
    return out


# ----------------------------------------------------------------------------- output

SETS = ("paths", "WAI_FEATURES", "WAI_PQ_FEATURES", "WAI_RELEASE_FEATURES", "union_bins", "pq_bins",
        "union_tests", "release_tests", "alone", "int_kernels_debug_features", "int_kernels_debug_tests",
        "int_kernels_release_features", "int_kernels_release_tests", "int_kernels_amd_features",
        "int_kernels_amd_tests", "corpora_features")


def norm_list(k, xs):
    if k == "alone":
        return sorted(uniq(",".join(sorted(x.split(","))) for x in xs))
    return sorted(uniq(xs))


def dry_run(L, C):
    out = ["# wai-conformance.yml: what its derived lists make it run, in a stable form",
           "# (lists sorted; steps and corpora in the order they run)"]
    for k in SETS:
        out.append(f"{k}: {' '.join(norm_list(k, L[k]))}")
    out.append("corpora (in order):")
    out += [f"  {c}" for c in L["corpora"]]
    out.append("independent-verifiers steps (in order):")
    for s in L["steps"]:
        out.append(f"  - step: {s['step']}  (working-directory: {s['wd']})")
        out += [f"    | {l}" for l in s["body"].split("\n")]
    out.append("the other derived steps' commands (as cargo is given them: flags sorted, features sorted, each")
    out.append("target once; in the order they run, but features-alone's sorted):")
    for label, legs, wds, cmds in C:
        out.append(f"  - {label}  ({legs}; working-directory: {', '.join(wds) or '-'})")
        out += [f"    $ {c}" for c in cmds]
    return "\n".join(out) + "\n"


def check(root):
    """Every finding about the files this script reads."""
    errs = []
    try:
        mods, e = verifiers(root)
        cs, e2 = corpora(root)
    except Bad as x:
        return [str(x)]
    errs += e + e2
    targets, feats = cargo_targets(root)
    tests = {n for k, n in targets if k == "test"} | {f[:-3] for f in os.listdir(os.path.join(root, CRATE, "tests")) if f.endswith(".rs")}
    bins = {n for k, n in targets if k == "bin"}
    # A checkout, rather than the files `dry-run --ref` extracts: directories can be checked.
    full = os.path.isdir(os.path.join(root, CRATE, "src"))
    gate = gate_module(root)
    from pathlib import Path
    wf_globs = gate.paths_of(Path(os.path.join(root, WORKFLOW)))
    if sorted(gate.declared_paths(Path(os.path.join(root, VERIFIERS))) or []) != sorted(p for m in mods for p in m["paths"]):
        errs.append(f"scripts/pr-touches-paths.py reads other paths from {VERIFIERS} than this script does")
    try:
        gate_paths(root)
    except Bad as x:
        errs.append(str(x))
    for m in mods:
        for lst in m["features"] + (m["alone"] or []) + m["release"]:
            for f in lst.split(","):
                if f not in feats:
                    errs.append(f"{m['file']}: feature `{f}` is not in {CRATE}/Cargo.toml [features]")
        for line in joined(m["body"]):
            for t in re.findall(r"--test[ =]([A-Za-z0-9_-]+)", line):
                if "cd wai-rs" in line and t not in tests:
                    errs.append(f"{m['file']}: --test {t}: {CRATE} has no such test")
        for b in m["bins"] + m["pq_bins"] + re.findall(r"wai-bins/(?:union|pq)/([A-Za-z0-9_-]+)", m["body"]):
            if b not in bins:
                errs.append(f"{m['file']}: binary `{b}` is not a [[bin]] of {CRATE}/Cargo.toml")
        for p in m["paths"]:
            # A path the forge's own filter does not cover never starts the workflow, whatever
            # the gate would say: a file under the glob stands for every file it matches.
            sample = p.replace("**", "s/s").replace("*", "s").replace("?", "s")
            if not any(gate.matches(sample, g) for g in wf_globs):
                errs.append(f"{m['file']}: path `{p}` is under none of {WORKFLOW}'s paths, so the forge would never start the workflow for it")
        if full and not os.path.isdir(os.path.join(root, m["wd"])):
            errs.append(f"{m['file']}: working-directory `{m['wd']}` does not exist")
    for c in cs:
        if c["bin"] not in bins:
            errs.append(f"{c['file']}: binary `{c['bin']}` is not a [[bin]] of {CRATE}/Cargo.toml")
        if full and not os.path.isdir(os.path.normpath(os.path.join(root, CRATE, c["dir"]))):
            errs.append(f"{c['file']}: dir `{c['dir']}` is no directory (it is read from {CRATE})")
    for t, ts in markers(root).items():
        for tag in ts:
            if tag not in TAGS:
                errs.append(f"{CRATE}/tests/{t}.rs: `wai-conformance: {tag}` is no tag a step takes ({', '.join(TAGS)})")
    return errs


def selftest(root, exact):
    errs = check(root)
    for e in errs:
        print(f"check: {e}")
    if errs:
        return 1
    with open(os.path.join(root, BASELINE), encoding="utf-8") as fh:
        base = json.load(fh)
    L = from_tree(root)
    added = base.get("added", {})
    bad = 0
    for k in SETS + ("corpora",):
        want = norm_list(k, base[k] + added.get(k, [])) if k in SETS else base[k]
        got = norm_list(k, L[k]) if k in SETS else L[k]
        lost = [x for x in want if x not in got]
        more = [x for x in got if x not in want]
        if lost:
            print(f"FAIL  {k}: lost {' '.join(lost)}")
            bad += 1
        elif exact and more:
            print(f"FAIL  {k}: more than the hand list: {' '.join(more)}")
            bad += 1
        else:
            print(f"ok    {k}: the hand list's {len(want)}{' and ' + str(len(more)) + ' more' if more else ''}")
    names = [s["step"] for s in L["steps"]]
    for s in base["steps"]:
        if s["step"] not in names:
            print(f"FAIL  step `{s['step']}` no longer runs")
            bad += 1
    if exact:
        # Each by name, not by place: a step or a corpus the tree adds is one addition, and
        # moves no other along. The order is that of the entries both hold.
        want = [s["step"] for s in base["steps"]]
        for n in names:
            if n not in want:
                print(f"FAIL  step `{n}`: more than the hand list")
                bad += 1
        if [n for n in names if n in want] != [n for n in want if n in names]:
            print("FAIL  the steps both lists hold run in another order than the hand list's")
            bad += 1
        derived = {s["step"]: s for s in L["steps"]}
        for s in base["steps"]:
            t = derived.get(s["step"])
            if t is not None and (s["wd"], s["body"]) != (t["wd"], t["body"]):
                print(f"FAIL  step `{s['step']}`: its body or directory is not the hand list's")
                bad += 1
        if [c for c in L["corpora"] if c in base["corpora"]] != [c for c in base["corpora"] if c in L["corpora"]]:
            print("FAIL  the corpora both lists hold run in another order than the hand list's")
            bad += 1
    print(f"ok    {len(base['steps'])} steps of the hand list run" if not bad else f"wai-conformance-lists selftest: {bad} failure(s)")
    return 1 if bad else 0


# ------------------------------------------------------------------------------ main


def opt(args, name):
    if name in args:
        i = args.index(name)
        v = args[i + 1]
        del args[i:i + 2]
        return v
    return None


def main(argv):
    args = list(argv)
    root = opt(args, "--root") or os.path.dirname(HERE)
    if not args:
        print(__doc__)
        return 2
    cmd, rest = args[0], args[1:]
    try:
        if cmd in ("env", "prebuild", "run", "alone", "paths"):
            mods, errs = verifiers(root)
            if errs:
                raise Bad("\n".join(errs))
            d = derive(mods)
            if cmd == "env":
                for k in ("WAI_FEATURES", "WAI_PQ_FEATURES", "WAI_RELEASE_FEATURES"):
                    print(f"{k}={','.join(d[k])}")
            elif cmd == "prebuild":
                sys.stdout.write(prebuild(d))
            elif cmd == "alone":
                print("\n".join(d["alone"]))
            elif cmd == "paths":
                print("\n".join(d["paths"]))
            else:
                only = [rest[i + 1] for i, a in enumerate(rest) if a == "--only"]
                env = dict(os.environ)
                for k in ("WAI_FEATURES", "WAI_PQ_FEATURES", "WAI_RELEASE_FEATURES"):
                    env[k] = ",".join(d[k])
                env.setdefault("RUNNER_TEMP", tempfile.gettempdir())
                todo = [m for m in mods if not only or m["slug"] in only]
                if only and len(todo) != len(set(only)):
                    raise Bad(f"--only names a step no file holds: {' '.join(sorted(set(only) - {m['slug'] for m in mods}))}")
                for m in todo:
                    print(f"::group::{m['step']}  ({m['file']})", flush=True)
                    rc = subprocess.call(["bash", "--noprofile", "--norc", "-eo", "pipefail", os.path.join(root, m["file"])],
                                         cwd=os.path.join(root, m["wd"]), env=env)
                    print("::endgroup::", flush=True)
                    if rc:
                        print(f"::error::{m['step']} failed with exit status {rc} ({m['file']})", flush=True)
                        return rc
                print(f"every step ran and passed: {len(todo)} of {len(mods)}")
        elif cmd in ("tests", "features"):
            print(script_value(root, [cmd] + rest))
        elif cmd == "test-tagged":
            line = test_tagged_line(root, *tagged_args(rest))
            print("+ " + " ".join(line), flush=True)
            return subprocess.call(line)
        elif cmd == "corpora":
            extra = [x for x in (opt(rest, "--extra-features") or "").split(",") if x]
            cs, errs = corpora(root)
            if errs:
                raise Bad("\n".join(errs))
            if "--verify" not in rest:
                for c in cs:
                    print(f"{c['corpus']} {c['bin']} {c['dir']}")
                return 0
            f, lines = corpus_lines(root, cs, extra)
            print(f"the corpora's features: {f}", flush=True)
            for c, line in zip(cs, lines):
                print(f"::group::{c['corpus']}", flush=True)
                print("+ " + " ".join(line), flush=True)
                rc = subprocess.call(line)
                print("::endgroup::", flush=True)
                if rc:
                    print(f"::error::the {c['corpus']} corpus failed with exit status {rc} ({c['file']})", flush=True)
                    return rc
        elif cmd == "dry-run":
            ref = opt(rest, "--ref")
            both = lambda r: (lists_of(r), step_commands(r))
            L, C = at_ref(ref, both) if ref else both(root)
            sys.stdout.write(dry_run(L, C))
        elif cmd == "baseline":
            ref = opt(rest, "--ref")
            if not ref:
                raise Bad("baseline --ref REF: the commit whose workflow kept the lists by hand")
            L = at_ref(ref, from_hand_lists)
            commit = subprocess.run(["git", "rev-parse", ref], capture_output=True, text=True, check=True).stdout.strip()
            print(json.dumps({"commit": commit, **L}, indent=1, ensure_ascii=False))
        elif cmd == "check":
            errs = check(root)
            for e in errs:
                print(e)
            if errs:
                print(f"wai-conformance-lists check: {len(errs)} finding(s)")
                return 1
            print("wai-conformance-lists check: every file is well formed and names what exists.")
        elif cmd == "selftest":
            return selftest(root, "--exact" in rest)
        else:
            print(__doc__)
            return 2
    except Bad as e:
        print(f"wai-conformance-lists {cmd}: {e}", file=sys.stderr)
        return 1
    return 0


if __name__ == "__main__":
    sys.exit(main(sys.argv[1:]))