minerva 0.2.0

extern crate alloc;

use alloc::collections::BTreeSet;

use super::super::Anchor;
use super::super::ancestry::{Coordinate, QueryError, Relation};
use super::super::placement::Dot;
#[cfg(feature = "timing")]
use super::MovementCycleValidationWork;
use crate::metis::dot::RawDot;

#[cfg(any(test, feature = "timing"))]
#[derive(Clone, Copy)]
pub(super) enum EnteredCycleGuard {
    SelfAnchor,
    LiveChild,
    StaleMonotone,
}

#[derive(Clone, Copy)]
pub(super) enum CycleTerminal {
    NotDescendant,
    Origin,
    Unborn,
    AnchorCycle,
    InvariantViolation,
    Target,
}

#[derive(Clone, Copy)]
pub(super) struct CycleWalk {
    pub(super) terminal: CycleTerminal,
    #[cfg(any(test, feature = "timing"))]
    pub(super) nodes_visited: usize,
}

impl CycleWalk {
    pub(super) const fn must_refuse(self) -> bool {
        matches!(
            self.terminal,
            CycleTerminal::Target | CycleTerminal::InvariantViolation
        )
    }
}

#[derive(Clone, Copy)]
pub(super) enum CycleOutcome {
    Skipped,
    Coordinate(CycleTerminal),
    Walk(CycleWalk),
}

impl CycleOutcome {
    pub(super) const fn must_refuse(self) -> bool {
        match self {
            Self::Skipped => false,
            Self::Coordinate(terminal) => matches!(
                terminal,
                CycleTerminal::Target | CycleTerminal::InvariantViolation
            ),
            Self::Walk(walk) => walk.must_refuse(),
        }
    }
}

#[cfg(any(test, feature = "timing"))]
#[derive(Clone, Copy)]
pub(super) enum CycleCheck {
    Skipped,
    Coordinate {
        guard: EnteredCycleGuard,
        terminal: CycleTerminal,
    },
    Walk {
        guard: EnteredCycleGuard,
        walk: CycleWalk,
    },
}

#[cfg(feature = "timing")]
impl CycleCheck {
    pub(super) const fn add_to(self, work: &mut MovementCycleValidationWork) {
        match self {
            Self::Skipped => work.guards_skipped += 1,
            Self::Coordinate { guard, terminal } => {
                add_guard(work, guard);
                work.coordinate_queries += 1;
                add_terminal(work, terminal);
            }
            Self::Walk { guard, walk } => {
                add_guard(work, guard);
                work.chain_nodes_visited += walk.nodes_visited;
                add_terminal(work, walk.terminal);
            }
        }
    }
}

#[cfg(feature = "timing")]
const fn add_guard(work: &mut MovementCycleValidationWork, guard: EnteredCycleGuard) {
    match guard {
        EnteredCycleGuard::SelfAnchor => work.self_guard_entries += 1,
        EnteredCycleGuard::LiveChild => work.live_guard_entries += 1,
        EnteredCycleGuard::StaleMonotone => work.stale_guard_entries += 1,
    }
}

#[cfg(feature = "timing")]
const fn add_terminal(work: &mut MovementCycleValidationWork, terminal: CycleTerminal) {
    match terminal {
        CycleTerminal::NotDescendant => work.not_descendant_terminals += 1,
        CycleTerminal::Origin => work.origin_terminals += 1,
        CycleTerminal::Unborn => work.unborn_terminals += 1,
        CycleTerminal::AnchorCycle => work.anchor_cycle_terminals += 1,
        CycleTerminal::InvariantViolation => work.invariant_refusals += 1,
        CycleTerminal::Target => work.refusals += 1,
    }
}

/// The cycle verdict, one home for both replay forms (the eager map fold
/// and the collation's suffix replay), so the two cannot drift: `true`
/// exactly when applying the move would place its own target inside its
/// anchor chain. `lookup` reads a chain link's anchor dot (`None` for a
/// link unborn in the replayed skeleton, `Some(None)` at the origin).
///
/// The verdict is exact for the state it runs against; its FUTURE
/// sensitivity (a later birth extending a chain at an unborn terminus)
/// is deliberately not this function's duty. It is recorded structurally
/// at locus-fold time instead (the `dangling` map), because the guard
/// below skips exactly some of the walks whose verdicts a birth can
/// flip, so walk-time recording would be incomplete (the collation
/// property's first counterexample).
///
/// The `anchored` guard keeps the replay near-linear: a move can close a
/// cycle onto its target only if the anchor IS the target (a
/// self-placement, which a public `Metathesis` can carry) or the target
/// already has a child in the effective skeleton; a move that satisfies
/// neither is acyclic and skips the walk. The guard set is monotone and
/// never pruned (a stale entry costs a needless walk, never a wrong
/// verdict). Woven birth loci may contain an unplaced anchor cycle. Brent's
/// checkpoint algorithm detects one with a single parent lookup per visited
/// node and no allocation. The traversal checks the target first, so a
/// detected repetition is necessarily a non-target cycle.
#[derive(Clone, Copy)]
pub(super) struct WalkBudget(core::num::NonZeroUsize);

