icu_collections/codepointinvliststringlist/
mod.rs

1// This file is part of ICU4X. For terms of use, please see the file
2// called LICENSE at the top level of the ICU4X source tree
3// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ).
4
5//! This module provides functionality for querying of sets of Unicode code points and strings.
6//!
7//! It depends on [`CodePointInversionList`] to efficiently represent Unicode code points, while
8//! it also maintains a list of strings in the set.
9//!
10//! It is an implementation of the existing [ICU4C UnicodeSet API](https://unicode-org.github.io/icu-docs/apidoc/released/icu4c/classicu_1_1UnicodeSet.html).
11
12#[cfg(feature = "alloc")]
13use crate::codepointinvlist::CodePointInversionListBuilder;
14use crate::codepointinvlist::{CodePointInversionList, CodePointInversionListULE};
15#[cfg(feature = "alloc")]
16use alloc::string::{String, ToString};
17#[cfg(feature = "alloc")]
18use alloc::vec::Vec;
19use displaydoc::Display;
20use yoke::Yokeable;
21use zerofrom::ZeroFrom;
22use zerovec::{VarZeroSlice, VarZeroVec};
23
24/// A data structure providing a concrete implementation of a set of code points and strings,
25/// using an inversion list for the code points.
26///
27/// This is what ICU4C calls a `UnicodeSet`.
28#[zerovec::make_varule(CodePointInversionListAndStringListULE)]
29#[zerovec::skip_derive(Ord)]
30#[zerovec::derive(Debug)]
31#[derive(Debug, Eq, PartialEq, Clone, Yokeable, ZeroFrom)]
32#[cfg_attr(not(feature = "alloc"), zerovec::skip_derive(ZeroMapKV, ToOwned))]
33// Valid to auto-derive Deserialize because the invariants are weakly held
34#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
35#[cfg_attr(feature = "serde", zerovec::derive(Serialize, Deserialize, Debug))]
36pub struct CodePointInversionListAndStringList<'data> {
37    #[cfg_attr(feature = "serde", serde(borrow))]
38    #[zerovec::varule(CodePointInversionListULE)]
39    cp_inv_list: CodePointInversionList<'data>,
40    // Invariants (weakly held):
41    //   - no input string is length 1 (a length 1 string should be a single code point)
42    //   - the string list is sorted
43    //   - the elements in the string list are unique
44    #[cfg_attr(feature = "serde", serde(borrow))]
45    str_list: VarZeroVec<'data, str>,
46}
47
48#[cfg(feature = "databake")]
49impl databake::Bake for CodePointInversionListAndStringList<'_> {
50    fn bake(&self, env: &databake::CrateEnv) -> databake::TokenStream {
51        env.insert("icu_collections");
52        let cp_inv_list = self.cp_inv_list.bake(env);
53        let str_list = self.str_list.bake(env);
54        // Safe because our parts are safe.
55        databake::quote! {
56            icu_collections::codepointinvliststringlist::CodePointInversionListAndStringList::from_parts_unchecked(#cp_inv_list, #str_list)
57        }
58    }
59}
60
61#[cfg(feature = "databake")]
62impl databake::BakeSize for CodePointInversionListAndStringList<'_> {
63    fn borrows_size(&self) -> usize {
64        self.cp_inv_list.borrows_size() + self.str_list.borrows_size()
65    }
66}
67
68impl<'data> CodePointInversionListAndStringList<'data> {
69    /// Returns a new [`CodePointInversionListAndStringList`] from both a [`CodePointInversionList`] for the
70    /// code points and a [`VarZeroVec`]`<`[`str`]`>` of strings.
71    pub fn try_from(
72        cp_inv_list: CodePointInversionList<'data>,
73        str_list: VarZeroVec<'data, str>,
74    ) -> Result<Self, InvalidStringList> {
75        // Verify invariants:
76        // Do so by using the equivalent of str_list.iter().windows(2) to get
77        // overlapping windows of size 2. The above putative code is not possible
78        // because `.windows()` exists on a slice, but VarZeroVec cannot return a slice
79        // because the non-fixed size elements necessitate at least some type
80        // of allocation.
81        {
82            let mut it = str_list.iter();
83            if let Some(mut x) = it.next() {
84                if x.len() == 1 {
85                    return Err(InvalidStringList::InvalidStringLength(
86                        #[cfg(feature = "alloc")]
87                        x.to_string(),
88                    ));
89                }
90                for y in it {
91                    if x.len() == 1 {
92                        return Err(InvalidStringList::InvalidStringLength(
93                            #[cfg(feature = "alloc")]
94                            x.to_string(),
95                        ));
96                    } else if x == y {
97                        return Err(InvalidStringList::StringListNotUnique(
98                            #[cfg(feature = "alloc")]
99                            x.to_string(),
100                        ));
101                    } else if x > y {
102                        return Err(InvalidStringList::StringListNotSorted(
103                            #[cfg(feature = "alloc")]
104                            x.to_string(),
105                            #[cfg(feature = "alloc")]
106                            y.to_string(),
107                        ));
108                    }
109
110                    // Next window begins. Update `x` here, `y` will be updated in next loop iteration.
111                    x = y;
112                }
113            }
114        }
115
116        Ok(CodePointInversionListAndStringList {
117            cp_inv_list,
118            str_list,
119        })
120    }
121
122    #[doc(hidden)] // databake internal
123    pub const fn from_parts_unchecked(
124        cp_inv_list: CodePointInversionList<'data>,
125        str_list: VarZeroVec<'data, str>,
126    ) -> Self {
127        CodePointInversionListAndStringList {
128            cp_inv_list,
129            str_list,
130        }
131    }
132
133    /// Returns the number of elements in this set (its cardinality).
134    /// Note than the elements of a set may include both individual
135    /// codepoints and strings.
136    pub fn size(&self) -> usize {
137        self.cp_inv_list.size() + self.str_list.len()
138    }
139
140    /// Return true if this set contains multi-code point strings or the empty string.
141    pub fn has_strings(&self) -> bool {
142        !self.str_list.is_empty()
143    }
144
145    ///
146    /// # Examples
147    /// ```
148    /// use icu::collections::codepointinvlist::CodePointInversionList;
149    /// use icu::collections::codepointinvliststringlist::CodePointInversionListAndStringList;
150    /// use zerovec::VarZeroVec;
151    ///
152    /// let cp_slice = &[0, 0x1_0000, 0x10_FFFF, 0x11_0000];
153    /// let cp_list =
154    ///    CodePointInversionList::try_from_u32_inversion_list_slice(cp_slice).unwrap();
155    /// let str_slice = &["", "bmp_max", "unicode_max", "zero"];
156    /// let str_list = VarZeroVec::<str>::from(str_slice);
157    ///
158    /// let cpilsl = CodePointInversionListAndStringList::try_from(cp_list, str_list).unwrap();
159    ///
160    /// assert!(cpilsl.contains_str("bmp_max"));
161    /// assert!(cpilsl.contains_str(""));
162    /// assert!(cpilsl.contains_str("A"));
163    /// assert!(cpilsl.contains_str("ቔ"));  // U+1254 ETHIOPIC SYLLABLE QHEE
164    /// assert!(!cpilsl.contains_str("bazinga!"));
165    /// ```
166    pub fn contains_str(&self, s: &str) -> bool {
167        let mut chars = s.chars();
168        if let Some(first_char) = chars.next() {
169            if chars.next().is_none() {
170                return self.contains(first_char);
171            }
172        }
173        self.str_list.binary_search(s).is_ok()
174    }
175
176    /// See [`Self::contains_str`]
177    pub fn contains_utf8(&self, s: &[u8]) -> bool {
178        if let Ok(well_formed) = core::str::from_utf8(s) {
179            self.contains_str(well_formed)
180        } else {
181            false
182        }
183    }
184
185    ///
186    /// # Examples
187    /// ```
188    /// use icu::collections::codepointinvlist::CodePointInversionList;
189    /// use icu::collections::codepointinvliststringlist::CodePointInversionListAndStringList;
190    /// use zerovec::VarZeroVec;
191    ///
192    /// let cp_slice = &[0, 0x80, 0xFFFF, 0x1_0000, 0x10_FFFF, 0x11_0000];
193    /// let cp_list =
194    ///     CodePointInversionList::try_from_u32_inversion_list_slice(cp_slice).unwrap();
195    /// let str_slice = &["", "ascii_max", "bmp_max", "unicode_max", "zero"];
196    /// let str_list = VarZeroVec::<str>::from(str_slice);
197    ///
198    /// let cpilsl = CodePointInversionListAndStringList::try_from(cp_list, str_list).unwrap();
199    ///
200    /// assert!(cpilsl.contains32(0));
201    /// assert!(cpilsl.contains32(0x0042));
202    /// assert!(!cpilsl.contains32(0x0080));
203    /// ```
204    pub fn contains32(&self, cp: u32) -> bool {
205        self.cp_inv_list.contains32(cp)
206    }
207
208    ///
209    /// # Examples
210    /// ```
211    /// use icu::collections::codepointinvlist::CodePointInversionList;
212    /// use icu::collections::codepointinvliststringlist::CodePointInversionListAndStringList;
213    /// use zerovec::VarZeroVec;
214    ///
215    /// let cp_slice = &[0, 0x1_0000, 0x10_FFFF, 0x11_0000];
216    /// let cp_list =
217    ///    CodePointInversionList::try_from_u32_inversion_list_slice(cp_slice).unwrap();
218    /// let str_slice = &["", "bmp_max", "unicode_max", "zero"];
219    /// let str_list = VarZeroVec::<str>::from(str_slice);
220    ///
221    /// let cpilsl = CodePointInversionListAndStringList::try_from(cp_list, str_list).unwrap();
222    ///
223    /// assert!(cpilsl.contains('A'));
224    /// assert!(cpilsl.contains('ቔ'));  // U+1254 ETHIOPIC SYLLABLE QHEE
225    /// assert!(!cpilsl.contains('\u{1_0000}'));
226    /// assert!(!cpilsl.contains('🨫'));  // U+1FA2B NEUTRAL CHESS TURNED QUEEN
227    pub fn contains(&self, ch: char) -> bool {
228        self.contains32(ch as u32)
229    }
230
231    /// Access the underlying [`CodePointInversionList`].
232    pub fn code_points(&self) -> &CodePointInversionList<'data> {
233        &self.cp_inv_list
234    }
235
236    /// Access the contained strings.
237    pub fn strings(&self) -> &VarZeroSlice<str> {
238        &self.str_list
239    }
240}
241
242#[cfg(feature = "alloc")]
243/// ✨ *Enabled with the `alloc` Cargo feature.*
244impl<'a> FromIterator<&'a str> for CodePointInversionListAndStringList<'_> {
245    fn from_iter<I>(it: I) -> Self
246    where
247        I: IntoIterator<Item = &'a str>,
248    {
249        let mut builder = CodePointInversionListBuilder::new();
250        let mut strings = Vec::<&str>::new();
251        for s in it {
252            let mut chars = s.chars();
253            if let Some(first_char) = chars.next() {
254                if chars.next().is_none() {
255                    builder.add_char(first_char);
256                    continue;
257                }
258            }
259            strings.push(s);
260        }
261
262        // Ensure that the string list is sorted. If not, the binary search that
263        // is used for `.contains(&str)` will return garbage output.
264        strings.sort_unstable();
265        strings.dedup();
266
267        let cp_inv_list = builder.build();
268        let str_list = VarZeroVec::<str>::from(&strings);
269
270        CodePointInversionListAndStringList {
271            cp_inv_list,
272            str_list,
273        }
274    }
275}
276
277/// Custom Errors for [`CodePointInversionListAndStringList`].
278#[derive(Display, Debug)]
279#[allow(clippy::exhaustive_enums)] // todo, missed in 2.0
280pub enum InvalidStringList {
281    /// A string in the string list had an invalid length
282    #[cfg_attr(feature = "alloc", displaydoc("Invalid string length for string: {0}"))]
283    InvalidStringLength(#[cfg(feature = "alloc")] String),
284    /// A string in the string list appears more than once
285    #[cfg_attr(feature = "alloc", displaydoc("String list has duplicate: {0}"))]
286    StringListNotUnique(#[cfg(feature = "alloc")] String),
287    /// Two strings in the string list compare to each other opposite of sorted order
288    #[cfg_attr(
289        feature = "alloc",
290        displaydoc("Strings in string list not in sorted order: ({0}, {1})")
291    )]
292    StringListNotSorted(
293        #[cfg(feature = "alloc")] String,
294        #[cfg(feature = "alloc")] String,
295    ),
296}
297
298#[cfg(test)]
299mod tests {
300    use super::*;
301
302    #[test]
303    fn test_size_has_strings() {
304        let cp_slice = &[0, 1, 0x7F, 0x80, 0xFFFF, 0x1_0000, 0x10_FFFF, 0x11_0000];
305        let cp_list = CodePointInversionList::try_from_u32_inversion_list_slice(cp_slice).unwrap();
306        let str_slice = &["ascii_max", "bmp_max", "unicode_max", "zero"];
307        let str_list = VarZeroVec::<str>::from(str_slice);
308
309        let cpilsl = CodePointInversionListAndStringList::try_from(cp_list, str_list).unwrap();
310
311        assert!(cpilsl.has_strings());
312        assert_eq!(8, cpilsl.size());
313    }
314
315    #[test]
316    fn test_empty_string_allowed() {
317        let cp_slice = &[0, 1, 0x7F, 0x80, 0xFFFF, 0x1_0000, 0x10_FFFF, 0x11_0000];
318        let cp_list = CodePointInversionList::try_from_u32_inversion_list_slice(cp_slice).unwrap();
319        let str_slice = &["", "ascii_max", "bmp_max", "unicode_max", "zero"];
320        let str_list = VarZeroVec::<str>::from(str_slice);
321
322        let cpilsl = CodePointInversionListAndStringList::try_from(cp_list, str_list).unwrap();
323
324        assert!(cpilsl.has_strings());
325        assert_eq!(9, cpilsl.size());
326    }
327
328    #[test]
329    fn test_invalid_string() {
330        let cp_slice = &[0, 1];
331        let cp_list = CodePointInversionList::try_from_u32_inversion_list_slice(cp_slice).unwrap();
332        let str_slice = &["a"];
333        let str_list = VarZeroVec::<str>::from(str_slice);
334
335        let cpilsl = CodePointInversionListAndStringList::try_from(cp_list, str_list);
336
337        assert!(matches!(
338            cpilsl,
339            Err(InvalidStringList::InvalidStringLength(_))
340        ));
341    }
342
343    #[test]
344    fn test_invalid_string_list_has_duplicate() {
345        let cp_slice = &[0, 1];
346        let cp_list = CodePointInversionList::try_from_u32_inversion_list_slice(cp_slice).unwrap();
347        let str_slice = &["abc", "abc"];
348        let str_list = VarZeroVec::<str>::from(str_slice);
349
350        let cpilsl = CodePointInversionListAndStringList::try_from(cp_list, str_list);
351
352        assert!(matches!(
353            cpilsl,
354            Err(InvalidStringList::StringListNotUnique(_))
355        ));
356    }
357
358    #[test]
359    fn test_invalid_string_list_not_sorted() {
360        let cp_slice = &[0, 1];
361        let cp_list = CodePointInversionList::try_from_u32_inversion_list_slice(cp_slice).unwrap();
362        let str_slice = &["xyz", "abc"];
363        let str_list = VarZeroVec::<str>::from(str_slice);
364
365        let cpilsl = CodePointInversionListAndStringList::try_from(cp_list, str_list);
366
367        assert!(matches!(
368            cpilsl,
369            Err(InvalidStringList::StringListNotSorted(_, _))
370        ));
371    }
372
373    #[test]
374    fn test_from_iter_invariants() {
375        let in_strs_1 = ["a", "abc", "xyz", "abc"];
376        let in_strs_2 = ["xyz", "abc", "a", "abc"];
377
378        let cpilsl_1 = CodePointInversionListAndStringList::from_iter(in_strs_1);
379        let cpilsl_2 = CodePointInversionListAndStringList::from_iter(in_strs_2);
380
381        assert_eq!(cpilsl_1, cpilsl_2);
382
383        assert!(cpilsl_1.has_strings());
384        assert!(cpilsl_1.contains_str("abc"));
385        assert!(cpilsl_1.contains_str("xyz"));
386        assert!(!cpilsl_1.contains_str("def"));
387
388        assert_eq!(1, cpilsl_1.cp_inv_list.size());
389        assert!(cpilsl_1.contains('a'));
390        assert!(!cpilsl_1.contains('0'));
391        assert!(!cpilsl_1.contains('q'));
392
393        assert_eq!(3, cpilsl_1.size());
394    }
395}
icu_collections/codepointinvliststringlist/mod.rs

icu_collections/codepointinvliststringlist/
mod.rs
