open-standards/wai/wai-wasmq/tests/review.rs

//! What a review of the profile found, each as a test that failed before its fix
//! (extensions/quantum-wasmq.md): engines that reached different results for one envelope,
//! members of a job no signature covered, input that panicked a reader instead of being
//! refused, and bundles that packed and then could not run.

use serde_json::{Value, json};
use wai_quantum::ed25519_dalek::SigningKey;
use wai_quantum::qasm::{ExternArg, ExternDecl};
use wai_wasmq::abi::{self, Stop};
use wai_wasmq::engine::{Engine, Interpreter, Trap};
use wai_wasmq::envelope::{Bundle, Callout, Module, Run, open, pack, write_unchecked};
use wai_wasmq::interp::Metering;
use wai_wasmq::run::{EngineKind, run};
use wai_wasmq::{meter, profile};

fn wasm(wat: &str) -> Vec<u8> {
    wat::parse_str(wat).unwrap()
}

fn leb(mut v: u64) -> Vec<u8> {
    let mut out = Vec::new();
    loop {
        let b = (v & 0x7f) as u8;
        v >>= 7;
        if v == 0 {
            out.push(b);
            return out;
        }
        out.push(b | 0x80);
    }
}

fn section(id: u8, body: &[u8]) -> Vec<u8> {
    let mut s = vec![id];
    s.extend(leb(body.len() as u64));
    s.extend_from_slice(body);
    s
}

fn raw(sections: &[Vec<u8>]) -> Vec<u8> {
    let mut m = b"\0asm\x01\0\0\0".to_vec();
    for s in sections {
        m.extend_from_slice(s);
    }
    m
}

/// One type `() -> ()`.
fn unit_type() -> Vec<u8> {
    section(1, &[0x01, 0x60, 0x00, 0x00])
}

/// `n` functions of type 0, each an empty body.
fn functions(n: u64) -> (Vec<u8>, Vec<u8>) {
    let mut f = leb(n);
    f.extend(std::iter::repeat_n(0u8, n as usize));
    let mut c = leb(n);
    for _ in 0..n {
        c.extend_from_slice(&[0x02, 0x00, 0x0b]);
    }
    (section(3, &f), section(10, &c))
}

fn kinds() -> Vec<EngineKind> {
    wai_wasmq::engine::available().iter().map(|s| EngineKind::parse(s).unwrap()).collect()
}

/// Every engine of this build on `module`: the interpreter on the module as written and on
/// its prepared form, and the native engine where the build has it.
fn engines(module: &[u8]) -> Vec<Box<dyn Engine>> {
    let module: &'static [u8] = Box::leak(module.to_vec().into_boxed_slice());
    let prepared: &'static [u8] = Box::leak(meter::prepare(module).unwrap().into_boxed_slice());
    #[allow(unused_mut)] // the native engine is added where this build has it
    let mut v: Vec<Box<dyn Engine>> = vec![Box::new(Interpreter::new(module, Metering::Own).unwrap()), Box::new(Interpreter::new(prepared, Metering::Module).unwrap())];
    #[cfg(all(feature = "wasmtime", not(target_arch = "wasm32")))]
    v.push(Box::new(wai_wasmq::engine::Native::new(prepared).unwrap()));
    v
}

const SCALAR: &str = "OPENQASM 3.0;\ninclude \"stdgates.inc\";\nextern f(bit[8]) -> bit[8];\nqubit[8] q;\nbit[8] b;\nbit[8] r;\nh q;\nb = measure q;\nr = f(b);\n";
const LIST: &str = "OPENQASM 3.0;\ninclude \"stdgates.inc\";\nextern f(bit[72]) -> bit[72];\nqubit[72] q;\nbit[72] b;\nbit[72] r;\nh q;\nb = measure q;\nr = f(b);\n";

fn bundle(program: &str, module: Vec<u8>, priors: Vec<(String, Vec<u8>)>) -> Bundle {
    Bundle { program: program.into(), inputs: Default::default(), modules: vec![Module { name: "m".into(), bytes: module, priors }], callouts: vec![Callout { name: "f".into(), module: 0, export: "f".into() }], run: Run::new(4, 1) }
}

fn code_of<T>(r: Result<T, profile::Refusal>) -> &'static str {
    match r {
        Ok(_) => "accepted",
        Err(e) => e.code,
    }
}

/// How a call ended, in words that compare.
fn outcome<T: std::fmt::Debug>(r: Result<T, Stop>) -> String {
    match r {
        Ok(v) => format!("ok {v:?}"),
        Err(Stop::Fault(f)) => format!("fault {}", f.reason),
        Err(Stop::Host(_)) => "host".into(),
    }
}

/// Runs an opened bundle on every engine of the build: each job's canonical bytes, or why
/// there is none.
fn everywhere(o: &wai_wasmq::Opened) -> Vec<String> {
    let key = SigningKey::from_bytes(&[7; 32]);
    kinds()
        .into_iter()
        .map(|k| match run(o, k, &key, false) {
            Ok((v, _)) => format!("{}", String::from_utf8_lossy(&wai_quantum::engine::receipt::canonical(&v))),
            Err(e) => format!("no receipt on {k:?}: {e}"),
        })
        .collect()
}

