//! `levenshtein` matcher: bounded edit distance.
//!
//! Why this exists: LLM output rarely matches a reference verbatim, but "close
//! enough" is often the real bar. The Levenshtein edit distance (insertions,
//! deletions, substitutions) between the stringified value and a reference is
//! a deterministic stand-in for fuzzy equality, no embedding model required.
//!
//! Argument shape: `{ value: "<reference>", max: <N> }`. The matcher passes
//! when the distance is at most `max`. The distance is computed inline with a
//! small two-row dynamic program so the crate gains no new dependency.

use serde_json::Value;

use super::{AssertionDiff, AssertionResult, MatcherKind};
use crate::{Error, Result};

/// Evaluate `levenshtein`.
///
/// The actual value is stringified (a JSON string uses its raw text; any other
/// JSON value uses its compact serialization) and compared against the
/// reference. A passing result carries the distance in its note; a failure
/// reports both the distance and the threshold.
pub fn evaluate(argument: &Value, actual: &Value) -> Result<AssertionResult> {
    let (reference, max) = parse_argument(argument)?;
    let candidate = stringify(actual);
    let distance = edit_distance(&candidate, reference);
    if distance <= max {
        Ok(AssertionResult::passed_with_note(
            MatcherKind::Levenshtein,
            format!("edit distance {distance} <= max {max}"),
        ))
    } else {
        Ok(AssertionResult::failed(
            MatcherKind::Levenshtein,
            AssertionDiff {
                path: String::new(),
                expected: Some(Value::String(reference.to_string())),
                actual: Some(Value::String(candidate)),
                note: Some(format!("edit distance {distance} exceeds max {max}")),
            },
        ))
    }
}

/// Extract the reference string and `max` threshold from the argument object.
fn parse_argument(argument: &Value) -> Result<(&str, usize)> {
    let map = argument.as_object().ok_or_else(|| {
        Error::InvalidMatcherInput("levenshtein argument must be a { value, max } object".into())
    })?;
    let reference = map
        .get("value")
        .and_then(Value::as_str)
        .ok_or_else(|| Error::InvalidMatcherInput("levenshtein needs a string `value`".into()))?;
    let max = map.get("max").and_then(Value::as_u64).ok_or_else(|| {
        Error::InvalidMatcherInput("levenshtein needs a non-negative integer `max`".into())
    })?;
    Ok((reference, max as usize))
}

/// Stringify the value at the target for comparison. Strings pass through
/// verbatim so the user compares text to text; other values fall back to their
/// compact JSON form.
fn stringify(value: &Value) -> String {
    match value {
        Value::String(s) => s.clone(),
        other => other.to_string(),
    }
}

/// Levenshtein edit distance via a two-row dynamic program over Unicode
/// scalar values. Kept inline to avoid a dependency; O(n*m) time, O(m) space.
fn edit_distance(a: &str, b: &str) -> usize {
    let a: Vec<char> = a.chars().collect();
    let b: Vec<char> = b.chars().collect();
    if a.is_empty() {
        return b.len();
    }
    if b.is_empty() {
        return a.len();
    }
    let mut prev: Vec<usize> = (0..=b.len()).collect();
    let mut curr: Vec<usize> = vec![0; b.len() + 1];
    for (i, ca) in a.iter().enumerate() {
        curr[0] = i + 1;
        for (j, cb) in b.iter().enumerate() {
            let cost = if ca == cb { 0 } else { 1 };
            curr[j + 1] = (prev[j + 1] + 1).min(curr[j] + 1).min(prev[j] + cost);
        }
        std::mem::swap(&mut prev, &mut curr);
    }
    prev[b.len()]
}

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

    #[test]
    fn edit_distance_of_identical_strings_is_zero() {
        assert_eq!(edit_distance("kitten", "kitten"), 0);
    }

    #[test]
    fn edit_distance_classic_kitten_sitting_is_three() {
        assert_eq!(edit_distance("kitten", "sitting"), 3);
    }

    #[test]
    fn edit_distance_handles_empty_strings() {
        assert_eq!(edit_distance("", "abc"), 3);
        assert_eq!(edit_distance("abc", ""), 3);
        assert_eq!(edit_distance("", ""), 0);
    }

    #[test]
    fn edit_distance_counts_unicode_scalars_not_bytes() {
        // Two distinct multi-byte chars: one substitution, not several.
        assert_eq!(edit_distance("\u{4e2d}", "\u{6587}"), 1);
    }

    #[test]
    fn levenshtein_passes_within_threshold() {
        let arg = json!({"value": "sitting", "max": 3});
        let r = evaluate(&arg, &json!("kitten")).unwrap();
        assert!(r.pass, "diffs: {:?}", r.diffs);
        assert_eq!(r.kind, MatcherKind::Levenshtein);
    }

    #[test]
    fn levenshtein_fails_beyond_threshold() {
        let arg = json!({"value": "sitting", "max": 2});
        let r = evaluate(&arg, &json!("kitten")).unwrap();
        assert!(!r.pass);
        assert!(r.diffs[0].note.as_deref().unwrap().contains("exceeds max"));
    }

    #[test]
    fn levenshtein_stringifies_non_string_values() {
        let arg = json!({"value": "42", "max": 0});
        let r = evaluate(&arg, &json!(42)).unwrap();
        assert!(r.pass, "diffs: {:?}", r.diffs);
    }

    #[test]
    fn levenshtein_rejects_missing_max() {
        let err = evaluate(&json!({"value": "x"}), &json!("x")).unwrap_err();
        assert!(matches!(err, Error::InvalidMatcherInput(_)));
    }

    #[test]
    fn levenshtein_rejects_non_object_argument() {
        let err = evaluate(&json!("oops"), &json!("x")).unwrap_err();
        assert!(matches!(err, Error::InvalidMatcherInput(_)));
    }
}
