wai-quantum 0.6.0

//! The gate kernel in WGSL, and everything a WebGPU member needs that is not
//! the device. Pure Rust: compiled and tested on every target.
//!
//! [`SHADER`] is the kernel: [`lanes`] transcribed line for line into WGSL,
//! with every value a `u32` holding a 32-bit two's-complement pattern, and an
//! exact 64-bit copy of every result beside it so that the kernel reports any
//! result that leaves 32 bits. Its entry point `apply` runs one gate over the
//! whole state, one invocation per amplitude pair, in place; `probe` runs the
//! wide multiply and the exact `fx` on listed operands. Around it, this module
//! holds what a host needs: the implementation id ([`implementation_id`]), the
//! 64-byte gate record ([`gate_record`]), the dispatch grid ([`grid`],
//! [`gate_grid`]), the id of a member built on an adapter
//! ([`AdapterIdentity`]), and the textual edits of the kernel a device must be
//! caught running ([`MUTANTS`]).
//!
//! The state is two planes, `re` and `im`, each `2^n` `u32` words. The report
//! is two atomic words: `report[0]` collects bit 1 (a result left 32 bits),
//! bit 2 (an index outside the state) and bit 4 (a malformed record), and
//! `report[1]` the lowest op-log index that set bit 1. The host writes
//! `(0, 0xffffffff)` before a run.
//!
//! # Why the kernel is bit-exact
//!
//! **Lemma 1 (the same function).** Line for line:
//!
//! | [`lanes`] (Rust) | WGSL | Why equal |
//! |---|---|---|
//! | `a < 0` | `neg(a)` | the two's-complement sign bit |
//! | `a.unsigned_abs()` | `select(a, 0u - a, neg(a))` | for `a < 0`, \|a\| = 2^32 − pattern(a) = `0u − a` modulo 2^32, the most negative value (→ 2^31) included |
//! | `x >> 16`, `x & 0xffff` | the same | logical shift and mask |
//! | `wrapping_mul` of halves | `*` | every partial product is below 2^32: exact in both |
//! | `wrapping_add`, `u32::from(mid < p01)` | `+`, `bit(mid < p01)` | `u32` addition modulo 2^32; `u32` comparison |
//! | `p00.wrapping_add(mid << 16)` | `p00 + (mid << 16u)` | `<<` discards the high bits in both |
//! | `(!lo).wrapping_add(1)`, … | `~lo + 1u`, … | complement, then addition modulo 2^32 |
//! | `fxmul`: `lo2`, `hi2`, `(lo2 >> 30) \| (hi2 << 2)` | `fx64(..).y` | identical expressions |
//! | `cmul`, `cadd` with wrapping 32-bit operations | the low words of `add64`, `sub64` | the low word of a 64-bit sum is the 32-bit wrapping sum of the low words |
//! | `(a0, a1)` read before both stores | `a0`, `a1` loaded before any store | the same data dependence |
//!
//! No partial product reaches 2^32 (`x0·y1 ≤ 0xffff·0x8000`), so no `u32`
//! multiply wraps; `mid_carry` is always zero and is kept so that the
//! transcription stays literal. The only intended wraps are the carry
//! additions, `mid << 16u`, the two's-complement negation, and the low words of
//! `add64` and `sub64`. So for every state and every record, the stored words
//! equal those of [`lanes::apply_words`], and report bit 1 is raised exactly
//! when it returns `Some(false)`. For a record whose `pairs` is half the
//! state's length, report bit 4 is raised exactly when it returns `None`: the
//! same predicate on `tbit` and `ctrl`.
//!
//! **Lemma 2 (`fx64` is exact).** `mul_wide` is exact for every pair of 32-bit
//! values; `|a·b| ≤ 2^62`, so adding 2^29 cannot overflow 64 bits; and an
//! arithmetic shift of `(hi2:lo2)` by 30 has as its low word bits 30 to 61,
//! `(lo2 >> 30) | (hi2 << 2)`, and as its high word `hi2 >> 30` with the sign
//! copied into bits 2 to 31, which is `EXT30`. Each output part is a sum of four
//! such values, each at most about 2^32 in size, so `add64` and `sub64` hold
//! it exactly, and `fits` (the high word repeats the low word's sign) is true
//! exactly when the value is a 32-bit one.
//!
//! **Lemma 3 (no dynamic error).** The map from `p` to `i`, a zero inserted at
//! bit `t`, is strictly increasing on `[0, 2^(n−1))` with inverse "delete bit
//! `t`": a bijection onto the indices with bit `t` clear, the set
//! [`lanes::apply`] visits. `p = id.y·row_stride + id.x` with
//! `id.x < row_stride` is injective, and the host's grid ([`gate_grid`])
//! covers every `p` below `pairs`. Every array access is guarded by
//! `arrayLength` and `i < j`, and a malformed record never reaches an access.
//! The pairs partition the indices, so no two invocations touch one location;
//! `report` is touched only by atomics; the record and `arrayLength` are only
//! read.
//!
//! **Lemma 4 (order does not matter).** Each invocation reads and writes only
//! its own pair, so a dispatch's result does not depend on the order in which
//! invocations run, and equals the sequential loop of [`lanes::apply`], whose
//! iterations also touch disjoint pairs. Dispatches run in queue order, each its
//! own usage scope. The final values of `atomicOr` and `atomicMin` do not depend
//! on order.
//!
//! **Theorem.** On an implementation that conforms for the constructs the
//! kernel uses (`u32` `+ − *` modulo 2^32; `~ & | ^`; shifts by literal amounts
//! below 32; `== != <`; `select`; relaxed `atomicOr` and `atomicMin`;
//! little-endian buffer layout; dispatches in queue order), dispatching `apply`
//! once per gate in op-log order over [`gate_grid`] gives the lanes and
//! `out_of_range` of [`plan::execute`]. With the exact range guard, if no gate
//! is reported, the state equals that of
//! [`Circuit::simulate_from`](crate::quantum::Circuit::simulate_from); a valid
//! circuit of at most [`lanes::horizon`] gates cannot have a gate reported.
//!
//! The kernel holds no signed type, no float, no division, no conversion or
//! bitcast, no workgroup memory and no barrier, and every shift amount is a
//! literal between 1 and 31: so the kernel brings no signed overflow, no shift
//! by 32 or more and no signed right shift into any language it is translated
//! to. The rules are checked on the translator's own reading of the text by
//! the unpublished crate `wai/tools/quantum-wgsl-check`.
//!
//! # Tile runs: a second implementation
//!
//! [`TILE_SHADER`] is [`SHADER`] followed by `lanes32_tile.wgsl`, whose entry
//! point `apply_tile` runs a [`Step::Tile`](super::plan::Step::Tile) of a
//! program planned with [`Config::TILED`](super::plan::Config::TILED): one
//! workgroup of [`TILE_WORKGROUP`] invocations per tile of up to 1024
//! consecutive amplitudes, which it alone touches for the whole dispatch while
//! it applies every gate of the run to the tile in place, in op-log order. A
//! run of gates is one dispatch instead of one per gate. The steps of a tiled
//! program that are single gates run on the same module's `apply`. It is its
//! own implementation ([`tile_implementation_id`]), certified on its own. A
//! member runs the per-gate kernel unless its caller asks for tile runs, and
//! falls back to it; [`place`](super::place), with both implementations'
//! entries for one member and no energy figures, breaks the tie by
//! implementation name and places the tile implementation
//! (`wgsl-lanes32-tile/…` sorts before `wgsl-lanes32/…`).
//!
//! - **The same function.** `apply_tile` computes every output with `row`, the
//!   per-gate kernel's exact 64-bit row, and stores its low words: for a pair,
//!   the per-gate kernel's computation; for a diagonal gate, the row with a
//!   zero partner, whose exact value is the per-gate one because `fx64(0, x)`
//!   is exactly 0 for every `x`. A gate is flagged when any exact output does
//!   not fit, and the report keeps the lowest op index flagged over every
//!   tile and gate. The tiled program on the CPU ([`plan::execute`]) mirrors
//!   this index arithmetic tile by tile, and equals the per-gate program on
//!   any words ([`plan`](super::plan) documents why it may).
//! - **No race.** Within a gate each amplitude (diagonal) or pair (otherwise)
//!   belongs to one invocation; a storage barrier (workgroup execution scope,
//!   storage memory) separates each gate from the next, so a gate reads what
//!   the gate before wrote; tiles are disjoint, one workgroup each, and the
//!   dispatch ends before the next step reads the state. A run record is
//!   refused (bit 4) and nothing is touched unless its size is a power of two
//!   of at most 1024, its run holds a gate, its tiles cover each state plane
//!   exactly, and its grid (`num_workgroups`, one deep) holds every tile once
//!   with `x_groups` workgroups to a row. A tile outside the state is reported
//!   (bit 2) and not touched; a record outside the gate buffer reads as
//!   malformed, never out of bounds.
//! - **A uniform barrier.** The early returns depend only on the run record (a
//!   uniform buffer), the workgroup id, the number of workgroups and the
//!   state planes' lengths. The barrier sits at the top level
//!   of the loop over the run's gates, whose bound is in the uniform record;
//!   that loop holds no `break`, `continue` or `return`, and no branch that
//!   depends on a gate or an invocation holds a barrier. Naga does not check
//!   barrier uniformity; a browser's WGSL compiler, which does, compiles this
//!   text in the browser leg of the member's checks.
//! - **The size travels in a uniform.** The tile size, the gate range and the
//!   grid are fields of the run record, never substituted into the text, so
//!   the implementation id names the exact text every device compiles.
//!
//! The tile file keeps the per-gate rules (unsigned 32-bit values only, literal
//! shift amounts, no conversion, division or float, no workgroup memory) and
//! adds exactly one barrier, `storageBarrier()`. It holds no workgroup memory
//! because the SPIR-V the native translator writes for a workgroup array or
//! structure carries explicit layout decorations, which a Vulkan SPIR-V
//! validator rejects for the workgroup storage class; the tile stays in the
//! state's own planes instead. A device must be caught running each of
//! [`TILE_MUTANTS`].
//!
//! # What the argument does not cover
//!
//! Whether a device and its shader compiler conform is not proved here. A
//! member earns that per adapter: by reproducing the pinned corpus digests of
//! [`FABRIC_DEFAULT`](super::FABRIC_DEFAULT), and by being caught running each
//! of [`MUTANTS`] (and, for tile runs, [`TILE_MUTANTS`]). Any edit to
//! [`SHADER`], to the tile file, to the host layout or to the meaning of a
//! program is a new implementation, with a new [`implementation_id`] or
//! [`tile_implementation_id`], whose certificates must be earned again.
//!
//! [`lanes`]: super::lanes
//! [`lanes::apply`]: super::lanes::apply
//! [`lanes::apply_words`]: super::lanes::apply_words
//! [`lanes::horizon`]: super::lanes::horizon
//! [`plan::execute`]: super::plan::execute

