tilezz 0.2.0

//! Corona-patch growers: build a compact, near-periodic patch of a monotile by
//! the Heesch burial discipline (close every boundary edge before moving
//! outward, with backtracking), capturing each placed copy's [`Iso`] placement.
//! The torus cover detector reads candidate lattices off these patches, and the
//! cert carve reads the tile adjacency off the grown patch inline (no recipe
//! replay -- replay survives only for re-deriving a stored witness).

use crate::classify::heesch::{BurySearch, TileSink, bury};
use crate::cyclotomic::IsRing;
use crate::geom::iso::{Iso, dir_of_unit};
use crate::geom::matches::PatchMatch;
use crate::geom::patch::{BasicPatch, IPatch, Patch, WithAdjacency, boundary_vertices};
use crate::geom::rat::Rat;
use crate::geom::tileset::TileSet;
use crate::geom::vertices::OpenJunctionType;

/// Reconstruct the placement (as an `Iso` in the patch's stable frame) of tile
/// instance `k` from one of its boundary edges: that edge's absolute
/// coordinates plus which shape-edge it is determine the rotation and shift.
pub(crate) fn capture_placement<T: IsRing, P: Patch<T>>(
    gp: &P,
    v: &[T],
    k: usize,
) -> Option<Iso<T>> {
    let n = v.len();
    let pos = gp.patch_tile_ids().iter().position(|&x| x == k)?;
    let off = gp.edges()[pos].canon_offset;
    let bp = gp.boundary_positions();
    let (p0, p1) = (bp[pos], bp[pos + 1]);
    let src = dir_of_unit(v[(off + 1) % n] - v[off])?;
    let dst = dir_of_unit(p1 - p0)?;
    Some(Iso::carrying(v[off], src, p0, dst))
}

/// Sink for [`bury`] that grows a periodic patch on a [`WithAdjacency`] patch: on
/// the winning path it collects each tile's `(instance, placement)` into `out`,
/// and at the winning corona closure it clones the whole [`WithAdjacency`] patch
/// (its inline adjacency is the tile-adjacency the cert carve reads -- built
/// DURING the search, no recipe to replay). It VETOES (returns `false`) a tile
/// whose placement geometry cannot be captured in the base frame, so `bury` drops
/// that branch instead of recording it. Bound to the concrete graph-carrying
/// patch (not generic over `P`) so [`mark`](TileSink::mark) can clone it.
struct GrowSink<'a, T: IsRing> {
    out: &'a mut Vec<(usize, Iso<T>)>,
    v: &'a [T],
    /// The corona depth whose closure is the search target (see `mark`).
    target: usize,
    /// The winning graph-carrying patch, captured at the target-depth closure.
    patch: Option<IPatch<T>>,
}
impl<T: IsRing> TileSink<T, WithAdjacency<BasicPatch<T>>> for GrowSink<'_, T> {
    fn push(
        &mut self,
        _pm: &PatchMatch,
        patch: &WithAdjacency<BasicPatch<T>>,
        new_id: usize,
    ) -> bool {
        let Some(iso) = capture_placement(patch, self.v, new_id) else {
            return false; // cannot place this tile in `v`'s frame -- skip the branch
        };
        self.out.push((new_id, iso));
        true
    }
    fn pop(&mut self) {
        self.out.pop();
    }
    fn mark(&mut self, depth: usize, patch: &WithAdjacency<BasicPatch<T>>) {
        // The search short-circuits on the first closure at `target` (the winning
        // corona), so this fires exactly once with the final patch in hand: ONE
        // patch clone, not one per branch.
        if depth == self.target {
            self.patch = Some(patch.clone());
        }
    }
}

/// Replay a RECORDED glue recipe against `base` into a patch, driving `observe`
/// in lockstep. The recipe's first [`PatchMatch`] seeds the two-tile patch;
/// each subsequent one is `add_tile`d. `observe` fires once after the seed glue
/// and once after every add, receiving the current patch and the id of the
/// most-recently-placed tile (`1` after the seed glue -- tile 0 is its partner;
/// the new tile's id after each add); returning `false` aborts. Returns the
/// final patch, or `None` if the recipe cannot replay against this base
/// (malformed / wrong base: `grow` or `add_tile` fails) or `observe` aborts.
///
/// `build` must be non-empty -- the empty recipe (the bare base) has no single
/// natural patch, so callers handle it themselves. This is the one place the
/// "grow the seed, then add each match in order" replay protocol lives; the
/// recorded recipes come from cert `build`s and corona witnesses.
pub(crate) fn replay_recipe<T: IsRing>(
    base: &Rat<T>,
    build: &[PatchMatch],
    mut observe: impl FnMut(&BasicPatch<T>, usize) -> bool,
) -> Option<BasicPatch<T>> {
    let seed = BasicPatch::single_tile(TileSet::single(base.clone()), 0);
    let mut gp = seed.with_tile(&build[0])?;
    if !observe(&gp, 1) {
        return None;
    }
    for pm in &build[1..] {
        let new_id = gp.next_tile_id();
        gp.add_tile(pm)?;
        if !observe(&gp, new_id) {
            return None;
        }
    }
    Some(gp)
}

