tilezz 0.2.0

//! The decision cascades: compose detectors + minters into a verdict.
//!
//! ONE funnel executor ([`run_stages`]: run a tile down a `Vec<Stage>` until a
//! stage settles it), TWO policies as data over the same stage constructors:
//!
//! - [`fast_stages`] -- the fast screen's funnel, swept over a whole
//!   perimeter by [`run_fast`](crate::classify::classify_tiles::run_fast).
//! - [`deep_stages`] -- the `--deep` residue funnel ([`classify`] is
//!   `run_stages` over it): cheap accepts, ONE full-budget Heesch reject,
//!   expensive accepts, else Undecided (reusing the reject's banked witness).
//!
//! POLICY NOTE (intentional divergence, measured on the n<=10..13 runs): the
//! two tables order accepts/rejects differently (--fast screens with cheap
//! escalating rejects, iso before aniso; --deep pays one full-budget reject
//! between the cheap and expensive accepts, aniso before iso) and probe the
//! torus detector at different depths -- --fast grows once at depth
//! `torus_coronas` (3) and once at `torus_coronas + 1` in its torus-deep
//! stage; the --deep cheap accepts try depths 2..=3 and the deep accepts
//! 4..=torus_coronas. Each ordering was tuned for its residue mix (--fast
//! sees everything, --deep sees the non-tiler-heavy remainder); do not
//! "unify" the tables without re-measuring. The DETECTOR and MINTER logic
//! behind both is single-sourced (the `*_pc` fns here and
//! [`mint`](crate::classify::mint)).

use serde::{Deserialize, Serialize};

use crate::classify::aniso::tiles_anisohedral_restart;
use crate::classify::cert::{Classified, PeriodicCert, Verdict};
use crate::classify::conway::build_tiling;
use crate::classify::heesch::{Heesch, heesch_number_witnessed};
use crate::classify::isohedral::isohedral_tiling;
use crate::classify::mint::{cert_from_cluster, cert_from_tiling, heesch_cert, torus_cert};
use crate::classify::tiling::{DETECT_ORBIT_CAP, ORBIT_RADIUS_FACTOR};
use crate::cyclotomic::IsRing;
use crate::geom::matches::PatchMatch;
use crate::geom::rat::Rat;
use crate::geom::tileset::TileSet;

// ---------------------------------------------------------------------------
// Periodic-acceptance provenance and coverage bounds.
//
// The detectors (Conway, isohedral, anisohedral cluster, torus cover) all answer
// the SAME question -- "does the tile have a connected k-tile translation
// fundamental cell?" -- but each is a faster, partial detector of it, so the
// combined search is SOUND (every positive is constructively verified) but NOT
// complete: "not periodic" only means "none found within `AcceptBounds`", never
// "none exists". The detect-and-mint driver is [`certify_periodic`].
// ---------------------------------------------------------------------------

/// Which detector certified periodicity. Every variant is a *proof* (each
/// positive is constructively verified); they differ only in how complete the
/// detector is, noted per variant.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
pub enum PeriodicVia {
    /// Conway boundary criterion -- sufficient for translation/half-turn
    /// tilings with palindromic side arcs (p2-style).
    Conway,
    /// Beauquier-Nivat boundary factorization -- COMPLETE for tilings by
    /// pure translation (p1), including offset brick walls whose bumpy
    /// translate-pair arcs the Conway criterion cannot express.
    Translation,
    /// Edge-gluing isohedral search -- complete for single-orbit, edge-to-edge
    /// p3/p4/p6 within the build budget.
    Isohedral,
    /// A `k`-copy cluster tiles (Conway on the cluster) -- sound, incomplete.
    Anisohedral(usize),
    /// A patch-derived `k`-tile torus domain -- sound, incomplete (the grower
    /// can jam before exposing the lattice).
    Torus(usize),
}

/// The explicit **coverage bound** for the periodic detectors
/// ([`certify_periodic`] and the fast pass's stages): the search
/// looks no further than these limits, so a "not periodic" is bounded by them,
/// not absolute.
#[derive(Debug, Clone, Copy)]
pub struct AcceptBounds {
    /// Isohedral involutions to try (>= the involution count is exhaustive).
    pub iso_builds: usize,
    /// Largest anisohedral cluster size, and breadth kept per size.
    pub aniso_kmax: usize,
    pub aniso_cap: usize,
    /// DETERMINISTIC ceiling on clusters examined PER SEARCH (0 = unlimited). Same
    /// budget => same verdict, every run. NOTE: this is a per-*search* budget, so
    /// with `aniso_restarts > 1` the total work bound is `aniso_restarts *
    /// aniso_budget` (one big budget vs many small restarts is the caller's
    /// choice: --fast uses one large budget, `restarts = 1`; the --deep residue
    /// uses a small `aniso_budget` with many `restarts`).
    pub aniso_budget: usize,
    /// Seeded restarts for the anisohedral search: `<= 1` is the plain
    /// deterministic search (`aniso_budget` clusters, one order), `> 1` runs that
    /// many restarts of `aniso_budget` clusters each with different seeds. The
    /// search is heavy-tailed (a tiling cluster surfaces early under some seeds),
    /// so restarts certify a hard tile far faster, bounded by
    /// `aniso_restarts * aniso_budget`.
    pub aniso_restarts: usize,
    /// Largest torus domain size, and corona depth grown to find its lattice.
    pub torus_kmax: usize,
    pub torus_coronas: usize,
}

