tilezz 0.2.0

//! Certificates of a screened tile's verdict.
//!
//! A verdict is only useful if you can hand it to someone else and have them
//! re-check it without redoing the search. These types are that hand-off: a
//! small, purely combinatorial recipe that, replayed against the base tile,
//! reproduces the geometry that justifies the verdict.
//!
//! # Why the certs carry no coordinates
//!
//! Everything here is a sequence of [`PatchMatch`] / [`TileMatch`] -- pairs of
//! `usize` edge indices, nothing more. There are no ring elements, no `Iso`,
//! no lattice. The base tile (recovered from the dataset by its DAFSA index)
//! supplies all the geometry; each match is a purely local instruction ("glue
//! the new tile's edge range here"), and the absolute placement it forces is
//! recomputed on replay. So a cert is reproducible and content-addressable,
//! and it stays correct under any reindexing the patch machinery does
//! internally.
//!
//! # The two halves of the screen
//!
//! [`PeriodicCert`] is an NP-witness that a tile **tiles the plane
//! periodically**: replay `build` to assemble one fundamental domain (a
//! meta-tile of `k` base copies), then `glue` is the self-gluing rule that
//! grows that domain by pure translation, unboundedly, with no search. Cheap
//! to verify (local checks, no detector re-run) and cheap to grow.
//!
//! [`HeeschCert`] is the **cannot-tile** half. Its `build` is a sample
//! gap-free `k`-corona -- a cheap witness that the (true) Heesch number is at
//! least `k`. The matching upper half ("and no `k+1`-corona exists") is
//! co-NP: there is no small witness for it, so we record the search outcome
//! ([`HeeschStatus::Finite`] = exhausted within budget, a sound reject) rather
//! than a proof, plus the parameters needed to reproduce the search.

use serde::{Deserialize, Serialize};

use crate::classify::cascade::PeriodicVia;
use crate::classify::grow;
use crate::classify::heesch::count_coronas;
use crate::classify::lattice::{
    basis_inverse, lattice_classes, lattice_from_orbit, signature_groups,
};
use crate::classify::torus::gold_check;
use crate::cyclotomic::IsRing;
use crate::cyclotomic::geometry::float::norm_f;
use crate::cyclotomic::geometry::{area_eq_k_area, covol_eq_m_areas};
use crate::geom::iso::{Iso, build_orbit, cryst_order, gluing_iso};
use crate::geom::matches::{PatchMatch, TileMatch};
use crate::geom::patch::{BasicPatch, boundary_vertices};
use crate::geom::rat::Rat;

/// Verification-orbit placement cap: bounds the [`PeriodicCert::verify`] orbit
/// even when a malformed glue proposes a non-discrete group (the checks below
/// then fail on the truncated orbit -- reject, never hang).
const VERIFY_ORBIT_CAP: usize = 3_000;

/// Verification-orbit radius factors, in meta-tile extents plus a flat pad;
/// rationale on [`orbit_radius`], the one consumer.
const VERIFY_RADIUS_EXTENTS: f64 = 16.0;
const VERIFY_RADIUS_PAD: f64 = 30.0;

/// Replay ceiling: no legitimate cert's `build` comes near this (meta-tiles
/// are tens of tiles, the deepest corona witnesses low thousands). A hostile
/// store line with a huge recipe is rejected up front instead of stalling
/// `--verify` in a very long replay (fail closed, like gold_check's reach
/// guards).
const REPLAY_CAP: usize = 100_000;

/// Replay a `build` recipe against `base` (see [`grow::replay_recipe`], the one
/// place the replay protocol lives): seed a patch on the base tile, glue
/// `build[0]`, then `add_tile` the rest in order. Returns the assembled patch,
/// or `None` if the recipe is empty or oversized ([`REPLAY_CAP`]) or any glue
/// fails (an invalid / mismatched recipe, or one replayed against the wrong
/// base). The base must be presented
/// in the same frame the recipe was captured in (lex-min canonical, tile 0).
fn replay_build<T: IsRing>(build: &[PatchMatch], base: &Rat<T>) -> Option<BasicPatch<T>> {
    if build.is_empty() || build.len() > REPLAY_CAP {
        return None;
    }
    grow::replay_recipe(base, build, |_, _| true)
}

