sqlite-forensic 0.9.0

//! Independent-oracle differential validation of [`carve_deleted_records`].
//!
//! # Why this test exists (Doer-Checker)
//!
//! `carve.rs` validates the carver against a fixture WE generated, with a carver
//! WE wrote and assertions WE wrote — self-referential validation that can pass
//! while sharing a blind spot with the generator. This test removes that blind
//! spot by reconciling our output against an **independent reference tool** as
//! the yardstick.
//!
//! ## Two independent oracles: `undark` and `fqlite`
//!
//! - **undark** (Paul L. Daniels) — a small C SQLite deleted-record carver.
//! - **fqlite** (Dirk Pawlaszczyk) — a Java forensic SQLite recovery tool. Its
//!   command-line mode was removed at v2.0, but its carving engine
//!   (`fqlite.base.Job`) is plain Java that populates a result list the GUI
//!   merely reads. A headless source-instrumentation tap
//!   (`tools/fqlite/run-tap.sh`) drives that engine with no `JavaFX` UI and emits
//!   recovered DELETED records as CSV. So fqlite IS usable as an oracle — the CLI
//!   cancellation was the only blocker. See `tools/fqlite/ENGINE_NOTES.md`.
//!
//! Two different authors, two different languages, two different algorithms — the
//! independence an oracle requires. Where all three (ours, undark, fqlite) agree
//! on our fixture, that is the strongest evidence.
//!
//! ## Two corpora, two levels of independence
//!
//! 1. `tests/data/deleted_places.db` — OUR fixture. undark and fqlite are
//!    independent *oracles* over our input.
//! 2. `tests-oracle-corpus/dc3-sqlite-dissect/*.db` — the DC3 (Department of
//!    Defense Cyber Crime Center) `sqlite_dissect` test corpus. Authored by
//!    neither us nor the oracle authors, so neither the input DB nor the oracle
//!    is ours — the strongest form of Doer-Checker validation. These DBs exercise
//!    in-page free-block deletion and dropped-table cases our whole-freed-page
//!    fixture cannot reach, and they surface a documented carver scope boundary.
//!
//! # Gating
//!
//! Each oracle is independently gated: the undark tests skip unless `UNDARK_BIN`
//! is set; the fqlite test skips unless `FQLITE_TAP` is set — so CI without
//! either tool still passes. The DC3 corpus is gitignored; cases over it also
//! skip if the files are absent. Provenance, hashes, and the exact build recipes
//! are in `docs/validation.md`, `docs/corpus-catalog.md`, and
//! `tools/fqlite/README.md` + `ENGINE_NOTES.md`.

#![allow(clippy::unwrap_used, clippy::expect_used)]

use std::collections::BTreeMap;
use std::path::{Path, PathBuf};
use std::process::Command;

use sqlite_core::{Database, Value};
use sqlite_forensic::carve_all_deleted_records;

/// A row reduced to its forensically-comparable identity: rowid -> (url, title).
/// Both tools are compared on this projection (the `moz_places` / `users`-style
/// `url`/`name`-and-`title`/`surname` text columns at positions 1 and 2).
type RowSet = BTreeMap<i64, (String, String)>;

fn undark_bin() -> Option<PathBuf> {
    std::env::var_os("UNDARK_BIN").map(PathBuf::from)
}

fn fqlite_tap() -> Option<PathBuf> {
    std::env::var_os("FQLITE_TAP").map(PathBuf::from)
}

