icu_collections/codepointtrie/cptrie.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
5use crate::codepointtrie::error::Error;
6use crate::codepointtrie::impl_const::*;
7
8#[cfg(feature = "alloc")]
9use crate::codepointinvlist::CodePointInversionList;
10use core::char::CharTryFromError;
11use core::convert::Infallible;
12use core::convert::TryFrom;
13use core::fmt::Display;
14#[cfg(feature = "alloc")]
15use core::iter::FromIterator;
16use core::num::TryFromIntError;
17use core::ops::RangeInclusive;
18use yoke::Yokeable;
19use zerofrom::ZeroFrom;
20use zerovec::ZeroSlice;
21use zerovec::ZeroVec;
22use zerovec::ule::AsULE;
23#[cfg(feature = "alloc")]
24use zerovec::ule::UleError;
25
26/// The type of trie represents whether the trie has an optimization that
27/// would make it smaller or faster.
28///
29/// Regarding performance, a trie being a small or fast type affects the number of array lookups
30/// needed for code points in the range `[0x1000, 0x10000)`. In this range, `Small` tries use 4 array lookups,
31/// while `Fast` tries use 2 array lookups.
32/// Code points before the interval (in `[0, 0x1000)`) will always use 2 array lookups.
33/// Code points after the interval (in `[0x10000, 0x10FFFF]`) will always use 4 array lookups.
34///
35/// Regarding size, `Fast` type tries are larger than `Small` type tries because the minimum size of
36/// the index array is larger. The minimum size is the "fast max" limit, which is the limit of the range
37/// of code points with 2 array lookups.
38///
39/// 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).
40///
41/// Also see [`UCPTrieType`](https://unicode-org.github.io/icu-docs/apidoc/dev/icu4c/ucptrie_8h.html) in ICU4C.
42#[derive(Clone, Copy, PartialEq, Debug, Eq)]
43#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
44#[cfg_attr(feature = "databake", derive(databake::Bake))]
45#[cfg_attr(feature = "databake", databake(path = icu_collections::codepointtrie))]
46#[allow(clippy::exhaustive_enums)] // based on a stable serialized form
47pub enum TrieType {
48 /// Represents the "fast" type code point tries for the
49 /// [`TrieType`] trait. The "fast max" limit is set to `0xffff`.
50 Fast = 0,
51 /// Represents the "small" type code point tries for the
52 /// [`TrieType`] trait. The "fast max" limit is set to `0x0fff`.
53 Small = 1,
54}
55
56// TrieValue trait
57
58// AsULE is AsUnalignedLittleEndian, i.e. "allowed in a zerovec"
59
60/// A trait representing the values stored in the data array of a [`CodePointTrie`].
61/// This trait is used as a type parameter in constructing a `CodePointTrie`.
62///
63/// This trait can be implemented on anything that can be represented as a u32s worth of data.
64pub trait TrieValue: Copy + Eq + PartialEq + AsULE + 'static {
65 /// Last-resort fallback value to return if we cannot read data from the trie.
66 ///
67 /// In most cases, the error value is read from the last element of the `data` array,
68 /// this value is used for empty codepointtrie arrays
69 /// Error type when converting from a u32 to this `TrieValue`.
70 type TryFromU32Error: Display;
71 /// A parsing function that is primarily motivated by deserialization contexts.
72 /// When the serialization type width is smaller than 32 bits, then it is expected
73 /// that the call site will widen the value to a `u32` first.
74 fn try_from_u32(i: u32) -> Result<Self, Self::TryFromU32Error>;
75
76 /// A method for converting back to a `u32` that can roundtrip through
77 /// [`Self::try_from_u32()`]. The default implementation of this trait
78 /// method panics in debug mode and returns 0 in release mode.
79 ///
80 /// This method is allowed to have GIGO behavior when fed a value that has
81 /// no corresponding `u32` (since such values cannot be stored in the trie)
82 fn to_u32(self) -> u32;
83}
84
85macro_rules! impl_primitive_trie_value {
86 ($primitive:ty, $error:ty) => {
87 impl TrieValue for $primitive {
88 type TryFromU32Error = $error;
89 fn try_from_u32(i: u32) -> Result<Self, Self::TryFromU32Error> {
90 Self::try_from(i)
91 }
92
93 #[allow(trivial_numeric_casts)]
94 fn to_u32(self) -> u32 {
95 // bitcast when the same size, zero-extend/sign-extend
96 // when not the same size
97 self as u32
98 }
99 }
100 };
101}
102
103impl_primitive_trie_value!(u8, TryFromIntError);
104impl_primitive_trie_value!(u16, TryFromIntError);
105impl_primitive_trie_value!(u32, Infallible);
106impl_primitive_trie_value!(i8, TryFromIntError);
107impl_primitive_trie_value!(i16, TryFromIntError);
108impl_primitive_trie_value!(i32, TryFromIntError);
109impl_primitive_trie_value!(char, CharTryFromError);
110
111/// Helper function used by [`get_range`]. Converts occurrences of trie's null
112/// value into the provided `null_value`.
113///
114/// Note: the ICU version of this helper function uses a `ValueFilter` function
115/// to apply a transform on a non-null value. But currently, this implementation
116/// stops short of that functionality, and instead leaves the non-null trie value
117/// untouched. This is equivalent to having a `ValueFilter` function that is the
118/// identity function.
119fn maybe_filter_value<T: TrieValue>(value: T, trie_null_value: T, null_value: T) -> T {
120 if value == trie_null_value {
121 null_value
122 } else {
123 value
124 }
125}
126
127/// This struct represents a de-serialized [`CodePointTrie`] that was exported from
128/// ICU binary data.
129///
130/// For more information:
131/// - [ICU Site design doc](https://unicode-org.github.io/icu/design/struct/utrie)
132/// - [ICU User Guide section on Properties lookup](https://unicode-org.github.io/icu/userguide/strings/properties.html#lookup)
133// serde impls in crate::serde
134#[derive(Debug, Eq, PartialEq, Yokeable, ZeroFrom)]
135pub struct CodePointTrie<'trie, T: TrieValue> {
136 /// # Safety Invariant
137 ///
138 /// The value of `header.trie_type` must not change after construction.
139 pub(crate) header: CodePointTrieHeader,
140 /// # Safety Invariant
141 ///
142 /// If `header.trie_type == TrieType::Fast`, `index.len()` must be greater
143 /// than `FAST_TYPE_FAST_INDEXING_MAX`. Otherwise, `index.len()`
144 /// must be greater than `SMALL_TYPE_FAST_INDEXING_MAX`. Furthermore,
145 /// this field must not change after construction. (Strictly: It must
146 /// not become shorter than the length requirement stated above and the
147 /// values within the prefix up to the length requirement must not change.)
148 pub(crate) index: ZeroVec<'trie, u16>,
149 /// # Safety Invariant
150 ///
151 /// If `header.trie_type == TrieType::Fast`, `data.len()` must be greater
152 /// than `FAST_TYPE_DATA_MASK` plus the largest value in
153 /// `index[0..FAST_TYPE_FAST_INDEXING_MAX + 1]`. Otherwise, `data.len()`
154 /// must be greater than `FAST_TYPE_DATA_MASK` plus the largest value in
155 /// `index[0..SMALL_TYPE_FAST_INDEXING_MAX + 1]`. Furthermore, this field
156 /// must not change after construction. (Strictly: The stated length
157 /// requirement must continue to hold.)
158 pub(crate) data: ZeroVec<'trie, T>,
159 // serde impl skips this field
160 #[zerofrom(clone)] // TrieValue is Copy, this allows us to avoid
161 // a T: ZeroFrom bound
162 pub(crate) error_value: T,
163 // serde impl skips this field
164 #[zerofrom(clone)] // TrieValue is Copy, this allows us to avoid
165 // a T: ZeroFrom bound
166 pub(crate) null_value: T,
167}
168
169/// This struct contains the fixed-length header fields of a [`CodePointTrie`].
170///
171/// # Safety Invariant
172///
173/// The `trie_type` field must not change after construction.
174///
175/// (In practice, all the fields here remain unchanged during the lifetime
176/// of the trie.)
177#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
178#[cfg_attr(feature = "databake", derive(databake::Bake))]
179#[cfg_attr(feature = "databake", databake(path = icu_collections::codepointtrie))]
180#[derive(Copy, Clone, Debug, Eq, PartialEq, Yokeable, ZeroFrom)]
181#[allow(clippy::exhaustive_structs)] // based on a stable serialized form
182pub struct CodePointTrieHeader {
183 /// The code point of the start of the last range of the trie. A
184 /// range is defined as a partition of the code point space such that the
185 /// value in this trie associated with all code points of the same range is
186 /// the same.
187 ///
188 /// For the property value data for many Unicode properties,
189 /// often times, `high_start` is `U+10000` or lower. In such cases, not
190 /// reserving space in the `index` array for duplicate values is a large
191 /// savings. The "highValue" associated with the `high_start` range is
192 /// stored at the second-to-last position of the `data` array.
193 /// (See `impl_const::HIGH_VALUE_NEG_DATA_OFFSET`.)
194 pub high_start: u32,
195 /// A version of the `high_start` value that is right-shifted 12 spaces,
196 /// but is rounded up to a multiple `0x1000` for easy testing from UTF-8
197 /// lead bytes.
198 pub shifted12_high_start: u16,
199 /// Offset for the null block in the "index-3" table of the `index` array.
200 /// Set to an impossibly high value (e.g., `0xffff`) if there is no
201 /// dedicated index-3 null block.
202 pub index3_null_offset: u16,
203 /// Internal data null block offset, not shifted.
204 /// Set to an impossibly high value (e.g., `0xfffff`) if there is no
205 /// dedicated data null block.
206 pub data_null_offset: u32,
207 /// The value stored in the trie that represents a null value being
208 /// associated to a code point.
209 pub null_value: u32,
210 /// The enum value representing the type of trie, where trie type is as it
211 /// is defined in ICU (ex: Fast, Small).
212 ///
213 /// # Safety Invariant
214 ///
215 /// Must not change after construction.
216 pub trie_type: TrieType,
217}
218
219impl TryFrom<u8> for TrieType {
220 type Error = Error;
221
222 fn try_from(trie_type_int: u8) -> Result<TrieType, Error> {
223 match trie_type_int {
224 0 => Ok(TrieType::Fast),
225 1 => Ok(TrieType::Small),
226 _ => Err(Error::FromDeserialized {
227 reason: "Cannot parse value for trie_type",
228 }),
229 }
230 }
231}
232
233// Helper macro that turns arithmetic into wrapping-in-release, checked-in-debug arithmetic
234//
235// This is rustc's default behavior anyway, however some projects like Android deliberately
236// enable overflow checks. CodePointTrie::get() is intended to be used in Android bionic which
237// cares about codesize and we don't want the pile of panicking infrastructure brought in by overflow
238// checks, so we force wrapping in release.
239// See #6052
240macro_rules! w(
241 // Note: these matchers are not perfect since you cannot have an operator after an expr matcher
242 // Use variables if you need complex first operands.
243 ($a:tt + $b:expr) => {
244 {
245 #[allow(unused_parens)]
246 let a = $a;
247 let b = $b;
248 debug_assert!(a.checked_add(b).is_some());
249 $a.wrapping_add($b)
250 }
251 };
252 ($a:tt - $b:expr) => {
253
254 {
255 #[allow(unused_parens)]
256 let a = $a;
257 let b = $b;
258 debug_assert!(a.checked_sub(b).is_some());
259 $a.wrapping_sub($b)
260 }
261 };
262 ($a:tt * $b:expr) => {
263 {
264 #[allow(unused_parens)]
265 let a = $a;
266 let b = $b;
267 debug_assert!(a.checked_mul(b).is_some());
268 $a.wrapping_mul($b)
269 }
270 };
271);
272
273impl<'trie, T: TrieValue> CodePointTrie<'trie, T> {
274 #[doc(hidden)] // databake internal
275 /// # Safety
276 ///
277 /// `header.trie_type`, `index`, and `data` must
278 /// satisfy the invariants for the fields of the
279 /// same names on `CodePointTrie`.
280 pub const unsafe fn from_parts_unstable_unchecked_v1(
281 header: CodePointTrieHeader,
282 index: ZeroVec<'trie, u16>,
283 data: ZeroVec<'trie, T>,
284 error_value: T,
285 null_value: T,
286 ) -> Self {
287 // Field invariants upheld: The caller is responsible.
288 // In practice, this means that datagen in the databake
289 // mode upholds these invariants when constructing the
290 // `CodePointTrie` that is then baked.
291 Self {
292 header,
293 index,
294 data,
295 error_value,
296 null_value,
297 }
298 }
299
300 /// Returns a new [`CodePointTrie`] backed by borrowed data for the `index`
301 /// array and `data` array, whose data values have width `W`.
302 pub fn try_new(
303 header: CodePointTrieHeader,
304 index: ZeroVec<'trie, u16>,
305 data: ZeroVec<'trie, T>,
306 ) -> Result<CodePointTrie<'trie, T>, Error> {
307 let (error_value, null_value) = Self::validate_fields(&header, &index, &data)?;
308 // Field invariants upheld: Checked by `validate_fields` above.
309 let trie: CodePointTrie<'trie, T> = CodePointTrie {
310 header,
311 index,
312 data,
313 error_value,
314 null_value,
315 };
316 Ok(trie)
317 }
318
319 /// Checks the invariant on the fields that fast-path access relies on for
320 /// safety in order to omit slice bound checks and upon success returns the
321 /// `error_value` and `null_value` for the trie.
322 ///
323 /// # Safety Usable Invariant
324 ///
325 /// Iff this function returns `Ok(T)`, the arguments satisfy the invariants
326 /// for corresponding fields of `CodePointTrie`. (Other than proving that
327 /// nothing else changes the fields subsequently.)
328 pub(crate) fn validate_fields(
329 header: &CodePointTrieHeader,
330 index: &ZeroSlice<u16>,
331 data: &ZeroSlice<T>,
332 ) -> Result<(T, T), Error> {
333 let error_value = data.last().ok_or(Error::EmptyDataVector)?;
334 let null_value = T::try_from_u32(header.null_value).map_err(|_| Error::InvalidNullValue)?;
335
336 // `CodePointTrie` lookup has two stages: fast and small (the trie types
337 // are also fast and small; they affect where the boundary between fast
338 // and small lookups is).
339 //
340 // The length requirements for `index` and `data` are checked here only
341 // for the fast lookup case so that the fast lookup can omit bound checks
342 // at the time of access. In the small lookup case, bounds are checked at
343 // the time of access.
344 //
345 // The fast lookup happens on the prefixes of `index` and `data` with
346 // more items for the small lookup case afterwards. The check here
347 // only looks at the prefixes relevant to the fast case.
348 //
349 // In the fast lookup case, the bits of the of the code point are
350 // partitioned into a bit prefix and a bit suffix. First, a value
351 // is read from `index` by indexing into it using the bit prefix.
352 // Then `data` is accessed by the value just read from `index` plus
353 // the bit suffix.
354 //
355 // Therefore, the length of `index` needs to accommodate access
356 // by the maximum possible bit prefix, and the length of `data`
357 // needs to accommodate access by the largest value stored in the part
358 // of `data` reachable by the bit prefix plus the maximum possible bit
359 // suffix.
360 //
361 // The maximum possible bit prefix depends on the trie type.
362
363 // The maximum code point that can be used for fast-path access:
364 let fast_max = match header.trie_type {
365 TrieType::Fast => FAST_TYPE_FAST_INDEXING_MAX,
366 TrieType::Small => SMALL_TYPE_FAST_INDEXING_MAX,
367 };
368 // Keep only the prefix bits:
369 let max_bit_prefix = fast_max >> FAST_TYPE_SHIFT;
370 // Attempt slice the part of `index` that the fast path can index into.
371 // Since `max_bit_prefix` is the largest possible value used for
372 // indexing (inclusive bound), we need to add one to get the exclusive
373 // bound, which is what `get_subslice` wants.
374 let fast_index = index
375 .get_subslice(0..(max_bit_prefix as usize) + 1)
376 .ok_or(Error::IndexTooShortForFastAccess)?;
377 // Invariant upheld for `index`: If we got this far, the length of `index`
378 // satisfies its length invariant on the assumption that `header.trie_type`
379 // will not change subsequently.
380
381 // Now find the largest offset in the part of `index` reachable by the
382 // bit prefix. `max` can never actually return `None`, since we already
383 // know the slice isn't empty. Hence, reusing the error kind instead of
384 // minting a new one for this check.
385 let max_offset = fast_index
386 .iter()
387 .max()
388 .ok_or(Error::IndexTooShortForFastAccess)?;
389 // `FAST_TYPE_DATA_MASK` is the maximum possible bit suffix, since the
390 // maximum is when all the bits in the suffix are set, and the mask
391 // has that many bits set.
392 if (max_offset) as usize + (FAST_TYPE_DATA_MASK as usize) >= data.len() {
393 return Err(Error::DataTooShortForFastAccess);
394 }
395
396 // Invariant upheld for `data`: If we got this far, the length of `data`
397 // satisfies `data`'s length invariant on the assumption that the contents
398 // of `fast_index` subslice of `index` and `header.trie_type` will not
399 // change subsequently.
400
401 Ok((error_value, null_value))
402 }
403
404 /// Turns this trie into a version whose trie type is encoded in the Rust type.
405 #[inline]
406 pub fn to_typed(self) -> Typed<FastCodePointTrie<'trie, T>, SmallCodePointTrie<'trie, T>> {
407 match self.header.trie_type {
408 TrieType::Fast => Typed::Fast(FastCodePointTrie { inner: self }),
409 TrieType::Small => Typed::Small(SmallCodePointTrie { inner: self }),
410 }
411 }
412
413 /// Obtains a reference to this trie as a Rust type that encodes the trie type in the Rust type.
414 #[inline]
415 pub fn as_typed_ref(
416 &self,
417 ) -> Typed<&FastCodePointTrie<'trie, T>, &SmallCodePointTrie<'trie, T>> {
418 // SAFETY: `FastCodePointTrie` and `SmallCodePointTrie` are `repr(transparent)`
419 // with `CodePointTrie`, so transmuting between the references is OK when the
420 // actual trie type agrees with the semantics of the typed wrapper.
421 match self.header.trie_type {
422 TrieType::Fast => Typed::Fast(unsafe {
423 &*(self as *const CodePointTrie<'trie, T> as *const FastCodePointTrie<'trie, T>)
424 }),
425 TrieType::Small => Typed::Small(unsafe {
426 &*(self as *const CodePointTrie<'trie, T> as *const SmallCodePointTrie<'trie, T>)
427 }),
428 }
429 }
430
431 /// Returns the position in the data array containing the trie's stored
432 /// error value.
433 #[inline(always)] // `always` was based on previous normalizer benchmarking
434 fn trie_error_val_index(&self) -> u32 {
435 // We use wrapping_sub here to avoid panicky overflow checks.
436 // len should always be > 1, but if it isn't this will just cause GIGO behavior of producing
437 // None on `.get()`
438 debug_assert!(self.data.len() as u32 >= ERROR_VALUE_NEG_DATA_OFFSET);
439 w!((self.data.len() as u32) - ERROR_VALUE_NEG_DATA_OFFSET)
440 }
441
442 fn internal_small_index(&self, code_point: u32) -> u32 {
443 // We use wrapping arithmetic here to avoid overflow checks making their way into binaries
444 // with overflow checks enabled. Ultimately this code ends up as a checked index, so any
445 // bugs here will cause GIGO
446 let mut index1_pos: u32 = code_point >> SHIFT_1;
447 if self.header.trie_type == TrieType::Fast {
448 debug_assert!(
449 FAST_TYPE_FAST_INDEXING_MAX < code_point && code_point < self.header.high_start
450 );
451 index1_pos = w!(index1_pos + BMP_INDEX_LENGTH - OMITTED_BMP_INDEX_1_LENGTH);
452 } else {
453 assert!(code_point < self.header.high_start && self.header.high_start > SMALL_LIMIT);
454 index1_pos = w!(index1_pos + SMALL_INDEX_LENGTH);
455 }
456 let index1_val = if let Some(index1_val) = self.index.get(index1_pos as usize) {
457 index1_val
458 } else {
459 return self.trie_error_val_index();
460 };
461 let index3_block_idx: u32 =
462 w!((index1_val as u32) + (code_point >> SHIFT_2) & INDEX_2_MASK);
463 let mut index3_block: u32 =
464 if let Some(index3_block) = self.index.get(index3_block_idx as usize) {
465 index3_block as u32
466 } else {
467 return self.trie_error_val_index();
468 };
469 let mut index3_pos: u32 = (code_point >> SHIFT_3) & INDEX_3_MASK;
470 let mut data_block: u32;
471 if index3_block & 0x8000 == 0 {
472 // 16-bit indexes
473 data_block =
474 if let Some(data_block) = self.index.get(w!(index3_block + index3_pos) as usize) {
475 data_block as u32
476 } else {
477 return self.trie_error_val_index();
478 };
479 } else {
480 // 18-bit indexes stored in groups of 9 entries per 8 indexes.
481 index3_block = w!((index3_block & 0x7fff) + w!((index3_pos & !7) + index3_pos >> 3));
482 index3_pos &= 7;
483 data_block = if let Some(data_block) = self.index.get(index3_block as usize) {
484 data_block as u32
485 } else {
486 return self.trie_error_val_index();
487 };
488 data_block = (data_block << w!(2u32 + w!(2u32 * index3_pos))) & 0x30000;
489 index3_block += 1;
490 data_block =
491 if let Some(index3_val) = self.index.get(w!(index3_block + index3_pos) as usize) {
492 data_block | (index3_val as u32)
493 } else {
494 return self.trie_error_val_index();
495 };
496 }
497 // Returns data_pos == data_block (offset) +
498 // portion of code_point bit field for last (4th) lookup
499 w!(data_block + code_point & SMALL_DATA_MASK)
500 }
501
502 /// Returns the position in the `data` array for the given code point,
503 /// where this code point is at or above the fast limit associated for the
504 /// `trie_type`. We will refer to that limit as "`fastMax`" here.
505 ///
506 /// A lookup of the value in the code point trie for a code point in the
507 /// code point space range [`fastMax`, `high_start`) will be a 4-step
508 /// lookup: 3 lookups in the `index` array and one lookup in the `data`
509 /// array. Lookups for code points in the range [`high_start`,
510 /// `CODE_POINT_MAX`] are short-circuited to be a single lookup, see
511 /// [`CodePointTrieHeader::high_start`].
512 fn small_index(&self, code_point: u32) -> u32 {
513 if code_point >= self.header.high_start {
514 w!((self.data.len() as u32) - HIGH_VALUE_NEG_DATA_OFFSET)
515 } else {
516 self.internal_small_index(code_point) // helper fn
517 }
518 }
519
520 /// Returns the position in the `data` array for the given code point,
521 /// where this code point is below the fast limit associated for the
522 /// `trie type`. We will refer to that limit as "`fastMax`" here.
523 ///
524 /// A lookup of the value in the code point trie for a code point in the
525 /// code point space range [0, `fastMax`) will be a 2-step lookup: 1
526 /// lookup in the `index` array and one lookup in the `data` array. By
527 /// design, for trie type `T`, there is an element allocated in the `index`
528 /// array for each block of code points in [0, `fastMax`), which in
529 /// turn guarantees that those code points are represented and only need 1
530 /// lookup.
531 fn fast_index(&self, code_point: u32) -> u32 {
532 let index_array_pos: u32 = code_point >> FAST_TYPE_SHIFT;
533 let index_array_val: u16 =
534 if let Some(index_array_val) = self.index.get(index_array_pos as usize) {
535 index_array_val
536 } else {
537 return self.trie_error_val_index();
538 };
539 let masked_cp = code_point & FAST_TYPE_DATA_MASK;
540 let index_array_val = index_array_val as u32;
541 let fast_index_val: u32 = w!(index_array_val + masked_cp);
542 fast_index_val
543 }
544
545 /// Returns the value that is associated with `code_point` in this [`CodePointTrie`]
546 /// if `code_point` uses fast-path lookup or `None` if `code_point`
547 /// should use small-path lookup or is above the supported range.
548 #[inline(always)] // "always" to make the `Option` collapse away
549 fn get32_by_fast_index(&self, code_point: u32) -> Option<T> {
550 let fast_max = match self.header.trie_type {
551 TrieType::Fast => FAST_TYPE_FAST_INDEXING_MAX,
552 TrieType::Small => SMALL_TYPE_FAST_INDEXING_MAX,
553 };
554 if code_point <= fast_max {
555 // SAFETY: We just checked the invariant of
556 // `get32_assuming_fast_index`,
557 // which is
558 // "If `self.header.trie_type == TrieType::Small`, `code_point` must be at most
559 // `SMALL_TYPE_FAST_INDEXING_MAX`. If `self.header.trie_type ==
560 // TrieType::Fast`, `code_point` must be at most `FAST_TYPE_FAST_INDEXING_MAX`."
561 Some(unsafe { self.get32_assuming_fast_index(code_point) })
562 } else {
563 // The caller needs to call `get32_by_small_index` or determine
564 // that the argument is above the permitted range.
565 None
566 }
567 }
568
569 /// Performs the actual fast-mode lookup
570 ///
571 /// # Safety
572 ///
573 /// If `self.header.trie_type == TrieType::Small`, `code_point` must be at most
574 /// `SMALL_TYPE_FAST_INDEXING_MAX`. If `self.header.trie_type ==
575 /// TrieType::Fast`, `code_point` must be at most `FAST_TYPE_FAST_INDEXING_MAX`.
576 #[inline(always)]
577 unsafe fn get32_assuming_fast_index(&self, code_point: u32) -> T {
578 // Check the safety invariant of this method.
579 debug_assert!(
580 code_point
581 <= match self.header.trie_type {
582 TrieType::Fast => FAST_TYPE_FAST_INDEXING_MAX,
583 TrieType::Small => SMALL_TYPE_FAST_INDEXING_MAX,
584 }
585 );
586
587 let bit_prefix = (code_point as usize) >> FAST_TYPE_SHIFT;
588 debug_assert!(bit_prefix < self.index.len());
589 // SAFETY: Relying on the length invariant of `self.index` having
590 // been checked and on the unchangedness invariant of `self.index`
591 // and `self.header.trie_type` after construction.
592 let base_offset_to_data: usize = usize::from(u16::from_unaligned(*unsafe {
593 self.index.as_ule_slice().get_unchecked(bit_prefix)
594 }));
595 let bit_suffix = (code_point & FAST_TYPE_DATA_MASK) as usize;
596 // SAFETY: Cannot overflow with supported (32-bit and 64-bit) `usize`
597 // sizes, since `base_offset_to_data` was extended from `u16` and
598 // `bit_suffix` is at most `FAST_TYPE_DATA_MASK`, which is well
599 // under what it takes to reach the 32-bit (or 64-bit) max with
600 // additon from the max of `u16`.
601 let offset_to_data = w!(base_offset_to_data + bit_suffix);
602 debug_assert!(offset_to_data < self.data.len());
603 // SAFETY: Relying on the length invariant of `self.data` having
604 // been checked and on the unchangedness invariant of `self.data`,
605 // `self.index`, and `self.header.trie_type` after construction.
606 T::from_unaligned(*unsafe { self.data.as_ule_slice().get_unchecked(offset_to_data) })
607 }
608
609 /// Coldness wrapper for `get32_by_small_index` to also allow
610 /// calls without the effects of `#[cold]`.
611 #[cold]
612 #[inline(always)]
613 fn get32_by_small_index_cold(&self, code_point: u32) -> T {
614 self.get32_by_small_index(code_point)
615 }
616
617 /// Returns the value that is associated with `code_point` in this [`CodePointTrie`]
618 /// assuming that the small index path should be used.
619 ///
620 /// # Intended Precondition
621 ///
622 /// `code_point` must be at most `CODE_POINT_MAX` AND greter than
623 /// `FAST_TYPE_FAST_INDEXING_MAX` if the trie type is fast or greater
624 /// than `SMALL_TYPE_FAST_INDEXING_MAX` if the trie type is small.
625 /// This is checked when debug assertions are enabled. If this
626 /// precondition is violated, the behavior of this method is
627 /// memory-safe, but the returned value may be bogus (not
628 /// necessarily the designated error value).
629 #[inline(never)]
630 fn get32_by_small_index(&self, code_point: u32) -> T {
631 debug_assert!(code_point <= CODE_POINT_MAX);
632 debug_assert!(
633 code_point
634 > match self.header.trie_type {
635 TrieType::Fast => FAST_TYPE_FAST_INDEXING_MAX,
636 TrieType::Small => SMALL_TYPE_FAST_INDEXING_MAX,
637 }
638 );
639 self.data
640 .get(self.small_index(code_point) as usize)
641 .unwrap_or(self.error_value)
642 }
643
644 /// Returns the value that is associated with `code_point` in this [`CodePointTrie`].
645 ///
646 /// # Examples
647 ///
648 /// ```
649 /// use icu::collections::codepointtrie::planes;
650 /// let trie = planes::get_planes_trie();
651 ///
652 /// assert_eq!(0, trie.get32(0x41)); // 'A' as u32
653 /// assert_eq!(0, trie.get32(0x13E0)); // 'Ꮰ' as u32
654 /// assert_eq!(1, trie.get32(0x10044)); // '𐁄' as u32
655 /// ```
656 #[inline(always)] // `always` based on normalizer benchmarking
657 pub fn get32(&self, code_point: u32) -> T {
658 if let Some(v) = self.get32_by_fast_index(code_point) {
659 v
660 } else if code_point <= CODE_POINT_MAX {
661 self.get32_by_small_index_cold(code_point)
662 } else {
663 self.error_value
664 }
665 }
666
667 /// Returns the value that is associated with `char` in this [`CodePointTrie`].
668 ///
669 /// # Examples
670 ///
671 /// ```
672 /// use icu::collections::codepointtrie::planes;
673 /// let trie = planes::get_planes_trie();
674 ///
675 /// assert_eq!(0, trie.get('A')); // 'A' as u32
676 /// assert_eq!(0, trie.get('Ꮰ')); // 'Ꮰ' as u32
677 /// assert_eq!(1, trie.get('𐁄')); // '𐁄' as u32
678 /// ```
679 #[inline(always)]
680 pub fn get(&self, c: char) -> T {
681 // LLVM's optimizations have been observed not to be 100%
682 // reliable around collapsing away unnecessary parts of
683 // `get32`, so not just calling `get32` here.
684 let code_point = u32::from(c);
685 if let Some(v) = self.get32_by_fast_index(code_point) {
686 v
687 } else {
688 self.get32_by_small_index_cold(code_point)
689 }
690 }
691
692 /// Returns the value that is associated with `bmp` in this [`CodePointTrie`].
693 #[inline(always)]
694 pub fn get16(&self, bmp: u16) -> T {
695 // LLVM's optimizations have been observed not to be 100%
696 // reliable around collapsing away unnecessary parts of
697 // `get32`, so not just calling `get32` here.
698 let code_point = u32::from(bmp);
699 if let Some(v) = self.get32_by_fast_index(code_point) {
700 v
701 } else {
702 self.get32_by_small_index_cold(code_point)
703 }
704 }
705
706 /// Lookup trie value by non-Basic Multilingual Plane Scalar Value.
707 ///
708 /// The return value may be bogus (not necessarily `error_value`) is the argument is actually in
709 /// the Basic Multilingual Plane or above the Unicode Scalar Value
710 /// range (panics instead with debug assertions enabled).
711 #[inline(always)]
712 pub fn get32_supplementary(&self, supplementary: u32) -> T {
713 debug_assert!(supplementary > 0xFFFF);
714 debug_assert!(supplementary <= CODE_POINT_MAX);
715 self.get32_by_small_index(supplementary)
716 }
717
718 /// Returns a reference to the ULE of the value that is associated with `code_point` in this [`CodePointTrie`].
719 ///
720 /// # Examples
721 ///
722 /// ```
723 /// use icu::collections::codepointtrie::planes;
724 /// let trie = planes::get_planes_trie();
725 ///
726 /// assert_eq!(Some(&0), trie.get32_ule(0x41)); // 'A' as u32
727 /// assert_eq!(Some(&0), trie.get32_ule(0x13E0)); // 'Ꮰ' as u32
728 /// assert_eq!(Some(&1), trie.get32_ule(0x10044)); // '𐁄' as u32
729 /// ```
730 #[inline(always)] // `always` was based on previous normalizer benchmarking
731 pub fn get32_ule(&self, code_point: u32) -> Option<&T::ULE> {
732 // All code points up to the fast max limit are represented
733 // individually in the `index` array to hold their `data` array position, and
734 // thus only need 2 lookups for a [CodePointTrie::get()](`crate::codepointtrie::CodePointTrie::get`).
735 // Code points above the "fast max" limit require 4 lookups.
736 let fast_max = match self.header.trie_type {
737 TrieType::Fast => FAST_TYPE_FAST_INDEXING_MAX,
738 TrieType::Small => SMALL_TYPE_FAST_INDEXING_MAX,
739 };
740 let data_pos: u32 = if code_point <= fast_max {
741 Self::fast_index(self, code_point)
742 } else if code_point <= CODE_POINT_MAX {
743 Self::small_index(self, code_point)
744 } else {
745 self.trie_error_val_index()
746 };
747 // Returns the trie value (or trie's error value).
748 self.data.as_ule_slice().get(data_pos as usize)
749 }
750
751 /// Converts the [`CodePointTrie`] into one that returns another type of the same size.
752 ///
753 /// Borrowed data remains borrowed, and owned data remains owned.
754 ///
755 /// If the old and new types are not the same size, use
756 /// [`CodePointTrie::try_alloc_map_value`].
757 ///
758 /// # Panics
759 ///
760 /// Panics if `T` and `P` are different sizes.
761 ///
762 /// More specifically, panics if [`ZeroVec::try_into_converted()`] panics when converting
763 /// `ZeroVec<T>` into `ZeroVec<P>`, which happens if `T::ULE` and `P::ULE` differ in size.
764 ///
765 /// ✨ *Enabled with the `alloc` Cargo feature.*
766 ///
767 /// # Examples
768 ///
769 /// ```no_run
770 /// use icu::collections::codepointtrie::CodePointTrie;
771 /// use icu::collections::codepointtrie::planes;
772 ///
773 /// let planes_trie_u8: CodePointTrie<u8> = planes::get_planes_trie();
774 /// let planes_trie_i8: CodePointTrie<i8> =
775 /// planes_trie_u8.try_into_converted().expect("infallible");
776 ///
777 /// assert_eq!(planes_trie_i8.get32(0x30000), 3);
778 /// ```
779 #[cfg(feature = "alloc")]
780 pub fn try_into_converted<P>(self) -> Result<CodePointTrie<'trie, P>, UleError>
781 where
782 P: TrieValue,
783 {
784 let converted_data = self.data.try_into_converted()?;
785 let error_ule = self.error_value.to_unaligned();
786 let error_slice = &[error_ule];
787 let error_vec = ZeroVec::<T>::new_borrowed(error_slice);
788 let error_converted = error_vec.try_into_converted::<P>()?;
789 let null_ule = self.null_value.to_unaligned();
790 let null_slice = &[null_ule];
791 let null_vec = ZeroVec::<T>::new_borrowed(null_slice);
792 let null_converted = null_vec.try_into_converted::<P>()?;
793 #[expect(clippy::expect_used)] // we know this cannot fail
794 Ok(CodePointTrie {
795 header: self.header,
796 index: self.index,
797 data: converted_data,
798 error_value: error_converted
799 .get(0)
800 .expect("vector known to have one element"),
801 null_value: null_converted
802 .get(0)
803 .expect("vector known to have one element"),
804 })
805 }
806
807 /// Maps the [`CodePointTrie`] into one that returns a different type.
808 ///
809 /// This function returns owned data.
810 ///
811 /// If the old and new types are the same size, use the more efficient
812 /// [`CodePointTrie::try_into_converted`].
813 ///
814 /// ✨ *Enabled with the `alloc` Cargo feature.*
815 ///
816 /// # Examples
817 ///
818 /// ```
819 /// use icu::collections::codepointtrie::CodePointTrie;
820 /// use icu::collections::codepointtrie::planes;
821 ///
822 /// let planes_trie_u8: CodePointTrie<u8> = planes::get_planes_trie();
823 /// let planes_trie_u16: CodePointTrie<u16> = planes_trie_u8
824 /// .try_alloc_map_value(TryFrom::try_from)
825 /// .expect("infallible");
826 ///
827 /// assert_eq!(planes_trie_u16.get32(0x30000), 3);
828 /// ```
829 #[cfg(feature = "alloc")]
830 pub fn try_alloc_map_value<P, E>(
831 &self,
832 mut f: impl FnMut(T) -> Result<P, E>,
833 ) -> Result<CodePointTrie<'trie, P>, E>
834 where
835 P: TrieValue,
836 {
837 let error_converted = f(self.error_value)?;
838 let null_converted = f(self.error_value)?;
839 let converted_data = self.data.iter().map(f).collect::<Result<ZeroVec<P>, E>>()?;
840 Ok(CodePointTrie {
841 header: self.header,
842 index: self.index.clone(),
843 data: converted_data,
844 error_value: error_converted,
845 null_value: null_converted,
846 })
847 }
848
849 /// Returns a [`CodePointMapRange`] struct which represents a range of code
850 /// points associated with the same trie value. The returned range will be
851 /// the longest stretch of consecutive code points starting at `start` that
852 /// share this value.
853 ///
854 /// This method is designed to use the internal details of
855 /// the structure of [`CodePointTrie`] to be optimally efficient. This will
856 /// outperform a naive approach that just uses [`CodePointTrie::get()`].
857 ///
858 /// This method provides lower-level functionality that can be used in the
859 /// implementation of other methods that are more convenient to the user.
860 /// To obtain an optimal partition of the code point space for
861 /// this trie resulting in the fewest number of ranges, see
862 /// [`CodePointTrie::iter_ranges()`].
863 ///
864 /// # Examples
865 ///
866 /// ```
867 /// use icu::collections::codepointtrie::planes;
868 ///
869 /// let trie = planes::get_planes_trie();
870 ///
871 /// const CODE_POINT_MAX: u32 = 0x10ffff;
872 /// let start = 0x1_0000;
873 /// let exp_end = 0x1_ffff;
874 ///
875 /// let start_val = trie.get32(start);
876 /// assert_eq!(trie.get32(exp_end), start_val);
877 /// assert_ne!(trie.get32(exp_end + 1), start_val);
878 ///
879 /// use icu::collections::codepointtrie::CodePointMapRange;
880 ///
881 /// let cpm_range: CodePointMapRange<u8> = trie.get_range(start).unwrap();
882 ///
883 /// assert_eq!(cpm_range.range.start(), &start);
884 /// assert_eq!(cpm_range.range.end(), &exp_end);
885 /// assert_eq!(cpm_range.value, start_val);
886 ///
887 /// // `start` can be any code point, whether or not it lies on the boundary
888 /// // of a maximally large range that still contains `start`
889 ///
890 /// let submaximal_1_start = start + 0x1234;
891 /// let submaximal_1 = trie.get_range(submaximal_1_start).unwrap();
892 /// assert_eq!(submaximal_1.range.start(), &0x1_1234);
893 /// assert_eq!(submaximal_1.range.end(), &0x1_ffff);
894 /// assert_eq!(submaximal_1.value, start_val);
895 ///
896 /// let submaximal_2_start = start + 0xffff;
897 /// let submaximal_2 = trie.get_range(submaximal_2_start).unwrap();
898 /// assert_eq!(submaximal_2.range.start(), &0x1_ffff);
899 /// assert_eq!(submaximal_2.range.end(), &0x1_ffff);
900 /// assert_eq!(submaximal_2.value, start_val);
901 /// ```
902 pub fn get_range(&self, start: u32) -> Option<CodePointMapRange<T>> {
903 // Exit early if the start code point is out of range, or if it is
904 // in the last range of code points in high_start..=CODE_POINT_MAX
905 // (start- and end-inclusive) that all share the same trie value.
906 if CODE_POINT_MAX < start {
907 return None;
908 }
909 if start >= self.header.high_start {
910 let di: usize = self.data.len() - (HIGH_VALUE_NEG_DATA_OFFSET as usize);
911 let value: T = self.data.get(di)?;
912 return Some(CodePointMapRange {
913 range: start..=CODE_POINT_MAX,
914 value,
915 });
916 }
917
918 let mut prev_i3_block: u32 = u32::MAX; // using u32::MAX (instead of -1 as an i32 in ICU)
919 let mut prev_block: u32 = u32::MAX; // using u32::MAX (instead of -1 as an i32 in ICU)
920 let mut c: u32 = start;
921 let mut trie_value: T = self.error_value();
922 let mut value: T = self.error_value();
923 let mut have_value: bool = false;
924
925 loop {
926 let i3_block: u32;
927 let mut i3: u32;
928 let i3_block_length: u32;
929 let data_block_length: u32;
930
931 // Initialize values before beginning the iteration in the subsequent
932 // `loop` block. In particular, use the "i3*" local variables
933 // (representing the `index` array position's offset + increment
934 // for a 3rd-level trie lookup) to help initialize the data block
935 // variable `block` in the loop for the `data` array.
936 //
937 // When a lookup code point is <= the trie's *_FAST_INDEXING_MAX that
938 // corresponds to its `trie_type`, the lookup only takes 2 steps
939 // (once into the `index`, once into the `data` array); otherwise,
940 // takes 4 steps (3 iterative lookups into the `index`, once more
941 // into the `data` array). So for convenience's sake, when we have the
942 // 2-stage lookup, reuse the "i3*" variable names for the first lookup.
943 if c <= 0xffff
944 && (self.header.trie_type == TrieType::Fast || c <= SMALL_TYPE_FAST_INDEXING_MAX)
945 {
946 i3_block = 0;
947 i3 = c >> FAST_TYPE_SHIFT;
948 i3_block_length = if self.header.trie_type == TrieType::Fast {
949 BMP_INDEX_LENGTH
950 } else {
951 SMALL_INDEX_LENGTH
952 };
953 data_block_length = FAST_TYPE_DATA_BLOCK_LENGTH;
954 } else {
955 // Use the multi-stage index.
956 let mut i1: u32 = c >> SHIFT_1;
957 if self.header.trie_type == TrieType::Fast {
958 debug_assert!(0xffff < c && c < self.header.high_start);
959 i1 = i1 + BMP_INDEX_LENGTH - OMITTED_BMP_INDEX_1_LENGTH;
960 } else {
961 debug_assert!(
962 c < self.header.high_start && self.header.high_start > SMALL_LIMIT
963 );
964 i1 += SMALL_INDEX_LENGTH;
965 }
966 let i2: u16 = self.index.get(i1 as usize)?;
967 let i3_block_idx: u32 = (i2 as u32) + ((c >> SHIFT_2) & INDEX_2_MASK);
968 i3_block = self.index.get(i3_block_idx as usize)? as u32;
969 if i3_block == prev_i3_block && (c - start) >= CP_PER_INDEX_2_ENTRY {
970 // The index-3 block is the same as the previous one, and filled with value.
971 debug_assert!((c & (CP_PER_INDEX_2_ENTRY - 1)) == 0);
972 c += CP_PER_INDEX_2_ENTRY;
973
974 if c >= self.header.high_start {
975 break;
976 } else {
977 continue;
978 }
979 }
980 prev_i3_block = i3_block;
981 if i3_block == self.header.index3_null_offset as u32 {
982 // This is the index-3 null block.
983 // All of the `data` array blocks pointed to by the values
984 // in this block of the `index` 3rd-stage subarray will
985 // contain this trie's null_value. So if we are in the middle
986 // of a range, end it and return early, otherwise start a new
987 // range of null values.
988 if have_value {
989 if self.null_value != value {
990 return Some(CodePointMapRange {
991 range: start..=(c - 1),
992 value,
993 });
994 }
995 } else {
996 trie_value = self.null_value;
997 value = self.null_value;
998 have_value = true;
999 }
1000 prev_block = self.header.data_null_offset;
1001 c = (c + CP_PER_INDEX_2_ENTRY) & !(CP_PER_INDEX_2_ENTRY - 1);
1002
1003 if c >= self.header.high_start {
1004 break;
1005 } else {
1006 continue;
1007 }
1008 }
1009 i3 = (c >> SHIFT_3) & INDEX_3_MASK;
1010 i3_block_length = INDEX_3_BLOCK_LENGTH;
1011 data_block_length = SMALL_DATA_BLOCK_LENGTH;
1012 }
1013
1014 // Enumerate data blocks for one index-3 block.
1015 loop {
1016 let mut block: u32;
1017 if (i3_block & 0x8000) == 0 {
1018 block = self.index.get((i3_block + i3) as usize)? as u32;
1019 } else {
1020 // 18-bit indexes stored in groups of 9 entries per 8 indexes.
1021 let mut group: u32 = (i3_block & 0x7fff) + (i3 & !7) + (i3 >> 3);
1022 let gi: u32 = i3 & 7;
1023 let gi_val: u32 = self.index.get(group as usize)?.into();
1024 block = (gi_val << (2 + (2 * gi))) & 0x30000;
1025 group += 1;
1026 let ggi_val: u32 = self.index.get((group + gi) as usize)? as u32;
1027 block |= ggi_val;
1028 }
1029
1030 // If our previous and current return values of the 3rd-stage `index`
1031 // lookup yield the same `data` block offset, and if we already know that
1032 // the entire `data` block / subarray starting at that offset stores
1033 // `value` and nothing else, then we can extend our range by the length
1034 // of a data block and continue.
1035 // Otherwise, we have to iterate over the values stored in the
1036 // new data block to see if they differ from `value`.
1037 if block == prev_block && (c - start) >= data_block_length {
1038 // The block is the same as the previous one, and filled with value.
1039 debug_assert!((c & (data_block_length - 1)) == 0);
1040 c += data_block_length;
1041 } else {
1042 let data_mask: u32 = data_block_length - 1;
1043 prev_block = block;
1044 if block == self.header.data_null_offset {
1045 // This is the data null block.
1046 // If we are in the middle of a range, end it and
1047 // return early, otherwise start a new range of null
1048 // values.
1049 if have_value {
1050 if self.null_value != value {
1051 return Some(CodePointMapRange {
1052 range: start..=(c - 1),
1053 value,
1054 });
1055 }
1056 } else {
1057 trie_value = self.null_value;
1058 value = self.null_value;
1059 have_value = true;
1060 }
1061 c = (c + data_block_length) & !data_mask;
1062 } else {
1063 let mut di: u32 = block + (c & data_mask);
1064 let mut trie_value_2: T = self.data.get(di as usize)?;
1065 if have_value {
1066 if trie_value_2 != trie_value {
1067 if maybe_filter_value(
1068 trie_value_2,
1069 self.null_value,
1070 self.null_value,
1071 ) != value
1072 {
1073 return Some(CodePointMapRange {
1074 range: start..=(c - 1),
1075 value,
1076 });
1077 }
1078 // `trie_value` stores the previous value that was retrieved
1079 // from the trie.
1080 // `value` stores the value associated for the range (return
1081 // value) that we are currently building, which is computed
1082 // as a transformation by applying maybe_filter_value()
1083 // to the trie value.
1084 // The current trie value `trie_value_2` within this data block
1085 // differs here from the previous value in `trie_value`.
1086 // But both map to `value` after applying `maybe_filter_value`.
1087 // It is not clear whether the previous or the current trie value
1088 // (or neither) is more likely to match potential subsequent trie
1089 // values that would extend the range by mapping to `value`.
1090 // On the assumption of locality -- often times consecutive
1091 // characters map to the same trie values -- remembering the new
1092 // one might make it faster to extend this range further
1093 // (by increasing the chance that the next `trie_value_2 !=
1094 // trie_value` test will be false).
1095 trie_value = trie_value_2; // may or may not help
1096 }
1097 } else {
1098 trie_value = trie_value_2;
1099 value =
1100 maybe_filter_value(trie_value_2, self.null_value, self.null_value);
1101 have_value = true;
1102 }
1103
1104 c += 1;
1105 while (c & data_mask) != 0 {
1106 di += 1;
1107 trie_value_2 = self.data.get(di as usize)?;
1108 if trie_value_2 != trie_value {
1109 if maybe_filter_value(
1110 trie_value_2,
1111 self.null_value,
1112 self.null_value,
1113 ) != value
1114 {
1115 return Some(CodePointMapRange {
1116 range: start..=(c - 1),
1117 value,
1118 });
1119 }
1120 // `trie_value` stores the previous value that was retrieved
1121 // from the trie.
1122 // `value` stores the value associated for the range (return
1123 // value) that we are currently building, which is computed
1124 // as a transformation by applying maybe_filter_value()
1125 // to the trie value.
1126 // The current trie value `trie_value_2` within this data block
1127 // differs here from the previous value in `trie_value`.
1128 // But both map to `value` after applying `maybe_filter_value`.
1129 // It is not clear whether the previous or the current trie value
1130 // (or neither) is more likely to match potential subsequent trie
1131 // values that would extend the range by mapping to `value`.
1132 // On the assumption of locality -- often times consecutive
1133 // characters map to the same trie values -- remembering the new
1134 // one might make it faster to extend this range further
1135 // (by increasing the chance that the next `trie_value_2 !=
1136 // trie_value` test will be false).
1137 trie_value = trie_value_2; // may or may not help
1138 }
1139
1140 c += 1;
1141 }
1142 }
1143 }
1144
1145 i3 += 1;
1146 if i3 >= i3_block_length {
1147 break;
1148 }
1149 }
1150
1151 if c >= self.header.high_start {
1152 break;
1153 }
1154 }
1155
1156 debug_assert!(have_value);
1157
1158 // Now that c >= high_start, compare `value` to `high_value` to see
1159 // if we can merge our current range with the high_value range
1160 // high_start..=CODE_POINT_MAX (start- and end-inclusive), otherwise
1161 // stop at high_start - 1.
1162 let di: u32 = self.data.len() as u32 - HIGH_VALUE_NEG_DATA_OFFSET;
1163 let high_value: T = self.data.get(di as usize)?;
1164 if maybe_filter_value(high_value, self.null_value, self.null_value) != value {
1165 c -= 1;
1166 } else {
1167 c = CODE_POINT_MAX;
1168 }
1169 Some(CodePointMapRange {
1170 range: start..=c,
1171 value,
1172 })
1173 }
1174
1175 /// Yields an [`Iterator`] returning ranges of consecutive code points that
1176 /// share the same value in the [`CodePointTrie`], as given by
1177 /// [`CodePointTrie::get_range()`].
1178 ///
1179 /// # Examples
1180 ///
1181 /// ```
1182 /// use core::ops::RangeInclusive;
1183 /// use icu::collections::codepointtrie::CodePointMapRange;
1184 /// use icu::collections::codepointtrie::planes;
1185 ///
1186 /// let planes_trie = planes::get_planes_trie();
1187 ///
1188 /// let mut ranges = planes_trie.iter_ranges();
1189 ///
1190 /// for plane in 0..=16 {
1191 /// let exp_start = plane * 0x1_0000;
1192 /// let exp_end = exp_start + 0xffff;
1193 /// assert_eq!(
1194 /// ranges.next(),
1195 /// Some(CodePointMapRange {
1196 /// range: exp_start..=exp_end,
1197 /// value: plane as u8
1198 /// })
1199 /// );
1200 /// }
1201 ///
1202 /// // Hitting the end of the iterator returns `None`, as will subsequent
1203 /// // calls to .next().
1204 /// assert_eq!(ranges.next(), None);
1205 /// assert_eq!(ranges.next(), None);
1206 /// ```
1207 pub fn iter_ranges(&self) -> CodePointMapRangeIterator<'_, T> {
1208 let init_range = Some(CodePointMapRange {
1209 range: u32::MAX..=u32::MAX,
1210 value: self.error_value(),
1211 });
1212 CodePointMapRangeIterator::<T> {
1213 cpt: self,
1214 cpm_range: init_range,
1215 }
1216 }
1217
1218 /// Yields an [`Iterator`] returning the ranges of the code points whose values
1219 /// match `value` in the [`CodePointTrie`].
1220 ///
1221 /// # Examples
1222 ///
1223 /// ```
1224 /// use icu::collections::codepointtrie::planes;
1225 ///
1226 /// let trie = planes::get_planes_trie();
1227 ///
1228 /// let plane_val = 2;
1229 /// let mut sip_range_iter = trie.iter_ranges_for_value(plane_val as u8);
1230 ///
1231 /// let start = plane_val * 0x1_0000;
1232 /// let end = start + 0xffff;
1233 ///
1234 /// let sip_range = sip_range_iter.next()
1235 /// .expect("Plane 2 (SIP) should exist in planes data");
1236 /// assert_eq!(start..=end, sip_range);
1237 ///
1238 /// assert!(sip_range_iter.next().is_none());
1239 pub fn iter_ranges_for_value(
1240 &self,
1241 value: T,
1242 ) -> impl Iterator<Item = RangeInclusive<u32>> + '_ {
1243 self.iter_ranges()
1244 .filter(move |cpm_range| cpm_range.value == value)
1245 .map(|cpm_range| cpm_range.range)
1246 }
1247
1248 /// Yields an [`Iterator`] returning the ranges of the code points after passing
1249 /// the value through a mapping function.
1250 ///
1251 /// This is preferable to calling `.get_ranges().map()` since it will coalesce
1252 /// adjacent ranges into one.
1253 ///
1254 /// # Examples
1255 ///
1256 /// ```
1257 /// use icu::collections::codepointtrie::planes;
1258 ///
1259 /// let trie = planes::get_planes_trie();
1260 ///
1261 /// let plane_val = 2;
1262 /// let mut sip_range_iter = trie.iter_ranges_mapped(|value| value != plane_val as u8).filter(|range| range.value);
1263 ///
1264 /// let end = plane_val * 0x1_0000 - 1;
1265 ///
1266 /// let sip_range = sip_range_iter.next()
1267 /// .expect("Complemented planes data should have at least one entry");
1268 /// assert_eq!(0..=end, sip_range.range);
1269 pub fn iter_ranges_mapped<'a, U: Eq + 'a>(
1270 &'a self,
1271 mut map: impl FnMut(T) -> U + Copy + 'a,
1272 ) -> impl Iterator<Item = CodePointMapRange<U>> + 'a {
1273 crate::iterator_utils::RangeListIteratorCoalescer::new(self.iter_ranges().map(
1274 move |range| CodePointMapRange {
1275 range: range.range,
1276 value: map(range.value),
1277 },
1278 ))
1279 }
1280
1281 /// Returns a [`CodePointInversionList`] for the code points that have the given
1282 /// [`TrieValue`] in the trie.
1283 ///
1284 /// ✨ *Enabled with the `alloc` Cargo feature.*
1285 ///
1286 /// # Examples
1287 ///
1288 /// ```
1289 /// use icu::collections::codepointtrie::planes;
1290 ///
1291 /// let trie = planes::get_planes_trie();
1292 ///
1293 /// let plane_val = 2;
1294 /// let sip = trie.get_set_for_value(plane_val as u8);
1295 ///
1296 /// let start = plane_val * 0x1_0000;
1297 /// let end = start + 0xffff;
1298 ///
1299 /// assert!(!sip.contains32(start - 1));
1300 /// assert!(sip.contains32(start));
1301 /// assert!(sip.contains32(end));
1302 /// assert!(!sip.contains32(end + 1));
1303 /// ```
1304 #[cfg(feature = "alloc")]
1305 pub fn get_set_for_value(&self, value: T) -> CodePointInversionList<'static> {
1306 let value_ranges = self.iter_ranges_for_value(value);
1307 CodePointInversionList::from_iter(value_ranges)
1308 }
1309
1310 /// Returns the value used as an error value for this trie
1311 #[inline]
1312 pub fn error_value(&self) -> T {
1313 self.error_value
1314 }
1315
1316 /// Returns the value used as a null value for this trie
1317 #[inline]
1318 pub fn null_value(&self) -> T {
1319 self.null_value
1320 }
1321}
1322
1323#[cfg(feature = "databake")]
1324impl<T: TrieValue + databake::Bake> databake::Bake for CodePointTrie<'_, T> {
1325 fn bake(&self, env: &databake::CrateEnv) -> databake::TokenStream {
1326 let header = self.header.bake(env);
1327 let index = self.index.bake(env);
1328 let data = self.data.bake(env);
1329 let error_value = self.error_value.bake(env);
1330 let null_value = self.null_value.bake(env);
1331 databake::quote! { unsafe {
1332 #[allow(unused_unsafe)]
1333 icu_collections::codepointtrie::CodePointTrie::from_parts_unstable_unchecked_v1(#header, #index, #data, #error_value, #null_value)
1334 }}
1335 }
1336}
1337
1338#[cfg(feature = "databake")]
1339impl<T: TrieValue + databake::Bake> databake::BakeSize for CodePointTrie<'_, T> {
1340 fn borrows_size(&self) -> usize {
1341 self.header.borrows_size() + self.index.borrows_size() + self.data.borrows_size()
1342 }
1343}
1344
1345impl<T: TrieValue + Into<u32>> CodePointTrie<'_, T> {
1346 /// Returns the value that is associated with `code_point` for this [`CodePointTrie`]
1347 /// as a `u32`.
1348 ///
1349 /// # Examples
1350 ///
1351 /// ```
1352 /// use icu::collections::codepointtrie::planes;
1353 /// let trie = planes::get_planes_trie();
1354 ///
1355 /// let cp = '𑖎' as u32;
1356 /// assert_eq!(cp, 0x1158E);
1357 ///
1358 /// let plane_num: u8 = trie.get32(cp);
1359 /// assert_eq!(trie.get32_u32(cp), plane_num as u32);
1360 /// ```
1361 // Note: This API method maintains consistency with the corresponding
1362 // original ICU APIs.
1363 pub fn get32_u32(&self, code_point: u32) -> u32 {
1364 self.get32(code_point).into()
1365 }
1366}
1367
1368impl<T: TrieValue> Clone for CodePointTrie<'_, T>
1369where
1370 <T as AsULE>::ULE: Clone,
1371{
1372 fn clone(&self) -> Self {
1373 CodePointTrie {
1374 header: self.header,
1375 index: self.index.clone(),
1376 data: self.data.clone(),
1377 error_value: self.error_value,
1378 null_value: self.null_value,
1379 }
1380 }
1381}
1382
1383/// Represents a range of consecutive code points sharing the same value in a
1384/// code point map.
1385///
1386/// The start and end of the interval is represented as a
1387/// `RangeInclusive<u32>`, and the value is represented as `T`.
1388#[derive(PartialEq, Eq, Debug, Clone)]
1389#[allow(clippy::exhaustive_structs)] // based on a stable serialized form
1390pub struct CodePointMapRange<T> {
1391 /// Range of code points from start to end (inclusive).
1392 pub range: RangeInclusive<u32>,
1393 /// Trie value associated with this range.
1394 pub value: T,
1395}
1396
1397/// A custom [`Iterator`] type specifically for a code point trie that returns
1398/// [`CodePointMapRange`]s.
1399#[derive(Debug)]
1400pub struct CodePointMapRangeIterator<'a, T: TrieValue> {
1401 cpt: &'a CodePointTrie<'a, T>,
1402 // Initialize `range` to Some(CodePointMapRange{ start: u32::MAX, end: u32::MAX, value: 0}).
1403 // When `range` is Some(...) and has a start value different from u32::MAX, then we have
1404 // returned at least one code point range due to a call to `next()`.
1405 // When `range` == `None`, it means that we have hit the end of iteration. It would occur
1406 // after a call to `next()` returns a None <=> we attempted to call `get_range()`
1407 // with a start code point that is > CODE_POINT_MAX.
1408 cpm_range: Option<CodePointMapRange<T>>,
1409}
1410
1411impl<T: TrieValue> Iterator for CodePointMapRangeIterator<'_, T> {
1412 type Item = CodePointMapRange<T>;
1413
1414 fn next(&mut self) -> Option<Self::Item> {
1415 self.cpm_range = match &self.cpm_range {
1416 Some(cpmr) => {
1417 if *cpmr.range.start() == u32::MAX {
1418 self.cpt.get_range(0)
1419 } else {
1420 self.cpt.get_range(cpmr.range.end() + 1)
1421 }
1422 }
1423 None => None,
1424 };
1425 // Note: Clone is cheap. We can't Copy because RangeInclusive does not impl Copy.
1426 self.cpm_range.clone()
1427 }
1428}
1429
1430/// For sealing `TypedCodePointTrie`
1431///
1432/// # Safety Usable Invariant
1433///
1434/// All implementations of `TypedCodePointTrie` are reviewable in this module.
1435trait Seal {}
1436
1437/// Trait for writing trait bounds for monomorphizing over either
1438/// `FastCodePointTrie` or `SmallCodePointTrie`.
1439#[allow(private_bounds)] // Permit sealing
1440pub trait TypedCodePointTrie<'trie, T: TrieValue>: Seal {
1441 /// The `TrieType` associated with this `TypedCodePointTrie`
1442 ///
1443 /// # Safety Usable Invariant
1444 ///
1445 /// This constant matches `self.as_untyped_ref().header.trie_type`.
1446 const TRIE_TYPE: TrieType;
1447
1448 /// Lookup trie value as `u32` by Unicode Scalar Value without branching on trie type.
1449 #[inline(always)]
1450 fn get32_u32(&self, code_point: u32) -> u32 {
1451 self.get32(code_point).to_u32()
1452 }
1453
1454 /// Lookup trie value by Basic Multilingual Plane Code Point without branching on trie type.
1455 #[inline(always)]
1456 fn get16(&self, bmp: u16) -> T {
1457 // LLVM's optimizations have been observed not to be 100%
1458 // reliable around collapsing away unnecessary parts of
1459 // `get32`, so not just calling `get32` here.
1460 let code_point = u32::from(bmp);
1461 if let Some(v) = self.get32_by_fast_index(code_point) {
1462 v
1463 } else {
1464 self.as_untyped_ref().get32_by_small_index_cold(code_point)
1465 }
1466 }
1467
1468 /// Lookup trie value by non-Basic Multilingual Plane Scalar Value without branching on trie type.
1469 #[inline(always)]
1470 fn get32_supplementary(&self, supplementary: u32) -> T {
1471 self.as_untyped_ref().get32_supplementary(supplementary)
1472 }
1473
1474 /// Lookup trie value by Unicode Scalar Value without branching on trie type.
1475 #[inline(always)]
1476 fn get(&self, c: char) -> T {
1477 // LLVM's optimizations have been observed not to be 100%
1478 // reliable around collapsing away unnecessary parts of
1479 // `get32`, so not just calling `get32` here.
1480 let code_point = u32::from(c);
1481 if let Some(v) = self.get32_by_fast_index(code_point) {
1482 v
1483 } else {
1484 self.as_untyped_ref().get32_by_small_index_cold(code_point)
1485 }
1486 }
1487
1488 /// Lookup trie value by Unicode Code Point without branching on trie type.
1489 #[inline(always)]
1490 fn get32(&self, code_point: u32) -> T {
1491 if let Some(v) = self.get32_by_fast_index(code_point) {
1492 v
1493 } else if code_point <= CODE_POINT_MAX {
1494 self.as_untyped_ref().get32_by_small_index_cold(code_point)
1495 } else {
1496 self.as_untyped_ref().error_value
1497 }
1498 }
1499
1500 /// Returns the value that is associated with `code_point` in this [`CodePointTrie`]
1501 /// if `code_point` uses fast-path lookup or `None` if `code_point`
1502 /// should use small-path lookup or is above the supported range.
1503 #[inline(always)] // "always" to make the `Option` collapse away
1504 fn get32_by_fast_index(&self, code_point: u32) -> Option<T> {
1505 debug_assert_eq!(Self::TRIE_TYPE, self.as_untyped_ref().header.trie_type);
1506 let fast_max = match Self::TRIE_TYPE {
1507 TrieType::Fast => FAST_TYPE_FAST_INDEXING_MAX,
1508 TrieType::Small => SMALL_TYPE_FAST_INDEXING_MAX,
1509 };
1510 if code_point <= fast_max {
1511 // SAFETY: We just checked the invariant of
1512 // `get32_assuming_fast_index`,
1513 // which is
1514 // "If `self.header.trie_type == TrieType::Small`, `code_point` must be at most
1515 // `SMALL_TYPE_FAST_INDEXING_MAX`. If `self.header.trie_type ==
1516 // TrieType::Fast`, `code_point` must be at most `FAST_TYPE_FAST_INDEXING_MAX`."
1517 // ... assuming that `Self::TRIE_TYPE` always matches
1518 // `self.as_untyped_ref().header.trie_type`, i.e. we're relying on
1519 // `CodePointTrie::to_typed` and `CodePointTrie::as_typed_ref` being correct
1520 // and the exclusive ways of obtaining `Self`.
1521 Some(unsafe { self.as_untyped_ref().get32_assuming_fast_index(code_point) })
1522 } else {
1523 // The caller needs to call `get32_by_small_index` or determine
1524 // that the argument is above the permitted range.
1525 None
1526 }
1527 }
1528
1529 /// Returns a reference to the wrapped `CodePointTrie`.
1530 fn as_untyped_ref(&self) -> &CodePointTrie<'trie, T>;
1531
1532 /// Extracts the wrapped `CodePointTrie`.
1533 fn to_untyped(self) -> CodePointTrie<'trie, T>;
1534}
1535
1536/// Type-safe wrapper for a fast trie guaranteeing
1537/// the the getters don't branch on the trie type
1538/// and for guarenteeing that `get16` is branchless
1539/// in release builds.
1540#[derive(Debug)]
1541#[repr(transparent)]
1542pub struct FastCodePointTrie<'trie, T: TrieValue> {
1543 inner: CodePointTrie<'trie, T>,
1544}
1545
1546impl<'trie, T: TrieValue> TypedCodePointTrie<'trie, T> for FastCodePointTrie<'trie, T> {
1547 const TRIE_TYPE: TrieType = TrieType::Fast;
1548
1549 /// Returns a reference to the wrapped `CodePointTrie`.
1550 #[inline(always)]
1551 fn as_untyped_ref(&self) -> &CodePointTrie<'trie, T> {
1552 &self.inner
1553 }
1554
1555 /// Extracts the wrapped `CodePointTrie`.
1556 #[inline(always)]
1557 fn to_untyped(self) -> CodePointTrie<'trie, T> {
1558 self.inner
1559 }
1560
1561 /// Lookup trie value by Basic Multilingual Plane Code Point without branching on trie type.
1562 #[inline(always)]
1563 fn get16(&self, bmp: u16) -> T {
1564 debug_assert!(u32::from(u16::MAX) <= FAST_TYPE_FAST_INDEXING_MAX);
1565 debug_assert_eq!(Self::TRIE_TYPE, TrieType::Fast);
1566 debug_assert_eq!(self.as_untyped_ref().header.trie_type, TrieType::Fast);
1567 let code_point = u32::from(bmp);
1568 // SAFETY: With `TrieType::Fast`, the `u16` range satisfies
1569 // the invariant of `get32_assuming_fast_index`, which is
1570 // "If `self.header.trie_type == TrieType::Small`, `code_point` must be at most
1571 // `SMALL_TYPE_FAST_INDEXING_MAX`. If `self.header.trie_type ==
1572 // TrieType::Fast`, `code_point` must be at most `FAST_TYPE_FAST_INDEXING_MAX`."
1573 //
1574 // We're relying on `CodePointTrie::to_typed` and `CodePointTrie::as_typed_ref`
1575 // being correct and the exclusive ways of obtaining `Self`.
1576 unsafe { self.as_untyped_ref().get32_assuming_fast_index(code_point) }
1577 }
1578}
1579
1580impl<'trie, T: TrieValue> Seal for FastCodePointTrie<'trie, T> {}
1581
1582impl<'trie, T: TrieValue> TryFrom<&'trie CodePointTrie<'trie, T>>
1583 for &'trie FastCodePointTrie<'trie, T>
1584{
1585 type Error = TypedCodePointTrieError;
1586
1587 fn try_from(
1588 reference: &'trie CodePointTrie<'trie, T>,
1589 ) -> Result<&'trie FastCodePointTrie<'trie, T>, TypedCodePointTrieError> {
1590 match reference.as_typed_ref() {
1591 Typed::Fast(trie) => Ok(trie),
1592 Typed::Small(_) => Err(TypedCodePointTrieError),
1593 }
1594 }
1595}
1596
1597impl<'trie, T: TrieValue> TryFrom<CodePointTrie<'trie, T>> for FastCodePointTrie<'trie, T> {
1598 type Error = TypedCodePointTrieError;
1599
1600 fn try_from(
1601 value: CodePointTrie<'trie, T>,
1602 ) -> Result<FastCodePointTrie<'trie, T>, TypedCodePointTrieError> {
1603 match value.to_typed() {
1604 Typed::Fast(trie) => Ok(trie),
1605 Typed::Small(_) => Err(TypedCodePointTrieError),
1606 }
1607 }
1608}
1609
1610/// Type-safe wrapper for a small trie guaranteeing
1611/// the the getters don't branch on the trie type.
1612#[derive(Debug)]
1613#[repr(transparent)]
1614pub struct SmallCodePointTrie<'trie, T: TrieValue> {
1615 inner: CodePointTrie<'trie, T>,
1616}
1617
1618impl<'trie, T: TrieValue> TypedCodePointTrie<'trie, T> for SmallCodePointTrie<'trie, T> {
1619 const TRIE_TYPE: TrieType = TrieType::Small;
1620
1621 /// Returns a reference to the wrapped `CodePointTrie`.
1622 #[inline(always)]
1623 fn as_untyped_ref(&self) -> &CodePointTrie<'trie, T> {
1624 &self.inner
1625 }
1626
1627 /// Extracts the wrapped `CodePointTrie`.
1628 #[inline(always)]
1629 fn to_untyped(self) -> CodePointTrie<'trie, T> {
1630 self.inner
1631 }
1632}
1633
1634impl<'trie, T: TrieValue> Seal for SmallCodePointTrie<'trie, T> {}
1635
1636impl<'trie, T: TrieValue> TryFrom<&'trie CodePointTrie<'trie, T>>
1637 for &'trie SmallCodePointTrie<'trie, T>
1638{
1639 type Error = TypedCodePointTrieError;
1640
1641 fn try_from(
1642 reference: &'trie CodePointTrie<'trie, T>,
1643 ) -> Result<&'trie SmallCodePointTrie<'trie, T>, TypedCodePointTrieError> {
1644 match reference.as_typed_ref() {
1645 Typed::Fast(_) => Err(TypedCodePointTrieError),
1646 Typed::Small(trie) => Ok(trie),
1647 }
1648 }
1649}
1650
1651impl<'trie, T: TrieValue> TryFrom<CodePointTrie<'trie, T>> for SmallCodePointTrie<'trie, T> {
1652 type Error = TypedCodePointTrieError;
1653
1654 fn try_from(
1655 value: CodePointTrie<'trie, T>,
1656 ) -> Result<SmallCodePointTrie<'trie, T>, TypedCodePointTrieError> {
1657 match value.to_typed() {
1658 Typed::Fast(_) => Err(TypedCodePointTrieError),
1659 Typed::Small(trie) => Ok(trie),
1660 }
1661 }
1662}
1663
1664/// Error indicating that the `TrieType` of an untyped trie
1665/// does not match the requested typed trie type.
1666#[derive(Debug)]
1667#[non_exhaustive]
1668pub struct TypedCodePointTrieError;
1669
1670/// Holder for either fast or small trie with the trie
1671/// type encoded into the Rust type.
1672#[allow(clippy::exhaustive_enums)]
1673#[derive(Debug)]
1674pub enum Typed<F, S> {
1675 /// The trie type is fast.
1676 Fast(F),
1677 /// The trie type is small.
1678 Small(S),
1679}
1680
1681#[cfg(test)]
1682mod tests {
1683 use super::*;
1684 use crate::codepointtrie::planes;
1685 use alloc::vec::Vec;
1686
1687 #[test]
1688 #[cfg(feature = "serde")]
1689 fn test_serde_with_postcard_roundtrip() -> Result<(), postcard::Error> {
1690 let trie = planes::get_planes_trie();
1691 let trie_serialized: Vec<u8> = postcard::to_allocvec(&trie).unwrap();
1692
1693 // Assert an expected (golden data) version of the serialized trie.
1694 const EXP_TRIE_SERIALIZED: &[u8] = &[
1695 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,
1696 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,
1697 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,
1698 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,
1699 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,
1700 2, 144, 2, 144, 2, 144, 2, 176, 2, 176, 2, 176, 2, 176, 2, 208, 2, 208, 2, 208, 2, 208,
1701 2, 240, 2, 240, 2, 240, 2, 240, 2, 16, 3, 16, 3, 16, 3, 16, 3, 48, 3, 48, 3, 48, 3, 48,
1702 3, 80, 3, 80, 3, 80, 3, 80, 3, 112, 3, 112, 3, 112, 3, 112, 3, 144, 3, 144, 3, 144, 3,
1703 144, 3, 176, 3, 176, 3, 176, 3, 176, 3, 208, 3, 208, 3, 208, 3, 208, 3, 240, 3, 240, 3,
1704 240, 3, 240, 3, 16, 4, 16, 4, 16, 4, 16, 4, 48, 4, 48, 4, 48, 4, 48, 4, 80, 4, 80, 4,
1705 80, 4, 80, 4, 112, 4, 112, 4, 112, 4, 112, 4, 0, 0, 16, 0, 32, 0, 48, 0, 64, 0, 80, 0,
1706 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,
1707 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,
1708 0, 0, 0, 16, 0, 32, 0, 48, 0, 0, 0, 16, 0, 32, 0, 48, 0, 128, 0, 128, 0, 128, 0, 128,
1709 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128,
1710 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128,
1711 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144,
1712 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144,
1713 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 144,
1714 0, 144, 0, 144, 0, 144, 0, 144, 0, 144, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160,
1715 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160,
1716 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160, 0, 160,
1717 0, 160, 0, 160, 0, 160, 0, 160, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176,
1718 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176,
1719 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176, 0, 176,
1720 0, 176, 0, 176, 0, 176, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192,
1721 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192,
1722 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192, 0, 192,
1723 0, 192, 0, 192, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208,
1724 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208,
1725 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208, 0, 208,
1726 0, 208, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224,
1727 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224,
1728 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224, 0, 224,
1729 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240,
1730 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240,
1731 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 240, 0, 0,
1732 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,
1733 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,
1734 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,
1735 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,
1736 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,
1737 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,
1738 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,
1739 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,
1740 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,
1741 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,
1742 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,
1743 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,
1744 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,
1745 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,
1746 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,
1747 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,
1748 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,
1749 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 96, 1, 128, 0, 136, 0, 136, 0, 136, 0, 136,
1750 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,
1751 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,
1752 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,
1753 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0,
1754 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 168, 0,
1755 168, 0, 168, 0, 168, 0, 168, 0, 168, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0,
1756 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0,
1757 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0, 200, 0,
1758 200, 0, 200, 0, 200, 0, 200, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0,
1759 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0,
1760 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0, 232, 0,
1761 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,
1762 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,
1763 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,
1764 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,
1765 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,
1766 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,
1767 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,
1768 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 72, 1, 104, 1, 104, 1, 104, 1, 104, 1,
1769 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1,
1770 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1,
1771 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 104, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1,
1772 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1,
1773 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 136, 1,
1774 136, 1, 136, 1, 136, 1, 136, 1, 136, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1,
1775 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1,
1776 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1, 168, 1,
1777 168, 1, 168, 1, 168, 1, 168, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1,
1778 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1,
1779 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1, 200, 1,
1780 200, 1, 200, 1, 200, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1,
1781 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1,
1782 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1, 232, 1,
1783 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,
1784 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,
1785 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,
1786 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,
1787 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,
1788 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,
1789 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,
1790 2, 72, 2, 72, 2, 72, 2, 72, 2, 72, 2, 72, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2,
1791 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2,
1792 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2, 104, 2,
1793 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,
1794 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,
1795 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,
1796 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,
1797 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,
1798 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,
1799 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,
1800 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,
1801 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,
1802 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,
1803 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11,
1804 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
1805 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14,
1806 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15,
1807 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 0,
1808 ];
1809 assert_eq!(trie_serialized, EXP_TRIE_SERIALIZED);
1810
1811 let trie_deserialized = postcard::from_bytes::<CodePointTrie<u8>>(&trie_serialized)?;
1812
1813 assert_eq!(&trie.index, &trie_deserialized.index);
1814 assert_eq!(&trie.data, &trie_deserialized.data);
1815
1816 assert!(!trie_deserialized.index.is_owned());
1817 assert!(!trie_deserialized.data.is_owned());
1818
1819 Ok(())
1820 }
1821
1822 #[test]
1823 fn test_typed() {
1824 let untyped = planes::get_planes_trie();
1825 assert_eq!(untyped.get('\u{10000}'), 1);
1826 let small_ref = <&SmallCodePointTrie<_>>::try_from(&untyped).unwrap();
1827 assert_eq!(small_ref.get('\u{10000}'), 1);
1828 let _ = <&FastCodePointTrie<_>>::try_from(&untyped).is_err();
1829 let small = <SmallCodePointTrie<_>>::try_from(untyped).unwrap();
1830 assert_eq!(small.get('\u{10000}'), 1);
1831 }
1832
1833 #[test]
1834 fn test_get_range() {
1835 let planes_trie = planes::get_planes_trie();
1836
1837 let first_range: Option<CodePointMapRange<u8>> = planes_trie.get_range(0x0);
1838 assert_eq!(
1839 first_range,
1840 Some(CodePointMapRange {
1841 range: 0x0..=0xffff,
1842 value: 0
1843 })
1844 );
1845
1846 let second_range: Option<CodePointMapRange<u8>> = planes_trie.get_range(0x1_0000);
1847 assert_eq!(
1848 second_range,
1849 Some(CodePointMapRange {
1850 range: 0x10000..=0x1ffff,
1851 value: 1
1852 })
1853 );
1854
1855 let penultimate_range: Option<CodePointMapRange<u8>> = planes_trie.get_range(0xf_0000);
1856 assert_eq!(
1857 penultimate_range,
1858 Some(CodePointMapRange {
1859 range: 0xf_0000..=0xf_ffff,
1860 value: 15
1861 })
1862 );
1863
1864 let last_range: Option<CodePointMapRange<u8>> = planes_trie.get_range(0x10_0000);
1865 assert_eq!(
1866 last_range,
1867 Some(CodePointMapRange {
1868 range: 0x10_0000..=0x10_ffff,
1869 value: 16
1870 })
1871 );
1872 }
1873
1874 #[test]
1875 fn databake() {
1876 databake::test_bake!(
1877 CodePointTrie<'static, u32>,
1878 const,
1879 unsafe {
1880 #[allow(unused_unsafe)]
1881 crate::codepointtrie::CodePointTrie::from_parts_unstable_unchecked_v1(
1882 crate::codepointtrie::CodePointTrieHeader {
1883 high_start: 1u32,
1884 shifted12_high_start: 2u16,
1885 index3_null_offset: 3u16,
1886 data_null_offset: 4u32,
1887 null_value: 5u32,
1888 trie_type: crate::codepointtrie::TrieType::Small,
1889 },
1890 zerovec::ZeroVec::new(),
1891 zerovec::ZeroVec::new(),
1892 0u32,
1893 5u32,
1894 )
1895 },
1896 icu_collections,
1897 [zerovec],
1898 );
1899 }
1900}