impl Default for AcceptBounds {
    /// The bounds validated on the n<=10 sweep: isohedral exhaustive for
    /// n<=10 (`T(10)=9496`), torus domains up to 12 tiles.
    fn default() -> Self {
        AcceptBounds {
            iso_builds: 20_000,
            // aniso_kmax 3->4 (2026-06-28): one notch too tight -- n11 tile 104492
            // tiles with a 4-copy cluster (needs kmax>=4); 4 also covers p4. The
            // residue recert uses a higher kmax for p6.
            aniso_kmax: 4,
            aniso_cap: 4_000,
            // Examined-cluster ceiling. >= what kmax<=4 explores (so the
            // validated n<=10 behaviour is unchanged) yet bounds the high-kmax
            // residue search to minutes instead of hours. Calibrated below.
            aniso_budget: 300_000,
            // Deterministic single search by default (--fast unchanged); the
            // residue pass opts into restarts.
            aniso_restarts: 1,
            torus_kmax: 12,
            // 3 coronas already hold several translation cells -- enough for the
            // recurrence detector to read off any domain up to torus_kmax. Deeper
            // growth only adds (super-linear) cost, not lattice information: at
            // depth 5 the hard specimens cost ~100x more for the same verdict.
            torus_coronas: 3,
        }
    }
}

// ---------------------------------------------------------------------------
// Stage building blocks -- the ONE place each detector is turned into a
// settle-or-pass check. A check settles a tile only when it also MINTS a
// verifying cert (a detector that fires but cannot mint returns None, so later
// stages get their chance); each stamps the cert's `via` provenance.
// ---------------------------------------------------------------------------

fn periodic_verdict(pc: PeriodicCert) -> Classified {
    Classified::Decided(Verdict::Periodic(pc))
}

// --- One detect-and-mint pipeline PER DETECTOR, `Option<PeriodicCert>`-shaped.
// Both tables compose these: [`fast_stages`] wraps them in accept() stages,
// and the certify_periodic_* cascades (the --deep accept sub-orders) chain
// them directly -- so each detector -> minter composition exists exactly once.
// (Before this they were written twice and had already drifted.)

/// Beauquier-Nivat p1 detect + mint: instant boundary factorization, each
/// candidate lattice minted as a k=1 corona self-glue (verify-gated). THE
/// brick-wall detector: complete for pure-translation tilings, microseconds
/// per tile, no patch growth -- immune to the rosette-grain trap that blinds
/// the torus detector on these shapes.
fn bn_pc<T: IsRing>(seq: &[i8]) -> Option<PeriodicCert> {
    let base = Rat::<T>::from_slice_trusted(seq);
    crate::classify::conway::bn_criterion::<T>(seq)
        .into_iter()
        .find_map(|(v1, v2)| crate::classify::mint::translation_cert(&base, v1, v2))
}

/// Conway p1/p2 detect + mint: instant criterion, minted from its constructed
/// tiling as a k=1 corona self-glue.
fn conway_pc<T: IsRing>(seq: &[i8]) -> Option<PeriodicCert> {
    let base = Rat::<T>::from_slice_trusted(seq);
    let tiling = build_tiling::<T>(
        seq,
        ORBIT_RADIUS_FACTOR * seq.len() as f64,
        DETECT_ORBIT_CAP,
    )?;
    cert_from_tiling(&base, &tiling, PeriodicVia::Conway)
}

/// Torus cover detect + mint at one corona depth: one grow, then a k=1
/// self-glue or a k>1 carve (any fundamental cell -- rotation-carrying or not
/// -- tiles by translation of the cell). `None` if the patch does not expose
/// the lattice at this depth or the carve fails.
fn torus_pc<T: IsRing>(seq: &[i8], kmax: usize, coronas: usize) -> Option<PeriodicCert> {
    torus_cert::<T>(&Rat::<T>::from_slice_trusted(seq), kmax, coronas)
}

/// Isohedral p3/p4/p6 edge-gluing search + mint, bounded by `iso_builds`.
fn iso_pc<T: IsRing>(seq: &[i8], bounds: &AcceptBounds) -> Option<PeriodicCert> {
    let base = Rat::<T>::from_slice_trusted(seq);
    let tiling = isohedral_tiling::<T>(
        seq,
        ORBIT_RADIUS_FACTOR * seq.len() as f64,
        DETECT_ORBIT_CAP,
        bounds.iso_builds,
    )?;
    cert_from_tiling(&base, &tiling, PeriodicVia::Isohedral)
}