// ---------------------------------------------------------------------------
// 1. One envelope, one receipt: the memory a host reaches
// ---------------------------------------------------------------------------

/// A list-form callout whose module declares a memory and does not export it.
const UNEXPORTED: &str = r#"(module (memory 1 1)
    (func (export "cabi_realloc") (param i32 i32 i32 i32) (result i32) i32.const 1024)
    (func (export "f") (param i32 i32) (result i32)
        i32.const 2048 local.get 0 i32.store i32.const 2052 local.get 1 i32.store i32.const 2048))"#;

#[test]
fn every_engine_reaches_a_module_s_memory_the_same_way() {
    let decl = ExternDecl { name: "f".into(), args: vec![ExternArg::Bit(72)], ret: Some(72) };
    let input = vec![true; 72];
    for (what, module) in [("not exported", wasm(UNEXPORTED)), ("exported", wasm(&UNEXPORTED.replace("(memory 1 1)", "(memory (export \"memory\") 1 1)")))] {
        // How the call ended, and the fuel it left: an engine that got further than
        // another before it stopped has used more.
        let got: Vec<(String, i64)> = engines(&module)
            .iter()
            .map(|e| {
                let mut i = e.instantiate().unwrap();
                i.set_fuel(1 << 30);
                let r = outcome(abi::call(i.as_mut(), &decl, "f", &input, false));
                (r, i.fuel())
            })
            .collect();
        assert!(got.windows(2).all(|w| w[0] == w[1]), "a memory that is {what}: the engines differ: {got:?}");
        assert!(got[0].0.starts_with(if what == "exported" { "ok " } else { "fault bad_result" }), "{got:?}");
    }
}

#[test]
fn a_bundle_whose_memory_the_host_cannot_reach_is_refused_on_reading() {
    // A list-form callout.
    assert_eq!(code_of(pack(&bundle(LIST, wasm(UNEXPORTED), vec![]))), "W015");
    // A prior, with a scalar callout.
    let priors = r#"(module (memory 1 1)
        (func (export "cabi_realloc") (param i32 i32 i32 i32) (result i32) i32.const 1024)
        (func (export "wasmq-prior") (param i32 i32 i32))
        (func (export "f") (param i64) (result i64) local.get 0))"#;
    assert_eq!(code_of(pack(&bundle(SCALAR, wasm(priors), vec![("p".into(), b"prior".to_vec())]))), "W015");
    // The positive control: the same two modules with the memory exported pack and run.
    for (program, module, pr) in [
        (LIST, UNEXPORTED.replace("(memory 1 1)", "(memory (export \"memory\") 1 1)"), vec![]),
        (SCALAR, priors.replace("(memory 1 1)", "(memory (export \"memory\") 1 1)"), vec![("p".to_string(), b"prior".to_vec())]),
    ] {
        let env = pack(&bundle(program, wasm(&module), pr)).unwrap();
        let jobs = everywhere(&open(&env).unwrap());
        assert!(jobs.windows(2).all(|w| w[0] == w[1]) && jobs[0].contains("\"status\":\"done\""), "{jobs:?}");
    }
}

// ---------------------------------------------------------------------------
// 2. Nothing a reader takes from a job is outside the signature
// ---------------------------------------------------------------------------

fn a_job(module: &str, per_call: u64) -> (wai_wasmq::Opened, Value) {
    let mut b = bundle(SCALAR, wasm(module), vec![]);
    b.run.per_call = per_call;
    let o = open(&pack(&b).unwrap()).unwrap();
    let (body, _) = run(&o, EngineKind::Interpreter, &SigningKey::from_bytes(&[7; 32]), false).unwrap();
    (o, body)
}

const IDENTITY: &str = r#"(module (func (export "f") (param i64) (result i64) local.get 0))"#;
const SPIN: &str = r#"(module (func (export "f") (param i64) (result i64) loop br 0 end i64.const 0))"#;

/// A program past the controls the reader writes in standard gates is refused, and the
/// refusal offers nothing a hybrid program cannot use: its run is on the tableau alone.
#[test]
fn a_refusal_for_controls_offers_no_method_a_hybrid_program_cannot_use() {
    let program = "OPENQASM 3.0;\ninclude \"stdgates.inc\";\nextern f(bit[1]) -> bit[1];\nqubit[18] q;\nbit[1] d;\nctrl(17) @ x q[0], q[1], q[2], q[3], q[4], q[5], q[6], q[7], q[8], q[9], q[10], q[11], q[12], q[13], q[14], q[15], q[16], q[17];\nd = f(d);\n";
    let b = Bundle { program: program.into(), inputs: Default::default(), modules: vec![Module { name: "m".into(), bytes: wasm(IDENTITY), priors: vec![] }], callouts: vec![Callout { name: "f".into(), module: 0, export: "f".into() }], run: Run::new(4, 1) };
    let e = pack(&b).expect_err("17 controls");
    assert!(e.code == "W016" && e.message.contains("Q208"), "{e}");
    assert!(!e.message.contains("state vector") && !e.message.contains("bit-exact"), "{e}");
}

