tilezz 0.2.0

//! Depth-first walk over the cyclotomic unit-direction graph.
//!
//! Two entry points over one generic worker:
//!
//! - [`rat_enum_with`]: single-threaded top-level. Constructs the
//!   initial `Snake`, runs [`rat_enum_step`], collects the closed
//!   canonical sequences into a `HashSet`.
//!
//! - [`rat_enum_step`]: the one recursive worker, generic over the
//!   geometry [`Boundary`] (`Snake` or the domino automaton). It tries
//!   every direction (subject to `step`), applies all prunes in order
//!   (canonical -> reachability -> modular -> closure-table -> the
//!   backend's self-avoidance), and recurses or records. Its
//!   **seed-split policy** (`split_depth` + `seeds`) subsumes the old
//!   `collect_seeds`: an alive prefix reaching `split_depth` is emitted
//!   as a work unit for the parallel / streaming drivers instead of
//!   being recursed into (pass `usize::MAX` to enumerate the whole
//!   subtree).
//!
//! `rat_enum_step` takes a `&mut dyn FnMut(&[i8])` for closed canonical
//! sequences, so the same engine drives the in-memory
//! ([`hashset_recorder`]) and streaming ([`super::stream`]) sinks, and
//! respects the optional [`super::prune::Prunes`]; see [`super::prune`].

use std::collections::HashSet;
use std::sync::atomic::{AtomicBool, Ordering};

use crate::cyclotomic::{IsRing, Units};
use crate::enumerate::boundary::Boundary;
use crate::enumerate::canonical::CanonicalOps;
use crate::geom::rat::Rat;
// `Snake` is no longer named here: rat_enum_step is generic over the
// geometry `Boundary`, and callers supply the concrete backend.
use crate::enumerate::prune::Prunes;
use crate::enumerate::stats::DfsStats;
use crate::enumerate::stream::progress::{FLUSH_MASK, WorkerCell, odometer_fraction};

/// When `true`, the DFS streams each newly-discovered rat to stdout
/// as `RAT [...]` on the fly. This is the protocol used by `--seed`
/// and `--mode render`; modes that consume the set internally
/// (`--mode bench` times the DFS; `--mode dafsa`/`dafsa-blocks`/`stream`
/// write a binary artifact) set this to `false` before enumerating to
/// avoid millions of useless stdout lines.
pub static STREAM_RAT_LINES: AtomicBool = AtomicBool::new(true);

/// Single-threaded enumeration entry point. Initializes an empty
/// snake, runs the recursive DFS, returns the `(sorted-by-length)
/// list, stats)` pair.
///
/// `label` is the header to print at start/end (e.g. `"free
/// enumeration"`); `prefix` is the prefix for the closing summary
/// line (e.g. `"free "`).
#[allow(clippy::too_many_arguments)]
pub fn rat_enum_with<ZZ, B, Mk>(
    mk: Mk,
    max_steps: usize,
    step: i8,
    ops: CanonicalOps,
    label: &str,
    prefix: &str,
    paranoid: bool,
    prunes: &Prunes,
) -> (Vec<Vec<i8>>, DfsStats)
where
    ZZ: IsRing,
    B: Boundary<ZZ>,
    Mk: Fn(&[i8]) -> B,
{
    let mut result: HashSet<Vec<i8>> = HashSet::new();
    let mut b = mk(&[]);
    let mut stats = DfsStats::default();

    println!("-------- {label} started --------");
    if paranoid {
        println!("paranoid: per-step fresh-snake cross-check enabled");
    }
    {
        let mut record = hashset_recorder(&mut result);
        // Whole-subtree enumeration: never split, so the seed sink is
        // unused.
        rat_enum_step::<ZZ, B>(
            &mut b,
            max_steps,
            step,
            &mut record,
            &mut stats,
            ops,
            paranoid,
            prunes,
            None,
            usize::MAX,
            &mut Vec::new(),
        );
    }
    println!(
        "-------- {label} completed --------\n{prefix}{} rats found",
        result.len()
    );

    let mut result: Vec<Vec<i8>> = result.into_iter().collect();
    result.sort_by_key(|x| x.len());
    (result, stats)
}

