// This file is part of ICU4X. For terms of use, please see the file // called LICENSE at the top level of the ICU4X source tree // (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ). use crate::codepointtrie::error::Error; use crate::codepointtrie::impl_const::*; use crate::codepointinvlist::CodePointInversionList; use core::char::CharTryFromError; use core::convert::Infallible; use core::convert::TryFrom; use core::fmt::Display; use core::iter::FromIterator; use core::num::TryFromIntError; use core::ops::RangeInclusive; use yoke::Yokeable; use zerofrom::ZeroFrom; use zerovec::ZeroVec; use zerovec::ZeroVecError; /// The type of trie represents whether the trie has an optimization that /// would make it smaller or faster. /// /// Regarding performance, a trie being a small or fast type affects the number of array lookups /// needed for code points in the range `[0x1000, 0x10000)`. In this range, `Small` tries use 4 array lookups, /// while `Fast` tries use 2 array lookups. /// Code points before the interval (in `[0, 0x1000)`) will always use 2 array lookups. /// Code points after the interval (in `[0x10000, 0x10FFFF]`) will always use 4 array lookups. /// /// Regarding size, `Fast` type tries are larger than `Small` type tries because the minimum size of /// the index array is larger. The minimum size is the "fast max" limit, which is the limit of the range /// of code points with 2 array lookups. /// /// See the document [Unicode Properties and Code Point Tries in ICU4X](https://github.com/unicode-org/icu4x/blob/main/documents/design/properties_code_point_trie.md). /// /// Also see [`UCPTrieType`](https://unicode-org.github.io/icu-docs/apidoc/dev/icu4c/ucptrie_8h.html) in ICU4C. #[derive(Clone, Copy, PartialEq, Debug, Eq)] #[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))] #[cfg_attr(feature = "databake", derive(databake::Bake), databake(path = icu_collections::codepointtrie))] pub enum TrieType { /// Represents the "fast" type code point tries for the /// [`TrieType`] trait. The "fast max" limit is set to `0xffff`. Fast = 0, /// Represents the "small" type code point tries for the /// [`TrieType`] trait. The "fast max" limit is set to `0x0fff`. Small = 1, } // TrieValue trait // AsULE is AsUnalignedLittleEndian, i.e. "allowed in a zerovec" /// A trait representing the values stored in the data array of a [`CodePointTrie`]. /// This trait is used as a type parameter in constructing a `CodePointTrie`. pub trait TrieValue: Copy + Eq + PartialEq + zerovec::ule::AsULE + 'static { /// Last-resort fallback value to return if we cannot read data from the trie. /// /// In most cases, the error value is read from the last element of the `data` array, /// this value is used for empty codepointtrie arrays /// Error type when converting from a u32 to this `TrieValue`. type TryFromU32Error: Display; /// A parsing function that is primarily motivated by deserialization contexts. /// When the serialization type width is smaller than 32 bits, then it is expected /// that the call site will widen the value to a `u32` first. fn try_from_u32(i: u32) -> Result; /// A method for converting back to a `u32` that can roundtrip through /// [`Self::try_from_u32()`]. The default implementation of this trait /// method panics in debug mode and returns 0 in release mode. /// /// This method is allowed to have GIGO behavior when fed a value that has /// no corresponding `u32` (since such values cannot be stored in the trie) fn to_u32(self) -> u32 { debug_assert!( false, "TrieValue::to_u32() not implemented for {}", ::core::any::type_name::() ); 0 } } macro_rules! impl_primitive_trie_value { ($primitive:ty, $error:ty) => { impl TrieValue for $primitive { type TryFromU32Error = $error; fn try_from_u32(i: u32) -> Result { Self::try_from(i) } fn to_u32(self) -> u32 { // bitcast when the same size, zero-extend/sign-extend // when not the same size self as u32 } } }; } impl_primitive_trie_value!(u8, TryFromIntError); impl_primitive_trie_value!(u16, TryFromIntError); impl_primitive_trie_value!(u32, Infallible); impl_primitive_trie_value!(i8, TryFromIntError); impl_primitive_trie_value!(i16, TryFromIntError); impl_primitive_trie_value!(i32, TryFromIntError); impl_primitive_trie_value!(char, CharTryFromError); /// Helper function used by [`get_range`]. Converts occurrences of trie's null /// value into the provided `null_value`. /// /// Note: the ICU version of this helper function uses a `ValueFilter` function /// to apply a transform on a non-null value. But currently, this implementation /// stops short of that functionality, and instead leaves the non-null trie value /// untouched. This is equivalent to having a `ValueFilter` function that is the /// identity function. fn maybe_filter_value(value: T, trie_null_value: T, null_value: T) -> T { if value == trie_null_value { null_value } else { value } } /// This struct represents a de-serialized [`CodePointTrie`] that was exported from /// ICU binary data. /// /// For more information: /// - [ICU Site design doc](http://site.icu-project.org/design/struct/utrie) /// - [ICU User Guide section on Properties lookup](https://unicode-org.github.io/icu/userguide/strings/properties.html#lookup) // serde impls in crate::serde #[derive(Debug, Eq, PartialEq, Yokeable, ZeroFrom)] pub struct CodePointTrie<'trie, T: TrieValue> { pub(crate) header: CodePointTrieHeader, pub(crate) index: ZeroVec<'trie, u16>, pub(crate) data: ZeroVec<'trie, T>, // serde impl skips this field #[zerofrom(clone)] // TrieValue is Copy, this allows us to avoid // a T: ZeroFrom bound pub(crate) error_value: T, } /// This struct contains the fixed-length header fields of a [`CodePointTrie`]. #[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))] #[cfg_attr(feature = "databake", derive(databake::Bake), databake(path = icu_collections::codepointtrie))] #[derive(Copy, Clone, Debug, Eq, PartialEq, Yokeable, ZeroFrom)] pub struct CodePointTrieHeader { /// The code point of the start of the last range of the trie. A /// range is defined as a partition of the code point space such that the /// value in this trie associated with all code points of the same range is /// the same. /// /// For the property value data for many Unicode properties, /// often times, `high_start` is `U+10000` or lower. In such cases, not /// reserving space in the `index` array for duplicate values is a large /// savings. The "highValue" associated with the `high_start` range is /// stored at the second-to-last position of the `data` array. /// (See `impl_const::HIGH_VALUE_NEG_DATA_OFFSET`.) pub high_start: u32, /// A version of the `high_start` value that is right-shifted 12 spaces, /// but is rounded up to a multiple `0x1000` for easy testing from UTF-8 /// lead bytes. pub shifted12_high_start: u16, /// Offset for the null block in the "index-3" table of the `index` array. /// Set to an impossibly high value (e.g., `0xffff`) if there is no /// dedicated index-3 null block. pub index3_null_offset: u16, /// Internal data null block offset, not shifted. /// Set to an impossibly high value (e.g., `0xfffff`) if there is no /// dedicated data null block. pub data_null_offset: u32, /// The value stored in the trie that represents a null value being /// associated to a code point. pub null_value: u32, /// The enum value representing the type of trie, where trie type is as it /// is defined in ICU (ex: Fast, Small). pub trie_type: TrieType, } impl TryFrom for TrieType { type Error = crate::codepointtrie::error::Error; fn try_from(trie_type_int: u8) -> Result { match trie_type_int { 0 => Ok(TrieType::Fast), 1 => Ok(TrieType::Small), _ => Err(crate::codepointtrie::error::Error::FromDeserialized { reason: "Cannot parse value for trie_type", }), } } } impl<'trie, T: TrieValue> CodePointTrie<'trie, T> { #[doc(hidden)] // databake internal pub const fn from_parts( header: CodePointTrieHeader, index: ZeroVec<'trie, u16>, data: ZeroVec<'trie, T>, error_value: T, ) -> Self { Self { header, index, data, error_value, } } /// Returns a new [`CodePointTrie`] backed by borrowed data for the `index` /// array and `data` array, whose data values have width `W`. pub fn try_new( header: CodePointTrieHeader, index: ZeroVec<'trie, u16>, data: ZeroVec<'trie, T>, ) -> Result, Error> { // Validation invariants are not needed here when constructing a new // `CodePointTrie` because: // // - Rust includes the size of a slice (or Vec or similar), which allows it // to prevent lookups at out-of-bounds indices, whereas in C++, it is the // programmer's responsibility to keep track of length info. // - For lookups into collections, Rust guarantees that a fallback value will // be returned in the case of `.get()` encountering a lookup error, via // the `Option` type. // - The `ZeroVec` serializer stores the length of the array along with the // ZeroVec data, meaning that a deserializer would also see that length info. let error_value = data.last().ok_or(Error::EmptyDataVector)?; let trie: CodePointTrie<'trie, T> = CodePointTrie { header, index, data, error_value, }; Ok(trie) } /// Returns the position in the data array containing the trie's stored /// error value. #[inline(always)] // `always` based on normalizer benchmarking fn trie_error_val_index(&self) -> u32 { self.data.len() as u32 - ERROR_VALUE_NEG_DATA_OFFSET } fn internal_small_index(&self, code_point: u32) -> u32 { let mut index1_pos: u32 = code_point >> SHIFT_1; if self.header.trie_type == TrieType::Fast { debug_assert!( FAST_TYPE_FAST_INDEXING_MAX < code_point && code_point < self.header.high_start ); index1_pos = index1_pos + BMP_INDEX_LENGTH - OMITTED_BMP_INDEX_1_LENGTH; } else { assert!(code_point < self.header.high_start && self.header.high_start > SMALL_LIMIT); index1_pos += SMALL_INDEX_LENGTH; } let index1_val = if let Some(index1_val) = self.index.get(index1_pos as usize) { index1_val } else { return self.trie_error_val_index(); }; let index3_block_idx: u32 = (index1_val as u32) + ((code_point >> SHIFT_2) & INDEX_2_MASK); let mut index3_block: u32 = if let Some(index3_block) = self.index.get(index3_block_idx as usize) { index3_block as u32 } else { return self.trie_error_val_index(); }; let mut index3_pos: u32 = (code_point >> SHIFT_3) & INDEX_3_MASK; let mut data_block: u32; if index3_block & 0x8000 == 0 { // 16-bit indexes data_block = if let Some(data_block) = self.index.get((index3_block + index3_pos) as usize) { data_block as u32 } else { return self.trie_error_val_index(); }; } else { // 18-bit indexes stored in groups of 9 entries per 8 indexes. index3_block = (index3_block & 0x7fff) + (index3_pos & !7) + (index3_pos >> 3); index3_pos &= 7; data_block = if let Some(data_block) = self.index.get(index3_block as usize) { data_block as u32 } else { return self.trie_error_val_index(); }; data_block = (data_block << (2 + (2 * index3_pos))) & 0x30000; index3_block += 1; data_block = if let Some(index3_val) = self.index.get((index3_block + index3_pos) as usize) { data_block | (index3_val as u32) } else { return self.trie_error_val_index(); }; } // Returns data_pos == data_block (offset) + // portion of code_point bit field for last (4th) lookup data_block + (code_point & SMALL_DATA_MASK) } /// Returns the position in the `data` array for the given code point, /// where this code point is at or above the fast limit associated for the /// `trie_type`. We will refer to that limit as "`fastMax`" here. /// /// A lookup of the value in the code point trie for a code point in the /// code point space range [`fastMax`, `high_start`) will be a 4-step /// lookup: 3 lookups in the `index` array and one lookup in the `data` /// array. Lookups for code points in the range [`high_start`, /// `CODE_POINT_MAX`] are short-circuited to be a single lookup, see /// [`CodePointTrieHeader::high_start`]. fn small_index(&self, code_point: u32) -> u32 { if code_point >= self.header.high_start { self.data.len() as u32 - HIGH_VALUE_NEG_DATA_OFFSET } else { self.internal_small_index(code_point) // helper fn } } /// Returns the position in the `data` array for the given code point, /// where this code point is below the fast limit associated for the /// `trie type`. We will refer to that limit as "`fastMax`" here. /// /// A lookup of the value in the code point trie for a code point in the /// code point space range [0, `fastMax`) will be a 2-step lookup: 1 /// lookup in the `index` array and one lookup in the `data` array. By /// design, for trie type `T`, there is an element allocated in the `index` /// array for each block of code points in [0, `fastMax`), which in /// turn guarantees that those code points are represented and only need 1 /// lookup. #[inline(always)] // `always` based on normalizer benchmarking fn fast_index(&self, code_point: u32) -> u32 { let index_array_pos: u32 = code_point >> FAST_TYPE_SHIFT; let index_array_val: u16 = if let Some(index_array_val) = self.index.get(index_array_pos as usize) { index_array_val } else { return self.trie_error_val_index(); }; let fast_index_val: u32 = index_array_val as u32 + (code_point & FAST_TYPE_DATA_MASK); fast_index_val } /// Returns the value that is associated with `code_point` in this [`CodePointTrie`]. /// /// # Examples /// /// ``` /// use icu::collections::codepointtrie::planes; /// let trie = planes::get_planes_trie(); /// /// assert_eq!(0, trie.get32(0x41)); // 'A' as u32 /// assert_eq!(0, trie.get32(0x13E0)); // 'Ꮰ' as u32 /// assert_eq!(1, trie.get32(0x10044)); // '𐁄' as u32 /// ``` #[inline(always)] // `always` based on normalizer benchmarking pub fn get32(&self, code_point: u32) -> T { // If we cannot read from the data array, then return the sentinel value // self.error_value() for the instance type for T: TrieValue. self.get32_ule(code_point) .map(|t| T::from_unaligned(*t)) .unwrap_or(self.error_value) } /// Returns the value that is associated with `char` in this [`CodePointTrie`]. /// /// # Examples /// /// ``` /// use icu::collections::codepointtrie::planes; /// let trie = planes::get_planes_trie(); /// /// assert_eq!(0, trie.get('A')); // 'A' as u32 /// assert_eq!(0, trie.get('Ꮰ')); // 'Ꮰ' as u32 /// assert_eq!(1, trie.get('𐁄')); // '𐁄' as u32 /// ``` #[inline(always)] pub fn get(&self, c: char) -> T { self.get32(u32::from(c)) } /// Returns a reference to the ULE of the value that is associated with `code_point` in this [`CodePointTrie`]. /// /// # Examples /// /// ``` /// use icu::collections::codepointtrie::planes; /// let trie = planes::get_planes_trie(); /// /// assert_eq!(Some(&0), trie.get32_ule(0x41)); // 'A' as u32 /// assert_eq!(Some(&0), trie.get32_ule(0x13E0)); // 'Ꮰ' as u32 /// assert_eq!(Some(&1), trie.get32_ule(0x10044)); // '𐁄' as u32 /// ``` #[inline(always)] // `always` based on normalizer benchmarking pub fn get32_ule(&self, code_point: u32) -> Option<&T::ULE> { // All code points up to the fast max limit are represented // individually in the `index` array to hold their `data` array position, and // thus only need 2 lookups for a [CodePointTrie::get()](`crate::codepointtrie::CodePointTrie::get`). // Code points above the "fast max" limit require 4 lookups. let fast_max = match self.header.trie_type { TrieType::Fast => FAST_TYPE_FAST_INDEXING_MAX, TrieType::Small => SMALL_TYPE_FAST_INDEXING_MAX, }; let data_pos: u32 = if code_point <= fast_max { Self::fast_index(self, code_point) } else if code_point <= CODE_POINT_MAX { Self::small_index(self, code_point) } else { self.trie_error_val_index() }; // Returns the trie value (or trie's error value). self.data.as_ule_slice().get(data_pos as usize) } /// Converts the [`CodePointTrie`] into one that returns another type of the same size. /// /// Borrowed data remains borrowed, and owned data remains owned. /// /// If the old and new types are not the same size, use /// [`CodePointTrie::try_alloc_map_value`]. /// /// # Panics /// /// Panics if `T` and `P` are different sizes. /// /// More specifically, panics if [`ZeroVec::try_into_converted()`] panics when converting /// `ZeroVec` into `ZeroVec

