zerotrie 0.2.4

// This file is part of ICU4X. For terms of use, please see the file
// called LICENSE at the top level of the ICU4X source tree
// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ).

//! # Internal layout of [`ZeroTrie`](crate::ZeroTrie)
//!
//! A [`ZeroTrie`](crate::ZeroTrie) is composed of a series of nodes stored in sequence in a byte slice.
//!
//! There are 4 types of nodes:
//!
//! 1. ASCII (`0xxxxxxx`): matches a literal ASCII byte.
//! 2. Span (`101xxxxx`): matches a span of non-ASCII bytes.
//! 3. Value (`100xxxxx`): associates a value with a string
//! 4. Branch (`11xxxxxx`): matches one of a set of bytes.
//!
//! Span, Value, and Branch nodes contain a varint, which has different semantics for each:
//!
//! - Span varint: length of the span
//! - Value varint: value associated with the string
//! - Branch varint: number of edges in the branch and width of the offset table
//!
//! If reading an ASCII, Span, or Branch node, one or more bytes are consumed from the input
//! string. If the next byte(s) in the input string do not match the node, we return `None`.
//! If reading a Value node, if the string is empty, return `Some(value)`; otherwise, we skip
//! the Value node and continue on to the next node.
//!
//! When a node is consumed, a shorter, well-formed [`ZeroTrie`](crate::ZeroTrie) remains.
//!
//! ### Basic Example
//!
//! Here is an example [`ZeroTrie`](crate::ZeroTrie) without branch nodes:
//!
//! ```
//! use zerotrie::ZeroTriePerfectHash;
//!
//! let bytes = [
//!     b'a',       // ASCII literal
//!     0b10001010, // value 10
//!     b'b',       // ASCII literal
//!     0b10100011, // span of 3
//!     0x81,       // first byte in span
//!     0x91,       // second byte in span
//!     0xA1,       // third and final byte in span
//!     0b10000100, // value 4
//! ];
//!
//! let trie = ZeroTriePerfectHash::from_bytes(&bytes);
//!
//! // First value: "a" → 10
//! assert_eq!(trie.get(b"a"), Some(10));
//!
//! // Second value: "ab\x81\x91\xA1" → 4
//! assert_eq!(trie.get(b"ab\x81\x91\xA1"), Some(4));
//!
//! // A few examples of strings that do NOT have values in the trie:
//! assert_eq!(trie.get(b"ab"), None);
//! assert_eq!(trie.get(b"b"), None);
//! assert_eq!(trie.get(b"b\x81\x91\xA1"), None);
//! ```
//!
//! ## Branch Nodes
//!
//! There are two types of branch nodes: binary search and perfect hash. `ZeroTrieSimpleAscii`
//! contains only binary search nodes, whereas `ZeroTriePerfectHash` can contain either.
//!
//! The head node of the branch has a varint that encodes two things:
//!
//! - Bottom 8 bits: number of edges in the branch (`N`); if N = 0, set N to 256
//! - Bits 9 and 10: width of the offset table (`W`)
//!
//! Note that N is always in the range [1, 256]. There can't be more than 256 edges because
//! there are only 256 unique u8 values.
//!
//! A few examples of the head node of the branch:
//!
//! - `0b11000000`: varint bits `0`: N = 0 which means N = 256; W = 0
//! - `0b11000110`: varint bits `110`: N = 6; W = 0
//! - `0b11100000 0b00000101`: varint bits `1000101`: N = 69; W = 0
//! - `0b11100010 0b00000000`: varint bits `101000000`: N = 64; W = 1
//!
//! In `ZeroTriePerfectHash`, if N <= 15, the branch is assumed to be a binary search, and if
//! N > 15, the branch is assumed to be a perfect hash.
//!
//! ### Binary Search Branch Nodes
//!
//! A binary search branch node is used when:
//!
//! 1. The trie is a `ZeroTrieSimpleAscii`, OR
//! 2. There are 15 or fewer items in the branch.
//!
//! The head branch node is followed by N sorted bytes. When evaluating a branch node, one byte
//! is consumed from the input. If it is one of the N sorted bytes (scanned using binary search),
//! the index `i` of the byte within the list is used to index into the offset table (described
//! below). If the byte is not in the list, the string is not in the trie, so return `None`.
//!
//! ### Perfect Hash Branch Nodes
//!
//! A perfect hash branch node is used when:
//!
//! 1. The trie is NOT a `ZeroTrieSimpleAscii`, AND
//! 2. There are 16 or more items in the branch.
//!
//! The head branch node is followed by 1 byte containing parameter `p`, N bytes containing
//! parameters `q`, and N bytes containing the bytes to match. From these parameters, either an
//! index within the hash table `i` is resolved and used as input to index into the offset
//! table (described below), or the value is determined to not be present and `None` is
//! returned. For more detail on resolving the perfect hash function, see [`crate::byte_phf`].
//!
//! ### Offset Tables
//!
//! The _offset table_ encodes the range of the remaining buffer containing the trie reachable
//! from the byte matched in the branch node. Both types of branch nodes include an offset
//! table followig the key lookup. Given the index `i` from the first step, the range
//! `[s_i, s_(i+1))` brackets the next step in the trie.
//!
//! Offset tables utilize the `W` parameter stored in the branch head node. The special case
//! when `W == 0`, with `N - 1` bytes, is easiest to understand:
//!
//! **Offset table, W = 0:** `[s_1, s_2, ..., s_(N-1)]`
//!
//! Note that `s_0` is always 0 and `s_N` is always the length of the remaining slice, so those
//! values are not explicitly included in the offset table.
//!
//! When W > 0, the high and low bits of the offsets are in separate bytes, arranged as follows:
//!
//! **Generalized offset table:** `[a_1, a_2, ..., a_(N-1), b_1, b_2, ..., b_(N-1), c_1, ...]`
//!
//! where `s_i = (a_i << 8 + b_i) << 8 + c_i ...` (high bits first, low bits last)
//!
//! ### Advanced Example
//!
//! The following trie encodes the following map. It has multiple varints and branch nodes, which
//! are all binary search with W = 0. Note that there is a value for the empty string.
//!
//! - "" → 0
//! - "axb" → 100
//! - "ayc" → 2
//! - "azd" → 3
//! - "bxe" → 4
//! - "bxefg" → 500
//! - "bxefh" → 6
//! - "bxei" → 7
//! - "bxeikl" → 8
//!
//! ```
//! use zerotrie::ZeroTrieSimpleAscii;
//!
//! let bytes = [
//!     0b10000000, // value 0
//!     0b11000010, // branch of 2
//!     b'a',       //
//!     b'b',       //
//!     13,         //
//!     0b11000011, // start of 'a' subtree: branch of 3
//!     b'x',       //
//!     b'y',       //
//!     b'z',       //
//!     3,          //
//!     5,          //
//!     b'b',       //
//!     0b10010000, // value 100 (lead)
//!     0x54,       // value 100 (trail)
//!     b'c',       //
//!     0b10000010, // value 2
//!     b'd',       //
//!     0b10000011, // value 3
//!     b'x',       // start of 'b' subtree
//!     b'e',       //
//!     0b10000100, // value 4
//!     0b11000010, // branch of 2
//!     b'f',       //
//!     b'i',       //
//!     7,          //
//!     0b11000010, // branch of 2
//!     b'g',       //
//!     b'h',       //
//!     2,          //
//!     0b10010011, // value 500 (lead)
//!     0x64,       // value 500 (trail)
//!     0b10000110, // value 6
//!     0b10000111, // value 7
//!     b'k',       //
//!     b'l',       //
//!     0b10001000, // value 8
//! ];
//!
//! let trie = ZeroTrieSimpleAscii::from_bytes(&bytes);
//!
//! // Assert that the specified items are in the map
//! assert_eq!(trie.get(b""), Some(0));
//! assert_eq!(trie.get(b"axb"), Some(100));
//! assert_eq!(trie.get(b"ayc"), Some(2));
//! assert_eq!(trie.get(b"azd"), Some(3));
//! assert_eq!(trie.get(b"bxe"), Some(4));
//! assert_eq!(trie.get(b"bxefg"), Some(500));
//! assert_eq!(trie.get(b"bxefh"), Some(6));
//! assert_eq!(trie.get(b"bxei"), Some(7));
//! assert_eq!(trie.get(b"bxeikl"), Some(8));
//!
//! // Assert that some other items are not in the map
//! assert_eq!(trie.get(b"a"), None);
//! assert_eq!(trie.get(b"bx"), None);
//! assert_eq!(trie.get(b"xba"), None);
//! ```