/// Run the headless fqlite tap on `db` and parse its CSV dump.
///
/// The tap (`tools/fqlite/run-tap.sh`) boots fqlite's recovery engine
/// (`fqlite.base.Job`) headlessly — no `JavaFX` GUI — and emits one CSV line per
/// recovered DELETED record: `rowid,col1,col2,...`. fqlite cannot always recover
/// the rowid for a carved record (emits `-1`), so we key this oracle by the two
/// text columns' content (url at field 1, title at field 2), not by rowid.
/// Returns a map keyed by url -> (rowid, url, title).
fn fqlite_recover(tap: &Path, db: &Path) -> BTreeMap<String, (i64, String, String)> {
    let out = Command::new(tap)
        .arg(db)
        .output()
        .expect("fqlite tap must execute");
    let text = String::from_utf8_lossy(&out.stdout);
    let mut set = BTreeMap::new();
    for line in text.lines() {
        if line.trim().is_empty() {
            continue;
        }
        let fields = split_csv(line);
        let rowid = fields
            .first()
            .and_then(|f| f.trim().parse::<i64>().ok())
            .unwrap_or(-1);
        let url = fields.get(1).map(|s| unquote(s)).unwrap_or_default();
        let title = fields.get(2).map(|s| unquote(s)).unwrap_or_default();
        if url.is_empty() {
            continue;
        }
        // Prefer a known rowid if the same row appears twice (freelist vs in-page).
        set.entry(url.clone())
            .and_modify(|e: &mut (i64, String, String)| {
                if e.0 == -1 && rowid != -1 {
                    e.0 = rowid;
                }
            })
            .or_insert((rowid, url, title));
    }
    set
}

/// Project our carver's output keyed by url, for the fqlite (content-keyed)
/// comparison: url -> (rowid, url, title). Uses the full-coverage carver.
fn ours_recover_by_url(db: &Database, _cols: usize) -> BTreeMap<String, (i64, String, String)> {
    let mut set = BTreeMap::new();
    for rec in carve_all_deleted_records(db) {
        let url = match rec.values.get(1) {
            Some(Value::Text(s)) => s.clone(),
            _ => String::new(),
        };
        let title = match rec.values.get(2) {
            Some(Value::Text(s)) => s.clone(),
            _ => String::new(),
        };
        if url.is_empty() {
            continue;
        }
        set.insert(url.clone(), (rec.rowid, url, title));
    }
    set
}

/// Run undark on `db` and parse its CSV dump into rowid -> (col1, col2).
///
/// undark emits one CSV line per recovered record: `rowid,id,col1,col2,...`.
/// We key by the integer rowid (field 0) and project the two text columns at
/// CSV fields 2 and 3 (the table's first two non-id text columns).
fn undark_recover(undark: &Path, db: &Path) -> RowSet {
    let out = Command::new(undark)
        .arg("-i")
        .arg(db)
        .output()
        .expect("undark must execute");
    let text = String::from_utf8_lossy(&out.stdout);
    let mut set = RowSet::new();
    for line in text.lines() {
        if line.trim().is_empty() {
            continue;
        }
        let fields = split_csv(line);
        let Some(rowid) = fields.first().and_then(|f| f.parse::<i64>().ok()) else {
            continue;
        };
        let c1 = fields.get(2).cloned().unwrap_or_default();
        let c2 = fields.get(3).cloned().unwrap_or_default();
        set.insert(rowid, (unquote(&c1), unquote(&c2)));
    }
    set
}

/// Minimal CSV field split honoring undark's `"..."` quoting (no embedded
/// escaped quotes appear in this corpus). Sufficient for the oracle projection.
fn split_csv(line: &str) -> Vec<String> {
    let mut fields = Vec::new();
    let mut cur = String::new();
    let mut in_q = false;
    for ch in line.chars() {
        match ch {
            '"' => in_q = !in_q,
            ',' if !in_q => {
                fields.push(std::mem::take(&mut cur));
            }
            _ => cur.push(ch),
        }
    }
    fields.push(cur);
    fields
}

fn unquote(s: &str) -> String {
    s.trim().trim_matches('"').to_string()
}

/// Project our carver's output to the same rowid -> (text1, text2) identity.
/// Uses the full-coverage carver so every recovery class (freelist whole-page,
/// freelist trunk body, in-page free block, dropped table) is compared.
fn ours_recover(db: &Database, _cols: usize) -> RowSet {
    let mut set = RowSet::new();
    for rec in carve_all_deleted_records(db) {
        let t1 = match rec.values.get(1) {
            Some(Value::Text(s)) => s.clone(),
            _ => String::new(),
        };
        let t2 = match rec.values.get(2) {
            Some(Value::Text(s)) => s.clone(),
            _ => String::new(),
        };
        set.insert(rec.rowid, (t1, t2));
    }
    set
}