use super::lanes::{GateWords, Lane};
use super::plan::{PLAN_REVISION, PlannedGate, Program, Step};
use super::{FabricClass, put};
use crate::quantum::MAX_QUBITS;

/// The kernel, `lanes32.wgsl`, exactly as it is compiled.
pub const SHADER: &str = include_str!("lanes32.wgsl");

/// The implementation name the id starts with.
pub const IMPLEMENTATION: &str = "wgsl-lanes32";

/// Version of the host-side layout: planar `u32` planes, the 64-byte gate
/// record, the grid rule, and for tile runs the 48-byte tile gate record, the
/// 32-byte run record and the tile grid rule. Bumped on any change to them;
/// it is part of both implementation ids.
pub const HOST_LAYOUT: u32 = 1;

/// Invocations per workgroup, as the kernel declares.
pub const WORKGROUP: u32 = 64;

/// Workgroups along x, at most. Production and certification use the same
/// value, so two-dimensional grids (14 qubits or more) occur inside the
/// certification corpus.
pub const X_GROUPS_MAX: u32 = 64;

/// Bytes of one gate record, the kernel's `Gate` uniform.
pub const GATE_RECORD_BYTES: usize = 64;

const DOMAIN_IMPLEMENTATION: &[u8] = b"wai:quantum-fabric-wgsl\x01";
const DOMAIN_MEMBER: &[u8] = b"wai:quantum-fabric-webgpu-member\x01";

fn hex(bytes: &[u8]) -> String {
    bytes.iter().map(|b| format!("{b:02x}")).collect()
}

/// `"wgsl-lanes32/<16 hex>"`: the first 8 bytes of
/// BLAKE3(`"wai:quantum-fabric-wgsl\x01"` ‖ put([`SHADER`]) ‖ [`HOST_LAYOUT`]
/// as a big-endian `u32`), in hex. Any edit to the kernel's text or to the host
/// layout changes it.
pub fn implementation_id() -> String {
    let mut o = DOMAIN_IMPLEMENTATION.to_vec();
    put(&mut o, SHADER.as_bytes());
    o.extend_from_slice(&HOST_LAYOUT.to_be_bytes());
    format!("{IMPLEMENTATION}/{}", hex(&blake3::hash(&o).as_bytes()[..8]))
}

/// The 64-byte little-endian uniform record of one gate: `m[0..8]`, `tbit`,
/// `ctrl`, `pairs`, `row_stride`, `index`, then three zero words.
pub fn gate_record(w: &GateWords, pairs: u32, row_stride: u32, index: u32) -> [u8; GATE_RECORD_BYTES] {
    let mut r = [0u8; GATE_RECORD_BYTES];
    let words = w.m.into_iter().chain([w.tbit, w.ctrl, pairs, row_stride, index, 0, 0, 0]);
    for (k, v) in words.enumerate() {
        r[4 * k..4 * k + 4].copy_from_slice(&v.to_le_bytes());
    }
    r
}

/// A dispatch: `x` by `y` workgroups of [`WORKGROUP`] invocations, where the
/// invocation at `(gx, gy)` handles item `gy·row_stride + gx` if it is below
/// `items`.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Grid {
    pub x: u32,
    pub y: u32,
    pub row_stride: u32,
    pub items: u32,
}