use crate::byte_phf::PerfectByteHashMap;
use crate::cursor::AsciiProbeResult;
use crate::helpers::*;
use crate::options::*;
use crate::varint::read_varint_meta2;
use crate::varint::read_varint_meta3;

#[cfg(feature = "alloc")]
use alloc::string::String;

/// Given a slice starting with an offset table, returns the trie for the given index.
///
/// Arguments:
/// - `trie` = a trie pointing at an offset table (after the branch node and search table)
/// - `i` = the desired index within the offset table
/// - `n` = the number of items in the offset table
/// - `w` = the width of the offset table items minus one
#[inline]
fn get_branch(mut trie: &[u8], i: usize, n: usize, mut w: usize) -> &[u8] {
    let mut p = 0usize;
    let mut q = 0usize;
    loop {
        let indices;
        (indices, trie) = trie.debug_split_at(n - 1);
        p = (p << 8)
            + if i == 0 {
                0
            } else {
                *indices.get(i - 1).debug_unwrap_or(&0) as usize
            };
        q = match indices.get(i) {
            Some(x) => (q << 8) + *x as usize,
            None => trie.len(),
        };
        if w == 0 {
            break;
        }
        w -= 1;
    }
    trie.get(p..q).debug_unwrap_or(&[])
}

/// Version of [`get_branch()`] specialized for the case `w == 0` for performance
#[inline]
fn get_branch_w0(mut trie: &[u8], i: usize, n: usize) -> &[u8] {
    let indices;
    (indices, trie) = trie.debug_split_at(n - 1);
    let p = if i == 0 {
        0
    } else {
        *indices.get(i - 1).debug_unwrap_or(&0) as usize
    };
    let q = match indices.get(i) {
        Some(x) => *x as usize,
        None => trie.len(),
    };
    trie.get(p..q).debug_unwrap_or(&[])
}