/// Anisohedral k-copy cluster search (seeded restarts when
/// `bounds.aniso_restarts > 1`) + META-tile mint from the cluster witness --
/// the k>1 self-glue the torus k=1 minter cannot produce.
fn aniso_pc<T: IsRing>(seq: &[i8], bounds: &AcceptBounds) -> Option<PeriodicCert> {
    let w = tiles_anisohedral_restart::<T>(
        seq,
        bounds.aniso_kmax,
        bounds.aniso_cap,
        bounds.aniso_budget,
        bounds.aniso_restarts,
    )?;
    cert_from_cluster::<T>(
        &Rat::<T>::from_slice_trusted(seq),
        &w.build,
        &w.tiling,
        PeriodicVia::Anisohedral(w.k),
    )
}

// ---------------------------------------------------------------------------
// The shared funnel: stages as data, ONE executor for both modes.
//
// A funnel is a Vec<Stage> run by [`run_stages`] until a stage settles the
// tile; --fast and --deep differ only in their table ([`fast_stages`] /
// [`deep_stages`]) and in the driver that feeds tiles in (windowed dafsa
// sweep vs store-residue rewrite, in classify_tiles.rs).
// ---------------------------------------------------------------------------

/// Whether a stage accepts (mints a periodic cert) or rejects (mints a
/// cannot-tile cert). Used to select stages per [`StageMode`].
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum StageKind {
    Accept,
    Reject,
}

impl StageKind {
    pub fn selected_by(self, mode: StageMode) -> bool {
        match self {
            StageKind::Accept => mode.runs_accepts(),
            StageKind::Reject => mode.runs_rejects(),
        }
    }
}

/// One stage's outcome for one tile.
pub enum StageOutcome {
    /// The stage settled the tile (a minted, verifying cert).
    Settled(Classified),
    /// Nothing to say; the tile continues down the funnel.
    Pass,
    /// A Heesch stage that did not exhaust: the tile continues, but the
    /// search's outcome + deepest banked corona witness travel with it, so
    /// the funnel's terminal Undecided verdict reuses them -- the A2/A3
    /// contract (depth is WITNESSED; a search that already ran is never
    /// re-run).
    PassWitnessed(Heesch, Vec<PatchMatch>),
}

/// A stage's boxed check: one tile's turn sequence in, a [`StageOutcome`] out.
pub type StageCheck = Box<dyn Fn(&[i8]) -> StageOutcome + Sync>;

/// A named settle-or-pass check over one tile: the unit both funnels are
/// composed from.
pub struct Stage {
    pub name: &'static str,
    pub kind: StageKind,
    pub check: StageCheck,
}

/// An accept stage from a detect-and-mint pipeline (`Some(cert)` settles).
fn accept(name: &'static str, f: impl Fn(&[i8]) -> Option<PeriodicCert> + Sync + 'static) -> Stage {
    let check = move |s: &[i8]| match f(s) {
        Some(pc) => StageOutcome::Settled(periodic_verdict(pc)),
        None => StageOutcome::Pass,
    };
    Stage {
        name,
        kind: StageKind::Accept,
        check: Box::new(check),
    }
}

/// A Heesch reject stage: settles iff the search EXHAUSTS (finite Heesch, a
/// sound cannot-tile); a bound- or budget-limited outcome passes the tile on
/// WITH the search's banked witness. As the last stage of a funnel this is
/// the terminal settler: [`run_stages`] turns the passed-on witness into the
/// Undecided verdict.
fn reject<T: IsRing>(name: &'static str, bound: usize, budget: usize) -> Stage {
    let check = move |s: &[i8]| {
        let base = Rat::<T>::from_slice_trusted(s);
        let (h, build) = heesch_number_witnessed(TileSet::single(base.clone()), 0, bound, budget);
        if h.cannot_tile() {
            StageOutcome::Settled(Classified::Decided(Verdict::CannotTile(heesch_cert(
                &base, h, build, bound, budget,
            ))))
        } else {
            StageOutcome::PassWitnessed(h, build)
        }
    };
    Stage {
        name,
        kind: StageKind::Reject,
        check: Box::new(check),
    }
}

/// The corona depth a non-reject Heesch outcome actually witnessed (its
/// banked corona replays to exactly this many rings).
fn witnessed_depth(h: Heesch) -> usize {
    match h {
        Heesch::AtLeast(b) => b,
        Heesch::Unknown(k) | Heesch::Finite(k) => k,
    }
}

