lgwks_std 1.1.0

//! Pure similarity primitives with replaceable scoring seams.
//!
//! This module keeps deterministic lexical, structural, and geometric scores
//! behind [`Similarity`]. Each concrete scorer owns only its policy; callers
//! can replace one scorer without changing the code that combines or consumes
//! scores. The algorithms use `core` and `alloc` only, and every score the
//! [`Similarity`] seam returns is clamped to the contract's closed interval
//! `[0.0, 1.0]`.
//!
//! # Two domains, and the difference between a measurement and a refusal
//!
//! Raw cosine similarity has a mathematical domain of `[-1, 1]`, and
//! [`Cosine::try_score`] keeps it. The shared [`Similarity`] contract has the
//! domain `[0, 1]`, and the mapping between the two is the explicit, named,
//! versioned [`Cosine::normalized_score`] (`(raw + 1) / 2`). An opposite pair
//! is therefore `0.0` through the shared contract and `-1.0` through the raw
//! one, which is a stated mapping rather than a silent shift.
//!
//! A weight total below `1.0` is a deliberate evidence deficit, so an identical
//! pair scored at weight `0.5` reads `0.5` rather than the trait's identity
//! `1.0`. The maximum is not renormalized to hide the deficit, and the deficit
//! is never presented as an identity score.
//!
//! A refusal is not a measurement. Every checked scorer reports one through a
//! typed error, and [`CheckedEvidence::verdict`] carries component identity,
//! the refusal, and applicability through to the acceptance decision, so an
//! unavailable component cannot satisfy a threshold — including a threshold of
//! zero. All-zero effective evidence is [`EvidenceError::InsufficientEvidence`]
//! rather than a score of zero.
//!
//! The infallible [`Similarity`] methods remain for source compatibility and
//! are documented as lossy: they map a refusal to `0.0`. They are not the
//! authority-facing path; the checked composition is.
//!
//! [`Similarity`]: crate::similarity::Similarity
//! [`Cosine::try_score`]: crate::similarity::Cosine::try_score
//! [`Cosine::normalized_score`]: crate::similarity::Cosine::normalized_score
//! [`CheckedEvidence::verdict`]: crate::similarity::CheckedEvidence::verdict
//! [`EvidenceError::InsufficientEvidence`]: crate::similarity::EvidenceError::InsufficientEvidence
//!
//! # Example
//!
//! ```rust
//! use lgwks_std::similarity::{Cosine, CosineError, Similarity};
//!
//! let cosine = Cosine::new();
//! assert_eq!(cosine.try_score(&[1.0_f32], &[-1.0_f32])?, -1.0);
//! assert_eq!(Similarity::score(&cosine, &[1.0_f32], &[-1.0_f32]), 0.0);
//! assert!(matches!(
//!     cosine.try_score(&[1.0_f32, 0.0], &[1.0_f32, 0.0, 0.0]),
//!     Err(CosineError::DimensionMismatch { .. })
//! ));
//! # Ok::<(), CosineError>(())
//! ```
//!
//! The named normalized mapping is available on its own:
//!
//! ```rust
//! use lgwks_std::similarity::Cosine;
//!
//! let cosine = Cosine::new();
//! // Opposite reads 0.0 through the shared contract.
//! assert_eq!(cosine.normalized_score(&[1.0_f32], &[-1.0_f32]).unwrap_or(-1.0), 0.0);
//! ```

extern crate alloc;

use alloc::boxed::Box;
use alloc::string::String;
use alloc::vec;
use alloc::vec::Vec;
use core::fmt;
use core::marker::PhantomData;

/// A score-producing seam for one kind of comparable value.
///
/// Every implementation returns `1.0` for identical values, `0.0` for values
/// with no similarity, and a finite result in `[0.0, 1.0]`. Implementations
/// that can refuse document the infallible mapping in their own `impl` block;
/// [`CheckedEvidence::verdict`] is the path that preserves the refusal.
pub trait Similarity {
    /// The value type accepted by this scorer.
    type Value: ?Sized;

    /// Scores how similar `left` and `right` are.
    ///
    /// Implementations return `1.0` for identical values and `0.0` for values
    /// with no similarity. Every result is finite and lies in `[0.0, 1.0]`.
    fn score(&self, left: &Self::Value, right: &Self::Value) -> f64;
}

/// Why a bounded edit-distance calculation was refused.
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub enum EditDistanceError {
    /// At least one input exceeded the scorer's declared character bound.
    InputTooLong {
        /// The largest permitted input length.
        maximum: usize,
        /// The first observed length known to exceed `maximum`.
        observed: usize,
    },
}

impl From<EditDistanceError> for EvidenceError {
    fn from(value: EditDistanceError) -> Self {
        match value {
            EditDistanceError::InputTooLong { maximum, observed } => {
                Self::InputTooLong { maximum, observed }
            }
        }
    }
}

impl fmt::Display for EditDistanceError {
    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
        match *self {
            Self::InputTooLong { maximum, observed } => write!(
                formatter,
                "similarity input length {observed} exceeds maximum {maximum}"
            ),
        }
    }
}

impl core::error::Error for EditDistanceError {}

/// Bounded Levenshtein similarity over normalized text.
///
/// Inputs are trimmed, internal whitespace is collapsed, and Unicode
/// lower-case expansion is applied before the edit distance is calculated.
/// The score is `1 - distance / max(input lengths)`, with two empty inputs
/// scoring `1.0`. The dynamic-programming row is bounded by
/// `maximum_length`, so hostile input is refused before the row is allocated.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub struct EditDistance {
    /// The maximum raw character count accepted per input.
    maximum_length: usize,
}

impl EditDistance {
    /// Creates a scorer that accepts at most `maximum_length` input characters.
    #[must_use]
    pub const fn new(maximum_length: usize) -> Self {
        Self { maximum_length }
    }

    /// Returns the maximum number of raw input characters accepted per side.
    #[must_use]
    pub const fn maximum_length(&self) -> usize {
        self.maximum_length
    }

    /// Returns the normalized scalar count an input occupies under this
    /// scorer's text normalization.
    ///
    /// Normalization trims, collapses internal whitespace, and applies Unicode
    /// lower-case expansion, so this is the unit [`Self::maximum_length`]
    /// charges rather than the raw scalar count. Lower-casing can expand a
    /// scalar — `İ` becomes two — so the two units differ and only this one is
    /// the budget.
    #[must_use]
    pub fn normalized_length(&self, input: &str) -> usize {
        normalize_text(input, usize::MAX).map_or(0, |normalized| normalized.len())
    }

    /// Calculates the normalized score or reports an over-limit input.
    ///
    /// The budget is charged against the normalized scalar count, so a scalar
    /// whose lower-case form expands can be refused even when its raw scalar
    /// count is inside the limit. The refusal names the normalized length that
    /// crossed the bound.
    ///
    /// # Errors
    ///
    /// Returns [`EditDistanceError::InputTooLong`] when either input's
    /// normalized length exceeds [`Self::maximum_length`]. Both the raw pass
    /// and the normalized pass are checked, and the raw pass runs first, so a
    /// hostile input is refused before the row is allocated.
    pub fn try_score(&self, left: &str, right: &str) -> Result<f64, EditDistanceError> {
        let left = normalize_text(left, self.maximum_length)?;
        let right = normalize_text(right, self.maximum_length)?;
        Ok(sequence_similarity(&left, &right))
    }
}

/// Why a checked comparison could not produce a measurement.
///
/// Every variant is a refusal, never a score. A refusal reaching a composition
/// is retained with its component identity and can never satisfy an acceptance
/// threshold, so "we could not measure this" and "these did not match" stay
/// distinguishable through every layer.
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub enum EvidenceError {
    /// The two vectors had different lengths.
    DimensionMismatch {
        /// Length of the left-hand vector.
        left: usize,
        /// Length of the right-hand vector.
        right: usize,
    },
    /// A vector had zero magnitude, so its angle is undefined.
    ZeroMagnitude,
    /// A vector or coordinate carried a value that is not finite.
    NonFinite,
    /// At least one input exceeded the scorer's declared normalized budget.
    InputTooLong {
        /// The largest permitted normalized length.
        maximum: usize,
        /// The first normalized length known to exceed `maximum`.
        observed: usize,
    },
    /// A collection exceeded the scorer's declared element budget.
    CollectionTooLong {
        /// The largest permitted element count.
        maximum: usize,
        /// The first observed count known to exceed `maximum`.
        observed: usize,
    },
    /// The composition had no effective evidence at all.
    ///
    /// A weight total of zero is not a measurement of zero similarity; it is
    /// the absence of anything to weigh, and it refuses regardless of the
    /// configured threshold.
    InsufficientEvidence {
        /// The sum of the configured component weights.
        total_weight: u64,
    },
    /// The weighted composition itself could not be constructed or evaluated.
    Composition(WeightedError),
}