/// The node type. See the module-level docs for more explanation of the four node types.
enum NodeType {
    /// An ASCII node. Contains a single literal ASCII byte and no varint.
    Ascii,
    /// A span node. Contains a varint indicating how big the span is.
    Span,
    /// A value node. Contains a varint representing the value.
    Value,
    /// A branch node. Contains a varint of the number of output nodes, plus W in the high bits.
    Branch,
}

impl core::fmt::Debug for NodeType {
    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
        use NodeType::*;
        f.write_str(match *self {
            Ascii => "a",
            Span => "s",
            Value => "v",
            Branch => "m",
        })
    }
}

#[inline]
fn byte_type(b: u8) -> NodeType {
    match b & 0b11100000 {
        0b10000000 => NodeType::Value,
        0b10100000 => NodeType::Span,
        0b11000000 => NodeType::Branch,
        0b11100000 => NodeType::Branch,
        _ => NodeType::Ascii,
    }
}

#[inline]
pub(crate) fn get_parameterized<T: ZeroTrieWithOptions + ?Sized>(
    mut trie: &[u8],
    mut ascii: &[u8],
) -> Option<usize> {
    loop {
        let (b, x, i, search);
        (b, trie) = trie.split_first()?;
        let byte_type = byte_type(*b);
        (x, trie) = match byte_type {
            NodeType::Ascii => (0, trie),
            NodeType::Span => {
                if matches!(T::OPTIONS.ascii_mode, AsciiMode::BinarySpans) {
                    read_varint_meta3(*b, trie)
                } else {
                    debug_assert!(false, "Span node found in ASCII trie!");
                    return None;
                }
            }
            NodeType::Value => read_varint_meta3(*b, trie),
            NodeType::Branch => read_varint_meta2(*b, trie),
        };
        if let Some((c, temp)) = ascii.split_first() {
            if matches!(byte_type, NodeType::Ascii) {
                let is_match = if matches!(T::OPTIONS.case_sensitivity, CaseSensitivity::IgnoreCase)
                {
                    b.eq_ignore_ascii_case(c)
                } else {
                    b == c
                };
                if is_match {
                    // Matched a byte
                    ascii = temp;
                    continue;
                } else {
                    // Byte that doesn't match
                    return None;
                }
            }
            if matches!(byte_type, NodeType::Value) {
                // Value node, but not at end of string
                continue;
            }
            if matches!(T::OPTIONS.ascii_mode, AsciiMode::BinarySpans)
                && matches!(byte_type, NodeType::Span)
            {
                let (trie_span, ascii_span);
                (trie_span, trie) = trie.debug_split_at(x);
                (ascii_span, ascii) = ascii.split_at_checked(x)?;
                if trie_span == ascii_span {
                    // Matched a byte span
                    continue;
                } else {
                    // Byte span that doesn't match
                    return None;
                }
            }
            // Branch node
            let (x, w) = if x >= 256 { (x & 0xff, x >> 8) } else { (x, 0) };
            let w = if matches!(T::OPTIONS.capacity_mode, CapacityMode::Extended) {
                w
            } else {
                // See the table below regarding this assertion
                debug_assert!(w <= 3, "get: w > 3 but we assume w <= 3");
                w & 0x3
            };
            let x = if x == 0 { 256 } else { x };
            if matches!(T::OPTIONS.phf_mode, PhfMode::BinaryOnly) || x < 16 {
                // binary search
                (search, trie) = trie.debug_split_at(x);
                let bsearch_result =
                    if matches!(T::OPTIONS.case_sensitivity, CaseSensitivity::IgnoreCase) {
                        search.binary_search_by_key(&c.to_ascii_lowercase(), |x| {
                            x.to_ascii_lowercase()
                        })
                    } else {
                        search.binary_search(c)
                    };
                i = bsearch_result.ok()?;
            } else {
                // phf
                (search, trie) = trie.debug_split_at(x * 2 + 1);
                i = PerfectByteHashMap::from_store(search).get(*c)?;
            }
            trie = if w == 0 {
                get_branch_w0(trie, i, x)
            } else {
                get_branch(trie, i, x, w)
            };
            ascii = temp;
            continue;
        } else {
            if matches!(byte_type, NodeType::Value) {
                // Value node at end of string
                return Some(x);
            }
            return None;
        }
    }
}