/// THE funnel executor, shared by both modes: run `seq` down `stages` (those
/// selected by `mode`) until one settles it. A tile no stage settles is
/// Undecided, reusing the DEEPEST corona witness any Heesch stage banked
/// (later stages win ties). NOTE this can out-witness a terminal reject whose
/// budget is smaller than an earlier stage's (fast_stages: heesch2 searches
/// 1M nodes, deep-heesch 500k, so a tile whose 2-corona costs between the
/// two records depth 2 from heesch2) -- the verdict is always the best
/// witnessed truth of the whole funnel, never just the last search's. If no
/// Heesch stage ran (e.g. `PeriodicOnly`), a cheap bounded witness is grown
/// fresh ([`undecided`]).
pub fn run_stages<T: IsRing>(seq: &[i8], stages: &[Stage], mode: StageMode) -> Classified {
    let mut bank: Option<(Heesch, Vec<PatchMatch>)> = None;
    for stage in stages.iter().filter(|st| st.kind.selected_by(mode)) {
        match (stage.check)(seq) {
            StageOutcome::Settled(c) => return c,
            StageOutcome::Pass => {}
            StageOutcome::PassWitnessed(h, build) => {
                if bank
                    .as_ref()
                    .is_none_or(|(bh, _)| witnessed_depth(h) >= witnessed_depth(*bh))
                {
                    bank = Some((h, build));
                }
            }
        }
    }
    match bank {
        Some((h, build)) => undecided_witnessed(h, build),
        None => undecided::<T>(seq, UNDECIDED_WITNESS_BOUND, UNDECIDED_WITNESS_BUDGET),
    }
}

// ---------------------------------------------------------------------------
// The two policies, as data. Both are pure composition over the SAME accept()
// / reject() stage constructors and *_pc pipelines; only order, depths and
// budgets differ -- see the POLICY NOTE in the module docs before touching
// either.
// ---------------------------------------------------------------------------

/// --fast Heesch reject budgets (node ceilings). Genuine low-Heesch non-tilers
/// reject well under these; the ceiling only bounds the rare grinder, which then
/// defers to the --deep residue pass. Raising a budget only shifts hard tiles from
/// `--deep` into --fast, never changes a verdict.
const H2_BUDGET: usize = 1_000_000; // bound-2 bulk reject (settles Heesch 0/1/2)
const H3_BUDGET: usize = 200_000; // bound-3 prefilter ahead of the accepts

/// The --fast (fast screen) funnel: cheap rejects cut the non-tiler majority
/// first, THEN the periodic accepts run on the residue, then the deep rejects.
/// Two principles keep it fast (measured on the n=10 funnel): (1) every accept
/// precedes the deep Heesch reject, so a rotational periodic is never ground
/// through a deep Heesch search (heesch3 between torus and aniso once cost
/// ~15-70s/perimeter of pure waste); (2) every budget is SMALL -- a tile the
/// cheap stages cannot settle falls to Undecided and `--deep` crunches it. Do
/// NOT raise the budgets to "finish" hard tiles here: --fast must stay a fast
/// filter over millions of tiles.
pub fn fast_stages<T: IsRing>(
    b: AcceptBounds,
    deep_torus_kmax: usize,
    deep_bound: usize,
    deep_budget: usize,
) -> Vec<Stage> {
    // torus-deep mints at a higher kmax + one more corona than the shallow pass;
    // both grow the patch once and mint at their OWN depth (so a deep-only cover
    // actually mints, not just detects).
    let deep = AcceptBounds {
        torus_kmax: deep_torus_kmax,
        torus_coronas: b.torus_coronas + 1,
        ..b
    };
    vec![
        accept("conway", |s| conway_pc::<T>(s)),
        // BN right after Conway: both are microsecond boundary tests; between
        // them they cover palindromic-arc p1/p2 AND every pure-translation
        // brick wall (learned at n=14 -- 27 fast-pass survivors were BN tiles).
        accept("bn", |s| bn_pc::<T>(s)),
        // Bulk reject: Heesch to bound 2 rejects Heesch 0 AND 1 too (a preceding
        // bound-1 pass would be redundant -- bound 2 subsumes it at the same cost).
        // Cuts the non-tiler bulk before the accepts run.
        reject::<T>("heesch2", 2, H2_BUDGET),
        // torus first among accepts: cheapest sound accepter (a single shallow
        // corona grow, ~0.1-0.5s/tile). A cover whose carve fails (a rotational
        // domain) returns None here, so the tile continues to iso/aniso.
        accept("torus", move |s| {
            torus_pc::<T>(s, b.torus_kmax, b.torus_coronas)
        }),
        // iso before aniso: it is the cheaper detector and catches a DIFFERENT set
        // (p3/p4/p6 single-tile) that aniso cannot, so running it first removes the
        // iso-periodics from aniso's grind list.
        accept("iso", move |s| iso_pc::<T>(s, &b)),
        // aniso mints a META-tile cert from its own cluster witness (the k>1
        // self-glue the torus k=1 minter cannot produce); settles only on a mint.
        // Bounded to aniso_budget examined clusters (restarts = 1 in the fast pass): a
        // cluster not found cheaply defers to --deep's seeded restarts, so aniso
        // never grinds long on the non-tilers / iso-periodics it cannot detect.
        accept("aniso", move |s| aniso_pc::<T>(s, &b)),
        // torus-deep: large-period catcher on the tiny residue the cheap torus /
        // iso / aniso missed (an n=13 period-18 tile needed it).
        accept("torus-deep", move |s| {
            torus_pc::<T>(s, deep.torus_kmax, deep.torus_coronas)
        }),
        // heesch3 (bound 3, cheap H3_BUDGET): the residue now is non-tilers the
        // accepts left behind, so this rejects genuine Heesch-3 non-tilers without
        // grinding any periodic (they were skimmed off above).
        reject::<T>("heesch3", 3, H3_BUDGET),
        // deep-heesch (bound 6): the real deep reject, on the last residue only.
        // As the terminal stage it settles every tile it sees -- CannotTile on a
        // finite exhaustion, else run_stages turns its banked witness into the
        // Undecided verdict.
        reject::<T>("deep-heesch", deep_bound, deep_budget),
    ]
}