impl fmt::Display for EvidenceError {
    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
        match *self {
            Self::DimensionMismatch { left, right } => write!(
                formatter,
                "cosine vectors differ in length: {left} and {right}"
            ),
            Self::ZeroMagnitude => formatter.write_str("cosine vector has zero magnitude"),
            Self::NonFinite => formatter.write_str("cosine vector is not finite"),
            Self::InputTooLong { maximum, observed } => write!(
                formatter,
                "similarity input length {observed} exceeds maximum {maximum}"
            ),
            Self::CollectionTooLong { maximum, observed } => write!(
                formatter,
                "similarity collection length {observed} exceeds maximum {maximum}"
            ),
            Self::InsufficientEvidence { total_weight } => write!(
                formatter,
                "weighted similarity has no effective evidence (total weight {total_weight})"
            ),
            Self::Composition(inner) => {
                write!(formatter, "weighted similarity composition: {inner}")
            }
        }
    }
}

impl core::error::Error for EvidenceError {}

impl From<WeightedError> for EvidenceError {
    fn from(value: WeightedError) -> Self {
        Self::Composition(value)
    }
}

impl From<CosineError> for EvidenceError {
    fn from(value: CosineError) -> Self {
        match value {
            CosineError::DimensionMismatch { left, right } => {
                Self::DimensionMismatch { left, right }
            }
            CosineError::ZeroMagnitude => Self::ZeroMagnitude,
            CosineError::NonFinite => Self::NonFinite,
        }
    }
}

/// One component's outcome inside a checked composition.
///
/// The fields are private because an outcome is a report about a measurement,
/// not a value the caller may rewrite: a caller that could set `score` to
/// `Some(1.0)` on a refused component would defeat the whole contract.
#[derive(Debug, Clone, PartialEq)]
#[non_exhaustive]
pub struct ComponentOutcome {
    /// Position of this component in the composition's weight list.
    index: usize,
    /// The component's configured weight.
    weight: f64,
    /// The measured score, or [`None`] when the component refused.
    score: Option<f64>,
    /// Why this component refused, or [`None`] when it measured.
    reason: Option<EvidenceError>,
}

impl ComponentOutcome {
    /// Position of this component in the composition's weight list.
    #[must_use]
    pub const fn index(&self) -> usize {
        self.index
    }

    /// The component's configured weight.
    #[must_use]
    pub const fn weight(&self) -> f64 {
        self.weight
    }

    /// The measured score, or [`None`] when the component refused.
    ///
    /// [`None`] is the refusal signal, distinct from a measured `0.0`.
    #[must_use]
    pub const fn score(&self) -> Option<f64> {
        self.score
    }

    /// Why this component refused, or [`None`] when it measured.
    #[must_use]
    pub const fn reason(&self) -> Option<&EvidenceError> {
        self.reason.as_ref()
    }

    /// Whether this component produced a usable measurement.
    ///
    /// A refused component is never applicable, so it cannot contribute to an
    /// acceptance decision at any threshold.
    #[must_use]
    pub const fn is_applicable(&self) -> bool {
        self.score.is_some() && self.reason.is_none()
    }
}

/// One component's evidence: either a measurement or a refusal.
#[derive(Debug, Clone, PartialEq)]
#[non_exhaustive]
pub enum Evidence {
    /// A finite measured score.
    Measured {
        /// The measured score.
        value: f64,
    },
    /// The component could not be measured.
    Refused {
        /// Why it could not be measured.
        reason: EvidenceError,
    },
}

impl Evidence {
    /// Wraps a measured score as applicable evidence.
    #[must_use]
    pub const fn measured(value: f64) -> Self {
        Self::Measured { value }
    }

    /// Wraps a refusal as inapplicable evidence.
    #[must_use]
    pub const fn refused(reason: EvidenceError) -> Self {
        Self::Refused { reason }
    }

    /// Whether this evidence can be composed.
    ///
    /// A refusal is not applicable: unavailable evidence never acquires the
    /// authority of a measurement.
    #[must_use]
    pub const fn is_applicable(&self) -> bool {
        matches!(self, Self::Measured { .. })
    }

    /// The measured score, or [`None`] for a refusal.
    #[must_use]
    pub const fn value(&self) -> Option<f64> {
        match *self {
            Self::Measured { value } => Some(value),
            Self::Refused { .. } => None,
        }
    }
}

impl Similarity for EditDistance {
    type Value = str;

    fn score(&self, left: &Self::Value, right: &Self::Value) -> f64 {
        self.try_score(left, right).unwrap_or(0.0)
    }
}

/// A set-based Jaccard similarity scorer with no length ceiling.
///
/// `T` is intentionally constrained only by equality. The implementation
/// treats duplicate entries as one set member and uses bounded pairwise scans,
/// so it needs no hashing policy or third-party dependency.
///
/// The pairwise scans are `O(n²)` in the element count and this scorer declares
/// no ceiling, so it is reachable from the default `core` build with no bound at
/// all on caller-supplied input. That is stated here rather than left to be
/// discovered: prefer [`BoundedJaccard`] whenever the input comes from outside
/// the process, and use this type for small in-process sets whose size you
/// control.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub struct Jaccard<T = String> {
    /// Keeps the collection element type in the scorer's type identity.
    marker: PhantomData<fn() -> T>,
}

impl<T> Jaccard<T> {
    /// Creates an unbounded Jaccard scorer for collections of `T`.
    ///
    /// For untrusted input use [`BoundedJaccard::new`], which refuses before
    /// the quadratic scan rather than after it.
    #[must_use]
    pub const fn new() -> Self {
        Self {
            marker: PhantomData,
        }
    }
}

impl<T> Default for Jaccard<T> {
    fn default() -> Self {
        Self::new()
    }
}

/// A Jaccard scorer that refuses an over-budget element count.
///
/// The budget is charged against the *input* length, before dedup and before
/// the pairwise scans, so a hostile input is refused without paying the `O(n²)`
/// cost it was trying to cause. The refusal names the limit and the observed
/// count.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub struct BoundedJaccard<T = String> {
    /// The largest element count accepted per side.
    maximum_length: usize,
    /// Keeps the collection element type in the scorer's type identity.
    marker: PhantomData<fn() -> T>,
}

impl<T> BoundedJaccard<T> {
    /// Creates a scorer that accepts at most `maximum_length` elements per side.
    #[must_use]
    pub const fn new(maximum_length: usize) -> Self {
        Self {
            maximum_length,
            marker: PhantomData,
        }
    }

    /// Returns the maximum element count accepted per side.
    #[must_use]
    pub const fn maximum_length(&self) -> usize {
        self.maximum_length
    }
}

impl<T> Default for BoundedJaccard<T> {
    fn default() -> Self {
        Self::new(256)
    }
}

/// Scores two sets, or refuses an over-budget element count.
///
/// The empty/empty, empty/non-empty, and full-overlap cases are handled before
/// the scans, so the budget is charged against what the caller supplied rather
/// than against dedup work.
fn bounded_jaccard_score<T: PartialEq>(
    maximum_length: usize,
    left: &[T],
    right: &[T],
) -> Result<f64, EvidenceError> {
    let observed = left.len().max(right.len());
    if observed > maximum_length {
        let refusal = Err(EvidenceError::CollectionTooLong {
            maximum: maximum_length,
            observed,
        });
        #[cfg(feature = "trace")]
        crate::trace::debug!(error = ?refusal.as_ref().err(), "bounded_jaccard_score: returning an error to the caller");
        return refusal;
    }
    Ok(jaccard_unit(left, right))
}

impl<T: PartialEq + Sync> CheckedSimilarity for BoundedJaccard<T> {
    type Value = [T];

    fn try_score(&self, left: &Self::Value, right: &Self::Value) -> Result<f64, EvidenceError> {
        bounded_jaccard_score(self.maximum_length, left, right)
    }
}

impl<T: PartialEq> Similarity for BoundedJaccard<T> {
    type Value = [T];

    fn score(&self, left: &Self::Value, right: &Self::Value) -> f64 {
        bounded_jaccard_score(self.maximum_length, left, right).unwrap_or(0.0)
    }
}

impl<T: PartialEq> Similarity for Jaccard<T> {
    type Value = [T];