`, which happens if `T::ULE` and `P::ULE` differ in size. /// /// # Examples /// /// ```no_run /// use icu::collections::codepointtrie::planes; /// use icu::collections::codepointtrie::CodePointTrie; /// /// let planes_trie_u8: CodePointTrie = planes::get_planes_trie(); /// let planes_trie_i8: CodePointTrie = /// planes_trie_u8.try_into_converted().expect("infallible"); /// /// assert_eq!(planes_trie_i8.get32(0x30000), 3); /// ``` pub fn try_into_converted

(self) -> Result, ZeroVecError> where P: TrieValue, { let converted_data = self.data.try_into_converted()?; let error_ule = self.error_value.to_unaligned(); let slice = &[error_ule]; let error_vec = ZeroVec::::new_borrowed(slice); let error_converted = error_vec.try_into_converted::

()?; #[allow(clippy::expect_used)] // we know this cannot fail Ok(CodePointTrie { header: self.header, index: self.index, data: converted_data, error_value: error_converted .get(0) .expect("vector known to have one element"), }) } /// Maps the [`CodePointTrie`] into one that returns a different type. /// /// This function returns owned data. /// /// If the old and new types are the same size, use the more efficient /// [`CodePointTrie::try_into_converted`]. /// /// # Examples /// /// ``` /// use icu::collections::codepointtrie::planes; /// use icu::collections::codepointtrie::CodePointTrie; /// /// let planes_trie_u8: CodePointTrie = planes::get_planes_trie(); /// let planes_trie_u16: CodePointTrie = planes_trie_u8 /// .try_alloc_map_value(TryFrom::try_from) /// .expect("infallible"); /// /// assert_eq!(planes_trie_u16.get32(0x30000), 3); /// ``` pub fn try_alloc_map_value( &self, mut f: impl FnMut(T) -> Result, ) -> Result, E> where P: TrieValue, { let error_converted = f(self.error_value)?; let converted_data = self.data.iter().map(f).collect::, E>>()?; Ok(CodePointTrie { header: self.header, index: self.index.clone(), data: converted_data, error_value: error_converted, }) } /// Returns a [`CodePointMapRange`] struct which represents a range of code /// points associated with the same trie value. The returned range will be /// the longest stretch of consecutive code points starting at `start` that /// share this value. /// /// This method is designed to use the internal details of /// the structure of [`CodePointTrie`] to be optimally efficient. This will /// outperform a naive approach that just uses [`CodePointTrie::get()`]. /// /// This method provides lower-level functionality that can be used in the /// implementation of other methods that are more convenient to the user. /// To obtain an optimal partition of the code point space for /// this trie resulting in the fewest number of ranges, see /// [`CodePointTrie::iter_ranges()`]. /// /// # Examples /// /// ``` /// use icu::collections::codepointtrie::planes; /// /// let trie = planes::get_planes_trie(); /// /// const CODE_POINT_MAX: u32 = 0x10ffff; /// let start = 0x1_0000; /// let exp_end = 0x1_ffff; /// /// let start_val = trie.get32(start); /// assert_eq!(trie.get32(exp_end), start_val); /// assert_ne!(trie.get32(exp_end + 1), start_val); /// /// use icu::collections::codepointtrie::CodePointMapRange; /// /// let cpm_range: CodePointMapRange = trie.get_range(start).unwrap(); /// /// assert_eq!(cpm_range.range.start(), &start); /// assert_eq!(cpm_range.range.end(), &exp_end); /// assert_eq!(cpm_range.value, start_val); /// /// // `start` can be any code point, whether or not it lies on the boundary /// // of a maximally large range that still contains `start` /// /// let submaximal_1_start = start + 0x1234; /// let submaximal_1 = trie.get_range(submaximal_1_start).unwrap(); /// assert_eq!(submaximal_1.range.start(), &0x1_1234); /// assert_eq!(submaximal_1.range.end(), &0x1_ffff); /// assert_eq!(submaximal_1.value, start_val); /// /// let submaximal_2_start = start + 0xffff; /// let submaximal_2 = trie.get_range(submaximal_2_start).unwrap(); /// assert_eq!(submaximal_2.range.start(), &0x1_ffff); /// assert_eq!(submaximal_2.range.end(), &0x1_ffff); /// assert_eq!(submaximal_2.value, start_val); /// ``` pub fn get_range(&self, start: u32) -> Option> { // Exit early if the start code point is out of range, or if it is // in the last range of code points in high_start..=CODE_POINT_MAX // (start- and end-inclusive) that all share the same trie value. if CODE_POINT_MAX < start { return None; } if start >= self.header.high_start { let di: usize = self.data.len() - (HIGH_VALUE_NEG_DATA_OFFSET as usize); let value: T = self.data.get(di)?; return Some(CodePointMapRange { range: RangeInclusive::new(start, CODE_POINT_MAX), value, }); } let null_value: T = T::try_from_u32(self.header.null_value).ok()?; let mut prev_i3_block: u32 = u32::MAX; // using u32::MAX (instead of -1 as an i32 in ICU) let mut prev_block: u32 = u32::MAX; // using u32::MAX (instead of -1 as an i32 in ICU) let mut c: u32 = start; let mut trie_value: T = self.error_value(); let mut value: T = self.error_value(); let mut have_value: bool = false; loop { let i3_block: u32; let mut i3: u32; let i3_block_length: u32; let data_block_length: u32; // Initialize values before beginning the iteration in the subsequent // `loop` block. In particular, use the "i3*" local variables // (representing the `index` array position's offset + increment // for a 3rd-level trie lookup) to help initialize the data block // variable `block` in the loop for the `data` array. // // When a lookup code point is <= the trie's *_FAST_INDEXING_MAX that // corresponds to its `trie_type`, the lookup only takes 2 steps // (once into the `index`, once into the `data` array); otherwise, // takes 4 steps (3 iterative lookups into the `index`, once more // into the `data` array). So for convenience's sake, when we have the // 2-stage lookup, reuse the "i3*" variable names for the first lookup. if c <= 0xffff && (self.header.trie_type == TrieType::Fast || c <= SMALL_TYPE_FAST_INDEXING_MAX) { i3_block = 0; i3 = c >> FAST_TYPE_SHIFT; i3_block_length = if self.header.trie_type == TrieType::Fast { BMP_INDEX_LENGTH } else { SMALL_INDEX_LENGTH }; data_block_length = FAST_TYPE_DATA_BLOCK_LENGTH; } else { // Use the multi-stage index. let mut i1: u32 = c >> SHIFT_1; if self.header.trie_type == TrieType::Fast { debug_assert!(0xffff < c && c < self.header.high_start); i1 = i1 + BMP_INDEX_LENGTH - OMITTED_BMP_INDEX_1_LENGTH; } else { debug_assert!( c < self.header.high_start && self.header.high_start > SMALL_LIMIT ); i1 += SMALL_INDEX_LENGTH; } let i2: u16 = self.index.get(i1 as usize)?; let i3_block_idx: u32 = (i2 as u32) + ((c >> SHIFT_2) & INDEX_2_MASK); i3_block = if let Some(i3b) = self.index.get(i3_block_idx as usize) { i3b as u32 } else { return None; }; if i3_block == prev_i3_block && (c - start) >= CP_PER_INDEX_2_ENTRY { // The index-3 block is the same as the previous one, and filled with value. debug_assert!((c & (CP_PER_INDEX_2_ENTRY - 1)) == 0); c += CP_PER_INDEX_2_ENTRY; if c >= self.header.high_start { break; } else { continue; } } prev_i3_block = i3_block; if i3_block == self.header.index3_null_offset as u32 { // This is the index-3 null block. // All of the `data` array blocks pointed to by the values // in this block of the `index` 3rd-stage subarray will // contain this trie's null_value. So if we are in the middle // of a range, end it and return early, otherwise start a new // range of null values. if have_value { if null_value != value { return Some(CodePointMapRange { range: RangeInclusive::new(start, c - 1), value, }); } } else { trie_value = T::try_from_u32(self.header.null_value).ok()?; value = null_value; have_value = true; } prev_block = self.header.data_null_offset; c = (c + CP_PER_INDEX_2_ENTRY) & !(CP_PER_INDEX_2_ENTRY - 1); if c >= self.header.high_start { break; } else { continue; } } i3 = (c >> SHIFT_3) & INDEX_3_MASK; i3_block_length = INDEX_3_BLOCK_LENGTH; data_block_length = SMALL_DATA_BLOCK_LENGTH; } // Enumerate data blocks for one index-3 block. loop { let mut block: u32; if (i3_block & 0x8000) == 0 { block = if let Some(b) = self.index.get((i3_block + i3) as usize) { b as u32 } else { return None; }; } else { // 18-bit indexes stored in groups of 9 entries per 8 indexes. let mut group: u32 = (i3_block & 0x7fff) + (i3 & !7) + (i3 >> 3); let gi: u32 = i3 & 7; let gi_val: u32 = if let Some(giv) = self.index.get(group as usize) { giv.into() } else { return None; }; block = (gi_val << (2 + (2 * gi))) & 0x30000; group += 1; let ggi_val: u32 = if let Some(ggiv) = self.index.get((group + gi) as usize) { ggiv as u32 } else { return None; }; block |= ggi_val; } // If our previous and current return values of the 3rd-stage `index` // lookup yield the same `data` block offset, and if we already know that // the entire `data` block / subarray starting at that offset stores // `value` and nothing else, then we can extend our range by the length // of a data block and continue. // Otherwise, we have to iterate over the values stored in the // new data block to see if they differ from `value`. if block == prev_block && (c - start) >= data_block_length { // The block is the same as the previous one, and filled with value. debug_assert!((c & (data_block_length - 1)) == 0); c += data_block_length; } else { let data_mask: u32 = data_block_length - 1; prev_block = block; if block == self.header.data_null_offset { // This is the data null block. // If we are in the middle of a range, end it and // return early, otherwise start a new range of null // values. if have_value { if null_value != value { return Some(CodePointMapRange { range: RangeInclusive::new(start, c - 1), value, }); } } else { trie_value = T::try_from_u32(self.header.null_value).ok()?; value = null_value; have_value = true; } c = (c + data_block_length) & !data_mask; } else { let mut di: u32 = block + (c & data_mask); let mut trie_value_2: T = self.data.get(di as usize)?; if have_value { if trie_value_2 != trie_value { if maybe_filter_value( trie_value_2, T::try_from_u32(self.header.null_value).ok()?, null_value, ) != value { return Some(CodePointMapRange { range: RangeInclusive::new(start, c - 1), value, }); } // `trie_value` stores the previous value that was retrieved // from the trie. // `value` stores the value associated for the range (return // value) that we are currently building, which is computed // as a transformation by applying maybe_filter_value() // to the trie value. // The current trie value `trie_value_2` within this data block // differs here from the previous value in `trie_value`. // But both map to `value` after applying `maybe_filter_value`. // It is not clear whether the previous or the current trie value // (or neither) is more likely to match potential subsequent trie // values that would extend the range by mapping to `value`. // On the assumption of locality -- often times consecutive // characters map to the same trie values -- remembering the new // one might make it faster to extend this range further // (by increasing the chance that the next `trie_value_2 != // trie_value` test will be false). trie_value = trie_value_2; // may or may not help } } else { trie_value = trie_value_2; value = maybe_filter_value( trie_value_2, T::try_from_u32(self.header.null_value).ok()?, null_value, ); have_value = true; } c += 1; while (c & data_mask) != 0 { di += 1; trie_value_2 = self.data.get(di as usize)?; if trie_value_2 != trie_value { if maybe_filter_value( trie_value_2, T::try_from_u32(self.header.null_value).ok()?, null_value, ) != value { return Some(CodePointMapRange { range: RangeInclusive::new(start, c - 1), value, }); } // `trie_value` stores the previous value that was retrieved // from the trie. // `value` stores the value associated for the range (return // value) that we are currently building, which is computed // as a transformation by applying maybe_filter_value() // to the trie value. // The current trie value `trie_value_2` within this data block // differs here from the previous value in `trie_value`. // But both map to `value` after applying `maybe_filter_value`. // It is not clear whether the previous or the current trie value // (or neither) is more likely to match potential subsequent trie // values that would extend the range by mapping to `value`. // On the assumption of locality -- often times consecutive // characters map to the same trie values -- remembering the new // one might make it faster to extend this range further // (by increasing the chance that the next `trie_value_2 != // trie_value` test will be false). trie_value = trie_value_2; // may or may not help } c += 1; } } } i3 += 1; if i3 >= i3_block_length { break; } } if c >= self.header.high_start { break; } } debug_assert!(have_value); // Now that c >= high_start, compare `value` to `high_value` to see // if we can merge our current range with the high_value range // high_start..=CODE_POINT_MAX (start- and end-inclusive), otherwise // stop at high_start - 1. let di: u32 = self.data.len() as u32 - HIGH_VALUE_NEG_DATA_OFFSET; let high_value: T = self.data.get(di as usize)?; if maybe_filter_value( high_value, T::try_from_u32(self.header.null_value).ok()?, null_value, ) != value { c -= 1; } else { c = CODE_POINT_MAX; } Some(CodePointMapRange { range: RangeInclusive::new(start, c), value, }) } /// Yields an [`Iterator`] returning ranges of consecutive code points that /// share the same value in the [`CodePointTrie`], as given by /// [`CodePointTrie::get_range()`]. /// /// # Examples /// /// ``` /// use core::ops::RangeInclusive; /// use icu::collections::codepointtrie::planes; /// use icu::collections::codepointtrie::CodePointMapRange; /// /// let planes_trie = planes::get_planes_trie(); /// /// let mut ranges = planes_trie.iter_ranges(); /// /// for plane in 0..=16 { /// let exp_start = plane * 0x1_0000; /// let exp_end = exp_start + 0xffff; /// assert_eq!( /// ranges.next(), /// Some(CodePointMapRange { /// range: RangeInclusive::new(exp_start, exp_end), /// value: plane as u8 /// }) /// ); /// } /// /// // Hitting the end of the iterator returns `None`, as will subsequent /// // calls to .next(). /// assert_eq!(ranges.next(), None); /// assert_eq!(ranges.next(), None); /// ``` pub fn iter_ranges(&self) -> CodePointMapRangeIterator { let init_range = Some(CodePointMapRange { range: RangeInclusive::new(u32::MAX, u32::MAX), value: self.error_value(), }); CodePointMapRangeIterator:: { cpt: self, cpm_range: init_range, } } /// Yields an [`Iterator`] returning the ranges of the code points whose values /// match `value` in the [`CodePointTrie`]. /// /// # Examples /// /// ``` /// use icu::collections::codepointtrie::planes; /// /// let trie = planes::get_planes_trie(); /// /// let plane_val = 2; /// let mut sip_range_iter = trie.get_ranges_for_value(plane_val as u8); /// /// let start = plane_val * 0x1_0000; /// let end = start + 0xffff; /// /// let sip_range = sip_range_iter.next() /// .expect("Plane 2 (SIP) should exist in planes data"); /// assert_eq!(start..=end, sip_range); /// /// assert!(sip_range_iter.next().is_none()); pub fn get_ranges_for_value(&self, value: T) -> impl Iterator> + '_ { self.iter_ranges() .filter(move |cpm_range| cpm_range.value == value) .map(|cpm_range| cpm_range.range) } /// Yields an [`Iterator`] returning the ranges of the code points after passing /// the value through a mapping function. /// /// This is preferable to calling `.get_ranges().map()` since it will coalesce /// adjacent ranges into one. /// /// # Examples /// /// ``` /// use icu::collections::codepointtrie::planes; /// /// let trie = planes::get_planes_trie(); /// /// let plane_val = 2; /// let mut sip_range_iter = trie.iter_ranges_mapped(|value| value != plane_val as u8).filter(|range| range.value); /// /// let end = plane_val * 0x1_0000 - 1; /// /// let sip_range = sip_range_iter.next() /// .expect("Complemented planes data should have at least one entry"); /// assert_eq!(0..=end, sip_range.range); pub fn iter_ranges_mapped<'a, U: Eq + 'a>( &'a self, mut map: impl FnMut(T) -> U + Copy + 'a, ) -> impl Iterator> + 'a { crate::iterator_utils::RangeListIteratorCoalescer::new(self.iter_ranges().map( move |range| CodePointMapRange { range: range.range, value: map(range.value), }, )) } /// Returns a [`CodePointInversionList`] for the code points that have the given /// [`TrieValue`] in the trie. /// /// # Examples /// /// ``` /// use icu::collections::codepointtrie::planes; /// /// let trie = planes::get_planes_trie(); /// /// let plane_val = 2; /// let sip = trie.get_set_for_value(plane_val as u8); /// /// let start = plane_val * 0x1_0000; /// let end = start + 0xffff; /// /// assert!(!sip.contains32(start - 1)); /// assert!(sip.contains32(start)); /// assert!(sip.contains32(end)); /// assert!(!sip.contains32(end + 1)); /// ``` pub fn get_set_for_value(&self, value: T) -> CodePointInversionList<'static> { let value_ranges = self.get_ranges_for_value(value); CodePointInversionList::from_iter(value_ranges) } /// Returns the value used as an error value for this trie #[inline] pub fn error_value(&self) -> T { self.error_value } } #[cfg(feature = "databake")] impl<'trie, T: TrieValue + databake::Bake> databake::Bake for CodePointTrie<'trie, T> { fn bake(&self, env: &databake::CrateEnv) -> databake::TokenStream { let header = self.header.bake(env); let index = self.index.bake(env); let data = self.data.bake(env); let error_value = self.error_value.bake(env); databake::quote! { icu_collections::codepointtrie::CodePointTrie::from_parts(#header, #index, #data, #error_value) } } } impl<'trie, T: TrieValue + Into> CodePointTrie<'trie, T> { /// Returns the value that is associated with `code_point` for this [`CodePointTrie`] /// as a `u32`. /// /// # Examples /// /// ``` /// use icu::collections::codepointtrie::planes; /// let trie = planes::get_planes_trie(); /// /// let cp = '𑖎' as u32; /// assert_eq!(cp, 0x1158E); /// /// let plane_num: u8 = trie.get32(cp); /// assert_eq!(trie.get32_u32(cp), plane_num as u32); /// ``` // Note: This API method maintains consistency with the corresponding // original ICU APIs. pub fn get32_u32(&self, code_point: u32) -> u32 { self.get32(code_point).into() } } impl<'trie, T: TrieValue> Clone for CodePointTrie<'trie, T> where ::ULE: Clone, { fn clone(&self) -> Self { CodePointTrie { header: self.header, index: self.index.clone(), data: self.data.clone(), error_value: self.error_value, } } } /// Represents a range of consecutive code points sharing the same value in a /// code point map. The start and end of the interval is represented as a /// `RangeInclusive`, and the value is represented as `T`. #[derive(PartialEq, Eq, Debug, Clone)] pub struct CodePointMapRange { /// Range of code points from start to end (inclusive). pub range: RangeInclusive, /// Trie value associated with this range. pub value: T, } /// A custom [`Iterator`] type specifically for a code point trie that returns /// [`CodePointMapRange`]s. pub struct CodePointMapRangeIterator<'a, T: TrieValue> { cpt: &'a CodePointTrie<'a, T>, // Initialize `range` to Some(CodePointMapRange{ start: u32::MAX, end: u32::MAX, value: 0}). // When `range` is Some(...) and has a start value different from u32::MAX, then we have // returned at least one code point range due to a call to `next()`. // When `range` == `None`, it means that we have hit the end of iteration. It would occur // after a call to `next()` returns a None <=> we attempted to call `get_range()` // with a start code point that is > CODE_POINT_MAX. cpm_range: Option>, } impl<'a, T: TrieValue> Iterator for CodePointMapRangeIterator<'a, T> { type Item = CodePointMapRange; fn next(&mut self) -> Option { self.cpm_range = match &self.cpm_range { Some(cpmr) => { if *cpmr.range.start() == u32::MAX { self.cpt.get_range(0) } else { self.cpt.get_range(cpmr.range.end() + 1) } } None => None, }; // Note: Clone is cheap. We can't Copy because RangeInclusive does not impl Copy. self.cpm_range.clone() } } #[cfg(test)] mod tests { use super::*; use crate::codepointtrie::planes; use alloc::vec::Vec; #[test] #[cfg(feature = "serde")] fn test_serde_with_postcard_roundtrip() -> Result<(), postcard::Error> { let trie = crate::codepointtrie::planes::get_planes_trie(); let trie_serialized: Vec = postcard::to_allocvec(&trie).unwrap(); // Assert an expected (golden data) version of the serialized trie. const EXP_TRIE_SERIALIZED: &[u8] = &[ 128, 128, 64, 128, 2, 2, 0, 0, 1, 160, 18, 0, 0, 64, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 136, 2, 144, 2, 144, 2, 144, 2, 176, 2, 176, 2, 176, 2, 176, 2, 208, 2, 208, 2, 208, 2, 208, 2, 240, 2, 240, 2, 240, 2, 240, 2, 16, 3, 16, 3, 16, 3, 16, 3, 48, 3, 48, 3, 48, 3, 48, 3, 80, 3, 80, 3, 80, 3, 80, 3, 112, 3, 112, 3, 112, 3, 112, 3, 144, 3, 144, 3, 144, 3, 144, 3, 176, 3, 176, 3, 176, 3, 176, 3, 208, 3, 208, 3, 208, 3, 208, 3, 240, 3, 240, 3, 240, 3, 240, 3, 16, 4, 16, 4, 16, 4, 16, 4, 48, 4, 48, 4, 48, 4, 48, 4, 80, 4, 80, 4, 80, 4, 80, 4, 112, 4, 112, 4, 112, 4, 112, 4, 0, 0, 16, 0, 32, 0, 48, 0, 64, 0, 80, 0, 96, 0, 112, 0, 0, 0, 16, 0, 32, 0, 48, 0, 0, 0, 16, 0, 32, 0, 48, 0, 0, 0, 16, 0, 32, 0, 48, 0, 0, 0, 16, 0, 32, 0, 48, 0, 0, 0, 16, 0, 32, 0, 48, 0, 0, 0, 16, 0, 32, 0, 48, 0, 0, 0, 16, 0, 32, 0, 48, 0, 0, 0, 16, 0, 32, 0, 48, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 32, 1, 32, 1, 32, 1, 32, 1, 32, 1, 32, 1, 32, 1, 32, 1, 32, 1, 32, 1, 32, 1, 32, 1, 32, 1, 32, 1, 32, 1, 32, 1, 32, 1, 32, 1, 32, 1, 32, 1, 32, 1, 32, 1, 32, 1, 32, 1, 32, 1, 32, 1, 32, 1, 32, 1, 32, 1, 32, 1, 32, 1, 32, 1, 48, 1, 48, 1, 48, 1, 48, 1, 48, 1, 48, 1, 48, 1, 48, 1, 48, 1, 48, 1, 48, 1, 48, 1, 48, 1, 48, 1, 48, 1, 48, 1, 48, 1, 48, 1, 48, 1, 48, 1, 48, 1, 48, 1, 48, 1, 48, 1, 48, 1, 48, 1, 48, 1, 48, 1, 48, 1, 48, 1, 48, 1, 48, 1, 64, 1, 64, 1, 64, 1, 64, 1, 64, 1, 64, 1, 64, 1, 64, 1, 64, 1, 64, 1, 64, 1, 64, 1, 64, 1, 64, 1, 64, 1, 64, 1, 64, 1, 64, 1, 64, 1, 64, 1, 64, 1, 64, 1, 64, 1, 64, 1, 64, 1, 64, 1, 64, 1, 64, 1, 64, 1, 64, 1, 64, 1, 64, 1, 80, 1, 80, 1, 80, 1, 80, 1, 80, 1, 80, 1, 80, 1, 80, 1, 80, 1, 80, 1, 80, 1, 80, 1, 80, 1, 80, 1, 80, 1, 80, 1, 80, 1, 80, 1, 80, 1, 80, 1, 80, 1, 80, 1, 80, 1, 80, 1, 80, 1, 80, 1, 80, 1, 80, 1, 80, 1, 80, 1, 80, 1, 80, 1, 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 128, 0, 136, 0, 136, 0, 136, 0, 136, 0, 136, 0, 136, 0, 136, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 8, 1, 8, 1, 8, 1, 8, 1, 8, 1, 8, 1, 8, 1, 8, 1, 8, 1, 8, 1, 8, 1, 8, 1, 8, 1, 8, 1, 8, 1, 8, 1, 8, 1, 8, 1, 8, 1, 8, 1, 8, 1, 8, 1, 8, 1, 8, 1, 8, 1, 8, 1, 8, 1, 8, 1, 8, 1, 8, 1, 8, 1, 8, 1, 40, 1, 40, 1, 40, 1, 40, 1, 40, 1, 40, 1, 40, 1, 40, 1, 40, 1, 40, 1, 40, 1, 40, 1, 40, 1, 40, 1, 40, 1, 40, 1, 40, 1, 40, 1, 40, 1, 40, 1, 40, 1, 40, 1, 40, 1, 40, 1, 40, 1, 40, 1, 40, 1, 40, 1, 40, 1, 40, 1, 40, 1, 40, 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 8, 2, 8, 2, 8, 2, 8, 2, 8, 2, 8, 2, 8, 2, 8, 2, 8, 2, 8, 2, 8, 2, 8, 2, 8, 2, 8, 2, 8, 2, 8, 2, 8, 2, 8, 2, 8, 2, 8, 2, 8, 2, 8, 2, 8, 2, 8, 2, 8, 2, 8, 2, 8, 2, 8, 2, 8, 2, 8, 2, 8, 2, 8, 2, 40, 2, 40, 2, 40, 2, 40, 2, 40, 2, 40, 2, 40, 2, 40, 2, 40, 2, 40, 2, 40, 2, 40, 2, 40, 2, 40, 2, 40, 2, 40, 2, 40, 2, 40, 2, 40, 2, 40, 2, 40, 2, 40, 2, 40, 2, 40, 2, 40, 2, 40, 2, 40, 2, 40, 2, 40, 2, 40, 2, 40, 2, 40, 2, 72, 2, 72, 2, 72, 2, 72, 2, 72, 2, 72, 2, 72, 2, 72, 2, 72, 2, 72, 2, 72, 2, 72, 2, 72, 2, 72, 2, 72, 2, 72, 2, 72, 2, 72, 2, 72, 2, 72, 2, 72, 2, 72, 2, 72, 2, 72, 2, 72, 2, 72, 2, 72, 2, 72, 2, 72, 2, 72, 2, 72, 2, 72, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 244, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 0, ]; assert_eq!(trie_serialized, EXP_TRIE_SERIALIZED); let trie_deserialized = postcard::from_bytes::>(&trie_serialized)?; assert_eq!(&trie.index, &trie_deserialized.index); assert_eq!(&trie.data, &trie_deserialized.data); assert!(!trie_deserialized.index.is_owned()); assert!(!trie_deserialized.data.is_owned()); Ok(()) } #[test] fn test_get_range() { let planes_trie = planes::get_planes_trie(); let first_range: Option> = planes_trie.get_range(0x0); assert_eq!( first_range, Some(CodePointMapRange { range: RangeInclusive::new(0x0, 0xffff), value: 0 }) ); let second_range: Option> = planes_trie.get_range(0x1_0000); assert_eq!( second_range, Some(CodePointMapRange { range: RangeInclusive::new(0x10000, 0x1ffff), value: 1 }) ); let penultimate_range: Option> = planes_trie.get_range(0xf_0000); assert_eq!( penultimate_range, Some(CodePointMapRange { range: RangeInclusive::new(0xf_0000, 0xf_ffff), value: 15 }) ); let last_range: Option> = planes_trie.get_range(0x10_0000); assert_eq!( last_range, Some(CodePointMapRange { range: RangeInclusive::new(0x10_0000, 0x10_ffff), value: 16 }) ); } #[test] fn databake() { databake::test_bake!( CodePointTrie<'static, u32>, const: crate::codepointtrie::CodePointTrie::from_parts( crate::codepointtrie::CodePointTrieHeader { high_start: 1u32, shifted12_high_start: 2u16, index3_null_offset: 3u16, data_null_offset: 4u32, null_value: 5u32, trie_type: crate::codepointtrie::TrieType::Small, }, zerovec::ZeroVec::new(), zerovec::ZeroVec::new(), 0u32, ), icu_collections, [zerovec], ); } }