/// Replay a RECORDED glue recipe (a cert's `build`, a corona witness) against
/// `base` and capture every placed copy's [`Iso`] -- the presentation
/// primitive: a stored witness replays into drawable per-tile placements
/// (each captured immediately after its glue, before later tiles can bury its
/// boundary edges), normalized to tile 0 = identity. An empty recipe is the
/// bare base. `None` if the recipe does not replay against this base (wrong
/// base, malformed) or a placement cannot be captured.
pub fn replay_placements<T: IsRing>(base: &Rat<T>, build: &[PatchMatch]) -> Option<Vec<Iso<T>>> {
    let v = boundary_vertices::<T>(base.seq());
    if build.is_empty() {
        return Some(vec![Iso::id()]);
    }
    let mut out = Vec::new();
    replay_recipe(base, build, |gp, new_id| {
        // The seed glue places tiles 0 and 1 at once; every later add places one
        // tile (`new_id`). Capture each immediately, before later tiles bury its
        // boundary edges.
        let first = if new_id == 1 { 0 } else { new_id };
        for id in first..=new_id {
            match capture_placement(gp, &v, id) {
                Some(iso) => out.push(iso),
                None => return false,
            }
        }
        true
    })?;
    let i0inv = out[0].inv();
    Some(out.into_iter().map(|iso| i0inv.after(&iso)).collect())
}

/// Grow a compact patch: `n_coronas` successive EDGE-BURIAL rings around the
/// seed (each ring buries every exposed edge of the previous, most-concave-first
/// with backtracking, so no fjords and no greedy jams). Returns the placements,
/// or empty if `n_coronas` rings are not reachable within the node budget.
///
/// (For a tile that tiles periodically the interior comes out near-periodic --
/// repeated copies at consistent displacements -- which is what the Torus
/// detector reads a lattice off; for a non-periodic tile it is just a compact
/// patch, no lattice. The grower guarantees the compact edge-buried patch, not
/// the near-periodicity.)
///
/// These rings are edge-buried ONLY -- the corner wedges are deliberately left
/// unsealed (`bury` runs in `edge_only` mode, skipping its wedge-seal phase).
/// So this is a compact, lattice-exposing patch, NOT a fully surrounded one, and
/// a ring here is NOT a "complete corona" in the Heesch sense (every edge buried
/// AND every vertex sealed) -- that is what
/// [`heesch_number_witnessed`](crate::classify::heesch::heesch_number_witnessed)
/// produces. This grower exists solely for the Torus detector
/// ([`tiles_torus`](crate::classify::torus::tiles_torus)) and its cert carve,
/// which only need an orbit that exposes the lattice and cannot afford the much
/// branchier wedge-sealing. Do not use it to render or reason about coronas.
pub fn grow_coronas<T: IsRing>(tile_seq: &[i8], n_coronas: usize) -> Vec<Iso<T>> {
    grow_coronas_build(tile_seq, n_coronas).map_or_else(Vec::new, |(pls, _)| pls)
}

