rexact-core 0.2.0

//! Case-insensitive matching (FR-A10) as closure of symbol sets.
//!
//! A [`CaseFold`] is a canonicalisation `canon: code point -> code point`
//! (stored sparsely as the pairs where it changes a character). Two characters
//! match case-insensitively when their canonical forms are equal, so the set
//! matched by a class `S` is `{ c : canon(c) in canon(S) }`.
//!
//! Dialects differ only in the canonicalisation (RULE-10):
//! * ECMAScript without `u`: `toUpperCase` when it yields one character and
//!   does not map non-ASCII into ASCII (ECMA-262 Canonicalize);
//! * ECMAScript with `u`, Go, Rust, PCRE2: Unicode simple case folding;
//! * Python `re`: simple lowercase plus the interpreter's equivalence keys
//!   (e.g. `i` also matches dotless `ı`), or ASCII-only under `re.ASCII`.
//!
//! No supported dialect defines full case folding (`ß` vs `ss`) for matching,
//! so none is implemented.

use crate::charset::CharSet;
use rexact_unicode as uni;

type Extra = Vec<(u32, Vec<u32>)>;

/// Which canonicalisation to use.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum CaseModel {
    /// ECMAScript non-Unicode mode (`toUpperCase`).
    EsLegacy,
    /// Simple case folding (ECMAScript `u`, Go, Rust, PCRE2).
    SimpleFold,
    /// Python `re.IGNORECASE` on str patterns.
    Python,
    /// Python with `re.ASCII`: only `A-Z` / `a-z`.
    PythonAscii,
}

/// Sparse canonicalisation and the closure operations built on it.
pub struct CaseFold {
    /// (code point, canonical form) for code points whose form differs.
    map: Vec<(u32, u32)>,
    changed: CharSet,
    /// Python only: lowered key -> additional keys it also matches.
    extra: Vec<(u32, Vec<u32>)>,
    model: CaseModel,
}

impl CaseFold {
    /// Build the tables for a model.
    pub fn new(model: CaseModel) -> Self {
        let (map, extra): (Vec<(u32, u32)>, Extra) = match model {
            CaseModel::EsLegacy => (
                uni::upper_single_pairs()
                    .iter()
                    .copied()
                    // Canonicalize: never map a non-ASCII character to ASCII.
                    .filter(|&(c, u)| !(c >= 128 && u < 128))
                    .collect(),
                Vec::new(),
            ),
            CaseModel::SimpleFold => (uni::simple_fold_pairs().to_vec(), Vec::new()),
            CaseModel::Python => (
                uni::lower_simple_pairs().to_vec(),
                uni::py_lower_extra()
                    .iter()
                    .map(|(k, v)| (*k, v.to_vec()))
                    .collect(),
            ),
            CaseModel::PythonAscii => ((0x41..=0x5A).map(|c| (c, c + 32)).collect(), Vec::new()),
        };
        let changed = CharSet::from_ranges(map.iter().map(|&(c, _)| (c, c)));
        CaseFold {
            map,
            changed,
            extra,
            model,
        }
    }

    /// Canonical form of one code point.
    pub fn canon(&self, c: u32) -> u32 {
        self.map
            .binary_search_by_key(&c, |&(k, _)| k)
            .map(|i| self.map[i].1)
            .unwrap_or(c)
    }

    /// Set of canonical forms of the members of `s`.
    fn images(&self, s: &CharSet) -> CharSet {
        let mut out = s.difference(&self.changed);
        let mapped: Vec<(u32, u32)> = self
            .map
            .iter()
            .filter(|&&(c, _)| s.contains(c))
            .map(|&(_, v)| (v, v))
            .collect();
        out = out.union(&CharSet::from_ranges(mapped));
        if self.model == CaseModel::Python {
            let more: Vec<(u32, u32)> = self
                .extra
                .iter()
                .filter(|(k, _)| out.contains(*k))
                .flat_map(|(_, v)| v.iter().map(|&x| (x, x)))
                .collect();
            out = out.union(&CharSet::from_ranges(more));
        }
        out
    }

    /// All characters whose canonical form lies in `t`.
    fn preimage(&self, t: &CharSet) -> CharSet {
        let moved: Vec<(u32, u32)> = self
            .map
            .iter()
            .filter(|&&(_, v)| t.contains(v))
            .map(|&(c, _)| (c, c))
            .collect();
        t.difference(&self.changed)
            .union(&CharSet::from_ranges(moved))
    }

    /// Characters matching any member of `s` case-insensitively.
    pub fn close(&self, s: &CharSet) -> CharSet {
        self.preimage(&self.images(s))
    }

    /// Python class semantics: range/literal `members` go through the
    /// canonicalisation, while category sets (`\w`, `\d`, ...) are tested on
    /// the lowered input character as they are. A class with no cased member
    /// is not folded at all (the interpreter emits a plain `IN`).
    pub fn close_python_class(&self, members: &CharSet, categories: &CharSet) -> CharSet {
        if !self.has_case(members) {
            return members.union(categories);
        }
        self.preimage(&self.images(members).union(categories))
    }

    /// Does the set contain a cased character (one the model changes, or the
    /// image of one)?
    pub fn has_case(&self, s: &CharSet) -> bool {
        !s.intersect(&self.changed).is_empty()
            || self.map.iter().any(|&(_, v)| s.contains(v))
            || self.extra.iter().any(|(k, _)| s.contains(*k))
    }
}

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

    fn set(cs: &[u32]) -> CharSet {
        CharSet::from_ranges(cs.iter().map(|&c| (c, c)))
    }

    #[test]
    fn simple_fold_orbits_include_kelvin_and_long_s() {
        let f = CaseFold::new(CaseModel::SimpleFold);
        let k = f.close(&set(&['k' as u32]));
        assert!(k.contains('K' as u32) && k.contains(0x212A) && k.contains('k' as u32));
        let s = f.close(&set(&['S' as u32]));
        assert!(s.contains(0x17F) && s.contains('s' as u32));
        assert!(!f.close(&set(&[0xDF])).contains('S' as u32)); // sharp s: no simple folding
    }

    #[test]
    fn legacy_es_never_maps_non_ascii_to_ascii() {
        let f = CaseFold::new(CaseModel::EsLegacy);
        assert!(!f.close(&set(&['k' as u32])).contains(0x212A));
        assert!(!f.close(&set(&['s' as u32])).contains(0x17F));
        assert!(f.close(&set(&[0x3C3])).contains(0x3C2)); // sigma ~ final sigma via capital sigma
        assert!(f.close(&set(&[0xE9])).contains(0xC9));
    }

    #[test]
    fn python_has_dotless_i_equivalence_but_not_turkish_dotted() {
        let f = CaseFold::new(CaseModel::Python);
        let i = f.close(&set(&['i' as u32]));
        assert!(i.contains('I' as u32) && i.contains(0x131) && i.contains(0x130));
        let a = CaseFold::new(CaseModel::PythonAscii).close(&set(&['k' as u32]));
        assert!(a.contains('K' as u32) && !a.contains(0x212A));
    }

    #[test]
    fn python_class_without_cased_members_is_not_folded() {
        let f = CaseFold::new(CaseModel::Python);
        let digits = CharSet::range('0' as u32, '9' as u32);
        assert_eq!(f.close_python_class(&digits, &CharSet::empty()), digits);
        assert!(f
            .close_python_class(&set(&['a' as u32]), &CharSet::empty())
            .contains('A' as u32));
    }
}