// DISCUSS: This function is 7% faster *on aarch64* if we assert a max on w.
//
// | Bench         | No Assert, x86_64 | No Assert, aarch64 | Assertion, x86_64 | Assertion, aarch64 |
// |---------------|-------------------|--------------------|-------------------|--------------------|
// | basic         | ~187.51 ns        | ~97.586 ns         | ~199.11 ns        | ~99.236 ns         |
// | subtags_10pct | ~9.5557 µs        | ~4.8696 µs         | ~9.5779 µs        | ~4.5649 µs         |
// | subtags_full  | ~137.75 µs        | ~76.016 µs         | ~142.02 µs        | ~70.254 µs         |

/// Steps one node into the trie assuming all branch nodes are binary search and that
/// there are no span nodes.
///
/// The input-output argument `trie` starts at the original trie and ends pointing to
/// the sub-trie reachable by `c`.
#[inline]
pub(crate) fn step_parameterized<T: ZeroTrieWithOptions + ?Sized>(
    trie: &mut &[u8],
    c: u8,
) -> Option<u8> {
    // Currently, the only option `step_parameterized` supports is `CaseSensitivity::IgnoreCase`.
    // `AsciiMode::BinarySpans` is tricky because the state can no longer be simply a trie.
    // If a span node is encountered, `None` is returned later in this function.
    debug_assert!(
        matches!(T::OPTIONS.ascii_mode, AsciiMode::AsciiOnly),
        "Spans not yet implemented in step function"
    );
    // PHF can be easily implemented but the code is not yet reachable
    debug_assert!(
        matches!(T::OPTIONS.phf_mode, PhfMode::BinaryOnly),
        "PHF not yet implemented in step function"
    );
    // Extended Capacity can be easily implemented but the code is not yet reachable
    debug_assert!(
        matches!(T::OPTIONS.capacity_mode, CapacityMode::Normal),
        "Extended capacity not yet implemented in step function"
    );
    let (mut b, x, search);
    loop {
        (b, *trie) = match trie.split_first() {
            Some(v) => v,
            None => {
                // Empty trie or only a value node
                return None;
            }
        };
        match byte_type(*b) {
            NodeType::Ascii => {
                let is_match = if matches!(T::OPTIONS.case_sensitivity, CaseSensitivity::IgnoreCase)
                {
                    b.eq_ignore_ascii_case(&c)
                } else {
                    *b == c
                };
                if is_match {
                    // Matched a byte
                    return Some(*b);
                } else {
                    // Byte that doesn't match
                    *trie = &[];
                    return None;
                }
            }
            NodeType::Branch => {
                // Proceed to the branch node logic below
                (x, *trie) = read_varint_meta2(*b, trie);
                break;
            }
            NodeType::Span => {
                // Question: Should we put the trie back into a valid state?
                // Currently this code is unreachable so let's not worry about it.
                debug_assert!(false, "Span node found in ASCII trie!");
                return None;
            }
            NodeType::Value => {
                // Skip the value node and go to the next node
                (_, *trie) = read_varint_meta3(*b, trie);
                continue;
            }
        };
    }
    // Branch node
    let (x, w) = if x >= 256 { (x & 0xff, x >> 8) } else { (x, 0) };
    // See comment above regarding this assertion
    debug_assert!(w <= 3, "get: w > 3 but we assume w <= 3");
    let w = w & 0x3;
    let x = if x == 0 { 256 } else { x };
    // Always use binary search
    (search, *trie) = trie.debug_split_at(x);
    let bsearch_result = if matches!(T::OPTIONS.case_sensitivity, CaseSensitivity::IgnoreCase) {
        search.binary_search_by_key(&c.to_ascii_lowercase(), |x| x.to_ascii_lowercase())
    } else {
        search.binary_search(&c)
    };
    match bsearch_result {
        Ok(i) => {
            // Matched a byte
            *trie = if w == 0 {
                get_branch_w0(trie, i, x)
            } else {
                get_branch(trie, i, x, w)
            };
            #[allow(clippy::indexing_slicing)] // i is from a binary search
            Some(search[i])
        }
        Err(_) => {
            // Byte that doesn't match
            *trie = &[];
            None
        }
    }
}

