icu_collections/codepointinvliststringlist/
mod.rs

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

icu_collections/codepointinvliststringlist/
mod.rs