/// Each budget is at most 2^39 (§2.2, §4.8), as every verifier holds a contract to it: at
/// the bound a run packs, runs and verifies, and one past it is refused when packed, so the
/// writer never seals a job its verifiers refuse.
#[test]
fn a_budget_past_what_a_run_may_be_given_is_refused_when_packed() {
    use wai_wasmq::envelope::MAX_BUDGET;
    assert_eq!(MAX_BUDGET, 1 << 39);
    type Set = fn(&mut Bundle, u64);
    let sets: [(&str, Set); 3] = [("per call", |b, v| b.run.per_call = v), ("per instance", |b, v| b.run.per_init = v), ("per run", |b, v| b.run.per_job = v)];
    for (what, set) in sets {
        let mut b = bundle(SCALAR, wasm(IDENTITY), vec![]);
        set(&mut b, MAX_BUDGET + 1);
        let e = pack(&b).expect_err(what);
        assert!(e.code == "W017" && e.message.contains("past 2^39"), "{what}: {e}");
        if what == "per run" {
            continue; // a run given 2^39 asks more than a host has (§4.8), and is refused for its work
        }
        set(&mut b, MAX_BUDGET);
        let o = open(&pack(&b).unwrap_or_else(|e| panic!("{what}: {e}"))).unwrap();
        let (body, _) = run(&o, EngineKind::Interpreter, &SigningKey::from_bytes(&[7; 32]), false).unwrap();
        let v = wai_wasmq::verify(&body, Some(&o), EngineKind::Interpreter).unwrap();
        assert!(v.ok(), "{what} at 2^39: {:?}", v.well_formed);
    }
}

/// A job whose contract a JSON writer carried and wrote otherwise (4.0 for 4) is the same
/// sealed content, its receipt the same: given its envelope, the envelope is the one it binds
/// and runs again to the same result, as every reader of the job finds.
#[test]
fn a_contract_written_otherwise_is_the_same_bundle() {
    let (o, done) = a_job(IDENTITY, 500);
    let mut respelt = done.clone();
    let shots = respelt["request"]["wasmq"]["run"]["shots"].as_u64().unwrap();
    respelt["request"]["wasmq"]["run"]["shots"] = json!(shots as f64);
    assert_ne!(respelt, done, "a number written another way is another value to a reader that keeps its spelling");
    let v = wai_wasmq::verify(&respelt, Some(&o), EngineKind::Interpreter).unwrap();
    assert!(v.signature && v.well_formed.is_empty(), "{:?}", v.well_formed);
    assert_eq!((v.bundle, v.reproduced), (Some(true), Some(true)));
}