/// Build the canonical "record into a `HashSet`" callback used by
/// the in-memory enumeration paths. Inserts each new sequence and,
/// if [`STREAM_RAT_LINES`] is set, emits a `RAT [...]` line to
/// stdout. Lifted here so every in-memory caller -- single-thread,
/// parallel workers, seed-walk closures -- uses the same recipe.
pub fn hashset_recorder<'a>(set: &'a mut HashSet<Vec<i8>>) -> impl FnMut(&[i8]) + 'a {
    move |seq: &[i8]| {
        if set.insert(seq.to_vec()) && STREAM_RAT_LINES.load(Ordering::Relaxed) {
            println!("RAT {seq:?}");
        }
    }
}

/// Publish a live telemetry snapshot for the current worker: the
/// running counters plus the base-`B` odometer reading over the
/// in-cylinder turns (the path below the worker's seed prefix). Called
/// only on the [`FLUSH_MASK`] cadence, so the per-call cost (a handful
/// of arithmetic ops over <=`max_steps` digits) is paid ~once per
/// million DFS events.
#[inline]
fn publish_progress<ZZ: IsRing>(cell: &WorkerCell, angles: &[i8], stats: &DfsStats, step: i8) {
    let seed_len = cell.seed_len.load(Ordering::Relaxed) as usize;
    let rel: &[i8] = angles.get(seed_len..).unwrap_or(&[]);
    // Clamp to < 1e6 so the swept fraction never reads >= 100% and the
    // per-seed ETA divide stays strictly positive (see `seed_eta`).
    let ppm = ((odometer_fraction(rel, ZZ::hturn(), step) * 1_000_000.0) as u32).min(999_999);
    cell.publish(stats.total(), stats.closed, angles.len() as u32, ppm);
}

/// Cadence-gated wrapper around [`publish_progress`]: publish only when
/// the gating counter `key` crosses a [`FLUSH_MASK`] boundary. The DFS
/// keeps two regimes -- closure-storm (`key = stats.closed`) and descent
/// (`key = stats.recursed`) -- so one advances when the other stalls;
/// both funnel through here. A no-op (one mask test) when `progress` is
/// `None`, i.e. on the in-memory / seed-collection paths.
#[inline]
fn maybe_publish<ZZ: IsRing>(
    progress: Option<&WorkerCell>,
    key: u64,
    angles: &[i8],
    stats: &DfsStats,
    step: i8,
) {
    if let Some(cell) = progress
        && key & FLUSH_MASK == 0
    {
        publish_progress::<ZZ>(cell, angles, stats, step);
    }
}