/// The --deep (`--deep` residue) funnel -- [`classify`] documents the order's
/// rationale. The accept sub-orders are [`certify_periodic_cheap`] and
/// [`certify_periodic_deep`] (single-sourced there for their standalone
/// callers); the reject between them runs ONCE at the full budget.
pub fn deep_stages<T: IsRing>(bounds: AcceptBounds, hbound: usize, hbudget: usize) -> Vec<Stage> {
    vec![
        accept("cheap-accepts", move |s| {
            certify_periodic_cheap::<T>(s, &bounds)
        }),
        reject::<T>("heesch", hbound, hbudget),
        accept("deep-accepts", move |s| {
            certify_periodic_deep::<T>(s, &bounds)
        }),
    ]
}

/// Fallback Undecided-witness bound/budget, for the funnels where NO Heesch
/// search ran (the `PeriodicOnly` mode): a cheap bounded
/// attempt to keep SOME corona witness for the candidate. Where a Heesch
/// search did run, [`undecided_witnessed`] reuses its banked witness instead
/// and these are irrelevant.
pub const UNDECIDED_WITNESS_BOUND: usize = 3;
pub const UNDECIDED_WITNESS_BUDGET: usize = 100_000;

/// Build the [`Classified::Undecided`] verdict straight from a finished Heesch
/// search's outcome: [`heesch_number_witnessed`] banked the deepest gap-free
/// corona witness DURING the search, so the witnessed depth and its corona come
/// for free -- no re-search. `AtLeast(b)` witnessed `b` coronas; `Unknown(k)`
/// closed `k` before the budget hit. A `Finite` outcome is a settled reject and
/// never reaches here (debug-asserted; still recorded truthfully if it does).
pub fn undecided_witnessed(h: Heesch, corona: Vec<PatchMatch>) -> Classified {
    debug_assert!(
        !h.cannot_tile(),
        "Finite is a settled reject, not Undecided"
    );
    Classified::Undecided {
        depth: witnessed_depth(h),
        corona,
    }
}

/// Build the [`Classified::Undecided`] verdict by growing a FRESH corona
/// witness at `target` -- the fallback for paths where no Heesch search ran.
/// Truthful by construction: on success the recorded depth is `target` (the
/// witness replays to it); if no `target`-corona surrounding is found within
/// `budget`, it records depth 0 with an empty corona -- never an unwitnessed
/// claim. (Callers that already ran a Heesch search should use
/// [`undecided_witnessed`] and pay nothing.)
pub fn undecided<T: IsRing>(seq: &[i8], target: usize, budget: usize) -> Classified {
    let ts = TileSet::single(Rat::<T>::from_slice_trusted(seq));
    match crate::classify::heesch::corona_witness(&ts, 0, target, budget) {
        Some(corona) => Classified::Undecided {
            depth: target,
            corona,
        },
        None => Classified::Undecided {
            depth: 0,
            corona: Vec::new(),
        },
    }
}

/// Which verdict-half the decision cascade pursues. `Full` tries both (accept a
/// periodic cert, else reject via Heesch); the restricted modes chase only one
/// half and leave everything else `Undecided` -- for when you already know what
/// to expect (e.g. a deep pass over a residue you believe is all periodic, or a
/// reject-only sweep of a block you expect to be non-tilers). Orthogonal to the
/// fast/deep mode split: it selects WHICH stages run, not how hard they search.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub enum StageMode {
    /// Periodic accepts + Heesch rejects -- the full cascade.
    #[default]
    Full,
    /// Only the periodic-accept stages (Conway / torus / aniso / iso).
    PeriodicOnly,
    /// Only the Heesch-reject stages.
    HeeschOnly,
}

impl StageMode {
    /// Whether the periodic-accept stages run.
    pub fn runs_accepts(self) -> bool {
        matches!(self, StageMode::Full | StageMode::PeriodicOnly)
    }
    /// Whether the Heesch-reject stages run.
    pub fn runs_rejects(self) -> bool {
        matches!(self, StageMode::Full | StageMode::HeeschOnly)
    }
}

