//! Exhaustive verification of [`coprime::number::is_prime`] over the entire `u64`
//! range, via Feitsma's base-2 pseudoprime database.
//!
//! A composite `n < 2^64` can fool the twelve-base Miller–Rabin test only if it
//! is a strong pseudoprime to base 2 — and every base-2 strong pseudoprime below
//! `2^64` is a base-2 *Fermat* pseudoprime, all of which Jan Feitsma enumerated
//! (2009; hosted at `cecm.sfu.ca`). So running `is_prime` over that complete list
//! and confirming none is called prime turns the deterministic-MR guarantee from
//! a cited theorem (Sorenson–Webster 2017: the smallest strong pseudoprime to the
//! first twelve primes is `ψ₁₂ = 318665857834031151167461 ≈ 3.19e23`, far past
//! `u64::MAX`) into an exhaustive, independently-checked fact.
//!
//! This is a heavy, on-demand tier — it needs the ~884 MB database and a few
//! minutes — so it is `#[ignore]`d. Drive it with `scripts/feitsma-verify.sh`, or:
//!
//! ```text
//! COPRIME_FEITSMA_PSPS=/path/to/psps-below-2-to-64.txt.bz2 \
//!   cargo test --release -p coprime --test feitsma_exhaustive -- --ignored --nocapture
//! ```
//!
//! The path may be the `.bz2` (streamed through `bzcat`, no 2.35 GB on disk) or a
//! decompressed plain file (one decimal integer per line).

use std::io::{BufRead, BufReader};
use std::process::{Command, Stdio};

/// Feitsma's counts below `2^64`, quoted verbatim from Baillie–Fiori–Wagstaff,
/// "Strengthening the Baillie–PSW Primality Test": of the `118_968_378` base-2
/// Fermat pseudoprimes, exactly `31_894_014` are base-2 *strong* pseudoprimes.
const FERMAT_PSP2_COUNT: u64 = 118_968_378;
const STRONG_PSP2_COUNT: u64 = 31_894_014;

#[test]
#[ignore = "needs the ~884MB Feitsma DB; set COPRIME_FEITSMA_PSPS (see scripts/feitsma-verify.sh)"]
fn is_prime_has_no_false_positive_below_2_to_64() {
    let path = std::env::var("COPRIME_FEITSMA_PSPS")
        .expect("set COPRIME_FEITSMA_PSPS to the Feitsma psps-below-2-to-64 file (.bz2 or plain)");

    // Stream the .bz2 through bzcat (no 2.35 GB on disk), or read a plain file.
    let is_bz2 = std::path::Path::new(&path)
        .extension()
        .is_some_and(|e| e.eq_ignore_ascii_case("bz2"));
    let mut bzcat: Option<std::process::Child> = None;
    let reader: Box<dyn BufRead> = if is_bz2 {
        let mut child = Command::new("bzcat")
            .arg(&path)
            .stdout(Stdio::piped())
            .spawn()
            .expect("spawn bzcat (install bzip2) to stream the .bz2");
        let out = child.stdout.take().expect("bzcat stdout");
        bzcat = Some(child);
        Box::new(BufReader::new(out))
    } else {
        Box::new(BufReader::new(
            std::fs::File::open(&path).expect("open psps file"),
        ))
    };

    let mut total: u64 = 0;
    let mut strong_psp2: u64 = 0;
    for line in reader.lines() {
        let line = line.expect("read line");
        let s = line.trim();
        if s.is_empty() {
            continue;
        }
        let n: u64 = s.parse().expect("parse u64");

        // The exhaustive claim: every base-2 (Fermat) pseudoprime < 2^64 is
        // composite, so is_prime MUST reject it. A single `true` here would be a
        // u64 composite that fools the twelve-base test — a primality bug.
        assert!(
            !coprime::number::is_prime(n),
            "FALSE POSITIVE: is_prime({n}) == true, but {n} is a base-2 pseudoprime (composite)"
        );

        // Bonus cross-check: of the Fermat psp-2, exactly the strong ones pass
        // is_strong_probable_prime(n, 2). Counting them re-derives the literature
        // figure and exercises the single-round test on 118.9M real inputs.
        if coprime::number::is_strong_probable_prime(n, 2) {
            strong_psp2 += 1;
        }
        total += 1;
        if total.is_multiple_of(10_000_000) {
            eprintln!("  {total} / {FERMAT_PSP2_COUNT} checked ({strong_psp2} strong so far)");
        }
    }

    if let Some(mut child) = bzcat {
        let status = child.wait().expect("wait on bzcat");
        assert!(status.success(), "bzcat exited with failure: {status}");
    }

    assert_eq!(
        total, FERMAT_PSP2_COUNT,
        "database line count mismatch — incomplete or corrupt file?"
    );
    assert_eq!(
        strong_psp2, STRONG_PSP2_COUNT,
        "base-2 strong pseudoprime count disagrees with the literature"
    );
    eprintln!(
        "OK: {total} base-2 pseudoprimes < 2^64, every one rejected by is_prime; \
         {strong_psp2} strong (matches literature). is_prime is exhaustively verified over u64."
    );
}