#[test]
fn a_job_whose_status_or_method_was_edited_outside_the_signature_is_judged_by_what_is_sealed_and_noted() {
    // The verdict is the sealed content's, on every surface alike (§6.5): the host's
    // unsealed words decide nothing, and where they differ from what is sealed a reader is
    // told, beside the verdict. The outcome a check reports is the sealed result's.
    let (o, fault) = a_job(SPIN, 500);
    assert_eq!(fault["status"], "fault");
    let v = wai_wasmq::verify(&fault, Some(&o), EngineKind::Interpreter).unwrap();
    assert!(v.ok() && v.notes.is_empty(), "the positive control: {:?}", v.notes);
    let mut edited = fault.clone();
    edited["status"] = json!("done");
    let v = wai_wasmq::verify(&edited, Some(&o), EngineKind::Interpreter).unwrap();
    assert!(v.ok(), "a fault edited to done is the sealed fault's verdict");
    assert_eq!(v.outcome.as_deref(), Some("fault"), "the outcome is the sealed result's");
    assert_eq!(v.notes, vec![r#"the host's unsealed status says "done"; the sealed result says "fault""#.to_string()]);
    let (o, done) = a_job(IDENTITY, 500);
    for (member, value, note) in [
        ("status", json!("fault"), r#"the host's unsealed status says "fault"; the sealed result says "done""#),
        ("method", json!("statevector"), r#"the host's unsealed method says "statevector"; the sealed result says "stabilizer""#),
        ("note", json!("a member nothing signs"), "the host's body holds `note`, which nothing seals"),
    ] {
        let mut edited = done.clone();
        edited[member] = value;
        for bundle in [Some(&o), None] {
            let v = wai_wasmq::verify(&edited, bundle, EngineKind::Interpreter).unwrap();
            assert!(v.ok(), "the body's `{member}` changed: {:?}", v.well_formed);
            assert_eq!(v.notes, vec![note.to_string()], "the body's `{member}` changed");
        }
    }
    let mut bare = done.clone();
    bare.as_object_mut().unwrap().remove("status");
    assert_eq!(wai_wasmq::verify(&bare, None, EngineKind::Interpreter).unwrap().notes, vec!["the host's body has no `status`; the sealed result gives it".to_string()]);
}

#[test]
fn a_job_names_its_signer_and_a_job_sealed_again_names_another() {
    // A receipt shows that a key sealed a result; who holds the key is the reader's to
    // compare. So a check names the key, and a result changed and sealed again under
    // another key shows as another signer.
    let (o, job) = a_job(IDENTITY, 500);
    let genuine = wai_wasmq::verify(&job, None, EngineKind::Interpreter).unwrap();
    let demo = SigningKey::from_bytes(&[7; 32]);
    let hex = |b: &[u8]| b.iter().map(|x| format!("{x:02x}")).collect::<String>();
    assert_eq!(genuine.signer.as_deref(), Some(hex(demo.verifying_key().as_bytes()).as_str()));
    assert_eq!(genuine.outcome.as_deref(), Some("ok"));
    // The forgery: other counts with the same sum, sealed with a key of the forger's.
    let mut result = job["result"].clone();
    result.as_object_mut().unwrap().remove("receipt");
    result.as_object_mut().unwrap().remove("energy");
    result["counts"] = json!({ "0000000000000000": 4 });
    let other = SigningKey::from_bytes(&[9; 32]);
    let forged = wai_wasmq::run::seal(&o, result, &other);
    let v = wai_wasmq::verify(&forged, None, EngineKind::Interpreter).unwrap();
    assert!(v.signature, "a seal under any key is a valid seal: that is what a receipt is");
    assert_eq!(v.signer.as_deref(), Some(hex(other.verifying_key().as_bytes()).as_str()));
    assert_ne!(v.signer, genuine.signer, "the forgery shows as another signer");
    // And with the bundle, the forged result is not the one a run gives.
    assert_eq!(wai_wasmq::verify(&forged, Some(&o), EngineKind::Interpreter).unwrap().reproduced, Some(false));
}

// ---------------------------------------------------------------------------
// 4. A module is refused, never a panic, and is held to the feature set
// ---------------------------------------------------------------------------

#[test]
fn a_malformed_module_is_refused_not_a_panic() {
    let cases: [&[u8]; 2] = [
        // One type, one function of a type that does not exist, one body.
        &[0x00, 0x61, 0x73, 0x6d, 0x01, 0, 0, 0, 0x01, 0x04, 0x01, 0x60, 0x00, 0x00, 0x03, 0x02, 0x01, 0x05, 0x0a, 0x04, 0x01, 0x02, 0x00, 0x0b],
        // No type section at all.
        &[0x00, 0x61, 0x73, 0x6d, 0x01, 0, 0, 0, 0x03, 0x02, 0x01, 0x05, 0x0a, 0x04, 0x01, 0x02, 0x00, 0x0b],
    ];
    for bytes in cases {
        let r = std::panic::catch_unwind(|| profile::check(bytes));
        assert_eq!(r.map(code_of).unwrap_or("panicked"), "W001", "{bytes:02x?}");
    }
    // A function section that declares more functions than any reader holds, with one body.
    let mut f = leb(1_000_001);
    f.push(0);
    let m = raw(&[unit_type(), section(3, &f), section(10, &[0x01, 0x02, 0x00, 0x0b])]);
    let r = std::panic::catch_unwind(|| profile::check(&m));
    assert!(matches!(r.map(code_of), Ok("W001" | "W010")), "a function count past every reader's limit");
}

#[test]
fn a_body_that_does_not_end_or_is_not_in_the_feature_set_s_encoding_is_refused() {
    let memory = section(5, &[0x01, 0x01, 0x01, 0x01]);
    let one = section(3, &[0x01, 0x00]);
    let cases: [(&str, Vec<u8>); 4] = [
        ("the positive control: i32.const 0, drop, end", raw(&[unit_type(), one.clone(), section(10, &[0x01, 0x05, 0x00, 0x41, 0x00, 0x1a, 0x0b])])),
        ("a body with no end", raw(&[unit_type(), one.clone(), section(10, &[0x01, 0x04, 0x00, 0x41, 0x00, 0x1a])])),
        ("i32.load with a memory index in its alignment", raw(&[unit_type(), one.clone(), memory.clone(), section(10, &[0x01, 0x09, 0x00, 0x41, 0x00, 0x28, 0x42, 0x00, 0x00, 0x1a, 0x0b])])),
        ("memory.grow with an overlong memory index", raw(&[unit_type(), one.clone(), memory.clone(), section(10, &[0x01, 0x08, 0x00, 0x41, 0x00, 0x40, 0x80, 0x00, 0x1a, 0x0b])])),
    ];
    for (i, (what, m)) in cases.iter().enumerate() {
        let r = std::panic::catch_unwind(|| profile::check(m)).map(code_of).unwrap_or("panicked");
        assert_eq!(r, if i == 0 { "accepted" } else { "W001" }, "{what}");
    }
}

#[test]
fn the_function_limit_is_one_a_module_can_reach() {
    let at = |n: u64| {
        let (f, c) = functions(n);
        code_of(profile::check(&raw(&[unit_type(), f, c])))
    };
    assert_eq!(at(1 << 16), "accepted", "2^16 functions");
    assert_eq!(at((1 << 16) + 1), "W010", "one more");
}

// ---------------------------------------------------------------------------
// 5. A fault is the same fault on every engine
// ---------------------------------------------------------------------------

/// The largest `n` below `past` for which `ok` holds, `ok` holding up to some `n` and no further.
fn largest(past: usize, ok: impl Fn(usize) -> bool) -> usize {
    let (mut lo, mut hi) = (1, past);
    assert!(ok(lo) && !ok(hi));
    while hi - lo > 1 {
        let mid = (lo + hi) / 2;
        if ok(mid) { lo = mid } else { hi = mid }
    }
    lo
}

fn call_all(module: &[u8], name: &str, arg: u64) -> Vec<(Result<Vec<u64>, Trap>, i64)> {
    engines(module)
        .iter()
        .map(|e| {
            let mut i = e.instantiate().unwrap();
            i.set_fuel(1 << 40);
            i.set_stack(0);
            let r = i.call(name, &[arg]);
            (r, i.fuel())
        })
        .collect()
}

#[test]
fn an_indirect_call_where_the_stack_ends_faults_the_same_way_on_every_engine() {
    // `$r` recurses `n` times and then calls through the table with an index outside it.
    let m = wasm(
        r#"(module (type $t (func (param i64) (result i64))) (table 1 funcref)
            (func $r (param i64) (result i64)
                local.get 0 i64.eqz
                if (result i64) i64.const 0 i32.const 7 call_indirect (type $t)
                else local.get 0 i64.const 1 i64.sub call $r end)
            (func (export "f") (param i64) (result i64) local.get 0 call $r))"#,
    );
    // The smallest recursion at which the interpreter stops for the stack.
    let own = Interpreter::new(&m, Metering::Own).unwrap();
    let stops = |n: u64| {
        let mut i = own.instantiate().unwrap();
        i.set_fuel(1 << 40);
        i.set_stack(0);
        i.call("f", &[n]) == Err(Trap::Stack)
    };
    let (mut lo, mut hi) = (0u64, 1 << 24);
    assert!(!stops(lo) && stops(hi));
    while hi - lo > 1 {
        let mid = (lo + hi) / 2;
        if stops(mid) { hi = mid } else { lo = mid }
    }
    for n in hi.saturating_sub(4)..=hi + 2 {
        let got = call_all(&m, "f", n);
        assert!(got.windows(2).all(|w| w[0] == w[1]), "recursing {n} times (the stack ends at {hi}): {:?}", got.iter().map(|g| &g.0).collect::<Vec<_>>());
    }
}

#[test]
fn every_way_an_indirect_call_traps_is_the_same_on_every_engine() {
    let m = wasm(
        r#"(module (type $t (func (param i64) (result i64))) (type $u (func (result i64)))
            (table 4 funcref) (elem (i32.const 0) $ok $other)
            (func $ok (type $t) local.get 0 i64.const 1 i64.add)
            (func $other (type $u) i64.const 9)
            (func (export "f") (param i64) (result i64) i64.const 5 local.get 0 i32.wrap_i64 call_indirect (type $t)))"#,
    );
    for (index, want) in [(0u64, Ok(vec![6])), (1, Err(Trap::IndirectCallType)), (2, Err(Trap::IndirectCallNull)), (4, Err(Trap::TableOutOfBounds)), (u32::MAX as u64, Err(Trap::TableOutOfBounds))] {
        let got = call_all(&m, "f", index);
        assert!(got.windows(2).all(|w| w[0] == w[1]), "index {index}: {got:?}");
        assert_eq!(got[0].0, want, "index {index}");
    }
}

#[test]
fn an_argument_is_read_as_a_value_of_its_parameter_s_type_on_every_engine() {
    // Found by this crate's own sweep of the family, not by the review: the interpreter
    // took a 64-bit argument for a 32-bit parameter whole, where the native engine takes
    // its low 32 bits. No run reaches it (a host passes values of the type), but the
    // engines are held to one answer for any call.
    let m = wasm(r#"(module (func (export "i") (param i32) (result i32) local.get 0) (func (export "f") (param f32) (result f32) local.get 0))"#);
    for name in ["i", "f"] {
        let got = call_all(&m, name, (1 << 40) + 5);
        assert!(got.windows(2).all(|w| w[0] == w[1]), "{name}: {got:?}");
        assert_eq!(got[0].0, Ok(vec![5]), "{name}");
    }
}

// ---------------------------------------------------------------------------
// 6. The native engine holds every call the profile admits
// ---------------------------------------------------------------------------

/// The reviewer's module: a function of forty parameters that recurses to the limit and
/// then holds tens of thousands of values across calls in two dozen locals.
fn rotating(steps: usize, depth: u64) -> Vec<u8> {
    let mut body = format!("local.get 0 i64.const {depth} i64.lt_u if local.get 0 i64.const 1 i64.add ");
    for p in 1..40 {
        body.push_str(&format!("local.get {p} "));
    }
    body.push_str("call $f drop end local.get 0 i64.const 99999999 i64.eq if ");
    for k in 0..steps {
        body.push_str(&format!("i32.const 0 i64.load local.set {} call $g local.get {} local.get 64 i64.add local.set 64 ", 40 + k % 24, 40 + (k + 1) % 24));
    }
    body.push_str("end local.get 64 ");
    for p in 0..40 {
        body.push_str(&format!("local.get {p} i64.add "));
    }
    let consts: String = (1..40).map(|p| format!("i64.const {p} ")).collect();
    wasm(&format!(
        "(module (memory 1 1) (func $g i32.const 0 i32.const 0 i64.load i64.const 1 i64.add i64.store) (func $f (param {}) (result i64) (local {}) {body}) (func (export \"f\") (param i64) (result i64) local.get 0 {consts} call $f))",
        "i64 ".repeat(40),
        "i64 ".repeat(25)
    ))
}

#[test]
fn a_module_the_profile_admits_runs_on_every_engine_at_the_depth_it_admits() {
    // As the review gave it, 40,000 steps recursing 1023 times: a body past the profile's.
    assert_eq!(profile::check(&rotating(40_000, 1023)).unwrap_err().code, "W010");
    // The most steps a body the profile admits holds, at the depth the stack admits, and
    // one deeper: the same on every engine, and the first runs where the second faults.
    let steps = largest(4000, |s| profile::check(&rotating(s, 1)).is_ok());
    assert!(steps > 500, "{steps} steps");
    let w = profile::check(&rotating(steps, 1)).unwrap().weights;
    let depth = (u64::from(profile::MAX_STACK) - u64::from(w[2])) / u64::from(w[1]);
    for (d, ok) in [(depth, true), (depth + 1, false)] {
        let got = call_all(&rotating(steps, d), "f", 0);
        assert!(got.windows(2).all(|w| w[0] == w[1]), "the engines differ at depth {d}: {:?}", got.iter().map(|g| format!("{:?}", g.0).chars().take(90).collect::<String>()).collect::<Vec<_>>());
        assert_eq!(got[0].0.is_ok(), ok, "depth {d}: {:?}", got[0].0);
    }
}

// ---------------------------------------------------------------------------
// 7. What is packed is what was given
// ---------------------------------------------------------------------------

#[test]
fn an_input_a_double_cannot_hold_is_refused_not_changed() {
    let program = "OPENQASM 3.0;\ninclude \"stdgates.inc\";\ninput uint[64] mask;\nextern f(uint[64]) -> bit[8];\nqubit[8] q;\nbit[8] r;\nr = f(mask);\nh q;\nbit[8] b;\nb = measure q;\n";
    let module = wasm(IDENTITY);
    for mask in [(1i64 << 53) + 1, i64::MAX - 100] {
        let mut b = bundle(program, module.clone(), vec![]);
        b.inputs.insert("mask".into(), mask);
        match pack(&b) {
            Err(e) => assert_eq!(e.code, "W017", "{e}"),
            Ok(env) => assert_eq!(open(&env).map(|o| o.bundle.inputs).map_err(|e| e.to_string()), Ok(b.inputs.clone()), "pack wrote another input than the one given ({mask})"),
        }
    }
    // The positive control: the largest input a double holds is packed as it is.
    let mut b = bundle(program, module, vec![]);
    b.inputs.insert("mask".into(), (1i64 << 53) - 1);
    b.run.method = "stabilizer".into();
    assert_eq!(open(&pack(&b).unwrap()).unwrap().bundle, b);
}

// ---------------------------------------------------------------------------
// 8. The profile runs what its text defines, and no more
// ---------------------------------------------------------------------------

#[test]
fn a_program_outside_the_clifford_gates_is_refused() {
    // A gate outside the group, and a gate that takes an angle, whatever the angle.
    for gate in ["t q[0];", "rx(0.3) q[0];", "rz(pi / 2) q[0];", "ccx q[0], q[1], q[2];"] {
        let program = SCALAR.replace("h q;", &format!("h q;\n{gate}"));
        assert_eq!(code_of(pack(&bundle(&program, wasm(IDENTITY), vec![]))), "W016", "{gate}");
    }
    assert_eq!(code_of(pack(&bundle(SCALAR, wasm(IDENTITY), vec![]))), "accepted");
}

#[test]
fn a_program_of_more_qubits_than_the_method_holds_is_refused_on_reading() {
    let program = |n: u32| format!("OPENQASM 3.0;\ninclude \"stdgates.inc\";\nextern f(bit[8]) -> bit[8];\nqubit[{n}] q;\nbit[8] b;\nbit[8] r;\nh q[0];\nb[0] = measure q[0];\nr = f(b);\n");
    assert_eq!(code_of(pack(&bundle(&program(32_769), wasm(IDENTITY), vec![]))), "W016");
    // The largest the method holds is taken (its tableau is half a gibibyte: not run here).
    assert!(open(&pack(&bundle(&program(32_768), wasm(IDENTITY), vec![])).unwrap()).is_ok());
    // And a program of many qubits runs: 3000 here.
    let jobs = everywhere(&open(&pack(&bundle(&program(3000), wasm(IDENTITY), vec![])).unwrap()).unwrap());
    assert!(jobs.windows(2).all(|w| w[0] == w[1]) && jobs[0].contains("\"status\":\"done\""), "{}", &jobs[0][..jobs[0].len().min(200)]);
}

#[test]
fn a_measurement_or_reset_takes_a_value_only_when_its_outcome_is_random() {
    // §6.1, worked by hand for this program: `a` is put in superposition and reset (its
    // outcome is random: the first value of the shot's stream); `q` is reset while still
    // in |0> (determined: no value); then each of q's eight measurements is random, and
    // takes the next value in order. `r` is `f(b)`, and `f` returns what it is given.
    let program = "OPENQASM 3.0;\ninclude \"stdgates.inc\";\nextern f(bit[8]) -> bit[8];\nqubit[8] q;\nqubit a;\nbit[8] b;\nbit[8] r;\nh a;\nreset a;\nreset q;\nh q;\nb = measure q;\nr = f(b);\n";
    let mut bun = bundle(program, wasm(IDENTITY), vec![]);
    bun.run = Run::new(200, 42);
    let o = open(&pack(&bun).unwrap()).unwrap();
    let mut want: std::collections::BTreeMap<String, u64> = Default::default();
    for shot in 0..200 {
        let mut stream = wai_wasmq::run::Outcomes::of_shot(42, shot);
        stream.next_reads_one(); // the reset of `a`
        let b: Vec<bool> = (0..8).map(|_| stream.next_reads_one()).collect();
        // The outcome: r then b, each with its highest bit first.
        let half: String = (0..8).rev().map(|i| if b[i] { '1' } else { '0' }).collect();
        *want.entry(format!("{half}{half}")).or_default() += 1;
    }
    let jobs = everywhere(&o);
    assert!(jobs.windows(2).all(|w| w[0] == w[1]));
    let job: Value = serde_json::from_str(&jobs[0]).unwrap();
    assert_eq!(job["result"]["counts"], json!(want));
    // The stream is the text's: SplitMix64 from the shot's seed XOR 0x51574d31, a value
    // below 2^63 reading 1.
    let mut state = wai_wasmq::run::shot_seed(42, 7) ^ 0x5157_4d31;
    let mut stream = wai_wasmq::run::Outcomes::of_shot(42, 7);
    for _ in 0..100 {
        state = state.wrapping_add(0x9e37_79b9_7f4a_7c15);
        let mut z = state;
        z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
        z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
        assert_eq!(stream.next_reads_one(), (z ^ (z >> 31)) >> 63 == 0);
    }
}

// ---------------------------------------------------------------------------
// 11. What packs, runs; and each rule has its code
// ---------------------------------------------------------------------------

#[test]
fn what_pack_accepts_every_engine_can_run() {
    // `(func)` and an exported function of `calls` calls of it.
    let module = |calls: usize| {
        let mut body = vec![0x00];
        for _ in 0..calls {
            body.extend_from_slice(&[0x10, 0x00]);
        }
        body.extend_from_slice(&[0x20, 0x00, 0x0b]);
        let mut code = leb(2);
        code.extend_from_slice(&[0x02, 0x00, 0x0b]);
        code.extend(leb(body.len() as u64));
        code.extend_from_slice(&body);
        let types = section(1, &[0x02, 0x60, 0x00, 0x00, 0x60, 0x01, 0x7e, 0x01, 0x7e]);
        raw(&[types, section(3, &[0x02, 0x00, 0x01]), section(7, &[0x01, 0x01, b'f', 0x00, 0x01]), section(10, &code)])
    };
    // As the review gave it, 183,000 calls: a body past the profile's.
    assert_eq!(pack(&bundle(SCALAR, module(183_000), vec![])).unwrap_err().code, "W010");
    // The most calls a body the profile admits holds: packed, and run the same everywhere.
    let calls = largest(10_000, |n| profile::check(&module(n)).is_ok());
    assert!(calls > 8000, "{calls} calls");
    let env = pack(&bundle(SCALAR, module(calls), vec![])).unwrap();
    let jobs = everywhere(&open(&env).unwrap());
    assert!(jobs.windows(2).all(|w| w[0] == w[1]), "the engines differ");
    assert!(jobs[0].contains("\"status\":\"ok\""), "{}", &jobs[0][..jobs[0].len().min(200)]);
}

#[test]
fn a_type_outside_the_profile_has_its_rule_s_code_with_or_without_an_instruction() {
    for (wat, code) in [
        ("(module (func (param externref)))", "W007"),
        ("(module (func (local funcref)))", "W007"),
        ("(module (type (struct (field i32))))", "W007"),
        ("(module (func (param v128)))", "W006"),
        ("(module (func (local v128)))", "W006"),
        ("(module (func (param i64)))", "accepted"),
    ] {
        assert_eq!(code_of(profile::check(&wasm(wat))), code, "{wat}");
    }
}

#[test]
fn an_export_the_host_calls_has_exactly_its_type() {
    let with = |export: &str| format!(r#"(module (memory (export "memory") 1 1) {export} (func (export "f") (param i64) (result i64) local.get 0))"#);
    for (export, code) in [
        (r#"(func (export "wasmq-seed") (param i64))"#, "accepted"),
        (r#"(func (export "wasmq-seed") (param i32))"#, "W012"),
        (r#"(func (export "wasmq-seed") (param f64))"#, "W012"),
        (r#"(func (export "init") (param i32))"#, "W012"),
        (r#"(func (export "wasmq-prior") (param i32 i32 i64))"#, "W012"),
        (r#"(func (export "wasmq-prior") (param i32 i32 i32))"#, "accepted"),
        (r#"(func (export "cabi_realloc") (param i64 i64 i64 i64) (result i64) i64.const 0)"#, "W012"),
        (r#"(func (export "cabi_realloc") (param i32 i32 i32 i32) (result i32) i32.const 0)"#, "accepted"),
        (r#"(func (export "cabi_post_f") (param i32 i32))"#, "W012"),
        (r#"(func (export "cabi_post_f") (param i32))"#, "accepted"),
    ] {
        assert_eq!(code_of(profile::check(&wasm(&with(export)))), code, "{export}");
    }
}

#[test]
fn a_contract_names_one_callout_for_each_extern_in_the_order_declared() {
    let two = "OPENQASM 3.0;\ninclude \"stdgates.inc\";\nextern f(bit[8]) -> bit[8];\nextern g(bit[8]) -> bit[8];\nqubit[8] q;\nbit[8] b;\nbit[8] r;\nh q;\nb = measure q;\nr = f(b);\nr = g(r);\n";
    let module = wasm(r#"(module (func (export "f") (param i64) (result i64) local.get 0) (func (export "g") (param i64) (result i64) local.get 0))"#);
    let callout = |name: &str, module: usize, export: &str| Callout { name: name.into(), module, export: export.into() };
    let with = |program: &str, callouts: Vec<Callout>, modules: usize| {
        let mut b = bundle(program, module.clone(), vec![]);
        b.modules = (0..modules).map(|k| Module { name: format!("m{k}"), bytes: module.clone(), priors: vec![] }).collect();
        b.callouts = callouts;
        code_of(open(&write_unchecked(&b, "stabilizer", 8).unwrap()))
    };
    assert_eq!(with(two, vec![callout("f", 0, "f"), callout("g", 0, "g")], 1), "accepted");
    assert_eq!(with(two, vec![callout("g", 0, "g"), callout("f", 0, "f")], 1), "W015", "the other order");
    assert_eq!(with(SCALAR, vec![callout("f", 0, "f"), callout("f", 0, "g")], 1), "W015", "two callouts for one extern");
    assert_eq!(with(SCALAR, vec![callout("f", 0, "f"), callout("f", 7, "anything")], 1), "W015", "a second callout nothing checks");
    assert_eq!(with(SCALAR, vec![callout("f", 0, "f")], 2), "W015", "a module no callout names");
}

#[test]
fn a_module_with_priors_exports_what_the_host_calls_to_pass_them() {
    let module = r#"(module (memory (export "memory") 1 1) (func (export "wasmq-prior") (param i32 i32 i32)) (func (export "f") (param i64) (result i64) local.get 0))"#;
    assert_eq!(code_of(pack(&bundle(SCALAR, wasm(module), vec![("p".into(), vec![1, 2, 3])]))), "W015", "priors and no cabi_realloc");
    assert_eq!(code_of(pack(&bundle(SCALAR, wasm(module), vec![]))), "accepted", "no priors");
}

#[test]
fn a_result_holds_only_members_the_text_defines() {
    let (_, done) = a_job(IDENTITY, 500);
    let r = &done["result"];
    let keys = |v: &Value| v.as_object().map(|o| o.keys().cloned().collect::<Vec<_>>()).unwrap_or_default();
    let mut k = keys(&r["modules"][0]);
    k.sort();
    assert_eq!(k, ["blake3", "name"], "a module's members");
    assert_eq!(r["accuracy"], json!({ "class": "exact" }));
    let trap = r#"(module (func (export "f") (param i64) (result i64) i64.const 256))"#;
    let (_, fault) = a_job(trap, 500);
    let mut k = keys(&fault["result"]["fault"]);
    k.sort();
    assert_eq!(fault["result"]["fault"]["reason"], "bad_result");
    assert!(!k.contains(&"detail".to_string()), "a fault's members: {k:?}");
}