    fn score(&self, left: &Self::Value, right: &Self::Value) -> f64 {
        jaccard_unit(left, right)
    }
}

/// Scores two collections as sets, with no input ceiling.
///
/// `PartialEq` is the only law used, so `T` must have equivalence-like
/// equality: a type whose equality is not reflexive — `f64` with `NaN`, say —
/// does not satisfy set-identity laws and is outside the supported domain.
/// Callers scoring floats should map them to an ordered key first.
fn jaccard_unit<T: PartialEq>(left: &[T], right: &[T]) -> f64 {
    if left.is_empty() && right.is_empty() {
        return 1.0;
    }
    if left.is_empty() || right.is_empty() {
        return 0.0;
    }

    let left_unique = unique_count(left);
    let right_unique = unique_count(right);
    let intersection = left
        .iter()
        .enumerate()
        .filter(|item| {
            let index = item.0;
            let value = item.1;
            !left[..index].iter().any(|previous| previous == value)
                && right.iter().any(|candidate| candidate == value)
        })
        .fold(0.0, |count, _| count + 1.0);
    let union = left_unique + right_unique - intersection;
    unit_score(intersection / union)
}

/// Structural path similarity that ignores volatile identifiers and hashes.
///
/// Paths may use `/`, `>`, or whitespace as separators. Numeric segments and
/// generated-looking class/hash suffixes are discarded before a normalized
/// Levenshtein comparison of the remaining structural segments.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
#[non_exhaustive]
pub struct PathSimilarity;

impl PathSimilarity {
    /// Creates a structural path scorer.
    #[must_use]
    pub const fn new() -> Self {
        Self
    }
}

impl Similarity for PathSimilarity {
    type Value = str;

    fn score(&self, left: &Self::Value, right: &Self::Value) -> f64 {
        let left = normalized_path(left);
        let right = normalized_path(right);
        sequence_similarity(&left, &right)
    }
}

/// Whether two paths are exactly equal, with no normalization applied.
///
/// [`PathSimilarity`] deliberately drops numeric, hash-suffixed and
/// class-prefixed segments, so two genuinely different paths can score `1.0`.
/// That makes the score a structural heuristic, not an identity claim, and this
/// is the exact comparison a caller reaches for when it needs one. Never
/// substitute a heuristic score for this, and never use this as a canonical
/// key: a path that differs only in a dropped segment is a different path.
#[must_use]
pub fn is_exact_path_match(left: &str, right: &str) -> bool {
    left == right
}

/// A normalized four-coordinate bounding box.
///
/// Coordinates are caller-defined normalized values, commonly fractions of a
/// viewport. No coordinate is silently clipped; [`Geometry`] handles
/// non-finite values by returning the safe lower score.
#[derive(Debug, Clone, Copy, PartialEq)]
#[non_exhaustive]
pub struct BoundingBox {
    /// The normalized horizontal origin.
    x: f64,
    /// The normalized vertical origin.
    y: f64,
    /// The normalized width.
    width: f64,
    /// The normalized height.
    height: f64,
}

impl BoundingBox {
    /// Creates a bounding box from its normalized origin and dimensions.
    #[must_use]
    pub const fn new(x: f64, y: f64, width: f64, height: f64) -> Self {
        Self {
            x,
            y,
            width,
            height,
        }
    }

    /// Returns the normalized horizontal origin.
    #[must_use]
    pub const fn x(&self) -> f64 {
        self.x
    }

    /// Returns the normalized vertical origin.
    #[must_use]
    pub const fn y(&self) -> f64 {
        self.y
    }

    /// Returns the normalized width.
    #[must_use]
    pub const fn width(&self) -> f64 {
        self.width
    }

    /// Returns the normalized height.
    #[must_use]
    pub const fn height(&self) -> f64 {
        self.height
    }

    /// Returns coordinates in `(x, y, width, height)` order.
    ///
    /// Named `to_` rather than `as_` because it returns an owned array by value:
    /// the four coordinates are separate fields, so there is no contiguous
    /// array behind `&self` to borrow from, and the conversion therefore costs
    /// a copy rather than a reborrow.
    #[must_use]
    pub const fn to_array(&self) -> [f64; 4] {
        [self.x, self.y, self.width, self.height]
    }
}

impl From<[f64; 4]> for BoundingBox {
    fn from(values: [f64; 4]) -> Self {
        Self::new(values[0], values[1], values[2], values[3])
    }
}

impl From<BoundingBox> for [f64; 4] {
    fn from(value: BoundingBox) -> Self {
        value.to_array()
    }
}

/// Geometric similarity over normalized bounding boxes.
///
/// The Euclidean distance between the four coordinates is mapped with
/// `1 - distance / maximum_distance` and clamped to `[0.0, 1.0]`. A
/// non-positive or non-finite maximum is treated as an exact-match-only
/// policy, which keeps construction infallible and every score bounded.
#[derive(Debug, Clone, Copy)]
#[non_exhaustive]
pub struct Geometry {
    /// The caller-supplied distance that maps to zero similarity.
    maximum_distance: f64,
}

impl Geometry {
    /// Creates a geometry scorer with the caller-supplied maximum distance.
    #[must_use]
    pub const fn new(maximum_distance: f64) -> Self {
        Self { maximum_distance }
    }

    /// Returns the maximum distance used for normalization.
    #[must_use]
    pub const fn maximum_distance(&self) -> f64 {
        self.maximum_distance
    }

    /// Scores two equal-shaped bounding-box values.
    ///
    /// The inherent method accepts either a `[f64; 4]` or a [`BoundingBox`].
    /// The [`Similarity`] implementation below uses `[f64; 4]` as the stable
    /// trait value, so the scorer can also be placed in [`Weighted`].
    #[must_use]
    pub fn score<Value>(&self, left: &Value, right: &Value) -> f64
    where
        Value: Copy + Into<[f64; 4]>,
    {
        let left = (*left).into();
        let right = (*right).into();
        geometry_score(self.maximum_distance, &left, &right)
    }
}

impl Similarity for Geometry {
    type Value = [f64; 4];

    fn score(&self, left: &Self::Value, right: &Self::Value) -> f64 {
        geometry_score(self.maximum_distance, left, right)
    }
}

/// Why a cosine similarity was refused.
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub enum CosineError {
    /// The two vectors had different lengths.
    ///
    /// A dimension mismatch is a defect in whatever produced the vectors, not a
    /// pair of values that merely differ, so it is reported rather than scored
    /// as zero. Reporting `0.0` would make an inconsistent provider
    /// indistinguishable from two genuinely unrelated vectors.
    DimensionMismatch {
        /// Length of the left-hand vector.
        left: usize,
        /// Length of the right-hand vector.
        right: usize,
    },
    /// A vector had zero magnitude, so its angle is undefined.
    ///
    /// An all-zero vector is a direction that does not exist. It is reported
    /// apart from [`Self::NonFinite`] because the two have different causes and
    /// different repairs: a zero vector is usually an empty or padded input at
    /// the caller, where a non-finite one is a numeric fault inside whatever
    /// produced it.
    ZeroMagnitude,
    /// A vector carried a value that is not finite, so no angle can be computed.
    ///
    /// This is a *fourth* state behind a metric that most callers read as one
    /// number, and it needs to be its own variant rather than folded into
    /// [`Self::ZeroMagnitude`]. `NaN` compares `false` against everything,
    /// including itself, so a caller that lets one through a comparison reads
    /// "no measurement was possible" as "the measurement came out negative" —
    /// which is exactly the inference that must not be available. The
    /// accumulated sums are checked as well as the inputs, because a vector of
    /// finite values can still overflow to infinity.
    NonFinite,
}

impl fmt::Display for CosineError {
    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
        match *self {
            Self::DimensionMismatch { left, right } => write!(
                formatter,
                "cosine vectors differ in length: {left} and {right}"
            ),
            Self::ZeroMagnitude => formatter.write_str("cosine vector has zero magnitude"),
            Self::NonFinite => formatter.write_str("cosine vector is not finite"),
        }
    }
}

impl core::error::Error for CosineError {}

/// Cosine similarity over dense `f32` vectors, as a model's embedding produces.
///
/// The dot product and both magnitudes accumulate in `f64` even though the
/// inputs are `f32`. Summing a few hundred `f32` products in `f32` loses
/// precision exactly where it matters — near the decision threshold, where two
/// candidates are close and the ordering is the answer. `f64::from` is exact,
/// so the wider accumulator costs nothing in fidelity and no cast.
///
/// The result is clamped to `[-1.0, 1.0]`: the arithmetic cannot leave that
/// interval, so a value outside it means the inputs were not finite, and
/// clamping keeps the metric inside the range every [`Similarity`] promises.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
#[non_exhaustive]
pub struct Cosine;