/// Classify a tile and mint its certificate. The order is a funnel tuned for the
/// `--deep` RESIDUE (which is non-tiler-heavy: the fast classification already caught the
/// easy periodics), and it runs the Heesch reject exactly ONCE:
///   1. cheap periodic accepts -- [`certify_periodic_cheap`] (Conway + shallow
///      torus): catch the common periodics up front, cheap even when they miss.
///   2. Heesch reject (once, full budget) -- [`heesch_number_witnessed`] up to `hbound`.
///      Placed before the EXPENSIVE accepts so a non-tiler is rejected here at its
///      true proof cost, not first ground through aniso restarts / torus-deep.
///   3. expensive periodic accepts -- [`certify_periodic_deep`] (aniso / iso /
///      deep torus): only the rare rotational / large-period periodic that
///      survives both the cheap accepts AND the reject reaches here.
///   4. otherwise undecided.
///
/// `mode` restricts which halves run (see [`StageMode`]): `PeriodicOnly` skips the
/// Heesch reject (a non-periodic tile falls straight to `Undecided`), `HeeschOnly`
/// skips both accept steps (pure reject).
pub fn classify<T: IsRing>(
    seq: &[i8],
    bounds: &AcceptBounds,
    hbound: usize,
    hbudget: usize,
    mode: StageMode,
) -> Classified {
    run_stages::<T>(seq, &deep_stages::<T>(*bounds, hbound, hbudget), mode)
}

/// Mint a verifying [`PeriodicCert`] for a tile, CHEAPEST-BOUNDED-FIRST, tagging
/// the winner's [`PeriodicVia`] (provenance -- which algorithm proved it):
///
/// 1. Conway p1/p2 -- an instant boundary test.
/// 2. Torus at SHALLOW coronas (2..=3) -- both cheap (ms to sub-second). The cert
///    is a fundamental-domain carve that self-glues by pure TRANSLATION of the
///    cell -- and since ANY fundamental cell tiles by translation, this covers
///    rotation-carrying domains too (tile 626002 certifies here as a k=4 cell of
///    four orientations; 4173 k=4, 12814 k=1, ~15ms-350ms). It misses only when
///    the shallow patch does not expose the lattice.
/// 3. Anisohedral cluster -- bounded by `aniso_budget` * `aniso_restarts`, the
///    catcher for small-cluster meta-tiles whose lattice hides from the shallow
///    patch (self-glues via a constructed tiling, rotations included: tile 2551
///    k=6, <1s). Genuine hits exit early; a miss costs the (bounded) budget.
/// 4. Isohedral p3/p4/p6 -- bounded by the involution build budget.
/// 5. Deep torus (coronas 4..=torus_coronas) LAST -- the only unbounded step (its
///    grow can take ~a minute on a frustrated tile), a last resort for large-k
///    translational domains a shallow patch buries (the period-18 tile at k=14);
///    reached only when everything cheaper/bounded has missed.
///
/// Each branch mints through its own verify-gated path, so a positive is always
/// a replayable cert. (Torus/aniso have OPPOSITE cost profiles -- torus grows
/// expensively and misses when the patch hides the lattice, aniso searches
/// expensively and misses deep-translational cells -- so this order keeps the
/// unbounded deep-torus grow last and the bounded aniso search ahead of it,
/// which measured fastest across the n<=13 residue.)
///
/// This is the full cascade; [`classify`] runs the two halves separately so the
/// Heesch reject can sit between them -- steps 1-2 are [`certify_periodic_cheap`]
/// (cheap, run before the reject) and steps 3-5 are [`certify_periodic_deep`]
/// (expensive, run after).
pub fn certify_periodic<T: IsRing>(seq: &[i8], bounds: &AcceptBounds) -> Option<PeriodicCert> {
    certify_periodic_cheap::<T>(seq, bounds).or_else(|| certify_periodic_deep::<T>(seq, bounds))
}

/// The CHEAP periodic accepts (steps 1-2): Conway p1/p2 (instant) and shallow
/// torus (coronas 2..=3, ~ms to sub-second). These catch the common periodics,
/// and are cheap even when they miss, so [`classify`] runs them BEFORE the Heesch
/// reject -- a periodic is thus never ground through a deep Heesch search. The
/// returned cert carries its provenance in [`PeriodicCert::via`].
pub fn certify_periodic_cheap<T: IsRing>(
    seq: &[i8],
    bounds: &AcceptBounds,
) -> Option<PeriodicCert> {
    // 1. Conway p1/p2: instant, minted from its constructed tiling.
    if let Some(pc) = conway_pc::<T>(seq) {
        return Some(pc);
    }
    // 1b. Beauquier-Nivat p1: instant, the brick-wall class Conway misses.
    if let Some(pc) = bn_pc::<T>(seq) {
        return Some(pc);
    }
    // 2. Torus at SHALLOW coronas (2..=3): both cheap, catch translational domains
    //    whose lattice shows at either depth. (c=4+ is the deep grower, in _deep.)
    // The cert carries via = Torus(k), stamped by the minter (k = meta-tile size).
    for c in 2..=3.min(bounds.torus_coronas.max(2)) {
        if let Some(pc) = torus_pc::<T>(seq, bounds.torus_kmax, c) {
            return Some(pc);
        }
    }
    None
}

