stuffr-core 0.10.4

//! The salvage engine: format-agnostic scanning, bounding and collection.
//!
//! Salvage recovers entries from a damaged archive by scanning for records
//! directly, rather than trusting a single index (a central directory, an
//! EOCD) that may be truncated, zeroed, or — the motivating case — may
//! shadow real records behind a repeated name. The per-format part of that
//! (recognising a local header, computing a checksum) is a
//! [`SalvageScan`] implementation; this module is everything that does not
//! need to know which format it is scanning.
//!
//! **This module implements no per-format scanning at all.** It is proven
//! entirely against mocks — [`SalvageScan`] is the seam Task 2 onward builds
//! real scanners against (starting with zip).
//!
//! ## Verification and shadowing (Task 4)
//!
//! Two things this module now does, both format-agnostic:
//!
//! - **Deciding [`SalvageStatus`]** is delegated to [`SalvageScan::verify`],
//!   called once per candidate in [`annotate_candidates`]. The default
//!   answers [`SalvageStatus::Unattested`] — "nothing attests that this
//!   candidate is an entry at all" — which is the honest reading of a method
//!   that reads nothing, and the right answer for a mock with no
//!   [`Candidate::verifier`] and for a real format with neither a checksum
//!   nor a self-verifying header (cpio, ar). A format with a self-verifying
//!   header and no content checksum (tar) overrides it to answer
//!   [`SalvageStatus::Complete`]. A format that carries a content checksum
//!   (zip's CRC-32) overrides `verify` to
//!   decode the payload and compare it, answering `Intact` on agreement and
//!   `Partial` otherwise — never `Complete`, which is reserved for "no way
//!   to prove", not "tried and it disagreed". Earlier revisions of this
//!   module recorded every candidate as `Complete` unconditionally; that was
//!   a placeholder, not a claim about zip, and it was wrong for every zip
//!   entry the moment a real scanner carried a CRC-32.
//! - **Detecting a shadowed record** (setting [`SalvagedEntry::shadows`]) is
//!   generic too: [`annotate_candidates`] remembers the first candidate to
//!   report each distinct `(name, declared_len, verifier)` triple and marks
//!   any LATER candidate reporting the identical triple as shadowing it.
//!   This is a MEASUREMENT, never an inference from [`EntryMeta::name`]
//!   alone repeating: two different files that happen to share a name must
//!   not be linked this way, only two records whose original writer
//!   computed the same checksum, over the same declared length, under the
//!   same name. The checksum alone is not enough either — fixed after this
//!   module's own fix-round review measured it against real archives: every
//!   empty file and every directory entry in a zip has `Crc32(0)` — a
//!   structural certainty for a zero-byte payload, not a collision — so a
//!   checksum-only match reported an ordinary Python package's dozen
//!   `__init__.py` files, and its directories, as duplicates of one another.
//!   The degenerate case is refused outright rather than papered over by the
//!   wider conjunction: a candidate with `declared_len == Some(0)` never
//!   shadows and is never shadowed, because a checksum over zero bytes is
//!   the same value for every empty entry that ever existed and proves
//!   nothing about any of them being copies of each other.
//! - **Detecting a repeated NAME** ([`SalvagedEntry::collides_with`]) is a
//!   second, deliberately separate annotation, added after the final
//!   whole-branch review found the word "shadow" doing two jobs. The two
//!   facts are different and both worth printing: a shadow is a record
//!   MEASURED to be a copy of an earlier one, a collision is a record whose
//!   name an earlier one already used and whose content this scan could not
//!   prove identical. `stuffr list`'s own `Fidelity::EntryCountMismatch`
//!   warning is about the second, so on an archive whose duplicates differ,
//!   `list` reported two records shadowed while `salvage --list` marked
//!   none — one tool telling a user two contradictory things about the same
//!   eight records. None of the guards on shadow detection above apply to a
//!   collision, and applying them would be wrong: they exist because
//!   claiming two records are COPIES needs proof, and a collision claims
//!   nothing about content at all. The two are mutually exclusive — a
//!   proven copy is reported as a shadow and nothing else, since that is
//!   the strictly more informative claim.
//!
//! [`collect_candidates`] (the resync loop: find a candidate, advance) and
//! [`annotate_candidates`] (bound + verify + shadow, above) are both
//! exposed separately from [`salvage_all`] — which is just the two of them
//! run in sequence — so a format that reconciles more than one candidate
//! source (zip's central-directory fallback, `zip_salvage.rs`) can collect
//! from each source, merge, and annotate the merged list exactly once
//! rather than annotating twice and reconciling two already-decided
//! outcomes. The run's ceiling on a single entry is applied once, in
//! `annotate_candidates`, to whatever the merge produced — see
//! [`UnverifiedCause::OverEntryCeiling`] for why it is a status there
//! rather than a [`crate::Error`] anywhere.

use std::collections::HashMap;
use std::io::{self, Read, SeekFrom, Write};
use std::path::Path;

use crate::archive::EntryMeta;
use crate::error::{Error, Result};
use crate::format::FormatId;
use crate::source::SeekRead;

/// 4 GiB. A scanned length is untrustworthy TWICE over — attacker-controlled
/// AND possibly corrupt — so this is a structural ceiling, not a budget.
///
/// Applied per ENTRY, never to the run: an entry over it is reported
/// [`UnverifiedCause::OverEntryCeiling`] and skipped, and the rest of the
/// archive is recovered as usual. It used to abort the run outright, which
/// meant one absurd declaration cost every entry around it.
pub const MAX_SALVAGE_ENTRY: u64 = 4 * 1024 * 1024 * 1024;

/// What a format can prove about a candidate it found.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum Verifier {
    /// CRC-32, as zip, arj and gzip compute it.
    Crc32(u32),
    /// CRC-16/ARC, as lha, arc and zoo compute it.
    Crc16(u16),
}

/// A record a scanner believes it found, before anything is decoded.
///
/// # Why this is `#[non_exhaustive]` AND has a constructor
///
/// Ruling S-I, deferred from Salvage Stage 2 Task 1 to Task 9 on purpose:
/// this struct is the one shape [`SalvageScan::next_candidate`] *forces* an
/// external implementor to build, so every field added to it used to break
/// every out-of-crate scanner at once — and at `0.5.0` all four crates are
/// published, so "out-of-crate" is not hypothetical. The attribute alone
/// would have been the wrong fix (`CONTRIBUTING.md`'s `#[non_exhaustive]`
/// section says why: it forbids `..` construction from another crate, which
/// is exactly what an implementor must do), which is why it waited for
/// [`Candidate::new`] — and for all five in-tree scanners to exist, so the
/// constructor's shape could be read off real callers rather than guessed.
///
/// The three arguments [`Candidate::new`] takes are the three facts every
/// scanner knows the instant it recognises a record. The four `with_*`
/// setters cover the rest, each taking the field's own type unchanged so
/// nothing is hidden behind a conversion.
#[derive(Debug)]
#[non_exhaustive]
pub struct Candidate {
    /// Byte offset of the record's header in the archive.
    pub offset: u64,
    /// Byte offset where this record's PAYLOAD begins — past whatever
    /// fixed and variable-length header fields this format's record
    /// carries (a zip local header's name/extra fields, ARC's fixed
    /// 28-byte record, and so on).
    ///
    /// Task 3c added this field after `entries.rs`'s write path hardcoded
    /// a ZIP local header's own 30-byte-plus-name-plus-extra layout as
    /// the way to locate every format's payload — which crashed
    /// (`Error::Io`, exit 1, the wildcard this project treats as a
    /// defect) the moment a non-zip scanner (ARC) reported a candidate
    /// near the end of the file, because reading 30 bytes from ITS offset
    /// ran past EOF. Each scanner already computes this value once, at
    /// discovery, to know where ITS OWN payload begins — this field
    /// carries that computation forward instead of a consumer re-deriving
    /// (and mis-deriving) it later. A future scanner (zoo, lha, arj) fills
    /// this the same way; nothing outside the scanner that discovered a
    /// candidate needs to know its record's own layout at all.
    pub payload_start: u64,
    pub meta: EntryMeta,
    /// Declared payload length. `None` when the header does not carry one.
    pub declared_len: Option<u64>,
    /// The checksum the ORIGINAL writer computed, when the format has one.
    /// `None` is what produces the intact/complete split honestly, rather
    /// than by a per-format convention someone has to remember.
    pub verifier: Option<Verifier>,
    /// How many of `declared_len`'s bytes the SOURCE actually holds, when
    /// it holds fewer — the truncated-tail case. `None` means the declared
    /// payload is entirely present (the ordinary case) or nothing was
    /// declared at all; `Some(n)` always means `n < declared_len`.
    ///
    /// # Why a scanner reports this instead of dropping the candidate
    ///
    /// A truncated archive — an interrupted download — is the single most
    /// common damaged zip there is, and it was the one shape salvage said
    /// nothing at all about. `zip_salvage.rs`'s validation gate refused any
    /// candidate whose declared payload ran past the end of the file, which
    /// is a correct refusal to INVENT the missing bytes (`zip -FF`
    /// fabricates them and reports success) implemented as SILENCE: no row,
    /// no note, no non-zero exit. Swept across six truncation points inside
    /// a three-header archive's last entry, every one reported "2 scanned"
    /// at exit 0 — the third header was not even counted.
    ///
    /// Reporting the candidate with this field set is what turns the
    /// refusal into a statement. Nothing is invented: the declared length
    /// stays exactly what the header said, so a reader can see both figures,
    /// and the bytes that ARE present are still a genuine prefix. What a
    /// scanner must NOT do is fold the shortfall into `declared_len` — that
    /// would make a truncated entry indistinguishable from a whole one of
    /// the smaller size, which is the same mistake in a different place.
    pub available_len: Option<u64>,
    /// The archive's own record marks this entry DELETED — the format's
    /// owner removed it and the writer left the record, and its payload,
    /// in place.
    ///
    /// `false` for every format that has no such flag (zip, tar, ar, cpio,
    /// arc), which is why it is a plain `bool` rather than an `Option`:
    /// "this format cannot express deletion" and "this record is not
    /// deleted" lead to the identical, unannotated row, and a third state
    /// would be a distinction no consumer could act on.
    ///
    /// # Why a scanner reports one rather than dropping it (Ruling S-R)
    ///
    /// Salvage Stage 2 Task 4, for ZOO — the first format here with the
    /// flag. `zoo d` marks an entry `deleted = 1` and leaves it whole in the
    /// file; `zoolist.c` neither lists nor extracts it, and `legacy::zoo`'s
    /// reader follows that exactly. The flag is ONE BYTE, so in a damaged
    /// archive a bit flip turns a live entry into one no ordinary verb will
    /// ever hand back — which is precisely the archive this verb exists for.
    /// So the scanner reports it.
    ///
    /// **And the report carries a marker, which is the part that took a
    /// review to get right.** Everywhere else salvage accepts less than an
    /// ordinary entry it says so on the artifact or in the row: a `Partial`
    /// lands as `NAME.partial` and never under its real name, a second
    /// record under a taken name lands as `NAME.salvaged-N`, a proven copy
    /// prints `[shadowed]`. A deleted record reported `Intact` under its
    /// real name at exit 0 was the one place that leniency was invisible —
    /// four verbs call the archive empty and the fifth writes the file, with
    /// nothing telling a user which it was.
    ///
    /// **The exit code deliberately does NOT move.** Recovering a deleted
    /// record is this verb working as designed, not degraded fidelity — see
    /// `stuffr::entries`'s own exit-code aggregation, which this field is
    /// invisible to.
    pub marked_deleted: bool,
}

impl Candidate {
    /// A candidate at `offset`, whose payload begins at `payload_start`,
    /// carrying `meta`.
    ///
    /// Nothing else is claimed. The four fields this does not take default
    /// to the answers that assert the least:
    ///
    /// * `declared_len: None` — the header carries no length, so nothing
    ///   bounds the payload and [`annotate_candidates`] reports
    ///   [`UnverifiedCause::NoDeclaredLength`] rather than reading it.
    /// * `verifier: None` — the format offers nothing to prove the content
    ///   with, so no shadow is ever claimed for this record (see
    ///   [`SalvagedEntry::shadows`], which needs a verifier to compare).
    /// * `available_len: None` — every declared byte is present, which is
    ///   the ordinary case; a scanner sets this only when it has MEASURED a
    ///   shortfall.
    /// * `marked_deleted: false` — the format has no deleted flag, or this
    ///   record is not marked. Four of the five in-tree scanners leave it.
    ///
    /// One default is worth naming because it decides a STATUS, not just a
    /// field: with no `verifier`, [`SalvageScan::verify`]'s own default
    /// answers [`SalvageStatus::Unattested`] — the tier that asserts the
    /// least, matching the discipline of the four above. It answered
    /// [`SalvageStatus::Complete`] until Salvage Stage 3, which was the
    /// lenient direction: `Complete` claims a header self-check the default
    /// never performs, and routes to exit 0. A scanner carrying a checksum
    /// has to write its own `verify` regardless (the default checks
    /// nothing), and that `verify` reads this very field, so the omission
    /// fails in the scanner's own first test rather than silently.
    pub fn new(offset: u64, payload_start: u64, meta: EntryMeta) -> Self {
        Self {
            offset,
            payload_start,
            meta,
            declared_len: None,
            verifier: None,
            available_len: None,
            marked_deleted: false,
        }
    }

    /// Sets [`Self::declared_len`].
    #[must_use]
    pub fn with_declared_len(mut self, declared_len: Option<u64>) -> Self {
        self.declared_len = declared_len;
        self
    }

    /// Sets [`Self::verifier`].
    #[must_use]
    pub fn with_verifier(mut self, verifier: Option<Verifier>) -> Self {
        self.verifier = verifier;
        self
    }

    /// Sets [`Self::available_len`] — the truncated-tail case, and only
    /// when the shortfall was measured. See that field's doc for why a
    /// scanner must never fold it into [`Self::declared_len`] instead.
    #[must_use]
    pub fn with_available_len(mut self, available_len: Option<u64>) -> Self {
        self.available_len = available_len;
        self
    }

    /// Sets [`Self::marked_deleted`] — Ruling S-R. See that field's doc.
    #[must_use]
    pub fn with_marked_deleted(mut self, marked_deleted: bool) -> Self {
        self.marked_deleted = marked_deleted;
        self
    }
}

/// Why an entry is [`SalvageStatus::Unverified`].
///
/// Three causes, and the STATUS does not distinguish them because the
/// decision they lead to is identical (listed, not written, exit 3) — the
/// same split [`crate::salvage`]'s consumers apply to
/// [`SalvageStatus::Partial`] via their own cause type (`entries.rs`'s
/// `PartialCause`, one crate up): **a tier carries a decision, a message
/// carries a cause.**
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum UnverifiedCause {
    /// This build recognises the entry's compression method but cannot
    /// decode it (zip method 99 is AES, 14 is LZMA — recognised, not
    /// decoded).
    UndecodableMethod,
    /// No length was available to bound the payload, so it was never read —
    /// a data-descriptor entry the raw scan found with no central-directory
    /// record to reconcile against. A CD-reconciled data-descriptor entry
    /// gets a real declared length and CRC from the central directory and
    /// does NOT reach this cause; see `zip_salvage.rs`'s
    /// `candidate_from_cd_record`.
    NoDeclaredLength,
    /// The bytes this entry would have required are past the ceiling this
    /// run will read for ONE entry — `policy.max_entry` narrowed by the
    /// scanner's own [`SalvageScan::max_whole_entry`] — so nothing was read
    /// and nothing was decoded. See [`annotate_candidates`], which is the
    /// one place that decides this, for the whole rule.
    ///
    /// # Why this is a cause and not an `Err`
    ///
    /// Salvage Stage 2 Task 3c's fix round 3. This refusal used to be an
    /// [`crate::Error::ResourceLimit`] raised from two different places — the
    /// engine's own [`collect_candidates`], and (for ARC) the scanner's own
    /// `verify` — and an `Err` at either site **aborts the whole run**:
    /// measured at the CLI on a two-entry archive whose second entry was
    /// over the ceiling, `stuffr salvage --list` printed no rows at all and
    /// exited 6, and `salvage -C out` left the destination empty, losing a
    /// first entry that decodes perfectly. That is the one thing this verb
    /// exists not to do. Three fix rounds chased the shape from site to
    /// site; what actually closes it is that an over-ceiling entry has a
    /// STATUS, so there is no `Err` left to propagate.
    ///
    /// Distinct from [`SalvageStatus::Partial`], which is what this used to
    /// collapse into once the `Err` was folded away at the write layer: a
    /// truncated entry's genuine prefix IS recovered (as `NAME.partial`),
    /// while an over-ceiling entry has real bytes nobody read. Reporting it
    /// as `Partial (truncated)` stated two false things — the entry is not
    /// truncated, and the empty `NAME.partial` it produced said nothing
    /// survived.
    ///
    /// # Why it carries both figures (fix round 4, NEW-F)
    ///
    /// The `Err` this replaced carried a sentence naming the declared size
    /// and the ceiling; the first version of this variant was a unit, so a
    /// user meeting a container's own fixed ceiling was told neither number
    /// and could not tell whether `--max-entry` would help. The cause is
    /// the only place that knows both, so it carries both and the CLI row
    /// prints them — the project's own "a message carries a cause", with
    /// the numbers that make the message actionable.
    OverEntryCeiling {
        /// Bytes reading this entry would have required: the BOUNDED
        /// figure the comparison actually used — `available_len` when the
        /// payload is truncated, the header's `declared_len` otherwise —
        /// never the raw declaration when the file holds less than it.
        needed: u64,
        /// The ceiling in force for this run: [`SalvagePolicy::max_entry`]
        /// narrowed by [`SalvageScan::max_whole_entry`]. Equal to
        /// `max_entry` means `--max-entry` can raise it; below it means a
        /// whole-decoding container's own fixed ceiling decided, and no
        /// flag moves that.
        ceiling: u64,
    },
}