impl Cosine {
    /// Creates a cosine scorer.
    #[must_use]
    pub const fn new() -> Self {
        Self
    }

    /// Calculates the cosine similarity, or reports why it is undefined.
    pub fn try_score(&self, left: &[f32], right: &[f32]) -> Result<f64, CosineError> {
        if left.len() != right.len() {
            let refusal = Err(CosineError::DimensionMismatch {
                left: left.len(),
                right: right.len(),
            });
            #[cfg(feature = "trace")]
            crate::trace::debug!(error = ?refusal.as_ref().err(), "try_score: returning an error to the caller");
            return refusal;
        }
        let mut dot = 0.0_f64;
        let mut left_squared = 0.0_f64;
        let mut right_squared = 0.0_f64;
        for (left_value, right_value) in left.iter().zip(right) {
            let left_value = f64::from(*left_value);
            let right_value = f64::from(*right_value);
            // Checked before it is accumulated, so a `NaN` component is named
            // as what it is rather than surfacing later as a `NaN` magnitude
            // that a caller could mistake for an all-zero vector.
            if !left_value.is_finite() || !right_value.is_finite() {
                let refusal = Err(CosineError::NonFinite);
                #[cfg(feature = "trace")]
                crate::trace::debug!(error = ?refusal.as_ref().err(), "try_score: returning an error to the caller");
                return refusal;
            }
            dot += left_value * right_value;
            left_squared += left_value * left_value;
            right_squared += right_value * right_value;
        }
        // Every `f32` is far below the smallest `f64` value whose square
        // overflows, so the per-component check above already implies these
        // sums are finite. The guard stays because it is the one that becomes
        // load-bearing if the element type ever widens, and because a `NaN`
        // accumulator would otherwise fall through `magnitudes <= 0.0` — `NaN`
        // compares false against everything — and return as a score.
        if !dot.is_finite() || !left_squared.is_finite() || !right_squared.is_finite() {
            let refusal = Err(CosineError::NonFinite);
            #[cfg(feature = "trace")]
            crate::trace::debug!(error = ?refusal.as_ref().err(), "try_score: returning an error to the caller");
            return refusal;
        }
        let magnitudes = left_squared.sqrt() * right_squared.sqrt();
        if magnitudes <= 0.0 {
            let refusal = Err(CosineError::ZeroMagnitude);
            #[cfg(feature = "trace")]
            crate::trace::debug!(error = ?refusal.as_ref().err(), "try_score: returning an error to the caller");
            return refusal;
        }
        Ok((dot / magnitudes).clamp(-1.0, 1.0))
    }

    /// Maps raw cosine similarity into the shared `[0.0, 1.0]` contract with
    /// `(raw + 1) / 2`.
    ///
    /// This is the one named mapping between the two domains. It is affine and
    /// monotone, so ordering is preserved: an opposite pair reads `0.0`, an
    /// orthogonal pair `0.5`, and an identical direction `1.0`. No threshold is
    /// shifted by it — a caller comparing against a raw-cosine threshold must
    /// call [`Self::try_score`], not this.
    ///
    /// # Errors
    ///
    /// Returns the same [`EvidenceError`] refusal variants as the vector
    /// scorers, for the same reasons.
    pub fn normalized_score(&self, left: &[f32], right: &[f32]) -> Result<f64, EvidenceError> {
        let raw = self.try_score(left, right)?;
        Ok(unit_score((raw + 1.0) / 2.0))
    }
}

impl Similarity for Cosine {
    type Value = [f32];

    /// Returns the normalized `(raw + 1) / 2` score, so an opposite pair reads
    /// `0.0` rather than escaping the trait's documented `[0.0, 1.0]` interval
    /// as `-1.0`. Use [`Cosine::try_score`] for the raw mathematical domain.
    fn score(&self, left: &Self::Value, right: &Self::Value) -> f64 {
        self.normalized_score(left, right).unwrap_or(0.0)
    }
}

/// Why a weighted scorer could not be constructed.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum WeightedError {
    /// No component scorer was supplied.
    Empty,
    /// A component weight was negative or non-finite.
    InvalidWeight {
        /// Index of the invalid component.
        index: usize,
    },
    /// The component weights would produce a score above `1.0`.
    WeightSumExceedsOne,
    /// The acceptance threshold was outside the finite unit interval.
    InvalidThreshold,
    /// A checked composition's scorer and weight lists had different lengths.
    WeightCountMismatch {
        /// Number of configured scorers.
        scorers: usize,
        /// Number of configured weights.
        weights: usize,
    },
}

impl fmt::Display for WeightedError {
    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
        match *self {
            Self::Empty => formatter.write_str("weighted similarity needs a component"),
            Self::InvalidWeight { index } => {
                write!(
                    formatter,
                    "weighted similarity has invalid weight at {index}"
                )
            }
            Self::WeightSumExceedsOne => {
                formatter.write_str("weighted similarity weights must sum to at most 1.0")
            }
            Self::InvalidThreshold => {
                formatter.write_str("weighted similarity threshold must be in [0.0, 1.0]")
            }
            Self::WeightCountMismatch { scorers, weights } => write!(
                formatter,
                "weighted similarity has {scorers} scorers and {weights} weights"
            ),
        }
    }
}

impl core::error::Error for WeightedError {}

/// A weighted composition of replaceable similarity scorers.
///
/// Components are evaluated as `sum(weight * score)`. Construction rejects an
/// empty component set, invalid weights, and totals above `1.0`, preserving the
/// range promised by [`Similarity`].
pub struct Weighted<Value: ?Sized> {
    /// Non-empty scorers and their bounded non-negative weights.
    components: Vec<(f64, Box<dyn Similarity<Value = Value>>)>,
    /// The score at or above which [`Self::is_accepted`] returns `true`.
    threshold: f64,
}

/// Refuses a weighted scorer built from nothing.
///
/// Shared by both constructors so the empty case has one refusal and one place
/// it is reported from.
fn require_present(count: usize) -> Result<(), WeightedError> {
    if count == 0 {
        let refusal = Err(WeightedError::Empty);
        #[cfg(feature = "trace")]
        crate::trace::debug!(error = ?refusal.as_ref().err(), "weighted scorer: there are no components");
        return refusal;
    }
    Ok(())
}

/// Refuses an acceptance threshold or weight set outside the declared policy:
/// the threshold must lie in `[0, 1]`, each weight must be finite and
/// non-negative, and the weights may not sum past one.
///
/// Shared by both constructors, so the plain and the checked scorer cannot come
/// to disagree about which policies are legal. The threshold is judged before
/// the weights, as both constructors always did.
fn validate_policy(
    threshold: f64,
    weights: impl Iterator<Item = f64>,
) -> Result<(), WeightedError> {
    if !threshold.is_finite() || !(0.0..=1.0).contains(&threshold) {
        let refusal = Err(WeightedError::InvalidThreshold);
        #[cfg(feature = "trace")]
        crate::trace::debug!(error = ?refusal.as_ref().err(), threshold, "weighted scorer: the threshold is outside [0, 1]");
        return refusal;
    }
    let mut total = 0.0;
    for (index, weight) in weights.enumerate() {
        if !weight.is_finite() || weight < 0.0 {
            let refusal = Err(WeightedError::InvalidWeight { index });
            #[cfg(feature = "trace")]
            crate::trace::debug!(error = ?refusal.as_ref().err(), index, weight, "weighted scorer: the weight is not finite and non-negative");
            return refusal;
        }
        total += weight;
    }
    if total > 1.0 {
        let refusal = Err(WeightedError::WeightSumExceedsOne);
        #[cfg(feature = "trace")]
        crate::trace::debug!(error = ?refusal.as_ref().err(), total, "weighted scorer: the weights sum past one");
        return refusal;
    }
    Ok(())
}

impl<Value: ?Sized> Weighted<Value> {
    /// Creates a weighted scorer and its acceptance threshold.
    pub fn new(
        components: Vec<(f64, Box<dyn Similarity<Value = Value>>)>,
        threshold: f64,
    ) -> Result<Self, WeightedError> {
        require_present(components.len())?;
        validate_policy(threshold, components.iter().map(|component| component.0))?;

        Ok(Self {
            components,
            threshold,
        })
    }