/// A certificate that the base tile tiles the plane periodically.
///
/// Picture one fundamental domain -- a *meta-tile* of `k` base copies fused
/// along shared edges -- that paves the plane by translation alone. `build`
/// is the recipe that assembles that meta-tile from a single base copy;
/// `glue` is the rule that clones it across the translation lattice.
///
/// - `build`: replayed in order from a [`crate::geom::patch::BasicPatch`] on
///   the base tile (`grow(build[0])`, then `add_tile(build[1..])`). Each
///   [`PatchMatch`] is keyed on the *transient* growing-patch boundary, so the
///   order matters and the sequence must be replayed from the seed -- it is
///   not an order-free set.
/// - `glue`: the meta-tile's self-gluing rule. Each [`TileMatch`] is keyed on
///   stable shape-edges (both sides carry tile ids), so `glue` is an
///   order-free, reusable rule. Every boundary edge of the meta-tile appears
///   in exactly one `glue` entry; the translation each entry forces is
///   determined by its matched edges, and those translations generate the
///   lattice (derived on demand, never stored).
///
/// `glue` present <=> the tile tiles: this is the structural content of the
/// certificate.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct PeriodicCert {
    /// Assemble the meta-tile (k base copies) from the base tile; replay in order.
    pub build: Vec<PatchMatch>,
    /// The meta-tile self-gluing rule (unbounded translation growth, no search).
    pub glue: Vec<TileMatch>,
    /// Which detector proved periodicity (provenance): Conway / Torus(k) /
    /// Anisohedral(k) / Isohedral. Set at mint time by every path.
    pub via: PeriodicVia,
}

impl PeriodicCert {
    /// Replay `build` to assemble the meta-tile patch (k base copies). The
    /// patch's [`BasicPatch::to_rat`] is the meta-tile shape. `None` if the
    /// recipe is invalid for `base`.
    pub fn reconstruct<T: IsRing>(&self, base: &Rat<T>) -> Option<BasicPatch<T>> {
        replay_build(&self.build, base)
    }

    /// Decompose the meta-tile boundary into complementary glued arcs. Returns,
    /// per meta boundary edge, the index of its arc-PAIR: the two arcs that glue
    /// to each other (a `glue` translation or half-turn) share an index. This is
    /// the boundary's pairing into complementary pieces -- consecutive edges stay
    /// in one arc while their glued partners stay consecutive. `None` if the
    /// recipe does not replay against `base`.
    pub fn boundary_arc_pairs<T: IsRing>(&self, base: &Rat<T>) -> Option<Vec<usize>> {
        let n = self
            .reconstruct(base)?
            .boundary_positions()
            .len()
            .checked_sub(1)?;
        if n == 0 {
            return Some(Vec::new());
        }
        // partner[e] = the boundary edge glued to edge e (single-edge glue).
        let mut partner = vec![usize::MAX; n];
        for tm in &self.glue {
            let (a, b) = (tm.a.range.start_offset, tm.b.range.start_offset);
            if a < n && b < n {
                partner[a] = b;
                partner[b] = a;
            }
        }
        // Edges e and e+1 share an arc iff their partners are adjacent (|diff|==1).
        let same_arc = |e: usize| -> bool {
            let (p, q) = (partner[e], partner[(e + 1) % n]);
            p != usize::MAX && q != usize::MAX && ((p + 1) % n == q || (q + 1) % n == p)
        };
        let brk = (0..n).find(|&e| !same_arc(e)).unwrap_or(0);
        let mut arc_of = vec![0usize; n];
        let mut cur = 0usize;
        for k in 0..n {
            let e = (brk + 1 + k) % n;
            arc_of[e] = cur;
            if !same_arc(e) {
                cur += 1;
            }
        }
        // Pair each arc with the arc holding its partner edges; share a color.
        let mut arc_color = vec![usize::MAX; cur + 1];
        let mut ncol = 0usize;
        for e in 0..n {
            let a = arc_of[e];
            if arc_color[a] == usize::MAX && partner[e] != usize::MAX {
                arc_color[a] = ncol;
                arc_color[arc_of[partner[e]]] = ncol;
                ncol += 1;
            }
        }
        Some(
            (0..n)
                .map(|e| arc_color[arc_of[e]].min(ncol.saturating_sub(1)))
                .collect(),
        )
    }
}

