fxfs_unicode/
lib.rs

1// Copyright 2024 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4use fprint::TypeFingerprint;
5use serde::{Deserialize, Serialize};
6use std::hash::{Hash, Hasher};
7
8mod lookup;
9mod nfd;
10use unicode_gen;
11
12/// Filters a valid sequence of unicode characters, casefolding.
13pub(crate) struct CaseFoldIterator<I: Iterator<Item = char>> {
14    /// The not-yet-normalized input sequence.
15    input: I,
16    buf: [char; 4],
17    buf_len: usize,
18    buf_pos: usize,
19}
20
21impl<I: Iterator<Item = char>> Iterator for CaseFoldIterator<I> {
22    type Item = char;
23
24    fn next(&mut self) -> Option<char> {
25        if self.buf_pos < self.buf_len {
26            let ch = self.buf[self.buf_pos];
27            self.buf_pos += 1;
28            return Some(ch);
29        }
30        self.buf_len = 0;
31        self.buf_pos = 0;
32
33        self.input.next().map(|ch| {
34            if let Some(mapping) = crate::lookup::casefold(ch) {
35                let mut chars = mapping.chars();
36                let first = chars.next().unwrap();
37                for c in chars {
38                    self.buf[self.buf_len] = c;
39                    self.buf_len += 1;
40                }
41                first
42            } else {
43                ch
44            }
45        })
46    }
47}
48
49pub(crate) fn casefold<I: Iterator<Item = char>>(input: I) -> CaseFoldIterator<I> {
50    CaseFoldIterator { input, buf: ['\0'; 4], buf_len: 0, buf_pos: 0 }
51}
52
53/// Helper function to convert a `char` to an iterator over its UTF-8 bytes
54/// without any heap allocations.
55pub fn utf8_bytes(c: char) -> impl Iterator<Item = u8> {
56    let mut buf = [0; 4];
57    let len = c.encode_utf8(&mut buf).len();
58    buf.into_iter().take(len)
59}
60
61/// A comparison function that:
62///  * Applies casefolding.
63///  * Removes default ignorable characters.
64///  * Applies nfd normalization.
65/// That function will early-out at the first non-matching character.
66pub fn casefold_cmp(a: &str, b: &str) -> std::cmp::Ordering {
67    let a_it = nfd::nfd(casefold(a.chars()).filter(|x| !lookup::default_ignorable(*x)));
68    let b_it = nfd::nfd(casefold(b.chars()).filter(|x| !lookup::default_ignorable(*x)));
69    a_it.cmp(b_it)
70}
71
72// A simple wrapper around String that provides casefolding comparison.
73#[derive(arbitrary::Arbitrary, Clone, Eq, Serialize, Deserialize, TypeFingerprint)]
74pub struct CasefoldString(String);
75impl CasefoldString {
76    pub fn new(s: String) -> Self {
77        Self(s)
78    }
79}
80impl std::fmt::Debug for CasefoldString {
81    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
82        write!(f, "CasefoldString(\"{}\")", self.0)
83    }
84}
85impl std::fmt::Display for CasefoldString {
86    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
87        write!(f, "{}", self.0)
88    }
89}
90/// A borrowed slice of a casefolded string.
91///
92/// It is designed to be the borrowed counterpart to `CasefoldString`, mirroring
93/// the relationship between `str` and `String`.
94///
95/// We wrap `str` instead of a struct like `CasefoldStr<'a>(&'a str)`
96/// so that `CasefoldString` can implement `Deref<Target = CasefoldStr>`. This allows
97/// `CasefoldString` to coerce to `&CasefoldStr` automatically, and enables zero-allocation
98/// map lookups via `Borrow<CasefoldStr>`.
99#[repr(transparent)]
100pub struct CasefoldStr(str);
101
102impl CasefoldStr {
103    pub fn new(s: &str) -> &Self {
104        // SAFETY: `CasefoldStr` is `#[repr(transparent)]` around `str`, so it has the same layout
105        // and alignment.
106        unsafe { &*(s as *const str as *const CasefoldStr) }
107    }
108
109    pub fn as_str(&self) -> &str {
110        &self.0
111    }
112
113    pub fn casefold_normalized_chars(&self) -> impl Iterator<Item = char> + '_ {
114        nfd::nfd(casefold(self.0.chars()).filter(|x| !lookup::default_ignorable(*x)))
115    }
116}
117
118impl std::fmt::Debug for CasefoldStr {
119    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
120        write!(f, "CasefoldStr(\"{}\")", &self.0)
121    }
122}
123
124impl std::fmt::Display for CasefoldStr {
125    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
126        write!(f, "{}", &self.0)
127    }
128}
129
130impl std::cmp::PartialEq for CasefoldStr {
131    fn eq(&self, rhs: &Self) -> bool {
132        casefold_cmp(self.as_str(), rhs.as_str()).is_eq()
133    }
134}
135impl std::cmp::Eq for CasefoldStr {}
136
137impl std::cmp::Ord for CasefoldStr {
138    fn cmp(&self, rhs: &Self) -> std::cmp::Ordering {
139        casefold_cmp(self.as_str(), rhs.as_str())
140    }
141}
142impl std::cmp::PartialOrd for CasefoldStr {
143    fn partial_cmp(&self, rhs: &Self) -> Option<std::cmp::Ordering> {
144        Some(self.cmp(rhs))
145    }
146}
147
148impl ToOwned for CasefoldStr {
149    type Owned = CasefoldString;
150    fn to_owned(&self) -> Self::Owned {
151        CasefoldString::new(self.as_str().to_owned())
152    }
153}
154
155impl Hash for CasefoldStr {
156    fn hash<H: Hasher>(&self, state: &mut H) {
157        for ch in self.casefold_normalized_chars() {
158            ch.hash(state);
159        }
160    }
161}
162
163impl CasefoldString {
164    pub fn as_str(&self) -> &str {
165        &self.0
166    }
167}
168
169impl std::ops::Deref for CasefoldString {
170    type Target = CasefoldStr;
171    fn deref(&self) -> &CasefoldStr {
172        CasefoldStr::new(&self.0)
173    }
174}
175
176impl std::borrow::Borrow<CasefoldStr> for CasefoldString {
177    fn borrow(&self) -> &CasefoldStr {
178        &**self
179    }
180}
181
182impl std::cmp::PartialEq for CasefoldString {
183    fn eq(&self, rhs: &Self) -> bool {
184        **self == **rhs
185    }
186}
187
188impl std::cmp::Ord for CasefoldString {
189    fn cmp(&self, rhs: &Self) -> std::cmp::Ordering {
190        (**self).cmp(&**rhs)
191    }
192}
193
194impl std::cmp::PartialOrd for CasefoldString {
195    fn partial_cmp(&self, rhs: &Self) -> Option<std::cmp::Ordering> {
196        Some(self.cmp(rhs))
197    }
198}
199
200// Nb: This trait is provided for completeness but is NOT intended to be performant.
201impl Hash for CasefoldString {
202    fn hash<H>(&self, state: &mut H)
203    where
204        H: Hasher,
205    {
206        (**self).hash(state);
207    }
208}
209
210impl From<&str> for CasefoldString {
211    fn from(item: &str) -> Self {
212        CasefoldString(item.into())
213    }
214}
215
216impl<'a> From<&'a str> for &'a CasefoldStr {
217    fn from(item: &'a str) -> Self {
218        CasefoldStr::new(item)
219    }
220}
221
222impl<'a> std::convert::TryFrom<&'a [u8]> for &'a CasefoldStr {
223    type Error = std::str::Utf8Error;
224
225    fn try_from(bytes: &'a [u8]) -> Result<Self, Self::Error> {
226        std::str::from_utf8(bytes).map(CasefoldStr::new)
227    }
228}
229
230#[cfg(test)]
231mod test {
232    use super::*;
233    use std::hash::{Hash, Hasher};
234
235    fn get_hash<T: Hash + ?Sized>(t: &T) -> u64 {
236        let mut s = std::collections::hash_map::DefaultHasher::new();
237        t.hash(&mut s);
238        s.finish()
239    }
240
241    #[test]
242    fn test_casefold() {
243        assert_eq!(casefold("Hello There".chars()).collect::<String>(), "hello there");
244        assert_eq!(casefold("HELLO There".chars()).collect::<String>(), "hello there");
245    }
246
247    #[test]
248    fn test_casefold_cmp() {
249        assert_eq!(casefold_cmp("Hello", "hello"), std::cmp::Ordering::Equal);
250        assert_eq!(casefold_cmp("Hello There", "hello"), std::cmp::Ordering::Greater);
251        assert_eq!(casefold_cmp("hello there", "hello"), std::cmp::Ordering::Greater);
252        assert_eq!(casefold_cmp("hello\u{00AD}", "hello"), std::cmp::Ordering::Equal);
253        assert_eq!(casefold_cmp("\u{03AA}", "\u{0399}\u{0308}"), std::cmp::Ordering::Equal);
254
255        // Gracefully handle the degenerate case where we start with modifiers
256        assert_eq!(
257            casefold_cmp("\u{308}\u{05ae}Hello", "\u{05ae}\u{308}hello"),
258            std::cmp::Ordering::Equal
259        );
260    }
261
262    #[test]
263    fn test_casefoldstring() {
264        let a = CasefoldString::new("Hello There".to_owned());
265        let b = CasefoldString::new("hello there".to_owned());
266        let c = CasefoldString::new("hello".to_owned());
267        let d = CasefoldString::new("\u{03AA}".to_owned());
268        let e = CasefoldString::new("\u{0399}\u{0308}".to_owned());
269        // Check some comparisons.
270        assert_eq!(a, a);
271        assert_eq!(a, b);
272        assert_eq!(d, e);
273        assert!(a > c);
274        assert!(b > c);
275        assert_eq!(a.0, format!("{}", a));
276        // Debug::fmt should show type to avoid confusion.
277        assert_eq!("CasefoldString(\"Hello There\")", format!("{:?}", a));
278        // Displays the same as String.
279        assert_eq!(format!("{}", "Hello There".to_owned()), format!("{}", a));
280    }
281
282    #[test]
283    fn test_casefold_hash_equality() {
284        // hello and hello with soft hyphen (ignorable) should be equal and have identical hashes
285        let a = CasefoldString::new("hello\u{00AD}".to_owned());
286        let b = CasefoldString::new("hello".to_owned());
287        assert_eq!(a, b);
288        assert_eq!(get_hash(&a), get_hash(&b));
289    }
290
291    #[test]
292    fn test_casefoldstr() {
293        use std::borrow::Borrow;
294
295        let a = CasefoldString::new("Hello There".to_owned());
296        let b = CasefoldStr::new("hello there");
297        let c = CasefoldStr::new("hello");
298
299        // Compare CasefoldString with CasefoldStr (via Borrow)
300        let borrowed_a: &CasefoldStr = a.borrow();
301        assert_eq!(borrowed_a, b);
302        assert!(borrowed_a > c);
303
304        // Compare CasefoldStr with CasefoldStr
305        assert_eq!(b, b);
306        assert_eq!(CasefoldStr::new("Hello"), CasefoldStr::new("hello"));
307        assert!(b > c);
308
309        // Verify as_str() returns the original case-sensitive string
310        assert_eq!(b.as_str(), "hello there");
311        assert_ne!(b.as_str(), "Hello There");
312
313        // Test ToOwned
314        let owned_b: CasefoldString = b.to_owned();
315        assert_eq!(owned_b, a);
316
317        // Test Hash consistency
318        assert_eq!(get_hash(&a), get_hash(borrowed_a));
319        assert_eq!(get_hash(&owned_b), get_hash(b));
320    }
321
322    #[test]
323    fn test_casefold_str_normalized() {
324        // soft hyphen (ignorable), ohm sign (decomposes to omega)
325        let raw = "Hello\u{00AD} World\u{2126}";
326        let cf_str = CasefoldStr::new(raw);
327
328        let normalized_chars: String = cf_str.casefold_normalized_chars().collect();
329
330        // expected:
331        // "Hello" -> "hello"
332        // "\u{00AD}" -> stripped
333        // " " -> " "
334        // "World" -> "world"
335        // "\u{2126}" -> \u{03c9} (omega lowercase in NFD)
336        let expected_str = "hello world\u{03c9}";
337        assert_eq!(normalized_chars, expected_str);
338    }
339}
fxfs_unicode/lib.rs

fxfs_unicode/
lib.rs