    /// Returns the acceptance threshold.
    #[must_use]
    pub const fn threshold(&self) -> f64 {
        self.threshold
    }

    /// Scores the pair and reports whether it reaches the configured threshold.
    ///
    /// This is the infallible adapter: a refused component reaches it as `0.0`,
    /// so an unavailable component satisfies a threshold of `0.0`. Prefer
    /// [`CheckedEvidence::verdict`], which retains the refusal.
    #[must_use]
    pub fn is_accepted(&self, left: &Value, right: &Value) -> bool {
        self.score(left, right) >= self.threshold
    }

    /// Returns the sum of the configured component weights.
    ///
    /// A total below `1.0` is a deliberate evidence deficit: the composition's
    /// maximum is that total, not `1.0`, and it is never renormalized away.
    #[must_use]
    pub fn total_weight(&self) -> f64 {
        self.components
            .iter()
            .fold(0.0, |sum, component| sum + component.0)
    }
}

impl<Value: ?Sized> core::fmt::Debug for Weighted<Value> {
    /// Reports the composition rather than the components.
    ///
    /// The component list is a set of `dyn Similarity` trait objects, so a
    /// derived `Debug` would print pointers instead of policy: the useful
    /// facts are how many scorers there are and where the acceptance line
    /// sits.
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        f.debug_struct("Weighted")
            .field("components", &self.components.len())
            .field("weights", &WeightList(self))
            .field("threshold", &self.threshold)
            .finish_non_exhaustive()
    }
}

/// The component weights, formatted in composition order.
struct WeightList<'a, Value: ?Sized>(&'a Weighted<Value>);

impl<Value: ?Sized> core::fmt::Debug for WeightList<'_, Value> {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        f.debug_list()
            .entries(self.0.components.iter().map(|component| component.0))
            .finish()
    }
}

impl<Value: ?Sized> Similarity for Weighted<Value> {
    type Value = Value;

    fn score(&self, left: &Self::Value, right: &Self::Value) -> f64 {
        let total = self.components.iter().fold(0.0, |sum, component| {
            sum + (component.0 * unit_score(component.1.score(left, right)))
        });
        unit_score(total)
    }
}

/// A scorer that reports a refusal instead of folding it into a number.
///
/// [`Similarity`] is the numeric seam every scorer can satisfy; this is the
/// checked seam a scorer that can refuse also satisfies, so a composition can
/// carry the refusal rather than losing it at a trait-object boundary.
///
/// [`Clone`] is a supertrait rather than a bound on the boxed trait object
/// because Rust permits only auto traits there. The requirement is real
/// rather than convenience: [`CheckedEvidence`] is clonable so a caller can
/// hand each tenant its own policy, and a component that could not be copied
/// would make that impossible to state.
pub trait CheckedSimilarity {
    /// The value type accepted by this scorer.
    ///
    /// [`Sync`] because [`CheckedEvidence`] is shareable across threads and a
    /// scorer that were not would make that a lie: the composition reads its
    /// components from `&self` on every call.
    type Value: ?Sized + Sync;

    /// Scores the pair, or reports why it could not be measured.
    ///
    /// # Errors
    ///
    /// Returns [`EvidenceError`] naming the reason the measurement is
    /// unavailable. Every refusal is a variant of that enum; none of them is a
    /// score.
    fn try_score(&self, left: &Self::Value, right: &Self::Value) -> Result<f64, EvidenceError>;
}

impl CheckedSimilarity for EditDistance {
    type Value = str;

    fn try_score(&self, left: &Self::Value, right: &Self::Value) -> Result<f64, EvidenceError> {
        EditDistance::try_score(self, left, right).map_err(EvidenceError::from)
    }
}

impl CheckedSimilarity for Cosine {
    type Value = [f32];

    /// Returns the raw `[-1, 1]` cosine, not the normalized mapping, so a
    /// caller reading a weighted composition sees the domain it declared. Use
    /// [`Cosine::normalized_score`] for the unit interval.
    fn try_score(&self, left: &Self::Value, right: &Self::Value) -> Result<f64, EvidenceError> {
        Cosine::try_score(self, left, right).map_err(EvidenceError::from)
    }
}

impl CheckedSimilarity for Geometry {
    type Value = [f64; 4];

    fn try_score(&self, left: &Self::Value, right: &Self::Value) -> Result<f64, EvidenceError> {
        Ok(Similarity::score(self, left, right))
    }
}

/// A weighted composition that preserves each component's refusal.
///
/// This is the authority-facing path. [`Weighted`] stays available for callers
/// that want a bare number and accept that a refusal reads as `0.0`;
/// [`CheckedEvidence`] keeps "could not measure" distinct from "measured
/// zero" all the way to the acceptance decision.
///
/// # Sharing one policy across threads
///
/// One `CheckedEvidence` serves any number of concurrent callers, and
/// [`verdict`] takes `&self`. That is only true because the policy is
/// immutable, so the contract is carried on the types rather than left to
/// inference:
///
/// - [`CheckedSimilarity::Value`] is [`Sync`], and [`CheckedEvidence::new`]
///   takes `Box<dyn CheckedSimilarity<Value = Value> + Send + Sync>`.
/// - Every scorer shipped here is `Copy` with no interior mutability, so the
///   bounds are satisfied without a lock.
/// - [`CheckedSimilarity::Value`] being [`Sync`] is what lets a caller hold a
///   `&str` or a `&[f32]` across the concurrent calls it shares.
///
/// A caller whose own scorer is not `Sync` still composes: the trait carries
/// the bound, so such a scorer cannot be installed rather than silently
/// producing a policy that is `Sync` on the outside and racy inside.
///
/// The per-tenant route is to build one composition per tenant rather than to
/// share one. Two [`CheckedEvidence`] values built from the same scorer type are
/// already two independent configurations, and that is the shape
/// `tests/sim_tenant_isolation.rs` drives across three tenants at every
/// concurrency tier.
///
/// [`verdict`]: CheckedEvidence::verdict
///
/// ```
/// use lgwks_std::similarity::{CheckedEvidence, CheckedSimilarity, EditDistance};
///
/// let policy = CheckedEvidence::new(
///     vec![Box::new(EditDistance::new(3))],
///     vec![1.0],
///     0.0,
/// )?;
/// // The input is over budget, so it is refused rather than scored 0.0.
/// let verdict = policy.verdict("four", "four")?;
/// assert!(!verdict.is_accepted());
/// assert_eq!(verdict.score(), None);
/// assert_eq!(verdict.refusals()[0].index(), 0);
/// // One policy, shared: the bound that makes it shareable is part of the API.
/// fn shared<T: Sync>(value: T) -> std::sync::Arc<T> {
///     std::sync::Arc::new(value)
/// }
/// let shared = shared(policy);
/// /// // Within the three-character budget, so the same policy measures rather than
/// // refuses, and one `Arc` hands the identical value to any number of callers.
/// assert!(shared.verdict("cat", "cat")?.is_accepted());
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
pub struct CheckedEvidence<Value: ?Sized> {
    /// The component scorers, in configuration order.
    scorers: Vec<Box<dyn CheckedSimilarity<Value = Value> + Send + Sync>>,
    /// Each component's bounded non-negative weight, parallel to `scorers`.
    weights: Vec<f64>,
    /// The score at or above which a measured verdict accepts.
    threshold: f64,
}

impl<Value: ?Sized + Sync> CheckedEvidence<Value> {
    /// Creates a checked composition from parallel scorer and weight lists.
    ///
    /// The two lists must be the same length. Weights are validated exactly as
    /// [`Weighted::new`] validates them: finite, non-negative, totalling at
    /// most `1.0`. A total of `0.0` is accepted here and refused at evaluation
    /// time as [`EvidenceError::InsufficientEvidence`], so the policy can be
    /// constructed and inspected while still never producing a verdict from
    /// nothing.
    ///
    /// # Errors
    ///
    /// Returns [`WeightedError::Empty`] for no components,
    /// [`WeightedError::InvalidWeight`] for a negative or non-finite weight,
    /// [`WeightedError::WeightSumExceedsOne`] for a total above `1.0`, and
    /// [`WeightedError::InvalidThreshold`] for a threshold outside `[0, 1]`.
    pub fn new(
        scorers: Vec<Box<dyn CheckedSimilarity<Value = Value> + Send + Sync>>,
        weights: Vec<f64>,
        threshold: f64,
    ) -> Result<Self, WeightedError> {
        require_present(scorers.len())?;
        if scorers.len() != weights.len() {
            let refusal = Err(WeightedError::WeightCountMismatch {
                scorers: scorers.len(),
                weights: weights.len(),
            });
            #[cfg(feature = "trace")]
            crate::trace::debug!(error = ?refusal.as_ref().err(), scorers = scorers.len(), weights = weights.len(), "checked weighted scorer: every scorer needs exactly one weight");
            return refusal;
        }
        validate_policy(threshold, weights.iter().copied())?;
        Ok(Self {
            scorers,
            weights,
            threshold,
        })
    }