/// Like [`grow_coronas`], but also returns the graph-carrying [`WithAdjacency`]
/// patch itself -- its inline tile-adjacency is built DURING the search, so it is
/// the true adjacency of the exact lattice-exposing patch the placements came
/// from (node `i` == tile instance `i`, matching `pls[i]`). The cert carve
/// ([`carve_domain`](crate::classify::mint)) reads the fundamental domain
/// straight off this patch's adjacency -- no recipe to replay. `None` if no such
/// patch is reached within the node budget. The placements are normalized to
/// tile 0 = identity.
pub fn grow_coronas_build<T: IsRing>(
    tile_seq: &[i8],
    n_coronas: usize,
) -> Option<(Vec<Iso<T>>, IPatch<T>)> {
    let ts = TileSet::single(Rat::<T>::from_slice_trusted(tile_seq));
    let v = boundary_vertices::<T>(tile_seq);
    let seed = WithAdjacency::single_tile(ts, 0);
    // Grow via the shared corona search ([`bury`]) in EDGE-ONLY mode: a growth
    // corona closes on edge-burial (no wedge seal -- we want a compact periodic
    // patch, not a surroundable one) and there is no cursed prune. The frozen set
    // is inert in this mode (the wedge phase is skipped and the empty prune never
    // fires), so an empty snapshot suffices; `bury` recomputes it per ring anyway.
    // One shared budget across all first-candidate attempts, so a tile that cannot
    // reach the target fails fast instead of re-spending per candidate.
    let empty_frozen: rustc_hash::FxHashSet<T> = rustc_hash::FxHashSet::default();
    let empty_cursed: rustc_hash::FxHashSet<OpenJunctionType> = rustc_hash::FxHashSet::default();
    const GROW_BUDGET: usize = 1_500_000;
    let mut ctx = BurySearch::new(n_coronas, GROW_BUDGET, &empty_cursed, true);
    for first in seed.get_all_matches() {
        // Seed node 0 is pre-seeded; the first glue goes through add_tile like any
        // other, projecting node 1 + its edge into the graph.
        let mut gp = seed.clone();
        if gp.add_tile(&first).is_none() {
            continue;
        }
        let mut out: Vec<(usize, Iso<T>)> = Vec::new();
        if let Some(i0) = capture_placement(&gp, &v, 0) {
            out.push((0, i0));
        }
        if let Some(i1) = capture_placement(&gp, &v, 1) {
            out.push((1, i1));
        }
        let mut sink = GrowSink {
            out: &mut out,
            v: &v,
            target: n_coronas,
            patch: None,
        };
        // The grower runs with an EMPTY cursed set (edge-only mode), so the
        // junction lookup is never consulted -- `has_cursed_frozen` short-circuits
        // on the empty set before touching it. A `None`-returning stub keeps
        // `bury` on the core [`Patch`] surface (no junction layer), which is why
        // the graph patch can wrap the bare [`BasicPatch`] rather than an EPatch.
        let reached =
            bury(&gp, 1, &empty_frozen, 0, &mut ctx, &mut sink, &|_, _| None) >= n_coronas;
        let patch = sink.patch;
        if reached {
            let patch = patch.expect("winning closure fired mark(n_coronas)");
            out.sort_by_key(|&(k, _)| k);
            // Normalize into the seed frame: the patch grows in its own stable
            // frame where tile 0 sits at `iso0` (generally rotated/shifted off
            // the origin), but downstream consumers -- and any cert minted from
            // the cover read off this patch -- want tile 0 == identity. Undoing
            // iso0 is a global isometry, so it leaves the lattice/gold check
            // intact while putting the base where the seed frame expects it.
            let i0inv = out[0].1.inv();
            let pls = out.into_iter().map(|(_, iso)| i0inv.after(&iso)).collect();
            return Some((pls, patch));
        }
        if ctx.budget_hit || ctx.spent >= GROW_BUDGET {
            break;
        }
    }
    None
}

/// Replay a recorded glue recipe (a banked corona witness) against `base`
/// through a graph-carrying [`WithAdjacency`] patch, returning per-tile
/// placements (tile 0 = identity) AND the patch itself -- the witness-cover
/// analogue of [`grow_coronas_build`] (which grows the patch natively). The
/// inline adjacency is built during replay by `WithAdjacency::add_tile`, so
/// node `i` is tile instance `i`, matching `pls[i]`; the pairing is what
/// [`carve_domain`](crate::classify::mint) needs. `build` must be non-empty (the
/// bare base has no single natural patch); `None` if the recipe does not replay
/// against this base (wrong base / malformed) or a placement cannot be captured
/// in the base frame.
pub(crate) fn replay_placements_graph<T: IsRing>(
    base: &Rat<T>,
    build: &[PatchMatch],
) -> Option<(Vec<Iso<T>>, IPatch<T>)> {
    if build.is_empty() {
        return None;
    }
    let v = boundary_vertices::<T>(base.seq());
    let ts = TileSet::single(base.clone());
    let mut gp = WithAdjacency::single_tile(ts, 0);
    // Seed glue places tiles 0 and 1 at once; every later add places one tile.
    gp.add_tile(&build[0])?;
    let mut out = vec![
        capture_placement(&gp, &v, 0)?,
        capture_placement(&gp, &v, 1)?,
    ];
    for pm in &build[1..] {
        let new_id = gp.next_tile_id();
        gp.add_tile(pm)?;
        out.push(capture_placement(&gp, &v, new_id)?);
    }
    let i0inv = out[0].inv();
    let pls = out.into_iter().map(|iso| i0inv.after(&iso)).collect();
    Some((pls, gp))
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::classify::heesch::heesch_number_witnessed;
    use crate::cyclotomic::ZZ12;
    use crate::geom::tiles;

    /// replay_placements turns a banked corona witness back into per-tile
    /// placements: one Iso per placed copy (build.len() + 1), tile 0 at the
    /// identity, all placements distinct.
    #[test]
    fn replay_placements_reconstructs_witness_patch() {
        let tri = Rat::<ZZ12>::from_snake_trusted(&tiles::triangle());
        let (h, build) = heesch_number_witnessed(TileSet::single(tri.clone()), 0, 1, 200_000);
        assert!(!h.cannot_tile() && !build.is_empty());
        let pls = replay_placements(&tri, &build).expect("witness replays");
        assert_eq!(pls.len(), build.len() + 1, "one placement per placed copy");
        assert_eq!(pls[0], Iso::id(), "base normalized to the identity");
        let distinct: std::collections::HashSet<_> = pls.iter().copied().collect();
        assert_eq!(distinct.len(), pls.len(), "no duplicate placements");
        // Empty recipe = the bare base.
        assert_eq!(replay_placements(&tri, &[]), Some(vec![Iso::id()]));
    }
}