/// Whether a Heesch search ran to exhaustion or merely to its budget.
///
/// [`Finite`](HeeschStatus::Finite) is the load-bearing one: the search proved
/// no deeper corona exists, so the recorded number is the exact Heesch number
/// and the cannot-tile verdict is sound. [`Unknown`](HeeschStatus::Unknown)
/// means the budget ran out first, so the number is only a lower bound and the
/// verdict is not yet a proof.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
pub enum HeeschStatus {
    /// Search exhausted within budget: the number is exact, the reject is sound.
    Finite,
    /// Budget hit before exhaustion: the number is a lower bound only.
    Unknown,
}

/// A record of the base tile's (true, gap-free) Heesch number.
///
/// The cheap half is `build`: a sample gap-free `heesch`-corona surrounding,
/// which any verifier can replay to confirm Heesch >= `heesch`. The expensive
/// half -- that no `heesch + 1` corona exists -- is co-NP and has no small
/// witness, so we keep the search outcome (`status`) and its parameters
/// (`bound`, `budget`) instead of a proof. A [`HeeschStatus::Finite`] status
/// with `heesch < bound` is a sound proof the tile cannot tile the plane
/// single-chirally: the exhaustion covers edge-to-edge tilings, and the
/// edge-to-edge reduction theorem (`docs/math/edge-to-edge-reduction.md`) extends
/// that to all tilings; see the [`classify`](crate::classify) module
/// docs for the scope statement.
///
/// `build` is empty exactly when `heesch == 0` (nothing to witness) -- the
/// number search banks the deepest corona witness for free in the same pass.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct HeeschCert {
    /// The true (gap-free) Heesch number reached.
    pub heesch: u8,
    /// Exhausted (sound) vs budget-limited (lower bound only).
    pub status: HeeschStatus,
    /// A sample gap-free `heesch`-corona surrounding; empty = number only.
    pub build: Vec<PatchMatch>,
    /// The corona bound the search ran to.
    pub bound: u8,
    /// The node budget the search ran under.
    pub budget: u32,
}

impl HeeschCert {
    /// Replay `build` to assemble the sample gap-free `heesch`-corona patch
    /// (for presentation / lower-bound verification). `None` if `build` is
    /// empty (number-only cert) or invalid for `base`.
    pub fn reconstruct<T: IsRing>(&self, base: &Rat<T>) -> Option<BasicPatch<T>> {
        replay_build(&self.build, base)
    }

    /// Cheaply confirm the lower bound: replay `build` and check it surrounds
    /// the base tile at least `heesch` times -- a sound proof the Heesch number
    /// is `>= heesch`. An empty build only confirms `heesch == 0`. The matching
    /// upper bound (no deeper corona exists) is co-NP and lives in `status`, not
    /// re-verified here.
    pub fn verify_lower_bound<T: IsRing>(&self, base: &Rat<T>) -> bool {
        count_coronas(base, &self.build) >= self.heesch as usize
    }
}

/// The settled verdict for a tile. Absence from the store is the third,
/// implicit state ("undecided / not yet resolved") -- there is deliberately no
/// `Undecided` variant here, so a stored verdict is always a real conclusion.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub enum Verdict {
    /// Tiles the plane periodically (NP-witness: reconstruct + grow).
    Periodic(PeriodicCert),
    /// Cannot tile the plane (finite Heesch) -- or a lower bound if budget-limited.
    /// SCOPE: single chirality (rotations only, no reflections), and the jump
    /// from "no edge-to-edge tiling" to "no tiling" rests on the edge-to-edge
    /// reduction (docs/math/edge-to-edge-reduction.md). See the module docs.
    CannotTile(HeeschCert),
}

/// The base tile's own vertices in the seed frame (turtle from origin).
pub(crate) fn base_verts<T: IsRing>(base: &Rat<T>) -> Vec<T> {
    boundary_vertices::<T>(base.seq())
}