fn corpus_db(name: &str) -> PathBuf {
    Path::new(env!("CARGO_MANIFEST_DIR"))
        .join("../tests-oracle-corpus/dc3-sqlite-dissect")
        .join(name)
}

/// OUR fixture, reconciled against the undark oracle.
///
/// Post-#49 the full-coverage carver (`carve_all_deleted_records`) carves the
/// in-page free space of allocated pages too, so it now recovers the in-page
/// remnant (rowid 237) the freelist-only path missed. The former
/// `FIXTURE_IN_PAGE_DIVERGENCES` exemption is GONE — the criterion is now exact
/// set agreement:
///   1. No false positives: every rowid we carve, undark also recovers.
///   2. Exact content agreement on every overlapping rowid (url + title).
///   3. Completeness: we recover EVERY deleted row undark recovers (no exemption).
#[test]
fn our_fixture_agrees_with_undark() {
    let Some(undark) = undark_bin() else {
        eprintln!("SKIP our_fixture_agrees_with_undark: set UNDARK_BIN to the undark binary");
        return;
    };
    let db_path = Path::new(env!("CARGO_MANIFEST_DIR")).join("../tests/data/deleted_places.db");
    let bytes = std::fs::read(&db_path).unwrap();
    let db = Database::open(bytes).unwrap();

    let ours = ours_recover(&db, 6);
    let oracle = undark_recover(&undark, &db_path);

    // The deleted ground-truth range for this fixture is ids 201..=400.
    let in_del = |k: &i64| (201..=400).contains(k);
    let oracle_deleted: RowSet = oracle
        .iter()
        .filter(|(k, _)| in_del(k))
        .map(|(k, v)| (*k, v.clone()))
        .collect();
    let ours_deleted: RowSet = ours
        .iter()
        .filter(|(k, _)| in_del(k))
        .map(|(k, v)| (*k, v.clone()))
        .collect();

    // (1) No false positives — never carve a rowid undark cannot corroborate.
    for rowid in ours_deleted.keys() {
        assert!(
            oracle_deleted.contains_key(rowid),
            "carved rowid {rowid} is not corroborated by the undark oracle (possible false positive)"
        );
    }

    // (2) Exact content agreement on every overlapping rowid.
    for (rowid, ours_val) in &ours_deleted {
        let oracle_val = &oracle_deleted[rowid];
        assert_eq!(
            ours_val, oracle_val,
            "content mismatch for rowid {rowid}: ours {ours_val:?} vs undark {oracle_val:?}"
        );
    }

    // (3) Completeness — EXACT set agreement now (the in-page exemption is gone):
    // our carver recovers every deleted row undark recovers, and vice versa.
    assert_eq!(
        ours_deleted.keys().collect::<Vec<_>>(),
        oracle_deleted.keys().collect::<Vec<_>>(),
        "ours and undark must recover the identical deleted-row set post-#49"
    );

    // The row-300 verbatim spot-check, now cross-checked against the oracle too.
    assert_eq!(
        ours_deleted.get(&300),
        Some(&(
            "https://site-300.example.com/path/page".to_string(),
            "Title for record number 300 SECRETMARKER".to_string()
        )),
        "row 300 must be recovered verbatim and agree with undark"
    );
}

/// Deleted-range urls that fqlite recovers but our carver does NOT, for a
/// documented and understood reason. Post-#49 our full-coverage carver recovers
/// the in-page remnant site-237, so only **site-235** remains: its cell *prefix*
/// (the payload-length and rowid varints) was overwritten by an adjacent record,
/// so a forward, 0-false-positive parse cannot reconstruct it. Only fqlite's
/// freeblock-geometry reconstruction (which accepts an unknown rowid) recovers
/// 235; chasing it would relax our rowid check and risk false positives. See
/// `docs/recovery-comparison.md`.
const FQLITE_IN_PAGE_DIVERGENCES: &[u32] = &[235];