    /// Returns the acceptance threshold.
    #[must_use]
    pub const fn threshold(&self) -> f64 {
        self.threshold
    }

    /// Returns the sum of the configured component weights.
    #[must_use]
    pub fn total_weight(&self) -> f64 {
        self.weights.iter().fold(0.0, |sum, weight| sum + weight)
    }

    /// Evaluates every component and returns the verdict.
    ///
    /// When any component refuses, the verdict's `score` is [`None`] and
    /// `is_accepted` is `false` at every threshold, including `0.0`: a refusal
    /// is not a measurement of zero. Each refusal is attributed to its
    /// component index and retains its typed reason.
    ///
    /// The surviving weights are not renormalized. A missing component leaves an
    /// evidence deficit rather than inflating its neighbours to cover the gap,
    /// so geometry alone can never acquire a missing identity field's authority.
    ///
    /// # Errors
    ///
    /// Returns [`EvidenceError::InsufficientEvidence`] when the weight total is
    /// zero: there is nothing to weigh, which is not a measurement of zero
    /// similarity.
    pub fn verdict(&self, left: &Value, right: &Value) -> Result<EvidenceVerdict, EvidenceError> {
        let total_weight = self.total_weight();
        if total_weight <= 0.0 {
            let refusal = Err(EvidenceError::InsufficientEvidence {
                total_weight: total_weight.to_bits(),
            });
            #[cfg(feature = "trace")]
            crate::trace::debug!(error = ?refusal.as_ref().err(), "verdict: returning an error to the caller");
            return refusal;
        }

        let mut outcomes = Vec::with_capacity(self.scorers.len());
        let mut measured_total = 0.0;
        let mut refusals = 0_usize;
        for (index, scorer) in self.scorers.iter().enumerate() {
            let weight = self.weights[index];
            match scorer.try_score(left, right) {
                Ok(score) => {
                    measured_total += weight * score;
                    outcomes.push(ComponentOutcome {
                        index,
                        weight,
                        score: Some(score),
                        reason: None,
                    });
                }
                Err(reason) => {
                    refusals = refusals.saturating_add(1);
                    outcomes.push(ComponentOutcome {
                        index,
                        weight,
                        score: None,
                        reason: Some(reason),
                    });
                }
            }
        }

        if refusals > 0 {
            return Ok(EvidenceVerdict {
                score: None,
                is_accepted: false,
                outcomes,
            });
        }
        let score = unit_score(measured_total);
        Ok(EvidenceVerdict {
            score: Some(score),
            is_accepted: score >= self.threshold,
            outcomes,
        })
    }
}

impl<Value: ?Sized + Sync> core::fmt::Debug for CheckedEvidence<Value> {
    /// Reports the composition policy rather than the scorer identities.
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        f.debug_struct("CheckedEvidence")
            .field("components", &self.scorers.len())
            .field("weights", &self.weights)
            .field("threshold", &self.threshold)
            .finish()
    }
}

/// A checked composition's verdict: what was measured, what refused, and
/// whether the pair is accepted.
///
/// The score is [`None`] whenever any component refused, so a refusal is never
/// read as a number, and the composition is then not accepted at any
/// threshold, including `0.0`.
#[derive(Debug, Clone, PartialEq)]
#[non_exhaustive]
pub struct EvidenceVerdict {
    /// The composed score, or [`None`] when any component refused.
    score: Option<f64>,
    /// Whether the composition reaches the configured threshold.
    ///
    /// Always `false` when the score is [`None`].
    is_accepted: bool,
    /// Each component's index, weight, score, and refusal reason.
    outcomes: Vec<ComponentOutcome>,
}

impl EvidenceVerdict {
    /// Returns the composed score, or [`None`] when any component refused.
    ///
    /// [`None`] is the refusal signal: it is distinct from a measured `0.0`,
    /// and it never satisfies a threshold.
    #[must_use]
    pub const fn score(&self) -> Option<f64> {
        self.score
    }

    /// Whether the composition reaches the configured threshold.
    ///
    /// Always `false` when [`Self::score`] is [`None`].
    #[must_use]
    pub const fn is_accepted(&self) -> bool {
        self.is_accepted
    }

    /// Returns each component's outcome, in composition order.
    #[must_use]
    pub fn outcomes(&self) -> &[ComponentOutcome] {
        &self.outcomes
    }

    /// Returns only the components that refused, in composition order.
    #[must_use]
    pub fn refusals(&self) -> Vec<&ComponentOutcome> {
        self.outcomes
            .iter()
            .filter(|outcome| outcome.reason.is_some())
            .collect()
    }
}

/// Converts a finite candidate into the similarity contract's unit interval.
fn unit_score(candidate: f64) -> f64 {
    if candidate.is_finite() {
        candidate.clamp(0.0, 1.0)
    } else {
        0.0
    }
}

/// Normalizes text without allocating until the raw bound has been checked.
fn normalize_text(input: &str, maximum: usize) -> Result<Vec<char>, EditDistanceError> {
    let mut observed = 0usize;
    for _ in input.chars() {
        observed = observed.saturating_add(1);
        if observed > maximum {
            let refusal = Err(EditDistanceError::InputTooLong { maximum, observed });
            #[cfg(feature = "trace")]
            crate::trace::debug!(error = ?refusal.as_ref().err(), "normalize_text: returning an error to the caller");
            return refusal;
        }
    }

    let mut normalized = Vec::with_capacity(observed);
    let mut pending_space = false;
    for character in input.chars() {
        if character.is_whitespace() {
            if !normalized.is_empty() {
                pending_space = true;
            }
            continue;
        }
        if pending_space {
            normalized.push(' ');
            pending_space = false;
        }
        for lower in character.to_lowercase() {
            normalized.push(lower);
        }
    }

    if normalized.len() > maximum {
        let refusal = Err(EditDistanceError::InputTooLong {
            maximum,
            observed: normalized.len(),
        });
        #[cfg(feature = "trace")]
        crate::trace::debug!(error = ?refusal.as_ref().err(), "normalize_text: returning an error to the caller");
        return refusal;
    }
    Ok(normalized)
}

/// Computes normalized Levenshtein similarity with one rolling row.
fn sequence_similarity<T: PartialEq>(left: &[T], right: &[T]) -> f64 {
    if left.is_empty() && right.is_empty() {
        return 1.0;
    }
    if left.is_empty() || right.is_empty() {
        return 0.0;
    }

    let (rows, columns) = if left.len() < right.len() {
        (left, right)
    } else {
        (right, left)
    };

    let mut previous: Vec<f64> = Vec::with_capacity(columns.len().saturating_add(1));
    let mut denominator = 0.0f64;
    previous.push(0.0);
    for _ in columns {
        denominator += 1.0;
        previous.push(denominator);
    }
    let mut current: Vec<f64> = vec![0.0; columns.len().saturating_add(1)];
    let mut row_distance = 1.0;
    for row_value in rows {
        current[0] = row_distance;
        for (column_index, column_value) in columns.iter().enumerate() {
            let cost = if row_value == column_value { 0.0 } else { 1.0 };
            let index = column_index.saturating_add(1);
            let deletion = previous[index] + 1.0;
            let insertion = current[column_index] + 1.0;
            let substitution = previous[column_index] + cost;
            current[index] = deletion.min(insertion).min(substitution);
        }
        core::mem::swap(&mut previous, &mut current);
        row_distance += 1.0;
    }

    unit_score(1.0 - (previous[columns.len()] / denominator))
}

/// Counts distinct values without requiring a hashing policy.
fn unique_count<T: PartialEq>(values: &[T]) -> f64 {
    values
        .iter()
        .enumerate()
        .filter(|item| {
            let index = item.0;
            let value = item.1;
            !values[..index].iter().any(|previous| previous == value)
        })
        .fold(0.0, |count, _| count + 1.0)
}

/// Removes path syntax and volatile segments while borrowing the input.
fn normalized_path(path: &str) -> Vec<&str> {
    let mut segments = Vec::new();
    for part in path.split(|character: char| {
        character == '/' || character == '\\' || character == '>' || character.is_whitespace()
    }) {
        for component in part.split(['#', '.']) {
            let component = component.trim();
            if !component.is_empty() && !is_volatile_segment(component) {
                segments.push(component);
            }
        }
    }
    segments
}