/// Steps one node into the trie, assuming all branch nodes are binary search and that
/// there are no span nodes, using an index.
///
/// The input-output argument `trie` starts at the original trie and ends pointing to
/// the sub-trie indexed by `index`.
#[inline]
pub(crate) fn probe_parameterized<T: ZeroTrieWithOptions + ?Sized>(
    trie: &mut &[u8],
    index: usize,
) -> Option<AsciiProbeResult> {
    // Currently, the only option `step_parameterized` supports is `CaseSensitivity::IgnoreCase`.
    // `AsciiMode::BinarySpans` is tricky because the state can no longer be simply a trie.
    // If a span node is encountered, `None` is returned later in this function.
    debug_assert!(
        matches!(T::OPTIONS.ascii_mode, AsciiMode::AsciiOnly),
        "Spans not yet implemented in step function"
    );
    // PHF can be easily implemented but the code is not yet reachable
    debug_assert!(
        matches!(T::OPTIONS.phf_mode, PhfMode::BinaryOnly),
        "PHF not yet implemented in step function"
    );
    // Extended Capacity can be easily implemented but the code is not yet reachable
    debug_assert!(
        matches!(T::OPTIONS.capacity_mode, CapacityMode::Normal),
        "Extended capacity not yet implemented in step function"
    );
    let (mut b, x, search);
    loop {
        (b, *trie) = match trie.split_first() {
            Some(v) => v,
            None => {
                // Empty trie or only a value node
                return None;
            }
        };
        match byte_type(*b) {
            NodeType::Ascii => {
                if index > 0 {
                    *trie = &[];
                    return None;
                }
                return Some(AsciiProbeResult {
                    byte: *b,
                    total_siblings: 1,
                });
            }
            NodeType::Branch => {
                // Proceed to the branch node logic below
                (x, *trie) = read_varint_meta2(*b, trie);
                break;
            }
            NodeType::Span => {
                // Question: Should we put the trie back into a valid state?
                // Currently this code is unreachable so let's not worry about it.
                debug_assert!(false, "Span node found in ASCII trie!");
                return None;
            }
            NodeType::Value => {
                // Skip the value node and go to the next node
                (_, *trie) = read_varint_meta3(*b, trie);
                continue;
            }
        };
    }
    // Branch node
    let (x, w) = if x >= 256 { (x & 0xff, x >> 8) } else { (x, 0) };
    debug_assert!(u8::try_from(x).is_ok());
    let total_siblings = x as u8;
    // See comment above regarding this assertion
    debug_assert!(w <= 3, "get: w > 3 but we assume w <= 3");
    let w = w & 0x3;
    let x = if x == 0 { 256 } else { x };
    if index >= x {
        *trie = &[];
        return None;
    }
    (search, *trie) = trie.debug_split_at(x);
    *trie = if w == 0 {
        get_branch_w0(trie, index, x)
    } else {
        get_branch(trie, index, x, w)
    };
    Some(AsciiProbeResult {
        #[allow(clippy::indexing_slicing)] // index < x, the length of search
        byte: search[index],
        total_siblings,
    })
}

/// Steps one node into the trie if the head node is a value node, returning the value.
/// If the head node is not a value node, no change is made.
///
/// The input-output argument `trie` starts at the original trie and ends pointing to
/// the sub-trie with the value node removed.
pub(crate) fn take_value(trie: &mut &[u8]) -> Option<usize> {
    let (b, new_trie) = trie.split_first()?;
    match byte_type(*b) {
        NodeType::Ascii | NodeType::Span | NodeType::Branch => None,
        NodeType::Value => {
            let x;
            (x, *trie) = read_varint_meta3(*b, new_trie);
            Some(x)
        }
    }
}