/// OUR fixture, reconciled against the SECOND independent oracle: fqlite.
///
/// Post-#49 our full-coverage carver recovers the in-page remnant 237 and the
/// freelist trunk-page rows (238..=276), so we now MATCH OR EXCEED fqlite on the
/// fixture. The honest criterion:
///   1. No false positives: every deleted row we carve, fqlite also recovers
///      (content agreement on overlap). The only row we miss is the documented
///      site-235 (clobbered cell prefix — fqlite-only, see
///      `FQLITE_IN_PAGE_DIVERGENCES`).
///   2. We recover everything fqlite does except that one documented remnant —
///      i.e. ours ⊇ (fqlite ∖ {235}).
///
/// The fqlite tap is mildly non-deterministic (its result list ordering / dedup
/// varies run-to-run), so this test asserts the *direction* of the relationship
/// (we match-or-exceed) rather than an exact set, and tolerates fqlite recovering
/// fewer rows on a given run.
#[test]
fn our_fixture_agrees_with_fqlite() {
    let Some(tap) = fqlite_tap() else {
        eprintln!("SKIP our_fixture_agrees_with_fqlite: set FQLITE_TAP to tools/fqlite/run-tap.sh");
        return;
    };
    let db_path = Path::new(env!("CARGO_MANIFEST_DIR")).join("../tests/data/deleted_places.db");
    let db = Database::open(std::fs::read(&db_path).unwrap()).unwrap();

    let ours = ours_recover_by_url(&db, 6);
    let oracle = fqlite_recover(&tap, &db_path);

    // site-N id of a deleted-range url, if any.
    let site_id = |url: &str| -> Option<u32> {
        url.strip_prefix("https://site-")
            .and_then(|s| s.split('.').next())
            .and_then(|n| n.parse::<u32>().ok())
            .filter(|n| (201..=400).contains(n))
    };
    let ours_del: BTreeMap<u32, &(i64, String, String)> = ours
        .iter()
        .filter_map(|(u, v)| site_id(u).map(|n| (n, v)))
        .collect();
    let oracle_del: BTreeMap<u32, &(i64, String, String)> = oracle
        .iter()
        .filter_map(|(u, v)| site_id(u).map(|n| (n, v)))
        .collect();

    let in_page: std::collections::BTreeSet<u32> =
        FQLITE_IN_PAGE_DIVERGENCES.iter().copied().collect();

    // (1) Exact content agreement (url + title) on every overlapping row.
    for (n, ours_val) in &ours_del {
        if let Some(oracle_val) = oracle_del.get(n) {
            assert_eq!(
                (&ours_val.1, &ours_val.2),
                (&oracle_val.1, &oracle_val.2),
                "site-{n}: content mismatch ours {ours_val:?} vs fqlite {oracle_val:?}"
            );
        }
    }

    // (2) We match or exceed fqlite: every fqlite-recovered deleted row is
    // recovered by us too, except the one documented clobbered-prefix remnant
    // (235) only fqlite's freeblock reconstruction reaches.
    let mut fqlite_only: Vec<u32> = oracle_del
        .keys()
        .filter(|n| !ours_del.contains_key(n) && !in_page.contains(n))
        .copied()
        .collect();
    fqlite_only.sort_unstable();
    assert!(
        fqlite_only.is_empty(),
        "fqlite recovered deleted rows we miss with no documented reason: {fqlite_only:?}"
    );

    // (3) The 237 in-page remnant we now recover must be present (the #49 gap is
    // closed): it is no longer a fqlite-only row.
    assert!(
        ours_del.contains_key(&237),
        "post-#49 our carver must recover the in-page remnant site-237"
    );

    // Row-300 verbatim, cross-checked against fqlite when fqlite recovered it.
    if let Some(v) = oracle_del.get(&300) {
        assert_eq!(
            (&v.1, &v.2),
            (
                &"https://site-300.example.com/path/page".to_string(),
                &"Title for record number 300 SECRETMARKER".to_string()
            ),
            "row 300 content must agree with fqlite"
        );
    }
}

/// The forensic class of a DC3 corpus DB, determining the post-#49 expectation.
#[derive(Clone, Copy, PartialEq)]
enum Dc3Class {
    /// `DROP TABLE` left genuine records on a freelist page with no schema. Our
    /// inferred-column carver now recovers them — we match or exceed undark.
    DroppedTable,
    /// No genuine deleted residue: the live table is intact and packed, so undark
    /// and fqlite "recover" rows only by RE-READING the live cells. Our 0-FP
    /// carver correctly recovers ~none — undark's count here is over-reporting,
    /// not a gap on our side.
    NoGenuineDeletion,
}