/// Recognizes numeric ids and common generated class/hash suffixes.
fn is_volatile_segment(segment: &str) -> bool {
    let bytes = segment.as_bytes();
    if bytes.is_empty() || bytes.iter().all(|byte| byte.is_ascii_digit()) {
        return true;
    }
    if bytes.len() >= 6 && bytes.iter().all(|byte| byte.is_ascii_hexdigit()) {
        return true;
    }

    let suffix_is_numeric =
        |suffix: &str| !suffix.is_empty() && suffix.bytes().all(|byte| byte.is_ascii_digit());
    let suffix_is_hash = |suffix: &str| {
        suffix.len() >= 6
            && suffix.bytes().all(|byte| byte.is_ascii_alphanumeric())
            && suffix.bytes().any(|byte| byte.is_ascii_digit())
    };
    if let Some((_, suffix)) = segment.rsplit_once(['-', '_'])
        && (suffix_is_numeric(suffix) || suffix_is_hash(suffix))
    {
        return true;
    }
    ["css-", "sc-", "jsx-", "emotion-", "hash-"]
        .iter()
        .any(|prefix| {
            segment.strip_prefix(prefix).is_some_and(|suffix| {
                suffix.len() >= 4 && suffix.bytes().all(|byte| byte.is_ascii_alphanumeric())
            })
        })
}

/// Computes normalized Euclidean similarity for four coordinates.
fn geometry_score(maximum_distance: f64, left: &[f64; 4], right: &[f64; 4]) -> f64 {
    let mut squared_distance = 0.0;
    for (left_value, right_value) in left.iter().zip(right.iter()) {
        let difference = *left_value - *right_value;
        if !difference.is_finite() {
            return 0.0;
        }
        squared_distance = difference.mul_add(difference, squared_distance);
        if !squared_distance.is_finite() {
            return 0.0;
        }
    }
    let distance = squared_distance.sqrt();
    if !distance.is_finite() {
        return 0.0;
    }
    if maximum_distance.is_finite() && maximum_distance > 0.0 {
        unit_score(1.0 - (distance / maximum_distance))
    } else if distance <= f64::EPSILON {
        1.0
    } else {
        0.0
    }
}

// ── Tests ───────────────────────────────────────────────────────────────────

#[cfg(test)]
mod tests {
    use super::*;

    fn assert_unit(value: f64) {
        assert!(value.is_finite(), "similarity must be finite: {value}");
        assert!(
            (0.0..=1.0).contains(&value),
            "similarity outside [0, 1]: {value}"
        );
    }

    /// Compares floating-point outputs without relying on exact arithmetic.
    fn assert_close(actual: f64, expected: f64) {
        assert!(
            (actual - expected).abs() < 1e-12,
            "expected {expected}, got {actual}"
        );
    }

    /// Erases one edit scorer for a weighted composition without a cast.
    fn boxed_edit_distance(maximum_length: usize) -> Box<dyn Similarity<Value = str>> {
        Box::new(EditDistance::new(maximum_length))
    }

    #[test]
    fn edit_distance_handles_empty_and_identical_inputs() -> Result<(), EditDistanceError> {
        let scorer = EditDistance::new(16);
        assert_close(scorer.try_score("", "")?, 1.0);
        assert_close(scorer.try_score("same", "same")?, 1.0);
        assert_close(scorer.try_score("", "text")?, 0.0);
        assert_close(scorer.try_score("text", "")?, 0.0);
        assert_close(scorer.try_score("  SAME ", "same")?, 1.0);
        Ok(())
    }

    #[test]
    fn edit_distance_normalizes_known_distance() -> Result<(), EditDistanceError> {
        let scorer = EditDistance::new(16);
        let score = scorer.try_score("kitten", "sitting")?;
        assert!((score - (4.0 / 7.0)).abs() < 1e-12, "score was {score}");
        Ok(())
    }

    #[test]
    fn edit_distance_refuses_over_limit_inputs() -> Result<(), EditDistanceError> {
        let scorer = EditDistance::new(3);
        assert_close(scorer.try_score("abc", "abc")?, 1.0);
        assert!(matches!(
            scorer.try_score("four", "four"),
            Err(EditDistanceError::InputTooLong {
                maximum: 3,
                observed: 4
            })
        ));
        assert_close(scorer.score("four", "four"), 0.0);
        assert!(
            scorer.score("four", "four") <= 0.0,
            "the infallible trait method must map refusal to no similarity"
        );
        Ok(())
    }

    #[test]
    fn every_evidence_error_variant_is_exercised_by_a_test() {
        // Each variant of the refusal enum is produced here, so a new variant
        // without a producer fails this test rather than sitting unreachable.
        let produced: Vec<EvidenceError> = vec![
            EvidenceError::from(EditDistanceError::InputTooLong {
                maximum: 1,
                observed: 2,
            }),
            EvidenceError::from(CosineError::DimensionMismatch { left: 1, right: 2 }),
            EvidenceError::from(CosineError::ZeroMagnitude),
            EvidenceError::from(CosineError::NonFinite),
            EvidenceError::CollectionTooLong {
                maximum: 1,
                observed: 2,
            },
            EvidenceError::InsufficientEvidence {
                total_weight: 0.0_f64.to_bits(),
            },
            EvidenceError::from(WeightedError::Empty),
            EvidenceError::from(WeightedError::InvalidWeight { index: 0 }),
            EvidenceError::from(WeightedError::WeightSumExceedsOne),
            EvidenceError::from(WeightedError::InvalidThreshold),
            EvidenceError::from(WeightedError::WeightCountMismatch {
                scorers: 2,
                weights: 1,
            }),
        ];
        assert_eq!(
            produced.len(),
            11,
            "every EvidenceError variant is produced exactly once"
        );
        // Each renders, and each conversion preserves the variant it came from.
        for reason in &produced {
            assert!(
                !reason.to_string().is_empty(),
                "{reason:?} must render a message"
            );
        }
        assert_eq!(
            EvidenceError::from(CosineError::ZeroMagnitude),
            EvidenceError::ZeroMagnitude,
            "a zero magnitude stays its own refusal through conversion"
        );
        assert_ne!(
            EvidenceError::ZeroMagnitude.to_string(),
            EvidenceError::NonFinite.to_string(),
            "the two vector refusals must not render identically"
        );
        assert_ne!(
            EvidenceError::InputTooLong {
                maximum: 1,
                observed: 2
            }
            .to_string(),
            EvidenceError::CollectionTooLong {
                maximum: 1,
                observed: 2
            }
            .to_string(),
            "the text and set budgets must name themselves apart"
        );
    }

    #[test]
    fn bounded_jaccard_refuses_before_the_quadratic_scan() -> Result<(), EvidenceError> {
        let scorer = BoundedJaccard::<u32>::new(2);
        assert_close(
            CheckedSimilarity::try_score(&scorer, &[1, 2], &[2, 1])?,
            1.0,
        );
        assert_eq!(
            CheckedSimilarity::try_score(&scorer, &[1, 2, 3], &[1, 2]),
            Err(EvidenceError::CollectionTooLong {
                maximum: 2,
                observed: 3
            }),
            "an over-budget set is refused with its limit, before dedup"
        );
        assert_close(Similarity::score(&scorer, &[], &[]), 1.0);
        Ok(())
    }

    #[test]
    fn the_normalized_budget_unit_is_the_expanded_scalar_count() -> Result<(), EditDistanceError> {
        let tight = EditDistance::new(1);
        assert_eq!(
            tight.normalized_length("i"),
            1,
            "an ASCII scalar normalizes to itself"
        );
        assert_eq!(
            tight.normalized_length("İ"),
            2,
            "`İ` lower-cases to two scalars, and that is the charged unit"
        );
        assert_eq!(
            tight.try_score("İ", "i"),
            Err(EditDistanceError::InputTooLong {
                maximum: 1,
                observed: 2
            }),
            "a budget of one refuses the expanded scalar, not the raw count"
        );
        let roomy = EditDistance::new(2);
        // With room for the expansion, the pair is one edit over two scalars.
        assert_close(roomy.try_score("İ", "i")?, 0.5);
        Ok(())
    }