/// The meta-tile of a `build` recipe in the SEED frame: its boundary vertex
/// coordinates, its boundary turn sequence, and the tile-copy count `k`. An
/// empty `build` is the translation-monotile case (k = 1, meta-tile = base).
/// `None` if the recipe fails to replay.
///
/// Seed frame (not the canonical lex-min rotation): replaying `build` is
/// deterministic, so mint and verify get byte-identical boundaries, and the
/// `glue` edge indices line up. Crucially this lets us reuse the detector's
/// seed-frame lattice directly -- no canonical-frame re-derivation.
pub(crate) fn meta_of<T: IsRing>(
    build: &[PatchMatch],
    base: &Rat<T>,
) -> Option<(Vec<T>, Vec<i8>, usize)> {
    if build.is_empty() {
        return Some((base_verts(base), base.seq().to_vec(), 1));
    }
    let gp = replay_build(build, base)?;
    let k = gp.next_tile_id(); // number of placed tile instances
    let bp = gp.boundary_positions(); // n+1 entries, closing vertex repeated
    let verts = bp[..bp.len() - 1].to_vec();
    let seq = gp.angles().to_vec();
    Some((verts, seq, k))
}

impl PeriodicCert {
    /// Cheap soundness check (no detector re-run). Replay `build` to get
    /// the meta-tile, read `glue` as the isometries that place its neighbours,
    /// grow the orbit those isometries generate, and prove that orbit is a
    /// periodic tiling: it carries two independent pure translations (a
    /// lattice), the meta-tile's translation cosets within it tile the lattice
    /// cell (covolume == #cosets * meta area == #cosets * k * base area), and
    /// the central meta-tile is exactly surrounded (the exact [`gold_check`]).
    ///
    /// The glue pairs edges by translation OR half-turn (`gluing_iso` reads the
    /// rotation off the edge directions), so this certifies p1 translation
    /// monotiles and p2 half-turn tilings with the same machinery -- a p2 tile
    /// needs no 2-copy meta-tile, just half-turn glue on its own boundary.
    pub fn verify<T: IsRing>(&self, base: &Rat<T>) -> bool {
        let Some((meta_verts, meta_seq, k)) = meta_of(&self.build, base) else {
            return false;
        };
        let Some(gens) = glue_isometries(&self.glue, &meta_verts) else {
            return false;
        };
        let orbit = build_orbit(
            &meta_verts,
            &gens,
            orbit_radius(&meta_verts),
            VERIFY_ORBIT_CAP,
        );
        let Some((v1, v2)) = lattice_from_orbit(&orbit) else {
            return false;
        };
        let Some(inv) = basis_inverse(&v1, &v2) else {
            return false;
        };
        let domain = coset_reps(&orbit, &meta_verts, v1, v2, &inv);
        // THE MULTIPLICITY GATE, exact (see torus.rs's Soundness section): the
        // per-class gold check below proves a constant-multiplicity covering;
        // these two exact ring identities -- one lattice cell holds `#cosets`
        // meta-tiles of `k` base copies each -- force multiplicity 1. Both are
        // integer-coefficient equalities in the ring, no float tolerance.
        if !covol_eq_m_areas(v1, v2, &meta_verts, domain.len())
            || !area_eq_k_area(&meta_verts, &base_verts(base), k)
        {
            return false;
        }
        gold_check(&meta_verts, &meta_seq, &domain, v1, v2)
    }

    /// Grow the tiling with no search: apply the glue isometries (and inverses)
    /// breadth-first from the meta-tile, out to `radius`, capped at `cap`.
    /// Returns the placements (a translation `rot == 0`, a half-turn `rot ==
    /// turn/2`). `None` if the cert is malformed. (No production consumer yet
    /// -- a renderer/explorer would be one; the mint tests exercise it. Kept
    /// `pub` as the natural "consume the cert" API, like `heesch_cert_for`.)
    pub fn grow<T: IsRing>(&self, base: &Rat<T>, radius: f64, cap: usize) -> Option<Vec<Iso<T>>> {
        let (meta_verts, _seq, _k) = meta_of(&self.build, base)?;
        let gens = glue_isometries(&self.glue, &meta_verts)?;
        Some(build_orbit(&meta_verts, &gens, radius, cap))
    }
}