/// The single recursive DFS worker, generic over the geometry
/// [`Boundary`] (`Snake` or the domino automaton) so there is exactly one
/// copy of the walk. It extends `b` by one edge (via `add`/`pop`), applies
/// the canonical + reachability prunes, and on closure passes the
/// canonical sequence to `record`.
///
/// The **seed-split policy** subsumes the old `collect_seeds`: an alive
/// (non-closed) prefix that reaches `split_depth` is pushed to `seeds`
/// instead of being recursed into -- these are the work units the
/// parallel/streaming drivers hand to workers. Pass `split_depth =
/// usize::MAX` (and an unused `seeds`) to enumerate the whole subtree.
#[allow(clippy::too_many_arguments)]
pub fn rat_enum_step<ZZ: IsRing, B: Boundary<ZZ>>(
    b: &mut B,
    max_steps: usize,
    step: i8,
    record: &mut dyn FnMut(&[i8]),
    stats: &mut DfsStats,
    ops: CanonicalOps,
    paranoid: bool,
    prunes: &Prunes,
    progress: Option<&WorkerCell>,
    split_depth: usize,
    seeds: &mut Vec<Vec<i8>>,
) {
    let depth = b.angles().len();
    if depth >= max_steps {
        return;
    }
    let remaining = (max_steps - depth) as i64;

    for direction in ((-ZZ::hturn() + 1)..ZZ::hturn()).rev() {
        if direction.rem_euclid(step) != 0 {
            continue;
        }
        // Canonical prune before the radius and geometry checks so
        // that rejected branches pay nothing.
        if !(ops.is_canonical)(b.angles(), direction) {
            stats.canonical_skip += 1;
            continue;
        }

        // Early reachability prune: compute the next head position
        // before paying the geometry cost of `add`. If the new point is
        // too far from the origin to ever close, skip this direction.
        let new_pt =
            b.offset() + <ZZ as Units>::unit(b.direction()) * <ZZ as Units>::unit(direction);
        if !new_pt.is_zero() && !new_pt.within_radius(remaining) {
            stats.too_far += 1;
            continue;
        }
        // Archimedean half of the reachability prune (set via
        // `--reachability-prune`, alongside the modular/finite-place half): the
        // same `within_radius` bound in the non-physical conjugate
        // embeddings. A closing walk returns to 0 in every place, so
        // |sigma_g(new_pt)| <= remaining must hold for each. Completes
        // the always-on physical `within_radius`. See `prune::shadow`.
        if let Some(sp) = prunes.shadow_prune.as_deref()
            && !new_pt.is_zero()
            && !sp.allows_closure(&new_pt, remaining)
        {
            stats.shadow_skip += 1;
            continue;
        }

        // Optional modular reachability prune (set via `--reachability-prune`).
        // After taking this direction, the snake will be at `new_pt`
        // with `remaining - 1` directions still to add for closure.
        // If no sum of (remaining-1) unit vectors equals `-new_pt`
        // (modulo any active modulus), closure is impossible.
        let remaining_after = (remaining as usize).saturating_sub(1);
        if let Some(mp) = prunes.modular_prune.as_deref()
            && !mp.allows_closure(new_pt.int_coeffs_slice(), remaining_after)
        {
            stats.modular_skip += 1;
            continue;
        }
        // Optional closure-table prune (set via `--closure-table-prune`).
        // Only fires when `remaining_after <= max_l` (otherwise the
        // tabulated suffix lengths aren't enough to cover the
        // closing range, and pruning would be unsound).
        if let Some(ck) = prunes.closure_table_prune.as_deref()
            && remaining_after <= ck.max_l
        {
            let turn = ZZ::turn();
            let new_facing = (b.direction() + direction).rem_euclid(turn);
            let neg_facing = (-new_facing).rem_euclid(turn);
            // target suffix endpoint = -unit(-new_facing) * new_pt.
            let target: ZZ = -(<ZZ as Units>::unit(neg_facing) * new_pt);
            let key = (target.int_coeffs_slice().to_vec(), neg_facing);
            if !ck.keys.contains(&key) {
                stats.closure_table_skip += 1;
                continue;
            }
        }
        if !b.add(direction) {
            stats.intersected += 1;
            continue;
        }
        if paranoid {
            b.paranoid_recheck();
        }
        if b.is_closed() {
            stats.closed += 1;
            maybe_publish::<ZZ>(progress, stats.closed, b.angles(), stats, step);
            let r = {
                let tmp = Rat::<ZZ>::from_slice_trusted(b.angles());
                if tmp.chirality() > 0 {
                    tmp
                } else {
                    tmp.reversed()
                }
                .canonical()
            };
            let seq = (ops.canonicalize)(r.seq());
            record(&seq);
        } else {
            stats.recursed += 1;
            maybe_publish::<ZZ>(progress, stats.recursed, b.angles(), stats, step);
            // Seed-split policy: an alive prefix at the split boundary is
            // handed off as a work unit instead of being recursed into.
            if b.angles().len() >= split_depth {
                seeds.push(b.angles().to_vec());
            } else {
                rat_enum_step::<ZZ, B>(
                    b,
                    max_steps,
                    step,
                    record,
                    stats,
                    ops,
                    paranoid,
                    prunes,
                    progress,
                    split_depth,
                    seeds,
                );
            }
        }
        b.pop();
    }
}