/// What was proven about an entry AFTER decoding it.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum SalvageStatus {
    /// A checksum the original writer computed agrees.
    Intact,
    /// Every declared byte was present and the header self-verified, but the
    /// format offers NO CHECKSUM AT ALL to prove the content — `tar`, in
    /// this project's own formats. Never the right answer for a format that
    /// DOES carry one; see [`SalvageStatus::Unverified`] for that case,
    /// which this status is not permitted to stand in for.
    ///
    /// # `cpio` and `ar` are NOT this tier, and were named here until Stage 3
    ///
    /// This doc said "tar, cpio and ar" from Stage 1 until Salvage Stage 3,
    /// which is where the sentence's own *"and the header self-verified"*
    /// clause was measured against the three formats it named. `tar` has a
    /// header checksum and really does self-verify. **`cpio` and `ar` have
    /// neither a content checksum nor a self-verifying header**, so for
    /// those two the clause is not merely unproven — there is nothing in the
    /// format it could ever be true of, and a scanner answering `Complete`
    /// for one would be asserting a header self-check that does not exist.
    /// They are [`SalvageStatus::Unattested`].
    ///
    /// `stuffr_core::testing::check_salvage_claim` is what holds the line: this
    /// tier requires a format whose only checksum covers the HEADER
    /// (`Attestation::HeaderChecksumOnly`) AND that checksum to have been
    /// checked — so the checksumless pair cannot reach it, and neither can a
    /// format with a content checksum, whose honest tiers are `Intact`,
    /// `Partial` and `Unverified`.
    Complete,
    /// Nothing attests that this candidate is an entry AT ALL: the format
    /// carries **no checksum and no self-verifying header**, so a
    /// coincidental header match and a real entry are indistinguishable in
    /// the bytes — `cpio` and `ar`, in this project's own formats.
    ///
    /// The entry is still WRITTEN, under its real name: `salvage` is the
    /// recovery-biased verb, and a tier that refused to write would make
    /// these two formats unsalvageable rather than honestly salvaged. What
    /// the tier buys is that the run says so — `salvage_exit_code` answers
    /// **4** for it (degraded fidelity, never 3: nothing was refused and no
    /// capability was missing), and the `--list` row carries the reason
    /// beside the entry. There is no flag to opt into or out of this; the
    /// formats' own shape decides it.
    ///
    /// # Not [`Self::Unverified`] — and the near-miss name is the hazard
    ///
    /// The variant deliberately is NOT called `Unverifiable`: that is two
    /// letters from the [`Self::Unverified`] this enum already has, in an
    /// enum whose variants select exit codes, and a reviewer skimming match
    /// arms would not reliably see the difference. The distinction, stated
    /// wherever both appear:
    ///
    /// * [`Self::Unverified`] — the format *has* a checksum; this build
    ///   could not use it (an undecodable method), or the header declared
    ///   nothing to check.
    /// * `Unattested` — the format has **no checksum and no self-verifying
    ///   header**, so nothing attests that this candidate is an entry at
    ///   all.
    ///
    /// The consequences differ as much as the claims do: `Unverified` is
    /// NOT written and exits 3 (this build could not do it — a rebuild may
    /// fix it), `Unattested` IS written and exits 4 (nothing can fix it;
    /// the format carries no evidence to find).
    Unattested,
    /// Nothing about this entry's content was verified.
    ///
    /// Two causes ([`UnverifiedCause`]), and the tier does not distinguish
    /// them because the decision is identical — the entry is listed, not
    /// written, and the run exits 3:
    ///   * this build could not decode the method (zip 99 is AES, 14 is
    ///     LZMA);
    ///   * no length was available to bound the payload, so it was never
    ///     read (a data-descriptor entry the raw scan found with no
    ///     central-directory record to reconcile against).
    ///
    /// Distinct from [`Self::Complete`], which asserts every DECLARED byte
    /// was present — a claim that requires something to have been declared
    /// in the first place. Reporting `Complete` for either cause above was
    /// this enum's third instance of "nothing to disprove" being read as
    /// "proven" (after the Task 1 hardcoded placeholder and the Task 4
    /// undecodable-method case this variant was originally added for) — the
    /// exit-code table this status exists to keep honest reserves exit 3 for
    /// both causes, never exit 0, which is what `Complete` would have routed
    /// either one to.
    Unverified(UnverifiedCause),
    /// The payload ran out, the decoder failed mid-stream, or the content
    /// decoded whole and disagreed with the checksum the original writer
    /// computed. All three are the same fact from a caller's perspective —
    /// this build could not confirm the content is what was written — and
    /// none of them is `Complete` (something WAS checked) or `Intact` (it
    /// did not agree, or never finished).
    Partial,
}

/// Which class of evidence a FORMAT offers for one of its entries — a
/// per-format constant, and the third argument to the honesty oracle
/// `stuffr_core::testing::check_salvage_claim`.
///
/// **Always compiled, unlike the oracle**, since Salvage Stage 3 Task 5:
/// `stuffr formats`' SALVAGE column renders it (`yes` only for
/// [`Attestation::ContentChecksum`]), so it cannot live behind the
/// `testing` feature with the oracle that consumes it. Which format has
/// which class is stated once, beside the scanner dispatch
/// (`stuffr::entries::salvage_attestation`); the fuzz target and the corpus
/// generator read it from there rather than keeping a table of their own.
///
/// **Three classes, which is why this is an enum and not a `bool`.** Salvage
/// Stage 3 Task 1 first shipped the argument as `format_offers_verifier:
/// bool`, and its fix round's review showed with a truth table that no
/// reading of a two-valued flag can hold the boundary: read as "a content
/// checksum", it let `cpio` claim [`SalvageStatus::Complete`]; read as "a
/// content checksum OR a self-verifying header" (the shipped reading), it
/// let `tar` claim [`SalvageStatus::Intact`] and — live against the five
/// scanners that shipped before this stage — let `zip`, `arc`, `zoo`, `lha`
/// or `arj` answer `Complete` for an entry whose CRC was compared and
/// DISAGREED, turning an exit-4 `Partial` into an exit-0 clean recovery.
/// Both false claims sat in the one cell (`checked`, `offers`) that tar's
/// honest `Complete` also occupies, so no function of those inputs could
/// refuse them and permit it. Ruling 3-G.
///
/// Two bools (`offers_content_checksum`, `header_self_verifies`) were
/// considered and refused: four states for three classes, one of them
/// meaningless, and the split pushed back onto every caller. Here each
/// scanner NAMES its class.
///
/// **Deliberately NOT `#[non_exhaustive]`**, for the reason Ruling 3-D kept
/// it off [`SalvageStatus`]: a fourth class of evidence must fail to compile
/// at every `match`, `check_salvage_claim`'s own included, rather than be
/// absorbed by a wildcard arm that decides what it permits by accident.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Attestation {
    /// A checksum over the entry's CONTENT, computed by the original writer —
    /// `zip`, `arc`, `zoo`, `lha`, `arj`. The only class that can earn
    /// [`SalvageStatus::Intact`].
    ContentChecksum,
    /// A checksum over the HEADER only; the content has none — `tar`. The
    /// only class that can earn [`SalvageStatus::Complete`]: "every declared
    /// byte was present and the header self-verified" is exactly what this
    /// class can prove and all it can prove.
    HeaderChecksumOnly,
    /// Neither — `cpio`, `ar`. A coincidental header match and a real entry
    /// are indistinguishable in the bytes, so the only honest tier this
    /// class can reach on a whole entry is [`SalvageStatus::Unattested`].
    Nothing,
}

/// One entry the scan recovered.
///
/// `#[non_exhaustive]` plus [`SalvagedEntry::new`], for the same reason
/// [`Candidate`] carries both — see that type's own doc. This one is built
/// by [`annotate_candidates`] in ordinary use, but every per-format scanner
/// crate builds one directly to drive its `write_payload` seam, so the
/// literal it used to need was an out-of-crate literal all the same.
#[derive(Debug)]
#[non_exhaustive]
pub struct SalvagedEntry {
    /// This entry's position in SCAN order — not an index any container's
    /// own format assigns, and never renumbered by what `list` would show.
    /// A later task's CLI surfaces this distinction explicitly (`--index`
    /// on `salvage` names a scan position, not a list index).
    pub scan_position: usize,
    pub offset: u64,
    /// Carried forward from [`Candidate::payload_start`] — see that
    /// field's doc for why a consumer must use this rather than
    /// re-deriving a payload's location from `offset` itself.
    pub payload_start: u64,
    pub meta: EntryMeta,
    pub status: SalvageStatus,
    /// Set when this record's `(name, declared_len, verifier)` all agree
    /// with an EARLIER record's — a measurement, never inferred from a
    /// repeated name alone, and never set for a degenerate zero-length
    /// checksum (every empty file and every directory entry shares one).
    /// See [`annotate_candidates`] for where this is computed.
    ///
    /// **This is the byte-identical duplicate, and ONLY that.** The other,
    /// weaker fact — an earlier record under the same name whose content
    /// this scan could not prove identical — is [`Self::collides_with`], and
    /// the two are mutually exclusive by construction. They were one word
    /// ("shadow") until the final whole-branch review measured what that
    /// cost: `stuffr list`'s own fidelity warning uses "shadowed" for a
    /// repeated NAME, so on an archive whose duplicates differ, `list` said
    /// two records were shadowed and `salvage --list` marked none.
    pub shadows: Option<usize>,
    /// Set when an EARLIER record carries the same `meta.name` and this one
    /// is not that record's [`Self::shadows`] — i.e. the name repeats but
    /// the content could not be proven identical.
    ///
    /// This is the fact `stuffr list`'s `Fidelity::EntryCountMismatch`
    /// warning is about: a later record repeating a name is what makes an
    /// earlier one unreachable through a central directory's name index,
    /// whatever the bytes under it. It is also the fact that decides
    /// anything on the WRITE side, because two records under one name and
    /// two different payloads cannot both land on one path.
    ///
    /// Deliberately NOT gated on a verifier, a declared length or the
    /// degenerate zero-length case the way [`Self::shadows`] is: those
    /// guards exist because claiming two records are COPIES of each other
    /// needs proof, and this annotation claims no such thing. A repeated
    /// name is directly observed, and `None` here means only that no
    /// earlier record used this name — never that one did and this could
    /// not tell.
    pub collides_with: Option<usize>,
    /// Carried forward unchanged from [`Candidate::marked_deleted`] — see
    /// that field for the whole ruling. Unlike [`Self::shadows`] and
    /// [`Self::collides_with`], this is not something this module MEASURES:
    /// it is a fact the archive's own record states, which only the scanner
    /// that read that record can know.
    pub marked_deleted: bool,
}

impl SalvagedEntry {
    /// An entry at scan position `scan_position`, found at `offset`, whose
    /// payload begins at `payload_start`, carrying `meta` and proven to
    /// `status`.
    ///
    /// The three fields this does not take default to "nothing was
    /// observed": no shadow, no name collision, not marked deleted. All
    /// three are annotations [`annotate_candidates`] adds (or, for
    /// `marked_deleted`, carries forward from [`Candidate`]), so a caller
    /// building one directly — every per-format `write_payload` test does —
    /// wants exactly those defaults.
    pub fn new(
        scan_position: usize,
        offset: u64,
        payload_start: u64,
        meta: EntryMeta,
        status: SalvageStatus,
    ) -> Self {
        Self {
            scan_position,
            offset,
            payload_start,
            meta,
            status,
            shadows: None,
            collides_with: None,
            marked_deleted: false,
        }
    }

    /// Sets [`Self::shadows`] — the byte-identical duplicate, and only
    /// that. See the field's own doc for what separates it from
    /// [`Self::collides_with`].
    #[must_use]
    pub fn with_shadows(mut self, shadows: Option<usize>) -> Self {
        self.shadows = shadows;
        self
    }

    /// Sets [`Self::collides_with`] — the weaker, name-only annotation.
    #[must_use]
    pub fn with_collides_with(mut self, collides_with: Option<usize>) -> Self {
        self.collides_with = collides_with;
        self
    }

    /// Sets [`Self::marked_deleted`], carried forward from
    /// [`Candidate::marked_deleted`] rather than measured here.
    #[must_use]
    pub fn with_marked_deleted(mut self, marked_deleted: bool) -> Self {
        self.marked_deleted = marked_deleted;
        self
    }
}

/// The result of a scan: every entry the scanner recovered, in scan order.
///
/// Later tasks may extend this struct; the `entries` field stays public,
/// and `#[non_exhaustive]` is what makes "extend" honest. No constructor is
/// paired with it, unlike [`Candidate`] and [`SalvagedEntry`]: this struct
/// is built by [`salvage_all`] alone, in this crate, and no scanner — in
/// this workspace or outside it — has any reason to build one.
#[derive(Debug)]
#[non_exhaustive]
pub struct SalvageOutcome {
    pub entries: Vec<SalvagedEntry>,
    /// Header shapes the scanner recognised and could not gate, in scan
    /// order — see [`Sighting`]. Always empty from [`salvage_all`]: the
    /// engine cannot know what its scanner refused, so a format's own
    /// `salvage_*` entry point fills it in after the scan. A sighting is
    /// never an entry; the facade's `salvage_exit_code` counts a
    /// non-selective run that has one as degraded (exit 4) since the
    /// Salvage Stage 3 final review's I-1, which reversed Ruling S-X there.
    pub sightings: Vec<Sighting>,
    /// Where a SEQUENTIAL-ONLY scanner's walk stopped short of the end of
    /// the source, if it did — see [`WalkStop`]. Always `None` from
    /// [`salvage_all`], for the same reason [`Self::sightings`] is always
    /// empty there: only the scanner knows its walk ended early, so its own
    /// `salvage_*` entry point fills this in. Like a sighting it is never an
    /// entry and never touches the run's exit code.
    pub walk_stop: Option<WalkStop>,
}

/// A header a scanner SAW and has no gate for (Rulings S-V and 3-J): its
/// structure is a header's, and something about it — a field this build
/// cannot check, a shape a shifted copy also takes — leaves the scan unable
/// to tell it from a phantom. So it is counted here and never becomes a
/// [`Candidate`], because the engine advances past a candidate by its
/// declared length and a phantom's length is how a scan jumps a real header.
///
/// **Why it has to be reported at all.** A run that recovers nothing while
/// seeing one refuses with [`Error::Unsupported`] (exit 3) — the scanner's own
/// job, since only it can name the shape. A run that recovered OTHER entries
/// reports them at its ordinary exit code (Ruling S-X), and until Salvage
/// Stage 3's Task 2-N it said nothing else: an entry `stuffr list` shows was
/// simply absent from `salvage --list`, at exit 0, with an empty stderr. The
/// sightings recorded here are what the caller prints instead
/// ([`describe_sightings`]), in a mixed run as in any other — and since the
/// stage's final review (I-1, reversing S-X for this case) a non-selective
/// mixed run also exits 4, not 0: a `salvage -C out && rm` script must not
/// delete an archive holding an entry `stuffr list` reads.
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub struct Sighting {
    /// The scanner's format, for the sentence [`describe_sightings`] writes.
    pub format: FormatId,
    /// Where the header was seen.
    pub offset: u64,
    /// What was seen, as a plural noun phrase that follows a count —
    /// `"header(s) whose magic field … is neither \`ustar\` nor blank"`. One
    /// phrase per shape, shared with the scanner's own exit-3 refusal, so
    /// the two can never describe one shape two ways.
    pub shape: &'static str,
    /// Why the header was not listed — which sentence
    /// [`describe_sightings`] reports it in.
    pub kind: SightingKind,
    /// How many further sightings of this same (format, shape, kind) a
    /// [`SightingLog`] saw but did not store, folded into this one. 0 from
    /// every constructor. [`describe_sightings`] adds it to the count it
    /// prints, so a capped log reports the same total as an uncapped one.
    pub more: u64,
}