    #[test]
    fn jaccard_handles_boundary_sets() {
        let scorer = Jaccard::<&str>::new();
        assert_close(scorer.score(&[], &[]), 1.0);
        assert_close(scorer.score(&["a", "b"], &["a", "b"]), 1.0);
        assert_close(scorer.score(&["a"], &["b"]), 0.0);
        assert_close(scorer.score(&["a", "a"], &["a"]), 1.0);
    }

    #[test]
    fn cosine_scores_known_angles() -> Result<(), CosineError> {
        let scorer = Cosine::new();
        // Identical direction, different magnitude: the magnitude cancels, and
        // that is the property that makes cosine the right metric for an
        // embedding, where a longer vector is not a closer one.
        assert_close(scorer.try_score(&[1.0, 2.0, 3.0], &[2.0, 4.0, 6.0])?, 1.0);
        assert_close(scorer.try_score(&[1.0, 0.0], &[0.0, 1.0])?, 0.0);
        assert_close(scorer.try_score(&[1.0, 0.0], &[-1.0, 0.0])?, -1.0);
        // 45 degrees: cos(pi/4).
        let diagonal = scorer.try_score(&[1.0, 0.0], &[1.0, 1.0])?;
        assert!((diagonal - core::f64::consts::FRAC_1_SQRT_2).abs() < 1e-12);
        Ok(())
    }

    #[test]
    fn cosine_refuses_a_dimension_mismatch_rather_than_scoring_zero() {
        let scorer = Cosine::new();
        assert!(matches!(
            scorer.try_score(&[1.0, 0.0], &[1.0, 0.0, 0.0]),
            Err(CosineError::DimensionMismatch { left: 2, right: 3 })
        ));
        // The infallible trait method still maps refusal to no similarity, so a
        // caller that ignores the typed error cannot read refusal as a match.
        assert_close(scorer.score(&[1.0, 0.0], &[1.0, 0.0, 0.0]), 0.0);
    }

    #[test]
    fn cosine_refuses_a_zero_magnitude_vector() {
        let scorer = Cosine::new();
        assert!(matches!(
            scorer.try_score(&[0.0, 0.0], &[1.0, 0.0]),
            Err(CosineError::ZeroMagnitude)
        ));
        assert!(matches!(
            scorer.try_score(&[], &[]),
            Err(CosineError::ZeroMagnitude)
        ));
    }

    #[test]
    fn cosine_names_a_non_finite_vector_apart_from_a_zero_magnitude_one() {
        let scorer = Cosine::new();
        // A `NaN` component on either side, and an infinity on either side. All
        // four are refused as `NonFinite`, not as `ZeroMagnitude`: the two have
        // different repairs, and reporting the wrong one sends the operator to
        // the wrong end of the pipeline.
        for (left, right) in [
            (&[f32::NAN, 1.0][..], &[1.0, 1.0][..]),
            (&[1.0, 1.0][..], &[f32::NAN, 1.0][..]),
            (&[f32::INFINITY, 1.0][..], &[1.0, 1.0][..]),
            (&[1.0, 1.0][..], &[1.0, f32::NEG_INFINITY][..]),
        ] {
            assert!(
                matches!(scorer.try_score(left, right), Err(CosineError::NonFinite)),
                "a non-finite vector must be refused as NonFinite: {left:?} {right:?}"
            );
        }
        // The distinction has to reach the operator, so it is carried by the
        // rendered message and not only by the variant name.
        assert_ne!(
            CosineError::NonFinite.to_string(),
            CosineError::ZeroMagnitude.to_string(),
            "the two refusals must not render identically"
        );
    }

    #[test]
    fn cosine_never_returns_a_non_finite_score_from_the_infallible_method() {
        let scorer = Cosine::new();
        // This is the property the typed error protects. A caller that reads
        // only the trait method gets `0.0` — "no similarity" — and never `NaN`,
        // which would compare false against every threshold and turn "we could
        // not measure this" into "this did not match".
        let score = scorer.score(&[f32::NAN, 1.0], &[1.0, 1.0]);
        assert!(score.is_finite(), "the infallible method returned {score}");
        assert_close(score, 0.0);
        assert_close(scorer.score(&[f32::INFINITY, 1.0], &[1.0, 1.0]), 0.0);
    }

    #[test]
    fn cosine_stays_inside_the_contract_interval() -> Result<(), CosineError> {
        let scorer = Cosine::new();
        // `f32::from(u16)` is lossless and needs no cast; the second vector is
        // the first scaled, so the two are the same direction by construction.
        let wide: Vec<f32> = (0_u16..64).map(f32::from).collect();
        let narrow: Vec<f32> = wide.iter().map(|value| value * 0.5).collect();
        for (left, right) in [(&wide, &narrow), (&narrow, &wide)] {
            let score = scorer.try_score(left, right)?;
            assert!(
                (-1.0..=1.0).contains(&score),
                "score {score} left the contract interval"
            );
        }
        assert_close(scorer.try_score(&wide, &narrow)?, 1.0);
        Ok(())
    }

    #[test]
    fn path_similarity_discards_volatile_segments() {
        let scorer = PathSimilarity::new();
        assert_close(
            scorer.score(
                "html/body/div/123/button.css-a1b2c3",
                "html/body/div/987/button.css-z9y8x7",
            ),
            1.0,
        );
        assert_close(scorer.score("root/left", "root/right"), 0.5);
        assert_close(scorer.score("", ""), 1.0);
        assert_close(scorer.score("left", "right"), 0.0);
    }

    #[test]
    fn geometry_maps_zero_and_maximum_distance() {
        let scorer = Geometry::new(2.0);
        let origin = [0.0, 0.0, 0.0, 0.0];
        let far = [2.0, 0.0, 0.0, 0.0];
        assert_close(scorer.score(&origin, &origin), 1.0);
        assert_close(scorer.score(&origin, &far), 0.0);
        assert_close(scorer.score(&origin, &[1.0, 0.0, 0.0, 0.0]), 0.5);
    }

    #[test]
    fn bounding_box_accessors_preserve_coordinates() {
        let box_value = BoundingBox::new(0.1, 0.2, 0.3, 0.4);
        assert_close(box_value.x(), 0.1);
        assert_close(box_value.y(), 0.2);
        assert_close(box_value.width(), 0.3);
        assert_close(box_value.height(), 0.4);
        for (actual, expected) in box_value.to_array().iter().zip([0.1, 0.2, 0.3, 0.4]) {
            assert_close(*actual, expected);
        }
    }

    #[test]
    fn weighted_rejects_empty_components() {
        let result = Weighted::<str>::new(Vec::new(), 0.5);
        assert!(matches!(result, Err(WeightedError::Empty)));
    }

    #[test]
    fn weighted_single_vector_returns_that_vectors_score() -> Result<(), WeightedError> {
        let direct = EditDistance::new(16);
        let weighted = Weighted::<str>::new(vec![(1.0, boxed_edit_distance(16))], 0.8)?;
        assert_close(
            weighted.score("kitten", "sitting"),
            direct.score("kitten", "sitting"),
        );
        assert!(!weighted.is_accepted("kitten", "sitting"));
        Ok(())
    }

    #[test]
    fn every_metric_stays_in_unit_interval_for_fixed_inputs() -> Result<(), WeightedError> {
        let edit = EditDistance::new(32);
        for (left, right) in [("", ""), ("a", "b"), ("short", "longer"), ("A B", "a b")] {
            assert_unit(edit.score(left, right));
        }

        let sets = Jaccard::<&str>::new();
        for (left, right) in [
            (&[][..], &[][..]),
            (&["a"][..], &["b"][..]),
            (&["a", "b"][..], &["b", "c"][..]),
        ] {
            assert_unit(sets.score(left, right));
        }

        let paths = PathSimilarity::new();
        for (left, right) in [("", ""), ("root/1", "root/2"), ("a", "b/c")] {
            assert_unit(paths.score(left, right));
        }

        let geometry = Geometry::new(1.0);
        for (left, right) in [
            ([0.0, 0.0, 0.0, 0.0], [0.0, 0.0, 0.0, 0.0]),
            ([0.0, 0.0, 0.0, 0.0], [1.0, 1.0, 1.0, 1.0]),
            ([0.5, 0.5, 0.25, 0.25], [0.25, 0.25, 0.5, 0.5]),
        ] {
            assert_unit(geometry.score(&left, &right));
        }

        let weighted = Weighted::<str>::new(vec![(1.0, boxed_edit_distance(32))], 0.5)?;
        for (left, right) in [
            ("", ""),
            ("same", "same"),
            ("a", "b"),
            ("too long", "too long"),
        ] {
            assert_unit(weighted.score(left, right));
        }
        Ok(())
    }
}