/// Workgroups covering `items` invocations: `groups = ⌈items / 64⌉`,
/// `x = min(groups, max_x)`, `y = ⌈groups / x⌉`, `row_stride = 64·x`.
///
/// Panics if `items` or `max_x` is zero, or if `64·x` does not fit in 32 bits.
pub fn grid(items: u32, max_x: u32) -> Grid {
    assert!(items >= 1 && max_x >= 1, "a grid covers at least one item, with at least one workgroup along x");
    let groups = items.div_ceil(WORKGROUP);
    let x = groups.min(max_x);
    let row_stride = WORKGROUP.checked_mul(x).expect("the row stride fits in 32 bits");
    Grid { x, y: groups.div_ceil(x), row_stride, items }
}

/// The grid of one gate on `n_qubits`: `grid(2^(n−1), X_GROUPS_MAX)`, one
/// invocation per amplitude pair.
///
/// Panics unless `1 ≤ n_qubits ≤ MAX_QUBITS`.
pub fn gate_grid(n_qubits: u8) -> Grid {
    assert!((1..=MAX_QUBITS).contains(&n_qubits), "a gate acts on 1 to {MAX_QUBITS} qubits, not {n_qubits}");
    grid(1 << (n_qubits - 1), X_GROUPS_MAX)
}

/// The kernel with tile runs, `lanes32.wgsl` followed by `lanes32_tile.wgsl`,
/// exactly as it is compiled: the entry points `apply` and `probe` of
/// [`SHADER`], and `apply_tile`.
pub const TILE_SHADER: &str = concat!(include_str!("lanes32.wgsl"), include_str!("lanes32_tile.wgsl"));

/// The tile implementation's name, which its id starts with.
pub const TILE_IMPLEMENTATION: &str = "wgsl-lanes32-tile";

/// Invocations per workgroup of `apply_tile`, as it declares: a tile of up to
/// 1024 amplitudes is four per invocation, or two pairs.
pub const TILE_WORKGROUP: u32 = 256;

/// Workgroups along x of a tile step, at most: at 1024 amplitudes a tile, two
/// rows or more from 14 qubits on, inside the certification corpus.
pub const TILE_X_GROUPS_MAX: u32 = 8;

/// Bytes of one tile gate record, the tile kernel's `TileGate`.
pub const TILE_GATE_RECORD_BYTES: usize = 48;

/// Bytes of one run record, the tile kernel's `TileRun` uniform.
pub const TILE_RUN_RECORD_BYTES: usize = 32;

/// `"wgsl-lanes32-tile/<16 hex>"`: the first 8 bytes of
/// BLAKE3(`"wai:quantum-fabric-wgsl\x01"` ‖ put([`TILE_SHADER`]) ‖
/// [`HOST_LAYOUT`] ‖ [`PLAN_REVISION`], both big-endian `u32`), in hex. The
/// tile size is a field of the run record, never part of the text, so this
/// names the exact text every device compiles.
pub fn tile_implementation_id() -> String {
    let mut o = DOMAIN_IMPLEMENTATION.to_vec();
    put(&mut o, TILE_SHADER.as_bytes());
    o.extend_from_slice(&HOST_LAYOUT.to_be_bytes());
    o.extend_from_slice(&PLAN_REVISION.to_be_bytes());
    format!("{TILE_IMPLEMENTATION}/{}", hex(&blake3::hash(&o).as_bytes()[..8]))
}

/// The 48-byte little-endian storage record of one gate of a tile run:
/// `m[0..8]`, `tbit`, `ctrl`, `diag` (1 or 0), `index`.
pub fn tile_gate_record(g: &PlannedGate) -> [u8; TILE_GATE_RECORD_BYTES] {
    let mut r = [0u8; TILE_GATE_RECORD_BYTES];
    let w = &g.words;
    let words = w.m.into_iter().chain([w.tbit, w.ctrl, u32::from(g.diag), g.index]);
    for (k, v) in words.enumerate() {
        r[4 * k..4 * k + 4].copy_from_slice(&v.to_le_bytes());
    }
    r
}

/// The 32-byte little-endian uniform record of one tile run: `first` (its
/// first record in the tile gate buffer), `count`, `size`, `x_groups`,
/// `tiles`, then three zero words.
pub fn tile_run_record(first: u32, count: u32, size: u32, x_groups: u32, tiles: u32) -> [u8; TILE_RUN_RECORD_BYTES] {
    let mut r = [0u8; TILE_RUN_RECORD_BYTES];
    for (k, v) in [first, count, size, x_groups, tiles, 0, 0, 0].into_iter().enumerate() {
        r[4 * k..4 * k + 4].copy_from_slice(&v.to_le_bytes());
    }
    r
}

/// A tile step's dispatch: `x` by `y` workgroups, where the workgroup at
/// `(wx, wy)` holds tile `wy·x + wx` if it is below `tiles`.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct TileGrid {
    pub x: u32,
    pub y: u32,
    pub tiles: u32,
}

/// Workgroups covering `tiles` tiles: `x = min(tiles, max_x)`,
/// `y = ⌈tiles / x⌉`. In production `max_x` is [`TILE_X_GROUPS_MAX`]; both
/// are powers of two, so `y = tiles / x` exactly.
///
/// Panics if `tiles` or `max_x` is zero.
pub fn tile_grid(tiles: u32, max_x: u32) -> TileGrid {
    assert!(tiles >= 1 && max_x >= 1, "a tile grid covers at least one tile, with at least one workgroup along x");
    let x = tiles.min(max_x);
    TileGrid { x, y: tiles.div_ceil(x), tiles }
}

/// What a WebGPU member is, as its id hashes it. The device module fills it
/// from the adapter's information and the granted limits; the fields are plain
/// values here so that the id is testable without a device.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct AdapterIdentity {
    /// `"metal"`, `"vulkan"`, `"dx12"` or `"webgpu"`.
    pub backend: String,
    pub name: String,
    pub vendor: u32,
    pub device: u32,
    /// `"discrete"`, `"integrated"`, `"virtual"`, `"cpu"` or `"other"`.
    pub device_type: String,
    pub pci_bus: String,
    pub driver: String,
    pub driver_info: String,
    /// What turns WGSL into the platform's shader language, as the device
    /// module names it: `"naga"` natively, followed where a bytecode compiler
    /// is pinned by the bytecode format it emits (`"naga+dxbc"` on DX12), and
    /// `"user-agent"` for a browser's own compiler.
    pub translator: String,
    pub max_storage_binding: u64,
    pub max_buffer: u64,
}

impl AdapterIdentity {
    fn software(&self) -> bool {
        self.device_type == "cpu"
    }

    /// [`FabricClass::Cpu`] for a software adapter (device type `"cpu"`),
    /// [`FabricClass::Gpu`] otherwise.
    pub fn class(&self) -> FabricClass {
        if self.software() { FabricClass::Cpu } else { FabricClass::Gpu }
    }