/// The EXPENSIVE periodic accepts (steps 3-5): anisohedral clusters (seeded
/// restarts), isohedral p3/p4/p6, and deep torus (coronas 4+, the unbounded
/// grower). Each is fruitless-but-costly on a non-tiler (aniso searches, torus
/// grows), so [`classify`] runs these AFTER the Heesch reject -- only the rare
/// rotational / large-period periodic that survives both the cheap accepts and
/// the reject reaches here. (Torus and aniso have opposite cost profiles, so the
/// bounded aniso search precedes the unbounded deep-torus grow: measured fastest
/// across the n<=13 residue.)
pub fn certify_periodic_deep<T: IsRing>(seq: &[i8], bounds: &AcceptBounds) -> Option<PeriodicCert> {
    // 3. Anisohedral cluster (bounded, seeded restarts): rotational / small-cluster
    //    meta-tiles. Restarts make hard (heavy-tailed) clusters fast + bounded.
    if let Some(pc) = aniso_pc::<T>(seq, bounds) {
        return Some(pc);
    }
    // 4. Isohedral p3/p4/p6: bounded involution build.
    if let Some(pc) = iso_pc::<T>(seq, bounds) {
        return Some(pc);
    }
    // 5. Deep torus (coronas 4..=torus_coronas): the unbounded grower, only for
    //    large-k translational domains a shallow patch buries (period-18 at k=14).
    for c in 4..=bounds.torus_coronas {
        if let Some(pc) = torus_pc::<T>(seq, bounds.torus_kmax, c) {
            return Some(pc);
        }
    }
    None
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::classify::cert::{HeeschStatus, Verdict};
    use crate::cyclotomic::ZZ12;
    use crate::geom::tiles;

    /// An Undecided verdict keeps the deepest corona witness (the largest known
    /// patch) so an aperiodic candidate's structure survives, and round-trips
    /// through serde. Uses the n=13 tile that surrounds AtLeast(12).
    #[test]
    fn undecided_keeps_corona_witness() {
        let c = undecided::<ZZ12>(&[-4, 0, 2, 0, 4, 0, 0, 2, 0, 2, 0, 4, 2], 3, 5_000_000);
        match &c {
            Classified::Undecided { depth, corona } => {
                assert_eq!(*depth, 3);
                assert!(!corona.is_empty(), "kept a non-empty corona witness");
            }
            other => panic!("expected Undecided, got {other:?}"),
        }
        let js = serde_json::to_string(&c).unwrap();
        assert_eq!(
            serde_json::from_str::<Classified>(&js).unwrap(),
            c,
            "serde round-trip"
        );
    }

    /// An Undecided built from a finished Heesch search reuses that SAME
    /// search's banked witness: the recorded depth is what the search actually
    /// reached, and the witness replays (count_coronas) to exactly that depth.
    /// Guards the A2/A3 contract -- depth is a WITNESSED lower bound, never the
    /// requested bound.
    #[test]
    fn undecided_witnessed_reuses_search_witness() {
        use crate::classify::heesch::count_coronas;
        // The triangle (a tiler) reaches any small bound: AtLeast(2).
        let tri = Rat::<ZZ12>::from_snake_trusted(&tiles::triangle());
        let ts = TileSet::single(tri.clone());
        let (h, build) = heesch_number_witnessed(ts, 0, 2, 5_000_000);
        assert_eq!(h, Heesch::AtLeast(2));
        match undecided_witnessed(h, build) {
            Classified::Undecided { depth, corona } => {
                assert_eq!(depth, 2);
                assert_eq!(
                    count_coronas(&tri, &corona),
                    2,
                    "witness replays to the recorded depth"
                );
            }
            other => panic!("expected Undecided, got {other:?}"),
        }
    }

    /// The fallback witness grower claims only what it witnessed: a target the
    /// tile cannot reach (the dodecagon cannot even be surrounded once) records
    /// depth 0 with an empty corona -- never the unreached target.
    #[test]
    fn undecided_fallback_never_overclaims() {
        let dodec = Rat::<ZZ12>::from_snake_trusted(&tiles::dodecagon());
        let c = undecided::<ZZ12>(dodec.seq(), 2, 200_000);
        assert_eq!(
            c,
            Classified::Undecided {
                depth: 0,
                corona: vec![]
            }
        );
    }

    /// classify routes tiles to the right certified verdict: a tiler to
    /// Periodic (cert verifies), a non-surroundable tile to CannotTile Heesch 0,
    /// a finite-Heesch tile to CannotTile Heesch k (witness verifies >= k).
    /// Heavy (a deep bound-2 Heesch exhaustion on the finite tile), hence opt-in.
    #[test]
    #[ignore = "integration: full classify across the three verdict kinds (~80s)"]
    fn classify_routes_to_certified_verdicts() {
        use crate::cyclotomic::ZZ12;
        let b = AcceptBounds::default();

        // Periodic tiler.
        let tri = Rat::<ZZ12>::from_snake_trusted(&tiles::triangle());
        match classify::<ZZ12>(tri.seq(), &b, 2, 20_000_000, StageMode::Full) {
            Classified::Decided(Verdict::Periodic(pc)) => {
                assert!(pc.verify(&tri));
            }
            other => panic!("triangle should be Periodic, got {other:?}"),
        }

        // Cannot tile, Heesch 0 (dodecagon).
        let dodec = Rat::<ZZ12>::from_snake_trusted(&tiles::dodecagon());
        match classify::<ZZ12>(dodec.seq(), &b, 2, 200_000, StageMode::Full) {
            Classified::Decided(Verdict::CannotTile(hc)) => {
                assert_eq!(hc.heesch, 0);
                assert!(hc.verify_lower_bound(&dodec));
            }
            other => panic!("dodecagon should be CannotTile(0), got {other:?}"),
        }

        // Cannot tile, finite Heesch 1.
        let t1 = [-2i8, 1, 4, -1, 4, -1, 2, -1, 5, 1];
        match classify::<ZZ12>(&t1, &b, 2, 20_000_000, StageMode::Full) {
            Classified::Decided(Verdict::CannotTile(hc)) => {
                assert_eq!((hc.heesch, hc.status), (1, HeeschStatus::Finite));
                assert!(hc.verify_lower_bound(&Rat::<ZZ12>::from_slice_trusted(&t1)));
            }
            other => panic!("[-2,1,4,...] should be CannotTile(1), got {other:?}"),
        }
    }

    /// Minting is REPRODUCIBLE: certifying the same tile repeatedly yields a
    /// byte-identical cert. Guards the FxHashMap + sorted-disps/domain_reps work
    /// in torus.rs -- with std's random-seeded HashMap the chosen cover (and thus
    /// the whole cert) varied run to run.
    #[test]
    fn certify_periodic_is_deterministic() {
        use crate::cyclotomic::ZZ12;
        let bounds = AcceptBounds {
            torus_coronas: 4,
            ..AcceptBounds::default()
        };
        // A k>1 carve tile (the interesting case -- the cover lattice is read off
        // a HashMap-grouped patch) and a plain translational one.
        let tri = Rat::<ZZ12>::from_snake_trusted(&tiles::triangle());
        for seq in [&[-2i8, -1, 2, 5, -2, 1, 2, 1, 2, 4][..], tri.seq()] {
            let first = certify_periodic::<ZZ12>(seq, &bounds).expect("mints");
            let a = serde_json::to_string(&first).unwrap();
            for _ in 0..3 {
                let pc = certify_periodic::<ZZ12>(seq, &bounds).expect("mints");
                assert_eq!(pc.via, first.via, "{seq:?}: via stable");
                assert_eq!(
                    serde_json::to_string(&pc).unwrap(),
                    a,
                    "{seq:?}: cert byte-identical across runs"
                );
            }
        }
    }

    /// certify_periodic tags the cert with the detector that proved it, and picks
    /// the expected detector per tile: p2 -> Conway, a translational domain ->
    /// Torus, a rotational cluster -> Anisohedral. Guards both the provenance and
    /// the cheapest-first ordering.
    #[test]
    fn certify_periodic_tags_provenance() {
        use crate::cyclotomic::ZZ12;
        let bounds = AcceptBounds {
            torus_coronas: 4,
            ..AcceptBounds::default()
        };
        let tri = Rat::<ZZ12>::from_snake_trusted(&tiles::triangle());
        // 626002 pins the per-class gold check: its patch proposes hybrid
        // mixed-rotation covers that the old single-tile check ACCEPTED (they
        // then only failed at the carve, dropping the tile to Anisohedral(2)).
        // The per-class check rejects those, and the first genuine cover -- a
        // k=4 cell of four orientations -- carves and certifies at the cheaper
        // torus stage. A regression back to Anisohedral(2) here means the
        // gold check got weaker again.
        let cases: [(&[i8], PeriodicVia); 4] = [
            (tri.seq(), PeriodicVia::Conway), // triangle, p2
            (&[-2, -1, 2, 5, -2, 1, 2, 1, 2, 4], PeriodicVia::Torus(3)), // 14280, k=3 carve
            (
                &[-3, 2, 2, 2, -2, 3, 1, 3, -3, 2, 2, 3],
                PeriodicVia::Torus(4),
            ), // 626002, 4-orientation cell
            // n=14 brick wall (idx 20729692): pure translation, Conway-negative
            // (bumpy non-palindromic arcs), rosette-prone under the torus
            // grower -- ONLY the BN stage catches it cheaply.
            (
                &[-4, 0, 4, 0, 2, 2, -2, 0, 4, 2, -2, 0, 4, 2],
                PeriodicVia::Translation,
            ),
        ];
        for (seq, want) in cases {
            let pc =
                certify_periodic::<ZZ12>(seq, &bounds).unwrap_or_else(|| panic!("{seq:?}: mints"));
            assert_eq!(pc.via, want, "{seq:?}: cert carries its via");
            assert!(
                pc.verify(&Rat::<ZZ12>::from_slice_trusted(seq)),
                "{seq:?}: verifies"
            );
        }
    }
}