/// The neighbour-placing isometries of a meta-tile's self-gluing rule. Each
/// `glue` entry pairs one meta boundary edge with the edge of the neighbour
/// abutting it; [`gluing_iso`] turns that into the placement -- a translation
/// when the edges are anti-parallel, a half-turn when parallel. Each isometry
/// and its inverse are returned, so [`build_orbit`] generates the whole group.
/// `None` if an entry is malformed or names a non-crystallographic rotation.
fn glue_isometries<T: IsRing>(glue: &[TileMatch], meta_verts: &[T]) -> Option<Vec<Iso<T>>> {
    let mut gens = Vec::with_capacity(glue.len() * 2);
    for tm in glue {
        // Meta-tile glue lives over a single-tile TileSet, so both sides must
        // name tile_id 0 (the "meta-tile itself" sentinel -- meaning 3 of the
        // overload documented on geom::matches::Segment) and be single-edge.
        if tm.a.tile_id != 0 || tm.b.tile_id != 0 || tm.a.range.len != 1 || tm.b.range.len != 1 {
            return None;
        }
        let g = gluing_iso(meta_verts, tm.a.range.start_offset, tm.b.range.start_offset)?;
        cryst_order::<T>(g.rot)?;
        gens.push(g);
        gens.push(g.inv());
    }
    Some(gens)
}

/// One representative per translation coset present in `orbit`: two placements
/// share a coset when their placed tiles have equal orientation signature and
/// anchors differing by a lattice vector. The shared coset partition
/// ([`lattice_classes`]) keeps each class's first-seen member, so the reps sit
/// near the origin of the breadth-first orbit.
fn coset_reps<T: IsRing>(
    orbit: &[Iso<T>],
    meta_verts: &[T],
    v1: T,
    v2: T,
    inv: &[[f64; 2]; 2],
) -> Vec<Iso<T>> {
    let groups = signature_groups(orbit, meta_verts);
    lattice_classes(&groups, v1, v2, inv)
        .into_iter()
        .map(|(_, iso)| iso)
        .collect()
}

/// Build radius for the verification orbit: many meta-tile extents -- enough to
/// expose two independent translations and every coset even for a large (k up to
/// ~12) fundamental cell, while staying cheap (the orbit is just `Iso`
/// composition, and the `cap` bounds it).
fn orbit_radius<T: IsRing>(meta_verts: &[T]) -> f64 {
    let maxn = meta_verts.iter().map(norm_f).fold(0.0_f64, f64::max);
    maxn * VERIFY_RADIUS_EXTENTS + VERIFY_RADIUS_PAD
}