    /// `"local/gpu-<backend>-<d12>"`, or `"local/swgpu-<backend>-<d12>"` for a
    /// software adapter. `d12` is the first 12 hex digits of
    /// BLAKE3(`"wai:quantum-fabric-webgpu-member\x01"` ‖ put(backend) ‖
    /// put(name) ‖ vendor ‖ device ‖ put(device_type) ‖ put(pci_bus) ‖
    /// put(driver) ‖ put(driver_info) ‖ put(translator) ‖ max_storage_binding ‖
    /// max_buffer), the numbers big-endian.
    ///
    /// Every such id sorts after every `local/cpu-<arch>`, so with no energy
    /// figures [`place`](super::place) keeps the CPU reference: a software
    /// adapter is class `Cpu`, but its id does not begin `local/cpu-`.
    pub fn member_id(&self) -> String {
        let mut o = DOMAIN_MEMBER.to_vec();
        put(&mut o, self.backend.as_bytes());
        put(&mut o, self.name.as_bytes());
        o.extend_from_slice(&self.vendor.to_be_bytes());
        o.extend_from_slice(&self.device.to_be_bytes());
        for s in [&self.device_type, &self.pci_bus, &self.driver, &self.driver_info, &self.translator] {
            put(&mut o, s.as_bytes());
        }
        o.extend_from_slice(&self.max_storage_binding.to_be_bytes());
        o.extend_from_slice(&self.max_buffer.to_be_bytes());
        let d12 = hex(&blake3::hash(&o).as_bytes()[..6]);
        format!("local/{}-{}-{d12}", self.prefix(), self.backend)
    }

    /// The key a runner declares in CI: `"<gpu|swgpu>-<backend>-<vendor in
    /// lowercase hex>"`, for instance `"gpu-metal-0"` or `"swgpu-vulkan-10005"`.
    pub fn key(&self) -> String {
        format!("{}-{}-{:x}", self.prefix(), self.backend, self.vendor)
    }

    fn prefix(&self) -> &'static str {
        if self.software() { "swgpu" } else { "gpu" }
    }
}

/// How a device that runs a mutant must be caught.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Detector {
    /// The arithmetic probe's outputs differ from the CPU's on the probe edges.
    Probe,
    /// The corpus digest differs from the pinned one.
    Certificate,
    /// A result that left 32 bits is not reported.
    Range,
    /// The lanes of [`race_witness`], a tile run in which invocations read
    /// amplitudes other invocations wrote for the gate before, differ from
    /// the CPU's.
    Race,
    /// [`malformed_tile_run`], a run holding a gate the tile kernel must
    /// refuse, is not refused as a host defect.
    Malformed,
}

/// A textual edit of [`SHADER`] that a conforming device must be caught
/// running.
#[derive(Clone, Copy, Debug)]
pub struct Mutant {
    pub name: &'static str,
    pub find: &'static str,
    pub replace: &'static str,
    pub detector: Detector,
}

/// The mutants. Each `find` occurs exactly once in [`SHADER`]. `mid_carry` is
/// always zero, so an edit of it would change nothing and is not among them.
pub const MUTANTS: [Mutant; 7] = [
    // fx64 takes the wrong 32 bits of the rounded product.
    Mutant { name: "M1", find: "let lo = (lo2 >> 30u) | (hi2 << 2u);", replace: "let lo = (lo2 >> 29u) | (hi2 << 3u);", detector: Detector::Probe },
    // mul_wide never negates.
    Mutant { name: "M2", find: "let negative = neg(a) != neg(b);", replace: "let negative = false;", detector: Detector::Probe },
    // The rounding constant is one short.
    Mutant { name: "M3", find: "const HALF: u32 = 0x20000000u;", replace: "const HALF: u32 = 0x1fffffffu;", detector: Detector::Probe },
    // The carry out of the low word is dropped.
    Mutant { name: "M4", find: "let lo_carry = bit(lo < p00);", replace: "let lo_carry = 0u;", detector: Detector::Probe },
    // The control test is inverted.
    Mutant { name: "M5", find: "if ((i & g.ctrl) != g.ctrl) { return; }", replace: "if ((i & g.ctrl) == g.ctrl) { return; }", detector: Detector::Certificate },
    // The range guard never fires.
    Mutant { name: "M6", find: "fn fits(v: vec2<u32>) -> bool { return v.x == select(0u, ONES, neg(v.y)); }", replace: "fn fits(v: vec2<u32>) -> bool { return true; }", detector: Detector::Range },
    // The arithmetic shift by 30 loses the sign.
    Mutant { name: "M7", find: "const EXT30: u32 = 0xfffffffcu;", replace: "const EXT30: u32 = 0x00000000u;", detector: Detector::Probe },
];

/// [`SHADER`] with `m` applied. Panics unless `m.find` occurs exactly once.
pub fn mutate(m: &Mutant) -> String {
    let n = SHADER.matches(m.find).count();
    assert_eq!(n, 1, "mutant {}: `{}` occurs {n} times in the kernel", m.name, m.find);
    SHADER.replacen(m.find, m.replace, 1)
}

/// The mutants of the tile kernel. Each `find` occurs exactly once in
/// [`TILE_SHADER`], in its tile part.
pub const TILE_MUTANTS: [Mutant; 3] = [
    // The barrier between gates is gone: a gate may read what the gate before has not yet written.
    Mutant {
        name: "T1",
        find: "storageBarrier();                          // this gate's writes before the next gate's reads",
        replace: "// no barrier between gates",
        detector: Detector::Race,
    },
    // The report never keeps the op index of a result that left 32 bits.
    Mutant { name: "T2", find: "select(bad, h.index, h.index < bad)", replace: "bad", detector: Detector::Range },
    // A gate whose pairs leave the tile is run instead of refused.
    Mutant { name: "T3", find: "h.tbit < size", replace: "h.tbit <= size", detector: Detector::Malformed },
];

/// [`TILE_SHADER`] with `m` applied. Panics unless `m.find` occurs exactly
/// once.
pub fn mutate_tile(m: &Mutant) -> String {
    let n = TILE_SHADER.matches(m.find).count();
    assert_eq!(n, 1, "mutant {}: `{}` occurs {n} times in the tile kernel", m.name, m.find);
    TILE_SHADER.replacen(m.find, m.replace, 1)
}

/// A state of `2^n_qubits` lanes (10 or more qubits, at most 20) and a run of
/// 1024 gates that a tiled plan makes one tile step per tile, built so that a
/// tile kernel without a barrier between gates goes wrong: diagonal gates
/// whose controls (qubits 5, 6 and 7) leave most invocations of a workgroup
/// idle alternate with gates on qubits 0 to 4, whose pairs are held by other
/// invocations than the amplitudes the diagonal gates updated. Idle
/// invocations run ahead into the next gate and read amplitudes not yet
/// written. Every value spans the whole 32-bit range, so a stale read shows in
/// the lanes. Panics unless `10 ≤ n_qubits ≤ 20`.
pub fn race_witness(n_qubits: u8) -> (Vec<Lane>, Vec<GateWords>) {
    assert!((10..=20).contains(&n_qubits), "the race witness takes 10 to 20 qubits, not {n_qubits}");
    let mut s = 0x7261_6365u64 + u64::from(n_qubits);
    let mut next = || {
        s = s.wrapping_add(0x9E37_79B9_7F4A_7C15);
        let mut z = s;
        z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
        z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
        z ^ (z >> 31)
    };
    let state: Vec<Lane> = (0..1usize << n_qubits).map(|_| [next() as i32, next() as i32]).collect();
    let gates = (0..1024u32)
        .map(|r| {
            let mut m = [0u32; 8];
            m.iter_mut().for_each(|x| *x = next() as u32);
            if r % 2 == 0 {
                m[2..6].fill(0);
                GateWords { m, tbit: 1 << (8 + (r / 2) % 2), ctrl: 0b1110_0000 }
            } else {
                GateWords { m, tbit: 1 << ((r / 2) % 5), ctrl: 0 }
            }
        })
        .collect();
    (state, gates)
}