/// Why a [`Sighting`]'s header was not listed. The two are different claims,
/// so [`describe_sightings`] words them apart.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
#[non_exhaustive]
pub enum SightingKind {
    /// A header with a header's structure, in a shape this build has no
    /// gate for — every sighting before 0.10.3.
    #[default]
    Ungateable,
    /// A header the scan could gate, but whose extension chains it did not
    /// read because a bound on the work it spends on them was reached —
    /// tar's per-header and scan-wide budgets (0.10.3). The header itself
    /// may be genuine: the scan-wide budget can be spent by forged chains
    /// elsewhere in the file. The scan carries on past it.
    WorkBounded,
    /// A candidate header whose verdict needed a long field — a name, a
    /// variable part, an extension chain, the bytes a header CRC covers —
    /// that the scan did not read, because its [`ScanBudget`] was spent
    /// (0.10.3). Like [`Self::WorkBounded`] the header itself may be
    /// genuine, starved by forged candidates elsewhere in the file, and the
    /// scan carries on past it. Its own kind rather than
    /// [`Self::WorkBounded`] because that one's sentence names extension
    /// chains, which is false of a zip name or a CRC.
    VerdictBounded,
}

impl Sighting {
    /// An [`SightingKind::Ungateable`] sighting.
    pub fn new(format: FormatId, offset: u64, shape: &'static str) -> Self {
        Self {
            format,
            offset,
            shape,
            kind: SightingKind::Ungateable,
            more: 0,
        }
    }

    /// This sighting standing for `more` further ones that were counted but
    /// not stored (see [`Sighting::more`]).
    #[must_use]
    pub fn with_more(self, more: u64) -> Self {
        Self { more, ..self }
    }

    /// A [`SightingKind::WorkBounded`] sighting.
    pub fn work_bounded(format: FormatId, offset: u64, shape: &'static str) -> Self {
        Self {
            kind: SightingKind::WorkBounded,
            ..Self::new(format, offset, shape)
        }
    }

    /// A [`SightingKind::VerdictBounded`] sighting: the candidate at
    /// `offset` was refused unexamined because the scan's [`ScanBudget`]
    /// was spent.
    pub fn verdict_bounded(format: FormatId, offset: u64, shape: &'static str) -> Self {
        Self {
            kind: SightingKind::VerdictBounded,
            ..Self::new(format, offset, shape)
        }
    }
}

/// A bounded store for [`Sighting`]s: at most `cap` per (format, shape,
/// kind) are kept, so the memory one scan spends on them is at most
/// groups x cap however hostile the input, while the count of each group
/// stays exact. [`Self::count`] gives the exact total pushed, and
/// [`Self::into_sightings`] folds the uncounted remainder into the last
/// stored sighting's [`Sighting::more`], so [`describe_sightings`] prints
/// the same sentence it would for every sighting stored.
#[derive(Debug, Clone)]
pub struct SightingLog {
    cap: usize,
    groups: Vec<LogGroup>,
}

#[derive(Debug, Clone)]
struct LogGroup {
    key: (FormatId, &'static str, SightingKind),
    stored: Vec<Sighting>,
    total: u64,
}

impl SightingLog {
    /// The default per-group cap.
    pub const DEFAULT_CAP: usize = 64;

    /// An empty log with [`Self::DEFAULT_CAP`].
    pub fn new() -> Self {
        Self::with_cap(Self::DEFAULT_CAP)
    }

    /// An empty log keeping at most `cap` sightings per group. A `cap` of 0
    /// is raised to 1, so a group always has a sighting to carry its count.
    ///
    /// A `cap` below 8 (`SIGHTING_OFFSETS_SHOWN`) CHANGES the sentence
    /// [`describe_sightings`] prints: it lists only the stored offsets, so a
    /// group holding more than `cap` would show fewer offsets and a larger
    /// "and N more" than an uncapped list. The count stays exact either way.
    pub fn with_cap(cap: usize) -> Self {
        Self {
            cap: cap.max(1),
            groups: Vec::new(),
        }
    }

    /// Record `sighting`: stored while its group holds fewer than the cap,
    /// and always counted. A sighting's own [`Sighting::more`] is counted
    /// too.
    pub fn push(&mut self, sighting: Sighting) {
        let key = (sighting.format, sighting.shape, sighting.kind);
        let idx = match self.groups.iter().position(|g| g.key == key) {
            Some(i) => i,
            None => {
                self.groups.push(LogGroup {
                    key,
                    stored: Vec::new(),
                    total: 0,
                });
                self.groups.len() - 1
            }
        };
        let g = &mut self.groups[idx];
        g.total = g.total.saturating_add(1).saturating_add(sighting.more);
        if g.stored.len() < self.cap {
            g.stored.push(sighting);
        }
    }

    /// The exact number of sightings of this group pushed, stored or not.
    pub fn count(&self, format: FormatId, shape: &'static str, kind: SightingKind) -> u64 {
        self.groups
            .iter()
            .find(|g| g.key == (format, shape, kind))
            .map_or(0, |g| g.total)
    }

    /// Whether nothing has been pushed.
    pub fn is_empty(&self) -> bool {
        self.groups.is_empty()
    }

    /// The stored sightings, groups in first-seen order, each group's last
    /// one carrying the count of those not stored in [`Sighting::more`].
    ///
    /// The offsets kept are the first `cap` of each group in PUSH order, so
    /// a scanner that wants the smallest listed must push each group in
    /// ascending offset order.
    pub fn into_sightings(self) -> Vec<Sighting> {
        let mut out = Vec::new();
        for mut g in self.groups {
            let stored_weight: u64 = g
                .stored
                .iter()
                .fold(0u64, |a, s| a.saturating_add(1).saturating_add(s.more));
            let rest = g.total.saturating_sub(stored_weight);
            if let Some(last) = g.stored.last_mut() {
                last.more = last.more.saturating_add(rest);
            }
            out.extend(g.stored);
        }
        out
    }
}

impl Default for SightingLog {
    fn default() -> Self {
        Self::new()
    }
}

/// The most offsets [`describe_sightings`] lists per shape before it says
/// how many more there were. The count itself is always the complete figure.
const SIGHTING_OFFSETS_SHOWN: usize = 8;

/// The one sentence a caller prints for `sightings`, or `None` when there
/// are none — how many headers of each shape were seen, where, and that the
/// ordinary verbs may read them or name the variant they are in. It is the
/// same wording family as each scanner's exit-3 refusal (its shape phrases
/// are the scanner's own), and it is written here, once, so every scanner
/// that records a [`Sighting`] gets the same report without a line of its
/// own.
///
/// **"Or name the variant" is cpio's clause (Salvage Stage 3 Task 3).** The
/// tail said only "may read these headers normally", which is true of a tar
/// header the scan cannot gate and false of a cpio `odc` or `newc-crc`
/// header: `stuffr list` refuses both variants at exit 3, naming them. A note
/// telling a user to expect `list` to read them would be the false "list
/// reads it" claim Task 2-N's fix round removed from tar.
///
/// **[`SightingKind::WorkBounded`] sightings get their own sentence**
/// (0.10.3): "the structure of a header, but in a shape it has no gate for"
/// is false of a header the scan gated and then stopped spending work on.
/// When a run has both kinds, the two sentences are joined; the
/// [`SightingKind::Ungateable`] one is worded exactly as before.
///
/// **So do [`SightingKind::VerdictBounded`] ones** (0.10.3 Task 4b): the
/// work-bounded sentence names extension chains, which is false of a zip
/// name, a ZOO variable part or the bytes an ARJ header CRC covers. Each
/// sentence that applies is joined in the same way, and the two older ones
/// are worded exactly as before.
pub fn describe_sightings(sightings: &[Sighting]) -> Option<String> {
    describe(sightings, true)
}

/// [`describe_sightings`], optionally without each sentence's closing
/// "`stuffr list` and `stuffr unpack` may read these headers normally"
/// clause — for a caller that has just said so itself.
fn describe(sightings: &[Sighting], list_clause: bool) -> Option<String> {
    let tail = if list_clause {
        "; `stuffr list` and `stuffr unpack` may read these headers normally"
    } else {
        ""
    };
    let of_kind = |kind: SightingKind| -> Vec<&Sighting> {
        sightings.iter().filter(|s| s.kind == kind).collect()
    };
    let ungateable = of_kind(SightingKind::Ungateable);
    let bounded = of_kind(SightingKind::WorkBounded);
    let verdicts = of_kind(SightingKind::VerdictBounded);
    let mut sentences = Vec::new();
    if !ungateable.is_empty() {
        sentences.push(format!(
            "this build's salvage scanner saw {} — each with the structure of a header, but in \
             a shape it has no gate for, so none is listed or recovered; `stuffr list` and \
             `stuffr unpack` may read these headers normally, or name the variant they are in, \
             and it is the SCAN that stops there",
            sighting_groups(&ungateable)
        ));
    }
    if !bounded.is_empty() {
        sentences.push(format!(
            "this build's salvage scanner bounds the work it spends on extension chains, and \
             did not read the chains in front of {} — so whatever those chains describe is not \
             listed or recovered there, though the scan went on past them{tail}",
            sighting_groups(&bounded)
        ));
    }
    if !verdicts.is_empty() {
        sentences.push(format!(
            "this build's salvage scanner bounds the work it spends judging candidate headers \
             across the whole scan, and did not judge {} — so whatever those headers \
             describe is not listed or recovered there, though the scan went on past them{tail}",
            sighting_groups(&verdicts)
        ));
    }
    (!sentences.is_empty()).then(|| sentences.join("; and separately, "))
}

/// What a salvage refusal's own text already says about `stuffr list` and
/// `stuffr unpack`, which decides whether [`refusal_with_bounded_notes`]'s
/// note repeats the point.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum RefusalSays {
    /// The refusal has just said that `stuffr list` and `stuffr unpack` read
    /// these headers normally (tar, lha): the note leaves its closing clause
    /// to that.
    ListReadsThem,
    /// The refusal says nothing of the kind (cpio's names the variant, not
    /// the verbs): the note closes with "`stuffr list` and `stuffr unpack`
    /// may read these headers normally".
    NothingAboutList,
}

/// `refusal` for an `Err(Unsupported)` that also carries what the scan would
/// otherwise have dropped: the work- and verdict-bounded `sightings`, in
/// [`describe_sightings`]' words, after `"; and separately, "`. Ungateable
/// sightings are left out — the refusal already describes those shapes — and
/// with no bounded sighting the refusal comes back unchanged. One line.
/// `says` is what `refusal` already says about the list/unpack verbs; see
/// [`RefusalSays`].
pub fn refusal_with_bounded_notes(
    refusal: String,
    sightings: Vec<Sighting>,
    says: RefusalSays,
) -> String {
    let bounded: Vec<Sighting> = sightings
        .into_iter()
        .filter(|s| s.kind != SightingKind::Ungateable)
        .collect();
    match describe(&bounded, says == RefusalSays::NothingAboutList) {
        Some(note) => format!("{refusal}; and separately, {note}"),
        None => refusal,
    }
}

