comm-central/third_party/rust/icu_collections/src/codepointtrie/cptrie.rs

Revision control

Copy as Markdown

Other Tools

// 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
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).
///
#[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<Self, Self::TryFromU32Error>;
/// 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::<Self>()
);
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, Self::TryFromU32Error> {
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<T: TrieValue>(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 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<u8> for TrieType {
type Error = crate::codepointtrie::error::Error;
fn try_from(trie_type_int: u8) -> Result<TrieType, crate::codepointtrie::error::Error> {
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<CodePointTrie<'trie, T>, 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<T>` into `ZeroVec<P>`, 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<u8> = planes::get_planes_trie();
/// let planes_trie_i8: CodePointTrie<i8> =
/// planes_trie_u8.try_into_converted().expect("infallible");
///
/// assert_eq!(planes_trie_i8.get32(0x30000), 3);
/// ```
pub fn try_into_converted<P>(self) -> Result<CodePointTrie<'trie, P>, 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::<T>::new_borrowed(slice);
let error_converted = error_vec.try_into_converted::<P>()?;
#[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<u8> = planes::get_planes_trie();
/// let planes_trie_u16: CodePointTrie<u16> = 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<P, E>(
&self,
mut f: impl FnMut(T) -> Result<P, E>,
) -> Result<CodePointTrie<'trie, P>, E>
where
P: TrieValue,
{
let error_converted = f(self.error_value)?;
let converted_data = self.data.iter().map(f).collect::<Result<ZeroVec<P>, 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<u8> = 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<CodePointMapRange<T>> {
// 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<T> {
let init_range = Some(CodePointMapRange {
range: RangeInclusive::new(u32::MAX, u32::MAX),
value: self.error_value(),
});
CodePointMapRangeIterator::<T> {
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<Item = RangeInclusive<u32>> + '_ {
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<Item = CodePointMapRange<U>> + '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<u32>> 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
<T as zerovec::ule::AsULE>::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<u32>`, and the value is represented as `T`.
#[derive(PartialEq, Eq, Debug, Clone)]
pub struct CodePointMapRange<T> {
/// Range of code points from start to end (inclusive).
pub range: RangeInclusive<u32>,
/// 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<CodePointMapRange<T>>,
}
impl<'a, T: TrieValue> Iterator for CodePointMapRangeIterator<'a, T> {
type Item = CodePointMapRange<T>;
fn next(&mut self) -> Option<Self::Item> {
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<u8> = 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::<CodePointTrie<u8>>(&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<CodePointMapRange<u8>> = planes_trie.get_range(0x0);
assert_eq!(
first_range,
Some(CodePointMapRange {
range: RangeInclusive::new(0x0, 0xffff),
value: 0
})
);
let second_range: Option<CodePointMapRange<u8>> = planes_trie.get_range(0x1_0000);
assert_eq!(
second_range,
Some(CodePointMapRange {
range: RangeInclusive::new(0x10000, 0x1ffff),
value: 1
})
);
let penultimate_range: Option<CodePointMapRange<u8>> = 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<CodePointMapRange<u8>> = 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],
);
}
}