/// DC3 `sqlite_dissect` corpus, reconciled against the undark oracle — post-#49.
///
/// The full-coverage carver (`carve_all_deleted_records`) now carves in-page free
/// space and dropped-table pages (inferring the column count). The corpus splits
/// into two classes (see `Dc3Class` and `docs/recovery-comparison.md`):
///
/// - **Dropped-table** (`0A-01`, `0A-02`): genuine deleted records — we now
///   recover them, matching or exceeding undark, with 0 false positives.
/// - **No-genuine-deletion** (`01-01`, `01-02`, `03-02`, `07-01`): the live table
///   is intact; undark/fqlite over-report by re-reading live cells. Our 0-FP
///   carver recovers ~none — which is CORRECT, not a gap. The test asserts we do
///   NOT replicate that over-reporting.
#[test]
fn dc3_corpus_agrees_with_undark() {
    let Some(undark) = undark_bin() else {
        eprintln!("SKIP dc3_corpus_agrees_with_undark: set UNDARK_BIN to the undark binary");
        return;
    };
    struct Case {
        name: &'static str,
        class: Dc3Class,
    }
    let cases = [
        Case {
            name: "corpus_01-01.db",
            class: Dc3Class::NoGenuineDeletion,
        },
        Case {
            name: "corpus_01-02.db",
            class: Dc3Class::NoGenuineDeletion,
        },
        Case {
            name: "corpus_03-02.db",
            class: Dc3Class::NoGenuineDeletion,
        },
        Case {
            name: "corpus_07-01.db",
            class: Dc3Class::NoGenuineDeletion,
        },
        Case {
            name: "corpus_0A-01.db",
            class: Dc3Class::DroppedTable,
        },
        Case {
            name: "corpus_0A-02.db",
            class: Dc3Class::DroppedTable,
        },
    ];

    let mut ran = 0usize;
    for case in &cases {
        let path = corpus_db(case.name);
        if !path.exists() {
            eprintln!(
                "SKIP {}: DC3 corpus DB absent (gitignored — see tests-oracle-corpus/README.md)",
                case.name
            );
            continue;
        }
        ran += 1;
        let name = case.name;
        let db = Database::open(std::fs::read(&path).unwrap()).unwrap();
        let ours = ours_recover(&db, 0);
        let oracle = undark_recover(&undark, &path);

        match case.class {
            Dc3Class::DroppedTable => {
                // We must recover the dropped rows, MATCHING OR EXCEEDING undark.
                // Compare by COUNT of distinct recovered data rows, not exact
                // strings: undark mangles non-ASCII (e.g. "Günther" -> "G..nther",
                // "Schröder" -> "Schr..der"), so an exact-string subset check
                // would wrongly flag our *correct* UTF-8 decoding. We recover at
                // least as many distinct data rows as undark, with 0 false
                // positives (no live table exists, so nothing to over-report).
                let ours_data_rows = ours.len();
                assert!(
                    ours_data_rows >= oracle.len(),
                    "{name}: dropped-table recovery must match or exceed undark \
                     (ours {ours_data_rows} vs undark {})",
                    oracle.len()
                );
            }
            Dc3Class::NoGenuineDeletion => {
                // The live table is intact; undark over-reports by re-reading live
                // rows. Our 0-FP carver must NOT do that — every record it carves
                // here would have to be genuine deleted residue. In practice it
                // recovers none, so assert that we do not over-report (ours is a
                // strict subset of undark, and small).
                assert!(
                    ours.len() < oracle.len(),
                    "{name}: we must not over-report like undark (ours {} vs undark {})",
                    ours.len(),
                    oracle.len()
                );
            }
        }
    }
    assert!(ran > 0, "no DC3 corpus DB was available to test");
}