#[cfg(feature = "alloc")]
use alloc::vec::Vec;

/// Iterator type for walking the byte sequences contained in a [`ZeroTrie`](crate::ZeroTrie).
///
/// ✨ *Enabled with the `alloc` Cargo feature.*
#[cfg(feature = "alloc")]
#[derive(Debug)]
pub struct ZeroTrieIterator<'a> {
    /// Whether the PHF is enabled on this trie.
    use_phf: bool,
    /// Intermediate state during iteration:
    /// 1. A trie (usually a slice of the original, bigger trie)
    /// 2. The string that leads to the trie
    /// 3. If the trie's lead node is a branch node, the current index being evaluated
    state: Vec<(&'a [u8], Vec<u8>, usize)>,
}

#[cfg(feature = "alloc")]
impl<'a> ZeroTrieIterator<'a> {
    pub(crate) fn new<S: AsRef<[u8]> + ?Sized>(store: &'a S, use_phf: bool) -> Self {
        ZeroTrieIterator {
            use_phf,
            state: alloc::vec![(store.as_ref(), alloc::vec![], 0)],
        }
    }
}

#[cfg(feature = "alloc")]
impl Iterator for ZeroTrieIterator<'_> {
    type Item = (Vec<u8>, usize);
    fn next(&mut self) -> Option<Self::Item> {
        let (mut trie, mut string, mut branch_idx);
        (trie, string, branch_idx) = self.state.pop()?;
        loop {
            let (b, x, span, search);
            let return_trie = trie;
            (b, trie) = match trie.split_first() {
                Some(tpl) => tpl,
                None => {
                    // At end of current branch; step back to the branch node.
                    // If there are no more branches, we are finished.
                    (trie, string, branch_idx) = self.state.pop()?;
                    continue;
                }
            };
            let byte_type = byte_type(*b);
            if matches!(byte_type, NodeType::Ascii) {
                string.push(*b);
                continue;
            }
            (x, trie) = match byte_type {
                NodeType::Ascii => (0, trie),
                NodeType::Span | NodeType::Value => read_varint_meta3(*b, trie),
                NodeType::Branch => read_varint_meta2(*b, trie),
            };
            if matches!(byte_type, NodeType::Span) {
                (span, trie) = trie.debug_split_at(x);
                string.extend(span);
                continue;
            }
            if matches!(byte_type, NodeType::Value) {
                let retval = string.clone();
                // Return to this position on the next step
                self.state.push((trie, string, 0));
                return Some((retval, x));
            }
            // Match node
            let (x, w) = if x >= 256 { (x & 0xff, x >> 8) } else { (x, 0) };
            let x = if x == 0 { 256 } else { x };
            if branch_idx + 1 < x {
                // Return to this branch node at the next index
                self.state
                    .push((return_trie, string.clone(), branch_idx + 1));
            }
            let byte = if x < 16 || !self.use_phf {
                // binary search
                (search, trie) = trie.debug_split_at(x);
                debug_unwrap!(search.get(branch_idx), return None)
            } else {
                // phf
                (search, trie) = trie.debug_split_at(x * 2 + 1);
                debug_unwrap!(search.get(branch_idx + x + 1), return None)
            };
            string.push(*byte);
            trie = if w == 0 {
                get_branch_w0(trie, branch_idx, x)
            } else {
                get_branch(trie, branch_idx, x, w)
            };
            branch_idx = 0;
        }
    }
}

#[cfg(feature = "alloc")]
pub(crate) fn get_iter_phf<S: AsRef<[u8]> + ?Sized>(store: &S) -> ZeroTrieIterator<'_> {
    ZeroTrieIterator::new(store, true)
}

/// # Panics
/// Panics if the trie contains non-ASCII items.
#[cfg(feature = "alloc")]
#[expect(clippy::type_complexity)]
pub(crate) fn get_iter_ascii_or_panic<S: AsRef<[u8]> + ?Sized>(
    store: &S,
) -> core::iter::Map<ZeroTrieIterator<'_>, fn((Vec<u8>, usize)) -> (String, usize)> {
    ZeroTrieIterator::new(store, false).map(|(k, v)| {
        #[expect(clippy::unwrap_used)] // in signature of function
        let ascii_str = String::from_utf8(k).unwrap();
        (ascii_str, v)
    })
}