impl WalkBudget {
    /// Brent detects every finite functional-graph cycle within `3n` visits.
    pub(super) const fn for_skeleton(nodes: usize) -> Self {
        Self(
            core::num::NonZeroUsize::new(nodes.saturating_mul(3).saturating_add(1))
                .expect("a saturated node count remains nonzero"),
        )
    }
}

pub(super) fn move_forms_cycle(
    coordinate: Option<&mut Coordinate>,
    target: RawDot,
    anchor: Anchor,
    anchored: &BTreeSet<RawDot>,
    budget: WalkBudget,
    lookup: impl Fn(RawDot) -> Option<Option<RawDot>>,
) -> CycleOutcome {
    let Some(descendant) = anchor.dot() else {
        return CycleOutcome::Skipped;
    };
    if descendant != target && !anchored.contains(&target) {
        return CycleOutcome::Skipped;
    }
    // Both operands are payload coordinates. A non-dot one names no
    // resident address, so the coordinate query cannot answer and the
    // bounded walk decides, exactly as an unknown operand did before the
    // type carried the law (ruling R-91).
    let operands = Dot::try_from(descendant)
        .ok()
        .zip(Dot::try_from(target).ok());
    if let (Some(coordinate), Some((descendant_dot, target_dot))) = (coordinate, operands) {
        match coordinate.relation(descendant_dot, target_dot) {
            Ok(Relation::Same | Relation::Descendant) => {
                return CycleOutcome::Coordinate(CycleTerminal::Target);
            }
            Ok(Relation::NotDescendant) => {
                return CycleOutcome::Coordinate(CycleTerminal::NotDescendant);
            }
            Err(QueryError::InvariantViolation) => {
                return CycleOutcome::Coordinate(CycleTerminal::InvariantViolation);
            }
            Err(
                QueryError::UnknownDescendant { .. }
                | QueryError::UnknownAncestor { .. }
                | QueryError::UnplacedReading { .. },
            ) => {}
        }
    }
    move_forms_a_cycle(target, anchor, anchored, budget, lookup)
}

pub(super) fn move_forms_a_cycle(
    target: RawDot,
    anchor: Anchor,
    anchored: &BTreeSet<RawDot>,
    budget: WalkBudget,
    lookup: impl Fn(RawDot) -> Option<Option<RawDot>>,
) -> CycleOutcome {
    let self_anchored = anchor.dot() == Some(target);
    if !(self_anchored || anchored.contains(&target)) {
        return CycleOutcome::Skipped;
    }
    let mut cursor = anchor.dot();
    let mut remaining = budget.0.get();
    let mut checkpoint = cursor;
    let mut checkpoint_span = 0usize;
    let mut next_checkpoint = 1usize;
    #[cfg(any(test, feature = "timing"))]
    let mut nodes_visited = 0usize;
    let terminal = loop {
        let Some(at) = cursor else {
            break CycleTerminal::Origin;
        };
        let Some(next_remaining) = remaining.checked_sub(1) else {
            break CycleTerminal::InvariantViolation;
        };
        remaining = next_remaining;
        #[cfg(any(test, feature = "timing"))]
        {
            nodes_visited += 1;
        }
        if at == target {
            break CycleTerminal::Target;
        }
        if checkpoint_span != 0 && checkpoint == Some(at) {
            break CycleTerminal::AnchorCycle;
        }
        if checkpoint_span == next_checkpoint {
            checkpoint = Some(at);
            checkpoint_span = 0;
            next_checkpoint = next_checkpoint.saturating_mul(2);
        }
        match lookup(at) {
            None => break CycleTerminal::Unborn,
            Some(next) => {
                cursor = next;
                checkpoint_span = checkpoint_span.saturating_add(1);
            }
        }
    };
    CycleOutcome::Walk(CycleWalk {
        terminal,
        #[cfg(any(test, feature = "timing"))]
        nodes_visited,
    })
}