/// How many lines a raw tool dump contains a given substring on (e.g. the
/// pre-update body marker). Used to reconcile prior-version recovery against the
/// oracles without imposing a column projection (the oracles disagree on layout).
fn tool_marker_lines(out: &str, marker: &str) -> usize {
    out.lines().filter(|l| l.contains(marker)).count()
}

/// Prior-version recovery (the false-negative → true-positive fix), reconciled
/// against undark and fqlite on `tests/data/updated_messages.db`.
///
/// Ground truth: row 7's `body` was edited (grow then shrink), leaving an
/// intermediate version `"PRIORVERSION secret …"` in slack while the live row
/// holds `"EDITED final body"`. Our value-aware carver recovers that prior
/// version (rowid 7, source `PriorVersion`) WITHOUT re-surfacing the live row.
///
/// Honest, page-diagnosed reconciliation (see `docs/recovery-comparison.md`):
///   * ours: recovers the 1 genuine prior version, 0 false positives.
///   * undark: recovers 0 from this fixture (it does not carve the freed slack
///     here) — we EXCEED it.
///   * fqlite: recovers the same genuine prior version (we MATCH it) plus two
///     records we deliberately do NOT emit: a freed `sqlite_master` schema row
///     (a different recovery class) and a truncated `"…ORIGI"` fragment (a
///     partial, clobbered recovery our 0-false-positive parser correctly
///     rejects — the full original body survives nowhere in the file).
#[test]
fn prior_version_reconciled_with_oracles() {
    let db_path = Path::new(env!("CARGO_MANIFEST_DIR")).join("../tests/data/updated_messages.db");
    let db = Database::open(std::fs::read(&db_path).unwrap()).unwrap();
    let carved = carve_all_deleted_records(&db);

    // Ours: exactly the prior version of row 7, never the live "EDITED" row.
    let prior_count = carved
        .iter()
        .filter(
            |c| matches!(c.values.get(2), Some(Value::Text(t)) if t.starts_with("PRIORVERSION")),
        )
        .count();
    assert_eq!(
        prior_count, 1,
        "ours must recover the single genuine prior version"
    );
    assert!(
        !carved
            .iter()
            .any(|c| matches!(c.values.get(2), Some(Value::Text(t)) if t.starts_with("EDITED"))),
        "ours must NOT re-surface the live (edited) row — 0 false positives"
    );

    // undark: recovers nothing here; we exceed it. (Gated; skips without the bin.)
    if let Some(undark) = undark_bin() {
        let out = Command::new(&undark)
            .arg("-i")
            .arg(&db_path)
            .output()
            .expect("undark must execute");
        let text = String::from_utf8_lossy(&out.stdout);
        assert_eq!(
            tool_marker_lines(&text, "PRIORVERSION"),
            0,
            "undark does not recover the prior version from this fixture (we exceed it)"
        );
    } else {
        eprintln!("SKIP undark leg: set UNDARK_BIN");
    }

    // fqlite: recovers the SAME genuine prior version (we match it). It also emits
    // a truncated "…ORIGI" fragment we correctly decline; assert only that the
    // genuine prior version is present in fqlite's output.
    if let Some(tap) = fqlite_tap() {
        let out = Command::new(&tap)
            .arg(&db_path)
            .output()
            .expect("fqlite tap must execute");
        let text = String::from_utf8_lossy(&out.stdout);
        assert!(
            tool_marker_lines(&text, "PRIORVERSION") >= 1,
            "fqlite must also recover the genuine prior version (we match it)"
        );
    } else {
        eprintln!("SKIP fqlite leg: set FQLITE_TAP");
    }
}

// ─────────────────────────────────────────────────────────────────────────────
// Oracle 3 — sqlite3 (the canonical SQLite reference implementation)
//
// undark and fqlite are third-party carvers. The strongest possible independent
// reference is SQLite *itself* — the engine that wrote the file. Two roles:
//
//   * LIVE read — `sqlite3 SELECT *` is ground truth for the intact b-tree. Our
//     base parser (`Database::live_rows`) must read byte-identical live rows.
//   * DELETED carve — `sqlite3 .recover` (SQLite's own corruption-recovery dot
//     command) reconstructs reachable content into a `lost_and_found` table. On
//     this fixture it recovers exactly the freelist-LEAF rows (277..=400); our
//     carver also reaches the freelist trunk-page body (238..=276), so ours is a
//     SUPERSET. The reference engine's own recovery being a subset of ours is a
//     clean third oracle.
//
// Gated on a `sqlite3` binary (PATH, or `SQLITE3_BIN`); skips if absent so CI
// without sqlite3 still passes.
// ─────────────────────────────────────────────────────────────────────────────

