vitaminc-ore 0.8.1

//! Accent and case folding for text order terms.
//!
//! An order term only has to tie where values should sort together, so it
//! folds further than an equality term may: `É`, `é`, `E` and `e` all
//! become `e`. The steps are Unicode's canonical caseless matching
//! (NFD, full default case folding, NFD again; *Unicode Standard* §3.13,
//! D145) with every accent then dropped, and the result put back into
//! NFC. An accent is a mark that attaches to its base letter, one with a
//! non-zero canonical combining class: the acute in `é`, the umlaut in
//! `ö`, a Devanagari virama. A mark of class zero is a letter of its own
//! in its script, such as a Devanagari or Thai vowel sign (`कि` and `की`
//! are different words), and is kept. Folding before dropping marks means a precomposed letter's
//! case mapping is applied before its accent is lost, and decomposing
//! again after folding catches a mark a case mapping introduces.
//!
//! The case-folding table is generated from Unicode 16's
//! `CaseFolding.txt` and pinned, like the assignment table, so a frozen
//! domain's accepted input and output never widen with a dependency
//! upgrade.

use core::str::Chars;

use unicode_general_category::{get_general_category, GeneralCategory};
use unicode_normalization::char::canonical_combining_class;
use unicode_normalization::UnicodeNormalization;
use vitaminc_normalize::NormalizeError;
use vitaminc_protected::{Controlled, Protected};

use crate::casefold_unicode16::FOLD;

/// The folded form of `text`, in one protected buffer sized exactly up
/// front (the pipeline runs twice, once to measure), so it never
/// reallocates and frees an unwiped partial copy.
///
/// The normalization iterators keep pending code points in small buffers
/// of their own, with room for four code points inside the iterator.
/// Decomposition holds the combining marks that follow a character in the
/// same buffer as the decomposed form of the next character, so the
/// buffer moves to the heap as soon as those together pass four code
/// points: four marks followed by any character is enough. Once a buffer
/// is on the heap it stays there for the rest of the string, so every
/// later character passes through it, and it is freed without being
/// wiped. That is out of this crate's control (see #488). NFC in
/// `vitaminc_normalize` has the same limit.
pub(crate) fn folded(text: &str) -> Result<Protected<Vec<u8>>, NormalizeError> {
    if text
        .chars()
        .any(|c| get_general_category(c) == GeneralCategory::Unassigned)
    {
        return Err(NormalizeError::UnassignedCodePoint);
    }
    let len = pipeline(text).map(char::len_utf8).sum();
    let mut result = Protected::new(Vec::with_capacity(len));
    for c in pipeline(text) {
        let mut encoded = Protected::new([0u8; 4]);
        result
            .risky_inner_mut()
            .extend_from_slice(c.encode_utf8(encoded.risky_inner_mut()).as_bytes());
    }
    Ok(result)
}

/// NFD, case fold, NFD, drop accents, NFC.
fn pipeline(text: &str) -> impl Iterator<Item = char> + '_ {
    text.nfd()
        .flat_map(fold)
        .nfd()
        .filter(|&c| !is_mark(c))
        .nfc()
}

/// The full default case folding of one code point: the table's mapping,
/// or the code point itself.
///
/// Built from the standard library's finite iterators rather than a
/// hand-written `Iterator`, so there is no `next` that could fail to end.
fn fold(c: char) -> core::iter::Chain<core::option::IntoIter<char>, Chars<'static>> {
    match FOLD.binary_search_by_key(&(c as u32), |&(code, _)| code) {
        Ok(index) => None.into_iter().chain(FOLD[index].1.chars()),
        Err(_) => Some(c).into_iter().chain("".chars()),
    }
}

/// Whether `c` is an accent: a mark with a non-zero canonical combining
/// class. A class is fixed once a code point is assigned, so the Unicode
/// 16 pin still holds.
fn is_mark(c: char) -> bool {
    canonical_combining_class(c) != 0
        && matches!(
            get_general_category(c),
            GeneralCategory::NonspacingMark
                | GeneralCategory::SpacingMark
                | GeneralCategory::EnclosingMark
        )
}

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

    fn fold_str(s: &str) -> String {
        String::from_utf8(folded(s).expect("assigned").risky_ref().clone()).expect("utf-8")
    }

    /// One code point folds to its mapping, or to itself, and then the
    /// iterator ends.
    #[test]
    fn one_code_point_folds_and_then_ends() {
        let take = |c: char| fold(c).take(4).collect::<String>();
        assert_eq!(take('a'), "a");
        assert_eq!(take('A'), "a");
        assert_eq!(take('ß'), "ss");
        assert_eq!(take('ffi'), "ffi");
    }

    #[test]
    fn the_table_is_sorted_by_code_point_with_no_repeats() {
        // The lookup is a binary search, so a regenerated table that was
        // not in code point order would silently miss mappings.
        assert!(FOLD.windows(2).all(|pair| pair[0].0 < pair[1].0));
        assert!(!FOLD.is_empty());
    }

    #[test]
    fn accents_and_case_fold_and_the_result_is_nfc() {
        for (input, expected) in [
            ("École", "ecole"),
            ("Straße", "strasse"),
            ("Σςσ", "σσσ"),
            ("İ", "i"),
            ("ffi", "ffi"),
            ("\u{10400}", "\u{10428}"),
            ("e\u{301}", "e"),
            // A spacing mark of class zero is kept.
            ("a\u{0903}", "a\u{0903}"),
            ("ÅNGSTRÖM", "angstrom"),
            ("", ""),
        ] {
            assert_eq!(fold_str(input), expected, "{input:?}");
        }
    }

    /// A vowel sign is a letter of its script, so words that differ only
    /// in one stay apart; an accent of the same script still folds.
    #[test]
    fn vowel_signs_are_kept_and_accents_of_every_script_dropped() {
        let ki = ["कि", "की", "के", "को"].map(fold_str);
        for (i, a) in ki.iter().enumerate() {
            for b in &ki[i + 1..] {
                assert_ne!(a, b, "Devanagari vowel signs are kept");
            }
        }
        assert_eq!(fold_str("कि"), "कि");
        assert_ne!(fold_str("กิ"), fold_str("กี"), "Thai vowel signs are kept");
        assert_ne!(
            fold_str("কি"),
            fold_str("কী"),
            "Bengali vowel signs are kept"
        );
        // Class-nonzero marks still drop: the Devanagari nukta (7) and
        // virama (9), Greek tonos, Cyrillic breve.
        assert_eq!(fold_str("क\u{93c}"), "क");
        assert_eq!(fold_str("क\u{94d}"), "क");
        assert_eq!(fold_str("Ά"), "α");
        assert_eq!(fold_str("й"), "и");
    }

    #[test]
    fn folding_is_idempotent_and_canonically_equivalent_inputs_agree() {
        for input in ["École", "Straße", "ᾈ", "Dž", "Ⅸ", "fi", "ẞ"] {
            let once = fold_str(input);
            assert_eq!(fold_str(&once), once, "{input:?}");
            let decomposed: String = input.nfd().collect();
            assert_eq!(fold_str(&decomposed), once, "{input:?}");
        }
    }

    #[test]
    fn an_unassigned_code_point_is_refused() {
        assert_eq!(
            folded("a\u{378}").expect_err("refused"),
            NormalizeError::UnassignedCodePoint
        );
    }
}