rexact_core/
casefold.rs

1//! Case-insensitive matching (FR-A10) as closure of symbol sets.
2//!
3//! A [`CaseFold`] is a canonicalisation `canon: code point -> code point`
4//! (stored sparsely as the pairs where it changes a character). Two characters
5//! match case-insensitively when their canonical forms are equal, so the set
6//! matched by a class `S` is `{ c : canon(c) in canon(S) }`.
7//!
8//! Dialects differ only in the canonicalisation (RULE-10):
9//! * ECMAScript without `u`: `toUpperCase` when it yields one character and
10//!   does not map non-ASCII into ASCII (ECMA-262 Canonicalize);
11//! * ECMAScript with `u`, Go, Rust, PCRE2: Unicode simple case folding;
12//! * Python `re`: simple lowercase plus the interpreter's equivalence keys
13//!   (e.g. `i` also matches dotless `ı`), or ASCII-only under `re.ASCII`.
14//!
15//! No supported dialect defines full case folding (`ß` vs `ss`) for matching,
16//! so none is implemented.
17
18use crate::charset::CharSet;
19use rexact_unicode as uni;
20
21type Extra = Vec<(u32, Vec<u32>)>;
22
23/// Which canonicalisation to use.
24#[derive(Debug, Clone, Copy, PartialEq, Eq)]
25pub enum CaseModel {
26    /// ECMAScript non-Unicode mode (`toUpperCase`).
27    EsLegacy,
28    /// Simple case folding (ECMAScript `u`, Go, Rust, PCRE2).
29    SimpleFold,
30    /// Python `re.IGNORECASE` on str patterns.
31    Python,
32    /// Python with `re.ASCII`: only `A-Z` / `a-z`.
33    PythonAscii,
34}
35
36/// Sparse canonicalisation and the closure operations built on it.
37pub struct CaseFold {
38    /// (code point, canonical form) for code points whose form differs.
39    map: Vec<(u32, u32)>,
40    changed: CharSet,
41    /// Python only: lowered key -> additional keys it also matches.
42    extra: Vec<(u32, Vec<u32>)>,
43    model: CaseModel,
44}
45
46impl CaseFold {
47    /// Build the tables for a model.
48    pub fn new(model: CaseModel) -> Self {
49        let (map, extra): (Vec<(u32, u32)>, Extra) = match model {
50            CaseModel::EsLegacy => (
51                uni::upper_single_pairs()
52                    .iter()
53                    .copied()
54                    // Canonicalize: never map a non-ASCII character to ASCII.
55                    .filter(|&(c, u)| !(c >= 128 && u < 128))
56                    .collect(),
57                Vec::new(),
58            ),
59            CaseModel::SimpleFold => (uni::simple_fold_pairs().to_vec(), Vec::new()),
60            CaseModel::Python => (
61                uni::lower_simple_pairs().to_vec(),
62                uni::py_lower_extra()
63                    .iter()
64                    .map(|(k, v)| (*k, v.to_vec()))
65                    .collect(),
66            ),
67            CaseModel::PythonAscii => ((0x41..=0x5A).map(|c| (c, c + 32)).collect(), Vec::new()),
68        };
69        let changed = CharSet::from_ranges(map.iter().map(|&(c, _)| (c, c)));
70        CaseFold {
71            map,
72            changed,
73            extra,
74            model,
75        }
76    }
77
78    /// Canonical form of one code point.
79    pub fn canon(&self, c: u32) -> u32 {
80        self.map
81            .binary_search_by_key(&c, |&(k, _)| k)
82            .map(|i| self.map[i].1)
83            .unwrap_or(c)
84    }
85
86    /// Set of canonical forms of the members of `s`.
87    fn images(&self, s: &CharSet) -> CharSet {
88        let mut out = s.difference(&self.changed);
89        let mapped: Vec<(u32, u32)> = self
90            .map
91            .iter()
92            .filter(|&&(c, _)| s.contains(c))
93            .map(|&(_, v)| (v, v))
94            .collect();
95        out = out.union(&CharSet::from_ranges(mapped));
96        if self.model == CaseModel::Python {
97            let more: Vec<(u32, u32)> = self
98                .extra
99                .iter()
100                .filter(|(k, _)| out.contains(*k))
101                .flat_map(|(_, v)| v.iter().map(|&x| (x, x)))
102                .collect();
103            out = out.union(&CharSet::from_ranges(more));
104        }
105        out
106    }
107
108    /// All characters whose canonical form lies in `t`.
109    fn preimage(&self, t: &CharSet) -> CharSet {
110        let moved: Vec<(u32, u32)> = self
111            .map
112            .iter()
113            .filter(|&&(_, v)| t.contains(v))
114            .map(|&(c, _)| (c, c))
115            .collect();
116        t.difference(&self.changed)
117            .union(&CharSet::from_ranges(moved))
118    }
119
120    /// Characters matching any member of `s` case-insensitively.
121    pub fn close(&self, s: &CharSet) -> CharSet {
122        self.preimage(&self.images(s))
123    }
124
125    /// Python class semantics: range/literal `members` go through the
126    /// canonicalisation, while category sets (`\w`, `\d`, ...) are tested on
127    /// the lowered input character as they are. A class with no cased member
128    /// is not folded at all (the interpreter emits a plain `IN`).
129    pub fn close_python_class(&self, members: &CharSet, categories: &CharSet) -> CharSet {
130        if !self.has_case(members) {
131            return members.union(categories);
132        }
133        self.preimage(&self.images(members).union(categories))
134    }
135
136    /// Does the set contain a cased character (one the model changes, or the
137    /// image of one)?
138    pub fn has_case(&self, s: &CharSet) -> bool {
139        !s.intersect(&self.changed).is_empty()
140            || self.map.iter().any(|&(_, v)| s.contains(v))
141            || self.extra.iter().any(|(k, _)| s.contains(*k))
142    }
143}
144
145#[cfg(test)]
146mod tests {
147    use super::*;
148
149    fn set(cs: &[u32]) -> CharSet {
150        CharSet::from_ranges(cs.iter().map(|&c| (c, c)))
151    }
152
153    #[test]
154    fn simple_fold_orbits_include_kelvin_and_long_s() {
155        let f = CaseFold::new(CaseModel::SimpleFold);
156        let k = f.close(&set(&['k' as u32]));
157        assert!(k.contains('K' as u32) && k.contains(0x212A) && k.contains('k' as u32));
158        let s = f.close(&set(&['S' as u32]));
159        assert!(s.contains(0x17F) && s.contains('s' as u32));
160        assert!(!f.close(&set(&[0xDF])).contains('S' as u32)); // sharp s: no simple folding
161    }
162
163    #[test]
164    fn legacy_es_never_maps_non_ascii_to_ascii() {
165        let f = CaseFold::new(CaseModel::EsLegacy);
166        assert!(!f.close(&set(&['k' as u32])).contains(0x212A));
167        assert!(!f.close(&set(&['s' as u32])).contains(0x17F));
168        assert!(f.close(&set(&[0x3C3])).contains(0x3C2)); // sigma ~ final sigma via capital sigma
169        assert!(f.close(&set(&[0xE9])).contains(0xC9));
170    }
171
172    #[test]
173    fn python_has_dotless_i_equivalence_but_not_turkish_dotted() {
174        let f = CaseFold::new(CaseModel::Python);
175        let i = f.close(&set(&['i' as u32]));
176        assert!(i.contains('I' as u32) && i.contains(0x131) && i.contains(0x130));
177        let a = CaseFold::new(CaseModel::PythonAscii).close(&set(&['k' as u32]));
178        assert!(a.contains('K' as u32) && !a.contains(0x212A));
179    }
180
181    #[test]
182    fn python_class_without_cased_members_is_not_folded() {
183        let f = CaseFold::new(CaseModel::Python);
184        let digits = CharSet::range('0' as u32, '9' as u32);
185        assert_eq!(f.close_python_class(&digits, &CharSet::empty()), digits);
186        assert!(f
187            .close_python_class(&set(&['a' as u32]), &CharSet::empty())
188            .contains('A' as u32));
189    }
190}
rexact_core/casefold.rs

rexact_core/
casefold.rs