fn sqlite3_bin() -> Option<String> {
    let bin = std::env::var("SQLITE3_BIN").unwrap_or_else(|_| "sqlite3".to_string());
    Command::new(&bin)
        .arg("--version")
        .output()
        .ok()
        .filter(|o| o.status.success())
        .map(|_| bin)
}

/// site-N id (201..=400) of a deleted-range `moz_places` url, if any.
fn deleted_site_id(url: &str) -> Option<u32> {
    url.strip_prefix("https://site-")
        .and_then(|s| s.split('.').next())
        .and_then(|n| n.parse::<u32>().ok())
        .filter(|n| (201..=400).contains(n))
}

/// Run `sqlite3 <db> .recover`, reload the recovered SQL into an in-memory db,
/// and SELECT the recovered rows back out — letting sqlite3 parse its own dump
/// instead of hand-rolling a SQL-literal parser. `.recover` places orphaned rows
/// in `lost_and_found(rootpgno,pgno,nfield,id,c0..c5)`; for `moz_places`,
/// `c1`=url and `c2`=title. Returns site-id -> (url, title) for recovered
/// DELETED rows.
fn sqlite3_recover(bin: &str, db: &Path) -> BTreeMap<u32, (String, String)> {
    use std::io::Write;
    let mut script = Command::new(bin)
        .arg(db)
        .arg(".recover")
        .output()
        .expect("sqlite3 .recover must execute")
        .stdout;
    script.extend_from_slice(
        b"\n.mode list\n.separator |\nSELECT c1, c2 FROM lost_and_found \
          WHERE c1 LIKE 'https://site-%';\n",
    );
    let mut child = Command::new(bin)
        .arg(":memory:")
        .stdin(std::process::Stdio::piped())
        .stdout(std::process::Stdio::piped())
        .stderr(std::process::Stdio::null())
        .spawn()
        .expect("sqlite3 :memory: must spawn");
    child
        .stdin
        .take()
        .unwrap()
        .write_all(&script)
        .expect("write recovered SQL to sqlite3 stdin");
    let out = child
        .wait_with_output()
        .expect("sqlite3 :memory: must finish");
    let text = String::from_utf8_lossy(&out.stdout);
    let mut set = BTreeMap::new();
    for line in text.lines() {
        let mut it = line.splitn(2, '|');
        let (Some(url), Some(title)) = (it.next(), it.next()) else {
            continue;
        };
        if let Some(n) = deleted_site_id(url) {
            set.insert(n, (url.to_string(), title.to_string()));
        }
    }
    set
}