/// A program a tile kernel must refuse as a host defect: on 3 qubits, a tile
/// step of 4 amplitudes holding `X` on qubit 2, whose pairs leave the tile.
pub fn malformed_tile_run() -> Program {
    let x = GateWords { m: [0, 0, 1 << 30, 0, 1 << 30, 0, 0, 0], tbit: 4, ctrl: 0 };
    Program { n_qubits: 3, start: 0, gates: vec![PlannedGate::new(x, 0)], steps: vec![Step::Tile { first: 0, count: 1, size: 4 }] }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::quantum::{BaseGate, Gate, Gateset};
    use crate::quantum_fabric::lanes::{self, Lane};
    use crate::quantum_fabric::{Certificate, Corpus, FABRIC_DEFAULT, KernelEntry, Member, Parity, Presence, apply_kernel, detect_local, place};

    /// Changes only with a reviewed edit to the kernel and to the argument in
    /// this module's documentation (or to the host layout, with
    /// [`HOST_LAYOUT`]): every certificate of the old id must then be earned
    /// again.
    const PINNED_IMPLEMENTATION: &str = "wgsl-lanes32/dc8e19f61e0e87ab";

    #[test]
    fn implementation_id_is_pinned() {
        let id = implementation_id();
        assert_eq!(id, PINNED_IMPLEMENTATION);
        let digest = id.strip_prefix("wgsl-lanes32/").expect("the implementation name");
        assert_eq!(digest.len(), 16);
        assert!(digest.bytes().all(|b| b.is_ascii_digit() || (b'a'..=b'f').contains(&b)), "{id}");
        assert_eq!(implementation_id(), id);
        // The kernel is stored with LF line endings.
        assert!(!SHADER.contains('\r'));
    }

    #[test]
    fn gate_record_layout() {
        let w = GateWords { m: [1, 2, 3, 4, 5, 6, 7, 8], tbit: 4, ctrl: 3 };
        let r = gate_record(&w, 16, 64, 9);
        let word = |k: usize| u32::from_le_bytes(r[4 * k..4 * k + 4].try_into().unwrap());
        for k in 0..8 {
            assert_eq!(r[4 * k..4 * k + 4], (k as u32 + 1).to_le_bytes(), "m[{k}]");
        }
        assert_eq!((word(8), word(9), word(10), word(11), word(12)), (4, 3, 16, 64, 9));
        assert_eq!(r[52..64], [0; 12]);
        // Little-endian: the low byte first.
        let r = gate_record(&GateWords { m: [0x8000_0001, 0, 0, 0, 0, 0, 0, 0], tbit: 1, ctrl: 0 }, 1, 64, 0x0102_0304);
        assert_eq!(r[0..4], [0x01, 0x00, 0x00, 0x80]);
        assert_eq!(r[48..52], [0x04, 0x03, 0x02, 0x01]);
    }

    #[test]
    fn grids_cover_every_item_once() {
        for n in 1..=26u32 {
            let items = 1u32 << (n - 1);
            for max_x in [1, 3, X_GROUPS_MAX] {
                let g = grid(items, max_x);
                assert_eq!((g.items, g.row_stride), (items, WORKGROUP * g.x));
                assert!(g.x >= 1 && g.x <= max_x && g.y >= 1, "{g:?}");
                let per_row = u64::from(g.x) * u64::from(WORKGROUP);
                assert!(per_row * u64::from(g.y) >= u64::from(items), "n = {n}, {g:?}");
                assert!(per_row * u64::from(g.y - 1) < u64::from(items), "n = {n}, {g:?}");
                if max_x == X_GROUPS_MAX {
                    assert!(g.y <= 65535, "n = {n}, {g:?}");
                    assert_eq!(gate_grid(n as u8), g);
                }
                if n <= 12 {
                    let mut hits = vec![0u32; items as usize];
                    for gy in 0..g.y {
                        for gx in 0..g.row_stride {
                            let p = gy * g.row_stride + gx;
                            if p < items {
                                hits[p as usize] += 1;
                            }
                        }
                    }
                    assert!(hits.iter().all(|&h| h == 1), "n = {n}, {g:?}");
                }
            }
            // The dispatch shapes fabric-v1 is checked to cover: up to 6
            // qubits part of one workgroup, 7 to 13 one row, 14 or more a grid.
            let g = gate_grid(n as u8);
            assert_eq!(n <= 6, items < WORKGROUP, "n = {n}");
            assert_eq!((7..=13).contains(&n), items >= WORKGROUP && g.y == 1, "n = {n}");
            assert_eq!(n >= 14, g.y > 1, "n = {n}");
        }
    }

    /// The kernel's index map: `p` with a zero inserted at the target bit.
    fn insert0(p: u32, tbit: u32) -> u32 {
        let low = p & (tbit - 1);
        ((p ^ low) << 1) | low
    }

    #[test]
    fn the_index_map_is_a_bijection() {
        for n in 1..=12u32 {
            for t in 0..n {
                let tbit = 1u32 << t;
                let mapped: Vec<u32> = (0..1u32 << (n - 1)).map(|p| insert0(p, tbit)).collect();
                let clear: Vec<u32> = (0..1u32 << n).filter(|i| i & tbit == 0).collect();
                // Strictly increasing and onto the indices with bit t clear.
                assert_eq!(mapped, clear, "n = {n}, t = {t}");
            }
        }
    }

    fn hardware() -> AdapterIdentity {
        AdapterIdentity {
            backend: "metal".into(),
            name: "Test GPU".into(),
            vendor: 0,
            device: 0,
            device_type: "integrated".into(),
            pci_bus: String::new(),
            driver: String::new(),
            driver_info: String::new(),
            translator: "naga".into(),
            max_storage_binding: 1 << 28,
            max_buffer: 1 << 28,
        }
    }

    fn software() -> AdapterIdentity {
        AdapterIdentity {
            backend: "vulkan".into(),
            name: "Test software rasterizer".into(),
            vendor: 0x10005,
            device: 0,
            device_type: "cpu".into(),
            pci_bus: String::new(),
            driver: "test-driver".into(),
            driver_info: "1.0".into(),
            translator: "naga".into(),
            max_storage_binding: 1 << 27,
            max_buffer: 1 << 28,
        }
    }

    /// The ids of [`hardware`] and [`software`]. They change only with a
    /// reviewed change to what a member id hashes; every certificate earned
    /// under an old id must then be earned again.
    const PINNED_HARDWARE: &str = "local/gpu-metal-a47619e299a8";
    const PINNED_SOFTWARE: &str = "local/swgpu-vulkan-917c9bb1d948";

    #[test]
    fn member_ids_are_pinned() {
        let (hw, sw) = (hardware(), software());
        assert_eq!((hw.member_id(), sw.member_id()), (PINNED_HARDWARE.to_string(), PINNED_SOFTWARE.to_string()));
        assert_eq!((hw.class(), sw.class()), (FabricClass::Gpu, FabricClass::Cpu));
        assert_eq!((hw.key(), sw.key()), ("gpu-metal-0".to_string(), "swgpu-vulkan-10005".to_string()));
        // Every field is in the id.
        let edits: [fn(&mut AdapterIdentity); 11] = [
            |a| a.backend.push('x'),
            |a| a.name.push('x'),
            |a| a.vendor ^= 1,
            |a| a.device ^= 1,
            |a| a.device_type = if a.device_type == "cpu" { "virtual".into() } else { "discrete".into() },
            |a| a.pci_bus.push('0'),
            |a| a.driver.push('x'),
            |a| a.driver_info.push('x'),
            |a| a.translator.push_str("+bytecode"),
            |a| a.max_storage_binding += 1,
            |a| a.max_buffer += 1,
        ];
        for base in [hw, sw] {
            for (k, edit) in edits.iter().enumerate() {
                let mut a = base.clone();
                edit(&mut a);
                assert_ne!(a.member_id(), base.member_id(), "field {k} of {base:?}");
            }
        }
        // Fields do not run into each other.
        let mut a = hardware();
        let mut b = hardware();
        (a.driver, a.driver_info) = ("ab".into(), String::new());
        (b.driver, b.driver_info) = ("a".into(), "b".into());
        assert_ne!(a.member_id(), b.member_id());
    }

    #[test]
    fn the_cpu_reference_is_placed_first_when_nothing_is_metered() {
        for arch in ["aarch64", "x86_64", "x86", "wasm32", "riscv64", "arm", "s390x", "powerpc64", "loongarch64"] {
            let cpu = format!("local/cpu-{arch}");
            assert!(cpu.as_str() < PINNED_HARDWARE && cpu.as_str() < PINNED_SOFTWARE, "{cpu}");
        }
        let local = detect_local();
        for gs in Gateset::ALL {
            let kernel = apply_kernel(gs);
            let member = |a: &AdapterIdentity| {
                let id = a.member_id();
                let certificate = Certificate {
                    kernel: kernel.into(),
                    implementation: implementation_id(),
                    member: id.clone(),
                    generator: FABRIC_DEFAULT.generator(gs),
                    parity: Parity::BitExact,
                    cases: 224,
                    corpus: [7; 32],
                    provenance: Default::default(),
                };
                let entry = KernelEntry { kernel: kernel.into(), implementation: implementation_id(), certificate, energy: None };
                Member { id, class: a.class(), presence: Presence::Detected, kernels: vec![entry], detail: String::new() }
            };
            let (gpu, swgpu) = (member(&hardware()), member(&software()));
            // Each member is placeable on its own.
            for m in [&gpu, &swgpu] {
                let (placed, k) = place(std::slice::from_ref(m), kernel, &Parity::BitExact).unwrap();
                assert_eq!((placed.id.as_str(), k.implementation.as_str()), (m.id.as_str(), implementation_id().as_str()));
            }
            // Beside the CPU, with no energy figure anywhere, the reference stays.
            for members in [vec![local.clone(), gpu.clone()], vec![gpu.clone(), swgpu.clone(), local.clone()]] {
                let (m, k) = place(&members, kernel, &Parity::BitExact).unwrap();
                assert_eq!((m.id.as_str(), k.implementation.as_str()), (local.id.as_str(), crate::quantum_fabric::REFERENCE), "{gs:?}");
            }
        }
    }

    /// With both implementations' entries for one member and no energy
    /// figures, placement breaks the tie by implementation name: the tile
    /// implementation sorts first and is placed, as the documentation says.
    #[test]
    fn placement_breaks_an_implementation_tie_by_name() {
        assert!(tile_implementation_id() < implementation_id());
        let id = hardware().member_id();
        for gs in Gateset::ALL {
            let kernel = apply_kernel(gs);
            let entry = |implementation: String| {
                let certificate = Certificate { kernel: kernel.into(), implementation: implementation.clone(), member: id.clone(), generator: FABRIC_DEFAULT.generator(gs), parity: Parity::BitExact, cases: 224, corpus: [7; 32], provenance: Default::default() };
                KernelEntry { kernel: kernel.into(), implementation, certificate, energy: None }
            };
            for kernels in [vec![entry(implementation_id()), entry(tile_implementation_id())], vec![entry(tile_implementation_id()), entry(implementation_id())]] {
                let m = Member { id: id.clone(), class: FabricClass::Gpu, presence: Presence::Detected, kernels, detail: String::new() };
                let (_, k) = place(std::slice::from_ref(&m), kernel, &Parity::BitExact).unwrap();
                assert_eq!(k.implementation, tile_implementation_id(), "{gs:?}");
            }
            // Offered alone, the per-gate entry is placed.
            let m = Member { id: id.clone(), class: FabricClass::Gpu, presence: Presence::Detected, kernels: vec![entry(implementation_id())], detail: String::new() };
            assert_eq!(place(std::slice::from_ref(&m), kernel, &Parity::BitExact).unwrap().1.implementation, implementation_id());
        }
    }

    #[test]
    fn mutants_apply_once() {
        let names: Vec<&str> = MUTANTS.iter().map(|m| m.name).collect();
        assert_eq!(names, ["M1", "M2", "M3", "M4", "M5", "M6", "M7"]);
        for m in &MUTANTS {
            let text = mutate(m);
            assert_ne!(text, SHADER, "{}", m.name);
            assert_eq!(text.matches(m.replace).count(), 1, "{}", m.name);
            assert_eq!(text.len() as isize - SHADER.len() as isize, m.replace.len() as isize - m.find.len() as isize);
        }
        let detectors: Vec<Detector> = MUTANTS.iter().map(|m| m.detector).collect();
        use Detector::*;
        assert_eq!(detectors, [Probe, Probe, Probe, Probe, Certificate, Range, Probe]);
    }

    /// The kernel's `mul_wide` and `fx64` in Rust, line for line, with one of
    /// the probe-detected mutants applied (or none): `[hi, lo, fx_hi, fx_lo]`,
    /// what the probe entry point writes.
    fn probe_mirror(a: u32, b: u32, mutant: &str) -> [u32; 4] {
        let neg = |x: u32| x & 0x8000_0000 != 0;
        let bit = |c: bool| u32::from(c);
        let half: u32 = if mutant == "M3" { 0x1fff_ffff } else { 0x2000_0000 };
        let ext30: u32 = if mutant == "M7" { 0 } else { 0xffff_fffc };
        // mul_wide
        let negative = if mutant == "M2" { false } else { neg(a) != neg(b) };
        let x = if neg(a) { 0u32.wrapping_sub(a) } else { a };
        let y = if neg(b) { 0u32.wrapping_sub(b) } else { b };
        let (x1, x0, y1, y0) = (x >> 16, x & 0xffff, y >> 16, y & 0xffff);
        let (p00, p01, p10, p11) = (x0 * y0, x0 * y1, x1 * y0, x1 * y1);
        let mid = p01.wrapping_add(p10);
        let mid_carry = bit(mid < p01);
        let lo = p00.wrapping_add(mid << 16);
        let lo_carry = if mutant == "M4" { 0 } else { bit(lo < p00) };
        let hi = p11.wrapping_add(mid >> 16).wrapping_add(mid_carry << 16).wrapping_add(lo_carry);
        let (hi, lo) = if negative {
            let lo_n = (!lo).wrapping_add(1);
            ((!hi).wrapping_add(bit(lo_n == 0)), lo_n)
        } else {
            (hi, lo)
        };
        // fx64
        let lo2 = lo.wrapping_add(half);
        let hi2 = hi.wrapping_add(bit(lo2 < lo));
        let fx_lo = if mutant == "M1" { (lo2 >> 29) | (hi2 << 3) } else { (lo2 >> 30) | (hi2 << 2) };
        let fx_hi = (hi2 >> 30) | if neg(hi2) { ext30 } else { 0 };
        [hi, lo, fx_hi, fx_lo]
    }

    fn probe_reference(a: i32, b: i32) -> [u32; 4] {
        let ((hi, lo), (fx_hi, fx_lo)) = (lanes::mul_wide(a, b), lanes::fxmul_wide(a, b));
        [hi, lo, fx_hi, fx_lo]
    }

    /// `apply_words` with the control test inverted (M5): a pair is updated
    /// when its control bits are not all set.
    fn apply_inverted_control(amps: &mut [Lane], w: &GateWords) {
        let fx = |a: i32, b: i32| {
            let (hi, lo) = lanes::fxmul_wide(a, b);
            ((u64::from(hi) << 32) | u64::from(lo)) as i64
        };
        let e = |k: usize| w.m[k] as i32;
        let (tbit, ctrl) = (w.tbit as usize, w.ctrl as usize);
        for i in 0..amps.len() {
            if i & tbit == 0 && i & ctrl != ctrl {
                let j = i | tbit;
                let (a0, a1) = (amps[i], amps[j]);
                let row = |r: usize| -> Lane {
                    let (mr, mi, nr, ni) = (e(4 * r), e(4 * r + 1), e(4 * r + 2), e(4 * r + 3));
                    [
                        (fx(mr, a0[0]) - fx(mi, a0[1]) + fx(nr, a1[0]) - fx(ni, a1[1])) as i32,
                        (fx(mr, a0[1]) + fx(mi, a0[0]) + fx(nr, a1[1]) + fx(ni, a1[0])) as i32,
                    ]
                };
                (amps[i], amps[j]) = (row(0), row(1));
            }
        }
    }

    #[test]
    fn mutant_witnesses_exist() {
        let edges = lanes::PROBE_EDGES;
        let pairs: Vec<(i32, i32)> = edges.iter().flat_map(|&a| edges.iter().map(move |&b| (a, b))).collect();
        // The mirror without a mutant is the CPU's arithmetic, on the edges
        // and across the whole 32-bit range.
        let mut s = 17u64;
        let mut next = || {
            s = s.wrapping_add(0x9E37_79B9_7F4A_7C15);
            let mut z = s;
            z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
            z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
            z ^ (z >> 31)
        };
        let random: Vec<(i32, i32)> = (0..20_000).map(|_| (next() as i32, next() as i32)).collect();
        for &(a, b) in pairs.iter().chain(&random) {
            assert_eq!(probe_mirror(a as u32, b as u32, ""), probe_reference(a, b), "{a} × {b}");
        }
        // Each probe-detected mutant changes the probe's output on some pair
        // of edges. The counts are the ones computed, independently of this
        // crate, when the mutants were chosen.
        for (name, differing) in [("M1", 436), ("M2", 220), ("M3", 80), ("M4", 48), ("M7", 184)] {
            let m = MUTANTS.iter().find(|m| m.name == name).unwrap();
            assert_eq!(m.detector, Detector::Probe);
            let count = pairs.iter().filter(|&&(a, b)| probe_mirror(a as u32, b as u32, name) != probe_reference(a, b)).count();
            assert!(count >= 1, "{name}");
            assert_eq!(count, differing, "{name}");
        }
        // M5 changes the output of a random-v1 circuit, so the certificate's
        // digest moves.
        let mut changed = 0;
        for c in (Corpus::Random { seed: 7, cases: 200 }).circuits(Gateset::V1) {
            let mut amps = vec![[0i32; 2]; 1 << c.n_qubits];
            amps[0] = [crate::quantum::ONE as i32, 0];
            for g in &c.ops {
                apply_inverted_control(&mut amps, &lanes::gate_words(g, c.gateset));
            }
            if lanes::output(&amps) != lanes::reference_output(&c).unwrap() {
                changed += 1;
            }
        }
        assert!(changed >= 1);
        // M6 is witnessed by `z_on_the_most_negative_lane_is_flagged`: a
        // correct guard raises the flag there, and M6's never does.
        let z = lanes::gate_words(&Gate { base: BaseGate::Z, controls: vec![], target: 0, param: 0 }, Gateset::V2);
        assert_eq!(lanes::apply_words(&mut [[0, 0], [i32::MIN, 0]], &z), Some(false));
    }

    /// Changes only with a reviewed edit to the tile kernel or to the per-gate
    /// kernel it is appended to, to the argument in this module's
    /// documentation, to the host layout ([`HOST_LAYOUT`]) or to the meaning
    /// of a program ([`PLAN_REVISION`]): every certificate of the old id must
    /// then be earned again.
    const PINNED_TILE_IMPLEMENTATION: &str = "wgsl-lanes32-tile/54e443520c020013";

    #[test]
    fn tile_implementation_id_is_pinned() {
        let id = tile_implementation_id();
        assert_eq!(id, PINNED_TILE_IMPLEMENTATION);
        let digest = id.strip_prefix("wgsl-lanes32-tile/").expect("the implementation name");
        assert_eq!(digest.len(), 16);
        assert!(digest.bytes().all(|b| b.is_ascii_digit() || (b'a'..=b'f').contains(&b)), "{id}");
        assert_ne!(id.split('/').nth(1), implementation_id().split('/').nth(1));
        // The tile kernel is appended to the per-gate one, both with LF line
        // endings, and names no tile size.
        assert!(TILE_SHADER.starts_with(SHADER) && TILE_SHADER.len() > SHADER.len());
        assert!(!TILE_SHADER.contains('\r'));
        assert_eq!(TILE_SHADER.matches("@compute").count(), 3);
        assert_eq!(TILE_SHADER.matches("storageBarrier()").count(), 1);
        assert!(!TILE_SHADER.contains("workgroupBarrier") && !TILE_SHADER.contains("var<workgroup>"));
        assert!(!SHADER.contains("Barrier"));
    }

    #[test]
    fn tile_records_layout() {
        let g = PlannedGate { words: GateWords { m: [1, 2, 3, 4, 5, 6, 7, 8], tbit: 4, ctrl: 3 }, index: 9, diag: true };
        let r = tile_gate_record(&g);
        let word = |r: &[u8], k: usize| u32::from_le_bytes(r[4 * k..4 * k + 4].try_into().unwrap());
        for k in 0..8 {
            assert_eq!(word(&r, k), k as u32 + 1, "m[{k}]");
        }
        assert_eq!((word(&r, 8), word(&r, 9), word(&r, 10), word(&r, 11)), (4, 3, 1, 9));
        assert_eq!(word(&tile_gate_record(&PlannedGate { diag: false, ..g }), 10), 0);
        let r = tile_run_record(5, 6, 1024, 8, 16);
        assert_eq!((0..5).map(|k| word(&r, k)).collect::<Vec<_>>(), [5, 6, 1024, 8, 16]);
        assert_eq!(r[20..32], [0; 12]);
        // Little-endian: the low byte first.
        assert_eq!(tile_run_record(0x0102_0304, 1, 2, 1, 1)[0..4], [0x04, 0x03, 0x02, 0x01]);
    }

    #[test]
    fn tile_grids_cover_every_tile_once() {
        for n in 0..=16u32 {
            let tiles = 1u32 << n;
            for max_x in [1, 3, TILE_X_GROUPS_MAX] {
                let g = tile_grid(tiles, max_x);
                assert!(g.x >= 1 && g.x <= max_x && g.tiles == tiles, "{g:?}");
                let mut hits = vec![0u32; tiles as usize];
                for wy in 0..g.y {
                    for wx in 0..g.x {
                        let tile = wy * g.x + wx;
                        if tile < tiles {
                            hits[tile as usize] += 1;
                        }
                    }
                }
                assert!(hits.iter().all(|&h| h == 1), "{g:?}");
                assert!(u64::from(g.x) * u64::from(g.y - 1) < u64::from(tiles), "{g:?}");
            }
            // In production both are powers of two: an exact grid.
            let g = tile_grid(tiles, TILE_X_GROUPS_MAX);
            assert_eq!(g.x * g.y, tiles);
        }
        // 26 qubits in tiles of 1024: (8, 8192).
        assert_eq!(tile_grid(1 << 16, TILE_X_GROUPS_MAX), TileGrid { x: 8, y: 8192, tiles: 1 << 16 });
    }

    #[test]
    fn tile_mutants_apply_once() {
        let names: Vec<&str> = TILE_MUTANTS.iter().map(|m| m.name).collect();
        assert_eq!(names, ["T1", "T2", "T3"]);
        for m in &TILE_MUTANTS {
            let text = mutate_tile(m);
            assert_ne!(text, TILE_SHADER, "{}", m.name);
            // The edit is in the tile part: the per-gate kernel is untouched.
            assert!(text.starts_with(SHADER), "{}", m.name);
            assert!(!SHADER.contains(m.find), "{}", m.name);
        }
        let detectors: Vec<Detector> = TILE_MUTANTS.iter().map(|m| m.detector).collect();
        assert_eq!(detectors, [Detector::Race, Detector::Range, Detector::Malformed]);
        // T1 leaves no barrier.
        assert!(!mutate_tile(&TILE_MUTANTS[0]).contains("storageBarrier()"));
        // The per-gate mutants apply to the tile kernel's copy of the per-gate one as well.
        for m in &MUTANTS {
            assert_eq!(TILE_SHADER.matches(m.find).count(), 1, "{}", m.name);
        }
    }

    /// A tile run with no barrier between its gates, in one schedule a device
    /// may choose: each of the [`TILE_WORKGROUP`] invocations runs every gate
    /// of the run before the next invocation starts. With the barrier, the
    /// only order is gate by gate.
    fn run_invocation_by_invocation(tile: &mut [Lane], base: usize, gates: &[PlannedGate]) {
        let size = tile.len();
        let lanes_of = |v: [i64; 2]| [v[0] as i32, v[1] as i32];
        for lid in 0..TILE_WORKGROUP as usize {
            for g in gates {
                let (t, c) = (g.words.tbit as usize, g.words.ctrl as usize);
                if g.diag {
                    for e in (0..4).map(|k| lid + TILE_WORKGROUP as usize * k).filter(|&e| e < size && (base + e) & c == c) {
                        let a = tile[e];
                        tile[e] = lanes_of(if (base + e) & t == 0 { lanes::exact_row(&g.words, 0, a, [0, 0]) } else { lanes::exact_row(&g.words, 1, [0, 0], a) });
                    }
                } else {
                    for q in (0..2).map(|k| lid + TILE_WORKGROUP as usize * k).filter(|&q| q < size / 2) {
                        let low = q & (t - 1);
                        let li = ((q ^ low) << 1) | low;
                        let lj = li | t;
                        if (base + li) & c == c {
                            let (a0, a1) = (tile[li], tile[lj]);
                            (tile[li], tile[lj]) = (lanes_of(lanes::exact_row(&g.words, 0, a0, a1)), lanes_of(lanes::exact_row(&g.words, 1, a0, a1)));
                        }
                    }
                }
            }
        }
    }

    #[test]
    fn tile_mutant_witnesses_exist() {
        use crate::quantum_fabric::plan::{self, Config};
        // T1: the race witness is one tile step per tile, gate by gate it is
        // the CPU's, and invocation by invocation, which a kernel without the
        // barrier between gates may do, it is not.
        for n in [10u8, 11] {
            let (state, words) = race_witness(n);
            let planned: Vec<PlannedGate> = words.iter().enumerate().map(|(k, w)| PlannedGate::new(*w, k as u32)).collect();
            let p = plan::schedule(n, 0, planned.clone(), &Config::TILED);
            assert_eq!(p.steps, [Step::Tile { first: 0, count: 1024, size: 1024 }], "n = {n}");
            let want = lanes::run_words(&state, &words).unwrap();
            assert_eq!(plan::execute_from(&p, &state), Some(want.clone()));
            let mut racy = state.clone();
            for base in (0..racy.len()).step_by(1024) {
                run_invocation_by_invocation(&mut racy[base..base + 1024], base, &planned);
            }
            let differing = racy.iter().zip(&want.amps).filter(|(a, b)| a != b).count();
            assert!(differing > 100, "n = {n}: {differing} lanes differ");
        }
        // T2: a result that leaves 32 bits inside a tile step is reported.
        let z = lanes::gate_words(&Gate { base: BaseGate::Z, controls: vec![], target: 0, param: 0 }, Gateset::V2);
        let p = plan::schedule(1, 0, vec![PlannedGate::new(z, 0)], &Config::TILED);
        assert_eq!(p.steps, [Step::Tile { first: 0, count: 1, size: 2 }]);
        assert_eq!(plan::execute_from(&p, &[[0, 0], [i32::MIN, 0]]).unwrap().out_of_range, Some(0));
        // T3: the malformed run is refused, and the same gate in a tile that
        // holds its pairs is not.
        let bad = malformed_tile_run();
        assert_eq!(plan::execute_from(&bad, &[[0, 0]; 8]), None);
        let held = Program { steps: vec![Step::Tile { first: 0, count: 1, size: 8 }], ..bad.clone() };
        assert!(plan::execute_from(&held, &[[0, 0]; 8]).is_some());
    }
}