tilezz 0.2.0

//! Rat enumeration: depth-first walk over a cyclotomic ring's
//! unit-direction graph that finds every simple closed polygon
//! (`Rat`) up to a chosen perimeter.
//!
//! The enumeration is the engine behind the `rat_enum` binary; this
//! module exposes it as a library so the binary stays thin and so
//! tests (correctness cross-validation, OEIS pinning) can drive the
//! same code paths from `#[cfg(test)]` without spawning subprocesses.
//!
//! # Optional optimizations
//!
//! All on top of the baseline DFS, all gated by [`prune::Prunes`]:
//!
//! - **Reachability prune** (the `--reachability-prune` flag): the
//!   necessary condition "can the remaining unit-step budget still
//!   cancel the current head displacement?", checked at the places of
//!   the field. Two complementary halves, installed together:
//!     - **modular** ([`prune::modular`], finite places): for a set of
//!       small moduli `m`, precomputes the mod-`m` displacements
//!       reachable by sums of `<= r` unit vectors and rejects any
//!       candidate whose post-step residue isn't in the table for the
//!       remaining-steps slot. ~10-376× on rings with non-trivial
//!       mod-2/3/4/6 structure.
//!     - **shadow-radius** ([`prune::shadow`], archimedean places): the
//!       always-on baseline `within_radius` bounds the head in the
//!       *physical* embedding (`|sigma_1(head)| <= remaining`); this
//!       extends the identical bound to the non-physical conjugate
//!       ("shadow") places the physical check cannot see. Since the
//!       field norm is a nonzero integer, a head physically near the
//!       origin necessarily has a large shadow.
//!
//! - **Closure-table prune** ([`prune::closure_table`], the
//!   `--closure-table-prune` flag): pre-enumerates every simple open
//!   snake up to length `L` and stores their (endpoint, facing)
//!   "closure keys". When the DFS's remaining step budget is `<= L`,
//!   rejects any candidate whose required suffix key isn't in the
//!   table. Strictly stronger than any reachability projection (uses
//!   exact lattice + facing info). Adds 2-5× on top.
//!
//! # Output modes
//!
//! Driven by the binary's `--mode` flag (see `Mode` in
//! `src/bin/rat_enum.rs`); the library exposes the underlying
//! functions independent of any CLI framing.
//!
//! - In-memory: [`enumerate_dispatch`] / [`run_rat_enum_seqs`]
//!   return the full set as `Vec<Vec<i8>>`. Fine up to ~5 GB of
//!   peak RSS.
//! - Streaming (memory-bounded, for large `n`): [`stream`] runs the
//!   same DFS but routes closures through `FnMut(&[i8])` callbacks
//!   into per-thread sort-buffer run files, then a k-way merge
//!   stage produces a deduplicated sorted artifact plus a BLAKE3
//!   certificate. See [`stream::stream_enum_dispatch`] and
//!   [`stream::merge_runs`].
//!
//! See submodule docs for the specific contracts.
//!
//! # Correctness
//!
//! Every optimization has dedicated cross-validation tests against
//! the baseline DFS, plus an OEIS A316192 anchor through n=10. See
//! `opt_correctness_tests` in this module's `tests` submodule
//! (`#[cfg(test)]`).

pub mod boundary;
pub mod canonical;
pub mod dfs;
pub mod output;
pub mod prune;
pub mod seed;
pub mod stats;
pub mod stream;

#[cfg(test)]
mod tests;

use crate::cyclotomic::IsRing;
use crate::enumerate::boundary::{Boundary, DominoBoundary};
use crate::enumerate::canonical::make_ops;
use crate::enumerate::dfs::rat_enum_with;
use crate::enumerate::prune::snapshot_prunes;
use crate::enumerate::seed::parallel::rat_enum_parallel;
use crate::enumerate::stats::DfsStats;
use crate::geom::celltable::{FragmentAlphabet, StateAlphabet};
use crate::geom::snake::Snake;

/// Output of a single-ring enumeration: the canonical sequences
/// (sorted by length), plus the DFS stats counters.
pub type EnumResult = (Vec<Vec<i8>>, DfsStats);

/// Generic ring-specific dispatcher: picks single-threaded vs parallel
/// based on `n_threads`, builds the canonical-ops pair, snapshots the
/// global prune state, and runs the enumeration. Returns the canonical
/// sequences (sorted by length) plus DFS stats.
pub fn enumerate_dispatch<ZZ: IsRing + Sync>(
    max_steps: usize,
    step: i8,
    n_threads: usize,
    free: bool,
    paranoid: bool,
    domino: bool,
) -> EnumResult {
    let ops = make_ops(free);
    let label = if free {
        "free enumeration"
    } else {
        "enumeration"
    };
    let prefix = if free { "free " } else { "" };
    let prunes = snapshot_prunes();

    // Pick the geometry backend once, as a boundary factory (seed prefix
    // -> boundary at that state); the enumeration below is identical
    // either way. The domino automaton needs a prebuilt cell alphabet
    // (radius = max_steps), immutable and shared read-only across workers.
    if domino {
        let st = StateAlphabet::<ZZ>::build(max_steps as u32);
        let fr = FragmentAlphabet::build(&st);
        let mk = |seed: &[i8]| {
            let mut b = DominoBoundary::new(&st, &fr);
            for &a in seed {
                let ok = b.add(a);
                debug_assert!(ok, "domino rejected a valid seed prefix angle");
            }
            b
        };
        run_enum::<ZZ, _, _>(
            mk, max_steps, step, n_threads, ops, label, prefix, paranoid, &prunes,
        )
    } else {
        let mk = |seed: &[i8]| Snake::<ZZ>::from_slice_trusted(seed);
        run_enum::<ZZ, _, _>(
            mk, max_steps, step, n_threads, ops, label, prefix, paranoid, &prunes,
        )
    }
}

/// Single- vs multi-threaded enumeration over a chosen boundary factory
/// -- the one place `n_threads` branches; the backend is entirely in `mk`.
#[allow(clippy::too_many_arguments)]
fn run_enum<ZZ, B, Mk>(
    mk: Mk,
    max_steps: usize,
    step: i8,
    n_threads: usize,
    ops: crate::enumerate::canonical::CanonicalOps,
    label: &str,
    prefix: &str,
    paranoid: bool,
    prunes: &crate::enumerate::prune::Prunes,
) -> EnumResult
where
    ZZ: IsRing + Sync,
    B: Boundary<ZZ>,
    Mk: Fn(&[i8]) -> B + Sync,
{
    if n_threads <= 1 {
        rat_enum_with::<ZZ, B, Mk>(mk, max_steps, step, ops, label, prefix, paranoid, prunes)
    } else {
        rat_enum_parallel::<ZZ, B, Mk>(
            mk, max_steps, step, n_threads, ops, label, prefix, paranoid, prunes,
        )
    }
}

/// Runtime-ring dispatcher: like [`enumerate_dispatch`] but takes a
/// `ring: u8` and selects the underlying type by match. Used by the
/// CLI which only knows the ring number at runtime.
#[allow(clippy::too_many_arguments)]
pub fn run_rat_enum_seqs(
    ring: u8,
    max_steps: usize,
    step: i8,
    n_threads: usize,
    free: bool,
    paranoid: bool,
    domino: bool,
) -> EnumResult {
    crate::dispatch_ring!(
        ring,
        enumerate_dispatch::<ZZ>(max_steps, step, n_threads, free, paranoid, domino)
    )
}