/// LIVE-read parity: our base parser must read exactly the rows `sqlite3
/// SELECT *` reads from the intact b-tree (id, url, title), with no deleted-row
/// leakage. Validates the foundation the carving sits on against the engine that
/// wrote the file.
#[test]
fn live_read_matches_sqlite3() {
    let Some(bin) = sqlite3_bin() else {
        eprintln!("SKIP live_read_matches_sqlite3: no sqlite3 on PATH (set SQLITE3_BIN)");
        return;
    };
    let db_path = Path::new(env!("CARGO_MANIFEST_DIR")).join("../tests/data/deleted_places.db");
    let db = Database::open(std::fs::read(&db_path).unwrap()).unwrap();

    // Ours: id -> (url, title) from the live b-tree.
    let ours: BTreeMap<i64, (String, String)> = db
        .live_rows()
        .into_iter()
        .map(|(id, vals)| {
            let txt = |i: usize| match vals.get(i) {
                Some(Value::Text(s)) => s.clone(),
                _ => String::new(),
            };
            (id, (txt(1), txt(2)))
        })
        .collect();

    // sqlite3 reference: SELECT id, url, title FROM moz_places.
    let out = Command::new(&bin)
        .arg(&db_path)
        .arg("-cmd")
        .arg(".mode list")
        .arg("-cmd")
        .arg(".separator |")
        .arg("SELECT id, url, title FROM moz_places;")
        .output()
        .expect("sqlite3 SELECT must execute");
    let text = String::from_utf8_lossy(&out.stdout);
    let theirs: BTreeMap<i64, (String, String)> = text
        .lines()
        .filter_map(|l| {
            let f: Vec<&str> = l.splitn(3, '|').collect();
            if f.len() < 3 {
                return None;
            }
            f[0].parse::<i64>()
                .ok()
                .map(|id| (id, (f[1].to_string(), f[2].to_string())))
        })
        .collect();

    assert!(!theirs.is_empty(), "sqlite3 returned no live rows");
    assert_eq!(
        ours, theirs,
        "live-read parity: our base parser disagrees with sqlite3 SELECT"
    );
    // Ground-truth sanity: exactly the 200 live rows, no deleted leakage.
    assert_eq!(ours.len(), 200, "expected 200 live rows (ids 1..=200)");
    assert!(
        ours.keys().all(|&id| (1..=200).contains(&id)),
        "live set must be ids 1..=200 with no deleted-row leakage"
    );
}

/// OUR fixture, reconciled against the THIRD independent oracle: sqlite3's own
/// `.recover`. The reference engine recovers the freelist-LEAF rows (277..=400)
/// into `lost_and_found`; our carver also reaches the freelist trunk-page body
/// (238..=276), so ours ⊇ sqlite3 `.recover`. Honest criteria:
///   1. Content agreement (title) on every overlapping row.
///   2. ours ⊇ `.recover` — every deleted row the canonical engine recovers, we
///      recover too (no `.recover`-only row). The load-bearing claim.
#[test]
fn our_fixture_agrees_with_sqlite3_recover() {
    let Some(bin) = sqlite3_bin() else {
        eprintln!("SKIP our_fixture_agrees_with_sqlite3_recover: no sqlite3 on PATH");
        return;
    };
    let db_path = Path::new(env!("CARGO_MANIFEST_DIR")).join("../tests/data/deleted_places.db");
    let db = Database::open(std::fs::read(&db_path).unwrap()).unwrap();

    let ours = ours_recover_by_url(&db, 6);
    let ours_del: BTreeMap<u32, &(i64, String, String)> = ours
        .iter()
        .filter_map(|(u, v)| deleted_site_id(u).map(|n| (n, v)))
        .collect();
    let oracle = sqlite3_recover(&bin, &db_path);

    // `.recover`'s freelist-page handling is build-dependent: some sqlite3 builds
    // (e.g. the ones on CI runners) surface no freelist-leaf rows at all. With no
    // oracle baseline the two checks below are vacuous, so skip rather than fail —
    // our carver's recall is asserted against the Nemetz/undark/fqlite oracles.
    if oracle.is_empty() {
        eprintln!(
            "SKIP our_fixture_agrees_with_sqlite3_recover: this sqlite3 build's .recover \
             surfaced no freelist-leaf rows (no oracle baseline to diff)"
        );
        return;
    }

    // (1) Content agreement (title) on every overlapping row.
    for (n, (_url, title)) in &oracle {
        if let Some(ours_val) = ours_del.get(n) {
            assert_eq!(
                &ours_val.2, title,
                "site-{n}: title mismatch ours {:?} vs sqlite3 .recover {:?}",
                ours_val.2, title
            );
        }
    }

    // (2) ours ⊇ sqlite3 .recover: no row the reference engine recovers that we miss.
    let mut recover_only: Vec<u32> = oracle
        .keys()
        .filter(|n| !ours_del.contains_key(n))
        .copied()
        .collect();
    recover_only.sort_unstable();
    assert!(
        recover_only.is_empty(),
        "sqlite3 .recover recovered deleted rows we miss: {recover_only:?}"
    );

    // (3) Sanity: .recover surfaces only deleted rows (201..=400), no live leakage.
    assert!(
        oracle.keys().all(|&n| (201..=400).contains(&n)),
        ".recover oracle set must contain only deleted ids"
    );
}