/// `"{count} {format} {shape} at offset(s) {offsets}"` per (format, shape),
/// joined by `"; and "` — the middle of each [`describe_sightings`] sentence.
fn sighting_groups(sightings: &[&Sighting]) -> String {
    // Grouped by (format, shape) in first-seen order: a handful of shapes
    // at most, so a linear search beats a map and keeps the order stable.
    // `extra` is the sightings a [`SightingLog`] counted but did not store.
    let mut groups: Vec<((FormatId, &'static str), Vec<u64>, u64)> = Vec::new();
    for s in sightings {
        let key = (s.format, s.shape);
        match groups.iter_mut().find(|(k, _, _)| *k == key) {
            Some((_, offsets, extra)) => {
                offsets.push(s.offset);
                *extra = extra.saturating_add(s.more);
            }
            None => groups.push((key, vec![s.offset], s.more)),
        }
    }
    let parts: Vec<String> = groups
        .iter()
        .map(|((format, shape), offsets, extra)| {
            let count = offsets.len() as u64 + extra;
            let mut shown: Vec<String> = offsets
                .iter()
                .take(SIGHTING_OFFSETS_SHOWN)
                .map(u64::to_string)
                .collect();
            if count > SIGHTING_OFFSETS_SHOWN as u64 {
                shown.push(format!("and {} more", count - shown.len() as u64));
            }
            format!("{count} {format} {shape} at offset(s) {}", shown.join(", "))
        })
        .collect();
    parts.join("; and ")
}

/// Where a scanner that can ONLY walk its format in order — record after
/// record from the start, the way the ordinary reader does — had to stop
/// before the end of the source (Salvage Stage 3 Task 4).
///
/// # Why a walk stop is not a [`Sighting`]
///
/// A sighting is a header the scan SAW, whose structure is a header's and
/// which it cannot gate. A walk stop is the opposite: a place where the
/// walk found nothing it could read as a record at all, and — because the
/// format carries nothing strong enough to search for (an `ar` member's
/// only marker is two bytes) — cannot look any further. Folding it into
/// [`Sighting`] would make "saw a real header" and "could see nothing" one
/// channel, and [`describe_sightings`]'s own sentence ("`stuffr list` may
/// read these headers normally") would then be false about it.
///
/// # What it must say, and why it has to be said at all
///
/// The entries a sequential walk cannot reach are **unreachable by
/// construction, not absent**: a run that recovers three entries from a
/// ten-entry archive with a hole after the third reports three rows, and
/// nothing in those rows says seven more may sit behind the hole. So the
/// caller prints [`describe_walk_stop`] of this on every run that has one,
/// and the offset it names is where a user with a hex editor would look.
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub struct WalkStop {
    /// The scanner's format, for the sentence [`describe_walk_stop`] writes.
    pub format: FormatId,
    /// Where the record the walk could not read begins — the first byte
    /// after the last record it did read.
    pub offset: u64,
    /// Bytes from [`Self::offset`] to the end of the source.
    pub remaining: u64,
    /// Which of the two things this stop is — see [`WalkStopKind`].
    pub kind: WalkStopKind,
    /// The ordinary reader's own words for why that record would not read,
    /// so the note and `stuffr list`'s refusal of the same bytes agree.
    pub cause: String,
}

/// The three stops a sequential walk can make, each told apart by what the
/// scanner measured rather than guessed.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum WalkStopKind {
    /// The file ends inside the record at the stop point — the reader ran
    /// out of bytes mid-record, or fewer bytes remain than the format's
    /// smallest record header. Everything from the stop point on belongs to
    /// that incomplete record, so no entry can be hiding after it — the
    /// common damage, and the one a sequential walk handles fully.
    CutShort,
    /// Enough bytes remain to hold further records, and the walk could not
    /// read the one at the stop point. Whatever those bytes hold is
    /// unreachable by construction.
    Unreadable,
    /// The record at the stop point is one the scanner RECOGNISES — its
    /// [`WalkStop::cause`] names it — in a shape this build cannot read (Task
    /// 4 fix round 1: an `ar` symbol table whose header the reader cannot
    /// parse; GNU `ar`'s Mach-O `__.SYMDEF` with a blank mode was the first,
    /// and is read since 0.8.1). Not evidence of damage; what follows is
    /// unreachable to this scanner.
    UnsupportedShape,
}

impl WalkStop {
    pub fn new(
        format: FormatId,
        offset: u64,
        remaining: u64,
        kind: WalkStopKind,
        cause: impl Into<String>,
    ) -> Self {
        Self {
            format,
            offset,
            remaining,
            kind,
            cause: cause.into(),
        }
    }
}

/// The one sentence a caller prints for a [`WalkStop`] — written here, once,
/// so every sequential-only scanner gets the same report without a line of
/// its own, and so its kinds can never be described two ways each.
///
/// An [`WalkStopKind::Unreadable`] stop says the entries after it are
/// *unreachable by construction, not absent*, with the offset and the byte
/// count; a [`WalkStopKind::CutShort`] one says that nothing after it is
/// missing from the report, which is exactly as true — the file ended inside
/// that record; an [`WalkStopKind::UnsupportedShape`] one names the shape and
/// says it is not evidence of damage.
///
/// Two of the sentences say the walk goes "as `stuffr list` does". That is a
/// contract on every scanner that reports a [`WalkStop`]: it walks with its
/// format's ORDINARY reader, over the file's own bytes, repairing none of
/// them. `ar`'s walk served its global header as `!<arch>\n` until Stage 3
/// Task 4's fix round 1, which made the phrase false (a bad magic `list`
/// refuses was walked past) — a scanner that needs a repair like that must
/// get its own sentence here rather than borrow this one.
pub fn describe_walk_stop(stop: &WalkStop) -> String {
    let WalkStop {
        format,
        offset,
        remaining,
        kind,
        cause,
    } = stop;
    let bytes = if *remaining == 1 { "byte" } else { "bytes" };
    match kind {
        WalkStopKind::Unreadable => format!(
            "this build's {format} salvage scanner walks the archive in order from its start, \
             as `stuffr list` does, and stopped at offset {offset} with {remaining} {bytes} still \
             to go: {cause}. The {format} format marks its records with nothing strong enough \
             to search for, so the scanner cannot find its way past a record it cannot read; \
             any entries in those {remaining} {bytes} are unreachable by construction — not \
             absent, and not counted in this report"
        ),
        WalkStopKind::UnsupportedShape => format!(
            "this build's {format} salvage scanner walks the archive in order from its start, \
             as `stuffr list` does, and stopped at offset {offset} with {remaining} {bytes} still \
             to go: {cause}. That is a record shape this build does not read, not evidence of \
             damage; any entries in those {remaining} {bytes} are unreachable to this scanner \
             and not counted in this report"
        ),
        WalkStopKind::CutShort => format!(
            "this build's {format} salvage scanner walks the archive in order from its start, \
             and the file ends {remaining} {bytes} into the record at offset {offset} ({cause}): \
             too few for any further entry, so the archive is cut short there and nothing \
             after that point is missing from this report"
        ),
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PartialPolicy {
    Keep,
    Skip,
    Ask,
}

pub struct SalvagePolicy {
    /// Recovery-biased by default: salvage is the one permissive verb, and
    /// the strict path is the entire rest of the tool.
    pub partial: PartialPolicy,
    /// Structural ceiling on any one entry's length, refused BEFORE
    /// allocation — and refused as a per-entry
    /// [`UnverifiedCause::OverEntryCeiling`], never as an error that ends
    /// the run. [`SalvageScan::max_whole_entry`] narrows it further for a
    /// format that decodes an entry whole; the two compose as a minimum and
    /// are applied together, once, in [`annotate_candidates`].
    pub max_entry: u64,
    /// Demand proof: every [`SalvageStatus::Partial`] entry is skipped,
    /// whatever [`Self::partial`] says, and so is every
    /// [`SalvageStatus::Unattested`] one (Ruling 3-H, Salvage Stage 3).
    ///
    /// The second clause is this flag's doing, unlike the two refused
    /// below: an `Unattested` entry is WRITTEN by default, under its real
    /// name, and only `strict` declines it — the format carries nothing
    /// that could prove it, which is exactly what "demand proof" asks for.
    ///
    /// **Those two are the whole of it, and this doc claimed three things
    /// until the final whole-branch review's F5.** It read "partial skipped,
    /// ceiling fixed, nothing unverifiable", and only the first clause was
    /// this flag's doing. The ceiling is NOT fixed under `strict`:
    /// [`Self::max_entry`] applies identically with and without it, and
    /// `--max-entry` is honoured either way. And an
    /// [`SalvageStatus::Unverified`] entry is never written under any
    /// policy at all — that is the ops layer's unconditional rule, not
    /// something `strict` causes — so crediting it here made a flag look
    /// load-bearing for a guarantee that holds without it.
    ///
    /// The true clauses are enough to justify the flag: `salvage` is this
    /// tool's single recovery-biased verb, so `strict` is how a caller asks
    /// for the discipline every other verb applies by default.
    pub strict: bool,
}

impl Default for SalvagePolicy {
    fn default() -> Self {
        Self {
            partial: PartialPolicy::Keep,
            max_entry: MAX_SALVAGE_ENTRY,
            strict: false,
        }
    }
}

/// Reusable scratch for a scanner's forward search for its next signature
/// (a magic, a checksum-valid block). Reads start at [`Self::FIRST_CHUNK`],
/// or at `2 * sig_len - 1` when that is larger, so the first read always
/// tests `sig_len` offsets, and double up to [`Self::MAX_CHUNK`], into one
/// buffer kept across calls,
/// so a search whose answer is a few bytes away reads a few bytes: a scan
/// that resumes one byte past a refused candidate costs work proportional to
/// the distance it actually searched, never a fixed 64 KiB per call. That is
/// the property `testing::check_scan_is_linear` holds every scanner to.
/// O(1) memory however far the next signature is.
///
/// **The bytes a search read past its answer are kept for the next call
/// (0.10.3 Task 4).** A call whose `from` lies inside what the previous
/// call read tests those bytes again without reading them again, and reads
/// only past them. Without that, every call paid at least its first read
/// afresh, so candidates a few bytes apart — an accepted header every
/// eleven bytes, say — cost a first read EACH: 64 bytes, or `2 * sig_len -
/// 1` for a long signature, per candidate. A scan whose `from` only moves
/// forward therefore reads each byte about once in its searches, however
/// dense its candidates are.
///
/// **One `ForwardSearch` serves one source**, whose bytes do not change
/// while it is in use — a scanner owns one per scan. Pass a different
/// source and the kept bytes are that other source's. A call with a
/// smaller `file_len` than the last never tests a kept byte at or past it.
#[derive(Debug, Default)]
pub struct ForwardSearch {
    /// Bytes read from the source, starting at offset `window_start`.
    window: Vec<u8>,
    window_start: u64,
}

impl ForwardSearch {
    /// Size of the first read of every search, unless the signature is long
    /// enough that `2 * sig_len - 1` is larger — see [`Self::find`].
    pub const FIRST_CHUNK: usize = 64;
    /// Ceiling the read size doubles up to.
    pub const MAX_CHUNK: usize = 64 * 1024;

    /// An empty search; the buffer grows on first use and is then reused.
    pub fn new() -> Self {
        Self::default()
    }

    /// The first offset `>= from` at which `matches` accepts the `sig_len`
    /// bytes starting there, or `None` when none does before `file_len`.
    /// `matches` sees exactly `sig_len` bytes. Every offset is tested once,
    /// carrying `sig_len - 1` bytes across a chunk boundary. Never reads at
    /// or past `file_len`, and stops at EOF if the source is shorter.
    ///
    /// The first read is `max(FIRST_CHUNK, 2 * sig_len - 1)` bytes, so it
    /// tests at least `sig_len` offsets. A first read of only `sig_len`
    /// bytes tests ONE offset: for tar's 512-byte block, a header one block
    /// on then cost 512 + 1,024 bytes, three times the distance searched.
    pub fn find(
        &mut self,
        src: &mut dyn SeekRead,
        from: u64,
        file_len: u64,
        sig_len: usize,
        matches: impl FnMut(&[u8]) -> bool,
    ) -> io::Result<Option<u64>> {
        self.find_to_eof(src, from, file_len, sig_len, sig_len, matches)
    }

    /// [`Self::find`] for a record whose length is not fixed: offsets with
    /// at least `sig_len` bytes before `file_len` are offered exactly
    /// `sig_len` bytes, and the last offsets — those with fewer, down to
    /// `min_len` — are offered every byte left before `file_len`. A record
    /// whose longest form is `sig_len` bytes can then be judged whole
    /// inside the search, wherever it starts, without a second read near
    /// EOF. `min_len` is at least 1 and at most `sig_len`.
    pub fn find_to_eof(
        &mut self,
        src: &mut dyn SeekRead,
        from: u64,
        file_len: u64,
        sig_len: usize,
        min_len: usize,
        mut matches: impl FnMut(&[u8]) -> bool,
    ) -> io::Result<Option<u64>> {
        debug_assert!(1 <= min_len && min_len <= sig_len);
        if min_len == 0 || file_len.saturating_sub(from) < min_len as u64 {
            return Ok(None);
        }
        // Keep what the last call read from `from` on, if it read `from`;
        // otherwise start empty. Never keep a byte at or past `file_len`.
        let kept_end = self.window_start + self.window.len() as u64;
        if from >= self.window_start && from < kept_end {
            self.window.drain(..(from - self.window_start) as usize);
            let fits = (file_len - from).min(self.window.len() as u64);
            self.window.truncate(fits as usize);
        } else {
            self.window.clear();
        }
        self.window_start = from;
        let mut chunk = Self::FIRST_CHUNK.max(2 * sig_len - 1);
        let mut at_eof = false;
        loop {
            // Every offset with a full `sig_len` bytes in the window.
            if self.window.len() >= sig_len {
                let last = self.window.len() - sig_len;
                if let Some(at) = (0..=last).find(|&i| matches(&self.window[i..i + sig_len])) {
                    return Ok(Some(self.window_start + at as u64));
                }
                let tested = last + 1;
                self.window_start += tested as u64;
                self.window.drain(..tested);
            }
            let end = self.window_start + self.window.len() as u64;
            if at_eof || end >= file_len {
                // Nothing more to read: the offsets left have fewer than
                // `sig_len` bytes, and are offered what there is down to
                // `min_len`. They stay in the window, so a later call
                // re-tests them without a read.
                let short = self.window.len().saturating_sub(min_len - 1);
                let tail = (0..short).find(|&i| matches(&self.window[i..]));
                return Ok(tail.map(|at| self.window_start + at as u64));
            }
            let old = self.window.len();
            let want = (chunk as u64).min(file_len - end) as usize;
            src.seek(SeekFrom::Start(end))?;
            self.window.resize(old + want, 0);
            let n = src.read(&mut self.window[old..])?;
            self.window.truncate(old + n);
            if n == 0 {
                at_eof = true;
            } else if n == want {
                // Grow only on a full read: a source that trickles short
                // reads must not make every call zero a 64 KiB buffer for
                // 7 bytes.
                chunk = (chunk * 2).min(Self::MAX_CHUNK);
            }
        }
    }
}

/// The work one salvage scan may spend judging candidates beyond their
/// fixed headers: bytes a verdict consumes (a long name, a variable part, an
/// extension chain, the bytes a header CRC covers), counted whether they come
/// from the source or from a search window. A legitimate archive consumes
/// each verdict's bytes once, at most `file_len` in total, so the limit of
/// `2 × file_len + 32 KiB` never trips on real input; forged candidates
/// that would spend past it are refused unexamined and reported as a
/// verdict-bounded sighting ([`SightingKind::VerdictBounded`]), and the
/// scan goes on.
///
/// **Why the slack is only 32 KiB (Rulings T4b-2 and T4b-5).** A
/// legitimate scan's verdict bytes all lie inside the file, so they total
/// at most `file_len` — and where a scanner pays for a second read too
/// (cpio pays for a name in the scan and again when the header before it
/// corroborates its size), at most `2 × file_len`. The per-byte term covers
/// real input on its own, and the slack only rounds. It was 1 MiB, which
/// let a fuzz-scale input of a few KiB spend about 1 MiB: an 8 KiB file of
/// overlapping zip names read 536,640 bytes, past
/// `stuffr_core::testing::check_scan_is_linear`'s `8 × file_len + 64 KiB`.
/// At 32 KiB the same file reads 65,536 bytes, half that bound. 16 KiB
/// was tried first and changed the outcome of 27 fuzz-corpus ZOO inputs,
/// whose overlapping type-2 records each read most of the file; at 32 KiB,
/// with ZOO charging each variable part once, all 27 keep their outcome.
///
/// **Why a scan needs one (0.10.3).** A scanner resumes one byte past every
/// candidate it refuses, and past every candidate whose payload runs off the
/// end of the file, so candidates can overlap. Where a candidate's verdict
/// needs a field the format lets run to 64 KiB — a zip name, a ZOO type-2
/// variable part, an LHA extension chain — packing such candidates every few
/// dozen bytes made the scan read that field once per candidate: measured at
/// 495x, 962x and 957x the input. No verdict can be reached by reading less,
/// so the WORK is bounded instead, across the whole scan: tar's extension-read
/// budget (Ruling T3-1), generalised.
///
/// One per scan, shared by every pass the scan makes. A refused candidate is
/// reported through [`Sighting::verdict_bounded`], so a genuine header
/// starved by forgeries elsewhere is named, never lost silently.
#[derive(Debug)]
pub struct ScanBudget {
    limit: u64,
    spent: u64,
}

impl ScanBudget {
    /// Verdict bytes the scan may spend per byte of input.
    pub const PER_INPUT_BYTE: u64 = 2;
    /// Verdict bytes the scan may spend on top of [`Self::PER_INPUT_BYTE`]:
    /// rounding only, and small enough that it never dominates a small
    /// input's `check_scan_is_linear` bound — see the type's doc.
    pub const SLACK: u64 = 32 * 1024;

    /// The budget for one scan of a `file_len`-byte input:
    /// `2 × file_len + 32 KiB`.
    pub fn for_input(file_len: u64) -> Self {
        Self {
            limit: file_len
                .saturating_mul(Self::PER_INPUT_BYTE)
                .saturating_add(Self::SLACK),
            spent: 0,
        }
    }

    /// Charges `bytes` if they fit; `false` (charging nothing) if they would
    /// take the scan past its limit: the caller refuses the candidate
    /// without examining it.
    pub fn try_spend(&mut self, bytes: u64) -> bool {
        match self.spent.checked_add(bytes) {
            Some(total) if total <= self.limit => {
                self.spent = total;
                true
            }
            _ => false,
        }
    }

    /// Bytes charged so far.
    pub fn spent(&self) -> u64 {
        self.spent
    }
}

/// The per-format seam. A scanner recognises its own format's record shape
/// (a local header's magic, a member's checksum field) and reports what it
/// finds as a stream of [`Candidate`]s; [`salvage_all`] supplies everything
/// that does not depend on which format that is.
pub trait SalvageScan {
    /// Find the next candidate at or after `from`. `Ok(None)` ends the scan.
    fn next_candidate(&mut self, src: &mut dyn SeekRead, from: u64) -> Result<Option<Candidate>>;

    /// The largest single entry this scanner is willing to have read for it
    /// — the ceiling [`annotate_candidates`] applies, narrowed further by
    /// `policy.max_entry`, before it calls [`Self::verify`] at all.
    ///
    /// `u64::MAX` (the default) means "this scanner imposes none of its
    /// own": zip streams every payload it verifies through a `take`, so the
    /// only figure that bounds it is the policy's. A format that **decodes
    /// an entry whole** — ARC, and the legacy containers still to come —
    /// overrides this with its own container-side ceiling
    /// (`arc.rs`'s `MAX_ARC_ENTRY_LEN`, 256 MiB), because for those the
    /// figure really does become a single allocation.
    ///
    /// **Declaring a ceiling here is the ONLY way a scanner refuses an
    /// entry for its size**, and that is the point: the refusal is then a
    /// [`SalvageStatus`] the engine assigns
    /// ([`UnverifiedCause::OverEntryCeiling`]), not a [`crate::Error`] the
    /// scanner raises, so it can never abort a run over one entry. A
    /// scanner that instead checks a size inside [`Self::verify`] and
    /// `?`-propagates the failure reintroduces the exact defect three fix
    /// rounds of Task 3c chased.
    ///
    /// **That is documented, not enforced, and saying so is more useful
    /// than claiming otherwise.** An earlier wording here called the defect
    /// "unrepresentable"; it is not. [`Self::verify`] still returns
    /// `Result` — it must, so a scanner CAN report a genuine run-level
    /// fault — so the wrong thing is still expressible. What changed is
    /// that the right thing now exists, costs one method, and is written
    /// into [`Self::verify`]'s contract below.
    fn max_whole_entry(&self) -> u64 {
        u64::MAX
    }

    /// Decide what was actually proven about a candidate's payload, after
    /// discovery — called once per candidate, in file order, by
    /// [`annotate_candidates`].
    ///
    /// # The contract on `Err`
    ///
    /// **`Err` here aborts the WHOLE run**, discarding every entry already
    /// recovered, so it is reserved for a fault that really is about the
    /// run and not about this one entry (the destination is gone, the
    /// source handle itself failed). Everything a single candidate can be
    /// wrong about — a short read, a bad checksum, a method this build
    /// cannot decode, a device error partway through one payload — is a
    /// [`SalvageStatus`], never an `Err`. `zip_salvage.rs`'s own
    /// `verify_candidate` has stated this in prose since Stage 1 and folds
    /// every one of those; ARC's did not, for one case (its size ceiling),
    /// and that single `?` cost three fix rounds. The size ceiling now
    /// belongs to [`Self::max_whole_entry`], which the engine applies, so
    /// there is nothing left for an implementation to `?` on.
    ///
    /// # What an implementation may assume
    ///
    /// The candidate's bounded length (`available_len` if the payload was
    /// truncated, else `declared_len`) is already **at or below**
    /// [`Self::max_whole_entry`] — [`annotate_candidates`] answers
    /// [`UnverifiedCause::OverEntryCeiling`] itself, without calling this,
    /// for anything above it. So an implementation that decodes whole may
    /// size a buffer from that length without re-checking it.
    ///
    /// The default answers [`SalvageStatus::Unattested`] unconditionally,
    /// which is the least this method can claim: it reads nothing, decodes
    /// nothing and compares nothing, so "nothing attests that this candidate
    /// is an entry at all" is exactly what happened. A format that carries a
    /// checksum overrides this to decode the payload — reusing its own
    /// existing codec machinery, never inventing a new one here — and
    /// compare it against [`Candidate::verifier`]; a format that carries a
    /// self-verifying HEADER and no content checksum (tar) overrides it to
    /// check that header and answer [`SalvageStatus::Complete`].
    ///
    /// **It answered `Complete` until Salvage Stage 3**, and the change is
    /// not cosmetic. `Complete` asserts that every declared byte was present
    /// *and the header self-verified* — two claims this default has never
    /// been in a position to make — and it routes to **exit 0**, so a
    /// checksumless scanner that simply forgot to override was reporting a
    /// clean recovery over candidates nothing had examined. `Unattested`
    /// routes to exit 4 and says why on the row. The same argument
    /// [`Candidate::new`] makes for its own four defaults: the default is
    /// the answer that asserts the LEAST, so forgetting to override is
    /// visible rather than flattering.
    fn verify(&self, _src: &mut dyn SeekRead, _candidate: &Candidate) -> Result<SalvageStatus> {
        Ok(SalvageStatus::Unattested)
    }

    /// Decode one salvaged entry's payload out of the archive at
    /// `archive_path` and into `out`, answering whether the entry's whole
    /// declared length was produced.
    ///
    /// # Why this is on the trait at all (final whole-branch review, F2)
    ///
    /// `0.6.0` spends a breaking release making this trait implementable
    /// from outside. It was implementable and not USABLE: the ops layer's
    /// payload dispatch was a private `match` on a [`crate::FormatId`]
    /// string, so a scanner written outside this workspace got
    /// [`salvage_all`] and none of the behaviour that makes `salvage` what
    /// it is. This method is where a scanner's write half now DECLARES
    /// itself, beside the scan half, in one place a reader can see both.
    ///
    /// **It does not by itself make an out-of-tree scanner reachable from
    /// `stuffr salvage`, and pretending otherwise would be the same
    /// over-claim F2 named.** The ops layer still resolves a format to a
    /// scanner by name, with no registration point for a third party to add
    /// one; closing that needs a salvage registry and is Stage 3's. What
    /// changed is that the seam is now declared rather than scattered — the
    /// five in-tree scanners implement this method and the ops layer calls
    /// it, so the next one has a signature to fit rather than a convention
    /// to guess.
    ///
    /// # The contract
    ///
    /// `Ok(true)` means every declared byte was produced; `Ok(false)` means
    /// the payload ran short or the decoder stopped early, which the caller
    /// renders as a `.partial` write. **`Err` is reserved for the same
    /// narrow set [`Self::verify`] reserves it for** — with one addition
    /// the ops layer relies on: [`crate::Error::Io`] here is treated as a
    /// fact about THIS entry (the archive could not be re-opened or read
    /// for it, the destination refused the bytes) and folded into that
    /// entry's own outcome, never the run's. A size refusal is never an
    /// `Err`: it belongs to [`Self::max_whole_entry`], which the engine
    /// applies before `verify` is ever called.
    ///
    /// The default refuses. A scanner that only ever reports
    /// [`SalvageStatus::Unverified`] has nothing to write, and inheriting a
    /// refusal is the honest answer for it; the alternative — a required
    /// method — would be a breaking change to every implementation for no
    /// gain to one that cannot write anything anyway.
    fn write_payload(
        &self,
        _archive_path: &Path,
        _entry: &SalvagedEntry,
        _compressed_len: u64,
        _out: &mut dyn Write,
    ) -> Result<bool> {
        Err(Error::Unsupported(
            "this salvage scanner has no payload writer".to_string(),
        ))
    }
}

/// Walk `scan` over `src`, collecting every candidate it reports into a
/// [`SalvageOutcome`].
///
/// **Requires a seekable source.** Scanning searches back and forth over the
/// archive rather than reading it once in order, so this takes
/// `&mut dyn SeekRead` rather than the ladder's `Box<dyn Source>` (whose
/// `as_seek()` may be `None` for a pipe). A caller sitting on a
/// non-seekable source must spool it first — exactly as the `arj` and `zoo`
/// containers already do, reporting `Rung::Spilled` — which is a later
/// task's ops-layer concern, not this function's.
///
/// Every candidate's length is bounded against the run's entry ceiling
/// (`policy.max_entry`, narrowed by [`SalvageScan::max_whole_entry`])
/// **before** anything is sized from it — in [`annotate_candidates`], one
/// step before the only place that could size anything, and as a per-entry
/// [`UnverifiedCause::OverEntryCeiling`] rather than a [`crate::Error`] that ends
/// the run.
pub fn salvage_all(
    scan: &mut dyn SalvageScan,
    src: &mut dyn SeekRead,
    policy: &SalvagePolicy,
) -> Result<SalvageOutcome> {
    let candidates = collect_candidates(scan, src)?;
    annotate_candidates(&*scan, src, candidates, policy)
}

/// The resync loop alone: find a candidate, advance strictly past it,
/// repeat. Never reads a payload, never sizes anything from a declared
/// length, and never calls [`SalvageScan::verify`] — see
/// [`annotate_candidates`] for both the entry ceiling and the verification.
///
/// Exposed separately from [`salvage_all`] so a format that reconciles more
/// than one candidate source (zip's central-directory fallback) can collect
/// from each source before merging, and annotate the merged list once.
///
/// # The entry ceiling used to be enforced here, and was an `Err`
///
/// Salvage Stage 2 Task 3c's fix round 3 moved it to
/// [`annotate_candidates`] and turned it into a status. Two things were
/// wrong with it here, and only the second is obvious:
///
/// 1. **It refused a whole archive over one entry.** Measured at the CLI on
///    a 78-byte two-entry ARC, `stuffr salvage --list --max-entry 4`
///    printed no rows and exited 6 — the healthy first entry, which the
///    same binary recovers byte-for-byte at the default ceiling, simply
///    lost. That is the same defect the ARC scanner's own ceiling had, in
///    the engine rather than in a format.
/// 2. **It was one of two ceilings, checked in two places**, so which
///    disposition an over-ceiling entry got depended on which check saw it
///    first. There is now one rule, applied once, to both figures.
///
/// Nothing is weakened by the move: this loop sizes nothing from a declared
/// length (it only advances `from` by it), so "bounded before anything is
/// sized from it" holds exactly as before — the bound simply sits one
/// function later, still strictly before the only allocation there is.
pub fn collect_candidates(
    scan: &mut dyn SalvageScan,
    src: &mut dyn SeekRead,
) -> Result<Vec<Candidate>> {
    let mut candidates = Vec::new();
    let mut from = 0u64;

    while let Some(candidate) = scan.next_candidate(src, from)? {
        // Advance strictly past this candidate so the scan always makes
        // progress — but NEVER by a length this candidate merely CLAIMED.
        // `available_len.is_some()` means the header's own declared length
        // disagreed with the file (there were fewer bytes left than it
        // said), and a header that lied about its size once cannot be
        // trusted to say how much of the source its "payload" consumed
        // either. This used to advance by `available_len` — the bytes
        // actually present, not the declared figure — on the reasoning that
        // a truncated entry has nothing worth finding after it anyway. That
        // is true for a genuinely truncated REAL last entry, but the
        // engine cannot tell that case apart from a coincidental
        // false-positive header sitting on top of noise with a garbage
        // multi-hundred-megabyte declared length: `available_len` is the
        // same "everything left in the file" figure either way. Salvage
        // Stage 2 Task 3's fix round 1 found exactly this — one
        // coincidental marker+name match in an ARC noise corpus, with a
        // declared length far past the file, jumped the scan straight to
        // EOF in one step and silently dropped every real entry that
        // happened to sit between it and the end of the file: no error, no
        // `Partial`, no note, in the one verb whose entire job is not
        // losing entries silently. So a truncated candidate now advances
        // minimally — past its own marker byte only — so the very next
        // byte onward is examined for another header. That costs a few
        // bytes of re-scanning after a genuinely truncated real entry
        // (which has nothing left to find anyway, so the outcome is
        // unchanged); it is the entire fix for a phantom, whose lie no
        // longer costs the rest of the archive. An UNTRUNCATED candidate's
        // declared length was just checked against the file two lines
        // above — it fits, so it is not a lie, and advancing by it is
        // unchanged.
        let advance = if candidate.available_len.is_some() {
            1
        } else {
            candidate.declared_len.unwrap_or(1).max(1)
        };
        from = candidate.offset.saturating_add(advance);

        candidates.push(candidate);
    }

    Ok(candidates)
}

/// Turns already-discovered candidates — in file order — into the bounded,
/// verified, shadow-annotated entries a caller receives. See this module's
/// doc comment for what the passes (bound, verify, shadow) mean and why
/// they live here rather than per-format.
///
/// # The entry ceiling, in one place (fix round 3, Task 3c)
///
/// `policy.max_entry` narrowed by [`SalvageScan::max_whole_entry`] is the
/// run's ceiling on ONE entry, and this is the only place it is applied. A
/// candidate whose bounded length (`available_len` if the payload is
/// truncated, else `declared_len`) is over it is reported
/// [`SalvageStatus::Unverified`]`(`[`UnverifiedCause::OverEntryCeiling`]`)`
/// and [`SalvageScan::verify`] is **not called for it at all** — so nothing
/// is read and nothing is allocated, which was the whole purpose of the two
/// `Err`-raising checks this replaced, without their cost: neither the
/// engine's own nor a scanner's could refuse one entry without ending the
/// run and discarding every entry already recovered.
///
/// The bounded length, never the declared one, is what is compared — the
/// rule [`Candidate::available_len`]'s own doc argues for and the reason a
/// truncated tail's garbage declaration cannot decide anything: a candidate
/// whose payload ran out can never cost more than the bytes that exist.
pub fn annotate_candidates(
    scan: &dyn SalvageScan,
    src: &mut dyn SeekRead,
    candidates: Vec<Candidate>,
    policy: &SalvagePolicy,
) -> Result<SalvageOutcome> {
    let ceiling = policy.max_entry.min(scan.max_whole_entry());
    let mut entries = Vec::with_capacity(candidates.len());
    // Earliest scan_position to report each distinct (name, declared_len,
    // verifier) triple seen so far — a candidate reporting one already in
    // here is shadowing that position. A degenerate zero-length checksum
    // (every empty file, every directory entry) is never inserted here and
    // never looked up here — see `is_degenerate` below.
    let mut seen: HashMap<(String, Option<u64>, Verifier), usize> = HashMap::new();
    // Earliest scan_position to report each distinct NAME, regardless of
    // anything else about the record — the weaker, directly-observed fact
    // `SalvagedEntry::collides_with` reports, and the one `stuffr list`'s
    // own fidelity warning is about. Kept separate from `seen` above rather
    // than folded into it: that map is deliberately full of guards against
    // over-claiming a COPY (a verifier must exist, the declared length must
    // agree, a zero-length checksum never counts), and every one of them
    // would be wrong here, where nothing about content is being claimed.
    let mut names_seen: HashMap<String, usize> = HashMap::new();

    for (scan_position, candidate) in candidates.into_iter().enumerate() {
        // Bounded length, then the ceiling, then — only if it fits —
        // verification. `verify` is what reads and (for a whole-decoding
        // format) allocates, so refusing above it is refusing before the
        // allocation, which is the property the two `Err`s this replaced
        // existed for.
        let bounded_len = candidate.available_len.or(candidate.declared_len);
        let status = match bounded_len {
            Some(needed) if needed > ceiling => {
                SalvageStatus::Unverified(UnverifiedCause::OverEntryCeiling { needed, ceiling })
            }
            _ => scan.verify(src, &candidate)?,
        };

        let declared_len = candidate.declared_len;
        let verifier = candidate.verifier;
        // A checksum over zero declared bytes is the same value for every
        // empty entry that ever existed (CRC-32 and CRC-16/ARC of an empty
        // input are both fixed constants) and proves nothing about any two
        // of them being copies of each other — measured against a real
        // archive during this task's fix round: every `__init__.py` and
        // every directory entry collapsed onto one shadow chain under a
        // checksum-only match.
        let is_degenerate = declared_len == Some(0);

        let shadows = if is_degenerate {
            None
        } else {
            verifier.and_then(|v| {
                seen.get(&(candidate.meta.name.clone(), declared_len, v))
                    .copied()
            })
        };

        if !is_degenerate
            && shadows.is_none()
            && let Some(v) = verifier
        {
            seen.entry((candidate.meta.name.clone(), declared_len, v))
                .or_insert(scan_position);
        }

        // The two annotations are mutually exclusive: a record proven to be
        // a copy is reported as a shadow and nothing else, because "this is
        // a duplicate of #2" is strictly more informative than "something
        // earlier used this name". Everything else that repeats a name is a
        // collision.
        let earliest_with_name = names_seen.get(&candidate.meta.name).copied();
        let collides_with = if shadows.is_some() {
            None
        } else {
            earliest_with_name
        };
        if earliest_with_name.is_none() {
            names_seen.insert(candidate.meta.name.clone(), scan_position);
        }

        let marked_deleted = candidate.marked_deleted;
        entries.push(
            SalvagedEntry::new(
                scan_position,
                candidate.offset,
                candidate.payload_start,
                candidate.meta,
                status,
            )
            .with_shadows(shadows)
            .with_collides_with(collides_with)
            .with_marked_deleted(marked_deleted),
        );
    }

    Ok(SalvageOutcome {
        entries,
        sightings: Vec::new(),
        walk_stop: None,
    })
}

/// Streams `reader` into `out`, bounded to `expected_len` bytes — the
/// entry's own declared uncompressed size — so a small compressed input
/// cannot expand arbitrarily far past what its own header claims. Never
/// buffers a growable copy of the payload, only a fixed 64 KiB window, and
/// never trusts the decoder to stop on its own.
///
/// Returns `true` when exactly `expected_len` bytes were produced, `false`
/// when `reader` ran out or errored first — [`crate`]'s own convention
/// throughout this module: "did not fully recover" is a fact a caller
/// reports (as [`SalvageStatus::Partial`]'s own two causes already are),
/// never a [`crate::Error`] that aborts the whole run over one entry.
///
/// Lives here, rather than duplicated once per format module, because it
/// has no format-specific knowledge at all — only `Read`/`Write` and a byte
/// count. Task 3c moved it up from `entries.rs`, where it was zip-shaped
/// plumbing bolted onto a zip-only write path; every [`SalvageScan`]
/// implementation's own `write_payload` (zip's, ARC's, and any later
/// format's) calls this same function once it has a decoded reader in
/// hand, so a truncated or overrunning decode is reported identically
/// regardless of which format produced it.
pub fn stream_bounded_copy(
    mut reader: impl Read,
    expected_len: u64,
    out: &mut dyn Write,
) -> Result<bool> {
    let mut buf = [0u8; 64 * 1024];
    let mut produced = 0u64;
    loop {
        if produced >= expected_len {
            return Ok(true);
        }
        let want = ((expected_len - produced) as usize).min(buf.len());
        let n = match reader.read(&mut buf[..want]) {
            Ok(0) => return Ok(false),
            Ok(n) => n,
            Err(_) => return Ok(false),
        };
        out.write_all(&buf[..n])?;
        produced += n as u64;
    }
}

#[cfg(test)]
mod tests {
    use std::io::{Cursor, Read, Seek, SeekFrom};

    use super::*;

    fn bytes(data: &[u8]) -> Cursor<Vec<u8>> {
        Cursor::new(data.to_vec())
    }

    /// A reader that panics if asked to read more bytes in one call than its
    /// backing buffer holds. `salvage_all`'s own loop never reads a
    /// candidate's payload at all (see the module doc), so a correct
    /// implementation never trips this — it exists to catch a regression
    /// that reads before bounding, the exact shape this project has shipped
    /// six times across `cpio`, `ar` and `zip`.
    struct PanickingReader(Cursor<Vec<u8>>);

    impl Read for PanickingReader {
        fn read(&mut self, buf: &mut [u8]) -> std::io::Result<usize> {
            let backing_len = self.0.get_ref().len();
            assert!(
                buf.len() <= backing_len,
                "oversized read requested: {} bytes against a {backing_len}-byte source \
                 — an allocation or read was sized from a declared length before it was bounded",
                buf.len()
            );
            self.0.read(buf)
        }
    }

    impl Seek for PanickingReader {
        fn seek(&mut self, pos: SeekFrom) -> std::io::Result<u64> {
            self.0.seek(pos)
        }
    }

    fn panicking_reader(len: usize) -> PanickingReader {
        PanickingReader(Cursor::new(vec![0u8; len]))
    }

    /// A scanner that never finds anything, however many times it is asked.
    struct NeverFinds;

    impl SalvageScan for NeverFinds {
        fn next_candidate(
            &mut self,
            _src: &mut dyn SeekRead,
            _from: u64,
        ) -> Result<Option<Candidate>> {
            Ok(None)
        }
    }

    /// A scanner that reports exactly one candidate, declaring the given
    /// length, then ends the scan. It never touches `src` itself — it
    /// exists purely to hand `salvage_all` a declared length to bound.
    struct DeclaresLength(u64);

    impl SalvageScan for DeclaresLength {
        fn next_candidate(
            &mut self,
            _src: &mut dyn SeekRead,
            from: u64,
        ) -> Result<Option<Candidate>> {
            if from > 0 {
                return Ok(None);
            }
            Ok(Some(Candidate {
                offset: 0,
                payload_start: 0,
                meta: EntryMeta::file("absurd"),
                declared_len: Some(self.0),
                verifier: None,
                available_len: None,
                marked_deleted: false,
            }))
        }
    }

    /// A scanner reporting one candidate whose header DECLARES `declared`
    /// bytes while the source holds only `available` of them — the
    /// truncated-tail shape, the one a real scanner reports by setting
    /// [`Candidate::available_len`].
    struct DeclaresMoreThanIsThere {
        declared: u64,
        available: u64,
    }

    impl SalvageScan for DeclaresMoreThanIsThere {
        fn next_candidate(
            &mut self,
            _src: &mut dyn SeekRead,
            from: u64,
        ) -> Result<Option<Candidate>> {
            if from > 0 {
                return Ok(None);
            }
            Ok(Some(Candidate {
                offset: 0,
                payload_start: 0,
                meta: EntryMeta::file("cut-short"),
                declared_len: Some(self.declared),
                verifier: Some(Verifier::Crc32(1)),
                available_len: Some(self.available),
                marked_deleted: false,
            }))
        }
    }

    #[test]
    fn a_scanner_that_finds_nothing_yields_no_entries() {
        let out = salvage_all(
            &mut NeverFinds,
            &mut bytes(&[0u8; 4096]),
            &SalvagePolicy::default(),
        );
        assert!(
            out.unwrap().entries.is_empty(),
            "a scanner finding nothing must yield nothing"
        );
    }

    /// The ceiling test that matters most: a reader that PANICS on an
    /// oversized read, so this test fails if the read happens at all — not
    /// merely if the wrong status comes back. See this module's
    /// falsification note in the task report for what happens when the
    /// bound is moved below a read.
    ///
    /// Fix round 3 (Task 3c): the refusal is a per-entry STATUS now, not an
    /// `Err` — so this asserts both halves, that nothing was read AND that
    /// the run completed with the entry reported. The old assertion
    /// (`unwrap_err()`, exit 6) proved only the first and was satisfied by
    /// the behaviour that lost every other entry in the archive.
    #[test]
    fn an_absurd_declared_length_is_refused_before_the_allocation_it_would_size() {
        let mut scan = DeclaresLength(u64::MAX);
        let out = salvage_all(
            &mut scan,
            &mut panicking_reader(4096),
            &SalvagePolicy::default(),
        )
        .expect("an entry over the ceiling must not abort the run");
        assert_eq!(out.entries.len(), 1, "the entry is still reported");
        assert_eq!(
            out.entries[0].status,
            SalvageStatus::Unverified(UnverifiedCause::OverEntryCeiling {
                needed: u64::MAX,
                ceiling: MAX_SALVAGE_ENTRY,
            })
        );
    }

    /// The other half of the same rule, and the one the CLI reaches:
    /// everything AROUND an over-ceiling entry is still recovered. Measured
    /// before this fix as `stuffr salvage --list --max-entry 4` over a
    /// 78-byte ARC — no rows at all, exit 6.
    #[test]
    fn an_entry_over_the_ceiling_does_not_cost_the_entries_around_it() {
        struct TwoCandidates;
        impl SalvageScan for TwoCandidates {
            fn next_candidate(
                &mut self,
                _src: &mut dyn SeekRead,
                from: u64,
            ) -> Result<Option<Candidate>> {
                let (offset, len, name) = match from {
                    0 => (0u64, 16u64, "small-first"),
                    1..=16 => (17u64, 4096u64, "huge-second"),
                    _ => return Ok(None),
                };
                Ok(Some(Candidate {
                    offset,
                    payload_start: offset,
                    meta: EntryMeta::file(name),
                    declared_len: Some(len),
                    verifier: Some(Verifier::Crc32(len as u32)),
                    available_len: None,
                    marked_deleted: false,
                }))
            }
        }

        let out = salvage_all(
            &mut TwoCandidates,
            &mut bytes(&[0u8; 8192]),
            &SalvagePolicy {
                max_entry: 64,
                ..SalvagePolicy::default()
            },
        )
        .expect("one over-ceiling entry must never abort the run");
        assert_eq!(out.entries.len(), 2);
        // `TwoCandidates` does not override `verify`, so the first entry
        // takes the trait's default — `Unattested` since Salvage Stage 3,
        // where it was `Complete`. Neither figure is what this test is
        // about: the point is that the SECOND entry's ceiling refusal did
        // not cost the first entry its row.
        assert_eq!(out.entries[0].status, SalvageStatus::Unattested);
        assert_eq!(
            out.entries[1].status,
            SalvageStatus::Unverified(UnverifiedCause::OverEntryCeiling {
                needed: 4096,
                ceiling: 64,
            })
        );
    }

    /// A scanner's own [`SalvageScan::max_whole_entry`] narrows the policy's
    /// ceiling — the composition ARC relies on, proven against a mock so it
    /// does not depend on ARC's own 256 MiB constant. The candidate here is
    /// well under `policy.max_entry` and over the scanner's own figure, so
    /// only the `min` can refuse it; the panicking reader proves it is
    /// refused without being read.
    #[test]
    fn a_scanners_own_whole_entry_ceiling_narrows_the_policys() {
        struct DecodesWhole;
        impl SalvageScan for DecodesWhole {
            fn next_candidate(
                &mut self,
                _src: &mut dyn SeekRead,
                from: u64,
            ) -> Result<Option<Candidate>> {
                if from > 0 {
                    return Ok(None);
                }
                Ok(Some(Candidate {
                    offset: 0,
                    payload_start: 0,
                    meta: EntryMeta::file("whole"),
                    declared_len: Some(2048),
                    verifier: Some(Verifier::Crc32(7)),
                    available_len: None,
                    marked_deleted: false,
                }))
            }
            fn max_whole_entry(&self) -> u64 {
                1024
            }
            fn verify(&self, _src: &mut dyn SeekRead, _c: &Candidate) -> Result<SalvageStatus> {
                panic!("verify must not run for a candidate over the ceiling");
            }
        }

        let out = salvage_all(
            &mut DecodesWhole,
            &mut panicking_reader(4096),
            &SalvagePolicy::default(),
        )
        .expect("a scanner ceiling is a per-entry refusal, not a run failure");
        assert_eq!(
            out.entries[0].status,
            SalvageStatus::Unverified(UnverifiedCause::OverEntryCeiling {
                needed: 2048,
                // The SCANNER's figure, not the policy's 4 GiB — the `min`
                // is what this test is really pinning.
                ceiling: 1024,
            })
        );
    }

    #[test]
    fn a_declared_length_within_the_ceiling_is_collected_rather_than_refused() {
        let mut scan = DeclaresLength(4096);
        let out = salvage_all(
            &mut scan,
            &mut panicking_reader(4096),
            &SalvagePolicy::default(),
        )
        .unwrap();
        assert_eq!(out.entries.len(), 1);
        let entry = &out.entries[0];
        assert_eq!(entry.scan_position, 0);
        assert_eq!(entry.offset, 0);
        // `DeclaresLength` does not override `verify`, so this is the
        // trait's default: `Unattested` since Salvage Stage 3, where it was
        // `Complete`. The test is about the entry being COLLECTED — its
        // declared length sits under the ceiling — not about which tier a
        // mock that checks nothing lands in.
        assert_eq!(entry.status, SalvageStatus::Unattested);
        assert_eq!(entry.shadows, None);
        assert_eq!(entry.collides_with, None);
    }

    /// A truncated candidate is COLLECTED, not dropped — the whole point of
    /// [`Candidate::available_len`]. Before it existed, `zip_salvage.rs`
    /// refused such a candidate outright and a truncated archive's last
    /// entry vanished with no row, no note and exit 0.
    #[test]
    fn a_candidate_whose_payload_ran_out_is_still_collected() {
        let mut scan = DeclaresMoreThanIsThere {
            declared: 4000,
            available: 1950,
        };
        let out = salvage_all(
            &mut scan,
            &mut panicking_reader(4096),
            &SalvagePolicy::default(),
        )
        .unwrap();
        assert_eq!(
            out.entries.len(),
            1,
            "a header found but not completable is a fact worth reporting"
        );
    }

    /// The ceiling is checked against what could be READ, not against what
    /// a truncated header CLAIMED. Otherwise a garbage length in a tail the
    /// scan has already established is not there would abort the entire run
    /// at exit 6 — losing every earlier entry over an absent one, in the
    /// verb that exists to rescue exactly that archive.
    #[test]
    fn a_truncated_candidate_is_bounded_by_what_is_there_not_by_what_it_claimed() {
        let mut scan = DeclaresMoreThanIsThere {
            declared: u64::MAX,
            available: 2048,
        };
        let out = salvage_all(
            &mut scan,
            &mut panicking_reader(4096),
            &SalvagePolicy::default(),
        )
        .expect("an absent tail must not abort a run that recovered real entries");
        assert_eq!(out.entries.len(), 1);
    }

    /// The complement, so the rule above cannot be read as "truncated
    /// candidates are never bounded": what IS there is still bounded, and a
    /// truncated candidate holding more available bytes than the ceiling
    /// allows is refused exactly as an untruncated one would be — reported
    /// [`UnverifiedCause::OverEntryCeiling`], never read (the reader
    /// panics if it is), and never allowed to end the run.
    #[test]
    fn a_truncated_candidate_whose_available_bytes_exceed_the_ceiling_is_refused() {
        let mut scan = DeclaresMoreThanIsThere {
            declared: u64::MAX,
            available: 4096,
        };
        let out = salvage_all(
            &mut scan,
            &mut panicking_reader(4096),
            &SalvagePolicy {
                max_entry: 1024,
                ..SalvagePolicy::default()
            },
        )
        .expect("a bounded refusal is per-entry, never a run failure");
        assert_eq!(
            out.entries[0].status,
            // `needed` is 4096 — the bytes that ARE there — never the
            // `u64::MAX` this candidate's header declared. Fix round 4
            // (NEW-F): the figures a user is shown are the ones the
            // comparison used.
            SalvageStatus::Unverified(UnverifiedCause::OverEntryCeiling {
                needed: 4096,
                ceiling: 1024,
            }),
            "an over-ceiling entry is unverified, not truncated: nobody read it"
        );
    }

    #[test]
    fn the_default_policy_is_recovery_biased() {
        let policy = SalvagePolicy::default();
        assert_eq!(policy.partial, PartialPolicy::Keep);
        assert_eq!(policy.max_entry, MAX_SALVAGE_ENTRY);
        assert!(!policy.strict);
    }

    // -----------------------------------------------------------------
    // Task 4: `verify` dispatch and shadow detection, proven against a
    // mock — same discipline as the rest of this module, since neither
    // mechanism needs to know which format it is annotating.
    // -----------------------------------------------------------------

    /// Reports a fixed, caller-scripted sequence of candidates and answers
    /// `verify` from the SAME script rather than decoding anything — this
    /// module's engine is proven against mocks, and verification/shadow
    /// detection are no exception. Each entry names its own `name` and
    /// `declared_len` (rather than a fixed, offset-derived name) so a test
    /// can freely vary any one of the three fields shadow detection now
    /// requires to agree.
    struct ScriptedCandidates {
        plan: Vec<(&'static str, Option<u64>, Option<Verifier>, SalvageStatus)>,
        next: usize,
    }

    impl SalvageScan for ScriptedCandidates {
        fn next_candidate(
            &mut self,
            _src: &mut dyn SeekRead,
            _from: u64,
        ) -> Result<Option<Candidate>> {
            if self.next >= self.plan.len() {
                return Ok(None);
            }
            let offset = self.next as u64;
            let (name, declared_len, verifier, _) = self.plan[self.next];
            self.next += 1;
            Ok(Some(Candidate {
                offset,
                payload_start: offset,
                meta: EntryMeta::file(name),
                declared_len,
                verifier,
                available_len: None,
                marked_deleted: false,
            }))
        }

        fn verify(&self, _src: &mut dyn SeekRead, candidate: &Candidate) -> Result<SalvageStatus> {
            Ok(self.plan[candidate.offset as usize].3)
        }
    }

    /// `verify` decides each entry's status — the whole point of Task 4:
    /// this used to be a hardcoded `Complete` for every candidate, which was
    /// wrong for any format carrying a real checksum.
    #[test]
    fn verify_decides_each_entrys_status_not_a_hardcoded_default() {
        let mut scan = ScriptedCandidates {
            plan: vec![
                (
                    "a",
                    Some(1),
                    Some(Verifier::Crc32(1)),
                    SalvageStatus::Intact,
                ),
                ("b", Some(1), None, SalvageStatus::Complete),
                (
                    "c",
                    Some(1),
                    Some(Verifier::Crc32(2)),
                    SalvageStatus::Partial,
                ),
            ],
            next: 0,
        };
        let out = salvage_all(&mut scan, &mut bytes(&[0u8; 16]), &SalvagePolicy::default())
            .expect("scripted candidates must annotate cleanly");
        assert_eq!(out.entries[0].status, SalvageStatus::Intact);
        assert_eq!(out.entries[1].status, SalvageStatus::Complete);
        assert_eq!(out.entries[2].status, SalvageStatus::Partial);
    }

    /// A later candidate reporting the SAME name, declared_len AND verifier
    /// as an earlier one is its shadow — pointing at the earliest position,
    /// not merely "some" earlier one.
    #[test]
    fn a_later_candidate_sharing_an_earlier_verifier_is_marked_as_its_shadow() {
        let mut scan = ScriptedCandidates {
            plan: vec![
                (
                    "dup",
                    Some(1),
                    Some(Verifier::Crc32(7)),
                    SalvageStatus::Intact,
                ),
                (
                    "other",
                    Some(1),
                    Some(Verifier::Crc32(9)),
                    SalvageStatus::Intact,
                ),
                (
                    "dup",
                    Some(1),
                    Some(Verifier::Crc32(7)),
                    SalvageStatus::Intact,
                ),
            ],
            next: 0,
        };
        let out = salvage_all(&mut scan, &mut bytes(&[0u8; 16]), &SalvagePolicy::default())
            .expect("scripted candidates must annotate cleanly");
        assert_eq!(out.entries[0].shadows, None);
        assert_eq!(out.entries[1].shadows, None);
        assert_eq!(
            out.entries[2].shadows,
            Some(0),
            "must point at the earliest matching position"
        );
    }

    fn find_all(data: &[u8], sig: &[u8]) -> Vec<u64> {
        let mut search = ForwardSearch::new();
        let mut src = Cursor::new(data.to_vec());
        let len = data.len() as u64;
        let mut from = 0;
        let mut hits = Vec::new();
        while let Some(at) = search
            .find(&mut src, from, len, sig.len(), |w| w == sig)
            .unwrap()
        {
            hits.push(at);
            from = at + 1;
        }
        hits
    }

    fn naive(data: &[u8], sig: &[u8]) -> Vec<u64> {
        (0..=data.len().saturating_sub(sig.len()))
            .filter(|&i| data.len() >= sig.len() && &data[i..i + sig.len()] == sig)
            .map(|i| i as u64)
            .collect()
    }

    #[test]
    fn forward_search_finds_what_a_naive_scan_finds() {
        let sig = b"070701";
        // Hits at 0, near small-chunk boundaries (each `find` restarts at
        // FIRST_CHUNK, so large-chunk straddles are tested separately below),
        // and flush against EOF.
        let mut data = vec![b'x'; 200_000];
        for at in [0usize, 62, 63, 127, 255, 4093, 65_533, 131_070, 199_994] {
            data[at..at + sig.len()].copy_from_slice(sig);
        }
        assert_eq!(find_all(&data, sig), naive(&data, sig));
    }

    #[test]
    fn forward_search_past_eof_and_on_short_input_is_none() {
        let mut search = ForwardSearch::new();
        let mut src = Cursor::new(b"0707".to_vec());
        assert_eq!(search.find(&mut src, 0, 4, 6, |_| true).unwrap(), None);
        assert_eq!(search.find(&mut src, 9, 4, 1, |_| true).unwrap(), None);
    }

    /// A source that returns at most 7 bytes per read.
    struct Trickle(Cursor<Vec<u8>>);
    impl Read for Trickle {
        fn read(&mut self, out: &mut [u8]) -> std::io::Result<usize> {
            let n = out.len().min(7);
            self.0.read(&mut out[..n])
        }
    }
    impl Seek for Trickle {
        fn seek(&mut self, to: SeekFrom) -> std::io::Result<u64> {
            self.0.seek(to)
        }
    }

    #[test]
    fn forward_search_survives_short_reads() {
        let mut data = vec![0u8; 5_000];
        data[4_321..4_327].copy_from_slice(b"070701");
        let mut search = ForwardSearch::new();
        let mut src = Trickle(Cursor::new(data));
        assert_eq!(
            search
                .find(&mut src, 0, 5_000, 6, |w| w == b"070701")
                .unwrap(),
            Some(4_321)
        );
    }

    #[test]
    fn forward_search_no_match_reads_each_byte_once_and_ends_at_eof() {
        use crate::testing::CountingSource;
        let data = vec![b'x'; 200_000];
        let mut src = CountingSource::new(Cursor::new(data));
        let mut search = ForwardSearch::new();
        assert_eq!(
            search
                .find(&mut src, 0, 200_000, 6, |w| w == b"070701")
                .unwrap(),
            None
        );
        assert_eq!(src.bytes_read(), 200_000);
    }

    #[test]
    fn forward_search_no_match_through_short_reads_ends_at_eof() {
        let mut search = ForwardSearch::new();
        let mut src = Trickle(Cursor::new(vec![b'x'; 200_000]));
        assert_eq!(
            search
                .find(&mut src, 0, 200_000, 6, |w| w == b"070701")
                .unwrap(),
            None
        );
    }

    #[test]
    fn forward_search_on_a_truncated_source_ends_at_eof() {
        let mut search = ForwardSearch::new();
        let mut src = Cursor::new(vec![b'x'; 1_000]);
        assert_eq!(
            search
                .find(&mut src, 0, 50_000, 6, |w| w == b"070701")
                .unwrap(),
            None
        );
    }

    #[test]
    fn forward_search_never_looks_past_an_understated_file_len() {
        let mut data = vec![b'x'; 10_000];
        data[5_000..5_006].copy_from_slice(b"070701");
        let mut search = ForwardSearch::new();
        let mut src = Cursor::new(data);
        assert_eq!(
            search
                .find(&mut src, 0, 4_000, 6, |w| w == b"070701")
                .unwrap(),
            None
        );
        // A hit straddling file_len is not "before file_len" either.
        assert_eq!(
            search
                .find(&mut src, 0, 5_003, 6, |w| w == b"070701")
                .unwrap(),
            None
        );
        assert_eq!(
            search
                .find(&mut src, 0, 5_006, 6, |w| w == b"070701")
                .unwrap(),
            Some(5_000)
        );
    }

    #[test]
    fn forward_search_finds_a_hit_straddling_large_chunk_boundaries() {
        let sig = b"070701";
        // Cumulative end offset of each read in one `find` from 0.
        let mut ends = Vec::new();
        let (mut chunk, mut at) = (ForwardSearch::FIRST_CHUNK, 0usize);
        while ends.len() < 14 {
            at += chunk;
            ends.push(at);
            chunk = (chunk * 2).min(ForwardSearch::MAX_CHUNK);
        }
        // The read of MAX_CHUNK / 2 is the last doubling; the next read is
        // the first of MAX_CHUNK size.
        let (mut sizes, mut chunk) = (Vec::new(), ForwardSearch::FIRST_CHUNK);
        for _ in 0..ends.len() {
            sizes.push(chunk);
            chunk = (chunk * 2).min(ForwardSearch::MAX_CHUNK);
        }
        let doubling = ends[sizes
            .iter()
            .position(|&c| c == ForwardSearch::MAX_CHUNK / 2)
            .unwrap()];
        let first_max = ends[sizes
            .iter()
            .position(|&c| c == ForwardSearch::MAX_CHUNK)
            .unwrap()];
        for boundary in [doubling, first_max, first_max + ForwardSearch::MAX_CHUNK] {
            for start in [boundary - 5, boundary - 3, boundary - 1] {
                let mut data = vec![b'x'; boundary + 100];
                data[start..start + sig.len()].copy_from_slice(sig);
                let mut search = ForwardSearch::new();
                let mut src = Cursor::new(data.clone());
                let found = search
                    .find(&mut src, 0, data.len() as u64, sig.len(), |w| w == sig)
                    .unwrap();
                assert_eq!(found, Some(start as u64), "boundary {boundary}");
            }
        }
    }

    #[test]
    fn a_nearby_hit_reads_only_a_few_bytes() {
        use crate::testing::CountingSource;
        let mut data = vec![0u8; 1 << 20];
        data[10..16].copy_from_slice(b"070701");
        let mut src = CountingSource::new(Cursor::new(data));
        let mut search = ForwardSearch::new();
        assert_eq!(
            search
                .find(&mut src, 0, 1 << 20, 6, |w| w == b"070701")
                .unwrap(),
            Some(10)
        );
        assert!(
            src.bytes_read() <= ForwardSearch::FIRST_CHUNK as u64,
            "{}",
            src.bytes_read()
        );
    }

    /// A long signature's first read tests `sig_len` offsets, not one: a
    /// 512-byte signature 300 bytes on is found by ONE read of `2 * 512 - 1`
    /// bytes. With a first read of `sig_len` it took 512 + 1,024.
    #[test]
    fn a_long_signature_s_first_read_tests_sig_len_offsets() {
        use crate::testing::CountingSource;
        let sig = [0xA5u8; 512];
        let mut data = vec![0u8; 1 << 20];
        data[300..812].copy_from_slice(&sig);
        let mut src = CountingSource::new(Cursor::new(data));
        let mut search = ForwardSearch::new();
        assert_eq!(
            search
                .find(&mut src, 0, 1 << 20, 512, |w| w == sig)
                .unwrap(),
            Some(300)
        );
        assert_eq!(src.bytes_read(), 2 * 512 - 1);
    }

    /// Dense hits cost no first read each: what one call read past its
    /// answer is tested by the next without reading it again. A hit every 7
    /// bytes through 1 MiB used to cost 64 bytes read per hit (9x); kept,
    /// the searches read each byte once.
    #[test]
    fn dense_hits_read_each_byte_about_once() {
        use crate::testing::CountingSource;
        let sig = b"070701";
        let mut data = vec![b'x'; 1 << 20];
        for at in (0..data.len() - sig.len()).step_by(7) {
            data[at..at + sig.len()].copy_from_slice(sig);
        }
        let len = data.len() as u64;
        let mut src = CountingSource::new(Cursor::new(data.clone()));
        let mut search = ForwardSearch::new();
        let (mut from, mut hits) = (0, Vec::new());
        while let Some(at) = search
            .find(&mut src, from, len, sig.len(), |w| w == sig)
            .unwrap()
        {
            hits.push(at);
            // A scanner reads its candidate between searches; the kept
            // bytes must survive the source's position moving.
            src.seek(SeekFrom::Start(at)).unwrap();
            let mut header = [0u8; 6];
            src.read_exact(&mut header).unwrap();
            from = at + 1;
        }
        assert_eq!(hits, naive(&data, sig));
        let header_reads = 6 * hits.len() as u64;
        assert!(
            src.bytes_read() - header_reads <= len + ForwardSearch::MAX_CHUNK as u64,
            "searches read {} bytes of a {len}-byte input",
            src.bytes_read() - header_reads
        );
    }

    /// A call starting before what was kept, or past it, still answers
    /// exactly what a fresh search answers.
    #[test]
    fn kept_bytes_never_change_an_answer() {
        let sig = b"070701";
        let mut data = vec![b'x'; 300_000];
        for at in [5usize, 70, 4_000, 70_000, 250_000, 299_994] {
            data[at..at + sig.len()].copy_from_slice(sig);
        }
        let len = data.len() as u64;
        let mut kept = ForwardSearch::new();
        let mut src = Cursor::new(data.clone());
        for from in [
            0u64, 6, 3, 71, 60, 4_001, 200_000, 69_000, 299_995, 250_001, 0,
        ] {
            for file_len in [len, 250_003, 70_006, 4_005] {
                let fresh = ForwardSearch::new()
                    .find(&mut Cursor::new(data.clone()), from, file_len, 6, |w| {
                        w == sig
                    })
                    .unwrap();
                let got = kept
                    .find(&mut src, from, file_len, 6, |w| w == sig)
                    .unwrap();
                assert_eq!(got, fresh, "from {from}, file_len {file_len}");
            }
        }
    }

    /// `find_to_eof` offers the last offsets every byte left, down to
    /// `min_len`, and offers the rest exactly `sig_len`.
    #[test]
    fn find_to_eof_offers_the_tail_what_is_left() {
        let data: Vec<u8> = (0..100u8).collect();
        let mut offered = Vec::new();
        let found = ForwardSearch::new()
            .find_to_eof(&mut Cursor::new(data.clone()), 10, 100, 20, 3, |w| {
                offered.push((w[0], w.len()));
                false
            })
            .unwrap();
        assert_eq!(found, None);
        let expected: Vec<(u8, usize)> = (10u8..=97)
            .map(|at| (at, 20.min(100 - at as usize)))
            .collect();
        assert_eq!(offered, expected);
        // A hit in the tail answers its offset.
        let at = ForwardSearch::new()
            .find_to_eof(&mut Cursor::new(data), 0, 100, 20, 1, |w| w[0] == 95)
            .unwrap();
        assert_eq!(at, Some(95));
    }

    /// Pins `annotate_candidates`' semantics across the Vec -> HashMap change:
    /// a repeat's `collides_with` is the EARLIEST position with its name, and
    /// a non-degenerate same-name/length/verifier repeat shadows the earliest.
    #[test]
    fn annotate_candidates_reports_the_earliest_position_at_scale() {
        let names: Vec<&'static str> = (0..3_000)
            .map(|i| &*Box::leak(format!("f{i}").into_boxed_str()))
            .collect();
        let mut plan = Vec::new();
        for i in 0..3_000usize {
            // Every tenth candidate repeats the name of an original (never a repeat),
            // at position (i % 100) / 10 * 10.
            let name = if i % 10 == 9 {
                names[(i % 100) / 10 * 10]
            } else {
                names[i]
            };
            let declared = if i % 20 == 19 { Some(8) } else { Some(4) };
            // Some repeats carry a different checksum: same name and length
            // but another verifier is a collision, not a shadow.
            let crc = if i % 10 == 9 && (i / 10) % 2 == 0 {
                8
            } else {
                7
            };
            plan.push((
                name,
                declared,
                Some(Verifier::Crc32(crc)),
                SalvageStatus::Intact,
            ));
        }
        let keys: Vec<_> = plan.iter().map(|p| (p.0, p.1, p.2)).collect();
        let mut scan = ScriptedCandidates { plan, next: 0 };
        let out = salvage_all(&mut scan, &mut bytes(&[0u8; 16]), &SalvagePolicy::default())
            .expect("scripted candidates must annotate cleanly");
        assert_eq!(out.entries.len(), 3_000);
        let mut first_triple = HashMap::new();
        let mut first_name = HashMap::new();
        for (i, k) in keys.iter().enumerate() {
            first_triple.entry(*k).or_insert(i);
            first_name.entry(k.0).or_insert(i);
        }
        for (i, e) in out.entries.iter().enumerate() {
            let same_triple = first_triple[&keys[i]];
            let same_name = first_name[keys[i].0];
            let (want_shadow, want_collide) = if same_triple != i {
                (Some(same_triple), None)
            } else if same_name != i {
                (None, Some(same_name))
            } else {
                (None, None)
            };
            assert_eq!(e.shadows, want_shadow, "shadows at {i}");
            assert_eq!(e.collides_with, want_collide, "collides_with at {i}");
        }
        let shadowed = out.entries.iter().filter(|e| e.shadows.is_some()).count();
        let collided = out
            .entries
            .iter()
            .filter(|e| e.collides_with.is_some())
            .count();
        assert!(shadowed > 0 && collided > 0, "{shadowed} {collided}");
    }

    /// A candidate with no verifier at all (a format with no checksum, or a
    /// zip data-descriptor entry) must never be reported as shadowing or
    /// shadowed — there is nothing to measure, so nothing is claimed.
    #[test]
    fn candidates_with_no_verifier_never_shadow_each_other() {
        let mut scan = ScriptedCandidates {
            plan: vec![
                ("a", Some(1), None, SalvageStatus::Complete),
                ("a", Some(1), None, SalvageStatus::Complete),
            ],
            next: 0,
        };
        let out = salvage_all(&mut scan, &mut bytes(&[0u8; 16]), &SalvagePolicy::default())
            .expect("scripted candidates must annotate cleanly");
        assert_eq!(out.entries[0].shadows, None);
        assert_eq!(out.entries[1].shadows, None);
    }

    /// Two candidates whose checksum AND declared_len agree but whose NAME
    /// differs must never be linked — the fix-round requirement that a
    /// checksum match alone is not enough, only the full
    /// `(name, declared_len, verifier)` triple.
    #[test]
    fn a_matching_verifier_under_a_different_name_is_never_marked_as_a_shadow() {
        let mut scan = ScriptedCandidates {
            plan: vec![
                (
                    "one.txt",
                    Some(4),
                    Some(Verifier::Crc32(42)),
                    SalvageStatus::Intact,
                ),
                (
                    "two.txt",
                    Some(4),
                    Some(Verifier::Crc32(42)),
                    SalvageStatus::Intact,
                ),
            ],
            next: 0,
        };
        let out = salvage_all(&mut scan, &mut bytes(&[0u8; 16]), &SalvagePolicy::default())
            .expect("scripted candidates must annotate cleanly");
        assert_eq!(
            out.entries[1].shadows, None,
            "same checksum, different name — not a shadow"
        );
    }

    /// The degenerate case: every empty entry (and, in zip, every directory
    /// entry) checksums to the same fixed constant over zero declared
    /// bytes. Even under the SAME name, a zero-length checksum must never
    /// mark a shadow — the value proves nothing, unlike a real collision.
    #[test]
    fn a_zero_length_declared_verifier_never_shadows_even_under_a_matching_name() {
        let mut scan = ScriptedCandidates {
            plan: vec![
                (
                    "empty.txt",
                    Some(0),
                    Some(Verifier::Crc32(0)),
                    SalvageStatus::Complete,
                ),
                (
                    "empty.txt",
                    Some(0),
                    Some(Verifier::Crc32(0)),
                    SalvageStatus::Complete,
                ),
            ],
            next: 0,
        };
        let out = salvage_all(&mut scan, &mut bytes(&[0u8; 16]), &SalvagePolicy::default())
            .expect("scripted candidates must annotate cleanly");
        assert_eq!(out.entries[0].shadows, None);
        assert_eq!(
            out.entries[1].shadows, None,
            "a zero-byte checksum must never mark a shadow, even under an identical name"
        );
        assert_eq!(
            out.entries[1].collides_with,
            Some(0),
            "the NAME still repeats, and that is a directly observed fact no checksum \
             guard applies to"
        );
    }

    // -----------------------------------------------------------------
    // Name collisions: the second annotation, separate from shadowing.
    // -----------------------------------------------------------------

    /// The finding this annotation closes: two records under one name whose
    /// content does NOT agree are what `stuffr list` calls shadowed, and
    /// what salvage marked in no way at all — because its own `shadows`
    /// means something stricter.
    #[test]
    fn a_repeated_name_with_different_content_is_reported_as_a_collision() {
        let mut scan = ScriptedCandidates {
            plan: vec![
                (
                    "dup.txt",
                    Some(21),
                    Some(Verifier::Crc32(7)),
                    SalvageStatus::Intact,
                ),
                (
                    "other.txt",
                    Some(21),
                    Some(Verifier::Crc32(9)),
                    SalvageStatus::Intact,
                ),
                (
                    "dup.txt",
                    Some(21),
                    Some(Verifier::Crc32(11)),
                    SalvageStatus::Intact,
                ),
            ],
            next: 0,
        };
        let out = salvage_all(&mut scan, &mut bytes(&[0u8; 16]), &SalvagePolicy::default())
            .expect("scripted candidates must annotate cleanly");
        assert_eq!(out.entries[2].shadows, None, "the content does not agree");
        assert_eq!(
            out.entries[2].collides_with,
            Some(0),
            "but the name does, and that is the fact `list` warns about"
        );
        assert_eq!(out.entries[0].collides_with, None);
        assert_eq!(out.entries[1].collides_with, None);
    }

    /// The two annotations are mutually exclusive: a record PROVEN to be a
    /// copy says so, and does not also report the weaker fact. Reporting
    /// both would make every shadow print two markers for one relationship.
    #[test]
    fn a_proven_shadow_is_not_also_reported_as_a_name_collision() {
        let mut scan = ScriptedCandidates {
            plan: vec![
                (
                    "dup.txt",
                    Some(21),
                    Some(Verifier::Crc32(7)),
                    SalvageStatus::Intact,
                ),
                (
                    "dup.txt",
                    Some(21),
                    Some(Verifier::Crc32(7)),
                    SalvageStatus::Intact,
                ),
            ],
            next: 0,
        };
        let out = salvage_all(&mut scan, &mut bytes(&[0u8; 16]), &SalvagePolicy::default())
            .expect("scripted candidates must annotate cleanly");
        assert_eq!(out.entries[1].shadows, Some(0));
        assert_eq!(out.entries[1].collides_with, None);
    }

    /// A third record under a name two earlier ones already used points at
    /// the EARLIEST of them, the same rule `shadows` follows — so a chain of
    /// collisions names one origin rather than each pointing at its
    /// predecessor.
    #[test]
    fn a_third_record_under_one_name_names_the_earliest_position() {
        let mut scan = ScriptedCandidates {
            plan: vec![
                (
                    "dup",
                    Some(4),
                    Some(Verifier::Crc32(1)),
                    SalvageStatus::Intact,
                ),
                (
                    "dup",
                    Some(4),
                    Some(Verifier::Crc32(2)),
                    SalvageStatus::Intact,
                ),
                (
                    "dup",
                    Some(4),
                    Some(Verifier::Crc32(3)),
                    SalvageStatus::Intact,
                ),
            ],
            next: 0,
        };
        let out = salvage_all(&mut scan, &mut bytes(&[0u8; 16]), &SalvagePolicy::default())
            .expect("scripted candidates must annotate cleanly");
        assert_eq!(out.entries[1].collides_with, Some(0));
        assert_eq!(out.entries[2].collides_with, Some(0));
    }

    /// The negative double: distinct names must never be marked, however
    /// much else they share. Without this, an annotation that fired on
    /// everything would pass every test above.
    #[test]
    fn distinct_names_are_never_reported_as_colliding() {
        let mut scan = ScriptedCandidates {
            plan: vec![
                (
                    "one.txt",
                    Some(4),
                    Some(Verifier::Crc32(42)),
                    SalvageStatus::Intact,
                ),
                (
                    "two.txt",
                    Some(4),
                    Some(Verifier::Crc32(42)),
                    SalvageStatus::Intact,
                ),
            ],
            next: 0,
        };
        let out = salvage_all(&mut scan, &mut bytes(&[0u8; 16]), &SalvagePolicy::default())
            .expect("scripted candidates must annotate cleanly");
        assert_eq!(out.entries[0].collides_with, None);
        assert_eq!(out.entries[1].collides_with, None);
    }

    /// A collision needs no verifier at all, unlike a shadow. A format with
    /// no checksum (tar, cpio, ar — and a zip data-descriptor entry) can
    /// still repeat a name, and that repetition is exactly as real there.
    #[test]
    fn a_repeated_name_collides_even_with_no_verifier_to_compare() {
        let mut scan = ScriptedCandidates {
            plan: vec![
                ("same", Some(4), None, SalvageStatus::Complete),
                ("same", Some(4), None, SalvageStatus::Complete),
            ],
            next: 0,
        };
        let out = salvage_all(&mut scan, &mut bytes(&[0u8; 16]), &SalvagePolicy::default())
            .expect("scripted candidates must annotate cleanly");
        assert_eq!(
            out.entries[1].shadows, None,
            "no verifier, so nothing proves they are copies"
        );
        assert_eq!(
            out.entries[1].collides_with,
            Some(0),
            "but the name repeats, which needs no verifier to observe"
        );
    }

    /// Ruling S-I. `Candidate` is `#[non_exhaustive]`, so an out-of-crate
    /// scanner reaches it only through `new` plus the `with_*` setters —
    /// which means the DEFAULTS are now public API, not an implementation
    /// detail of six struct literals. Each of the four must assert the
    /// least: nothing declared, nothing to verify with, nothing missing,
    /// nothing deleted.
    #[test]
    fn a_new_candidate_claims_nothing_it_was_not_told() {
        let c = Candidate::new(7, 42, EntryMeta::file("probe"));
        assert_eq!(c.offset, 7);
        assert_eq!(c.payload_start, 42);
        assert_eq!(c.declared_len, None, "no length was declared");
        assert_eq!(c.verifier, None, "nothing can prove the content");
        assert_eq!(
            c.available_len, None,
            "a shortfall is MEASURED, never assumed"
        );
        assert!(!c.marked_deleted, "no record is deleted until one says so");
    }

    /// The four setters are the only route to those fields from another
    /// crate, so each one is pinned rather than trusted to the compiler.
    #[test]
    fn each_candidate_setter_reaches_its_own_field() {
        let c = Candidate::new(0, 0, EntryMeta::file("probe"))
            .with_declared_len(Some(9))
            .with_verifier(Some(Verifier::Crc16(0xbeef)))
            .with_available_len(Some(4))
            .with_marked_deleted(true);
        assert_eq!(c.declared_len, Some(9));
        assert_eq!(c.verifier, Some(Verifier::Crc16(0xbeef)));
        assert_eq!(c.available_len, Some(4));
        assert!(c.marked_deleted);
    }

    /// Same ruling, same reason, for the type every per-format
    /// `write_payload` test builds directly. Its three defaults are the
    /// annotations `annotate_candidates` adds, so an entry built by hand
    /// must carry none of them.
    #[test]
    fn a_new_salvaged_entry_carries_no_annotations() {
        let e = SalvagedEntry::new(3, 7, 42, EntryMeta::file("probe"), SalvageStatus::Complete);
        assert_eq!(e.scan_position, 3);
        assert_eq!(e.offset, 7);
        assert_eq!(e.payload_start, 42);
        assert_eq!(e.status, SalvageStatus::Complete);
        assert_eq!(e.shadows, None);
        assert_eq!(e.collides_with, None);
        assert!(!e.marked_deleted);

        let annotated = SalvagedEntry::new(0, 0, 0, EntryMeta::file("p"), SalvageStatus::Intact)
            .with_shadows(Some(1))
            .with_collides_with(Some(2))
            .with_marked_deleted(true);
        assert_eq!(annotated.shadows, Some(1));
        assert_eq!(annotated.collides_with, Some(2));
        assert!(annotated.marked_deleted);
    }

    /// 0.10.4: a log stores at most its cap per (format, shape, kind), and
    /// the count it keeps is exact.
    #[test]
    fn a_log_stores_at_most_the_cap_per_group_and_counts_the_rest() {
        let mut log = SightingLog::with_cap(4);
        for off in 0..10u64 {
            log.push(Sighting::verdict_bounded(FormatId::new("zip"), off, "x"));
        }
        log.push(Sighting::new(FormatId::new("zip"), 99, "y"));
        assert_eq!(
            log.count(FormatId::new("zip"), "x", SightingKind::VerdictBounded),
            10
        );
        let out = log.into_sightings();
        let x: Vec<_> = out.iter().filter(|s| s.shape == "x").collect();
        assert_eq!(x.iter().map(|s| s.offset).collect::<Vec<_>>(), [0, 1, 2, 3]);
        assert_eq!(x.iter().map(|s| s.more).sum::<u64>(), 6);
        assert_eq!(x.last().unwrap().more, 6);
        assert_eq!(out.iter().filter(|s| s.shape == "y").count(), 1);
    }

    /// 0.10.4: capping never changes the sentence a caller prints.
    #[test]
    fn capping_keeps_the_printed_sentence_identical() {
        let all: Vec<Sighting> = (0..500u64)
            .map(|o| Sighting::verdict_bounded(FormatId::new("zip"), o * 3, "x"))
            .chain((0..20u64).map(|o| Sighting::new(FormatId::new("tar"), o, "y")))
            .collect();
        let mut log = SightingLog::new();
        for s in all.clone() {
            log.push(s);
        }
        assert_eq!(
            describe_sightings(&log.into_sightings()),
            describe_sightings(&all)
        );
    }

    /// 0.10.4: the printed sentence is identical capped and uncapped for
    /// every cap from [`SIGHTING_OFFSETS_SHOWN`] up, over 1000 deterministic
    /// inputs that interleave formats, shapes and kinds.
    #[test]
    fn capping_keeps_the_sentence_identical_across_random_inputs() {
        let mut state = 0x9E37_79B9_7F4A_7C15u64;
        let mut next = move || {
            state ^= state << 13;
            state ^= state >> 7;
            state ^= state << 17;
            state
        };
        let formats = [FormatId::new("zip"), FormatId::new("tar")];
        let shapes = ["x", "y", "z"];
        let kinds = [
            SightingKind::Ungateable,
            SightingKind::WorkBounded,
            SightingKind::VerdictBounded,
        ];
        for _ in 0..1000 {
            let len = (next() % 300) as usize;
            let all: Vec<Sighting> = (0..len)
                .map(|_| {
                    let r = next();
                    let s = Sighting::new(
                        formats[(r % 2) as usize],
                        (r >> 8) % 100_000,
                        shapes[((r >> 2) % 3) as usize],
                    );
                    Sighting {
                        kind: kinds[((r >> 4) % 3) as usize],
                        ..s
                    }
                })
                .collect();
            for cap in [8, 9, 64] {
                let mut log = SightingLog::with_cap(cap);
                for s in all.clone() {
                    log.push(s);
                }
                assert_eq!(
                    describe_sightings(&log.into_sightings()),
                    describe_sightings(&all),
                    "cap {cap}, {len} sightings"
                );
            }
        }
    }

    /// Task 2-N: the note a caller prints for its sightings. None for none —
    /// a run with nothing refused must print nothing — and otherwise one
    /// group per (format, shape), each with its complete count and at most
    /// [`SIGHTING_OFFSETS_SHOWN`] offsets, in the order first seen.
    #[test]
    fn describe_sightings_groups_by_shape_and_bounds_what_it_lists() {
        assert_eq!(describe_sightings(&[]), None);

        let f = FormatId::new("fmt");
        let mut seen: Vec<Sighting> = (0..10u64)
            .map(|i| Sighting::new(f, i * 512, "a(s)"))
            .collect();
        seen.insert(1, Sighting::new(f, 7, "b(s)"));
        let note = describe_sightings(&seen).unwrap();
        assert!(
            note.contains("10 fmt a(s) at offset(s) 0, 512, 1024, 1536, 2048, 2560, 3072, 3584, and 2 more; and 1 fmt b(s) at offset(s) 7"),
            "{note}"
        );
        assert!(note.contains("`stuffr list`"), "{note}");
    }

    /// 0.10.3: a work-bounded sighting has its own sentence, and an
    /// ungateable one keeps its sentence word for word — alone or alongside.
    #[test]
    fn describe_sightings_words_a_work_bounded_sighting_apart() {
        let f = FormatId::new("fmt");
        let old = describe_sightings(&[Sighting::new(f, 0, "a(s)")]).unwrap();
        assert_eq!(
            old,
            "this build's salvage scanner saw 1 fmt a(s) at offset(s) 0 — each with the \
             structure of a header, but in a shape it has no gate for, so none is listed or \
             recovered; `stuffr list` and `stuffr unpack` may read these headers normally, or \
             name the variant they are in, and it is the SCAN that stops there"
        );
        let bounded = describe_sightings(&[Sighting::work_bounded(f, 9, "b(s)")]).unwrap();
        assert!(bounded.contains("1 fmt b(s) at offset(s) 9"), "{bounded}");
        assert!(!bounded.contains("no gate for"), "{bounded}");
        assert!(bounded.contains("bounds the work"), "{bounded}");
        // Fix round 1: true for a genuine header starved by forgeries
        // elsewhere, and for a scan that goes on past it.
        assert!(bounded.contains("the scan went on past them"), "{bounded}");
        assert!(!bounded.contains("forged"), "{bounded}");
        assert!(!bounded.contains("SCAN that stops"), "{bounded}");
        let both = describe_sightings(&[
            Sighting::work_bounded(f, 9, "b(s)"),
            Sighting::new(f, 0, "a(s)"),
        ])
        .unwrap();
        assert_eq!(both, format!("{old}; and separately, {bounded}"));
    }

    /// 0.10.3 Task 4b: a verdict-bounded sighting has a third sentence —
    /// not the extension-chain one, which would be false of a zip name —
    /// and the other two keep their words beside it.
    #[test]
    fn describe_sightings_words_a_verdict_bounded_sighting_apart() {
        let f = FormatId::new("fmt");
        let old = describe_sightings(&[Sighting::new(f, 0, "a(s)")]).unwrap();
        let bounded = describe_sightings(&[Sighting::work_bounded(f, 9, "b(s)")]).unwrap();
        let verdict = describe_sightings(&[Sighting::verdict_bounded(f, 7, "c(s)")]).unwrap();
        assert_eq!(
            verdict,
            "this build's salvage scanner bounds the work it spends judging candidate headers \
             across the whole scan, and did not judge 1 fmt c(s) at offset(s) 7 — so \
             whatever those headers describe is not listed or recovered there, though the scan \
             went on past them; `stuffr list` and `stuffr unpack` may read these headers normally"
        );
        assert!(!verdict.contains("extension chains"), "{verdict}");
        let all = describe_sightings(&[
            Sighting::verdict_bounded(f, 7, "c(s)"),
            Sighting::work_bounded(f, 9, "b(s)"),
            Sighting::new(f, 0, "a(s)"),
        ])
        .unwrap();
        assert_eq!(
            all,
            format!("{old}; and separately, {bounded}; and separately, {verdict}")
        );
    }

    /// Task 4b: the budget is exactly `2 × file_len + 32 KiB`, a charge
    /// that lands on the limit fits, and one past it is refused WHOLE —
    /// nothing is charged, so a later, smaller charge can still fit.
    #[test]
    fn a_scan_budget_spends_to_its_exact_limit_and_refuses_past_it() {
        let limit = 2 * 1000 + 32 * 1024;
        let mut budget = ScanBudget::for_input(1000);
        assert!(budget.try_spend(limit - 10));
        assert_eq!(budget.spent(), limit - 10);
        assert!(!budget.try_spend(11), "one byte past the limit");
        assert_eq!(budget.spent(), limit - 10, "a refusal charges nothing");
        assert!(budget.try_spend(10), "exactly to the limit");
        assert_eq!(budget.spent(), limit);
        assert!(!budget.try_spend(1));
        assert_eq!(budget.spent(), limit);
    }

    /// Spending zero always fits, even on a spent budget, and a charge whose
    /// sum overflows `u64` is a refusal, never a wrap.
    #[test]
    fn a_scan_budget_takes_zero_and_refuses_an_overflowing_charge() {
        let mut budget = ScanBudget::for_input(0);
        assert!(budget.try_spend(0));
        assert_eq!(budget.spent(), 0);
        assert!(budget.try_spend(ScanBudget::SLACK));
        assert!(budget.try_spend(0), "zero fits a spent budget");
        assert!(!budget.try_spend(u64::MAX));
        assert_eq!(budget.spent(), ScanBudget::SLACK);

        let mut huge = ScanBudget::for_input(u64::MAX);
        assert!(huge.try_spend(u64::MAX), "the limit saturates at u64::MAX");
        assert!(!huge.try_spend(1), "and a sum past it does not wrap");
        assert_eq!(huge.spent(), u64::MAX);
    }

    /// Task 4: the walk-stop note. A hole says what the brief requires —
    /// the entries after it are unreachable by construction, NOT absent,
    /// with the offset and the byte count — and a cut-short tail says the
    /// opposite, because nothing can be hiding in too few bytes for a record.
    #[test]
    fn describe_walk_stop_says_unreachable_for_a_hole_and_complete_for_a_cut() {
        let f = FormatId::new("fmt");
        let hole = describe_walk_stop(&WalkStop::new(
            f,
            1234,
            5000,
            WalkStopKind::Unreadable,
            "bad field",
        ));
        for needle in [
            "offset 1234",
            "5000 bytes",
            "bad field",
            "unreachable by construction",
            "not absent",
            "fmt",
        ] {
            assert!(hole.contains(needle), "missing {needle:?}: {hole}");
        }
        let cut = describe_walk_stop(&WalkStop::new(f, 90, 1, WalkStopKind::CutShort, "eof"));
        assert!(cut.contains("1 byte into the record at offset 90"), "{cut}");
        assert!(cut.contains("cut short"), "{cut}");
        assert!(!cut.contains("unreachable"), "{cut}");
        let shape = describe_walk_stop(&WalkStop::new(
            f,
            8,
            600,
            WalkStopKind::UnsupportedShape,
            "the symbol table",
        ));
        assert!(shape.contains("the symbol table"), "{shape}");
        assert!(shape.contains("not evidence of damage"), "{shape}");
        assert!(!shape.contains("unreachable by construction"), "{shape}");
    }
}