/// Outcome of classifying one tile: a settled [`Verdict`] (Periodic or
/// CannotTile, with a certificate), or the single unsettled state the classification must
/// surface rather than silently drop. There is no "periodic but uncertified"
/// state: the carve + seeded-restart minters certify every periodic tile a
/// detector finds, so a detector that fires always yields a replayable cert.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub enum Classified {
    /// Settled with a certificate.
    Decided(Verdict),
    /// Neither periodic-accepted nor finite-Heesch within the bounds searched --
    /// an aperiodic CANDIDATE. Carries `depth` (the surrounded-corona lower bound
    /// actually WITNESSED -- `corona` replays to exactly that many coronas) and
    /// `corona` (the deepest corona witness, the largest known patch) so the
    /// candidate's structure is preserved for inspection rather than discarded.
    /// `depth == 0` with an empty corona means nothing was witnessed.
    Undecided {
        depth: usize,
        corona: Vec<PatchMatch>,
    },
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::geom::matches::{EdgeRange, Segment};
    use crate::geom::tiles;
    use crate::geom::tileset::TileSet;

    fn sample_periodic() -> PeriodicCert {
        PeriodicCert {
            build: vec![
                PatchMatch::new(EdgeRange::new(0, 1), Segment::new(1, EdgeRange::new(3, 1))),
                PatchMatch::new(EdgeRange::new(2, 2), Segment::new(2, EdgeRange::new(5, 2))),
            ],
            glue: vec![TileMatch::new(
                Segment::new(0, EdgeRange::new(1, 2)),
                Segment::new(1, EdgeRange::new(4, 2)),
            )],
            via: PeriodicVia::Anisohedral(3),
        }
    }

    #[test]
    fn periodic_cert_round_trips() {
        let cert = sample_periodic();
        let json = serde_json::to_string(&cert).unwrap();
        let back: PeriodicCert = serde_json::from_str(&json).unwrap();
        assert_eq!(back, cert);
    }

    #[test]
    fn heesch_cert_round_trips() {
        let cert = HeeschCert {
            heesch: 1,
            status: HeeschStatus::Finite,
            build: vec![PatchMatch::new(
                EdgeRange::new(0, 1),
                Segment::new(1, EdgeRange::new(3, 1)),
            )],
            bound: 2,
            budget: 20_000_000,
        };
        let json = serde_json::to_string(&cert).unwrap();
        let back: HeeschCert = serde_json::from_str(&json).unwrap();
        assert_eq!(back, cert);
    }

    #[test]
    fn reconstruct_replays_a_hand_recipe() {
        use crate::cyclotomic::ZZ12;

        // Grow a real patch, recording the PatchMatch at each glue, then check
        // that replaying that recipe reproduces the same meta-tile.
        let base = Rat::<ZZ12>::from_snake_trusted(&tiles::triangle()); // [4, 4, 4]
        let ts = TileSet::single(base.clone());
        let seed = BasicPatch::single_tile(ts, 0);
        let m0 = *seed.get_all_matches().first().unwrap();
        let mut gp = seed.with_tile(&m0).unwrap();
        let mut build = vec![m0];
        for _ in 0..2 {
            let m = *gp.get_all_matches().first().expect("a glue is available");
            assert!(gp.add_tile(&m).is_some());
            build.push(m);
        }
        let direct_rat = gp.to_rat();

        let cert = PeriodicCert {
            build,
            glue: vec![],
            via: PeriodicVia::Conway,
        };
        let recon = cert.reconstruct(&base).expect("recipe replays");
        assert_eq!(
            recon.to_rat(),
            direct_rat,
            "reconstructed meta-tile matches the grown one"
        );

        // A recipe replayed against the wrong base must fail, not silently
        // produce a different shape.
        let wrong = Rat::<ZZ12>::from_snake_trusted(&tiles::dodecagon());
        assert!(
            cert.reconstruct(&wrong).is_none(),
            "recipe is base-specific"
        );
    }

    #[test]
    fn boundary_arc_pairs_labels_every_meta_edge() {
        use crate::classify::cascade::{AcceptBounds, certify_periodic};
        use crate::cyclotomic::ZZ12;

        // A Torus k=4 tile: a genuine k>=2 meta-tile (so `build` is non-empty),
        // whose boundary decomposes into several complementary glued arcs.
        let seq: &[i8] = &[-3, 2, 2, 2, -2, 3, 1, 3, -3, 2, 2, 3];
        let base = Rat::<ZZ12>::from_slice_trusted(seq);
        let cert =
            certify_periodic::<ZZ12>(seq, &AcceptBounds::default()).expect("tiles periodically");

        let arcs = cert
            .boundary_arc_pairs(&base)
            .expect("k>=2 meta has a boundary");
        let n = cert.reconstruct(&base).unwrap().boundary_positions().len() - 1;
        assert_eq!(arcs.len(), n, "one arc-pair label per meta boundary edge");
        let ncol = arcs.iter().max().map_or(0, |m| m + 1);
        assert!(
            ncol >= 2,
            "a k=4 cell boundary splits into several arc-pairs"
        );
        assert!(arcs.iter().all(|&c| c < ncol), "labels dense in 0..ncol");
    }

    #[test]
    fn verdict_round_trips_both_arms() {
        for v in [
            Verdict::Periodic(sample_periodic()),
            Verdict::CannotTile(HeeschCert {
                heesch: 0,
                status: HeeschStatus::Finite,
                build: vec![],
                bound: 1,
                budget: 100_000,
            }),
        ] {
            let json = serde_json::to_string(&v).unwrap();
            let back: Verdict = serde_json::from_str(&json).unwrap();
            assert_eq!(back, v);
        }
    }
}