icu_collections/char16trie/
trie.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 zerofrom::ZeroFrom;
6use zerovec::{ZeroSlice, ZeroVec};
7
8// Match-node lead unit values, after masking off intermediate-value bits:
9
10// 00..0f: Branch node. If node!=0 then the length is node+1, otherwise
11// the length is one more than the next byte.
12
13// For a branch sub-node with at most this many entries, we drop down
14// to a linear search.
15const MAX_BRANCH_LINEAR_SUB_NODE_LENGTH: usize = 5;
16
17// 0030..003f: Linear-match node, match 1..16 units and continue reading the next node.
18const MIN_LINEAR_MATCH: u16 = 0x30;
19const MAX_LINEAR_MATCH_LENGTH: u16 = 0x10;
20
21// Match-node lead unit bits 14..6 for the optional intermediate value.
22// If these bits are 0, then there is no intermediate value.
23// Otherwise, see the *NodeValue* constants below.
24const MIN_VALUE_LEAD: u16 = MIN_LINEAR_MATCH + MAX_LINEAR_MATCH_LENGTH; // 0x40
25const NODE_TYPE_MASK: u16 = MIN_VALUE_LEAD - 1; // 0x003f
26
27// A final-value node has bit 15 set.
28const VALUE_IS_FINAL: u16 = 0x8000;
29
30// Compact value: After testing bit 0, shift right by 15 and then use the following thresholds.
31const MAX_ONE_UNIT_VALUE: u16 = 0x3fff;
32
33const MIN_TWO_UNIT_VALUE_LEAD: u16 = MAX_ONE_UNIT_VALUE + 1; // 0x4000
34
35const MAX_ONE_UNIT_NODE_VALUE: u16 = 0xff;
36
37const MIN_TWO_UNIT_NODE_VALUE_LEAD: u16 = MIN_VALUE_LEAD + ((MAX_ONE_UNIT_NODE_VALUE + 1) << 6); // 0x4040
38
39const THREE_UNIT_NODE_VALUE_LEAD: u16 = 0x7fc0;
40
41const THREE_UNIT_VALUE_LEAD: u16 = 0x7fff;
42
43// Compact delta integers.
44const MAX_ONE_UNIT_DELTA: u16 = 0xfbff;
45const MIN_TWO_UNIT_DELTA_LEAD: u16 = MAX_ONE_UNIT_DELTA + 1; // 0xfc00
46const THREE_UNIT_DELTA_LEAD: u16 = 0xffff;
47
48fn skip_value(pos: usize, lead: u16) -> usize {
49    if lead < MIN_TWO_UNIT_VALUE_LEAD {
50        pos
51    } else if lead < THREE_UNIT_VALUE_LEAD {
52        pos + 1
53    } else {
54        pos + 2
55    }
56}
57
58fn skip_node_value(pos: usize, lead: u16) -> usize {
59    if lead < MIN_TWO_UNIT_NODE_VALUE_LEAD {
60        pos
61    } else if lead < THREE_UNIT_NODE_VALUE_LEAD {
62        pos + 1
63    } else {
64        pos + 2
65    }
66}
67
68/// This struct represents a de-serialized `Char16Trie` that was exported from
69/// ICU binary data.
70///
71/// Light-weight, non-const reader class for a `CharsTrie`. Traverses a
72/// char-serialized data structure with minimal state, for mapping 16-bit-unit
73/// sequences to non-negative integer values.
74///
75/// For more information:
76/// - [ICU4C UCharsTrie](https://unicode-org.github.io/icu-docs/apidoc/released/icu4c/classicu_1_1UCharsTrie.html)
77/// - [ICU4J CharsTrie](https://unicode-org.github.io/icu-docs/apidoc/released/icu4j/com/ibm/icu/util/CharsTrie.html) API.
78#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
79#[cfg_attr(feature = "databake", derive(databake::Bake))]
80#[cfg_attr(feature = "databake", databake(path = icu_collections::char16trie))]
81#[derive(Clone, Debug, PartialEq, Eq, ZeroFrom)]
82#[allow(clippy::exhaustive_structs)] // effectively exhaustive, struct-constructible for baking
83pub struct Char16Trie<'data> {
84    /// An array of u16 containing the trie data.
85    #[cfg_attr(feature = "serde", serde(borrow))]
86    #[doc(hidden)] // #2417
87    pub data: ZeroVec<'data, u16>,
88}
89
90impl<'data> Char16Trie<'data> {
91    /// Returns a new [`Char16Trie`] with ownership of the provided data.
92    #[inline]
93    pub fn new(data: ZeroVec<'data, u16>) -> Self {
94        Self { data }
95    }
96
97    /// Returns a new [`Char16TrieIterator`] backed by borrowed data from the `trie` data
98    #[inline]
99    pub fn iter(&self) -> Char16TrieIterator<'_> {
100        Char16TrieIterator::new(&self.data)
101    }
102}
103
104/// This struct represents an iterator over a [`Char16Trie`].
105#[derive(Clone, Debug)]
106pub struct Char16TrieIterator<'a> {
107    /// A reference to the [`Char16Trie`] data to iterate over.
108    trie: &'a ZeroSlice<u16>,
109    /// Index of next trie unit to read, or `None` if there are no more matches.
110    pos: Option<usize>,
111    /// Remaining length of a linear-match node, minus 1, or `None` if not in
112    /// such a node.
113    remaining_match_length: Option<usize>,
114}
115
116/// An enum representing the return value from a lookup in [`Char16Trie`].
117#[derive(Clone, Copy, Debug, PartialEq)]
118#[allow(clippy::exhaustive_enums)]
119pub enum TrieResult {
120    /// The input unit(s) did not continue a matching string.
121    /// Once `next()` returns `TrieResult::NoMatch`, all further calls to `next()`
122    /// will also return `TrieResult::NoMatch`.
123    NoMatch,
124    /// The input unit(s) matched a string but there is no value for the string
125    /// so far.  (It is a prefix of a longer string.)
126    NoValue,
127    /// The input unit(s) continued a matching string and there is a value for
128    /// the string so far. No further input byte/unit can continue a matching
129    /// string.
130    FinalValue(i32),
131    /// The input unit(s) continued a matching string and there is a value for
132    /// the string so far.  Another input byte/unit can continue a matching
133    /// string.
134    Intermediate(i32),
135}
136
137// Get the lead surrogate (0xd800..0xdbff) for a
138// supplementary code point (0x10000..0x10ffff).
139// @param supplementary 32-bit code point (U+10000..U+10ffff)
140// @return lead surrogate (U+d800..U+dbff) for supplementary
141fn u16_lead(supplementary: i32) -> u16 {
142    (((supplementary) >> 10) + 0xd7c0) as u16
143}
144
145// Get the trail surrogate (0xdc00..0xdfff) for a
146// supplementary code point (0x10000..0x10ffff).
147// @param supplementary 32-bit code point (U+10000..U+10ffff)
148// @return trail surrogate (U+dc00..U+dfff) for supplementary
149fn u16_tail(supplementary: i32) -> u16 {
150    (((supplementary) & 0x3ff) | 0xdc00) as u16
151}
152
153/// A macro that takes an `Option` argument and either unwraps it if it has a value or
154/// causes the function to return `TrieResult::NoMatch` if there is no value.
155/// This could perhaps be done with `std::ops::Try` once stabilized.
156macro_rules! trie_unwrap {
157    ($option:expr) => {
158        match $option {
159            Some(x) => x,
160            None => {
161                // Unexpected
162                debug_assert!(false);
163                return TrieResult::NoMatch;
164            }
165        }
166    };
167}
168
169impl<'a> Char16TrieIterator<'a> {
170    /// Returns a new [`Char16TrieIterator`] backed by borrowed data for the `trie` array
171    #[inline]
172    pub fn new(trie: &'a ZeroSlice<u16>) -> Self {
173        Self {
174            trie,
175            pos: Some(0),
176            remaining_match_length: None,
177        }
178    }
179
180    /// Traverses the trie from the current state for this input char.
181    ///
182    /// # Examples
183    ///
184    /// ```
185    /// use icu::collections::char16trie::{Char16Trie, TrieResult};
186    /// use zerovec::ZeroVec;
187    ///
188    /// // A Char16Trie containing the ASCII characters 'a' and 'b'.
189    /// let trie_data = [48, 97, 176, 98, 32868];
190    /// let trie = Char16Trie::new(ZeroVec::from_slice_or_alloc(&trie_data));
191    ///
192    /// let mut iter = trie.iter();
193    /// let res = iter.next('a');
194    /// assert_eq!(res, TrieResult::Intermediate(1));
195    /// let res = iter.next('b');
196    /// assert_eq!(res, TrieResult::FinalValue(100));
197    /// let res = iter.next('c');
198    /// assert_eq!(res, TrieResult::NoMatch);
199    /// ```
200    pub fn next(&mut self, c: char) -> TrieResult {
201        if (c as u32) <= 0xffff {
202            self.next16(c as u16)
203        } else {
204            match self.next16(u16_lead(c as i32)) {
205                TrieResult::NoValue | TrieResult::Intermediate(_) => {
206                    self.next16(u16_tail(c as i32))
207                }
208                _ => TrieResult::NoMatch,
209            }
210        }
211    }
212
213    /// Traverses the trie from the current state for this input char.
214    ///
215    /// # Examples
216    ///
217    /// ```
218    /// use icu::collections::char16trie::{Char16Trie, TrieResult};
219    /// use zerovec::ZeroVec;
220    ///
221    /// // A Char16Trie containing the ASCII characters 'a' and 'b'.
222    /// let trie_data = [48, 97, 176, 98, 32868];
223    /// let trie = Char16Trie::new(ZeroVec::from_slice_or_alloc(&trie_data));
224    ///
225    /// let mut iter = trie.iter();
226    /// let res = iter.next('a');
227    /// assert_eq!(res, TrieResult::Intermediate(1));
228    /// let res = iter.next('b');
229    /// assert_eq!(res, TrieResult::FinalValue(100));
230    /// let res = iter.next('c');
231    /// assert_eq!(res, TrieResult::NoMatch);
232    /// ```
233    pub fn next32(&mut self, c: u32) -> TrieResult {
234        if c <= 0xffff {
235            self.next16(c as u16)
236        } else {
237            match self.next16(u16_lead(c as i32)) {
238                TrieResult::NoValue | TrieResult::Intermediate(_) => {
239                    self.next16(u16_tail(c as i32))
240                }
241                _ => TrieResult::NoMatch,
242            }
243        }
244    }
245
246    /// Traverses the trie from the current state for this input char.
247    ///
248    /// # Examples
249    ///
250    /// ```
251    /// use icu::collections::char16trie::{Char16Trie, TrieResult};
252    /// use zerovec::ZeroVec;
253    ///
254    /// // A Char16Trie containing the ASCII characters 'a' and 'b'.
255    /// let trie_data = [48, 97, 176, 98, 32868];
256    /// let trie = Char16Trie::new(ZeroVec::from_slice_or_alloc(&trie_data));
257    ///
258    /// let mut iter = trie.iter();
259    /// let res = iter.next16('a' as u16);
260    /// assert_eq!(res, TrieResult::Intermediate(1));
261    /// let res = iter.next16('b' as u16);
262    /// assert_eq!(res, TrieResult::FinalValue(100));
263    /// let res = iter.next16('c' as u16);
264    /// assert_eq!(res, TrieResult::NoMatch);
265    /// ```
266    pub fn next16(&mut self, c: u16) -> TrieResult {
267        let mut pos = match self.pos {
268            Some(p) => p,
269            None => return TrieResult::NoMatch,
270        };
271        if let Some(length) = self.remaining_match_length {
272            // Remaining part of a linear-match node
273            if c == trie_unwrap!(self.trie.get(pos)) {
274                pos += 1;
275                self.pos = Some(pos);
276                if length == 0 {
277                    self.remaining_match_length = None;
278                    let node = trie_unwrap!(self.trie.get(pos));
279                    if node >= MIN_VALUE_LEAD {
280                        return self.value_result(pos);
281                    }
282                } else {
283                    self.remaining_match_length = Some(length - 1);
284                }
285                return TrieResult::NoValue;
286            }
287            self.stop();
288            TrieResult::NoMatch
289        } else {
290            self.next_impl(pos, c)
291        }
292    }
293
294    fn branch_next(&mut self, pos: usize, length: usize, in_unit: u16) -> TrieResult {
295        let mut pos = pos;
296        let mut length = length;
297        if length == 0 {
298            length = trie_unwrap!(self.trie.get(pos)) as usize;
299            pos += 1;
300        }
301        length += 1;
302
303        // The length of the branch is the number of units to select from.
304        // The data structure encodes a binary search.
305        while length > MAX_BRANCH_LINEAR_SUB_NODE_LENGTH {
306            if in_unit < trie_unwrap!(self.trie.get(pos)) {
307                length >>= 1;
308                pos = trie_unwrap!(self.jump_by_delta(pos + 1));
309            } else {
310                length = length - (length >> 1);
311                pos = trie_unwrap!(self.skip_delta(pos + 1));
312            }
313        }
314        // Drop down to linear search for the last few bytes.
315        // length>=2 because the loop body above sees length>kMaxBranchLinearSubNodeLength>=3
316        // and divides length by 2.
317        loop {
318            if in_unit == trie_unwrap!(self.trie.get(pos)) {
319                pos += 1;
320                let mut node = trie_unwrap!(self.trie.get(pos));
321                if node & VALUE_IS_FINAL != 0 {
322                    self.pos = Some(pos);
323                    return self.value_result(pos);
324                }
325                // Use the non-final value as the jump delta.
326                pos += 1;
327
328                if node < MIN_TWO_UNIT_VALUE_LEAD {
329                    pos += node as usize;
330                } else if node < THREE_UNIT_VALUE_LEAD {
331                    pos += (((node - MIN_TWO_UNIT_VALUE_LEAD) as u32) << 16) as usize
332                        | trie_unwrap!(self.trie.get(pos)) as usize;
333                    pos += 1;
334                } else {
335                    pos += ((trie_unwrap!(self.trie.get(pos)) as usize) << 16)
336                        | trie_unwrap!(self.trie.get(pos + 1)) as usize;
337                    pos += 2;
338                }
339                node = trie_unwrap!(self.trie.get(pos));
340                self.pos = Some(pos);
341
342                if node >= MIN_VALUE_LEAD {
343                    return self.value_result(pos);
344                }
345                return TrieResult::NoValue;
346            }
347            length -= 1;
348            pos = trie_unwrap!(self.skip_value(pos + 1));
349            if length <= 1 {
350                break;
351            }
352        }
353
354        if in_unit == trie_unwrap!(self.trie.get(pos)) {
355            pos += 1;
356            self.pos = Some(pos);
357            let node = trie_unwrap!(self.trie.get(pos));
358            if node >= MIN_VALUE_LEAD {
359                return self.value_result(pos);
360            }
361            TrieResult::NoValue
362        } else {
363            self.stop();
364            TrieResult::NoMatch
365        }
366    }
367
368    fn next_impl(&mut self, pos: usize, in_unit: u16) -> TrieResult {
369        let mut node = trie_unwrap!(self.trie.get(pos));
370        let mut pos = pos + 1;
371        loop {
372            if node < MIN_LINEAR_MATCH {
373                return self.branch_next(pos, node as usize, in_unit);
374            } else if node < MIN_VALUE_LEAD {
375                // Match the first of length+1 units.
376                let length = node - MIN_LINEAR_MATCH;
377                if in_unit == trie_unwrap!(self.trie.get(pos)) {
378                    pos += 1;
379                    if length == 0 {
380                        self.remaining_match_length = None;
381                        self.pos = Some(pos);
382                        node = trie_unwrap!(self.trie.get(pos));
383                        if node >= MIN_VALUE_LEAD {
384                            return self.value_result(pos);
385                        }
386                        return TrieResult::NoValue;
387                    }
388                    self.remaining_match_length = Some(length as usize - 1);
389                    self.pos = Some(pos);
390                    return TrieResult::NoValue;
391                }
392                // No match
393                break;
394            } else if (node & VALUE_IS_FINAL) != 0 {
395                // No further matching units.
396                break;
397            } else {
398                // Skip intermediate value.
399                pos = skip_node_value(pos, node);
400                node &= NODE_TYPE_MASK;
401            }
402        }
403        self.stop();
404        TrieResult::NoMatch
405    }
406
407    fn stop(&mut self) {
408        self.pos = None;
409    }
410
411    #[inline(always)] // 1 call site and we want the Option to go away
412    fn jump_by_delta(&self, pos: usize) -> Option<usize> {
413        let delta = self.trie.get(pos)?;
414        let v = if delta < MIN_TWO_UNIT_DELTA_LEAD {
415            // nothing to do
416            pos + 1 + delta as usize
417        } else if delta == THREE_UNIT_DELTA_LEAD {
418            let delta =
419                ((self.trie.get(pos + 1)? as usize) << 16) | (self.trie.get(pos + 2)? as usize);
420            pos + delta + 3
421        } else {
422            let delta = (((delta - MIN_TWO_UNIT_DELTA_LEAD) as usize) << 16)
423                | (self.trie.get(pos + 1)? as usize);
424            pos + delta + 2
425        };
426        Some(v)
427    }
428
429    #[inline(always)] // 1 call site and we want the Option to go away
430    fn skip_value(&self, pos: usize) -> Option<usize> {
431        let lead_unit = self.trie.get(pos)?;
432        Some(skip_value(pos + 1, lead_unit & 0x7fff))
433    }
434
435    #[inline(always)] // 1 call site and we want the Option to go away
436    fn skip_delta(&self, pos: usize) -> Option<usize> {
437        let delta = self.trie.get(pos)?;
438        let v = if delta < MIN_TWO_UNIT_DELTA_LEAD {
439            pos + 1
440        } else if delta == THREE_UNIT_DELTA_LEAD {
441            pos + 3
442        } else {
443            pos + 2
444        };
445        Some(v)
446    }
447
448    fn value_result(&self, pos: usize) -> TrieResult {
449        match self.get_value(pos) {
450            Some(result) => result,
451            None => {
452                // Unexpected
453                debug_assert!(false);
454                TrieResult::NoMatch
455            }
456        }
457    }
458
459    #[inline(always)] // 1 call site and we want the Option to go away
460    fn get_value(&self, pos: usize) -> Option<TrieResult> {
461        let lead_unit = self.trie.get(pos)?;
462        if lead_unit & VALUE_IS_FINAL == VALUE_IS_FINAL {
463            self.read_value(pos + 1, lead_unit & 0x7fff)
464                .map(TrieResult::FinalValue)
465        } else {
466            self.read_node_value(pos + 1, lead_unit)
467                .map(TrieResult::Intermediate)
468        }
469    }
470
471    #[inline(always)] // 1 call site and we want the Option to go away
472    fn read_value(&self, pos: usize, lead_unit: u16) -> Option<i32> {
473        let v = if lead_unit < MIN_TWO_UNIT_VALUE_LEAD {
474            lead_unit.into()
475        } else if lead_unit < THREE_UNIT_VALUE_LEAD {
476            (((lead_unit - MIN_TWO_UNIT_VALUE_LEAD) as i32) << 16) | self.trie.get(pos)? as i32
477        } else {
478            ((self.trie.get(pos)? as i32) << 16) | self.trie.get(pos + 1)? as i32
479        };
480        Some(v)
481    }
482
483    #[inline(always)] // 1 call site and we want the Option to go away
484    fn read_node_value(&self, pos: usize, lead_unit: u16) -> Option<i32> {
485        let v = if lead_unit < (MIN_TWO_UNIT_NODE_VALUE_LEAD) {
486            ((lead_unit >> 6) - 1).into()
487        } else if lead_unit < THREE_UNIT_NODE_VALUE_LEAD {
488            ((((lead_unit & 0x7fc0) - MIN_TWO_UNIT_NODE_VALUE_LEAD) as i32) << 10)
489                | self.trie.get(pos)? as i32
490        } else {
491            ((self.trie.get(pos)? as i32) << 16) | self.trie.get(pos + 1)? as i32
492        };
493        Some(v)
494    }
495}
icu_collections/char16trie/trie.rs

icu_collections/char16trie/
trie.rs
