vyre 0.4.0

use crate::ops::string_similarity::validation::{to_u32, validate_dp_product, validate_pair, SimilarityError};

// CPU reference kernel for `string_similarity.levenshtein`.


/// Compute byte-wise Levenshtein edit distance.
///
/// # Errors
///
/// Returns `Fix: ...` when input sizes exceed caps, when the DP cell product
/// overflows, or when the documented OOM guard is exceeded.
pub fn levenshtein(a: &[u8], b: &[u8]) -> Result<u32, SimilarityError> {
    validate_pair(a, b)?;
    validate_dp_product(a.len(), b.len())?;
    if a.is_empty() {
        return to_u32(b.len(), "levenshtein distance");
    }
    if b.is_empty() {
        return to_u32(a.len(), "levenshtein distance");
    }
    let mut previous: Vec<usize> = (0..=b.len()).collect();
    let mut current = vec![0usize; b.len() + 1];
    for (i, &left) in a.iter().enumerate() {
        current[0] = i + 1;
        for (j, &right) in b.iter().enumerate() {
            let substitution = previous[j] + usize::from(left != right);
            let insertion = current[j] + 1;
            let deletion = previous[j + 1] + 1;
            current[j + 1] = substitution.min(insertion).min(deletion);
        }
        std::mem::swap(&mut previous, &mut current);
    }
    to_u32(previous[b.len()], "levenshtein distance")
}

// Backend-specific lowering marker.

// WGSL lowering unavailable for `string_similarity.levenshtein`.
//
// Exact CPU parity requires caller-provided dynamic-programming rows whose
// size depends on `len(a) * len(b)`, but the current intrinsic ABI exposes
// only `Bytes, Bytes -> U32` and no scratch arena. Fix: keep this op CPU-only
// until the spec defines bounded DP scratch buffers.